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

[mcrosier]

Summary

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

Chad

[spatel]

Missed a digit on the bug number in the summary (PR33611):
https://bugs.llvm.org//show_bug.cgi?id=33611

[craig.topper]

LGTM

[mcrosier]

r307304

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// the truth table for implication is the same as <=u on i1 values (but not
   /// <=s!).  The truth table for both is:
   ///    | T | F (B)
   ///  T | T | F
   ///  F | T | T
   /// (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);
 } // end namespace llvm
 
 #endif

lib/Analysis/ValueTracking.cpp

isImpliedCondMatchingImmOperands(CmpInst::Predicate APred, const Value *ALHS,
   if (Intersection.isEmptySet())
     return false;
   if (Difference.isEmptySet())
     return true;
   return None;
 }
 
 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) {
   // A mismatch occurs when we compare a scalar cmp to a vector cmp, for example.
   if (LHS->getType() != RHS->getType())
     return None;
 
   Type *OpTy = LHS->getType();
   assert(OpTy->getScalarType()->isIntegerTy(1));
 
   // LHS ==> RHS by definition
-  if (!InvertAPred && LHS == RHS)
+  if (!LHSIsFalse && LHS == RHS)
     return true;
 
   if (OpTy->isVectorTy())
     // TODO: extending the code below to handle vectors
     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?
   bool IsSwappedOps;
   if (isMatchingOps(ALHS, ARHS, BLHS, BRHS, IsSwappedOps)) {
     if (Optional<bool> Implication = isImpliedCondMatchingOperands(
             APred, ALHS, ARHS, BPred, BLHS, BRHS, IsSwappedOps))
       return Implication;

test/Transforms/InstCombine/select-implied.ll

taken:
   br label %end
 
 end:
   ret void
 }
 
 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
+}

test/Transforms/SimplifyCFG/implied-and-or.ll

+; 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
+}