diff options
Diffstat (limited to 'llvm/lib/Analysis/LazyValueInfo.cpp')
| -rw-r--r-- | llvm/lib/Analysis/LazyValueInfo.cpp | 315 |
1 files changed, 200 insertions, 115 deletions
diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp index 2fae260e0d8f..f1587cecf9fb 100644 --- a/llvm/lib/Analysis/LazyValueInfo.cpp +++ b/llvm/lib/Analysis/LazyValueInfo.cpp @@ -13,7 +13,6 @@ #include "llvm/Analysis/LazyValueInfo.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/ConstantFolding.h" @@ -38,6 +37,7 @@ #include "llvm/Support/FormattedStream.h" #include "llvm/Support/KnownBits.h" #include "llvm/Support/raw_ostream.h" +#include <optional> using namespace llvm; using namespace PatternMatch; @@ -164,7 +164,7 @@ namespace { SmallDenseSet<AssertingVH<Value>, 4> OverDefined; // None indicates that the nonnull pointers for this basic block // block have not been computed yet. - Optional<NonNullPointerSet> NonNullPointers; + std::optional<NonNullPointerSet> NonNullPointers; }; /// Cached information per basic block. @@ -210,18 +210,18 @@ namespace { addValueHandle(Val); } - Optional<ValueLatticeElement> getCachedValueInfo(Value *V, - BasicBlock *BB) const { + std::optional<ValueLatticeElement> + getCachedValueInfo(Value *V, BasicBlock *BB) const { const BlockCacheEntry *Entry = getBlockEntry(BB); if (!Entry) - return None; + return std::nullopt; if (Entry->OverDefined.count(V)) return ValueLatticeElement::getOverdefined(); auto LatticeIt = Entry->LatticeElements.find_as(V); if (LatticeIt == Entry->LatticeElements.end()) - return None; + return std::nullopt; return LatticeIt->second; } @@ -394,38 +394,40 @@ class LazyValueInfoImpl { /// if it exists in the module. Function *GuardDecl; - Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB, - Instruction *CxtI); - Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F, - BasicBlock *T, Instruction *CxtI = nullptr); + std::optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB, + Instruction *CxtI); + std::optional<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<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val, - BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN, - BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S, - BasicBlock *BB); - Optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI, - BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl( + std::optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, + BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val, + BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN, + BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S, + BasicBlock *BB); + std::optional<ConstantRange> getRangeFor(Value *V, Instruction *CxtI, + BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValueBinaryOpImpl( Instruction *I, BasicBlock *BB, - std::function<ConstantRange(const ConstantRange &, - const ConstantRange &)> OpFn); - Optional<ValueLatticeElement> solveBlockValueBinaryOp(BinaryOperator *BBI, - BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI, - BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic( - WithOverflowInst *WO, BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II, + std::function<ConstantRange(const ConstantRange &, const ConstantRange &)> + OpFn); + std::optional<ValueLatticeElement> + solveBlockValueBinaryOp(BinaryOperator *BBI, BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValueCast(CastInst *CI, BasicBlock *BB); - Optional<ValueLatticeElement> solveBlockValueExtractValue( - ExtractValueInst *EVI, BasicBlock *BB); + std::optional<ValueLatticeElement> + solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB); + std::optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II, + BasicBlock *BB); + std::optional<ValueLatticeElement> + solveBlockValueExtractValue(ExtractValueInst *EVI, BasicBlock *BB); bool isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, ValueLatticeElement &BBLV, @@ -516,7 +518,7 @@ void LazyValueInfoImpl::solve() { // The work item was completely processed. assert(BlockValueStack.back() == e && "Nothing should have been pushed!"); #ifndef NDEBUG - Optional<ValueLatticeElement> BBLV = + std::optional<ValueLatticeElement> BBLV = TheCache.getCachedValueInfo(e.second, e.first); assert(BBLV && "Result should be in cache!"); LLVM_DEBUG( @@ -533,13 +535,14 @@ void LazyValueInfoImpl::solve() { } } -Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue( - Value *Val, BasicBlock *BB, Instruction *CxtI) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::getBlockValue(Value *Val, BasicBlock *BB, + Instruction *CxtI) { // If already a constant, there is nothing to compute. if (Constant *VC = dyn_cast<Constant>(Val)) return ValueLatticeElement::get(VC); - if (Optional<ValueLatticeElement> OptLatticeVal = + if (std::optional<ValueLatticeElement> OptLatticeVal = TheCache.getCachedValueInfo(Val, BB)) { intersectAssumeOrGuardBlockValueConstantRange(Val, *OptLatticeVal, CxtI); return OptLatticeVal; @@ -550,7 +553,7 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue( return ValueLatticeElement::getOverdefined(); // Yet to be resolved. - return None; + return std::nullopt; } static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { @@ -577,7 +580,7 @@ bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { // Hold off inserting this value into the Cache in case we have to return // false and come back later. - Optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB); + std::optional<ValueLatticeElement> Res = solveBlockValueImpl(Val, BB); if (!Res) // Work pushed, will revisit return false; @@ -586,8 +589,8 @@ bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { return true; } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl( - Value *Val, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueImpl(Value *Val, BasicBlock *BB) { Instruction *BBI = dyn_cast<Instruction>(Val); if (!BBI || BBI->getParent() != BB) return solveBlockValueNonLocal(Val, BB); @@ -669,8 +672,8 @@ bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) { }); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( - Value *Val, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueNonLocal(Value *Val, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. // If this is the entry block, we must be asking about an argument. The @@ -690,10 +693,10 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( // canonicalizing to make this true rather than relying on this happy // accident. for (BasicBlock *Pred : predecessors(BB)) { - Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB); + std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, Pred, BB); if (!EdgeResult) // Explore that input, then return here - return None; + return std::nullopt; Result.mergeIn(*EdgeResult); @@ -701,7 +704,8 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( // to overdefined. if (Result.isOverdefined()) { LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() - << "' - overdefined because of pred (non local).\n"); + << "' - overdefined because of pred '" + << Pred->getName() << "' (non local).\n"); return Result; } } @@ -711,8 +715,8 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal( return Result; } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode( - PHINode *PN, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValuePHINode(PHINode *PN, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. // Loop over all of our predecessors, merging what we know from them into @@ -724,11 +728,11 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode( // 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<ValueLatticeElement> EdgeResult = + std::optional<ValueLatticeElement> EdgeResult = getEdgeValue(PhiVal, PhiBB, BB, PN); if (!EdgeResult) // Explore that input, then return here - return None; + return std::nullopt; Result.mergeIn(*EdgeResult); @@ -801,19 +805,19 @@ static ConstantRange getConstantRangeOrFull(const ValueLatticeElement &Val, return ConstantRange::getFull(DL.getTypeSizeInBits(Ty)); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect( - SelectInst *SI, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueSelect(SelectInst *SI, BasicBlock *BB) { // Recurse on our inputs if needed - Optional<ValueLatticeElement> OptTrueVal = + std::optional<ValueLatticeElement> OptTrueVal = getBlockValue(SI->getTrueValue(), BB, SI); if (!OptTrueVal) - return None; + return std::nullopt; ValueLatticeElement &TrueVal = *OptTrueVal; - Optional<ValueLatticeElement> OptFalseVal = + std::optional<ValueLatticeElement> OptFalseVal = getBlockValue(SI->getFalseValue(), BB, SI); if (!OptFalseVal) - return None; + return std::nullopt; ValueLatticeElement &FalseVal = *OptFalseVal; if (TrueVal.isConstantRange() || FalseVal.isConstantRange()) { @@ -882,17 +886,16 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect( return Result; } -Optional<ConstantRange> LazyValueInfoImpl::getRangeFor(Value *V, - Instruction *CxtI, - BasicBlock *BB) { - Optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI); +std::optional<ConstantRange> +LazyValueInfoImpl::getRangeFor(Value *V, Instruction *CxtI, BasicBlock *BB) { + std::optional<ValueLatticeElement> OptVal = getBlockValue(V, BB, CxtI); if (!OptVal) - return None; + return std::nullopt; return getConstantRangeOrFull(*OptVal, V->getType(), DL); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast( - CastInst *CI, BasicBlock *BB) { +std::optional<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()) @@ -917,11 +920,11 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast( // Figure out the range of the LHS. If that fails, we still apply the // transfer rule on the full set since we may be able to locally infer // interesting facts. - Optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB); + std::optional<ConstantRange> LHSRes = getRangeFor(CI->getOperand(0), CI, BB); if (!LHSRes) // More work to do before applying this transfer rule. - return None; - const ConstantRange &LHSRange = LHSRes.value(); + return std::nullopt; + const ConstantRange &LHSRange = *LHSRes; const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth(); @@ -932,27 +935,28 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast( ResultBitWidth)); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl( +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueBinaryOpImpl( Instruction *I, BasicBlock *BB, - std::function<ConstantRange(const ConstantRange &, - const ConstantRange &)> OpFn) { + std::function<ConstantRange(const ConstantRange &, const ConstantRange &)> + OpFn) { // Figure out the ranges of the operands. If that fails, use a // conservative range, but apply the transfer rule anyways. This // lets us pick up facts from expressions like "and i32 (call i32 // @foo()), 32" - Optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB); - Optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB); + std::optional<ConstantRange> LHSRes = getRangeFor(I->getOperand(0), I, BB); + std::optional<ConstantRange> RHSRes = getRangeFor(I->getOperand(1), I, BB); if (!LHSRes || !RHSRes) // More work to do before applying this transfer rule. - return None; + return std::nullopt; - const ConstantRange &LHSRange = LHSRes.value(); - const ConstantRange &RHSRange = RHSRes.value(); + const ConstantRange &LHSRange = *LHSRes; + const ConstantRange &RHSRange = *RHSRes; return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp( - BinaryOperator *BO, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueBinaryOp(BinaryOperator *BO, BasicBlock *BB) { assert(BO->getOperand(0)->getType()->isSized() && "all operands to binary operators are sized"); if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BO)) { @@ -975,7 +979,7 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp( }); } -Optional<ValueLatticeElement> +std::optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, BasicBlock *BB) { return solveBlockValueBinaryOpImpl( @@ -984,8 +988,8 @@ LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, }); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic( - IntrinsicInst *II, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueIntrinsic(IntrinsicInst *II, BasicBlock *BB) { if (!ConstantRange::isIntrinsicSupported(II->getIntrinsicID())) { LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - unknown intrinsic.\n"); @@ -994,9 +998,9 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic( SmallVector<ConstantRange, 2> OpRanges; for (Value *Op : II->args()) { - Optional<ConstantRange> Range = getRangeFor(Op, II, BB); + std::optional<ConstantRange> Range = getRangeFor(Op, II, BB); if (!Range) - return None; + return std::nullopt; OpRanges.push_back(*Range); } @@ -1004,8 +1008,9 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic( ConstantRange::intrinsic(II->getIntrinsicID(), OpRanges)); } -Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueExtractValue( - ExtractValueInst *EVI, BasicBlock *BB) { +std::optional<ValueLatticeElement> +LazyValueInfoImpl::solveBlockValueExtractValue(ExtractValueInst *EVI, + BasicBlock *BB) { if (auto *WO = dyn_cast<WithOverflowInst>(EVI->getAggregateOperand())) if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0) return solveBlockValueOverflowIntrinsic(WO, BB); @@ -1161,11 +1166,16 @@ static ValueLatticeElement getValueFromOverflowCondition( return ValueLatticeElement::getRange(NWR); } -static Optional<ValueLatticeElement> -getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, - bool isRevisit, - SmallDenseMap<Value *, ValueLatticeElement> &Visited, - SmallVectorImpl<Value *> &Worklist) { +// Tracks a Value * condition and whether we're interested in it or its inverse +typedef PointerIntPair<Value *, 1, bool> CondValue; + +static std::optional<ValueLatticeElement> getValueFromConditionImpl( + Value *Val, CondValue CondVal, bool isRevisit, + SmallDenseMap<CondValue, ValueLatticeElement> &Visited, + SmallVectorImpl<CondValue> &Worklist) { + + Value *Cond = CondVal.getPointer(); + bool isTrueDest = CondVal.getInt(); if (!isRevisit) { if (ICmpInst *ICI = dyn_cast<ICmpInst>(Cond)) return getValueFromICmpCondition(Val, ICI, isTrueDest); @@ -1176,6 +1186,17 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, return getValueFromOverflowCondition(Val, WO, isTrueDest); } + Value *N; + if (match(Cond, m_Not(m_Value(N)))) { + CondValue NKey(N, !isTrueDest); + auto NV = Visited.find(NKey); + if (NV == Visited.end()) { + Worklist.push_back(NKey); + return std::nullopt; + } + return NV->second; + } + Value *L, *R; bool IsAnd; if (match(Cond, m_LogicalAnd(m_Value(L), m_Value(R)))) @@ -1185,13 +1206,13 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, else return ValueLatticeElement::getOverdefined(); - auto LV = Visited.find(L); - auto RV = Visited.find(R); + auto LV = Visited.find(CondValue(L, isTrueDest)); + auto RV = Visited.find(CondValue(R, isTrueDest)); // if (L && R) -> intersect L and R - // if (!(L || R)) -> intersect L and R + // if (!(L || R)) -> intersect !L and !R // if (L || R) -> union L and R - // if (!(L && R)) -> union L and R + // if (!(L && R)) -> union !L and !R if ((isTrueDest ^ IsAnd) && (LV != Visited.end())) { ValueLatticeElement V = LV->second; if (V.isOverdefined()) @@ -1205,10 +1226,10 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, if (LV == Visited.end() || RV == Visited.end()) { assert(!isRevisit); if (LV == Visited.end()) - Worklist.push_back(L); + Worklist.push_back(CondValue(L, isTrueDest)); if (RV == Visited.end()) - Worklist.push_back(R); - return None; + Worklist.push_back(CondValue(R, isTrueDest)); + return std::nullopt; } return intersect(LV->second, RV->second); @@ -1217,12 +1238,13 @@ getValueFromConditionImpl(Value *Val, Value *Cond, bool isTrueDest, ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) { assert(Cond && "precondition"); - SmallDenseMap<Value*, ValueLatticeElement> Visited; - SmallVector<Value *> Worklist; + SmallDenseMap<CondValue, ValueLatticeElement> Visited; + SmallVector<CondValue> Worklist; - Worklist.push_back(Cond); + CondValue CondKey(Cond, isTrueDest); + Worklist.push_back(CondKey); do { - Value *CurrentCond = Worklist.back(); + CondValue CurrentCond = Worklist.back(); // Insert an Overdefined placeholder into the set to prevent // infinite recursion if there exists IRs that use not // dominated by its def as in this example: @@ -1231,15 +1253,15 @@ ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, auto Iter = Visited.try_emplace(CurrentCond, ValueLatticeElement::getOverdefined()); bool isRevisit = !Iter.second; - Optional<ValueLatticeElement> Result = getValueFromConditionImpl( - Val, CurrentCond, isTrueDest, isRevisit, Visited, Worklist); + std::optional<ValueLatticeElement> Result = getValueFromConditionImpl( + Val, CurrentCond, isRevisit, Visited, Worklist); if (Result) { Visited[CurrentCond] = *Result; Worklist.pop_back(); } } while (!Worklist.empty()); - auto Result = Visited.find(Cond); + auto Result = Visited.find(CondKey); assert(Result != Visited.end()); return Result->second; } @@ -1295,7 +1317,7 @@ static ValueLatticeElement constantFoldUser(User *Usr, Value *Op, /// Compute the value of Val on the edge BBFrom -> BBTo. Returns false if /// Val is not constrained on the edge. Result is unspecified if return value /// is false. -static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, +static std::optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we @@ -1352,7 +1374,8 @@ static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, Value *Op = Usr->getOperand(i); ValueLatticeElement OpLatticeVal = getValueFromCondition(Op, Condition, isTrueDest); - if (Optional<APInt> OpConst = OpLatticeVal.asConstantInteger()) { + if (std::optional<APInt> OpConst = + OpLatticeVal.asConstantInteger()) { Result = constantFoldUser(Usr, Op, *OpConst, DL); break; } @@ -1370,7 +1393,7 @@ static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) { Value *Condition = SI->getCondition(); if (!isa<IntegerType>(Val->getType())) - return None; + return std::nullopt; bool ValUsesConditionAndMayBeFoldable = false; if (Condition != Val) { // Check if Val has Condition as an operand. @@ -1378,7 +1401,7 @@ static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) && usesOperand(Usr, Condition); if (!ValUsesConditionAndMayBeFoldable) - return None; + return std::nullopt; } assert((Condition == Val || ValUsesConditionAndMayBeFoldable) && "Condition != Val nor Val doesn't use Condition"); @@ -1396,7 +1419,7 @@ static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, ValueLatticeElement EdgeLatticeVal = constantFoldUser(Usr, Condition, CaseValue, DL); if (EdgeLatticeVal.isOverdefined()) - return None; + return std::nullopt; EdgeVal = EdgeLatticeVal.getConstantRange(); } if (DefaultCase) { @@ -1413,13 +1436,14 @@ static Optional<ValueLatticeElement> getEdgeValueLocal(Value *Val, } return ValueLatticeElement::getRange(std::move(EdgesVals)); } - return None; + return std::nullopt; } /// 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<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue( - Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) { +std::optional<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<Constant>(Val)) return ValueLatticeElement::get(VC); @@ -1431,10 +1455,10 @@ Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue( // Can't get any more precise here return LocalResult; - Optional<ValueLatticeElement> OptInBlock = + std::optional<ValueLatticeElement> OptInBlock = getBlockValue(Val, BBFrom, BBFrom->getTerminator()); if (!OptInBlock) - return None; + return std::nullopt; ValueLatticeElement &InBlock = *OptInBlock; // We can use the context instruction (generically the ultimate instruction @@ -1456,7 +1480,7 @@ ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); - Optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI); + std::optional<ValueLatticeElement> OptResult = getBlockValue(V, BB, CxtI); if (!OptResult) { solve(); OptResult = getBlockValue(V, BB, CxtI); @@ -1491,7 +1515,8 @@ getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB, << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); - Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI); + std::optional<ValueLatticeElement> Result = + getEdgeValue(V, FromBB, ToBB, CxtI); if (!Result) { solve(); Result = getEdgeValue(V, FromBB, ToBB, CxtI); @@ -1625,6 +1650,48 @@ ConstantRange LazyValueInfo::getConstantRange(Value *V, Instruction *CxtI, return ConstantRange::getFull(Width); } +ConstantRange LazyValueInfo::getConstantRangeAtUse(const Use &U, + bool UndefAllowed) { + Value *V = U.get(); + ConstantRange CR = + getConstantRange(V, cast<Instruction>(U.getUser()), UndefAllowed); + + // Check whether the only (possibly transitive) use of the value is in a + // position where V can be constrained by a select or branch condition. + const Use *CurrU = &U; + // TODO: Increase limit? + const unsigned MaxUsesToInspect = 3; + for (unsigned I = 0; I < MaxUsesToInspect; ++I) { + std::optional<ValueLatticeElement> CondVal; + auto *CurrI = cast<Instruction>(CurrU->getUser()); + if (auto *SI = dyn_cast<SelectInst>(CurrI)) { + if (CurrU->getOperandNo() == 1) + CondVal = getValueFromCondition(V, SI->getCondition(), true); + else if (CurrU->getOperandNo() == 2) + CondVal = getValueFromCondition(V, SI->getCondition(), false); + } else if (auto *PHI = dyn_cast<PHINode>(CurrI)) { + // TODO: Use non-local query? + CondVal = + getEdgeValueLocal(V, PHI->getIncomingBlock(*CurrU), PHI->getParent()); + } else if (!isSafeToSpeculativelyExecute(CurrI)) { + // Stop walking if we hit a non-speculatable instruction. Even if the + // result is only used under a specific condition, executing the + // instruction itself may cause side effects or UB already. + break; + } + if (CondVal && CondVal->isConstantRange()) + CR = CR.intersectWith(CondVal->getConstantRange()); + + // Only follow one-use chain, to allow direct intersection of conditions. + // If there are multiple uses, we would have to intersect with the union of + // all conditions at different uses. + if (!CurrI->hasOneUse()) + break; + CurrU = &*CurrI->use_begin(); + } + return CR; +} + /// Determine whether the specified value is known to be a /// constant on the specified edge. Return null if not. Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB, @@ -1859,9 +1926,27 @@ LazyValueInfo::Tristate LazyValueInfo::getPredicateAt(unsigned P, Value *LHS, return getPredicateAt(CmpInst::getSwappedPredicate(Pred), RHS, C, CxtI, UseBlockValue); - // Got two non-Constant values. While we could handle them somewhat, - // by getting their constant ranges, and applying ConstantRange::icmp(), - // so far it did not appear to be profitable. + // Got two non-Constant values. Try to determine the comparison results based + // on the block values of the two operands, e.g. because they have + // non-overlapping ranges. + if (UseBlockValue) { + Module *M = CxtI->getModule(); + ValueLatticeElement L = + getImpl(PImpl, AC, M).getValueInBlock(LHS, CxtI->getParent(), CxtI); + if (L.isOverdefined()) + return LazyValueInfo::Unknown; + + ValueLatticeElement R = + getImpl(PImpl, AC, M).getValueInBlock(RHS, CxtI->getParent(), CxtI); + Type *Ty = CmpInst::makeCmpResultType(LHS->getType()); + if (Constant *Res = L.getCompare((CmpInst::Predicate)P, Ty, R, + M->getDataLayout())) { + if (Res->isNullValue()) + return LazyValueInfo::False; + if (Res->isOneValue()) + return LazyValueInfo::True; + } + } return LazyValueInfo::Unknown; } |