[LVI] Handle conditions in the form of (cond1 && cond2)

[apilipenko]

Summary

Teach LVI how to gather information from conditions in the form of (cond1 && cond2). Our out-of-tree front-end emits range checks in this form.

[sanjoy]

lgtm with comments addressed

lib/Analysis/LazyValueInfo.cpp

1244 ↗

(On Diff #66928)

I'd suggest using a visited set here. That way you don't infinitely recurse in unreachable code (I'm not sure if that is filtered out already) and won't have exponential time complexity for cases like

%c0 = icmp ..
%c1 = icmp ..
%a0 = and %c0, %c1
%a1 = and %a0, %a0
%a2 = and %a1, %a1
%a3 = and %a2, %a2
%a4 = and %a3, %a3
%a5 = and %a4, %a4
...

test/Transforms/CorrelatedValuePropagation/add.ll

155 ↗

(On Diff #66928)

I'd also throw in a

if (a s< Unknown && Unknown2)
  b = a + 1;

to

if (a s< Unknown && Unknown2)
  b = a nsw+ 1;

type transform.

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

default:
     llvm_unreachable("inconsistent with above");
     break;
   }
 
   BBLV = Result;
   return true;
 }
 
-LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
-  assert(Cond && "precondition");
-
-  // For now we only support ICmpInst conditions
-  ICmpInst *ICI = dyn_cast<ICmpInst>(Cond);
-  if (!ICI)
-    return LVILatticeVal::getOverdefined();
-
+static LVILatticeVal getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
+                                               bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
   CmpInst::Predicate Predicate = ICI->getPredicate();
 
   if (isa<Constant>(RHS)) {
     if (ICI->isEquality() && LHS == Val) {
       // We know that V has the RHS constant if this is a true SETEQ or
       // false SETNE.
if (Offset) // Apply the offset from above.
       TrueValues = TrueValues.subtract(Offset->getValue());
 
     return LVILatticeVal::getRange(std::move(TrueValues));
   }
 
   return LVILatticeVal::getOverdefined();
 }
 
+static LVILatticeVal
+getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
+                      DenseMap<Value*, LVILatticeVal> &Visited);
+
+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();
+
+  BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond);
+  if (!BO || BO->getOpcode() != BinaryOperator::And)
+    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
+getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
+                      DenseMap<Value*, LVILatticeVal> &Visited) {
+  auto I = Visited.find(Cond);
+  if (I != Visited.end())
+    return I->second;
+  return Visited[Cond] = getValueFromConditionImpl(Val, Cond, isTrueDest,
+                                                   Visited);
+}
+
+LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
+  assert(Cond && "precondition");
+  DenseMap<Value*, LVILatticeVal> Visited;
+  return getValueFromCondition(Val, Cond, isTrueDest, Visited);
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                               BasicBlock *BBTo, LVILatticeVal &Result) {
   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
   // know that v != 0.
   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {

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

 ; LVILatticeValue instead of constantrange. Check that we don't fail with an
 ; assertion in this case.
 @b = global i32 0, align 4
 define void @test6(i32 %a) {
 bb:
   %add = add i32 %a, ptrtoint (i32* @b to i32)
   ret void
 }
+
+; Check that we can gather information for conditions is the form of
+;   and ( i s< 100, Unknown )
+; CHECK-LABEL: @test7(
+define void @test7(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp = and i1 %cmp.1, %flag
+  br i1 %cmp, label %bb, label %exit
+
+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
+;   and ( i s< 100, i s> 0 )
+; CHECK-LABEL: @test8(
+define void @test8(i32 %a) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp.2 = icmp sgt i32 %a, 0
+  %cmp = and i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %bb, label %exit
+
+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 false path.
+; CHECK-LABEL: @test8_neg(
+define void @test8_neg(i32 %a) {
+entry:
+  %cmp.1 = icmp sge i32 %a, 100
+  %cmp.2 = icmp sle i32 %a, 0
+  %cmp = and i1 %cmp.1, %cmp.2
+  br i1 %cmp, label %exit, label %bb
+
+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
+;   and ( i s< 100, and (i s> 0, Unknown )
+; CHECK-LABEL: @test9(
+define void @test9(i32 %a, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, 100
+  %cmp.2 = icmp sgt i32 %a, 0
+  %cmp.3 = and i1 %cmp.2, %flag
+  %cmp = and i1 %cmp.1, %cmp.3
+  br i1 %cmp, label %bb, label %exit
+
+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
+;   and ( i s< Unknown, ... )
+; CHECK-LABEL: @test10(
+define void @test10(i32 %a, i32 %b, i1 %flag) {
+entry:
+  %cmp.1 = icmp slt i32 %a, %b
+  %cmp = and i1 %cmp.1, %flag
+  br i1 %cmp, label %bb, label %exit
+
+bb:
+; CHECK: %add = add nsw i32 %a, 1
+  %add = add i32 %a, 1
+  br label %exit
+
+exit:
+  ret void
+}