Move instruction simplification to new file "simplify.c".

Also, allow marking a pseudo unused by setting it to VOID, which just disables further renaming of that use. This is needed to make phi-source instructions (that can be shared among multiple phi-nodes thanks to CSE) be collectable. We used to just mark the phi source dead, but that was wrong, since _another_ phi node might be using it.
author: Linus Torvalds <torvalds@ppc970.osdl.org> 2004-11-25 10:37:34 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:04:49 -0700
commit: 384b8be31a6ae2813867cea7fcccc464b788b812 (patch)
tree: 99e95fc21f76ebf3899819a1a8c91720a4309e85
parent: 0cde10b1951b7175edab953b3325f8c0c990eea1 (diff)
download: sparse-dev-384b8be31a6ae2813867cea7fcccc464b788b812.tar.gz
5 files changed, 242 insertions, 196 deletions
diff --git a/Makefile b/Makefile
index 0e9ba646..3656c689 100644
--- a/Makefile
+++ b/Makefile
@@ -13,7 +13,7 @@ LIB_H=    token.h parse.h lib.h symbol.h scope.h expression.h target.h \
 
 LIB_OBJS= target.o parse.o tokenize.o pre-process.o symbol.o lib.o scope.o \
 	  expression.o show-parse.o evaluate.o expand.o inline.o linearize.o \
-	  sort.o flow.o cse.o compat-$(OS).o
+	  sort.o flow.o cse.o simplify.o compat-$(OS).o
 
 LIB_FILE= sparse.a
 LIBS=$(LIB_FILE)
@@ -73,6 +73,7 @@ expand.o: $(LIB_H)
 linearize.o: $(LIB_H)
 flow.o: $(LIB_H)
 cse.o: $(LIB_H)
+simplify.o: $(LIB_H)
 sort.o: $(LIB_H)
 inline.o: $(LIB_H)
 target.o: $(LIB_H)
diff --git a/cse.c b/cse.c
index 8c00a6b9..016c7f52 100644
--- a/cse.c
+++ b/cse.c
@@ -36,187 +36,6 @@ static int phi_compare(pseudo_t phi1, pseudo_t phi2)
 	return 0;
 }
 
