lib/Analysis/RangeConstraintManager.cpp - platform/external/clang - Gitiles

 //== RangeConstraintManager.cpp - Manage range constraints.------*- C++ -*--==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines RangeConstraintManager, a class that tracks simple
 //  equality and inequality constraints on symbolic values of GRState.
 //
 //===----------------------------------------------------------------------===//

 #include "SimpleConstraintManager.h"
 #include "clang/Analysis/PathSensitive/GRState.h"
 #include "clang/Analysis/PathSensitive/GRStateTrait.h"
 #include "clang/Analysis/PathSensitive/GRTransferFuncs.h"
 #include "clang/Driver/ManagerRegistry.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/ImmutableSet.h"
 #include "llvm/Support/raw_ostream.h"

 using namespace clang;

 namespace { class VISIBILITY_HIDDEN ConstRange {}; }

 static int ConstRangeIndex = 0;

 // A Range represents the closed range [from, to].  The caller must
 // guarantee that from <= to.  Note that Range is immutable, so as not
 // to subvert RangeSet's immutability.
 class Range : public std::pair<llvm::APSInt, llvm::APSInt> {
 public:
   Range(const llvm::APSInt &from, const llvm::APSInt &to)
     : std::pair<llvm::APSInt, llvm::APSInt>(from, to) {
     assert(from <= to);
   }
   bool Includes(const llvm::APSInt &v) const {
     return first <= v && v <= second;
   }
   const llvm::APSInt &From() const {
     return first;
   }
   const llvm::APSInt &To() const {
     return second;
   }
   const llvm::APSInt *HasConcreteValue() const {
     return From() == To() ? &From() : NULL;
   }

   void Profile(llvm::FoldingSetNodeID &ID) const {
     From().Profile(ID);
     To().Profile(ID);
   }
 };

 struct RangeCmp {
   bool operator()(const Range &r1, const Range &r2) {
     if (r1.From() < r2.From()) {
       assert(!r1.Includes(r2.From()));
       assert(!r2.Includes(r1.To()));
       return true;
     } else if (r1.From() > r2.From()) {
       assert(!r1.Includes(r2.To()));
       assert(!r2.Includes(r1.From()));
       return false;
     } else
       assert(!"Ranges should never be equal in the same set");
   }
 };

 typedef llvm::ImmutableSet<Range> PrimRangeSet;

 class RangeSet;
 std::ostream &operator<<(std::ostream &os, const RangeSet &r);


 // A RangeSet contains a set of ranges. If the set is empty, then
 //   noValues -> Nothing matches.
 //  !noValues -> Everything (in range of the bit representation) matches.
 class RangeSet {
   PrimRangeSet ranges; // no need to make const, since it is an
                        // ImmutableSet - this allows default operator=
                        // to work.
   bool noValues;  // if true, no value is possible (should never happen)

   static const llvm::APSInt Max(const llvm::APSInt &v) {
     return llvm::APSInt::getMaxValue(v.getBitWidth(), v.isUnsigned());
   }
   static const llvm::APSInt Min(const llvm::APSInt &v) {
      return llvm::APSInt::getMinValue(v.getBitWidth(), v.isUnsigned());
   }
   static const llvm::APSInt One(const llvm::APSInt &v) {
     return llvm::APSInt(llvm::APInt(v.getBitWidth(), 1), v.isUnsigned());
   }

 public:
   // Create a RangeSet that allows all possible values.
   RangeSet(PrimRangeSet::Factory *factory) : ranges(factory->GetEmptySet()),
                                              noValues(false) {
   }
   // Note that if the empty set is passed, then there are no possible
   // values.  To create a RangeSet that covers all values when the
   // empty set is passed, use RangeSet(r, false).
   RangeSet(const PrimRangeSet &r) : ranges(r), noValues(r.isEmpty()) {
   }
   // Allow an empty set to be passed meaning "all values" instead of
   // "no values".
   RangeSet(const PrimRangeSet &r, bool n) : ranges(r), noValues(n) {
     assert(!n);
   }
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ranges.Profile(ID);
     ID.AddBoolean(noValues);
   }

   const llvm::APSInt *HasConcreteValue() const {
     if (!ranges.isSingleton())
       return NULL;
     return ranges.begin()->HasConcreteValue();
   }

   bool CouldBeNE(const llvm::APSInt &ne) const {
     DOUT << "CouldBeNE(" << ne.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     const llvm::APSInt *v = HasConcreteValue();
     if (v && *v == ne)
         return false;
     return true;
   }

   bool CouldBeEQ(const llvm::APSInt &eq) const {
     DOUT << "CouldBeEQ(" << eq.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     if (ranges.isEmpty())
       return true;
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
       if (i->Includes(eq))
         return true;
     return false;
   }

   bool CouldBeLT(const llvm::APSInt &lt) const {
     DOUT << "CouldBeLT(" << lt.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     // FIXME: should test if lt == min -> false here, since that's
     // impossible to meet.
     if (ranges.isEmpty())
       return true;
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
       if (i->From() < lt)
         return true;
     return false;
   }

   bool CouldBeLE(const llvm::APSInt &le) const {
     DOUT << "CouldBeLE(" << le.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     if (ranges.isEmpty())
       return true;
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
       if (i->From() <= le)
         return true;
     return false;
   }

   bool CouldBeGT(const llvm::APSInt &gt) const {
     DOUT << "CouldBeGT(" << gt.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     // FIXME: should we test if gt == max -> false here, since that's
     // impossible to meet.
     if (ranges.isEmpty())
       return true;
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
       if (i->To() > gt)
         return true;
     return false;
   }

   bool CouldBeGE(const llvm::APSInt &ge) const {
     DOUT << "CouldBeGE(" << ge.toString(10) << ") " << *this << std::endl;
     assert(!noValues);
     if (ranges.isEmpty())
       return true;
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
       if (i->To() >= ge)
         return true;
     return false;
   }

   // Make all existing ranges fall within this new range
   RangeSet Restrict(PrimRangeSet::Factory *factory, const llvm::APSInt &from,
                     const llvm::APSInt &to) const {
     if (ranges.isEmpty())
       return factory->Add(ranges, Range(from, to));;

     PrimRangeSet newRanges = factory->GetEmptySet();

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       if (i->Includes(from)) {
         if (i->Includes(to)) {
           newRanges = factory->Add(newRanges, Range(from, to));
         } else {
           newRanges = factory->Add(newRanges, Range(from, i->To()));
         }
       } else if (i->Includes(to)) {
         newRanges = factory->Add(newRanges, Range(i->From(), to));
       }
     }
     return RangeSet(newRanges);
   }

   // Create a new RangeSet with the additional constraint that the
   // range must be == eq. In other words the range becomes [eq,
   // eq]. Note that this RangeSet must have included eq in the first
   // place, or we shouldn't be here.
   RangeSet AddEQ(PrimRangeSet::Factory *factory, const llvm::APSInt &eq) {
     DOUT << "AddEQ(" << eq.toString(10) << ") " << *this << " -> ";
     assert(CouldBeEQ(eq));
     RangeSet r(factory->Add(factory->GetEmptySet(), Range(eq, eq)));
     DOUT << r << std::endl;
     return r;
   }

   RangeSet AddNE(PrimRangeSet::Factory *factory, const llvm::APSInt &ne) {
     DOUT << "AddNE(" << ne.toString(10) << ") " << *this << " -> ";

     const llvm::APSInt max = Max(ne);
     const llvm::APSInt min = Min(ne);
     const llvm::APSInt one = One(ne);

     PrimRangeSet newRanges = factory->GetEmptySet();

     if (ranges.isEmpty()) {
       if (ne != max)
         newRanges = factory->Add(newRanges, Range(ne + one, max));
       if (ne != min)
         newRanges = factory->Add(newRanges, Range(min, ne - one));
       RangeSet r(newRanges);
       DOUT << r << std::endl;
       return r;
     }

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       if (i->Includes(ne)) {
         if (ne != i->From())
           newRanges = factory->Add(newRanges, Range(i->From(), ne - one));
         if (ne != i->To())
           newRanges = factory->Add(newRanges, Range(ne + one, i->To()));
       } else {
         newRanges = factory->Add(newRanges, *i);
       }
     }
     RangeSet r(newRanges);
     DOUT << r << std::endl;
     return r;
   }

   RangeSet AddLT(PrimRangeSet::Factory *factory, const llvm::APSInt &lt) {
     DOUT << "AddLT(" << lt.toString(10) << ") " << *this << " -> ";
     const llvm::APSInt min = Min(lt);
     const llvm::APSInt one = One(lt);

     if (ranges.isEmpty()) {
       PrimRangeSet pr = factory->GetEmptySet();
       if (lt != min)
         pr = factory->Add(pr, Range(min, lt - one));
       RangeSet r(pr, false);
       DOUT << r << std::endl;
       return r;
     }

     PrimRangeSet newRanges = factory->GetEmptySet();

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       if (i->Includes(lt) && i->From() < lt)
         newRanges = factory->Add(newRanges, Range(i->From(), lt - one));
       else if (i->To() < lt)
         newRanges = factory->Add(newRanges, *i);
     }
     RangeSet r(newRanges);
     DOUT << r << std::endl;
     return r;
   }

   RangeSet AddLE(PrimRangeSet::Factory *factory, const llvm::APSInt &le) {
     DOUT << "AddLE(" << le.toString(10) << ") " << *this << " -> ";
     const llvm::APSInt min = Min(le);

     if (ranges.isEmpty()) {
       RangeSet r(factory->Add(ranges, Range(min, le)));
       DOUT << r << std::endl;
       return r;
     }

     PrimRangeSet newRanges = factory->GetEmptySet();

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       // Strictly we should test for includes le + 1, but no harm is
       // done by this formulation
       if (i->Includes(le))
         newRanges = factory->Add(newRanges, Range(i->From(), le));
       else if (i->To() <= le)
         newRanges = factory->Add(newRanges, *i);
     }
     RangeSet r(newRanges);
     DOUT << r << std::endl;
     return r;
   }

   RangeSet AddGT(PrimRangeSet::Factory *factory, const llvm::APSInt &gt) {
     DOUT << "AddGT(" << gt.toString(10) << ") " << *this << " -> ";
     const llvm::APSInt max = Max(gt);
     const llvm::APSInt one = One(gt);

     if (ranges.isEmpty()) {
       RangeSet r(factory->Add(ranges, Range(gt + one, max)));
       DOUT << r << std::endl;
       return r;
     }

     PrimRangeSet newRanges = factory->GetEmptySet();

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       if (i->Includes(gt) && i->To() > gt)
         newRanges = factory->Add(newRanges, Range(gt + one, i->To()));
       else if (i->From() > gt)
         newRanges = factory->Add(newRanges, *i);
     }
     RangeSet r(newRanges);
     DOUT << r << std::endl;
     return r;
   }

   RangeSet AddGE(PrimRangeSet::Factory *factory, const llvm::APSInt &ge) {
     DOUT << "AddGE(" << ge.toString(10) << ") " << *this << " -> ";
     const llvm::APSInt max = Max(ge);

     if (ranges.isEmpty()) {
       RangeSet r(factory->Add(ranges, Range(ge, max)));
       DOUT << r << std::endl;
       return r;
     }

     PrimRangeSet newRanges = factory->GetEmptySet();

     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       // Strictly we should test for includes ge - 1, but no harm is
       // done by this formulation
       if (i->Includes(ge))
         newRanges = factory->Add(newRanges, Range(ge, i->To()));
       else if (i->From() >= ge)
         newRanges = factory->Add(newRanges, *i);
     }

     RangeSet r(newRanges);
     DOUT << r << std::endl;
     return r;
   }

   void Print(std::ostream &os) const {
     os << "{ ";
     if (noValues) {
       os << "**no values** }";
       return;
     }
     for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
       if (i != ranges.begin())
         os << ", ";
       os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
          << ']';
     }
     os << " }";

 }
   bool operator==(const RangeSet &other) const {
     return ranges == other.ranges;
   }
 };

 std::ostream &operator<<(std::ostream &os, const RangeSet &r) {
   r.Print(os);
   return os;
 }

 typedef llvm::ImmutableMap<SymbolRef,RangeSet> ConstRangeTy;

 namespace clang {
 template<>
 struct GRStateTrait<ConstRange> : public GRStatePartialTrait<ConstRangeTy> {
   static inline void* GDMIndex() { return &ConstRangeIndex; }
 };
 }

 namespace {
 class VISIBILITY_HIDDEN RangeConstraintManager
   : public SimpleConstraintManager {
 public:
   RangeConstraintManager(GRStateManager& statemgr)
       : SimpleConstraintManager(statemgr) {}

   const GRState* AssumeSymNE(const GRState* St, SymbolRef sym,
                              const llvm::APSInt& V, bool& isFeasible);

   const GRState* AssumeSymEQ(const GRState* St, SymbolRef sym,
                                 const llvm::APSInt& V, bool& isFeasible);

   const GRState* AssumeSymLT(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible);

   const GRState* AssumeSymGT(const GRState* St, SymbolRef sym,
                              const llvm::APSInt& V, bool& isFeasible);

   const GRState* AssumeSymGE(const GRState* St, SymbolRef sym,
                              const llvm::APSInt& V, bool& isFeasible);

   const GRState* AssumeSymLE(const GRState* St, SymbolRef sym,
                              const llvm::APSInt& V, bool& isFeasible);

   const GRState* AddEQ(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   const GRState* AddNE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   const GRState* AddLT(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   const GRState* AddLE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   const GRState* AddGT(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   const GRState* AddGE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

   // FIXME: these two are required because they are pure virtual, but
   // are they useful with ranges? Neither is used in this file.
   const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) const;
   bool isEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;

   bool CouldBeEQ(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   bool CouldBeNE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;

   bool CouldBeLT(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   bool CouldBeLE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   bool CouldBeGT(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   bool CouldBeGE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
   const GRState* RemoveDeadBindings(const GRState* St, SymbolReaper& SymReaper);

   void print(const GRState* St, std::ostream& Out,
              const char* nl, const char *sep);

 private:
   PrimRangeSet::Factory factory;
   BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
 };

 } // end anonymous namespace

 ConstraintManager* clang::CreateRangeConstraintManager(GRStateManager& StateMgr)
 {
   return new RangeConstraintManager(StateMgr);
 }

 const GRState*
 RangeConstraintManager::AssumeSymNE(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {
   isFeasible = CouldBeNE(St, sym, V);
   if (isFeasible)
     return AddNE(St, sym, V);
   return St;
 }

 const GRState*
 RangeConstraintManager::AssumeSymEQ(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {
   isFeasible = CouldBeEQ(St, sym, V);
   if (isFeasible)
     return AddEQ(St, sym, V);
   return St;
 }

 const GRState*
 RangeConstraintManager::AssumeSymLT(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {

   // Is 'V' the smallest possible value?
   if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) {
     // sym cannot be any value less than 'V'.  This path is infeasible.
     isFeasible = false;
     return St;
   }

   isFeasible = CouldBeLT(St, sym, V);
   if (isFeasible)
     return AddLT(St, sym, V);

   return St;
 }

 const GRState*
 RangeConstraintManager::AssumeSymGT(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {

   // Is 'V' the largest possible value?
   if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) {
     // sym cannot be any value greater than 'V'.  This path is infeasible.
     isFeasible = false;
     return St;
   }

   isFeasible = CouldBeGT(St, sym, V);
   if (isFeasible)
     return AddGT(St, sym, V);

   return St;
 }

 const GRState*
 RangeConstraintManager::AssumeSymGE(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {

   isFeasible = CouldBeGE(St, sym, V);
   if (isFeasible)
     return AddGE(St, sym, V);

   return St;
 }

 const GRState*
 RangeConstraintManager::AssumeSymLE(const GRState* St, SymbolRef sym,
                                     const llvm::APSInt& V, bool& isFeasible) {

   isFeasible = CouldBeLT(St, sym, V);
   if (isFeasible)
     return AddLE(St, sym, V);

   return St;
 }

 const GRState* RangeConstraintManager::AddEQ(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   // Create a new state with the old binding replaced.
   GRStateRef state(St, StateMgr);
   RangeSet R(&factory);
   R = R.AddEQ(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const GRState* RangeConstraintManager::AddNE(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
   RangeSet R(&factory);
   if (T)
     R = *T;
   R = R.AddNE(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const GRState* RangeConstraintManager::AddLT(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
   RangeSet R(&factory);
   if (T)
     R = *T;
   R = R.AddLT(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const GRState* RangeConstraintManager::AddLE(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
   RangeSet R(&factory);
   if (T)
     R = *T;
   R = R.AddLE(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const GRState* RangeConstraintManager::AddGT(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
   RangeSet R(&factory);
   if (T)
     R = *T;
   R = R.AddGT(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const GRState* RangeConstraintManager::AddGE(const GRState* St, SymbolRef sym,
                                              const llvm::APSInt& V) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
   RangeSet R(&factory);
   if (T)
     R = *T;
   R = R.AddGE(&factory, V);
   return state.set<ConstRange>(sym, R);
 }

 const llvm::APSInt* RangeConstraintManager::getSymVal(const GRState* St,
                                                       SymbolRef sym) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->HasConcreteValue() : NULL;
 }

 bool RangeConstraintManager::CouldBeLT(const GRState* St, SymbolRef sym,
                                        const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeLT(V) : true;
 }

 bool RangeConstraintManager::CouldBeLE(const GRState* St, SymbolRef sym,
                                        const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeLE(V) : true;
 }

 bool RangeConstraintManager::CouldBeGT(const GRState* St, SymbolRef sym,
                                        const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeGT(V) : true;
 }

 bool RangeConstraintManager::CouldBeGE(const GRState* St, SymbolRef sym,
                                        const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeGE(V) : true;
 }

 bool RangeConstraintManager::CouldBeNE(const GRState* St, SymbolRef sym,
                                         const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeNE(V) : true;
 }

 bool RangeConstraintManager::CouldBeEQ(const GRState* St, SymbolRef sym,
                                         const llvm::APSInt& V) const {
   const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
   return T ? T->CouldBeEQ(V) : true;
 }

 bool RangeConstraintManager::isEqual(const GRState* St, SymbolRef sym,
                                      const llvm::APSInt& V) const {
   const llvm::APSInt *i = getSymVal(St, sym);
   return i ? *i == V : false;
 }

 /// Scan all symbols referenced by the constraints. If the symbol is not alive
 /// as marked in LSymbols, mark it as dead in DSymbols.
 const GRState*
 RangeConstraintManager::RemoveDeadBindings(const GRState* St,
                                            SymbolReaper& SymReaper) {
   GRStateRef state(St, StateMgr);

   ConstRangeTy CR = state.get<ConstRange>();
   ConstRangeTy::Factory& CRFactory = state.get_context<ConstRange>();

   for (ConstRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
     SymbolRef sym = I.getKey();
     if (SymReaper.maybeDead(sym))
       CR = CRFactory.Remove(CR, sym);
   }

   return state.set<ConstRange>(CR);
 }

 void RangeConstraintManager::print(const GRState* St, std::ostream& Out,
                                    const char* nl, const char *sep) {

   ConstRangeTy Ranges = St->get<ConstRange>();

   if (Ranges.isEmpty())
     return;

   Out << nl << sep << "ranges of symbol values:";

   for (ConstRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I) {
     Out << nl << " $" << I.getKey() << " : ";
     I.getData().Print(Out);
   }
 }
	//== RangeConstraintManager.cpp - Manage range constraints.------- C++ ---==//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//
	//
	// This file defines RangeConstraintManager, a class that tracks simple
	// equality and inequality constraints on symbolic values of GRState.
	//
	//===----------------------------------------------------------------------===//

	#include "SimpleConstraintManager.h"
	#include "clang/Analysis/PathSensitive/GRState.h"
	#include "clang/Analysis/PathSensitive/GRStateTrait.h"
	#include "clang/Analysis/PathSensitive/GRTransferFuncs.h"
	#include "clang/Driver/ManagerRegistry.h"
	#include "llvm/Support/Compiler.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/ADT/FoldingSet.h"
	#include "llvm/ADT/ImmutableSet.h"
	#include "llvm/Support/raw_ostream.h"

	using namespace clang;

	namespace { class VISIBILITY_HIDDEN ConstRange {}; }

	static int ConstRangeIndex = 0;

	// A Range represents the closed range [from, to]. The caller must
	// guarantee that from <= to. Note that Range is immutable, so as not
	// to subvert RangeSet's immutability.
	class Range : public std::pair<llvm::APSInt, llvm::APSInt> {
	public:
	Range(const llvm::APSInt &from, const llvm::APSInt &to)
	: std::pair<llvm::APSInt, llvm::APSInt>(from, to) {
	assert(from <= to);
	}
	bool Includes(const llvm::APSInt &v) const {
	return first <= v && v <= second;
	}
	const llvm::APSInt &From() const {
	return first;
	}
	const llvm::APSInt &To() const {
	return second;
	}
	const llvm::APSInt *HasConcreteValue() const {
	return From() == To() ? &From() : NULL;
	}

	void Profile(llvm::FoldingSetNodeID &ID) const {
	From().Profile(ID);
	To().Profile(ID);
	}
	};

	struct RangeCmp {
	bool operator()(const Range &r1, const Range &r2) {
	if (r1.From() < r2.From()) {
	assert(!r1.Includes(r2.From()));
	assert(!r2.Includes(r1.To()));
	return true;
	} else if (r1.From() > r2.From()) {
	assert(!r1.Includes(r2.To()));
	assert(!r2.Includes(r1.From()));
	return false;
	} else
	assert(!"Ranges should never be equal in the same set");
	}
	};

	typedef llvm::ImmutableSet<Range> PrimRangeSet;

	class RangeSet;
	std::ostream &operator<<(std::ostream &os, const RangeSet &r);


	// A RangeSet contains a set of ranges. If the set is empty, then
	// noValues -> Nothing matches.
	// !noValues -> Everything (in range of the bit representation) matches.
	class RangeSet {
	PrimRangeSet ranges; // no need to make const, since it is an
	// ImmutableSet - this allows default operator=
	// to work.
	bool noValues; // if true, no value is possible (should never happen)

	static const llvm::APSInt Max(const llvm::APSInt &v) {
	return llvm::APSInt::getMaxValue(v.getBitWidth(), v.isUnsigned());
	}
	static const llvm::APSInt Min(const llvm::APSInt &v) {
	return llvm::APSInt::getMinValue(v.getBitWidth(), v.isUnsigned());
	}
	static const llvm::APSInt One(const llvm::APSInt &v) {
	return llvm::APSInt(llvm::APInt(v.getBitWidth(), 1), v.isUnsigned());
	}

	public:
	// Create a RangeSet that allows all possible values.
	RangeSet(PrimRangeSet::Factory *factory) : ranges(factory->GetEmptySet()),
	noValues(false) {
	}
	// Note that if the empty set is passed, then there are no possible
	// values. To create a RangeSet that covers all values when the
	// empty set is passed, use RangeSet(r, false).
	RangeSet(const PrimRangeSet &r) : ranges(r), noValues(r.isEmpty()) {
	}
	// Allow an empty set to be passed meaning "all values" instead of
	// "no values".
	RangeSet(const PrimRangeSet &r, bool n) : ranges(r), noValues(n) {
	assert(!n);
	}
	void Profile(llvm::FoldingSetNodeID &ID) const {
	ranges.Profile(ID);
	ID.AddBoolean(noValues);
	}

	const llvm::APSInt *HasConcreteValue() const {
	if (!ranges.isSingleton())
	return NULL;
	return ranges.begin()->HasConcreteValue();
	}

	bool CouldBeNE(const llvm::APSInt &ne) const {
	DOUT << "CouldBeNE(" << ne.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	const llvm::APSInt *v = HasConcreteValue();
	if (v && *v == ne)
	return false;
	return true;
	}

	bool CouldBeEQ(const llvm::APSInt &eq) const {
	DOUT << "CouldBeEQ(" << eq.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	if (ranges.isEmpty())
	return true;
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
	if (i->Includes(eq))
	return true;
	return false;
	}

	bool CouldBeLT(const llvm::APSInt &lt) const {
	DOUT << "CouldBeLT(" << lt.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	// FIXME: should test if lt == min -> false here, since that's
	// impossible to meet.
	if (ranges.isEmpty())
	return true;
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
	if (i->From() < lt)
	return true;
	return false;
	}

	bool CouldBeLE(const llvm::APSInt &le) const {
	DOUT << "CouldBeLE(" << le.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	if (ranges.isEmpty())
	return true;
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
	if (i->From() <= le)
	return true;
	return false;
	}

	bool CouldBeGT(const llvm::APSInt &gt) const {
	DOUT << "CouldBeGT(" << gt.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	// FIXME: should we test if gt == max -> false here, since that's
	// impossible to meet.
	if (ranges.isEmpty())
	return true;
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
	if (i->To() > gt)
	return true;
	return false;
	}

	bool CouldBeGE(const llvm::APSInt &ge) const {
	DOUT << "CouldBeGE(" << ge.toString(10) << ") " << *this << std::endl;
	assert(!noValues);
	if (ranges.isEmpty())
	return true;
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i)
	if (i->To() >= ge)
	return true;
	return false;
	}

	// Make all existing ranges fall within this new range
	RangeSet Restrict(PrimRangeSet::Factory *factory, const llvm::APSInt &from,
	const llvm::APSInt &to) const {
	if (ranges.isEmpty())
	return factory->Add(ranges, Range(from, to));;

	PrimRangeSet newRanges = factory->GetEmptySet();

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	if (i->Includes(from)) {
	if (i->Includes(to)) {
	newRanges = factory->Add(newRanges, Range(from, to));
	} else {
	newRanges = factory->Add(newRanges, Range(from, i->To()));
	}
	} else if (i->Includes(to)) {
	newRanges = factory->Add(newRanges, Range(i->From(), to));
	}
	}
	return RangeSet(newRanges);
	}

	// Create a new RangeSet with the additional constraint that the
	// range must be == eq. In other words the range becomes [eq,
	// eq]. Note that this RangeSet must have included eq in the first
	// place, or we shouldn't be here.
	RangeSet AddEQ(PrimRangeSet::Factory *factory, const llvm::APSInt &eq) {
	DOUT << "AddEQ(" << eq.toString(10) << ") " << *this << " -> ";
	assert(CouldBeEQ(eq));
	RangeSet r(factory->Add(factory->GetEmptySet(), Range(eq, eq)));
	DOUT << r << std::endl;
	return r;
	}

	RangeSet AddNE(PrimRangeSet::Factory *factory, const llvm::APSInt &ne) {
	DOUT << "AddNE(" << ne.toString(10) << ") " << *this << " -> ";

	const llvm::APSInt max = Max(ne);
	const llvm::APSInt min = Min(ne);
	const llvm::APSInt one = One(ne);

	PrimRangeSet newRanges = factory->GetEmptySet();

	if (ranges.isEmpty()) {
	if (ne != max)
	newRanges = factory->Add(newRanges, Range(ne + one, max));
	if (ne != min)
	newRanges = factory->Add(newRanges, Range(min, ne - one));
	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	if (i->Includes(ne)) {
	if (ne != i->From())
	newRanges = factory->Add(newRanges, Range(i->From(), ne - one));
	if (ne != i->To())
	newRanges = factory->Add(newRanges, Range(ne + one, i->To()));
	} else {
	newRanges = factory->Add(newRanges, *i);
	}
	}
	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	RangeSet AddLT(PrimRangeSet::Factory *factory, const llvm::APSInt &lt) {
	DOUT << "AddLT(" << lt.toString(10) << ") " << *this << " -> ";
	const llvm::APSInt min = Min(lt);
	const llvm::APSInt one = One(lt);

	if (ranges.isEmpty()) {
	PrimRangeSet pr = factory->GetEmptySet();
	if (lt != min)
	pr = factory->Add(pr, Range(min, lt - one));
	RangeSet r(pr, false);
	DOUT << r << std::endl;
	return r;
	}

	PrimRangeSet newRanges = factory->GetEmptySet();

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	if (i->Includes(lt) && i->From() < lt)
	newRanges = factory->Add(newRanges, Range(i->From(), lt - one));
	else if (i->To() < lt)
	newRanges = factory->Add(newRanges, *i);
	}
	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	RangeSet AddLE(PrimRangeSet::Factory *factory, const llvm::APSInt &le) {
	DOUT << "AddLE(" << le.toString(10) << ") " << *this << " -> ";
	const llvm::APSInt min = Min(le);

	if (ranges.isEmpty()) {
	RangeSet r(factory->Add(ranges, Range(min, le)));
	DOUT << r << std::endl;
	return r;
	}

	PrimRangeSet newRanges = factory->GetEmptySet();

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	// Strictly we should test for includes le + 1, but no harm is
	// done by this formulation
	if (i->Includes(le))
	newRanges = factory->Add(newRanges, Range(i->From(), le));
	else if (i->To() <= le)
	newRanges = factory->Add(newRanges, *i);
	}
	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	RangeSet AddGT(PrimRangeSet::Factory *factory, const llvm::APSInt &gt) {
	DOUT << "AddGT(" << gt.toString(10) << ") " << *this << " -> ";
	const llvm::APSInt max = Max(gt);
	const llvm::APSInt one = One(gt);

	if (ranges.isEmpty()) {
	RangeSet r(factory->Add(ranges, Range(gt + one, max)));
	DOUT << r << std::endl;
	return r;
	}

	PrimRangeSet newRanges = factory->GetEmptySet();

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	if (i->Includes(gt) && i->To() > gt)
	newRanges = factory->Add(newRanges, Range(gt + one, i->To()));
	else if (i->From() > gt)
	newRanges = factory->Add(newRanges, *i);
	}
	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	RangeSet AddGE(PrimRangeSet::Factory *factory, const llvm::APSInt &ge) {
	DOUT << "AddGE(" << ge.toString(10) << ") " << *this << " -> ";
	const llvm::APSInt max = Max(ge);

	if (ranges.isEmpty()) {
	RangeSet r(factory->Add(ranges, Range(ge, max)));
	DOUT << r << std::endl;
	return r;
	}

	PrimRangeSet newRanges = factory->GetEmptySet();

	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	// Strictly we should test for includes ge - 1, but no harm is
	// done by this formulation
	if (i->Includes(ge))
	newRanges = factory->Add(newRanges, Range(ge, i->To()));
	else if (i->From() >= ge)
	newRanges = factory->Add(newRanges, *i);
	}

	RangeSet r(newRanges);
	DOUT << r << std::endl;
	return r;
	}

	void Print(std::ostream &os) const {
	os << "{ ";
	if (noValues) {
	os << "no values }";
	return;
	}
	for (PrimRangeSet::iterator i = ranges.begin() ; i != ranges.end() ; ++i) {
	if (i != ranges.begin())
	os << ", ";
	os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
	<< ']';
	}
	os << " }";

	}
	bool operator==(const RangeSet &other) const {
	return ranges == other.ranges;
	}
	};

	std::ostream &operator<<(std::ostream &os, const RangeSet &r) {
	r.Print(os);
	return os;
	}

	typedef llvm::ImmutableMap<SymbolRef,RangeSet> ConstRangeTy;

	namespace clang {
	template<>
	struct GRStateTrait<ConstRange> : public GRStatePartialTrait<ConstRangeTy> {
	static inline void* GDMIndex() { return &ConstRangeIndex; }
	};
	}

	namespace {
	class VISIBILITY_HIDDEN RangeConstraintManager
	: public SimpleConstraintManager {
	public:
	RangeConstraintManager(GRStateManager& statemgr)
	: SimpleConstraintManager(statemgr) {}

	const GRState* AssumeSymNE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AssumeSymEQ(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AssumeSymLT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AssumeSymGT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AssumeSymGE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AssumeSymLE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible);

	const GRState* AddEQ(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	const GRState* AddNE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	const GRState* AddLT(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	const GRState* AddLE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	const GRState* AddGT(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	const GRState* AddGE(const GRState* St, SymbolRef sym, const llvm::APSInt& V);

	// FIXME: these two are required because they are pure virtual, but
	// are they useful with ranges? Neither is used in this file.
	const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) const;
	bool isEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;

	bool CouldBeEQ(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
	bool CouldBeNE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;

	bool CouldBeLT(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
	bool CouldBeLE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
	bool CouldBeGT(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
	bool CouldBeGE(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const;
	const GRState* RemoveDeadBindings(const GRState* St, SymbolReaper& SymReaper);

	void print(const GRState* St, std::ostream& Out,
	const char* nl, const char *sep);

	private:
	PrimRangeSet::Factory factory;
	BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
	};

	} // end anonymous namespace

	ConstraintManager* clang::CreateRangeConstraintManager(GRStateManager& StateMgr)
	{
	return new RangeConstraintManager(StateMgr);
	}

	const GRState*
	RangeConstraintManager::AssumeSymNE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {
	isFeasible = CouldBeNE(St, sym, V);
	if (isFeasible)
	return AddNE(St, sym, V);
	return St;
	}

	const GRState*
	RangeConstraintManager::AssumeSymEQ(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {
	isFeasible = CouldBeEQ(St, sym, V);
	if (isFeasible)
	return AddEQ(St, sym, V);
	return St;
	}

	const GRState*
	RangeConstraintManager::AssumeSymLT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {

	// Is 'V' the smallest possible value?
	if (V == llvm::APSInt::getMinValue(V.getBitWidth(), V.isUnsigned())) {
	// sym cannot be any value less than 'V'. This path is infeasible.
	isFeasible = false;
	return St;
	}

	isFeasible = CouldBeLT(St, sym, V);
	if (isFeasible)
	return AddLT(St, sym, V);

	return St;
	}

	const GRState*
	RangeConstraintManager::AssumeSymGT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {

	// Is 'V' the largest possible value?
	if (V == llvm::APSInt::getMaxValue(V.getBitWidth(), V.isUnsigned())) {
	// sym cannot be any value greater than 'V'. This path is infeasible.
	isFeasible = false;
	return St;
	}

	isFeasible = CouldBeGT(St, sym, V);
	if (isFeasible)
	return AddGT(St, sym, V);

	return St;
	}

	const GRState*
	RangeConstraintManager::AssumeSymGE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {

	isFeasible = CouldBeGE(St, sym, V);
	if (isFeasible)
	return AddGE(St, sym, V);

	return St;
	}

	const GRState*
	RangeConstraintManager::AssumeSymLE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V, bool& isFeasible) {

	isFeasible = CouldBeLT(St, sym, V);
	if (isFeasible)
	return AddLE(St, sym, V);

	return St;
	}

	const GRState* RangeConstraintManager::AddEQ(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	// Create a new state with the old binding replaced.
	GRStateRef state(St, StateMgr);
	RangeSet R(&factory);
	R = R.AddEQ(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const GRState* RangeConstraintManager::AddNE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
	RangeSet R(&factory);
	if (T)
	R = *T;
	R = R.AddNE(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const GRState* RangeConstraintManager::AddLT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
	RangeSet R(&factory);
	if (T)
	R = *T;
	R = R.AddLT(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const GRState* RangeConstraintManager::AddLE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
	RangeSet R(&factory);
	if (T)
	R = *T;
	R = R.AddLE(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const GRState* RangeConstraintManager::AddGT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
	RangeSet R(&factory);
	if (T)
	R = *T;
	R = R.AddGT(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const GRState* RangeConstraintManager::AddGE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy::data_type* T = state.get<ConstRange>(sym);
	RangeSet R(&factory);
	if (T)
	R = *T;
	R = R.AddGE(&factory, V);
	return state.set<ConstRange>(sym, R);
	}

	const llvm::APSInt* RangeConstraintManager::getSymVal(const GRState* St,
	SymbolRef sym) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->HasConcreteValue() : NULL;
	}

	bool RangeConstraintManager::CouldBeLT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeLT(V) : true;
	}

	bool RangeConstraintManager::CouldBeLE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeLE(V) : true;
	}

	bool RangeConstraintManager::CouldBeGT(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeGT(V) : true;
	}

	bool RangeConstraintManager::CouldBeGE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeGE(V) : true;
	}

	bool RangeConstraintManager::CouldBeNE(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeNE(V) : true;
	}

	bool RangeConstraintManager::CouldBeEQ(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const ConstRangeTy::data_type *T = St->get<ConstRange>(sym);
	return T ? T->CouldBeEQ(V) : true;
	}

	bool RangeConstraintManager::isEqual(const GRState* St, SymbolRef sym,
	const llvm::APSInt& V) const {
	const llvm::APSInt *i = getSymVal(St, sym);
	return i ? *i == V : false;
	}

	/// Scan all symbols referenced by the constraints. If the symbol is not alive
	/// as marked in LSymbols, mark it as dead in DSymbols.
	const GRState*
	RangeConstraintManager::RemoveDeadBindings(const GRState* St,
	SymbolReaper& SymReaper) {
	GRStateRef state(St, StateMgr);

	ConstRangeTy CR = state.get<ConstRange>();
	ConstRangeTy::Factory& CRFactory = state.get_context<ConstRange>();

	for (ConstRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
	SymbolRef sym = I.getKey();
	if (SymReaper.maybeDead(sym))
	CR = CRFactory.Remove(CR, sym);
	}

	return state.set<ConstRange>(CR);
	}

	void RangeConstraintManager::print(const GRState* St, std::ostream& Out,
	const char* nl, const char *sep) {

	ConstRangeTy Ranges = St->get<ConstRange>();

	if (Ranges.isEmpty())
	return;

	Out << nl << sep << "ranges of symbol values:";

	for (ConstRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I) {
	Out << nl << " $" << I.getKey() << " : ";
	I.getData().Print(Out);
	}
	}