Add initial CSE pass

It ain't very smart yet, but give it time. In particular, right now it gathers information for the whole function, but it only does the actual replacement if the instructions are in the same basic block.
author: Linus Torvalds <torvalds@ppc970.osdl.org> 2004-11-23 13:26:50 -0700
committer: Linus Torvalds <torvalds@ppc970.osdl.org> 2005-04-07 21:04:35 -0700
commit: fe8df476cce241da882b6895b219e082ad3960f2 (patch)
tree: c1d2d6677ed26e25ad8dedfbcbbfa19d9b8d3d19
parent: 34038a899aa290c162229cab3289264961fd1772 (diff)
download: sparse-dev-fe8df476cce241da882b6895b219e082ad3960f2.tar.gz
5 files changed, 304 insertions, 13 deletions
diff --git a/Makefile b/Makefile
index 2057c4fb..f57f4954 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 compat-$(OS).o
+	  sort.o flow.o cse.o compat-$(OS).o
 
 LIB_FILE= sparse.a
 LIBS=$(LIB_FILE)
diff --git a/cse.c b/cse.c
new file mode 100644
index 00000000..165fe55d
--- /dev/null
+++ b/cse.c
@@ -0,0 +1,291 @@
+/*
+ * CSE - walk the linearized instruction flow, and
+ * see if we can simplify it and apply CSE on it.
+ *
+ * Copyright (C) 2004 Linus Torvalds
+ */
+
+#include <string.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <stddef.h>
+
+#include "parse.h"
+#include "expression.h"
+#include "linearize.h"
+#include "flow.h"
+
+#define INSN_HASH_SIZE 65536
+static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
+
+#define hashval(x) ((unsigned long)(x))
+
+static int phi_compare(const void *_phi1, const void *_phi2)
+{
+	const struct phi *phi1 = _phi1;
+	const struct phi *phi2 = _phi2;
+
+	if (phi1->pseudo != phi2->pseudo)
+		return phi1->pseudo < phi2->pseudo ? -1 : 1;
+	if (phi1->source != phi2->source)
+		return phi1->source < phi2->source ? -1 : 1;
+	return 0;
+}
+
+static void sort_phi_list(struct phi_list **list)
+{
+	sort_list((struct ptr_list **)list , phi_compare);
+}
+
+static unsigned long clean_up_phi(struct instruction *insn)
+{
+	struct phi *phi, *last;
+	unsigned long hash = 0;
+
+	sort_phi_list(&insn->phi_list);
+
+	last = NULL;
+	FOR_EACH_PTR(insn->phi_list, phi) {
+		if (last) {
+			if (last->pseudo == phi->pseudo &&
+			    last->source == phi->source) {
+				DELETE_CURRENT_PTR(phi);
+				continue;
+			}
+		}
+		last = phi;
+		hash += hashval(phi->pseudo);
+		hash += hashval(phi->source);
+	} END_FOR_EACH_PTR(phi);
+	return hash;
+}
+
+static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
+{
+	unsigned long hash;
+
+	if (insn->bb != bb)
+		warning(bb->pos, "instruction with bad bb");
+	hash = insn->opcode;
+	switch (insn->opcode) {	
+
+	/* Binary arithmetic */
+	case OP_ADD: case OP_SUB:
+	case OP_MUL: case OP_DIV:
+	case OP_MOD: case OP_SHL:
+	case OP_SHR: case OP_SEL:
+	case OP_AND: case OP_OR:
+
+	/* Binary logical */
+	case OP_XOR: case OP_AND_BOOL:
+	case OP_OR_BOOL:
+
+	/* Binary comparison */
+	case OP_SET_EQ: case OP_SET_NE:
+	case OP_SET_LE: case OP_SET_GE:
+	case OP_SET_LT: case OP_SET_GT:
+	case OP_SET_B:  case OP_SET_A:
+	case OP_SET_BE: case OP_SET_AE:
+		hash += hashval(insn->src1);
+		hash += hashval(insn->src2);
+		break;
+	
+	/* Unary */
+	case OP_NOT: case OP_NEG:
+		hash += hashval(insn->src1);
+		break;
+
+	case OP_SETVAL:
+		hash += hashval(insn->val);
+		hash += hashval(insn->symbol);
+		break;
+
+	/* Other */
+	case OP_PHI:
+		hash += clean_up_phi(insn);
+		break;
+
+	default:
+		/*
+		 * Nothing to do, don't even bother hashing them,
+		 * we're not going to try to CSE them
+		 */
+		return;
+	}
+	hash += hash >> 16;
+	hash &= INSN_HASH_SIZE-1;
+	add_instruction(insn_hash_table + hash, insn);
+}
+
+static void clean_up_insns(struct entrypoint *ep)
+{
+	struct basic_block *bb;
+
+	FOR_EACH_PTR(ep->bbs, bb) {
+		struct instruction *insn;
+		FOR_EACH_PTR(bb->insns, insn) {
+			clean_up_one_instruction(bb, insn);
+		} END_FOR_EACH_PTR(insn);
+	} END_FOR_EACH_PTR(bb);
+}
+
+extern void show_instruction(struct instruction *);
+
+/* Compare two (sorted) phi-lists */
+static int phi_list_compare(struct phi_list *l1, struct phi_list *l2)
+{
+	struct phi *phi1, *phi2;
+
+	PREPARE_PTR_LIST(l1, phi1);
+	PREPARE_PTR_LIST(l2, phi2);
+	for (;;) {
+		int cmp;
+
+		if (!phi1)
+			return phi2 ? -1 : 0;
+		if (!phi2)
+			return phi1 ? 1 : 0;
+		cmp = phi_compare(phi1, phi2);
+		if (cmp)
+			return cmp;
+		NEXT_PTR_LIST(phi1);
+		NEXT_PTR_LIST(phi2);
+	}
+	/* Not reached, but we need to make the nesting come out right */
+	FINISH_PTR_LIST(phi2);
+	FINISH_PTR_LIST(phi1);
+}
+
+static int insn_compare(const void *_i1, const void *_i2)
+{
+	const struct instruction *i1 = _i1;
+	const struct instruction *i2 = _i2;
+
+	if (i1->opcode != i2->opcode)
+		return i1->opcode < i2->opcode ? -1 : 1;
+
+	switch (i1->opcode) {
+
+	/* Binary arithmetic */
+	case OP_ADD: case OP_SUB:
+	case OP_MUL: case OP_DIV:
+	case OP_MOD: case OP_SHL:
+	case OP_SHR: case OP_SEL:
+	case OP_AND: case OP_OR:
+
+	/* Binary logical */
+	case OP_XOR: case OP_AND_BOOL:
+	case OP_OR_BOOL:
+
+	/* Binary comparison */
+	case OP_SET_EQ: case OP_SET_NE:
+	case OP_SET_LE: case OP_SET_GE:
+	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 (i1->src1 != i2->src1)
+			return i1->src1 < i2->src1 ? -1 : 1;
+		if (i1->src2 != i2->src2)
+			return i1->src2 < i2->src2 ? -1 : 1;
+		break;
+
+	/* Unary */
+	case OP_NOT: case OP_NEG:
+		if (i1->src1 != i2->src1)
+			return i1->src1 < i2->src1 ? -1 : 1;
+		break;
+
+	case OP_SETVAL:
+		if (i1->val != i2->val)
+			return i1->val < i2->val ? -1 : 1;
+		if (i1->symbol != i2->symbol)
+			return i1->symbol < i2->symbol ? -1 : 1;
+		break;
+
+	/* Other */
+	case OP_PHI:
+		return phi_list_compare(i1->phi_list, i2->phi_list);
+
+	default:
+		warning(i1->bb->pos, "bad instruction on hash chain");
+	}
+	return 0;
+}
+
+static void sort_instruction_list(struct instruction_list **list)
+{
+	sort_list((struct ptr_list **)list , insn_compare);
+}
+
+static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
+{
+	/* We re-use the "convert_load_insn()" function. Does the same thing */
+	convert_load_insn(insn, def->target);
+	return def;
+}
+
+static struct instruction * try_to_cse(struct instruction *i1, struct instruction *i2)
+{
+	struct basic_block *b1, *b2;
+
+	/*
+	 * Ok, i1 and i2 are the same instruction, modulo "target".
+	 * We should now see if we can combine them.
+	 */
+	b1 = i1->bb;
+	b2 = i2->bb;
+
+	/*
+	 * Currently we only handle the uninteresting degenerate case where
+	 * the CSE is inside one basic-block.
+	 */
+	if (b1 == b2) {
+		struct instruction *insn;
+		FOR_EACH_PTR(b1->insns, insn) {
+			if (insn == i1)
+				return cse_one_instruction(i2, i1);
+			if (insn == i2)
+				return cse_one_instruction(i1, i2);
+		} END_FOR_EACH_PTR(insn);
+		warning(b1->pos, "Whaa? unable to find CSE instructions");
+	}
+	return NULL;
+}
+
+void cleanup_and_cse(struct entrypoint *ep)
+{
+	int i, success;
+
+repeat:
+	success = 0;
+	clean_up_insns(ep);
+	for (i = 0; i < INSN_HASH_SIZE; i++) {
+		struct instruction_list **list = insn_hash_table + i;
+		if (*list) {
+			if (instruction_list_size(*list) > 1) {
+				struct instruction *insn, *last;
+
+				sort_instruction_list(list);
+
+				last = NULL;
+				FOR_EACH_PTR(*list, insn) {
+					if (last) {
+						if (!insn_compare(last, insn)) {
+							struct instruction *def = try_to_cse(last, insn);
+							if (def) {
+								success++;
+								insn = def;
+							}
+						}
+					}
+					last = insn;
+				} END_FOR_EACH_PTR(insn);
+			}
+			free_ptr_list((struct ptr_list **)list);
+		}
+	}
+
+	if (success)
+		goto repeat;
+}
diff --git a/flow.c b/flow.c
index c1467e13..d8d8b72c 100644
--- a/flow.c
+++ b/flow.c
@@ -14,6 +14,7 @@
 #include "parse.h"
 #include "expression.h"
 #include "linearize.h"
