add initial version of copy elimination

4 files changed, 171 insertions, 4 deletions

diff --git a/lisc/Makefile b/lisc/Makefile
index 389e376..6db1153 100644
--- a/lisc/Makefile
+++ b/lisc/Makefile
@@ -1,5 +1,5 @@
 BIN = lisc
-OBJ = main.o util.o parse.o ssa.o live.o isel.o spill.o rega.o emit.o
+OBJ = main.o util.o parse.o ssa.o copy.o live.o isel.o spill.o rega.o emit.o
 
 CFLAGS = -Wall -Wextra -std=c99 -g -pedantic
 
diff --git a/lisc/copy.c b/lisc/copy.c
new file mode 100644
index 0000000..9367e8d
--- /dev/null
+++ b/lisc/copy.c
@@ -0,0 +1,158 @@
+#include "lisc.h"
+
+typedef struct RList RList;
+struct RList {
+	int t;
+	RList *l;
+};
+
+static Ref
+copyof(Ref r, Ref *cp)
+{
+	if (rtype(r) == RTmp)
+		return cp[r.val];
+	else
+		return r;
+}
+
+static void
+update(Ref r, Ref rcp, Ref *cp, RList **w)
+{
+	RList *l;
+
+	if (!req(cp[r.val], rcp)) {
+		cp[r.val] = rcp;
+		l = emalloc(sizeof *l);
+		l->t = r.val;
+		l->l = *w;
+		*w = l;
+	}
+}
+
+static void
+visitphi(Phi *p, Ref *cp, RList **w)
+{
+	uint a;
+	Ref r, r1;
+
+	r = R;
+	for (a=0; a<p->narg; a++) {
+		r1 = copyof(p->arg[a], cp);
+		if (req(r1, R))
+			continue;
+		if (req(r, R) || req(r, r1))
+			r = r1;
+		else {
+			r = p->to;
+			break;
+		}
+	}
+	assert(!req(r, R));
+	update(p->to, r, cp, w);
+}
+
+static void
+visitins(Ins *i, Ref *cp, RList **w)
+{
+	Ref r;
+
+	if (i->op != OCopy) {
+		if (!req(i->to, R)) {
+			assert(rtype(i->to) == RTmp);
+			update(i->to, i->to, cp, w);
+		}
+	} else {
+		assert(rtype(i->to) == RTmp);
+		r = copyof(i->arg[0], cp);
+		update(i->to, r, cp, w);
+	}
+}
+
+void
+copy(Fn *fn)
+{
+	Blk *b;
+	Ref *cp, r;
+	RList *w, *w1;
+	Use *u, *u1;
+	Ins *i;
+	Phi *p, **pp;
+	uint a;
+	int t;
+
+	w = 0;
+	cp = emalloc(fn->ntmp * sizeof cp[0]);
+	for (b=fn->start; b; b=b->link) {
+		for (p=b->phi; p; p=p->link)
+			visitphi(p, cp, &w);
+		for (i=b->ins; i!=&b->ins[b->nins]; i++)
+			visitins(i, cp, &w);
+	}
+	while ((w1=w)) {
+		t = w->t;
+		w = w->l;
+		free(w1);
+		u = fn->tmp[t].use;
+		u1 = u + fn->tmp[t].nuse;
+		for (; u<u1; u++)
+			switch (u->type) {
+			default:
+				diag("copy: invalid use");
+			case UPhi:
+				visitphi(u->u.phi, cp, &w);
+				break;
+			case UIns:
+				visitins(u->u.ins, cp, &w);
+				break;
+			case UJmp:
+				break;
+			}
+	}
+	for (b=fn->start; b; b=b->link) {
+		for (pp=&b->phi; (p=*pp); pp=&p->link) {
+		Again:
+			r = cp[p->to.val];
+			if (!req(r, p->to)) {
+				*pp = p->link;
+				p = *pp;
+				goto Again;
+			}
+			for (a=0; a<p->narg; a++)
+				if (rtype(p->arg[a]) == RTmp) {
+					r = cp[p->arg[a].val];
+					assert(!req(r, R));
+					p->arg[a] = r;
+				}
+		}
+		for (i=b->ins; i!=&b->ins[b->nins]; i++) {
+			r = cp[i->to.val];
+			if (!req(r, i->to)) {
+				*i = (Ins){.op = ONop};
+				continue;
+			}
+			for (a=0; a<2; a++)
+				if (rtype(i->arg[a]) == RTmp) {
+					r = cp[i->arg[a].val];
+					assert(!req(r, R));
+					i->arg[a] = r;
+				}
+		}
+		if (rtype(b->jmp.arg) == RTmp) {
+			r = cp[b->jmp.arg.val];
+			assert(!req(r, R));
+			b->jmp.arg = r;
+		}
+	}
+	if (debug['C']) {
+		fprintf(stderr, "\n> Copy information:");
+		for (t=Tmp0; t<fn->ntmp; t++)
+			if (!req(cp[t], TMP(t))) {
+				fprintf(stderr, "\n%10s copy of ",
+					fn->tmp[t].name);
+				printref(cp[t], fn, stderr);
+			}
+		fprintf(stderr, "\n\n> After copy elimination:\n");
+		printfn(fn, stderr);
+	}
+	free(cp);
+}
diff --git a/lisc/lisc.h b/lisc/lisc.h
index 3643e48..fcce670 100644
--- a/lisc/lisc.h
+++ b/lisc/lisc.h
@@ -257,8 +257,8 @@ struct Use {
 	} type;
 	int bid;
 	union {
-		int ins;
-		Ref phi;
+		Ins *ins;
+		Phi *phi;
 	} u;
 };
 
@@ -371,6 +371,7 @@ void addcon(Con *, Con *);
 extern OpDesc opdesc[NOp];
 void parse(FILE *, void (Dat *), void (Fn *));
 void printfn(Fn *, FILE *);
+void printref(Ref, Fn *, FILE *);
 
 /* ssa.c */
 void filluse(Fn *);
@@ -378,10 +379,14 @@ void fillpreds(Fn *);
 void fillrpo(Fn *);
 void ssa(Fn *);
 
+/* copy.c */
+void copy(Fn *);
+
 /* live.c */
 Bits liveon(Blk *, Blk *);
 void filllive(Fn *);
 
+
 /* isel.c */
 extern int rsave[NRSave];
 extern int rclob[NRClob];
diff --git a/lisc/main.c b/lisc/main.c
index e91d65e..90f8b37 100644
--- a/lisc/main.c
+++ b/lisc/main.c
@@ -3,9 +3,11 @@
 
 char debug['Z'+1] = {
 	['P'] = 0, /* parsing */
-	['C'] = 0, /* call lowering */
+	['A'] = 0, /* abi lowering */
 	['I'] = 0, /* instruction selection */
 	['L'] = 0, /* liveness */
+	['N'] = 0, /* ssa construction */
+	['C'] = 0, /* copy elimination */
 	['S'] = 0, /* spilling */
 	['R'] = 0, /* reg. allocation */
 };
@@ -52,6 +54,8 @@ func(Fn *fn)
 	filluse(fn);
 	ssa(fn);
 	filluse(fn);
+	copy(fn);
+	filluse(fn);
 	isel(fn);
 	filllive(fn);
 	fillcost(fn);