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