Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20100521160828

Diff

Diff from 1.77 to:

Annotations

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

Annotated File View

ragge
1.77
1 /*      $Id: optim2.c,v 1.77 2010/05/21 16:08:28 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);
pj
1.4
76
ragge
1.66
77 /* create "proper" basic blocks, add labels where needed (so bblocks have labels) */
78 /* run before bb generate */
79 static void add_labels(struct p2env*) ;
80
81 /* Perform trace scheduling, try to get rid of gotos as much as possible */
82 void TraceSchedule(struct p2env*) ;
83
84 #ifdef ENABLE_NEW
85 static void do_cse(struct p2envp2e) ;
86 #endif
87
88 /* Walk the complete set, performing a function on each node. 
89  * if type is given, apply function on only that type */
ragge
1.67
90 void WalkAll(struct p2envp2evoid (*f) (NODE*, void*), voidargint type) ;
ragge
1.66
91
92 void BBLiveDead(struct basicblockbblockint whatunsigned int variable) ;
93
94 /* Fill the live/dead code */
ragge
1.67
95 void LiveDead(struct p2envp2eint whatunsigned int variable) ;
ragge
1.66
96
pantzer
1.63
97 #ifdef PCC_DEBUG
ragge
1.74
98 void printflowdiagram(struct p2env *, char *);
pantzer
1.63
99 #endif
100
ragge
1.38
101 void
ragge
1.56
102 optimize(struct p2env *p2e)
ragge
1.38
103 {
ragge
1.56
104         struct interpass *ipole = &p2e->ipole;
ragge
1.38
105
106         if (b2debug) {
107                 printf("initial links\n");
108                 printip(ipole);
109         }
110
111         if (xdeljumps)
ragge
1.56
112                 deljumps(p2e); /* Delete redundant jumps and dead code */
ragge
1.38
113
ragge
1.66
114         if (xssaflag)
115                 add_labels(p2e) ;
116 #ifdef ENABLE_NEW
117         do_cse(p2e);
118 #endif
119
ragge
1.38
120 #ifdef PCC_DEBUG
121         if (b2debug) {
122                 printf("links after deljumps\n");
123                 printip(ipole);
124         }
125 #endif
126         if (xssaflag || xtemps) {
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) {
ragge
1.77
136                 BDEBUG(("Calling liveanal\n"));
137                 liveanal(p2e);
ragge
1.38
138                 BDEBUG(("Calling dominators\n"));
ragge
1.74
139                 dominators(p2e);
ragge
1.38
140                 BDEBUG(("Calling computeDF\n"));
ragge
1.74
141                 computeDF(p2eDLIST_NEXT(&p2e->bblocksbbelem));
pantzer
1.59
142
143                 if (b2debug) {
ragge
1.74
144                         printDF(p2e);
pantzer
1.59
145                 }
146
147                 BDEBUG(("Calling placePhiFunctions\n"));
148
ragge
1.74
149                 placePhiFunctions(p2e);
pantzer
1.59
150
151                 BDEBUG(("Calling renamevar\n"));
152
ragge
1.74
153                 renamevar(p2e,DLIST_NEXT(&p2e->bblocksbbelem));
pantzer
1.59
154
155                 BDEBUG(("Calling removephi\n"));
156
pantzer
1.63
157 #ifdef PCC_DEBUG
ragge
1.74
158                 printflowdiagram(p2e"ssa");
pantzer
1.63
159 #endif
160
ragge
1.74
161                 removephi(p2e);
pantzer
1.59
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                 bblocks_build(p2e, &labinfo, &bbinfo);
180                 BDEBUG(("Calling cfg_build\n"));
181                 cfg_build(p2e, &labinfo);
182
183                 TraceSchedule(p2e);
184 #ifdef PCC_DEBUG
185                 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
186
187                 if (b2debug) {
188                         printf("after tracesched\n");
189                         printip(ipole);
190                         fflush(stdout) ;
191                 }
192 #endif
193 #endif
194
195                 /* Now, clean up the gotos we do not need any longer */
196                 if (xdeljumps)
197                         deljumps(p2e); /* Delete redundant jumps and dead code */
pantzer
1.59
198
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);
ragge
1.76
283         struct interpass *nip;
ragge
1.72
284         struct dlnod *p, *lastp;
285         NODE *q;
286
287         lastp = dl;
288         while (ip->type != IP_DEFLAB)
289                 ip = DLIST_NEXT(ip,qelem);
290         ip = DLIST_NEXT(ip,qelem);
291         while (ip->type != IP_DEFLAB)
292                 ip = DLIST_NEXT(ip,qelem);
293         /* Now ip is at the beginning */
294         for (;;) {
295                 ip = DLIST_NEXT(ip,qelem);
296                 if (ip == ipole)
297                         break;
298                 p = tmpalloc(sizeof(struct dlnod));
299                 p->labno = 0;
300                 p->dlip = ip;
301                 switch (ip->type) {
302                 case IP_DEFLAB:
303                         p->op = LABEL;
304                         p->labno = ip->ip_lbl;
305                         break;
ragge
1.26
306
ragge
1.72
307                 case IP_NODE:
308                         q = ip->ip_node;
309                         switch (q->n_op) {
310                         case GOTO:
311                                 p->op = JBR;
312                                 p->labno = q->n_left->n_lval;
313                                 break;
314                         case CBRANCH:
315                                 p->op = CBR;
316                                 p->labno = q->n_right->n_lval;
317                                 break;
ragge
1.76
318                         case ASSIGN:
319                                 /* remove ASSIGN to self for regs */
320                                 if (q->n_left->n_op == REG && 
321                                     q->n_right->n_op == REG &&
322                                     regno(q->n_left) == regno(q->n_right)) {
323                                         nip = DLIST_PREV(ipqelem);
324                                         tfree(q);
325                                         DLIST_REMOVE(ipqelem);
326                                         ip = nip;
327                                         continue;
328                                 }
329                                 /* FALLTHROUGH */
ragge
1.72
330                         default:
331                                 p->op = STMT;
332                                 break;
333                         }
334                         break;
ragge
1.28
335
ragge
1.72
336                 case IP_ASM:
337                         p->op = STMT;
338                         break;
ragge
1.45
339
ragge
1.72
340                 case IP_EPILOG:
341                         p->op = EROU;
ragge
1.45
342                         break;
ragge
1.72
343
344                 default:
345                         comperr("listsetup: bad ip node %d"ip->type);
346                 }
347                 p->forw = 0;
348                 p->back = lastp;
349                 lastp->forw = p;
350                 lastp = p;
351                 p->ref = 0;
ragge
1.45
352         }
ragge
1.72
353 }
354
355 static struct dlnod *
356 nonlab(struct dlnod *p)
357 {
358         while (p && p->op==LABEL)
359                 p = p->forw;
360         return(p);
361 }
ragge
1.26
362
ragge
1.72
363 static void
364 iprem(struct dlnod *p)
365 {
366         if (p->dlip->type == IP_NODE)
367                 tfree(p->dlip->ip_node);
368         DLIST_REMOVE(p->dlipqelem);
369 }
ragge
1.26
370
ragge
1.72
371 static void
372 decref(struct dlnod *p)
373 {
374         if (--p->refc <= 0) {
375                 iprem(p);
376                 p->back->forw = p->forw;
377                 p->forw->back = p->back;
378         }
379 }
380
381 static void
382 setlab(struct dlnod *pint labno)
383 {
384         p->labno = labno;
385         if (p->op == JBR)
386                 p->dlip->ip_node->n_left->n_lval = labno;
ragge
1.76
387         else if (p->op == CBR) {
ragge
1.72
388                 p->dlip->ip_node->n_right->n_lval = labno;
ragge
1.76
389                 p->dlip->ip_node->n_left->n_label = labno;
390         } else
ragge
1.72
391                 comperr("setlab bad op %d"p->op);
392 }
ragge
1.45
393
ragge
1.72
394 /*
395  * Label reference counting and removal of unused labels.
396  */
397 #define LABHS 127
398 static void
399 refcount(struct p2env *p2estruct dlnod *dl)
400 {
401         struct dlnod *p, *lp;
402         struct dlnod *labhash[LABHS];
403         struct dlnod **hp, *tp;
404
405         /* Clear label hash */
406         for (hp = labhashhp < &labhash[LABHS];)
407                 *hp++ = 0;
408         /* Enter labels into hash.  Later overwrites earlier */
409         for (p = dl->forwp!=0p = p->forw)
410                 if (p->op==LABEL) {
411                         labhash[p->labno % LABHS] = p;
412                         p->refc = 0;
413                 }
414
415         /* search for jumps to labels and fill in reference */
416         for (p = dl->forwp!=0p = p->forw) {
417                 if (p->op==JBR || p->op==CBR) {
418                         p->ref = 0;
419                         lp = labhash[p->labno % LABHS];
420                         if (lp==0 || p->labno!=lp->labno)
421                             for (lp = dl->forwlp!=0lp = lp->forw) {
422                                 if (lp->op==LABEL && p->labno==lp->labno)
423                                         break;
424                             }
425                         if (lp) {
426                                 tp = nonlab(lp)->back;
427                                 if (tp!=lp) {
428                                         setlab(ptp->labno);
429                                         lp = tp;
ragge
1.45
430                                 }
ragge
1.72
431                                 p->ref = lp;
432                                 lp->refc++;
ragge
1.27
433                         }
434                 }
ragge
1.72
435         }
436         for (p = dl->forwp!=0p = p->forw)
ragge
1.76
437                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
ragge
1.72
438                         decref(p);
439 }
440
441 static int nchange;
ragge
1.45
442
ragge
1.72
443 static struct dlnod *
444 codemove(struct dlnod *p)
445 {
446         struct dlnod *p1, *p2, *p3;
447 #ifdef notyet
448         struct dlnod *t, *tl;
449         int n;
450 #endif
ragge
1.27
451
ragge
1.72
452         p1 = p;
453         if (p1->op!=JBR || (p2 = p1->ref)==0)
454                 return(p1);
455         while (p2->op == LABEL)
456                 if ((p2 = p2->back) == 0)
457                         return(p1);
458         if (p2->op!=JBR)
459                 goto ivloop;
460         if (p1==p2)
461                 return(p1);
462         p2 = p2->forw;
463         p3 = p1->ref;
464         while (p3) {
465                 if (p3->op==JBR) {
466                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
467                                 return(p1);
468                         nchange++;
469                         p1->back->forw = p2;
470                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
471
472                         p1->forw->back = p3;
473                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
474
475
476                         p2->back->forw = p3->forw;
477                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
478
479                         p3->forw->back = p2->back;
480                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
481
482                         p2->back = p1->back;
483                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
484
485                         p3->forw = p1->forw;
486                         p3->dlip->qelem.q_forw = p1->forw->dlip;
487
488                         decref(p1->ref);
489                         if (p1->dlip->type == IP_NODE)
490                                 tfree(p1->dlip->ip_node);
ragge
1.45
491
ragge
1.72
492                         return(p2);
493                 } else
494                         p3 = p3->forw;
ragge
1.26
495         }
ragge
1.72
496         return(p1);
ragge
1.27
497
ragge
1.72
498 ivloop:
499         if (p1->forw->op!=LABEL)
500                 return(p1);
501         return(p1);
502
503 #ifdef notyet
504         p3 = p2 = p2->forw;
505         n = 16;
506         do {
507                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
508                         return(p1);
509         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
510         do 
511                 if ((p1 = p1->back) == 0)
512                         return(p);
513         while (p1!=p3);
514         p1 = p;
515         tl = insertl(p1);
516         p3->subop = revbr[p3->subop];
517         decref(p3->ref);
518                 p2->back->forw = p1;
519         p3->forw->back = p1;
520         p1->back->forw = p2;
521         p1->forw->back = p3;
522         t = p1->back;
523         p1->back = p2->back;
524         p2->back = t;
525         t = p1->forw;
526         p1->forw = p3->forw;
527         p3->forw = t;
528         p2 = insertl(p1->forw);
529         p3->labno = p2->labno;
530         p3->ref = p2;
531         decref(tl);
532         if (tl->refc<=0)
533                 nrlab--;
534         nchange++;
535         return(p3);
ragge
1.69
536 #endif
ragge
1.72
537 }
ragge
1.33
538
ragge
1.72
539 static void
540 iterate(struct p2env *p2estruct dlnod *dl)
541 {
542         struct dlnod *p, *rp, *p1;
543         extern int negrel[];
544         extern size_t negrelsize;
545         int i;
ragge
1.33
546
ragge
1.72
547         nchange = 0;
548         for (p = dl->forwp!=0p = p->forw) {
549                 if ((p->op==JBR||p->op==CBR) && p->ref) {
550                         /* Resolves:
551                          * jbr L7
552                          * ...
553                          * L7: jbr L8
554                          */
555                         rp = nonlab(p->ref);
556                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
557                                 setlab(prp->labno);
558                                 decref(p->ref);
559                                 rp->ref->refc++;
560                                 p->ref = rp->ref;
561                                 nchange++;
562                         }
563                 }
564                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
565                         /* Resolves:
566                          * cbr L7
567                          * jbr L8
568                          * L7:
569                          */
570                         rp = p->ref;
571                         do
572                                 rp = rp->back;
573                         while (rp->op==LABEL);
574                         if (rp==p1) {
575                                 decref(p->ref);
576                                 p->ref = p1->ref;
577                                 setlab(pp1->labno);
578
579                                 iprem(p1);
580
581                                 p1->forw->back = p;
582                                 p->forw = p1->forw;
583
584                                 i = p->dlip->ip_node->n_left->n_op;
585                                 if (i < EQ || i - EQ >= (int)negrelsize)
586                                         comperr("deljumps: unexpected op");
587                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
588                                 nchange++;
589                         }
ragge
1.1
590                 }
ragge
1.72
591                 if (p->op == JBR) {
592                         /* Removes dead code */
593                         while (p->forw && p->forw->op!=LABEL &&
594                             p->forw->op!=EROU) {
595                                 nchange++;
596                                 if (p->forw->ref)
597                                         decref(p->forw->ref);
ragge
1.28
598
ragge
1.72
599                                 iprem(p->forw);
ragge
1.45
600
ragge
1.72
601                                 p->forw = p->forw->forw;
602                                 p->forw->back = p;
603                         }
604                         rp = p->forw;
605                         while (rp && rp->op==LABEL) {
606                                 if (p->ref == rp) {
607                                         p->back->forw = p->forw;
608                                         p->forw->back = p->back;
609                                         iprem(p);
610                                         p = p->back;
611                                         decref(rp);
612                                         nchange++;
613                                         break;
614                                 }
615                                 rp = rp->forw;
616                         }
617                 }
618                 if (p->op == JBR) {
619                         /* xjump(p); * needs tree rewrite; not yet */
620                         p = codemove(p);
ragge
1.45
621                 }
622         }
ragge
1.72
623 }
ragge
1.45
624
ragge
1.72
625 void
626 deljumps(struct p2env *p2e)
627 {
628         struct interpass *ipole = &p2e->ipole;
629         struct dlnod dln;
630         MARK mark;
631
632         markset(&mark);
ragge
1.28
633
ragge
1.72
634         memset(&dln0sizeof(dln));
635         listsetup(ipole, &dln);
636         do {
637                 refcount(p2e, &dln);
638                 do {
639                         iterate(p2e, &dln);
640                 } while (nchange);
ragge
1.28
641 #ifdef notyet
ragge
1.72
642                 comjump();
ragge
1.26
643 #endif
ragge
1.72
644         } while (nchange);
645
646         markfree(&mark);
ragge
1.1
647 }
648
649 void
650 optdump(struct interpass *ip)
651 {
652         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
653                 "deflab""defnam""asm" };
654         printf("type %s\n"nm[ip->type-1]);
655         switch (ip->type) {
656         case IP_NODE:
gmcgarry
1.52
657 #ifdef PCC_DEBUG
ragge
1.1
658                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
659 #endif
ragge
1.1
660                 break;
661         case IP_DEFLAB:
662                 printf("label " LABFMT "\n"ip->ip_lbl);
663                 break;
664         case IP_ASM:
665                 printf(": %s\n"ip->ip_asm);
666                 break;
667         }
668 }
pj
1.4
669
670 /*
671  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
672  *
673  * Also fills the labelinfo struct with information about which bblocks
674  * that contain which label.
675  */
676
ragge
1.30
677 void
ragge
1.74
678 bblocks_build(struct p2env *p2e)
pj
1.4
679 {
ragge
1.56
680         struct interpass *ipole = &p2e->ipole;
pj
1.4
681         struct interpass *ip;
682         struct basicblock *bb = NULL;
ragge
1.30
683         int lowhigh;
pj
1.8
684         int count = 0;
pj
1.4
685         int i;
686
ragge
1.74
687         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
ragge
1.56
688         low = p2e->ipp->ip_lblnum;
689         high = p2e->epp->ip_lblnum;
ragge
1.30
690
pj
1.4
691         /* 
692          * First statement is a leader.
693          * Any statement that is target of a jump is a leader.
694          * Any statement that immediately follows a jump is a leader.
695          */
ragge
1.75
696         DLIST_INIT(&p2e->bblocksbbelem);
ragge
1.38
697         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
698                 if (bb == NULL || (ip->type == IP_EPILOG) ||
699                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
700                         bb = tmpalloc(sizeof(struct basicblock));
701                         bb->first = ip;
702                         SLIST_INIT(&bb->children);
703                         SLIST_INIT(&bb->parents);
704                         bb->dfnum = 0;
705                         bb->dfparent = 0;
706                         bb->semi = 0;
707                         bb->ancestor = 0;
708                         bb->idom = 0;
709                         bb->samedom = 0;
710                         bb->bucket = NULL;
711                         bb->df = NULL;
712                         bb->dfchildren = NULL;
713                         bb->Aorig = NULL;
714                         bb->Aphi = NULL;
pantzer
1.59
715                         SLIST_INIT(&bb->phi);
ragge
1.34
716                         bb->bbnum = count;
ragge
1.56
717                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
718                         count++;
719                 }
720                 bb->last = ip;
721                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
722                     ip->ip_node->n_op == CBRANCH))
723                         bb = NULL;
724                 if (ip->type == IP_PROLOG)
725                         bb = NULL;
726         }
ragge
1.56
727         p2e->nbblocks = count;
ragge
1.30
728
ragge
1.31
729         if (b2debug) {
ragge
1.32
730                 printf("Basic blocks in func: %d, low %d, high %d\n",
731                     countlowhigh);
ragge
1.56
732                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.73
733                         printf("bb(%d) %p: first %p last %p\n"bb->bbnumbb,
ragge
1.31
734                             bb->firstbb->last);
735                 }
736         }
pj
1.4
737
ragge
1.74
738         p2e->labinfo.low = low;
739         p2e->labinfo.size = high - low + 1;
740         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
741         for (i = 0i < p2e->labinfo.sizei++) {
742                 p2e->labinfo.arr[i] = NULL;
pj
1.4
743         }
pj
1.8
744         
ragge
1.74
745         p2e->bbinfo.size = count + 1;
746         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
747         for (i = 0i < p2e->bbinfo.sizei++) {
748                 p2e->bbinfo.arr[i] = NULL;
pj
1.8
749         }
pj
1.4
750
ragge
1.32
751         /* Build the label table */
ragge
1.56
752         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
753                 if (bb->first->type == IP_DEFLAB)
ragge
1.74
754                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
755         }
756
757         if (b2debug) {
ragge
1.76
758                 static void printip2(struct interpass *);
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                         BITSET(bblock->dfcnode->bblock->dfnum);
985