[LVI] Teach LVI to reason about ORs of icmps similar to how it reasons about ANDs of icmps

[craig.topper]

Summary

LVI can reason about an AND of icmps on the true dest of a branch. I believe we can do similar for the false dest of ORs. This allows us to get the same answer for the demorganed versions of some of the AND test cases as you can see.

[reames]

LGTM. Nice catch.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

 
 static LVILatticeVal
 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
                           DenseMap<Value*, LVILatticeVal> &Visited) {
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
     return getValueFromICmpCondition(Val, ICI, isTrueDest);
 
   // Handle conditions in the form of (cond1 && cond2), we know that on the
-  // true dest path both of the conditions hold.
-  if (!isTrueDest)
-    return LVILatticeVal::getOverdefined();
-
+  // true dest path both of the conditions hold. Similarly for conditions of
+  // the form (cond1 || cond2), we know that on the false dest path neither
+  // condition holds.
   BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
-  if (!BO || BO->getOpcode() != BinaryOperator::And)
+  if (!BO || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
+             (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
     return LVILatticeVal::getOverdefined();
 
   auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited);
   auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited);
   return intersect(RHS, LHS);
 }
 
 static LVILatticeVal

llvm/trunk/test/Transforms/CorrelatedValuePropagation/add.ll

 then:
 ; CHECK: %i.plus.6 = add nuw nsw i32 %i, 6
   %i.plus.6 = add i32 %i, 6
   ret i32 %i.plus.6
 
 else:
   ret i32 0
 }
+
+; Check that we can gather information for conditions is the form of
+;   or ( i s>= 100, Unknown )
+; CHECK-LABEL: @test12(
+define void @test12(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp sge i32 %a, 100
+  %cmp = or i1 %cmp.1, %flag
+  br i1 %cmp, label %exit, label %bb
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that we can gather information for conditions is the form of
+;   or ( i s>= 100, i s<= 0 )
+; CHECK-LABEL: @test13(
+define void @test13(i32 %a) {
+entry:
+  %cmp.1 = icmp sge i32 %a, 100
+  %cmp.2 = icmp sle i32 %a, 0
+  %cmp = or i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %exit, label %bb
+
+bb:
+; CHECK: %add = add nuw nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that for conditions is the form of cond1 || cond2 we don't mistakenly
+; assume that cond1 || cond2 holds down to true path.
+; CHECK-LABEL: @test13_neg(
+define void @test13_neg(i32 %a) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp.2 = icmp sgt i32 %a, 0
+  %cmp = or i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that we can gather information for conditions is the form of
+;   or ( i s>=100, or (i s<= 0, Unknown )
+; CHECK-LABEL: @test14(
+define void @test14(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp sge i32 %a, 100
+  %cmp.2 = icmp sle i32 %a, 0
+  %cmp.3 = or i1 %cmp.2, %flag
+  %cmp = or i1 %cmp.1, %cmp.3
+  br i1 %cmp, label %exit, label %bb
+
+bb:
+; CHECK: %add = add nuw nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+
+; Check that we can gather information for conditions is the form of
+;   or ( i s>= Unknown, ... )
+; CHECK-LABEL: @test15(
+define void @test15(i32 %a, i32 %b, i1 %flag) {
+entry:
+  %cmp.1 = icmp sge i32 %a, %b
+  %cmp = or i1 %cmp.1, %flag
+  br i1 %cmp, label %exit, label %bb
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}
+