[ValueLattice] Allocate value lattice elements on a pool (WIP)

[nikic]

Summary

This introduces a uniqued, bump-pointer allocated pool of value lattice elements. ValueLatticeElement is still used directly for some temporaries, but the persisted values are fetched from the pool and represented as const ValueLatticeElement *.

I think this has a couple of advantages:

• This should use less memory, as each distinct value lattice element is only stored once.
• As a consequence, LVI no longer needs to store overdefined values separately, as storing everything directly is now cheap.
• SCCP will no longer have to worry about invalidating references to value lattice elements.

This patch only has the LVI portion of the change (and there's probably some optimization potential there). For SCCP the main extra thing to handle would be the NumRangeExtensions, which would have to be moved into a separate value->int map under this model.

Preliminary compile-time numbers are a small improvement: https://llvm-compile-time-tracker.com/compare.php?from=862db369f8a8c543735c475ed05cf512846c3868&to=4388725f333c69cf29724528405038f8e143e579&stat=instructions

[nikic]

Hm, migrating SCCP to this model might be harder than I initially thought, because it uses in-place modification so much.

[fhahn]

Interesting, thanks for working on this!

This introduces a uniqued, bump-pointer allocated pool of value lattice elements. ValueLatticeElement is still used directly for some temporaries, but the persisted values are fetched from the pool and represented as const ValueLatticeElement *.

It would be interesting how many duplicated elements are actually eliminated. Using a single element for undef/unknown/overdefiened is definitely very profitable, as most lattice values probably end up overdefined. Removing the overdefined set in LVI is definitely a nice thing and SCCP currently does not have anything similar, so there should be a clear benefit there.

For constant/constantrange I am not sure if the extra book-keeping is actually worth it. Without deduplication, we should be able to get rid of the extra sets/maps. Also, SCCP currently updates the lattice elements directly, so caching them might be problematic (or we might have to allocate new objects for each state change?).

Unless there are large savings from the de-duplication, starting out with only de-duplicating overdefined for both SCCP and LVI, together with the bump allocator without de-duplication. That would be quite straight-forward and should be a clear benefit, at least for SCCP. Not sure if uniquing undef/unknown would be beneficial for SCCP, given the amount of code changes that would be needed.

https://llvm-compile-time-tracker.com/compare.php?from=862db369f8a8c543735c475ed05cf512846c3868&to=4388725f333c69cf29724528405038f8e143e579&stat=instructions

It looks like there are a few max-rss regressions? Is that noise?

Another thing to consider might be using a bump-allocator for ConstantRange and then using ConstantRange* to reduce the total size of ValueLatticeElement.

[fhahn]

(marking as changes requested to indicate that there's an outstanding comment to clear up review queue)

llvm/include/llvm/Analysis/ValueLattice.h

 //===- ValueLattice.h - Value constraint analysis ---------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_VALUELATTICE_H
 #define LLVM_ANALYSIS_VALUELATTICE_H
 
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/Support/Allocator.h"
+
 //
 //===----------------------------------------------------------------------===//
 //                               ValueLatticeElement
 //===----------------------------------------------------------------------===//
 
-/// This class represents lattice values for constants.
-///
-/// FIXME: This is basically just for bringup, this can be made a lot more rich
-/// in the future.
-///
-
 namespace llvm {
+/// This class represents lattice values for constants.
 class ValueLatticeElement {
+  friend struct ValueLatticeMapInfo;
+
   enum ValueLatticeElementTy {
     /// This Value has no known value yet.  As a result, this implies the
     /// producing instruction is dead.  Caution: We use this as the starting
     /// state in our local meet rules.  In this usage, it's taken to mean
     /// "nothing known yet".
     /// Transition to any other state allowed.
     unknown,
 
public:
   unsigned getNumRangeExtensions() const { return NumRangeExtensions; }
   void setNumRangeExtensions(unsigned N) { NumRangeExtensions = N; }
 };
 
 static_assert(sizeof(ValueLatticeElement) <= 40,
               "size of ValueLatticeElement changed unexpectedly");
 
 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
+
+struct ValueLatticeMapInfo {
+  static inline ValueLatticeElement *getEmptyKey() {
+    return DenseMapInfo<ValueLatticeElement *>::getEmptyKey();
+  }
+  static inline ValueLatticeElement *getTombstoneKey() {
+    return DenseMapInfo<ValueLatticeElement *>::getTombstoneKey();
+  }
+
+  static unsigned getHashValue(const ValueLatticeElement *Elem) {
+    switch (Elem->Tag) {
+      case ValueLatticeElement::overdefined:
+      case ValueLatticeElement::unknown:
+      case ValueLatticeElement::undef:
+        return hash_combine(Elem->Tag);
+      case ValueLatticeElement::constant:
+      case ValueLatticeElement::notconstant:
+        return hash_combine(Elem->Tag, Elem->ConstVal);
+      case ValueLatticeElement::constantrange_including_undef:
+      case ValueLatticeElement::constantrange:
+        return hash_combine(Elem->Tag, Elem->Range.getLower(),
+                            Elem->Range.getUpper());
+    }
+    llvm_unreachable("Invalid tag");
+  }
+
+  static bool isEqual(const ValueLatticeElement *A,
+                      const ValueLatticeElement *B) {
+    if (A == getEmptyKey() || A == getTombstoneKey() ||
+        B == getEmptyKey() || B == getTombstoneKey())
+      return A == B;
+
+    if (A->Tag != B->Tag)
+      return false;
+
+    switch (A->Tag) {
+    case ValueLatticeElement::overdefined:
+    case ValueLatticeElement::unknown:
+    case ValueLatticeElement::undef:
+      return true;
+    case ValueLatticeElement::constant:
+    case ValueLatticeElement::notconstant:
+      return A->ConstVal == B->ConstVal;
+    case ValueLatticeElement::constantrange_including_undef:
+    case ValueLatticeElement::constantrange:
+      return A->Range.getBitWidth() == B->Range.getBitWidth() &&
+             A->Range == B->Range;
+    }
+    llvm_unreachable("Invalid tag");
+  }
+};
+
+class ValueLatticePool {
+  SpecificBumpPtrAllocator<ValueLatticeElement> BPA;
+  const ValueLatticeElement *Unknown;
+  const ValueLatticeElement *Overdefined;
+  DenseMap<Constant *, const ValueLatticeElement *> ConstantElems;
+  DenseSet<const ValueLatticeElement *, ValueLatticeMapInfo> Elems;
+
+public:
+  ValueLatticePool();
+
+  const ValueLatticeElement *getUnknown() const { return Unknown; }
+  const ValueLatticeElement *getOverdefined() const { return Overdefined; }
+
+  const ValueLatticeElement *getConstant(Constant *C);
+  const ValueLatticeElement *getNotConstant(Constant *C);
+  const ValueLatticeElement *getRange(const ConstantRange &CR,
+                                      bool MayIncludeUndef = false);
+  const ValueLatticeElement *getElement(const ValueLatticeElement &Elem);
+};
+
 } // end namespace llvm
 #endif

llvm/lib/Analysis/LazyValueInfo.cpp

 namespace {
   /// This is the cache kept by LazyValueInfo which
   /// maintains information about queries across the clients' queries.
   class LazyValueInfoCache {
     /// This is all of the cached information for one basic block. It contains
     /// the per-value lattice elements, as well as a separate set for
     /// overdefined values to reduce memory usage.
     struct BlockCacheEntry {
-      SmallDenseMap<AssertingVH<Value>, ValueLatticeElement, 4> LatticeElements;
-      SmallDenseSet<AssertingVH<Value>, 4> OverDefined;
+      SmallDenseMap<AssertingVH<Value>, const ValueLatticeElement *, 4>
+          LatticeElements;
     };
 
     /// Cached information per basic block.
     DenseMap<PoisoningVH<BasicBlock>, std::unique_ptr<BlockCacheEntry>>
         BlockCache;
     /// Set of value handles used to erase values from the cache on deletion.
     DenseSet<LVIValueHandle, DenseMapInfo<Value *>> ValueHandles;
 
BlockCacheEntry *getOrCreateBlockEntry(BasicBlock *BB) {
         It = BlockCache.insert({ BB, std::make_unique<BlockCacheEntry>() })
                        .first;
 
       return It->second.get();
     }
 
   public:
     void insertResult(Value *Val, BasicBlock *BB,
-                      const ValueLatticeElement &Result) {
+                      const ValueLatticeElement *Result) {
       BlockCacheEntry *Entry = getOrCreateBlockEntry(BB);
-
-      // Insert over-defined values into their own cache to reduce memory
-      // overhead.
-      if (Result.isOverdefined())
-        Entry->OverDefined.insert(Val);
-      else
-        Entry->LatticeElements.insert({ Val, Result });
 
       auto HandleIt = ValueHandles.find_as(Val);
       if (HandleIt == ValueHandles.end())
         ValueHandles.insert({ Val, this });
     }
 
-    Optional<ValueLatticeElement> getCachedValueInfo(Value *V,
-                                                     BasicBlock *BB) const {
+    const ValueLatticeElement *getCachedValueInfo(Value *V,
       const BlockCacheEntry *Entry = getBlockEntry(BB);
       if (!Entry)
-        return None;
-
-      if (Entry->OverDefined.count(V))
-        return ValueLatticeElement::getOverdefined();
-
-      auto LatticeIt = Entry->LatticeElements.find(V);
-      if (LatticeIt == Entry->LatticeElements.end())
-        return None;
+        return nullptr;
 
-      return LatticeIt->second;
+      return Entry->LatticeElements.lookup(V);
     }
 
     /// clear - Empty the cache.
     void clear() {
       BlockCache.clear();
       ValueHandles.clear();
     }
 
     /// Inform the cache that a given value has been deleted.
     void eraseValue(Value *V);
 
     /// This is part of the update interface to inform the cache
     /// that a block has been deleted.
     void eraseBlock(BasicBlock *BB);
 
     /// Updates the cache to remove any influence an overdefined value in
     /// OldSucc might have (unless also overdefined in NewSucc).  This just
     /// flushes elements from the cache and does not add any.
-    void threadEdgeImpl(BasicBlock *OldSucc,BasicBlock *NewSucc);
+    void threadEdgeImpl(BasicBlock *OldSucc, BasicBlock *NewSucc);
   };
 }
 
 void LazyValueInfoCache::eraseValue(Value *V) {
-  for (auto &Pair : BlockCache) {
+  for (auto &Pair : BlockCache)
     Pair.second->LatticeElements.erase(V);
-    Pair.second->OverDefined.erase(V);
-  }
 
   auto HandleIt = ValueHandles.find_as(V);
   if (HandleIt != ValueHandles.end())
     ValueHandles.erase(HandleIt);
 }
 
 void LVIValueHandle::deleted() {
   // This erasure deallocates *this, so it MUST happen after we're done
void LazyValueInfoCache::threadEdgeImpl(BasicBlock *OldSucc,
   // The updating process is fairly simple: we need to drop cached info
   // for all values that were marked overdefined in OldSucc, and for those same
   // values in any successor of OldSucc (except NewSucc) in which they were
   // also marked overdefined.
   std::vector<BasicBlock*> worklist;
   worklist.push_back(OldSucc);
 
   const BlockCacheEntry *Entry = getBlockEntry(OldSucc);
-  if (!Entry || Entry->OverDefined.empty())
-    return; // Nothing to process here.
-  SmallVector<Value *, 4> ValsToClear(Entry->OverDefined.begin(),
-                                      Entry->OverDefined.end());
+  if (!Entry)
+    return;
+
+  SmallVector<Value *, 4> ValsToClear;
+  for (const auto &Pair : Entry->LatticeElements)
+    if (Pair.second->isOverdefined())
+      ValsToClear.push_back(Pair.first);
+  if (ValsToClear.empty())
+    return;
 
   // Use a worklist to perform a depth-first search of OldSucc's successors.
   // NOTE: We do not need a visited list since any blocks we have already
   // visited will have had their overdefined markers cleared already, and we
   // thus won't loop to their successors.
   while (!worklist.empty()) {
     BasicBlock *ToUpdate = worklist.back();
     worklist.pop_back();
 
     // Skip blocks only accessible through NewSucc.
     if (ToUpdate == NewSucc) continue;
 
     // If a value was marked overdefined in OldSucc, and is here too...
     auto OI = BlockCache.find(ToUpdate);
-    if (OI == BlockCache.end() || OI->second->OverDefined.empty())
+    if (OI == BlockCache.end())
       continue;
-    auto &ValueSet = OI->second->OverDefined;
+    auto &ValueSet = OI->second->LatticeElements;
 
     bool changed = false;
     for (Value *V : ValsToClear) {
-      if (!ValueSet.erase(V))
+      auto It = ValueSet.find(V);
+      if (It == ValueSet.end() || !It->second->isOverdefined())
         continue;
 
       // If we removed anything, then we potentially need to update
       // blocks successors too.
+      ValueSet.erase(It);
       changed = true;
     }
 
     if (!changed) continue;
 
     worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
   }
 }

 // The actual implementation of the lazy analysis and update.  Note that the
 // inheritance from LazyValueInfoCache is intended to be temporary while
 // splitting the code and then transitioning to a has-a relationship.
 class LazyValueInfoImpl {
 
   /// Cached results from previous queries
   LazyValueInfoCache TheCache;
 
+  /// Pool of ValueLatticeElements.
+  ValueLatticePool Pool;
+
   /// This stack holds the state of the value solver during a query.
   /// It basically emulates the callstack of the naive
   /// recursive value lookup process.
   SmallVector<std::pair<BasicBlock*, Value*>, 8> BlockValueStack;
 
   /// Keeps track of which block-value pairs are in BlockValueStack.
   DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
 
class LazyValueInfoImpl {
 
   AssumptionCache *AC;  ///< A pointer to the cache of @llvm.assume calls.
   const DataLayout &DL; ///< A mandatory DataLayout
 
   /// Declaration of the llvm.experimental.guard() intrinsic,
   /// if it exists in the module.
   Function *GuardDecl;
 
-  Optional<ValueLatticeElement> getBlockValue(Value *Val, BasicBlock *BB);
-  Optional<ValueLatticeElement> getEdgeValue(Value *V, BasicBlock *F,
+  const ValueLatticeElement *getBlockValue(Value *Val, BasicBlock *BB);
+  const ValueLatticeElement *getEdgeValue(Value *V, BasicBlock *F,
                                 BasicBlock *T, Instruction *CxtI = nullptr);
 
   // These methods process one work item and may add more. A false value
   // returned means that the work item was not completely processed and must
   // be revisited after going through the new items.
   bool solveBlockValue(Value *Val, BasicBlock *BB);
-  Optional<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);
+  const ValueLatticeElement *solveBlockValueImpl(Value *Val, BasicBlock *BB);
+  const ValueLatticeElement *solveBlockValueNonLocal(Value *Val,
+  const ValueLatticeElement *solveBlockValuePHINode(PHINode *PN,
+  const ValueLatticeElement *solveBlockValueSelect(SelectInst *S,
   Optional<ConstantRange> getRangeForOperand(unsigned Op, Instruction *I,
                                              BasicBlock *BB);
-  Optional<ValueLatticeElement> solveBlockValueBinaryOpImpl(
+  const 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(
+  const ValueLatticeElement *solveBlockValueBinaryOp(BinaryOperator *BBI,
+  const ValueLatticeElement *solveBlockValueCast(CastInst *CI,
+  const ValueLatticeElement *solveBlockValueOverflowIntrinsic(
       WithOverflowInst *WO, BasicBlock *BB);
-  Optional<ValueLatticeElement> solveBlockValueSaturatingIntrinsic(
+  const ValueLatticeElement *solveBlockValueSaturatingIntrinsic(
       SaturatingInst *SI, BasicBlock *BB);
-  Optional<ValueLatticeElement> solveBlockValueIntrinsic(IntrinsicInst *II,
-                                                         BasicBlock *BB);
-  Optional<ValueLatticeElement> solveBlockValueExtractValue(
+  const ValueLatticeElement *solveBlockValueIntrinsic(IntrinsicInst *II,
+  const ValueLatticeElement *solveBlockValueExtractValue(
       ExtractValueInst *EVI, BasicBlock *BB);
   void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
                                                      ValueLatticeElement &BBLV,
                                                      Instruction *BBI);
 
   void solve();
 
 public:
while (!BlockValueStack.empty()) {
     // PredicateInfo is used in LVI or CVP, we should be able to make the
     // overdefined cache global, and remove this throttle.
     if (processedCount > MaxProcessedPerValue) {
       LLVM_DEBUG(
           dbgs() << "Giving up on stack because we are getting too deep\n");
       // Fill in the original values
       while (!StartingStack.empty()) {
         std::pair<BasicBlock *, Value *> &e = StartingStack.back();
-        TheCache.insertResult(e.second, e.first,
-                              ValueLatticeElement::getOverdefined());
+        TheCache.insertResult(e.second, e.first, Pool.getOverdefined());
         StartingStack.pop_back();
       }
       BlockValueSet.clear();
       BlockValueStack.clear();
       return;
     }
     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
-      Optional<ValueLatticeElement> BBLV =
+      const 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");
 #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!");
     }
   }
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::getBlockValue(Value *Val,
-                                                               BasicBlock *BB) {
+const ValueLatticeElement *LazyValueInfoImpl::getBlockValue(Value *Val,
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
-    return ValueLatticeElement::get(VC);
+    return Pool.getConstant(VC);
 
-  if (Optional<ValueLatticeElement> OptLatticeVal =
+  if (const ValueLatticeElement *OptLatticeVal =
           TheCache.getCachedValueInfo(Val, BB))
     return OptLatticeVal;
 
   // We have hit a cycle, assume overdefined.
   if (!pushBlockValue({ BB, Val }))
-    return ValueLatticeElement::getOverdefined();
+    return Pool.getOverdefined();
 
   // Yet to be resolved.
-  return None;
+  return nullptr;
 }
 
-static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
+static const ValueLatticeElement *getFromRangeMetadata(ValueLatticePool &Pool,
+                                                       Instruction *BBI) {
   switch (BBI->getOpcode()) {
   default: break;
   case Instruction::Load:
   case Instruction::Call:
   case Instruction::Invoke:
     if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
-      if (isa<IntegerType>(BBI->getType())) {
-        return ValueLatticeElement::getRange(
-            getConstantRangeFromMetadata(*Ranges));
-      }
+      if (isa<IntegerType>(BBI->getType()))
+        return Pool.getRange(getConstantRangeFromMetadata(*Ranges));
     break;
   };
   // Nothing known - will be intersected with other facts
-  return ValueLatticeElement::getOverdefined();
+  return Pool.getOverdefined();
 }
 
 bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
   assert(!isa<Constant>(Val) && "Value should not be constant");
   assert(!TheCache.getCachedValueInfo(Val, BB) &&
          "Value should not be in cache");
 
   // 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);
+  const ValueLatticeElement *Res = solveBlockValueImpl(Val, BB);
   if (!Res)
     // Work pushed, will revisit
     return false;
 
-  TheCache.insertResult(Val, BB, *Res);
+  TheCache.insertResult(Val, BB, Res);
   return true;
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueImpl(
+const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueImpl(
     Value *Val, BasicBlock *BB) {
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB)
     return solveBlockValueNonLocal(Val, BB);
 
   if (PHINode *PN = dyn_cast<PHINode>(BBI))
     return solveBlockValuePHINode(PN, BB);
 
   if (auto *SI = dyn_cast<SelectInst>(BBI))
     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))
-    return ValueLatticeElement::getNot(ConstantPointerNull::get(PT));
+    return Pool.getNotConstant(ConstantPointerNull::get(PT));
 
   if (BBI->getType()->isIntegerTy()) {
     if (auto *CI = dyn_cast<CastInst>(BBI))
       return solveBlockValueCast(CI, BB);
 
     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI))
       return solveBlockValueBinaryOp(BO, BB);
 
     if (auto *EVI = dyn_cast<ExtractValueInst>(BBI))
       return solveBlockValueExtractValue(EVI, BB);
 
     if (auto *II = dyn_cast<IntrinsicInst>(BBI))
       return solveBlockValueIntrinsic(II, BB);
   }
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - unknown inst def found.\n");
-  return getFromRangeMetadata(BBI);
+  return getFromRangeMetadata(Pool, BBI);
 }
 
 static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
   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;
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueNonLocal(
+const 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
   // 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()))))
-      return ValueLatticeElement::getNot(ConstantPointerNull::get(PTy));
+      return Pool.getNotConstant(ConstantPointerNull::get(PTy));
     else
-      return ValueLatticeElement::getOverdefined();
+      return Pool.getOverdefined();
   }
 
   // Loop over all of our predecessors, merging what we know from them into
   // 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) {
-    Optional<ValueLatticeElement> EdgeResult = getEdgeValue(Val, *PI, BB);
+    const ValueLatticeElement *EdgeResult = getEdgeValue(Val, *PI, BB);
     if (!EdgeResult)
       // Explore that input, then return here
-      return None;
+      return nullptr;
 
     Result.mergeIn(*EdgeResult);
 
     // 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));
-      }
-
-      return Result;
+          !NullPointerIsDefined(BB->getParent(), PTy->getAddressSpace()))
+        return Pool.getNotConstant(ConstantPointerNull::get(PTy));
+      else
+        return Pool.getOverdefined();
     }
   }
 
   // Return the merged value, which is more precise than 'overdefined'.
   assert(!Result.isOverdefined());
-  return Result;
+  return Pool.getElement(Result);
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValuePHINode(
+const ValueLatticeElement *LazyValueInfoImpl::solveBlockValuePHINode(
     PHINode *PN, BasicBlock *BB) {
   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);
     // 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 =
+    const ValueLatticeElement *EdgeResult =
         getEdgeValue(PhiVal, PhiBB, BB, PN);
     if (!EdgeResult)
       // Explore that input, then return here
-      return None;
+      return nullptr;
 
     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");
 
-      return Result;
+      return Pool.getOverdefined();
     }
   }
 
   // Return the merged value, which is more precise than 'overdefined'.
   assert(!Result.isOverdefined() && "Possible PHI in entry block?");
-  return Result;
+  return Pool.getElement(Result);
 }
 
 static ValueLatticeElement getValueFromCondition(Value *Val, Value *Cond,
                                                  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()),
                                    BB->rend())) {
     Value *Cond = nullptr;
     if (match(&I, m_Intrinsic<Intrinsic::experimental_guard>(m_Value(Cond))))
       BBLV = intersect(BBLV, getValueFromCondition(Val, Cond));
   }
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueSelect(
+const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueSelect(
     SelectInst *SI, BasicBlock *BB) {
   // Recurse on our inputs if needed
-  Optional<ValueLatticeElement> OptTrueVal =
-      getBlockValue(SI->getTrueValue(), BB);
-  if (!OptTrueVal)
-    return None;
-  ValueLatticeElement &TrueVal = *OptTrueVal;
+  const ValueLatticeElement *TrueVal = getBlockValue(SI->getTrueValue(), BB);
+  if (!TrueVal)
+    return nullptr;
 
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
-  if (TrueVal.isOverdefined())
-    return ValueLatticeElement::getOverdefined();
+  if (TrueVal->isOverdefined())
+    return Pool.getOverdefined();
 
-  Optional<ValueLatticeElement> OptFalseVal =
-      getBlockValue(SI->getFalseValue(), BB);
-  if (!OptFalseVal)
-    return None;
-  ValueLatticeElement &FalseVal = *OptFalseVal;
+  const ValueLatticeElement *FalseVal = getBlockValue(SI->getFalseValue(), BB);
+  if (!FalseVal)
+    return nullptr;
 
   // If we hit overdefined, don't ask more queries.  We want to avoid poisoning
   // extra slots in the table if we can.
-  if (FalseVal.isOverdefined())
-    return ValueLatticeElement::getOverdefined();
+  if (FalseVal->isOverdefined())
+    return Pool.getOverdefined();
 
-  if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
-    const ConstantRange &TrueCR = TrueVal.getConstantRange();
-    const ConstantRange &FalseCR = FalseVal.getConstantRange();
+  if (TrueVal->isConstantRange() && FalseVal->isConstantRange()) {
+    const ConstantRange &TrueCR = TrueVal->getConstantRange();
+    const ConstantRange &FalseCR = FalseVal->getConstantRange();
     Value *LHS = nullptr;
     Value *RHS = nullptr;
     SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
     // Is this a min specifically of our two inputs?  (Avoid the risk of
     // ValueTracking getting smarter looking back past our immediate inputs.)
     if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
         LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
       ConstantRange ResultCR = [&]() {
         switch (SPR.Flavor) {
         default:
           llvm_unreachable("unexpected minmax type!");
         case SPF_SMIN:                   /// Signed minimum
           return TrueCR.smin(FalseCR);
         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);
         };
       }();
-      return ValueLatticeElement::getRange(
-          ResultCR, TrueVal.isConstantRangeIncludingUndef() |
-                        FalseVal.isConstantRangeIncludingUndef());
+      return Pool.getRange(ResultCR, TrueVal->isConstantRangeIncludingUndef() |
+                                     FalseVal->isConstantRangeIncludingUndef());
     }
 
     if (SPR.Flavor == SPF_ABS) {
       if (LHS == SI->getTrueValue())
-        return ValueLatticeElement::getRange(
-            TrueCR.abs(), TrueVal.isConstantRangeIncludingUndef());
+        return Pool.getRange(
+            TrueCR.abs(), TrueVal->isConstantRangeIncludingUndef());
       if (LHS == SI->getFalseValue())
-        return ValueLatticeElement::getRange(
-            FalseCR.abs(), FalseVal.isConstantRangeIncludingUndef());
+        return Pool.getRange(
+            FalseCR.abs(), FalseVal->isConstantRangeIncludingUndef());
     }
 
     if (SPR.Flavor == SPF_NABS) {
       ConstantRange Zero(APInt::getNullValue(TrueCR.getBitWidth()));
       if (LHS == SI->getTrueValue())
-        return ValueLatticeElement::getRange(
-            Zero.sub(TrueCR.abs()), FalseVal.isConstantRangeIncludingUndef());
+        return Pool.getRange(
+            Zero.sub(TrueCR.abs()), FalseVal->isConstantRangeIncludingUndef());
       if (LHS == SI->getFalseValue())
-        return ValueLatticeElement::getRange(
-            Zero.sub(FalseCR.abs()), FalseVal.isConstantRangeIncludingUndef());
+        return Pool.getRange(
+            Zero.sub(FalseCR.abs()), FalseVal->isConstantRangeIncludingUndef());
     }
   }
 
   // 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,
-                      getValueFromCondition(SI->getTrueValue(), Cond, true));
-  FalseVal = intersect(FalseVal,
-                       getValueFromCondition(SI->getFalseValue(), Cond, false));
+  ValueLatticeElement NewTrueVal = intersect(
+      *TrueVal, getValueFromCondition(SI->getTrueValue(), Cond, true));
+  ValueLatticeElement NewFalseVal = intersect(
+      *FalseVal, getValueFromCondition(SI->getFalseValue(), Cond, false));
 
   // Handle clamp idioms such as:
   //   %24 = constantrange<0, 17>
   //   %39 = icmp eq i32 %24, 0
   //   %40 = add i32 %24, -1
   //   %siv.next = select i1 %39, i32 16, i32 %40
   //   %siv.next = constantrange<0, 17> not <-1, 17>
   // In general, this can handle any clamp idiom which tests the edge
if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
       // that input doesn't include C + C2.
       ConstantInt *CIAdded;
       switch (Pred) {
       default: break;
       case ICmpInst::ICMP_EQ:
         if (match(SI->getFalseValue(), m_Add(m_Specific(A),
                                              m_ConstantInt(CIAdded)))) {
           auto ResNot = addConstants(CIBase, CIAdded);
-          FalseVal = intersect(FalseVal,
+          NewFalseVal = intersect(NewFalseVal,
                                   ValueLatticeElement::getNot(ResNot));
         }
         break;
       case ICmpInst::ICMP_NE:
         if (match(SI->getTrueValue(), m_Add(m_Specific(A),
                                             m_ConstantInt(CIAdded)))) {
           auto ResNot = addConstants(CIBase, CIAdded);
-          TrueVal = intersect(TrueVal,
+          NewTrueVal = intersect(NewTrueVal,
                                  ValueLatticeElement::getNot(ResNot));
         }
         break;
       };
     }
   }
 
-  ValueLatticeElement Result = TrueVal;
-  Result.mergeIn(FalseVal);
-  return Result;
+  ValueLatticeElement Result = std::move(NewTrueVal);
+  Result.mergeIn(NewFalseVal);
+  return Pool.getElement(Result);
 }
 
 Optional<ConstantRange> LazyValueInfoImpl::getRangeForOperand(unsigned Op,
                                                               Instruction *I,
                                                               BasicBlock *BB) {
-  Optional<ValueLatticeElement> OptVal = getBlockValue(I->getOperand(Op), BB);
+  const ValueLatticeElement *OptVal = getBlockValue(I->getOperand(Op), BB);
   if (!OptVal)
     return None;
 
-  ValueLatticeElement &Val = *OptVal;
+  ValueLatticeElement Val = *OptVal;
   intersectAssumeOrGuardBlockValueConstantRange(I->getOperand(Op), Val, I);
   if (Val.isConstantRange())
     return Val.getConstantRange();
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(I->getOperand(Op)->getType());
   return ConstantRange::getFull(OperandBitWidth);
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueCast(
+const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueCast(
     CastInst *CI, BasicBlock *BB) {
   // Without knowing how wide the input is, we can't analyze it in any useful
   // way.
   if (!CI->getOperand(0)->getType()->isSized())
-    return ValueLatticeElement::getOverdefined();
+    return Pool.getOverdefined();
 
   // Filter out casts we don't know how to reason about before attempting to
   // recurse on our operand.  This can cut a long search short if we know we're
   // 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");
-    return ValueLatticeElement::getOverdefined();
+    return Pool.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 None;
-  const ConstantRange &LHSRange = LHSRes.getValue();
+    return nullptr;
 
+  const ConstantRange &LHSRange = LHSRes.getValue();
   const unsigned ResultBitWidth = CI->getType()->getIntegerBitWidth();
 
   // NOTE: We're currently limited by the set of operations that ConstantRange
   // can evaluate symbolically.  Enhancing that set will allows us to analyze
   // more definitions.
-  return ValueLatticeElement::getRange(LHSRange.castOp(CI->getOpcode(),
-                                                       ResultBitWidth));
+  return Pool.getRange(LHSRange.castOp(CI->getOpcode(), ResultBitWidth));
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOpImpl(
+const 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 None;
+    return nullptr;
 
   const ConstantRange &LHSRange = LHSRes.getValue();
   const ConstantRange &RHSRange = RHSRes.getValue();
-  return ValueLatticeElement::getRange(OpFn(LHSRange, RHSRange));
+  return Pool.getRange(OpFn(LHSRange, RHSRange));
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueBinaryOp(
+const 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");
-    return ValueLatticeElement::getOverdefined();
+    return Pool.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(
         BO, BB,
         [BO, NoWrapKind](const ConstantRange &CR1, const ConstantRange &CR2) {
           return CR1.overflowingBinaryOp(BO->getOpcode(), CR2, NoWrapKind);
         });
   }
 
   return solveBlockValueBinaryOpImpl(
       BO, BB, [BO](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.binaryOp(BO->getOpcode(), CR2);
       });
 }
 
-Optional<ValueLatticeElement>
+const ValueLatticeElement *
 LazyValueInfoImpl::solveBlockValueOverflowIntrinsic(WithOverflowInst *WO,
                                                     BasicBlock *BB) {
   return solveBlockValueBinaryOpImpl(
       WO, BB, [WO](const ConstantRange &CR1, const ConstantRange &CR2) {
         return CR1.binaryOp(WO->getBinaryOp(), CR2);
       });
 }
 
-Optional<ValueLatticeElement>
+const ValueLatticeElement *
 LazyValueInfoImpl::solveBlockValueSaturatingIntrinsic(SaturatingInst *SI,
                                                       BasicBlock *BB) {
   switch (SI->getIntrinsicID()) {
   case Intrinsic::uadd_sat:
     return solveBlockValueBinaryOpImpl(
         SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) {
           return CR1.uadd_sat(CR2);
         });
return solveBlockValueBinaryOpImpl(
         SI, BB, [](const ConstantRange &CR1, const ConstantRange &CR2) {
           return CR1.ssub_sat(CR2);
         });
   default:
     llvm_unreachable("All llvm.sat intrinsic are handled.");
   }
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueIntrinsic(
+const ValueLatticeElement *LazyValueInfoImpl::solveBlockValueIntrinsic(
     IntrinsicInst *II, BasicBlock *BB) {
   if (auto *SI = dyn_cast<SaturatingInst>(II))
     return solveBlockValueSaturatingIntrinsic(SI, BB);
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - overdefined (unknown intrinsic).\n");
-  return ValueLatticeElement::getOverdefined();
+  return Pool.getOverdefined();
 }
 
-Optional<ValueLatticeElement> LazyValueInfoImpl::solveBlockValueExtractValue(
+const 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);
 
   // 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(V, BB);
 
   LLVM_DEBUG(dbgs() << " compute BB '" << BB->getName()
                     << "' - overdefined (unknown extractvalue).\n");
-  return ValueLatticeElement::getOverdefined();
+  return Pool.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 (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
     }
     return ValueLatticeElement::getRange(std::move(EdgesVals));
   }
   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.
-Optional<ValueLatticeElement> LazyValueInfoImpl::getEdgeValue(
+const ValueLatticeElement *LazyValueInfoImpl::getEdgeValue(
     Value *Val, BasicBlock *BBFrom, BasicBlock *BBTo, Instruction *CxtI) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
-    return ValueLatticeElement::get(VC);
+    return Pool.getConstant(VC);
 
   ValueLatticeElement LocalResult = getEdgeValueLocal(Val, BBFrom, BBTo)
       .getValueOr(ValueLatticeElement::getOverdefined());
   if (hasSingleValue(LocalResult))
     // Can't get any more precise here
-    return LocalResult;
+    return Pool.getElement(LocalResult);
 
-  Optional<ValueLatticeElement> OptInBlock = getBlockValue(Val, BBFrom);
+  const ValueLatticeElement *OptInBlock = getBlockValue(Val, BBFrom);
   if (!OptInBlock)
-    return None;
-  ValueLatticeElement &InBlock = *OptInBlock;
+    return nullptr;
+  ValueLatticeElement InBlock = *OptInBlock;
 
   // Try to intersect ranges of the BB and the constraint on the edge.
   intersectAssumeOrGuardBlockValueConstantRange(Val, InBlock,
                                                 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);
 
-  return intersect(LocalResult, InBlock);
+  return Pool.getElement(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());
-  Optional<ValueLatticeElement> OptResult = getBlockValue(V, BB);
+  const ValueLatticeElement *OptResult = getBlockValue(V, BB);
   if (!OptResult) {
     solve();
     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()
                     << "'\n");
 
   if (auto *C = dyn_cast<Constant>(V))
     return ValueLatticeElement::get(C);
 
   ValueLatticeElement Result = ValueLatticeElement::getOverdefined();
   if (auto *I = dyn_cast<Instruction>(V))
-    Result = getFromRangeMetadata(I);
+    Result = *getFromRangeMetadata(Pool, I);
   intersectAssumeOrGuardBlockValueConstantRange(V, Result, CxtI);
 
   LLVM_DEBUG(dbgs() << "  Result = " << Result << "\n");
   return Result;
 }
 
 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");
 
-  Optional<ValueLatticeElement> Result = getEdgeValue(V, FromBB, ToBB, CxtI);
+  const ValueLatticeElement *Result = getEdgeValue(V, FromBB, ToBB, CxtI);
   if (!Result) {
     solve();
     Result = getEdgeValue(V, FromBB, ToBB, CxtI);
     assert(Result && "More work to do after problem solved?");
   }
 
   LLVM_DEBUG(dbgs() << "  Result = " << *Result << "\n");
   return *Result;

llvm/lib/Analysis/ValueLattice.cpp

return OS << "constantrange incl. undef <"
               << Val.getConstantRange(true).getLower() << ", "
               << Val.getConstantRange(true).getUpper() << ">";
 
   if (Val.isConstantRange())
     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
+
+ValueLatticePool::ValueLatticePool() {
+  Unknown = new (BPA.Allocate()) ValueLatticeElement();
+  Overdefined = new (BPA.Allocate()) ValueLatticeElement(
+      ValueLatticeElement::getOverdefined());
+}
+
+const ValueLatticeElement *ValueLatticePool::getConstant(Constant *C) {
+  auto It = ConstantElems.find(C);
+  if (It != ConstantElems.end())
+    return It->second;
+
+  return getElement(ValueLatticeElement::get(C));
+}
+
+const ValueLatticeElement *ValueLatticePool::getNotConstant(Constant *C) {
+  return getElement(ValueLatticeElement::getNot(C));
+}
+
+const ValueLatticeElement *
+ValueLatticePool::getRange(const ConstantRange &CR, bool MayIncludeUndef) {
+  return getElement(ValueLatticeElement::getRange(CR, MayIncludeUndef));
+}
+
+const ValueLatticeElement *
+ValueLatticePool::getElement(const ValueLatticeElement &Elem) {
+  if (Elem.isUnknown())
+    return Unknown;
+  if (Elem.isOverdefined())
+    return Overdefined;
+
+  auto It = Elems.find(&Elem);
+  if (It != Elems.end())
+    return *It;
+
+  const ValueLatticeElement *NewElem =
+    new (BPA.Allocate()) ValueLatticeElement(Elem);
+  Elems.insert(NewElem);
+  return NewElem;
+}
+
 } // end namespace llvm