Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100512170500

Diff

Diff from 1.75 to:

Annotations

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

Annotated File View

ragge
1.75
1 /*      $Id: optim2.c,v 1.75 2010/05/12 17:05:00 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);
280         struct dlnod *p, *lastp;
281         NODE *q;
282
283         lastp = dl;
284         while (ip->type != IP_DEFLAB)
285                 ip = DLIST_NEXT(ip,qelem);
286         ip = DLIST_NEXT(ip,qelem);
287         while (ip->type != IP_DEFLAB)
288                 ip = DLIST_NEXT(ip,qelem);
289         /* Now ip is at the beginning */
290         for (;;) {
291                 ip = DLIST_NEXT(ip,qelem);
292                 if (ip == ipole)
293                         break;
294                 p = tmpalloc(sizeof(struct dlnod));
295                 p->labno = 0;
296                 p->dlip = ip;
297                 switch (ip->type) {
298                 case IP_DEFLAB:
299                         p->op = LABEL;
300                         p->labno = ip->ip_lbl;
301                         break;
ragge
1.26
302
ragge
1.72
303                 case IP_NODE:
304                         q = ip->ip_node;
305                         switch (q->n_op) {
306                         case GOTO:
307                                 p->op = JBR;
308                                 p->labno = q->n_left->n_lval;
309                                 break;
310                         case CBRANCH:
311                                 p->op = CBR;
312                                 p->labno = q->n_right->n_lval;
313                                 break;
314                         default:
315                                 p->op = STMT;
316                                 break;
317                         }
318                         break;
ragge
1.28
319
ragge
1.72
320                 case IP_ASM:
321                         p->op = STMT;
322                         break;
ragge
1.45
323
ragge
1.72
324                 case IP_EPILOG:
325                         p->op = EROU;
ragge
1.45
326                         break;
ragge
1.72
327
328                 default:
329                         comperr("listsetup: bad ip node %d"ip->type);
330                 }
331                 p->forw = 0;
332                 p->back = lastp;
333                 lastp->forw = p;
334                 lastp = p;
335                 p->ref = 0;
ragge
1.45
336         }
ragge
1.72
337 }
338
339 static struct dlnod *
340 nonlab(struct dlnod *p)
341 {
342         while (p && p->op==LABEL)
343                 p = p->forw;
344         return(p);
345 }
ragge
1.26
346
ragge
1.72
347 static void
348 iprem(struct dlnod *p)
349 {
350         if (p->dlip->type == IP_NODE)
351                 tfree(p->dlip->ip_node);
352         DLIST_REMOVE(p->dlipqelem);
353 }
ragge
1.26
354
ragge
1.72
355 static void
356 decref(struct dlnod *p)
357 {
358         if (--p->refc <= 0) {
359                 iprem(p);
360                 p->back->forw = p->forw;
361                 p->forw->back = p->back;
362         }
363 }
364
365 static void
366 setlab(struct dlnod *pint labno)
367 {
368         p->labno = labno;
369         if (p->op == JBR)
370                 p->dlip->ip_node->n_left->n_lval = labno;
371         else if (p->op == CBR)
372                 p->dlip->ip_node->n_right->n_lval = labno;
373         else
374                 comperr("setlab bad op %d"p->op);
375 }
ragge
1.45
376
ragge
1.72
377 /*
378  * Label reference counting and removal of unused labels.
379  */
380 #define LABHS 127
381 static void
382 refcount(struct p2env *p2estruct dlnod *dl)
383 {
384         struct dlnod *p, *lp;
385         struct dlnod *labhash[LABHS];
386         struct dlnod **hp, *tp;
387
388         /* Clear label hash */
389         for (hp = labhashhp < &labhash[LABHS];)
390                 *hp++ = 0;
391         /* Enter labels into hash.  Later overwrites earlier */
392         for (p = dl->forwp!=0p = p->forw)
393                 if (p->op==LABEL) {
394                         labhash[p->labno % LABHS] = p;
395                         p->refc = 0;
396                 }
397
398         /* search for jumps to labels and fill in reference */
399         for (p = dl->forwp!=0p = p->forw) {
400                 if (p->op==JBR || p->op==CBR) {
401                         p->ref = 0;
402                         lp = labhash[p->labno % LABHS];
403                         if (lp==0 || p->labno!=lp->labno)
404                             for (lp = dl->forwlp!=0lp = lp->forw) {
405                                 if (lp->op==LABEL && p->labno==lp->labno)
406                                         break;
407                             }
408                         if (lp) {
409                                 tp = nonlab(lp)->back;
410                                 if (tp!=lp) {
411                                         setlab(ptp->labno);
412                                         lp = tp;
ragge
1.45
413                                 }
ragge
1.72
414                                 p->ref = lp;
415                                 lp->refc++;
ragge
1.27
416                         }
417                 }
ragge
1.72
418         }
419         for (p = dl->forwp!=0p = p->forw)
420                 if (p->op==LABEL && p->refc==0
421                  && (lp = nonlab(p))->op)
422                         decref(p);
423 }
424
425 static int nchange;
ragge
1.45
426
ragge
1.72
427 static struct dlnod *
428 codemove(struct dlnod *p)
429 {
430         struct dlnod *p1, *p2, *p3;
431 #ifdef notyet
432         struct dlnod *t, *tl;
433         int n;
434 #endif
ragge
1.27
435
ragge
1.72
436         p1 = p;
437         if (p1->op!=JBR || (p2 = p1->ref)==0)
438                 return(p1);
439         while (p2->op == LABEL)
440                 if ((p2 = p2->back) == 0)
441                         return(p1);
442         if (p2->op!=JBR)
443                 goto ivloop;
444         if (p1==p2)
445                 return(p1);
446         p2 = p2->forw;
447         p3 = p1->ref;
448         while (p3) {
449                 if (p3->op==JBR) {
450                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
451                                 return(p1);
452                         nchange++;
453                         p1->back->forw = p2;
454                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
455
456                         p1->forw->back = p3;
457                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
458
459
460                         p2->back->forw = p3->forw;
461                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
462
463                         p3->forw->back = p2->back;
464                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
465
466                         p2->back = p1->back;
467                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
468
469                         p3->forw = p1->forw;
470                         p3->dlip->qelem.q_forw = p1->forw->dlip;
471
472                         decref(p1->ref);
473                         if (p1->dlip->type == IP_NODE)
474                                 tfree(p1->dlip->ip_node);
ragge
1.45
475
ragge
1.72
476                         return(p2);
477                 } else
478                         p3 = p3->forw;
ragge
1.26
479         }
ragge
1.72
480         return(p1);
ragge
1.27
481
ragge
1.72
482 ivloop:
483         if (p1->forw->op!=LABEL)
484                 return(p1);
485         return(p1);
486
487 #ifdef notyet
488         p3 = p2 = p2->forw;
489         n = 16;
490         do {
491                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
492                         return(p1);
493         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
494         do 
495                 if ((p1 = p1->back) == 0)
496                         return(p);
497         while (p1!=p3);
498         p1 = p;
499         tl = insertl(p1);
500         p3->subop = revbr[p3->subop];
501         decref(p3->ref);
502                 p2->back->forw = p1;
503         p3->forw->back = p1;
504         p1->back->forw = p2;
505         p1->forw->back = p3;
506         t = p1->back;
507         p1->back = p2->back;
508         p2->back = t;
509         t = p1->forw;
510         p1->forw = p3->forw;
511         p3->forw = t;
512         p2 = insertl(p1->forw);
513         p3->labno = p2->labno;
514         p3->ref = p2;
515         decref(tl);
516         if (tl->refc<=0)
517                 nrlab--;
518         nchange++;
519         return(p3);
ragge
1.69
520 #endif
ragge
1.72
521 }
ragge
1.33
522
ragge
1.72
523 static void
524 iterate(struct p2env *p2estruct dlnod *dl)
525 {
526         struct dlnod *p, *rp, *p1;
527         extern int negrel[];
528         extern size_t negrelsize;
529         int i;
ragge
1.33
530
ragge
1.72
531         nchange = 0;
532         for (p = dl->forwp!=0p = p->forw) {
533                 if ((p->op==JBR||p->op==CBR) && p->ref) {
534                         /* Resolves:
535                          * jbr L7
536                          * ...
537                          * L7: jbr L8
538                          */
539                         rp = nonlab(p->ref);
540                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
541                                 setlab(prp->labno);
542                                 decref(p->ref);
543                                 rp->ref->refc++;
544                                 p->ref = rp->ref;
545                                 nchange++;
546                         }
547                 }
548                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
549                         /* Resolves:
550                          * cbr L7
551                          * jbr L8
552                          * L7:
553                          */
554                         rp = p->ref;
555                         do
556                                 rp = rp->back;
557                         while (rp->op==LABEL);
558                         if (rp==p1) {
559                                 decref(p->ref);
560                                 p->ref = p1->ref;
561                                 setlab(pp1->labno);
562
563                                 iprem(p1);
564
565                                 p1->forw->back = p;
566                                 p->forw = p1->forw;
567
568                                 i = p->dlip->ip_node->n_left->n_op;
569                                 if (i < EQ || i - EQ >= (int)negrelsize)
570                                         comperr("deljumps: unexpected op");
571                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
572                                 nchange++;
573                         }
ragge
1.1
574                 }
ragge
1.72
575                 if (p->op == JBR) {
576                         /* Removes dead code */
577                         while (p->forw && p->forw->op!=LABEL &&
578                             p->forw->op!=EROU) {
579                                 nchange++;
580                                 if (p->forw->ref)
581                                         decref(p->forw->ref);
ragge
1.28
582
ragge
1.72
583                                 iprem(p->forw);
ragge
1.45
584
ragge
1.72
585                                 p->forw = p->forw->forw;
586                                 p->forw->back = p;
587                         }
588                         rp = p->forw;
589                         while (rp && rp->op==LABEL) {
590                                 if (p->ref == rp) {
591                                         p->back->forw = p->forw;
592                                         p->forw->back = p->back;
593                                         iprem(p);
594                                         p = p->back;
595                                         decref(rp);
596                                         nchange++;
597                                         break;
598                                 }
599                                 rp = rp->forw;
600                         }
601                 }
602                 if (p->op == JBR) {
603                         /* xjump(p); * needs tree rewrite; not yet */
604                         p = codemove(p);
ragge
1.45
605                 }
606         }
ragge
1.72
607 }
ragge
1.45
608
ragge
1.72
609 void
610 deljumps(struct p2env *p2e)
611 {
612         struct interpass *ipole = &p2e->ipole;
613         struct dlnod dln;
614         MARK mark;
615
616         markset(&mark);
ragge
1.28
617
ragge
1.72
618         memset(&dln0sizeof(dln));
619         listsetup(ipole, &dln);
620         do {
621                 refcount(p2e, &dln);
622                 do {
623                         iterate(p2e, &dln);
624                 } while (nchange);
ragge
1.28
625 #ifdef notyet
ragge
1.72
626                 comjump();
ragge
1.26
627 #endif
ragge
1.72
628         } while (nchange);
629
630         markfree(&mark);
ragge
1.1
631 }
632
633 void
634 optdump(struct interpass *ip)
635 {
636         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
637                 "deflab""defnam""asm" };
638         printf("type %s\n"nm[ip->type-1]);
639         switch (ip->type) {
640         case IP_NODE:
gmcgarry
1.52
641 #ifdef PCC_DEBUG
ragge
1.1
642                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
643 #endif
ragge
1.1
644                 break;
645         case IP_DEFLAB:
646                 printf("label " LABFMT "\n"ip->ip_lbl);
647                 break;
648         case IP_ASM:
649                 printf(": %s\n"ip->ip_asm);
650                 break;
651         }
652 }
pj
1.4
653
654 /*
655  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
656  *
657  * Also fills the labelinfo struct with information about which bblocks
658  * that contain which label.
659  */
660
ragge
1.30
661 void
ragge
1.74
662 bblocks_build(struct p2env *p2e)
pj
1.4
663 {
ragge
1.56
664         struct interpass *ipole = &p2e->ipole;
pj
1.4
665         struct interpass *ip;
666         struct basicblock *bb = NULL;
ragge
1.30
667         int lowhigh;
pj
1.8
668         int count = 0;
pj
1.4
669         int i;
670
ragge
1.74
671         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
ragge
1.56
672         low = p2e->ipp->ip_lblnum;
673         high = p2e->epp->ip_lblnum;
ragge
1.30
674
pj
1.4
675         /* 
676          * First statement is a leader.
677          * Any statement that is target of a jump is a leader.
678          * Any statement that immediately follows a jump is a leader.
679          */
ragge
1.75
680         DLIST_INIT(&p2e->bblocksbbelem);
ragge
1.38
681         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
682                 if (bb == NULL || (ip->type == IP_EPILOG) ||
683                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
684                         bb = tmpalloc(sizeof(struct basicblock));
685                         bb->first = ip;
686                         SLIST_INIT(&bb->children);
687                         SLIST_INIT(&bb->parents);
688                         bb->dfnum = 0;
689                         bb->dfparent = 0;
690                         bb->semi = 0;
691                         bb->ancestor = 0;
692                         bb->idom = 0;
693                         bb->samedom = 0;
694                         bb->bucket = NULL;
695                         bb->df = NULL;
696                         bb->dfchildren = NULL;
697                         bb->Aorig = NULL;
698                         bb->Aphi = NULL;
pantzer
1.59
699                         SLIST_INIT(&bb->phi);
ragge
1.34
700                         bb->bbnum = count;
ragge
1.56
701                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
702                         count++;
703                 }
704                 bb->last = ip;
705                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
706                     ip->ip_node->n_op == CBRANCH))
707                         bb = NULL;
708                 if (ip->type == IP_PROLOG)
709                         bb = NULL;
710         }
ragge
1.56
711         p2e->nbblocks = count;
ragge
1.30
712
ragge
1.31
713         if (b2debug) {
ragge
1.32
714                 printf("Basic blocks in func: %d, low %d, high %d\n",
715                     countlowhigh);
ragge
1.56
716                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.73
717                         printf("bb(%d) %p: first %p last %p\n"bb->bbnumbb,
ragge
1.31
718                             bb->firstbb->last);
719                 }
720         }
pj
1.4
721
ragge
1.74
722         p2e->labinfo.low = low;
723         p2e->labinfo.size = high - low + 1;
724         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
725         for (i = 0i < p2e->labinfo.sizei++) {
726                 p2e->labinfo.arr[i] = NULL;
pj
1.4
727         }
pj
1.8
728         
ragge
1.74
729         p2e->bbinfo.size = count + 1;
730         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
731         for (i = 0i < p2e->bbinfo.sizei++) {
732                 p2e->bbinfo.arr[i] = NULL;
pj
1.8
733         }
pj
1.4
734
ragge
1.32
735         /* Build the label table */
ragge
1.56
736         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
737                 if (bb->first->type == IP_DEFLAB)
ragge
1.74
738                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
739         }
740
741         if (b2debug) {
742                 printf("Label table:\n");
ragge
1.74
743                 for (i = 0i < p2e->labinfo.sizei++)
744                         if (p2e->labinfo.arr[i])
ragge
1.32
745                                 printf("Label %d bblock %p\n"i+low,
ragge
1.74
746                                     p2e->labinfo.arr[i]);
pj
1.4
747         }
748 }
749
750 /*
751  * Build the control flow graph.
752  */
753
754 void
ragge
1.74
755 cfg_build(struct p2env *p2e)
pj
1.4
756 {
757         /* Child and parent nodes */
758         struct cfgnode *cnode
759         struct cfgnode *pnode;
760         struct basicblock *bb;
761         
ragge
1.56
762         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.4
763
764                 if (bb->first->type == IP_EPILOG) {
765                         break;
766                 }
767
768                 cnode = tmpalloc(sizeof(struct cfgnode));
769                 pnode = tmpalloc(sizeof(struct cfgnode));
770                 pnode->bblock = bb;
771
772                 if ((bb->last->type == IP_NODE) && 
gmcgarry
1.47
773                     (bb->last->ip_node->n_op == GOTO) &&
774                     (bb->last->ip_node->n_left->n_op == ICON))  {
ragge
1.74
775                         if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low > 
776                             p2e->labinfo.size) {
pj
1.4
777                                 comperr("Label out of range: %d, base %d"
778                                         bb->last->ip_node->n_left->n_lval
ragge
1.74
779                                         p2e->labinfo.low);
pj
1.4
780                         }
ragge
1.74
781                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low];
ragge
1.11
782                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
783                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
784                         continue;
785                 }
786                 if ((bb->last->type == IP_NODE) && 
787                     (bb->last->ip_node->n_op == CBRANCH)) {
ragge
1.74
788                         if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low > 
789                             p2e->labinfo.size
pj
1.4
790                                 comperr("Label out of range: %d"
791                                         bb->last->ip_node->n_left->n_lval);
ragge
1.66
792
ragge
1.74
793                         cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low];
ragge
1.11
794                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
795                         SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
796                         cnode = tmpalloc(sizeof(struct cfgnode));
797                         pnode = tmpalloc(sizeof(struct cfgnode));
798                         pnode->bblock = bb;
799                 }
800
ragge
1.11
801                 cnode->bblock = DLIST_NEXT(bbbbelem);
802                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
803                 SLIST_INSERT_LAST(&bb->childrencnodecfgelem);
pj
1.4
804         }
805 }
pj
1.6
806
pj
1.8
807 void
808 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
809 {
810         struct cfgnode *cnode;
811         
812         if (bb->dfnum != 0)
813                 return;
814
815         bb->dfnum = ++dfsnum;
816         bb->dfparent = parent;
817         bbinfo->arr[bb->dfnum] = bb;
ragge
1.11
818         SLIST_FOREACH(cnode, &bb->childrencfgelem) {
pj
1.8
819                 cfg_dfs(cnode->bblockbb->dfnumbbinfo);
820         }
pj
1.13
821         /* Don't bring in unreachable nodes in the future */
pj
1.20
822         bbinfo->size = dfsnum + 1;
pj
1.8
823 }
824
ragge
1.11
825 static bittype *
826 setalloc(int nelem)
827 {
828         bittype *b;
829         int sz = (nelem+NUMBITS-1)/NUMBITS;
830
831         b = tmpalloc(sz * sizeof(bittype));
832         memset(b0sz * sizeof(bittype));
833         return b;
834 }
835
pj
1.8
836 /*
837  * Algorithm 19.9, pp 414 from Appel.
838  */
839
840 void
ragge
1.74
841 dominators(struct p2env *p2e)
pj
1.8
842 {
843         struct cfgnode *cnode;
844         struct basicblock *bb, *y, *v;
845         struct basicblock *s, *sprime, *p;
pj
1.10
846         int hi;
pj
1.8
847
ragge
1.56
848         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.74
849                 bb->bucket = setalloc(p2e->bbinfo.size);
850                 bb->df = setalloc(p2e->bbinfo.size);
851                 bb->dfchildren = setalloc(p2e->bbinfo.size);
pj
1.8
852         }
853
854         dfsnum = 0;
ragge
1.74
855         cfg_dfs(DLIST_NEXT(&p2e->bblocksbbelem), 0, &p2e->bbinfo);
pj
1.8
856
ragge
1.30
857         if (b2debug) {
858                 struct basicblock *bbb;
859                 struct cfgnode *ccnode;
860
ragge
1.56
861                 DLIST_FOREACH(bbb, &p2e->bblocksbbelem) {
ragge
1.30
862                         printf("Basic block %d, parents: "bbb->dfnum);
863                         SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
864                                 printf("%d, "ccnode->bblock->dfnum);
865                         }
866                         printf("\nChildren: ");
867                         SLIST_FOREACH(ccnode, &bbb->childrencfgelem) {
868                                 printf("%d, "ccnode->bblock->dfnum);
869                         }
870                         printf("\n");
pj
1.20
871                 }
872         }
873
ragge
1.74
874         for(h = p2e->bbinfo.size - 1h > 1h--) {
875                 bb = p2e->bbinfo.arr[h];
876                 p = s = p2e->bbinfo.arr[bb->dfparent];
ragge
1.11
877                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pantzer
1.60
878                         if (cnode->bblock->dfnum ==0)
879                                 continue/* Ignore unreachable code */
880
pj
1.8
881                         if (cnode->bblock->dfnum <= bb->dfnum
882                                 sprime = cnode->bblock;
pj
1.10
883                         else 
ragge
1.74
884                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
885                                               (cnode->bblock, &p2e->bbinfo)->semi];
pj
1.8
886                         if (sprime->dfnum < s->dfnum)
887                                 s = sprime;
888                 }
889                 bb->semi = s->dfnum;
pj
1.10
890                 BITSET(s->bucketbb->dfnum);
pj
1.8
891                 link(pbb);
ragge
1.74
892                 for (i = 1i < p2e->bbinfo.sizei++) {
pj
1.10
893                         if(TESTBIT(p->bucketi)) {
ragge
1.74
894                                 v = p2e->bbinfo.arr[i];
895                                 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
pj
1.10
896                                 if (y->semi == v->semi
pj
1.8
897                                         v->idom = p->dfnum;
898                                 else
899                                         v->samedom = y->dfnum;
900                         }
901                 }
ragge
1.74
902                 memset(p->bucket0, (p2e->bbinfo.size + 7)/8);
pj
1.8
903         }
ragge
1.30
904
905         if (b2debug) {
906                 printf("Num\tSemi\tAncest\tidom\n");
ragge
1.56
907                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.30
908                         printf("%d\t%d\t%d\t%d\n"bb->dfnumbb->semi,
909                             bb->ancestorbb->idom);
910                 }
pj
1.10
911         }
ragge
1.30
912
ragge
1.74
913         for(h = 2h < p2e->bbinfo.sizeh++) {
914                 bb = p2e->bbinfo.arr[h];
pj
1.10
915                 if (bb->samedom != 0) {
ragge
1.74
916                         bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
pj
1.10
917                 }
918         }
ragge
1.56
919         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
pj
1.10
920                 if (bb->idom != 0 && bb->idom != bb->dfnum) {
ragge
1.30
921                         BDEBUG(("Setting child %d of %d\n",
ragge
1.74
922                             bb->dfnump2e->bbinfo.arr[bb->idom]->dfnum));
923                         BITSET(p2e->bbinfo.arr[bb->idom]->dfchildrenbb->dfnum);
pj
1.10
924                 }
pj
1.8
925         }
926 }
927
928
929 struct basicblock *
930 ancestorwithlowestsemi(struct basicblock *bblockstruct bblockinfo *bbinfo)
931 {
932         struct basicblock *u = bblock;
933         struct basicblock *v = bblock;
934
935         while (v->ancestor != 0) {
936                 if (bbinfo->arr[v->semi]->dfnum < 
pj
1.10
937                     bbinfo->arr[u->semi]->dfnum
pj
1.8
938                         u = v;
939                 v = bbinfo->arr[v->ancestor];
940         }
941         return u;
942 }
943
944 void
945 link(struct basicblock *parentstruct basicblock *child)
946 {
947         child->ancestor = parent->dfnum;
948 }
949
950 void
ragge
1.74
951 computeDF(struct p2env *p2estruct basicblock *bblock)
pj
1.8
952 {
953         struct cfgnode *cnode;
pj
1.10
954         int hi;
pj
1.8
955         
ragge
1.11
956         SLIST_FOREACH(cnode, &bblock->childrencfgelem) {
pj
1.8
957                 if (cnode->bblock->idom != bblock->dfnum)
958                         BITSET(bblock->dfcnode->bblock->dfnum);
959         }
ragge
1.74
960         for (h = 1h < p2e->bbinfo.sizeh++) {
pj
1.10
961                 if (!TESTBIT(bblock->dfchildrenh))
962                         continue;
ragge
1.74
963                 computeDF(p2ep2e->bbinfo.arr[h]);
964                 for (i = 1i < p2e->bbinfo.sizei++) {
965                         if (TESTBIT(p2e->bbinfo.arr[h]->dfi) && 
966                             (p2e->bbinfo.arr[i] == bblock ||
967                              (bblock->dfnum != p2e->bbinfo.arr[i]->idom))) 
pj
1.8
968                             BITSET(bblock->dfi);
969                 }
970         }
971 }
pj
1.15
972
ragge
1.74
973 void printDF(struct p2env *p2e)
pantzer
1.59
974 {
975         struct basicblock *bb;
976         int i;
977
978         printf("Dominance frontiers:\n");
979     
980         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
981                 printf("bb %d : "bb->dfnum);
982         
ragge
1.74
983                 for (i=1i < p2e->bbinfo.size;i++) {
pantzer
1.59
984                         if (TESTBIT(bb->df,i)) {
985                                 printf("%d ",i);
986                         }
987                 }
988             
989                 printf("\n");
990         }
991