Index: lib/Analysis/LazyValueInfo.cpp =================================================================== --- lib/Analysis/LazyValueInfo.cpp +++ lib/Analysis/LazyValueInfo.cpp @@ -211,21 +211,18 @@ return ODI->second.count(V); } - bool getCachedValueInfo(ValueLatticeElement &BBLV, Value *V, - BasicBlock *BB) const { - if (isOverdefined(V, BB)) { - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } + Optional getCachedValueInfo(Value *V, + BasicBlock *BB) const { + if (isOverdefined(V, BB)) + return ValueLatticeElement::getOverdefined(); auto I = ValueCache.find_as(V); if (I == ValueCache.end()) - return false; + return None; auto BBI = I->second->BlockVals.find(BB); if (BBI == I->second->BlockVals.end()) - return false; - BBLV = BBI->second; - return true; + return None; + return BBI->second; } /// clear - Empty the cache. @@ -402,40 +399,39 @@ DominatorTree *DT; ///< An optional DT pointer. DominatorTree *DisabledDT; ///< Stores DT if it's disabled. - bool getBlockValue(ValueLatticeElement &Result, Value *Val, BasicBlock *BB); - bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T, - ValueLatticeElement &Result, Instruction *CxtI = nullptr); + Optional getBlockValue(Value *Val, BasicBlock *BB); + Optional 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); - bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val, - BasicBlock *BB); - bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val, - BasicBlock *BB); - bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN, - BasicBlock *BB); - bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S, - 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); Optional getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB); - bool solveBlockValueBinaryOpImpl( - ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB, + Optional solveBlockValueBinaryOpImpl( + Instruction *I, BasicBlock *BB, std::function OpFn); - bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI, - BasicBlock *BB); - bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI, - BasicBlock *BB); - bool solveBlockValueOverflowIntrinsic( - ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB); - bool solveBlockValueSaturatingIntrinsic(ValueLatticeElement &BBLV, - SaturatingInst *SI, BasicBlock *BB); - bool solveBlockValueIntrinsic(ValueLatticeElement &BBLV, IntrinsicInst *II, - BasicBlock *BB); - bool solveBlockValueExtractValue(ValueLatticeElement &BBLV, - ExtractValueInst *EVI, BasicBlock *BB); + Optional solveBlockValueBinaryOp(BinaryOperator *BBI, + BasicBlock *BB); + Optional solveBlockValueCast(CastInst *CI, + BasicBlock *BB); + Optional solveBlockValueOverflowIntrinsic( + WithOverflowInst *WO, BasicBlock *BB); + Optional solveBlockValueSaturatingIntrinsic( + SaturatingInst *SI, BasicBlock *BB); + Optional solveBlockValueIntrinsic(IntrinsicInst *II, + BasicBlock *BB); + Optional solveBlockValueExtractValue( + ExtractValueInst *EVI, BasicBlock *BB); void intersectAssumeOrGuardBlockValueConstantRange(Value *Val, ValueLatticeElement &BBLV, Instruction *BBI); @@ -540,12 +536,12 @@ // The work item was completely processed. assert(BlockValueStack.back() == e && "Nothing should have been pushed!"); #ifndef NDEBUG - ValueLatticeElement BBLV; - assert(TheCache.getCachedValueInfo(BBLV, e.second, e.first) && - "Result should be in cache!"); + Optional BBLV = + TheCache.getCachedValueInfo(e.second, e.first); + assert(BBLV && "Result should be in cache!"); LLVM_DEBUG( dbgs() << "POP " << *e.second << " in " << e.first->getName() << " = " - << BBLV << "\n"); + << *BBLV << "\n"); #endif BlockValueStack.pop_back(); @@ -557,25 +553,22 @@ } } -bool LazyValueInfoImpl::getBlockValue(ValueLatticeElement &BBLV, - Value *Val, BasicBlock *BB) { +Optional LazyValueInfoImpl::getBlockValue(Value *Val, + BasicBlock *BB) { // If already a constant, there is nothing to compute. - if (Constant *VC = dyn_cast(Val)) { - BBLV = ValueLatticeElement::get(VC); - return true; - } + if (Constant *VC = dyn_cast(Val)) + return ValueLatticeElement::get(VC); - if (TheCache.getCachedValueInfo(BBLV, Val, BB)) - return true; + if (Optional OptLatticeVal = + TheCache.getCachedValueInfo(Val, BB)) + return OptLatticeVal; // We have hit a cycle, assume overdefined. - if (!pushBlockValue({ BB, Val })) { - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } + if (!pushBlockValue({ BB, Val })) + return ValueLatticeElement::getOverdefined(); // Yet to be resolved. - return false; + return None; } static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) { @@ -596,36 +589,32 @@ } bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) { -#ifndef NDEBUG - ValueLatticeElement BBLV; assert(!isa(Val) && "Value should not be constant"); - assert(!TheCache.getCachedValueInfo(BBLV, Val, BB) && + assert(!TheCache.getCachedValueInfo(Val, BB) && "Value should not be in cache"); -#endif // Hold off inserting this value into the Cache in case we have to return // false and come back later. - ValueLatticeElement Res; - if (!solveBlockValueImpl(Res, Val, BB)) + Optional Res = solveBlockValueImpl(Val, BB); + if (!Res) // Work pushed, will revisit return false; - TheCache.insertResult(Val, BB, Res); + TheCache.insertResult(Val, BB, *Res); return true; } -bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res, - Value *Val, BasicBlock *BB) { - +Optional LazyValueInfoImpl::solveBlockValueImpl( + Value *Val, BasicBlock *BB) { Instruction *BBI = dyn_cast(Val); if (!BBI || BBI->getParent() != BB) - return solveBlockValueNonLocal(Res, Val, BB); + return solveBlockValueNonLocal(Val, BB); if (PHINode *PN = dyn_cast(BBI)) - return solveBlockValuePHINode(Res, PN, BB); + return solveBlockValuePHINode(PN, BB); if (auto *SI = dyn_cast(BBI)) - return solveBlockValueSelect(Res, SI, BB); + return solveBlockValueSelect(SI, BB); // If this value is a nonnull pointer, record it's range and bailout. Note // that for all other pointer typed values, we terminate the search at the @@ -637,28 +626,26 @@ // instruction is placed, even if it could legally be hoisted much higher. // That is unfortunate. PointerType *PT = dyn_cast(BBI->getType()); - if (PT && isKnownNonZero(BBI, DL)) { - Res = ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); - return true; - } + if (PT && isKnownNonZero(BBI, DL)) + return ValueLatticeElement::getNot(ConstantPointerNull::get(PT)); + if (BBI->getType()->isIntegerTy()) { if (auto *CI = dyn_cast(BBI)) - return solveBlockValueCast(Res, CI, BB); + return solveBlockValueCast(CI, BB); if (BinaryOperator *BO = dyn_cast(BBI)) - return solveBlockValueBinaryOp(Res, BO, BB); + return solveBlockValueBinaryOp(BO, BB); if (auto *EVI = dyn_cast(BBI)) - return solveBlockValueExtractValue(Res, EVI, BB); + return solveBlockValueExtractValue(EVI, BB); if (auto *II = dyn_cast(BBI)) - return solveBlockValueIntrinsic(Res, II, BB); + return solveBlockValueIntrinsic(II, BB); } LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - unknown inst def found.\n"); - Res = getFromRangeMetadata(BBI); - return true; + return getFromRangeMetadata(BBI); } static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) { @@ -710,8 +697,8 @@ return false; } -bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV, - Value *Val, BasicBlock *BB) { +Optional LazyValueInfoImpl::solveBlockValueNonLocal( + Value *Val, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. // If this is the entry block, we must be asking about an argument. The @@ -724,13 +711,10 @@ if (PTy && (isKnownNonZero(Val, DL) || (isObjectDereferencedInBlock(Val, BB) && - !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) { - Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); - } else { - Result = ValueLatticeElement::getOverdefined(); - } - BBLV = Result; - return true; + !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())))) + return ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); + else + return ValueLatticeElement::getOverdefined(); } // Loop over all of our predecessors, merging what we know from them into @@ -743,12 +727,12 @@ // 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) { - ValueLatticeElement EdgeResult; - if (!getEdgeValue(Val, *PI, BB, EdgeResult)) + Optional EdgeResult = getEdgeValue(Val, *PI, BB); + if (!EdgeResult) // Explore that input, then return here - return false; + return None; - Result.mergeIn(EdgeResult); + Result.mergeIn(*EdgeResult); // If we hit overdefined, exit early. The BlockVals entry is already set // to overdefined. @@ -763,19 +747,17 @@ Result = ValueLatticeElement::getNot(ConstantPointerNull::get(PTy)); } - BBLV = Result; - return true; + return Result; } } // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined()); - BBLV = Result; - return true; + return Result; } -bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV, - PHINode *PN, BasicBlock *BB) { +Optional LazyValueInfoImpl::solveBlockValuePHINode( + PHINode *PN, BasicBlock *BB) { ValueLatticeElement Result; // Start Undefined. // Loop over all of our predecessors, merging what we know from them into @@ -784,15 +766,16 @@ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { BasicBlock *PhiBB = PN->getIncomingBlock(i); Value *PhiVal = PN->getIncomingValue(i); - ValueLatticeElement EdgeResult; // 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. - if (!getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN)) + Optional EdgeResult = + getEdgeValue(PhiVal, PhiBB, BB, PN); + if (!EdgeResult) // Explore that input, then return here - return false; + return None; - Result.mergeIn(EdgeResult); + Result.mergeIn(*EdgeResult); // If we hit overdefined, exit early. The BlockVals entry is already set // to overdefined. @@ -800,15 +783,13 @@ LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined because of pred (local).\n"); - BBLV = Result; - return true; + return Result; } } // Return the merged value, which is more precise than 'overdefined'. assert(!Result.isOverdefined() && "Possible PHI in entry block?"); - BBLV = Result; - return true; + return Result; } static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond, @@ -848,31 +829,30 @@ } } -bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV, - SelectInst *SI, BasicBlock *BB) { - +Optional LazyValueInfoImpl::solveBlockValueSelect( + SelectInst *SI, BasicBlock *BB) { // Recurse on our inputs if needed - ValueLatticeElement TrueVal; - if (!getBlockValue(TrueVal, SI->getTrueValue(), BB)) - return false; + Optional OptTrueVal = + getBlockValue(SI->getTrueValue(), BB); + if (!OptTrueVal) + return None; + ValueLatticeElement TrueVal = *OptTrueVal; // 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()) { - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } + if (TrueVal.isOverdefined()) + return ValueLatticeElement::getOverdefined(); - ValueLatticeElement FalseVal; - if (!getBlockValue(FalseVal, SI->getFalseValue(), BB)) - return false; + Optional OptFalseVal = + getBlockValue(SI->getFalseValue(), BB); + if (!OptFalseVal) + return None; + ValueLatticeElement FalseVal = *OptFalseVal; // 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()) { - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } + if (FalseVal.isOverdefined()) + return ValueLatticeElement::getOverdefined(); if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) { const ConstantRange &TrueCR = TrueVal.getConstantRange(); @@ -898,37 +878,28 @@ return TrueCR.umax(FalseCR); }; }(); - BBLV = ValueLatticeElement::getRange( + return ValueLatticeElement::getRange( ResultCR, TrueVal.isConstantRangeIncludingUndef() | FalseVal.isConstantRangeIncludingUndef()); - return true; } if (SPR.Flavor == SPF_ABS) { - if (LHS == SI->getTrueValue()) { - BBLV = ValueLatticeElement::getRange( + if (LHS == SI->getTrueValue()) + return ValueLatticeElement::getRange( TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef()); - return true; - } - if (LHS == SI->getFalseValue()) { - BBLV = ValueLatticeElement::getRange( + if (LHS == SI->getFalseValue()) + return ValueLatticeElement::getRange( FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef()); - return true; - } } if (SPR.Flavor == SPF_NABS) { ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth())); - if (LHS == SI->getTrueValue()) { - BBLV = ValueLatticeElement::getRange( + if (LHS == SI->getTrueValue()) + return ValueLatticeElement::getRange( Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef()); - return true; - } - if (LHS == SI->getFalseValue()) { - BBLV = ValueLatticeElement::getRange( + if (LHS == SI->getFalseValue()) + return ValueLatticeElement::getRange( Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef()); - return true; - } } } @@ -986,17 +957,17 @@ ValueLatticeElement Result; // Start Undefined. Result.mergeIn(TrueVal); Result.mergeIn(FalseVal); - BBLV = Result; - return true; + return Result; } Optional LazyValueInfoImpl::getRangeForOperand(unsigned Op, Instruction *I, BasicBlock *BB) { - ValueLatticeElement Val; - if (!getBlockValue(Val, I->getOperand(Op), BB)) + Optional OptVal = getBlockValue(I->getOperand(Op), BB); + if (!OptVal) return None; + ValueLatticeElement Val = *OptVal; intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I); if (Val.isConstantRange()) return Val.getConstantRange(); @@ -1006,15 +977,12 @@ return ConstantRange::getFull(OperandBitWidth); } -bool LazyValueInfoImpl::solveBlockValueCast(ValueLatticeElement &BBLV, - CastInst *CI, - BasicBlock *BB) { - if (!CI->getOperand(0)->getType()->isSized()) { - // Without knowing how wide the input is, we can't analyze it in any useful - // way. - BBLV = ValueLatticeElement::getOverdefined(); - return true; - } +Optional 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(); // 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 @@ -1029,8 +997,7 @@ // Unhandled instructions are overdefined. LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown cast).\n"); - BBLV = ValueLatticeElement::getOverdefined(); - return true; + return ValueLatticeElement::getOverdefined(); } // Figure out the range of the LHS. If that fails, we still apply the @@ -1039,21 +1006,20 @@ Optional LHSRes = getRangeForOperand(0, CI, BB); if (!LHSRes.hasValue()) // More work to do before applying this transfer rule. - return false; - ConstantRange LHSRange = LHSRes.getValue(); + return None; + 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. - BBLV = ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), + return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(), ResultBitWidth)); - return true; } -bool LazyValueInfoImpl::solveBlockValueBinaryOpImpl( - ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB, +Optional LazyValueInfoImpl::solveBlockValueBinaryOpImpl( + Instruction *I, BasicBlock *BB, std::function OpFn) { // Figure out the ranges of the operands. If that fails, use a @@ -1064,26 +1030,22 @@ Optional RHSRes = getRangeForOperand(1, I, BB); if (!LHSRes.hasValue() || !RHSRes.hasValue()) // More work to do before applying this transfer rule. - return false; + return None; - ConstantRange LHSRange = LHSRes.getValue(); - ConstantRange RHSRange = RHSRes.getValue(); - BBLV = ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); - return true; + const ConstantRange &LHSRange = LHSRes.getValue(); + const ConstantRange &RHSRange = RHSRes.getValue(); + return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange)); } -bool LazyValueInfoImpl::solveBlockValueBinaryOp(ValueLatticeElement &BBLV, - BinaryOperator *BO, - BasicBlock *BB) { - +Optional LazyValueInfoImpl::solveBlockValueBinaryOp( + BinaryOperator *BO, BasicBlock *BB) { assert(BO->getOperand(0)->getType()->isSized() && "all operands to binary operators are sized"); if (BO->getOpcode() == Instruction::Xor) { // Xor is the only operation not supported by ConstantRange::binaryOp(). LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown binary operator).\n"); - BBLV = ValueLatticeElement::getOverdefined(); - return true; + return ValueLatticeElement::getOverdefined(); } if (auto *OBO = dyn_cast(BO)) { @@ -1094,47 +1056,49 @@ NoWrapKind |= OverflowingBinaryOperator::NoSignedWrap; return solveBlockValueBinaryOpImpl( - BBLV, BO, BB, + BO, BB, [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind); }); } return solveBlockValueBinaryOpImpl( - BBLV, BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { + BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.binaryOp(BO->getOpcode(), CR2); }); } -bool LazyValueInfoImpl::solveBlockValueOverflowIntrinsic( - ValueLatticeElement &BBLV, WithOverflowInst *WO, BasicBlock *BB) { - return solveBlockValueBinaryOpImpl(BBLV, WO, BB, - [WO](const ConstantRange &CR1, const ConstantRange &CR2) { +Optional +LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO, + BasicBlock *BB) { + return solveBlockValueBinaryOpImpl( + WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.binaryOp(WO->getBinaryOp(), CR2); }); } -bool LazyValueInfoImpl::solveBlockValueSaturatingIntrinsic( - ValueLatticeElement &BBLV, SaturatingInst *SI, BasicBlock *BB) { +Optional +LazyValueInfoImpl::solveBlockValueSaturatingIntrinsic(SaturatingInst *SI, + BasicBlock *BB) { switch (SI->getIntrinsicID()) { case Intrinsic::uadd_sat: return solveBlockValueBinaryOpImpl( - BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { + SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.uadd_sat(CR2); }); case Intrinsic::usub_sat: return solveBlockValueBinaryOpImpl( - BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { + SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.usub_sat(CR2); }); case Intrinsic::sadd_sat: return solveBlockValueBinaryOpImpl( - BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { + SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.sadd_sat(CR2); }); case Intrinsic::ssub_sat: return solveBlockValueBinaryOpImpl( - BBLV, SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { + SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) { return CR1.ssub_sat(CR2); }); default: @@ -1142,35 +1106,32 @@ } } -bool LazyValueInfoImpl::solveBlockValueIntrinsic(ValueLatticeElement &BBLV, - IntrinsicInst *II, - BasicBlock *BB) { +Optional LazyValueInfoImpl::solveBlockValueIntrinsic( + IntrinsicInst *II, BasicBlock *BB) { if (auto *SI = dyn_cast(II)) - return solveBlockValueSaturatingIntrinsic(BBLV, SI, BB); + return solveBlockValueSaturatingIntrinsic(SI, BB); LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown intrinsic).\n"); - BBLV = ValueLatticeElement::getOverdefined(); - return true; + return ValueLatticeElement::getOverdefined(); } -bool LazyValueInfoImpl::solveBlockValueExtractValue( - ValueLatticeElement &BBLV, ExtractValueInst *EVI, BasicBlock *BB) { +Optional LazyValueInfoImpl::solveBlockValueExtractValue( + ExtractValueInst *EVI, BasicBlock *BB) { if (auto *WO = dyn_cast(EVI->getAggregateOperand())) if (EVI->getNumIndices() == 1 && *EVI->idx_begin() == 0) - return solveBlockValueOverflowIntrinsic(BBLV, WO, BB); + return solveBlockValueOverflowIntrinsic(WO, BB); // Handle extractvalue of insertvalue to allow further simplification // based on replaced with.overflow intrinsics. if (Value *V = SimplifyExtractValueInst( EVI->getAggregateOperand(), EVI->getIndices(), EVI->getModule()->getDataLayout())) - return getBlockValue(BBLV, V, BB); + return getBlockValue(V, BB); LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName() << "' - overdefined (unknown extractvalue).\n"); - BBLV = ValueLatticeElement::getOverdefined(); - return true; + return ValueLatticeElement::getOverdefined(); } static ValueLatticeElement getValueFromICmpCondition(Value *Val, ICmpInst *ICI, @@ -1362,8 +1323,9 @@ /// 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 bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, ValueLatticeElement &Result) { +static Optional getEdgeValueLocal(Value *Val, + BasicBlock *BBFrom, + BasicBlock *BBTo) { // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we // know that v != 0. if (BranchInst *BI = dyn_cast(BBFrom->getTerminator())) { @@ -1378,17 +1340,16 @@ // If V is the condition of the branch itself, then we know exactly what // it is. - if (Condition == Val) { - Result = ValueLatticeElement::get(ConstantInt::get( + if (Condition == Val) + return ValueLatticeElement::get(ConstantInt::get( Type::getInt1Ty(Val->getContext()), isTrueDest)); - 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); + ValueLatticeElement Result = getValueFromCondition(Val, Condition, + isTrueDest); if (!Result.isOverdefined()) - return true; + return Result; if (User *Usr = dyn_cast(Val)) { assert(Result.isOverdefined() && "Result isn't overdefined"); @@ -1428,7 +1389,7 @@ } } if (!Result.isOverdefined()) - return true; + return Result; } } @@ -1437,7 +1398,7 @@ if (SwitchInst *SI = dyn_cast(BBFrom->getTerminator())) { Value *Condition = SI->getCondition(); if (!isa(Val->getType())) - return false; + return None; bool ValUsesConditionAndMayBeFoldable = false; if (Condition != Val) { // Check if Val has Condition as an operand. @@ -1445,7 +1406,7 @@ ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) && usesOperand(Usr, Condition); if (!ValUsesConditionAndMayBeFoldable) - return false; + return None; } assert((Condition == Val || ValUsesConditionAndMayBeFoldable) && "Condition != Val nor Val doesn't use Condition"); @@ -1463,7 +1424,7 @@ ValueLatticeElement EdgeLatticeVal = constantFoldUser(Usr, Condition, CaseValue, DL); if (EdgeLatticeVal.isOverdefined()) - return false; + return None; EdgeVal = EdgeLatticeVal.getConstantRange(); } if (DefaultCase) { @@ -1478,39 +1439,29 @@ } else if (Case.getCaseSuccessor() == BBTo) EdgesVals = EdgesVals.unionWith(EdgeVal); } - Result = ValueLatticeElement::getRange(std::move(EdgesVals)); - return true; + return ValueLatticeElement::getRange(std::move(EdgesVals)); } - return false; + return None; } /// Compute the value of Val on the edge BBFrom -> BBTo or the value at /// the basic block if the edge does not constrain Val. -bool LazyValueInfoImpl::getEdgeValue(Value *Val, BasicBlock *BBFrom, - BasicBlock *BBTo, - ValueLatticeElement &Result, - Instruction *CxtI) { +Optional 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)) { - Result = ValueLatticeElement::get(VC); - return true; - } + if (Constant *VC = dyn_cast(Val)) + return ValueLatticeElement::get(VC); - ValueLatticeElement LocalResult; - if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult)) - // If we couldn't constrain the value on the edge, LocalResult doesn't - // provide any information. - LocalResult = ValueLatticeElement::getOverdefined(); - - if (hasSingleValue(LocalResult)) { + ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo) + .getValueOr(ValueLatticeElement::getOverdefined()); + if (hasSingleValue(LocalResult)) // Can't get any more precise here - Result = LocalResult; - return true; - } + return LocalResult; - ValueLatticeElement InBlock; - if (!getBlockValue(InBlock, Val, BBFrom)) - return false; + Optional OptInBlock = getBlockValue(Val, BBFrom); + if (!OptInBlock) + return None; + ValueLatticeElement InBlock = *OptInBlock; // Try to intersect ranges of the BB and the constraint on the edge. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, @@ -1525,8 +1476,7 @@ // but then the result is not cached. intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock, CxtI); - Result = intersect(LocalResult, InBlock); - return true; + return intersect(LocalResult, InBlock); } ValueLatticeElement LazyValueInfoImpl::getValueInBlock(Value *V, BasicBlock *BB, @@ -1535,13 +1485,13 @@ << BB->getName() << "'\n"); assert(BlockValueStack.empty() && BlockValueSet.empty()); - ValueLatticeElement Result; - if (!getBlockValue(Result, V, BB)) { + Optional OptResult = getBlockValue(V, BB); + if (!OptResult) { solve(); - bool ValueAvailable = getBlockValue(Result, V, BB); - (void) ValueAvailable; - assert(ValueAvailable && "Value not available after solving"); + OptResult = getBlockValue(V, BB); + assert(OptResult && "Value not available after solving"); } + ValueLatticeElement Result = *OptResult; intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI); LLVM_DEBUG(dbgs() << " Result = " << Result << "\n"); @@ -1571,16 +1521,15 @@ << FromBB->getName() << "' to '" << ToBB->getName() << "'\n"); - ValueLatticeElement Result; - if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) { + Optional Result = getEdgeValue(V, FromBB, ToBB, CxtI); + if (!Result) { solve(); - bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI); - (void)WasFastQuery; - assert(WasFastQuery && "More work to do after problem solved?"); + Result = getEdgeValue(V, FromBB, ToBB, CxtI); + assert(Result && "More work to do after problem solved?"); } - LLVM_DEBUG(dbgs() << " Result = " << Result << "\n"); - return Result; + LLVM_DEBUG(dbgs() << " Result = " << *Result << "\n"); + return *Result; } void LazyValueInfoImpl::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,