commit 7abf421ea2b88ba8c2e08365cd2385ebe34f9d30
parent 5b54910adcd012c98da49bcbffb89cdd5acaef47
Author: Quentin Carbonneaux <quentin.carbonneaux@yale.edu>
Date: Sat, 31 Oct 2015 23:39:52 -0400
make phi-class handling more local
The phi classes are no longer in a union-find
structure, instead each temporary argument of
a phi node gets a pointer to it. The hinting
of the phi node is then shared with its the
one of its arguments. When liveness proceeds
and finds out that two elements with same
hinting (a phi node and one of its arguments
or two arguments of the same phi node)
interfere, one of them has its phi pointer
reset, that way, the hinting won't be shared.
Diffstat:
6 files changed, 23 insertions(+), 59 deletions(-)
diff --git a/lisc/lisc.h b/lisc/lisc.h
@@ -347,8 +347,6 @@ void printfn(Fn *, FILE *);
/* ssa.c */
void fillpreds(Fn *);
void fillrpo(Fn *);
-int phirepr(Tmp *, int);
-void fillphi(Fn *);
void ssafix(Fn *, int);
/* live.c */
diff --git a/lisc/live.c b/lisc/live.c
@@ -18,23 +18,32 @@ liveon(Blk *b, Blk *s)
return v;
}
+static int
+phitmp(int t, Tmp *tmp)
+{
+ int tp;
+
+ tp = tmp[t].phi;
+ return tp ? tp : t;
+}
+
static void
phifix(int t1, short *phi, Tmp *tmp)
{
int t, t2;
- /* detect temporaries in the same
- * phi-class that interfere and
- * separate them
+ /* detect temporaries arguments
+ * of the same phi node that
+ * interfere and separate them
*/
- t = phirepr(tmp, t1);
+ t = phitmp(t1, tmp);
t2 = phi[t];
if (t2 && t2 != t1) {
- if (tmp[t1].phi != t1) {
- tmp[t1].phi = t1;
+ if (t != t1) {
+ tmp[t1].phi = 0;
t = t1;
} else {
- tmp[t2].phi = t2;
+ tmp[t2].phi = 0;
phi[t2] = t2;
}
}
@@ -115,7 +124,7 @@ Again:
nlv -= BGET(b->in, i->to.val);
BSET(b->gen, i->to.val);
BCLR(b->in, i->to.val);
- t = phirepr(f->tmp, i->to.val);
+ t = phitmp(i->to.val, f->tmp);
phi[t] = 0;
}
for (m=0; m<2; m++)
diff --git a/lisc/main.c b/lisc/main.c
@@ -50,7 +50,6 @@ func(Fn *fn)
isel(fn);
fillrpo(fn);
fillpreds(fn);
- fillphi(fn);
filllive(fn);
fillcost(fn);
spill(fn);
diff --git a/lisc/parse.c b/lisc/parse.c
@@ -547,6 +547,8 @@ DoOp:
arg[i] = parseref();
if (req(arg[i], R))
err("invalid instruction argument");
+ if (op == -1 && rtype(arg[i]) == RTmp)
+ tmp[arg[i].val].phi = r.val;
i++;
t = peek();
if (t == TNL)
diff --git a/lisc/rega.c b/lisc/rega.c
@@ -25,8 +25,10 @@ static int cpm, npm; /* capacity and size of pm */
static int *
hint(int t)
{
- t = phirepr(tmp, t);
- return &tmp[t].hint;
+ if (tmp[t].phi)
+ return &tmp[tmp[t].phi].hint;
+ else
+ return &tmp[t].hint;
}
static int
diff --git a/lisc/ssa.c b/lisc/ssa.c
@@ -87,52 +87,6 @@ fillrpo(Fn *f)
}
}
-/* gets the representant for the phi class of t
- */
-int
-phirepr(Tmp *tmp, int t)
-{
- int tp;
-
- tp = tmp[t].phi;
- if (tp == 0)
- tp = t;
- else if (tp != t) {
- tp = phirepr(tmp, tp);
- tmp[t].phi = tp;
- }
- return tp;
-}
-
-/* fill union find data for phi classes
- */
-void
-fillphi(Fn *fn)
-{
- Blk *b;
- Phi *p;
- uint a;
- int t, ta;
- Tmp *tmp;
-
- tmp = fn->tmp;
- for (t=Tmp0; t<fn->ntmp; t++)
- tmp[t].phi = 0;
- for (b=fn->start; b; b=b->link)
- for (p=b->phi; p; p=p->link) {
- t = p->to.val;
- if (tmp[t].phi == 0)
- tmp[t].phi = t;
- for (a=0; a<p->narg; a++) {
- if (rtype(p->arg[a]) != RTmp)
- continue;
- ta = p->arg[a].val;
- ta = phirepr(tmp, ta);
- tmp[ta].phi = t;
- }
- }
-}
-
static Ref *top, *bot;
static Ref topdef(Blk *, Fn *, int);
