[ValueLattice] Add CompactValueLatticeElement.

[fhahn]

Summary

This patch adds a CompactValueLatticeElement class which uses
PointerIntPair to store info about the element in a compact
fashion. Something along those lines has been mentioned in
PR26921.

Most of the actual ValueLatticeElement logic is moved to
ValueLatticeElementBase. Templates are used to dispatch calls to
subtypes of ValueLatticeElementBase (which contain the actual data)
statically.

In LazyValueInfo, the compact representation is used to store the
cached values, but ValueLatticeElement is used for the temporary
objects, to avoid internalizing constant ranges unnecessarily.

I also tried to push down the conversions between the 2 representations
as far as possible. In general, we should only need to do at most
1 conversion to and from to compact representation each.

Also the plan is to use reference counting to remove ConstantRanges
from the pool as they become unused. That's not implemented yet.

[fhahn]

This version still contains style violations and there are a few parts that could potentially be committed as NFCs.

[reames]

Structural suggestion: pick either of the two subtasks and implement them in isolation. That is *either* replace the ConstantRange with an owned ConstantRange allocation and implement the tagged pointer OR implement the ConstantRange folding set. Doing both in one change is needlessly complicated. Once one is done, the other follows more naturally. I'd suggest the first then the second, but either order is defensible.

Can I ask why you chose to tackle this one? What motivated you to care about the memory consumption of LVI? Just curious about the background and motivating test cases.

[fhahn]

Thanks @reames ! This patch should introduces a more compact lattice element representation using PointerIntPair, not the ConstantRange folding set.

Updated the patch to avoid the need to internalize constant ranges for temporary objects, as used by LazyValueInfo.

[fhahn]

In D39743#918748, @reames wrote:

> Can I ask why you chose to tackle this one? What motivated you to care about the memory consumption of LVI? Just curious about the background and motivating test cases.

There is no particular test case I am looking at. But I want to use ValueLatticeElement for values in IPSCCP (not just parameters, as it is at the moment), and thought it would be a good idea to try to get a more compact representation before that. Also, the more compact representation should make it easier to add additional lattices in the future.

[fhahn]

This needs some more work. I'll update the patch and post some data once I am done.

[reames]

Marking to get off my queue.

[fhahn]

Abandoning for now

include/llvm/Analysis/ValueLattice.h

return static_cast<unsigned>(
         hash_combine(hash_value(V.getLower()), hash_value(V.getUpper())));
   }
 
   static bool isEqual(const ConstantRange &LHS, const ConstantRange &RHS) {
     return LHS.getBitWidth() == RHS.getBitWidth() && LHS == RHS;
   }
 };
 
