[ValueTracking] Support icmps fed by 'and' and 'or'.

This patch adds support for handling some forms of ands and ors in
ValueTracking's isImpliedCondition API.

PR33611
https://reviews.llvm.org/D34901

llvm-svn: 307304

4 files changed, 257 insertions, 9 deletions

diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h
index e953ec8ab6a..f4c57d4289f 100644
--- a/llvm/include/llvm/Analysis/ValueTracking.h
+++ b/llvm/include/llvm/Analysis/ValueTracking.h
@@ -523,8 +523,7 @@ template <typename T> class ArrayRef;
   /// (A)
   Optional<bool> isImpliedCondition(const Value *LHS, const Value *RHS,
                                     const DataLayout &DL,
-                                    bool InvertAPred = false,
-                                    unsigned Depth = 0,
+                                    bool LHSIsFalse = false, unsigned Depth = 0,
                                     AssumptionCache *AC = nullptr,
                                     const Instruction *CxtI = nullptr,
                                     const DominatorTree *DT = nullptr);
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
index c9a6485afad..514b8f29f84 100644
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -4393,7 +4393,7 @@ isImpliedCondMatchingImmOperands(CmpInst::Predicate APred, const Value *ALHS,
 }
 
 Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
-                                        const DataLayout &DL, bool InvertAPred,
+                                        const DataLayout &DL, bool LHSIsFalse,
                                         unsigned Depth, AssumptionCache *AC,
                                         const Instruction *CxtI,
                                         const DominatorTree *DT) {
@@ -4405,7 +4405,7 @@ Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
-  if (!InvertAPred && LHS == RHS)
+  if (!LHSIsFalse && LHS == RHS)
     return true;
 
   if (OpTy->isVectorTy())
@@ -4413,15 +4413,40 @@ Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS,
     return None;
   assert(OpTy->isIntegerTy(1) && "implied by above");
 
-  ICmpInst::Predicate APred, BPred;
-  Value *ALHS, *ARHS;
   Value *BLHS, *BRHS;
+  ICmpInst::Predicate BPred;
+  // We expect the RHS to be an icmp.
+  if (!match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
+    return None;
 
-  if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS))) ||
-      !match(RHS, m_ICmp(BPred, m_Value(BLHS), m_Value(BRHS))))
+  Value *ALHS, *ARHS;
+  ICmpInst::Predicate APred;
+  // The LHS can be an 'or', 'and', or 'icmp'.
+  if (!match(LHS, m_ICmp(APred, m_Value(ALHS), m_Value(ARHS)))) {
+    // The remaining tests are all recursive, so bail out if we hit the limit.
+    if (Depth == MaxDepth)
+      return None;
+    // If the result of an 'or' is false, then we know both legs of the 'or' are
+    // false.  Similarly, if the result of an 'and' is true, then we know both
+    // legs of the 'and' are true.
+    if ((LHSIsFalse && match(LHS, m_Or(m_Value(ALHS), m_Value(ARHS)))) ||
+        (!LHSIsFalse && match(LHS, m_And(m_Value(ALHS), m_Value(ARHS))))) {
+      if (Optional<bool> Implication = isImpliedCondition(
+              ALHS, RHS, DL, LHSIsFalse, Depth + 1, AC, CxtI, DT))
+        return Implication;
+      if (Optional<bool> Implication = isImpliedCondition(
+              ARHS, RHS, DL, LHSIsFalse, Depth + 1, AC, CxtI, DT))
+        return Implication;
+      return None;
+    }
     return None;
+  }
+  // All of the below logic assumes both LHS and RHS are icmps.
+  assert(isa<ICmpInst>(LHS) && isa<ICmpInst>(RHS) && "Expected icmps.");
 
-  if (InvertAPred)
+  // The rest of the logic assumes the LHS condition is true.  If that's not the
+  // case, invert the predicate to make it so.
+  if (LHSIsFalse)
     APred = CmpInst::getInversePredicate(APred);
 
   // Can we infer anything when the two compares have matching operands?
diff --git a/llvm/test/Transforms/InstCombine/select-implied.ll b/llvm/test/Transforms/InstCombine/select-implied.ll
index 2100e3eae00..6b2ec7ffce7 100644
--- a/llvm/test/Transforms/InstCombine/select-implied.ll
+++ b/llvm/test/Transforms/InstCombine/select-implied.ll
@@ -121,3 +121,44 @@ end:
 
 declare void @foo(i32)
 declare i32 @bar(i32)
