?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
* add p cc
[mascara-docs.git] / compilers / pcc / pcc-1.0.0 / mip / optim2.c
blobcd8f903f6cf0f515a318c7befe332a7dcee42550
1 /* $Id: optim2.c,v 1.79 2010/06/04 07:18:46 ragge Exp $ */
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
31 #include <string.h>
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
41
42 #define BDEBUG(x) if (b2debug) printf x
43
44 #define mktemp(n, t) mklnode(TEMP, 0, n, t)
45
46 #define CHADD(bb,c) { if (bb->ch[0] == 0) bb->ch[0] = c; \
47 else if (bb->ch[1] == 0) bb->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
52 /* main switch for new things not yet ready for all-day use */
53 /* #define ENABLE_NEW */
54
55
56 static int dfsnum;
57
58 void saveip(struct interpass *ip);
59 void deljumps(struct p2env *);
60 void optdump(struct interpass *ip);
61 void printip(struct interpass *pole);
62
63 static struct varinfo defsites;
64 struct interpass *storesave;
65
66 void bblocks_build(struct p2env *);
67 void cfg_build(struct p2env *);
68 void cfg_dfs(struct basicblock *bb, unsigned int parent,
69 struct bblockinfo *bbinfo);
70 void dominators(struct p2env *);
71 struct basicblock *
72 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo);
73 void link(struct basicblock *parent, struct basicblock *child);
74 void computeDF(struct p2env *, struct basicblock *bblock);
75 void printDF(struct p2env *p2e);
76 void findTemps(struct interpass *ip);
77 void placePhiFunctions(struct p2env *);
78 void renamevar(struct p2env *p2e,struct basicblock *bblock);
79 void removephi(struct p2env *p2e);
80 void remunreach(struct p2env *);
81 static void liveanal(struct p2env *p2e);
82 static void printip2(struct interpass *);
83
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 p2env* p2e) ;
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 */
97 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type) ;
98
99 void BBLiveDead(struct basicblock* bblock, int what, unsigned int variable) ;
100
101 /* Fill the live/dead code */
102 void LiveDead(struct p2env* p2e, int what, unsigned int variable) ;
103
104 #ifdef PCC_DEBUG
105 void printflowdiagram(struct p2env *, char *);
106 #endif
107
108 void
109 optimize(struct p2env *p2e)
110 {
111 struct interpass *ipole = &p2e->ipole;
112
113 if (b2debug) {
114 printf("initial links\n");
115 printip(ipole);
116 }
117
118 if (xdeljumps)
119 deljumps(p2e); /* Delete redundant jumps and dead code */
120
121 if (xssaflag)
122 add_labels(p2e) ;
123 #ifdef ENABLE_NEW
124 do_cse(p2e);
125 #endif
126
127 #ifdef PCC_DEBUG
128 if (b2debug) {
129 printf("links after deljumps\n");
130 printip(ipole);
131 }
132 #endif
133 if (xssaflag || xtemps) {
134 bblocks_build(p2e);
135 BDEBUG(("Calling cfg_build\n"));
136 cfg_build(p2e);
137
138 #ifdef PCC_DEBUG
139 printflowdiagram(p2e, "first");
140 #endif
141 }
142 if (xssaflag) {
143 BDEBUG(("Calling liveanal\n"));
144 liveanal(p2e);
145 BDEBUG(("Calling dominators\n"));
146 dominators(p2e);
147 BDEBUG(("Calling computeDF\n"));
148 computeDF(p2e, DLIST_NEXT(&p2e->bblocks, bbelem));
149
150 if (b2debug) {
151 printDF(p2e);
152 }
153
154 BDEBUG(("Calling placePhiFunctions\n"));
155
156 placePhiFunctions(p2e);
157
158 BDEBUG(("Calling renamevar\n"));
159
160 renamevar(p2e,DLIST_NEXT(&p2e->bblocks, bbelem));
161
162 BDEBUG(("Calling removephi\n"));
163
164 #ifdef PCC_DEBUG
165 printflowdiagram(p2e, "ssa");
166 #endif
167
168 removephi(p2e);
169
170 BDEBUG(("Calling remunreach\n"));
171 /* remunreach(p2e); */
172
173 /*
174 * Recalculate basic blocks and cfg that was destroyed
175 * by removephi
176 */
177 /* first, clean up all what deljumps should have done, and more */
178
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.
183 */
184
185 #ifdef ENABLE_NEW
186 bblocks_build(p2e, &labinfo, &bbinfo);
187 BDEBUG(("Calling cfg_build\n"));
188 cfg_build(p2e, &labinfo);
189
190 TraceSchedule(p2e);
191 #ifdef PCC_DEBUG
192 printflowdiagram(p2e, &labinfo, &bbinfo,"sched_trace");
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 */
205
206 bblocks_build(p2e);
207 BDEBUG(("Calling cfg_build\n"));
208 cfg_build(p2e);
209
210 #ifdef PCC_DEBUG
211 printflowdiagram(p2e, "no_phi");
212
213 if (b2debug) {
214 printf("new tree\n");
215 printip(ipole);
216 }
217 #endif
218 }
219
220 #ifdef PCC_DEBUG
221 {
222 int i;
223 for (i = NIPPREGS; i--; )
224 if (p2e->epp->ipp_regs[i] != 0)
225 comperr("register error");
226 }
227 #endif
228
229 myoptim(ipole);
230 }
231
232 /*
233 * Delete unused labels, excess of labels, gotos to gotos.
234 * This routine can be made much more efficient.
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.
246 */
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)
265 {
266 printf("dumplink %p\n", dl);
267 for (; dl; dl = dl->forw) {
268 if (dl->op == STMT) {
269 printf("STMT(%p)\n", dl);
270 fwalk(dl->dlip->ip_node, e2print, 0);
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 dl, dl->labno, dl->refc, dl->ref);
277 }
278 }
279 printf("end dumplink\n");
280 }
281 #endif
282
283 /*
284 * Create the linked list that we can work on.
285 */
286 static void
287 listsetup(struct interpass *ipole, struct dlnod *dl)
288 {
289 struct interpass *ip = DLIST_NEXT(ipole, qelem);
290 struct interpass *nip;
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;
313
314 case IP_NODE:
315 q = ip->ip_node;
316 switch (q->n_op) {
317 case GOTO:
318 p->op = JBR;
319 p->labno = q->n_left->n_lval;
320 break;
321 case CBRANCH:
322 p->op = CBR;
323 p->labno = q->n_right->n_lval;
324 break;
325 case ASSIGN:
326 /* remove ASSIGN to self for regs */
327 if (q->n_left->n_op == REG &&
328 q->n_right->n_op == REG &&
329 regno(q->n_left) == regno(q->n_right)) {
330 nip = DLIST_PREV(ip, qelem);
331 tfree(q);
332 DLIST_REMOVE(ip, qelem);
333 ip = nip;
334 continue;
335 }
336 /* FALLTHROUGH */
337 default:
338 p->op = STMT;
339 break;
340 }
341 break;
342
343 case IP_ASM:
344 p->op = STMT;
345 break;
346
347 case IP_EPILOG:
348 p->op = EROU;
349 break;
350
351 default:
352 comperr("listsetup: bad ip node %d", ip->type);
353 }
354 p->forw = 0;
355 p->back = lastp;
356 lastp->forw = p;
357 lastp = p;
358 p->ref = 0;
359 }
360 }
361
362 static struct dlnod *
363 nonlab(struct dlnod *p)
364 {
365 while (p && p->op==LABEL)
366 p = p->forw;
367 return(p);
368 }
369
370 static void
371 iprem(struct dlnod *p)
372 {
373 if (p->dlip->type == IP_NODE)
374 tfree(p->dlip->ip_node);
375 DLIST_REMOVE(p->dlip, qelem);
376 }
377
378 static void
379 decref(struct dlnod *p)
380 {
381 if (--p->refc <= 0) {
382 iprem(p);
383 p->back->forw = p->forw;
384 p->forw->back = p->back;
385 }
386 }
387
388 static void
389 setlab(struct dlnod *p, int labno)
390 {
391 p->labno = labno;
392 if (p->op == JBR)
393 p->dlip->ip_node->n_left->n_lval = labno;
394 else if (p->op == CBR) {
395 p->dlip->ip_node->n_right->n_lval = labno;
396 p->dlip->ip_node->n_left->n_label = labno;
397 } else
398 comperr("setlab bad op %d", p->op);
399 }
400
401 /*
402 * Label reference counting and removal of unused labels.
403 */
404 #define LABHS 127
405 static void
406 refcount(struct p2env *p2e, struct dlnod *dl)
407 {
408 struct dlnod *p, *lp;
409 struct dlnod *labhash[LABHS];
410 struct dlnod **hp, *tp;
411
412 /* Clear label hash */
413 for (hp = labhash; hp < &labhash[LABHS];)
414 *hp++ = 0;
415 /* Enter labels into hash. Later overwrites earlier */
416 for (p = dl->forw; p!=0; p = p->forw)
417 if (p->op==LABEL) {
418 labhash[p->labno % LABHS] = p;
419 p->refc = 0;
420 }
421
422 /* search for jumps to labels and fill in reference */
423 for (p = dl->forw; p!=0; p = p->forw) {
424 if (p->op==JBR || p->op==CBR) {
425 p->ref = 0;
426 lp = labhash[p->labno % LABHS];
427 if (lp==0 || p->labno!=lp->labno)
428 for (lp = dl->forw; lp!=0; lp = lp->forw) {
429 if (lp->op==LABEL && p->labno==lp->labno)
430 break;
431 }
432 if (lp) {
433 tp = nonlab(lp)->back;
434 if (tp!=lp) {
435 setlab(p, tp->labno);
436 lp = tp;
437 }
438 p->ref = lp;
439 lp->refc++;
440 }
441 }
442 }
443 for (p = dl->forw; p!=0; p = p->forw)
444 if (p->op==LABEL && p->refc==0 && (lp = nonlab(p))->op)
445 decref(p);
446 }
447
448 static int nchange;
449
450 static struct dlnod *
451 codemove(struct dlnod *p)
452 {
453 struct dlnod *p1, *p2, *p3;
454 #ifdef notyet
455 struct dlnod *t, *tl;
456 int n;
457 #endif
458
459 p1 = p;
460 if (p1->op!=JBR || (p2 = p1->ref)==0)
461 return(p1);
462 while (p2->op == LABEL)
463 if ((p2 = p2->back) == 0)
464 return(p1);
465 if (p2->op!=JBR)
466 goto ivloop;
467 if (p1==p2)
468 return(p1);
469 p2 = p2->forw;
470 p3 = p1->ref;
471 while (p3) {
472 if (p3->op==JBR) {
473 if (p1==p3 || p1->forw==p3 || p1->back==p3)
474 return(p1);
475 nchange++;
476 p1->back->forw = p2;
477 p1->dlip->qelem.q_back->qelem.q_forw = p2->dlip;
478
479 p1->forw->back = p3;
480 p1->dlip->qelem.q_forw->qelem.q_back = p3->dlip;
481
482
483 p2->back->forw = p3->forw;
484 p2->dlip->qelem.q_back->qelem.q_forw = p3->forw->dlip;
485
486 p3->forw->back = p2->back;
487 p3->dlip->qelem.q_forw->qelem.q_back = p2->back->dlip;
488
489 p2->back = p1->back;
490 p2->dlip->qelem.q_back = p1->dlip->qelem.q_back;
491
492 p3->forw = p1->forw;
493 p3->dlip->qelem.q_forw = p1->forw->dlip;
494
495 decref(p1->ref);
496 if (p1->dlip->type == IP_NODE)
497 tfree(p1->dlip->ip_node);
498
499 return(p2);
500 } else
501 p3 = p3->forw;
502 }
503 return(p1);
504
505 ivloop:
506 if (p1->forw->op!=LABEL)
507 return(p1);
508 return(p1);
509
510 #ifdef notyet
511 p3 = p2 = p2->forw;
512 n = 16;
513 do {
514 if ((p3 = p3->forw) == 0 || p3==p1 || --n==0)
515 return(p1);
516 } while (p3->op!=CBR || p3->labno!=p1->forw->labno);
517 do
518 if ((p1 = p1->back) == 0)
519 return(p);
520 while (p1!=p3);
521 p1 = p;
522 tl = insertl(p1);
523 p3->subop = revbr[p3->subop];
524 decref(p3->ref);
525 p2->back->forw = p1;
526 p3->forw->back = p1;
527 p1->back->forw = p2;
528 p1->forw->back = p3;
529 t = p1->back;
530 p1->back = p2->back;
531 p2->back = t;
532 t = p1->forw;
533 p1->forw = p3->forw;
534 p3->forw = t;
535 p2 = insertl(p1->forw);
536 p3->labno = p2->labno;
537 p3->ref = p2;
538 decref(tl);
539 if (tl->refc<=0)
540 nrlab--;
541 nchange++;
542 return(p3);
543 #endif
544 }
545
546 static void
547 iterate(struct p2env *p2e, struct dlnod *dl)
548 {
549 struct dlnod *p, *rp, *p1;
550 extern int negrel[];
551 extern size_t negrelsize;
552 int i;
553
554 nchange = 0;
555 for (p = dl->forw; p!=0; p = p->forw) {
556 if ((p->op==JBR||p->op==CBR) && p->ref) {
557 /* Resolves:
558 * jbr L7
559 * ...
560 * L7: jbr L8
561 */
562 rp = nonlab(p->ref);
563 if (rp->op==JBR && rp->labno && p->labno!=rp->labno) {
564 setlab(p, rp->labno);
565 decref(p->ref);
566 rp->ref->refc++;
567 p->ref = rp->ref;
568 nchange++;
569 }
570 }
571 if (p->op==CBR && (p1 = p->forw)->op==JBR) {
572 /* Resolves:
573 * cbr L7
574 * jbr L8
575 * L7:
576 */
577 rp = p->ref;
578 do
579 rp = rp->back;
580 while (rp->op==LABEL);
581 if (rp==p1) {
582 decref(p->ref);
583 p->ref = p1->ref;
584 setlab(p, p1->labno);
585
586 iprem(p1);
587
588 p1->forw->back = p;
589 p->forw = p1->forw;
590
591 i = p->dlip->ip_node->n_left->n_op;
592 if (i < EQ || i - EQ >= (int)negrelsize)
593 comperr("deljumps: unexpected op");
594 p->dlip->ip_node->n_left->n_op = negrel[i - EQ];
595 nchange++;
596 }
597 }
598 if (p->op == JBR) {
599 /* Removes dead code */
600 while (p->forw && p->forw->op!=LABEL &&
601 p->forw->op!=EROU) {
602 nchange++;
603 if (p->forw->ref)
604 decref(p->forw->ref);
605
606 iprem(p->forw);
607
608 p->forw = p->forw->forw;
609 p->forw->back = p;
610 }
611 rp = p->forw;
612 while (rp && rp->op==LABEL) {
613 if (p->ref == rp) {
614 p->back->forw = p->forw;
615 p->forw->back = p->back;
616 iprem(p);
617 p = p->back;
618 decref(rp);
619 nchange++;
620 break;
621 }
622 rp = rp->forw;
623 }
624 }
625 if (p->op == JBR) {
626 /* xjump(p); * needs tree rewrite; not yet */
627 p = codemove(p);
628 }
629 }
630 }
631
632 void
633 deljumps(struct p2env *p2e)
634 {
635 struct interpass *ipole = &p2e->ipole;
636 struct dlnod dln;
637 MARK mark;
638
639 markset(&mark);
640
641 memset(&dln, 0, sizeof(dln));
642 listsetup(ipole, &dln);
643 do {
644 refcount(p2e, &dln);
645 do {
646 iterate(p2e, &dln);
647 } while (nchange);
648 #ifdef notyet
649 comjump();
650 #endif
651 } while (nchange);
652
653 markfree(&mark);
654 }
655
656 void
657 optdump(struct interpass *ip)
658 {
659 static char *nm[] = { "node", "prolog", "newblk", "epilog", "locctr",
660 "deflab", "defnam", "asm" };
661 printf("type %s\n", nm[ip->type-1]);
662 switch (ip->type) {
663 case IP_NODE:
664 #ifdef PCC_DEBUG
665 fwalk(ip->ip_node, e2print, 0);
666 #endif
667 break;
668 case IP_DEFLAB:
669 printf("label " LABFMT "\n", ip->ip_lbl);
670 break;
671 case IP_ASM:
672 printf(": %s\n", ip->ip_asm);
673 break;
674 }
675 }
676
677 /*
678 * Build the basic blocks, algorithm 9.1, pp 529 in Compilers.
679 *
680 * Also fills the labelinfo struct with information about which bblocks
681 * that contain which label.
682 */
683
684 void
685 bblocks_build(struct p2env *p2e)
686 {
687 struct interpass *ipole = &p2e->ipole;
688 struct interpass *ip;
689 struct basicblock *bb = NULL;
690 int low, high;
691 int count = 0;
692 int i;
693
694 BDEBUG(("bblocks_build (%p, %p)\n", &p2e->labinfo, &p2e->bbinfo));
695 low = p2e->ipp->ip_lblnum;
696 high = p2e->epp->ip_lblnum;
697
698 /*
699 * First statement is a leader.
700 * Any statement that is target of a jump is a leader.
701 * Any statement that immediately follows a jump is a leader.
702 */
703 DLIST_INIT(&p2e->bblocks, bbelem);
704 DLIST_FOREACH(ip, ipole, qelem) {
705 if (bb == NULL || (ip->type == IP_EPILOG) ||
706 (ip->type == IP_DEFLAB) || (ip->type == IP_DEFNAM)) {
707 bb = tmpalloc(sizeof(struct basicblock));
708 bb->first = ip;
709 SLIST_INIT(&bb->parents);
710 bb->ch[0] = bb->ch[1] = NULL;
711 bb->dfnum = 0;
712 bb->dfparent = 0;
713 bb->semi = 0;
714 bb->ancestor = 0;
715 bb->idom = 0;
716 bb->samedom = 0;
717 bb->bucket = NULL;
718 bb->df = NULL;
719 bb->dfchildren = NULL;
720 bb->Aorig = NULL;
721 bb->Aphi = NULL;
722 SLIST_INIT(&bb->phi);
723 bb->bbnum = count;
724 DLIST_INSERT_BEFORE(&p2e->bblocks, bb, bbelem);
725 count++;
726 }
727 bb->last = ip;
728 if ((ip->type == IP_NODE) && (ip->ip_node->n_op == GOTO ||
729 ip->ip_node->n_op == CBRANCH))
730 bb = NULL;
731 if (ip->type == IP_PROLOG)
732 bb = NULL;
733 }
734 p2e->nbblocks = count;
735
736 if (b2debug) {
737 printf("Basic blocks in func: %d, low %d, high %d\n",
738 count, low, high);
739 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
740 printf("bb(%d) %p: first %p last %p\n", bb->bbnum, bb,
741 bb->first, bb->last);
742 }
743 }
744
745 p2e->labinfo.low = low;
746 p2e->labinfo.size = high - low + 1;
747 p2e->labinfo.arr = tmpalloc(p2e->labinfo.size * sizeof(struct basicblock *));
748 for (i = 0; i < p2e->labinfo.size; i++) {
749 p2e->labinfo.arr[i] = NULL;
750 }
751
752 p2e->bbinfo.size = count + 1;
753 p2e->bbinfo.arr = tmpalloc(p2e->bbinfo.size * sizeof(struct basicblock *));
754 for (i = 0; i < p2e->bbinfo.size; i++) {
755 p2e->bbinfo.arr[i] = NULL;
756 }
757
758 /* Build the label table */
759 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
760 if (bb->first->type == IP_DEFLAB)
761 p2e->labinfo.arr[bb->first->ip_lbl - low] = bb;
762 }
763
764 if (b2debug) {
765 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
766 printf("bblock %d\n", bb->bbnum);
767 for (ip = bb->first; ip != bb->last;
768 ip = DLIST_NEXT(ip, qelem)) {
769 printip2(ip);
770 }
771 printip2(ip);
772 }
773
774 printf("Label table:\n");
775 for (i = 0; i < p2e->labinfo.size; i++)
776 if (p2e->labinfo.arr[i])
777 printf("Label %d bblock %p\n", i+low,
778 p2e->labinfo.arr[i]);
779 }
780 }
781
782 /*
783 * Build the control flow graph.
784 */
785
786 void
787 cfg_build(struct p2env *p2e)
788 {
789 /* Child and parent nodes */
790 struct cfgnode *cnode;
791 struct cfgnode *pnode;
792 struct basicblock *bb;
793
794 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
795
796 if (bb->first->type == IP_EPILOG) {
797 break;
798 }
799
800 cnode = tmpalloc(sizeof(struct cfgnode));
801 pnode = tmpalloc(sizeof(struct cfgnode));
802 pnode->bblock = bb;
803
804 if ((bb->last->type == IP_NODE) &&
805 (bb->last->ip_node->n_op == GOTO) &&
806 (bb->last->ip_node->n_left->n_op == ICON)) {
807 if (bb->last->ip_node->n_left->n_lval - p2e->labinfo.low >
808 p2e->labinfo.size) {
809 comperr("Label out of range: %d, base %d",
810 bb->last->ip_node->n_left->n_lval,
811 p2e->labinfo.low);
812 }
813 cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_left->n_lval - p2e->labinfo.low];
814 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
815 CHADD(bb, cnode);
816 continue;
817 }
818 if ((bb->last->type == IP_NODE) &&
819 (bb->last->ip_node->n_op == CBRANCH)) {
820 if (bb->last->ip_node->n_right->n_lval - p2e->labinfo.low >
821 p2e->labinfo.size)
822 comperr("Label out of range: %d",
823 bb->last->ip_node->n_left->n_lval);
824
825 cnode->bblock = p2e->labinfo.arr[bb->last->ip_node->n_right->n_lval - p2e->labinfo.low];
826 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
827 CHADD(bb, cnode);
828 cnode = tmpalloc(sizeof(struct cfgnode));
829 pnode = tmpalloc(sizeof(struct cfgnode));
830 pnode->bblock = bb;
831 }
832
833 cnode->bblock = DLIST_NEXT(bb, bbelem);
834 SLIST_INSERT_LAST(&cnode->bblock->parents, pnode, cfgelem);
835 CHADD(bb, cnode);
836 }
837 }
838
839 void
840 cfg_dfs(struct basicblock *bb, unsigned int parent, struct bblockinfo *bbinfo)
841 {
842 struct cfgnode **cn;
843
844 if (bb->dfnum != 0)
845 return;
846
847 bb->dfnum = ++dfsnum;
848 bb->dfparent = parent;
849 bbinfo->arr[bb->dfnum] = bb;
850 FORCH(cn, bb->ch)
851 cfg_dfs((*cn)->bblock, bb->dfnum, bbinfo);
852 /* Don't bring in unreachable nodes in the future */
853 bbinfo->size = dfsnum + 1;
854 }
855
856 static bittype *
857 setalloc(int nelem)
858 {
859 bittype *b;
860 int sz = (nelem+NUMBITS-1)/NUMBITS;
861
862 b = tmpalloc(sz * sizeof(bittype));
863 memset(b, 0, sz * sizeof(bittype));
864 return b;
865 }
866
867 /*
868 * Algorithm 19.9, pp 414 from Appel.
869 */
870
871 void
872 dominators(struct p2env *p2e)
873 {
874 struct cfgnode *cnode;
875 struct basicblock *bb, *y, *v;
876 struct basicblock *s, *sprime, *p;
877 int h, i;
878
879 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
880 bb->bucket = setalloc(p2e->bbinfo.size);
881 bb->df = setalloc(p2e->bbinfo.size);
882 bb->dfchildren = setalloc(p2e->bbinfo.size);
883 }
884
885 dfsnum = 0;
886 cfg_dfs(DLIST_NEXT(&p2e->bblocks, bbelem), 0, &p2e->bbinfo);
887
888 if (b2debug) {
889 struct basicblock *bbb;
890 struct cfgnode *ccnode, **cn;
891
892 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
893 printf("Basic block %d, parents: ", bbb->dfnum);
894 SLIST_FOREACH(ccnode, &bbb->parents, cfgelem) {
895 printf("%d, ", ccnode->bblock->dfnum);
896 }
897 printf("\nChildren: ");
898 FORCH(cn, bbb->ch)
899 printf("%d, ", (*cn)->bblock->dfnum);
900 printf("\n");
901 }
902 }
903
904 for(h = p2e->bbinfo.size - 1; h > 1; h--) {
905 bb = p2e->bbinfo.arr[h];
906 p = s = p2e->bbinfo.arr[bb->dfparent];
907 SLIST_FOREACH(cnode, &bb->parents, cfgelem) {
908 if (cnode->bblock->dfnum ==0)
909 continue; /* Ignore unreachable code */
910
911 if (cnode->bblock->dfnum <= bb->dfnum)
912 sprime = cnode->bblock;
913 else
914 sprime = p2e->bbinfo.arr[ancestorwithlowestsemi
915 (cnode->bblock, &p2e->bbinfo)->semi];
916 if (sprime->dfnum < s->dfnum)
917 s = sprime;
918 }
919 bb->semi = s->dfnum;
920 BITSET(s->bucket, bb->dfnum);
921 link(p, bb);
922 for (i = 1; i < p2e->bbinfo.size; i++) {
923 if(TESTBIT(p->bucket, i)) {
924 v = p2e->bbinfo.arr[i];
925 y = ancestorwithlowestsemi(v, &p2e->bbinfo);
926 if (y->semi == v->semi)
927 v->idom = p->dfnum;
928 else
929 v->samedom = y->dfnum;
930 }
931 }
932 memset(p->bucket, 0, (p2e->bbinfo.size + 7)/8);
933 }
934
935 if (b2debug) {
936 printf("Num\tSemi\tAncest\tidom\n");
937 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
938 printf("%d\t%d\t%d\t%d\n", bb->dfnum, bb->semi,
939 bb->ancestor, bb->idom);
940 }
941 }
942
943 for(h = 2; h < p2e->bbinfo.size; h++) {
944 bb = p2e->bbinfo.arr[h];
945 if (bb->samedom != 0) {
946 bb->idom = p2e->bbinfo.arr[bb->samedom]->idom;
947 }
948 }
949 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
950 if (bb->idom != 0 && bb->idom != bb->dfnum) {
951 BDEBUG(("Setting child %d of %d\n",
952 bb->dfnum, p2e->bbinfo.arr[bb->idom]->dfnum));
953 BITSET(p2e->bbinfo.arr[bb->idom]->dfchildren, bb->dfnum);
954 }
955 }
956 }
957
958
959 struct basicblock *
960 ancestorwithlowestsemi(struct basicblock *bblock, struct bblockinfo *bbinfo)
961 {
962 struct basicblock *u = bblock;
963 struct basicblock *v = bblock;
964
965 while (v->ancestor != 0) {
966 if (bbinfo->arr[v->semi]->dfnum <
967 bbinfo->arr[u->semi]->dfnum)
968 u = v;
969 v = bbinfo->arr[v->ancestor];
970 }
971 return u;
972 }
973
974 void
975 link(struct basicblock *parent, struct basicblock *child)
976 {
977 child->ancestor = parent->dfnum;
978 }
979
980 void
981 computeDF(struct p2env *p2e, struct basicblock *bblock)
982 {
983 struct cfgnode **cn;
984 int h, i;
985
986 FORCH(cn, bblock->ch) {
987 if ((*cn)->bblock->idom != bblock->dfnum)
988 BITSET(bblock->df, (*cn)->bblock->dfnum);
989 }
990 for (h = 1; h < p2e->bbinfo.size; h++) {
991 if (!TESTBIT(bblock->dfchildren, h))
992 continue;
993 computeDF(p2e, p2e->bbinfo.arr[h]);
994 for (i = 1; i < p2e->bbinfo.size; i++) {
995 if (TESTBIT(p2e->bbinfo.arr[h]->df, i) &&
996 (p2e->bbinfo.arr[i] == bblock ||
997 (bblock->dfnum != p2e->bbinfo.arr[i]->idom)))
998 BITSET(bblock->df, i);
999 }
1000 }
1001 }
1002
1003 void printDF(struct p2env *p2e)
1004 {
1005 struct basicblock *bb;
1006 int i;
1007
1008 printf("Dominance frontiers:\n");
1009
1010 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
1011 printf("bb %d : ", bb->dfnum);
1012
1013 for (i=1; i < p2e->bbinfo.size;i++) {
1014 if (TESTBIT(bb->df,i)) {
1015 printf("%d ",i);
1016 }
1017 }
1018
1019 printf("\n");
1020 }
1021
1022 }
1023
1024
1025
1026 static struct basicblock *currbb;
1027 static struct interpass *currip;
1028
1029 /* Helper function for findTemps, Find assignment nodes. */
1030 static void
1031 searchasg(NODE *p, void *arg)
1032 {
1033 struct pvarinfo *pv;
1034 int tempnr;
1035 struct varstack *stacke;
1036
1037 if (p->n_op != ASSIGN)
1038 return;
1039
1040 if (p->n_left->n_op != TEMP)
1041 return;
1042
1043 tempnr=regno(p->n_left)-defsites.low;
1044
1045 BITSET(currbb->Aorig, tempnr);
1046
1047 pv = tmpcalloc(sizeof(struct pvarinfo));
1048 pv->next = defsites.arr[tempnr];
1049 pv->bb = currbb;
1050 pv->n_type = p->n_left->n_type;
1051
1052 defsites.arr[tempnr] = pv;
1053
1054
1055 if (SLIST_FIRST(&defsites.stack[tempnr])==NULL) {
1056 stacke=tmpcalloc(sizeof (struct varstack));
1057 stacke->tmpregno=0;
1058 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
1059 }
1060 }
1061
1062 /* Walk the interpass looking for assignment nodes. */
1063 void findTemps(struct interpass *ip)
1064 {
1065 if (ip->type != IP_NODE)
1066 return;
1067
1068 currip = ip;
1069
1070 walkf(ip->ip_node, searchasg, 0);
1071 }
1072
1073 /*
1074 * Algorithm 19.6 from Appel.
1075 */
1076
1077 void
1078 placePhiFunctions(struct p2env *p2e)
1079 {
1080 struct basicblock *bb;
1081 struct basicblock *y;
1082 struct interpass *ip;
1083 int maxtmp, i, j, k;
1084 struct pvarinfo *n;
1085 struct cfgnode *cnode;
1086 TWORD ntype;
1087 struct pvarinfo *pv;
1088 struct phiinfo *phi;
1089 int phifound;
1090
1091 bb = DLIST_NEXT(&p2e->bblocks, bbelem);
1092 defsites.low = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
1093 bb = DLIST_PREV(&p2e->bblocks, bbelem);
1094 maxtmp = ((struct interpass_prolog *)bb->first)->ip_tmpnum;
1095 defsites.size = maxtmp - defsites.low + 1;
1096 defsites.arr = tmpcalloc(defsites.size*sizeof(struct pvarinfo *));
1097 defsites.stack = tmpcalloc(defsites.size*sizeof(SLIST_HEAD(, varstack)));
1098
1099 for (i=0;i<defsites.size;i++)
1100 SLIST_INIT(&defsites.stack[i]);
1101
1102 /* Find all defsites */
1103 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
1104 currbb = bb;
1105 ip = bb->first;
1106 bb->Aorig = setalloc(defsites.size);
1107 bb->Aphi = setalloc(defsites.size);
1108
1109 while (ip != bb->last) {
1110 findTemps(ip);
1111 ip = DLIST_NEXT(ip, qelem);
1112 }
1113 /* Make sure we get the last statement in the bblock */
1114 findTemps(ip);
1115 }
1116
1117 /* For each variable */
1118 for (i = 0; i < defsites.size; i++) {
1119 /* While W not empty */
1120 while (defsites.arr[i] != NULL) {
1121 /* Remove some node n from W */
1122 n = defsites.arr[i];
1123 defsites.arr[i] = n->next;
1124 /* For each y in n->bb->df */
1125 for (j = 0; j < p2e->bbinfo.size; j++) {
1126 if (!TESTBIT(n->bb->df, j))
1127 continue;
1128
1129 if (TESTBIT(p2e->bbinfo.arr[j]->Aphi, i))
1130 continue;
1131
1132 y=p2e->bbinfo.arr[j];
1133 ntype = n->n_type;
1134 k = 0;
1135 /* Amount of predecessors for y */
1136 SLIST_FOREACH(cnode, &y->parents, cfgelem)
1137 k++;
1138 /* Construct phi(...)
1139 */
1140
1141 phifound=0;
1142
1143 SLIST_FOREACH(phi, &y->phi, phielem) {
1144 if (phi->tmpregno==i+defsites.low)
1145 phifound++;
1146 }
1147
1148 if (phifound==0) {
1149 if (b2debug)
1150 printf("Phi in %d(%d) (%p) for %d\n",
1151 y->dfnum,y->bbnum,y,i+defsites.low);
1152
1153 /* If no live in, no phi node needed */
1154 if (!TESTBIT(y->in,
1155 (i+defsites.low-p2e->ipp->ip_tmpnum+MAXREGS))) {
1156 if (b2debug)
1157 printf("tmp %d bb %d unused, no phi\n",
1158 i+defsites.low, y->bbnum);
1159 /* No live in */
1160 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
1161 continue;
1162 }
1163
1164 phi = tmpcalloc(sizeof(struct phiinfo));
1165
1166 phi->tmpregno=i+defsites.low;
1167 phi->size=k;
1168 phi->n_type=ntype;
1169 phi->intmpregno=tmpcalloc(k*sizeof(int));
1170
1171 SLIST_INSERT_LAST(&y->phi,phi,phielem);
1172 } else {
1173 if (b2debug)
1174 printf("Phi already in %d for %d\n",y->dfnum,i+defsites.low);
1175 }
1176
1177 BITSET(p2e->bbinfo.arr[j]->Aphi, i);
1178 if (!TESTBIT(p2e->bbinfo.arr[j]->Aorig, i)) {
1179 pv = tmpalloc(sizeof(struct pvarinfo));
1180 pv->bb = y;
1181 pv->n_type=ntype;
1182 pv->next = defsites.arr[i];
1183 defsites.arr[i] = pv;
1184 }
1185 }
1186 }
1187 }
1188 }
1189
1190 /* Helper function for renamevar. */
1191 static void
1192 renamevarhelper(struct p2env *p2e,NODE *t,void *poplistarg)
1193 {
1194 SLIST_HEAD(, varstack) *poplist=poplistarg;
1195 int opty;
1196 int tempnr;
1197 int newtempnr;
1198 int x;
1199 struct varstack *stacke;
1200
1201 if (t->n_op == ASSIGN && t->n_left->n_op == TEMP) {
1202 renamevarhelper(p2e,t->n_right,poplist);
1203
1204 tempnr=regno(t->n_left)-defsites.low;
1205
1206 newtempnr=p2e->epp->ip_tmpnum++;
1207 regno(t->n_left)=newtempnr;
1208
1209 stacke=tmpcalloc(sizeof (struct varstack));
1210 stacke->tmpregno=newtempnr;
1211 SLIST_INSERT_FIRST(&defsites.stack[tempnr],stacke,varstackelem);
1212
1213 stacke=tmpcalloc(sizeof (struct varstack));
1214 stacke->tmpregno=tempnr;
1215 SLIST_INSERT_FIRST(poplist,stacke,varstackelem);
1216 } else {
1217 if (t->n_op == TEMP) {
1218 tempnr=regno(t)-defsites.low;
1219
1220 if (SLIST_FIRST(&defsites.stack[tempnr])!=NULL) {
1221 x=SLIST_FIRST(&defsites.stack[tempnr])->tmpregno;
1222 regno(t)=x;
1223 }
1224 }
1225
1226 opty = optype(t->n_op);
1227
1228 if (opty != LTYPE)
1229 renamevarhelper(p2e, t->n_left,poplist);
1230 if (opty == BITYPE)
1231 renamevarhelper(p2e, t->n_right,poplist);
1232 }
1233 }
1234
1235
1236 void
1237 renamevar(struct p2env *p2e,struct basicblock *bb)
1238 {
1239 struct interpass *ip;
1240 int h,j;
1241 SLIST_HEAD(, varstack) poplist;
1242 struct varstack *stacke;
1243 struct cfgnode *cfgn2, **cn;
1244 int tmpregno,newtmpregno;
1245 struct phiinfo *phi;
1246
1247 SLIST_INIT(&poplist);
1248
1249 SLIST_FOREACH(phi,&bb->phi,phielem) {
1250 tmpregno=phi->tmpregno-defsites.low;
1251
1252 newtmpregno=p2e->epp->ip_tmpnum++;
1253 phi->newtmpregno=newtmpregno;
1254
1255 stacke=tmpcalloc(sizeof (struct varstack));
1256 stacke->tmpregno=newtmpregno;
1257 SLIST_INSERT_FIRST(&defsites.stack[tmpregno],stacke,varstackelem);
1258
1259 stacke=tmpcalloc(sizeof (struct varstack));
1260 stacke->tmpregno=tmpregno;
1261 SLIST_INSERT_FIRST(&poplist,stacke,varstackelem);
1262 }
1263
1264
1265 ip=bb->first;
1266
1267 while (1) {
1268 if ( ip->type == IP_NODE) {
1269 renamevarhelper(p2e,ip->ip_node,&poplist);
1270 }
1271
1272 if (ip==bb->last)
1273 break;
1274
1275 ip = DLIST_NEXT(ip, qelem);
1276 }
1277
1278 FORCH(cn, bb->ch) {
1279 j=0;
1280
1281 SLIST_FOREACH(cfgn2, &(*cn)->bblock->parents, cfgelem) {
1282 if (cfgn2->bblock->dfnum==bb->dfnum)
1283 break;
1284
1285 j++;
1286 }
1287
1288 SLIST_FOREACH(phi,&(*cn)->bblock->phi,phielem) {
1289 phi->intmpregno[j]=SLIST_FIRST(&defsites.stack[phi->tmpregno-defsites.low])->tmpregno;
1290 }
1291 }
1292
1293 for (h = 1; h < p2e->bbinfo.size; h++) {
1294 if (!TESTBIT(bb->dfchildren, h))
1295 continue;
1296
1297 renamevar(p2e,p2e->bbinfo.arr[h]);
1298 }
1299
1300 SLIST_FOREACH(stacke,&poplist,varstackelem) {
1301 tmpregno=stacke->tmpregno;
1302
1303 defsites.stack[tmpregno].q_forw=defsites.stack[tmpregno].q_forw->varstackelem.q_forw;
1304 }
1305 }
1306
1307 enum pred_type {
1308 pred_unknown = 0,
1309 pred_goto = 1,
1310 pred_cond = 2,
1311 pred_falltrough = 3,
1312 } ;
1313
1314 void
1315 removephi(struct p2env *p2e)
1316 {
1317 struct basicblock *bb,*bbparent;
1318 struct cfgnode *cfgn;
1319 struct phiinfo *phi;
1320 int i;
1321 struct interpass *ip;
1322 struct interpass *pip;
1323 TWORD n_type;
1324
1325 enum pred_type complex = pred_unknown ;
1326
1327 int label=0;
1328 int newlabel;
1329
1330 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
1331 SLIST_FOREACH(phi,&bb->phi,phielem) {
1332 /* Look at only one, notice break at end */
1333 i=0;
1334
1335 SLIST_FOREACH(cfgn, &bb->parents, cfgelem) {
1336 bbparent=cfgn->bblock;
1337
1338 pip=bbparent->last;
1339
1340 complex = pred_unknown ;
1341
1342 BDEBUG(("removephi: %p in %d",pip,bb->dfnum));
1343
1344 if (pip->type == IP_NODE && pip->ip_node->n_op == GOTO) {
1345 BDEBUG((" GOTO "));
1346 label = (int)pip->ip_node->n_left->n_lval;
1347 complex = pred_goto ;
1348 } else if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
1349 BDEBUG((" CBRANCH "));
1350 label = (int)pip->ip_node->n_right->n_lval;
1351
1352 if (bb==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
1353 complex = pred_cond ;
1354 else
1355 complex = pred_falltrough ;
1356
1357 } else if (DLIST_PREV(bb, bbelem) == bbparent) {
1358 complex = pred_falltrough ;
1359 } else {
1360 /* PANIC */
1361 comperr("Assumption blown in rem-phi") ;
1362 }
1363
1364 BDEBUG((" Complex: %d ",complex)) ;
1365
1366 switch (complex) {
1367 case pred_goto:
1368 /* gotos can only go to this place. No bounce tab needed */
1369 SLIST_FOREACH(phi,&bb->phi,phielem) {
1370 if (phi->intmpregno[i]>0) {
1371 n_type=phi->n_type;
1372 ip = ipnode(mkbinode(ASSIGN,
1373 mktemp(phi->newtmpregno, n_type),
1374 mktemp(phi->intmpregno[i],n_type),
1375 n_type));
1376 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
1377
1378 DLIST_INSERT_BEFORE((bbparent->last), ip, qelem);
1379 }
1380 }
1381 break ;
1382 case pred_cond:
1383 /* Here, we need a jump pad */
1384 newlabel=getlab2();
1385
1386 ip = tmpalloc(sizeof(struct interpass));
1387 ip->type = IP_DEFLAB;
1388 /* Line number?? ip->lineno; */
1389 ip->ip_lbl = newlabel;
1390 DLIST_INSERT_BEFORE((bb->first), ip, qelem);
1391
1392 SLIST_FOREACH(phi,&bb->phi,phielem) {
1393 if (phi->intmpregno[i]>0) {
1394 n_type=phi->n_type;
1395 ip = ipnode(mkbinode(ASSIGN,
1396 mktemp(phi->newtmpregno, n_type),
1397 mktemp(phi->intmpregno[i],n_type),
1398 n_type));
1399
1400 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
1401 DLIST_INSERT_BEFORE((bb->first), ip, qelem);
1402 }
1403 }
1404 /* add a jump to us */
1405 ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
1406 DLIST_INSERT_BEFORE((bb->first), ip, qelem);
1407 pip->ip_node->n_right->n_lval=newlabel;
1408 if (!logop(pip->ip_node->n_left->n_op))
1409 comperr("SSA not logop");
1410 pip->ip_node->n_left->n_label=newlabel;
1411 break ;
1412 case pred_falltrough:
1413 if (bb->first->type == IP_DEFLAB) {
1414 label = bb->first->ip_lbl;
1415 BDEBUG(("falltrough label %d\n", label));
1416 } else {
1417 comperr("BBlock has no label?") ;
1418 }
1419
1420 /*
1421 * add a jump to us. We _will_ be, or already have, added code in between.
1422 * The code is created in the wrong order and switched at the insert, thus
1423 * comming out correctly
1424 */
1425
1426 ip = ipnode(mkunode(GOTO, mklnode(ICON, label, 0, INT), 0, INT));
1427 DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
1428
1429 /* Add the code to the end, add a jump to us. */
1430 SLIST_FOREACH(phi,&bb->phi,phielem) {
1431 if (phi->intmpregno[i]>0) {
1432 n_type=phi->n_type;
1433 ip = ipnode(mkbinode(ASSIGN,
1434 mktemp(phi->newtmpregno, n_type),
1435 mktemp(phi->intmpregno[i],n_type),
1436 n_type));
1437
1438 BDEBUG(("(%p, %d -> %d) ", ip, phi->intmpregno[i], phi->newtmpregno));
1439 DLIST_INSERT_AFTER((bbparent->last), ip, qelem);
1440 }
1441 }
1442 break ;
1443 default:
1444 comperr("assumption blown, complex is %d\n", complex) ;
1445 }
1446 BDEBUG(("\n"));
1447 i++;
1448 }
1449 break;
1450 }
1451 }
1452 }
1453
1454
1455 /*
1456 * Remove unreachable nodes in the CFG.
1457 */
1458
1459 void
1460 remunreach(struct p2env *p2e)
1461 {
1462 struct basicblock *bb, *nbb;
1463 struct interpass *next, *ctree;
1464
1465 bb = DLIST_NEXT(&p2e->bblocks, bbelem);
1466 while (bb != &p2e->bblocks) {
1467 nbb = DLIST_NEXT(bb, bbelem);
1468
1469 /* Code with dfnum 0 is unreachable */
1470 if (bb->dfnum != 0) {
1471 bb = nbb;
1472 continue;
1473 }
1474
1475 /* Need the epilogue node for other parts of the
1476 compiler, set its label to 0 and backend will
1477 handle it. */
1478 if (bb->first->type == IP_EPILOG) {
1479 bb->first->ip_lbl = 0;
1480 bb = nbb;
1481 continue;
1482 }
1483
1484 next = bb->first;
1485 do {
1486 ctree = next;
1487 next = DLIST_NEXT(ctree, qelem);
1488
1489 if (ctree->type == IP_NODE)
1490 tfree(ctree->ip_node);
1491 DLIST_REMOVE(ctree, qelem);
1492 } while (ctree != bb->last);
1493
1494 DLIST_REMOVE(bb, bbelem);
1495 bb = nbb;
1496 }
1497 }
1498
1499 static void
1500 printip2(struct interpass *ip)
1501 {
1502 static char *foo[] = {
1503 0, "NODE", "PROLOG", "STKOFF", "EPILOG", "DEFLAB", "DEFNAM", "ASM" };
1504 struct interpass_prolog *ipplg, *epplg;
1505 unsigned i;
1506
1507 if (ip->type > MAXIP)
1508 printf("IP(%d) (%p): ", ip->type, ip);
1509 else
1510 printf("%s (%p): ", foo[ip->type], ip);
1511 switch (ip->type) {
1512 case IP_NODE: printf("\n");
1513 #ifdef PCC_DEBUG
1514 fwalk(ip->ip_node, e2print, 0); break;
1515 #endif
1516 case IP_PROLOG:
1517 ipplg = (struct interpass_prolog *)ip;
1518 printf("%s %s regs",
1519 ipplg->ipp_name, ipplg->ipp_vis ? "(local)" : "");
1520 for (i = 0; i < NIPPREGS; i++)
1521 printf("%s0x%lx", i? ":" : " ",
1522 (long) ipplg->ipp_regs[i]);
1523 printf(" autos %d mintemp %d minlbl %d\n",
1524 ipplg->ipp_autos, ipplg->ip_tmpnum, ipplg->ip_lblnum);
1525 break;
1526 case IP_EPILOG:
1527 epplg = (struct interpass_prolog *)ip;
1528 printf("%s %s regs",
1529 epplg->ipp_name, epplg->ipp_vis ? "(local)" : "");
1530 for (i = 0; i < NIPPREGS; i++)
1531 printf("%s0x%lx", i? ":" : " ",
1532 (long) epplg->ipp_regs[i]);
1533 printf(" autos %d mintemp %d minlbl %d\n",
1534 epplg->ipp_autos, epplg->ip_tmpnum, epplg->ip_lblnum);
1535 break;
1536 case IP_DEFLAB: printf(LABFMT "\n", ip->ip_lbl); break;
1537 case IP_DEFNAM: printf("\n"); break;
1538 case IP_ASM: printf("%s\n", ip->ip_asm); break;
1539 default:
1540 break;
1541 }
1542 }
1543
1544 void
1545 printip(struct interpass *pole)
1546 {
1547 struct interpass *ip;
1548
1549 DLIST_FOREACH(ip, pole, qelem)
1550 printip2(ip);
1551 }
1552
1553 #ifdef PCC_DEBUG
1554 void flownodeprint(NODE *p,FILE *flowdiagramfile);
1555
1556 void
1557 flownodeprint(NODE *p,FILE *flowdiagramfile)
1558 {
1559 int opty;
1560 char *o;
1561
1562 fprintf(flowdiagramfile,"{");
1563
1564 o=opst[p->n_op];
1565
1566 while (*o != 0) {
1567 if (*o=='<' || *o=='>')
1568 fputc('\\',flowdiagramfile);
1569
1570 fputc(*o,flowdiagramfile);
1571 o++;
1572 }
1573
1574
1575 switch( p->n_op ) {
1576 case REG:
1577 fprintf(flowdiagramfile, " %s", rnames[p->n_rval] );
1578 break;
1579
1580 case TEMP:
1581 fprintf(flowdiagramfile, " %d", regno(p));
1582 break;
1583
1584 case XASM:
1585 case XARG:
1586 fprintf(flowdiagramfile, " '%s'", p->n_name);
1587 break;
1588
1589 case ICON:
1590 case NAME:
1591 case OREG:
1592 fprintf(flowdiagramfile, " " );
1593 adrput(flowdiagramfile, p );
1594 break;
1595
1596 case STCALL:
1597 case USTCALL:
1598 case STARG:
1599 case STASG:
1600 fprintf(flowdiagramfile, " size=%d", p->n_stsize );
1601 fprintf(flowdiagramfile, " align=%d", p->n_stalign );
1602 break;
1603 }
1604
1605 opty = optype(p->n_op);
1606
1607 if (opty != LTYPE) {
1608 fprintf(flowdiagramfile,"| {");
1609
1610 flownodeprint(p->n_left,flowdiagramfile);
1611
1612 if (opty == BITYPE) {
1613 fprintf(flowdiagramfile,"|");
1614 flownodeprint(p->n_right,flowdiagramfile);
1615 }
1616 fprintf(flowdiagramfile,"}");
1617 }
1618
1619 fprintf(flowdiagramfile,"}");
1620 }
1621
1622 void
1623 printflowdiagram(struct p2env *p2e, char *type) {
1624 struct basicblock *bbb;
1625 struct cfgnode **cn;
1626 struct interpass *ip;
1627 struct interpass_prolog *plg;
1628 struct phiinfo *phi;
1629 char *name;
1630 char *filename;
1631 int filenamesize;
1632 char *ext=".dot";
1633 FILE *flowdiagramfile;
1634
1635 if (!g2debug)
1636 return;
1637
1638 bbb=DLIST_NEXT(&p2e->bblocks, bbelem);
1639 ip=bbb->first;
1640
1641 if (ip->type != IP_PROLOG)
1642 return;
1643 plg = (struct interpass_prolog *)ip;
1644
1645 name=plg->ipp_name;
1646
1647 filenamesize=strlen(name)+1+strlen(type)+strlen(ext)+1;
1648 filename=tmpalloc(filenamesize);
1649 snprintf(filename,filenamesize,"%s-%s%s",name,type,ext);
1650
1651 flowdiagramfile=fopen(filename,"w");
1652
1653 fprintf(flowdiagramfile,"digraph {\n");
1654 fprintf(flowdiagramfile,"rankdir=LR\n");
1655
1656 DLIST_FOREACH(bbb, &p2e->bblocks, bbelem) {
1657 ip=bbb->first;
1658
1659 fprintf(flowdiagramfile,"bb%p [shape=record ",bbb);
1660
1661 if (ip->type==IP_PROLOG)
1662 fprintf(flowdiagramfile,"root ");
1663
1664 fprintf(flowdiagramfile,"label=\"");
1665
1666 SLIST_FOREACH(phi,&bbb->phi,phielem) {
1667 fprintf(flowdiagramfile,"Phi %d|",phi->tmpregno);
1668 }
1669
1670
1671 while (1) {
1672 switch (ip->type) {
1673 case IP_NODE:
1674 flownodeprint(ip->ip_node,flowdiagramfile);
1675 break;
1676
1677 case IP_DEFLAB:
1678 fprintf(flowdiagramfile,"Label: %d", ip->ip_lbl);
1679 break;
1680
1681 case IP_PROLOG:
1682 plg = (struct interpass_prolog *)ip;
1683
1684 fprintf(flowdiagramfile,"%s %s",plg->ipp_name,type);
1685 break;
1686 }
1687
1688 fprintf(flowdiagramfile,"|");
1689 fprintf(flowdiagramfile,"|");
1690
1691 if (ip==bbb->last)
1692 break;
1693
1694 ip = DLIST_NEXT(ip, qelem);
1695 }
1696 fprintf(flowdiagramfile,"\"]\n");
1697
1698 FORCH(cn, bbb->ch) {
1699 char *color="black";
1700 struct interpass *pip=bbb->last;
1701
1702 if (pip->type == IP_NODE && pip->ip_node->n_op == CBRANCH) {
1703 int label = (int)pip->ip_node->n_right->n_lval;
1704
1705 if ((*cn)->bblock==p2e->labinfo.arr[label - p2e->ipp->ip_lblnum])
1706 color="red";
1707 }
1708
1709 fprintf(flowdiagramfile,"bb%p -> bb%p [color=%s]\n", bbb,(*cn)->bblock,color);
1710 }
1711 }
1712
1713 fprintf(flowdiagramfile,"}\n");
1714 fclose(flowdiagramfile);
1715 }
1716
1717 #endif
1718
1719 /* walk all the programm */
1720 void WalkAll(struct p2env* p2e, void (*f) (NODE*, void*), void* arg, int type)
1721 {
1722 struct interpass *ipole = &p2e->ipole;
1723 struct interpass *ip ;
1724 if (0 != type) {
1725 DLIST_FOREACH(ip, ipole, qelem) {
1726 if (ip->type == IP_NODE && ip->ip_node->n_op == type)
1727 walkf(ip->ip_node, f, arg) ;
1728 }
1729 } else {
1730 DLIST_FOREACH(ip, ipole, qelem) {
1731 if (ip->type == IP_NODE)
1732 walkf(ip->ip_node, f, arg) ;
1733 }
1734 }
1735 }
1736 #if 0
1737 static int is_goto_label(struct interpass*g, struct interpass* l)
1738 {
1739 if (!g || !l)
1740 return 0 ;
1741 if (g->type != IP_NODE) return 0 ;
1742 if (l->type != IP_DEFLAB) return 0 ;
1743 if (g->ip_node->n_op != GOTO) return 0 ;
1744 if (g->ip_node->n_left->n_lval != l->ip_lbl) return 0 ;
1745 return 1 ;
1746 }
1747 #endif
1748
1749 /*
1750 * iterate over the basic blocks.
1751 * In case a block has only one successor and that one has only one pred, and the link is a goto:
1752 * place the second one immediately behind the first one (in terms of nodes, means cut&resplice).
1753 * This should take care of a lot of jumps.
1754 * one problem: Cannot move the first or last basic block (prolog/epilog). This is taken care of by
1755 * moving block #1 to #2, not #2 to #1
1756 * More complex (on the back cooker;) : first coalesc the inner loops (L1 cache), then go from inside out.
1757 */
1758
1759 static unsigned long count_blocks(struct p2env* p2e)
1760 {
1761 struct basicblock* bb ;
1762 unsigned long count = 0 ;
1763 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
1764 ++count ;
1765 }
1766 return count ;
1767 }
1768
1769 struct block_map {
1770 struct basicblock* block ;
1771 unsigned long index ;
1772 unsigned long thread ;
1773 } ;
1774
1775 static unsigned long map_blocks(struct p2env* p2e, struct block_map* map, unsigned long count)
1776 {
1777 struct basicblock* bb ;
1778 unsigned long indx = 0 ;
1779 int ignore = 2 ;
1780 unsigned long thread ;
1781 unsigned long changes ;
1782
1783 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
1784 map[indx].block = bb ;
1785 map[indx].index = indx ;
1786
1787 /* ignore the first 2 labels, maybe up to 3 BBs */
1788 if (ignore) {
1789 if (bb->first->type == IP_DEFLAB)
1790 --ignore;
1791
1792 map[indx].thread = 1 ; /* these are "fixed" */
1793 } else
1794 map[indx].thread = 0 ;
1795
1796 indx++ ;
1797 }
1798
1799 thread = 1 ;
1800 do {
1801 changes = 0 ;
1802
1803 for (indx=0; indx < count; indx++) {
1804 /* find block without trace */
1805 if (map[indx].thread == 0) {
1806 /* do new thread */
1807 struct cfgnode **cn ;
1808 struct basicblock *block2 = 0;
1809 unsigned long i ;
1810 unsigned long added ;
1811
1812 BDEBUG (("new thread %ld at block %ld\n", thread, indx)) ;
1813
1814 bb = map[indx].block ;
1815 do {
1816 added = 0 ;
1817
1818 for (i=0; i < count; i++) {
1819 if (map[i].block == bb && map[i].thread == 0) {
1820 map[i].thread = thread ;
1821
1822 BDEBUG(("adding block %ld to trace %ld\n", i, thread)) ;
1823
1824 changes ++ ;
1825 added++ ;
1826
1827 /*
1828 * pick one from followers. For now (simple), pick the
1829 * one who is directly following us. If none of that exists,
1830 * this code picks the last one.
1831 */
1832
1833 FORCH(cn, bb->ch) {
1834 block2=(*cn)->bblock ;
1835 #if 1
1836 if (i+1 < count && map[i+1].block == block2)
1837 break ; /* pick that one */
1838 #else
1839 if (block2) break ;
1840 #endif
1841 }
1842
1843 if (block2)
1844 bb = block2 ;
1845 }
1846 }
1847 } while (added) ;
1848 thread++ ;
1849 }
1850 }
1851 } while (changes);
1852
1853 /* Last block is also a thread on it's own, and the highest one. */
1854 /*
1855 thread++ ;
1856 map[count-1].thread = thread ;
1857 */
1858 if (b2debug) {
1859 printf("Threads\n");
1860 for (indx=0; indx < count; indx++) {
1861 printf("Block #%ld (lbl %d) Thread %ld\n", indx, map[indx].block->first->ip_lbl, map[indx].thread);
1862 }
1863 }
1864 return thread ;
1865 }
1866
1867
1868 void TraceSchedule(struct p2env* p2e)
1869 {
1870 struct block_map* map ;
1871 unsigned long block_count = count_blocks(p2e);
1872 unsigned long i ;
1873 unsigned long threads;
1874 struct interpass *front, *back ;
1875
1876 map = tmpalloc(block_count * sizeof(struct block_map));
1877
1878 threads = map_blocks(p2e, map, block_count) ;
1879
1880 back = map[0].block->last ;
1881 for (i=1; i < block_count; i++) {
1882 /* collect the trace */
1883 unsigned long j ;
1884 unsigned long thread = map[i].thread ;
1885 if (thread) {
1886 BDEBUG(("Thread %ld\n", thread)) ;
1887 for (j=i; j < block_count; j++) {
1888 if (map[j].thread == thread) {
1889 front = map[j].block->first ;
1890
1891 BDEBUG(("Trace %ld, old BB %ld, next BB %ld\t",
1892 thread, i, j)) ;
1893 BDEBUG(("Label %d\n", front->ip_lbl)) ;
1894 DLIST_NEXT(back, qelem) = front ;
1895 DLIST_PREV(front, qelem) = back ;
1896 map[j].thread = 0 ; /* done */
1897 back = map[j].block->last ;
1898 DLIST_NEXT(back, qelem) = 0 ;
1899 }
1900 }
1901 }
1902 }
1903 DLIST_NEXT(back, qelem) = &(p2e->ipole) ;
1904 DLIST_PREV(&p2e->ipole, qelem) = back ;
1905 }
1906
1907 static void add_labels(struct p2env* p2e)
1908 {
1909 struct interpass *ipole = &p2e->ipole ;
1910 struct interpass *ip ;
1911
1912 DLIST_FOREACH(ip, ipole, qelem) {
1913 if (ip->type == IP_NODE && ip->ip_node->n_op == CBRANCH) {
1914 struct interpass *n = DLIST_NEXT(ip, qelem);
1915 if (n && n->type != IP_DEFLAB) {
1916 struct interpass* lab;
1917 int newlabel=getlab2() ;
1918
1919 BDEBUG(("add_label L%d\n", newlabel));
1920
1921 lab = tmpalloc(sizeof(struct interpass));
1922 lab->type = IP_DEFLAB;
1923 /* Line number?? ip->lineno; */
1924 lab->ip_lbl = newlabel;
1925 DLIST_INSERT_AFTER(ip, lab, qelem);
1926 }
1927 }
1928 }
1929 }
1930
1931 /* node map */
1932 #ifdef ENABLE_NEW
1933 struct node_map {
1934 NODE* node ; /* the node */
1935 unsigned int node_num ; /* node is equal to that one */
1936 unsigned int var_num ; /* node computes this variable */
1937 } ;
1938
1939 static unsigned long nodes_counter ;
1940 static void node_map_count_walker(NODE* n, void* x)
1941 {
1942 nodes_counter ++ ;
1943 }
1944
1945 static void do_cse(struct p2env* p2e)
1946 {
1947 nodes_counter = 0 ;
1948 WalkAll(p2e, node_map_count_walker, 0, 0) ;
1949 BDEBUG(("Found %ld nodes\n", nodes_counter)) ;
1950 }
1951 #endif
1952
1953 #define BITALLOC(ptr,all,sz) { \
1954 int sz__s = BIT2BYTE(sz); ptr = all(sz__s); memset(ptr, 0, sz__s); }
1955 #define VALIDREG(p) (p->n_op == REG && TESTBIT(validregs, regno(p)))
1956 #define XCHECK(x) if (x < 0 || x >= xbits) printf("x out of range %d\n", x)
1957 #define RUP(x) (((x)+NUMBITS-1)/NUMBITS)
1958 #define SETCOPY(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] = f[i]
1959 #define SETSET(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] |= f[i]
1960 #define SETCLEAR(t,f,i,n) for (i = 0; i < RUP(n); i++) t[i] &= ~f[i]
1961 #define SETCMP(v,t,f,i,n) for (i = 0; i < RUP(n); i++) \
1962 if (t[i] != f[i]) v = 1
1963
1964 static int xxx, xbits;
1965 /*
1966 * Set/clear long term liveness for regs and temps.
1967 */
1968 static void
1969 unionize(NODE *p, struct basicblock *bb, int suboff)
1970 {
1971 int o, ty;
1972
1973 if ((o = p->n_op) == TEMP || VALIDREG(p)) {
1974 int b = regno(p);
1975 if (o == TEMP)
1976 b = b - suboff + MAXREGS;
1977 XCHECK(b);
1978 BITSET(bb->gen, b);
1979 }
1980 if (asgop(o)) {
1981 if (p->n_left->n_op == TEMP || VALIDREG(p)) {
1982 int b = regno(p->n_left);
1983 if (p->n_left->n_op == TEMP)
1984 b = b - suboff + MAXREGS;
1985 XCHECK(b);
1986 BITCLEAR(bb->gen, b);
1987 BITSET(bb->killed, b);
1988 unionize(p->n_right, bb, suboff);
1989 return;
1990 }
1991 }
1992 ty = optype(o);
1993 if (ty != LTYPE)
1994 unionize(p->n_left, bb, suboff);
1995 if (ty == BITYPE)
1996 unionize(p->n_right, bb, suboff);
1997 }
1998
1999 /*
2000 * Found an extended assembler node, so growel out gen/killed nodes.
2001 */
2002 static void
2003 xasmionize(NODE *p, void *arg)
2004 {
2005 struct basicblock *bb = arg;
2006 int cw, b;
2007
2008 if (p->n_op == ICON && p->n_type == STRTY)
2009 return; /* dummy end marker */
2010
2011 cw = xasmcode(p->n_name);
2012 if (XASMVAL(cw) == 'n' || XASMVAL(cw) == 'm')
2013 return; /* no flow analysis */
2014 p = p->n_left;
2015
2016 if (XASMVAL(cw) == 'g' && p->n_op != TEMP && p->n_op != REG)
2017 return; /* no flow analysis */
2018
2019 b = regno(p);
2020 #if 0
2021 if (XASMVAL(cw) == 'r' && p->n_op == TEMP)
2022 addnotspill(b);
2023 #endif
2024 #define MKTOFF(r) ((r) - xxx)
2025 if (XASMISOUT(cw)) {
2026 if (p->n_op == TEMP) {
2027 BITCLEAR(bb->gen, MKTOFF(b));
2028 BITSET(bb->killed, MKTOFF(b));
2029 } else if (p->n_op == REG) {
2030 BITCLEAR(bb->gen, b);
2031 BITSET(bb->killed, b);
2032 } else
2033 uerror("bad xasm node type %d", p->n_op);
2034 }
2035 if (XASMISINP(cw)) {
2036 if (p->n_op == TEMP) {
2037 BITSET(bb->gen, MKTOFF(b));
2038 } else if (p->n_op == REG) {
2039 BITSET(bb->gen, b);
2040 } else if (optype(p->n_op) != LTYPE) {
2041 if (XASMVAL(cw) == 'r')
2042 uerror("couldn't find available register");
2043 else
2044 uerror("bad xasm node type2");
2045 }
2046 }
2047 }
2048
2049 /*
2050 * Do variable liveness analysis. Only analyze the long-lived
2051 * variables, and save the live-on-exit temporaries in a bit-field
2052 * at the end of each basic block. This bit-field is later used
2053 * when doing short-range liveness analysis in Build().
2054 */
2055 void
2056 liveanal(struct p2env *p2e)
2057 {
2058 struct basicblock *bb;
2059 struct interpass *ip;
2060 bittype *saved;
2061 int i, mintemp, again;
2062
2063 xbits = p2e->epp->ip_tmpnum - p2e->ipp->ip_tmpnum + MAXREGS;
2064 mintemp = p2e->ipp->ip_tmpnum;
2065
2066 /* Just fetch space for the temporaries from heap */
2067 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
2068 BITALLOC(bb->gen,tmpalloc,xbits);
2069 BITALLOC(bb->killed,tmpalloc,xbits);
2070 BITALLOC(bb->in,tmpalloc,xbits);
2071 BITALLOC(bb->out,tmpalloc,xbits);
2072 }
2073 BITALLOC(saved,tmpalloc,xbits);
2074
2075 xxx = mintemp;
2076 /*
2077 * generate the gen-killed sets for all basic blocks.
2078 */
2079 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
2080 for (ip = bb->last; ; ip = DLIST_PREV(ip, qelem)) {
2081 /* gen/killed is 'p', this node is 'n' */
2082 if (ip->type == IP_NODE) {
2083 if (ip->ip_node->n_op == XASM)
2084 flist(ip->ip_node->n_left,
2085 xasmionize, bb);
2086 else
2087 unionize(ip->ip_node, bb, mintemp);
2088 }
2089 if (ip == bb->first)
2090 break;
2091 }
2092 memcpy(bb->in, bb->gen, BIT2BYTE(xbits));
2093 #ifdef PCC_DEBUG
2094 #define PRTRG(x) printf("%d ", i < MAXREGS ? i : i + p2e->ipp->ip_tmpnum-MAXREGS)
2095 if (b2debug > 1) {
2096 printf("basic block %d\ngen: ", bb->bbnum);
2097 for (i = 0; i < xbits; i++)
2098 if (TESTBIT(bb->gen, i))
2099 PRTRG(i);
2100 printf("\nkilled: ");
2101 for (i = 0; i < xbits; i++)
2102 if (TESTBIT(bb->killed, i))
2103 PRTRG(i);
2104 printf("\n");
2105 }
2106 #endif
2107 }
2108 /* do liveness analysis on basic block level */
2109 do {
2110 struct cfgnode **cn;
2111 int j;
2112
2113 again = 0;
2114 /* XXX - loop should be in reversed execution-order */
2115 DLIST_FOREACH_REVERSE(bb, &p2e->bblocks, bbelem) {
2116 SETCOPY(saved, bb->out, j, xbits);
2117 FORCH(cn, bb->ch) {
2118 SETSET(bb->out, cn[0]->bblock->in, j, xbits);
2119 }
2120 SETCMP(again, saved, bb->out, j, xbits);
2121 SETCOPY(saved, bb->in, j, xbits);
2122 SETCOPY(bb->in, bb->out, j, xbits);
2123 SETCLEAR(bb->in, bb->killed, j, xbits);
2124 SETSET(bb->in, bb->gen, j, xbits);
2125 SETCMP(again, saved, bb->in, j, xbits);
2126 }
2127 } while (again);
2128
2129 #ifdef PCC_DEBUG
2130 DLIST_FOREACH(bb, &p2e->bblocks, bbelem) {
2131 if (b2debug) {
2132 printf("all basic block %d\nin: ", bb->bbnum);
2133 for (i = 0; i < xbits; i++)
2134 if (TESTBIT(bb->in, i))
2135 PRTRG(i);
2136 printf("\nout: ");
2137 for (i = 0; i < xbits; i++)
2138 if (TESTBIT(bb->out, i))
2139 PRTRG(i);
2140 printf("\n");
2141 }
2142 }
2143 #endif
2144 }