From 452c58f4c45249b5046f74a165430eedaab5f8f6 Mon Sep 17 00:00:00 2001
From: Duncan Sands <baldrick@free.fr>
Date: Wed, 5 Oct 2011 14:17:01 +0000
Subject: [PATCH] Generalize GVN's conditional propagation logic slightly: it's
 OK for the false/true destination to have multiple predecessors as long as
 the extra ones are dominated by the branch destination.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141176 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/GVN.cpp   | 33 +++++++++++++++++++++++++++++----
 test/Transforms/GVN/condprop.ll | 22 +++++++++++++++++++++-
 2 files changed, 50 insertions(+), 5 deletions(-)

diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index f0f16d84371..0ad6a8faa4c 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -1921,14 +1921,39 @@ bool GVN::processInstruction(Instruction *I) {
   
     BasicBlock *TrueSucc = BI->getSuccessor(0);
     BasicBlock *FalseSucc = BI->getSuccessor(1);
-  
-    if (TrueSucc->getSinglePredecessor())
+    BasicBlock *Parent = BI->getParent();
+
+    // If the true and false branches are to the same basic block then the
+    // branch gives no information about the condition.  Eliminating this
+    // here simplifies the rest of the logic.
+    if (TrueSucc == FalseSucc)
+      return false;
+
+    // If the true block can be reached without executing the true edge then we
+    // can't say anything about the value of the condition there.
+    for (pred_iterator PI = pred_begin(TrueSucc), PE = pred_end(TrueSucc);
+         PI != PE; ++PI)
+      if (*PI != Parent && !DT->dominates(TrueSucc, *PI)) {
+        TrueSucc = 0;
+        break;
+      }
+
+    // If the false block can be reached without executing the false edge then
+    // we can't say anything about the value of the condition there.
+    for (pred_iterator PI = pred_begin(FalseSucc), PE = pred_end(FalseSucc);
+         PI != PE; ++PI)
+      if (*PI != Parent && !DT->dominates(FalseSucc, *PI)) {
+        FalseSucc = 0;
+        break;
+      }
+
+    if (TrueSucc)
       addToLeaderTable(CondVN,
                    ConstantInt::getTrue(TrueSucc->getContext()),
                    TrueSucc);
-    if (FalseSucc->getSinglePredecessor())
+    if (FalseSucc)
       addToLeaderTable(CondVN,
-                   ConstantInt::getFalse(TrueSucc->getContext()),
+                   ConstantInt::getFalse(FalseSucc->getContext()),
                    FalseSucc);
     
     return false;
diff --git a/test/Transforms/GVN/condprop.ll b/test/Transforms/GVN/condprop.ll
index be6c3498fe4..b0728565f38 100644
--- a/test/Transforms/GVN/condprop.ll
+++ b/test/Transforms/GVN/condprop.ll
@@ -52,4 +52,24 @@ bb8:		; preds = %bb7, %bb6, %bb4, %bb2, %bb
 
 return:		; preds = %bb8
 	ret i32 %.0
-}
\ No newline at end of file
+}
+
+declare void @ext(i1)
+
+; CHECK: @bar
+define void @bar(i1 %x, i1 %y) {
+  %z = or i1 %x, %y
+  br i1 %z, label %true, label %false
+true:
+; CHECK: true:
+  %z2 = or i1 %x, %y
+  call void @ext(i1 %z2)
+; CHECK: call void @ext(i1 true)
+  br label %true
+false:
+; CHECK: false:
+  %z3 = or i1 %x, %y
+  call void @ext(i1 %z3)
+; CHECK: call void @ext(i1 false)
+  br label %false
+}
-- 
2.34.1