Index: include/llvm/ADT/APInt.h =================================================================== --- include/llvm/ADT/APInt.h +++ include/llvm/ADT/APInt.h @@ -16,6 +16,7 @@ #ifndef LLVM_ADT_APINT_H #define LLVM_ADT_APINT_H +#include "llvm/ADT/Hashing.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/MathExtras.h" #include @@ -2151,6 +2152,30 @@ // See friend declaration above. This additional declaration is required in // order to compile LLVM with IBM xlC compiler. hash_code hash_value(const APInt &Arg); + +struct DenseMapAPIntKeyInfo { + static inline APInt getEmptyKey() { + APInt V(nullptr, 0); + V.U.VAL = 0; + return V; + } + + static inline APInt getTombstoneKey() { + APInt V(nullptr, 0); + V.U.VAL = 1; + return V; + } + + static unsigned getHashValue(const APInt &Key) { + return static_cast(hash_value(Key)); + } + + static bool isEqual(const APInt &LHS, const APInt &RHS) { + return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; + } +}; + + } // End of llvm namespace #endif Index: include/llvm/Analysis/ValueLattice.h =================================================================== --- include/llvm/Analysis/ValueLattice.h +++ include/llvm/Analysis/ValueLattice.h @@ -24,6 +24,53 @@ /// namespace llvm { + +constexpr size_t const_min(size_t a, size_t b) { + return (a < b) ? a : b; +} + +// We use this trait to set NumLowBitsAvailable based on the alignment of +// Constant and ConstantRange. +struct ConstantAndConstantRangePointerTraits { + static inline void *getAsVoidPointer(void *P) { return P; } + + static inline void *getFromVoidPointer(void *P) { + return P; + } + + enum { NumLowBitsAvailable = + const_min(detail::ConstantLog2::value, + detail::ConstantLog2::value) }; +}; + + + +/// Provide DenseMapInfo for ConstantRange +template<> struct DenseMapInfo { + static inline ConstantRange getEmptyKey() { + return ConstantRange(DenseMapAPIntKeyInfo::getEmptyKey(), + DenseMapAPIntKeyInfo::getEmptyKey()); + } + + static inline ConstantRange getTombstoneKey() { + return ConstantRange(DenseMapAPIntKeyInfo::getEmptyKey(), + DenseMapAPIntKeyInfo::getTombstoneKey()); + } + + static unsigned getHashValue(const ConstantRange &V) { + return static_cast( + hash_combine(hash_value(V.getLower()), hash_value(V.getUpper()))); + } + + static bool isEqual(const ConstantRange &LHS, + const ConstantRange &RHS) { + return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; + } +}; + + +ConstantRange* addConstantRange(ConstantRange CR, DenseMap &CRP); + class ValueLatticeElement { enum ValueLatticeElementTy { /// This Value has no known value yet. As a result, this implies the @@ -51,28 +98,30 @@ /// Val: This stores the current lattice value along with the Constant* for /// the constant if this is a 'constant' or 'notconstant' value. - ValueLatticeElementTy Tag; - Constant *Val; - ConstantRange Range; + PointerIntPair ValuePtr; public: - ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {} + ValueLatticeElement() : ValuePtr(nullptr, undefined) {} - static ValueLatticeElement get(Constant *C) { + static ValueLatticeElement get(Constant *C, + DenseMap &CRP) { ValueLatticeElement Res; if (!isa(C)) - Res.markConstant(C); + Res.markConstant(C, CRP); return Res; } - static ValueLatticeElement getNot(Constant *C) { + static ValueLatticeElement getNot(Constant *C, + DenseMap &CRP ) { ValueLatticeElement Res; if (!isa(C)) - Res.markNotConstant(C); + Res.markNotConstant(C, CRP); return Res; } - static ValueLatticeElement getRange(ConstantRange CR) { + static ValueLatticeElement getRange(ConstantRange CR, + DenseMap &CRP ) { ValueLatticeElement Res; - Res.markConstantRange(std::move(CR)); + Res.markConstantRange(CR, CRP); return Res; } static ValueLatticeElement getOverdefined() { @@ -81,33 +130,34 @@ return Res; } - bool isUndefined() const { return Tag == undefined; } - bool isConstant() const { return Tag == constant; } - bool isNotConstant() const { return Tag == notconstant; } - bool isConstantRange() const { return Tag == constantrange; } - bool isOverdefined() const { return Tag == overdefined; } + unsigned getTag() const { return ValuePtr.getInt(); } + bool isUndefined() const { return getTag() == undefined; } + bool isConstant() const { return getTag() == constant; } + bool isNotConstant() const { return getTag() == notconstant; } + bool isConstantRange() const { return getTag() == constantrange; } + bool isOverdefined() const { return getTag() == overdefined; } Constant *getConstant() const { assert(isConstant() && "Cannot get the constant of a non-constant!"); - return Val; + return static_cast(ValuePtr.getPointer()); } Constant *getNotConstant() const { assert(isNotConstant() && "Cannot get the constant of a non-notconstant!"); - return Val; + return static_cast(ValuePtr.getPointer()); } const ConstantRange &getConstantRange() const { assert(isConstantRange() && "Cannot get the constant-range of a non-constant-range!"); - return Range; + return *static_cast(ValuePtr.getPointer()); } Optional asConstantInteger() const { - if (isConstant() && isa(Val)) { - return cast(Val)->getValue(); - } else if (isConstantRange() && Range.isSingleElement()) { - return *Range.getSingleElement(); + if (isConstant() && isa(getConstant())) { + return cast(getConstant())->getValue(); + } else if (isConstantRange() && getConstantRange().isSingleElement()) { + return *getConstantRange().getSingleElement(); } return None; } @@ -116,13 +166,13 @@ void markOverdefined() { if (isOverdefined()) return; - Tag = overdefined; + ValuePtr.setInt(overdefined); } - void markConstant(Constant *V) { + void markConstant(Constant *V, DenseMap &CRP) { assert(V && "Marking constant with NULL"); if (ConstantInt *CI = dyn_cast(V)) { - markConstantRange(ConstantRange(CI->getValue())); + markConstantRange(ConstantRange(CI->getValue()), CRP); return; } if (isa(V)) @@ -131,14 +181,14 @@ assert((!isConstant() || getConstant() == V) && "Marking constant with different value"); assert(isUndefined()); - Tag = constant; - Val = V; + ValuePtr.setInt(constant); + ValuePtr.setPointer(static_cast(V)); } - void markNotConstant(Constant *V) { + void markNotConstant(Constant *V, DenseMap &CRP) { assert(V && "Marking constant with NULL"); if (ConstantInt *CI = dyn_cast(V)) { - markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue())); + markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()), CRP); return; } if (isa(V)) @@ -149,16 +199,17 @@ assert((!isNotConstant() || getNotConstant() == V) && "Marking !constant with different value"); assert(isUndefined() || isConstant()); - Tag = notconstant; - Val = V; + ValuePtr.setInt(notconstant); + ValuePtr.setPointer(static_cast(V)); } - void markConstantRange(ConstantRange NewR) { + void markConstantRange(ConstantRange NewR, + DenseMap &CRP) { if (isConstantRange()) { if (NewR.isEmptySet()) markOverdefined(); else { - Range = std::move(NewR); + ValuePtr.setPointer(static_cast(addConstantRange(NewR, CRP))); } return; } @@ -167,15 +218,16 @@ if (NewR.isEmptySet()) markOverdefined(); else { - Tag = constantrange; - Range = std::move(NewR); + ValuePtr.setInt(constantrange); + ValuePtr.setPointer(static_cast(addConstantRange(NewR, CRP))); } } public: /// Updates this object to approximate both this object and RHS. Returns /// true if this object has been changed. - bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) { + bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL, + DenseMap &CRP) { if (RHS.isUndefined() || isOverdefined()) return false; if (RHS.isOverdefined()) { @@ -189,14 +241,14 @@ } if (isConstant()) { - if (RHS.isConstant() && Val == RHS.Val) + if (RHS.isConstant() && getConstant() == RHS.getConstant()) return false; markOverdefined(); return true; } if (isNotConstant()) { - if (RHS.isNotConstant() && Val == RHS.Val) + if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant()) return false; markOverdefined(); return true; @@ -209,11 +261,11 @@ markOverdefined(); return true; } - ConstantRange NewR = Range.unionWith(RHS.getConstantRange()); + ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange()); if (NewR.isFullSet()) markOverdefined(); else - markConstantRange(std::move(NewR)); + markConstantRange(std::move(NewR), CRP); return true; } Index: include/llvm/IR/ConstantRange.h =================================================================== --- include/llvm/IR/ConstantRange.h +++ include/llvm/IR/ConstantRange.h @@ -194,6 +194,9 @@ bool operator!=(const ConstantRange &CR) const { return !operator==(CR); } + bool operator<(const ConstantRange &CR) const { + return Upper.slt(CR.Upper); + } /// Subtract the specified constant from the endpoints of this constant range. ConstantRange subtract(const APInt &CI) const; Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -90,7 +90,8 @@ /// not confuse the rest of LVI. Ideally, we'd always return Undefined, but /// we do not make this guarantee. TODO: This would be a useful enhancement. static ValueLatticeElement intersect(const ValueLatticeElement &A, - const ValueLatticeElement &B) { + const ValueLatticeElement &B, + DenseMap &CRP) { // Undefined is the strongest state. It means the value is known to be along // an unreachable path. if (A.isUndefined()) @@ -122,7 +123,7 @@ // Note: An empty range is implicitly converted to overdefined internally. // TODO: We could instead use Undefined here since we've proven a conflict // and thus know this path must be unreachable. - return ValueLatticeElement::getRange(std::move(Range)); + return ValueLatticeElement::getRange(std::move(Range), CRP); } //===----------------------------------------------------------------------===// @@ -387,6 +388,8 @@ /// Keeps track of which block-value pairs are in BlockValueStack. DenseSet > BlockValueSet; + DenseMap ConstantRangePool; + /// Push BV onto BlockValueStack unless it's already in there. /// Returns true on success. bool pushBlockValue(const std::pair &BV) { @@ -470,7 +473,7 @@ LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL, DominatorTree *DT = nullptr) - : AC(AC), DL(DL), DT(DT) {} + : ConstantRangePool(), AC(AC), DL(DL), DT(DT){} }; } // end anonymous namespace @@ -536,12 +539,13 @@ BasicBlock *BB) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) - return ValueLatticeElement::get(VC); + return ValueLatticeElement::get(VC, ConstantRangePool); return TheCache.getCachedValueInfo(Val, BB); } -static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { +static ValueLatticeElement getFromRangeMetadata(Instruction *BBI, + DenseMap &CRP) { switch (BBI->getOpcode()) { default: break; case Instruction::Load: @@ -550,7 +554,7 @@ if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) if (isa(BBI->getType())) { return ValueLatticeElement::getRange( - getConstantRangeFromMetadata(*Ranges)); + getConstantRangeFromMetadata(*Ranges), CRP); } break; }; @@ -608,7 +612,8 @@ // That is unfortunate. PointerType *PT = dyn_cast(BBI->getType()); if (PT && isKnownNonZero(BBI, DL)) { - Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); + Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT), + ConstantRangePool); return true; } if (BBI->getType()->isIntegerTy()) { @@ -622,7 +627,7 @@ DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"); - Res = getFromRangeMetadata(BBI); + Res = getFromRangeMetadata(BBI, ConstantRangePool); return true; } @@ -688,7 +693,8 @@ if (Val->getType()->isPointerTy() && (isKnownNonZero(Val, DL) || isObjectDereferencedInBlock(Val, BB))) { PointerType *PTy = cast(Val->getType()); - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); + Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy), + ConstantRangePool); } else { Result = ValueLatticeElement::getOverdefined(); } @@ -711,7 +717,7 @@ // Explore that input, then return here return false; - Result.mergeIn(EdgeResult, DL); + Result.mergeIn(EdgeResult, DL, ConstantRangePool); // If we hit overdefined, exit early. The BlockVals entry is already set // to overdefined. @@ -723,7 +729,8 @@ if (Val->getType()->isPointerTy() && isObjectDereferencedInBlock(Val, BB)) { PointerType *PTy = cast(Val->getType()); - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); + Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy), + ConstantRangePool); } BBLV = Result; @@ -755,7 +762,7 @@ // Explore that input, then return here return false; - Result.mergeIn(EdgeResult, DL); + Result.mergeIn(EdgeResult, DL, ConstantRangePool); // If we hit overdefined, exit early. The BlockVals entry is already set // to overdefined. @@ -775,6 +782,7 @@ } static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, + DenseMap &CRP, bool isTrueDest = true); // If we can determine a constraint on the value given conditions assumed by @@ -792,7 +800,9 @@ if (!isValidAssumeForContext(I, BBI, DT)) continue; - BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0))); + BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0), + ConstantRangePool), + ConstantRangePool); } // If guards are not used in the module, don't spend time looking for them @@ -805,7 +815,9 @@ BBI->getParent()->rend())) { Value *Cond = nullptr; if (match(&I, m_Intrinsic(m_Value(Cond)))) - BBLV = intersect(BBLV, getValueFromCondition(Val, Cond)); + BBLV = intersect(BBLV, getValueFromCondition(Val, Cond, + ConstantRangePool), + ConstantRangePool); } } @@ -865,7 +877,7 @@ return TrueCR.umax(FalseCR); }; }(); - BBLV = ValueLatticeElement::getRange(ResultCR); + BBLV = ValueLatticeElement::getRange(ResultCR, ConstantRangePool); return true; } @@ -877,9 +889,13 @@ // TODO: We could potentially refine an overdefined true value above. Value *Cond = SI->getCondition(); TrueVal = intersect(TrueVal, - getValueFromCondition(SI->getTrueValue(), Cond, true)); + getValueFromCondition(SI->getTrueValue(), Cond, + ConstantRangePool, true), + ConstantRangePool); FalseVal = intersect(FalseVal, - getValueFromCondition(SI->getFalseValue(), Cond, false)); + getValueFromCondition(SI->getFalseValue(), Cond, + ConstantRangePool, false), + ConstantRangePool); // Handle clamp idioms such as: // %24 = constantrange<0, 17> @@ -908,7 +924,9 @@ m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); FalseVal = intersect(FalseVal, - ValueLatticeElement::getNot(ResNot)); + ValueLatticeElement::getNot(ResNot, + ConstantRangePool), + ConstantRangePool); } break; case ICmpInst::ICMP_NE: @@ -916,7 +934,9 @@ m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); TrueVal = intersect(TrueVal, - ValueLatticeElement::getNot(ResNot)); + ValueLatticeElement::getNot(ResNot, + ConstantRangePool), + ConstantRangePool); } break; }; @@ -924,8 +944,8 @@ } ValueLatticeElement Result; // Start Undefined. - Result.mergeIn(TrueVal, DL); - Result.mergeIn(FalseVal, DL); + Result.mergeIn(TrueVal, DL, ConstantRangePool); + Result.mergeIn(FalseVal, DL, ConstantRangePool); BBLV = Result; return true; } @@ -982,7 +1002,8 @@ // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), - ResultBitWidth)); + ResultBitWidth), + ConstantRangePool); return true; } @@ -1041,11 +1062,13 @@ // 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)); + BBLV = ValueLatticeElement::getRange(LHSRange.binaryOp(BinOp, RHSRange), + ConstantRangePool); return true; } static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, + DenseMap &CRP, bool isTrueDest) { Value *LHS = ICI->getOperand(0); Value *RHS = ICI->getOperand(1); @@ -1053,12 +1076,12 @@ if (isa(RHS)) { if (ICI->isEquality() && LHS == Val) { - // We know that V has the RHS constant if this is a true SETEQ or + // we know that v has the RHS constant if this is a true SETEQ or // false SETNE. if (isTrueDest == (Predicate == ICmpInst::ICMP_EQ)) - return ValueLatticeElement::get(cast(RHS)); + return ValueLatticeElement::get(cast(RHS), CRP); else - return ValueLatticeElement::getNot(cast(RHS)); + return ValueLatticeElement::getNot(cast(RHS), CRP); } } @@ -1102,7 +1125,7 @@ if (Offset) // Apply the offset from above. TrueValues = TrueValues.subtract(Offset->getValue()); - return ValueLatticeElement::getRange(std::move(TrueValues)); + return ValueLatticeElement::getRange(std::move(TrueValues), CRP); } return ValueLatticeElement::getOverdefined(); @@ -1110,13 +1133,16 @@ static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited); + DenseMap &Visited, + DenseMap &CRP); static ValueLatticeElement getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited) { + DenseMap &Visited, + DenseMap &CRP) { + if (ICmpInst *ICI = dyn_cast(Cond)) - return getValueFromICmpCondition(Val, ICI, isTrueDest); + return getValueFromICmpCondition(Val, ICI, CRP, 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 @@ -1127,28 +1153,32 @@ (!isTrueDest && BO->getOpcode() != BinaryOperator::Or)) return ValueLatticeElement::getOverdefined(); - auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited); - auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited); - return intersect(RHS, LHS); + auto RHS = getValueFromCondition(Val, BO->getOperand(0), isTrueDest, Visited, + CRP); + auto LHS = getValueFromCondition(Val, BO->getOperand(1), isTrueDest, Visited, + CRP); + return intersect(RHS, LHS, CRP); } static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest, - DenseMap &Visited) { + DenseMap &Visited, + DenseMap &CRP) { auto I = Visited.find(Cond); if (I != Visited.end()) return I->second; - auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited); + auto Result = getValueFromConditionImpl(Val, Cond, isTrueDest, Visited, CRP); Visited[Cond] = Result; return Result; } ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, + DenseMap &CRP, bool isTrueDest) { assert(Cond && "precondition"); DenseMap Visited; - return getValueFromCondition(Val, Cond, isTrueDest, Visited); + return getValueFromCondition(Val, Cond, isTrueDest, Visited, CRP); } // Return true if Usr has Op as an operand, otherwise false. @@ -1170,7 +1200,8 @@ // lattice value. static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, const APInt &OpConstVal, - const DataLayout &DL) { + const DataLayout &DL, + DenseMap &CRP) { assert(isOperationFoldable(Usr) && "Precondition"); Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal); // Check if Usr can be simplified to a constant. @@ -1179,7 +1210,7 @@ if (auto *C = dyn_cast_or_null( SimplifyCastInst(CI->getOpcode(), OpConst, CI->getDestTy(), DL))) { - return ValueLatticeElement::getRange(ConstantRange(C->getValue())); + return ValueLatticeElement::getRange(ConstantRange(C->getValue()), CRP); } } else if (auto *BO = dyn_cast(Usr)) { bool Op0Match = BO->getOperand(0) == Op; @@ -1190,7 +1221,7 @@ Value *RHS = Op1Match ? OpConst : BO->getOperand(1); if (auto *C = dyn_cast_or_null( SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) { - return ValueLatticeElement::getRange(ConstantRange(C->getValue())); + return ValueLatticeElement::getRange(ConstantRange(C->getValue()), CRP); } } return ValueLatticeElement::getOverdefined(); @@ -1200,7 +1231,8 @@ /// Val is not constrained on the edge. Result is unspecified if return value /// is false. static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, ValueLatticeElement &Result) { + BasicBlock *BBTo, ValueLatticeElement &Result, + DenseMap &CRP) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we // know that v != 0. if (BranchInst *BI = dyn_cast(BBFrom->getTerminator())) { @@ -1217,13 +1249,14 @@ // it is. if (Condition == Val) { Result = ValueLatticeElement::get(ConstantInt::get( - Type::getInt1Ty(Val->getContext()), isTrueDest)); + Type::getInt1Ty(Val->getContext()), isTrueDest), + CRP); return true; } // If the condition of the branch is an equality comparison, we may be // able to infer the value. - Result = getValueFromCondition(Val, Condition, isTrueDest); + Result = getValueFromCondition(Val, Condition, CRP, isTrueDest); if (!Result.isOverdefined()) return true; @@ -1243,7 +1276,7 @@ // %Val = and i1 %Condition, true. // br %Condition, label %then, label %else APInt ConditionVal(1, isTrueDest ? 1 : 0); - Result = constantFoldUser(Usr, Condition, ConditionVal, DL); + Result = constantFoldUser(Usr, Condition, ConditionVal, DL, CRP); } else { // If one of Val's operand has an inferred value, we may be able to // infer the value of Val. @@ -1255,9 +1288,9 @@ for (unsigned i = 0; i < Usr->getNumOperands(); ++i) { Value *Op = Usr->getOperand(i); ValueLatticeElement OpLatticeVal = - getValueFromCondition(Op, Condition, isTrueDest); + getValueFromCondition(Op, Condition, CRP, isTrueDest); if (Optional OpConst = OpLatticeVal.asConstantInteger()) { - Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL); + Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL, CRP); break; } } @@ -1298,7 +1331,7 @@ User *Usr = cast(Val); const DataLayout &DL = BBTo->getModule()->getDataLayout(); ValueLatticeElement EdgeLatticeVal = - constantFoldUser(Usr, Condition, CaseValue, DL); + constantFoldUser(Usr, Condition, CaseValue, DL, CRP); if (EdgeLatticeVal.isOverdefined()) return false; EdgeVal = EdgeLatticeVal.getConstantRange(); @@ -1315,7 +1348,7 @@ } else if (Case.getCaseSuccessor() == BBTo) EdgesVals = EdgesVals.unionWith(EdgeVal); } - Result = ValueLatticeElement::getRange(std::move(EdgesVals)); + Result = ValueLatticeElement::getRange(std::move(EdgesVals), CRP); return true; } return false; @@ -1329,12 +1362,12 @@ Instruction *CxtI) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) { - Result = ValueLatticeElement::get(VC); + Result = ValueLatticeElement::get(VC, ConstantRangePool); return true; } ValueLatticeElement LocalResult; - if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) + if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult, ConstantRangePool)) // If we couldn't constrain the value on the edge, LocalResult doesn't // provide any information. LocalResult = ValueLatticeElement::getOverdefined(); @@ -1367,7 +1400,7 @@ // but then the result is not cached. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); - Result = intersect(LocalResult, InBlock); + Result = intersect(LocalResult, InBlock, ConstantRangePool); return true; } @@ -1393,11 +1426,11 @@ << CxtI->getName() << "'\n"); if (auto *C = dyn_cast(V)) - return ValueLatticeElement::get(C); + return ValueLatticeElement::get(C, ConstantRangePool); ValueLatticeElement Result = ValueLatticeElement::getOverdefined(); if (auto *I = dyn_cast(V)) - Result = getFromRangeMetadata(I); + Result = getFromRangeMetadata(I, ConstantRangePool); intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); DEBUG(dbgs() << " Result = " << Result << "\n"); Index: lib/Analysis/ValueLattice.cpp =================================================================== --- lib/Analysis/ValueLattice.cpp +++ lib/Analysis/ValueLattice.cpp @@ -7,9 +7,24 @@ // //===----------------------------------------------------------------------===// +#include "llvm/ADT/DenseMap.h" #include "llvm/Analysis/ValueLattice.h" + namespace llvm { + + +static DenseMap ConstantRangePool; + + +ConstantRange* addConstantRange(ConstantRange CR, DenseMap &CRP) { + auto I = CRP.insert({CR, 1}); + if (!I.second) + I.first->second += 1; + return const_cast(&I.first->first); +} + + raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) { if (Val.isUndefined()) return OS << "undefined"; Index: lib/IR/LLVMContextImpl.h =================================================================== --- lib/IR/LLVMContextImpl.h +++ lib/IR/LLVMContextImpl.h @@ -59,28 +59,6 @@ class Value; class ValueHandleBase; -struct DenseMapAPIntKeyInfo { - static inline APInt getEmptyKey() { - APInt V(nullptr, 0); - V.U.VAL = 0; - return V; - } - - static inline APInt getTombstoneKey() { - APInt V(nullptr, 0); - V.U.VAL = 1; - return V; - } - - static unsigned getHashValue(const APInt &Key) { - return static_cast(hash_value(Key)); - } - - static bool isEqual(const APInt &LHS, const APInt &RHS) { - return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS; - } -}; - struct DenseMapAPFloatKeyInfo { static inline APFloat getEmptyKey() { return APFloat(APFloat::Bogus(), 1); } static inline APFloat getTombstoneKey() { return APFloat(APFloat::Bogus(), 2); } Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -178,11 +178,11 @@ Val.setPointer(V); } - ValueLatticeElement toValueLattice() const { + ValueLatticeElement toValueLattice(DenseMap &CRP) const { if (isOverdefined()) return ValueLatticeElement::getOverdefined(); if (isConstant()) - return ValueLatticeElement::get(getConstant()); + return ValueLatticeElement::get(getConstant(), CRP); return ValueLatticeElement(); } }; @@ -246,6 +246,8 @@ using Edge = std::pair; DenseSet KnownFeasibleEdges; + DenseMap ConstantRangePool; + public: SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli) : DL(DL), TLI(tli) {} @@ -335,7 +337,7 @@ DenseMap::const_iterator I = ValueState.find(V); assert(I != ValueState.end() && "V not found in ValueState nor Paramstate map!"); - LV = I->second.toValueLattice(); + LV = I->second.toValueLattice(ConstantRangePool); } return LV; @@ -474,7 +476,7 @@ PI = ParamState.insert(std::make_pair(V, ValueLatticeElement())); ValueLatticeElement &LV = PI.first->second; if (PI.second) - LV = getValueState(V).toValueLattice(); + LV = getValueState(V).toValueLattice(ConstantRangePool); return LV; } @@ -1207,7 +1209,7 @@ } else { // Most other parts of the Solver still only use the simpler value // lattice, so we propagate changes for parameters to both lattices. - getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL); + getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(ConstantRangePool), DL, ConstantRangePool); mergeInValue(&*AI, getValueState(*CAI)); } } Index: unittests/Analysis/ValueLatticeTest.cpp =================================================================== --- unittests/Analysis/ValueLatticeTest.cpp +++ unittests/Analysis/ValueLatticeTest.cpp @@ -30,40 +30,42 @@ }; TEST_F(ValueLatticeTest, ValueLatticeGetters) { + DenseMap CRP; auto I32Ty = IntegerType::get(Context, 32); auto *C1 = ConstantInt::get(I32Ty, 1); - EXPECT_TRUE(ValueLatticeElement::get(C1).isConstantRange()); + EXPECT_TRUE(ValueLatticeElement::get(C1, CRP).isConstantRange()); EXPECT_TRUE( - ValueLatticeElement::getRange({C1->getValue()}).isConstantRange()); + ValueLatticeElement::getRange({C1->getValue()}, CRP).isConstantRange()); EXPECT_TRUE(ValueLatticeElement::getOverdefined().isOverdefined()); auto FloatTy = Type::getFloatTy(Context); auto *C2 = ConstantFP::get(FloatTy, 1.1); - EXPECT_TRUE(ValueLatticeElement::get(C2).isConstant()); - EXPECT_TRUE(ValueLatticeElement::getNot(C2).isNotConstant()); + EXPECT_TRUE(ValueLatticeElement::get(C2, CRP).isConstant()); + EXPECT_TRUE(ValueLatticeElement::getNot(C2, CRP).isNotConstant()); } TEST_F(ValueLatticeTest, MergeIn) { + DenseMap CRP; auto I32Ty = IntegerType::get(Context, 32); auto *C1 = ConstantInt::get(I32Ty, 1); // Merge to lattice values with equal integer constant. - auto LV1 = ValueLatticeElement::get(C1); - LV1.mergeIn(ValueLatticeElement::get(C1), M.getDataLayout()); + auto LV1 = ValueLatticeElement::get(C1, CRP); + LV1.mergeIn(ValueLatticeElement::get(C1, CRP), M.getDataLayout(), CRP); EXPECT_TRUE(LV1.isConstantRange()); EXPECT_EQ(LV1.asConstantInteger().getValue().getLimitedValue(), 1U); // Merge LV1 with different integer constant. - LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99)), - M.getDataLayout()); + LV1.mergeIn(ValueLatticeElement::get(ConstantInt::get(I32Ty, 99), CRP), + M.getDataLayout(), CRP); EXPECT_TRUE(LV1.isConstantRange()); EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U); EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U); // Merge LV1 in undefined value. ValueLatticeElement LV2; - LV2.mergeIn(LV1, M.getDataLayout()); + LV2.mergeIn(LV1, M.getDataLayout(), CRP); EXPECT_TRUE(LV1.isConstantRange()); EXPECT_EQ(LV1.getConstantRange().getLower().getLimitedValue(), 1U); EXPECT_EQ(LV1.getConstantRange().getUpper().getLimitedValue(), 100U); @@ -72,14 +74,15 @@ EXPECT_EQ(LV2.getConstantRange().getUpper().getLimitedValue(), 100U); // Merge with overdefined. - LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout()); + LV1.mergeIn(ValueLatticeElement::getOverdefined(), M.getDataLayout(), CRP); EXPECT_TRUE(LV1.isOverdefined()); } TEST_F(ValueLatticeTest, satisfiesPredicateIntegers) { + DenseMap CRP; auto I32Ty = IntegerType::get(Context, 32); auto *C1 = ConstantInt::get(I32Ty, 1); - auto LV1 = ValueLatticeElement::get(C1); + auto LV1 = ValueLatticeElement::get(C1, CRP); // Check satisfiesPredicate for equal integer constants. EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_EQ, LV1)); @@ -90,7 +93,8 @@ EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV1)); auto LV2 = - ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)}); + ValueLatticeElement::getRange({APInt(32, 10, true), APInt(32, 20, true)}, + CRP); // Check satisfiesPredicate with distinct integer ranges. EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLT, LV2)); EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::ICMP_SLE, LV2)); @@ -100,7 +104,8 @@ EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::ICMP_SGT, LV2)); auto LV3 = - ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)}); + ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 19, true)}, + CRP); // Check satisfiesPredicate with a subset integer ranges. EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLT, LV3)); EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SLE, LV3)); @@ -110,7 +115,8 @@ EXPECT_FALSE(LV2.satisfiesPredicate(CmpInst::ICMP_SGT, LV3)); auto LV4 = - ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)}); + ValueLatticeElement::getRange({APInt(32, 15, true), APInt(32, 25, true)}, + CRP); // Check satisfiesPredicate with overlapping integer ranges. EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLT, LV4)); EXPECT_FALSE(LV3.satisfiesPredicate(CmpInst::ICMP_SLE, LV4)); @@ -121,10 +127,11 @@ } TEST_F(ValueLatticeTest, satisfiesPredicateFloat) { + DenseMap CRP; auto FloatTy = IntegerType::getFloatTy(Context); auto *C1 = ConstantFP::get(FloatTy, 1.0); - auto LV1 = ValueLatticeElement::get(C1); - auto LV2 = ValueLatticeElement::get(C1); + auto LV1 = ValueLatticeElement::get(C1, CRP); + auto LV2 = ValueLatticeElement::get(C1, CRP); // Check satisfiesPredicate for equal floating point constants. EXPECT_TRUE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2)); @@ -134,8 +141,8 @@ EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLT, LV2)); EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGT, LV2)); - LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2)), - M.getDataLayout()); + LV1.mergeIn(ValueLatticeElement::get(ConstantFP::get(FloatTy, 2.2), CRP), + M.getDataLayout(), CRP); EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OEQ, LV2)); EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OGE, LV2)); EXPECT_FALSE(LV1.satisfiesPredicate(CmpInst::FCMP_OLE, LV2));