ref: 576fba41b7b07b0736386f980163c285ebdf1be3
parent: 017a4c99e5701996225fb75f9edb27a434b81bf4
author: Ori Bernstein <ori@eigenstate.org>
date: Sat May 5 12:39:37 EDT 2012
More work on instruction selector.
--- a/8/asm.h
+++ b/8/asm.h
@@ -56,4 +56,4 @@
int narg;
};
-void genasm(Node **nl, int nn);
+void genasm(Fn *fn);
--- a/8/gen.h
+++ b/8/gen.h
@@ -19,7 +19,12 @@
struct Fn {
char *name; /* assembly name; mangled */
+ int isglobl;
+ /* filled in by the lowering process */
+ size_t stksz;
+ Htab *locs;
+
Htab *bbnames; /* char* => Bb* map */
Bb *start;
Bb *end;
@@ -26,11 +31,15 @@
Bb *cur;
Bb **bb;
size_t nbb;
-
/* we can't know all the edges as we
* construct the bb list, so we fix up later */
Bb **fixup;
size_t nfixup;
+
+ /* FIXME: do we want the node list raw here? For now, it's here. */
+ Node **nl;
+ size_t nn;
+
};
struct Bb {
--- a/8/insns.def
+++ b/8/insns.def
@@ -10,22 +10,40 @@
preceeding it is the operand desired for
the mode.
%v - a value (ie, immediate integer or label)
+ Currently, there aren't any attrs, because none were needed yet.
+ Eventually, they'll probably include flag setting and so on.
*/
/* Note, the mov instruction is specified in an overly general manner. */
-Insn(Imov, "\tmov%t %x,%x\n", 0)
-Insn(Imovz, "\tmovz%0t%1t %x,%x\n", 0)
-Insn(Imovs, "\tmovs%0t%1t %x,%x\n", 0)
+Insn(Imov, "\tmov%t %x,%x\n", 0)
+Insn(Imovz, "\tmovz%0t%1t %x,%x\n", 0)
+Insn(Imovs, "\tmovs%0t%1t %x,%x\n", 0)
-Insn(Iadd, "\tadd%t %r,%x\n", 0)
-Insn(Isub, "\tsub%t %r,%x\n", 0)
-Insn(Ipush, "\tpush%t %r\n", 0)
-Insn(Ipop, "\tpop%t %r\n", 0)
+Insn(Iadd, "\tadd%t %r,%x\n", 0)
+Insn(Isub, "\tsub%t %r,%x\n", 0)
+Insn(Ipush, "\tpush%t %r\n", 0)
+Insn(Ipop, "\tpop%t %r\n", 0)
+Insn(Itest, "\ttest%t %r,%r", 0)
+Insn(Icmp, "\tcmp%t %r,%r", 0)
/* branch instructions */
-Insn(Ijmp, "\tjmp %v\n", 0)
-Insn(Iret, "\tret\n", 0)
+Insn(Isetz, "\tsetz\n", 0)
+Insn(Isetnz, "\tsetnz\n", 0)
+Insn(Isetlt, "\tsetlt\n", 0)
+Insn(Isetle, "\tsetle\n", 0)
+Insn(Isetgt, "\tsetgt\n", 0)
+Insn(Isetge, "\tsetge\n", 0)
+/* branch instructions */
+Insn(Ijmp, "\tjmp\n", 0)
+Insn(Ijz, "\tjz\n", 0)
+Insn(Ijnz, "\tjnz\n", 0)
+Insn(Ijlt, "\tjlt\n", 0)
+Insn(Ijle, "\tjle\n", 0)
+Insn(Ijgt, "\tjgt\n", 0)
+Insn(Ijge, "\tjge\n", 0)
+Insn(Iret, "\tret\n", 0)
+
/* not really an insn... */
-Insn(Ilbl, "%v:\n", 0)
+Insn(Ilbl, "%v:\n", 0)
--- a/8/isel.c
+++ b/8/isel.c
@@ -14,12 +14,15 @@
#include "gen.h"
#include "asm.h"
+/* instruction selection state */
typedef struct Isel Isel;
struct Isel {
Insn **il;
size_t ni;
+ Htab *locs; /* Node => int stkoff */
};
+/* string tables */
char *regnames[] = {
#define Reg(r, name, mode) name,
#include "regs.def"
@@ -38,7 +41,26 @@
#undef Insn
};
+/* used to decide which operator is appropriate
+ * for implementing various conditional operators */
+struct {
+ AsmOp test;
+ AsmOp jmp;
+ AsmOp getflag;
+} reloptab[Numops] = {
+ [Oeq] = {Itest, Ijnz, Isetnz},
+ [One] = {Itest, Ijz, Isetz},
+ [Ogt] = {Icmp, Ijgt, Isetgt},
+ [Oge] = {Icmp, Ijge, Isetge},
+ [Olt] = {Icmp, Ijlt, Isetlt},
+ [Ole] = {Icmp, Ijle, Isetle}
+};
+
+/* forward decls */
+Loc selexpr(Isel *s, Node *n);
+
+
Loc *loclbl(Loc *l, char *lbl)
{
l->type = Loclbl;
@@ -113,6 +135,36 @@
return ModeL;
}
+Loc coreg(Loc r, Mode m)
+{
+ Loc l;
+
+ Reg crtab[][4] = {
+ [Ral] = {Ral, Rax, Reax},
+ [Rcl] = {Rcl, Rcx, Recx},
+ [Rdl] = {Rdl, Rdx, Redx},
+ [Rbl] = {Rbl, Rbx, Rebx},
+
+ [Rax] = {Ral, Rax, Reax},
+ [Rcx] = {Rcl, Rcx, Recx},
+ [Rdx] = {Rdl, Rdx, Redx},
+ [Rbx] = {Rbl, Rbx, Rebx},
+ [Rsi] = {0, Rsi, Resi},
+ [Rdi] = {0, Rdi, Redi},
+
+ [Reax] = {Ral, Rax, Reax},
+ [Recx] = {Rcl, Rcx, Recx},
+ [Redx] = {Rdl, Rdx, Redx},
+ [Rebx] = {Rbl, Rbx, Rebx},
+ [Resi] = {0, Rsi, Resi},
+ [Redi] = {0, Rdi, Redi},
+ };
+ if (r.type != Locreg)
+ die("Non-reg passed to coreg()");
+ locreg(&l, crtab[r.reg][m]);
+ return l;
+}
+
Loc getreg(Isel *s, Mode m)
{
Loc l;
@@ -157,9 +209,56 @@
lappend(&s->il, &s->ni, i);
}
+void mov(Isel *s, Loc *a, Loc *b)
+{
+ if (a->type == Locreg && b->type == Locreg)
+ if (a->reg == b->reg)
+ return;
+ g(s, Imov, a, b, NULL);
+}
+
+
+/* If we're testing equality, etc, it's a bit silly
+ * to generate the test, store it to a bite, expand it
+ * to the right width, and then test it again. Try to optimize
+ * for these common cases.
+ *
+ * if we're doing the optimization to avoid
+ * multiple tests, we want to eval the children
+ * of the first arg, instead of the first arg
+ * directly */
+void selcjmp(Isel *s, Node *n, Node **args)
+{
+ Loc a, b;
+ Loc l1, l2;
+ AsmOp cond, jmp;
+
+ cond = reloptab[exprop(n)].test;
+ jmp = reloptab[exprop(n)].jmp;
+ /* if we have a cond, we're knocking off the redundant test,
+ * and want to eval the children */
+ if (cond) {
+ a = selexpr(s, args[0]->expr.args[0]);
+ b = selexpr(s, args[0]->expr.args[1]);
+ } else {
+ cond = Itest;
+ jmp = Ijnz;
+ a = selexpr(s, args[0]); /* cond */
+ b = a;
+ }
+
+ /* the jump targets will always be evaluated the same way */
+ l1 = selexpr(s, args[1]); /* if true */
+ l2 = selexpr(s, args[2]); /* if false */
+
+ g(s, cond, &a, &b, NULL);
+ g(s, jmp, &l1, NULL);
+ g(s, Ijmp, &l2, NULL);
+}
+
Loc selexpr(Isel *s, Node *n)
{
- Loc a, b, r;
+ Loc a, b, c, r;
Node **args;
args = n->expr.args;
@@ -194,42 +293,51 @@
case Oaddr: die("Unimplemented op %s", opstr(exprop(n))); break;
case Oderef: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Oeq: die("Unimplemented op %s", opstr(exprop(n))); break;
- case One: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Ogt: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Oge: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Olt: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Ole: die("Unimplemented op %s", opstr(exprop(n))); break;
+ case Oeq: case One: case Ogt: case Oge: case Olt: case Ole:
+ a = selexpr(s, args[0]);
+ b = selexpr(s, args[1]);
+ c = getreg(s, ModeB);
+ r = coreg(c, mode(n));
+ g(s, reloptab[exprop(n)].test, &a, &b, NULL);
+ g(s, reloptab[exprop(n)].getflag, &c, NULL);
+ g(s, Imovz, &c, &r);
+ return r;
case Oasn:
a = selexpr(s, args[0]);
b = selexpr(s, args[1]);
- g(s, Imov, &b, &a, NULL);
+ mov(s, &b, &a);
r = b;
break;
- case Oidx: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Oslice: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Osize: die("Unimplemented op %s", opstr(exprop(n))); break;
case Ocall: die("Unimplemented op %s", opstr(exprop(n))); break;
case Ocast: die("Unimplemented op %s", opstr(exprop(n))); break;
case Ojmp:
g(s, Ijmp, loclbl(&a, args[0]->lbl.name), NULL);
break;
- case Ocjmp: die("Unimplemented op %s", opstr(exprop(n))); break;
- case Olit:
+ case Ocjmp:
+ selcjmp(s, n, args);
+ break;
+
+ case Olit: /* fall through */
case Ovar:
- a = loc(s, n);
- b = getreg(s, mode(args[0]));
- g(s, Imov, &a, &b, NULL);
+ b = loc(s, n);
+ a = getreg(s, mode(args[0]));
+ mov(s, &b, &a);
r = b;
break;
- case Olbl: die("Unimplemented op %s", opstr(exprop(n))); break;
+ case Olbl:
+ loclbl(&r, args[0]->lbl.name);
+ break;
+ /* These operators should never show up in the reduced trees,
+ * since they should have been replaced with more primitive
+ * expressions by now */
case Obad: case Oret: case Opreinc: case Opostinc: case Opredec:
case Opostdec: case Olor: case Oland: case Olnot: case Oaddeq:
case Osubeq: case Omuleq: case Odiveq: case Omodeq: case Oboreq:
case Obandeq: case Obxoreq: case Obsleq: case Obsreq: case Omemb:
+ case Oslice: case Oidx: case Osize: case Numops:
die("Should not see %s in isel", opstr(exprop(n)));
break;
}
@@ -340,43 +448,51 @@
}
}
-void prologue(Isel *s)
+void prologue(Isel *s, size_t sz)
{
- Loc resp;
- Loc rebp;
+ Loc esp;
+ Loc ebp;
Loc stksz;
- locreg(&resp, Resp);
- locreg(&rebp, Rebp);
- loclit(&stksz, 16);
- g(s, Ipush, &rebp, NULL);
- g(s, Imov, &resp, &rebp, NULL);
- g(s, Isub, &stksz, &resp, NULL);
+ locreg(&esp, Resp);
+ locreg(&ebp, Rebp);
+ loclit(&stksz, sz);
+ g(s, Ipush, &ebp, NULL);
+ g(s, Imov, &esp, &ebp, NULL);
+ g(s, Isub, &stksz, &esp, NULL);
}
void epilogue(Isel *s)
{
- Loc resp;
- Loc rebp;
+ Loc esp;
+ Loc ebp;
Loc stksz;
- locreg(&resp, Resp);
- locreg(&rebp, Rebp);
+ locreg(&esp, Resp);
+ locreg(&ebp, Rebp);
loclit(&stksz, 16);
- g(s, Imov, &rebp, &resp, NULL);
- g(s, Ipop, &rebp, NULL);
+ g(s, Imov, &ebp, &esp, NULL);
+ g(s, Ipop, &ebp, NULL);
}
-void genasm(Node **nl, int nn)
+/* genasm requires all nodes in 'nl' to map cleanly to operations that are
+ * natively supported, as promised in the output of reduce(). No 64-bit
+ * operations on x32, no structures, and so on. */
+void genasm(Fn *fn)
{
struct Isel is = {0,};
int i;
- prologue(&is);
- for (i = 0; i < nn; i++)
- isel(&is, nl[i]);
+ is.locs = fn->locs;
+
+ prologue(&is, fn->stksz);
+ for (i = 0; i < fn->nn; i++)
+ isel(&is, fn->nl[i]);
epilogue(&is);
+ if (fn->isglobl)
+ fprintf(stdout, ".globl %s\n", fn->name);
+ fprintf(stdout, "%s:\n", fn->name);
for (i = 0; i < is.ni; i++)
iprintf(stdout, is.il[i]);
}
--- a/8/simp.c
+++ b/8/simp.c
@@ -22,6 +22,7 @@
f = zalloc(sizeof(Fn));
f->name = strdup(name);
+ f->isglobl = 1;
return f;
}
@@ -65,7 +66,6 @@
/* lower */
fn = mkfn(name);
- fn = zalloc(sizeof(Fn));
fn->name = strdup(name);
nl = reduce(n->func.body, &nn);
@@ -74,7 +74,9 @@
dump(nl[i], stdout);
}
- genasm(nl, nn);
+ fn->nl = nl;
+ fn->nn = nn;
+ genasm(fn);
}
int isconstfn(Sym *s)
--- a/parse/parse.h
+++ b/parse/parse.h
@@ -19,6 +19,7 @@
typedef enum {
#define O(op) op,
#include "ops.def"
+ Numops,
#undef O
} Op;