?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
* added compilers lcc and bcc (linux86)
[mascara-docs.git] / compilers / lcc / src / gen.c
blob4ee170d913f6ff54494b4189f5598b5bd892be6f
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];
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 }
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 }
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 }
104 void blockbeg(Env *e) {
105 e->offset = offset;
106 e->freemask[IREG] = freemask[IREG];
107 e->freemask[FREG] = freemask[FREG];
108 }
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 }
116 int mkactual(int align, int size) {
117 int n = roundup(argoffset, align);
118
119 argoffset = n + size;
120 return n;
121 }
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 }
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 }
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 }
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 }
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 }
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 }
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
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 }
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
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 }
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 }
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
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 }
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 }
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 }
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 }
382 int move(Node p) {
383 p->x.copy = 1;
384 return 1;
385 }
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 }
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 }
449 void setreg(Node p, Symbol r) {
450 p->syms[RX] = r;
451 }
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 }
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 }
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 }
525 int notarget(Node p) {
526 return p->syms[RX]->x.wildcard ? 0 : LBURG_MAX;
527 }
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 }
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 }
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
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 }
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 }
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 }
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 }
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 }
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 }
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 }
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
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 }
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 }
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 }
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
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
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