[analyzer] Overhaul how the static analyzer expects CFGs by forcing CFGs to be linearized only when used by the static analyzer. This required a rewrite of LiveVariables, and exposed a ton of subtle bugs.

The motivation of this large change is to drastically simplify the logic in ExprEngine going forward.

Some fallout is that the output of some BugReporterVisitors is not as accurate as before; those will
need to be fixed over time.  There is also some possible performance regression as RemoveDeadBindings
will be called frequently; this can also be improved over time.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@136419 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 45 insertions, 8 deletions

diff --git a/lib/StaticAnalyzer/Core/GRState.cpp b/lib/StaticAnalyzer/Core/GRState.cpp
index cbc4909490..370f98ac56 100644
--- a/lib/StaticAnalyzer/Core/GRState.cpp
+++ b/lib/StaticAnalyzer/Core/GRState.cpp
@@ -78,8 +78,11 @@ GRStateManager::removeDeadBindings(const GRState* state,
                                            state, RegionRoots);
 
   // Clean up the store.
-  NewState.setStore(StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
-                                                 SymReaper, RegionRoots));
+  StoreRef newStore = StoreMgr->removeDeadBindings(NewState.getStore(), LCtx,
+                                                   SymReaper, RegionRoots);
+  NewState.setStore(newStore);
+  SymReaper.setReapedStore(newStore);
+  
   state = getPersistentState(NewState);
   return ConstraintMgr->removeDeadBindings(state, SymReaper);
 }
@@ -519,9 +522,9 @@ const GRState *GRStateManager::removeGDM(const GRState *state, void *Key) {
 
 namespace {
 class ScanReachableSymbols : public SubRegionMap::Visitor  {
-  typedef llvm::DenseSet<const MemRegion*> VisitedRegionsTy;
+  typedef llvm::DenseMap<const void*, unsigned> VisitedItems;
 
-  VisitedRegionsTy visited;
+  VisitedItems visited;
   const GRState *state;
   SymbolVisitor &visitor;
   llvm::OwningPtr<SubRegionMap> SRM;
@@ -533,6 +536,7 @@ public:
   bool scan(nonloc::CompoundVal val);
   bool scan(SVal val);
   bool scan(const MemRegion *R);
+  bool scan(const SymExpr *sym);
 
   // From SubRegionMap::Visitor.
   bool Visit(const MemRegion* Parent, const MemRegion* SubRegion) {
@@ -549,6 +553,33 @@ bool ScanReachableSymbols::scan(nonloc::CompoundVal val) {
   return true;
 }
 
+bool ScanReachableSymbols::scan(const SymExpr *sym) {
+  unsigned &isVisited = visited[sym];
+  if (isVisited)
+    return true;
+  isVisited = 1;
+  
+  if (const SymbolData *sData = dyn_cast<SymbolData>(sym))
+    if (!visitor.VisitSymbol(sData))
+      return false;
+  
+  switch (sym->getKind()) {
+    case SymExpr::RegionValueKind:
+    case SymExpr::ConjuredKind:
+    case SymExpr::DerivedKind:
+    case SymExpr::ExtentKind:
+    case SymExpr::MetadataKind:
+      break;
+    case SymExpr::SymIntKind:
+      return scan(cast<SymIntExpr>(sym)->getLHS());
+    case SymExpr::SymSymKind: {
+      const SymSymExpr *x = cast<SymSymExpr>(sym);
+      return scan(x->getLHS()) && scan(x->getRHS());
+    }
+  }
+  return true;
+}
+
 bool ScanReachableSymbols::scan(SVal val) {
   if (loc::MemRegionVal *X = dyn_cast<loc::MemRegionVal>(&val))
     return scan(X->getRegion());
@@ -557,7 +588,10 @@ bool ScanReachableSymbols::scan(SVal val) {
     return scan(X->getLoc());
 
   if (SymbolRef Sym = val.getAsSymbol())
-    return visitor.VisitSymbol(Sym);
+    return scan(Sym);
+
+  if (const SymExpr *Sym = val.getAsSymbolicExpression())
+    return scan(Sym);
 
   if (nonloc::CompoundVal *X = dyn_cast<nonloc::CompoundVal>(&val))
     return scan(*X);
@@ -566,10 +600,13 @@ bool ScanReachableSymbols::scan(SVal val) {
 }
 
 bool ScanReachableSymbols::scan(const MemRegion *R) {
-  if (isa<MemSpaceRegion>(R) || visited.count(R))
+  if (isa<MemSpaceRegion>(R))
     return true;
-
-  visited.insert(R);
+  
+  unsigned &isVisited = visited[R];
+  if (isVisited)
+    return true;
+  isVisited = 1;
 
   // If this is a symbolic region, visit the symbol for the region.
   if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))