shithub: mc

Download patch

ref: 5f6c72e00d6053baf98563bb53afeb770e648e9d
parent: 1eb59b7b99d6dbb3c37cc9c8503450427f4d9564
author: Ori Bernstein <[email protected]>
date: Fri Jun 8 11:15:50 EDT 2012 

Move register allocation code into it's own file.

    Gearing up for implementing an actual (albeit simple) register
    allocator. This should allow us to do useful things like not
    dying if we have 2 shifts or 2 multiplies in the same tree by
    spilling, and other good stuff.


--- a/8/Makefile
+++ b/8/Makefile
@@ -2,6 +2,7 @@
 OBJ=isel.o \
     main.o \
     reduce.o \
+    regalloc.o \
 
 CFLAGS+=-I../parse
 LDFLAGS+=-L../parse -lparse
--- a/8/asm.h
+++ b/8/asm.h
@@ -35,6 +35,7 @@
 typedef struct Loc Loc;
 typedef struct Func Func;
 typedef struct Blob Blob;
+typedef struct Isel Isel;
 
 struct Blob {
     char *name; /* mangled asm name */
@@ -77,6 +78,18 @@
     size_t nn;
 };
 
+/* instruction selection state */
+struct Isel {
+    Insn **il;
+    size_t ni;
+    Node *ret;
+    Htab *locs; /* decl id => int stkoff */
+    Htab *globls; /* decl id => char *globlname */
+
+    /* 6 general purpose regs */
+    int rtaken[Nreg];
+};
+
 /* entry points */
 void genasm(FILE *fd, Func *fn, Htab *globls);
 void gen(Node *file, char *out);
@@ -83,6 +96,7 @@
 
 /* location generation */
 Loc *loclbl(Loc *l, Node *lbl);
+Loc *locstrlbl(Loc *l, char *lbl);
 Loc *locreg(Loc *l, Reg r);
 Loc *locmem(Loc *l, long disp, Reg base, Reg idx, Mode mode);
 Loc *locmeml(Loc *l, char *disp, Reg base, Reg idx, Mode mode);
@@ -89,8 +103,18 @@
 Loc *locmems(Loc *l, long disp, Reg base, Reg idx, int scale, Mode mode);
 Loc *locmemls(Loc *l, char *disp, Reg base, Reg idx, int scale, Mode mode);
 Loc *loclit(Loc *l, long val);
+void locprint(FILE *fd, Loc *l);
+void iprintf(FILE *fd, Insn *insn);
 
+/* register allocation */
+Loc getreg(Isel *s, Mode m);
+void freeloc(Isel *s, Loc l);
+Loc claimreg(Isel *s, Reg r);
+void freereg(Isel *s, Reg r);
+extern const char *regnames[];
+extern const Mode regmodes[];
+
+
 /* useful functions */
 size_t size(Node *n);
 void breakhere();
-
--- a/8/isel.c
+++ b/8/isel.c
@@ -13,58 +13,7 @@
 #include "parse.h"
 #include "asm.h"
 
-/* instruction selection state */
-typedef struct Isel Isel;
-struct Isel {
-    Insn **il;
-    size_t ni;
-    Node *ret;
-    Htab *locs; /* decl id => int stkoff */
-    Htab *globls; /* decl id => char *globlname */
-
-    /* 6 general purpose regs */
-    int rtaken[Nreg];
-};
-
 /* string tables */
-const char *regnames[] = {
-#define Reg(r, name, mode) name,
-#include "regs.def"
-#undef Reg
-};
-
-const Mode regmodes[] = {
-#define Reg(r, name, mode) mode,
-#include "regs.def"
-#undef Reg
-};
-
-const Reg reginterferes[Nreg][Nmode + 1] = {
-    /* byte */
-    [Ral] = {Ral, Rax, Reax},
-    [Rcl] = {Rcl, Rcx, Recx},
-    [Rdl] = {Rdl, Rdx, Redx},
-    [Rbl] = {Rbl, Rbx, Rebx},
-
-    /* word */
-    [Rax] = {Ral, Rax, Reax},
-    [Rcx] = {Rcl, Rcx, Recx},
-    [Rdx] = {Rdl, Rdx, Redx},
-    [Rbx] = {Rbl, Rbx, Rebx},
-    [Rsi] = {Rsi, Resi},
-    [Rdi] = {Rdi, Redi},
-
-    /* dword */
-    [Reax] = {Ral, Rax, Reax},
-    [Recx] = {Rcl, Rcx, Recx},
-    [Redx] = {Rdl, Rdx, Redx},
-    [Rebx] = {Rbl, Rbx, Rebx},
-    [Resi] = {Rsi, Resi},
-    [Redi] = {Rdi, Redi},
-    [Resp] = {Resp},
-    [Rebp] = {Rebp},
-};
-
 char *insnfmts[] = {
 #define Insn(val, fmt, attr) fmt,
 #include "insns.def"
@@ -71,9 +20,10 @@
 #undef Insn
 };
 
