[LVI] Use Optional instead of out parameter (NFC)

[nikic]

Summary

As suggested on D76788, this switches the LVI implementation to return Optional<ValueLatticeElement> from various methods, instead of passing in a ValueLatticeElement reference and returning a boolean.

[nikic]

lib/Analysis/LazyValueInfo.cpp

839

My C++ foo is weak... would the proper way to write this without copying the lattice value be TrueValue = *std::move(OptTrueVal)?

[nikic]

lib/Analysis/LazyValueInfo.cpp

839

Hm, it looks like moving an Optional moves the value (rather than making the Optional empty). As ValueLatticeElement does not specify a move constructor, I guess that means it would end up being copied, so that probably doesn't make sense.

[fhahn]

lib/Analysis/LazyValueInfo.cpp

839

Can this just be ValueLatticeElement &TrueVal?

[nikic]

Use reference to ValueLatticeElement where possible.

[nikic]

lib/Analysis/LazyValueInfo.cpp

839

Right, I went with that variant now. The use of Optional will still make for a small but measurable regression (~0.1%), but that seems acceptable to me.

I'll also submit a followup to add a move constructor to ValueLatticeElement. It makes no difference for performance in practice, because we usually deal with APInts <= 64 bits, so move and copy constructor do about the same work. It would make a difference for large APInts.

[fhahn]

LGTM, thanks for the cleanup!

lib/Analysis/LazyValueInfo.cpp

bool isOverdefined(Value *V, BasicBlock *BB) const {
       auto ODI = OverDefinedCache.find(BB);
 
       if (ODI == OverDefinedCache.end())
         return false;
 
       return ODI->second.count(V);
     }
 
-    bool getCachedValueInfo(ValueLatticeElement &BBLV, Value *V,
+    Optional<ValueLatticeElement> getCachedValueInfo(Value *V,
                                                      BasicBlock *BB) const {
-      if (isOverdefined(V, BB)) {
-        BBLV = ValueLatticeElement::getOverdefined();
-        return true;
-      }
+      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.
     void clear() {
       SeenBlocks.clear();
       ValueCache.clear();
       OverDefinedCache.clear();
     }
bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
       return true;
     }
 
     AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
     const DataLayout &DL; ///< A mandatory DataLayout
     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<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB);
+  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);
-  bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
+  Optional<ValueLatticeElement> solveBlockValueImpl(Value *Val, BasicBlock *BB);
+  Optional<ValueLatticeElement> solveBlockValueNonLocal(Value *Val,
                                                         BasicBlock *BB);
-  bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
+  Optional<ValueLatticeElement> solveBlockValuePHINode(PHINode *PN,
                                                        BasicBlock *BB);
-  bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
-                              BasicBlock *BB);
-  bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
+  Optional<ValueLatticeElement> solveBlockValueSelect(SelectInst *S,
                                                       BasicBlock *BB);
   Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I,
                                              BasicBlock *BB);
-  bool solveBlockValueBinaryOpImpl(
-      ValueLatticeElement &BBLV, Instruction *I, BasicBlock *BB,
+  Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
+      Instruction *I, BasicBlock *BB,
       std::function<ConstantRange(const ConstantRange &,
                                   const ConstantRange &)> OpFn);
-  bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
+  Optional<ValueLatticeElement> solveBlockValueBinaryOp(BinaryOperator *BBI,
                                                         BasicBlock *BB);
-  bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
+  Optional<ValueLatticeElement> solveBlockValueCast(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,
+  Optional<ValueLatticeElement> solveBlockValueOverflowIntrinsic(
+      WithOverflowInst *WO, BasicBlock *BB);
+  Optional<ValueLatticeElement> solveBlockValueSaturatingIntrinsic(
+  Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
                                                          BasicBlock *BB);
-  bool solveBlockValueExtractValue(ValueLatticeElement &BBLV,
-                                   ExtractValueInst *EVI, BasicBlock *BB);
+  Optional<ValueLatticeElement> solveBlockValueExtractValue(
   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                      ValueLatticeElement &BBLV,
                                                      Instruction *BBI);
 
   void solve();
 
   public:
     /// This is the query interface to determine the lattice
while (!BlockValueStack.empty()) {
     }
     std::pair<BasicBlock *, Value *> e = BlockValueStack.back();
     assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
 
     if (solveBlockValue(e.second, e.first)) {
       // 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<ValueLatticeElement> 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();
       BlockValueSet.erase(e);
     } else {
       // More work needs to be done before revisiting.
       assert(BlockValueStack.back() != e && "Stack should have been pushed!");
     }
   }
 }
 
