path: root/lib/Analysis/RegionStore.cpp

//== RegionStore.cpp - Field-sensitive store model --------------*- 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 a basic region store model. In this model, we do have field
// sensitivity. But we assume nothing about the heap shape. So recursive data
// structures are largely ignored. Basically we do 1-limiting analysis.
// Parameter pointers are assumed with no aliasing. Pointee objects of
// parameters are created lazily.
//
//===----------------------------------------------------------------------===//
#include "clang/Analysis/PathSensitive/MemRegion.h"
#include "clang/Analysis/PathSensitive/GRState.h"
#include "clang/Analysis/PathSensitive/GRStateTrait.h"
#include "clang/Analysis/Analyses/LiveVariables.h"

#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/ImmutableList.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Compiler.h"

using namespace clang;

// Actual Store type.
typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;

// RegionView GDM stuff.
typedef llvm::ImmutableList<const MemRegion*> RegionViewTy;
typedef llvm::ImmutableMap<const MemRegion*, RegionViewTy> RegionViewMapTy;
static int RegionViewMapTyIndex = 0;
namespace clang {
template<> struct GRStateTrait<RegionViewMapTy> 
  : public GRStatePartialTrait<RegionViewMapTy> {
  static void* GDMIndex() { return &RegionViewMapTyIndex; }
};
}

// RegionExtents GDM stuff.
// Currently RegionExtents are in bytes. We can change this representation when
// there are real requirements.
typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionExtentsTy;
static int RegionExtentsTyIndex = 0;
namespace clang {
template<> struct GRStateTrait<RegionExtentsTy>
  : public GRStatePartialTrait<RegionExtentsTy> {
  static void* GDMIndex() { return &RegionExtentsTyIndex; }
};
}

// KillSet GDM stuff.
typedef llvm::ImmutableSet<const MemRegion*> RegionKills;
static int RegionKillsIndex = 0;
namespace clang {
  template<> struct GRStateTrait<RegionKills>
  : public GRStatePartialTrait<RegionKills> {
    static void* GDMIndex() { return &RegionKillsIndex; }
  };
}


namespace {

class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
  RegionBindingsTy::Factory RBFactory;
  RegionViewTy::Factory RVFactory;

  GRStateManager& StateMgr;
  MemRegionManager MRMgr;

public:
  RegionStoreManager(GRStateManager& mgr) 
    : RBFactory(mgr.getAllocator()),
      RVFactory(mgr.getAllocator()),
      StateMgr(mgr), 
      MRMgr(StateMgr.getAllocator()) {}

  virtual ~RegionStoreManager() {}

  MemRegionManager& getRegionManager() { return MRMgr; }
  
  Store BindCompoundLiteral(Store store, const CompoundLiteralExpr* CL, SVal V);

  SVal getLValueString(const GRState* St, const StringLiteral* S);

  SVal getLValueCompoundLiteral(const GRState* St, const CompoundLiteralExpr*);

  SVal getLValueVar(const GRState* St, const VarDecl* VD);
  
  SVal getLValueIvar(const GRState* St, const ObjCIvarDecl* D, SVal Base);

  SVal getLValueField(const GRState* St, SVal Base, const FieldDecl* D);

  SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);

  SVal getSizeInElements(const GRState* St, const MemRegion* R);

  SVal ArrayToPointer(SVal Array);

  std::pair<const GRState*, SVal>
  CastRegion(const GRState* St, SVal VoidPtr, QualType CastToTy, Stmt* CastE);

  SVal Retrieve(const GRState* state, Loc L, QualType T = QualType());

  Store Bind(Store St, Loc LV, SVal V);

  Store Remove(Store store, Loc LV) {
    // FIXME: Implement.
    return store;
  }

  Store getInitialStore();
  
  /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
  ///  'this' object (C++).  When used when analyzing a normal function this
  ///  method returns NULL.
  const MemRegion* getSelfRegion(Store) {
    assert (false && "Not implemented.");
    return 0;
  }
  
  /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
  ///  It returns a new Store with these values removed, and populates LSymbols
  //   and DSymbols with the known set of live and dead symbols respectively.
  Store RemoveDeadBindings(const GRState* state, Stmt* Loc,
                           const LiveVariables& Live,
                           llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
                           LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);

  void UpdateLiveSymbols(SVal X, LiveSymbolsTy& LSymbols);

  Store