-void locprint(FILE *fd, Loc *l);
-void iprintf(FILE *fd, Insn *insn);
 
+/* forward decls */
+Loc selexpr(Isel *s, Node *n);
+
 /* used to decide which operator is appropriate
  * for implementing various conditional operators */
 struct {
@@ -91,76 +41,6 @@
 };
 
 
-/* forward decls */
-Loc selexpr(Isel *s, Node *n);
-
-Loc *locstrlbl(Loc *l, char *lbl)
-{
-    l->type = Loclbl;
-    l->mode = ModeL;
-    l->lbl = strdup(lbl);
-    return l;
-}
-
-Loc *loclbl(Loc *l, Node *lbl)
-{
-    assert(lbl->type = Nlbl);
-    return locstrlbl(l, lbl->lbl.name);
-}
-
-Loc *locreg(Loc *l, Reg r)
-{
-    l->type = Locreg;
-    l->mode = regmodes[r];
-    l->reg = r;
-    return l;
-}
-
-Loc *locmem(Loc *l, long disp, Reg base, Reg idx, Mode mode)
-{
-    l->type = Locmem;
-    l->mode = mode;
-    l->mem.constdisp = disp;
-    l->mem.base = base;
-    l->mem.idx = idx;
-    l->mem.scale = 0;
-    return l;
-}
-
-Loc *locmems(Loc *l, long disp, Reg base, Reg idx, int scale, Mode mode)
-{
-    locmem(l, disp, base, idx, mode);
-    l->mem.scale = scale;
-    return l;
-}
-
-Loc *locmeml(Loc *l, char *disp, Reg base, Reg idx, Mode mode)
-{
-    l->type = Locmem;
-    l->mode = mode;
-    l->mem.lbldisp = strdup(disp);
-    l->mem.base = base;
-    l->mem.idx = idx;
-    l->mem.scale = 0;
-    return l;
-}
-
-Loc *locmemls(Loc *l, char *disp, Reg base, Reg idx, int scale, Mode mode)
-{
-    locmeml(l, disp, base, idx, mode);
-    l->mem.scale = scale;
-    return l;
-}
-
-
-Loc *loclit(Loc *l, long val)
-{
-    l->type = Loclit;
-    l->mode = ModeL; /* FIXME: what do we do for mode? */
-    l->lit = val;
-    return l;
-}
-
 Loc loc(Isel *s, Node *n)
 {
     Loc l;
@@ -230,55 +110,6 @@
     return l;
 }
 
