Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100512170121

Diff

Diff from 1.74 to:

Annotations

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

Annotated File View

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