lib/Checker/FlatStore.cpp

   1 //=== FlatStore.cpp - Flat region-based store model -------------*- 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 #include "clang/Checker/PathSensitive/GRState.h"
  11 #include "llvm/ADT/ImmutableIntervalMap.h"
  12 #include "llvm/Support/ErrorHandling.h"
  13
  14 using namespace clang;
  15 using llvm::Interval;
  16
  17 // The actual store type.
  18 typedef llvm::ImmutableIntervalMap<SVal> BindingVal;
  19 typedef llvm::ImmutableMap<const MemRegion *, BindingVal> RegionBindings;
  20
  21 namespace {
  22 class FlatStoreManager : public StoreManager {
  23   RegionBindings::Factory RBFactory;
  24   BindingVal::Factory BVFactory;
  25
  26 public:
  27   FlatStoreManager(GRStateManager &mgr)
  28     : StoreManager(mgr),
  29       RBFactory(mgr.getAllocator()),
  30       BVFactory(mgr.getAllocator()) {}
  31
  32   SVal Retrieve(Store store, Loc L, QualType T);
  33   Store Bind(Store store, Loc L, SVal val);
  34   Store Remove(Store St, Loc L);
  35   Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* cl,
  36                             const LocationContext *LC, SVal v);
  37
  38   Store getInitialStore(const LocationContext *InitLoc) {
  39     return RBFactory.GetEmptyMap().getRoot();
  40   }
  41
  42   SubRegionMap *getSubRegionMap(Store store) {
  43     return 0;
  44   }
  45
  46   SVal ArrayToPointer(Loc Array);
  47   Store RemoveDeadBindings(Store store, Stmt* Loc, SymbolReaper& SymReaper,
  48                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
  49     return store;
  50   }
  51
  52   Store BindDecl(Store store, const VarRegion *VR, SVal initVal);
  53
  54   Store BindDeclWithNoInit(Store store, const VarRegion *VR);
  55
  56   typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
  57
  58   Store InvalidateRegion(Store store, const MemRegion *R, const Expr *E,
  59                          unsigned Count, InvalidatedSymbols *IS);
  60
  61   void print(Store store, llvm::raw_ostream& Out, const char* nl,
  62              const char *sep);
  63   void iterBindings(Store store, BindingsHandler& f);
  64
  65 private:
  66   static RegionBindings getRegionBindings(Store store) {
  67     return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
  68   }
  69
  70   Interval RegionToInterval(const MemRegion *R);
  71
  72   SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
  73 };
  74 } // end anonymous namespace
  75
  76 StoreManager *clang::CreateFlatStoreManager(GRStateManager &StMgr) {
  77   return new FlatStoreManager(StMgr);
  78 }
  79
  80 SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
  81   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
  82   Interval I = RegionToInterval(R);
  83   RegionBindings B = getRegionBindings(store);
  84   const BindingVal *BV = B.lookup(R);
  85   if (BV) {
  86     const SVal *V = BVFactory.Lookup(*BV, I);
  87     if (V)
  88       return *V;
  89     else
  90       return RetrieveRegionWithNoBinding(R, T);
  91   }
  92   return RetrieveRegionWithNoBinding(R, T);
  93 }
  94
  95 SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
  96                                                    QualType T) {
  97   if (R->hasStackNonParametersStorage())
  98     return UndefinedVal();
  99   else
 100     return ValMgr.getRegionValueSymbolVal(R, T);
 101 }
 102
 103 Store FlatStoreManager::Bind(Store store, Loc L, SVal val) {
 104   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
 105   RegionBindings B = getRegionBindings(store);
 106   const BindingVal *V = B.lookup(R);
 107
 108   BindingVal BV = BVFactory.GetEmptyMap();
 109   if (V)
 110     BV = *V;
 111
 112   Interval I = RegionToInterval(R);
 113   BV = BVFactory.Add(BV, I, val);
 114   B = RBFactory.Add(B, R, BV);
 115   return B.getRoot();
 116 }
 117
 118 Store FlatStoreManager::Remove(Store store, Loc L) {
 119   return store;
 120 }
 121
 122 Store FlatStoreManager::BindCompoundLiteral(Store store,
 123                                             const CompoundLiteralExpr* cl,
 124                                             const LocationContext *LC,
 125                                             SVal v) {
 126   return store;
 127 }
 128
 129 SVal FlatStoreManager::ArrayToPointer(Loc Array) {
 130   return Array;
 131 }
 132
 133 Store FlatStoreManager::BindDecl(Store store, const VarRegion *VR,
 134                                  SVal initVal) {
 135   return store;
 136 }
 137
 138 Store FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR) {
 139   return store;
 140 }
 141
 142 Store FlatStoreManager::InvalidateRegion(Store store, const MemRegion *R,
 143                                          const Expr *E, unsigned Count,
 144                                          InvalidatedSymbols *IS) {
 145   return store;
 146 }
 147
 148 void FlatStoreManager::print(Store store, llvm::raw_ostream& Out,
 149                              const char* nl, const char *sep) {
 150 }
 151
 152 void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
 153 }
 154
 155 Interval FlatStoreManager::RegionToInterval(const MemRegion *R) {
 156   switch (R->getKind()) {
 157   case MemRegion::VarRegionKind: {
 158     QualType T = cast<VarRegion>(R)->getValueType(Ctx);
 159     uint64_t Size = Ctx.getTypeSize(T);
 160     return Interval(0, Size-1);
 161   }
 162   default:
 163     llvm_unreachable("Region kind unhandled.");
 164     return Interval(0, 0);
 165   }
 166 }