qbe

Internal scc patchset buffer for QBE
Log | Files | Refs | README | LICENSE

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 }