From e19250992c2bf7b95dafed7dea3751428bdf7c32 Mon Sep 17 00:00:00 2001
From: Linus Torvalds <torvalds@ppc970.osdl.org>
Date: Sun, 28 Nov 2004 10:38:52 -0700
Subject: [PATCH] Allow CSE to run after bb packing.

...but we can't merge phi-sources after packing. Or rather, we
could, but we'll have to be more careful about not re-ordering
them, which we aren't. Sort it out later.
---
 cse.c       |  6 +++++-
 flow.c      | 18 ++++++++++++++++++
 lib.h       |  2 +-
 linearize.c | 11 +++++------
 4 files changed, 29 insertions(+), 8 deletions(-)

diff --git a/cse.c b/cse.c
index 4c91e566..a35177e8 100644
--- a/cse.c
+++ b/cse.c
@@ -22,7 +22,7 @@ static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
 
 #define hashval(x) ((unsigned long)(x))
 
-int repeat_phase;
+int repeat_phase, merge_phi_sources;
 
 static int phi_compare(pseudo_t phi1, pseudo_t phi2)
 {
@@ -209,6 +209,10 @@ static int insn_compare(const void *_i1, const void *_i2)
 			return i1->src1 < i2->src1 ? -1 : 1;
 		if (i1->bb != i2->bb)
 			return i1->bb < i2->bb ? -1 : 1;
+		if (!merge_phi_sources) {
+			if (i1 != i2)
+				return i1 < i2 ? -1 : 1;
+		}
 		break;
 
 	default:
diff --git a/flow.c b/flow.c
index 564391f1..ac6ea278 100644
--- a/flow.c
+++ b/flow.c
@@ -32,6 +32,8 @@ static void rewrite_branch(struct basic_block *bb,
 	if (*ptr != old)
 		return;
 
+	/* We might find new if-conversions or non-dominating CSEs */
+	repeat_phase |= REPEAT_CSE;
 	*ptr = new;
 	replace_bb_in_list(&bb->children, old, new, 1);
 	remove_bb_from_list(&old->parents, bb, 1);
@@ -814,6 +816,21 @@ out:
 				goto no_merge;
 		} END_FOR_EACH_PTR(child);
 
+		/*
+		 * Merge the two.
+		 */
+		repeat_phase |= REPEAT_CSE;
+
+		/*
+		 *  But don't allow phi-source merges after this.
+		 * FIXME, FIXME! I really need to think about this.
+		 * Is it true? I think it's ok to merge phi-sources,
+		 * as long as we keep their relative position in
+		 * the stream. It's the re-ordering we can't have.
+		 * I think. 
+		 */
+		merge_phi_sources = 0;
+
 		parent->children = bb->children;
 		FOR_EACH_PTR(bb->children, child) {
 			struct basic_block *p;
@@ -823,6 +840,7 @@ out:
 				*THIS_ADDRESS(p) = parent;
 			} END_FOR_EACH_PTR(p);
 		} END_FOR_EACH_PTR(child);
+		bb->children = NULL;
 
 		delete_last_instruction(&parent->insns);
 		FOR_EACH_PTR(bb->insns, insn) {
diff --git a/lib.h b/lib.h
index eb74ac10..2abafa0a 100644
--- a/lib.h
+++ b/lib.h
@@ -17,7 +17,7 @@
 #include "compat.h"
 
 extern int verbose, optimize, preprocessing;
-extern int repeat_phase;
+extern int repeat_phase, merge_phi_sources;
 
 #define container(ptr, type, member) \
 	(type *)((void *)(ptr) - offsetof(type, member))
diff --git a/linearize.c b/linearize.c
index 97207a3d..46f6ced4 100644
--- a/linearize.c
+++ b/linearize.c
@@ -1741,12 +1741,11 @@ static struct entrypoint *linearize_fn(struct symbol *sym, struct symbol *base_t
 	 * Remove trivial instructions, and try to CSE
 	 * the rest.
 	 */
-	cleanup_and_cse(ep);
-
-	/*
-	 * Remove or merge basic blocks.
-	 */
-	pack_basic_blocks(ep);
+	merge_phi_sources = 1;
+	do {
+		cleanup_and_cse(ep);
+		pack_basic_blocks(ep);
+	} while (repeat_phase & REPEAT_CSE);
 
 	/* Cleanup */
 	clear_symbol_pseudos(ep);
-- 
2.11.4.GIT