Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100521073716

Diff

Diff from 1.76 to:

Annotations

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

Annotated File View

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