regalloc skeleton

13 files changed, 298 insertions, 60 deletions

diff --git a/Makefile b/Makefile
index f9f3e12..90bac1b 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-SRC=main.c io.c mem.c parse.c lex.c type.c targ.c eval.c ir.c irdump.c
+SRC=main.c io.c mem.c parse.c lex.c type.c targ.c eval.c ir.c irdump.c regalloc.c amd64/sysv.c
 CFLAGS=-Wall -std=c11 -pedantic
 OBJ=$(patsubst %.c,obj/%.o,$(SRC))
 OUT=cchomp
@@ -16,7 +16,7 @@ $(OUT): $(OBJ)
 	$(CC) $(CFLAGS) -o $@ $(OBJ)
 
 obj/%.o: %.c common.h
-	@mkdir -p obj/
+	@mkdir -p `dirname $@`
 	$(CC) $(CFLAGS) -c -o $@ $<
 
 obj/main.o: parse.h
@@ -26,6 +26,7 @@ obj/irdump.o: ir.h op.def
 obj/lex.o: parse.h
 obj/eval.o: parse.h
 obj/io.o: parse.h keywords.def
+obj/amd64/sysv.o: ir.h amd64/all.h
 
 clean:
 	$(RM) -r obj/ $(OUT)
diff --git a/amd64/all.h b/amd64/all.h
new file mode 100644
index 0000000..ae21d3d
--- /dev/null
+++ b/amd64/all.h
@@ -0,0 +1,32 @@
+#include "../ir.h"
+
+
+#define LIST_REGS(_)                                               \
+   _(RAX) _(RCX) _(RDX) _(RBX) _(RSP) _(RBP) _(RSI) _(RDI)         \
+   _(R8) _(R9) _(R10) _(R11) _(R12) _(R13) _(R14) _(R15)           \
+   _(XMM0) _(XMM1) _(XMM2) _(XMM3) _(XMM4) _(XMM5) _(XMM6) _(XMM7) \
+   _(XMM8) _(XMM9) _(XMM10) _(XMM11) _(XMM12) _(XMM13) _(XMM14) _(XMM15)
+
+enum {
+   Rxxx,
+#define R(r) r,
+   LIST_REGS(R)
+#undef R
+};
+
+const char amd64_rnames[][6] = {
+   "?",
+#define R(r) #r,
+   LIST_REGS(R)
+#undef R
+};
+
+const struct mctarg t_amd64_sysv = {
+   .gpr0 = RAX, .ngpr = R15 - RAX + 1,
+   .fpr0 = XMM0, .nfpr = XMM15 - XMM0 + 1,
+   .rcallee = {{1<<RBX | 1<<R12 | 1<<R13 | 1<<R14 | 1<<R15}},
+   .rglob = {{1<<RSP | 1<<RBP}},
+   .rnames = amd64_rnames,
+};
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/amd64/sysv.c b/amd64/sysv.c
new file mode 100644
index 0000000..e998036
--- /dev/null
+++ b/amd64/sysv.c
@@ -0,0 +1,3 @@
+#include "all.h"
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/common.h b/common.h
index 872fdd6..0871257 100644
--- a/common.h
+++ b/common.h
@@ -108,6 +108,7 @@ enum typetag { /* ordering is important here! */
    TYVALIST,
    TYPTR, TYARRAY, TYFUNC,
    TYSTRUCT, TYUNION,
+   NTYPETAG,
    TYSIGNEDSET_ = 1<<TYSCHAR | 1<<TYSHORT | 1<<TYINT | 1<<TYLONG | 1<<TYVLONG,
    TYUNSIGNEDSET_ = 1<<TYUCHAR | 1<<TYUSHORT | 1<<TYUINT | 1<<TYULONG | 1<<TYUVLONG,
    TYSCALARSET_ = ((1u << (TYLDOUBLE - TYENUM + 1)) - 1) << TYENUM | 1<<TYPTR
@@ -276,7 +277,8 @@ extern uchar targ_primsizes[];
 extern uchar targ_primalign[];
 extern enum typetag targ_sizetype, targ_ptrdifftype;
 extern bool targ_charsigned, targ_bigendian;
-void targ_init(const char *targ);
+extern const struct mctarg *mctarg;
+void targ_init(const char *);
 
 /*********/
 /** MEM **/
@@ -317,13 +319,25 @@ bstest(struct bitset *bs, uint i)
 }
 
 static inline void
