From 4d00af1bde7a9db210fe80bb7207832112ef9394 Mon Sep 17 00:00:00 2001 From: Philip Reames Date: Thu, 1 Dec 2016 20:08:47 +0000 Subject: [PATCH] Factor out common parts of LVI and Float2Int into ConstantRange [NFCI] This just extracts out the transfer rules for constant ranges into a single shared point. As it happens, neither bit of code actually overlaps in terms of the handled operators, but with this change that could easily be tweaked in the future. I also want to have this separated out to make experimenting with a eager value info implementation and possibly a ValueTracking-like fixed depth recursion peephole version. There's no reason all four of these can't share a common implementation which reduces the chances of bugs. Differential Revision: https://reviews.llvm.org/D27294 llvm-svn: 288413 --- llvm/include/llvm/IR/ConstantRange.h | 15 ++++++ llvm/lib/Analysis/LazyValueInfo.cpp | 54 ++-------------------- llvm/lib/IR/ConstantRange.cpp | 79 ++++++++++++++++++++++++++++++++ llvm/lib/Transforms/Scalar/Float2Int.cpp | 45 ++++++------------ 4 files changed, 113 insertions(+), 80 deletions(-) diff --git a/llvm/include/llvm/IR/ConstantRange.h b/llvm/include/llvm/IR/ConstantRange.h index 286e2cf..27a9b13 100644 --- a/llvm/include/llvm/IR/ConstantRange.h +++ b/llvm/include/llvm/IR/ConstantRange.h @@ -233,6 +233,15 @@ public: /// ConstantRange unionWith(const ConstantRange &CR) const; + /// Return a new range representing the possible values resulting + /// from an application of the specified cast operator to this range. \p + /// BitWidth is the target bitwidth of the cast. For casts which don't + /// change bitwidth, it must be the same as the source bitwidth. For casts + /// which do change bitwidth, the bitwidth must be consistent with the + /// requested cast and source bitwidth. + ConstantRange castOp(Instruction::CastOps CastOp, + uint32_t BitWidth) const; + /// Return a new range in the specified integer type, which must /// be strictly larger than the current type. The returned range will /// correspond to the possible range of values if the source range had been @@ -260,6 +269,12 @@ public: ConstantRange sextOrTrunc(uint32_t BitWidth) const; /// Return a new range representing the possible values resulting + /// from an application of the specified binary operator to an left hand side + /// of this range and a right hand side of \p Other. + ConstantRange binaryOp(Instruction::BinaryOps BinOp, + const ConstantRange &Other) const; + + /// Return a new range representing the possible values resulting /// from an addition of a value in this range and a value in \p Other. ConstantRange add(const ConstantRange &Other) const; diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 508c9f8..646895a 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -1160,25 +1160,8 @@ bool LazyValueInfoImpl::solveBlockValueCast(LVILatticeVal &BBLV, // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. LVILatticeVal Result; - switch (BBI->getOpcode()) { - case Instruction::Trunc: - Result.markConstantRange(LHSRange.truncate(ResultBitWidth)); - break; - case Instruction::SExt: - Result.markConstantRange(LHSRange.signExtend(ResultBitWidth)); - break; - case Instruction::ZExt: - Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth)); - break; - case Instruction::BitCast: - Result.markConstantRange(LHSRange); - break; - default: - // Should be dead if the code above is correct - llvm_unreachable("inconsistent with above"); - break; - } - + auto CastOp = (Instruction::CastOps) BBI->getOpcode(); + Result.markConstantRange(LHSRange.castOp(CastOp, ResultBitWidth)); BBLV = Result; return true; } @@ -1238,37 +1221,8 @@ bool LazyValueInfoImpl::solveBlockValueBinaryOp(LVILatticeVal &BBLV, // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. LVILatticeVal Result; - switch (BBI->getOpcode()) { - case Instruction::Add: - Result.markConstantRange(LHSRange.add(RHSRange)); - break; - case Instruction::Sub: - Result.markConstantRange(LHSRange.sub(RHSRange)); - break; - case Instruction::Mul: - Result.markConstantRange(LHSRange.multiply(RHSRange)); - break; - case Instruction::UDiv: - Result.markConstantRange(LHSRange.udiv(RHSRange)); - break; - case Instruction::Shl: - Result.markConstantRange(LHSRange.shl(RHSRange)); - break; - case Instruction::LShr: - Result.markConstantRange(LHSRange.lshr(RHSRange)); - break; - case Instruction::And: - Result.markConstantRange(LHSRange.binaryAnd(RHSRange)); - break; - case Instruction::Or: - Result.markConstantRange(LHSRange.binaryOr(RHSRange)); - break; - default: - // Should be dead if the code above is correct - llvm_unreachable("inconsistent with above"); - break; - } - + auto BinOp = (Instruction::BinaryOps) BBI->getOpcode(); + Result.markConstantRange(LHSRange.binaryOp(BinOp, RHSRange)); BBLV = Result; return true; } diff --git a/llvm/lib/IR/ConstantRange.cpp b/llvm/lib/IR/ConstantRange.cpp index e188c80..a85ad46 100644 --- a/llvm/lib/IR/ConstantRange.cpp +++ b/llvm/lib/IR/ConstantRange.cpp @@ -534,6 +534,49 @@ ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const { return ConstantRange(L, U); } +ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp, + uint32_t ResultBitWidth) const { + switch (CastOp) { + default: + llvm_unreachable("unsupported cast type"); + case Instruction::Trunc: + return truncate(ResultBitWidth); + case Instruction::SExt: + return signExtend(ResultBitWidth); + case Instruction::ZExt: + return zeroExtend(ResultBitWidth); + case Instruction::BitCast: + return *this; + case Instruction::FPToUI: + case Instruction::FPToSI: + if (getBitWidth() == ResultBitWidth) + return *this; + else + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + case Instruction::UIToFP: { + // TODO: use input range if available + auto BW = getBitWidth(); + APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth); + APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth); + return ConstantRange(Min, Max); + } + case Instruction::SIToFP: { + // TODO: use input range if available + auto BW = getBitWidth(); + APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth); + APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth); + return ConstantRange(SMin, SMax); + } + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::IntToPtr: + case Instruction::PtrToInt: + case Instruction::AddrSpaceCast: + // Conservatively return full set. + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + }; +} + /// zeroExtend - Return a new range in the specified integer type, which must /// be strictly larger than the current type. The returned range will /// correspond to the possible range of values as if the source range had been @@ -653,6 +696,42 @@ ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const { return *this; } +ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp, + const ConstantRange &Other) const { + assert(BinOp >= Instruction::BinaryOpsBegin && + BinOp < Instruction::BinaryOpsEnd && "Binary operators only!"); + + switch (BinOp) { + case Instruction::Add: + return add(Other); + case Instruction::Sub: + return sub(Other); + case Instruction::Mul: + return multiply(Other); + case Instruction::UDiv: + return udiv(Other); + case Instruction::Shl: + return shl(Other); + case Instruction::LShr: + return lshr(Other); + case Instruction::And: + return binaryAnd(Other); + case Instruction::Or: + return binaryOr(Other); + // Note: floating point operations applied to abstract ranges are just + // ideal integer operations with a lossy representation + case Instruction::FAdd: + return add(Other); + case Instruction::FSub: + return sub(Other); + case Instruction::FMul: + return multiply(Other); + default: + // Conservatively return full set. + return ConstantRange(getBitWidth(), /*isFullSet=*/true); + } +} + ConstantRange ConstantRange::add(const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) diff --git a/llvm/lib/Transforms/Scalar/Float2Int.cpp b/llvm/lib/Transforms/Scalar/Float2Int.cpp index 7aa6dc6..545036d 100644 --- a/llvm/lib/Transforms/Scalar/Float2Int.cpp +++ b/llvm/lib/Transforms/Scalar/Float2Int.cpp @@ -190,21 +190,14 @@ void Float2IntPass::walkBackwards(const SmallPtrSetImpl &Roots) { seen(I, badRange()); break; - case Instruction::UIToFP: { - // Path terminated cleanly. - unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); - APInt Min = APInt::getMinValue(BW).zextOrSelf(MaxIntegerBW+1); - APInt Max = APInt::getMaxValue(BW).zextOrSelf(MaxIntegerBW+1); - seen(I, validateRange(ConstantRange(Min, Max))); - continue; - } - + case Instruction::UIToFP: case Instruction::SIToFP: { - // Path terminated cleanly. + // Path terminated cleanly - use the type of the integer input to seed + // the analysis. unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits(); - APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(MaxIntegerBW+1); - APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(MaxIntegerBW+1); - seen(I, validateRange(ConstantRange(SMin, SMax))); + auto Input = ConstantRange(BW, true); + auto CastOp = (Instruction::CastOps)I->getOpcode(); + seen(I, validateRange(Input.castOp(CastOp, MaxIntegerBW+1))); continue; } @@ -249,23 +242,12 @@ void Float2IntPass::walkForwards() { llvm_unreachable("Should have been handled in walkForwards!"); case Instruction::FAdd: - Op = [](ArrayRef Ops) { - assert(Ops.size() == 2 && "FAdd is a binary operator!"); - return Ops[0].add(Ops[1]); - }; - break; - case Instruction::FSub: - Op = [](ArrayRef Ops) { - assert(Ops.size() == 2 && "FSub is a binary operator!"); - return Ops[0].sub(Ops[1]); - }; - break; - case Instruction::FMul: - Op = [](ArrayRef Ops) { - assert(Ops.size() == 2 && "FMul is a binary operator!"); - return Ops[0].multiply(Ops[1]); + Op = [I](ArrayRef Ops) { + assert(Ops.size() == 2 && "its a binary operator!"); + auto BinOp = (Instruction::BinaryOps) I->getOpcode(); + return Ops[0].binaryOp(BinOp, Ops[1]); }; break; @@ -275,9 +257,12 @@ void Float2IntPass::walkForwards() { // case Instruction::FPToUI: case Instruction::FPToSI: - Op = [](ArrayRef Ops) { + Op = [I](ArrayRef Ops) { assert(Ops.size() == 1 && "FPTo[US]I is a unary operator!"); - return Ops[0]; + // Note: We're ignoring the casts output size here as that's what the + // caller expects. + auto CastOp = (Instruction::CastOps)I->getOpcode(); + return Ops[0].castOp(CastOp, MaxIntegerBW+1); }; break; -- 2.7.4