live.c (3104B)
1 #include "all.h" 2 3 void 4 liveon(BSet *v, Blk *b, Blk *s) 5 { 6 Phi *p; 7 uint a; 8 9 bscopy(v, s->in); 10 for (p=s->phi; p; p=p->link) 11 if (rtype(p->to) == RTmp) 12 bsclr(v, p->to.val); 13 for (p=s->phi; p; p=p->link) 14 for (a=0; a<p->narg; a++) 15 if (p->blk[a] == b) 16 if (rtype(p->arg[a]) == RTmp) { 17 bsset(v, p->arg[a].val); 18 bsset(b->gen, p->arg[a].val); 19 } 20 } 21 22 static void 23 bset(Ref r, Blk *b, int *nlv, Tmp *tmp) 24 { 25 26 if (rtype(r) != RTmp) 27 return; 28 bsset(b->gen, r.val); 29 if (!bshas(b->in, r.val)) { 30 nlv[KBASE(tmp[r.val].cls)]++; 31 bsset(b->in, r.val); 32 } 33 } 34 35 /* liveness analysis 36 * requires rpo computation 37 */ 38 void 39 filllive(Fn *f) 40 { 41 Blk *b; 42 Ins *i; 43 int k, t, m[2], n, chg, nlv[2]; 44 BSet u[1], v[1]; 45 Mem *ma; 46 47 bsinit(u, f->ntmp); 48 bsinit(v, f->ntmp); 49 for (b=f->start; b; b=b->link) { 50 bsinit(b->in, f->ntmp); 51 bsinit(b->out, f->ntmp); 52 bsinit(b->gen, f->ntmp); 53 } 54 chg = 1; 55 Again: 56 for (n=f->nblk-1; n>=0; n--) { 57 b = f->rpo[n]; 58 59 bscopy(u, b->out); 60 if (b->s1) { 61 liveon(v, b, b->s1); 62 bsunion(b->out, v); 63 } 64 if (b->s2) { 65 liveon(v, b, b->s2); 66 bsunion(b->out, v); 67 } 68 chg |= !bsequal(b->out, u); 69 70 memset(nlv, 0, sizeof nlv); 71 b->out->t[0] |= T.rglob; 72 bscopy(b->in, b->out); 73 for (t=0; bsiter(b->in, &t); t++) 74 nlv[KBASE(f->tmp[t].cls)]++; 75 if (rtype(b->jmp.arg) == RCall) { 76 assert((int)bscount(b->in) == T.nrglob && 77 b->in->t[0] == T.rglob); 78 b->in->t[0] |= T.retregs(b->jmp.arg, nlv); 79 } else 80 bset(b->jmp.arg, b, nlv, f->tmp); 81 for (k=0; k<2; k++) 82 b->nlive[k] = nlv[k]; 83 for (i=&b->ins[b->nins]; i!=b->ins;) { 84 if ((--i)->op == Ocall && rtype(i->arg[1]) == RCall) { 85 b->in->t[0] &= ~T.retregs(i->arg[1], m); 86 for (k=0; k<2; k++) { 87 nlv[k] -= m[k]; 88 /* caller-save registers are used 89 * by the callee, in that sense, 90 * right in the middle of the call, 91 * they are live: */ 92 nlv[k] += T.nrsave[k]; 93 if (nlv[k] > b->nlive[k]) 94 b->nlive[k] = nlv[k]; 95 } 96 b->in->t[0] |= T.argregs(i->arg[1], m); 97 for (k=0; k<2; k++) { 98 nlv[k] -= T.nrsave[k]; 99 nlv[k] += m[k]; 100 } 101 } 102 if (!req(i->to, R)) { 103 assert(rtype(i->to) == RTmp); 104 t = i->to.val; 105 if (bshas(b->in, t)) 106 nlv[KBASE(f->tmp[t].cls)]--; 107 bsset(b->gen, t); 108 bsclr(b->in, t); 109 } 110 for (k=0; k<2; k++) 111 switch (rtype(i->arg[k])) { 112 case RMem: 113 ma = &f->mem[i->arg[k].val]; 114 bset(ma->base, b, nlv, f->tmp); 115 bset(ma->index, b, nlv, f->tmp); 116 break; 117 default: 118 bset(i->arg[k], b, nlv, f->tmp); 119 break; 120 } 121 for (k=0; k<2; k++) 122 if (nlv[k] > b->nlive[k]) 123 b->nlive[k] = nlv[k]; 124 } 125 } 126 if (chg) { 127 chg = 0; 128 goto Again; 129 } 130 131 if (debug['L']) { 132 fprintf(stderr, "\n> Liveness analysis:\n"); 133 for (b=f->start; b; b=b->link) { 134 fprintf(stderr, "\t%-10sin: ", b->name); 135 dumpts(b->in, f->tmp, stderr); 136 fprintf(stderr, "\t out: "); 137 dumpts(b->out, f->tmp, stderr); 138 fprintf(stderr, "\t gen: "); 139 dumpts(b->gen, f->tmp, stderr); 140 fprintf(stderr, "\t live: "); 141 fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]); 142 } 143 } 144 }