Some additional cleanups with method names.

Renamed ExprValue to RValue, as all expression values are RValues, and this
keeps with the C terminology (renamed old "RValue" class to "NonLValue").

Introduced "ConcreteInt", a class that represents a concrete, integer
constant as an RValue.

Temporarily removed classes to represent set of possible constants and set of !=
constants. Will replace with a more general class representing a set of
constraints.

Added some foundational code to track "symbolic" values, which are used to
accrue constraints on an abstract value that is shared between multiple
variables.  e.g:

   x = y;      // at this point "x" and "y" share the same "value"
   if (x > 1) 
     ...       // at this point, the value shared by "x" and "y" is "> 1".




git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@46466 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp
index 13d10f2..1b2545a 100644
--- a/Analysis/GRConstants.cpp
+++ b/Analysis/GRConstants.cpp
@@ -47,33 +47,61 @@
 ///  Stmt*.  Use cast<> or dyn_cast<> to get actual pointer type
 //===----------------------------------------------------------------------===//
 namespace {
+
+typedef uintptr_t SymbolID;
   
 class VISIBILITY_HIDDEN ValueKey {
-  uintptr_t Raw;
-  
+  uintptr_t Raw;  
   void operator=(const ValueKey& RHS); // Do not implement.
+  
 public:
-  enum  Kind { IsSubExpr=0x0, IsBlkExpr=0x1, IsDecl=0x2, Flags=0x3 };
-  inline void* getPtr() const { return reinterpret_cast<void*>(Raw & ~Flags); }
-  inline Kind getKind() const { return (Kind) (Raw & Flags); }
+  enum  Kind { IsSubExpr=0x0, IsBlkExpr=0x1, IsDecl=0x2, // L-Value Bindings.
+               IsSymbol=0x3, // Symbol Bindings.
+               Flags=0x3 };
+  
+  inline Kind getKind() const {
+    return (Kind) (Raw & Flags);
+  }
+  
+  inline void* getPtr() const { 
+    assert (getKind() != IsSymbol);
+    return reinterpret_cast<void*>(Raw & ~Flags);
+  }
+  
+  inline SymbolID getSymbolID() const {
+    assert (getKind() == IsSymbol);
+    return Raw >> 2;
+  }
   
   ValueKey(const ValueDecl* VD)
-    : Raw(reinterpret_cast<uintptr_t>(VD) | IsDecl) { assert(VD); }
+    : Raw(reinterpret_cast<uintptr_t>(VD) | IsDecl) {
+      assert(VD && "ValueDecl cannot be NULL.");
+    }
 
   ValueKey(Stmt* S, bool isBlkExpr = false) 
     : Raw(reinterpret_cast<uintptr_t>(S) | (isBlkExpr ? IsBlkExpr : IsSubExpr)){
-      assert(S);
+      assert(S && "Tracked statement cannot be NULL.");
     }
   
+  ValueKey(SymbolID V)
+    : Raw((V << 2) | IsSymbol) {}  
+  
+  bool isSymbol()  const { return getKind() == IsSymbol; }
   bool isSubExpr() const { return getKind() == IsSubExpr; }
-  bool isDecl() const { return getKind() == IsDecl; }
+  bool isDecl()    const { return getKind() == IsDecl; }
   
   inline void Profile(llvm::FoldingSetNodeID& ID) const {
-    ID.AddPointer(getPtr());
+    ID.AddInteger(isSymbol() ? 1 : 0);
+
+    if (isSymbol())
+      ID.AddInteger((uint64_t) getSymbolID());
+    else    
+      ID.AddPointer(getPtr());
   }
   
   inline bool operator==(const ValueKey& X) const {
-    return getPtr() == X.getPtr();
+    return isSymbol() ? getSymbolID() == X.getSymbolID()
+                      : getPtr() == X.getPtr();
   }
   
   inline bool operator!=(const ValueKey& X) const {
@@ -81,18 +109,10 @@
   }
   
   inline bool operator<(const ValueKey& X) const { 
-    Kind k = getKind(), Xk = X.getKind();
+    if (isSymbol())
+      return X.isSymbol() ? getSymbolID() < X.getSymbolID() : false;
     
-    if (k == IsDecl) {
-      if (Xk != IsDecl)
-        return false;
-    }
-    else {
-      if (Xk == IsDecl)
-        return true;
-    }
-
-    return getPtr() < X.getPtr();    
+    return getPtr() < X.getPtr();
   }
 };
 } // end anonymous namespace
@@ -103,7 +123,7 @@
     return V.getKind() == ValueKey::IsDecl;
   }
   template<> inline bool isa<Stmt,ValueKey>(const ValueKey& V) {
-    return ((unsigned) V.getKind()) != ValueKey::IsDecl;
+    return ((unsigned) V.getKind()) < ValueKey::IsDecl;
   }
   template<> struct VISIBILITY_HIDDEN cast_retty_impl<ValueDecl,ValueKey> {
     typedef const ValueDecl* ret_type;
@@ -129,39 +149,50 @@
 
   
 class VISIBILITY_HIDDEN ValueManager {
-  APSIntSetTy::Factory APSIntSetFactory;
   ASTContext* Ctx;
   
+  typedef  llvm::FoldingSet<llvm::FoldingSetNodeWrapper<APSInt> > APSIntSetTy;
+  APSIntSetTy APSIntSet;
+  
+  llvm::BumpPtrAllocator BPAlloc;
+  
 public:
   ValueManager() {}
-  ~ValueManager() {}
+  ~ValueManager();
   
   void setContext(ASTContext* ctx) { Ctx = ctx; }
   ASTContext* getContext() const { return Ctx; }
   
-  APSIntSetTy GetEmptyAPSIntSet() {
-    return APSIntSetFactory.GetEmptySet();
-  }
-  
-  APSIntSetTy AddToSet(const APSIntSetTy& Set, const APSInt& Val) {
-    return APSIntSetFactory.Add(Set, Val);
-  }
+  APSInt& getValue(const APSInt& X);      
+
 };
 } // end anonymous namespace
 