+
+; CHECK-LABEL: @test_and
+; CHECK: tpath:
+; CHECK-NOT: select
+; CHECK: ret i32 313
+define i32 @test_and(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp ne i32 %a, 0
+  %cmp2 = icmp ne i32 %b, 0
+  %and = and i1 %cmp1, %cmp2
+  br i1 %and, label %tpath, label %end
+
+tpath:
+  %cmp3 = icmp eq i32 %a, 0 ;; <-- implied false
+  %c = select i1 %cmp3, i32 0, i32 313
+  ret i32 %c
+
+end:
+  ret i32 0
+}
+
+; cmp1 and cmp2 are false on the 'fpath' path and thus cmp3 is true.
+; CHECK-LABEL: @test_or1
+; CHECK: fpath:
+; CHECK-NOT: select
+; CHECK: ret i32 37
+define i32 @test_or1(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %or = or i1 %cmp1, %cmp2
+  br i1 %or, label %end, label %fpath
+
+fpath:
+  %cmp3 = icmp ne i32 %a, 0  ;; <-- implied true
+  %c = select i1 %cmp3, i32 37, i32 0
+  ret i32 %c
+
+end:
+  ret i32 0
+}
diff --git a/llvm/test/Transforms/SimplifyCFG/implied-and-or.ll b/llvm/test/Transforms/SimplifyCFG/implied-and-or.ll
new file mode 100644
index 00000000000..e615f302fee
--- /dev/null
+++ b/llvm/test/Transforms/SimplifyCFG/implied-and-or.ll
@@ -0,0 +1,183 @@
+; RUN: opt %s -S -simplifycfg | FileCheck %s
+
+declare void @foo()
+declare void @bar()
+
+
+; CHECK-LABEL: @test_and1
+; CHECK: taken:
+; CHECK-NOT: cmp3
+; CHECK: call void @bar()
+; CHECK-NEXT: call void @foo()
+; CHECK: ret
+define void @test_and1(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %and = and i1 %cmp1, %cmp2
+  br i1 %and, label %taken, label %end
+
+taken:
+  call void @bar()
+  %cmp3 = icmp eq i32 %a, 0  ;; <-- implied true
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}
+
+; We can't infer anything if the result of the 'and' is false
+; CHECK-LABEL: @test_and2
+; CHECK: taken:
+; CHECK:   call void @bar()
+; CHECK:   %cmp3
+; CHECK:   br i1 %cmp3
+; CHECK: if.then:
+; CHECK:   call void @foo()
+; CHECK: ret
+define void @test_and2(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %and = and i1 %cmp1, %cmp2
+  br i1 %and, label %end, label %taken
+
+taken:
+  call void @bar()
+  %cmp3 = icmp eq i32 %a, 0
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}
+
+; CHECK-LABEL: @test_or1
+; CHECK: taken:
+; CHECK-NOT: cmp3
+; CHECK: call void @bar()
+; CHECK-NEXT: call void @foo()
+; CHECK: ret
+define void @test_or1(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %or = or i1 %cmp1, %cmp2
+  br i1 %or, label %end, label %taken
+
+taken:
+  call void @bar()
+  %cmp3 = icmp ne i32 %a, 0   ;; <-- implied true
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}
+
+; We can't infer anything if the result of the 'or' is true
+; CHECK-LABEL: @test_or2
+; CHECK:   call void @bar()
+; CHECK:   %cmp3
+; CHECK:   br i1 %cmp3
+; CHECK: if.then:
+; CHECK:   call void @foo()
+; CHECK: ret
+define void @test_or2(i32 %a, i32 %b) {
+entry:
+  %cmp1 = icmp eq i32 %a, 0
+  %cmp2 = icmp eq i32 %b, 0
+  %or = or i1 %cmp1, %cmp2
+  br i1 %or, label %taken, label %end
+
+taken:
+  call void @bar()
+  %cmp3 = icmp eq i32 %a, 0
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}
+
+; We can recurse a tree of 'and' or 'or's.
+; CHECK-LABEL: @test_and_recurse1
+; CHECK: taken:
+; CHECK-NEXT:  call void @bar()
+; CHECK-NEXT:  call void @foo()
+; CHECK-NEXT:  br label %end
+; CHECK: ret
+define void @test_and_recurse1(i32 %a, i32 %b, i32 %c) {
+entry:
+  %cmpa = icmp eq i32 %a, 0
+  %cmpb = icmp eq i32 %b, 0
+  %cmpc = icmp eq i32 %c, 0
+  %and1 = and i1 %cmpa, %cmpb
+  %and2 = and i1 %and1, %cmpc
+  br i1 %and2, label %taken, label %end
+
+taken:
+  call void @bar()
+  %cmp3 = icmp eq i32 %a, 0
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}
+
+; Check to make sure we don't recurse too deep.
+; CHECK-LABEL: @test_and_recurse2
+; CHECK: taken:
+; CHECK-NEXT:  call void @bar()
+; CHECK-NEXT:  %cmp3 = icmp eq i32 %a, 0
+; CHECK-NEXT:  br i1 %cmp3, label %if.then, label %end
+; CHECK: ret
+define void @test_and_recurse2(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32 %f,
+                               i32 %g, i32 %h) {
+entry:
+  %cmpa = icmp eq i32 %a, 0
+  %cmpb = icmp eq i32 %b, 0
+  %cmpc = icmp eq i32 %c, 0
+  %cmpd = icmp eq i32 %d, 0
+  %cmpe = icmp eq i32 %e, 0
+  %cmpf = icmp eq i32 %f, 0
+  %cmpg = icmp eq i32 %g, 0
+  %cmph = icmp eq i32 %h, 0
+  %and1 = and i1 %cmpa, %cmpb
+  %and2 = and i1 %and1, %cmpc
+  %and3 = and i1 %and2, %cmpd
+  %and4 = and i1 %and3, %cmpe
+  %and5 = and i1 %and4, %cmpf
+  %and6 = and i1 %and5, %cmpg
+  %and7 = and i1 %and6, %cmph
+  br i1 %and7, label %taken, label %end
+
+taken:
+  call void @bar()
+  %cmp3 = icmp eq i32 %a, 0 ; <-- can be implied true
+  br i1 %cmp3, label %if.then, label %end
+
+if.then:
+  call void @foo()
+  br label %end
+
+end:
+  ret void
+}