Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100512150757

Diff

Diff from 1.73 to:

Annotations

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

Annotated File View

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