lib/Checker/GRState.cpp

   1 //= GRState.cpp - Path-Sensitive "State" for tracking values -----*- C++ -*--=//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file implements GRState and GRStateManager.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "clang/Checker/PathSensitive/GRStateTrait.h"
  15 #include "clang/Checker/PathSensitive/GRState.h"
  16 #include "clang/Checker/PathSensitive/GRTransferFuncs.h"
  17 #include "llvm/ADT/SmallSet.h"
  18 #include "llvm/Support/raw_ostream.h"
  19
  20 using namespace clang;
  21
  22 // Give the vtable for ConstraintManager somewhere to live.
  23 // FIXME: Move this elsewhere.
  24 ConstraintManager::~ConstraintManager() {}
  25
  26 GRStateManager::~GRStateManager() {
  27   for (std::vector<GRState::Printer*>::iterator I=Printers.begin(),
  28         E=Printers.end(); I!=E; ++I)
  29     delete *I;
  30
  31   for (GDMContextsTy::iterator I=GDMContexts.begin(), E=GDMContexts.end();
  32        I!=E; ++I)
  33     I->second.second(I->second.first);
  34 }
  35
  36 const GRState*
  37 GRStateManager::RemoveDeadBindings(const GRState* state, Stmt* Loc,
  38                                    SymbolReaper& SymReaper) {
  39
  40   // This code essentially performs a "mark-and-sweep" of the VariableBindings.
  41   // The roots are any Block-level exprs and Decls that our liveness algorithm
  42   // tells us are live.  We then see what Decls they may reference, and keep
  43   // those around.  This code more than likely can be made faster, and the
  44   // frequency of which this method is called should be experimented with
  45   // for optimum performance.
  46   llvm::SmallVector<const MemRegion*, 10> RegionRoots;
  47   GRState NewState = *state;
  48
  49   NewState.Env = EnvMgr.RemoveDeadBindings(NewState.Env, Loc, SymReaper,
  50                                            state, RegionRoots);
  51
  52   // Clean up the store.
  53   NewState.St = StoreMgr->RemoveDeadBindings(NewState.St, Loc, SymReaper,
  54                                              RegionRoots);
  55
  56   return ConstraintMgr->RemoveDeadBindings(getPersistentState(NewState),
  57                                            SymReaper);
  58 }
  59
  60 const GRState *GRState::unbindLoc(Loc LV) const {
  61   Store OldStore = getStore();
  62   Store NewStore = getStateManager().StoreMgr->Remove(OldStore, LV);
  63
  64   if (NewStore == OldStore)
  65     return this;
  66
  67   GRState NewSt = *this;
  68   NewSt.St = NewStore;
  69   return getStateManager().getPersistentState(NewSt);
  70 }
  71
  72 SVal GRState::getSValAsScalarOrLoc(const MemRegion *R) const {
  73   // We only want to do fetches from regions that we can actually bind
  74   // values.  For example, SymbolicRegions of type 'id<...>' cannot
  75   // have direct bindings (but their can be bindings on their subregions).
  76   if (!R->isBoundable())
  77     return UnknownVal();
  78
  79   if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
  80     QualType T = TR->getValueType(getStateManager().getContext());
  81     if (Loc::IsLocType(T) || T->isIntegerType())
  82       return getSVal(R);
  83   }
  84
  85   return UnknownVal();
  86 }
  87
  88
  89 const GRState *GRState::BindExpr(const Stmt* Ex, SVal V, bool Invalidate) const{
  90   Environment NewEnv = getStateManager().EnvMgr.BindExpr(Env, Ex, V,
  91                                                          Invalidate);
  92   if (NewEnv == Env)
  93     return this;
  94
  95   GRState NewSt = *this;
  96   NewSt.Env = NewEnv;
  97   return getStateManager().getPersistentState(NewSt);
  98 }
  99
 100 const GRState* GRStateManager::getInitialState(const LocationContext *InitLoc) {
 101   GRState State(this,
 102                 EnvMgr.getInitialEnvironment(InitLoc->getAnalysisContext()),
 103                 StoreMgr->getInitialStore(InitLoc),
 104                 GDMFactory.GetEmptyMap());
 105
 106   return getPersistentState(State);
 107 }
 108
 109 const GRState* GRStateManager::getPersistentState(GRState& State) {
 110
 111   llvm::FoldingSetNodeID ID;
 112   State.Profile(ID);
 113   void* InsertPos;
 114
 115   if (GRState* I = StateSet.FindNodeOrInsertPos(ID, InsertPos))
 116     return I;
 117
 118   GRState* I = (GRState*) Alloc.Allocate<GRState>();
 119   new (I) GRState(State);
 120   StateSet.InsertNode(I, InsertPos);
 121   return I;
 122 }
 123
 124 const GRState* GRState::makeWithStore(Store store) const {
 125   GRState NewSt = *this;
 126   NewSt.St = store;
 127   return getStateManager().getPersistentState(NewSt);
 128 }
 129
 130 //===----------------------------------------------------------------------===//
 131 //  State pretty-printing.
 132 //===----------------------------------------------------------------------===//
 133
 134 void GRState::print(llvm::raw_ostream& Out, const char* nl,
 135                     const char* sep) const {
 136   // Print the store.
 137   GRStateManager &Mgr = getStateManager();
 138   Mgr.getStoreManager().print(getStore(), Out, nl, sep);
 139
 140   CFG &C = *getAnalysisContext().getCFG();
 141
 142   // Print Subexpression bindings.
 143   bool isFirst = true;
 144
 145   for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) {
 146     if (C.isBlkExpr(I.getKey()))
 147       continue;
 148
 149     if (isFirst) {
 150       Out << nl << nl << "Sub-Expressions:" << nl;
 151       isFirst = false;
 152     }
 153     else { Out << nl; }
 154
 155     Out << " (" << (void*) I.getKey() << ") ";
 156     LangOptions LO; // FIXME.
 157     I.getKey()->printPretty(Out, 0, PrintingPolicy(LO));
 158     Out << " : " << I.getData();
 159   }
 160
 161   // Print block-expression bindings.
 162   isFirst = true;
 163
 164   for (Environment::iterator I = Env.begin(), E = Env.end(); I != E; ++I) {
 165     if (!C.isBlkExpr(I.getKey()))
 166       continue;
 167
 168     if (isFirst) {
 169       Out << nl << nl << "Block-level Expressions:" << nl;
 170       isFirst = false;
 171     }
 172     else { Out << nl; }
 173
 174     Out << " (" << (void*) I.getKey() << ") ";
 175     LangOptions LO; // FIXME.
 176     I.getKey()->printPretty(Out, 0, PrintingPolicy(LO));
 177     Out << " : " << I.getData();
 178   }
 179
 180   Mgr.getConstraintManager().print(this, Out, nl, sep);
 181
 182   // Print checker-specific data.
 183   for (std::vector<Printer*>::iterator I = Mgr.Printers.begin(),
 184                                        E = Mgr.Printers.end(); I != E; ++I) {
 185     (*I)->Print(Out, this, nl, sep);
 186   }
 187 }
 188
 189 void GRState::printDOT(llvm::raw_ostream& Out) const {
 190   print(Out, "\\l", "\\|");
 191 }
 192
 193 void GRState::printStdErr() const {
 194   print(llvm::errs());
 195 }
 196
 197 //===----------------------------------------------------------------------===//
 198 // Generic Data Map.
 199 //===----------------------------------------------------------------------===//
 200
 201 void* const* GRState::FindGDM(void* K) const {
 202   return GDM.lookup(K);
 203 }
 204
 205 void*
 206 GRStateManager::FindGDMContext(void* K,
 207                                void* (*CreateContext)(llvm::BumpPtrAllocator&),
 208                                void (*DeleteContext)(void*)) {
 209
 210   std::pair<void*, void (*)(void*)>& p = GDMContexts[K];
 211   if (!p.first) {
 212     p.first = CreateContext(Alloc);
 213     p.second = DeleteContext;
 214   }
 215
 216   return p.first;
 217 }
 218
 219 const GRState* GRStateManager::addGDM(const GRState* St, void* Key, void* Data){
 220   GRState::GenericDataMap M1 = St->getGDM();
 221   GRState::GenericDataMap M2 = GDMFactory.Add(M1, Key, Data);
 222
 223   if (M1 == M2)
 224     return St;
 225
 226   GRState NewSt = *St;
 227   NewSt.GDM = M2;
 228   return getPersistentState(NewSt);
 229 }
 230
 231 //===----------------------------------------------------------------------===//
 232 // Utility.
 233 //===----------------------------------------------------------------------===//
 234
 235 namespace {
 236 class ScanReachableSymbols : public SubRegionMap::Visitor  {
 237   typedef llvm::DenseSet<const MemRegion*> VisitedRegionsTy;
 238
 239   VisitedRegionsTy visited;
 240   const GRState *state;
 241   SymbolVisitor &visitor;
 242   llvm::OwningPtr<SubRegionMap> SRM;
 243 public:
 244
 245   ScanReachableSymbols(const GRState *st, SymbolVisitor& v)
 246     : state(st), visitor(v) {}
 247
 248   bool scan(nonloc::CompoundVal val);
 249   bool scan(SVal val);
 250   bool scan(const MemRegion *R);
 251
 252   // From SubRegionMap::Visitor.
 253   bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) {
 254     return scan(SubRegion);
 255   }
 256 };
 257 }
 258
 259 bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
 260   for (nonloc::CompoundVal::iterator I=val.begin(), E=val.end(); I!=E; ++I)
 261     if (!scan(*I))
 262       return false;
 263
 264   return true;
 265 }
 266
 267 bool ScanReachableSymbols::scan(SVal val) {
 268   if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val))
 269     return scan(X->getRegion());
 270
 271   if (nonloc::LocAsInteger *X = dyn_cast<nonloc::LocAsInteger>(&val))
 272     return scan(X->getLoc());
 273
 274   if (SymbolRef Sym = val.getAsSymbol())
 275     return visitor.VisitSymbol(Sym);
 276
 277   if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val))
 278     return scan(*X);
 279
 280   return true;
 281 }
 282
 283 bool ScanReachableSymbols::scan(const MemRegion *R) {
 284   if (isa<MemSpaceRegion>(R) || visited.count(R))
 285     return true;
 286
 287   visited.insert(R);
 288
 289   // If this is a symbolic region, visit the symbol for the region.
 290   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
 291     if (!visitor.VisitSymbol(SR->getSymbol()))
 292       return false;
 293
 294   // If this is a subregion, also visit the parent regions.
 295   if (const SubRegion *SR = dyn_cast<SubRegion>(R))
 296     if (!scan(SR->getSuperRegion()))
 297       return false;
 298
 299   // Now look at the binding to this region (if any).
 300   if (!scan(state->getSValAsScalarOrLoc(R)))
 301     return false;
 302
 303   // Now look at the subregions.
 304   if (!SRM.get())
 305     SRM.reset(state->getStateManager().getStoreManager().
 306                                            getSubRegionMap(state->getStore()));
 307
 308   return SRM->iterSubRegions(R, *this);
 309 }
 310
 311 bool GRState::scanReachableSymbols(SVal val, SymbolVisitor& visitor) const {
 312   ScanReachableSymbols S(this, visitor);
 313   return S.scan(val);
 314 }
 315
 316 bool GRState::scanReachableSymbols(const SVal *I, const SVal *E,
 317                                    SymbolVisitor &visitor) const {
 318   ScanReachableSymbols S(this, visitor);
 319   for ( ; I != E; ++I) {
 320     if (!S.scan(*I))
 321       return false;
 322   }
 323   return true;
 324 }
 325
 326 bool GRState::scanReachableSymbols(const MemRegion * const *I,
 327                                    const MemRegion * const *E,
 328                                    SymbolVisitor &visitor) const {
 329   ScanReachableSymbols S(this, visitor);
 330   for ( ; I != E; ++I) {
 331     if (!S.scan(*I))
 332       return false;
 333   }
 334   return true;
 335 }
 336
 337 //===----------------------------------------------------------------------===//
 338 // Queries.
 339 //===----------------------------------------------------------------------===//
 340
 341 bool GRStateManager::isEqual(const GRState* state, const Expr* Ex,
 342                              const llvm::APSInt& Y) {
 343
 344   SVal V = state->getSVal(Ex);
 345
 346   if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V))
 347     return X->getValue() == Y;
 348
 349   if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V))
 350     return X->getValue() == Y;
 351
 352   if (SymbolRef Sym = V.getAsSymbol())
 353     return ConstraintMgr->isEqual(state, Sym, Y);
 354
 355   return false;
 356 }
 357
 358 bool GRStateManager::isEqual(const GRState* state, const Expr* Ex, uint64_t x) {
 359   return isEqual(state, Ex, getBasicVals().getValue(x, Ex->getType()));
 360 }