ref: 36a3a5fa99dc4887ca46c7807436ad44da19422f
parent: 04a014003d9dc62fc5fe80ad51958a39bb9d2f2a
author: Ori Bernstein <[email protected]>
date: Fri May 4 17:40:37 EDT 2012
Work towards generating assembly.
New reduction and start of instruction selection code.
--- a/8/Makefile
+++ b/8/Makefile
@@ -1,7 +1,8 @@
BIN=8m
-OBJ=main.o \
+OBJ=isel.o \
+ main.o \
simp.o \
- gen.o \
+ reduce.o \
CFLAGS+=-I../parse
LDFLAGS+=-L../parse -lparse
--- /dev/null
+++ b/8/asm.h
@@ -1,0 +1,56 @@
+#define MaxArg 4
+
+typedef enum {+#define Insn(val, fmt, attr) val,
+#include "insns.def"
+#undef Insn
+} AsmOp;
+
+typedef enum {+#define Reg(r, name) r,
+#include "regs.def"
+#undef Reg
+} Reg;
+
+
+typedef enum {+ Loclbl,
+ Locreg,
+ Locmem,
+ Locmeml, /* label offset */
+ Loclit,
+} LocType;
+
+typedef enum {+ ModeB,
+ ModeS,
+ ModeL,
+ ModeQ,
+} Mode;
+
+typedef struct Insn Insn;
+typedef struct Loc Loc;
+
+struct Loc {+ LocType type;
+ Mode mode;
+ union {+ char *lbl;
+ Reg reg;
+ long lit;
+ /* disp(base + index) */
+ struct {+ /* only one of lbldisp and constdisp may be used */
+ char *lbldisp;
+ long constdisp;
+ Reg base;
+ Reg idx;
+ } mem;
+ };
+};
+
+struct Insn {+ AsmOp op;
+ Loc args[MaxArg];
+ int nloc;
+};
--- a/8/gen.c
+++ /dev/null
@@ -1,2 +1,0 @@
-
-
--- a/8/gen.h
+++ b/8/gen.h
@@ -57,3 +57,4 @@
Fn *mkfn(char *name);
Bb *mkbb(void);
void edge(Bb *from, Bb *to);
+Node **reduce(Node *n, int *ret_nn);
--- /dev/null
+++ b/8/insns.def
@@ -1,0 +1,26 @@
+/* Table of instructions. Each instruction
+ is defined by the following macro:
+ Insn(enumval, fmt, attr)
+ The format string 'fmt' has the following expansions:
+ %r - A register
+ %m - A memory location.
+ %l - A location (either register or memory)
+ %x - Any value.
+ %[0-9]*t - Mode of an operand. The optional number
+ preceeding it is the operand desired for
+ the mode.
+ %v - a value (ie, immediate integer or label)
+
+ */
+
+/* Note, the mov instruction is specified in an overly general manner. */
+Insn(Imov, "mov%m %x,%x", 0)
+Insn(Imovz, "movz%0m%1m %x,%x", 0)
+Insn(Imovs, "movs%0m%1m %x,%x", 0)
+
+/* arithmetic instructions. */
+Insn(Iadd, "add%m %r,%x", 0)
+Insn(Iret, "ret", 0)
+
+/* not really an insn... */
+Insn(Ilbl, "%s:", 0)
--- /dev/null
+++ b/8/isel.c
@@ -1,0 +1,190 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <ctype.h>
+#include <string.h>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "parse.h"
+#include "gen.h"
+#include "asm.h"
+
+typedef struct Isel Isel;
+struct Isel {+ Insn **il;
+ size_t ni;
+};
+
+char *regnames[] = {+#define Reg(r, name) name,
+#include "regs.def"
+#undef Reg
+};
+
+char *insnfmts[] = {+#define Insn(val, fmt, attr) fmt,
+#include "insns.def"
+#undef Insn
+};
+
+void selexpr(Node *n)
+{+ switch (exprop(n)) {+ case Obad:
+ case Oadd:
+ case Osub:
+ case Omul:
+ case Odiv:
+ case Omod:
+ case Oneg:
+ case Obor:
+ case Oband:
+ case Obxor:
+ case Obsl:
+ case Obsr:
+ case Obnot:
+ case Opreinc:
+ case Opostinc:
+ case Opredec:
+ case Opostdec:
+ case Oaddr:
+ case Oderef:
+ case Olor:
+ case Oland:
+ case Olnot:
+ case Oeq:
+ case One:
+ case Ogt:
+ case Oge:
+ case Olt:
+ case Ole:
+ case Oasn:
+ case Oaddeq:
+ case Osubeq:
+ case Omuleq:
+ case Odiveq:
+ case Omodeq:
+ case Oboreq:
+ case Obandeq:
+ case Obxoreq:
+ case Obsleq:
+ case Obsreq:
+ case Oidx:
+ case Oslice:
+ case Omemb:
+ case Osize:
+ case Ocall:
+ case Ocast:
+ case Oret:
+ case Ojmp:
+ case Ocjmp:
+ case Ovar:
+ case Olit:
+ case Olbl:
+ break;
+ }
+}
+
+void ilbl(Isel *s, char *name)
+{+}
+
+void locprint(FILE *fd, Loc *l)
+{+
+ switch (l->type) {+ case Loclbl:
+ fprintf(fd, "%s", l->lbl);
+ break;
+ case Locreg:
+ fprintf(fd, "%s", regnames[l->reg]);
+ break;
+ case Locmem:
+ case Locmeml:
+ if (l->type == Locmem) {+ if (l->mem.constdisp)
+ fprintf(fd, "%ld", l->mem.constdisp);
+ } else {+ if (l->mem.lbldisp)
+ fprintf(fd, "%s", l->mem.lbldisp);
+ }
+ if (l->mem.base)
+ fprintf(fd, "(%s", regnames[l->mem.base]);
+ if (l->mem.idx)
+ fprintf(fd, ",%s", regnames[l->mem.idx]);
+ if (l->mem.base)
+ fprintf(fd, ")");
+ break;
+ break;
+ case Loclit:
+ break;
+ }
+}
+
+void modeprint(FILE *fd, Loc *l)
+{+ char mode[] = {'b', 's', 'l', 'q'};+ fputc(mode[l->mode], fd);
+}
+
+void iprintf(FILE *fd, Insn *insn)
+{+ char *p;
+ int i;
+ int modeidx;
+
+ p = insnfmts[insn->op];
+ for (; *p; p++) {+ if (*p != '%') {+ fputc(*p, fd);
+ continue;
+ }
+
+ /* %-formating */
+ p++;
+ switch (*p) {+ case '\0':
+ goto done;
+ case 'r':
+ case 'm':
+ case 'l':
+ case 'x':
+ case 'v':
+ locprint(fd, &insn->args[i]);
+ i++;
+ break;
+ case 't':
+ default:
+ if (isdigit(*p))
+ modeidx = strtol(p, &p, 10);
+ else
+ modeidx = 0;
+ modeprint(fd, &insn->args[modeidx]);
+ break;
+ }
+ }
+done:
+ return;
+}
+
+void isel(Node *n)
+{+ struct Isel is = {0,};+ switch (n->type) {+ case Nlbl:
+ ilbl(&is, n->lbl.name);
+ break;
+ case Nexpr:
+ selexpr(n);
+ break;
+ case Ndecl:
+ break;
+ default:
+ die("Bad node type in isel()");+ break;
+ }
+}
--- /dev/null
+++ b/8/reduce.c
@@ -1,0 +1,249 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <ctype.h>
+#include <string.h>
+#include <assert.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+#include "parse.h"
+#include "gen.h"
+
+
+/* takes a list of nodes, and reduces it (and it's subnodes) to a list
+ * following these constraints:
+ * - All nodes are expression nodes
+ * - Nodes with side effects are root nodes
+ * - All nodes operate on machine-primitive types and tuples
+ */
+typedef struct Simp Simp;
+struct Simp {+ Node **blk;
+ size_t nblk;
+ Node *endlbl;
+ Node *retval;
+};
+
+Node *simp(Simp *s, Node *n);
+
+void append(Simp *s, Node *n)
+{+ lappend(&s->blk, &s->nblk, n);
+}
+
+int isimpure(Node *n)
+{+ return 0;
+}
+
+Node *genlbl(void)
+{+ char buf[128];
+ static int nextlbl;
+
+ snprintf(buf, 128, ".L%d", nextlbl++);
+ return mklbl(-1, buf);
+}
+
+Node *temp(Node *e)
+{+ char buf[128];
+ static int nexttmp;
+ Node *n;
+ Node *t;
+ Sym *s;
+
+ assert(e->type == Nexpr);
+ snprintf(buf, 128, ".t%d", nexttmp++);
+ n = mkname(-1, buf);
+ s = mksym(-1, n, e->expr.type);
+ t = mkdecl(-1, s);
+ return mkexpr(-1, Ovar, t, NULL);
+}
+
+void cjmp(Simp *s, Node *cond, Node *iftrue, Node *iffalse)
+{+ Node *jmp;
+
+ jmp = mkexpr(-1, Ocjmp, cond, iftrue, iffalse, NULL);
+ append(s, jmp);
+}
+
+void jmp(Simp *s, Node *lbl)
+{+ append(s, mkexpr(-1, Ojmp, lbl, NULL));
+}
+
+Node *store(Node *t, Node *n)
+{+ return mkexpr(-1, Oasn, t, n, NULL);
+}
+
+Node *storetmp(Node *n)
+{+ return store(temp(n), n);
+}
+
+/* if foo; bar; else baz;;
+ * => cjmp (foo) :bar :baz */
+void simpif(Simp *s, Node *n)
+{+ Node *l1, *l2;
+ Node *c;
+
+ l1 = genlbl();
+ l2 = genlbl();
+ c = simp(s, n->ifstmt.cond);
+ cjmp(s, c, l1, l2);
+ simp(s, l1);
+ simp(s, n->ifstmt.iftrue);
+ simp(s, l2);
+ simp(s, n->ifstmt.iffalse);
+}
+
+/* init; while cond; body;;
+ * => init
+ * jmp :cond
+ * :body
+ * ...body...
+ * :cond
+ * ...cond...
+ * cjmp (cond) :body :end
+ * :end
+ */
+void simploop(Simp *s, Node *n)
+{+ Node *lbody;
+ Node *lend;
+ Node *lcond;
+ Node *c;
+
+ lbody = genlbl();
+ lcond = genlbl();
+ lend = genlbl();
+
+ simp(s, n->loopstmt.init);
+ jmp(s, lcond);
+ simp(s, lbody);
+ simp(s, n->loopstmt.body);
+ simp(s, n->loopstmt.step);
+ simp(s, lcond);
+ c = simp(s, n->loopstmt.cond);
+ cjmp(s, c, lbody, lend);
+ simp(s, lend);
+}
+
+void simpblk(Simp *s, Node *n)
+{+ int i;
+ Node *e;
+
+ for (i = 0; i < n->block.nstmts; i++) {+ e = simp(s, n->block.stmts[i]);
+ append(s, e);
+ }
+}
+
+Node *simpexpr(Simp *s, Node *n)
+{+ Node *r, *t;
+ int i;
+
+ switch (exprop(n)) {+ case Ovar:
+ break;
+ case Oret:
+ if (n->expr.args[0]) {+ t = storetmp(simp(s, n->expr.args[0]));
+ append(s, t);
+ }
+ jmp(s, s->endlbl);
+ break;
+ default:
+ if (isimpure(n)) {+ r = simp(s, n);
+ t = storetmp(r);
+ append(s, t);
+ return t;
+ } else {+ for (i = 0; i < n->expr.nargs; i++)
+ n->expr.args[i] = simp(s, n->expr.args[i]);
+ }
+ }
+ return n;
+}
+
+Node *simp(Simp *s, Node *n)
+{+ Node *r;
+
+ r = NULL;
+ switch (n->type) {+ case Nblock:
+ simpblk(s, n);
+ break;
+ case Nifstmt:
+ simpif(s, n);
+ break;
+ case Nloopstmt:
+ simploop(s, n);
+ break;
+ case Nexpr:
+ r = simpexpr(s, n);
+ break;
+ case Nlit:
+ r = n;
+ break;
+ case Ndecl:
+ //declare(s, n);
+ break;
+ case Nlbl:
+ append(s, n);
+ break;
+ default:
+ die("Bad node passsed to simp()");+ break;
+ }
+ return r;
+}
+
+Node **reduce(Node *n, int *ret_nn)
+{+ Simp s = {0,};+
+ s.nblk = 0;
+ s.endlbl = genlbl();
+ s.retval = NULL;
+ switch (n->type) {+ /* these should never be inside functions */
+ case Nnone:
+ case Nfile:
+ die("Bad node type in func");+ break;
+ case Nfunc:
+ die("FIXME: generate thunks");+ break;
+ /* no code generated */
+ case Nuse:
+ break;
+ /* complex nodes */
+ case Nblock:
+ simp(&s, n);
+ break;
+ case Nifstmt:
+ case Nloopstmt:
+ case Nexpr:
+ case Nlit:
+ case Nname:
+ case Ndecl:
+ case Nlbl:
+ break;
+ }
+ append(&s, s.endlbl);
+
+ *ret_nn = s.nblk;
+ return s.blk;
+}
--- /dev/null
+++ b/8/regs.def
@@ -1,0 +1,25 @@
+Reg(Rnone, "%NOREG")
+/* byte regs */
+Reg(Ral, "%al")
+Reg(Rcl, "%cl")
+Reg(Rdl, "%dl")
+Reg(Rbl, "%bl")
+
+/* short regs */
+Reg(Rax, "%ax")
+Reg(Rbx, "%bx")
+Reg(Rcx, "%cx")
+Reg(Rdx, "%dx")
+Reg(Rsi, "%si")
+Reg(Rdi, "%di")
+
+/* long regs */
+Reg(Reax, "%eax")
+Reg(Recx, "%ecx")
+Reg(Redx, "%edx")
+Reg(Rebx, "%ebx")
+Reg(Resi, "%esi")
+Reg(Redi, "%edi")
+Reg(Resp, "%esp")
+Reg(Rebp, "%ebp")
+
--- a/8/simp.c
+++ b/8/simp.c
@@ -18,7 +18,7 @@
static void lowerglobl(Comp *c, char *name, Node *init);
static void lowerif(Comp *c, Fn *fn, Node *cond);
static void lowerloop(Comp *c, Fn *fn, Node *loop);
-static void lowerblock(Comp *c, Fn *fn, Node *blk);
+void lowerblock(Comp *c, Fn *fn, Node *blk);
static void lowerfn(Comp *c, char *name, Node *n);
Fn *mkfn(char *name)
@@ -166,7 +166,7 @@
fn->cur = mkbb();
}
-static void lowerblock(Comp *c, Fn *fn, Node *blk)
+void lowerblock(Comp *c, Fn *fn, Node *blk)
{Node **n;
size_t nn;
@@ -202,14 +202,12 @@
static void lowerfn(Comp *c, char *name, Node *n)
{Fn *fn;
+ Node **nl;
+ int nn;
int i;
- Bb *fix;
- Node *last;
/* unwrap to the function body */
- assert(n->type == Nexpr && exprop(n) == Olit);
n = n->expr.args[0];
- assert(n->type == Nlit && n->lit.littype == Lfunc);
n = n->lit.fnval;
assert(n->type == Nfunc);
@@ -217,21 +215,11 @@
fn = mkfn(name);
fn = zalloc(sizeof(Fn));
fn->name = strdup(name);
- lowerblock(c, fn, n->func.body);
- lappend(&c->func, &c->nfunc, fn);
- for (i = 0; i < fn->nfixup; i++) {- fix = fn->fixup[i];
- last = fix->n[fix->nn - 1];
- switch (exprop(last)) {- case Ocjmp:
- break;
- case Ojmp:
- break;
- default:
- die("Invalid last node in BB");- break;
- }
+ nl = reduce(n->func.body, &nn);
+
+ for (i = 0; i < nn; i++) {+ dump(nl[i], stdout);
}
}