summaryrefslogtreecommitdiff
path: root/6/ra.c
diff options
context:
space:
mode:
Diffstat (limited to '6/ra.c')
-rw-r--r--6/ra.c2183
1 files changed, 1091 insertions, 1092 deletions
diff --git a/6/ra.c b/6/ra.c
index 7e8fe83..5c7452b 100644
--- a/6/ra.c
+++ b/6/ra.c
@@ -15,8 +15,8 @@
typedef struct Usemap Usemap;
struct Usemap {
- int l[Nreg + 1]; /* location of arg used in instruction's arg list */
- int r[Nreg + 1]; /* list of registers used implicitly by instruction */
+ int l[Nreg + 1]; /* location of arg used in instruction's arg list */
+ int r[Nreg + 1]; /* list of registers used implicitly by instruction */
};
void wlprint(FILE *fd, char *name, Loc **wl, size_t nwl);
@@ -47,297 +47,296 @@ Usemap deftab[] = {
/* A map of which registers interfere */
#define Northogonal 32
Reg regmap[Northogonal][Nmode] = {
- /* None, ModeB, ModeW, ModeL, ModeQ, ModeF, ModeD */
- [0] = {Rnone, Ral, Rax, Reax, Rrax, Rnone, Rnone},
- [1] = {Rnone, Rcl, Rcx, Recx, Rrcx, Rnone, Rnone},
- [2] = {Rnone, Rdl, Rdx, Redx, Rrdx, Rnone, Rnone},
- [3] = {Rnone, Rbl, Rbx, Rebx, Rrbx, Rnone, Rnone},
- [4] = {Rnone, Rsil, Rsi, Resi, Rrsi, Rnone, Rnone},
- [5] = {Rnone, Rdil, Rdi, Redi, Rrdi, Rnone, Rnone},
- [6] = {Rnone, Rr8b, Rr8w, Rr8d, Rr8, Rnone, Rnone},
- [7] = {Rnone, Rr9b, Rr9w, Rr9d, Rr9, Rnone, Rnone},
- [8] = {Rnone, Rr10b, Rr10w, Rr10d, Rr10, Rnone, Rnone},
- [9] = {Rnone, Rr11b, Rr11w, Rr11d, Rr11, Rnone, Rnone},
- [10] = {Rnone, Rr12b, Rr12w, Rr12d, Rr12, Rnone, Rnone},
- [11] = {Rnone, Rr13b, Rr13w, Rr13d, Rr13, Rnone, Rnone},
- [12] = {Rnone, Rr14b, Rr14w, Rr14d, Rr14, Rnone, Rnone},
- [13] = {Rnone, Rr15b, Rr15w, Rr15d, Rr15, Rnone, Rnone},
- [14] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rnone, Rnone},
- [15] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rnone, Rnone},
- [16] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm0f, Rxmm0d},
- [17] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm1f, Rxmm1d},
- [18] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm2f, Rxmm2d},
- [19] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm3f, Rxmm3d},
- [20] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm4f, Rxmm4d},
- [21] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm5f, Rxmm5d},
- [22] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm6f, Rxmm6d},
- [23] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm7f, Rxmm7d},
- [24] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm8f, Rxmm8d},
- [25] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm9f, Rxmm9d},
- [26] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm10f, Rxmm10d},
- [27] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm11f, Rxmm11d},
- [28] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm12f, Rxmm12d},
- [29] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm13f, Rxmm13d},
- [30] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm14f, Rxmm14d},
- [31] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm15f, Rxmm15d},
+ /* None, ModeB, ModeW, ModeL, ModeQ, ModeF, ModeD */
+ [0] = {Rnone, Ral, Rax, Reax, Rrax, Rnone, Rnone},
+ [1] = {Rnone, Rcl, Rcx, Recx, Rrcx, Rnone, Rnone},
+ [2] = {Rnone, Rdl, Rdx, Redx, Rrdx, Rnone, Rnone},
+ [3] = {Rnone, Rbl, Rbx, Rebx, Rrbx, Rnone, Rnone},
+ [4] = {Rnone, Rsil, Rsi, Resi, Rrsi, Rnone, Rnone},
+ [5] = {Rnone, Rdil, Rdi, Redi, Rrdi, Rnone, Rnone},
+ [6] = {Rnone, Rr8b, Rr8w, Rr8d, Rr8, Rnone, Rnone},
+ [7] = {Rnone, Rr9b, Rr9w, Rr9d, Rr9, Rnone, Rnone},
+ [8] = {Rnone, Rr10b, Rr10w, Rr10d, Rr10, Rnone, Rnone},
+ [9] = {Rnone, Rr11b, Rr11w, Rr11d, Rr11, Rnone, Rnone},
+ [10] = {Rnone, Rr12b, Rr12w, Rr12d, Rr12, Rnone, Rnone},
+ [11] = {Rnone, Rr13b, Rr13w, Rr13d, Rr13, Rnone, Rnone},
+ [12] = {Rnone, Rr14b, Rr14w, Rr14d, Rr14, Rnone, Rnone},
+ [13] = {Rnone, Rr15b, Rr15w, Rr15d, Rr15, Rnone, Rnone},
+ [14] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rnone, Rnone},
+ [15] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rnone, Rnone},
+ [16] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm0f, Rxmm0d},
+ [17] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm1f, Rxmm1d},
+ [18] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm2f, Rxmm2d},
+ [19] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm3f, Rxmm3d},
+ [20] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm4f, Rxmm4d},
+ [21] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm5f, Rxmm5d},
+ [22] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm6f, Rxmm6d},
+ [23] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm7f, Rxmm7d},
+ [24] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm8f, Rxmm8d},
+ [25] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm9f, Rxmm9d},
+ [26] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm10f, Rxmm10d},
+ [27] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm11f, Rxmm11d},
+ [28] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm12f, Rxmm12d},
+ [29] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm13f, Rxmm13d},
+ [30] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm14f, Rxmm14d},
+ [31] = {Rnone, Rnone, Rnone, Rnone, Rnone, Rxmm15f, Rxmm15d},
};
/* Which regmap entry a register maps to */
int colourmap[Nreg] = {
- /* byte */
- [Ral] = 0, [Rax] = 0, [Reax] = 0, [Rrax] = 0,
- [Rcl] = 1, [Rcx] = 1, [Recx] = 1, [Rrcx] = 1,
- [Rdl] = 2, [Rdx] = 2, [Redx] = 2, [Rrdx] = 2,
- [Rbl] = 3, [Rbx] = 3, [Rebx] = 3, [Rrbx] = 3,
- [Rsil] = 4, [Rsi] = 4, [Resi] = 4, [Rrsi] = 4,
- [Rdil] = 5, [Rdi] = 5, [Redi] = 5, [Rrdi] = 5,
- [Rr8b] = 6, [Rr8w] = 6, [Rr8d] = 6, [Rr8] = 6,
- [Rr9b] = 7, [Rr9w] = 7, [Rr9d] = 7, [Rr9] = 7,
- [Rr10b] = 8, [Rr10w] = 8, [Rr10d] = 8, [Rr10] = 8,
- [Rr11b] = 9, [Rr11w] = 9, [Rr11d] = 9, [Rr11] = 9,
- [Rr12b] = 10, [Rr12w] = 10, [Rr12d] = 10, [Rr12] = 10,
- [Rr13b] = 11, [Rr13w] = 11, [Rr13d] = 11, [Rr13] = 11,
- [Rr14b] = 12, [Rr14w] = 12, [Rr14d] = 12, [Rr14] = 12,
- [Rr15b] = 13, [Rr15w] = 13, [Rr15d] = 13, [Rr15] = 13,
-
- /* float */
- [Rxmm0f] = 16, [Rxmm0d] = 16,
- [Rxmm1f] = 17, [Rxmm1d] = 17,
- [Rxmm2f] = 18, [Rxmm2d] = 18,
- [Rxmm3f] = 19, [Rxmm3d] = 19,
- [Rxmm4f] = 20, [Rxmm4d] = 20,
- [Rxmm5f] = 21, [Rxmm5d] = 21,
- [Rxmm6f] = 22, [Rxmm6d] = 22,
- [Rxmm7f] = 23, [Rxmm7d] = 23,
- [Rxmm8f] = 24, [Rxmm8d] = 24,
- [Rxmm9f] = 25, [Rxmm9d] = 25,
- [Rxmm10f] = 26, [Rxmm10d] = 26,
- [Rxmm11f] = 27, [Rxmm11d] = 27,
- [Rxmm12f] = 28, [Rxmm12d] = 28,
- [Rxmm13f] = 29, [Rxmm13d] = 29,
- [Rxmm14f] = 30, [Rxmm14d] = 30,
- [Rxmm15f] = 31, [Rxmm15d] = 31,
+ /* byte */
+ [Ral] = 0, [Rax] = 0, [Reax] = 0, [Rrax] = 0,
+ [Rcl] = 1, [Rcx] = 1, [Recx] = 1, [Rrcx] = 1,
+ [Rdl] = 2, [Rdx] = 2, [Redx] = 2, [Rrdx] = 2,
+ [Rbl] = 3, [Rbx] = 3, [Rebx] = 3, [Rrbx] = 3,
+ [Rsil] = 4, [Rsi] = 4, [Resi] = 4, [Rrsi] = 4,
+ [Rdil] = 5, [Rdi] = 5, [Redi] = 5, [Rrdi] = 5,
+ [Rr8b] = 6, [Rr8w] = 6, [Rr8d] = 6, [Rr8] = 6,
+ [Rr9b] = 7, [Rr9w] = 7, [Rr9d] = 7, [Rr9] = 7,
+ [Rr10b] = 8, [Rr10w] = 8, [Rr10d] = 8, [Rr10] = 8,
+ [Rr11b] = 9, [Rr11w] = 9, [Rr11d] = 9, [Rr11] = 9,
+ [Rr12b] = 10, [Rr12w] = 10, [Rr12d] = 10, [Rr12] = 10,
+ [Rr13b] = 11, [Rr13w] = 11, [Rr13d] = 11, [Rr13] = 11,
+ [Rr14b] = 12, [Rr14w] = 12, [Rr14d] = 12, [Rr14] = 12,
+ [Rr15b] = 13, [Rr15w] = 13, [Rr15d] = 13, [Rr15] = 13,
+
+ /* float */
+ [Rxmm0f] = 16, [Rxmm0d] = 16,
+ [Rxmm1f] = 17, [Rxmm1d] = 17,
+ [Rxmm2f] = 18, [Rxmm2d] = 18,
+ [Rxmm3f] = 19, [Rxmm3d] = 19,
+ [Rxmm4f] = 20, [Rxmm4d] = 20,
+ [Rxmm5f] = 21, [Rxmm5d] = 21,
+ [Rxmm6f] = 22, [Rxmm6d] = 22,
+ [Rxmm7f] = 23, [Rxmm7d] = 23,
+ [Rxmm8f] = 24, [Rxmm8d] = 24,
+ [Rxmm9f] = 25, [Rxmm9d] = 25,
+ [Rxmm10f] = 26, [Rxmm10d] = 26,
+ [Rxmm11f] = 27, [Rxmm11d] = 27,
+ [Rxmm12f] = 28, [Rxmm12d] = 28,
+ [Rxmm13f] = 29, [Rxmm13d] = 29,
+ [Rxmm14f] = 30, [Rxmm14d] = 30,
+ [Rxmm15f] = 31, [Rxmm15d] = 31,
};
size_t modesize[Nmode] = {
- [ModeNone] = 0,
- [ModeB] = 1,
- [ModeW] = 2,
- [ModeL] = 4,
- [ModeQ] = 8,
- [ModeF] = 4,
- [ModeD] = 8,
+ [ModeNone] = 0,
+ [ModeB] = 1,
+ [ModeW] = 2,
+ [ModeL] = 4,
+ [ModeQ] = 8,
+ [ModeF] = 4,
+ [ModeD] = 8,
};
-
static int _K[Nclass] = {
- [Classbad] = 0,
- [Classint] = 14,
- [Classflt] = 16,
+ [Classbad] = 0,
+ [Classint] = 14,
+ [Classflt] = 16,
};
Rclass rclass(Loc *l)
{
- switch (l->mode) {
- case ModeNone: return Classbad;
- case Nmode: return Classbad;
- case ModeB: return Classint;
- case ModeW: return Classint;
- case ModeL: return Classint;
- case ModeQ: return Classint;
-
- case ModeF: return Classflt;
- case ModeD: return Classflt;
- }
- return Classbad;
+ switch (l->mode) {
+ case ModeNone: return Classbad;
+ case Nmode: return Classbad;
+ case ModeB: return Classint;
+ case ModeW: return Classint;
+ case ModeL: return Classint;
+ case ModeQ: return Classint;
+
+ case ModeF: return Classflt;
+ case ModeD: return Classflt;
+ }
+ return Classbad;
}
/* %esp, %ebp are not in the allocatable pool */
static int isfixreg(Loc *l)
{
- if (l->reg.colour == Resp)
- return 1;
- if (l->reg.colour == Rebp)
- return 1;
- return 0;
+ if (l->reg.colour == Resp)
+ return 1;
+ if (l->reg.colour == Rebp)
+ return 1;
+ return 0;
}
static size_t uses(Insn *insn, regid *u)
{
- size_t i, j;
- int k;
- Loc *m;
-
- j = 0;
- /* Add all the registers used and defined. Duplicates
- * in this list are fine, since they're being added to
- * a set anyways */
- for (i = 0; i < Maxarg; i++) {
- if (!usetab[insn->op].l[i])
- break;
- k = usetab[insn->op].l[i] - 1;
- /* non-registers are handled later */
- if (insn->args[k]->type == Locreg)
- if (!isfixreg(insn->args[k]))
- u[j++] = insn->args[k]->reg.id;
- }
- /* some insns don't reflect their defs in the args.
- * These are explictly listed in the insn description */
- for (i = 0; i < Nreg; i++) {
- if (!usetab[insn->op].r[i])
- break;
- /* not a leak; physical registers get memoized */
- u[j++] = locphysreg(usetab[insn->op].r[i])->reg.id;
- }
- /* If the registers are in an address calculation,
- * they're used no matter what. */
- for (i = 0; i < insn->nargs; i++) {
- m = insn->args[i];
- if (m->type != Locmem && m->type != Locmeml)
- continue;
- if (m->mem.base)
- if (!isfixreg(m->mem.base))
- u[j++] = m->mem.base->reg.id;
- if (m->mem.idx)
- if (!isfixreg(m->mem.base))
- u[j++] = m->mem.idx->reg.id;
- }
- return j;
+ size_t i, j;
+ int k;
+ Loc *m;
+
+ j = 0;
+ /* Add all the registers used and defined. Duplicates
+ * in this list are fine, since they're being added to
+ * a set anyways */
+ for (i = 0; i < Maxarg; i++) {
+ if (!usetab[insn->op].l[i])
+ break;
+ k = usetab[insn->op].l[i] - 1;
+ /* non-registers are handled later */
+ if (insn->args[k]->type == Locreg)
+ if (!isfixreg(insn->args[k]))
+ u[j++] = insn->args[k]->reg.id;
+ }
+ /* some insns don't reflect their defs in the args.
+ * These are explictly listed in the insn description */
+ for (i = 0; i < Nreg; i++) {
+ if (!usetab[insn->op].r[i])
+ break;
+ /* not a leak; physical registers get memoized */
+ u[j++] = locphysreg(usetab[insn->op].r[i])->reg.id;
+ }
+ /* If the registers are in an address calculation,
+ * they're used no matter what. */
+ for (i = 0; i < insn->nargs; i++) {
+ m = insn->args[i];
+ if (m->type != Locmem && m->type != Locmeml)
+ continue;
+ if (m->mem.base)
+ if (!isfixreg(m->mem.base))
+ u[j++] = m->mem.base->reg.id;
+ if (m->mem.idx)
+ if (!isfixreg(m->mem.base))
+ u[j++] = m->mem.idx->reg.id;
+ }
+ return j;
}
static size_t defs(Insn *insn, regid *d)
{
- size_t i, j;
- int k;
-
- j = 0;
- /* Add all the registers dsed and defined. Duplicates
- * in this list are fine, since they're being added to
- * a set anyways */
- for (i = 0; i < Maxarg; i++) {
- if (!deftab[insn->op].l[i])
- break;
- k = deftab[insn->op].l[i] - 1;
- if (insn->args[k]->type == Locreg)
- if (!isfixreg(insn->args[k]))
- d[j++] = insn->args[k]->reg.id;
- }
- /* some insns don't reflect their defs in the args.
- * These are explictly listed in the insn description */
- for (i = 0; i < Nreg; i++) {
- if (!deftab[insn->op].r[i])
- break;
- /* not a leak; physical registers get memoized */
- d[j++] = locphysreg(deftab[insn->op].r[i])->reg.id;
- }
- return j;
+ size_t i, j;
+ int k;
+
+ j = 0;
+ /* Add all the registers dsed and defined. Duplicates
+ * in this list are fine, since they're being added to
+ * a set anyways */
+ for (i = 0; i < Maxarg; i++) {
+ if (!deftab[insn->op].l[i])
+ break;
+ k = deftab[insn->op].l[i] - 1;
+ if (insn->args[k]->type == Locreg)
+ if (!isfixreg(insn->args[k]))
+ d[j++] = insn->args[k]->reg.id;
+ }
+ /* some insns don't reflect their defs in the args.
+ * These are explictly listed in the insn description */
+ for (i = 0; i < Nreg; i++) {
+ if (!deftab[insn->op].r[i])
+ break;
+ /* not a leak; physical registers get memoized */
+ d[j++] = locphysreg(deftab[insn->op].r[i])->reg.id;
+ }
+ return j;
}
/* The uses and defs for an entire BB. */
static void udcalc(Asmbb *bb)
{
- regid u[Nreg], d[Nreg];
- size_t nu, nd;
- size_t i, j;
-
- bb->use = bsclear(bb->use);
- bb->def = bsclear(bb->def);
- for (i = 0; i < bb->ni; i++) {
- nu = uses(bb->il[i], u);
- nd = defs(bb->il[i], d);
- for (j = 0; j < nu; j++)
- if (!bshas(bb->def, u[j]))
- bsput(bb->use, u[j]);
- for (j = 0; j < nd; j++)
- bsput(bb->def, d[j]);
- }
+ regid u[Nreg], d[Nreg];
+ size_t nu, nd;
+ size_t i, j;
+
+ bb->use = bsclear(bb->use);
+ bb->def = bsclear(bb->def);
+ for (i = 0; i < bb->ni; i++) {
+ nu = uses(bb->il[i], u);
+ nd = defs(bb->il[i], d);
+ for (j = 0; j < nu; j++)
+ if (!bshas(bb->def, u[j]))
+ bsput(bb->use, u[j]);
+ for (j = 0; j < nd; j++)
+ bsput(bb->def, d[j]);
+ }
}
static int istrivial(Isel *s, regid r)
{
- return s->degree[r] < _K[rclass(locmap[r])];
+ return s->degree[r] < _K[rclass(locmap[r])];
}
static void liveness(Isel *s)
{
- Bitset *old;
- Asmbb **bb;
- ssize_t nbb;
- ssize_t i;
- size_t j;
- int changed;
-
- bb = s->bb;
- nbb = s->nbb;
- for (i = 0; i < nbb; i++) {
- if (!bb[i])
- continue;
- udcalc(s->bb[i]);
- bb[i]->livein = bsclear(bb[i]->livein);
- bb[i]->liveout = bsclear(bb[i]->liveout);
- }
-
- changed = 1;
- while (changed) {
- changed = 0;
- old = NULL;
- for (i = nbb - 1; i >= 0; i--) {
- if (!bb[i])
- continue;
- old = bsdup(bb[i]->liveout);
- /* liveout[b] = U(s in succ) livein[s] */
- for (j = 0; bsiter(bb[i]->succ, &j); j++)
- bsunion(bb[i]->liveout, bb[j]->livein);
- /* livein[b] = use[b] U (out[b] \ def[b]) */
- bb[i]->livein = bsclear(bb[i]->livein);
- bsunion(bb[i]->livein, bb[i]->liveout);
- bsdiff(bb[i]->livein, bb[i]->def);
- bsunion(bb[i]->livein, bb[i]->use);
- if (!changed)
- changed = !bseq(old, bb[i]->liveout);
- bsfree(old);
- }
- }
+ Bitset *old;
+ Asmbb **bb;
+ ssize_t nbb;
+ ssize_t i;
+ size_t j;
+ int changed;
+
+ bb = s->bb;
+ nbb = s->nbb;
+ for (i = 0; i < nbb; i++) {
+ if (!bb[i])
+ continue;
+ udcalc(s->bb[i]);
+ bb[i]->livein = bsclear(bb[i]->livein);
+ bb[i]->liveout = bsclear(bb[i]->liveout);
+ }
+
+ changed = 1;
+ while (changed) {
+ changed = 0;
+ old = NULL;
+ for (i = nbb - 1; i >= 0; i--) {
+ if (!bb[i])
+ continue;
+ old = bsdup(bb[i]->liveout);
+ /* liveout[b] = U(s in succ) livein[s] */
+ for (j = 0; bsiter(bb[i]->succ, &j); j++)
+ bsunion(bb[i]->liveout, bb[j]->livein);
+ /* livein[b] = use[b] U (out[b] \ def[b]) */
+ bb[i]->livein = bsclear(bb[i]->livein);
+ bsunion(bb[i]->livein, bb[i]->liveout);
+ bsdiff(bb[i]->livein, bb[i]->def);
+ bsunion(bb[i]->livein, bb[i]->use);
+ if (!changed)
+ changed = !bseq(old, bb[i]->liveout);
+ bsfree(old);
+ }
+ }
}
/* we're only interested in register->register moves */
static int ismove(Insn *i)
{
- if (i->op != Imov && i->op != Imovs)
- return 0;
- return i->args[0]->type == Locreg && i->args[1]->type == Locreg;
+ if (i->op != Imov && i->op != Imovs)
+ return 0;
+ return i->args[0]->type == Locreg && i->args[1]->type == Locreg;
}
static int gbhasedge(Isel *s, size_t u, size_t v)
{
- size_t i;
- i = (s->nreg * v) + u;
- return (s->gbits[i/Sizetbits] & (1ULL <<(i % Sizetbits))) != 0;
+ size_t i;
+ i = (s->nreg * v) + u;
+ return (s->gbits[i/Sizetbits] & (1ULL <<(i % Sizetbits))) != 0;
}
static void gbputedge(Isel *s, size_t u, size_t v)
{
- size_t i, j;
+ size_t i, j;
- i = (s->nreg * u) + v;
- j = (s->nreg * v) + u;
- s->gbits[i/Sizetbits] |= 1ULL << (i % Sizetbits);
- s->gbits[j/Sizetbits] |= 1ULL << (j % Sizetbits);
- assert(gbhasedge(s, u, v) && gbhasedge(s, v, u));
+ i = (s->nreg * u) + v;
+ j = (s->nreg * v) + u;
+ s->gbits[i/Sizetbits] |= 1ULL << (i % Sizetbits);
+ s->gbits[j/Sizetbits] |= 1ULL << (j % Sizetbits);
+ assert(gbhasedge(s, u, v) && gbhasedge(s, v, u));
}
static int wlfind(Loc **wl, size_t nwl, regid v, size_t *idx)
{
- size_t i;
-
- for (i = 0; i < nwl; i++) {
- if (wl[i]->reg.id == v) {
- *idx = i;
- return 1;
- }
- }
- *idx = -1;
- return 0;
+ size_t i;
+
+ for (i = 0; i < nwl; i++) {
+ if (wl[i]->reg.id == v) {
+ *idx = i;
+ return 1;
+ }
+ }
+ *idx = -1;
+ return 0;
}
/*
@@ -347,609 +346,609 @@ static int wlfind(Loc **wl, size_t nwl, regid v, size_t *idx)
*/
static int degreechange(Isel *s, regid u, regid v)
{
- regid phys, virt, r;
- size_t i;
-
- if (bshas(s->prepainted, u)) {
- phys = u;
- virt = v;
- } else if (bshas(s->prepainted, v)) {
- phys = v;
- virt = u;
- } else {
- return 1;
- }
-
- for (i = 0; i < Nmode; i++) {
- r = regmap[colourmap[phys]][i];
- if (r != phys && gbhasedge(s, virt, regmap[colourmap[phys]][i])) {
- return 0;
- }
- }
- return 1;
+ regid phys, virt, r;
+ size_t i;
+
+ if (bshas(s->prepainted, u)) {
+ phys = u;
+ virt = v;
+ } else if (bshas(s->prepainted, v)) {
+ phys = v;
+ virt = u;
+ } else {
+ return 1;
+ }
+
+ for (i = 0; i < Nmode; i++) {
+ r = regmap[colourmap[phys]][i];
+ if (r != phys && gbhasedge(s, virt, regmap[colourmap[phys]][i])) {
+ return 0;
+ }
+ }
+ return 1;
}
static void alputedge(Isel *s, regid u, regid v)
{
- s->ngadj[u]++;
- s->gadj[u] = xrealloc(s->gadj[u], s->ngadj[u]*sizeof(regid));
- s->gadj[u][s->ngadj[u] - 1] = v;
+ s->ngadj[u]++;
+ s->gadj[u] = xrealloc(s->gadj[u], s->ngadj[u]*sizeof(regid));
+ s->gadj[u][s->ngadj[u] - 1] = v;
}
static void wlput(Loc ***wl, size_t *nwl, Loc *l)
{
- lappend(wl, nwl, l);
- l->list = wl;
+ lappend(wl, nwl, l);
+ l->list = wl;
}
static void wldel(Isel *s, Loc ***wl, size_t *nwl, size_t idx)
{
- (*wl)[idx]->list = NULL;
- ldel(wl, nwl, idx);
+ (*wl)[idx]->list = NULL;
+ ldel(wl, nwl, idx);
}
static void wlputset(Bitset *bs, regid r)
{
- bsput(bs, r);
- locmap[r]->list = bs;
+ bsput(bs, r);
+ locmap[r]->list = bs;
}
static void addedge(Isel *s, regid u, regid v)
{
- if (u == v || gbhasedge(s, u, v))
- return;
- if (u == Rrbp || u == Rrsp || u == Rrip)
- return;
- if (v == Rrbp || v == Rrsp || v == Rrip)
- return;
- if (rclass(locmap[u]) != rclass(locmap[v]))
- return;
- if (bshas(s->prepainted, u) && bshas(s->prepainted, v))
- return;
-
- gbputedge(s, u, v);
- gbputedge(s, v, u);
- if (!bshas(s->prepainted, u)) {
- alputedge(s, u, v);
- s->degree[u] += degreechange(s, v, u);
- }
- if (!bshas(s->prepainted, v)) {
- alputedge(s, v, u);
- s->degree[v] += degreechange(s, u, v);
- }
+ if (u == v || gbhasedge(s, u, v))
+ return;
+ if (u == Rrbp || u == Rrsp || u == Rrip)
+ return;
+ if (v == Rrbp || v == Rrsp || v == Rrip)
+ return;
+ if (rclass(locmap[u]) != rclass(locmap[v]))
+ return;
+ if (bshas(s->prepainted, u) && bshas(s->prepainted, v))
+ return;
+
+ gbputedge(s, u, v);
+ gbputedge(s, v, u);
+ if (!bshas(s->prepainted, u)) {
+ alputedge(s, u, v);
+ s->degree[u] += degreechange(s, v, u);
+ }
+ if (!bshas(s->prepainted, v)) {
+ alputedge(s, v, u);
+ s->degree[v] += degreechange(s, u, v);
+ }
}
static void gfree(Isel *s)
{
- size_t i;
+ size_t i;
- for (i = 0; i < s->nreg; i++)
- free(s->gadj[i]);
- free(s->gbits);
- free(s->gadj);
- free(s->ngadj);
+ for (i = 0; i < s->nreg; i++)
+ free(s->gadj[i]);
+ free(s->gbits);
+ free(s->gadj);
+ free(s->ngadj);
}
static void setup(Isel *s)
{
- size_t gchunks;
- size_t i;
-
- gfree(s);
- s->nreg = maxregid;
- gchunks = (s->nreg*s->nreg)/Sizetbits + 1;
- s->gbits = zalloc(gchunks*sizeof(size_t));
- /* fresh adj list repr. */
- s->gadj = zalloc(s->nreg * sizeof(regid*));
- s->ngadj = zalloc(s->nreg * sizeof(size_t));
-
- s->mactiveset = bsclear(s->mactiveset);
- s->wlmoveset = bsclear(s->wlmoveset);
- s->spilled = bsclear(s->spilled);
- s->coalesced = bsclear(s->coalesced);
- lfree(&s->wlspill, &s->nwlspill);
- lfree(&s->wlfreeze, &s->nwlfreeze);
- lfree(&s->wlsimp, &s->nwlsimp);
-
- free(s->aliasmap);
- free(s->degree);
- free(s->rmoves);
- free(s->nrmoves);
-
- s->aliasmap = zalloc(s->nreg * sizeof(Loc*));
- s->degree = zalloc(s->nreg * sizeof(int));
- s->nuses = zalloc(s->nreg * sizeof(int));
- s->rmoves = zalloc(s->nreg * sizeof(Insn**));
- s->nrmoves = zalloc(s->nreg * sizeof(size_t));
-
- for (i = 0; bsiter(s->prepainted, &i); i++)
- s->degree[i] = 1<<16;
+ size_t gchunks;
+ size_t i;
+
+ gfree(s);
+ s->nreg = maxregid;
+ gchunks = (s->nreg*s->nreg)/Sizetbits + 1;
+ s->gbits = zalloc(gchunks*sizeof(size_t));
+ /* fresh adj list repr. */
+ s->gadj = zalloc(s->nreg * sizeof(regid*));
+ s->ngadj = zalloc(s->nreg * sizeof(size_t));
+
+ s->mactiveset = bsclear(s->mactiveset);
+ s->wlmoveset = bsclear(s->wlmoveset);
+ s->spilled = bsclear(s->spilled);
+ s->coalesced = bsclear(s->coalesced);
+ lfree(&s->wlspill, &s->nwlspill);
+ lfree(&s->wlfreeze, &s->nwlfreeze);
+ lfree(&s->wlsimp, &s->nwlsimp);
+
+ free(s->aliasmap);
+ free(s->degree);
+ free(s->rmoves);
+ free(s->nrmoves);
+
+ s->aliasmap = zalloc(s->nreg * sizeof(Loc*));
+ s->degree = zalloc(s->nreg * sizeof(int));
+ s->nuses = zalloc(s->nreg * sizeof(int));
+ s->rmoves = zalloc(s->nreg * sizeof(Insn**));
+ s->nrmoves = zalloc(s->nreg * sizeof(size_t));
+
+ for (i = 0; bsiter(s->prepainted, &i); i++)
+ s->degree[i] = 1<<16;
}
static void build(Isel *s)
{
- regid u[Nreg], d[Nreg];
- size_t nu, nd;
- size_t i, k, a;
- ssize_t j;
- Bitset *live;
- Asmbb **bb;
- size_t nbb;
- Insn *insn;
- size_t l;
-
- /* set up convenience vars */
- bb = s->bb;
- nbb = s->nbb;
-
- for (i = 0; i < nbb; i++) {
- if (!bb[i])
- continue;
- live = bsdup(bb[i]->liveout);
- for (j = bb[i]->ni - 1; j >= 0; j--) {
- insn = bb[i]->il[j];
- nu = uses(insn, u);
- nd = defs(insn, d);
-
- /* add these to the initial set */
- for (k = 0; k < nu; k++) {
- if (!bshas(s->prepainted, u[k])) {
- wlputset(s->initial, u[k]);
- s->nuses[u[k]]++;
- }
- }
- for (k = 0; k < nd; k++) {
- if (!bshas(s->prepainted, d[k]))
- wlputset(s->initial, d[k]);
- }
-
- /* moves get special treatment, since we don't want spurious
- * edges between the src and dest */
- //iprintf(stdout, insn);
- if (ismove(insn)) {
- /* live \= uses(i) */
- for (k = 0; k < nu; k++) {
- /* remove all physical register aliases */
- if (bshas(s->prepainted, u[k])) {
- for (a = 0; a < Nmode; a++)
- bsdel(live, regmap[colourmap[u[k]]][a]);
- } else {
- bsdel(live, u[k]);
- }
- }
-
- for (k = 0; k < nu; k++)
- lappend(&s->rmoves[u[k]], &s->nrmoves[u[k]], insn);
- for (k = 0; k < nd; k++)
- lappend(&s->rmoves[d[k]], &s->nrmoves[d[k]], insn);
- lappend(&s->wlmove, &s->nwlmove, insn);
- bsput(s->wlmoveset, insn->uid);
- }
- /* live = live U def(i) */
- for (k = 0; k < nd; k++)
- bsput(live, d[k]);
-
- for (k = 0; k < nd; k++)
- for (l = 0; bsiter(live, &l); l++)
- addedge(s, d[k], l);
- /* live = use(i) U (live \ def(i)) */
- for (k = 0; k < nd; k++)
- bsdel(live, d[k]);
- for (k = 0; k < nu; k++)
- bsput(live, u[k]);
- }
- bsfree(live);
- }
+ regid u[Nreg], d[Nreg];
+ size_t nu, nd;
+ size_t i, k, a;
+ ssize_t j;
+ Bitset *live;
+ Asmbb **bb;
+ size_t nbb;
+ Insn *insn;
+ size_t l;
+
+ /* set up convenience vars */
+ bb = s->bb;
+ nbb = s->nbb;
+
+ for (i = 0; i < nbb; i++) {
+ if (!bb[i])
+ continue;
+ live = bsdup(bb[i]->liveout);
+ for (j = bb[i]->ni - 1; j >= 0; j--) {
+ insn = bb[i]->il[j];
+ nu = uses(insn, u);
+ nd = defs(insn, d);
+
+ /* add these to the initial set */
+ for (k = 0; k < nu; k++) {
+ if (!bshas(s->prepainted, u[k])) {
+ wlputset(s->initial, u[k]);
+ s->nuses[u[k]]++;
+ }
+ }
+ for (k = 0; k < nd; k++) {
+ if (!bshas(s->prepainted, d[k]))
+ wlputset(s->initial, d[k]);
+ }
+
+ /* moves get special treatment, since we don't want spurious
+ * edges between the src and dest */
+ //iprintf(stdout, insn);
+ if (ismove(insn)) {
+ /* live \= uses(i) */
+ for (k = 0; k < nu; k++) {
+ /* remove all physical register aliases */
+ if (bshas(s->prepainted, u[k])) {
+ for (a = 0; a < Nmode; a++)
+ bsdel(live, regmap[colourmap[u[k]]][a]);
+ } else {
+ bsdel(live, u[k]);
+ }
+ }
+
+ for (k = 0; k < nu; k++)
+ lappend(&s->rmoves[u[k]], &s->nrmoves[u[k]], insn);
+ for (k = 0; k < nd; k++)
+ lappend(&s->rmoves[d[k]], &s->nrmoves[d[k]], insn);
+ lappend(&s->wlmove, &s->nwlmove, insn);
+ bsput(s->wlmoveset, insn->uid);
+ }
+ /* live = live U def(i) */
+ for (k = 0; k < nd; k++)
+ bsput(live, d[k]);
+
+ for (k = 0; k < nd; k++)
+ for (l = 0; bsiter(live, &l); l++)
+ addedge(s, d[k], l);
+ /* live = use(i) U (live \ def(i)) */
+ for (k = 0; k < nd; k++)
+ bsdel(live, d[k]);
+ for (k = 0; k < nu; k++)
+ bsput(live, u[k]);
+ }
+ bsfree(live);
+ }
}
static int adjavail(Isel *s, regid r)
{
- if (bshas(s->coalesced, r))
- return 0;
- if (locmap[r]->list == &s->selstk)
- return 0;
- return 1;
+ if (bshas(s->coalesced, r))
+ return 0;
+ if (locmap[r]->list == &s->selstk)
+ return 0;
+ return 1;
}
static size_t nodemoves(Isel *s, regid n, Insn ***pil)
{
- size_t i;
- size_t count;
-
- /* FIXME: inefficient. Do I care? */
- count = 0;
- if (pil)
- *pil = NULL;
- for (i = 0; i < s->nrmoves[n]; i++) {
- if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
- lappend(pil, &count, s->rmoves[n][i]);
- if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
- lappend(pil, &count, s->rmoves[n][i]);
- }
- return count;
+ size_t i;
+ size_t count;
+
+ /* FIXME: inefficient. Do I care? */
+ count = 0;
+ if (pil)
+ *pil = NULL;
+ for (i = 0; i < s->nrmoves[n]; i++) {
+ if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
+ lappend(pil, &count, s->rmoves[n][i]);
+ if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
+ lappend(pil, &count, s->rmoves[n][i]);
+ }
+ return count;
}
static int moverelated(Isel *s, regid n)
{
- size_t i;
-
- for (i = 0; i < s->nrmoves[n]; i++) {
- if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
- return 1;
- if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
- return 1;
- }
- return 0;
+ size_t i;
+
+ for (i = 0; i < s->nrmoves[n]; i++) {
+ if (bshas(s->mactiveset, s->rmoves[n][i]->uid))
+ return 1;
+ if (bshas(s->wlmoveset, s->rmoves[n][i]->uid))
+ return 1;
+ }
+ return 0;
}
static void mkworklist(Isel *s)
{
- size_t i;
-
- for (i = 0; bsiter(s->initial, &i); i++) {
- if (bshas(s->prepainted, i))
- continue;
- else if (!istrivial(s, i))
- wlput(&s->wlspill, &s->nwlspill, locmap[i]);
- else if (moverelated(s, i)) {
- wlput(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
- }
- else
- wlput(&s->wlsimp, &s->nwlsimp, locmap[i]);
- locmap[i]->reg.colour = 0;
- }
+ size_t i;
+
+ for (i = 0; bsiter(s->initial, &i); i++) {
+ if (bshas(s->prepainted, i))
+ continue;
+ else if (!istrivial(s, i))
+ wlput(&s->wlspill, &s->nwlspill, locmap[i]);
+ else if (moverelated(s, i)) {
+ wlput(&s->wlfreeze, &s->nwlfreeze, locmap[i]);
+ }
+ else
+ wlput(&s->wlsimp, &s->nwlsimp, locmap[i]);
+ locmap[i]->reg.colour = 0;
+ }
}
static void enablemove(Isel *s, regid n)
{
- size_t i, j;
- Insn **il;
- size_t ni;
-
- ni = nodemoves(s, n, &il);
- for (i = 0; i < ni; i++) {
- if (!bshas(s->mactiveset, il[i]->uid))
- continue;
- for (j = 0; j < s->nmactive; j++) {
- if (il[i] == s->mactive[j]) {
- ldel(&s->mactive, &s->nmactive, j);
- lappend(&s->wlmove, &s->nwlmove, il[i]);
- bsdel(s->mactiveset, il[i]->uid);
- bsput(s->wlmoveset, il[i]->uid);
- }
- }
- }
+ size_t i, j;
+ Insn **il;
+ size_t ni;
+
+ ni = nodemoves(s, n, &il);
+ for (i = 0; i < ni; i++) {
+ if (!bshas(s->mactiveset, il[i]->uid))
+ continue;
+ for (j = 0; j < s->nmactive; j++) {
+ if (il[i] == s->mactive[j]) {
+ ldel(&s->mactive, &s->nmactive, j);
+ lappend(&s->wlmove, &s->nwlmove, il[i]);
+ bsdel(s->mactiveset, il[i]->uid);
+ bsput(s->wlmoveset, il[i]->uid);
+ }
+ }
+ }
}
static void decdegree(Isel *s, regid m)
{
- int before, after;
- int found;
- size_t idx, i;
- regid n;
-
- assert(m < s->nreg);
- before = istrivial(s, m);
- s->degree[m]--;
- after = istrivial(s, m);
-
- if (before != after) {
- enablemove(s, m);
- for (i = 0; i < s->ngadj[m]; i++) {
- n = s->gadj[m][i];
- if (adjavail(s, n))
- enablemove(s, n);
- }
-
- /* Subtle:
- *
- * If this code is being called from coalesce(),
- * then the degree could have been bumped up only
- * temporarily. This means that the node can already
- * be on wlfreeze or wlsimp.
- *
- * Therefore, if we don't find it on wlspill, we assert
- * that the node is already on the list that we'd be
- * moving it to.
- */
- found = wlfind(s->wlspill, s->nwlspill, m, &idx);
- if (found)
- wldel(s, &s->wlspill, &s->nwlspill, idx);
- if (moverelated(s, m)) {
- if (!found) {
- assert(wlfind(s->wlfreeze, s->nwlfreeze, m, &idx) != 0);
- } else {
- wlput(&s->wlfreeze, &s->nwlfreeze, locmap[m]);
- }
- } else {
- if (!found) {
- assert(wlfind(s->wlsimp, s->nwlsimp, m, &idx));
- } else {
- wlput(&s->wlsimp, &s->nwlsimp, locmap[m]);
- }
- }
- }
+ int before, after;
+ int found;
+ size_t idx, i;
+ regid n;
+
+ assert(m < s->nreg);
+ before = istrivial(s, m);
+ s->degree[m]--;
+ after = istrivial(s, m);
+
+ if (before != after) {
+ enablemove(s, m);
+ for (i = 0; i < s->ngadj[m]; i++) {
+ n = s->gadj[m][i];
+ if (adjavail(s, n))
+ enablemove(s, n);
+ }
+
+ /* Subtle:
+ *
+ * If this code is being called from coalesce(),
+ * then the degree could have been bumped up only
+ * temporarily. This means that the node can already
+ * be on wlfreeze or wlsimp.
+ *
+ * Therefore, if we don't find it on wlspill, we assert
+ * that the node is already on the list that we'd be
+ * moving it to.
+ */
+ found = wlfind(s->wlspill, s->nwlspill, m, &idx);
+ if (found)
+ wldel(s, &s->wlspill, &s->nwlspill, idx);
+ if (moverelated(s, m)) {
+ if (!found) {
+ assert(wlfind(s->wlfreeze, s->nwlfreeze, m, &idx) != 0);
+ } else {
+ wlput(&s->wlfreeze, &s->nwlfreeze, locmap[m]);
+ }
+ } else {
+ if (!found) {
+ assert(wlfind(s->wlsimp, s->nwlsimp, m, &idx));
+ } else {
+ wlput(&s->wlsimp, &s->nwlsimp, locmap[m]);
+ }
+ }
+ }
}
static void simp(Isel *s)
{
- Loc *l;
- regid m;
- size_t i;
-
- l = lpop(&s->wlsimp, &s->nwlsimp);
- wlput(&s->selstk, &s->nselstk, l);
- for (i = 0; i < s->ngadj[l->reg.id]; i++) {
- m = s->gadj[l->reg.id][i];
- if (adjavail(s, m))
- decdegree(s, m);
- }
+ Loc *l;
+ regid m;
+ size_t i;
+
+ l = lpop(&s->wlsimp, &s->nwlsimp);
+ wlput(&s->selstk, &s->nselstk, l);
+ for (i = 0; i < s->ngadj[l->reg.id]; i++) {
+ m = s->gadj[l->reg.id][i];
+ if (adjavail(s, m))
+ decdegree(s, m);
+ }
}
static regid getmappedalias(Loc **aliasmap, size_t nreg, regid id)
{
- /*
- * if we get called from rewrite(), we can get a register that
- * we just created, with an id bigger than the number of entries
- * in the alias map. We should just return its id in that case.
- */
- while (id < nreg) {
- if (!aliasmap[id])
- break;
- id = aliasmap[id]->reg.id;
- };
- return id;
+ /*
+ * if we get called from rewrite(), we can get a register that
+ * we just created, with an id bigger than the number of entries
+ * in the alias map. We should just return its id in that case.
+ */
+ while (id < nreg) {
+ if (!aliasmap[id])
+ break;
+ id = aliasmap[id]->reg.id;
+ };
+ return id;
}
static regid getalias(Isel *s, regid id)
{
- return getmappedalias(s->aliasmap, s->nreg, id);
+ return getmappedalias(s->aliasmap, s->nreg, id);
}
static void wladd(Isel *s, regid u)
{
- size_t i;
-
- if (bshas(s->prepainted, u))
- return;
- if (moverelated(s, u))
- return;
- if (!istrivial(s, u))
- return;
-
- assert(locmap[u]->list == &s->wlfreeze || locmap[u]->list == &s->wlsimp);
- if (wlfind(s->wlfreeze, s->nwlfreeze, u, &i))
- wldel(s, &s->wlfreeze, &s->nwlfreeze, i);
- wlput(&s->wlsimp, &s->nwlsimp, locmap[u]);
+ size_t i;
+
+ if (bshas(s->prepainted, u))
+ return;
+ if (moverelated(s, u))
+ return;
+ if (!istrivial(s, u))
+ return;
+
+ assert(locmap[u]->list == &s->wlfreeze || locmap[u]->list == &s->wlsimp);
+ if (wlfind(s->wlfreeze, s->nwlfreeze, u, &i))
+ wldel(s, &s->wlfreeze, &s->nwlfreeze, i);
+ wlput(&s->wlsimp, &s->nwlsimp, locmap[u]);
}
static int conservative(Isel *s, regid u, regid v)
{
- int k;
- size_t i;
- regid n;
-
- k = 0;
- for (i = 0; i < s->ngadj[u]; i++) {
- n = s->gadj[u][i];
- if (adjavail(s, n) && !istrivial(s, n))
- k++;
- }
- for (i = 0; i < s->ngadj[v]; i++) {
- n = s->gadj[v][i];
- if (adjavail(s, n) && !istrivial(s, n))
- k++;
- }
- return k < _K[rclass(locmap[u])];
+ int k;
+ size_t i;
+ regid n;
+
+ k = 0;
+ for (i = 0; i < s->ngadj[u]; i++) {
+ n = s->gadj[u][i];
+ if (adjavail(s, n) && !istrivial(s, n))
+ k++;
+ }
+ for (i = 0; i < s->ngadj[v]; i++) {
+ n = s->gadj[v][i];
+ if (adjavail(s, n) && !istrivial(s, n))
+ k++;
+ }
+ return k < _K[rclass(locmap[u])];
}
/* FIXME: is this actually correct? */
static int ok(Isel *s, regid t, regid r)
{
- return istrivial(s, t) || bshas(s->prepainted, t) || gbhasedge(s, t, r);
+ return istrivial(s, t) || bshas(s->prepainted, t) || gbhasedge(s, t, r);
}
static int combinable(Isel *s, regid u, regid v)
{
- regid t;
- size_t i;
-
- /* Regs of different modes can't be combined as things stand.
- * In principle they should be combinable, but it confused the
- * whole mode dance. */
- if (locmap[u]->mode != locmap[v]->mode)
- return 0;
- /* if u isn't prepainted, can we conservatively coalesce? */
- if (!bshas(s->prepainted, u) && conservative(s, u, v))
- return 1;
-
- /* if it is, are the adjacent nodes ok to combine with this? */
- for (i = 0; i < s->ngadj[v]; i++) {
- t = s->gadj[v][i];
- if (adjavail(s, t) && !ok(s, t, u))
- return 0;
- }
- return 1;
+ regid t;
+ size_t i;
+
+ /* Regs of different modes can't be combined as things stand.
+ * In principle they should be combinable, but it confused the
+ * whole mode dance. */
+ if (locmap[u]->mode != locmap[v]->mode)
+ return 0;
+ /* if u isn't prepainted, can we conservatively coalesce? */
+ if (!bshas(s->prepainted, u) && conservative(s, u, v))
+ return 1;
+
+ /* if it is, are the adjacent nodes ok to combine with this? */
+ for (i = 0; i < s->ngadj[v]; i++) {
+ t = s->gadj[v][i];
+ if (adjavail(s, t) && !ok(s, t, u))
+ return 0;
+ }
+ return 1;
}
static void combine(Isel *s, regid u, regid v)
{
- regid t;
- size_t idx;
- size_t i, j;
- int has;
-
- if (debugopt['r'] > 2)
- printedge(stdout, "combining:", u, v);
- if (wlfind(s->wlfreeze, s->nwlfreeze, v, &idx))
- wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
- else if (wlfind(s->wlspill, s->nwlspill, v, &idx)) {
- wldel(s, &s->wlspill, &s->nwlspill, idx);
- }
- wlputset(s->coalesced, v);
- s->aliasmap[v] = locmap[u];
- s->nuses[u] += s->nuses[v];
-
- /* nodemoves[u] = nodemoves[u] U nodemoves[v] */
- for (i = 0; i < s->nrmoves[v]; i++) {
- has = 0;
- for (j = 0; j < s->nrmoves[u]; j++) {
- if (s->rmoves[v][i] == s->rmoves[u][j]) {
- has = 1;
- break;
- }
- }
- if (!has)
- lappend(&s->rmoves[u], &s->nrmoves[u], s->rmoves[v][i]);
- }
-
- for (i = 0; i < s->ngadj[v]; i++) {
- t = s->gadj[v][i];
- if (!adjavail(s, t))
- continue;
- if (debugopt['r'] > 2)
- printedge(stdout, "combine-putedge:", t, u);
- addedge(s, t, u);
- decdegree(s, t);
- }
- if (!istrivial(s, u) && wlfind(s->wlfreeze, s->nwlfreeze, u, &idx)) {
- wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
- wlput(&s->wlspill, &s->nwlspill, locmap[u]);
- }
+ regid t;
+ size_t idx;
+ size_t i, j;
+ int has;
+
+ if (debugopt['r'] > 2)
+ printedge(stdout, "combining:", u, v);
+ if (wlfind(s->wlfreeze, s->nwlfreeze, v, &idx))
+ wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
+ else if (wlfind(s->wlspill, s->nwlspill, v, &idx)) {
+ wldel(s, &s->wlspill, &s->nwlspill, idx);
+ }
+ wlputset(s->coalesced, v);
+ s->aliasmap[v] = locmap[u];
+ s->nuses[u] += s->nuses[v];
+
+ /* nodemoves[u] = nodemoves[u] U nodemoves[v] */
+ for (i = 0; i < s->nrmoves[v]; i++) {
+ has = 0;
+ for (j = 0; j < s->nrmoves[u]; j++) {
+ if (s->rmoves[v][i] == s->rmoves[u][j]) {
+ has = 1;
+ break;
+ }
+ }
+ if (!has)
+ lappend(&s->rmoves[u], &s->nrmoves[u], s->rmoves[v][i]);
+ }
+
+ for (i = 0; i < s->ngadj[v]; i++) {
+ t = s->gadj[v][i];
+ if (!adjavail(s, t))
+ continue;
+ if (debugopt['r'] > 2)
+ printedge(stdout, "combine-putedge:", t, u);
+ addedge(s, t, u);
+ decdegree(s, t);
+ }
+ if (!istrivial(s, u) && wlfind(s->wlfreeze, s->nwlfreeze, u, &idx)) {
+ wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
+ wlput(&s->wlspill, &s->nwlspill, locmap[u]);
+ }
}
static int constrained(Isel *s, regid u, regid v)
{
- size_t i;
-
- if (bshas(s->prepainted, v))
- return 1;
- if (bshas(s->prepainted, u))
- for (i = 0; i < Nmode; i++)
- if (regmap[colourmap[u]][i] && gbhasedge(s, regmap[colourmap[u]][i], v))
- return 1;
- return gbhasedge(s, u, v);
+ size_t i;
+
+ if (bshas(s->prepainted, v))
+ return 1;
+ if (bshas(s->prepainted, u))
+ for (i = 0; i < Nmode; i++)
+ if (regmap[colourmap[u]][i] && gbhasedge(s, regmap[colourmap[u]][i], v))
+ return 1;
+ return gbhasedge(s, u, v);
}
static void coalesce(Isel *s)
{
- Insn *m;
- regid u, v, tmp;
-
- m = lpop(&s->wlmove, &s->nwlmove);
- bsdel(s->wlmoveset, m->uid);
- u = getalias(s, m->args[0]->reg.id);
- v = getalias(s, m->args[1]->reg.id);
-
- if (bshas(s->prepainted, v)) {
- tmp = u;
- u = v;
- v = tmp;
- }
-
- if (u == v) {
- lappend(&s->mcoalesced, &s->nmcoalesced, m);
- wladd(s, u);
- wladd(s, v);
- } else if (constrained(s, u, v)) {
- lappend(&s->mconstrained, &s->nmconstrained, m);
- wladd(s, u);
- wladd(s, v);
- } else if (combinable(s, u, v)) {
- lappend(&s->mcoalesced, &s->nmcoalesced, m);
- combine(s, u, v);
- wladd(s, u);
- } else {
- lappend(&s->mactive, &s->nmactive, m);
- bsput(s->mactiveset, m->uid);
- }
+ Insn *m;
+ regid u, v, tmp;
+
+ m = lpop(&s->wlmove, &s->nwlmove);
+ bsdel(s->wlmoveset, m->uid);
+ u = getalias(s, m->args[0]->reg.id);
+ v = getalias(s, m->args[1]->reg.id);
+
+ if (bshas(s->prepainted, v)) {
+ tmp = u;
+ u = v;
+ v = tmp;
+ }
+
+ if (u == v) {
+ lappend(&s->mcoalesced, &s->nmcoalesced, m);
+ wladd(s, u);
+ wladd(s, v);
+ } else if (constrained(s, u, v)) {
+ lappend(&s->mconstrained, &s->nmconstrained, m);
+ wladd(s, u);
+ wladd(s, v);
+ } else if (combinable(s, u, v)) {
+ lappend(&s->mcoalesced, &s->nmcoalesced, m);
+ combine(s, u, v);
+ wladd(s, u);
+ } else {
+ lappend(&s->mactive, &s->nmactive, m);
+ bsput(s->mactiveset, m->uid);
+ }
}
static int mldel(Insn ***ml, size_t *nml, Bitset *bs, Insn *m)
{
- size_t i;
- if (bshas(bs, m->uid)) {
- bsdel(bs, m->uid);
- for (i = 0; i < *nml; i++) {
- if (m == (*ml)[i]) {
- ldel(ml, nml, i);
- return 1;
- }
- }
- }
- return 0;
+ size_t i;
+ if (bshas(bs, m->uid)) {
+ bsdel(bs, m->uid);
+ for (i = 0; i < *nml; i++) {
+ if (m == (*ml)[i]) {
+ ldel(ml, nml, i);
+ return 1;
+ }
+ }
+ }
+ return 0;
}
static void freezemoves(Isel *s, Loc *u)
{
- size_t i;
- Insn **ml;
- Insn *m;
- size_t nml;
- size_t idx;
- Loc *v;
-
- nml = nodemoves(s, u->reg.id, &ml);
- for (i = 0; i < nml; i++) {
- m = ml[i];
- if (getalias(s, m->args[0]->reg.id) == getalias(s, u->reg.id))
- v = locmap[getalias(s, m->args[1]->reg.id)];
- else
- v = locmap[getalias(s, m->args[0]->reg.id)];
-
- if (!mldel(&s->mactive, &s->nmactive, s->mactiveset, m))
- mldel(&s->wlmove, &s->nwlmove, s->wlmoveset, m);
-
- lappend(&s->mfrozen, &s->nmfrozen, m);
- if (!moverelated(s, v->reg.id) && istrivial(s, v->reg.id)) {
- if (!wlfind(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
- die("Reg %zd not in freeze wl\n", v->reg.id);
- wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
- wlput(&s->wlsimp, &s->nwlsimp, v);
- }
-
- }
- lfree(&ml, &nml);
+ size_t i;
+ Insn **ml;
+ Insn *m;
+ size_t nml;
+ size_t idx;
+ Loc *v;
+
+ nml = nodemoves(s, u->reg.id, &ml);
+ for (i = 0; i < nml; i++) {
+ m = ml[i];
+ if (getalias(s, m->args[0]->reg.id) == getalias(s, u->reg.id))
+ v = locmap[getalias(s, m->args[1]->reg.id)];
+ else
+ v = locmap[getalias(s, m->args[0]->reg.id)];
+
+ if (!mldel(&s->mactive, &s->nmactive, s->mactiveset, m))
+ mldel(&s->wlmove, &s->nwlmove, s->wlmoveset, m);
+
+ lappend(&s->mfrozen, &s->nmfrozen, m);
+ if (!moverelated(s, v->reg.id) && istrivial(s, v->reg.id)) {
+ if (!wlfind(s->wlfreeze, s->nwlfreeze, v->reg.id, &idx))
+ die("Reg %zd not in freeze wl\n", v->reg.id);
+ wldel(s, &s->wlfreeze, &s->nwlfreeze, idx);
+ wlput(&s->wlsimp, &s->nwlsimp, v);
+ }
+
+ }
+ lfree(&ml, &nml);
}
static void freeze(Isel *s)
{
- Loc *l;
+ Loc *l;
- l = lpop(&s->wlfreeze, &s->nwlfreeze);
- wlput(&s->wlsimp, &s->nwlsimp, l);
- freezemoves(s, l);
+ l = lpop(&s->wlfreeze, &s->nwlfreeze);
+ wlput(&s->wlsimp, &s->nwlsimp, l);
+ freezemoves(s, l);
}
/* Select the spill candidates */
static void selspill(Isel *s)
{
- size_t i;
- Loc *m;
-
- /* FIXME: pick a better heuristic for spilling */
- m = NULL;
- for (i = 0; i < s->nwlspill; i++) {
- if (!bshas(s->shouldspill, s->wlspill[i]->reg.id))
- continue;
- m = s->wlspill[i];
- wldel(s, &s->wlspill, &s->nwlspill, i);
- break;
- }
- if (!m) {
- for (i = 0; i < s->nwlspill; i++) {
- if (bshas(s->neverspill, s->wlspill[i]->reg.id)) {
- continue;
- }
- m = s->wlspill[i];
- wldel(s, &s->wlspill, &s->nwlspill, i);
- break;
- }
- }
- assert(m != NULL);
- wlput(&s->wlsimp, &s->nwlsimp, m);
- freezemoves(s, m);
+ size_t i;
+ Loc *m;
+
+ /* FIXME: pick a better heuristic for spilling */
+ m = NULL;
+ for (i = 0; i < s->nwlspill; i++) {
+ if (!bshas(s->shouldspill, s->wlspill[i]->reg.id))
+ continue;
+ m = s->wlspill[i];
+ wldel(s, &s->wlspill, &s->nwlspill, i);
+ break;
+ }
+ if (!m) {
+ for (i = 0; i < s->nwlspill; i++) {
+ if (bshas(s->neverspill, s->wlspill[i]->reg.id)) {
+ continue;
+ }
+ m = s->wlspill[i];
+ wldel(s, &s->wlspill, &s->nwlspill, i);
+ break;
+ }
+ }
+ assert(m != NULL);
+ wlput(&s->wlsimp, &s->nwlsimp, m);
+ freezemoves(s, m);
}
/*
@@ -958,98 +957,98 @@ static void selspill(Isel *s)
*/
static int paint(Isel *s)
{
- int taken[Nreg];
- Loc *n, *w;
- regid l;
- size_t i, j;
- int spilled;
- int found;
-
- spilled = 0;
- while (s->nselstk) {
- memset(taken, 0, Nreg*sizeof(int));
- n = lpop(&s->selstk, &s->nselstk);
-
- for (j = 0; j < s->ngadj[n->reg.id];j++) {
- l = s->gadj[n->reg.id][j];
- if (debugopt['r'] > 1)
- printedge(stdout, "paint-edge:", n->reg.id, l);
- w = locmap[getalias(s, l)];
- if (w->reg.colour)
- taken[colourmap[w->reg.colour]] = 1;
- }
-
- found = 0;
- for (i = 0; i < Northogonal; i++) {
- if (regmap[i][n->mode] && !taken[i]) {
- n->reg.colour = regmap[i][n->mode];
- found = 1;
- break;
- }
- }
- if (!found) {
- spilled = 1;
- wlputset(s->spilled, n->reg.id);
- }
- }
- for (l = 0; bsiter(s->coalesced, &l); l++) {
- n = locmap[getalias(s, l)];
- locmap[l]->reg.colour = n->reg.colour;
- }
- return spilled;
+ int taken[Nreg];
+ Loc *n, *w;
+ regid l;
+ size_t i, j;
+ int spilled;
+ int found;
+
+ spilled = 0;
+ while (s->nselstk) {
+ memset(taken, 0, Nreg*sizeof(int));
+ n = lpop(&s->selstk, &s->nselstk);
+
+ for (j = 0; j < s->ngadj[n->reg.id];j++) {
+ l = s->gadj[n->reg.id][j];
+ if (debugopt['r'] > 1)
+ printedge(stdout, "paint-edge:", n->reg.id, l);
+ w = locmap[getalias(s, l)];
+ if (w->reg.colour)
+ taken[colourmap[w->reg.colour]] = 1;
+ }
+
+ found = 0;
+ for (i = 0; i < Northogonal; i++) {
+ if (regmap[i][n->mode] && !taken[i]) {
+ n->reg.colour = regmap[i][n->mode];
+ found = 1;
+ break;
+ }
+ }
+ if (!found) {
+ spilled = 1;
+ wlputset(s->spilled, n->reg.id);
+ }
+ }
+ for (l = 0; bsiter(s->coalesced, &l); l++) {
+ n = locmap[getalias(s, l)];
+ locmap[l]->reg.colour = n->reg.colour;
+ }
+ return spilled;
}
static Loc *mapfind(Isel *s, Htab *map, Loc *old)
{
- Loc *new;
- Loc *base;
- Loc *idx;
- regid id;
-
- if (!old)
- return NULL;
-
- new = NULL;
- if (old->type == Locreg) {
- id = getalias(s, old->reg.id);
- new = htget(map, locmap[id]);
- } else if (old->type == Locmem || old->type == Locmeml) {
- base = old->mem.base;
- idx = old->mem.idx;
- if (base)
- base = locmap[getalias(s, base->reg.id)];
- if (idx)
- idx = locmap[getalias(s, idx->reg.id)];
- base = mapfind(s, map, base);
- idx = mapfind(s, map, idx);
- if (base != old->mem.base || idx != old->mem.idx) {
- if (old->type == Locmem)
- new = locmems(old->mem.constdisp, base, idx, old->mem.scale, old->mode);
- else
- new = locmemls(old->mem.lbldisp, base, idx, old->mem.scale, old->mode);
- }
- }
- if (new)
- return new;
- return old;
+ Loc *new;
+ Loc *base;
+ Loc *idx;
+ regid id;
+
+ if (!old)
+ return NULL;
+
+ new = NULL;
+ if (old->type == Locreg) {
+ id = getalias(s, old->reg.id);
+ new = htget(map, locmap[id]);
+ } else if (old->type == Locmem || old->type == Locmeml) {
+ base = old->mem.base;
+ idx = old->mem.idx;
+ if (base)
+ base = locmap[getalias(s, base->reg.id)];
+ if (idx)
+ idx = locmap[getalias(s, idx->reg.id)];
+ base = mapfind(s, map, base);
+ idx = mapfind(s, map, idx);
+ if (base != old->mem.base || idx != old->mem.idx) {
+ if (old->type == Locmem)
+ new = locmems(old->mem.constdisp, base, idx, old->mem.scale, old->mode);
+ else
+ new = locmemls(old->mem.lbldisp, base, idx, old->mem.scale, old->mode);
+ }
+ }
+ if (new)
+ return new;
+ return old;
}
static Loc *spillslot(Isel *s, regid reg)
{
- size_t stkoff;
+ size_t stkoff;
- stkoff = ptoi(htget(s->spillslots, itop(reg)));
- return locmem(-stkoff, locphysreg(Rrbp), NULL, locmap[reg]->mode);
+ stkoff = ptoi(htget(s->spillslots, itop(reg)));
+ return locmem(-stkoff, locphysreg(Rrbp), NULL, locmap[reg]->mode);
}
static void updatelocs(Isel *s, Htab *map, Insn *insn)
{
- size_t i;
+ size_t i;
- for (i = 0; i < insn->nargs; i++) {
- insn->args[i] = mapfind(s, map, insn->args[i]);
- insn->args[i] = mapfind(s, map, insn->args[i]);
- }
+ for (i = 0; i < insn->nargs; i++) {
+ insn->args[i] = mapfind(s, map, insn->args[i]);
+ insn->args[i] = mapfind(s, map, insn->args[i]);
+ }
}
/*
@@ -1059,82 +1058,82 @@ static void updatelocs(Isel *s, Htab *map, Insn *insn)
*/
static int remap(Isel *s, Htab *map, Insn *insn, regid *use, size_t nuse, regid *def, size_t ndef)
{
- regid ruse, rdef;
- int remapped;
- Loc *tmp;
- size_t i;
-
- remapped = 0;
- for (i = 0; i < nuse; i++) {
- ruse = getalias(s, use[i]);
- if (!bshas(s->spilled, ruse))
- continue;
- tmp = locreg(locmap[ruse]->mode);
- htput(map, locmap[ruse], tmp);
- bsput(s->neverspill, tmp->reg.id);
- remapped = 1;
- }
-
- for (i = 0; i < ndef; i++) {
- rdef = getalias(s, def[i]);
- if (!bshas(s->spilled, rdef))
- continue;
- if (hthas(map, locmap[rdef]))
- continue;
- tmp = locreg(locmap[rdef]->mode);
- htput(map, locmap[rdef], tmp);
- bsput(s->neverspill, tmp->reg.id);
- remapped = 1;
- }
-
- return remapped;
+ regid ruse, rdef;
+ int remapped;
+ Loc *tmp;
+ size_t i;
+
+ remapped = 0;
+ for (i = 0; i < nuse; i++) {
+ ruse = getalias(s, use[i]);
+ if (!bshas(s->spilled, ruse))
+ continue;
+ tmp = locreg(locmap[ruse]->mode);
+ htput(map, locmap[ruse], tmp);
+ bsput(s->neverspill, tmp->reg.id);
+ remapped = 1;
+ }
+
+ for (i = 0; i < ndef; i++) {
+ rdef = getalias(s, def[i]);
+ if (!bshas(s->spilled, rdef))
+ continue;
+ if (hthas(map, locmap[rdef]))
+ continue;
+ tmp = locreg(locmap[rdef]->mode);
+ htput(map, locmap[rdef], tmp);
+ bsput(s->neverspill, tmp->reg.id);
+ remapped = 1;
+ }
+
+ return remapped;
}
static int nopmov(Insn *insn)
{
- if (insn->op != Imov && insn->op != Imovs)
- return 0;
- if (insn->args[0]->type != Locreg || insn->args[1]->type != Locreg)
- return 0;
- return insn->args[0]->reg.id == insn->args[1]->reg.id;
+ if (insn->op != Imov && insn->op != Imovs)
+ return 0;
+ if (insn->args[0]->type != Locreg || insn->args[1]->type != Locreg)
+ return 0;
+ return insn->args[0]->reg.id == insn->args[1]->reg.id;
}
void replacealias(Isel *s, Loc **map, size_t nreg, Insn *insn)
{
- size_t i;
- Loc *l;
-
- if (!map)
- return;
- for (i = 0; i < insn->nargs; i++) {
- l = insn->args[i];
- if (l->type == Locreg) {
- insn->args[i] = locmap[getalias(s, l->reg.id)];
- } else if (l->type == Locmem || l->type == Locmeml) {
- if (l->mem.base)
- l->mem.base = locmap[getalias(s, l->mem.base->reg.id)];
- if (l->mem.idx)
- l->mem.idx = locmap[getalias(s, l->mem.idx->reg.id)];
- }
- }
+ size_t i;
+ Loc *l;
+
+ if (!map)
+ return;
+ for (i = 0; i < insn->nargs; i++) {
+ l = insn->args[i];
+ if (l->type == Locreg) {
+ insn->args[i] = locmap[getalias(s, l->reg.id)];
+ } else if (l->type == Locmem || l->type == Locmeml) {
+ if (l->mem.base)
+ l->mem.base = locmap[getalias(s, l->mem.base->reg.id)];
+ if (l->mem.idx)
+ l->mem.idx = locmap[getalias(s, l->mem.idx->reg.id)];
+ }
+ }
}
static ulong reglochash(void *p)
{
- Loc *l;
-
- l = p;
- return inthash(l->reg.id);
+ Loc *l;
+
+ l = p;
+ return inthash(l->reg.id);
}
static int regloceq(void *pa, void *pb)
{
- Loc *a, *b;
-
- a = pa;
- b = pb;
- return a->reg.id == b->reg.id;
+ Loc *a, *b;
+
+ a = pa;
+ b = pb;
+ return a->reg.id == b->reg.id;
}
/*
* Rewrite instructions using spilled registers, inserting
@@ -1142,74 +1141,74 @@ static int regloceq(void *pa, void *pb)
*/
static void rewritebb(Isel *s, Asmbb *bb, Loc **aliasmap)
{
- regid use[Nreg], def[Nreg];
- size_t nuse, ndef;
- Insn *insn, *mov;
- size_t i, j;
- Insn **new;
- size_t nnew;
- Htab *map;
- Loc *tmp;
-
- new = NULL;
- nnew = 0;
- if (!bb)
- return;
- map = mkht(reglochash, regloceq);
- for (j = 0; j < bb->ni; j++) {
- insn = bb->il[j];
- replacealias(s, aliasmap, s->nreg, insn);
- if (nopmov(insn))
- continue;
- nuse = uses(insn, use);
- ndef = defs(insn, def);
- /* if there is a remapping, insert the loads and stores as needed */
- if (remap(s, map, insn, use, nuse, def, ndef)) {
- for (i = 0; i < nuse; i++) {
- tmp = htget(map, locmap[use[i]]);
- if (!tmp)
- continue;
- if (isfloatmode(tmp->mode))
- mov = mkinsn(Imovs, spillslot(s, use[i]), tmp, NULL);
- else
- mov = mkinsn(Imov, spillslot(s, use[i]), tmp, NULL);
- lappend(&new, &nnew, mov);
- }
- updatelocs(s, map, insn);
- lappend(&new, &nnew, insn);
- for (i = 0; i < ndef; i++) {
- tmp = htget(map, locmap[def[i]]);
- if (!tmp)
- continue;
- if (isfloatmode(tmp->mode))
- mov = mkinsn(Imovs, tmp, spillslot(s, def[i]), NULL);
- else
- mov = mkinsn(Imov, tmp, spillslot(s, def[i]), NULL);
- lappend(&new, &nnew, mov);
- }
- for (i = 0; i < nuse; i++)
- htdel(map, locmap[use[i]]);
- for (i = 0; i < ndef; i++)
- htdel(map, locmap[def[i]]);
- } else {
- lappend(&new, &nnew, insn);
- }
- }
- lfree(&bb->il, &bb->ni);
- bb->il = new;
- bb->ni = nnew;
+ regid use[Nreg], def[Nreg];
+ size_t nuse, ndef;
+ Insn *insn, *mov;
+ size_t i, j;
+ Insn **new;
+ size_t nnew;
+ Htab *map;
+ Loc *tmp;
+
+ new = NULL;
+ nnew = 0;
+ if (!bb)
+ return;
+ map = mkht(reglochash, regloceq);
+ for (j = 0; j < bb->ni; j++) {
+ insn = bb->il[j];
+ replacealias(s, aliasmap, s->nreg, insn);
+ if (nopmov(insn))
+ continue;
+ nuse = uses(insn, use);
+ ndef = defs(insn, def);
+ /* if there is a remapping, insert the loads and stores as needed */
+ if (remap(s, map, insn, use, nuse, def, ndef)) {
+ for (i = 0; i < nuse; i++) {
+ tmp = htget(map, locmap[use[i]]);
+ if (!tmp)
+ continue;
+ if (isfloatmode(tmp->mode))
+ mov = mkinsn(Imovs, spillslot(s, use[i]), tmp, NULL);
+ else
+ mov = mkinsn(Imov, spillslot(s, use[i]), tmp, NULL);
+ lappend(&new, &nnew, mov);
+ }
+ updatelocs(s, map, insn);
+ lappend(&new, &nnew, insn);
+ for (i = 0; i < ndef; i++) {
+ tmp = htget(map, locmap[def[i]]);
+ if (!tmp)
+ continue;
+ if (isfloatmode(tmp->mode))
+ mov = mkinsn(Imovs, tmp, spillslot(s, def[i]), NULL);
+ else
+ mov = mkinsn(Imov, tmp, spillslot(s, def[i]), NULL);
+ lappend(&new, &nnew, mov);
+ }
+ for (i = 0; i < nuse; i++)
+ htdel(map, locmap[use[i]]);
+ for (i = 0; i < ndef; i++)
+ htdel(map, locmap[def[i]]);
+ } else {
+ lappend(&new, &nnew, insn);
+ }
+ }
+ lfree(&bb->il, &bb->ni);
+ bb->il = new;
+ bb->ni = nnew;
}
static void addspill(Isel *s, Loc *l)
{
- s->stksz->lit += modesize[l->mode];
- s->stksz->lit = align(s->stksz->lit, modesize[l->mode]);
- if (debugopt['r']) {
- printf("spill ");
- dbglocprint(stdout, l, 'x');
- printf(" to %zd(%%rbp)\n", s->stksz->lit);
- }
- htput(s->spillslots, itop(l->reg.id), itop(s->stksz->lit));
+ s->stksz->lit += modesize[l->mode];
+ s->stksz->lit = align(s->stksz->lit, modesize[l->mode]);
+ if (debugopt['r']) {
+ printf("spill ");
+ dbglocprint(stdout, l, 'x');
+ printf(" to %zd(%%rbp)\n", s->stksz->lit);
+ }
+ htput(s->spillslots, itop(l->reg.id), itop(s->stksz->lit));
}
/*
@@ -1226,18 +1225,18 @@ static void addspill(Isel *s, Loc *l)
*/
static void rewrite(Isel *s, Loc **aliasmap)
{
- size_t i;
-
- s->spillslots = mkht(ptrhash, ptreq);
- /* set up stack locations for all spilled registers. */
- for (i = 0; bsiter(s->spilled, &i); i++)
- addspill(s, locmap[i]);
-
- /* rewrite instructions using them */
- for (i = 0; i < s->nbb; i++)
- rewritebb(s, s->bb[i], aliasmap);
- htfree(s->spillslots);
- bsclear(s->spilled);
+ size_t i;
+
+ s->spillslots = mkht(ptrhash, ptreq);
+ /* set up stack locations for all spilled registers. */
+ for (i = 0; bsiter(s->spilled, &i); i++)
+ addspill(s, locmap[i]);
+
+ /* rewrite instructions using them */
+ for (i = 0; i < s->nbb; i++)
+ rewritebb(s, s->bb[i], aliasmap);
+ htfree(s->spillslots);
+ bsclear(s->spilled);
}
/*
@@ -1250,187 +1249,187 @@ static void rewrite(Isel *s, Loc **aliasmap)
*/
static void delnops(Isel *s)
{
- Insn *insn;
- Asmbb *bb;
- Insn **new;
- size_t nnew;
- size_t i, j;
-
- for (i = 0; i < s->nbb; i++) {
- if (!s->bb[i])
- continue;
- new = NULL;
- nnew = 0;
- bb = s->bb[i];
- for (j = 0; j < bb->ni; j++) {
- insn = bb->il[j];
- if (ismove(insn) && insn->args[0]->reg.colour == insn->args[1]->reg.colour)
- continue;
- lappend(&new, &nnew, insn);
- }
- lfree(&bb->il, &bb->ni);
- bb->il = new;
- bb->ni = nnew;
- }
- if (debugopt['r'])
- dumpasm(s, stdout);
+ Insn *insn;
+ Asmbb *bb;
+ Insn **new;
+ size_t nnew;
+ size_t i, j;
+
+ for (i = 0; i < s->nbb; i++) {
+ if (!s->bb[i])
+ continue;
+ new = NULL;
+ nnew = 0;
+ bb = s->bb[i];
+ for (j = 0; j < bb->ni; j++) {
+ insn = bb->il[j];
+ if (ismove(insn) && insn->args[0]->reg.colour == insn->args[1]->reg.colour)
+ continue;
+ lappend(&new, &nnew, insn);
+ }
+ lfree(&bb->il, &bb->ni);
+ bb->il = new;
+ bb->ni = nnew;
+ }
+ if (debugopt['r'])
+ dumpasm(s, stdout);
}
void regalloc(Isel *s)
{
- int spilled;
- size_t i;
- Loc **aliasmap;
-
- /* Initialize the list of prepainted registers */
- s->prepainted = mkbs();
- bsput(s->prepainted, 0);
- for (i = 0; i < Nreg; i++)
- bsput(s->prepainted, i);
-
- s->shouldspill = mkbs();
- s->neverspill = mkbs();
- s->initial = mkbs();
- for (i = 0; i < s->nsaved; i++)
- bsput(s->shouldspill, s->calleesave[i]->reg.id);
- do {
- aliasmap = NULL;
- setup(s);
- liveness(s);
- build(s);
- mkworklist(s);
- if (debugopt['r'])
- dumpasm(s, stdout);
- do {
- if (s->nwlsimp)
- simp(s);
- else if (s->nwlmove)
- coalesce(s);
- else if (s->nwlfreeze)
- freeze(s);
- else if (s->nwlspill) {
- if (!aliasmap)
- aliasmap = memdup(s->aliasmap, s->nreg * sizeof(Loc*));
- selspill(s);
- }
- } while (s->nwlsimp || s->nwlmove || s->nwlfreeze || s->nwlspill);
- spilled = paint(s);
- if (spilled)
- rewrite(s, aliasmap);
- } while (spilled);
- delnops(s);
- bsfree(s->prepainted);
- bsfree(s->shouldspill);
- bsfree(s->neverspill);
- gfree(s);
+ int spilled;
+ size_t i;
+ Loc **aliasmap;
+
+ /* Initialize the list of prepainted registers */
+ s->prepainted = mkbs();
+ bsput(s->prepainted, 0);
+ for (i = 0; i < Nreg; i++)
+ bsput(s->prepainted, i);
+
+ s->shouldspill = mkbs();
+ s->neverspill = mkbs();
+ s->initial = mkbs();
+ for (i = 0; i < s->nsaved; i++)
+ bsput(s->shouldspill, s->calleesave[i]->reg.id);
+ do {
+ aliasmap = NULL;
+ setup(s);
+ liveness(s);
+ build(s);
+ mkworklist(s);
+ if (debugopt['r'])
+ dumpasm(s, stdout);
+ do {
+ if (s->nwlsimp)
+ simp(s);
+ else if (s->nwlmove)
+ coalesce(s);
+ else if (s->nwlfreeze)
+ freeze(s);
+ else if (s->nwlspill) {
+ if (!aliasmap)
+ aliasmap = memdup(s->aliasmap, s->nreg * sizeof(Loc*));
+ selspill(s);
+ }
+ } while (s->nwlsimp || s->nwlmove || s->nwlfreeze || s->nwlspill);
+ spilled = paint(s);
+ if (spilled)
+ rewrite(s, aliasmap);
+ } while (spilled);
+ delnops(s);
+ bsfree(s->prepainted);
+ bsfree(s->shouldspill);
+ bsfree(s->neverspill);
+ gfree(s);
}
void wlprint(FILE *fd, char *name, Loc **wl, size_t nwl)
{
- size_t i;
- char *sep;
-
- sep = "";
- fprintf(fd, "%s = [", name);
- for (i = 0; i < nwl; i++) {
- fprintf(fd, "%s", sep);
- dbglocprint(fd, wl[i], 'x');
- fprintf(fd, "(%zd)", wl[i]->reg.id);
- sep = ",";
- }
- fprintf(fd, "]\n");
+ size_t i;
+ char *sep;
+
+ sep = "";
+ fprintf(fd, "%s = [", name);
+ for (i = 0; i < nwl; i++) {
+ fprintf(fd, "%s", sep);
+ dbglocprint(fd, wl[i], 'x');
+ fprintf(fd, "(%zd)", wl[i]->reg.id);
+ sep = ",";
+ }
+ fprintf(fd, "]\n");
}
static void setprint(FILE *fd, Bitset *s)
{
- char *sep;
- size_t i;
-
- sep = "";
- for (i = 0; i < bsmax(s); i++) {
- if (bshas(s, i)) {
- fprintf(fd, "%s%zd", sep, i);
- sep = ",";
- }
- }
- fprintf(fd, "\n");
+ char *sep;
+ size_t i;
+
+ sep = "";
+ for (i = 0; i < bsmax(s); i++) {
+ if (bshas(s, i)) {
+ fprintf(fd, "%s%zd", sep, i);
+ sep = ",";
+ }
+ }
+ fprintf(fd, "\n");
}
static void locsetprint(FILE *fd, Bitset *s)
{
- char *sep;
- size_t i;
-
- sep = "";
- for (i = 0; i < bsmax(s); i++) {
- if (bshas(s, i)) {
- fprintf(fd, "%s", sep);
- dbglocprint(fd, locmap[i], 'x');
- sep = ",";
- }
- }
- fprintf(fd, "\n");
+ char *sep;
+ size_t i;
+
+ sep = "";
+ for (i = 0; i < bsmax(s); i++) {
+ if (bshas(s, i)) {
+ fprintf(fd, "%s", sep);
+ dbglocprint(fd, locmap[i], 'x');
+ sep = ",";
+ }
+ }
+ fprintf(fd, "\n");
}
static void printedge(FILE *fd, char *msg, size_t a, size_t b)
{
- fprintf(fd, "\t%s ", msg);
- dbglocprint(fd, locmap[a], 'x');
- fprintf(fd, " -- ");
- dbglocprint(fd, locmap[b], 'x');
- fprintf(fd, "\n");
+ fprintf(fd, "\t%s ", msg);
+ dbglocprint(fd, locmap[a], 'x');
+ fprintf(fd, " -- ");
+ dbglocprint(fd, locmap[b], 'x');
+ fprintf(fd, "\n");
}
void dumpasm(Isel *s, FILE *fd)
{
- size_t i, j;
- char *sep;
- Asmbb *bb;
-
- fprintf(fd, "WORKLISTS -- \n");
- wlprint(stdout, "spill", s->wlspill, s->nwlspill);
- wlprint(stdout, "simp", s->wlsimp, s->nwlsimp);
- wlprint(stdout, "freeze", s->wlfreeze, s->nwlfreeze);
- /* noisy to dump this all the time; only dump for higher debug levels */
- if (debugopt['r'] > 2) {
- fprintf(fd, "IGRAPH ----- \n");
- for (i = 0; i < s->nreg; i++) {
- for (j = i; j < s->nreg; j++) {
- if (gbhasedge(s, i, j))
- printedge(stdout, "", i, j);
- }
- }
- }
- fprintf(fd, "ASM -------- \n");
- for (j = 0; j < s->nbb; j++) {
- bb = s->bb[j];
- if (!bb)
- continue;
- fprintf(fd, "\n");
- fprintf(fd, "Bb: %d labels=(", bb->id);
- sep = "";
- for (i = 0; i < bb->nlbls; i++) {;
- fprintf(fd, "%s%s", bb->lbls[i], sep);
- sep = ",";
- }
- fprintf(fd, ")\n");
-
- fprintf(fd, "Pred: ");
- setprint(fd, bb->pred);
- fprintf(fd, "Succ: ");
- setprint(fd, bb->succ);
-
- fprintf(fd, "Use: ");
- locsetprint(fd, bb->use);
- fprintf(fd, "Def: ");
- locsetprint(fd, bb->def);
- fprintf(fd, "Livein: ");
- locsetprint(fd, bb->livein);
- fprintf(fd, "Liveout: ");
- locsetprint(fd, bb->liveout);
- for (i = 0; i < bb->ni; i++)
- dbgiprintf(fd, bb->il[i]);
- }
- fprintf(fd, "ENDASM -------- \n");
+ size_t i, j;
+ char *sep;
+ Asmbb *bb;
+
+ fprintf(fd, "WORKLISTS -- \n");
+ wlprint(stdout, "spill", s->wlspill, s->nwlspill);
+ wlprint(stdout, "simp", s->wlsimp, s->nwlsimp);
+ wlprint(stdout, "freeze", s->wlfreeze, s->nwlfreeze);
+ /* noisy to dump this all the time; only dump for higher debug levels */
+ if (debugopt['r'] > 2) {
+ fprintf(fd, "IGRAPH ----- \n");
+ for (i = 0; i < s->nreg; i++) {
+ for (j = i; j < s->nreg; j++) {
+ if (gbhasedge(s, i, j))
+ printedge(stdout, "", i, j);
+ }
+ }
+ }
+ fprintf(fd, "ASM -------- \n");
+ for (j = 0; j < s->nbb; j++) {
+ bb = s->bb[j];
+ if (!bb)
+ continue;
+ fprintf(fd, "\n");
+ fprintf(fd, "Bb: %d labels=(", bb->id);
+ sep = "";
+ for (i = 0; i < bb->nlbls; i++) {;
+ fprintf(fd, "%s%s", bb->lbls[i], sep);
+ sep = ",";
+ }
+ fprintf(fd, ")\n");
+
+ fprintf(fd, "Pred: ");
+ setprint(fd, bb->pred);
+ fprintf(fd, "Succ: ");
+ setprint(fd, bb->succ);
+
+ fprintf(fd, "Use: ");
+ locsetprint(fd, bb->use);
+ fprintf(fd, "Def: ");
+ locsetprint(fd, bb->def);
+ fprintf(fd, "Livein: ");
+ locsetprint(fd, bb->livein);
+ fprintf(fd, "Liveout: ");
+ locsetprint(fd, bb->liveout);
+ for (i = 0; i < bb->ni; i++)
+ dbgiprintf(fd, bb->il[i]);
+ }
+ fprintf(fd, "ENDASM -------- \n");
}