+#include "flow.h"
 
 static unsigned long bb_generation;
 
@@ -134,7 +135,7 @@ static inline void concat_user_list(struct pseudo_ptr_list *src, struct pseudo_p
 	concat_ptr_list((struct ptr_list *)src, (struct ptr_list **)dst);
 }
 
-static void convert_load_insn(struct instruction *insn, pseudo_t src)
+void convert_load_insn(struct instruction *insn, pseudo_t src)
 {
 	pseudo_t target, *usep;
 
@@ -606,16 +607,6 @@ static void kill_unreachable_bbs(struct entrypoint *ep)
 	} END_FOR_EACH_PTR(bb);
 }
 
-static void try_to_replace(struct basic_block *bb, struct basic_block **target,
-	struct basic_block *old, struct basic_block *new)
-{
-	if (*target == old) {
-		*target = new;
-		/* FIXME!! Fix child information */
-		warning(bb->pos, "changed child from %p to %p", old, new);
-	}
-}
-
 static int rewrite_parent_branch(struct basic_block *bb, struct basic_block *old, struct basic_block *new)
 {
 	struct instruction *insn = last_instruction(bb->insns);
diff --git a/flow.h b/flow.h
index 06f54fb4..5d169c32 100644
--- a/flow.h
+++ b/flow.h
@@ -5,4 +5,7 @@ extern void simplify_symbol_usage(struct entrypoint *ep);
 extern void simplify_phi_nodes(struct entrypoint *ep);
 extern void pack_basic_blocks(struct entrypoint *ep);
 
+extern void convert_load_insn(struct instruction *insn, pseudo_t src);
+extern void cleanup_and_cse(struct entrypoint *ep);
+
 #endif
diff --git a/linearize.c b/linearize.c
index e0232dfd..14794285 100644
--- a/linearize.c
+++ b/linearize.c
@@ -152,7 +152,7 @@ static const char *show_pseudo(pseudo_t pseudo)
 	return buf;
 }
 
-static void show_instruction(struct instruction *insn)
+void show_instruction(struct instruction *insn)
 {
 	int op = insn->opcode;
 
@@ -1630,6 +1630,12 @@ struct entrypoint *linearize_symbol(struct symbol *sym)
 			simplify_phi_nodes(ep);
 
 			/*
+			 * Remove trivial instructions, and try to CSE
+			 * the rest.
+			 */
+			cleanup_and_cse(ep);
+
+			/*
 			 * Remove or merge basic blocks.
 			 */
 			pack_basic_blocks(ep);
author	Linus Torvalds <torvalds@ppc970.osdl.org>	2004-11-23 13:26:50 -0700
committer	Linus Torvalds <torvalds@ppc970.osdl.org>	2005-04-07 21:04:35 -0700
commit	fe8df476cce241da882b6895b219e082ad3960f2 (patch)
tree	c1d2d6677ed26e25ad8dedfbcbbfa19d9b8d3d19
parent	34038a899aa290c162229cab3289264961fd1772 (diff)
download	sparse-dev-fe8df476cce241da882b6895b219e082ad3960f2.tar.gz