-class ValueLatticeElement {
+static ConstantRange *addConstantRange(ConstantRange CR,
+                                       DenseMap<ConstantRange, unsigned> &CRP) {
+  auto I = CRP.insert({CR, 1});
+  if (!I.second)
+    I.first->second += 1;
+  return const_cast<ConstantRange *>(&I.first->first);
+}
+
+constexpr size_t const_min(size_t a, size_t b) { return (a < b) ? a : b; }
+
+// We use this trait to set NumLowBitsAvailable based on the alignment of
+// Constant and ConstantRange.
+struct ConstantAndConstantRangePointerTraits {
+  static inline void *getAsVoidPointer(void *P) { return P; }
+
+  static inline void *getFromVoidPointer(void *P) { return P; }
+
+  enum {
+    NumLowBitsAvailable =
+        const_min(detail::ConstantLog2<alignof(Constant)>::value,
+                  detail::ConstantLog2<alignof(ConstantRange)>::value)
+  };
+};
+
+/// Base class for ValueLatticeElement classes.
+///
+/// It contains methods shared between different representations.
+template <class SubTy> class ValueLatticeElementBase {
+protected:
   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".
     undefined,
 
     /// This Value has a specific constant value.  (For constant integers,
     /// constantrange is used instead.  Integer typed constantexprs can appear
     /// as constant.)
     constant,
 
     /// This Value is known to not have the specified value.  (For constant
     /// integers, constantrange is used instead.  As above, integer typed
     /// constantexprs can appear here.)
     notconstant,
 
     /// The Value falls within this range. (Used only for integer typed values.)
     constantrange,
 
     /// We can not precisely model the dynamic values this value might take.
     overdefined
   };
 
-  /// Val: This stores the current lattice value along with the Constant* for
-  /// the constant if this is a 'constant' or 'notconstant' value.
-  ValueLatticeElementTy Tag;
-  Constant *Val;
-  ConstantRange Range;
-
 public:
-  ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
-
-  static ValueLatticeElement get(Constant *C) {
-    ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
-      Res.markConstant(C);
-    return Res;
-  }
-  static ValueLatticeElement getNot(Constant *C) {
-    ValueLatticeElement Res;
-    if (!isa<UndefValue>(C))
-      Res.markNotConstant(C);
-    return Res;
-  }
-  static ValueLatticeElement getRange(ConstantRange CR) {
-    ValueLatticeElement Res;
-    Res.markConstantRange(std::move(CR));
-    return Res;
-  }
-  static ValueLatticeElement getOverdefined() {
-    ValueLatticeElement Res;
-    Res.markOverdefined();
+  static SubTy getRange(ConstantRange CR,
+                        DenseMap<ConstantRange, unsigned> *CRP = nullptr) {
+    SubTy Res;
+    Res.markConstantRange(std::move(CR), CRP);
     return Res;
   }
 
-  bool isUndefined() const { return Tag == undefined; }
-  bool isConstant() const { return Tag == constant; }
-  bool isNotConstant() const { return Tag == notconstant; }
-  bool isConstantRange() const { return Tag == constantrange; }
-  bool isOverdefined() const { return Tag == overdefined; }
+  unsigned getTag() const {
+    return static_cast<const SubTy *>(this)->implGetTag();
+  }
+  bool isUndefined() const { return getTag() == undefined; }
+  bool isConstant() const { return getTag() == constant; }
+  bool isNotConstant() const { return getTag() == notconstant; }
+  bool isConstantRange() const { return getTag() == constantrange; }
+  bool isOverdefined() const { return getTag() == overdefined; }
 
   Constant *getConstant() const {
     assert(isConstant() && "Cannot get the constant of a non-constant!");
-    return Val;
+    return static_cast<const SubTy *>(this)->implGetConstant();
   }
 
   Constant *getNotConstant() const {
     assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
-    return Val;
+    return static_cast<const SubTy *>(this)->implGetConstant();
   }
 
   const ConstantRange &getConstantRange() const {
     assert(isConstantRange() &&
            "Cannot get the constant-range of a non-constant-range!");
-    return Range;
+    return static_cast<const SubTy *>(this)->implGetConstantRange();
   }
 
   Optional<APInt> asConstantInteger() const {
-    if (isConstant() && isa<ConstantInt>(Val)) {
-      return cast<ConstantInt>(Val)->getValue();
-    } else if (isConstantRange() && Range.isSingleElement()) {
-      return *Range.getSingleElement();
+    if (isConstant() && isa<ConstantInt>(getConstant())) {
+      return cast<ConstantInt>(getConstant())->getValue();
+    } else if (isConstantRange() && getConstantRange().isSingleElement()) {
+      return *getConstantRange().getSingleElement();
     }
     return None;
   }
 
 private:
-  void markOverdefined() {
-    if (isOverdefined())
-      return;
-    Tag = overdefined;
-  }
+  SubTy *downcast() { return static_cast<SubTy *>(this); }
 
-  void markConstant(Constant *V) {
+protected:
+  void markConstant(Constant *V, DenseMap<ConstantRange, unsigned> *CRP) {
     assert(V && "Marking constant with NULL");
     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue()));
+      markConstantRange(ConstantRange(CI->getValue()), CRP);
       return;
     }
     if (isa<UndefValue>(V))
       return;
 
     assert((!isConstant() || getConstant() == V) &&
            "Marking constant with different value");
     assert(isUndefined());
-    Tag = constant;
-    Val = V;
+    downcast()->implMarkConstant(V);
   }
 
-  void markNotConstant(Constant *V) {
+  void markNotConstant(Constant *V, DenseMap<ConstantRange, unsigned> *CRP) {
     assert(V && "Marking constant with NULL");
     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
-      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
+      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()), CRP);
       return;
     }
     if (isa<UndefValue>(V))
       return;
 
     assert((!isConstant() || getConstant() != V) &&
            "Marking constant !constant with same value");
     assert((!isNotConstant() || getNotConstant() == V) &&
            "Marking !constant with different value");
     assert(isUndefined() || isConstant());
-    Tag = notconstant;
-    Val = V;
+    downcast()->implMarkNotConstant(V);
   }
 
