Index: include/llvm/Analysis/ValueLattice.h
===================================================================
--- include/llvm/Analysis/ValueLattice.h
+++ include/llvm/Analysis/ValueLattice.h
@@ -47,7 +47,35 @@
   }
 };
 
-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
@@ -72,80 +100,56 @@
     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))
@@ -154,14 +158,13 @@
     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))
@@ -172,33 +175,38 @@
     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()) {
@@ -207,19 +215,20 @@
     }
 
     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;
@@ -232,24 +241,17 @@
       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;
 
@@ -267,6 +269,173 @@
   }
 };
 
+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
Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -89,8 +89,7 @@
 ///   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())
@@ -160,7 +159,8 @@
     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
@@ -179,7 +179,7 @@
 
   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
@@ -217,16 +217,17 @@
       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;
     }
 
@@ -387,6 +388,8 @@
     /// 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) {
@@ -403,32 +406,34 @@
     const DataLayout &DL; ///< A mandatory DataLayout
     DominatorTree *DT;    ///< An optional DT pointer.
 
-  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,
+    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 solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
+    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 solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
-                           BasicBlock *BB);
-  void intersectAssumeOrGuardBlockValueConstantRange(Value *Val,
-                                                     ValueLatticeElement &BBLV,
-                                                     Instruction *BBI);
+    bool solveBlockValueBinaryOp(ValueLatticeElement &BBLV, BinaryOperator *BBI,
+                                 BasicBlock *BB);
+    bool solveBlockValueCast(ValueLatticeElement &BBLV, CastInst *CI,
+                             BasicBlock *BB);
+    template <class T>
+    void intersectAssumeOrGuardBlockValueConstantRange(
+        Value *Val, T &BBLV, Instruction *BBI,
+        DenseMap<ConstantRange, unsigned> *CRP = nullptr);
 
-  void solve();
+    void solve();
 
   public:
     /// This is the query interface to determine the lattice
@@ -469,8 +474,8 @@
     void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
 
     LazyValueInfoImpl(AssumptionCache *AC, const DataLayout &DL,
-                       DominatorTree *DT = nullptr)
-        : AC(AC), DL(DL), DT(DT) {}
+                      DominatorTree *DT = nullptr)
+        : ConstantRangePool(), AC(AC), DL(DL), DT(DT) {}
   };
 } // end anonymous namespace
 
@@ -496,7 +501,7 @@
       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();
@@ -532,13 +537,23 @@
   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) {
@@ -580,7 +595,8 @@
     // Work pushed, will revisit
     return false;
 
-  TheCache.insertResult(Val, BB, Res);
+  TheCache.insertResult(
+      Val, BB, CompactValueLatticeElement::getFrom(Res, &ConstantRangePool));
   return true;
 }
 
@@ -778,9 +794,13 @@
                                                  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;
@@ -792,7 +812,10 @@
     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
@@ -805,7 +828,9 @@
                                    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);
   }
 }
 
@@ -819,10 +844,10 @@
     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;
   }
@@ -833,17 +858,17 @@
     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);
@@ -876,10 +901,12 @@
   // 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),
+                getValueFromCondition(SI->getTrueValue(), Cond, true));
+  auto FalseVal =
+      intersect(ValueLatticeElement::getFrom(CompactFalseVal),
+                getValueFromCondition(SI->getFalseValue(), Cond, false));
 
   // Handle clamp idioms such as:
   //   %24 = constantrange<0, 17>
@@ -969,9 +996,9 @@
     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();
   }
@@ -1027,9 +1054,10 @@
     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();
   }
Index: lib/Analysis/ValueLattice.cpp
===================================================================
--- lib/Analysis/ValueLattice.cpp
+++ lib/Analysis/ValueLattice.cpp
@@ -8,8 +8,33 @@
 //===----------------------------------------------------------------------===//
 
 #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";
@@ -23,4 +48,5 @@
               << Val.getConstantRange().getUpper() << ">";
   return OS << "constant<" << *Val.getConstant() << ">";
 }
+
 } // end namespace llvm
Index: lib/Transforms/Scalar/SCCP.cpp
===================================================================
--- lib/Transforms/Scalar/SCCP.cpp
+++ lib/Transforms/Scalar/SCCP.cpp
@@ -178,12 +178,13 @@
     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();
   }
 };
 
@@ -198,7 +199,7 @@
   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.
@@ -246,6 +247,8 @@
   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) {}
@@ -325,17 +328,17 @@
     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;
@@ -467,14 +470,14 @@
     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;
   }
@@ -1207,7 +1210,9 @@
       } 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));
       }
     }
@@ -1605,7 +1610,7 @@
   if (!V->getType()->isIntegerTy())
     return false;
 
-  const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+  const CompactValueLatticeElement &IV = Solver.getLatticeValueFor(V);
   if (!IV.isConstantRange())
     return false;
 
@@ -1652,7 +1657,7 @@
     }
     Const = ConstantStruct::get(ST, ConstVals);
   } else {
-    const ValueLatticeElement &IV = Solver.getLatticeValueFor(V);
+    const CompactValueLatticeElement &IV = Solver.getLatticeValueFor(V);
     if (IV.isOverdefined())
       return false;