Index: llvm/include/llvm/Analysis/ValueLattice.h =================================================================== --- llvm/include/llvm/Analysis/ValueLattice.h +++ llvm/include/llvm/Analysis/ValueLattice.h @@ -9,21 +9,21 @@ #ifndef LLVM_ANALYSIS_VALUELATTICE_H #define LLVM_ANALYSIS_VALUELATTICE_H +#include "llvm/ADT/DenseSet.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" +#include "llvm/Support/Allocator.h" + // //===----------------------------------------------------------------------===// // ValueLatticeElement //===----------------------------------------------------------------------===// -/// This class represents lattice values for constants. -/// -/// FIXME: This is basically just for bringup, this can be made a lot more rich -/// in the future. -/// - namespace llvm { +/// This class represents lattice values for constants. class ValueLatticeElement { + friend struct ValueLatticeMapInfo; + enum ValueLatticeElementTy { /// This Value has no known value yet. As a result, this implies the /// producing instruction is dead. Caution: We use this as the starting @@ -481,5 +481,77 @@ "size of ValueLatticeElement changed unexpectedly"); raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val); + +struct ValueLatticeMapInfo { + static inline ValueLatticeElement *getEmptyKey() { + return DenseMapInfo::getEmptyKey(); + } + static inline ValueLatticeElement *getTombstoneKey() { + return DenseMapInfo::getTombstoneKey(); + } + + static unsigned getHashValue(const ValueLatticeElement *Elem) { + switch (Elem->Tag) { + case ValueLatticeElement::overdefined: + case ValueLatticeElement::unknown: + case ValueLatticeElement::undef: + return hash_combine(Elem->Tag); + case ValueLatticeElement::constant: + case ValueLatticeElement::notconstant: + return hash_combine(Elem->Tag, Elem->ConstVal); + case ValueLatticeElement::constantrange_including_undef: + case ValueLatticeElement::constantrange: + return hash_combine(Elem->Tag, Elem->Range.getLower(), + Elem->Range.getUpper()); + } + llvm_unreachable("Invalid tag"); + } + + static bool isEqual(const ValueLatticeElement *A, + const ValueLatticeElement *B) { + if (A == getEmptyKey() || A == getTombstoneKey() || + B == getEmptyKey() || B == getTombstoneKey()) + return A == B; + + if (A->Tag != B->Tag) + return false; + + switch (A->Tag) { + case ValueLatticeElement::overdefined: + case ValueLatticeElement::unknown: + case ValueLatticeElement::undef: + return true; + case ValueLatticeElement::constant: + case ValueLatticeElement::notconstant: + return A->ConstVal == B->ConstVal; + case ValueLatticeElement::constantrange_including_undef: + case ValueLatticeElement::constantrange: + return A->Range.getBitWidth() == B->Range.getBitWidth() && + A->Range == B->Range; + } + llvm_unreachable("Invalid tag"); + } +}; + +class ValueLatticePool { + SpecificBumpPtrAllocator BPA; + const ValueLatticeElement *Unknown; + const ValueLatticeElement *Overdefined; + DenseMap ConstantElems; + DenseSet Elems; + +public: + ValueLatticePool(); + + const ValueLatticeElement *getUnknown() const { return Unknown; } + const ValueLatticeElement *getOverdefined() const { return Overdefined; } + + const ValueLatticeElement *getConstant(Constant *C); + const ValueLatticeElement *getNotConstant(Constant *C); + const ValueLatticeElement *getRange(const ConstantRange &CR, + bool MayIncludeUndef = false); + const ValueLatticeElement *getElement(const ValueLatticeElement &Elem); +}; + } // end namespace llvm #endif Index: llvm/lib/Analysis/LazyValueInfo.cpp =================================================================== --- llvm/lib/Analysis/LazyValueInfo.cpp +++ llvm/lib/Analysis/LazyValueInfo.cpp @@ -157,8 +157,8 @@ /// the per-value lattice elements, as well as a separate set for /// overdefined values to reduce memory usage. struct BlockCacheEntry { - SmallDenseMap, ValueLatticeElement, 4> LatticeElements; - SmallDenseSet, 4> OverDefined; + SmallDenseMap, const ValueLatticeElement *, 4> + LatticeElements; }; /// Cached information per basic block. @@ -185,35 +185,22 @@ public: void insertResult(Value *Val, BasicBlock *BB, - const ValueLatticeElement &Result) { + const ValueLatticeElement *Result) { BlockCacheEntry *Entry = getOrCreateBlockEntry(BB); - - // Insert over-defined values into their own cache to reduce memory - // overhead. - if (Result.isOverdefined()) - Entry->OverDefined.insert(Val); - else - Entry->LatticeElements.insert({ Val, Result }); + Entry->LatticeElements.insert({ Val, Result }); auto HandleIt = ValueHandles.find_as(Val); if (HandleIt == ValueHandles.end()) ValueHandles.insert({ Val, this }); } - Optional getCachedValueInfo(Value *V, - BasicBlock *BB) const { + const ValueLatticeElement *getCachedValueInfo(Value *V, + BasicBlock *BB) const { const BlockCacheEntry *Entry = getBlockEntry(BB); if (!Entry) - return None; - - if (Entry->OverDefined.count(V)) - return ValueLatticeElement::getOverdefined(); - - auto LatticeIt = Entry->LatticeElements.find(V); - if (LatticeIt == Entry->LatticeElements.end()) - return None; + return nullptr; - return LatticeIt->second; + return Entry->LatticeElements.lookup(V); } /// clear - Empty the cache. @@ -232,15 +219,13 @@ /// Updates the cache to remove any influence an overdefined value in /// OldSucc might have (unless also overdefined in NewSucc). This just /// flushes elements from the cache and does not add any. - void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc); + void threadEdgeImpl(BasicBlock *OldSucc, BasicBlock *NewSucc); }; } void LazyValueInfoCache::eraseValue(Value *V) { - for (auto &Pair : BlockCache) { + for (auto &Pair : BlockCache) Pair.second->LatticeElements.erase(V); - Pair.second->OverDefined.erase(V); - } auto HandleIt = ValueHandles.find_as(V); if (HandleIt != ValueHandles.end()) @@ -273,10 +258,15 @@ worklist.push_back(OldSucc); const BlockCacheEntry *Entry = getBlockEntry(OldSucc); - if (!Entry || Entry->OverDefined.empty()) - return; // Nothing to process here. - SmallVector ValsToClear(Entry->OverDefined.begin(), - Entry->OverDefined.end()); + if (!Entry) + return; + + SmallVector ValsToClear; + for (const auto &Pair : Entry->LatticeElements) + if (Pair.second->isOverdefined()) + ValsToClear.push_back(Pair.first); + if (ValsToClear.empty()) + return; // Use a worklist to perform a depth-first search of OldSucc's successors. // NOTE: We do not need a visited list since any blocks we have already @@ -291,17 +281,19 @@ // If a value was marked overdefined in OldSucc, and is here too... auto OI = BlockCache.find(ToUpdate); - if (OI == BlockCache.end() || OI->second->OverDefined.empty()) + if (OI == BlockCache.end()) continue; - auto &ValueSet = OI->second->OverDefined; + auto &ValueSet = OI->second->LatticeElements; bool changed = false; for (Value *V : ValsToClear) { - if (!ValueSet.erase(V)) + auto It = ValueSet.find(V); + if (It == ValueSet.end() || !It->second->isOverdefined()) continue; // If we removed anything, then we potentially need to update // blocks successors too. + ValueSet.erase(It); changed = true; } @@ -342,6 +334,9 @@ /// Cached results from previous queries LazyValueInfoCache TheCache; + /// Pool of ValueLatticeElements. + ValueLatticePool Pool; + /// This stack holds the state of the value solver during a query. /// It basically emulates the callstack of the naive /// recursive value lookup process. @@ -369,38 +364,38 @@ /// if it exists in the module. Function *GuardDecl; - Optional getBlockValue(Value *Val, BasicBlock *BB); - Optional getEdgeValue(Value *V, BasicBlock *F, + const ValueLatticeElement *getBlockValue(Value *Val, BasicBlock *BB); + const ValueLatticeElement *getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, Instruction *CxtI = nullptr); // These methods process one work item and may add more. A false value // returned means that the work item was not completely processed and must // be revisited after going through the new items. bool solveBlockValue(Value *Val, BasicBlock *BB); - Optional solveBlockValueImpl(Value *Val, BasicBlock *BB); - Optional solveBlockValueNonLocal(Value *Val, - BasicBlock *BB); - Optional solveBlockValuePHINode(PHINode *PN, - BasicBlock *BB); - Optional solveBlockValueSelect(SelectInst *S, - BasicBlock *BB); + const ValueLatticeElement *solveBlockValueImpl(Value *Val, BasicBlock *BB); + const ValueLatticeElement *solveBlockValueNonLocal(Value *Val, + BasicBlock *BB); + const ValueLatticeElement *solveBlockValuePHINode(PHINode *PN, + BasicBlock *BB); + const ValueLatticeElement *solveBlockValueSelect(SelectInst *S, + BasicBlock *BB); Optional getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB); - Optional solveBlockValueBinaryOpImpl( + const ValueLatticeElement *solveBlockValueBinaryOpImpl( Instruction *I, BasicBlock *BB, std::function OpFn); - Optional solveBlockValueBinaryOp(BinaryOperator *BBI, - BasicBlock *BB); - Optional solveBlockValueCast(CastInst *CI, - BasicBlock *BB); - Optional solveBlockValueOverflowIntrinsic( + const ValueLatticeElement *solveBlockValueBinaryOp(BinaryOperator *BBI, + BasicBlock *BB); + const ValueLatticeElement *solveBlockValueCast(CastInst *CI, + BasicBlock *BB); + const ValueLatticeElement *solveBlockValueOverflowIntrinsic( WithOverflowInst *WO, BasicBlock *BB); - Optional solveBlockValueSaturatingIntrinsic( + const ValueLatticeElement *solveBlockValueSaturatingIntrinsic( SaturatingInst *SI, BasicBlock *BB); - Optional solveBlockValueIntrinsic(IntrinsicInst *II, - BasicBlock *BB); - Optional solveBlockValueExtractValue( + const ValueLatticeElement *solveBlockValueIntrinsic(IntrinsicInst *II, + BasicBlock *BB); + const ValueLatticeElement *solveBlockValueExtractValue( ExtractValueInst *EVI, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, ValueLatticeElement &BBLV, @@ -474,8 +469,7 @@ // Fill in the original values while (!StartingStack.empty()) { std::pair &e = StartingStack.back(); - TheCache.insertResult(e.second, e.first, - ValueLatticeElement::getOverdefined()); + TheCache.insertResult(e.second, e.first, Pool.getOverdefined()); StartingStack.pop_back(); } BlockValueSet.clear(); @@ -489,7 +483,7 @@ // The work item was completely processed. assert(BlockValueStack.back() == e && "Nothing should have been pushed!"); #ifndef NDEBUG - Optional BBLV = + const ValueLatticeElement *BBLV = TheCache.getCachedValueInfo(e.second, e.first); assert(BBLV && "Result should be in cache!"); LLVM_DEBUG( @@ -506,39 +500,38 @@ } } -Optional LazyValueInfoImpl::getBlockValue(Value *Val, - BasicBlock *BB) { +const ValueLatticeElement *LazyValueInfoImpl::getBlockValue(Value *Val, + BasicBlock *BB) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) - return ValueLatticeElement::get(VC); + return Pool.getConstant(VC); - if (Optional OptLatticeVal = + if (const ValueLatticeElement *OptLatticeVal = TheCache.getCachedValueInfo(Val, BB)) return OptLatticeVal; // We have hit a cycle, assume overdefined. if (!pushBlockValue({ BB, Val })) - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); // Yet to be resolved. - return None; + return nullptr; } -static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { +static const ValueLatticeElement *getFromRangeMetadata(ValueLatticePool &Pool, + Instruction *BBI) { switch (BBI->getOpcode()) { default: break; case Instruction::Load: case Instruction::Call: case Instruction::Invoke: if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range)) - if (isa(BBI->getType())) { - return ValueLatticeElement::getRange( - getConstantRangeFromMetadata(*Ranges)); - } + if (isa(BBI->getType())) + return Pool.getRange(getConstantRangeFromMetadata(*Ranges)); break; }; // Nothing known - will be intersected with other facts - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { @@ -548,16 +541,16 @@ // Hold off inserting this value into the Cache in case we have to return // false and come back later. - Optional Res = solveBlockValueImpl(Val, BB); + const ValueLatticeElement *Res = solveBlockValueImpl(Val, BB); if (!Res) // Work pushed, will revisit return false; - TheCache.insertResult(Val, BB, *Res); + TheCache.insertResult(Val, BB, Res); return true; } -Optional LazyValueInfoImpl::solveBlockValueImpl( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueImpl( Value *Val, BasicBlock *BB) { Instruction *BBI = dyn_cast(Val); if (!BBI || BBI->getParent() != BB) @@ -580,7 +573,7 @@ // That is unfortunate. PointerType *PT = dyn_cast(BBI->getType()); if (PT && isKnownNonZero(BBI, DL)) - return ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); + return Pool.getNotConstant(ConstantPointerNull::get(PT)); if (BBI->getType()->isIntegerTy()) { if (auto *CI = dyn_cast(BBI)) @@ -598,7 +591,7 @@ LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"); - return getFromRangeMetadata(BBI); + return getFromRangeMetadata(Pool, BBI); } static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { @@ -650,7 +643,7 @@ return false; } -Optional LazyValueInfoImpl::solveBlockValueNonLocal( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueNonLocal( Value *Val, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. @@ -665,9 +658,9 @@ (isKnownNonZero(Val, DL) || (isObjectDereferencedInBlock(Val, BB) && !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) - return ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); + return Pool.getNotConstant(ConstantPointerNull::get(PTy)); else - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } // Loop over all of our predecessors, merging what we know from them into @@ -680,10 +673,10 @@ // canonicalizing to make this true rather than relying on this happy // accident. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { - Optional EdgeResult = getEdgeValue(Val, *PI, BB); + const ValueLatticeElement *EdgeResult = getEdgeValue(Val, *PI, BB); if (!EdgeResult) // Explore that input, then return here - return None; + return nullptr; Result.mergeIn(*EdgeResult); @@ -696,20 +689,19 @@ // this particular block. PointerType *PTy = dyn_cast(Val->getType()); if (PTy && isObjectDereferencedInBlock(Val, BB) && - !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) { - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); - } - - return Result; + !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) + return Pool.getNotConstant(ConstantPointerNull::get(PTy)); + else + return Pool.getOverdefined(); } } // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined()); - return Result; + return Pool.getElement(Result); } -Optional LazyValueInfoImpl::solveBlockValuePHINode( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValuePHINode( PHINode *PN, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. @@ -722,11 +714,11 @@ // Note that we can provide PN as the context value to getEdgeValue, even // though the results will be cached, because PN is the value being used as // the cache key in the caller. - Optional EdgeResult = + const ValueLatticeElement *EdgeResult = getEdgeValue(PhiVal, PhiBB, BB, PN); if (!EdgeResult) // Explore that input, then return here - return None; + return nullptr; Result.mergeIn(*EdgeResult); @@ -736,13 +728,13 @@ LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (local).\n"); - return Result; + return Pool.getOverdefined(); } } // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined() && "Possible PHI in entry block?"); - return Result; + return Pool.getElement(Result); } static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, @@ -785,34 +777,30 @@ } } -Optional LazyValueInfoImpl::solveBlockValueSelect( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueSelect( SelectInst *SI, BasicBlock *BB) { // Recurse on our inputs if needed - Optional OptTrueVal = - getBlockValue(SI->getTrueValue(), BB); - if (!OptTrueVal) - return None; - ValueLatticeElement &TrueVal = *OptTrueVal; + const ValueLatticeElement *TrueVal = getBlockValue(SI->getTrueValue(), BB); + if (!TrueVal) + return nullptr; // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. - if (TrueVal.isOverdefined()) - return ValueLatticeElement::getOverdefined(); + if (TrueVal->isOverdefined()) + return Pool.getOverdefined(); - Optional OptFalseVal = - getBlockValue(SI->getFalseValue(), BB); - if (!OptFalseVal) - return None; - ValueLatticeElement &FalseVal = *OptFalseVal; + const ValueLatticeElement *FalseVal = getBlockValue(SI->getFalseValue(), BB); + if (!FalseVal) + return nullptr; // If we hit overdefined, don't ask more queries. We want to avoid poisoning // extra slots in the table if we can. - if (FalseVal.isOverdefined()) - return ValueLatticeElement::getOverdefined(); + if (FalseVal->isOverdefined()) + return Pool.getOverdefined(); - if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { - const ConstantRange &TrueCR = TrueVal.getConstantRange(); - const ConstantRange &FalseCR = FalseVal.getConstantRange(); + if (TrueVal->isConstantRange() && FalseVal->isConstantRange()) { + const ConstantRange &TrueCR = TrueVal->getConstantRange(); + const ConstantRange &FalseCR = FalseVal->getConstantRange(); Value *LHS = nullptr; Value *RHS = nullptr; SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS); @@ -834,28 +822,27 @@ return TrueCR.umax(FalseCR); }; }(); - return ValueLatticeElement::getRange( - ResultCR, TrueVal.isConstantRangeIncludingUndef() | - FalseVal.isConstantRangeIncludingUndef()); + return Pool.getRange(ResultCR, TrueVal->isConstantRangeIncludingUndef() | + FalseVal->isConstantRangeIncludingUndef()); } if (SPR.Flavor == SPF_ABS) { if (LHS == SI->getTrueValue()) - return ValueLatticeElement::getRange( - TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef()); + return Pool.getRange( + TrueCR.abs(), TrueVal->isConstantRangeIncludingUndef()); if (LHS == SI->getFalseValue()) - return ValueLatticeElement::getRange( - FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef()); + return Pool.getRange( + FalseCR.abs(), FalseVal->isConstantRangeIncludingUndef()); } if (SPR.Flavor == SPF_NABS) { ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth())); if (LHS == SI->getTrueValue()) - return ValueLatticeElement::getRange( - Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef()); + return Pool.getRange( + Zero.sub(TrueCR.abs()), FalseVal->isConstantRangeIncludingUndef()); if (LHS == SI->getFalseValue()) - return ValueLatticeElement::getRange( - Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef()); + return Pool.getRange( + Zero.sub(FalseCR.abs()), FalseVal->isConstantRangeIncludingUndef()); } } @@ -863,10 +850,10 @@ // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5). // TODO: We could potentially refine an overdefined true value above. Value *Cond = SI->getCondition(); - TrueVal = intersect(TrueVal, - getValueFromCondition(SI->getTrueValue(), Cond, true)); - FalseVal = intersect(FalseVal, - getValueFromCondition(SI->getFalseValue(), Cond, false)); + ValueLatticeElement NewTrueVal = intersect( + *TrueVal, getValueFromCondition(SI->getTrueValue(), Cond, true)); + ValueLatticeElement NewFalseVal = intersect( + *FalseVal, getValueFromCondition(SI->getFalseValue(), Cond, false)); // Handle clamp idioms such as: // %24 = constantrange<0, 17> @@ -894,35 +881,35 @@ if (match(SI->getFalseValue(), m_Add(m_Specific(A), m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); - FalseVal = intersect(FalseVal, - ValueLatticeElement::getNot(ResNot)); + NewFalseVal = intersect(NewFalseVal, + ValueLatticeElement::getNot(ResNot)); } break; case ICmpInst::ICMP_NE: if (match(SI->getTrueValue(), m_Add(m_Specific(A), m_ConstantInt(CIAdded)))) { auto ResNot = addConstants(CIBase, CIAdded); - TrueVal = intersect(TrueVal, - ValueLatticeElement::getNot(ResNot)); + NewTrueVal = intersect(NewTrueVal, + ValueLatticeElement::getNot(ResNot)); } break; }; } } - ValueLatticeElement Result = TrueVal; - Result.mergeIn(FalseVal); - return Result; + ValueLatticeElement Result = std::move(NewTrueVal); + Result.mergeIn(NewFalseVal); + return Pool.getElement(Result); } Optional LazyValueInfoImpl::getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB) { - Optional OptVal = getBlockValue(I->getOperand(Op), BB); + const ValueLatticeElement *OptVal = getBlockValue(I->getOperand(Op), BB); if (!OptVal) return None; - ValueLatticeElement &Val = *OptVal; + ValueLatticeElement Val = *OptVal; intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I); if (Val.isConstantRange()) return Val.getConstantRange(); @@ -932,12 +919,12 @@ return ConstantRange::getFull(OperandBitWidth); } -Optional LazyValueInfoImpl::solveBlockValueCast( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueCast( CastInst *CI, BasicBlock *BB) { // Without knowing how wide the input is, we can't analyze it in any useful // way. if (!CI->getOperand(0)->getType()->isSized()) - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); // Filter out casts we don't know how to reason about before attempting to // recurse on our operand. This can cut a long search short if we know we're @@ -952,7 +939,7 @@ // Unhandled instructions are overdefined. LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n"); - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } // Figure out the range of the LHS. If that fails, we still apply the @@ -961,19 +948,18 @@ Optional LHSRes = getRangeForOperand(0, CI, BB); if (!LHSRes.hasValue()) // More work to do before applying this transfer rule. - return None; - const ConstantRange &LHSRange = LHSRes.getValue(); + return nullptr; + const ConstantRange &LHSRange = LHSRes.getValue(); const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth(); // NOTE: We're currently limited by the set of operations that ConstantRange // can evaluate symbolically. Enhancing that set will allows us to analyze // more definitions. - return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), - ResultBitWidth)); + return Pool.getRange(LHSRange.castOp(CI->getOpcode(), ResultBitWidth)); } -Optional LazyValueInfoImpl::solveBlockValueBinaryOpImpl( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueBinaryOpImpl( Instruction *I, BasicBlock *BB, std::function OpFn) { @@ -985,14 +971,14 @@ Optional RHSRes = getRangeForOperand(1, I, BB); if (!LHSRes.hasValue() || !RHSRes.hasValue()) // More work to do before applying this transfer rule. - return None; + return nullptr; const ConstantRange &LHSRange = LHSRes.getValue(); const ConstantRange &RHSRange = RHSRes.getValue(); - return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); + return Pool.getRange(OpFn(LHSRange, RHSRange)); } -Optional LazyValueInfoImpl::solveBlockValueBinaryOp( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueBinaryOp( BinaryOperator *BO, BasicBlock *BB) { assert(BO->getOperand(0)->getType()->isSized() && "all operands to binary operators are sized"); @@ -1000,7 +986,7 @@ // Xor is the only operation not supported by ConstantRange::binaryOp(). LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown binary operator).\n"); - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } if (auto *OBO = dyn_cast(BO)) { @@ -1023,7 +1009,7 @@ }); } -Optional +const ValueLatticeElement * LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB) { return solveBlockValueBinaryOpImpl( @@ -1032,7 +1018,7 @@ }); } -Optional +const ValueLatticeElement * LazyValueInfoImpl::solveBlockValueSaturatingIntrinsic(SaturatingInst *SI, BasicBlock *BB) { switch (SI->getIntrinsicID()) { @@ -1061,17 +1047,17 @@ } } -Optional LazyValueInfoImpl::solveBlockValueIntrinsic( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueIntrinsic( IntrinsicInst *II, BasicBlock *BB) { if (auto *SI = dyn_cast(II)) return solveBlockValueSaturatingIntrinsic(SI, BB); LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown intrinsic).\n"); - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } -Optional LazyValueInfoImpl::solveBlockValueExtractValue( +const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueExtractValue( ExtractValueInst *EVI, BasicBlock *BB) { if (auto *WO = dyn_cast(EVI->getAggregateOperand())) if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0) @@ -1086,7 +1072,7 @@ LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown extractvalue).\n"); - return ValueLatticeElement::getOverdefined(); + return Pool.getOverdefined(); } static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, @@ -1401,22 +1387,22 @@ /// Compute the value of Val on the edge BBFrom -> BBTo or the value at /// the basic block if the edge does not constrain Val. -Optional LazyValueInfoImpl::getEdgeValue( +const ValueLatticeElement *LazyValueInfoImpl::getEdgeValue( Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast(Val)) - return ValueLatticeElement::get(VC); + return Pool.getConstant(VC); ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo) .getValueOr(ValueLatticeElement::getOverdefined()); if (hasSingleValue(LocalResult)) // Can't get any more precise here - return LocalResult; + return Pool.getElement(LocalResult); - Optional OptInBlock = getBlockValue(Val, BBFrom); + const ValueLatticeElement *OptInBlock = getBlockValue(Val, BBFrom); if (!OptInBlock) - return None; - ValueLatticeElement &InBlock = *OptInBlock; + return nullptr; + ValueLatticeElement InBlock = *OptInBlock; // Try to intersect ranges of the BB and the constraint on the edge. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, @@ -1431,7 +1417,7 @@ // but then the result is not cached. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); - return intersect(LocalResult, InBlock); + return Pool.getElement(intersect(LocalResult, InBlock)); } ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, @@ -1440,7 +1426,7 @@ << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); - Optional OptResult = getBlockValue(V, BB); + const ValueLatticeElement *OptResult = getBlockValue(V, BB); if (!OptResult) { solve(); OptResult = getBlockValue(V, BB); @@ -1462,7 +1448,7 @@ ValueLatticeElement Result = ValueLatticeElement::getOverdefined(); if (auto *I = dyn_cast(V)) - Result = getFromRangeMetadata(I); + Result = *getFromRangeMetadata(Pool, I); intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); LLVM_DEBUG(dbgs() << " Result = " << Result << "\n"); @@ -1476,7 +1462,7 @@ << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); - Optional Result = getEdgeValue(V, FromBB, ToBB, CxtI); + const ValueLatticeElement *Result = getEdgeValue(V, FromBB, ToBB, CxtI); if (!Result) { solve(); Result = getEdgeValue(V, FromBB, ToBB, CxtI); Index: llvm/lib/Analysis/ValueLattice.cpp =================================================================== --- llvm/lib/Analysis/ValueLattice.cpp +++ llvm/lib/Analysis/ValueLattice.cpp @@ -30,4 +30,45 @@ << Val.getConstantRange().getUpper() << ">"; return OS << "constant<" << *Val.getConstant() << ">"; } + +ValueLatticePool::ValueLatticePool() { + Unknown = new (BPA.Allocate()) ValueLatticeElement(); + Overdefined = new (BPA.Allocate()) ValueLatticeElement( + ValueLatticeElement::getOverdefined()); +} + +const ValueLatticeElement *ValueLatticePool::getConstant(Constant *C) { + auto It = ConstantElems.find(C); + if (It != ConstantElems.end()) + return It->second; + + return getElement(ValueLatticeElement::get(C)); +} + +const ValueLatticeElement *ValueLatticePool::getNotConstant(Constant *C) { + return getElement(ValueLatticeElement::getNot(C)); +} + +const ValueLatticeElement * +ValueLatticePool::getRange(const ConstantRange &CR, bool MayIncludeUndef) { + return getElement(ValueLatticeElement::getRange(CR, MayIncludeUndef)); +} + +const ValueLatticeElement * +ValueLatticePool::getElement(const ValueLatticeElement &Elem) { + if (Elem.isUnknown()) + return Unknown; + if (Elem.isOverdefined()) + return Overdefined; + + auto It = Elems.find(&Elem); + if (It != Elems.end()) + return *It; + + const ValueLatticeElement *NewElem = + new (BPA.Allocate()) ValueLatticeElement(Elem); + Elems.insert(NewElem); + return NewElem; +} + } // end namespace llvm