diff --git a/llvm/include/llvm/Analysis/AliasAnalysis.h b/llvm/include/llvm/Analysis/AliasAnalysis.h --- a/llvm/include/llvm/Analysis/AliasAnalysis.h +++ b/llvm/include/llvm/Analysis/AliasAnalysis.h @@ -37,6 +37,8 @@ #ifndef LLVM_ANALYSIS_ALIASANALYSIS_H #define LLVM_ANALYSIS_ALIASANALYSIS_H +#include "third_party/llvm/llvm-project/llvm/include/llvm/Analysis/ValueTracking.h" +#include "third_party/llvm/llvm-project/llvm/include/llvm/Support/KnownBits.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/Sequence.h" @@ -493,6 +495,8 @@ /// assumption is disproven. SmallVector AssumptionBasedResults; + KnownBitsCache KnownBitsCache; + AAQueryInfo(CaptureInfo *CI) : CI(CI) {} /// Create a new AAQueryInfo based on this one, but with the cache cleared. diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -46,244 +46,245 @@ constexpr unsigned MaxAnalysisRecursionDepth = 6; - /// Determine which bits of V are known to be either zero or one and return - /// them in the KnownZero/KnownOne bit sets. - /// - /// This function is defined on values with integer type, values with pointer - /// type, and vectors of integers. In the case - /// where V is a vector, the known zero and known one values are the - /// same width as the vector element, and the bit is set only if it is true - /// for all of the elements in the vector. - void computeKnownBits(const Value *V, KnownBits &Known, - const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - OptimizationRemarkEmitter *ORE = nullptr, - bool UseInstrInfo = true); +// Optional cache used by KnownBits. Populated as we walk the use/def graph. +// +// We can key lookups on the basic block that contains CxtI, rather than on CxtI +// itself, because the context instr itself is not significant, only its BB. +using KnownBitsCache = DenseMap< + std::pair, + KnownBits>; - /// Determine which bits of V are known to be either zero or one and return - /// them in the KnownZero/KnownOne bit sets. - /// - /// This function is defined on values with integer type, values with pointer - /// type, and vectors of integers. In the case - /// where V is a vector, the known zero and known one values are the - /// same width as the vector element, and the bit is set only if it is true - /// for all of the demanded elements in the vector. - void computeKnownBits(const Value *V, const APInt &DemandedElts, - KnownBits &Known, const DataLayout &DL, - unsigned Depth = 0, AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - OptimizationRemarkEmitter *ORE = nullptr, - bool UseInstrInfo = true); - - /// Returns the known bits rather than passing by reference. - KnownBits computeKnownBits(const Value *V, const DataLayout &DL, - unsigned Depth = 0, AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - OptimizationRemarkEmitter *ORE = nullptr, - bool UseInstrInfo = true); - - /// Returns the known bits rather than passing by reference. - KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts, - const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - OptimizationRemarkEmitter *ORE = nullptr, - bool UseInstrInfo = true); - - /// Compute known bits from the range metadata. - /// \p KnownZero the set of bits that are known to be zero - /// \p KnownOne the set of bits that are known to be one - void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, - KnownBits &Known); - - /// Return true if LHS and RHS have no common bits set. - bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, - const DataLayout &DL, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); - - /// 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 type and - /// vectors of integers. If 'OrZero' is set, then return true if the given - /// value is either a power of two or zero. - bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, - bool OrZero = false, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); - - bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI); - - /// Return true if the given value is known to be non-zero when defined. For - /// vectors, return true if every element is known to be non-zero when - /// defined. For pointers, if the context instruction and dominator tree are - /// specified, perform context-sensitive analysis and return true if the - /// pointer couldn't possibly be null at the specified instruction. - /// Supports values with integer or pointer type and vectors of integers. - bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, +/// Determine which bits of V are known to be either zero or one and return +/// them in the KnownZero/KnownOne bit sets. +/// +/// This function is defined on values with integer type, values with pointer +/// type, and vectors of integers. In the case +/// where V is a vector, the known zero and known one values are the +/// same width as the vector element, and the bit is set only if it is true +/// for all of the elements in the vector. +void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, + unsigned Depth = 0, AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); + OptimizationRemarkEmitter *ORE = nullptr, + bool UseInstrInfo = true, + KnownBitsCache *Cache = nullptr); - /// Return true if the two given values are negation. - /// Currently can recoginze Value pair: - /// 1: if X = sub (0, Y) or Y = sub (0, X) - /// 2: if X = sub (A, B) and Y = sub (B, A) - bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false); +/// Determine which bits of V are known to be either zero or one and return +/// them in the KnownZero/KnownOne bit sets. +/// +/// This function is defined on values with integer type, values with pointer +/// type, and vectors of integers. In the case +/// where V is a vector, the known zero and known one values are the +/// same width as the vector element, and the bit is set only if it is true +/// for all of the demanded elements in the vector. +void computeKnownBits( + const Value *V, const APInt &DemandedElts, KnownBits &Known, + const DataLayout &DL, unsigned Depth = 0, AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr, + OptimizationRemarkEmitter *ORE = nullptr, bool UseInstrInfo = true, + KnownBitsCache *Cache = nullptr); - /// Returns true if the give value is known to be non-negative. - bool isKnownNonNegative(const Value *V, const DataLayout &DL, - unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); +/// Returns the known bits rather than passing by reference. +KnownBits computeKnownBits( + const Value *V, const DataLayout &DL, unsigned Depth = 0, + AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, OptimizationRemarkEmitter *ORE = nullptr, + bool UseInstrInfo = true, + KnownBitsCache *Cache = nullptr); - /// Returns true if the given value is known be positive (i.e. non-negative - /// and non-zero). - bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); +/// Returns the known bits rather than passing by reference. +KnownBits computeKnownBits( + const Value *V, const APInt &DemandedElts, const DataLayout &DL, + unsigned Depth = 0, AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr, + OptimizationRemarkEmitter *ORE = nullptr, bool UseInstrInfo = true, + KnownBitsCache *Cache = nullptr); - /// Returns true if the given value is known be negative (i.e. non-positive - /// and non-zero). - bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); +/// Compute known bits from the range metadata. +/// \p KnownZero the set of bits that are known to be zero +/// \p KnownOne the set of bits that are known to be one +void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known); - /// Return true if the given values are known to be non-equal when defined. - /// Supports scalar integer types only. - bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); - - /// Return true if 'V & Mask' is known to be zero. We use this predicate to - /// simplify operations downstream. Mask is known to be zero for bits that V - /// cannot have. - /// - /// This function is defined on values with integer type, values with pointer - /// type, and vectors of integers. In the case - /// where V is a vector, the mask, known zero, and known one values are the - /// same width as the vector element, and the bit is set only if it is true - /// for all of the elements in the vector. - bool MaskedValueIsZero(const Value *V, const APInt &Mask, - const DataLayout &DL, - unsigned Depth = 0, AssumptionCache *AC = nullptr, +/// Return true if LHS and RHS have no common bits set. +bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, + const DataLayout &DL, AssumptionCache *AC = nullptr, const Instruction *CxtI = nullptr, const DominatorTree *DT = nullptr, bool UseInstrInfo = true); - /// Return the number of times the sign bit of the register is replicated into - /// the other bits. We know that at least 1 bit is always equal to the sign - /// bit (itself), but other cases can give us information. For example, - /// immediately after an "ashr X, 2", we know that the top 3 bits are all - /// equal to each other, so we return 3. For vectors, return the number of - /// sign bits for the vector element with the mininum number of known sign - /// bits. - unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, - unsigned Depth = 0, AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr, - bool UseInstrInfo = true); +/// 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 type and +/// vectors of integers. If 'OrZero' is set, then return true if the given +/// value is either a power of two or zero. +bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, + bool OrZero = false, unsigned Depth = 0, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Get the upper bound on bit size for this Value \p Op as a signed integer. - /// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)). - /// Similar to the APInt::getSignificantBits function. - unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, - unsigned Depth = 0, - AssumptionCache *AC = nullptr, - const Instruction *CxtI = nullptr, - const DominatorTree *DT = nullptr); +bool isOnlyUsedInZeroEqualityComparison(const Instruction *CxtI); - /// Map a call instruction to an intrinsic ID. Libcalls which have equivalent - /// intrinsics are treated as-if they were intrinsics. - Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, - const TargetLibraryInfo *TLI); +/// Return true if the given value is known to be non-zero when defined. For +/// vectors, return true if every element is known to be non-zero when +/// defined. For pointers, if the context instruction and dominator tree are +/// specified, perform context-sensitive analysis and return true if the +/// pointer couldn't possibly be null at the specified instruction. +/// Supports values with integer or pointer type and vectors of integers. +bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth = 0, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Return true if we can prove that the specified FP value is never equal to - /// -0.0. - bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, - unsigned Depth = 0); +/// Return true if the two given values are negation. +/// Currently can recoginze Value pair: +/// 1: if X = sub (0, Y) or Y = sub (0, X) +/// 2: if X = sub (A, B) and Y = sub (B, A) +bool isKnownNegation(const Value *X, const Value *Y, bool NeedNSW = false); - /// Return true if we can prove that the specified FP value is either NaN or - /// never less than -0.0. - /// - /// NaN --> true - /// +0 --> true - /// -0 --> true - /// x > +0 --> true - /// x < -0 --> false - bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI); +/// Returns true if the give value is known to be non-negative. +bool isKnownNonNegative(const Value *V, const DataLayout &DL, + unsigned Depth = 0, AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Return true if the floating-point scalar value is not an infinity or if - /// the floating-point vector value has no infinities. Return false if a value - /// could ever be infinity. - bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, - unsigned Depth = 0); +/// Returns true if the given value is known be positive (i.e. non-negative +/// and non-zero). +bool isKnownPositive(const Value *V, const DataLayout &DL, unsigned Depth = 0, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Return true if the floating-point scalar value is not a NaN or if the - /// floating-point vector value has no NaN elements. Return false if a value - /// could ever be NaN. - bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, - unsigned Depth = 0); +/// Returns true if the given value is known be negative (i.e. non-positive +/// and non-zero). +bool isKnownNegative(const Value *V, const DataLayout &DL, unsigned Depth = 0, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Return true if we can prove that the specified FP value's sign bit is 0. - /// - /// NaN --> true/false (depending on the NaN's sign bit) - /// +0 --> true - /// -0 --> false - /// x > +0 --> true - /// x < -0 --> false - bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI); +/// Return true if the given values are known to be non-equal when defined. +/// Supports scalar integer types only. +bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// If the specified value can be set by repeating the same byte in memory, - /// return the i8 value that it is represented with. This is true for all i8 - /// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double - /// 0.0 etc. If the value can't be handled with a repeated byte store (e.g. - /// i16 0x1234), return null. If the value is entirely undef and padding, - /// return undef. - Value *isBytewiseValue(Value *V, const DataLayout &DL); +/// Return true if 'V & Mask' is known to be zero. We use this predicate to +/// simplify operations downstream. Mask is known to be zero for bits that V +/// cannot have. +/// +/// This function is defined on values with integer type, values with pointer +/// type, and vectors of integers. In the case +/// where V is a vector, the mask, known zero, and known one values are the +/// same width as the vector element, and the bit is set only if it is true +/// for all of the elements in the vector. +bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, + unsigned Depth = 0, AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Given an aggregate and an sequence of indices, see if the scalar value - /// indexed is already around as a register, for example if it were inserted - /// directly into the aggregate. - /// - /// If InsertBefore is not null, this function will duplicate (modified) - /// insertvalues when a part of a nested struct is extracted. - Value *FindInsertedValue(Value *V, - ArrayRef idx_range, - Instruction *InsertBefore = nullptr); +/// Return the number of times the sign bit of the register is replicated into +/// the other bits. We know that at least 1 bit is always equal to the sign +/// bit (itself), but other cases can give us information. For example, +/// immediately after an "ashr X, 2", we know that the top 3 bits are all +/// equal to each other, so we return 3. For vectors, return the number of +/// sign bits for the vector element with the mininum number of known sign +/// bits. +unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, + unsigned Depth = 0, AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr, + bool UseInstrInfo = true); - /// Analyze the specified pointer to see if it can be expressed as a base - /// pointer plus a constant offset. Return the base and offset to the caller. - /// - /// This is a wrapper around Value::stripAndAccumulateConstantOffsets that - /// creates and later unpacks the required APInt. - inline Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, - const DataLayout &DL, - bool AllowNonInbounds = true) { - APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0); - Value *Base = - Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds); +/// Get the upper bound on bit size for this Value \p Op as a signed integer. +/// i.e. x == sext(trunc(x to MaxSignificantBits) to bitwidth(x)). +/// Similar to the APInt::getSignificantBits function. +unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, + unsigned Depth = 0, + AssumptionCache *AC = nullptr, + const Instruction *CxtI = nullptr, + const DominatorTree *DT = nullptr); - Offset = OffsetAPInt.getSExtValue(); - return Base; +/// Map a call instruction to an intrinsic ID. Libcalls which have equivalent +/// intrinsics are treated as-if they were intrinsics. +Intrinsic::ID getIntrinsicForCallSite(const CallBase &CB, + const TargetLibraryInfo *TLI); + +/// Return true if we can prove that the specified FP value is never equal to +/// -0.0. +bool CannotBeNegativeZero(const Value *V, const TargetLibraryInfo *TLI, + unsigned Depth = 0); + +/// Return true if we can prove that the specified FP value is either NaN or +/// never less than -0.0. +/// +/// NaN --> true +/// +0 --> true +/// -0 --> true +/// x > +0 --> true +/// x < -0 --> false +bool CannotBeOrderedLessThanZero(const Value *V, const TargetLibraryInfo *TLI); + +/// Return true if the floating-point scalar value is not an infinity or if +/// the floating-point vector value has no infinities. Return false if a value +/// could ever be infinity. +bool isKnownNeverInfinity(const Value *V, const TargetLibraryInfo *TLI, + unsigned Depth = 0); + +/// Return true if the floating-point scalar value is not a NaN or if the +/// floating-point vector value has no NaN elements. Return false if a value +/// could ever be NaN. +bool isKnownNeverNaN(const Value *V, const TargetLibraryInfo *TLI, + unsigned Depth = 0); + +/// Return true if we can prove that the specified FP value's sign bit is 0. +/// +/// NaN --> true/false (depending on the NaN's sign bit) +/// +0 --> true +/// -0 --> false +/// x > +0 --> true +/// x < -0 --> false +bool SignBitMustBeZero(const Value *V, const TargetLibraryInfo *TLI); + +/// If the specified value can be set by repeating the same byte in memory, +/// return the i8 value that it is represented with. This is true for all i8 +/// values obviously, but is also true for i32 0, i32 -1, i16 0xF0F0, double +/// 0.0 etc. If the value can't be handled with a repeated byte store (e.g. +/// i16 0x1234), return null. If the value is entirely undef and padding, +/// return undef. +Value *isBytewiseValue(Value *V, const DataLayout &DL); + +/// Given an aggregate and an sequence of indices, see if the scalar value +/// indexed is already around as a register, for example if it were inserted +/// directly into the aggregate. +/// +/// If InsertBefore is not null, this function will duplicate (modified) +/// insertvalues when a part of a nested struct is extracted. +Value *FindInsertedValue(Value *V, ArrayRef idx_range, + Instruction *InsertBefore = nullptr); + +/// Analyze the specified pointer to see if it can be expressed as a base +/// pointer plus a constant offset. Return the base and offset to the caller. +/// +/// This is a wrapper around Value::stripAndAccumulateConstantOffsets that +/// creates and later unpacks the required APInt. +inline Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, + const DataLayout &DL, + bool AllowNonInbounds = true) { + APInt OffsetAPInt(DL.getIndexTypeSizeInBits(Ptr->getType()), 0); + Value *Base = + Ptr->stripAndAccumulateConstantOffsets(DL, OffsetAPInt, AllowNonInbounds); + + Offset = OffsetAPInt.getSExtValue(); + return Base; } inline const Value * GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1227,8 +1227,9 @@ ConstantRange CR = computeConstantRange(Index.Val.V, /* ForSigned */ false, true, &AC, Index.CxtI); - KnownBits Known = - computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT); + KnownBits Known = computeKnownBits(Index.Val.V, DL, 0, &AC, Index.CxtI, DT, + /*ORE=*/nullptr, /*UseInstrInfo=*/true, + &AAQI.KnownBitsCache); CR = CR.intersectWith( ConstantRange::fromKnownBits(Known, /* Signed */ true), ConstantRange::Signed); diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -12,9 +12,16 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/ValueTracking.h" + +#include +#include +#include +#include + #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/Cleanup.h" #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" @@ -70,10 +77,6 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/MathExtras.h" -#include -#include -#include -#include using namespace llvm; using namespace llvm::PatternMatch; @@ -118,13 +121,23 @@ // provide it currently. OptimizationRemarkEmitter *ORE; + // Optional cache. + KnownBitsCache *Cache = nullptr; + /// If true, it is safe to use metadata during simplification. InstrInfoQuery IIQ; Query(const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo, - OptimizationRemarkEmitter *ORE = nullptr) - : DL(DL), AC(AC), CxtI(CxtI), DT(DT), ORE(ORE), IIQ(UseInstrInfo) {} + OptimizationRemarkEmitter *ORE = nullptr, + KnownBitsCache *Cache = nullptr) + : DL(DL), + AC(AC), + CxtI(CxtI), + DT(DT), + ORE(ORE), + Cache(Cache), + IIQ(UseInstrInfo) {} }; } // end anonymous namespace @@ -223,18 +236,20 @@ const DataLayout &DL, unsigned Depth, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, - OptimizationRemarkEmitter *ORE, bool UseInstrInfo) { + OptimizationRemarkEmitter *ORE, bool UseInstrInfo, + KnownBitsCache *Cache) { ::computeKnownBits(V, Known, Depth, - Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE)); + Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE, Cache)); } void llvm::computeKnownBits(const Value *V, const APInt &DemandedElts, KnownBits &Known, const DataLayout &DL, unsigned Depth, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, - OptimizationRemarkEmitter *ORE, bool UseInstrInfo) { + OptimizationRemarkEmitter *ORE, bool UseInstrInfo, + KnownBitsCache *Cache) { ::computeKnownBits(V, DemandedElts, Known, Depth, - Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE)); + Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE, Cache)); } static KnownBits computeKnownBits(const Value *V, const APInt &DemandedElts, @@ -248,9 +263,9 @@ const Instruction *CxtI, const DominatorTree *DT, OptimizationRemarkEmitter *ORE, - bool UseInstrInfo) { + bool UseInstrInfo, KnownBitsCache *Cache) { return ::computeKnownBits( - V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE)); + V, Depth, Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE, Cache)); } KnownBits llvm::computeKnownBits(const Value *V, const APInt &DemandedElts, @@ -258,10 +273,10 @@ AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, OptimizationRemarkEmitter *ORE, - bool UseInstrInfo) { + bool UseInstrInfo, KnownBitsCache* Cache) { return ::computeKnownBits( V, DemandedElts, Depth, - Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE)); + Query(DL, AC, safeCxtI(V, CxtI), DT, UseInstrInfo, ORE, Cache)); } bool llvm::haveNoCommonBitsSet(const Value *LHS, const Value *RHS, @@ -1984,6 +1999,28 @@ } #endif + bool UseCache = Q.Cache && DemandedElts.isAllOnes(); + auto CacheKey = std::make_pair(V, Q.CxtI ? Q.CxtI->getParent() : nullptr); + if (UseCache) { + auto it = Q.Cache->find(CacheKey); + if (it != Q.Cache->end()) { + Known = it->second; + return; + } + } + + // Insert `Known` into the cache when this call to computeKnownBits returns. + Cleanup InsertIntoCacheRAII = [&] { + if (UseCache) { + // We can't reuse the `it` that we looked up at the beginning of this + // function, because Q.Cache is a DenseMap, which does not guarantee + // iterator stability. + auto [_, inserted] = Q.Cache->insert({CacheKey, Known}); + (void) inserted; + assert(inserted); + } + }; + const APInt *C; if (match(V, m_APInt(C))) { // We know all of the bits for a scalar constant or a splat vector constant!