use a hashtable for addr refs

7 files changed, 39 insertions, 18 deletions

diff --git a/abi0.c b/abi0.c
index 314017b..83e6a0e 100644
--- a/abi0.c
+++ b/abi0.c
@@ -58,6 +58,7 @@ abiarg(struct abiargsvec *abiargs, int *ni, int *nf, int *ns, union irtype ty)
 static struct instr
 copyparam(struct abiarg abi)
 {
+   struct addr addr = {.base = mkref(RREG, mctarg->bpr), .disp = -abi.stk};
    if (abi.reg >= 0) { /* reg */
       assert(!abi.ty.isagg);
       return mkinstr(Ocopy, abi.ty.cls, mkref(RREG, abi.reg));
@@ -71,11 +72,9 @@ copyparam(struct abiarg abi)
       case KF4: ld = Oloadf4; break;
       case KF8: ld = Oloadf8; break;
       }
-      vpush(&addrtab, ((struct addr) {.base = mkref(RREG, mctarg->bpr), .disp = -abi.stk}));
-      return mkinstr(ld, abi.ty.cls, mkref(RMORE, addrtab.n - 1));
+      return mkinstr(ld, abi.ty.cls, mkaddr(addr));
    } else { /* aggregate in stack */
-      vpush(&addrtab, ((struct addr) {.base = mkref(RREG, mctarg->bpr), .disp = -abi.stk}));
-      return mkinstr(Ocopy, KPTR, mkref(RMORE, addrtab.n - 1));
+      return mkinstr(Ocopy, KPTR, mkaddr(addr));
    }
 }
 
