Vendor import of clang release_30 branch r142614:

http://llvm.org/svn/llvm-project/cfe/branches/release_30@142614

1 files changed, 114 insertions, 39 deletions

diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index c1ca1cf..b843ab1 100644
--- a/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -15,6 +15,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace clang;
@@ -24,11 +25,10 @@ void SymExpr::dump() const {
   dumpToStream(llvm::errs());
 }
 
-static void print(llvm::raw_ostream& os, BinaryOperator::Opcode Op) {
+static void print(raw_ostream &os, BinaryOperator::Opcode Op) {
   switch (Op) {
     default:
-      assert(false && "operator printing not implemented");
-      break;
+      llvm_unreachable("operator printing not implemented");
     case BO_Mul: os << '*'  ; break;
     case BO_Div: os << '/'  ; break;
     case BO_Rem: os << '%'  ; break;
@@ -48,7 +48,7 @@ static void print(llvm::raw_ostream& os, BinaryOperator::Opcode Op) {
   }
 }
 
-void SymIntExpr::dumpToStream(llvm::raw_ostream& os) const {
+void SymIntExpr::dumpToStream(raw_ostream &os) const {
   os << '(';
   getLHS()->dumpToStream(os);
   os << ") ";
@@ -57,7 +57,7 @@ void SymIntExpr::dumpToStream(llvm::raw_ostream& os) const {
   if (getRHS().isUnsigned()) os << 'U';
 }
 
-void SymSymExpr::dumpToStream(llvm::raw_ostream& os) const {
+void SymSymExpr::dumpToStream(raw_ostream &os) const {
   os << '(';
   getLHS()->dumpToStream(os);
   os << ") ";
@@ -66,33 +66,33 @@ void SymSymExpr::dumpToStream(llvm::raw_ostream& os) const {
   os << ')';
 }
 
-void SymbolConjured::dumpToStream(llvm::raw_ostream& os) const {
+void SymbolConjured::dumpToStream(raw_ostream &os) const {
   os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}';
 }
 
-void SymbolDerived::dumpToStream(llvm::raw_ostream& os) const {
+void SymbolDerived::dumpToStream(raw_ostream &os) const {
   os << "derived_$" << getSymbolID() << '{'
      << getParentSymbol() << ',' << getRegion() << '}';
 }
 
-void SymbolExtent::dumpToStream(llvm::raw_ostream& os) const {
+void SymbolExtent::dumpToStream(raw_ostream &os) const {
   os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
 }
 
-void SymbolMetadata::dumpToStream(llvm::raw_ostream& os) const {
+void SymbolMetadata::dumpToStream(raw_ostream &os) const {
   os << "meta_$" << getSymbolID() << '{'
      << getRegion() << ',' << T.getAsString() << '}';
 }
 
-void SymbolRegionValue::dumpToStream(llvm::raw_ostream& os) const {
+void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
   os << "reg_$" << getSymbolID() << "<" << R << ">";
 }
 
 const SymbolRegionValue*
-SymbolManager::getRegionValueSymbol(const TypedRegion* R) {
+SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
   llvm::FoldingSetNodeID profile;
   SymbolRegionValue::Profile(profile, R);
-  void* InsertPos;
+  void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
@@ -105,12 +105,12 @@ SymbolManager::getRegionValueSymbol(const TypedRegion* R) {
 }
 
 const SymbolConjured*
-SymbolManager::getConjuredSymbol(const Stmt* E, QualType T, unsigned Count,
-                                 const void* SymbolTag) {
+SymbolManager::getConjuredSymbol(const Stmt *E, QualType T, unsigned Count,
+                                 const void *SymbolTag) {
 
   llvm::FoldingSetNodeID profile;
   SymbolConjured::Profile(profile, E, T, Count, SymbolTag);
-  void* InsertPos;
+  void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
@@ -124,11 +124,11 @@ SymbolManager::getConjuredSymbol(const Stmt* E, QualType T, unsigned Count,
 
 const SymbolDerived*
 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
-                                const TypedRegion *R) {
+                                const TypedValueRegion *R) {
 
   llvm::FoldingSetNodeID profile;
   SymbolDerived::Profile(profile, parentSymbol, R);
-  void* InsertPos;
+  void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
@@ -144,7 +144,7 @@ const SymbolExtent*
 SymbolManager::getExtentSymbol(const SubRegion *R) {
   llvm::FoldingSetNodeID profile;
   SymbolExtent::Profile(profile, R);
-  void* InsertPos;
+  void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
@@ -157,12 +157,12 @@ SymbolManager::getExtentSymbol(const SubRegion *R) {
 }
 
 const SymbolMetadata*
-SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt* S, QualType T,
-                                 unsigned Count, const void* SymbolTag) {
+SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
+                                 unsigned Count, const void *SymbolTag) {
 
   llvm::FoldingSetNodeID profile;
   SymbolMetadata::Profile(profile, R, S, T, Count, SymbolTag);
-  void* InsertPos;
+  void *InsertPos;
   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
   if (!SD) {
     SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
@@ -214,11 +214,11 @@ QualType SymbolConjured::getType(ASTContext&) const {
   return T;
 }
 
-QualType SymbolDerived::getType(ASTContext& Ctx) const {
+QualType SymbolDerived::getType(ASTContext &Ctx) const {
   return R->getValueType();
 }
 
-QualType SymbolExtent::getType(ASTContext& Ctx) const {
+QualType SymbolExtent::getType(ASTContext &Ctx) const {
   return Ctx.getSizeType();
 }
 
@@ -226,11 +226,17 @@ QualType SymbolMetadata::getType(ASTContext&) const {
   return T;
 }
 
-QualType SymbolRegionValue::getType(ASTContext& C) const {
+QualType SymbolRegionValue::getType(ASTContext &C) const {
   return R->getValueType();
 }
 
-SymbolManager::~SymbolManager() {}
+SymbolManager::~SymbolManager() {
+  for (SymbolDependTy::const_iterator I = SymbolDependencies.begin(),
+       E = SymbolDependencies.end(); I != E; ++I) {
+    delete I->second;
+  }
+
+}
 
 bool SymbolManager::canSymbolicate(QualType T) {
   T = T.getCanonicalType();
@@ -247,9 +253,53 @@ bool SymbolManager::canSymbolicate(QualType T) {
   return false;
 }
 
+void SymbolManager::addSymbolDependency(const SymbolRef Primary,
+                                        const SymbolRef Dependent) {
+  SymbolDependTy::iterator I = SymbolDependencies.find(Primary);
+  SymbolRefSmallVectorTy *dependencies = 0;
+  if (I == SymbolDependencies.end()) {
+    dependencies = new SymbolRefSmallVectorTy();
+    SymbolDependencies[Primary] = dependencies;
+  } else {
+    dependencies = I->second;
+  }
+  dependencies->push_back(Dependent);
+}
+
+const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
+                                                     const SymbolRef Primary) {
+  SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
+  if (I == SymbolDependencies.end())
+    return 0;
+  return I->second;
+}
+
+void SymbolReaper::markDependentsLive(SymbolRef sym) {
+  // Do not mark dependents more then once.
+  SymbolMapTy::iterator LI = TheLiving.find(sym);
+  assert(LI != TheLiving.end() && "The primary symbol is not live.");
+  if (LI->second == HaveMarkedDependents)
+    return;
+  LI->second = HaveMarkedDependents;
+
+  if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
+    for (SymbolRefSmallVectorTy::const_iterator I = Deps->begin(),
+                                                E = Deps->end(); I != E; ++I) {
+      if (TheLiving.find(*I) != TheLiving.end())
+        continue;
+      markLive(*I);
+    }
+  }
+}
+
 void SymbolReaper::markLive(SymbolRef sym) {
-  TheLiving.insert(sym);
+  TheLiving[sym] = NotProcessed;
   TheDead.erase(sym);
+  markDependentsLive(sym);
+}
+
+void SymbolReaper::markLive(const MemRegion *region) {
+  RegionRoots.insert(region);
 }
 
 void SymbolReaper::markInUse(SymbolRef sym) {
@@ -265,14 +315,17 @@ bool SymbolReaper::maybeDead(SymbolRef sym) {
   return true;
 }
 
-static bool IsLiveRegion(SymbolReaper &Reaper, const MemRegion *MR) {
+bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
+  if (RegionRoots.count(MR))
+    return true;
+  
   MR = MR->getBaseRegion();
 
   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(MR))
-    return Reaper.isLive(SR->getSymbol());
+    return isLive(SR->getSymbol());
 
   if (const VarRegion *VR = dyn_cast<VarRegion>(MR))
-    return Reaper.isLive(VR);
+    return isLive(VR, true);
 
   // FIXME: This is a gross over-approximation. What we really need is a way to
   // tell if anything still refers to this region. Unlike SymbolicRegions,
@@ -291,8 +344,10 @@ static bool IsLiveRegion(SymbolReaper &Reaper, const MemRegion *MR) {
 }
 
 bool SymbolReaper::isLive(SymbolRef sym) {
-  if (TheLiving.count(sym))
+  if (TheLiving.count(sym)) {
+    markDependentsLive(sym);
     return true;
+  }
 
   if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) {
     if (isLive(derived->getParentSymbol())) {
@@ -303,7 +358,7 @@ bool SymbolReaper::isLive(SymbolRef sym) {
   }
 
   if (const SymbolExtent *extent = dyn_cast<SymbolExtent>(sym)) {
-    if (IsLiveRegion(*this, extent->getRegion())) {
+    if (isLiveRegion(extent->getRegion())) {
       markLive(sym);
       return true;
     }
@@ -312,7 +367,7 @@ bool SymbolReaper::isLive(SymbolRef sym) {
 
   if (const SymbolMetadata *metadata = dyn_cast<SymbolMetadata>(sym)) {
     if (MetadataInUse.count(sym)) {
-      if (IsLiveRegion(*this, metadata->getRegion())) {
+      if (isLiveRegion(metadata->getRegion())) {
         markLive(sym);
         MetadataInUse.erase(sym);
         return true;
@@ -326,18 +381,38 @@ bool SymbolReaper::isLive(SymbolRef sym) {
   return isa<SymbolRegionValue>(sym);
 }
 
-bool SymbolReaper::isLive(const Stmt* ExprVal) const {
-  return LCtx->getAnalysisContext()->getRelaxedLiveVariables()->
-      isLive(Loc, ExprVal);
+bool SymbolReaper::isLive(const Stmt *ExprVal) const {
+  return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
 }
 
-bool SymbolReaper::isLive(const VarRegion *VR) const {
+bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
   const StackFrameContext *VarContext = VR->getStackFrame();
   const StackFrameContext *CurrentContext = LCtx->getCurrentStackFrame();
 
-  if (VarContext == CurrentContext)
-    return LCtx->getAnalysisContext()->getRelaxedLiveVariables()->
-        isLive(Loc, VR->getDecl());
+  if (VarContext == CurrentContext) {
+    if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
+      return true;
+
+    if (!includeStoreBindings)
+      return false;
+    
+    unsigned &cachedQuery =
+      const_cast<SymbolReaper*>(this)->includedRegionCache[VR];
+
+    if (cachedQuery) {
+      return cachedQuery == 1;
+    }
+
+    // Query the store to see if the region occurs in any live bindings.
+    if (Store store = reapedStore.getStore()) {
+      bool hasRegion = 
+        reapedStore.getStoreManager().includedInBindings(store, VR);
+      cachedQuery = hasRegion ? 1 : 2;
+      return hasRegion;
+    }
+    
+    return false;
+  }
 
   return VarContext->isParentOf(CurrentContext);
 }