Add PredicateSimplifier pass. Collapses equal variables into one form

and simplifies expressions. This implements the optimization described
in PR807.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29947 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 223 insertions, 0 deletions

diff --git a/test/Transforms/PredicateSimplifier/predsimplify.ll b/test/Transforms/PredicateSimplifier/predsimplify.ll
new file mode 100644
index 0000000000..056d8c97dc
--- /dev/null
+++ b/test/Transforms/PredicateSimplifier/predsimplify.ll
@@ -0,0 +1,130 @@
+; RUN: llvm-as < %s | opt -predsimplify -instcombine -simplifycfg | llvm-dis | grep -v declare | not grep fail
+
+void %test1(int %x) {
+entry:
+  %A = seteq int %x, 0
+  br bool %A, label %then.1, label %else.1
+then.1:
+  %B = seteq int %x, 1
+  br bool %B, label %then.2, label %else.1
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  ret void
+}
+
+void %test2(int %x) {
+entry:
+  %A = seteq int %x, 0
+  %B = seteq int %x, 1
+  br bool %A, label %then.1, label %else.1
+then.1:
+  br bool %B, label %then.2, label %else.1
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  ret void
+}
+
+void %test3(int %x) {
+entry:
+  %A = seteq int %x, 0
+  %B = seteq int %x, 1
+  br bool %A, label %then.1, label %else.1
+then.1:
+  br bool %B, label %then.2, label %else.1
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  ret void
+}
+
+void %test4(int %x, int %y) {
+entry:
+  %A = seteq int %x, 0
+  %B = seteq int %y, 0
+  %C = and bool %A, %B
+  br bool %C, label %then.1, label %else.1
+then.1:
+  %D = seteq int %x, 0
+  br bool %D, label %then.2, label %else.2
+then.2:
+  %E = seteq int %y, 0
+  br bool %E, label %else.1, label %else.2
+else.1:
+  ret void
+else.2:
+  call void (...)* %fail( )
+  ret void
+}
+
+void %test5(int %x) {
+entry:
+  %A = seteq int %x, 0
+  br bool %A, label %then.1, label %else.1
+then.1:
+  ret void
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  %B = seteq int %x, 0
+  br bool %B, label %then.2, label %then.1
+}
+
+void %test6(int %x, int %y) {
+entry:
+  %A = seteq int %x, 0
+  %B = seteq int %y, 0
+  %C = or bool %A, %B
+  br bool %C, label %then.1, label %else.1
+then.1:
+  ret void
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  %D = seteq int %x, 0
+  br bool %D, label %then.2, label %else.2
+else.2:
+  %E = setne int %y, 0
+  br bool %E, label %then.1, label %then.2
+}
+
+void %test7(int %x) {
+entry:
+  %A = setne int %x, 0
+  %B = xor bool %A, true
+  br bool %B, label %then.1, label %else.1
+then.1:
+  %C = seteq int %x, 1
+  br bool %C, label %then.2, label %else.1
+then.2:
+  call void (...)* %fail( )
+  ret void
+else.1:
+  ret void
+}
+
+void %test8(int %x) {
+entry:
+  %A = add int %x, 1
+  %B = seteq int %x, 0
+  br bool %B, label %then.1, label %then.2
+then.1:
+  %C = seteq int %A, 1
+  br bool %C, label %then.2, label %else.2
+then.2:
+  ret void
+else.2:
+  call void (...)* %fail( )
+  ret void
+}
+
+
+declare void %fail(...)
+
+declare void %pass(...)
diff --git a/test/Transforms/PredicateSimplifier/predsimplify.reg1.ll b/test/Transforms/PredicateSimplifier/predsimplify.reg1.ll
new file mode 100644
index 0000000000..a7fd4cabed
--- /dev/null
+++ b/test/Transforms/PredicateSimplifier/predsimplify.reg1.ll
@@ -0,0 +1,23 @@
+; RUN: llvm-as < %s | opt -predsimplify -verify
+
+void %dgefa() {
+entry:
+        br label %cond_true96
+
+cond_true:              ; preds = %cond_true96
+        %tmp19 = seteq int %tmp10, %k.0         ; <bool> [#uses=1]
+        br bool %tmp19, label %cond_next, label %cond_true20
+
+cond_true20:            ; preds = %cond_true
+        br label %cond_next
+
+cond_next:              ; preds = %cond_true20, %cond_true
+        %tmp84 = setgt int %tmp3, 1999          ; <bool> [#uses=0]
+        ret void
+
+cond_true96:            ; preds = %cond_true96, %entry
+        %k.0 = phi int [ 0, %entry ], [ 0, %cond_true96 ]               ; <int> [#uses=3]
+        %tmp3 = add int %k.0, 1         ; <int> [#uses=1]
+        %tmp10 = add int 0, %k.0                ; <int> [#uses=1]
+        br bool false, label %cond_true96, label %cond_true
+}
diff --git a/test/Transforms/PredicateSimplifier/predsimplify.reg2.ll b/test/Transforms/PredicateSimplifier/predsimplify.reg2.ll
new file mode 100644
index 0000000000..a5e77aa9e4
--- /dev/null
+++ b/test/Transforms/PredicateSimplifier/predsimplify.reg2.ll
@@ -0,0 +1,49 @@
+; RUN: llvm-as < %s | opt -predsimplify -verify
+
+; ModuleID = 'bugpoint-reduced-simplified.bc'
+target endian = little
+target pointersize = 32
+target triple = "i686-pc-linux-gnu"
+deplibs = [ "c", "crtend" ]
+	%struct.anon = type { %struct.set_family*, %struct.set_family*, %struct.set_family*, sbyte*, int, uint*, %struct.pair_struct*, sbyte**, %struct.symbolic_t*, %struct.symbolic_t* }
+	%struct.pair_struct = type { int, int*, int* }
+	%struct.set_family = type { int, int, int, int, int, uint*, %struct.set_family* }
+	%struct.symbolic_label_t = type { sbyte*, %struct.symbolic_label_t* }
+	%struct.symbolic_list_t = type { int, int, %struct.symbolic_list_t* }
+	%struct.symbolic_t = type { %struct.symbolic_list_t*, int, %struct.symbolic_label_t*, int, %struct.symbolic_t* }
+
+implementation   ; Functions:
+
+void %find_pairing_cost(int %strategy) {
+entry:
+	br bool false, label %cond_true299, label %bb314
+
+bb94:		; preds = %cond_true299
+	switch int %strategy, label %bb246 [
+		 int 0, label %bb196
+		 int 1, label %bb159
+	]
+
+cond_next113:		; preds = %cond_true299
+	switch int %strategy, label %bb246 [
+		 int 0, label %bb196
+		 int 1, label %bb159
+	]
+
+bb159:		; preds = %cond_next113, %bb94
+	ret void
+
+bb196:		; preds = %cond_next113, %bb94
+	%Rsave.0.3 = phi %struct.set_family* [ null, %bb94 ], [ null, %cond_next113 ]		; <%struct.set_family*> [#uses=0]
+	ret void
+
+bb246:		; preds = %cond_next113, %bb94
+	br label %bb314
+
+cond_true299:		; preds = %entry
+	%tmp55 = setgt int %strategy, 0		; <bool> [#uses=1]
+	br bool %tmp55, label %bb94, label %cond_next113
+
+bb314:		; preds = %bb246, %entry
+	ret void
+}
diff --git a/test/Transforms/PredicateSimplifier/predsimplify.reg3.ll b/test/Transforms/PredicateSimplifier/predsimplify.reg3.ll
new file mode 100644
index 0000000000..facf336fa1
--- /dev/null
+++ b/test/Transforms/PredicateSimplifier/predsimplify.reg3.ll
@@ -0,0 +1,21 @@
+; RUN: llvm-as < %s | opt -predsimplify -simplifycfg | llvm-dis | grep pass
+
+void %regtest(int %x) {
+entry:
+  %A = seteq int %x, 0
+  br bool %A, label %middle, label %after
+middle:
+  br label %after
+after:
+  %B = seteq int %x, 0
+  br bool %B, label %then, label %else
+then:
+  br label %end
+else:
+  call void (...)* %pass( )
+  br label %end
+end:
+  ret void
+}
+
+declare void %pass(...)