-bool LazyValueInfoImpl::getBlockValue(ValueLatticeElement &BBLV,
-                                      Value *Val, BasicBlock *BB) {
+Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue(Value *Val,
+                                                               BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
-  if (Constant *VC = dyn_cast<Constant>(Val)) {
-    BBLV = ValueLatticeElement::get(VC);
-    return true;
-  }
+  if (Constant *VC = dyn_cast<Constant>(Val))
+    return ValueLatticeElement::get(VC);
 
-  if (TheCache.getCachedValueInfo(BBLV, Val, BB))
-    return true;
+  if (Optional<ValueLatticeElement> 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) {
   switch (BBI->getOpcode()) {
   default: break;
   case Instruction::Load:
   case Instruction::Call:
   case Instruction::Invoke:
     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
       if (isa<IntegerType>(BBI->getType())) {
         return ValueLatticeElement::getRange(
             getConstantRangeFromMetadata(*Ranges));
       }
     break;
   };
   // Nothing known - will be intersected with other facts
   return ValueLatticeElement::getOverdefined();
 }
 
 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
-#ifndef NDEBUG
-  ValueLatticeElement BBLV;
   assert(!isa<Constant>(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<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;
 }
 
-bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
-                                            Value *Val, BasicBlock *BB) {
-
+Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl(
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB)
-    return solveBlockValueNonLocal(Res, Val, BB);
+    return solveBlockValueNonLocal(Val, BB);
 
   if (PHINode *PN = dyn_cast<PHINode>(BBI))
-    return solveBlockValuePHINode(Res, PN, BB);
+    return solveBlockValuePHINode(PN, BB);
 
   if (auto *SI = dyn_cast<SelectInst>(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
   // definition.  We could easily extend this to look through geps, bitcasts,
   // and the like to prove non-nullness, but it's not clear that's worth it
   // compile time wise.  The context-insensitive value walk done inside
   // isKnownNonZero gets most of the profitable cases at much less expense.
   // This does mean that we have a sensitivity to where the defining
   // instruction is placed, even if it could legally be hoisted much higher.
   // That is unfortunate.
   PointerType *PT = dyn_cast<PointerType>(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<CastInst>(BBI))
-      return solveBlockValueCast(Res, CI, BB);
+      return solveBlockValueCast(CI, BB);
 
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
-      return solveBlockValueBinaryOp(Res, BO, BB);
+      return solveBlockValueBinaryOp(BO, BB);
 
     if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
-      return solveBlockValueExtractValue(Res, EVI, BB);
+      return solveBlockValueExtractValue(EVI, BB);
 
     if (auto *II = dyn_cast<IntrinsicInst>(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) {
   if (LoadInst *L = dyn_cast<LoadInst>(I)) {
     return L->getPointerAddressSpace() == 0 &&
            GetUnderlyingObject(L->getPointerOperand(),
                                L->getModule()->getDataLayout()) == Ptr;
   }
static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
   // inside InstructionDereferencesPointer either.
   if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
     for (Instruction &I : *BB)
       if (InstructionDereferencesPointer(&I, UnderlyingVal))
         return true;
   return false;
 }
 
-bool LazyValueInfoImpl::solveBlockValueNonLocal(ValueLatticeElement &BBLV,
-                                                 Value *Val, BasicBlock *BB) {
+Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal(
   ValueLatticeElement Result;  // Start Undefined.
 
   // If this is the entry block, we must be asking about an argument.  The
   // value is overdefined.
   if (BB == &BB->getParent()->getEntryBlock()) {
     assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
     // Before giving up, see if we can prove the pointer non-null local to
     // this particular block.
     PointerType *PTy = dyn_cast<PointerType>(Val->getType());
     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
   // result.  If we encounter an unexplored predecessor, we eagerly explore it
   // in a depth first manner.  In practice, this has the effect of discovering
   // paths we can't analyze eagerly without spending compile times analyzing
   // other paths.  This heuristic benefits from the fact that predecessors are
   // frequently arranged such that dominating ones come first and we quickly
   // find a path to function entry.  TODO: We should consider explicitly
   // 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<ValueLatticeElement> 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.
     if (Result.isOverdefined()) {
       LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                         << "' - overdefined because of pred (non local).\n");
       // Before giving up, see if we can prove the pointer non-null local to
       // this particular block.
       PointerType *PTy = dyn_cast<PointerType>(Val->getType());
       if (PTy && isObjectDereferencedInBlock(Val, BB) &&
           !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace())) {
         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<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode(
   ValueLatticeElement Result;  // Start Undefined.
 
   // Loop over all of our predecessors, merging what we know from them into
   // result.  See the comment about the chosen traversal order in
   // solveBlockValueNonLocal; the same reasoning applies here.
   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<ValueLatticeElement> 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.
     if (Result.isOverdefined()) {
       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,
                                                  bool isTrueDest = true);
 
 // If we can determine a constraint on the value given conditions assumed by
 // the program, intersect those constraints with BBLV
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
   for (Instruction &I : make_range(std::next(BBI->getIterator().getReverse()),
                                    BBI->getParent()->rend())) {
     Value *Cond = nullptr;
     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }
 
-bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
-                                              SelectInst *SI, BasicBlock *BB) {
-
+Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
   // Recurse on our inputs if needed
-  ValueLatticeElement TrueVal;
-  if (!getBlockValue(TrueVal, SI->getTrueValue(), BB))
-    return false;
+  Optional<ValueLatticeElement> 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<ValueLatticeElement> 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();
     const ConstantRange &FalseCR = FalseVal.getConstantRange();
     Value *LHS = nullptr;
     Value *RHS = nullptr;
     SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
     // Is this a min specifically of our two inputs?  (Avoid the risk of
if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
         case SPF_UMIN:                   /// Unsigned minimum
           return TrueCR.umin(FalseCR);
         case SPF_SMAX:                   /// Signed maximum
           return TrueCR.smax(FalseCR);
         case SPF_UMAX:                   /// Unsigned maximum
           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;
-      }
     }
   }
 
   // Can we constrain the facts about the true and false values by using the
   // 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,
if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
         break;
       };
     }
   }
 
   ValueLatticeElement Result;  // Start Undefined.
   Result.mergeIn(TrueVal);
   Result.mergeIn(FalseVal);
-  BBLV = Result;
-  return true;
+  return Result;
 }
 
 Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
                                                               Instruction *I,
                                                               BasicBlock *BB) {
-  ValueLatticeElement Val;
-  if (!getBlockValue(Val, I->getOperand(Op), BB))
+  Optional<ValueLatticeElement> 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();
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(I->getOperand(Op)->getType());
   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<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast(
+    CastInst *CI, BasicBlock *BB) {
+  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
   // not going to be able to get any useful information anways.
   switch (CI->getOpcode()) {
   case Instruction::Trunc:
   case Instruction::SExt:
   case Instruction::ZExt:
   case Instruction::BitCast:
     break;
   default:
     // 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
   // transfer rule on the full set since we may be able to locally infer
   // interesting facts.
   Optional<ConstantRange> 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<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
+    Instruction *I, BasicBlock *BB,
     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 = getRangeForOperand(0, I, BB);
   Optional<ConstantRange> 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<ValueLatticeElement> 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<OverflowingBinaryOperator>(BO)) {
     unsigned NoWrapKind = 0;
     if (OBO->hasNoUnsignedWrap())
       NoWrapKind |= OverflowingBinaryOperator::NoUnsignedWrap;
     if (OBO->hasNoSignedWrap())
       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<ValueLatticeElement>
+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<ValueLatticeElement>
+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:
     llvm_unreachable("All llvm.sat intrinsic are handled.");
   }
 }
 
-bool LazyValueInfoImpl::solveBlockValueIntrinsic(ValueLatticeElement &BBLV,
-                                                 IntrinsicInst *II,
-                                                 BasicBlock *BB) {
+Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic(
+    IntrinsicInst *II, BasicBlock *BB) {
   if (auto *SI = dyn_cast<SaturatingInst>(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<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(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,
                                                      bool isTrueDest) {
   Value *LHS = ICI->getOperand(0);
   Value *RHS = ICI->getOperand(1);
   CmpInst::Predicate Predicate = ICI->getPredicate();
 
if (auto *CI = dyn_cast<CastInst>(Usr)) {
     }
   }
   return ValueLatticeElement::getOverdefined();
 }
 
 /// 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<ValueLatticeElement> 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<BranchInst>(BBFrom->getTerminator())) {
     // If this is a conditional branch and only one successor goes to BBTo, then
     // we may be able to infer something from the condition.
     if (BI->isConditional() &&
         BI->getSuccessor(0) != BI->getSuccessor(1)) {
       bool isTrueDest = BI->getSuccessor(0) == BBTo;
       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
              "BBTo isn't a successor of BBFrom");
       Value *Condition = BI->getCondition();
 
       // 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<User>(Val)) {
         assert(Result.isOverdefined() && "Result isn't overdefined");
         // Check with isOperationFoldable() first to avoid linearly iterating
         // over the operands unnecessarily which can be expensive for
         // instructions with many operands.
         if (isa<IntegerType>(Usr->getType()) && isOperationFoldable(Usr)) {
           const DataLayout &DL = BBTo->getModule()->getDataLayout();
if (BI->isConditional() &&
                 Result = constantFoldUser(Usr, Op, OpConst.getValue(), DL);
                 break;
               }
             }
           }
         }
       }
       if (!Result.isOverdefined())
-        return true;
+        return Result;
     }
   }
 
   // If the edge was formed by a switch on the value, then we may know exactly
   // what it is.
   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
     Value *Condition = SI->getCondition();
     if (!isa<IntegerType>(Val->getType()))
-      return false;
+      return None;
     bool ValUsesConditionAndMayBeFoldable = false;
     if (Condition != Val) {
       // Check if Val has Condition as an operand.
       if (User *Usr = dyn_cast<User>(Val))
         ValUsesConditionAndMayBeFoldable = isOperationFoldable(Usr) &&
             usesOperand(Usr, Condition);
       if (!ValUsesConditionAndMayBeFoldable)
-        return false;
+        return None;
     }
     assert((Condition == Val || ValUsesConditionAndMayBeFoldable) &&
            "Condition != Val nor Val doesn't use Condition");
 
     bool DefaultCase = SI->getDefaultDest() == BBTo;
     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
 
     for (auto Case : SI->cases()) {
       APInt CaseValue = Case.getCaseValue()->getValue();
       ConstantRange EdgeVal(CaseValue);
       if (ValUsesConditionAndMayBeFoldable) {
         User *Usr = cast<User>(Val);
         const DataLayout &DL = BBTo->getModule()->getDataLayout();
         ValueLatticeElement EdgeLatticeVal =
             constantFoldUser(Usr, Condition, CaseValue, DL);
         if (EdgeLatticeVal.isOverdefined())
-          return false;
+          return None;
         EdgeVal = EdgeLatticeVal.getConstantRange();
       }
       if (DefaultCase) {
         // It is possible that the default destination is the destination of
         // some cases. We cannot perform difference for those cases.
         // We know Condition != CaseValue in BBTo.  In some cases we can use
         // this to infer Val == f(Condition) is != f(CaseValue).  For now, we
         // only do this when f is identity (i.e. Val == Condition), but we
         // should be able to do this for any injective f.
         if (Case.getCaseSuccessor() != BBTo && Condition == Val)
           EdgesVals = EdgesVals.difference(EdgeVal);
       } 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<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)) {
-    Result = ValueLatticeElement::get(VC);
-    return true;
-  }
-
-  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 (Constant *VC = dyn_cast<Constant>(Val))
+    return ValueLatticeElement::get(VC);
 
