Add pseudo death-note tracking.

Now that we have full pseudo usage lists, we can also add deathnotes to pseudos in the instruction stream. NOTE! We add the deathnote to _before_ the last instruction that uses that pseudo. That looks a bit strange, but it's actually what you want: when we traverse the instuctions, we want to know that the inputs are dead.
author: Linus Torvalds <torvalds@ppc970.osdl.org> 2004-12-02 18:04:06 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:05:26 -0700
commit: b6d2fa5bac3fed9e9242bb626a9ccce1fbb6b419 (patch)
tree: 4720cc323afd4ce2ee87325372841e6ad856a1f3
parent: 5aad28f0caa770be2b69717dba765763c6c3f7b2 (diff)
download: sparse-dev-b6d2fa5bac3fed9e9242bb626a9ccce1fbb6b419.tar.gz
4 files changed, 134 insertions, 58 deletions
diff --git a/flow.h b/flow.h
index 0c0d1d74..cfa4dd54 100644
--- a/flow.h
+++ b/flow.h
@@ -27,6 +27,8 @@ int dominates(pseudo_t pseudo, struct instruction *insn, struct instruction *dom
 
 extern void clear_liveness(struct entrypoint *ep);
 extern void track_pseudo_liveness(struct entrypoint *ep);
+extern void track_pseudo_death(struct entrypoint *ep);
+
 extern void vrfy_flow(struct entrypoint *ep);
 extern int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo);
 
diff --git a/linearize.c b/linearize.c
index 32e8b0ce..78e9936c 100644
--- a/linearize.c
+++ b/linearize.c
@@ -217,6 +217,7 @@ static const char* opcodes[] = {
 	[OP_SNOP] = "snop",
 	[OP_LNOP] = "lnop",
 	[OP_NOP] = "nop",
+	[OP_DEATHNOTE] = "dead",
 
 	/* Sparse tagging (line numbers, context, whatever) */
 	[OP_CONTEXT] = "context",
@@ -396,6 +397,9 @@ void show_instruction(struct instruction *insn)
 	case OP_NOP:
 		buf += sprintf(buf, "%s <- %s", show_pseudo(insn->target), show_pseudo(insn->src1));
 		break;
+	case OP_DEATHNOTE:
+		buf += sprintf(buf, "%s", show_pseudo(insn->target));
+		break;
 	default:
 		break;
 	}
@@ -1846,6 +1850,9 @@ repeat:
 		goto repeat;
 	}
 
+	/* Finally, add deathnotes to pseudos now that we have them */
+	track_pseudo_death(ep);
+
 	return ep;
 }
 
