From 1b8b7d61ee330f0e60e5260d6929e2e8953312fb Mon Sep 17 00:00:00 2001
From: Bjorn Steinbrink <bsteinbr@gmail.com>
Date: Tue, 12 May 2015 22:31:47 +0000
Subject: [PATCH] CVP: Improve handling of Selects used as incoming PHI values

Summary:
If the branch that leads to the PHI node and the Select instruction
depend on correlated conditions, we might be able to directly use the
corresponding value from the Select instruction as the incoming value
for the PHI node, allowing later removal of the select instruction.

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D9051

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@237201 91177308-0d34-0410-b5e6-96231b3b80d8
---
 .../Scalar/CorrelatedValuePropagation.cpp     | 41 ++++++++++----
 .../CorrelatedValuePropagation/select.ll      | 53 +++++++++++++++++++
 2 files changed, 83 insertions(+), 11 deletions(-)
 create mode 100644 test/Transforms/CorrelatedValuePropagation/select.ll

diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 912d527402a..d1302c6e22f 100644
--- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -103,24 +103,43 @@ bool CorrelatedValuePropagation::processPHI(PHINode *P) {
 
     Value *V = LVI->getConstantOnEdge(Incoming, P->getIncomingBlock(i), BB, P);
 
-    // Look if the incoming value is a select with a constant but LVI tells us
-    // that the incoming value can never be that constant. In that case replace
-    // the incoming value with the other value of the select. This often allows
-    // us to remove the select later.
+    // Look if the incoming value is a select with a scalar condition for which
+    // LVI can tells us the value. In that case replace the incoming value with
+    // the appropriate value of the select. This often allows us to remove the
+    // select later.
     if (!V) {
       SelectInst *SI = dyn_cast<SelectInst>(Incoming);
       if (!SI) continue;
 
-      Constant *C = dyn_cast<Constant>(SI->getFalseValue());
-      if (!C) continue;
+      Value *Condition = SI->getCondition();
+      if (!Condition->getType()->isVectorTy()) {
+        if (Constant *C = LVI->getConstantOnEdge(Condition, P->getIncomingBlock(i), BB, P)) {
+          if (C == ConstantInt::getTrue(Condition->getType())) {
+            V = SI->getTrueValue();
+          } else {
+            V = SI->getFalseValue();
+          }
+          // Once LVI learns to handle vector types, we could also add support
+          // for vector type constants that are not all zeroes or all ones.
+        }
+      }
 
-      if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
-                                  P->getIncomingBlock(i), BB, P) !=
-          LazyValueInfo::False)
-        continue;
+      // Look if the select has a constant but LVI tells us that the incoming
+      // value can never be that constant. In that case replace the incoming
+      // value with the other value of the select. This often allows us to
+      // remove the select later.
+      if (!V) {
+        Constant *C = dyn_cast<Constant>(SI->getFalseValue());
+        if (!C) continue;
+
+        if (LVI->getPredicateOnEdge(ICmpInst::ICMP_EQ, SI, C,
+              P->getIncomingBlock(i), BB, P) !=
+            LazyValueInfo::False)
+          continue;
+        V = SI->getTrueValue();
+      }
 
       DEBUG(dbgs() << "CVP: Threading PHI over " << *SI << '\n');
-      V = SI->getTrueValue();
     }
 
     P->setIncomingValue(i, V);
diff --git a/test/Transforms/CorrelatedValuePropagation/select.ll b/test/Transforms/CorrelatedValuePropagation/select.ll
new file mode 100644
index 00000000000..5501438f690
--- /dev/null
+++ b/test/Transforms/CorrelatedValuePropagation/select.ll
@@ -0,0 +1,53 @@
+; RUN: opt < %s -correlated-propagation -S | FileCheck %s
+
+; CHECK-LABEL: @simple(
+define i8 @simple(i1) {
+entry:
+  %s = select i1 %0, i8 0, i8 1
+  br i1 %0, label %then, label %else
+
+then:
+; CHECK: ret i8 0
+  %a = phi i8 [ %s, %entry ]
+  ret i8 %a
+
+else:
+; CHECK: ret i8 1
+  %b = phi i8 [ %s, %entry ]
+  ret i8 %b
+}
+
+; CHECK-LABEL: @loop(
+define void @loop(i32) {
+entry:
+  br label %loop
+
+loop:
+  %idx = phi i32 [ %0, %entry ], [ %sel, %loop ]
+; CHECK: %idx = phi i32 [ %0, %entry ], [ %2, %loop ]
+  %1 = icmp eq i32 %idx, 0
+  %2 = add i32 %idx, -1
+  %sel = select i1 %1, i32 0, i32 %2
+  br i1 %1, label %out, label %loop
+
+out:
+  ret void
+}
+
+; CHECK-LABEL: @not_correlated(
+define i8 @not_correlated(i1, i1) {
+entry:
+  %s = select i1 %0, i8 0, i8 1
+  br i1 %1, label %then, label %else
+
+then:
+; CHECK: ret i8 %s
+  %a = phi i8 [ %s, %entry ]
+  ret i8 %a
+
+else:
+; CHECK: ret i8 %s
+  %b = phi i8 [ %s, %entry ]
+  ret i8 %b
+}
+
-- 
2.34.1