diff options
Diffstat (limited to 'llvm/lib/Analysis/ValueTracking.cpp')
| -rw-r--r-- | llvm/lib/Analysis/ValueTracking.cpp | 509 |
1 files changed, 363 insertions, 146 deletions
diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index c14bdb8bc262..05d5e47bb8d7 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -26,6 +26,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumeBundleQueries.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/GuardUtils.h" #include "llvm/Analysis/InstructionSimplify.h" @@ -70,10 +71,8 @@ #include "llvm/Support/KnownBits.h" #include "llvm/Support/MathExtras.h" #include <algorithm> -#include <array> #include <cassert> #include <cstdint> -#include <iterator> #include <utility> using namespace llvm; @@ -86,13 +85,12 @@ static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses", // According to the LangRef, branching on a poison condition is absolutely // immediate full UB. However, historically we haven't implemented that -// consistently as we have an important transformation (non-trivial unswitch) -// which introduces instances of branch on poison/undef to otherwise well -// defined programs. This flag exists to let us test optimization benefit -// of exploiting the specified behavior (in combination with enabling the -// unswitch fix.) +// consistently as we had an important transformation (non-trivial unswitch) +// which introduced instances of branch on poison/undef to otherwise well +// defined programs. This issue has since been fixed, but the flag is +// temporarily retained to easily diagnose potential regressions. static cl::opt<bool> BranchOnPoisonAsUB("branch-on-poison-as-ub", - cl::Hidden, cl::init(false)); + cl::Hidden, cl::init(true)); /// Returns the bitwidth of the given scalar or pointer type. For vector types, @@ -275,13 +273,39 @@ bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS, assert(LHS->getType()->isIntOrIntVectorTy() && "LHS and RHS should be integers"); // Look for an inverted mask: (X & ~M) op (Y & M). - Value *M; - if (match(LHS, m_c_And(m_Not(m_Value(M)), m_Value())) && - match(RHS, m_c_And(m_Specific(M), m_Value()))) + { + Value *M; + if (match(LHS, m_c_And(m_Not(m_Value(M)), m_Value())) && + match(RHS, m_c_And(m_Specific(M), m_Value()))) + return true; + if (match(RHS, m_c_And(m_Not(m_Value(M)), m_Value())) && + match(LHS, m_c_And(m_Specific(M), m_Value()))) + return true; + } + + // X op (Y & ~X) + if (match(RHS, m_c_And(m_Not(m_Specific(LHS)), m_Value())) || + match(LHS, m_c_And(m_Not(m_Specific(RHS)), m_Value()))) return true; - if (match(RHS, m_c_And(m_Not(m_Value(M)), m_Value())) && - match(LHS, m_c_And(m_Specific(M), m_Value()))) + + // X op ((X & Y) ^ Y) -- this is the canonical form of the previous pattern + // for constant Y. + Value *Y; + if (match(RHS, + m_c_Xor(m_c_And(m_Specific(LHS), m_Value(Y)), m_Deferred(Y))) || + match(LHS, m_c_Xor(m_c_And(m_Specific(RHS), m_Value(Y)), m_Deferred(Y)))) return true; + + // Look for: (A & B) op ~(A | B) + { + Value *A, *B; + if (match(LHS, m_And(m_Value(A), m_Value(B))) && + match(RHS, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))) + return true; + if (match(RHS, m_And(m_Value(A), m_Value(B))) && + match(LHS, m_Not(m_c_Or(m_Specific(A), m_Specific(B))))) + return true; + } IntegerType *IT = cast<IntegerType>(LHS->getType()->getScalarType()); KnownBits LHSKnown(IT->getBitWidth()); KnownBits RHSKnown(IT->getBitWidth()); @@ -451,7 +475,12 @@ static void computeKnownBitsMul(const Value *Op0, const Value *Op1, bool NSW, } } - Known = KnownBits::mul(Known, Known2); + bool SelfMultiply = Op0 == Op1; + // TODO: SelfMultiply can be poison, but not undef. + if (SelfMultiply) + SelfMultiply &= + isGuaranteedNotToBeUndefOrPoison(Op0, Q.AC, Q.CxtI, Q.DT, Depth + 1); + Known = KnownBits::mul(Known, Known2, SelfMultiply); // Only make use of no-wrap flags if we failed to compute the sign bit // directly. This matters if the multiplication always overflows, in @@ -656,7 +685,8 @@ static void computeKnownBitsFromAssume(const Value *V, KnownBits &Known, if (V->getType()->isPointerTy()) { if (RetainedKnowledge RK = getKnowledgeValidInContext( V, {Attribute::Alignment}, Q.CxtI, Q.DT, Q.AC)) { - Known.Zero.setLowBits(Log2_64(RK.ArgValue)); + if (isPowerOf2_64(RK.ArgValue)) + Known.Zero.setLowBits(Log2_64(RK.ArgValue)); } } @@ -1041,7 +1071,7 @@ static void computeKnownBitsFromShiftOperator( // bits. This check is sunk down as far as possible to avoid the expensive // call to isKnownNonZero if the cheaper checks above fail. if (ShiftAmt == 0) { - if (!ShifterOperandIsNonZero.hasValue()) + if (!ShifterOperandIsNonZero) ShifterOperandIsNonZero = isKnownNonZero(I->getOperand(1), DemandedElts, Depth + 1, Q); if (*ShifterOperandIsNonZero) @@ -1726,8 +1756,7 @@ static void computeKnownBitsFromOperator(const Operator *I, break; } - unsigned FirstZeroHighBit = - 32 - countLeadingZeros(VScaleMax.getValue()); + unsigned FirstZeroHighBit = 32 - countLeadingZeros(*VScaleMax); if (FirstZeroHighBit < BitWidth) Known.Zero.setBitsFrom(FirstZeroHighBit); @@ -2007,6 +2036,63 @@ void computeKnownBits(const Value *V, const APInt &DemandedElts, assert((Known.Zero & Known.One) == 0 && "Bits known to be one AND zero?"); } +/// Try to detect a recurrence that the value of the induction variable is +/// always a power of two (or zero). +static bool isPowerOfTwoRecurrence(const PHINode *PN, bool OrZero, + unsigned Depth, Query &Q) { + BinaryOperator *BO = nullptr; + Value *Start = nullptr, *Step = nullptr; + if (!matchSimpleRecurrence(PN, BO, Start, Step)) + return false; + + // Initial value must be a power of two. + for (const Use &U : PN->operands()) { + if (U.get() == Start) { + // Initial value comes from a different BB, need to adjust context + // instruction for analysis. + Q.CxtI = PN->getIncomingBlock(U)->getTerminator(); + if (!isKnownToBeAPowerOfTwo(Start, OrZero, Depth, Q)) + return false; + } + } + + // Except for Mul, the induction variable must be on the left side of the + // increment expression, otherwise its value can be arbitrary. + if (BO->getOpcode() != Instruction::Mul && BO->getOperand(1) != Step) + return false; + + Q.CxtI = BO->getParent()->getTerminator(); + switch (BO->getOpcode()) { + case Instruction::Mul: + // Power of two is closed under multiplication. + return (OrZero || Q.IIQ.hasNoUnsignedWrap(BO) || + Q.IIQ.hasNoSignedWrap(BO)) && + isKnownToBeAPowerOfTwo(Step, OrZero, Depth, Q); + case Instruction::SDiv: + // Start value must not be signmask for signed division, so simply being a + // power of two is not sufficient, and it has to be a constant. + if (!match(Start, m_Power2()) || match(Start, m_SignMask())) + return false; + LLVM_FALLTHROUGH; + case Instruction::UDiv: + // Divisor must be a power of two. + // If OrZero is false, cannot guarantee induction variable is non-zero after + // division, same for Shr, unless it is exact division. + return (OrZero || Q.IIQ.isExact(BO)) && + isKnownToBeAPowerOfTwo(Step, false, Depth, Q); + case Instruction::Shl: + return OrZero || Q.IIQ.hasNoUnsignedWrap(BO) || Q.IIQ.hasNoSignedWrap(BO); + case Instruction::AShr: + if (!match(Start, m_Power2()) || match(Start, m_SignMask())) + return false; + LLVM_FALLTHROUGH; + case Instruction::LShr: + return OrZero || Q.IIQ.isExact(BO); + default: + return false; + } +} + /// Return true if the given value is known to have exactly one /// bit set when defined. For vectors return true if every element is known to /// be a power of two when defined. Supports values with integer or pointer @@ -2098,6 +2184,30 @@ bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero, unsigned Depth, } } + // A PHI node is power of two if all incoming values are power of two, or if + // it is an induction variable where in each step its value is a power of two. + if (const PHINode *PN = dyn_cast<PHINode>(V)) { + Query RecQ = Q; + + // Check if it is an induction variable and always power of two. + if (isPowerOfTwoRecurrence(PN, OrZero, Depth, RecQ)) + return true; + + // Recursively check all incoming values. Limit recursion to 2 levels, so + // that search complexity is limited to number of operands^2. + unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1); + return llvm::all_of(PN->operands(), [&](const Use &U) { + // Value is power of 2 if it is coming from PHI node itself by induction. + if (U.get() == PN) + return true; + + // Change the context instruction to the incoming block where it is + // evaluated. + RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator(); + return isKnownToBeAPowerOfTwo(U.get(), OrZero, NewDepth, RecQ); + }); + } + // An exact divide or right shift can only shift off zero bits, so the result // is a power of two only if the first operand is a power of two and not // copying a sign bit (sdiv int_min, 2). @@ -2588,6 +2698,9 @@ bool isKnownNonZero(const Value *V, const APInt &DemandedElts, unsigned Depth, if (isKnownNonZero(Op, Depth, Q) && isGuaranteedNotToBePoison(Op, Q.AC, Q.CxtI, Q.DT, Depth)) return true; + } else if (const auto *II = dyn_cast<IntrinsicInst>(V)) { + if (II->getIntrinsicID() == Intrinsic::vscale) + return true; } KnownBits Known(BitWidth); @@ -2885,6 +2998,24 @@ static bool isSignedMinMaxClamp(const Value *Select, const Value *&In, return CLow->sle(*CHigh); } +static bool isSignedMinMaxIntrinsicClamp(const IntrinsicInst *II, + const APInt *&CLow, + const APInt *&CHigh) { + assert((II->getIntrinsicID() == Intrinsic::smin || + II->getIntrinsicID() == Intrinsic::smax) && "Must be smin/smax"); + + Intrinsic::ID InverseID = getInverseMinMaxIntrinsic(II->getIntrinsicID()); + auto *InnerII = dyn_cast<IntrinsicInst>(II->getArgOperand(0)); + if (!InnerII || InnerII->getIntrinsicID() != InverseID || + !match(II->getArgOperand(1), m_APInt(CLow)) || + !match(InnerII->getArgOperand(1), m_APInt(CHigh))) + return false; + + if (II->getIntrinsicID() == Intrinsic::smin) + std::swap(CLow, CHigh); + return CLow->sle(*CHigh); +} + /// For vector constants, loop over the elements and find the constant with the /// minimum number of sign bits. Return 0 if the value is not a vector constant /// or if any element was not analyzed; otherwise, return the count for the @@ -3225,6 +3356,12 @@ static unsigned ComputeNumSignBitsImpl(const Value *V, // Absolute value reduces number of sign bits by at most 1. return Tmp - 1; + case Intrinsic::smin: + case Intrinsic::smax: { + const APInt *CLow, *CHigh; + if (isSignedMinMaxIntrinsicClamp(II, CLow, CHigh)) + return std::min(CLow->getNumSignBits(), CHigh->getNumSignBits()); + } } } } @@ -3358,9 +3495,6 @@ Intrinsic::ID llvm::getIntrinsicForCallSite(const CallBase &CB, /// NOTE: Do not check 'nsz' here because that fast-math-flag does not guarantee /// that a value is not -0.0. It only guarantees that -0.0 may be treated /// the same as +0.0 in floating-point ops. -/// -/// NOTE: this function will need to be revisited when we support non-default -/// rounding modes! bool llvm::CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, unsigned Depth) { if (auto *CFP = dyn_cast<ConstantFP>(V)) @@ -3390,9 +3524,21 @@ bool llvm::CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, case Intrinsic::sqrt: case Intrinsic::canonicalize: return CannotBeNegativeZero(Call->getArgOperand(0), TLI, Depth + 1); + case Intrinsic::experimental_constrained_sqrt: { + // NOTE: This rounding mode restriction may be too strict. + const auto *CI = cast<ConstrainedFPIntrinsic>(Call); + if (CI->getRoundingMode() == RoundingMode::NearestTiesToEven) + return CannotBeNegativeZero(Call->getArgOperand(0), TLI, Depth + 1); + else + return false; + } // fabs(x) != -0.0 case Intrinsic::fabs: return true; + // sitofp and uitofp turn into +0.0 for zero. + case Intrinsic::experimental_constrained_sitofp: + case Intrinsic::experimental_constrained_uitofp: + return true; } } @@ -4032,69 +4178,83 @@ bool llvm::isGEPBasedOnPointerToString(const GEPOperator *GEP, return true; } +// If V refers to an initialized global constant, set Slice either to +// its initializer if the size of its elements equals ElementSize, or, +// for ElementSize == 8, to its representation as an array of unsiged +// char. Return true on success. bool llvm::getConstantDataArrayInfo(const Value *V, ConstantDataArraySlice &Slice, unsigned ElementSize, uint64_t Offset) { assert(V); - // Look through bitcast instructions and geps. - V = V->stripPointerCasts(); + // Drill down into the pointer expression V, ignoring any intervening + // casts, and determine the identity of the object it references along + // with the cumulative byte offset into it. + const GlobalVariable *GV = + dyn_cast<GlobalVariable>(getUnderlyingObject(V)); + if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) + // Fail if V is not based on constant global object. + return false; - // If the value is a GEP instruction or constant expression, treat it as an - // offset. - if (const GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { - // The GEP operator should be based on a pointer to string constant, and is - // indexing into the string constant. - if (!isGEPBasedOnPointerToString(GEP, ElementSize)) - return false; + const DataLayout &DL = GV->getParent()->getDataLayout(); + APInt Off(DL.getIndexTypeSizeInBits(V->getType()), 0); - // If the second index isn't a ConstantInt, then this is a variable index - // into the array. If this occurs, we can't say anything meaningful about - // the string. - uint64_t StartIdx = 0; - if (const ConstantInt *CI = dyn_cast<ConstantInt>(GEP->getOperand(2))) - StartIdx = CI->getZExtValue(); - else - return false; - return getConstantDataArrayInfo(GEP->getOperand(0), Slice, ElementSize, - StartIdx + Offset); - } + if (GV != V->stripAndAccumulateConstantOffsets(DL, Off, + /*AllowNonInbounds*/ true)) + // Fail if a constant offset could not be determined. + return false; - // The GEP instruction, constant or instruction, must reference a global - // variable that is a constant and is initialized. The referenced constant - // initializer is the array that we'll use for optimization. - const GlobalVariable *GV = dyn_cast<GlobalVariable>(V); - if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) + uint64_t StartIdx = Off.getLimitedValue(); + if (StartIdx == UINT64_MAX) + // Fail if the constant offset is excessive. return false; - const ConstantDataArray *Array; - ArrayType *ArrayTy; + Offset += StartIdx; + + ConstantDataArray *Array = nullptr; + ArrayType *ArrayTy = nullptr; + if (GV->getInitializer()->isNullValue()) { Type *GVTy = GV->getValueType(); - if ( (ArrayTy = dyn_cast<ArrayType>(GVTy)) ) { - // A zeroinitializer for the array; there is no ConstantDataArray. - Array = nullptr; - } else { - const DataLayout &DL = GV->getParent()->getDataLayout(); - uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy).getFixedSize(); - uint64_t Length = SizeInBytes / (ElementSize / 8); - if (Length <= Offset) - return false; + uint64_t SizeInBytes = DL.getTypeStoreSize(GVTy).getFixedSize(); + uint64_t Length = SizeInBytes / (ElementSize / 8); - Slice.Array = nullptr; - Slice.Offset = 0; - Slice.Length = Length - Offset; - return true; + Slice.Array = nullptr; + Slice.Offset = 0; + // Return an empty Slice for undersized constants to let callers + // transform even undefined library calls into simpler, well-defined + // expressions. This is preferable to making the calls although it + // prevents sanitizers from detecting such calls. + Slice.Length = Length < Offset ? 0 : Length - Offset; + return true; + } + + auto *Init = const_cast<Constant *>(GV->getInitializer()); + if (auto *ArrayInit = dyn_cast<ConstantDataArray>(Init)) { + Type *InitElTy = ArrayInit->getElementType(); + if (InitElTy->isIntegerTy(ElementSize)) { + // If Init is an initializer for an array of the expected type + // and size, use it as is. + Array = ArrayInit; + ArrayTy = ArrayInit->getType(); } - } else { - // This must be a ConstantDataArray. - Array = dyn_cast<ConstantDataArray>(GV->getInitializer()); - if (!Array) + } + + if (!Array) { + if (ElementSize != 8) + // TODO: Handle conversions to larger integral types. + return false; + + // Otherwise extract the portion of the initializer starting + // at Offset as an array of bytes, and reset Offset. + Init = ReadByteArrayFromGlobal(GV, Offset); + if (!Init) return false; - ArrayTy = Array->getType(); + + Offset = 0; + Array = dyn_cast<ConstantDataArray>(Init); + ArrayTy = dyn_cast<ArrayType>(Init->getType()); } - if (!ArrayTy->getElementType()->isIntegerTy(ElementSize)) - return false; uint64_t NumElts = ArrayTy->getArrayNumElements(); if (Offset > NumElts) @@ -4117,6 +4277,12 @@ bool llvm::getConstantStringInfo(const Value *V, StringRef &Str, if (Slice.Array == nullptr) { if (TrimAtNul) { + // Return a nul-terminated string even for an empty Slice. This is + // safe because all existing SimplifyLibcalls callers require string + // arguments and the behavior of the functions they fold is undefined + // otherwise. Folding the calls this way is preferable to making + // the undefined library calls, even though it prevents sanitizers + // from reporting such calls. Str = StringRef(); return true; } @@ -4196,9 +4362,13 @@ static uint64_t GetStringLengthH(const Value *V, return 0; if (Slice.Array == nullptr) + // Zeroinitializer (including an empty one). return 1; - // Search for nul characters + // Search for the first nul character. Return a conservative result even + // when there is no nul. This is safe since otherwise the string function + // being folded such as strlen is undefined, and can be preferable to + // making the undefined library call. unsigned NullIndex = 0; for (unsigned E = Slice.Length; NullIndex < E; ++NullIndex) { if (Slice.Array->getElementAsInteger(Slice.Offset + NullIndex) == 0) @@ -4517,13 +4687,40 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, const Operator *Inst = dyn_cast<Operator>(V); if (!Inst) return false; + return isSafeToSpeculativelyExecuteWithOpcode(Inst->getOpcode(), Inst, CtxI, DT, TLI); +} + +bool llvm::isSafeToSpeculativelyExecuteWithOpcode(unsigned Opcode, + const Operator *Inst, + const Instruction *CtxI, + const DominatorTree *DT, + const TargetLibraryInfo *TLI) { +#ifndef NDEBUG + if (Inst->getOpcode() != Opcode) { + // Check that the operands are actually compatible with the Opcode override. + auto hasEqualReturnAndLeadingOperandTypes = + [](const Operator *Inst, unsigned NumLeadingOperands) { + if (Inst->getNumOperands() < NumLeadingOperands) + return false; + const Type *ExpectedType = Inst->getType(); + for (unsigned ItOp = 0; ItOp < NumLeadingOperands; ++ItOp) + if (Inst->getOperand(ItOp)->getType() != ExpectedType) + return false; + return true; + }; + assert(!Instruction::isBinaryOp(Opcode) || + hasEqualReturnAndLeadingOperandTypes(Inst, 2)); + assert(!Instruction::isUnaryOp(Opcode) || + hasEqualReturnAndLeadingOperandTypes(Inst, 1)); + } +#endif for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i))) if (C->canTrap()) return false; - switch (Inst->getOpcode()) { + switch (Opcode) { default: return true; case Instruction::UDiv: @@ -4554,7 +4751,9 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, return false; } case Instruction::Load: { - const LoadInst *LI = cast<LoadInst>(Inst); + const LoadInst *LI = dyn_cast<LoadInst>(Inst); + if (!LI) + return false; if (mustSuppressSpeculation(*LI)) return false; const DataLayout &DL = LI->getModule()->getDataLayout(); @@ -4563,7 +4762,9 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, TLI); } case Instruction::Call: { - auto *CI = cast<const CallInst>(Inst); + auto *CI = dyn_cast<const CallInst>(Inst); + if (!CI) + return false; const Function *Callee = CI->getCalledFunction(); // The called function could have undefined behavior or side-effects, even @@ -4595,8 +4796,20 @@ bool llvm::isSafeToSpeculativelyExecute(const Value *V, } } -bool llvm::mayBeMemoryDependent(const Instruction &I) { - return I.mayReadOrWriteMemory() || !isSafeToSpeculativelyExecute(&I); +bool llvm::mayHaveNonDefUseDependency(const Instruction &I) { + if (I.mayReadOrWriteMemory()) + // Memory dependency possible + return true; + if (!isSafeToSpeculativelyExecute(&I)) + // Can't move above a maythrow call or infinite loop. Or if an + // inalloca alloca, above a stacksave call. + return true; + if (!isGuaranteedToTransferExecutionToSuccessor(&I)) + // 1) Can't reorder two inf-loop calls, even if readonly + // 2) Also can't reorder an inf-loop call below a instruction which isn't + // safe to speculative execute. (Inverse of above) + return true; + return false; } /// Convert ConstantRange OverflowResult into ValueTracking OverflowResult. @@ -4766,6 +4979,22 @@ OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { + // X - (X % ?) + // The remainder of a value can't have greater magnitude than itself, + // so the subtraction can't overflow. + + // X - (X -nuw ?) + // In the minimal case, this would simplify to "?", so there's no subtract + // at all. But if this analysis is used to peek through casts, for example, + // then determining no-overflow may allow other transforms. + + // TODO: There are other patterns like this. + // See simplifyICmpWithBinOpOnLHS() for candidates. + if (match(RHS, m_URem(m_Specific(LHS), m_Value())) || + match(RHS, m_NUWSub(m_Specific(LHS), m_Value()))) + if (isGuaranteedNotToBeUndefOrPoison(LHS, AC, CxtI, DT)) + return OverflowResult::NeverOverflows; + // Checking for conditions implied by dominating conditions may be expensive. // Limit it to usub_with_overflow calls for now. if (match(CxtI, @@ -4789,6 +5018,19 @@ OverflowResult llvm::computeOverflowForSignedSub(const Value *LHS, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT) { + // X - (X % ?) + // The remainder of a value can't have greater magnitude than itself, + // so the subtraction can't overflow. + + // X - (X -nsw ?) + // In the minimal case, this would simplify to "?", so there's no subtract + // at all. But if this analysis is used to peek through casts, for example, + // then determining no-overflow may allow other transforms. + if (match(RHS, m_SRem(m_Specific(LHS), m_Value())) || + match(RHS, m_NSWSub(m_Specific(LHS), m_Value()))) + if (isGuaranteedNotToBeUndefOrPoison(LHS, AC, CxtI, DT)) + return OverflowResult::NeverOverflows; + // If LHS and RHS each have at least two sign bits, the subtraction // cannot overflow. if (ComputeNumSignBits(LHS, DL, 0, AC, CxtI, DT) > 1 && @@ -5100,7 +5342,9 @@ static bool isGuaranteedNotToBeUndefOrPoison(const Value *V, } if (auto *I = dyn_cast<LoadInst>(V)) - if (I->getMetadata(LLVMContext::MD_noundef)) + if (I->hasMetadata(LLVMContext::MD_noundef) || + I->hasMetadata(LLVMContext::MD_dereferenceable) || + I->hasMetadata(LLVMContext::MD_dereferenceable_or_null)) return true; if (programUndefinedIfUndefOrPoison(V, PoisonOnly)) @@ -5125,10 +5369,10 @@ static bool isGuaranteedNotToBeUndefOrPoison(const Value *V, auto *TI = Dominator->getBlock()->getTerminator(); Value *Cond = nullptr; - if (auto BI = dyn_cast<BranchInst>(TI)) { + if (auto BI = dyn_cast_or_null<BranchInst>(TI)) { if (BI->isConditional()) Cond = BI->getCondition(); - } else if (auto SI = dyn_cast<SwitchInst>(TI)) { + } else if (auto SI = dyn_cast_or_null<SwitchInst>(TI)) { Cond = SI->getCondition(); } @@ -5763,20 +6007,6 @@ static SelectPatternResult matchMinMax(CmpInst::Predicate Pred, if (Pred != CmpInst::ICMP_SGT && Pred != CmpInst::ICMP_SLT) return {SPF_UNKNOWN, SPNB_NA, false}; - // Z = X -nsw Y - // (X >s Y) ? 0 : Z ==> (Z >s 0) ? 0 : Z ==> SMIN(Z, 0) - // (X <s Y) ? 0 : Z ==> (Z <s 0) ? 0 : Z ==> SMAX(Z, 0) - if (match(TrueVal, m_Zero()) && - match(FalseVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS)))) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMIN : SPF_SMAX, SPNB_NA, false}; - - // Z = X -nsw Y - // (X >s Y) ? Z : 0 ==> (Z >s 0) ? Z : 0 ==> SMAX(Z, 0) - // (X <s Y) ? Z : 0 ==> (Z <s 0) ? Z : 0 ==> SMIN(Z, 0) - if (match(FalseVal, m_Zero()) && - match(TrueVal, m_NSWSub(m_Specific(CmpLHS), m_Specific(CmpRHS)))) - return {Pred == CmpInst::ICMP_SGT ? SPF_SMAX : SPF_SMIN, SPNB_NA, false}; - const APInt *C1; if (!match(CmpRHS, m_APInt(C1))) return {SPF_UNKNOWN, SPNB_NA, false}; @@ -6576,11 +6806,38 @@ Optional<bool> llvm::isImpliedCondition(const Value *LHS, const Value *RHS, if (LHS == RHS) return LHSIsTrue; - const ICmpInst *RHSCmp = dyn_cast<ICmpInst>(RHS); - if (RHSCmp) + if (const ICmpInst *RHSCmp = dyn_cast<ICmpInst>(RHS)) return isImpliedCondition(LHS, RHSCmp->getPredicate(), RHSCmp->getOperand(0), RHSCmp->getOperand(1), DL, LHSIsTrue, Depth); + + if (Depth == MaxAnalysisRecursionDepth) + return None; + + // LHS ==> (RHS1 || RHS2) if LHS ==> RHS1 or LHS ==> RHS2 + // LHS ==> !(RHS1 && RHS2) if LHS ==> !RHS1 or LHS ==> !RHS2 + const Value *RHS1, *RHS2; + if (match(RHS, m_LogicalOr(m_Value(RHS1), m_Value(RHS2)))) { + if (Optional<bool> Imp = + isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1)) + if (*Imp == true) + return true; + if (Optional<bool> Imp = + isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1)) + if (*Imp == true) + return true; + } + if (match(RHS, m_LogicalAnd(m_Value(RHS1), m_Value(RHS2)))) { + if (Optional<bool> Imp = + isImpliedCondition(LHS, RHS1, DL, LHSIsTrue, Depth + 1)) + if (*Imp == false) + return false; + if (Optional<bool> Imp = + isImpliedCondition(LHS, RHS2, DL, LHSIsTrue, Depth + 1)) + if (*Imp == false) + return false; + } + return None; } @@ -7072,66 +7329,25 @@ getOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, const DataLayout &DL) { Optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, const Value *Ptr2, const DataLayout &DL) { - Ptr1 = Ptr1->stripPointerCasts(); - Ptr2 = Ptr2->stripPointerCasts(); + APInt Offset1(DL.getIndexTypeSizeInBits(Ptr1->getType()), 0); + APInt Offset2(DL.getIndexTypeSizeInBits(Ptr2->getType()), 0); + Ptr1 = Ptr1->stripAndAccumulateConstantOffsets(DL, Offset1, true); + Ptr2 = Ptr2->stripAndAccumulateConstantOffsets(DL, Offset2, true); // Handle the trivial case first. - if (Ptr1 == Ptr2) { - return 0; - } + if (Ptr1 == Ptr2) + return Offset2.getSExtValue() - Offset1.getSExtValue(); const GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1); const GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2); - // If one pointer is a GEP see if the GEP is a constant offset from the base, - // as in "P" and "gep P, 1". - // Also do this iteratively to handle the the following case: - // Ptr_t1 = GEP Ptr1, c1 - // Ptr_t2 = GEP Ptr_t1, c2 - // Ptr2 = GEP Ptr_t2, c3 - // where we will return c1+c2+c3. - // TODO: Handle the case when both Ptr1 and Ptr2 are GEPs of some common base - // -- replace getOffsetFromBase with getOffsetAndBase, check that the bases - // are the same, and return the difference between offsets. - auto getOffsetFromBase = [&DL](const GEPOperator *GEP, - const Value *Ptr) -> Optional<int64_t> { - const GEPOperator *GEP_T = GEP; - int64_t OffsetVal = 0; - bool HasSameBase = false; - while (GEP_T) { - auto Offset = getOffsetFromIndex(GEP_T, 1, DL); - if (!Offset) - return None; - OffsetVal += *Offset; - auto Op0 = GEP_T->getOperand(0)->stripPointerCasts(); - if (Op0 == Ptr) { - HasSameBase = true; - break; - } - GEP_T = dyn_cast<GEPOperator>(Op0); - } - if (!HasSameBase) - return None; - return OffsetVal; - }; - - if (GEP1) { - auto Offset = getOffsetFromBase(GEP1, Ptr2); - if (Offset) - return -*Offset; - } - if (GEP2) { - auto Offset = getOffsetFromBase(GEP2, Ptr1); - if (Offset) - return Offset; - } - // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical // base. After that base, they may have some number of common (and // potentially variable) indices. After that they handle some constant // offset, which determines their offset from each other. At this point, we // handle no other case. - if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0)) + if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0) || + GEP1->getSourceElementType() != GEP2->getSourceElementType()) return None; // Skip any common indices and track the GEP types. @@ -7140,9 +7356,10 @@ Optional<int64_t> llvm::isPointerOffset(const Value *Ptr1, const Value *Ptr2, if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx)) break; - auto Offset1 = getOffsetFromIndex(GEP1, Idx, DL); - auto Offset2 = getOffsetFromIndex(GEP2, Idx, DL); - if (!Offset1 || !Offset2) + auto IOffset1 = getOffsetFromIndex(GEP1, Idx, DL); + auto IOffset2 = getOffsetFromIndex(GEP2, Idx, DL); + if (!IOffset1 || !IOffset2) return None; - return *Offset2 - *Offset1; + return *IOffset2 - *IOffset1 + Offset2.getSExtValue() - + Offset1.getSExtValue(); } |