qbe

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

spill.c (10374B)


      1 #include "all.h"
      2 
      3 static void
      4 aggreg(Blk *hd, Blk *b)
      5 {
      6 	int k;
      7 
      8 	/* aggregate looping information at
      9 	 * loop headers */
     10 	bsunion(hd->gen, b->gen);
     11 	for (k=0; k<2; k++)
     12 		if (b->nlive[k] > hd->nlive[k])
     13 			hd->nlive[k] = b->nlive[k];
     14 }
     15 
     16 static void
     17 tmpuse(Ref r, int use, int loop, Fn *fn)
     18 {
     19 	Mem *m;
     20 	Tmp *t;
     21 
     22 	if (rtype(r) == RMem) {
     23 		m = &fn->mem[r.val];
     24 		tmpuse(m->base, 1, loop, fn);
     25 		tmpuse(m->index, 1, loop, fn);
     26 	}
     27 	else if (rtype(r) == RTmp && r.val >= Tmp0) {
     28 		t = &fn->tmp[r.val];
     29 		t->nuse += use;
     30 		t->ndef += !use;
     31 		t->cost += loop;
     32 	}
     33 }
     34 
     35 /* evaluate spill costs of temporaries,
     36  * this also fills usage information
     37  * requires rpo, preds
     38  */
     39 void
     40 fillcost(Fn *fn)
     41 {
     42 	int n;
     43 	uint a;
     44 	Blk *b;
     45 	Ins *i;
     46 	Tmp *t;
     47 	Phi *p;
     48 
     49 	loopiter(fn, aggreg);
     50 	if (debug['S']) {
     51 		fprintf(stderr, "\n> Loop information:\n");
     52 		for (b=fn->start; b; b=b->link) {
     53 			for (a=0; a<b->npred; ++a)
     54 				if (b->id <= b->pred[a]->id)
     55 					break;
     56 			if (a != b->npred) {
     57 				fprintf(stderr, "\t%-10s", b->name);
     58 				fprintf(stderr, " (% 3d ", b->nlive[0]);
     59 				fprintf(stderr, "% 3d) ", b->nlive[1]);
     60 				dumpts(b->gen, fn->tmp, stderr);
     61 			}
     62 		}
     63 	}
     64 	for (t=fn->tmp; t-fn->tmp < fn->ntmp; t++) {
     65 		t->cost = t-fn->tmp < Tmp0 ? UINT_MAX : 0;
     66 		t->nuse = 0;
     67 		t->ndef = 0;
     68 	}
     69 	for (b=fn->start; b; b=b->link) {
     70 		for (p=b->phi; p; p=p->link) {
     71 			t = &fn->tmp[p->to.val];
     72 			tmpuse(p->to, 0, 0, fn);
     73 			for (a=0; a<p->narg; a++) {
     74 				n = p->blk[a]->loop;
     75 				t->cost += n;
     76 				tmpuse(p->arg[a], 1, n, fn);
     77 			}
     78 		}
     79 		n = b->loop;
     80 		for (i=b->ins; i<&b->ins[b->nins]; i++) {
     81 			tmpuse(i->to, 0, n, fn);
     82 			tmpuse(i->arg[0], 1, n, fn);
     83 			tmpuse(i->arg[1], 1, n, fn);
     84 		}
     85 		tmpuse(b->jmp.arg, 1, n, fn);
     86 	}
     87 	if (debug['S']) {
     88 		fprintf(stderr, "\n> Spill costs:\n");
     89 		for (n=Tmp0; n<fn->ntmp; n++)
     90 			fprintf(stderr, "\t%-10s %d\n",
     91 				fn->tmp[n].name,
     92 				fn->tmp[n].cost);
     93 		fprintf(stderr, "\n");
     94 	}
     95 }
     96 
     97 static BSet *fst; /* temps to prioritize in registers (for tcmp1) */
     98 static Tmp *tmp;  /* current temporaries (for tcmpX) */
     99 static int ntmp;  /* current # of temps (for limit) */
    100 static int locs;  /* stack size used by locals */
    101 static int slot4; /* next slot of 4 bytes */
    102 static int slot8; /* ditto, 8 bytes */
    103 static BSet mask[2][1]; /* class masks */
    104 
    105 static int
    106 tcmp0(const void *pa, const void *pb)
    107 {
    108 	uint ca, cb;
    109 
    110 	ca = tmp[*(int *)pa].cost;
    111 	cb = tmp[*(int *)pb].cost;
    112 	return (cb < ca) ? -1 : (cb > ca);
    113 }
    114 
    115 static int
    116 tcmp1(const void *pa, const void *pb)
    117 {
    118 	int c;
    119 
    120 	c = bshas(fst, *(int *)pb) - bshas(fst, *(int *)pa);
    121 	return c ? c : tcmp0(pa, pb);
    122 }
    123 
    124 static Ref
    125 slot(int t)
    126 {
    127 	int s;
    128 
    129 	assert(t >= Tmp0 && "cannot spill register");
    130 	s = tmp[t].slot;
    131 	if (s == -1) {
    132 		/* specific to NAlign == 3 */
    133 		/* nice logic to pack stack slots
    134 		 * on demand, there can be only
    135 		 * one hole and slot4 points to it
    136 		 *
    137 		 * invariant: slot4 <= slot8
    138 		 */
    139 		if (KWIDE(tmp[t].cls)) {
    140 			s = slot8;
    141 			if (slot4 == slot8)
    142 				slot4 += 2;
    143 			slot8 += 2;
    144 		} else {
    145 			s = slot4;
    146 			if (slot4 == slot8) {
    147 				slot8 += 2;
    148 				slot4 += 1;
    149 			} else
    150 				slot4 = slot8;
    151 		}
    152 		s += locs;
    153 		tmp[t].slot = s;
    154 	}
    155 	return SLOT(s);
    156 }
    157 
    158 /* restricts b to hold at most k
    159  * temporaries, preferring those
    160  * present in f (if given), then
    161  * those with the largest spill
    162  * cost
    163  */
    164 static void
    165 limit(BSet *b, int k, BSet *f)
    166 {
    167 	static int *tarr, maxt;
    168 	int i, t, nt;
    169 
    170 	nt = bscount(b);
    171 	if (nt <= k)
    172 		return;
    173 	if (nt > maxt) {
    174 		free(tarr);
    175 		tarr = emalloc(nt * sizeof tarr[0]);
    176 		maxt = nt;
    177 	}
    178 	for (i=0, t=0; bsiter(b, &t); t++) {
    179 		bsclr(b, t);
    180 		tarr[i++] = t;
    181 	}
    182 	if (nt > 1) {
    183 		if (!f)
    184 			qsort(tarr, nt, sizeof tarr[0], tcmp0);
    185 		else {
    186 			fst = f;
    187 			qsort(tarr, nt, sizeof tarr[0], tcmp1);
    188 		}
    189 	}
    190 	for (i=0; i<k && i<nt; i++)
    191 		bsset(b, tarr[i]);
    192 	for (; i<nt; i++)
    193 		slot(tarr[i]);
    194 }
    195 
    196 /* spills temporaries to fit the
    197  * target limits using the same
    198  * preferences as limit(); assumes
    199  * that k1 gprs and k2 fprs are
    200  * currently in use
    201  */
    202 static void
    203 limit2(BSet *b1, int k1, int k2, BSet *f)
    204 {
    205 	BSet b2[1];
    206 
    207 	bsinit(b2, ntmp); /* todo, free those */
    208 	bscopy(b2, b1);
    209 	bsinter(b1, mask[0]);
    210 	bsinter(b2, mask[1]);
    211 	limit(b1, T.ngpr - k1, f);
    212 	limit(b2, T.nfpr - k2, f);
    213 	bsunion(b1, b2);
    214 }
    215 
    216 static void
    217 sethint(BSet *u, bits r)
    218 {
    219 	int t;
    220 
    221 	for (t=Tmp0; bsiter(u, &t); t++)
    222 		tmp[phicls(t, tmp)].hint.m |= r;
    223 }
    224 
    225 /* reloads temporaries in u that are
    226  * not in v from their slots
    227  */
    228 static void
    229 reloads(BSet *u, BSet *v)
    230 {
    231 	int t;
    232 
    233 	for (t=Tmp0; bsiter(u, &t); t++)
    234 		if (!bshas(v, t))
    235 			emit(Oload, tmp[t].cls, TMP(t), slot(t), R);
    236 }
    237 
    238 static void
    239 store(Ref r, int s)
    240 {
    241 	if (s != -1)
    242 		emit(Ostorew + tmp[r.val].cls, 0, R, r, SLOT(s));
    243 }
    244 
    245 static int
    246 regcpy(Ins *i)
    247 {
    248 	return i->op == Ocopy && isreg(i->arg[0]);
    249 }
    250 
    251 static Ins *
    252 dopm(Blk *b, Ins *i, BSet *v)
    253 {
    254 	int n, t;
    255 	BSet u[1];
    256 	Ins *i1;
    257 	bits r;
    258 
    259 	bsinit(u, ntmp); /* todo, free those */
    260 	/* consecutive copies from
    261 	 * registers need to be handled
    262 	 * as one large instruction
    263 	 *
    264 	 * fixme: there is an assumption
    265 	 * that calls are always followed
    266 	 * by copy instructions here, this
    267 	 * might not be true if previous
    268 	 * passes change
    269 	 */
    270 	i1 = ++i;
    271 	do {
    272 		i--;
    273 		t = i->to.val;
    274 		if (!req(i->to, R))
    275 		if (bshas(v, t)) {
    276 			bsclr(v, t);
    277 			store(i->to, tmp[t].slot);
    278 		}
    279 		bsset(v, i->arg[0].val);
    280 	} while (i != b->ins && regcpy(i-1));
    281 	bscopy(u, v);
    282 	if (i != b->ins && (i-1)->op == Ocall) {
    283 		v->t[0] &= ~T.retregs((i-1)->arg[1], 0);
    284 		limit2(v, T.nrsave[0], T.nrsave[1], 0);
    285 		for (n=0, r=0; T.rsave[n]>=0; n++)
    286 			r |= BIT(T.rsave[n]);
    287 		v->t[0] |= T.argregs((i-1)->arg[1], 0);
    288 	} else {
    289 		limit2(v, 0, 0, 0);
    290 		r = v->t[0];
    291 	}
    292 	sethint(v, r);
    293 	reloads(u, v);
    294 	do
    295 		emiti(*--i1);
    296 	while (i1 != i);
    297 	return i;
    298 }
    299 
    300 static void
    301 merge(BSet *u, Blk *bu, BSet *v, Blk *bv)
    302 {
    303 	int t;
    304 
    305 	if (bu->loop <= bv->loop)
    306 		bsunion(u, v);
    307 	else
    308 		for (t=0; bsiter(v, &t); t++)
    309 			if (tmp[t].slot == -1)
    310 				bsset(u, t);
    311 }
    312 
    313 /* spill code insertion
    314  * requires spill costs, rpo, liveness
    315  *
    316  * Note: this will replace liveness
    317  * information (in, out) with temporaries
    318  * that must be in registers at block
    319  * borders
    320  *
    321  * Be careful with:
    322  * - Ocopy instructions to ensure register
    323  *   constraints
    324  */
    325 void
    326 spill(Fn *fn)
    327 {
    328 	Blk *b, *s1, *s2, *hd, **bp;
    329 	int j, l, t, k, lvarg[2];
    330 	uint n;
    331 	BSet u[1], v[1], w[1];
    332 	Ins *i;
    333 	Phi *p;
    334 	Mem *m;
    335 	bits r;
    336 
    337 	tmp = fn->tmp;
    338 	ntmp = fn->ntmp;
    339 	bsinit(u, ntmp);
    340 	bsinit(v, ntmp);
    341 	bsinit(w, ntmp);
    342 	bsinit(mask[0], ntmp);
    343 	bsinit(mask[1], ntmp);
    344 	locs = fn->slot;
    345 	slot4 = 0;
    346 	slot8 = 0;
    347 	for (t=0; t<ntmp; t++) {
    348 		k = 0;
    349 		if (t >= T.fpr0 && t < T.fpr0 + T.nfpr)
    350 			k = 1;
    351 		if (t >= Tmp0)
    352 			k = KBASE(tmp[t].cls);
    353 		bsset(mask[k], t);
    354 	}
    355 
    356 	for (bp=&fn->rpo[fn->nblk]; bp!=fn->rpo;) {
    357 		b = *--bp;
    358 		/* invariant: all blocks with bigger rpo got
    359 		 * their in,out updated. */
    360 
    361 		/* 1. find temporaries in registers at
    362 		 * the end of the block (put them in v) */
    363 		curi = 0;
    364 		s1 = b->s1;
    365 		s2 = b->s2;
    366 		hd = 0;
    367 		if (s1 && s1->id <= b->id)
    368 			hd = s1;
    369 		if (s2 && s2->id <= b->id)
    370 		if (!hd || s2->id >= hd->id)
    371 			hd = s2;
    372 		if (hd) {
    373 			/* back-edge */
    374 			bszero(v);
    375 			hd->gen->t[0] |= T.rglob; /* don't spill registers */
    376 			for (k=0; k<2; k++) {
    377 				n = k == 0 ? T.ngpr : T.nfpr;
    378 				bscopy(u, b->out);
    379 				bsinter(u, mask[k]);
    380 				bscopy(w, u);
    381 				bsinter(u, hd->gen);
    382 				bsdiff(w, hd->gen);
    383 				if (bscount(u) < n) {
    384 					j = bscount(w); /* live through */
    385 					l = hd->nlive[k];
    386 					limit(w, n - (l - j), 0);
    387 					bsunion(u, w);
    388 				} else
    389 					limit(u, n, 0);
    390 				bsunion(v, u);
    391 			}
    392 		} else if (s1) {
    393 			/* avoid reloading temporaries
    394 			 * in the middle of loops */
    395 			bszero(v);
    396 			liveon(w, b, s1);
    397 			merge(v, b, w, s1);
    398 			if (s2) {
    399 				liveon(u, b, s2);
    400 				merge(v, b, u, s2);
    401 				bsinter(w, u);
    402 			}
    403 			limit2(v, 0, 0, w);
    404 		} else {
    405 			bscopy(v, b->out);
    406 			if (rtype(b->jmp.arg) == RCall)
    407 				v->t[0] |= T.retregs(b->jmp.arg, 0);
    408 		}
    409 		for (t=Tmp0; bsiter(b->out, &t); t++)
    410 			if (!bshas(v, t))
    411 				slot(t);
    412 		bscopy(b->out, v);
    413 
    414 		/* 2. process the block instructions */
    415 		curi = &insb[NIns];
    416 		for (i=&b->ins[b->nins]; i!=b->ins;) {
    417 			i--;
    418 			if (regcpy(i)) {
    419 				i = dopm(b, i, v);
    420 				continue;
    421 			}
    422 			bszero(w);
    423 			if (!req(i->to, R)) {
    424 				assert(rtype(i->to) == RTmp);
    425 				t = i->to.val;
    426 				if (bshas(v, t))
    427 					bsclr(v, t);
    428 				else {
    429 					/* make sure we have a reg
    430 					 * for the result */
    431 					assert(t >= Tmp0 && "dead reg");
    432 					bsset(v, t);
    433 					bsset(w, t);
    434 				}
    435 			}
    436 			j = T.memargs(i->op);
    437 			for (n=0; n<2; n++)
    438 				if (rtype(i->arg[n]) == RMem)
    439 					j--;
    440 			for (n=0; n<2; n++)
    441 				switch (rtype(i->arg[n])) {
    442 				case RMem:
    443 					t = i->arg[n].val;
    444 					m = &fn->mem[t];
    445 					if (rtype(m->base) == RTmp) {
    446 						bsset(v, m->base.val);
    447 						bsset(w, m->base.val);
    448 					}
    449 					if (rtype(m->index) == RTmp) {
    450 						bsset(v, m->index.val);
    451 						bsset(w, m->index.val);
    452 					}
    453 					break;
    454 				case RTmp:
    455 					t = i->arg[n].val;
    456 					lvarg[n] = bshas(v, t);
    457 					bsset(v, t);
    458 					if (j-- <= 0)
    459 						bsset(w, t);
    460 					break;
    461 				}
    462 			bscopy(u, v);
    463 			limit2(v, 0, 0, w);
    464 			for (n=0; n<2; n++)
    465 				if (rtype(i->arg[n]) == RTmp) {
    466 					t = i->arg[n].val;
    467 					if (!bshas(v, t)) {
    468 						/* do not reload if the
    469 						 * argument is dead
    470 						 */
    471 						if (!lvarg[n])
    472 							bsclr(u, t);
    473 						i->arg[n] = slot(t);
    474 					}
    475 				}
    476 			reloads(u, v);
    477 			if (!req(i->to, R)) {
    478 				t = i->to.val;
    479 				store(i->to, tmp[t].slot);
    480 				if (t >= Tmp0)
    481 					/* in case i->to was a
    482 					 * dead temporary */
    483 					bsclr(v, t);
    484 			}
    485 			emiti(*i);
    486 			r = v->t[0]; /* Tmp0 is NBit */
    487 			if (r)
    488 				sethint(v, r);
    489 		}
    490 		if (b == fn->start)
    491 			assert(v->t[0] == (T.rglob | fn->reg));
    492 		else
    493 			assert(v->t[0] == T.rglob);
    494 
    495 		for (p=b->phi; p; p=p->link) {
    496 			assert(rtype(p->to) == RTmp);
    497 			t = p->to.val;
    498 			if (bshas(v, t)) {
    499 				bsclr(v, t);
    500 				store(p->to, tmp[t].slot);
    501 			} else if (bshas(b->in, t))
    502 				/* only if the phi is live */
    503 				p->to = slot(p->to.val);
    504 		}
    505 		bscopy(b->in, v);
    506 		b->nins = &insb[NIns] - curi;
    507 		idup(&b->ins, curi, b->nins);
    508 	}
    509 
    510 	/* align the locals to a 16 byte boundary */
    511 	/* specific to NAlign == 3 */
    512 	slot8 += slot8 & 3;
    513 	fn->slot += slot8;
    514 
    515 	if (debug['S']) {
    516 		fprintf(stderr, "\n> Block information:\n");
    517 		for (b=fn->start; b; b=b->link) {
    518 			fprintf(stderr, "\t%-10s (% 5d) ", b->name, b->loop);
    519 			dumpts(b->out, fn->tmp, stderr);
    520 		}
    521 		fprintf(stderr, "\n> After spilling:\n");
    522 		printfn(fn, stderr);
    523 	}
    524 }