Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100524051107

Diff

Diff from 1.78 to:

Annotations

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

Annotated File View

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