-/* Find the trivial parent for a phi-source */
-static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
-{
-	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
-	if (pseudo->type == PSEUDO_REG) {
-		struct instruction *def = pseudo->def;
-		if (def->bb == source)
-			return source;
-	}
-	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
-		return source;
-	return first_basic_block(source->parents);
-}
-
-static void clear_phi(struct instruction *insn)
-{
-	pseudo_t phi;
-
-	insn->bb = NULL;
-	FOR_EACH_PTR(insn->phi_list, phi) {
-		struct instruction *def = phi->def;
-		def->bb = NULL;
-	} END_FOR_EACH_PTR(phi);
-}
-
-static void if_convert_phi(struct instruction *insn)
-{
-	pseudo_t array[3];
-	struct basic_block *parents[3];
-	struct basic_block *bb, *bb1, *bb2, *source;
-	struct instruction *br;
-	pseudo_t p1, p2;
-
-	bb = insn->bb;
-	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
-		return;
-	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
-		return;
-	p1 = array[0]->def->src1;
-	bb1 = array[0]->def->bb;
-	p2 = array[1]->def->src1;
-	bb2 = array[1]->def->bb;
-
-	/* Only try the simple "direct parents" case */
-	if ((bb1 != parents[0] || bb2 != parents[1]) &&
-	    (bb1 != parents[1] || bb2 != parents[0]))
-		return;
-
-	/*
-	 * See if we can find a common source for this..
-	 */
-	source = phi_parent(bb1, p1);
-	if (phi_parent(bb2, p2) != source)
-		return;
-
-	/*
-	 * Cool. We now know that 'source' is the exclusive
-	 * parent of both phi-nodes, so the exit at the
-	 * end of it fully determines which one it is, and
-	 * we can turn it into a select.
-	 *
-	 * HOWEVER, right now we only handle regular
-	 * conditional branches. No multijumps or computed
-	 * stuff. Verify that here.
-	 */
-	br = last_instruction(source->insns);
-	if (!br || br->opcode != OP_BR)
-		return;
-
-	/*
-	 * We're in business. Match up true/false with p1/p2.
-	 */
-	if (br->bb_true == bb2 || br->bb_false == bb1) {
-		pseudo_t p = p1;
-		p1 = p2;
-		p2 = p;
-	}
-
-	/*
-	 * Ok, we can now replace that last
-	 *
-	 *	br cond, a, b
-	 *
-	 * with the sequence
-	 *
-	 *	setcc cond
-	 *	select pseudo, p1, p2
-	 *	br cond, a, b
-	 *
-	 * and remove the phi-node. If it then
-	 * turns out that 'a' or 'b' is entirely
-	 * empty (common case), and now no longer
-	 * a phi-source, we'll be able to simplify
-	 * the conditional branch too.
-	 */
-	insert_select(source, br, insn, p1, p2);
-	clear_phi(insn);
-	cse_repeat = 1;
-}
-
-static unsigned long clean_up_phi(struct instruction *insn)
-{
-	pseudo_t phi;
-	struct instruction *last;
-	unsigned long hash = 0;
-	int same;
-
-	last = NULL;
-	same = 1;
-	FOR_EACH_PTR(insn->phi_list, phi) {
-		struct instruction *def = phi->def;
-		if (def->src1 == VOID)
-			continue;
-		if (last) {
-			if (last->src1 != def->src1)
-				same = 0;
-			continue;
-		}
-		last = def;
-		hash += hashval(def->src1);
-		hash += hashval(def->bb);
-	} END_FOR_EACH_PTR(phi);
-
-	if (same) {
-		pseudo_t pseudo = last ? last->src1 : VOID;
-		convert_instruction_target(insn, pseudo);
-		cse_repeat = 1;
-		insn->bb = NULL;
-		/* This one is bogus, but no worse than anything else */
-		return hash;
-	}
-
-	if_convert_phi(insn);
-
-	return hash;
-}
-
-static void try_to_kill(struct instruction *);
-
-static void kill_use(pseudo_t pseudo)
-{
-	if (pseudo->type == PSEUDO_REG) {
-		if (ptr_list_size((struct ptr_list *)pseudo->users) == 1) {
-			try_to_kill(pseudo->def);
-		}
-	}
-}
-
-static void try_to_kill(struct instruction *insn)
-{
-	int opcode = insn->opcode;
-	switch (opcode) {
-	case OP_BINARY ... OP_BINCMP_END:
-		insn->bb = NULL;
-		kill_use(insn->src1);
-		kill_use(insn->src2);
-		return;
-	case OP_NOT: case OP_NEG:
-		insn->bb = NULL;
-		kill_use(insn->src1);
-		return;
-
-	case OP_PHI: case OP_SETVAL:
-		insn->bb = NULL;
-		return;
-	}
-}
-
-/*
- * Kill trivially dead instructions
- */
-static int dead_insn(struct instruction *insn, pseudo_t src1, pseudo_t src2)
-{
-	if (!insn->target->users) {
-		insn->bb = NULL;
-		kill_use(src1);
-		kill_use(src2);
-		return 1;
-	}
-	return 0;
-}
 
 static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
 {
@@ -225,6 +44,8 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 	if (!insn->bb)
 		return;
 	assert(insn->bb == bb);
+	if (simplify_instruction(insn))
+		cse_repeat = 1;
 	hash = insn->opcode;
 	switch (insn->opcode) {	
 
@@ -245,34 +66,33 @@ static void clean_up_one_instruction(struct basic_block *bb, struct instruction
 	case OP_SET_LT: case OP_SET_GT:
 	case OP_SET_B:  case OP_SET_A:
 	case OP_SET_BE: case OP_SET_AE:
-		if (dead_insn(insn, insn->src1, insn->src2))
-			return;
 		hash += hashval(insn->src1);
 		hash += hashval(insn->src2);
 		break;
 	
 	/* Unary */
 	case OP_NOT: case OP_NEG:
-		if (dead_insn(insn, insn->src1, VOID))
-			return;
 		hash += hashval(insn->src1);
 		break;
 
 	case OP_SETVAL:
-		if (dead_insn(insn, VOID, VOID))
-			return;
 		hash += hashval(insn->val);
 		hash += hashval(insn->symbol);
 		break;
 
 	/* Other */
-	case OP_PHI:
-		if (dead_insn(insn, VOID, VOID)) {
-			clear_phi(insn);
-			return;
-		}
-		hash += clean_up_phi(insn);
+	case OP_PHI: {
+		pseudo_t phi;
+		FOR_EACH_PTR(insn->phi_list, phi) {
+			struct instruction *def;
+			if (phi == VOID)
+				continue;
+			def = phi->def;
+			hash += hashval(def->src1);
+			hash += hashval(def->bb);
+		} END_FOR_EACH_PTR(phi);
 		break;
+	}
 
 	case OP_PHISOURCE:
 		hash += hashval(insn->src1);
@@ -315,6 +135,11 @@ static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
 	for (;;) {
 		int cmp;
 
+		while (phi1 == VOID)
+			NEXT_PTR_LIST(phi1);
+		while (phi2 == VOID)
+			NEXT_PTR_LIST(phi2);
+
 		if (!phi1)
 			return phi2 ? -1 : 0;
 		if (!phi2)
diff --git a/flow.c b/flow.c
index 4643251d..fcae77bc 100644
--- a/flow.c
+++ b/flow.c
@@ -146,8 +146,10 @@ void convert_instruction_target(struct instruction *insn, pseudo_t src)
 	 */
 	target = insn->target;
 	FOR_EACH_PTR(target->users, usep) {
-		assert(*usep == target);
-		*usep = src;
+		if (*usep != VOID) {
+			assert(*usep == target);
+			*usep = src;
+		}
 	} END_FOR_EACH_PTR(usep);
 	concat_user_list(target->users, &src->users);
 	target->users = NULL;
diff --git a/flow.h b/flow.h
index 14a91d98..0b3a4002 100644
--- a/flow.h
+++ b/flow.h
@@ -9,5 +9,6 @@ extern void pack_basic_blocks(struct entrypoint *ep);
 
 extern void convert_instruction_target(struct instruction *insn, pseudo_t src);
 extern void cleanup_and_cse(struct entrypoint *ep);
+extern int simplify_instruction(struct instruction *);
 
 #endif
diff --git a/simplify.c b/simplify.c
new file mode 100644
index 00000000..506c40c6
--- /dev/null
+++ b/simplify.c
@@ -0,0 +1,217 @@
+/*
+ * Simplify - do instruction simplification before CSE
+ *
+ * Copyright (C) 2004 Linus Torvalds
+ */
+
+#include "parse.h"
+#include "expression.h"
+#include "linearize.h"
+#include "flow.h"
+
+
+/* Find the trivial parent for a phi-source */
+static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
+{
+	/* Can't go upwards if the pseudo is defined in the bb it came from.. */
+	if (pseudo->type == PSEUDO_REG) {
+		struct instruction *def = pseudo->def;
+		if (def->bb == source)
+			return source;
+	}
+	if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
+		return source;
+	return first_basic_block(source->parents);
+}
+
+static void clear_phi(struct instruction *insn)
+{
+	pseudo_t phi;
+
+	insn->bb = NULL;
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		*THIS_ADDRESS(phi) = VOID;
+	} END_FOR_EACH_PTR(phi);
+}
+
+static int if_convert_phi(struct instruction *insn)
+{
+	pseudo_t array[3];
+	struct basic_block *parents[3];
+	struct basic_block *bb, *bb1, *bb2, *source;
+	struct instruction *br;
+	pseudo_t p1, p2;
+
+	bb = insn->bb;
+	if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
+		return 0;
+	if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
+		return 0;
+	p1 = array[0]->def->src1;
+	bb1 = array[0]->def->bb;
+	p2 = array[1]->def->src1;
+	bb2 = array[1]->def->bb;
+
+	/* Only try the simple "direct parents" case */
+	if ((bb1 != parents[0] || bb2 != parents[1]) &&
+	    (bb1 != parents[1] || bb2 != parents[0]))
+		return 0;
+
+	/*
+	 * See if we can find a common source for this..
+	 */
+	source = phi_parent(bb1, p1);
+	if (phi_parent(bb2, p2) != source)
+		return 0;
+
+	/*
+	 * Cool. We now know that 'source' is the exclusive
+	 * parent of both phi-nodes, so the exit at the
+	 * end of it fully determines which one it is, and
+	 * we can turn it into a select.
+	 *
+	 * HOWEVER, right now we only handle regular
+	 * conditional branches. No multijumps or computed
+	 * stuff. Verify that here.
+	 */
+	br = last_instruction(source->insns);
+	if (!br || br->opcode != OP_BR)
+		return 0;
+
+	/*
+	 * We're in business. Match up true/false with p1/p2.
+	 */
+	if (br->bb_true == bb2 || br->bb_false == bb1) {
+		pseudo_t p = p1;
+		p1 = p2;
+		p2 = p;
+	}
+
+	/*
+	 * Ok, we can now replace that last
+	 *
+	 *	br cond, a, b
+	 *
+	 * with the sequence
+	 *
+	 *	setcc cond
+	 *	select pseudo, p1, p2
+	 *	br cond, a, b
+	 *
+	 * and remove the phi-node. If it then
+	 * turns out that 'a' or 'b' is entirely
+	 * empty (common case), and now no longer
+	 * a phi-source, we'll be able to simplify
+	 * the conditional branch too.
+	 */
+	insert_select(source, br, insn, p1, p2);
+	clear_phi(insn);
+	return 1;
+}
+
+static int clean_up_phi(struct instruction *insn)
+{
+	pseudo_t phi;
+	struct instruction *last;
+	int same;
+
+	last = NULL;
+	same = 1;
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		struct instruction *def = phi->def;
+		if (def->src1 == VOID)
+			continue;
+		if (last) {
+			if (last->src1 != def->src1)
+				same = 0;
+			continue;
+		}
+		last = def;
+	} END_FOR_EACH_PTR(phi);
+
+	if (same) {
+		pseudo_t pseudo = last ? last->src1 : VOID;
+		convert_instruction_target(insn, pseudo);
+		insn->bb = NULL;
+		return 1;
+	}
+
+	return if_convert_phi(insn);
+}
+
+static void try_to_kill(struct instruction *);
+
+static void kill_use(pseudo_t pseudo)
+{
+	if (pseudo->type == PSEUDO_REG) {
+		if (ptr_list_size((struct ptr_list *)pseudo->users) == 1) {
+			try_to_kill(pseudo->def);
+		}
+	}
+}
+
+static void try_to_kill(struct instruction *insn)
+{
+	int opcode = insn->opcode;
+	switch (opcode) {
+	case OP_BINARY ... OP_BINCMP_END:
+		insn->bb = NULL;
+		kill_use(insn->src1);
+		kill_use(insn->src2);
+		return;
+	case OP_NOT: case OP_NEG:
+		insn->bb = NULL;
+		kill_use(insn->src1);
+		return;
+
+	case OP_PHI: case OP_SETVAL:
+		insn->bb = NULL;
+		return;
+	}
+}
+
+/*
+ * Kill trivially dead instructions
+ */
+static int dead_insn(struct instruction *insn, pseudo_t src1, pseudo_t src2)
+{
+	pseudo_t *usep;
+	FOR_EACH_PTR(insn->target->users, usep) {
+		if (*usep != VOID)
+			return 0;
+	} END_FOR_EACH_PTR(usep);
+
+	insn->bb = NULL;
+	kill_use(src1);
+	kill_use(src2);
+	return 1;
+}
+
+int simplify_instruction(struct instruction *insn)
+{
+	switch (insn->opcode) {
+	case OP_BINARY ... OP_BINCMP_END:
+		if (dead_insn(insn, insn->src1, insn->src2))
+			return 1;
+		break;
+	case OP_NOT: case OP_NEG:
+		if (dead_insn(insn, insn->src1, VOID))
+			return 1;
+		break;
+	case OP_SETVAL:
+		if (dead_insn(insn, VOID, VOID))
+			return 1;
+		break;
+	case OP_PHI:
+		if (dead_insn(insn, VOID, VOID)) {
+			clear_phi(insn);
+			return 1;
+		}
+		return clean_up_phi(insn);
+	case OP_PHISOURCE:
+		if (dead_insn(insn, insn->src1, VOID))
+			return 1;
+		break;
+	}
+	return 0;
+}
author	Linus Torvalds <torvalds@ppc970.osdl.org>	2004-11-25 10:37:34 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:04:49 -0700
commit	384b8be31a6ae2813867cea7fcccc464b788b812 (patch)
tree	99e95fc21f76ebf3899819a1a8c91720a4309e85
parent	0cde10b1951b7175edab953b3325f8c0c990eea1 (diff)
download	sparse-dev-384b8be31a6ae2813867cea7fcccc464b788b812.tar.gz