-Loc getreg(Isel *s, Mode m)
-{
-
-    Loc l;
-    int i;
-
-    assert(m != ModeNone);
-    l.reg = Rnone;
-    for (i = 0; i < Nreg; i++) {
-        if (!s->rtaken[i] && regmodes[i] == m) {
-            locreg(&l, i);
-            break;
-        }
-    }
-    if (l.reg == Rnone)
-        die("Not enough registers. Please split your expression and try again (FIXME: implement spilling)");
-    for (i = 0; i < Nmode; i++)
-        s->rtaken[reginterferes[l.reg][i]] = 1;
-
-    return l;
-}
-
-void freereg(Isel *s, Reg r)
-{
-    int i;
-
-    for (i = 0; i < Nmode; i++)
-        s->rtaken[reginterferes[r][i]] = 0;
-}
-
-void freeloc(Isel *s, Loc l)
-{
-    if (l.type == Locreg)
-        freereg(s, l.reg);
-}
-
-Loc claimreg(Isel *s, Reg r)
-{
-    Loc l;
-    int i;
-
-    if (s->rtaken[r])
-        die("Reg %s is already taken", regnames[r]);
-    for (i = 0; i < Nmode; i++)
-        s->rtaken[reginterferes[r][i]] = 1;
-    locreg(&l, r);
-    return l;
-}
-
 Insn *mkinsnv(AsmOp op, va_list ap)
 {
     Loc *l;
@@ -782,7 +613,7 @@
     char *p;
     int i;
     int modeidx;
-    
+
     p = insnfmts[insn->op];
     i = 0;
     for (; *p; p++) {
--- /dev/null
+++ b/8/regalloc.c
@@ -1,0 +1,169 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <stdarg.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 "asm.h"
+
+const Mode regmodes[] = {
+#define Reg(r, name, mode) mode,
+#include "regs.def"
+#undef Reg
+};
+
+const char *regnames[] = {
+#define Reg(r, name, mode) name,
+#include "regs.def"
+#undef Reg
+};
+
+
+const Reg reginterferes[Nreg][Nmode + 1] = {
+    /* byte */
+    [Ral] = {Ral, Rax, Reax},
+    [Rcl] = {Rcl, Rcx, Recx},
+    [Rdl] = {Rdl, Rdx, Redx},
+    [Rbl] = {Rbl, Rbx, Rebx},
+
+    /* word */
+    [Rax] = {Ral, Rax, Reax},
+    [Rcx] = {Rcl, Rcx, Recx},
+    [Rdx] = {Rdl, Rdx, Redx},
+    [Rbx] = {Rbl, Rbx, Rebx},
+    [Rsi] = {Rsi, Resi},
+    [Rdi] = {Rdi, Redi},
+
+    /* dword */
+    [Reax] = {Ral, Rax, Reax},
+    [Recx] = {Rcl, Rcx, Recx},
+    [Redx] = {Rdl, Rdx, Redx},
+    [Rebx] = {Rbl, Rbx, Rebx},
+    [Resi] = {Rsi, Resi},
+    [Redi] = {Rdi, Redi},
+    [Resp] = {Resp},
+    [Rebp] = {Rebp},
+};
+
+Loc *locstrlbl(Loc *l, char *lbl)
+{
+    l->type = Loclbl;
+    l->mode = ModeL;
+    l->lbl = strdup(lbl);
+    return l;
+}
+
+Loc *loclbl(Loc *l, Node *lbl)
+{
+    assert(lbl->type = Nlbl);
+    return locstrlbl(l, lbl->lbl.name);
+}
+
+Loc *locreg(Loc *l, Reg r)
+{
+    l->type = Locreg;
+    l->mode = regmodes[r];
+    l->reg = r;
+    return l;
+}
+
+Loc *locmem(Loc *l, long disp, Reg base, Reg idx, Mode mode)
+{
+    l->type = Locmem;
+    l->mode = mode;
+    l->mem.constdisp = disp;
+    l->mem.base = base;
+    l->mem.idx = idx;
+    l->mem.scale = 0;
+    return l;
+}
+
+Loc *locmems(Loc *l, long disp, Reg base, Reg idx, int scale, Mode mode)
+{
+    locmem(l, disp, base, idx, mode);
+    l->mem.scale = scale;
+    return l;
+}
+
+Loc *locmeml(Loc *l, char *disp, Reg base, Reg idx, Mode mode)
+{
+    l->type = Locmem;
+    l->mode = mode;
+    l->mem.lbldisp = strdup(disp);
+    l->mem.base = base;
+    l->mem.idx = idx;
+    l->mem.scale = 0;
+    return l;
+}
+
+Loc *locmemls(Loc *l, char *disp, Reg base, Reg idx, int scale, Mode mode)
+{
+    locmeml(l, disp, base, idx, mode);
+    l->mem.scale = scale;
+    return l;
+}
+
+
+Loc *loclit(Loc *l, long val)
+{
+    l->type = Loclit;
+    l->mode = ModeL; /* FIXME: what do we do for mode? */
+    l->lit = val;
+    return l;
+}
+
+Loc getreg(Isel *s, Mode m)
+{
+
+    Loc l;
+    int i;
+
+    assert(m != ModeNone);
+    l.reg = Rnone;
+    for (i = 0; i < Nreg; i++) {
+        if (!s->rtaken[i] && regmodes[i] == m) {
+            locreg(&l, i);
+            break;
+        }
+    }
+    if (l.reg == Rnone)
+        die("Not enough registers. Please split your expression and try again (FIXME: implement spilling)");
+    for (i = 0; i < Nmode; i++)
+        s->rtaken[reginterferes[l.reg][i]] = 1;
+
+    return l;
+}
+
+Loc claimreg(Isel *s, Reg r)
+{
+    Loc l;
+    int i;
+
+    if (s->rtaken[r])
+        die("Reg %s is already taken", regnames[r]);
+    for (i = 0; i < Nmode; i++)
+        s->rtaken[reginterferes[r][i]] = 1;
+    locreg(&l, r);
+    return l;
+}
+
+void freereg(Isel *s, Reg r)
+{
+    int i;
+
+    for (i = 0; i < Nmode; i++)
+        s->rtaken[reginterferes[r][i]] = 0;
+}
+
+void freeloc(Isel *s, Loc l)
+{
+    if (l.type == Locreg)
+        freereg(s, l.reg);
+}