From 9632f2f148bf545fea09f25f34a316ec8ae86256 Mon Sep 17 00:00:00 2001
From: Quentin Carbonneaux <quentin@c9x.me>
Date: Sat, 11 Mar 2023 21:51:10 +0100
Subject: kill dead stores when coalescing slots

This is necessary because, post
fusion, dead stores may clobber
data.  A new test case exposes
one such situation.
---
 mem.c         | 37 ++++++++++++++++++++++++++++++++-----
 test/mem2.ssa | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 64 insertions(+), 5 deletions(-)
 create mode 100644 test/mem2.ssa

diff --git a/mem.c b/mem.c
index 1db632f..8bde4be 100644
--- a/mem.c
+++ b/mem.c
@@ -1,6 +1,7 @@
 #include "all.h"
 
 typedef struct Range Range;
+typedef struct Store Store;
 typedef struct Slot Slot;
 
 /* require use, maintains use counts */
@@ -95,6 +96,11 @@ struct Range {
 	int a, b;
 };
 
+struct Store {
+	int ip;
+	Ins *i;
+};
+
 struct Slot {
 	int t;
 	int sz;
@@ -102,6 +108,8 @@ struct Slot {
 	bits l;
 	Range r;
 	Slot *s;
+	Store *dead;
+	int ndead;
 };
 
 static inline int
@@ -159,15 +167,20 @@ load(Ref r, bits x, int ip, Fn *fn, Slot *sl)
 }
 
 static void
-store(Ref r, bits x, int ip, Fn *fn, Slot *sl)
+store(Ref r, bits x, int ip, Ins *i, Fn *fn, Slot *sl)
 {
 	int64_t off;
 	Slot *s;
 
 	if (slot(&s, &off, r, fn, sl)) {
-		if (s->l)
+		if (s->l) {
 			radd(&s->r, ip);
-		s->l &= ~(x << off);
+			s->l &= ~(x << off);
+		} else {
+			vgrow(&s->dead, ++s->ndead);
+			s->dead[s->ndead-1].ip = ip;
+			s->dead[s->ndead-1].i = i;
+		}
 	}
 }
 
@@ -223,6 +236,8 @@ coalesce(Fn *fn)
 			s->sz = t->alias.u.loc.sz;
 			s->m = t->alias.u.loc.m;
 			s->s = 0;
+			s->dead = vnew(0, sizeof s->dead[0], PHeap);
+			s->ndead = 0;
 		}
 	}
 
@@ -264,14 +279,14 @@ coalesce(Fn *fn)
 			}
 			if (isstore(i->op)) {
 				x = BIT(storesz(i)) - 1;
-				store(arg[1], x, ip--, fn, sl);
+				store(arg[1], x, ip--, i, fn, sl);
 			}
 			if (i->op == Oblit0) {
 				assert((i+1)->op == Oblit1);
 				assert(rtype((i+1)->arg[0]) == RInt);
 				sz = abs(rsval((i+1)->arg[0]));
 				x = sz >= NBit ? (bits)-1 : BIT(sz) - 1;
-				store(arg[1], x, ip--, fn, sl);
+				store(arg[1], x, ip--, i, fn, sl);
 				load(arg[0], x, ip, fn, sl);
 				vgrow(&bl, ++nbl);
 				bl[nbl-1] = i;
@@ -289,6 +304,16 @@ coalesce(Fn *fn)
 	}
 	free(br);
 
+	/* kill dead stores */
+	for (s=sl; s<&sl[nsl]; s++)
+		for (n=0; n<s->ndead; n++)
+			if (!rin(s->r, s->dead[n].ip)) {
+				i = s->dead[n].i;
+				if (i->op == Oblit0)
+					*(i+1) = (Ins){.op = Onop};
+				*i = (Ins){.op = Onop};
+			}
+
 	/* kill slots with an empty live range */
 	total = 0;
 	freed = 0;
@@ -446,5 +471,7 @@ coalesce(Fn *fn)
 		printfn(fn, stderr);
 	}
 
+	for (s=sl; s<&sl[nsl]; s++)
+		vfree(s->dead);
 	vfree(sl);
 }
diff --git a/test/mem2.ssa b/test/mem2.ssa
new file mode 100644
index 0000000..4a136b4
--- /dev/null
+++ b/test/mem2.ssa
@@ -0,0 +1,32 @@
+# Ember Sawady reported this bug
+# in stack-slot coalescing
+
+type :t = { w 2 }
+
+function :t $func() {
+@start.0
+	%temp =l alloc4 4
+	%ret =l alloc4 8
+	storew 1, %temp
+	# storew can also go here
+	%field =l add %ret, 4
+	storew 2, %ret
+	blit %temp, %field, 4
+	# removing either of these storews causes it to work
+	storew 2, %ret
+	ret %ret
+}
+
+export function w $main() {
+@start
+	%ret =:t call $func()
+	%fptr =l add %ret, 4
+	%field =w loaduw %fptr
+	%x =w ceqw %field, 1
+	jnz %x, @passed, @failed
+@failed
+	# this fails despite 1 => temp => ret + 4 => field
+	call $abort()
+@passed
+	ret 0
+}
-- 
cgit 1.4.1