From 82cac0ae5d4e335719445857ab16ffdf05413222 Mon Sep 17 00:00:00 2001
From: lemon <lsof@mailbox.org>
Date: Wed, 31 May 2023 23:31:58 +0200
Subject: regalloc skeleton

---
 regalloc.c | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)
 create mode 100644 regalloc.c

(limited to 'regalloc.c')

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: */
-- 
cgit v1.2.3