Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:plunky:20121107100717

Diff

Diff from 1.86 to:

Annotations

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

Annotated File View

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