diff --git a/linearize.h b/linearize.h
index f9e5eb6f..506139ab 100644
--- a/linearize.h
+++ b/linearize.h
@@ -158,6 +158,7 @@ enum opcode {
 	OP_SNOP,
 	OP_LNOP,
 	OP_NOP,
+	OP_DEATHNOTE,
 
 	/* Sparse tagging (line numbers, context, whatever) */
 	OP_CONTEXT,
diff --git a/liveness.c b/liveness.c
index 39d3721d..19b65607 100644
--- a/liveness.c
+++ b/liveness.c
@@ -12,56 +12,8 @@
 #include "linearize.h"
 #include "flow.h"
 
-int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
-{
-	pseudo_t old;
-	FOR_EACH_PTR(list,old) {
-		if (old == pseudo)
-			return 1;
-	} END_FOR_EACH_PTR(old);   
-	return 0;
-}
-
-static int liveness_changed;
-
-static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
-{
-	if (!pseudo_in_list(*list, pseudo)) {
-		liveness_changed = 1;
-		add_pseudo(list, pseudo);
-	}
-}
-
-static inline int trackable_pseudo(pseudo_t pseudo)
-{
-	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_PHI);
-}
-
-static void insn_uses(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
-{
-	if (trackable_pseudo(pseudo)) {
-		struct instruction *def = pseudo->def;
-#if 1
-		/*
-		 * This assert is wrong, since this actually _can_ happen for
-		 * truly undefined programs, but it's good for finding bugs.
-		 */
-		assert(def && def->bb);
-#else
-		if (!def || !def->bb)
-			warning(insn->bb->pos, "undef pseudo ;(");
-#endif
-		add_pseudo_exclusive(&bb->needs, pseudo);
-	}
-}
-
-static void insn_defines(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
-{
-	assert(trackable_pseudo(pseudo));
-	add_pseudo(&bb->defines, pseudo);
-}
-
-static void phi_defines(struct instruction * phi_node, pseudo_t target)
+static void phi_defines(struct instruction * phi_node, pseudo_t target,
+	void (*defines)(struct basic_block *, struct instruction *, pseudo_t))
 {
 	pseudo_t phi;
 	FOR_EACH_PTR(phi_node->phi_list, phi) {
@@ -72,19 +24,21 @@ static void phi_defines(struct instruction * phi_node, pseudo_t target)
 		if (!def || !def->bb)
 			continue;
 		if (def->opcode == OP_PHI) {
-			phi_defines(def, target);
+			phi_defines(def, target, defines);
 			continue;
 		}
-		insn_defines(def->bb, phi->def, target);
+		defines(def->bb, phi->def, target);
 	} END_FOR_EACH_PTR(phi);
 }
 
-static void track_instruction_usage(struct basic_block *bb, struct instruction *insn)
+static void track_instruction_usage(struct basic_block *bb, struct instruction *insn,
+	void (*def)(struct basic_block *, struct instruction *, pseudo_t),
+	void (*use)(struct basic_block *, struct instruction *, pseudo_t))
 {
 	pseudo_t pseudo;
 
-	#define USES(x) insn_uses(bb, insn, insn->x)
-	#define DEFINES(x) insn_defines(bb, insn, insn->x)
+	#define USES(x)		use(bb, insn, insn->x)
+	#define DEFINES(x)	def(bb, insn, insn->x)
 
 	switch (insn->opcode) {
 	case OP_RET:
@@ -130,7 +84,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	/* Other */
 	case OP_PHI:
 		/* Phi-nodes are "backwards" nodes. Their def doesn't matter */
-		phi_defines(insn, insn->target);
+		phi_defines(insn, insn->target, def);
 		break;
 
 	case OP_PHISOURCE:
@@ -151,7 +105,7 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 		if (insn->target != VOID)
 			DEFINES(target);
 		FOR_EACH_PTR(insn->arguments, pseudo) {
-			insn_uses(bb, insn, pseudo);
+			use(bb, insn, pseudo);
 		} END_FOR_EACH_PTR(pseudo);
 		break;
 
@@ -176,6 +130,55 @@ static void track_instruction_usage(struct basic_block *bb, struct instruction *
 	}
 }
 
+int pseudo_in_list(struct pseudo_list *list, pseudo_t pseudo)
+{
+	pseudo_t old;
+	FOR_EACH_PTR(list,old) {
+		if (old == pseudo)
+			return 1;
+	} END_FOR_EACH_PTR(old);   
+	return 0;
+}
+
+static int liveness_changed;
+
+static void add_pseudo_exclusive(struct pseudo_list **list, pseudo_t pseudo)
+{
+	if (!pseudo_in_list(*list, pseudo)) {
+		liveness_changed = 1;
+		add_pseudo(list, pseudo);
+	}
+}
+
+static inline int trackable_pseudo(pseudo_t pseudo)
+{
+	return pseudo && (pseudo->type == PSEUDO_REG || pseudo->type == PSEUDO_PHI);
+}
+
+static void insn_uses(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
+{
+	if (trackable_pseudo(pseudo)) {
+		struct instruction *def = pseudo->def;
+#if 1
+		/*
+		 * This assert is wrong, since this actually _can_ happen for
+		 * truly undefined programs, but it's good for finding bugs.
+		 */
+		assert(def && def->bb);
+#else
+		if (!def || !def->bb)
+			warning(insn->bb->pos, "undef pseudo ;(");
+#endif
+		add_pseudo_exclusive(&bb->needs, pseudo);
+	}
+}
+
+static void insn_defines(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
+{
+	assert(trackable_pseudo(pseudo));
+	add_pseudo(&bb->defines, pseudo);
+}
+
 static void track_bb_liveness(struct basic_block *bb)
 {
 	pseudo_t needs;
@@ -226,7 +229,7 @@ void track_pseudo_liveness(struct entrypoint *ep)
 			if (!insn->bb)
 				continue;
 			assert(insn->bb == bb);
-			track_instruction_usage(bb, insn);
+			track_instruction_usage(bb, insn, insn_defines, insn_uses);
 		} END_FOR_EACH_PTR(insn);
 	} END_FOR_EACH_PTR(bb);
 
@@ -262,3 +265,66 @@ is_used:
 		PACK_PTR_LIST(&bb->defines);
 	} END_FOR_EACH_PTR(bb);
 }
+
+static void merge_pseudo_list(struct pseudo_list *src, struct pseudo_list **dest)
+{
+	pseudo_t pseudo;
+	FOR_EACH_PTR(src, pseudo) {
+		add_pseudo_exclusive(dest, pseudo);
+	} END_FOR_EACH_PTR(pseudo);
+}
+
+static struct pseudo_list **live_list;
+static struct pseudo_list *dead_list;
+
+static void death_def(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
+{
+}
+
+static void death_use(struct basic_block *bb, struct instruction *insn, pseudo_t pseudo)
+{
+	if (trackable_pseudo(pseudo) && !pseudo_in_list(*live_list, pseudo)) {
+		add_pseudo(&dead_list, pseudo);
+		add_pseudo(live_list, pseudo);
+	}
+}
+
+static void track_pseudo_death_bb(struct basic_block *bb)
+{
+	struct pseudo_list *live = NULL;
+	struct basic_block *child;
+	struct instruction *insn;
+
+	FOR_EACH_PTR(bb->children, child) {
+		merge_pseudo_list(child->needs, &live);
+	} END_FOR_EACH_PTR(child);
+
+	live_list = &live;
+	FOR_EACH_PTR_REVERSE(bb->insns, insn) {
+		if (!insn->bb)
+			continue;
+		dead_list = NULL;
+		track_instruction_usage(bb, insn, death_def, death_use);
+		if (dead_list) {
+			pseudo_t dead;
+			FOR_EACH_PTR(dead_list, dead) {
+				struct instruction *deathnote = __alloc_instruction(0);
+				deathnote->bb = bb;
+				deathnote->opcode = OP_DEATHNOTE;
+				deathnote->target = dead;
+				INSERT_CURRENT(deathnote, insn);
+			} END_FOR_EACH_PTR(dead);
+			free_ptr_list(&dead_list);
+		}
+	} END_FOR_EACH_PTR_REVERSE(insn);
+	free_ptr_list(&live);
+}
+
+void track_pseudo_death(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		track_pseudo_death_bb(bb);
+	} END_FOR_EACH_PTR(bb);
+}
author	Linus Torvalds <torvalds@ppc970.osdl.org>	2004-12-02 18:04:06 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:05:26 -0700
commit	b6d2fa5bac3fed9e9242bb626a9ccce1fbb6b419 (patch)
tree	4720cc323afd4ce2ee87325372841e6ad856a1f3
parent	5aad28f0caa770be2b69717dba765763c6c3f7b2 (diff)
download	sparse-dev-b6d2fa5bac3fed9e9242bb626a9ccce1fbb6b419.tar.gz