-  void markConstantRange(ConstantRange NewR) {
+  void markConstantRange(ConstantRange NewR,
+                         DenseMap<ConstantRange, unsigned> *CRP) {
     if (isConstantRange()) {
       if (NewR.isEmptySet())
         markOverdefined();
-      else {
-        Range = std::move(NewR);
-      }
+      else
+        downcast()->implMarkConstantRange(NewR, CRP);
       return;
     }
 
     assert(isUndefined());
     if (NewR.isEmptySet())
       markOverdefined();
-    else {
-      Tag = constantrange;
-      Range = std::move(NewR);
-    }
+    else
+      downcast()->implMarkConstantRange(NewR, CRP);
+
+  void markOverdefined() {
+    if (isOverdefined())
+      return;
+    downcast()->implMarkOverdefined();
   }
 
 public:
   /// Updates this object to approximate both this object and RHS. Returns
   /// true if this object has been changed.
-  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
+  template <class RHSTy>
+  bool mergeIn(const RHSTy &RHS, const DataLayout &DL,
+               DenseMap<ConstantRange, unsigned> *CRP = nullptr) {
     if (RHS.isUndefined() || isOverdefined())
       return false;
     if (RHS.isOverdefined()) {
       markOverdefined();
       return true;
     }
 
     if (isUndefined()) {
-      *this = RHS;
+      *downcast() = SubTy::getFrom(RHS, CRP);
+      assert(getTag() == RHS.getTag());
       return !RHS.isUndefined();
     }
 
     if (isConstant()) {
-      if (RHS.isConstant() && Val == RHS.Val)
+      if (RHS.isConstant() && getConstant() == RHS.getConstant())
         return false;
       markOverdefined();
       return true;
     }
 
     if (isNotConstant()) {
-      if (RHS.isNotConstant() && Val == RHS.Val)
+      if (RHS.isNotConstant() && getNotConstant() == RHS.getNotConstant())
         return false;
       markOverdefined();
       return true;
     }
 
     assert(isConstantRange() && "New ValueLattice type?");
     if (!RHS.isConstantRange()) {
       // We can get here if we've encountered a constantexpr of integer type
       // and merge it with a constantrange.
       markOverdefined();
       return true;
     }
-    ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
+    ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
     if (NewR.isFullSet())
       markOverdefined();
     else
-      markConstantRange(std::move(NewR));
+      markConstantRange(std::move(NewR), CRP);
     return true;
   }
 
-  ConstantInt *getConstantInt() const {
-    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
-           "No integer constant");
-    return cast<ConstantInt>(getConstant());
-  }
-
   bool satisfiesPredicate(CmpInst::Predicate Pred,
-                          const ValueLatticeElement &Other) const {
+                          const ValueLatticeElementBase &Other) const {
     // TODO: share with LVI getPredicateResult.
-
     if (isUndefined() || Other.isUndefined())
       return true;
 
     if (isConstant() && Other.isConstant() && Pred == CmpInst::FCMP_OEQ)
       return getConstant() == Other.getConstant();
 
     // Integer constants are represented as ConstantRanges with single
     // elements.
     if (!isConstantRange() || !Other.isConstantRange())
       return false;
 
     const auto &CR = getConstantRange();
     const auto &OtherCR = Other.getConstantRange();
     return ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR);
   }
 };
 
+class ValueLatticeElement;
+
+class CompactValueLatticeElement
+    : public ValueLatticeElementBase<CompactValueLatticeElement> {
+  friend class ValueLatticeElementBase<ValueLatticeElement>;
+  friend class ValueLatticeElementBase<CompactValueLatticeElement>;
+  /// Val: This stores the current lattice value along with the Constant* for
+  /// the constant if this is a 'constant' or 'notconstant' value.
+  PointerIntPair<void *, 3, unsigned, ConstantAndConstantRangePointerTraits>
+      ValuePtr;
+
+public:
+  CompactValueLatticeElement() : ValuePtr(nullptr, undefined) {}
+  CompactValueLatticeElement(unsigned Tag, Constant *Ptr)
+      : ValuePtr(Ptr, Tag) {}
+  CompactValueLatticeElement(ConstantRange *Ptr)
+      : ValuePtr(Ptr, constantrange) {}
+
+  static CompactValueLatticeElement getOverdefined() {
+    CompactValueLatticeElement Res;
+    Res.markOverdefined();
+    return Res;
+  }
+
+  static CompactValueLatticeElement
+  getFrom(const ValueLatticeElement &C, DenseMap<ConstantRange, unsigned> *CRP);
+
+  static CompactValueLatticeElement
+  getFrom(const CompactValueLatticeElement &C,
+          DenseMap<ConstantRange, unsigned> *CRP = nullptr) {
+    return C;
+  }
+
+private:
+  unsigned implGetTag() const { return ValuePtr.getInt(); }
+
+  Constant *implGetConstant() const {
+    return static_cast<Constant *>(ValuePtr.getPointer());
+  }
+
+  const ConstantRange &implGetConstantRange() const {
+    return *static_cast<ConstantRange *>(ValuePtr.getPointer());
+  }
+
+  void implMarkOverdefined() { ValuePtr.setInt(overdefined); }
+
+  void implMarkConstant(Constant *V) {
+    ValuePtr.setInt(constant);
+    ValuePtr.setPointer(V);
+  }
+
+  void implMarkNotConstant(Constant *V) {
+    ValuePtr.setInt(notconstant);
+    ValuePtr.setPointer(V);
+  }
+
+  void implMarkConstantRange(ConstantRange NewR,
+                             DenseMap<ConstantRange, unsigned> *CRP) {
+    assert(CRP && "Need constant range pool!");
+    ValuePtr.setInt(constantrange);
+    ValuePtr.setPointer(addConstantRange(NewR, *CRP));
+  }
+};
+
+class ValueLatticeElement
+    : public ValueLatticeElementBase<ValueLatticeElement> {
+  friend class ValueLatticeElementBase<ValueLatticeElement>;
+  friend class ValueLatticeElementBase<CompactValueLatticeElement>;
+  /// Val: This stores the current lattice value along with the Constant* for
+  /// the constant if this is a 'constant' or 'notconstant' value.
+  ValueLatticeElementTy Tag;
+  Constant *Val;
+  ConstantRange Range;
+
+public:
+  ValueLatticeElement() : Tag(undefined), Val(nullptr), Range(1, true) {}
+
+  static ValueLatticeElement get(Constant *C) {
+    ValueLatticeElement Res;
+    if (!isa<UndefValue>(C))
+      Res.markConstant(C, nullptr);
+    return Res;
+  }
+
+  static ValueLatticeElement getNot(Constant *C) {
+    ValueLatticeElement Res;
+    if (!isa<UndefValue>(C))
+      Res.markNotConstant(C, nullptr);
+    return Res;
+  }
+
+  static ValueLatticeElement getOverdefined() {
+    ValueLatticeElement Res;
+    Res.markOverdefined();
+    return Res;
+  }
+
+private:
+  unsigned implGetTag() const { return Tag; }
+
+  Constant *implGetConstant() const { return Val; }
+
+  const ConstantRange &implGetConstantRange() const { return Range; }
+
+  void implMarkOverdefined() { Tag = overdefined; }
+
+  void implMarkConstant(Constant *V) {
+    Tag = constant;
+    Val = V;
+  }
+
+  void implMarkNotConstant(Constant *V) {
+    Tag = notconstant;
+    Val = V;
+  }
+
+  void implMarkConstantRange(ConstantRange NewR,
+                             DenseMap<ConstantRange, unsigned> *CRP) {
+    Tag = constantrange;
+    Range = std::move(NewR);
+  }
+
+public:
+  static ValueLatticeElement
+  getFrom(const ValueLatticeElement &C,
+          DenseMap<ConstantRange, unsigned> *CRP = nullptr) {
+    return C;
+  }
+
+  static ValueLatticeElement
+  getFrom(const CompactValueLatticeElement &C,
+          DenseMap<ConstantRange, unsigned> *CRP = nullptr) {
+    if (C.isUndefined())
+      return ValueLatticeElement();
+    if (C.isConstant())
+      return ValueLatticeElement::get(C.getConstant());
+    if (C.isNotConstant())
+      return ValueLatticeElement::getNot(C.getNotConstant());
+    if (C.isConstantRange())
+      return ValueLatticeElement::getRange(C.getConstantRange());
+
+    return ValueLatticeElement::getOverdefined();
+  }
+
+  CompactValueLatticeElement
+  toCompact(DenseMap<ConstantRange, unsigned> &CRP) const {
+    if (isUndefined())
+      return CompactValueLatticeElement();
+    if (isConstant())
+      return CompactValueLatticeElement(constant, getConstant());
+    if (isNotConstant())
+      return CompactValueLatticeElement(notconstant, getNotConstant());
+    if (isConstantRange())
+      return CompactValueLatticeElement(
+          addConstantRange(getConstantRange(), CRP));
+
+    return CompactValueLatticeElement::getOverdefined();
+  }
+
+  ConstantInt *getConstantInt() const {
+    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
+           "No integer constant");
+    return cast<ConstantInt>(getConstant());
+  }
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const CompactValueLatticeElement &Val);
 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
 
 } // end namespace llvm
 #endif