-template <template <typename T> class OpTy>
-static inline APSIntSetTy APSIntSetOp(ValueManager& ValMgr,
-                                      APSIntSetTy S1, APSIntSetTy S2) {
+ValueManager::~ValueManager() {
+  // Note that the dstor for the contents of APSIntSet will never be called,
+  // so we iterate over the set and invoke the dstor for each APSInt.  This
+  // frees an aux. memory allocated to represent very large constants.
+  for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I)
+    I->getValue().~APSInt();
+}
   
-  APSIntSetTy M = ValMgr.GetEmptyAPSIntSet();
   
-  OpTy<APSInt> Op;
+
+APSInt& ValueManager::getValue(const APSInt& X) {
+  llvm::FoldingSetNodeID ID;
+  void* InsertPos;
+  typedef llvm::FoldingSetNodeWrapper<APSInt> FoldNodeTy;
   
-  for (APSIntSetTy::iterator I1=S1.begin(), E1=S2.end(); I1!=E1; ++I1)
-    for (APSIntSetTy::iterator I2=S2.begin(), E2=S2.end(); I2!=E2; ++I2)
-      M = ValMgr.AddToSet(M, Op(*I1, *I2));
+  X.Profile(ID);
+  FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos);
   
-  return M;
+  if (!P) {  
+    P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>();
+    new (P) FoldNodeTy(X);
+    APSIntSet.InsertNode(P, InsertPos);
+  }
+  
+  return *P;
 }
 
 //===----------------------------------------------------------------------===//
