Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:plunky:20140725060400

Diff

Diff from 1.90 to:

Annotations

Annotate by Age | Author | Mixed | None
/fisheye/browse/pcc/pcc/mip/optim2.c

Annotated File View

plunky
1.90
1 /*      $Id: optim2.c,v 1.90 2014/07/25 06:04:00 plunky Exp $   */
ragge
1.1
2 /*
3  * Copyright (c) 2004 Anders Magnusson (ragge@ludd.luth.se).
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 3. The name of the author may not be used to endorse or promote products
15  *    derived from this software without specific prior written permission
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "pass2.h"
30
ragge
1.3
31 #include <string.h>
pj
1.4
32 #include <stdlib.h>
33
34 #ifndef MIN
35 #define MIN(a,b) (((a)<(b))?(a):(b))
36 #endif
37
38 #ifndef MAX
39 #define MAX(a,b) (((a) > (b)) ? (a) : (b))
40 #endif
ragge
1.3
41
ragge
1.30
42 #define BDEBUG(x)       if (b2debug) printf x
43
ragge
1.50
44 #define mktemp(n, t)    mklnode(TEMP, 0, n, t)
45
ragge
1.79
46 #define CHADD(bb,c)     { if (bb->ch[0] == 0) bb->ch[0] = c; \
47                           else if (bb->ch[1] == 0bb->ch[1] = c; \
48                           else comperr("triple cfnodes"); }
49 #define FORCH(cn, chp)  \
50         for (cn = &chp[0]; cn < &chp[2] && cn[0]; cn++)
51
ragge
1.66
52 /* main switch for new things not yet ready for all-day use */
53 /* #define ENABLE_NEW */
54
55
pj
1.8
56 static int dfsnum;
ragge
1.1
57
58 void saveip(struct interpass *ip);
ragge
1.56
59 void deljumps(struct p2env *);
ragge
1.1
60 void optdump(struct interpass *ip);
ragge
1.19
61 void printip(struct interpass *pole);
ragge
1.1
62
pj
1.21
63 static struct varinfo defsites;
ragge
1.1
64
ragge
1.74
65 void bblocks_build(struct p2env *);
66 void cfg_build(struct p2env *);
pj
1.8
67 void cfg_dfs(struct basicblock *bbunsigned int parent
68              struct bblockinfo *bbinfo);
ragge
1.74
69 void dominators(struct p2env *);
pj
1.9
70 struct basicblock *
71 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo);
ragge
1.74
72 void computeDF(struct p2env *, struct basicblock *bblock);
73 void printDF(struct p2env *p2e);
pj
1.21
74 void findTemps(struct interpass *ip);
ragge
1.74
75 void placePhiFunctions(struct p2env *);
76 void renamevar(struct p2env *p2e,struct basicblock *bblock);
77 void removephi(struct p2env *p2e);
ragge
1.56
78 void remunreach(struct p2env *);
ragge
1.77
79 static void liveanal(struct p2env *p2e);
ragge
1.78
80 static void printip2(struct interpass *);
pj
1.4
81
ragge
1.66
82 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
83 /* run before bb generate */
84 static void add_labels(struct p2env*) ;
85
86 /* Perform trace scheduling, try to get rid of gotos as much as possible */
87 void TraceSchedule(struct p2env*) ;
88
89 #ifdef ENABLE_NEW
90 static void do_cse(struct p2envp2e) ;
91 #endif
92
93 /* Walk the complete set, performing a function on each node. 
94  * if type is given, apply function on only that type */
ragge
1.67
95 void WalkAll(struct p2envp2evoid (*f) (NODE*, void*), voidargint type) ;
ragge
1.66
96
97 void BBLiveDead(struct basicblockbblockint whatunsigned int variable) ;
98
99 /* Fill the live/dead code */
ragge
1.67
100 void LiveDead(struct p2envp2eint whatunsigned int variable) ;
ragge
1.66
101
pantzer
1.63
102 #ifdef PCC_DEBUG
ragge
1.74
103 void printflowdiagram(struct p2env *, char *);
pantzer
1.63
104 #endif
105
ragge
1.38
106 void
ragge
1.56
107 optimize(struct p2env *p2e)
ragge
1.38
108 {
ragge
1.56
109         struct interpass *ipole = &p2e->ipole;
ragge
1.38
110
111         if (b2debug) {
112                 printf("initial links\n");
113                 printip(ipole);
114         }
115
116         if (xdeljumps)
ragge
1.56
117                 deljumps(p2e); /* Delete redundant jumps and dead code */
ragge
1.38
118
plunky
1.81
119         if (xssa)
ragge
1.66
120                 add_labels(p2e) ;
121 #ifdef ENABLE_NEW
122         do_cse(p2e);
123 #endif
124
ragge
1.38
125 #ifdef PCC_DEBUG
126         if (b2debug) {
127                 printf("links after deljumps\n");
128                 printip(ipole);
129         }
130 #endif
plunky
1.81
131         if (xssa || xtemps) {
ragge
1.74
132                 bblocks_build(p2e);
ragge
1.38
133                 BDEBUG(("Calling cfg_build\n"));
ragge
1.74
134                 cfg_build(p2e);
pantzer
1.63
135         
136 #ifdef PCC_DEBUG
ragge
1.74
137                 printflowdiagram(p2e"first");
pantzer
1.63
138 #endif
ragge
1.38
139         }
plunky
1.81
140         if (xssa) {
ragge
1.77
141                 BDEBUG(("Calling liveanal\n"));
142                 liveanal(p2e);
ragge
1.38
143                 BDEBUG(("Calling dominators\n"));
ragge
1.74
144                 dominators(p2e);
ragge
1.38
145                 BDEBUG(("Calling computeDF\n"));
ragge
1.74
146                 computeDF(p2eDLIST_NEXT(&p2e->bblocksbbelem));
pantzer
1.59
147
148                 if (b2debug) {
ragge
1.74
149                         printDF(p2e);
pantzer
1.59
150                 }
151
152                 BDEBUG(("Calling placePhiFunctions\n"));
153
ragge
1.74
154                 placePhiFunctions(p2e);
pantzer
1.59
155
156                 BDEBUG(("Calling renamevar\n"));
157
ragge
1.74
158                 renamevar(p2e,DLIST_NEXT(&p2e->bblocksbbelem));
pantzer
1.59
159
160                 BDEBUG(("Calling removephi\n"));
161
pantzer
1.63
162 #ifdef PCC_DEBUG
ragge
1.74
163                 printflowdiagram(p2e"ssa");
pantzer
1.63
164 #endif
165
ragge
1.74
166                 removephi(p2e);
pantzer
1.59
167
ragge
1.38
168                 BDEBUG(("Calling remunreach\n"));
ragge
1.66
169 /*              remunreach(p2e); */
pantzer
1.59
170                 
171                 /*
ragge
1.73
172                  * Recalculate basic blocks and cfg that was destroyed
173                  * by removephi
pantzer
1.59
174                  */
ragge
1.66
175                 /* first, clean up all what deljumps should have done, and more */
176
ragge
1.73
177                 /* TODO: add the basic blocks done by the ssa code by hand. 
178                  * The trace scheduler should not change the order in
179                  * which blocks are executed or what data is calculated.
180                  * Thus, the BBlock order should remain correct.
ragge
1.66
181                  */
182
183 #ifdef ENABLE_NEW
ragge
1.82
184                 bblocks_build(p2e);
ragge
1.66
185                 BDEBUG(("Calling cfg_build\n"));
ragge
1.82
186                 cfg_build(p2e);
ragge
1.66
187
188                 TraceSchedule(p2e);
189 #ifdef PCC_DEBUG
ragge
1.82
190                 printflowdiagram(p2e"sched_trace");
ragge
1.66
191
192                 if (b2debug) {
193                         printf("after tracesched\n");
194                         printip(ipole);
195                         fflush(stdout) ;
196                 }
197 #endif
198 #endif
199
200                 /* Now, clean up the gotos we do not need any longer */
201                 if (xdeljumps)
202                         deljumps(p2e); /* Delete redundant jumps and dead code */
pantzer
1.59
203
ragge
1.74
204                 bblocks_build(p2e);
pantzer
1.59
205                 BDEBUG(("Calling cfg_build\n"));
ragge
1.74
206                 cfg_build(p2e);
pantzer
1.59
207
208 #ifdef PCC_DEBUG
ragge
1.74
209                 printflowdiagram(p2e"no_phi");
pantzer
1.63
210
pantzer
1.59
211                 if (b2debug) {
212                         printf("new tree\n");
213                         printip(ipole);
214                 }
ragge
1.38
215 #endif
216         }
217
218 #ifdef PCC_DEBUG
mickey
1.55
219         {
220                 int i;
221                 for (i = NIPPREGSi--; )
ragge
1.56
222                         if (p2e->epp->ipp_regs[i] != 0)
mickey
1.55
223                                 comperr("register error");
224         }
ragge
1.38
225 #endif
226
mickey
1.49
227         myoptim(ipole);
ragge
1.38
228 }
ragge
1.1
229
ragge
1.26
230 /*
231  * Delete unused labels, excess of labels, gotos to gotos.
232  * This routine can be made much more efficient.
ragge
1.72
233  *
234  * Layout of the statement list here (_must_ look this way!):
235  *      PROLOG
236  *      LABEL   - states beginning of function argument moves
237  *      ...code to save/move arguments
238  *      LABEL   - states beginning of execution code
239  *      ...code + labels in function in function
240  *      EPILOG
241  *
242  * This version of deljumps is based on the c2 implementation
243  * that were included in 2BSD.
ragge
1.26
244  */
ragge
1.72
245 #define LABEL 1
246 #define JBR     2
247 #define CBR     3
248 #define STMT    4
249 #define EROU    5
250 struct dlnod {
251         int op;
252         struct interpass *dlip;
253         struct dlnod *forw;
254         struct dlnod *back;
255         struct dlnod *ref;
256         int labno;
257         int refc;
258 };
259
260 #ifdef DLJDEBUG
261 static void
262 dumplink(struct dlnod *dl)
ragge
1.1
263 {
ragge
1.72
264         printf("dumplink %p\n"dl);
265         for (; dldl = dl->forw) {
266                 if (dl->op == STMT) {
267                         printf("STMT(%p)\n"dl);
268                         fwalk(dl->dlip->ip_nodee2print0);
269                 } else if (dl->op == EROU) {
270                         printf("EROU(%p)\n"dl);
271                 } else {
272                         static char *str[] = { 0"LABEL""JBR""CBR" };
273                         printf("%s(%p) %d refc %d ref %p\n"str[dl->op], 
274                             dldl->labnodl->refcdl->ref);
275                 }
276         }
277         printf("end dumplink\n");
278 }
279 #endif
ragge
1.26
280
ragge
1.72
281 /*
282  * Create the linked list that we can work on.
283  */
284 static void
285 listsetup(struct interpass *ipolestruct dlnod *dl)
286 {
287         struct interpass *ip = DLIST_NEXT(ipoleqelem);
ragge
1.76
288         struct interpass *nip;
ragge
1.72
289         struct dlnod *p, *lastp;
290         NODE *q;
291
292         lastp = dl;
293         while (ip->type != IP_DEFLAB)
294                 ip = DLIST_NEXT(ip,qelem);
295         ip = DLIST_NEXT(ip,qelem);
296         while (ip->type != IP_DEFLAB)
297                 ip = DLIST_NEXT(ip,qelem);
298         /* Now ip is at the beginning */
299         for (;;) {
300                 ip = DLIST_NEXT(ip,qelem);
301                 if (ip == ipole)
302                         break;
303                 p = tmpalloc(sizeof(struct dlnod));
304                 p->labno = 0;
305                 p->dlip = ip;
306                 switch (ip->type) {
307                 case IP_DEFLAB:
308                         p->op = LABEL;
309                         p->labno = ip->ip_lbl;
310                         break;
ragge
1.26
311
ragge
1.72
312                 case IP_NODE:
313                         q = ip->ip_node;
314                         switch (q->n_op) {
315                         case GOTO:
ragge
1.84
316                                 if (q->n_left->n_op == ICON) {
317                                         p->op = JBR;
318                                         p->labno = q->n_left->n_lval;
319                                 } else 
320                                         p->op = STMT;
ragge
1.72
321                                 break;
322                         case CBRANCH:
323                                 p->op = CBR;
324                                 p->labno = q->n_right->n_lval;
325                                 break;
ragge
1.76
326                         case ASSIGN:
327                                 /* remove ASSIGN to self for regs */
328                                 if (q->n_left->n_op == REG && 
329                                     q->n_right->n_op == REG &&
330                                     regno(q->n_left) == regno(q->n_right)) {
331                                         nip = DLIST_PREV(ipqelem);
332                                         tfree(q);
333                                         DLIST_REMOVE(ipqelem);
334                                         ip = nip;
335                                         continue;
336                                 }
337                                 /* FALLTHROUGH */
ragge
1.72
338                         default:
339                                 p->op = STMT;
340                                 break;
341                         }
342                         break;
ragge
1.28
343
ragge
1.72
344                 case IP_ASM:
345                         p->op = STMT;
346                         break;
ragge
1.45
347
ragge
1.72
348                 case IP_EPILOG:
349                         p->op = EROU;
ragge
1.45
350                         break;
ragge
1.72
351
352                 default:
353                         comperr("listsetup: bad ip node %d"ip->type);
354                 }
355                 p->forw = 0;
356                 p->back = lastp;
357                 lastp->forw = p;
358                 lastp = p;
359                 p->ref = 0;
ragge
1.45
360         }
ragge
1.72
361 }
362
ragge
1.84
363 /*
364  * Traverse to the first statement behind a label.
365  */
ragge
1.72
366 static struct dlnod *
367 nonlab(struct dlnod *p)
368 {
369         while (p && p->op==LABEL)
370                 p = p->forw;
371         return(p);
372 }
ragge
1.26
373
ragge
1.72
374 static void
375 iprem(struct dlnod *p)
376 {
377         if (p->dlip->type == IP_NODE)
378                 tfree(p->dlip->ip_node);
379         DLIST_REMOVE(p->dlipqelem);
380 }
ragge
1.26
381
ragge
1.72
382 static void
383 decref(struct dlnod *p)
384 {
385         if (--p->refc <= 0) {
386                 iprem(p);
387                 p->back->forw = p->forw;
388                 p->forw->back = p->back;
389         }
390 }
391
ragge
1.84
392 /*
393  * Change a label number for jump/branch instruction to labno.
394  */
ragge
1.72
395 static void
396 setlab(struct dlnod *pint labno)
397 {
398         p->labno = labno;
399         if (p->op == JBR)
400                 p->dlip->ip_node->n_left->n_lval = labno;
ragge
1.76
401         else if (p->op == CBR) {
ragge
1.72
402                 p->dlip->ip_node->n_right->n_lval = labno;
ragge
1.76
403                 p->dlip->ip_node->n_left->n_label = labno;
404         } else
ragge
1.72
405                 comperr("setlab bad op %d"p->op);
406 }
ragge
1.45
407
ragge
1.72
408 /*
ragge
1.84
409  * See if a label is used outside of us.
410  */
411 static int
412 inuse(struct p2env *p2eint lbl)
413 {
414         int *l;
415
416         for (l = p2e->epp->ip_labels; *ll++)
417                 if (*l == lbl)
418                         return 1;
419         return 0;
420 }
421
422 /*
ragge
1.72
423  * Label reference counting and removal of unused labels.
424  */
425 #define LABHS 127
426 static void
427 refcount(struct p2env *p2estruct dlnod *dl)
428 {
429         struct dlnod *p, *lp;
430         struct dlnod *labhash[LABHS];
431         struct dlnod **hp, *tp;
432
433         /* Clear label hash */
434         for (hp = labhashhp < &labhash[LABHS];)
435                 *hp++ = 0;
436         /* Enter labels into hash.  Later overwrites earlier */
ragge
1.84
437         for (p = dl->forwp!=0p = p->forw) {
ragge
1.72
438                 if (p->op==LABEL) {
439                         labhash[p->labno % LABHS] = p;
440                         p->refc = 0;
ragge
1.84
441                         if (inuse(p2ep->labno))
442                                 p->refc = 1000/* never remove */
ragge
1.72
443                 }
ragge
1.84
444         }
ragge
1.72
445         /* search for jumps to labels and fill in reference */
446         for (p = dl->forwp!=0p = p->forw) {
447                 if (p->op==JBR || p->op==CBR) {
448                         p->ref = 0;
449                         lp = labhash[p->labno % LABHS];
450                         if (lp==0 || p->labno!=lp->labno)
451                             for (lp = dl->forwlp!=0lp = lp->forw) {
452                                 if (lp->op==LABEL && p->labno==lp->labno)
453                                         break;
454                             }
455                         if (lp) {
456                                 tp = nonlab(lp)->back;
457                                 if (tp!=lp) {
458                                         setlab(ptp->labno);
459                                         lp = tp;
ragge
1.45
460                                 }
ragge
1.72
461                                 p->ref = lp;
462                                 lp->refc++;
ragge
1.27
463                         }
464                 }
ragge
1.72
465         }
466         for (p = dl->forwp!=0p = p->forw)
ragge
1.76
467                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
ragge
1.72
468                         decref(p);
469 }
470
471 static int nchange;
ragge
1.45
472
ragge
1.72
473 static struct dlnod *
474 codemove(struct dlnod *p)
475 {
476         struct dlnod *p1, *p2, *p3;
477 #ifdef notyet
478         struct dlnod *t, *tl;
479         int n;
480 #endif
ragge
1.27
481
ragge
1.72
482         p1 = p;
483         if (p1->op!=JBR || (p2 = p1->ref)==0)
484                 return(p1);
485         while (p2->op == LABEL)
486                 if ((p2 = p2->back) == 0)
487                         return(p1);
488         if (p2->op!=JBR)
489                 goto ivloop;
490         if (p1==p2)
491                 return(p1);
492         p2 = p2->forw;
493         p3 = p1->ref;
494         while (p3) {
495                 if (p3->op==JBR) {
496                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
497                                 return(p1);
498                         nchange++;
499                         p1->back->forw = p2;
500                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
501
502                         p1->forw->back = p3;
503                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
504
505
506                         p2->back->forw = p3->forw;
507                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
508
509                         p3->forw->back = p2->back;
510                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
511
512                         p2->back = p1->back;
513                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
514
515                         p3->forw = p1->forw;
516                         p3->dlip->qelem.q_forw = p1->forw->dlip;
517
518                         decref(p1->ref);
519                         if (p1->dlip->type == IP_NODE)
520                                 tfree(p1->dlip->ip_node);
ragge
1.45
521
ragge
1.72
522                         return(p2);
523                 } else
524                         p3 = p3->forw;
ragge
1.26
525         }
ragge
1.72
526         return(p1);
ragge
1.27
527
ragge
1.72
528 ivloop:
529         if (p1->forw->op!=LABEL)
530                 return(p1);
531         return(p1);
532
533 #ifdef notyet
534         p3 = p2 = p2->forw;
535         n = 16;
536         do {
537                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
538                         return(p1);
539         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
540         do 
541                 if ((p1 = p1->back) == 0)
542                         return(p);
543         while (p1!=p3);
544         p1 = p;
545         tl = insertl(p1);
546         p3->subop = revbr[p3->subop];
547         decref(p3->ref);
548                 p2->back->forw = p1;
549         p3->forw->back = p1;
550         p1->back->forw = p2;
551         p1->forw->back = p3;
552         t = p1->back;
553         p1->back = p2->back;
554         p2->back = t;
555         t = p1->forw;
556         p1->forw = p3->forw;
557         p3->forw = t;
558         p2 = insertl(p1->forw);
559         p3->labno = p2->labno;
560         p3->ref = p2;
561         decref(tl);
562         if (tl->refc<=0)
563                 nrlab--;
564         nchange++;
565         return(p3);
ragge
1.69
566 #endif
ragge
1.72
567 }
ragge
1.33
568
ragge
1.72
569 static void
570 iterate(struct p2env *p2estruct dlnod *dl)
571 {
572         struct dlnod *p, *rp, *p1;
573         extern int negrel[];
574         extern size_t negrelsize;
575         int i;
ragge
1.33
576
ragge
1.72
577         nchange = 0;
578         for (p = dl->forwp!=0p = p->forw) {
579                 if ((p->op==JBR||p->op==CBR) && p->ref) {
580                         /* Resolves:
581                          * jbr L7
582                          * ...
583                          * L7: jbr L8
584                          */
585                         rp = nonlab(p->ref);
586                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
587                                 setlab(prp->labno);
588                                 decref(p->ref);
589                                 rp->ref->refc++;
590                                 p->ref = rp->ref;
591                                 nchange++;
592                         }
593                 }
594                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
595                         /* Resolves:
596                          * cbr L7
597                          * jbr L8
598                          * L7:
599                          */
600                         rp = p->ref;
601                         do
602                                 rp = rp->back;
603                         while (rp->op==LABEL);
604                         if (rp==p1) {
605                                 decref(p->ref);
606                                 p->ref = p1->ref;
607                                 setlab(pp1->labno);
608
609                                 iprem(p1);
610
611                                 p1->forw->back = p;
612                                 p->forw = p1->forw;
613
614                                 i = p->dlip->ip_node->n_left->n_op;
615                                 if (i < EQ || i - EQ >= (int)negrelsize)
616                                         comperr("deljumps: unexpected op");
617                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
618                                 nchange++;
619                         }
ragge
1.1
620                 }
ragge
1.72
621                 if (p->op == JBR) {
622                         /* Removes dead code */
623                         while (p->forw && p->forw->op!=LABEL &&
624                             p->forw->op!=EROU) {
625                                 nchange++;
626                                 if (p->forw->ref)
627                                         decref(p->forw->ref);
ragge
1.28
628
ragge
1.72
629                                 iprem(p->forw);
ragge
1.45
630
ragge
1.72
631                                 p->forw = p->forw->forw;
632                                 p->forw->back = p;
633                         }
634                         rp = p->forw;
635                         while (rp && rp->op==LABEL) {
636                                 if (p->ref == rp) {
637                                         p->back->forw = p->forw;
638                                         p->forw->back = p->back;
639                                         iprem(p);
640                                         p = p->back;
641                                         decref(rp);
642                                         nchange++;
643                                         break;
644                                 }
645                                 rp = rp->forw;
646                         }
647                 }
648                 if (p->op == JBR) {
649                         /* xjump(p); * needs tree rewrite; not yet */
650                         p = codemove(p);
ragge
1.45
651                 }
652         }
ragge
1.72
653 }
ragge
1.45
654
ragge
1.72
655 void
656 deljumps(struct p2env *p2e)
657 {
658         struct interpass *ipole = &p2e->ipole;
659         struct dlnod dln;
660         MARK mark;
661
662         markset(&mark);
ragge
1.28
663
ragge
1.72
664         memset(&dln0sizeof(dln));
665         listsetup(ipole, &dln);
666         do {
667                 refcount(p2e, &dln);
668                 do {
669                         iterate(p2e, &dln);
670                 } while (nchange);
ragge
1.28
671 #ifdef notyet
ragge
1.72
672                 comjump();
ragge
1.26
673 #endif
ragge
1.72
674         } while (nchange);
675
676         markfree(&mark);
ragge
1.1
677 }
678
679 void
680 optdump(struct interpass *ip)
681 {
682         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
683                 "deflab""defnam""asm" };
684         printf("type %s\n"nm[ip->type-1]);
685         switch (ip->type) {
686         case IP_NODE:
gmcgarry
1.52
687 #ifdef PCC_DEBUG
ragge
1.1
688                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
689 #endif
ragge
1.1
690                 break;
691         case IP_DEFLAB:
692                 printf("label " LABFMT "\n"ip->ip_lbl);
693                 break;
694         case IP_ASM:
plunky
1.88
695                 printf("%s"ip->ip_asm);
ragge
1.1
696                 break;
697         }
698 }
pj
1.4
699
700 /*
701  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
702  *
703  * Also fills the labelinfo struct with information about which bblocks
704  * that contain which label.
705  */
706
ragge
1.30
707 void
ragge
1.74
708 bblocks_build(struct p2env *p2e)
pj
1.4
709 {
ragge
1.56
710         struct interpass *ipole = &p2e->ipole;
pj
1.4
711         struct interpass *ip;
712         struct basicblock *bb = NULL;
ragge
1.30
713         int lowhigh;
pj
1.8
714         int count = 0;
pj
1.4
715         int i;
716
ragge
1.74
717         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
ragge
1.56
718         low = p2e->ipp->ip_lblnum;
719         high = p2e->epp->ip_lblnum;
ragge
1.30
720
pj
1.4
721         /* 
722          * First statement is a leader.
723          * Any statement that is target of a jump is a leader.
724          * Any statement that immediately follows a jump is a leader.
725          */
ragge
1.75
726         DLIST_INIT(&p2e->bblocksbbelem);
ragge
1.38
727         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
728                 if (bb == NULL || (ip->type == IP_EPILOG) ||
729                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
730                         bb = tmpalloc(sizeof(struct basicblock));
731                         bb->first = ip;
732                         SLIST_INIT(&bb->parents);
ragge
1.83
733                         SLIST_INIT(&bb->child);
ragge
1.31
734                         bb->dfnum = 0;
735                         bb->dfparent = 0;
736                         bb->semi = 0;
737                         bb->ancestor = 0;
738                         bb->idom = 0;
739                         bb->samedom = 0;
740                         bb->bucket = NULL;
741                         bb->df = NULL;
742                         bb->dfchildren = NULL;
743                         bb->Aorig = NULL;
744                         bb->Aphi = NULL;
pantzer
1.59
745                         SLIST_INIT(&bb->phi);
ragge
1.34
746                         bb->bbnum = count;
ragge
1.56
747                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
748                         count++;
749                 }
750                 bb->last = ip;
751                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
752                     ip->ip_node->n_op == CBRANCH))
753                         bb = NULL;
754                 if (ip->type == IP_PROLOG)
755                         bb = NULL;
756         }
ragge
1.56
757         p2e->nbblocks = count;
ragge
1.30
758
ragge
1.31
759         if (b2debug) {
ragge
1.32
760                 printf("Basic blocks in func: %d, low %d, high %d\n",
761                     countlowhigh);
ragge
1.56
762                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.73
763                         printf("bb(%d) %p: first %p last %p\n"bb->bbnumbb,
ragge
1.31
764                             bb->firstbb->last);
765                 }
766         }
pj
1.4
767
ragge
1.74
768         p2e->labinfo.low = low;
769         p2e->labinfo.size = high - low + 1;
770         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
771         for (i = 0i < p2e->labinfo.sizei++) {
772                 p2e->labinfo.arr[i] = NULL;
pj
1.4
773         }
pj
1.8
774         
ragge
1.74
775         p2e->bbinfo.size = count + 1;
776         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
777         for (i = 0i < p2e->bbinfo.sizei++) {
778                 p2e->bbinfo.arr[i] = NULL;
pj
1.8
779         }
pj
1.4
780
ragge
1.32
781         /* Build the label table */
ragge
1.56
782         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
783                 if (bb->first->type == IP_DEFLAB)
ragge
1.74
784                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
785         }
786
787         if (b2debug) {
ragge
1.76
788                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
789                         printf("bblock %d\n"bb->bbnum);
790                         for (ip = bb->firstip != bb->last;
791                             ip = DLIST_NEXT(ipqelem)) {
792                                 printip2(ip);
793                         }
794                         printip2(ip);
795                 }
796
ragge
1.32
797                 printf("Label table:\n");
ragge
1.74
798                 for (i = 0i < p2e->labinfo.sizei++)
799                         if (p2e->labinfo.arr[i])
ragge
1.32
800                                 printf("Label %d bblock %p\n"i+low,
ragge
1.74
801                                     p2e->labinfo.arr[i]);
pj
1.4
802         }
803 }
804
805 /*
806  * Build the control flow graph.
807  */
808
809 void
ragge
1.74
810 cfg_build(struct p2env *p2e)
pj
1.4
811 {
812         /* Child and parent nodes */
813         struct cfgnode *cnode
814         struct cfgnode *pnode;
815         struct basicblock *bb;
ragge
1.84
816         NODE *p;
817
818 #ifdef notyet
ragge
1.56
819         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.84
820                 if (bb->first->type == IP_EPILOG)
821                         break;
822
823                 if (bb->last->type == IP_NODE) {
824                         p = bb->last->ip_node;
825                         switch (p->n_op) {
826                         case GOTO:
827                                 if (p->n_left->n_op == ICON) {
828                                         lbchk(p2ep->n_left->n_lval);
829                                         fillcnode(p2ep->n_left->n_lvalbb);
830                                 } else {
831                                 }
832                                 break;
833
834                         case CBRANCH:
835                                 lbchk(p2ep->n_right->n_lval);
836                                 fillcnode(p2ep->n_right->n_lvalbb);
837                                 ...
pj
1.4
838
ragge
1.84
839                         default:
840                                 ...
841                         }
842                 } else {
843                         ...
pj
1.4
844                 }
ragge
1.84
845         }
846 #endif
pj
1.4
847
ragge
1.84
848         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
849                 if (bb->first->type == IP_EPILOG)
850                         break;
851         
pj
1.4
852                 cnode = tmpalloc(sizeof(struct cfgnode));
853                 pnode = tmpalloc(sizeof(struct cfgnode));
854                 pnode->bblock = bb;
855
ragge
1.84
856                 p = bb->last->ip_node;
857                 if (bb->last->type == IP_NODE && p->n_op == GOTO) {
858                         if (p->n_left->n_op == ICON) {
859                                 if (p->n_left->n_lval - p2e->labinfo.low > p2e->labinfo.size)
860                                         comperr("Label out of range: %d, base %d"
861                                             p->n_left->n_lvalp2e->labinfo.low);
862                                 cnode->bblock = p2e->labinfo.arr[p->n_left->n_lval - p2e->labinfo.low];
863                                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
864                                 SLIST_INSERT_LAST(&bb->childcnodechld);
865                         } else {
866                                 int *l;
867                                 /* XXX assume all labels are valid as dest */
868                                 for (l = p2e->epp->ip_labels; *ll++) {
869                                         cnode->bblock = p2e->labinfo.arr[*l - p2e->labinfo.low];
870                                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
871                                         SLIST_INSERT_LAST(&bb->childcnodechld);
872                                         cnode = tmpalloc(sizeof(struct cfgnode));
873                                         pnode = tmpalloc(sizeof(struct cfgnode));
874                                         pnode->bblock = bb;
875                                 }
pj
1.4
876                         }
877                         continue;
878                 }
ragge
1.84
879                 if ((bb->last->type == IP_NODE) && p->n_op == CBRANCH) {
880                         if (p->n_right->n_lval - p2e->labinfo.low > p2e->labinfo.size
881                                 comperr("Label out of range: %d"p->n_left->n_lval);
ragge
1.66
882
ragge
1.84
883                         cnode->bblock = p2e->labinfo.arr[p->n_right->n_lval - p2e->labinfo.low];
ragge
1.11
884                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
ragge
1.83
885                         SLIST_INSERT_LAST(&bb->childcnodechld);
pj
1.4
886                         cnode = tmpalloc(sizeof(struct cfgnode));
887                         pnode = tmpalloc(sizeof(struct cfgnode));
888                         pnode->bblock = bb;
889                 }
890
ragge
1.11
891                 cnode->bblock = DLIST_NEXT(bbbbelem);
892                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
ragge
1.83
893                 SLIST_INSERT_LAST(&bb->childcnodechld);
pj
1.4
894         }
895 }
pj
1.6
896
pj
1.8
897 void
898 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
899 {
ragge
1.83
900         struct cfgnode *cn;
ragge
1.79
901
pj
1.8
902         if (bb->dfnum != 0)
903                 return;
904
905         bb->dfnum = ++dfsnum;
906         bb->dfparent = parent;
907         bbinfo->arr[bb->dfnum] = bb;
ragge
1.83
908         SLIST_FOREACH(cn, &bb->childchld)
909                 cfg_dfs(cn->bblockbb->dfnumbbinfo);
pj
1.13
910         /* Don't bring in unreachable nodes in the future */
pj
1.20
911         bbinfo->size = dfsnum + 1;
pj
1.8
912 }
913
ragge
1.11
914 static bittype *
915 setalloc(int nelem)
916 {
917         bittype *b;
918         int sz = (nelem+NUMBITS-1)/NUMBITS;
919
920         b = tmpalloc(sz * sizeof(bittype));
921         memset(b0sz * sizeof(bittype));
922         return b;
923 }
924
pj
1.8
925 /*
926  * Algorithm 19.9, pp 414 from Appel.
927  */
928
929 void
ragge
1.74
930 dominators(struct p2env *p2e)
pj
1.8
931 {
932         struct cfgnode *cnode;
933         struct basicblock *bb, *y, *v;
934         struct basicblock *s, *sprime, *p;
pj
1.10
935         int hi;
pj
1.8
936
ragge
1.56
937         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.74
938                 bb->bucket = setalloc(p2e->bbinfo.size);
939                 bb->df = setalloc(p2e->bbinfo.size);
940                 bb->dfchildren = setalloc(p2e->bbinfo.size);
pj
1.8
941         }
942
943         dfsnum = 0;
ragge
1.74
944         cfg_dfs(DLIST_NEXT(&p2e->bblocksbbelem), 0, &p2e->bbinfo);
pj
1.8
945
ragge
1.30
946         if (b2debug) {
947                 struct basicblock *bbb;
ragge
1.83
948                 struct cfgnode *ccnode, *cn;
ragge
1.30
949
ragge
1.56
950                 DLIST_FOREACH(bbb, &p2e->bblocksbbelem) {
ragge
1.30
951                         printf("Basic block %d, parents: "bbb->dfnum);
952                         SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
953                                 printf("%d, "ccnode->bblock->dfnum);
954                         }
955                         printf("\nChildren: ");
ragge
1.83
956                         SLIST_FOREACH(cn, &bbb->childchld)
957                                 printf("%d, "cn->bblock->dfnum);
ragge
1.30
958                         printf("\n");
pj
1.20
959                 }
960         }
961
ragge
1.74
962         for(h = p2e->bbinfo.size - 1h > 1h--) {
963                 bb = p2e->bbinfo.arr[h];
964                 p = s = p2e->bbinfo.arr[bb->dfparent];
ragge
1.11
965                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pantzer
1.60
966                         if (cnode->bblock->dfnum ==0)
967                                 continue/* Ignore unreachable code */
968
pj
1.8
969                         if (cnode->bblock->dfnum <= bb->dfnum
970                                 sprime = cnode->bblock;
pj
1.10
971                         else 
ragge
1.74
972                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
973                                               (cnode->bblock, &p2e->bbinfo)->semi];
pj
1.8
974                         if (sprime->dfnum < s->dfnum)
975                                 s = sprime;
976                 }
977                 bb->semi = s->dfnum;
pj
1.10
978                 BITSET(s->bucketbb->dfnum);