lib/Analysis/LazyValueInfo.cpp

 /// * This method does not promise to return the most precise possible lattice
 ///   value implied by A and B.  It is allowed to return any lattice element
 ///   which is at least as strong as *either* A or B (unless our facts
 ///   conflict, see below).
 /// * Due to unreachable code, the intersection of two lattice values could be
 ///   contradictory.  If this happens, we return some valid lattice value so as
 ///   not confuse the rest of LVI.  Ideally, we'd always return Undefined, but
 ///   we do not make this guarantee.  TODO: This would be a useful enhancement.
-static ValueLatticeElement intersect(const ValueLatticeElement &A,
-                                     const ValueLatticeElement &B) {
+template <class T> static T intersect(const T &A, const T &B) {
   // Undefined is the strongest state.  It means the value is known to be along
   // an unreachable path.
   if (A.isUndefined())
     return A;
   if (B.isUndefined())
     return B;
 
   // If we gave up for one, but got a useable fact from the other, use it.
class LazyValueInfoCache {
     /// This is all of the cached block information for exactly one Value*.
     /// The entries are sorted by the BasicBlock* of the
     /// entries, allowing us to do a lookup with a binary search.
     /// Over-defined lattice values are recorded in OverDefinedCache to reduce
     /// memory overhead.
     struct ValueCacheEntryTy {
       ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
       LVIValueHandle Handle;
-      SmallDenseMap<PoisoningVH<BasicBlock>, ValueLatticeElement, 4> BlockVals;
+      SmallDenseMap<PoisoningVH<BasicBlock>, CompactValueLatticeElement, 4>
+          BlockVals;
     };
 
     /// This tracks, on a per-block basis, the set of values that are
     /// over-defined at the end of that block.
     typedef DenseMap<PoisoningVH<BasicBlock>, SmallPtrSet<Value *, 4>>
         OverDefinedCacheTy;
     /// Keep track of all blocks that we have ever seen, so we
     /// don't spend time removing unused blocks from our caches.
     DenseSet<PoisoningVH<BasicBlock> > SeenBlocks;
 
     /// This is all of the cached information for all values,
     /// mapped from Value* to key information.
     DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
     OverDefinedCacheTy OverDefinedCache;
 
 
   public:
     void insertResult(Value *Val, BasicBlock *BB,
-                      const ValueLatticeElement &Result) {
+                      const CompactValueLatticeElement &Result) {
       SeenBlocks.insert(BB);
 
       // Insert over-defined values into their own cache to reduce memory
       // overhead.
       if (Result.isOverdefined())
         OverDefinedCache[BB].insert(Val);
       else {
         auto It = ValueCache.find_as(Val);
bool hasCachedValueInfo(Value *V, BasicBlock *BB) const {
 
       auto I = ValueCache.find_as(V);
       if (I == ValueCache.end())
         return false;
 
       return I->second->BlockVals.count(BB);
     }
 
-    ValueLatticeElement getCachedValueInfo(Value *V, BasicBlock *BB) const {
+    CompactValueLatticeElement getCachedValueInfo(Value *V,
+                                                  BasicBlock *BB) const {
       if (isOverdefined(V, BB))
-        return ValueLatticeElement::getOverdefined();
+        return CompactValueLatticeElement::getOverdefined();
 
       auto I = ValueCache.find_as(V);
       if (I == ValueCache.end())
-        return ValueLatticeElement();
+        return CompactValueLatticeElement();
       auto BBI = I->second->BlockVals.find(BB);
       if (BBI == I->second->BlockVals.end())
-        return ValueLatticeElement();
+        return CompactValueLatticeElement();
       return BBI->second;
     }
 
     /// clear - Empty the cache.
     void clear() {
       SeenBlocks.clear();
       ValueCache.clear();
       OverDefinedCache.clear();
class LazyValueInfoImpl {
     /// 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;
 
+    DenseMap<ConstantRange, unsigned> ConstantRangePool;
+
     /// Push BV onto BlockValueStack unless it's already in there.
     /// Returns true on success.
     bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
       if (!BlockValueSet.insert(BV).second)
         return false;  // It's already in the stack.
 
       DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
                    << "\n");
       BlockValueStack.push_back(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.
 
+    CompactValueLatticeElement getBlockValueCompact(Value *Val, BasicBlock *BB);
     ValueLatticeElement getBlockValue(Value *Val, BasicBlock *BB);
     bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
                       ValueLatticeElement &Result, Instruction *CxtI = nullptr);
     bool hasBlockValue(Value *Val, BasicBlock *BB);
 
     // These methods process one work item and may add more. A false value
     // returned means that the work item was not completely processed and must
     // be revisited after going through the new items.
     bool solveBlockValue(Value *Val, BasicBlock *BB);
     bool solveBlockValueImpl(ValueLatticeElement &Res, Value *Val,
                              BasicBlock *BB);
     bool solveBlockValueNonLocal(ValueLatticeElement &BBLV, Value *Val,
                                  BasicBlock *BB);
     bool solveBlockValuePHINode(ValueLatticeElement &BBLV, PHINode *PN,
                                 BasicBlock *BB);
     bool solveBlockValueSelect(ValueLatticeElement &BBLV, SelectInst *S,
                                BasicBlock *BB);
     bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
                                  BasicBlock *BB);
     bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
                              BasicBlock *BB);
-  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
-                                                     ValueLatticeElement &BBLV,
-                                                     Instruction *BBI);
+    template <class T>
+    void intersectAssumeOrGuardBlockValueConstantRange(
+        Value *Val, T &BBLV, Instruction *BBI,
+        DenseMap<ConstantRange, unsigned> *CRP = nullptr);
 
     void solve();
 
   public:
     /// This is the query interface to determine the lattice
     /// value for the specified Value* at the end of the specified block.
     ValueLatticeElement getValueInBlock(Value *V, BasicBlock *BB,
                                         Instruction *CxtI = nullptr);
 
     /// This is the query interface to determine the lattice
void eraseBlock(BasicBlock *BB) {
       TheCache.eraseBlock(BB);
     }
 
     /// This is the update interface to inform the cache that an edge from
     /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 
     LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
-                       DominatorTree *DT = nullptr)
-        : AC(AC), DL(DL), DT(DT) {}
+        : ConstantRangePool(), AC(AC), DL(DL), DT(DT) {}
   };
 } // end anonymous namespace
 
 
 void LazyValueInfoImpl::solve() {
   SmallVector<std::pair<BasicBlock *, Value *>, 8> StartingStack(
       BlockValueStack.begin(), BlockValueStack.end());
 
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) {
       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());
+                              CompactValueLatticeElement::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!");

 bool LazyValueInfoImpl::hasBlockValue(Value *Val, BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
   if (isa<Constant>(Val))
     return true;
 
   return TheCache.hasCachedValueInfo(Val, BB);
 }
 
+CompactValueLatticeElement
+LazyValueInfoImpl::getBlockValueCompact(Value *Val, BasicBlock *BB) {
+  // If already a constant, there is nothing to compute.
+  if (Constant *VC = dyn_cast<Constant>(Val))
+    return CompactValueLatticeElement::getFrom(ValueLatticeElement::get(VC),
+                                               &ConstantRangePool);
+
+  return TheCache.getCachedValueInfo(Val, BB);
+}
+
 ValueLatticeElement LazyValueInfoImpl::getBlockValue(Value *Val,
                                                      BasicBlock *BB) {
   // If already a constant, there is nothing to compute.
   if (Constant *VC = dyn_cast<Constant>(Val))
     return ValueLatticeElement::get(VC);
 
-  return TheCache.getCachedValueInfo(Val, BB);
+  return ValueLatticeElement::getFrom(getBlockValueCompact(Val, BB));
 }
 
 static ValueLatticeElement getFromRangeMetadata(Instruction *BBI) {
   switch (BBI->getOpcode()) {
   default: break;
   case Instruction::Load:
   case Instruction::Call:
   case Instruction::Invoke:
bool LazyValueInfoImpl::solveBlockValue(Value *Val, BasicBlock *BB) {
 
   // Hold off inserting this value into the Cache in case we have to return
   // false and come back later.
   ValueLatticeElement Res;
   if (!solveBlockValueImpl(Res, Val, BB))
     // Work pushed, will revisit
     return false;
 
-  TheCache.insertResult(Val, BB, Res);
+  TheCache.insertResult(
+      Val, BB, CompactValueLatticeElement::getFrom(Res, &ConstantRangePool));
   return true;
 }
 
 bool LazyValueInfoImpl::solveBlockValueImpl(ValueLatticeElement &Res,
                                             Value *Val, BasicBlock *BB) {
 
   Instruction *BBI = dyn_cast<Instruction>(Val);
   if (!BBI || BBI->getParent() != BB)
bool LazyValueInfoImpl::solveBlockValuePHINode(ValueLatticeElement &BBLV,
   BBLV = Result;
   return true;
 }
 
 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
+// the program, intersect those constraints with BBLV.
+// BBLV can be either a CompactValueLatticeElement or CompactValueLatticeElement
+// and we do conversion on demand.
+template <class VLETy>
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
-        Value *Val, ValueLatticeElement &BBLV, Instruction *BBI) {
+    Value *Val, VLETy &BBLV, Instruction *BBI,
+    DenseMap<ConstantRange, unsigned> *CRP) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
 
   for (auto &AssumeVH : AC->assumptionsFor(Val)) {
     if (!AssumeVH)
       continue;
     auto *I = cast<CallInst>(AssumeVH);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
-    BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
+    BBLV = VLETy::getFrom(
+        intersect(ValueLatticeElement::getFrom(BBLV),
+                  getValueFromCondition(Val, I->getArgOperand(0))),
+        CRP);
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(
           Intrinsic::getName(Intrinsic::experimental_guard));
   if (!GuardDecl || GuardDecl->use_empty())
     return;
 
   for (Instruction &I : make_range(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));
+      BBLV = VLETy::getFrom(intersect(ValueLatticeElement::getFrom(BBLV),
+                                      getValueFromCondition(Val, Cond)),
+                            CRP);
   }
 }
 
 bool LazyValueInfoImpl::solveBlockValueSelect(ValueLatticeElement &BBLV,
                                               SelectInst *SI, BasicBlock *BB) {
 
   // Recurse on our inputs if needed
   if (!hasBlockValue(SI->getTrueValue(), BB)) {
     if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
       return false;
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
-  ValueLatticeElement TrueVal = getBlockValue(SI->getTrueValue(), BB);
+  auto CompactTrueVal = getBlockValueCompact(SI->getTrueValue(), BB);
   // 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()) {
+  if (CompactTrueVal.isOverdefined()) {
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
   if (!hasBlockValue(SI->getFalseValue(), BB)) {
     if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
       return false;
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
-  ValueLatticeElement FalseVal = getBlockValue(SI->getFalseValue(), BB);
+  auto CompactFalseVal = getBlockValueCompact(SI->getFalseValue(), BB);
   // 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()) {
+  if (CompactFalseVal.isOverdefined()) {
     BBLV = ValueLatticeElement::getOverdefined();
     return true;
   }
 
-  if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
-    const ConstantRange &TrueCR = TrueVal.getConstantRange();
-    const ConstantRange &FalseCR = FalseVal.getConstantRange();
+  if (CompactTrueVal.isConstantRange() && CompactFalseVal.isConstantRange()) {
+    const ConstantRange &TrueCR = CompactTrueVal.getConstantRange();
+    const ConstantRange &FalseCR = CompactFalseVal.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 = [&]() {
if (CompactTrueVal.isConstantRange() && CompactFalseVal.isConstantRange()) {
 
     // TODO: ABS, NABS from the SelectPatternResult
   }
 
   // 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));
+  auto TrueVal =
+      intersect(ValueLatticeElement::getFrom(CompactTrueVal),
+  auto FalseVal =
+      intersect(ValueLatticeElement::getFrom(CompactFalseVal),
 
   // 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 (!hasBlockValue(CI->getOperand(0), BB))
     if (pushBlockValue(std::make_pair(BB, CI->getOperand(0))))
       // More work to do before applying this transfer rule.
       return false;
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(CI->getOperand(0)->getType());
   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
   if (hasBlockValue(CI->getOperand(0), BB)) {
-    ValueLatticeElement LHSVal = getBlockValue(CI->getOperand(0), BB);
-    intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal,
-                                                  CI);
+    auto LHSVal = getBlockValueCompact(CI->getOperand(0), BB);
+    intersectAssumeOrGuardBlockValueConstantRange(CI->getOperand(0), LHSVal, CI,
+                                                  &ConstantRangePool);
     if (LHSVal.isConstantRange())
       LHSRange = LHSVal.getConstantRange();
   }
 
   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
if (!hasBlockValue(BO->getOperand(0), BB))
     if (pushBlockValue(std::make_pair(BB, BO->getOperand(0))))
       // More work to do before applying this transfer rule.
       return false;
 
   const unsigned OperandBitWidth =
     DL.getTypeSizeInBits(BO->getOperand(0)->getType());
   ConstantRange LHSRange = ConstantRange(OperandBitWidth);
   if (hasBlockValue(BO->getOperand(0), BB)) {
-    ValueLatticeElement LHSVal = getBlockValue(BO->getOperand(0), BB);
-    intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal,
-                                                  BO);
+    CompactValueLatticeElement LHSVal =
+        getBlockValueCompact(BO->getOperand(0), BB);
+    intersectAssumeOrGuardBlockValueConstantRange(BO->getOperand(0), LHSVal, BO,
+                                                  &ConstantRangePool);
     if (LHSVal.isConstantRange())
       LHSRange = LHSVal.getConstantRange();
   }
 
   ConstantInt *RHS = cast<ConstantInt>(BO->getOperand(1));
   ConstantRange RHSRange = ConstantRange(RHS->getValue());
 
   // NOTE: We're currently limited by the set of operations that ConstantRange

lib/Analysis/ValueLattice.cpp

 //===- ValueLattice.cpp - Value constraint analysis -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/ValueLattice.h"
+#include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
+
+CompactValueLatticeElement
+CompactValueLatticeElement::getFrom(const ValueLatticeElement &C,
+                                    DenseMap<ConstantRange, unsigned> *CRP) {
+  assert(CRP &&
+         "Need constant range pool to convert to CompactValueLatticeElement.");
+  if (C.isUndefined())
+    return CompactValueLatticeElement();
+  if (C.isConstant())
+    return CompactValueLatticeElement(constant, C.getConstant());
+  if (C.isNotConstant())
+    return CompactValueLatticeElement(notconstant, C.getNotConstant());
+  if (C.isConstantRange())
+    return CompactValueLatticeElement(
+        addConstantRange(C.getConstantRange(), *CRP));
+
+  return CompactValueLatticeElement::getOverdefined();
+}
+
+raw_ostream &operator<<(raw_ostream &OS,
+                        const CompactValueLatticeElement &Val) {
+  return OS << ValueLatticeElement::getFrom(Val);
+}
+
 raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val) {
   if (Val.isUndefined())
     return OS << "undefined";
   if (Val.isOverdefined())
     return OS << "overdefined";
 
   if (Val.isNotConstant())
     return OS << "notconstant<" << *Val.getNotConstant() << ">";
   if (Val.isConstantRange())
     return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
+
 } // end namespace llvm

lib/Transforms/Scalar/SCCP.cpp

public:
   }
 
   void markForcedConstant(Constant *V) {
     assert(isUnknown() && "Can't force a defined value!");
     Val.setInt(forcedconstant);
     Val.setPointer(V);
   }
 
-  ValueLatticeElement toValueLattice() const {
+  CompactValueLatticeElement
+  toValueLattice(DenseMap<ConstantRange, unsigned> &CRP) const {
     if (isOverdefined())
-      return ValueLatticeElement::getOverdefined();
+      return ValueLatticeElement::getOverdefined().toCompact(CRP);
     if (isConstant())
-      return ValueLatticeElement::get(getConstant());
-    return ValueLatticeElement();
+      return ValueLatticeElement::get(getConstant()).toCompact(CRP);
+    return CompactValueLatticeElement();
   }
 };
 
 //===----------------------------------------------------------------------===//
 //
 /// SCCPSolver - This class is a general purpose solver for Sparse Conditional
 /// Constant Propagation.
 ///
 class SCCPSolver : public InstVisitor<SCCPSolver> {
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   SmallPtrSet<BasicBlock *, 8> BBExecutable; // The BBs that are executable.
   DenseMap<Value *, LatticeVal> ValueState;  // The state each value is in.
   // The state each parameter is in.
-  DenseMap<Value *, ValueLatticeElement> ParamState;
+  DenseMap<Value *, CompactValueLatticeElement> ParamState;
 
   /// StructValueState - This maintains ValueState for values that have
   /// StructType, for example for formal arguments, calls, insertelement, etc.
   DenseMap<std::pair<Value *, unsigned>, LatticeVal> StructValueState;
 
   /// GlobalValue - If we are tracking any values for the contents of a global
   /// variable, we keep a mapping from the constant accessor to the element of
   /// the global, to the currently known value.  If the value becomes
class SCCPSolver : public InstVisitor<SCCPSolver> {
   // The BasicBlock work list
   SmallVector<BasicBlock *, 64>  BBWorkList;
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   DenseSet<Edge> KnownFeasibleEdges;
 
+  DenseMap<ConstantRange, unsigned> ConstantRangePool;
+
 public:
   SCCPSolver(const DataLayout &DL, const TargetLibraryInfo *tli)
       : DL(DL), TLI(tli) {}
 
   /// MarkBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   ///
   /// This returns true if the block was not considered live before.
std::vector<LatticeVal> getStructLatticeValueFor(Value *V) const {
     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
       auto I = StructValueState.find(std::make_pair(V, i));
       assert(I != StructValueState.end() && "Value not in valuemap!");
       StructValues.push_back(I->second);
     }
     return StructValues;
   }
 
-  ValueLatticeElement getLatticeValueFor(Value *V) {
+  CompactValueLatticeElement getLatticeValueFor(Value *V) {
     assert(!V->getType()->isStructTy() &&
            "Should use getStructLatticeValueFor");
-    std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
-        PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
-    ValueLatticeElement &LV = PI.first->second;
+    std::pair<DenseMap<Value *, CompactValueLatticeElement>::iterator, bool>
+        PI = ParamState.insert(std::make_pair(V, CompactValueLatticeElement()));
+    CompactValueLatticeElement &LV = PI.first->second;
     if (PI.second) {
       DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
       assert(I != ValueState.end() &&
              "V not found in ValueState nor Paramstate map!");
-      LV = I->second.toValueLattice();
+      LV = I->second.toValueLattice(ConstantRangePool);
     }
 
     return LV;
   }
 
   /// getTrackedRetVals - Get the inferred return value map.
   const DenseMap<Function*, LatticeVal> &getTrackedRetVals() {
     return TrackedRetVals;
if (auto *C = dyn_cast<Constant>(V)) {
       if (!isa<UndefValue>(V))
         LV.markConstant(C);          // Constants are constant
     }
 
     // All others are underdefined by default.
     return LV;
   }
 
-  ValueLatticeElement &getParamState(Value *V) {
+  CompactValueLatticeElement &getParamState(Value *V) {
     assert(!V->getType()->isStructTy() && "Should use getStructValueState");
 
-    std::pair<DenseMap<Value*, ValueLatticeElement>::iterator, bool>
-        PI = ParamState.insert(std::make_pair(V, ValueLatticeElement()));
-    ValueLatticeElement &LV = PI.first->second;
+    std::pair<DenseMap<Value *, CompactValueLatticeElement>::iterator, bool>
+        PI = ParamState.insert(std::make_pair(V, CompactValueLatticeElement()));
+    CompactValueLatticeElement &LV = PI.first->second;
     if (PI.second)
-      LV = getValueState(V).toValueLattice();
+      LV = getValueState(V).toValueLattice(ConstantRangePool);
 
     return LV;
   }
 
   /// getStructValueState - Return the LatticeVal object that corresponds to the
   /// value/field pair.  This function handles the case when the value hasn't
   /// been seen yet by properly seeding constants etc.
   LatticeVal &getStructValueState(Value *V, unsigned i) {
for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
       if (auto *STy = dyn_cast<StructType>(AI->getType())) {
         for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
           LatticeVal CallArg = getStructValueState(*CAI, i);
           mergeInValue(getStructValueState(&*AI, i), &*AI, CallArg);
         }
       } else {
         // Most other parts of the Solver still only use the simpler value
         // lattice, so we propagate changes for parameters to both lattices.
-        getParamState(&*AI).mergeIn(getValueState(*CAI).toValueLattice(), DL);
+        getParamState(&*AI).mergeIn(
+            getValueState(*CAI).toValueLattice(ConstantRangePool), DL,
+            &ConstantRangePool);
         mergeInValue(&*AI, getValueState(*CAI));
       }
     }
   }
 
   // If this is a single/zero retval case, see if we're tracking the function.
   if (auto *STy = dyn_cast<StructType>(F->getReturnType())) {
     if (!MRVFunctionsTracked.count(F))

 
 static bool tryToReplaceWithConstantRange(SCCPSolver &Solver, Value *V) {
   bool Changed = false;
 
   // Currently we only use range information for integer values.
   if (!V->getType()->isIntegerTy())
     return false;
 
-  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+  const CompactValueLatticeElement &IV = Solver.getLatticeValueFor(V);
   if (!IV.isConstantRange())
     return false;
 
   for (auto UI = V->uses().begin(), E = V->uses().end(); UI != E;) {
     const Use &U = *UI++;
     auto *Icmp = dyn_cast<ICmpInst>(U.getUser());
     if (!Icmp || !Solver.isBlockExecutable(Icmp->getParent()))
       continue;
if (V->getType()->isStructTy()) {
     for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
       LatticeVal V = IVs[i];
       ConstVals.push_back(V.isConstant()
                               ? V.getConstant()
                               : UndefValue::get(ST->getElementType(i)));
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
-    const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+    const CompactValueLatticeElement &IV = Solver.getLatticeValueFor(V);
     if (IV.isOverdefined())
       return false;
 
     if (IV.isConstantRange()) {
       if (IV.getConstantRange().isSingleElement())
         Const =
             ConstantInt::get(V->getType(), IV.asConstantInteger().getValue());
       else