[LVI][CVP] Constrain values in with.overflow branches

[nikic]

Summary

If a branch is conditional on extractvalue(op.with.overflow(%x, C), 1) then we can constrain the value of %x inside the branch based on makeGuaranteedNoWrapRegion(). We do this by extending the edge-value handling in LVI. This allows CVP to then fold comparisons against %x, as illustrated in the tests.

[lebedev.ri]

Looks good, but someone familiar with LVI/CVP should review.

[nikic]

Rebase over WithOverflowInst.

[spatel]

I haven't looked at LVI much, but judging from the git log, nobody else has done that recently either.

The logic looks right, and the tests are great. LGTM.

llvm/lib/Analysis/LazyValueInfo.cpp

1140 ↗

(On Diff #195461)

I see that the lower-case variable "isTrueDest" is carried over from existing code, but I think it should be changed to conform with the current guidelines and the formatting of other variables (unless the lowerCamelCase proposal is going forward...).

llvm/trunk/lib/Analysis/LazyValueInfo.cpp

if (Offset) // Apply the offset from above.
       TrueValues = TrueValues.subtract(Offset->getValue());
 
     return ValueLatticeElement::getRange(std::move(TrueValues));
   }
 
   return ValueLatticeElement::getOverdefined();
 }
 
+// Handle conditions of the form
+// extractvalue(op.with.overflow(%x, C), 1).
+static ValueLatticeElement getValueFromOverflowCondition(
+    Value *Val, WithOverflowInst *WO, bool IsTrueDest) {
+  // TODO: This only works with a constant RHS for now. We could also compute
+  // the range of the RHS, but this doesn't fit into the current structure of
+  // the edge value calculation.
+  const APInt *C;
+  if (WO->getLHS() != Val || !match(WO->getRHS(), m_APInt(C)))
+    return ValueLatticeElement::getOverdefined();
+
+  // Calculate the possible values of %x for which no overflow occurs.
+  ConstantRange NWR = ConstantRange::makeGuaranteedNoWrapRegion(
+      WO->getBinaryOp(), ConstantRange(*C), WO->getNoWrapKind());
+
+  // If overflow is false, %x is constrained to NWR. If overflow is true, %x is
+  // constrained to it's inverse (all values that might cause overflow).
+  if (IsTrueDest)
+    NWR = NWR.inverse();
+  return ValueLatticeElement::getRange(NWR);
+}
+
 static ValueLatticeElement
 getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest,
                       DenseMap<Value*, ValueLatticeElement> &Visited);
 
 static ValueLatticeElement
 getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest,
                           DenseMap<Value*, ValueLatticeElement> &Visited) {
   if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond))
     return getValueFromICmpCondition(Val, ICI, isTrueDest);
 
+  if (auto *EVI = dyn_cast<ExtractValueInst>(Cond))
+    if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand()))
+      if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 1)
+        return getValueFromOverflowCondition(Val, WO, isTrueDest);
+
   // Handle conditions in the form of (cond1 && cond2), we know that on the
   // 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 || (isTrueDest && BO->getOpcode() != BinaryOperator::And) ||
              (!isTrueDest && BO->getOpcode() != BinaryOperator::Or))
     return ValueLatticeElement::getOverdefined();

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

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], -102
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], -101
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.uadd.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], -100
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], -101
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.uadd.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 26
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 27
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.sadd.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.sadd.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 28
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 27
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.sadd.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.usub.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i8 [[X]], 101
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ult i8 [[X]], 100
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.usub.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.usub.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ult i8 [[X]], 99
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ult i8 [[X]], 100
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.usub.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -27
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -28
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.ssub.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[X:%.*]], i8 100)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -29
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -28
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.ssub.with.overflow(i8 %x, i8 100)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], 24
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], 25
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.umul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.umul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp ugt i8 [[X]], 26
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ugt i8 [[X]], 25
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 true
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.umul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp slt i8 [[X]], -11
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i8 [[X]], -12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.smul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[TRAP:%.*]], label [[NO_OVERFLOW:%.*]]
 ; CHECK:       no_overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp sgt i8 [[X]], 11
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp sgt i8 [[X]], 12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.smul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[X]], -13
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[X]], -12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.smul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1

 ; CHECK-NEXT:    [[VAL_OV:%.*]] = call { i8, i1 } @llvm.smul.with.overflow.i8(i8 [[X:%.*]], i8 10)
 ; CHECK-NEXT:    [[VAL:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 0
 ; CHECK-NEXT:    store i8 [[VAL]], i8* [[PX:%.*]]
 ; CHECK-NEXT:    [[OV:%.*]] = extractvalue { i8, i1 } [[VAL_OV]], 1
 ; CHECK-NEXT:    br i1 [[OV]], label [[OVERFLOW:%.*]], label [[TRAP:%.*]]
 ; CHECK:       overflow:
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i8 [[X]], 13
 ; CHECK-NEXT:    store i1 [[C1]], i1* [[PC:%.*]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp eq i8 [[X]], 12
-; CHECK-NEXT:    ret i1 [[C2]]
+; CHECK-NEXT:    ret i1 false
 ; CHECK:       trap:
 ; CHECK-NEXT:    call void @llvm.trap()
 ; CHECK-NEXT:    unreachable
 ;
   %val_ov = call {i8, i1} @llvm.smul.with.overflow(i8 %x, i8 10)
   %val = extractvalue {i8, i1} %val_ov, 0
   store i8 %val, i8* %px
   %ov = extractvalue {i8, i1} %val_ov, 1