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/GR/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, const StackFrameContext *LCtx,
  48                            SymbolReaper& SymReaper,
  49                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
  50     return store;
  51   }
  52
  53   Store BindDecl(Store store, const VarRegion *VR, SVal initVal);
  54
  55   Store BindDeclWithNoInit(Store store, const VarRegion *VR);
  56
  57   typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
  58
  59   Store InvalidateRegions(Store store, const MemRegion * const *I,
  60                           const MemRegion * const *E, const Expr *Ex,
  61                           unsigned Count, InvalidatedSymbols *IS,
  62                           bool invalidateGlobals, InvalidatedRegions *Regions);
  63
  64   void print(Store store, llvm::raw_ostream& Out, const char* nl,
  65              const char *sep);
  66   void iterBindings(Store store, BindingsHandler& f);
  67
  68 private:
  69   static RegionBindings getRegionBindings(Store store) {
  70     return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
  71   }
  72
  73   class RegionInterval {
  74   public:
  75     const MemRegion *R;
  76     Interval I;
  77     RegionInterval(const MemRegion *r, int64_t s, int64_t e) : R(r), I(s, e){}
  78   };
  79
  80   RegionInterval RegionToInterval(const MemRegion *R);
  81
  82   SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
  83 };
  84 } // end anonymous namespace
  85
  86 StoreManager *clang::CreateFlatStoreManager(GRStateManager &StMgr) {
  87   return new FlatStoreManager(StMgr);
  88 }
  89
  90 SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
  91   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
  92   RegionInterval RI = RegionToInterval(R);
  93   // FIXME: FlatStore should handle regions with unknown intervals.
  94   if (!RI.R)
  95     return UnknownVal();
  96
  97   RegionBindings B = getRegionBindings(store);
  98   const BindingVal *BV = B.lookup(RI.R);
  99   if (BV) {
 100     const SVal *V = BVFactory.lookup(*BV, RI.I);
 101     if (V)
 102       return *V;
 103     else
 104       return RetrieveRegionWithNoBinding(R, T);
 105   }
 106   return RetrieveRegionWithNoBinding(R, T);
 107 }
 108
 109 SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
 110                                                    QualType T) {
 111   if (R->hasStackNonParametersStorage())
 112     return UndefinedVal();
 113   else
 114     return svalBuilder.getRegionValueSymbolVal(cast<TypedRegion>(R));
 115 }
 116
 117 Store FlatStoreManager::Bind(Store store, Loc L, SVal val) {
 118   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
 119   RegionBindings B = getRegionBindings(store);
 120   const BindingVal *V = B.lookup(R);
 121
 122   BindingVal BV = BVFactory.getEmptyMap();
 123   if (V)
 124     BV = *V;
 125
 126   RegionInterval RI = RegionToInterval(R);
 127   // FIXME: FlatStore should handle regions with unknown intervals.
 128   if (!RI.R)
 129     return B.getRoot();
 130   BV = BVFactory.add(BV, RI.I, val);
 131   B = RBFactory.add(B, RI.R, BV);
 132   return B.getRoot();
 133 }
 134
 135 Store FlatStoreManager::Remove(Store store, Loc L) {
 136   return store;
 137 }
 138
 139 Store FlatStoreManager::BindCompoundLiteral(Store store,
 140                                             const CompoundLiteralExpr* cl,
 141                                             const LocationContext *LC,
 142                                             SVal v) {
 143   return store;
 144 }
 145
 146 SVal FlatStoreManager::ArrayToPointer(Loc Array) {
 147   return Array;
 148 }
 149
 150 Store FlatStoreManager::BindDecl(Store store, const VarRegion *VR,
 151                                  SVal initVal) {
 152   return Bind(store, svalBuilder.makeLoc(VR), initVal);
 153 }
 154
 155 Store FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR) {
 156   return store;
 157 }
 158
 159 Store FlatStoreManager::InvalidateRegions(Store store,
 160                                           const MemRegion * const *I,
 161                                           const MemRegion * const *E,
 162                                           const Expr *Ex, unsigned Count,
 163                                           InvalidatedSymbols *IS,
 164                                           bool invalidateGlobals,
 165                                           InvalidatedRegions *Regions) {
 166   assert(false && "Not implemented");
 167   return store;
 168 }
 169
 170 void FlatStoreManager::print(Store store, llvm::raw_ostream& Out,
 171                              const char* nl, const char *sep) {
 172 }
 173
 174 void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
 175 }
 176
 177 FlatStoreManager::RegionInterval
 178 FlatStoreManager::RegionToInterval(const MemRegion *R) {
 179   switch (R->getKind()) {
 180   case MemRegion::VarRegionKind: {
 181     QualType T = cast<VarRegion>(R)->getValueType();
 182     int64_t Size = Ctx.getTypeSize(T);
 183     return RegionInterval(R, 0, Size-1);
 184   }
 185
 186   case MemRegion::ElementRegionKind:
 187   case MemRegion::FieldRegionKind: {
 188     RegionOffset Offset = R->getAsOffset();
 189     // We cannot compute offset for all regions, for example, elements
 190     // with symbolic offsets.
 191     if (!Offset.getRegion())
 192       return RegionInterval(0, 0, 0);
 193     int64_t Start = Offset.getOffset();
 194     int64_t Size = Ctx.getTypeSize(cast<TypedRegion>(R)->getValueType());
 195     return RegionInterval(Offset.getRegion(), Start, Start+Size);
 196   }
 197
 198   default:
 199     llvm_unreachable("Region kind unhandled.");
 200     return RegionInterval(0, 0, 0);
 201   }
 202 }