Quick Search:

View

Revision:
Expand:  
Changeset: MAIN:ragge:20160926164542

Diff

Diff from 1.94 to:

Annotations

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

Annotated File View

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