Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20110816061416

Diff

Diff from 1.82 to:

Annotations

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

Annotated File View

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