← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openarena/hardy-backports

« back to all changes in this revision

Viewing changes to code/tools/lcc/src/gen.c

  • Committer: Bazaar Package Importer
  • Author(s): Bruno "Fuddl" Kleinert
  • Date: 2007-01-20 12:28:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070120122809-2yza5ojt7nqiyiam
Tags: upstream-0.6.0
Import upstream version 0.6.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
code/tools/lcc/src/gen.c
 
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