-  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<ValueLatticeElement> 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,
                                                 BBFrom->getTerminator());
   // We can use the context instruction (generically the ultimate instruction
   // the calling pass is trying to simplify) here, even though the result of
   // this function is generally cached when called from the solve* functions
   // (and that cached result might be used with queries using a different
   // context instruction), because when this function is called from the solve*
   // functions, the context instruction is not provided. When called from
   // LazyValueInfoImpl::getValueOnEdge, the context instruction is provided,
   // 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,
                                                        Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
                     << BB->getName() << "'\n");
 
   assert(BlockValueStack.empty() && BlockValueSet.empty());
-  ValueLatticeElement Result;
-  if (!getBlockValue(Result, V, BB)) {
+  Optional<ValueLatticeElement> 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");
   return Result;
 }
 
 ValueLatticeElement LazyValueInfoImpl::getValueAt(Value *V, Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting value " << *V << " at '" << CxtI->getName()

 
 ValueLatticeElement LazyValueInfoImpl::
 getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
                Instruction *CxtI) {
   LLVM_DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
                     << FromBB->getName() << "' to '" << ToBB->getName()
                     << "'\n");
 
-  ValueLatticeElement Result;
-  if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
+  Optional<ValueLatticeElement> 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,
                                    BasicBlock *NewSucc) {
   TheCache.threadEdgeImpl(OldSucc, NewSucc);
 }
 
 //===----------------------------------------------------------------------===//