-bszero(struct bitset *bs, uint siz)
+bsset(struct bitset *bs, uint i)
+{
+   bs[i / BSNBIT].u |= 1 << i % BSNBIT;
+}
+
+static inline void
+bsclr(struct bitset *bs, uint i)
+{
+   bs[i / BSNBIT].u &= ~(1 << i % BSNBIT);
+}
+
+static inline void
+bszero(struct bitset bs[/*siz*/], uint siz)
 {
    memset(bs, 0, siz * sizeof *bs);
 }
 
 static inline bool
-bsiter(uint *i, struct bitset *bs, uint siz)
+bsiter(uint *i, struct bitset bs[/*siz*/], uint siz)
 {
    for (; *i < siz*BSNBIT; ++*i)
       if (bstest(bs, *i)) return 1;
diff --git a/io.c b/io.c
index cc9f672..48325d4 100644
--- a/io.c
+++ b/io.c
@@ -289,7 +289,7 @@ putdouble(struct wbuf *buf, double x, vlong prec)
 int
 vbfmt(struct wbuf *out, const char *fmt, va_list ap)
 {
-   bool quote, unsgnd, numlong, lower;
+   bool quote, umod, lmod, lower;
    int base;
    vlong i;
    int pad, prec, q;
@@ -337,8 +337,8 @@ vbfmt(struct wbuf *out, const char *fmt, va_list ap)
          for (; aisdigit(*fmt); ++fmt)
             prec = prec*10 + *fmt-'0';
       }
-      fmt += unsgnd = *fmt == 'u';
-      fmt += numlong = *fmt == 'l';
+      fmt += umod = *fmt == 'u';
+      fmt += lmod = *fmt == 'l';
       lower = 0;
       prevn = n;
       switch (*fmt++) {
@@ -356,10 +356,16 @@ vbfmt(struct wbuf *out, const char *fmt, va_list ap)
          assert(s && "%s null!");
          if (quote) {
             n += bputc(buf, '"');
-            for (; *s; ++s) n += putquoted(buf, *s, '"', s[1]);
+            if (lmod) /* lower */
+               for (; *s; ++s) n += putquoted(buf, aisalpha(*s) ? *s|32 : *s, '"', s[1]);
+            else
+               for (; *s; ++s) n += putquoted(buf, *s, '"', s[1]);
             n += bputc(buf, '"');
          } else {
-            while (*s) n += bputc(buf, *s++);
+            if (lmod) /* lower */
+               for (; *s; ++s) n += bputc(buf, aisalpha(*s) ? *s|32 : *s);
+            else
+               while (*s) n += bputc(buf, *s++);
          }
          break;
       case 'S':  /* string ptr + len */
@@ -377,8 +383,8 @@ vbfmt(struct wbuf *out, const char *fmt, va_list ap)
       case 'd': /* decimal */
          base = 10;
       Int:
-         if (base != 10) unsgnd = 1;
-         i = numlong ? va_arg(ap, vlong) : (unsgnd ? va_arg(ap, uint) : (vlong)va_arg(ap, int));
+         if (base != 10) umod = 1;
+         i = lmod ? va_arg(ap, vlong) : (umod ? va_arg(ap, uint) : (vlong)va_arg(ap, int));
          tmp2.len = 0;
          if (quote) {
             switch (base) {
@@ -387,7 +393,7 @@ vbfmt(struct wbuf *out, const char *fmt, va_list ap)
             case 16: n += bwriteS(buf, "0x"); break;
             }
          }
-         if (!unsgnd && i < 0) {
+         if (!umod && i < 0) {
             n += bputc(buf, '-');
             i = -i;
          }
@@ -545,7 +551,7 @@ vbfmt(struct wbuf *out, const char *fmt, va_list ap)
          if (!ccopt.nocolor) n += bputc(buf, 'm');
          break;
       default:
-         if (unsgnd || numlong) {
+         if (umod || lmod) {
             --fmt;
             base = 10;
             goto Int;
diff --git a/ir.c b/ir.c
index 3d2ad8e..65280f8 100644
--- a/ir.c
+++ b/ir.c
@@ -1,7 +1,7 @@
 #include "ir.h"
 #include "common.h"
 
-uchar type2cls[TYARRAY + 1];
+uchar type2cls[NTYPETAG];
 uchar cls2siz[KF8+1];
 const uchar siz2intcls[] = { [1] = KI4, [2] = KI4, [4] = KI4, [8] = KI8 };
 
@@ -34,6 +34,7 @@ irinit(struct function *fn)
       cls2siz[KPTR] = targ_primsizes[TYPTR];
    }
    fn->entry = fn->curblk = alloc(&fn->arena, sizeof(struct block), 0);
+   memset(fn->entry, 0, sizeof *fn->entry);
    fn->entry->lprev = fn->entry->lnext = fn->entry;
 }
 
@@ -264,4 +265,25 @@ putjump(struct function *fn, enum jumpkind j, union ref arg, struct block *t, st
    fn->curblk = NULL;
 }
 
+static void
+freefn(struct function *fn)
+{
+   struct block *blk = fn->entry;
+   do {
+      vfree(&blk->phi);
+      vfree(&blk->ins);
+      blk = blk->lnext;
+   } while (blk != fn->entry);
+}
+
+void
+irfini(struct function *fn)
+{
+   regalloc(fn);
+   efmt("after regalloc:\n");
+   irdump(fn, fn->name);
+
+   freefn(fn);
+}
+
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/ir.h b/ir.h
index b8095d9..f1a511e 100644
--- a/ir.h
+++ b/ir.h
@@ -6,7 +6,7 @@ enum irclass {
    KF4, KF8,
 };
 
-#define kisint(k) in_range((k), KI4, KIP)
+#define kisint(k) in_range((k), KI4, KPTR)
 #define kisflt(k) in_range((k), KF4, KF8)
 
 union irtype {
@@ -56,7 +56,13 @@ struct phi {
 };
 
 enum refkind {
-   RNONE, RTMP, RARG, RICON, RXCON, RSYM, REXT
+   RNONE,
+   RTMP,  /* reference to another instruction's result */
+   RARG,  /* function argument */
+   RICON, /* small integer constants */
+   RXCON, /* other constants (incl. external symbols) */
+   REXT,  /* reference to extra data for Ocall and Ophi */
+   RREG,  /* machine register */
 };
 
 union ref {
@@ -73,8 +79,8 @@ enum op {
 };
 
 struct instr {
-   uchar op;
-   uchar cls;
+   uchar op, cls;
+   uchar reg, hint;
    union ref l, r;
 };
 
@@ -85,9 +91,9 @@ enum jumpkind {
 struct block {
    int id;
    struct block *s1, *s2;
-   struct { uchar t; union ref arg; } jmp;   
    vec_of(ushort) phi;
    vec_of(ushort) ins;
+   struct { uchar t; union ref arg; } jmp;
    struct block *lprev, *lnext;
 };
 
@@ -101,13 +107,27 @@ struct function {
    bool globl;
 };
 
+enum { MAXREGS = 32 };
+
+struct mctarg {
+   short gpr0, /* first gpr */
+         ngpr, /* gpr count */
+         fpr0, /* first fpr */
+         nfpr; /* fpr count */
+   struct bitset rcallee[1], /* callee-saved */
+                 rglob[1];   /* globally live (never used for regalloc) */
+   const char (*rnames)[6];
+};
+
 extern uchar type2cls[];
 extern uchar cls2siz[];
 extern const uchar siz2intcls[];
-void irinit(struct function *);
 #define NOREF ((union ref) {0})
 #define mkref(t, x) ((union ref) {{ (t), (x) }})
-#define mkzerocon() ((union irref){ RICON, 0 })
+#define mkzerocon() ((union ref) {{ RICON, 0 }})
+#define mkinstr(O, C, ...) ((struct instr) { .op = (O), .cls = (C), .reg=0,.hint=0, __VA_ARGS__ })
+void irinit(struct function *);
+void irfini(struct function *);
 union irtype mkirtype(union type);
 union ref mkintcon(struct function *, enum irclass, vlong);
 union ref mkfltcon(struct function *, enum irclass, double);
@@ -121,6 +141,11 @@ union ref addphi(struct function *, enum irclass cls, struct block **blk, union
 struct block *newblk(struct function *);
 void useblk(struct function *, struct block *);
 void putjump(struct function *, enum jumpkind, union ref arg, struct block *t, struct block *f);
+void insertinstr(struct block *, int idx, struct instr);
+void delinstr(struct block *, int idx);
+
 void irdump(struct function *, const char *fname);
 
+void regalloc(struct function *);
+
 /* vim:set ts=3 sw=3 expandtab: */
diff --git a/irdump.c b/irdump.c
index f225431..425c7d2 100644
--- a/irdump.c
+++ b/irdump.c
@@ -37,8 +37,8 @@ dumpref(enum op o, union ref ref)
       case KI4: efmt("%d", con->i4); break;
       case KI8: efmt("%ld", con->i8); break;
       case KPTR: efmt("%'x", con->i8); break;
-      case KF4: efmt("%f", con->fs); break;
-      case KF8: efmt("%f", con->fd); break;
+      case KF4: efmt("%fs", con->fs); break;
+      case KF8: efmt("%fd", con->fd); break;
       default: assert(0);
       }
       break;
@@ -89,8 +89,11 @@ dumpinst(const struct instr *ins)
 {
    int i;
    efmt("    ");
-   if (ins->cls)
-      efmt("%s %%%d = ", clsname[ins->cls], ins - instr);
+   if (ins->cls) {
+      efmt("%s %%%d", clsname[ins->cls], ins - instr);
+      if (ins->reg) efmt("(%ls)", mctarg->rnames[ins->reg]);
+      efmt(" = ");
+   }
    efmt("%s ", opname[ins->op]);
    for (i = 0; i < opnarg[ins->op]; ++i) {
       if (i) efmt(", ");
diff --git a/mem.c b/mem.c
index c16fe54..07519d5 100644
--- a/mem.c
+++ b/mem.c
@@ -111,6 +111,10 @@ freearena(struct arena *ar)
       prev = ar->prev;
       if (ar->dyn)
          free(ar);
+      else {
+         assert(!prev);
+         ar->n = 0;
+      }
    }
 }
 
diff --git a/parse.c b/parse.c
index f243733..5b38637 100644
--- a/parse.c
+++ b/parse.c
@@ -954,7 +954,7 @@ expraddr(struct function *fn, const struct expr *ex)
 {
    struct decl *decl;
    union ref r;
-   struct instr ins;
+   struct instr ins = {0};
 
    switch (ex->t) {
    case ESYM:
@@ -1037,8 +1037,10 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref)
    ins.cls = kto;
    ins.l = ref;
    if (kisflt(kto) || kisflt(kfrom)) {
-      if (kto == KPTR) kto = siz2intcls[cls2siz[kto]];
-      if (kfrom == KPTR) kfrom = siz2intcls[cls2siz[kfrom]];
+      if (ref.t == RICON) {
+         assert(kisflt(kto) && kisint(kfrom));
+         return mkfltcon(fn, kto, kto == KF4 ? (float)ref.i : (double)ref.i);
+      }
       if (kisflt(kto) && kfrom == KI4) ins.op = issignedt(from) ? Ocvts4f : Ocvtu4f;
       else if (to == TYBOOL && kisflt(kfrom)) ins.op = Oneq, ins.r = mkfltcon(fn, kfrom, 0.0);
       else if (kisflt(kto) && kfrom == KI8) ins.op = issignedt(from) ? Ocvts8f : Ocvtu8f;
@@ -1048,7 +1050,16 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref)
       else if (kfrom == KF8) ins.op = issignedt(to) ? Ocvtf8s : Ocvtf8u;
       else assert(0);
    } else {
-      if (to == TYBOOL) ins.op = Oneq, ins.r = mkzerocon();
+      if (to == TYBOOL) {
+         if (from == TYBOOL) return ref;
+         if (ref.t == RTMP) {
+            extern struct instr instr[];
+            /* these instrs already have output range of [0,1] */
+            if (in_range(instr[ref.idx].op, Oequ, Oulte) || instr[ref.idx].op == Onot)
+               return ref;
+         }
+         ins.op = Oneq, ins.r = mkzerocon();
+      }
       else if (kfrom == KI4 && issignedt(from)) ins.op = Oexts4;
       else if (kfrom == KI4) ins.op = Oextu4;
       else ins.op = Ocopy;
@@ -1059,7 +1070,7 @@ cvt(struct function *fn, enum typetag to, enum typetag from, union ref ref)
 static union ref
 narrow(struct function *fn, enum irclass to, enum typetag tt, union ref ref)
 {
-   struct instr ins;
+   struct instr ins = {0};
    assert(isintt(tt) || tt == TYPTR);
    if (targ_primsizes[tt] >= cls2siz[to]) return ref;
    ins.cls = to;
@@ -1098,12 +1109,12 @@ genptroff(struct function *fn, enum op op, uint siz, union ref ptr,
       off = mkintcon(fn, cls, idx.i * siz);
    else if ((siz & (siz-1)) == 0) /* is power of 2 */
       off = addinstr(fn,
-            (struct instr) { Oshl, cls, .l = idx, .r = mkintcon(fn, cls, ilog2(siz)) });
+            mkinstr(Oshl, cls, .l = idx, .r = mkintcon(fn, cls, ilog2(siz))));
    else
       off = addinstr(fn,
-            (struct instr) { Omul, cls, .l = idx, .r = mkintcon(fn, cls, siz) });
+            mkinstr(Omul, cls, .l = idx, .r = mkintcon(fn, cls, siz)));
    assert(in_range(op, Oadd, Osub));
-   return addinstr(fn, (struct instr) { op, KPTR, .l = ptr, .r = off });
+   return addinstr(fn, mkinstr(op, KPTR, .l = ptr, .r = off));
 }
 
 union ref
@@ -1111,12 +1122,12 @@ genptrdiff(struct function *fn, uint siz, union ref a, union ref b)
 {
    uint cls = type2cls[targ_ptrdifftype];
    assert(siz > 0);
-   a = addinstr(fn, (struct instr) { Osub, cls, .l = a, .r = b });
+   a = addinstr(fn, mkinstr(Osub, cls, .l = a, .r = b));
    if (siz == 1) return a;
    else if ((siz & (siz-1)) == 0) /* is power of 2 */
-      return addinstr(fn, (struct instr) { Osar, cls, a, mkintcon(fn, cls, ilog2(siz)) });
+      return addinstr(fn, mkinstr(Osar, cls, a, mkintcon(fn, cls, ilog2(siz))));
    else
-      return addinstr(fn, (struct instr) { Odiv, cls, a, mkintcon(fn, cls, siz) });
+      return addinstr(fn, mkinstr(Odiv, cls, a, mkintcon(fn, cls, siz)));
 }
 
 /* used to emit the jumps in an in if (), while (), etc condition */
@@ -1173,8 +1184,8 @@ struct condphis {
 };
 
 static void
-condexprrec(struct function *fn, const struct expr *ex, bool tobool,
-            struct condphis *phis, struct block *end, struct block *zero)
+condexprrec(struct function *fn, const struct expr *ex, struct condphis *phis,
+            int boolcon, struct block *end, struct block *zero)
 {
    struct block *tr, *fl, *next;
    union ref r;
@@ -1184,31 +1195,37 @@ condexprrec(struct function *fn, const struct expr *ex, bool tobool,
    }
    if (ex->t == ELOGAND) {
       next = newblk(fn);
-      condexprrec(fn, &ex->sub[0], 0, phis, next, end);
+      condexprrec(fn, &ex->sub[0], phis, 0, next, end);
       useblk(fn, next);
-      condexprrec(fn, &ex->sub[1], 1, phis, end, zero);
+      condexprrec(fn, &ex->sub[1], phis, -2, end, zero);
    } else if (ex->t == ELOGIOR) {
       next = newblk(fn);
-      condexprrec(fn, &ex->sub[0], 1, phis, end, next);
+      condexprrec(fn, &ex->sub[0], phis, 1, end, next);
       useblk(fn, next);
-      condexprrec(fn, &ex->sub[1], 1, phis, end, zero);
+      condexprrec(fn, &ex->sub[1], phis, -2, end, zero);
    } else if (ex->t == ECOND) {
       tr = newblk(fn);
       fl = newblk(fn);
       condjump(fn, &ex->sub[0], tr, fl);
       useblk(fn, tr);
-      condexprrec(fn, &ex->sub[1], 0, phis, end, zero);
+      condexprrec(fn, &ex->sub[1], phis, -1, end, zero);
       useblk(fn, fl);
-      condexprrec(fn, &ex->sub[2], 0, phis, end, zero);
+      condexprrec(fn, &ex->sub[2], phis, -1, end, zero);
    } else {
       r = exprvalue(fn, ex);
-      if (tobool) r = cvt(fn, TYBOOL, ex->ty.t, r);
       vpush(&phis->blk, fn->curblk);
-      vpush(&phis->ref, r);
-      if (zero)
-         putjump(fn, Jbcnd, r, end, zero);
+      if (boolcon == -2)
+         r = cvt(fn, TYBOOL, ex->ty.t, r);
+      if (boolcon >= 0)
+         vpush(&phis->ref, mkintcon(fn, KI4, boolcon));
       else
+         vpush(&phis->ref, r);
+      if (zero) {
+         putjump(fn, Jbcnd, r, end, zero);
+      } else {
+         assert(boolcon < 0);
          putjump(fn, Jb, NOREF, end, NULL);
+      }
    }
 }
 
@@ -1223,7 +1240,7 @@ condexprvalue(struct function *fn, const struct expr *ex)
                             VINIT(refbuf, arraylength(refbuf))};
    struct block *dst = newblk(fn);
    union ref r;
-   condexprrec(fn, ex, 0, &phis, dst, NULL);
+   condexprrec(fn, ex, &phis, -1, dst, NULL);
    useblk(fn, dst);
    r = addphi(fn, type2cls[ex->ty.t], phis.blk.p, phis.ref.p, phis.blk.n);
    vfree(&phis.blk);
@@ -1639,8 +1656,7 @@ block(struct parser *pr, struct function *fn)
                   siz = typesize(decl.ty);
                   nalloc = siz/align + ((siz&(align-1)) != 0);
                   EMITS {
-                     decl.id = addinstr(fn,
-                                 (struct instr) { op, KPTR, mkintcon(fn, KI4, nalloc) }).idx;
+                     decl.id = addinstr(fn, mkinstr(op, KPTR, mkintcon(fn, KI4, nalloc))).idx;
                   }
                   if (st.varini) {
                      putdecl(pr, &decl);
@@ -1695,7 +1711,7 @@ function(struct parser *pr, struct function *fn, const char **pnames, const stru
          siz = typesize(arg.ty);
          nalloc = siz/align + ((siz&(align-1)) != 0);
          EMITS {
-            struct instr alloca = { op, KPTR, mkintcon(fn, KI4, nalloc) };
+            struct instr alloca = { op, KPTR, .l = mkintcon(fn, KI4, nalloc) };
             arg.id = addinstr(fn, alloca).idx;
             genstore(fn, arg.ty, mkref(RTMP, arg.id), mkref(RARG, i));
          }
@@ -2370,7 +2386,8 @@ parse(struct parser *pr)
             putdecl(pr, &decl);
             irinit(&fn);
             function(pr, &fn, st.pnames, st.pspans);
-            if (!nerror) irdump(&fn, decl.name);
+            /* if (!nerror) irdump(&fn, decl.name); */
+            irfini(&fn);
          } else if (decl.name) {
             putdecl(pr, &decl);
             if (st.varini) {
diff --git a/regalloc.c b/regalloc.c
new file mode 100644
index 0000000..4edbcb1
--- /dev/null
+++ b/regalloc.c
@@ -0,0 +1,88 @@
+#include "ir.h"
+
+extern struct instr instr[];
+extern vec_of(struct call) calls;
+extern vec_of(struct phi) phis;
+
+static struct bitset taken[1];
+
+static int
+nextreg(enum irclass cls)
+{
+   int r0, rend, i;
+
+   if (kisint(cls)) {
+      r0 = mctarg->gpr0;
+      rend = mctarg->gpr0 + mctarg->ngpr;
+   } else if (kisflt(cls)) {
+      r0 = mctarg->fpr0;
+      rend = mctarg->fpr0 + mctarg->nfpr;
+   } else assert(0);
+   for (i = r0; i < rend; ++i) {
+      if (!bstest(taken, i)) {
+         bsset(taken, i);
+         return i;
+      }
+   }
+   assert(!"no more reg");
+}
+
+static void
+use(struct block *blk, enum op op, int hint, union ref *ref)
+{
+   struct instr *ins;
+   if (ref->t == REXT) {
+      if (op == Ocall) {
+         struct call *call = &calls.p[ref->idx];
+         for (int i = 0; i < call->narg; ++i)
+            use(blk, 0, 0, &call->args[i]);
+      } else if (op == Ophi) {
+         struct phi *phi = &phis.p[ref->idx];
+         for (int i = 0; i < phi->n; ++i)
+            use(blk, 0, hint, &phi->ref[i]);
+      } else assert("ext?");
+      return;
+   } else if (ref->t != RTMP) return;
+
+   ins = &instr[ref->idx];
+   if (in_range(ins->op, Oalloca1, Oalloca16)) return;
+   if (!ins->reg) {
+      if (op == -1) /* cond branch */
+         if (in_range(ins->op, Oequ, Oulte) && ref->idx == blk->ins.p[blk->ins.n-1])
+            /* result of comparison instr is only used to conditionally branch,
+             * doesn't usually need a reg (handled by isel) */
+            return;
+      ins->reg = hint ? hint : nextreg(ins->cls);
+   }
+}
+
+void
+regalloc(struct function *fn)
+{
+   struct block *blk = fn->entry->lprev;
+   struct instr *ins;
+
+   /* a dumb linear register allocator that visits instructions backwards
+    * starting at the end of the function, when encountering a use of a new
+    * temporary, it allocates a register for it. when encountering the definition
+    * of a temporary, it frees up its register
+    */
+   do {
+      if (blk->jmp.arg.t) use(blk, blk->jmp.t == Jbcnd ? -1 : 0, 0, &blk->jmp.arg);
+      for (int i = blk->phi.n - 1; i >= 0; --i) {
+         ins = &instr[blk->phi.p[i]];
+         bsclr(taken, ins->reg);
+         assert(ins->op == Ophi);
+         use(blk, Ophi, ins->reg, &ins->l);
+      }
+      for (int i = blk->ins.n - 1; i >= 0; --i) {
+         ins = &instr[blk->ins.p[i]];
+         bsclr(taken, ins->reg);
+         if (ins->l.t) use(blk, ins->op, 0, &ins->l);
+         if (ins->r.t) use(blk, ins->op, 0, &ins->r);
+      }
+      blk = blk->lprev;
+   } while (blk != fn->entry->lprev);
+}
+
+/* vim:set ts=3 sw=3 expandtab: */
diff --git a/targ.c b/targ.c
index e323148..da3d86a 100644
--- a/targ.c
+++ b/targ.c
@@ -1,21 +1,24 @@
 #include "common.h"
 
-uchar targ_primsizes[TYPTR+1];
-uchar targ_primalign[TYPTR+1];
-enum typetag targ_sizetype, targ_ptrdifftype;
-bool targ_charsigned, targ_bigendian;
-
+extern const struct mctarg t_amd64_sysv;
 static const struct targ {
    const char *name;
    struct { uchar longsize, vlongsize, ptrsize, valistsize; };
    struct { uchar longalign, vlongalign, doublealign, ptralign; };
    bool charsigned;
    uchar sizetype, ptrdifftype;
+   const struct mctarg *mctarg;
 } targs[] = {
-   { "amd64-sysv", {8, 8, 8, 24}, {8, 8, 8, 8}, 1, TYULONG, TYLONG },
+   { "amd64-sysv", {8, 8, 8, 24}, {8, 8, 8, 8}, 1, TYULONG, TYLONG, &t_amd64_sysv },
    { "i686-sysv",  {4, 8, 4,  8}, {4, 4, 4, 4}, 1, TYUINT, TYINT }
 };
 
+uchar targ_primsizes[TYPTR+1];
+uchar targ_primalign[TYPTR+1];
+enum typetag targ_sizetype, targ_ptrdifftype;
+bool targ_charsigned, targ_bigendian;
+const struct mctarg *mctarg;
+
 void
 targ_init(const char *starg)
 {
@@ -40,4 +43,5 @@ targ_init(const char *starg)
    targ_ptrdifftype = t->ptrdifftype;
    targ_charsigned = t->charsigned;
    targ_bigendian = 0;
+   mctarg = t->mctarg;
 }
diff --git a/test.c b/test.c
index 5adb14f..5bb4e72 100644
--- a/test.c
+++ b/test.c
@@ -15,6 +15,7 @@ struct foo {
     int x, y, z;
 };
 
+
 int test0(struct foo *foo) { return foo->x ? foo->y : foo->z; }
 int test1(int x, int y, int z) { return x && y || z; }
 int test2(int x, int y, int z) { return x || y && z; }
@@ -44,4 +45,22 @@ int test6(int x)
     return !!!!x;
 }
 
+float sqr(float x) { return x * x; }
+
+int mula(int x, int y, int z) {
+    if (x < 0)
+        return -x * y + z;
+    return x * y + z;
+}
+
+void *copy(char *d, char *s, int n) {
+    while (n--)
+        *d++ = *s++;
+    return d;
+}
+
+int hmm(float x, int a, char *p, char *q) {
+    return x > 1 ? a || p : p < q && a > 0;
+}
+
 //