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