contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/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/StaticAnalyzer/Core/PathSensitive/GRState.h"
  11 #include "llvm/ADT/ImmutableIntervalMap.h"
  12 #include "llvm/Support/ErrorHandling.h"
  13
  14 using namespace clang;
  15 using namespace ento;
  16 using llvm::Interval;
  17
  18 // The actual store type.
  19 typedef llvm::ImmutableIntervalMap<SVal> BindingVal;
  20 typedef llvm::ImmutableMap<const MemRegion *, BindingVal> RegionBindings;
  21
  22 namespace {
  23 class FlatStoreManager : public StoreManager {
  24   RegionBindings::Factory RBFactory;
  25   BindingVal::Factory BVFactory;
  26
  27 public:
  28   FlatStoreManager(GRStateManager &mgr)
  29     : StoreManager(mgr),
  30       RBFactory(mgr.getAllocator()),
  31       BVFactory(mgr.getAllocator()) {}
  32
  33   SVal Retrieve(Store store, Loc L, QualType T);
  34   StoreRef Bind(Store store, Loc L, SVal val);
  35   StoreRef Remove(Store St, Loc L);
  36   StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr* cl,
  37                             const LocationContext *LC, SVal v);
  38
  39   StoreRef getInitialStore(const LocationContext *InitLoc) {
  40     return StoreRef(RBFactory.getEmptyMap().getRoot(), *this);
  41   }
  42
  43   SubRegionMap *getSubRegionMap(Store store) {
  44     return 0;
  45   }
  46
  47   SVal ArrayToPointer(Loc Array);
  48   StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
  49                               SymbolReaper& SymReaper,
  50                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
  51     return StoreRef(store, *this);
  52   }
  53
  54   StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal);
  55
  56   StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR);
  57
  58   typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
  59
  60   StoreRef invalidateRegions(Store store, const MemRegion * const *I,
  61                              const MemRegion * const *E, const Expr *Ex,
  62                              unsigned Count, InvalidatedSymbols &IS,
  63                              bool invalidateGlobals,
  64                              InvalidatedRegions *Regions);
  65
  66   void print(Store store, llvm::raw_ostream& Out, const char* nl,
  67              const char *sep);
  68   void iterBindings(Store store, BindingsHandler& f);
  69
  70 private:
  71   static RegionBindings getRegionBindings(Store store) {
  72     return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
  73   }
  74
  75   class RegionInterval {
  76   public:
  77     const MemRegion *R;
  78     Interval I;
  79     RegionInterval(const MemRegion *r, int64_t s, int64_t e) : R(r), I(s, e){}
  80   };
  81
  82   RegionInterval RegionToInterval(const MemRegion *R);
  83
  84   SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
  85 };
  86 } // end anonymous namespace
  87
  88 StoreManager *ento::CreateFlatStoreManager(GRStateManager &StMgr) {
  89   return new FlatStoreManager(StMgr);
  90 }
  91
  92 SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
  93   // For access to concrete addresses, return UnknownVal.  Checks
  94   // for null dereferences (and similar errors) are done by checkers, not
  95   // the Store.
  96   // FIXME: We can consider lazily symbolicating such memory, but we really
  97   // should defer this when we can reason easily about symbolicating arrays
  98   // of bytes.
  99   if (isa<loc::ConcreteInt>(L)) {
 100     return UnknownVal();
 101   }
 102   if (!isa<loc::MemRegionVal>(L)) {
 103     return UnknownVal();
 104   }
 105
 106   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
 107   RegionInterval RI = RegionToInterval(R);
 108   // FIXME: FlatStore should handle regions with unknown intervals.
 109   if (!RI.R)
 110     return UnknownVal();
 111
 112   RegionBindings B = getRegionBindings(store);
 113   const BindingVal *BV = B.lookup(RI.R);
 114   if (BV) {
 115     const SVal *V = BVFactory.lookup(*BV, RI.I);
 116     if (V)
 117       return *V;
 118     else
 119       return RetrieveRegionWithNoBinding(R, T);
 120   }
 121   return RetrieveRegionWithNoBinding(R, T);
 122 }
 123
 124 SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
 125                                                    QualType T) {
 126   if (R->hasStackNonParametersStorage())
 127     return UndefinedVal();
 128   else
 129     return svalBuilder.getRegionValueSymbolVal(cast<TypedRegion>(R));
 130 }
 131
 132 StoreRef FlatStoreManager::Bind(Store store, Loc L, SVal val) {
 133   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
 134   RegionBindings B = getRegionBindings(store);
 135   const BindingVal *V = B.lookup(R);
 136
 137   BindingVal BV = BVFactory.getEmptyMap();
 138   if (V)
 139     BV = *V;
 140
 141   RegionInterval RI = RegionToInterval(R);
 142   // FIXME: FlatStore should handle regions with unknown intervals.
 143   if (!RI.R)
 144     return StoreRef(B.getRoot(), *this);
 145   BV = BVFactory.add(BV, RI.I, val);
 146   B = RBFactory.add(B, RI.R, BV);
 147   return StoreRef(B.getRoot(), *this);
 148 }
 149
 150 StoreRef FlatStoreManager::Remove(Store store, Loc L) {
 151   return StoreRef(store, *this);
 152 }
 153
 154 StoreRef FlatStoreManager::BindCompoundLiteral(Store store,
 155                                             const CompoundLiteralExpr* cl,
 156                                             const LocationContext *LC,
 157                                             SVal v) {
 158   return StoreRef(store, *this);
 159 }
 160
 161 SVal FlatStoreManager::ArrayToPointer(Loc Array) {
 162   return Array;
 163 }
 164
 165 StoreRef FlatStoreManager::BindDecl(Store store, const VarRegion *VR,
 166                                     SVal initVal) {
 167   return Bind(store, svalBuilder.makeLoc(VR), initVal);
 168 }
 169
 170 StoreRef FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR){
 171   return StoreRef(store, *this);
 172 }
 173
 174 StoreRef FlatStoreManager::invalidateRegions(Store store,
 175                                              const MemRegion * const *I,
 176                                              const MemRegion * const *E,
 177                                              const Expr *Ex, unsigned Count,
 178                                              InvalidatedSymbols &IS,
 179                                              bool invalidateGlobals,
 180                                              InvalidatedRegions *Regions) {
 181   assert(false && "Not implemented");
 182   return StoreRef(store, *this);
 183 }
 184
 185 void FlatStoreManager::print(Store store, llvm::raw_ostream& Out,
 186                              const char* nl, const char *sep) {
 187 }
 188
 189 void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
 190 }
 191
 192 FlatStoreManager::RegionInterval
 193 FlatStoreManager::RegionToInterval(const MemRegion *R) {
 194   switch (R->getKind()) {
 195   case MemRegion::VarRegionKind: {
 196     QualType T = cast<VarRegion>(R)->getValueType();
 197     int64_t Size = Ctx.getTypeSize(T);
 198     return RegionInterval(R, 0, Size-1);
 199   }
 200
 201   case MemRegion::ElementRegionKind:
 202   case MemRegion::FieldRegionKind: {
 203     RegionOffset Offset = R->getAsOffset();
 204     // We cannot compute offset for all regions, for example, elements
 205     // with symbolic offsets.
 206     if (!Offset.getRegion())
 207       return RegionInterval(0, 0, 0);
 208     int64_t Start = Offset.getOffset();
 209     int64_t Size = Ctx.getTypeSize(cast<TypedRegion>(R)->getValueType());
 210     return RegionInterval(Offset.getRegion(), Start, Start+Size);
 211   }
 212
 213   default:
 214     llvm_unreachable("Region kind unhandled.");
 215     return RegionInterval(0, 0, 0);
 216   }
 217 }