Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20120818154413

Diff

Diff from 1.84 to:

Annotations

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

Annotated File View

ragge
1.84
1 /*      $Id: optim2.c,v 1.84 2012/08/18 15:44:14 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:
ragge
1.84
318                                 if (q->n_left->n_op == ICON) {
319                                         p->op = JBR;
320                                         p->labno = q->n_left->n_lval;
321                                 } else 
322                                         p->op = STMT;
ragge
1.72
323                                 break;
324                         case CBRANCH:
325                                 p->op = CBR;
326                                 p->labno = q->n_right->n_lval;
327                                 break;
ragge
1.76
328                         case ASSIGN:
329                                 /* remove ASSIGN to self for regs */
330                                 if (q->n_left->n_op == REG && 
331                                     q->n_right->n_op == REG &&
332                                     regno(q->n_left) == regno(q->n_right)) {
333                                         nip = DLIST_PREV(ipqelem);
334                                         tfree(q);
335                                         DLIST_REMOVE(ipqelem);
336                                         ip = nip;
337                                         continue;
338                                 }
339                                 /* FALLTHROUGH */
ragge
1.72
340                         default:
341                                 p->op = STMT;
342                                 break;
343                         }
344                         break;
ragge
1.28
345
ragge
1.72
346                 case IP_ASM:
347                         p->op = STMT;
348                         break;
ragge
1.45
349
ragge
1.72
350                 case IP_EPILOG:
351                         p->op = EROU;
ragge
1.45
352                         break;
ragge
1.72
353
354                 default:
355                         comperr("listsetup: bad ip node %d"ip->type);
356                 }
357                 p->forw = 0;
358                 p->back = lastp;
359                 lastp->forw = p;
360                 lastp = p;
361                 p->ref = 0;
ragge
1.45
362         }
ragge
1.72
363 }
364
ragge
1.84
365 /*
366  * Traverse to the first statement behind a label.
367  */
ragge
1.72
368 static struct dlnod *
369 nonlab(struct dlnod *p)
370 {
371         while (p && p->op==LABEL)
372                 p = p->forw;
373         return(p);
374 }
ragge
1.26
375
ragge
1.72
376 static void
377 iprem(struct dlnod *p)
378 {
379         if (p->dlip->type == IP_NODE)
380                 tfree(p->dlip->ip_node);
381         DLIST_REMOVE(p->dlipqelem);
382 }
ragge
1.26
383
ragge
1.72
384 static void
385 decref(struct dlnod *p)
386 {
387         if (--p->refc <= 0) {
388                 iprem(p);
389                 p->back->forw = p->forw;
390                 p->forw->back = p->back;
391         }
392 }
393
ragge
1.84
394 /*
395  * Change a label number for jump/branch instruction to labno.
396  */
ragge
1.72
397 static void
398 setlab(struct dlnod *pint labno)
399 {
400         p->labno = labno;
401         if (p->op == JBR)
402                 p->dlip->ip_node->n_left->n_lval = labno;
ragge
1.76
403         else if (p->op == CBR) {
ragge
1.72
404                 p->dlip->ip_node->n_right->n_lval = labno;
ragge
1.76
405                 p->dlip->ip_node->n_left->n_label = labno;
406         } else
ragge
1.72
407                 comperr("setlab bad op %d"p->op);
408 }
ragge
1.45
409
ragge
1.72
410 /*
ragge
1.84
411  * See if a label is used outside of us.
412  */
413 static int
414 inuse(struct p2env *p2eint lbl)
415 {
416         int *l;
417
418         for (l = p2e->epp->ip_labels; *ll++)
419                 if (*l == lbl)
420                         return 1;
421         return 0;
422 }
423
424 /*
ragge
1.72
425  * Label reference counting and removal of unused labels.
426  */
427 #define LABHS 127
428 static void
429 refcount(struct p2env *p2estruct dlnod *dl)
430 {
431         struct dlnod *p, *lp;
432         struct dlnod *labhash[LABHS];
433         struct dlnod **hp, *tp;
434
435         /* Clear label hash */
436         for (hp = labhashhp < &labhash[LABHS];)
437                 *hp++ = 0;
438         /* Enter labels into hash.  Later overwrites earlier */
ragge
1.84
439         for (p = dl->forwp!=0p = p->forw) {
ragge
1.72
440                 if (p->op==LABEL) {
441                         labhash[p->labno % LABHS] = p;
442                         p->refc = 0;
ragge
1.84
443                         if (inuse(p2ep->labno))
444                                 p->refc = 1000/* never remove */
ragge
1.72
445                 }
ragge
1.84
446         }
ragge
1.72
447         /* search for jumps to labels and fill in reference */
448         for (p = dl->forwp!=0p = p->forw) {
449                 if (p->op==JBR || p->op==CBR) {
450                         p->ref = 0;
451                         lp = labhash[p->labno % LABHS];
452                         if (lp==0 || p->labno!=lp->labno)
453                             for (lp = dl->forwlp!=0lp = lp->forw) {
454                                 if (lp->op==LABEL && p->labno==lp->labno)
455                                         break;
456                             }
457                         if (lp) {
458                                 tp = nonlab(lp)->back;
459                                 if (tp!=lp) {
460                                         setlab(ptp->labno);
461                                         lp = tp;
ragge
1.45
462                                 }
ragge
1.72
463                                 p->ref = lp;
464                                 lp->refc++;
ragge
1.27
465                         }
466                 }
ragge
1.72
467         }
468         for (p = dl->forwp!=0p = p->forw)
ragge
1.76
469                 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
ragge
1.72
470                         decref(p);
471 }
472
473 static int nchange;
ragge
1.45
474
ragge
1.72
475 static struct dlnod *
476 codemove(struct dlnod *p)
477 {
478         struct dlnod *p1, *p2, *p3;
479 #ifdef notyet
480         struct dlnod *t, *tl;
481         int n;
482 #endif
ragge
1.27
483
ragge
1.72
484         p1 = p;
485         if (p1->op!=JBR || (p2 = p1->ref)==0)
486                 return(p1);
487         while (p2->op == LABEL)
488                 if ((p2 = p2->back) == 0)
489                         return(p1);
490         if (p2->op!=JBR)
491                 goto ivloop;
492         if (p1==p2)
493                 return(p1);
494         p2 = p2->forw;
495         p3 = p1->ref;
496         while (p3) {
497                 if (p3->op==JBR) {
498                         if (p1==p3 || p1->forw==p3 || p1->back==p3)
499                                 return(p1);
500                         nchange++;
501                         p1->back->forw = p2;
502                         p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
503
504                         p1->forw->back = p3;
505                         p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
506
507
508                         p2->back->forw = p3->forw;
509                         p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
510
511                         p3->forw->back = p2->back;
512                         p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
513
514                         p2->back = p1->back;
515                         p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
516
517                         p3->forw = p1->forw;
518                         p3->dlip->qelem.q_forw = p1->forw->dlip;
519
520                         decref(p1->ref);
521                         if (p1->dlip->type == IP_NODE)
522                                 tfree(p1->dlip->ip_node);
ragge
1.45
523
ragge
1.72
524                         return(p2);
525                 } else
526                         p3 = p3->forw;
ragge
1.26
527         }
ragge
1.72
528         return(p1);
ragge
1.27
529
ragge
1.72
530 ivloop:
531         if (p1->forw->op!=LABEL)
532                 return(p1);
533         return(p1);
534
535 #ifdef notyet
536         p3 = p2 = p2->forw;
537         n = 16;
538         do {
539                 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
540                         return(p1);
541         } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
542         do 
543                 if ((p1 = p1->back) == 0)
544                         return(p);
545         while (p1!=p3);
546         p1 = p;
547         tl = insertl(p1);
548         p3->subop = revbr[p3->subop];
549         decref(p3->ref);
550                 p2->back->forw = p1;
551         p3->forw->back = p1;
552         p1->back->forw = p2;
553         p1->forw->back = p3;
554         t = p1->back;
555         p1->back = p2->back;
556         p2->back = t;
557         t = p1->forw;
558         p1->forw = p3->forw;
559         p3->forw = t;
560         p2 = insertl(p1->forw);
561         p3->labno = p2->labno;
562         p3->ref = p2;
563         decref(tl);
564         if (tl->refc<=0)
565                 nrlab--;
566         nchange++;
567         return(p3);
ragge
1.69
568 #endif
ragge
1.72
569 }
ragge
1.33
570
ragge
1.72
571 static void
572 iterate(struct p2env *p2estruct dlnod *dl)
573 {
574         struct dlnod *p, *rp, *p1;
575         extern int negrel[];
576         extern size_t negrelsize;
577         int i;
ragge
1.33
578
ragge
1.72
579         nchange = 0;
580         for (p = dl->forwp!=0p = p->forw) {
581                 if ((p->op==JBR||p->op==CBR) && p->ref) {
582                         /* Resolves:
583                          * jbr L7
584                          * ...
585                          * L7: jbr L8
586                          */
587                         rp = nonlab(p->ref);
588                         if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
589                                 setlab(prp->labno);
590                                 decref(p->ref);
591                                 rp->ref->refc++;
592                                 p->ref = rp->ref;
593                                 nchange++;
594                         }
595                 }
596                 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
597                         /* Resolves:
598                          * cbr L7
599                          * jbr L8
600                          * L7:
601                          */
602                         rp = p->ref;
603                         do
604                                 rp = rp->back;
605                         while (rp->op==LABEL);
606                         if (rp==p1) {
607                                 decref(p->ref);
608                                 p->ref = p1->ref;
609                                 setlab(pp1->labno);
610
611                                 iprem(p1);
612
613                                 p1->forw->back = p;
614                                 p->forw = p1->forw;
615
616                                 i = p->dlip->ip_node->n_left->n_op;
617                                 if (i < EQ || i - EQ >= (int)negrelsize)
618                                         comperr("deljumps: unexpected op");
619                                 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
620                                 nchange++;
621                         }
ragge
1.1
622                 }
ragge
1.72
623                 if (p->op == JBR) {
624                         /* Removes dead code */
625                         while (p->forw && p->forw->op!=LABEL &&
626                             p->forw->op!=EROU) {
627                                 nchange++;
628                                 if (p->forw->ref)
629                                         decref(p->forw->ref);
ragge
1.28
630
ragge
1.72
631                                 iprem(p->forw);
ragge
1.45
632
ragge
1.72
633                                 p->forw = p->forw->forw;
634                                 p->forw->back = p;
635                         }
636                         rp = p->forw;
637                         while (rp && rp->op==LABEL) {
638                                 if (p->ref == rp) {
639                                         p->back->forw = p->forw;
640                                         p->forw->back = p->back;
641                                         iprem(p);
642                                         p = p->back;
643                                         decref(rp);
644                                         nchange++;
645                                         break;
646                                 }
647                                 rp = rp->forw;
648                         }
649                 }
650                 if (p->op == JBR) {
651                         /* xjump(p); * needs tree rewrite; not yet */
652                         p = codemove(p);
ragge
1.45
653                 }
654         }
ragge
1.72
655 }
ragge
1.45
656
ragge
1.72
657 void
658 deljumps(struct p2env *p2e)
659 {
660         struct interpass *ipole = &p2e->ipole;
661         struct dlnod dln;
662         MARK mark;
663
664         markset(&mark);
ragge
1.28
665
ragge
1.72
666         memset(&dln0sizeof(dln));
667         listsetup(ipole, &dln);
668         do {
669                 refcount(p2e, &dln);
670                 do {
671                         iterate(p2e, &dln);
672                 } while (nchange);
ragge
1.28
673 #ifdef notyet
ragge
1.72
674                 comjump();
ragge
1.26
675 #endif
ragge
1.72
676         } while (nchange);
677
678         markfree(&mark);
ragge
1.1
679 }
680
681 void
682 optdump(struct interpass *ip)
683 {
684         static char *nm[] = { "node""prolog""newblk""epilog""locctr",
685                 "deflab""defnam""asm" };
686         printf("type %s\n"nm[ip->type-1]);
687         switch (ip->type) {
688         case IP_NODE:
gmcgarry
1.52
689 #ifdef PCC_DEBUG
ragge
1.1
690                 fwalk(ip->ip_nodee2print0);
gmcgarry
1.52
691 #endif
ragge
1.1
692                 break;
693         case IP_DEFLAB:
694                 printf("label " LABFMT "\n"ip->ip_lbl);
695                 break;
696         case IP_ASM:
697                 printf(": %s\n"ip->ip_asm);
698                 break;
699         }
700 }
pj
1.4
701
702 /*
703  * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
704  *
705  * Also fills the labelinfo struct with information about which bblocks
706  * that contain which label.
707  */
708
ragge
1.30
709 void
ragge
1.74
710 bblocks_build(struct p2env *p2e)
pj
1.4
711 {
ragge
1.56
712         struct interpass *ipole = &p2e->ipole;
pj
1.4
713         struct interpass *ip;
714         struct basicblock *bb = NULL;
ragge
1.30
715         int lowhigh;
pj
1.8
716         int count = 0;
pj
1.4
717         int i;
718
ragge
1.74
719         BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
ragge
1.56
720         low = p2e->ipp->ip_lblnum;
721         high = p2e->epp->ip_lblnum;
ragge
1.30
722
pj
1.4
723         /* 
724          * First statement is a leader.
725          * Any statement that is target of a jump is a leader.
726          * Any statement that immediately follows a jump is a leader.
727          */
ragge
1.75
728         DLIST_INIT(&p2e->bblocksbbelem);
ragge
1.38
729         DLIST_FOREACH(ipipoleqelem) {
ragge
1.31
730                 if (bb == NULL || (ip->type == IP_EPILOG) ||
731                     (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
732                         bb = tmpalloc(sizeof(struct basicblock));
733                         bb->first = ip;
734                         SLIST_INIT(&bb->parents);
ragge
1.83
735                         SLIST_INIT(&bb->child);
ragge
1.31
736                         bb->dfnum = 0;
737                         bb->dfparent = 0;
738                         bb->semi = 0;
739                         bb->ancestor = 0;
740                         bb->idom = 0;
741                         bb->samedom = 0;
742                         bb->bucket = NULL;
743                         bb->df = NULL;
744                         bb->dfchildren = NULL;
745                         bb->Aorig = NULL;
746                         bb->Aphi = NULL;
pantzer
1.59
747                         SLIST_INIT(&bb->phi);
ragge
1.34
748                         bb->bbnum = count;
ragge
1.56
749                         DLIST_INSERT_BEFORE(&p2e->bblocksbbbbelem);
ragge
1.31
750                         count++;
751                 }
752                 bb->last = ip;
753                 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO || 
754                     ip->ip_node->n_op == CBRANCH))
755                         bb = NULL;
756                 if (ip->type == IP_PROLOG)
757                         bb = NULL;
758         }
ragge
1.56
759         p2e->nbblocks = count;
ragge
1.30
760
ragge
1.31
761         if (b2debug) {
ragge
1.32
762                 printf("Basic blocks in func: %d, low %d, high %d\n",
763                     countlowhigh);
ragge
1.56
764                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.73
765                         printf("bb(%d) %p: first %p last %p\n"bb->bbnumbb,
ragge
1.31
766                             bb->firstbb->last);
767                 }
768         }
pj
1.4
769
ragge
1.74
770         p2e->labinfo.low = low;
771         p2e->labinfo.size = high - low + 1;
772         p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
773         for (i = 0i < p2e->labinfo.sizei++) {
774                 p2e->labinfo.arr[i] = NULL;
pj
1.4
775         }
pj
1.8
776         
ragge
1.74
777         p2e->bbinfo.size = count + 1;
778         p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
779         for (i = 0i < p2e->bbinfo.sizei++) {
780                 p2e->bbinfo.arr[i] = NULL;
pj
1.8
781         }
pj
1.4
782
ragge
1.32
783         /* Build the label table */
ragge
1.56
784         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.32
785                 if (bb->first->type == IP_DEFLAB)
ragge
1.74
786                         p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
ragge
1.32
787         }
788
789         if (b2debug) {
ragge
1.76
790                 DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
791                         printf("bblock %d\n"bb->bbnum);
792                         for (ip = bb->firstip != bb->last;
793                             ip = DLIST_NEXT(ipqelem)) {
794                                 printip2(ip);
795                         }
796                         printip2(ip);
797                 }
798
ragge
1.32
799                 printf("Label table:\n");
ragge
1.74
800                 for (i = 0i < p2e->labinfo.sizei++)
801                         if (p2e->labinfo.arr[i])
ragge
1.32
802                                 printf("Label %d bblock %p\n"i+low,
ragge
1.74
803                                     p2e->labinfo.arr[i]);
pj
1.4
804         }
805 }
806
807 /*
808  * Build the control flow graph.
809  */
810
811 void
ragge
1.74
812 cfg_build(struct p2env *p2e)
pj
1.4
813 {
814         /* Child and parent nodes */
815         struct cfgnode *cnode
816         struct cfgnode *pnode;
817         struct basicblock *bb;
ragge
1.84
818         NODE *p;
819
820 #ifdef notyet
ragge
1.56
821         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.84
822                 if (bb->first->type == IP_EPILOG)
823                         break;
824
825                 if (bb->last->type == IP_NODE) {
826                         p = bb->last->ip_node;
827                         switch (p->n_op) {
828                         case GOTO:
829                                 if (p->n_left->n_op == ICON) {
830                                         lbchk(p2ep->n_left->n_lval);
831                                         fillcnode(p2ep->n_left->n_lvalbb);
832                                 } else {
833                                 }
834                                 break;
835
836                         case CBRANCH:
837                                 lbchk(p2ep->n_right->n_lval);
838                                 fillcnode(p2ep->n_right->n_lvalbb);
839                                 ...
pj
1.4
840
ragge
1.84
841                         default:
842                                 ...
843                         }
844                 } else {
845                         ...
pj
1.4
846                 }
ragge
1.84
847         }
848 #endif
pj
1.4
849
ragge
1.84
850         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
851                 if (bb->first->type == IP_EPILOG)
852                         break;
853         
pj
1.4
854                 cnode = tmpalloc(sizeof(struct cfgnode));
855                 pnode = tmpalloc(sizeof(struct cfgnode));
856                 pnode->bblock = bb;
857
ragge
1.84
858                 p = bb->last->ip_node;
859                 if (bb->last->type == IP_NODE && p->n_op == GOTO) {
860                         if (p->n_left->n_op == ICON) {
861                                 if (p->n_left->n_lval - p2e->labinfo.low > p2e->labinfo.size)
862                                         comperr("Label out of range: %d, base %d"
863                                             p->n_left->n_lvalp2e->labinfo.low);
864                                 cnode->bblock = p2e->labinfo.arr[p->n_left->n_lval - p2e->labinfo.low];
865                                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
866                                 SLIST_INSERT_LAST(&bb->childcnodechld);
867                         } else {
868                                 int *l;
869                                 /* XXX assume all labels are valid as dest */
870                                 for (l = p2e->epp->ip_labels; *ll++) {
871                                         cnode->bblock = p2e->labinfo.arr[*l - p2e->labinfo.low];
872                                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
873                                         SLIST_INSERT_LAST(&bb->childcnodechld);
874                                         cnode = tmpalloc(sizeof(struct cfgnode));
875                                         pnode = tmpalloc(sizeof(struct cfgnode));
876                                         pnode->bblock = bb;
877                                 }
pj
1.4
878                         }
879                         continue;
880                 }
ragge
1.84
881                 if ((bb->last->type == IP_NODE) && p->n_op == CBRANCH) {
882                         if (p->n_right->n_lval - p2e->labinfo.low > p2e->labinfo.size
883                                 comperr("Label out of range: %d"p->n_left->n_lval);
ragge
1.66
884
ragge
1.84
885                         cnode->bblock = p2e->labinfo.arr[p->n_right->n_lval - p2e->labinfo.low];
ragge
1.11
886                         SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
ragge
1.83
887                         SLIST_INSERT_LAST(&bb->childcnodechld);
pj
1.4
888                         cnode = tmpalloc(sizeof(struct cfgnode));
889                         pnode = tmpalloc(sizeof(struct cfgnode));
890                         pnode->bblock = bb;
891                 }
892
ragge
1.11
893                 cnode->bblock = DLIST_NEXT(bbbbelem);
894                 SLIST_INSERT_LAST(&cnode->bblock->parentspnodecfgelem);
ragge
1.83
895                 SLIST_INSERT_LAST(&bb->childcnodechld);
pj
1.4
896         }
897 }
pj
1.6
898
pj
1.8
899 void
900 cfg_dfs(struct basicblock *bbunsigned int parentstruct bblockinfo *bbinfo)
901 {
ragge
1.83
902         struct cfgnode *cn;
ragge
1.79
903
pj
1.8
904         if (bb->dfnum != 0)
905                 return;
906
907         bb->dfnum = ++dfsnum;
908         bb->dfparent = parent;
909         bbinfo->arr[bb->dfnum] = bb;
ragge
1.83
910         SLIST_FOREACH(cn, &bb->childchld)
911                 cfg_dfs(cn->bblockbb->dfnumbbinfo);
pj
1.13
912         /* Don't bring in unreachable nodes in the future */
pj
1.20
913         bbinfo->size = dfsnum + 1;
pj
1.8
914 }
915
ragge
1.11
916 static bittype *
917 setalloc(int nelem)
918 {
919         bittype *b;
920         int sz = (nelem+NUMBITS-1)/NUMBITS;
921
922         b = tmpalloc(sz * sizeof(bittype));
923         memset(b0sz * sizeof(bittype));
924         return b;
925 }
926
pj
1.8
927 /*
928  * Algorithm 19.9, pp 414 from Appel.
929  */
930
931 void
ragge
1.74
932 dominators(struct p2env *p2e)
pj
1.8
933 {
934         struct cfgnode *cnode;
935         struct basicblock *bb, *y, *v;
936         struct basicblock *s, *sprime, *p;
pj
1.10
937         int hi;
pj
1.8
938
ragge
1.56
939         DLIST_FOREACH(bb, &p2e->bblocksbbelem) {
ragge
1.74
940                 bb->bucket = setalloc(p2e->bbinfo.size);
941                 bb->df = setalloc(p2e->bbinfo.size);
942                 bb->dfchildren = setalloc(p2e->bbinfo.size);
pj
1.8
943         }
944
945         dfsnum = 0;
ragge
1.74
946         cfg_dfs(DLIST_NEXT(&p2e->bblocksbbelem), 0, &p2e->bbinfo);
pj
1.8
947
ragge
1.30
948         if (b2debug) {
949                 struct basicblock *bbb;
ragge
1.83
950                 struct cfgnode *ccnode, *cn;
ragge
1.30
951
ragge
1.56
952                 DLIST_FOREACH(bbb, &p2e->bblocksbbelem) {
ragge
1.30
953                         printf("Basic block %d, parents: "bbb->dfnum);
954                         SLIST_FOREACH(ccnode, &bbb->parentscfgelem) {
955                                 printf("%d, "ccnode->bblock->dfnum);
956                         }
957                         printf("\nChildren: ");
ragge
1.83
958                         SLIST_FOREACH(cn, &bbb->childchld)
959                                 printf("%d, "cn->bblock->dfnum);
ragge
1.30
960                         printf("\n");
pj
1.20
961                 }
962         }
963
ragge
1.74
964         for(h = p2e->bbinfo.size - 1h > 1h--) {
965                 bb = p2e->bbinfo.arr[h];
966                 p = s = p2e->bbinfo.arr[bb->dfparent];
ragge
1.11
967                 SLIST_FOREACH(cnode, &bb->parentscfgelem) {
pantzer
1.60
968                         if (cnode->bblock->dfnum ==0)
969                                 continue/* Ignore unreachable code */
970
pj
1.8
971                         if (cnode->bblock->dfnum <= bb->dfnum
972                                 sprime = cnode->bblock;
pj
1.10
973                         else 
ragge
1.74
974                                 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
975                                               (cnode->bblock, &p2e->bbinfo)->semi];
pj
1.8
976                         if (sprime->dfnum < s->dfnum)
977                                 s = sprime;
978                 }
979                 bb->semi = s->dfnum;
pj
1.10
980                 BITSET(s->bucketbb->dfnum);
pj
1.8
981<