diff --git a/amd64/emit.c b/amd64/emit.c
index 6be080e..1f6e2b4 100644
--- a/amd64/emit.c
+++ b/amd64/emit.c
@@ -104,7 +104,7 @@ mkmemoper(union ref r)
       assert(wop.t == OREG);
       return mkoper(OMEM, .base = wop.reg, .index = NOINDEX);
    } else if (r.t == RMORE) {
-      struct addr *addr = &addrtab.p[r.i];
+      const struct addr *addr = &addrht[r.i];
       struct oper mem;
       if (addr->base.t == RTMP && ioper[addr->base.i].t == OMEM) {
          mem = ioper[addr->base.i];
@@ -432,7 +432,7 @@ gencopy(uchar **pcode, enum irclass cls, struct oper dst, union ref val)
    assert(dst.t == OREG);
    if (val.t == RMORE) {
       /* this is a LEA, but maybe it can be lowered to a 2-address instruction */
-      struct addr *addr = &addrtab.p[val.i];
+      const struct addr *addr = &addrht[val.i];
       if (addr->base.t && dst.reg == mkregoper(addr->base).reg) { /* base = dst */
          if (addr->index.t && !addr->disp && !addr->shift){
             /* lea Rx, [Rx + Ry] -> add Rx, Ry */
diff --git a/amd64/isel.c b/amd64/isel.c
index 3734143..469c56d 100644
--- a/amd64/isel.c
+++ b/amd64/isel.c
@@ -86,7 +86,7 @@ aadd(struct addr *addr, union ref r, bool rec)
          if (!ascale(addr, ins->l, ins->r)) return 0;
          ins->skip = 1;
       } else if (!rec && ins->op == Ocopy && ins->l.t == RMORE) {
-         struct addr save = *addr, *addr2 = &addrtab.p[ins->l.i];
+         struct addr save = *addr, *addr2 = &addrht[ins->l.i];
          if ((!addr2->base.t || aadd(addr, addr2->base, 1))
           && aadd(addr, mkintcon(KI4, addr2->disp), 1)
           && (!addr2->index.t || ascale(addr, addr2->index, mkref(RICON, addr2->shift))))
@@ -121,8 +121,7 @@ fuseaddr(struct function *fn, union ref *r)
 
    if (!aadd(&addr, *r, 0)) return 0;
 
-   vpush(&addrtab, addr);
-   *r = mkref(RMORE, addrtab.n-1);
+   *r = mkaddr(addr);
    return 1;
 }
 
diff --git a/ir.c b/ir.c
index d887fab..5b54d70 100644
--- a/ir.c
+++ b/ir.c
@@ -10,7 +10,7 @@ static int instrfreelist;
 struct calltab calltab;
 struct phitab phitab;
 struct dattab dattab;
-struct addrtab addrtab;
+struct addr addrht[1 << 12];
 
 void
 irinit(struct function *fn)
@@ -18,14 +18,13 @@ irinit(struct function *fn)
    static struct call callsbuf[64];
    static struct phi phisbuf[64];
    static struct irdat datsbuf[64];
-   static struct addr addrsbuf[64];
 
    ninstr = 0;
    instrfreelist = -1;
    vinit(&calltab, callsbuf, arraylength(callsbuf));
    vinit(&phitab, phisbuf, arraylength(phisbuf));
    vinit(&dattab, datsbuf, arraylength(datsbuf));
-   vinit(&addrtab, addrsbuf, arraylength(addrsbuf));
+   memset(addrht, 0, sizeof addrht);
    if (!type2cls[TYINT]) {
       for (int i = TYBOOL; i <= TYUVLONG; ++i) {
          int siz = targ_primsizes[i];
@@ -44,6 +43,23 @@ irinit(struct function *fn)
    fn->entry->lprev = fn->entry->lnext = fn->entry;
 }
 
+static int
+addaddr(const struct addr *addr)
+{
+   uint h = hashb(0, addr, sizeof *addr);
+   uint i = h, n = arraylength(addrht);
+   for (;; ++i) {
+      i &= arraylength(addrht) - 1;
+      if (!addrht[i].base.t && !addrht[i].index.t) {
+         addrht[i] = *addr;
+         return i;
+      } else if (!memcmp(&addrht[i], addr, sizeof *addr)) {
+         return i;
+      }
+      assert(--n > 0 && "addrht full");
+   }
+}
+
 struct xcon conht[1 << 12];
 
 static int
@@ -191,6 +207,12 @@ mkcallarg(union irtype ret, uint narg, int vararg)
    return mkref(RMORE, calltab.n-1);
 }
 
+union ref
+mkaddr(struct addr addr)
+{
+   return mkref(RMORE, addaddr(&addr));
+}
+
 static inline int
 newinstr(void)
 {
diff --git a/ir.h b/ir.h
index e1f9fba..7ff31c8 100644
--- a/ir.h
+++ b/ir.h
@@ -183,7 +183,7 @@ extern struct xcon conht[];
 extern struct calltab {vec_of(struct call);} calltab;
 extern struct phitab {vec_of(struct phi);} phitab;
 extern struct dattab {vec_of(struct irdat);} dattab;
-extern struct addrtab {vec_of(struct addr);} addrtab;
+extern struct addr addrht[];
 #define NOREF ((union ref) {0})
 #define ZEROREF ((union ref) {{ RICON, 0 }})
 #define mkref(t, x) ((union ref) {{ (t), (x) }})
@@ -203,6 +203,7 @@ struct instr mkalloca(uint siz, uint align);
 void conputdat(struct irdat *, uint off, enum typetag t, const void *dat);
 union ref mkcallarg(union irtype ret, uint narg, int vararg);
 #define mkintrin(B, C, N) mkinstr(Ointrin, C, {.t=RICON,B}, mkcallarg((union irtype){{0}},N,-1))
+union ref mkaddr(struct addr);
 union ref addinstr(struct function *, struct instr);
 union ref insertinstr(struct block *, int idx, struct instr);
 void delinstr(struct block *, int idx);
diff --git a/irdump.c b/irdump.c
index c41a196..49bca6b 100644
--- a/irdump.c
+++ b/irdump.c
@@ -116,9 +116,8 @@ dumpref(enum op o, union ref ref)
             dumpref(0, phi->ref[i]);
          }
       } else {
-         struct addr *addr = &addrtab.p[ref.i];
+         const struct addr *addr = &addrht[ref.i];
          bool k = 0;
-         assert(addrtab.n > ref.i);
          efmt("addr [");
          if ((k = addr->base.t)) dumpref(0, addr->base);
          if (addr->index.t) {
diff --git a/regalloc.c b/regalloc.c
index bf7bac6..b90940f 100644
--- a/regalloc.c
+++ b/regalloc.c
@@ -130,9 +130,10 @@ use(struct rega *ra, struct block *blk, int curi, enum op op, int hint, union re
    int excl = other.t == RREG ? other.i : -1;
 
    if (ref->t == RMORE) {
-      struct addr *addr = &addrtab.p[ref->i];
-      if (addr->base.t) use(ra, blk, curi, 0, hint, &addr->base, addr->index);
-      if (addr->index.t) use(ra, blk, curi, 0, hint, &addr->index, NOREF);
+      struct addr addr = addrht[ref->i];
+      if (addr.base.t) use(ra, blk, curi, 0, hint, &addr.base, addr.index);
+      if (addr.index.t) use(ra, blk, curi, 0, hint, &addr.index, NOREF);
+      *ref = mkaddr(addr);
       return;
    } else if (ref->t == RREG) {
       forcetake(ra, ref->i, *ref, blk, curi);