1 #include "c.h"
2 
3 
4 #define readsreg(p) \
5 	(generic((p)->op)==INDIR && (p)->kids[0]->op==VREG+P)
6 #define setsrc(d) ((d) && (d)->x.regnode && \
7 	(d)->x.regnode->set == src->x.regnode->set && \
8 	(d)->x.regnode->mask&src->x.regnode->mask)
9 
10 #define relink(a, b) ((b)->x.prev = (a), (a)->x.next = (b))
11 
12 static Symbol   askfixedreg(Symbol);
13 static Symbol   askreg(Symbol, unsigned*);
14 static void     blkunroll(int, int, int, int, int, int, int[]);
15 static void     docall(Node);
16 static void     dumpcover(Node, int, int);
17 static void     dumpregs(char *, char *, char *);
18 static void     dumprule(int);
19 static void     dumptree(Node);
20 static unsigned	emitasm(Node, int);
21 static void     genreload(Node, Symbol, int);
22 static void     genspill(Symbol, Node, Symbol);
23 static Symbol   getreg(Symbol, unsigned*, Node);
24 static int      getrule(Node, int);
25 static void     linearize(Node, Node);
26 static int      moveself(Node);
27 static void     prelabel(Node);
28 static Node*    prune(Node, Node*);
29 static void     putreg(Symbol);
30 static void     ralloc(Node);
31 static void     reduce(Node, int);
32 static int      reprune(Node*, int, int, Node);
33 static int      requate(Node);
34 static Node     reuse(Node, int);
35 static void     rewrite(Node);
36 static Symbol   spillee(Symbol, unsigned mask[], Node);
37 static void     spillr(Symbol, Node);
38 static int      uses(Node, Regnode);
39 
40 int offset;
41 
42 int maxoffset;
43 
44 int framesize;
45 int argoffset;
46 
47 int maxargoffset;
48 
49 int dalign, salign;
50 int bflag = 0;  /* omit */
51 int dflag = 0;
52 
53 int swap;
54 
55 unsigned (*emitter)(Node, int) = emitasm;
56 static char NeedsReg[] = {
57 	0,                      /* unused */
58 	1,                      /* CNST */
59 	0, 0,                   /* ARG ASGN */
60 	1,                      /* INDIR  */
61 	0, 0, 1, 1,             /*  -  - CVF CVI */
62 	1, 0, 1, 1,             /* CVP - CVU NEG */
63 	1,                      /* CALL */
64 	1,                      /* LOAD */
65 	0,                      /* RET */
66 	1, 1, 1,                /* ADDRG ADDRF ADDRL */
67 	1, 1, 1, 1, 1,          /* ADD SUB LSH MOD RSH */
68 	1, 1, 1, 1,             /* BAND BCOM BOR BXOR */
69 	1, 1,                   /* DIV MUL */
70 	0, 0, 0, 0, 0, 0,       /* EQ GE GT LE LT NE */
71 	0, 0                   /* JUMP LABEL   */
72 };
73 Node head;
74 
75 unsigned freemask[2];
76 unsigned usedmask[2];
77 unsigned tmask[2];
78 unsigned vmask[2];
mkreg(char * fmt,int n,int mask,int set)79 Symbol mkreg(char *fmt, int n, int mask, int set) {
80 	Symbol p;
81 
82 	NEW0(p, PERM);
83 	p->name = p->x.name = stringf(fmt, n);
84 	NEW0(p->x.regnode, PERM);
85 	p->x.regnode->number = n;
86 	p->x.regnode->mask = mask<<n;
87 	p->x.regnode->set = set;
88 	return p;
89 }
mkwildcard(Symbol * syms)90 Symbol mkwildcard(Symbol *syms) {
91 	Symbol p;
92 
93 	NEW0(p, PERM);
94 	p->name = p->x.name = "wildcard";
95 	p->x.wildcard = syms;
96 	return p;
97 }
mkauto(Symbol p)98 void mkauto(Symbol p) {
99 	assert(p->sclass == AUTO);
100 	offset = roundup(offset + p->type->size, p->type->align);
101 	p->x.offset = -offset;
102 	p->x.name = stringd(-offset);
103 }
blockbeg(Env * e)104 void blockbeg(Env *e) {
105 	e->offset = offset;
106 	e->freemask[IREG] = freemask[IREG];
107 	e->freemask[FREG] = freemask[FREG];
108 }
blockend(Env * e)109 void blockend(Env *e) {
110 	if (offset > maxoffset)
111 		maxoffset = offset;
112 	offset = e->offset;
113 	freemask[IREG] = e->freemask[IREG];
114 	freemask[FREG] = e->freemask[FREG];
115 }
mkactual(int align,int size)116 int mkactual(int align, int size) {
117 	int n = roundup(argoffset, align);
118 
119 	argoffset = n + size;
120 	return n;
121 }
docall(Node p)122 static void docall(Node p) {
123 	p->syms[1] = p->syms[0];
124 	p->syms[0] = intconst(argoffset);
125 	if (argoffset > maxargoffset)
126 		maxargoffset = argoffset;
127 	argoffset = 0;
128 }
blkcopy(int dreg,int doff,int sreg,int soff,int size,int tmp[])129 void blkcopy(int dreg, int doff, int sreg, int soff, int size, int tmp[]) {
130 	assert(size >= 0);
131 	if (size == 0)
132 		return;
133 	else if (size <= 2)
134 		blkunroll(size, dreg, doff, sreg, soff, size, tmp);
135 	else if (size == 3) {
136 		blkunroll(2, dreg, doff,   sreg, soff,   2, tmp);
137 		blkunroll(1, dreg, doff+2, sreg, soff+2, 1, tmp);
138 	}
139 	else if (size <= 16) {
140 		blkunroll(4, dreg, doff, sreg, soff, size&~3, tmp);
141 		blkcopy(dreg, doff+(size&~3),
142 	                sreg, soff+(size&~3), size&3, tmp);
143 	}
144 	else
145 		(*IR->x.blkloop)(dreg, doff, sreg, soff, size, tmp);
146 }
blkunroll(int k,int dreg,int doff,int sreg,int soff,int size,int tmp[])147 static void blkunroll(int k, int dreg, int doff, int sreg, int soff, int size, int tmp[]) {
148 	int i;
149 
150 	assert(IR->x.max_unaligned_load);
151 	if (k > IR->x.max_unaligned_load
152 	&& (k > salign || k > dalign))
153 		k = IR->x.max_unaligned_load;
154 	for (i = 0; i+k < size; i += 2*k) {
155 		(*IR->x.blkfetch)(k, soff+i,   sreg, tmp[0]);
156 		(*IR->x.blkfetch)(k, soff+i+k, sreg, tmp[1]);
157 		(*IR->x.blkstore)(k, doff+i,   dreg, tmp[0]);
158 		(*IR->x.blkstore)(k, doff+i+k, dreg, tmp[1]);
159 	}
160 	if (i < size) {
161 		(*IR->x.blkfetch)(k, i+soff, sreg, tmp[0]);
162 		(*IR->x.blkstore)(k, i+doff, dreg, tmp[0]);
163 	}
164 }
parseflags(int argc,char * argv[])165 void parseflags(int argc, char *argv[]) {
166 	int i;
167 
168 	for (i = 0; i < argc; i++)
169 		if (strcmp(argv[i], "-d") == 0)
170 			dflag = 1;
171 		else if (strcmp(argv[i], "-b") == 0)	/* omit */
172 			bflag = 1;			/* omit */
173 }
getrule(Node p,int nt)174 static int getrule(Node p, int nt) {
175 	int rulenum;
176 
177 	assert(p);
178 	rulenum = (*IR->x._rule)(p->x.state, nt);
179 	if (!rulenum) {
180 		fprint(stderr, "(%x->op=%s at %w is corrupt.)\n", p, opname(p->op), &src);
181 		assert(0);
182 	}
183 	return rulenum;
184 }
reduce(Node p,int nt)185 static void reduce(Node p, int nt) {
186 	int rulenum, i;
187 	short *nts;
188 	Node kids[10];
189 
190 	p = reuse(p, nt);
191 	rulenum = getrule(p, nt);
192 	nts = IR->x._nts[rulenum];
193 	(*IR->x._kids)(p, rulenum, kids);
194 	for (i = 0; nts[i]; i++)
195 		reduce(kids[i], nts[i]);
196 	if (IR->x._isinstruction[rulenum]) {
197 		assert(p->x.inst == 0 || p->x.inst == nt);
198 		p->x.inst = nt;
199 		if (p->syms[RX] && p->syms[RX]->temporary) {
200 			debug(fprint(stderr, "(using %s)\n", p->syms[RX]->name));
201 			p->syms[RX]->x.usecount++;
202 		}
203 	}
204 }
reuse(Node p,int nt)205 static Node reuse(Node p, int nt) {
206 	struct _state {
207 		short cost[1];
208 	};
209 	Symbol r = p->syms[RX];
210 
211 	if (generic(p->op) == INDIR && p->kids[0]->op == VREG+P
212 	&& r->u.t.cse && p->x.mayrecalc
213 	&& ((struct _state*)r->u.t.cse->x.state)->cost[nt] == 0)
214 		return r->u.t.cse;
215 	else
216 		return p;
217 }
218 
mayrecalc(Node p)219 int mayrecalc(Node p) {
220 	int op;
221 
222 	assert(p && p->syms[RX]);
223 	if (p->syms[RX]->u.t.cse == NULL)
224 		return 0;
225 	op = generic(p->syms[RX]->u.t.cse->op);
226 	if (op == CNST || op == ADDRF || op == ADDRG || op == ADDRL) {
227 		p->x.mayrecalc = 1;
228 		return 1;
229 	} else
230 		return 0;
231 }
prune(Node p,Node pp[])232 static Node *prune(Node p, Node pp[]) {
233 	if (p == NULL)
234 		return pp;
235 	p->x.kids[0] = p->x.kids[1] = p->x.kids[2] = NULL;
236 	if (p->x.inst == 0)
237 		return prune(p->kids[1], prune(p->kids[0], pp));
238 	else if (p->syms[RX] && p->syms[RX]->temporary
239 	&& p->syms[RX]->x.usecount < 2) {
240 		p->x.inst = 0;
241 		debug(fprint(stderr, "(clobbering %s)\n", p->syms[RX]->name));
242 		return prune(p->kids[1], prune(p->kids[0], pp));
243 	}
244 	else {
245 		prune(p->kids[1], prune(p->kids[0], &p->x.kids[0]));
246 		*pp = p;
247 		return pp + 1;
248 	}
249 }
250 
251 #define ck(i) return (i) ? 0 : LBURG_MAX
252 
range(Node p,int lo,int hi)253 int range(Node p, int lo, int hi) {
254 	Symbol s = p->syms[0];
255 
256 	switch (specific(p->op)) {
257 	case ADDRF+P:
258 	case ADDRL+P: ck(s->x.offset >= lo && s->x.offset <= hi);
259 	case CNST+I:  ck(s->u.c.v.i  >= lo && s->u.c.v.i  <= hi);
260 	case CNST+U:  ck(s->u.c.v.u  >= lo && s->u.c.v.u  <= hi);
261 	case CNST+P:  ck(s->u.c.v.p  == 0  && lo <= 0 && hi >= 0);
262 	}
263 	return LBURG_MAX;
264 }
dumptree(Node p)265 static void dumptree(Node p) {
266 	if (p->op == VREG+P && p->syms[0]) {
267 		fprint(stderr, "VREGP(%s)", p->syms[0]->name);
268 		return;
269 	} else if (generic(p->op) == LOAD) {
270 		fprint(stderr, "LOAD(");
271 		dumptree(p->kids[0]);
272 		fprint(stderr, ")");
273 		return;
274 	}
275 	fprint(stderr, "%s(", opname(p->op));
276 	switch (generic(p->op)) {
277 	case CNST: case LABEL:
278 	case ADDRG: case ADDRF: case ADDRL:
279 		if (p->syms[0])
280 			fprint(stderr, "%s", p->syms[0]->name);
281 		break;
282 	case RET:
283 		if (p->kids[0])
284 			dumptree(p->kids[0]);
285 		break;
286 	case CVF: case CVI: case CVP: case CVU: case JUMP:
287 	case ARG: case BCOM: case NEG: case INDIR:
288 		dumptree(p->kids[0]);
289 		break;
290 	case CALL:
291 		if (optype(p->op) != B) {
292 			dumptree(p->kids[0]);
293 			break;
294 		}
295 		/* else fall thru */
296 	case EQ: case NE: case GT: case GE: case LE: case LT:
297 	case ASGN: case BOR: case BAND: case BXOR: case RSH: case LSH:
298 	case ADD: case SUB:  case DIV: case MUL: case MOD:
299 		dumptree(p->kids[0]);
300 		fprint(stderr, ", ");
301 		dumptree(p->kids[1]);
302 		break;
303 	default: assert(0);
304 	}
305 	fprint(stderr, ")");
306 }
dumpcover(Node p,int nt,int in)307 static void dumpcover(Node p, int nt, int in) {
308 	int rulenum, i;
309 	short *nts;
310 	Node kids[10];
311 
312 	p = reuse(p, nt);
313 	rulenum = getrule(p, nt);
314 	nts = IR->x._nts[rulenum];
315 	fprint(stderr, "dumpcover(%x) = ", p);
316 	for (i = 0; i < in; i++)
317 		fprint(stderr, " ");
318 	dumprule(rulenum);
319 	(*IR->x._kids)(p, rulenum, kids);
320 	for (i = 0; nts[i]; i++)
321 		dumpcover(kids[i], nts[i], in+1);
322 }
323 
dumprule(int rulenum)324 static void dumprule(int rulenum) {
325 	assert(rulenum);
326 	fprint(stderr, "%s / %s", IR->x._string[rulenum],
327 		IR->x._templates[rulenum]);
328 	if (!IR->x._isinstruction[rulenum])
329 		fprint(stderr, "\n");
330 }
emitasm(Node p,int nt)331 static unsigned emitasm(Node p, int nt) {
332 	int rulenum;
333 	short *nts;
334 	char *fmt;
335 	Node kids[10];
336 
337 	p = reuse(p, nt);
338 	rulenum = getrule(p, nt);
339 	nts = IR->x._nts[rulenum];
340 	fmt = IR->x._templates[rulenum];
341 	assert(fmt);
342 	if (IR->x._isinstruction[rulenum] && p->x.emitted)
343 		print("%s", p->syms[RX]->x.name);
344 	else if (*fmt == '#')
345 		(*IR->x.emit2)(p);
346 	else {
347 		if (*fmt == '?') {
348 			fmt++;
349 			assert(p->kids[0]);
350 			if (p->syms[RX] == p->x.kids[0]->syms[RX])
351 				while (*fmt++ != '\n')
352 					;
353 		}
354 		for ((*IR->x._kids)(p, rulenum, kids); *fmt; fmt++)
355 			if (*fmt != '%')
356 				(void)putchar(*fmt);
357 			else if (*++fmt == 'F')
358 				print("%d", framesize);
359 			else if (*fmt >= '0' && *fmt <= '9')
360 				emitasm(kids[*fmt - '0'], nts[*fmt - '0']);
361 			else if (*fmt >= 'a' && *fmt < 'a' + NELEMS(p->syms))
362 				fputs(p->syms[*fmt - 'a']->x.name, stdout);
363 			else
364 				(void)putchar(*fmt);
365 	}
366 	return 0;
367 }
emit(Node p)368 void emit(Node p) {
369 	for (; p; p = p->x.next) {
370 		assert(p->x.registered);
371 		if ((p->x.equatable && requate(p)) || moveself(p))
372 			;
373 		else
374 			(*emitter)(p, p->x.inst);
375 		p->x.emitted = 1;
376 	}
377 }
moveself(Node p)378 static int moveself(Node p) {
379 	return p->x.copy
380 	&& p->syms[RX]->x.name == p->x.kids[0]->syms[RX]->x.name;
381 }
move(Node p)382 int move(Node p) {
383 	p->x.copy = 1;
384 	return 1;
385 }
requate(Node q)386 static int requate(Node q) {
387 	Symbol src = q->x.kids[0]->syms[RX];
388 	Symbol tmp = q->syms[RX];
389 	Node p;
390 	int n = 0;
391 
392 	debug(fprint(stderr, "(requate(%x): tmp=%s src=%s)\n", q, tmp->x.name, src->x.name));
393 	for (p = q->x.next; p; p = p->x.next)
394 		if (p->x.copy && p->syms[RX] == src
395 		&&  p->x.kids[0]->syms[RX] == tmp)
396 			debug(fprint(stderr, "(requate arm 0 at %x)\n", p)),
397 			p->syms[RX] = tmp;
398 		else if (setsrc(p->syms[RX]) && !moveself(p) && !readsreg(p))
399 			return 0;
400 		else if (p->x.spills)
401 			return 0;
402 		else if (generic(p->op) == CALL && p->x.next)
403 			return 0;
404 		else if (p->op == LABEL+V && p->x.next)
405 			return 0;
406 		else if (p->syms[RX] == tmp && readsreg(p))
407 			debug(fprint(stderr, "(requate arm 5 at %x)\n", p)),
408 			n++;
409 		else if (p->syms[RX] == tmp)
410 			break;
411 	debug(fprint(stderr, "(requate arm 7 at %x)\n", p));
412 	assert(n > 0);
413 	for (p = q->x.next; p; p = p->x.next)
414 		if (p->syms[RX] == tmp && readsreg(p)) {
415 			p->syms[RX] = src;
416 			if (--n <= 0)
417 				break;
418 		}
419 	return 1;
420 }
prelabel(Node p)421 static void prelabel(Node p) {
422 	if (p == NULL)
423 		return;
424 	prelabel(p->kids[0]);
425 	prelabel(p->kids[1]);
426 	if (NeedsReg[opindex(p->op)])
427 		setreg(p, (*IR->x.rmap)(opkind(p->op)));
428 	switch (generic(p->op)) {
429 	case ADDRF: case ADDRL:
430 		if (p->syms[0]->sclass == REGISTER)
431 			p->op = VREG+P;
432 		break;
433 	case INDIR:
434 		if (p->kids[0]->op == VREG+P)
435 			setreg(p, p->kids[0]->syms[0]);
436 		break;
437 	case ASGN:
438 		if (p->kids[0]->op == VREG+P)
439 			rtarget(p, 1, p->kids[0]->syms[0]);
440 		break;
441 	case CVI: case CVU: case CVP:
442 		if (optype(p->op) != F
443 		&&  opsize(p->op) <= p->syms[0]->u.c.v.i)
444 			p->op = LOAD + opkind(p->op);
445 		break;
446 	}
447 	(IR->x.target)(p);
448 }
setreg(Node p,Symbol r)449 void setreg(Node p, Symbol r) {
450 	p->syms[RX] = r;
451 }
rtarget(Node p,int n,Symbol r)452 void rtarget(Node p, int n, Symbol r) {
453 	Node q = p->kids[n];
454 
455 	assert(q);
456 	assert(r);
457 	assert(r->sclass == REGISTER || !r->x.wildcard);
458 	assert(q->syms[RX]);
459 	if (r != q->syms[RX] && !q->syms[RX]->x.wildcard) {
460 		q = newnode(LOAD + opkind(q->op),
461 			q, NULL, q->syms[0]);
462 		if (r->u.t.cse == p->kids[n])
463 			r->u.t.cse = q;
464 		p->kids[n] = p->x.kids[n] = q;
465 		q->x.kids[0] = q->kids[0];
466 	}
467 	setreg(q, r);
468 	debug(fprint(stderr, "(targeting %x->x.kids[%d]=%x to %s)\n", p, n, p->kids[n], r->x.name));
469 }
rewrite(Node p)470 static void rewrite(Node p) {
471 	assert(p->x.inst == 0);
472 	prelabel(p);
473 	debug(dumptree(p));
474 	debug(fprint(stderr, "\n"));
475 	(*IR->x._label)(p);
476 	debug(dumpcover(p, 1, 0));
477 	reduce(p, 1);
478 }
gen(Node forest)479 Node gen(Node forest) {
480 	int i;
481 	struct node sentinel;
482 	Node dummy, p;
483 
484 	head = forest;
485 	for (p = forest; p; p = p->link) {
486 		assert(p->count == 0);
487 		if (generic(p->op) == CALL)
488 			docall(p);
489 		else if (   generic(p->op) == ASGN
490 		&& generic(p->kids[1]->op) == CALL)
491 			docall(p->kids[1]);
492 		else if (generic(p->op) == ARG)
493 			(*IR->x.doarg)(p);
494 		rewrite(p);
495 		p->x.listed = 1;
496 	}
497 	for (p = forest; p; p = p->link)
498 		prune(p, &dummy);
499 	relink(&sentinel, &sentinel);
500 	for (p = forest; p; p = p->link)
501 		linearize(p, &sentinel);
502 	forest = sentinel.x.next;
503 	assert(forest);
504 	sentinel.x.next->x.prev = NULL;
505 	sentinel.x.prev->x.next = NULL;
506 	for (p = forest; p; p = p->x.next)
507 		for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
508 			assert(p->x.kids[i]->syms[RX]);
509 			if (p->x.kids[i]->syms[RX]->temporary) {
510 				p->x.kids[i]->x.prevuse =
511 					p->x.kids[i]->syms[RX]->x.lastuse;
512 				p->x.kids[i]->syms[RX]->x.lastuse = p->x.kids[i];
513 			}
514 		}
515 	for (p = forest; p; p = p->x.next) {
516 		ralloc(p);
517 		if (p->x.listed && NeedsReg[opindex(p->op)]
518 		&& (*IR->x.rmap)(opkind(p->op))) {
519 			assert(generic(p->op) == CALL || generic(p->op) == LOAD);
520 			putreg(p->syms[RX]);
521 		}
522 	}
523 	return forest;
524 }
notarget(Node p)525 int notarget(Node p) {
526 	return p->syms[RX]->x.wildcard ? 0 : LBURG_MAX;
527 }
putreg(Symbol r)528 static void putreg(Symbol r) {
529 	assert(r && r->x.regnode);
530 	freemask[r->x.regnode->set] |= r->x.regnode->mask;
531 	debug(dumpregs("(freeing %s)\n", r->x.name, NULL));
532 }
askfixedreg(Symbol s)533 static Symbol askfixedreg(Symbol s) {
534 	Regnode r = s->x.regnode;
535 	int n = r->set;
536 
537 	if (r->mask&~freemask[n])
538 		return NULL;
539 	else {
540 		freemask[n] &= ~r->mask;
541 		usedmask[n] |=  r->mask;
542 		return s;
543 	}
544 }
askreg(Symbol rs,unsigned rmask[])545 static Symbol askreg(Symbol rs, unsigned rmask[]) {
546 	int i;
547 
548 	if (rs->x.wildcard == NULL)
549 		return askfixedreg(rs);
550 	for (i = 31; i >= 0; i--) {
551 		Symbol r = rs->x.wildcard[i];
552 		if (r != NULL
553 		&& !(r->x.regnode->mask&~rmask[r->x.regnode->set])
554 		&& askfixedreg(r))
555 			return r;
556 	}
557 	return NULL;
558 }
559 
getreg(Symbol s,unsigned mask[],Node p)560 static Symbol getreg(Symbol s, unsigned mask[], Node p) {
561 	Symbol r = askreg(s, mask);
562 	if (r == NULL) {
563 		r = spillee(s, mask, p);
564 		assert(r && r->x.regnode);
565 		spill(r->x.regnode->mask, r->x.regnode->set, p);
566 		r = askreg(s, mask);
567 	}
568 	assert(r && r->x.regnode);
569 	r->x.regnode->vbl = NULL;
570 	return r;
571 }
askregvar(Symbol p,Symbol regs)572 int askregvar(Symbol p, Symbol regs) {
573 	Symbol r;
574 
575 	assert(p);
576 	if (p->sclass != REGISTER)
577 		return 0;
578 	else if (!isscalar(p->type)) {
579 		p->sclass = AUTO;
580 		return 0;
581 	}
582 	else if (p->temporary) {
583 		p->x.name = "?";
584 		return 1;
585 	}
586 	else if ((r = askreg(regs, vmask)) != NULL) {
587 		p->x.regnode = r->x.regnode;
588 		p->x.regnode->vbl = p;
589 		p->x.name = r->x.name;
590 		debug(dumpregs("(allocating %s to symbol %s)\n", p->x.name, p->name));
591 		return 1;
592 	}
593 	else {
594 		p->sclass = AUTO;
595 		return 0;
596 	}
597 }
linearize(Node p,Node next)598 static void linearize(Node p, Node next) {
599 	int i;
600 
601 	for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++)
602 		linearize(p->x.kids[i], next);
603 	relink(next->x.prev, p);
604 	relink(p, next);
605 	debug(fprint(stderr, "(listing %x)\n", p));
606 }
ralloc(Node p)607 static void ralloc(Node p) {
608 	int i;
609 	unsigned mask[2];
610 
611 	mask[0] = tmask[0];
612 	mask[1] = tmask[1];
613 	assert(p);
614 	debug(fprint(stderr, "(rallocing %x)\n", p));
615 	for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
616 		Node kid = p->x.kids[i];
617 		Symbol r = kid->syms[RX];
618 		assert(r && kid->x.registered);
619 		if (r->sclass != REGISTER && r->x.lastuse == kid)
620 			putreg(r);
621 	}
622 	if (!p->x.registered && NeedsReg[opindex(p->op)]
623 	&& (*IR->x.rmap)(opkind(p->op))) {
624 		Symbol sym = p->syms[RX], set = sym;
625 		assert(sym);
626 		if (sym->temporary)
627 			set = (*IR->x.rmap)(opkind(p->op));
628 		assert(set);
629 		if (set->sclass != REGISTER) {
630 			Symbol r;
631 			if (*IR->x._templates[getrule(p, p->x.inst)] == '?')
632 				for (i = 1; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
633 					Symbol r = p->x.kids[i]->syms[RX];
634 					assert(p->x.kids[i]->x.registered);
635 					assert(r && r->x.regnode);
636 					assert(sym->x.wildcard || sym != r);
637 					mask[r->x.regnode->set] &= ~r->x.regnode->mask;
638 				}
639 			r = getreg(set, mask, p);
640 			if (sym->temporary) {
641 				Node q;
642 				r->x.lastuse = sym->x.lastuse;
643 				for (q = sym->x.lastuse; q; q = q->x.prevuse) {
644 					q->syms[RX] = r;
645 					q->x.registered = 1;
646 					if (sym->u.t.cse && q->x.copy)
647 						q->x.equatable = 1;
648 				}
649 			} else {
650 				p->syms[RX] = r;
651 				r->x.lastuse = p;
652 			}
653 			debug(dumpregs("(allocating %s to node %x)\n", r->x.name, (char *) p));
654 		}
655 	}
656 	p->x.registered = 1;
657 	(*IR->x.clobber)(p);
658 }
spillee(Symbol set,unsigned mask[],Node here)659 static Symbol spillee(Symbol set, unsigned mask[], Node here) {
660 	Symbol bestreg = NULL;
661 	int bestdist = -1, i;
662 
663 	assert(set);
664 	if (!set->x.wildcard)
665 		bestreg = set;
666 	else {
667 		for (i = 31; i >= 0; i--) {
668 			Symbol ri = set->x.wildcard[i];
669 			if (
670 				ri != NULL &&
671 				ri->x.lastuse &&
672 				(ri->x.regnode->mask&tmask[ri->x.regnode->set]&mask[ri->x.regnode->set])
673 			) {
674 				Regnode rn = ri->x.regnode;
675 				Node q = here;
676 				int dist = 0;
677 				for (; q && !uses(q, rn); q = q->x.next)
678 					dist++;
679 				if (q && dist > bestdist) {
680 					bestdist = dist;
681 					bestreg = ri;
682 				}
683 			}
684 		}
685 	}
686 	assert(bestreg); /* Must be able to spill something. Reconfigure the register allocator
687 		to ensure that we can allocate a register for all nodes without spilling
688 		the node's necessary input regs. */
689 	assert(bestreg->x.regnode->vbl == NULL); /* Can't spill register variables because
690 		the reload site might be in other blocks. Reconfigure the register allocator
691 		to ensure that this register is never allocated to a variable. */
692 	return bestreg;
693 }
uses(Node p,Regnode rn)694 static int uses(Node p, Regnode rn) {
695 	int i;
696 
697 	for (i = 0; i < NELEMS(p->x.kids); i++)
698 		if (
699 			p->x.kids[i] &&
700 			p->x.kids[i]->x.registered &&
701 			rn->set == p->x.kids[i]->syms[RX]->x.regnode->set &&
702 			(rn->mask&p->x.kids[i]->syms[RX]->x.regnode->mask)
703 		)
704 			return 1;
705 	return 0;
706 }
spillr(Symbol r,Node here)707 static void spillr(Symbol r, Node here) {
708 	int i;
709 	Symbol tmp;
710 	Node p = r->x.lastuse;
711 	assert(p);
712 	while (p->x.prevuse)
713 		assert(r == p->syms[RX]),
714 		p = p->x.prevuse;
715 	assert(p->x.registered && !readsreg(p));
716 	tmp = newtemp(AUTO, optype(p->op), opsize(p->op));
717 	genspill(r, p, tmp);
718 	for (p = here->x.next; p; p = p->x.next)
719 		for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
720 			Node k = p->x.kids[i];
721 			if (k->x.registered && k->syms[RX] == r)
722 				genreload(p, tmp, i);
723 		}
724 	putreg(r);
725 }
genspill(Symbol r,Node last,Symbol tmp)726 static void genspill(Symbol r, Node last, Symbol tmp) {
727 	Node p, q;
728 	Symbol s;
729 	unsigned ty;
730 
731 	debug(fprint(stderr, "(spilling %s to local %s)\n", r->x.name, tmp->x.name));
732 	debug(fprint(stderr, "(genspill: "));
733 	debug(dumptree(last));
734 	debug(fprint(stderr, ")\n"));
735 	ty = opkind(last->op);
736 	NEW0(s, FUNC);
737 	s->sclass = REGISTER;
738 	s->name = s->x.name = r->x.name;
739 	s->x.regnode = r->x.regnode;
740 	q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, s);
741 	q = newnode(INDIR + ty, q, NULL, NULL);
742 	p = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp);
743 	p = newnode(ASGN + ty, p, q, NULL);
744 	p->x.spills = 1;
745 	rewrite(p);
746 	prune(p, &q);
747 	q = last->x.next;
748 	linearize(p, q);
749 	for (p = last->x.next; p != q; p = p->x.next) {
750 		ralloc(p);
751 		assert(!p->x.listed || !NeedsReg[opindex(p->op)] || !(*IR->x.rmap)(opkind(p->op)));
752 	}
753 }
754 
genreload(Node p,Symbol tmp,int i)755 static void genreload(Node p, Symbol tmp, int i) {
756 	Node q;
757 	int ty;
758 
759 	debug(fprint(stderr, "(replacing %x with a reload from %s)\n", p->x.kids[i], tmp->x.name));
760 	debug(fprint(stderr, "(genreload: "));
761 	debug(dumptree(p->x.kids[i]));
762 	debug(fprint(stderr, ")\n"));
763 	ty = opkind(p->x.kids[i]->op);
764 	q = newnode(ADDRL+P + sizeop(IR->ptrmetric.size), NULL, NULL, tmp);
765 	p->x.kids[i] = newnode(INDIR + ty, q, NULL, NULL);
766 	rewrite(p->x.kids[i]);
767 	prune(p->x.kids[i], &q);
768 	reprune(&p->kids[1], reprune(&p->kids[0], 0, i, p), i, p);
769 	prune(p, &q);
770 	linearize(p->x.kids[i], p);
771 }
reprune(Node * pp,int k,int n,Node p)772 static int reprune(Node *pp, int k, int n, Node p) {
773 	struct node x, *q = *pp;
774 
775 	if (q == NULL || k > n)
776 		return k;
777 	else if (q->x.inst == 0)
778 		return reprune(&q->kids[1],
779 			reprune(&q->kids[0], k, n, p), n, p);
780 	if (k == n) {
781 		debug(fprint(stderr, "(reprune changes %x from %x to %x)\n", pp, *pp, p->x.kids[n]));
782 		*pp = p->x.kids[n];
783 		x = *p;
784 		(IR->x.target)(&x);
785 	}
786 	return k + 1;
787 }
spill(unsigned mask,int n,Node here)788 void spill(unsigned mask, int n, Node here) {
789 	int i;
790 	Node p;
791 
792 	here->x.spills = 1;
793 	usedmask[n] |= mask;
794 	if (mask&~freemask[n]) {
795 
796 		assert( /* It makes no sense for a node to clobber() its target. */
797 			here->x.registered == 0 || /* call isn't coming through clobber() */
798 			here->syms[RX] == NULL ||
799 			here->syms[RX]->x.regnode == NULL ||
800 			here->syms[RX]->x.regnode->set != n ||
801 			(here->syms[RX]->x.regnode->mask&mask) == 0
802 		);
803 
804 		for (p = here; p; p = p->x.next)
805 			for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
806 				Symbol r = p->x.kids[i]->syms[RX];
807 				assert(r);
808 				if (p->x.kids[i]->x.registered && r->x.regnode->set == n
809 				&& r->x.regnode->mask&mask)
810 					spillr(r, here);
811 			}
812 	}
813 }
dumpregs(char * msg,char * a,char * b)814 static void dumpregs(char *msg, char *a, char *b) {
815 	fprint(stderr, msg, a, b);
816 	fprint(stderr, "(free[0]=%x)\n", freemask[0]);
817 	fprint(stderr, "(free[1]=%x)\n", freemask[1]);
818 }
819 
getregnum(Node p)820 int getregnum(Node p) {
821 	assert(p && p->syms[RX] && p->syms[RX]->x.regnode);
822 	return p->syms[RX]->x.regnode->number;
823 }
824 
825 
regloc(Symbol p)826 unsigned regloc(Symbol p) {
827 	assert(p && p->sclass == REGISTER && p->sclass == REGISTER && p->x.regnode);
828 	return p->x.regnode->set<<8 | p->x.regnode->number;
829 }
830 
831