In LVI, calculate the range of extractvalue(op.with.overflow(%x, %y), 0) as the range of op(%x, %y). This is mainly useful in conjunction with D60650: If the result of the operation is extracted in a branch guarded against overflow, then the value of %x will be appropriately constrained and the result range of the operation will be calculated taking that into account.
Details
Details
Diff Detail
Diff Detail
- Repository
- rL LLVM
Event Timeline
| llvm/test/Transforms/CorrelatedValuePropagation/overflow_predicate.ll | ||
|---|---|---|
| 486 ↗ | (On Diff #195032) | The BB split is here because CVP only simplifies (freestanding) icmps if they depend on a non-local value. |
Comment Actions
Similarly, looks ok, but someone familiar with LVI/CVP should review.
| llvm/lib/Analysis/LazyValueInfo.cpp | ||
|---|---|---|
| 1083–1087 ↗ | (On Diff #195032) | This seems like a repetitive, emergent pattern. |
| llvm/lib/Analysis/LazyValueInfo.cpp | ||
|---|---|---|
| 1083–1087 ↗ | (On Diff #195032) | As we have quite a lot of code by now that has special handling for with.overflow intrinsics, it probably makes sense to create a WithOverflowInst subclass for them, that can hold these kind of helper methods. |
Comment Actions
This looks correct to me, but someone familiar with LVI/CVP should ideally review this.
Comment Actions
This looks like a straightforward extension of the existing logic, so LGTM. Up to you if you want to wait for another review.
But how about making something like below as a preliminary NFC change? Then we would reduce the duplication, and this patch just becomes a single small addition.
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 02a829f500b..10c1dd8f415 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -422,6 +422,8 @@ namespace { BasicBlock *BB); Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB); + bool solveBlockValueForMathOp(ValueLatticeElement &BBLV, + Instruction *MathInst, BasicBlock *BB); bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI, BasicBlock *BB); bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, @@ -1019,6 +1021,31 @@ bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, return true; } +bool LazyValueInfoImpl::solveBlockValueForMathOp(ValueLatticeElement &BBLV, + Instruction *MathInst, + BasicBlock *BB) { + assert((isa<BinaryOperator>(MathInst) || isa<WithOverflowInst>(MathInst)) && + "Expected binop or overflow op"); + + Optional<ConstantRange> Range0 = getRangeForOperand(0, MathInst, BB); + Optional<ConstantRange> Range1 = getRangeForOperand(1, MathInst, BB); + if (!Range0.hasValue() || !Range1.hasValue()) + return false; + + // NOTE: We're currently limited by the set of operations that ConstantRange + // can evaluate symbolically. Enhancing that set will allows us to analyze + // more definitions. + Instruction::BinaryOps Opcode; + if (auto *WithOV = dyn_cast<WithOverflowInst>(MathInst)) + Opcode = WithOV->getBinaryOp(); + else + Opcode = cast<BinaryOperator>(MathInst)->getOpcode(); + + BBLV = ValueLatticeElement::getRange( + Range0.getValue().binaryOp(Opcode, Range1.getValue())); + return true; +} + bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BO, BasicBlock *BB) { @@ -1049,26 +1076,7 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, return true; }; - // Figure out the ranges of the operands. If that fails, use a - // conservative range, but apply the transfer rule anyways. This - // lets us pick up facts from expressions like "and i32 (call i32 - // @foo()), 32" - Optional<ConstantRange> LHSRes = getRangeForOperand(0, BO, BB); - Optional<ConstantRange> RHSRes = getRangeForOperand(1, BO, BB); - - if (!LHSRes.hasValue() || !RHSRes.hasValue()) - // More work to do before applying this transfer rule. - return false; - - ConstantRange LHSRange = LHSRes.getValue(); - ConstantRange RHSRange = RHSRes.getValue(); - - // NOTE: We're currently limited by the set of operations that ConstantRange - // can evaluate symbolically. Enhancing that set will allows us to analyze - // more definitions. - Instruction::BinaryOps BinOp = BO->getOpcode(); - BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange)); - return true; + return solveBlockValueForMathOp(BBLV, BO, BB); } static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
Comment Actions
Also, LGTM
| llvm/lib/Analysis/LazyValueInfo.cpp | ||
|---|---|---|
| 1083 ↗ | (On Diff #195462) | If I'm putting this together correctly, you don't need the filter clause from the actual binary operator version under the assumption that all of the overflowing binary operators are supported right? If so, that probably warrants a comment. |
| 1092 ↗ | (On Diff #195462) | This (correctly) only handles one of two outputs for the overflow inst. Are you planning on adding support for the other? Just curious. |
| llvm/lib/Analysis/LazyValueInfo.cpp | ||
|---|---|---|
| 1083 ↗ | (On Diff #195462) | The filtering in the binary operator code is just a performance optimization: It would still be correct without it, but of course it makes little sense to compute the input ranges, if the output is always going to be a full range due to lack of ConstantRange support. We can drop it once we support all binary operator in CR (urem in D60952, sdiv and srem are still missing). In this case though all the possible binary operators (add, sub and mul) are supported. |
| 1092 ↗ | (On Diff #195462) | I don't think that supporting the overflow result in LVI block value calculation makes a lot of sense: If the overflow value is known, then we'll want the with.overflow intrinsic to be optimized away entirely, which is something that CVP already does (at least for the no overflow case, it doesn't handle always overflow yet). |
Comment Actions
@spatel What do you think about going for the following abstraction instead? What I have in mind here is to make this also reusable for operations other than binaryOp(), such as uadd_sat() and friends.
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index e7ca69150c0..126a3359ea4 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -422,6 +422,10 @@ namespace { BasicBlock *BB); Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB); + bool solveBlockValueBinaryOpImpl( + ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB, + std::function<ConstantRange(const ConstantRange &, + const ConstantRange &)> OpFn); bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI, BasicBlock *BB); bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, @@ -1019,6 +1023,26 @@ bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, return true; } +bool LazyValueInfoImpl::solveBlockValueBinaryOpImpl( + ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB, + std::function<ConstantRange(const ConstantRange &, + const ConstantRange &)> OpFn) { + // Figure out the ranges of the operands. If that fails, use a + // conservative range, but apply the transfer rule anyways. This + // lets us pick up facts from expressions like "and i32 (call i32 + // @foo()), 32" + Optional<ConstantRange> LHSRes = getRangeForOperand(0, I, BB); + Optional<ConstantRange> RHSRes = getRangeForOperand(1, I, BB); + if (!LHSRes.hasValue() || !RHSRes.hasValue()) + // More work to do before applying this transfer rule. + return false; + + ConstantRange LHSRange = LHSRes.getValue(); + ConstantRange RHSRange = RHSRes.getValue(); + BBLV = ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); + return true; +} + bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BO, BasicBlock *BB) { @@ -1039,8 +1063,10 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, case Instruction::AShr: case Instruction::And: case Instruction::Or: - // continue into the code below - break; + return solveBlockValueBinaryOpImpl(BBLV, BO, BB, + [&](const ConstantRange &CR1, const ConstantRange &CR2) { + return CR1.binaryOp(BO->getOpcode(), CR2); + }); default: // Unhandled instructions are overdefined. LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() @@ -1048,27 +1074,6 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BBLV = ValueLatticeElement::getOverdefined(); return true; }; - - // Figure out the ranges of the operands. If that fails, use a - // conservative range, but apply the transfer rule anyways. This - // lets us pick up facts from expressions like "and i32 (call i32 - // @foo()), 32" - Optional<ConstantRange> LHSRes = getRangeForOperand(0, BO, BB); - Optional<ConstantRange> RHSRes = getRangeForOperand(1, BO, BB); - - if (!LHSRes.hasValue() || !RHSRes.hasValue()) - // More work to do before applying this transfer rule. - return false; - - ConstantRange LHSRange = LHSRes.getValue(); - ConstantRange RHSRange = RHSRes.getValue(); - - // NOTE: We're currently limited by the set of operations that ConstantRange - // can evaluate symbolically. Enhancing that set will allows us to analyze - // more definitions. - Instruction::BinaryOps BinOp = BO->getOpcode(); - BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange)); - return true; } static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI,
Comment Actions
I haven't spent much time in here, so I was just trying to avoid code duplication with my suggestion. If you see a better way and more enhancement potential, that's good with me. :)