From 9e6836a074ca8142a8a1674b25fe8e04b5c28b37 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Wed, 17 Apr 2019 16:57:42 +0000 Subject: [PATCH] [LVI][CVP] Constrain values in with.overflow branches 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. Differential Revision: https://reviews.llvm.org/D60650 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@358597 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/LazyValueInfo.cpp | 27 ++++++++++++ .../overflow_predicate.ll | 42 +++++++------------ 2 files changed, 41 insertions(+), 28 deletions(-) diff --git a/lib/Analysis/LazyValueInfo.cpp b/lib/Analysis/LazyValueInfo.cpp index 9442044b3e8..02a829f500b 100644 --- a/lib/Analysis/LazyValueInfo.cpp +++ b/lib/Analysis/LazyValueInfo.cpp @@ -1134,6 +1134,28 @@ static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, 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 &Visited); @@ -1144,6 +1166,11 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, if (ICmpInst *ICI = dyn_cast(Cond)) return getValueFromICmpCondition(Val, ICI, isTrueDest); + if (auto *EVI = dyn_cast(Cond)) + if (auto *WO = dyn_cast(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 diff --git a/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll b/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll index 395f9879804..e651237e65a 100644 --- a/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll +++ b/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll @@ -19,8 +19,7 @@ define i1 @uadd_ov_false(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -52,8 +51,7 @@ define i1 @uadd_ov_true(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -85,8 +83,7 @@ define i1 @sadd_ov_false(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -118,8 +115,7 @@ define i1 @sadd_ov_true(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -151,8 +147,7 @@ define i1 @usub_ov_false(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -184,8 +179,7 @@ define i1 @usub_ov_true(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -217,8 +211,7 @@ define i1 @ssub_ov_false(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -250,8 +243,7 @@ define i1 @ssub_ov_true(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -283,8 +275,7 @@ define i1 @umul_ov_false(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -316,8 +307,7 @@ define i1 @umul_ov_true(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -350,8 +340,7 @@ define i1 @smul_ov_false_bound1(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -383,8 +372,7 @@ define i1 @smul_ov_false_bound2(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -417,8 +405,7 @@ define i1 @smul_ov_true_bound1(i8 %x, i8* %px, i1* %pc) { ; 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 @@ -450,8 +437,7 @@ define i1 @smul_ov_true_bound2(i8 %x, i8* %px, i1* %pc) { ; 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 -- 2.50.1