@@ -170,27 +201,39 @@
 
 namespace {
   
-class VISIBILITY_HIDDEN ExprValue {
+class VISIBILITY_HIDDEN RValue {
 public:
-  enum BaseKind { LValueKind=0x1, RValueKind=0x2, InvalidKind=0x0 };
+  enum BaseKind { InvalidKind=0x0, LValueKind=0x1, NonLValueKind=0x2,
+                  SymbolKind=0x3, BaseFlags = 0x3 };
     
 private:
-  void* Data;
+  uintptr_t Data;
   unsigned Kind;
     
 protected:
-  ExprValue(void* d, bool isRValue, unsigned ValKind)
-    : Data(d),
-      Kind((isRValue ? RValueKind : LValueKind) | (ValKind << 2)) {}
+  RValue(const void* d, bool isLValue, unsigned ValKind)
+    : Data(reinterpret_cast<uintptr_t>(const_cast<void*>(d))),
+      Kind((isLValue ? LValueKind : NonLValueKind) | (ValKind << 2)) {}
   
-  ExprValue() : Data(NULL), Kind(0) {}    
+  explicit RValue()
+    : Data(0), Kind(InvalidKind) {}
   
-  void* getRawPtr() const { return Data; }   
+  explicit RValue(unsigned SymID)
+    : Data(SymID), Kind(SymbolKind) {}
+    
+  void* getRawPtr() const {
+    assert (getBaseKind() != InvalidKind && getBaseKind() != SymbolKind);
+    return reinterpret_cast<void*>(Data);
+  }
+  
+  uintptr_t getRawData() const {
+    return Data;
+  }
   
 public:
-  ~ExprValue() {};
+  ~RValue() {};
 
-  ExprValue EvalCast(ValueManager& ValMgr, Expr* CastExpr) const;
+  RValue Cast(ValueManager& ValMgr, Expr* CastExpr) const;
   
   unsigned getRawKind() const { return Kind; }
   BaseKind getBaseKind() const { return (BaseKind) (Kind & 0x3); }
@@ -198,303 +241,249 @@
   
   void Profile(llvm::FoldingSetNodeID& ID) const {
     ID.AddInteger((unsigned) getRawKind());
-    ID.AddPointer(Data);
+    ID.AddPointer(reinterpret_cast<void*>(Data));
   }
   
-  bool operator==(const ExprValue& RHS) const {
+  bool operator==(const RValue& RHS) const {
     return getRawKind() == RHS.getRawKind() && Data == RHS.Data;
   }
 
   inline bool isValid() const { return getRawKind() != InvalidKind; }
   inline bool isInvalid() const { return getRawKind() == InvalidKind; }
   
-  
   void print(std::ostream& OS) const;
   void print() const { print(*llvm::cerr.stream()); }
 
   // Implement isa<T> support.
-  static inline bool classof(const ExprValue*) { return true; }
+  static inline bool classof(const RValue*) { return true; }
 };
 
-class VISIBILITY_HIDDEN InvalidValue : public ExprValue {
+class VISIBILITY_HIDDEN InvalidValue : public RValue {
 public:
   InvalidValue() {}
   
-  static inline bool classof(const ExprValue* V) {
+  static inline bool classof(const RValue* V) {
     return V->getBaseKind() == InvalidKind;
   }  
 };
 
-class VISIBILITY_HIDDEN LValue : public ExprValue {
+class VISIBILITY_HIDDEN SymbolValue : public RValue {
+public:
+  SymbolValue(unsigned SymID) : RValue(SymID) {}
+  
+  unsigned getID() const {
+    return (unsigned) getRawData();
+  }
+  
+  static inline bool classof(const RValue* V) {
+    return V->getBaseKind() == SymbolKind;
+  }  
+};
+
+class VISIBILITY_HIDDEN LValue : public RValue {
 protected:
-  LValue(unsigned SubKind, void* D) : ExprValue(D, false, SubKind) {}
+  LValue(unsigned SubKind, void* D) : RValue(D, true, SubKind) {}
   
 public:  
   // Implement isa<T> support.
-  static inline bool classof(const ExprValue* V) {
+  static inline bool classof(const RValue* V) {
     return V->getBaseKind() == LValueKind;
   }
 };
 
-class VISIBILITY_HIDDEN RValue : public ExprValue {
+class VISIBILITY_HIDDEN NonLValue : public RValue {
 protected:
-  RValue(unsigned SubKind, void* d) : ExprValue(d, true, SubKind) {}
+  NonLValue(unsigned SubKind, const void* d) : RValue(d, false, SubKind) {}
   
 public:
   void print(std::ostream& Out) const;
   
-  RValue EvalAdd(ValueManager& ValMgr, const RValue& RHS) const;
-  RValue EvalSub(ValueManager& ValMgr, const RValue& RHS) const;
-  RValue EvalMul(ValueManager& ValMgr, const RValue& RHS) const;
-  RValue EvalDiv(ValueManager& ValMgr, const RValue& RHS) const;
-  RValue EvalMinus(ValueManager& ValMgr, UnaryOperator* U) const;
+  NonLValue Add(ValueManager& ValMgr, const NonLValue& RHS) const;
+  NonLValue Sub(ValueManager& ValMgr, const NonLValue& RHS) const;
+  NonLValue Mul(ValueManager& ValMgr, const NonLValue& RHS) const;
+  NonLValue Div(ValueManager& ValMgr, const NonLValue& RHS) const;
+  NonLValue Rem(ValueManager& ValMgr, const NonLValue& RHS) const;
+  NonLValue UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const;
   
-  static RValue GetRValue(ValueManager& ValMgr, const APSInt& V);
-  static RValue GetRValue(ValueManager& ValMgr, IntegerLiteral* I);
+  static NonLValue GetValue(ValueManager& ValMgr, const APSInt& V);
+  static NonLValue GetValue(ValueManager& ValMgr, IntegerLiteral* I);
   
   // Implement isa<T> support.
-  static inline bool classof(const ExprValue* V) {
-    return V->getBaseKind() == RValueKind;
+  static inline bool classof(const RValue* V) {
+    return V->getBaseKind() == NonLValueKind;
   }
 };
     
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
-// "R-Values": Interface.
+// LValues.
 //===----------------------------------------------------------------------===//
 
 namespace {
   
-enum { RValEqualityORSetKind,
-       RValInequalityANDSetKind,
-       NumRValueKind };
-  
-class VISIBILITY_HIDDEN RValEqualityORSet : public RValue {
-public:
-  RValEqualityORSet(const APSIntSetTy& S)
-    : RValue(RValEqualityORSetKind, S.getRoot()) {}
-  
-  APSIntSetTy GetValues() const {
-    return APSIntSetTy(reinterpret_cast<APSIntSetTy::TreeTy*>(getRawPtr()));
-  }
-  
-  RValEqualityORSet
-  EvalAdd(ValueManager& ValMgr, const RValEqualityORSet& V) const {
-    return APSIntSetOp<std::plus>(ValMgr, GetValues(), V.GetValues());
-  }
-  
-  RValEqualityORSet
-  EvalSub(ValueManager& ValMgr, const RValEqualityORSet& V) const {
-    return APSIntSetOp<std::minus>(ValMgr, GetValues(), V.GetValues());
-  }
-  
-  RValEqualityORSet
-  EvalMul(ValueManager& ValMgr, const RValEqualityORSet& V) const {
-    return APSIntSetOp<std::multiplies>(ValMgr, GetValues(), V.GetValues());
-  }
-  
-  RValEqualityORSet
-  EvalDiv(ValueManager& ValMgr, const RValEqualityORSet& V) const {
-    return APSIntSetOp<std::divides>(ValMgr, GetValues(), V.GetValues());
-  }
-
-  RValEqualityORSet
-  EvalCast(ValueManager& ValMgr, Expr* CastExpr) const;
-  
-  RValEqualityORSet
-  EvalMinus(ValueManager& ValMgr, UnaryOperator* U) const;
-  
-  // Implement isa<T> support.
-  static inline bool classof(const ExprValue* V) {
-    return V->getSubKind() == RValEqualityORSetKind;
-  }
-};
-  
-class VISIBILITY_HIDDEN RValInequalityANDSet : public RValue {
-public:
-  RValInequalityANDSet(const APSIntSetTy& S)
-  : RValue(RValInequalityANDSetKind, S.getRoot()) {}
-  
-  APSIntSetTy GetValues() const {
-    return APSIntSetTy(reinterpret_cast<APSIntSetTy::TreeTy*>(getRawPtr()));
-  }
-  
-  RValInequalityANDSet
-  EvalAdd(ValueManager& ValMgr, const RValInequalityANDSet& V) const;
-  
-  RValInequalityANDSet
-  EvalSub(ValueManager& ValMgr, const RValInequalityANDSet& V) const;
-  
-  RValInequalityANDSet
-  EvalMul(ValueManager& ValMgr, const RValInequalityANDSet& V) const;
-  
-  RValInequalityANDSet
-  EvalDiv(ValueManager& ValMgr, const RValInequalityANDSet& V) const;
-  
-  RValInequalityANDSet
-  EvalCast(ValueManager& ValMgr, Expr* CastExpr) const;
-  
-  RValInequalityANDSet
-  EvalMinus(ValueManager& ValMgr, UnaryOperator* U) const;
-  
-  // Implement isa<T> support.
-  static inline bool classof(const ExprValue* V) {
-    return V->getSubKind() == RValInequalityANDSetKind;
-  }
-};
-  
-} // end anonymous namespace
-
-//===----------------------------------------------------------------------===//
-// Transfer functions: Casts.
-//===----------------------------------------------------------------------===//
-
-ExprValue ExprValue::EvalCast(ValueManager& ValMgr, Expr* CastExpr) const {
-  switch (getSubKind()) {
-    case RValEqualityORSetKind:
-      return cast<RValEqualityORSet>(this)->EvalCast(ValMgr, CastExpr);
-    default:
-      return InvalidValue();
-  }
-}
-
-RValEqualityORSet
-RValEqualityORSet::EvalCast(ValueManager& ValMgr, Expr* CastExpr) const {
-  QualType T = CastExpr->getType();
-  assert (T->isIntegerType());
-  
-  APSIntSetTy S1 = GetValues();  
-  APSIntSetTy S2 = ValMgr.GetEmptyAPSIntSet();
-  
-  for (APSIntSetTy::iterator I=S1.begin(), E=S1.end(); I!=E; ++I) {
-    APSInt X = *I;
-    X.setIsSigned(T->isSignedIntegerType());
-    X.extOrTrunc(ValMgr.getContext()->getTypeSize(T,CastExpr->getLocStart()));    
-    S2 = ValMgr.AddToSet(S2, X);
-  }
-  
-  return S2;
-}
-
-//===----------------------------------------------------------------------===//
-// Transfer functions: Unary Operations over R-Values.
-//===----------------------------------------------------------------------===//
-
-RValue RValue::EvalMinus(ValueManager& ValMgr, UnaryOperator* U) const {
-  switch (getSubKind()) {
-    case RValEqualityORSetKind:
-      return cast<RValEqualityORSet>(this)->EvalMinus(ValMgr, U);
-    default:
-      return cast<RValue>(InvalidValue());
-  }
-}
-
-RValEqualityORSet
-RValEqualityORSet::EvalMinus(ValueManager& ValMgr, UnaryOperator* U) const{
-  
-  assert (U->getType() == U->getSubExpr()->getType());  
-  assert (U->getType()->isIntegerType());
-  
-  APSIntSetTy S1 = GetValues();  
-  APSIntSetTy S2 = ValMgr.GetEmptyAPSIntSet();
-  
-  for (APSIntSetTy::iterator I=S1.begin(), E=S1.end(); I!=E; ++I) {
-    assert ((*I).isSigned());
-    
-    // FIXME: Shouldn't operator- on APSInt return an APSInt with the proper
-    //  sign?
-    APSInt X(-(*I));
-    X.setIsSigned(true);
-    
-    S2 = ValMgr.AddToSet(S2, X);
-  }
-  
-  return S2;
-}
-
-//===----------------------------------------------------------------------===//
-// Transfer functions: Binary Operations over R-Values.
-//===----------------------------------------------------------------------===//
-
-#define RVALUE_DISPATCH_CASE(k1,k2,Op)\
-case (k1##Kind*NumRValueKind+k2##Kind):\
-  return cast<k1>(*this).Eval##Op(ValMgr,cast<k2>(RHS));
-
-#define RVALUE_DISPATCH(Op)\
-switch (getSubKind()*NumRValueKind+RHS.getSubKind()){\
-  RVALUE_DISPATCH_CASE(RValEqualityORSet,RValEqualityORSet,Op)\
-  default:\
-    assert (!isValid() || !RHS.isValid() && "Missing case.");\
-    break;\
-}\
-return cast<RValue>(InvalidValue());
-
-RValue RValue::EvalAdd(ValueManager& ValMgr, const RValue& RHS) const {
-  RVALUE_DISPATCH(Add)
-}
-
-RValue RValue::EvalSub(ValueManager& ValMgr, const RValue& RHS) const {
-  RVALUE_DISPATCH(Sub)
-}
-
-RValue RValue::EvalMul(ValueManager& ValMgr, const RValue& RHS) const {
-  RVALUE_DISPATCH(Mul)
-}
-
-RValue RValue::EvalDiv(ValueManager& ValMgr, const RValue& RHS) const {
-  RVALUE_DISPATCH(Div)
-}
-
-#undef RVALUE_DISPATCH_CASE
-#undef RVALUE_DISPATCH
-
-
-RValue RValue::GetRValue(ValueManager& ValMgr, const APSInt& V) {
-  return RValEqualityORSet(ValMgr.AddToSet(ValMgr.GetEmptyAPSIntSet(), V));
-}
-
-RValue RValue::GetRValue(ValueManager& ValMgr, IntegerLiteral* I) {
-  return GetRValue(ValMgr,
-                   APSInt(I->getValue(),I->getType()->isUnsignedIntegerType()));
-}
-
-//===----------------------------------------------------------------------===//
-// "L-Values".
-//===----------------------------------------------------------------------===//
-
-namespace {
-
-enum { LValueDeclKind, MaxLValueKind };
+enum { LValueDeclKind, NumLValueKind };
 
 class VISIBILITY_HIDDEN LValueDecl : public LValue {
 public:
   LValueDecl(const ValueDecl* vd) 
-    : LValue(LValueDeclKind,const_cast<ValueDecl*>(vd)) {}
+  : LValue(LValueDeclKind,const_cast<ValueDecl*>(vd)) {}
   
   ValueDecl* getDecl() const {
     return static_cast<ValueDecl*>(getRawPtr());
   }
   
   // Implement isa<T> support.
-  static inline bool classof(const ExprValue* V) {
+  static inline bool classof(const RValue* V) {
     return V->getSubKind() == LValueDeclKind;
   }
-};  
+};
+  
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
+// Non-LValues.
+//===----------------------------------------------------------------------===//
+
+namespace {
+  
+enum { ConcreteIntKind, ConstrainedIntegerKind, NumNonLValueKind };
+  
+class VISIBILITY_HIDDEN ConcreteInt : public NonLValue {
+public:
+  ConcreteInt(const APSInt& V) : NonLValue(ConcreteIntKind, &V) {}
+  
+  const APSInt& getValue() const {
+    return *static_cast<APSInt*>(getRawPtr());
+  }
+
+  ConcreteInt Add(ValueManager& ValMgr, const ConcreteInt& V) const {
+    return ValMgr.getValue(getValue() + V.getValue());
+  }
+
+  ConcreteInt Sub(ValueManager& ValMgr, const ConcreteInt& V) const {
+    return ValMgr.getValue(getValue() - V.getValue());
+  }
+  
+  ConcreteInt Mul(ValueManager& ValMgr, const ConcreteInt& V) const {
+    return ValMgr.getValue(getValue() * V.getValue());
+  }
+  
+  ConcreteInt Div(ValueManager& ValMgr, const ConcreteInt& V) const {
+    return ValMgr.getValue(getValue() / V.getValue());
+  }
+  
+  ConcreteInt Rem(ValueManager& ValMgr, const ConcreteInt& V) const {
+    return ValMgr.getValue(getValue() % V.getValue());
+  }
+  
+  ConcreteInt Cast(ValueManager& ValMgr, Expr* CastExpr) const {
+    assert (CastExpr->getType()->isIntegerType());
+    
+    APSInt X(getValue());  
+    X.extOrTrunc(ValMgr.getContext()->getTypeSize(CastExpr->getType(),
+                                                  CastExpr->getLocStart()));
+    return ValMgr.getValue(X);
+  }
+  
+  ConcreteInt UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const {
+    assert (U->getType() == U->getSubExpr()->getType());  
+    assert (U->getType()->isIntegerType());  
+    return ValMgr.getValue(-getValue()); 
+  }
+
+  // Implement isa<T> support.
+  static inline bool classof(const RValue* V) {
+    return V->getSubKind() == ConcreteIntKind;
+  }
+};
+  
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// Transfer function dispatch.
+//===----------------------------------------------------------------------===//
+
+RValue RValue::Cast(ValueManager& ValMgr, Expr* CastExpr) const {
+  switch (getSubKind()) {
+    case ConcreteIntKind:
+      return cast<ConcreteInt>(this)->Cast(ValMgr, CastExpr);
+    default:
+      return InvalidValue();
+  }
+}
+
+NonLValue NonLValue::UnaryMinus(ValueManager& ValMgr, UnaryOperator* U) const {
+  switch (getSubKind()) {
+    case ConcreteIntKind:
+      return cast<ConcreteInt>(this)->UnaryMinus(ValMgr, U);
+    default:
+      return cast<NonLValue>(InvalidValue());
+  }
+}
+
+#define RVALUE_DISPATCH_CASE(k1,k2,Op)\
+case (k1##Kind*NumNonLValueKind+k2##Kind):\
+  return cast<k1>(*this).Op(ValMgr,cast<k2>(RHS));
+
+#define RVALUE_DISPATCH(Op)\
+switch (getSubKind()*NumNonLValueKind+RHS.getSubKind()){\
+  RVALUE_DISPATCH_CASE(ConcreteInt,ConcreteInt,Op)\
+  default:\
+    assert (!isValid() || !RHS.isValid() && "Missing case.");\
+    break;\
+}\
+return cast<NonLValue>(InvalidValue());
+
+NonLValue NonLValue::Add(ValueManager& ValMgr, const NonLValue& RHS) const {
+  RVALUE_DISPATCH(Add)
+}
+
+NonLValue NonLValue::Sub(ValueManager& ValMgr, const NonLValue& RHS) const {
+  RVALUE_DISPATCH(Sub)
+}
+
+NonLValue NonLValue::Mul(ValueManager& ValMgr, const NonLValue& RHS) const {
+  RVALUE_DISPATCH(Mul)
+}
+
+NonLValue NonLValue::Div(ValueManager& ValMgr, const NonLValue& RHS) const {
+  RVALUE_DISPATCH(Div)
+}
+
+NonLValue NonLValue::Rem(ValueManager& ValMgr, const NonLValue& RHS) const {
+  RVALUE_DISPATCH(Rem)
+}
+
+
+#undef RVALUE_DISPATCH_CASE
+#undef RVALUE_DISPATCH
+
+//===----------------------------------------------------------------------===//
+// Utility methods for constructing RValues.
+//===----------------------------------------------------------------------===//
+
+NonLValue NonLValue::GetValue(ValueManager& ValMgr, const APSInt& V) {
+  return ConcreteInt(ValMgr.getValue(V));
+}
+
+NonLValue NonLValue::GetValue(ValueManager& ValMgr, IntegerLiteral* I) {
+  return ConcreteInt(ValMgr.getValue(APSInt(I->getValue(),
+                                       I->getType()->isUnsignedIntegerType())));
+}
+
+//===----------------------------------------------------------------------===//
 // Pretty-Printing.
 //===----------------------------------------------------------------------===//
 
-void ExprValue::print(std::ostream& Out) const {
+void RValue::print(std::ostream& Out) const {
   switch (getBaseKind()) {
     case InvalidKind:
       Out << "Invalid";
       break;
       
-    case RValueKind:
-      cast<RValue>(this)->print(Out);
+    case NonLValueKind:
+      cast<NonLValue>(this)->print(Out);
       break;
       
     case LValueKind:
@@ -502,37 +491,27 @@
       break;
       
     default:
-      assert (false && "Invalid ExprValue.");
+      assert (false && "Invalid RValue.");
   }
 }
 
-void RValue::print(std::ostream& Out) const {
+void NonLValue::print(std::ostream& Out) const {
   switch (getSubKind()) {  
-    case RValEqualityORSetKind: {
-      APSIntSetTy S = cast<RValEqualityORSet>(this)->GetValues();
-      bool first = true;
-
-      for (APSIntSetTy::iterator I=S.begin(), E=S.end(); I!=E; ++I) {
-        if (first) first = false;
-        else Out << " | ";
-        
-        Out << (*I).toString();
-      }
-      
+    case ConcreteIntKind:
+      Out << cast<ConcreteInt>(this)->getValue().toString();
       break;
-    }
       
     default:
-      assert (false && "Pretty-printed not implemented for this RValue.");
+      assert (false && "Pretty-printed not implemented for this NonLValue.");
       break;
   }
 }
 
 //===----------------------------------------------------------------------===//
-// ValueMapTy - A ImmutableMap type Stmt*/Decl* to ExprValues.
+// ValueMapTy - A ImmutableMap type Stmt*/Decl*/Symbols to RValues.
 //===----------------------------------------------------------------------===//
 
-typedef llvm::ImmutableMap<ValueKey,ExprValue> ValueMapTy;
+typedef llvm::ImmutableMap<ValueKey,RValue> ValueMapTy;
 
 namespace clang {
   template<>
@@ -547,7 +526,7 @@
 }
 
 //===----------------------------------------------------------------------===//
-// The Checker!
+// The Checker.
 //===----------------------------------------------------------------------===//
 
 namespace {
@@ -594,7 +573,7 @@
   /// StateMgr - Object that manages the data for all created states.
   ValueMapTy::Factory StateMgr;
   
-  /// ValueMgr - Object that manages the data for all created ExprValues.
+  /// ValueMgr - Object that manages the data for all created RValues.
   ValueManager ValMgr;
   
   /// cfg - the current CFG.
@@ -646,20 +625,20 @@
   ///  mappings removed.
   StateTy RemoveDeadBindings(Stmt* S, StateTy M);
 
-  StateTy SetValue(StateTy St, Stmt* S, const ExprValue& V);  
+  StateTy SetValue(StateTy St, Stmt* S, const RValue& V);  
 
-  StateTy SetValue(StateTy St, const Stmt* S, const ExprValue& V) {
+  StateTy SetValue(StateTy St, const Stmt* S, const RValue& V) {
     return SetValue(St, const_cast<Stmt*>(S), V);
   }
   
-  StateTy SetValue(StateTy St, const LValue& LV, const ExprValue& V);
+  StateTy SetValue(StateTy St, const LValue& LV, const RValue& V);
   
-  ExprValue GetValue(const StateTy& St, Stmt* S);  
-  inline ExprValue GetValue(const StateTy& St, const Stmt* S) {
+  RValue GetValue(const StateTy& St, Stmt* S);  
+  inline RValue GetValue(const StateTy& St, const Stmt* S) {
     return GetValue(St, const_cast<Stmt*>(S));
   }
   
-  ExprValue GetValue(const StateTy& St, const LValue& LV);
+  RValue GetValue(const StateTy& St, const LValue& LV);
   LValue GetLValue(const StateTy& St, Stmt* S);
   
   void Nodify(NodeSet& Dst, Stmt* S, NodeTy* Pred, StateTy St);
@@ -706,7 +685,7 @@
 }
 
 
-ExprValue GRConstants::GetValue(const StateTy& St, const LValue& LV) {
+RValue GRConstants::GetValue(const StateTy& St, const LValue& LV) {
   switch (LV.getSubKind()) {
     case LValueDeclKind: {
       StateTy::TreeTy* T = St.SlimFind(cast<LValueDecl>(LV).getDecl()); 
@@ -720,19 +699,34 @@
   return InvalidValue();
 }
   
-ExprValue GRConstants::GetValue(const StateTy& St, Stmt* S) {
+RValue GRConstants::GetValue(const StateTy& St, Stmt* S) {
   for (;;) {
     switch (S->getStmtClass()) {
+        
+      // ParenExprs are no-ops.
+        
       case Stmt::ParenExprClass:
         S = cast<ParenExpr>(S)->getSubExpr();
         continue;
         
+      // DeclRefExprs can either evaluate to an LValue or a Non-LValue
+      // (assuming an implicit "load") depending on the context.  In this
+      // context we assume that we are retrieving the value contained
+      // within the referenced variables.
+        
       case Stmt::DeclRefExprClass:
         return GetValue(St, LValueDecl(cast<DeclRefExpr>(S)->getDecl()));
 
+      // Integer literals evaluate to an RValue.  Simply retrieve the
+      // RValue for the literal.
+        
       case Stmt::IntegerLiteralClass:
-        return RValue::GetRValue(ValMgr, cast<IntegerLiteral>(S));
-      
+        return NonLValue::GetValue(ValMgr, cast<IntegerLiteral>(S));
+              
+      // Casts where the source and target type are the same
+      // are no-ops.  We blast through these to get the descendant
+      // subexpression that has a value.
+        
       case Stmt::ImplicitCastExprClass: {
         ImplicitCastExpr* C = cast<ImplicitCastExpr>(S);
         if (C->getType() == C->getSubExpr()->getType()) {
@@ -741,7 +735,7 @@
         }
         break;
       }
-        
+
       case Stmt::CastExprClass: {
         CastExpr* C = cast<CastExpr>(S);
         if (C->getType() == C->getSubExpr()->getType()) {
@@ -751,6 +745,8 @@
         break;
       }
 
+      // Handle all other Stmt* using a lookup.
+
       default:
         break;
     };
@@ -764,8 +760,8 @@
 }
 
 LValue GRConstants::GetLValue(const StateTy& St, Stmt* S) {
-  if (Expr* E = dyn_cast<Expr>(S))
-    S = E->IgnoreParens();
+  while (ParenExpr* P = dyn_cast<ParenExpr>(S))
+    S = P->getSubExpr();
   
   if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(S))
     return LValueDecl(DR->getDecl());
@@ -773,8 +769,9 @@
   return cast<LValue>(GetValue(St, S));
 }
 
+
 GRConstants::StateTy GRConstants::SetValue(StateTy St, Stmt* S,
-                                           const ExprValue& V) {
+                                           const RValue& V) {
   assert (S);
   
   if (!StateCleaned) {
@@ -796,7 +793,7 @@
 }
 
 GRConstants::StateTy GRConstants::SetValue(StateTy St, const LValue& LV,
-                                           const ExprValue& V) {
+                                           const RValue& V) {
   if (!LV.isValid())
     return St;
   
@@ -828,13 +825,10 @@
   }
 
   // Remove bindings for "dead" decls.
-  for (; I!=E ; ++I) {
-    assert (I.getKey().isDecl());
-    
+  for (; I!=E && I.getKey().isDecl(); ++I)
     if (VarDecl* V = dyn_cast<VarDecl>(cast<ValueDecl>(I.getKey())))
       if (!Liveness->isLive(Loc, V))
         M = StateMgr.Remove(M, I.getKey());
-  }
 
   return M;
 }
@@ -866,8 +860,8 @@
   for (NodeSet::iterator I1=S1.begin(), E1=S1.end(); I1 != E1; ++I1) {
     NodeTy* N = *I1;
     StateTy St = N->getState();
-    const ExprValue& V = GetValue(St, E);
-    Nodify(Dst, CastE, N, SetValue(St, CastE, V.EvalCast(ValMgr, CastE)));
+    const RValue& V = GetValue(St, E);
+    Nodify(Dst, CastE, N, SetValue(St, CastE, V.Cast(ValMgr, CastE)));
   }
 }
 
@@ -899,63 +893,63 @@
     switch (U->getOpcode()) {
       case UnaryOperator::PostInc: {
         const LValue& L1 = GetLValue(St, U->getSubExpr());
-        RValue R1 = cast<RValue>(GetValue(St, L1));
+        NonLValue R1 = cast<NonLValue>(GetValue(St, L1));
 
         QualType T = U->getType();
         unsigned bits = getContext()->getTypeSize(T, U->getLocStart());
         APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType());
-        RValue R2 = RValue::GetRValue(ValMgr, One);
+        NonLValue R2 = NonLValue::GetValue(ValMgr, One);
         
-        RValue Result = R1.EvalAdd(ValMgr, R2);
+        NonLValue Result = R1.Add(ValMgr, R2);
         Nodify(Dst, U, N1, SetValue(SetValue(St, U, R1), L1, Result));
         break;
       }
         
       case UnaryOperator::PostDec: {
         const LValue& L1 = GetLValue(St, U->getSubExpr());
-        RValue R1 = cast<RValue>(GetValue(St, L1));
+        NonLValue R1 = cast<NonLValue>(GetValue(St, L1));
         
         QualType T = U->getType();
         unsigned bits = getContext()->getTypeSize(T, U->getLocStart());
         APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType());
-        RValue R2 = RValue::GetRValue(ValMgr, One);
+        NonLValue R2 = NonLValue::GetValue(ValMgr, One);
         
-        RValue Result = R1.EvalSub(ValMgr, R2);
+        NonLValue Result = R1.Sub(ValMgr, R2);
         Nodify(Dst, U, N1, SetValue(SetValue(St, U, R1), L1, Result));
         break;
       }
         
       case UnaryOperator::PreInc: {
         const LValue& L1 = GetLValue(St, U->getSubExpr());
-        RValue R1 = cast<RValue>(GetValue(St, L1));
+        NonLValue R1 = cast<NonLValue>(GetValue(St, L1));
         
         QualType T = U->getType();
         unsigned bits = getContext()->getTypeSize(T, U->getLocStart());
         APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType());
-        RValue R2 = RValue::GetRValue(ValMgr, One);        
+        NonLValue R2 = NonLValue::GetValue(ValMgr, One);        
         
-        RValue Result = R1.EvalAdd(ValMgr, R2);
+        NonLValue Result = R1.Add(ValMgr, R2);
         Nodify(Dst, U, N1, SetValue(SetValue(St, U, Result), L1, Result));
         break;
       }
         
       case UnaryOperator::PreDec: {
         const LValue& L1 = GetLValue(St, U->getSubExpr());
-        RValue R1 = cast<RValue>(GetValue(St, L1));
+        NonLValue R1 = cast<NonLValue>(GetValue(St, L1));
         
         QualType T = U->getType();
         unsigned bits = getContext()->getTypeSize(T, U->getLocStart());
         APSInt One(llvm::APInt(bits, 1), T->isUnsignedIntegerType());
-        RValue R2 = RValue::GetRValue(ValMgr, One);       
+        NonLValue R2 = NonLValue::GetValue(ValMgr, One);       
         
-        RValue Result = R1.EvalSub(ValMgr, R2);
+        NonLValue Result = R1.Sub(ValMgr, R2);
         Nodify(Dst, U, N1, SetValue(SetValue(St, U, Result), L1, Result));
         break;
       }
         
       case UnaryOperator::Minus: {
-        const RValue& R1 = cast<RValue>(GetValue(St, U->getSubExpr()));
-        Nodify(Dst, U, N1, SetValue(St, U, R1.EvalMinus(ValMgr, U)));
+        const NonLValue& R1 = cast<NonLValue>(GetValue(St, U->getSubExpr()));
+        Nodify(Dst, U, N1, SetValue(St, U, R1.UnaryMinus(ValMgr, U)));
         break;
       }
         
@@ -977,8 +971,8 @@
     // When getting the value for the LHS, check if we are in an assignment.
     // In such cases, we want to (initially) treat the LHS as an LValue,
     // so we use GetLValue instead of GetValue so that DeclRefExpr's are
-    // evaluated to LValueDecl's instead of to an RValue.
-    const ExprValue& V1 = 
+    // evaluated to LValueDecl's instead of to an NonLValue.
+    const RValue& V1 = 
       B->isAssignmentOp() ? GetLValue(N1->getState(), B->getLHS())
                           : GetValue(N1->getState(), B->getLHS());
     
@@ -988,73 +982,73 @@
     for (NodeSet::iterator I2=S2.begin(), E2=S2.end(); I2 != E2; ++I2) {
       NodeTy* N2 = *I2;
       StateTy St = N2->getState();
-      const ExprValue& V2 = GetValue(St, B->getRHS());
+      const RValue& V2 = GetValue(St, B->getRHS());
 
       switch (B->getOpcode()) {
         case BinaryOperator::Add: {
-          const RValue& R1 = cast<RValue>(V1);
-          const RValue& R2 = cast<RValue>(V2);
+          const NonLValue& R1 = cast<NonLValue>(V1);
+          const NonLValue& R2 = cast<NonLValue>(V2);
           
-          Nodify(Dst, B, N2, SetValue(St, B, R1.EvalAdd(ValMgr, R2)));
+          Nodify(Dst, B, N2, SetValue(St, B, R1.Add(ValMgr, R2)));
           break;
         }
 
         case BinaryOperator::Sub: {
-          const RValue& R1 = cast<RValue>(V1);
-          const RValue& R2 = cast<RValue>(V2);
-	        Nodify(Dst, B, N2, SetValue(St, B, R1.EvalSub(ValMgr, R2)));
+          const NonLValue& R1 = cast<NonLValue>(V1);
+          const NonLValue& R2 = cast<NonLValue>(V2);
+	        Nodify(Dst, B, N2, SetValue(St, B, R1.Sub(ValMgr, R2)));
           break;
         }
           
         case BinaryOperator::Mul: {
-          const RValue& R1 = cast<RValue>(V1);
-          const RValue& R2 = cast<RValue>(V2);
-	        Nodify(Dst, B, N2, SetValue(St, B, R1.EvalMul(ValMgr, R2)));
+          const NonLValue& R1 = cast<NonLValue>(V1);
+          const NonLValue& R2 = cast<NonLValue>(V2);
+	        Nodify(Dst, B, N2, SetValue(St, B, R1.Mul(ValMgr, R2)));
           break;
         }
           
         case BinaryOperator::Div: {
-          const RValue& R1 = cast<RValue>(V1);
-          const RValue& R2 = cast<RValue>(V2);
-	        Nodify(Dst, B, N2, SetValue(St, B, R1.EvalDiv(ValMgr, R2)));
+          const NonLValue& R1 = cast<NonLValue>(V1);
+          const NonLValue& R2 = cast<NonLValue>(V2);
+	        Nodify(Dst, B, N2, SetValue(St, B, R1.Div(ValMgr, R2)));
           break;
         }
           
         case BinaryOperator::Assign: {
           const LValue& L1 = cast<LValue>(V1);
-          const RValue& R2 = cast<RValue>(V2);
+          const NonLValue& R2 = cast<NonLValue>(V2);
           Nodify(Dst, B, N2, SetValue(SetValue(St, B, R2), L1, R2));
           break;
         }
           
         case BinaryOperator::AddAssign: {
           const LValue& L1 = cast<LValue>(V1);
-          RValue R1 = cast<RValue>(GetValue(N1->getState(), L1));
-          RValue Result = R1.EvalAdd(ValMgr, cast<RValue>(V2));
+          NonLValue R1 = cast<NonLValue>(GetValue(N1->getState(), L1));
+          NonLValue Result = R1.Add(ValMgr, cast<NonLValue>(V2));
           Nodify(Dst, B, N2, SetValue(SetValue(St, B, Result), L1, Result));
           break;
         }
           
         case BinaryOperator::SubAssign: {
           const LValue& L1 = cast<LValue>(V1);
-          RValue R1 = cast<RValue>(GetValue(N1->getState(), L1));
-          RValue Result = R1.EvalSub(ValMgr, cast<RValue>(V2));
+          NonLValue R1 = cast<NonLValue>(GetValue(N1->getState(), L1));
+          NonLValue Result = R1.Sub(ValMgr, cast<NonLValue>(V2));
           Nodify(Dst, B, N2, SetValue(SetValue(St, B, Result), L1, Result));
           break;
         }
           
         case BinaryOperator::MulAssign: {
           const LValue& L1 = cast<LValue>(V1);
-          RValue R1 = cast<RValue>(GetValue(N1->getState(), L1));
-          RValue Result = R1.EvalMul(ValMgr, cast<RValue>(V2));
+          NonLValue R1 = cast<NonLValue>(GetValue(N1->getState(), L1));
+          NonLValue Result = R1.Mul(ValMgr, cast<NonLValue>(V2));
           Nodify(Dst, B, N2, SetValue(SetValue(St, B, Result), L1, Result));
           break;
         }
           
         case BinaryOperator::DivAssign: {
           const LValue& L1 = cast<LValue>(V1);
-          RValue R1 = cast<RValue>(GetValue(N1->getState(), L1));
-          RValue Result = R1.EvalDiv(ValMgr, cast<RValue>(V2));
+          NonLValue R1 = cast<NonLValue>(GetValue(N1->getState(), L1));
+          NonLValue Result = R1.Div(ValMgr, cast<NonLValue>(V2));
           Nodify(Dst, B, N2, SetValue(SetValue(St, B, Result), L1, Result));
           break;
         }