[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

8 files changed, 132 insertions, 77 deletions

diff --git a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
index 2c5a1a255d..f86bf55c32 100644
--- a/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/DeadStoresChecker.cpp
@@ -68,12 +68,12 @@ void ReachableCode::computeReachableBlocks() {
 }
 
 namespace {
-class DeadStoreObs : public LiveVariables::ObserverTy {
+class DeadStoreObs : public LiveVariables::Observer {
   const CFG &cfg;
   ASTContext &Ctx;
   BugReporter& BR;
   ParentMap& Parents;
-  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
+  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
   llvm::OwningPtr<ReachableCode> reachableCode;
   const CFGBlock *currentBlock;
 
@@ -82,13 +82,14 @@ class DeadStoreObs : public LiveVariables::ObserverTy {
 public:
   DeadStoreObs(const CFG &cfg, ASTContext &ctx,
                BugReporter& br, ParentMap& parents,
-               llvm::SmallPtrSet<VarDecl*, 20> &escaped)
+               llvm::SmallPtrSet<const VarDecl*, 20> &escaped)
     : cfg(cfg), Ctx(ctx), BR(br), Parents(parents),
       Escaped(escaped), currentBlock(0) {}
 
   virtual ~DeadStoreObs() {}
 
-  void Report(VarDecl* V, DeadStoreKind dsk, SourceLocation L, SourceRange R) {
+  void Report(const VarDecl* V, DeadStoreKind dsk,
+              SourceLocation L, SourceRange R) {
     if (Escaped.count(V))
       return;
     
@@ -134,10 +135,9 @@ public:
     BR.EmitBasicReport(BugType, "Dead store", msg, L, R);
   }
 
-  void CheckVarDecl(VarDecl* VD, Expr* Ex, Expr* Val,
+  void CheckVarDecl(const VarDecl* VD, const Expr* Ex, const Expr* Val,
                     DeadStoreKind dsk,
-                    const LiveVariables::AnalysisDataTy& AD,
-                    const LiveVariables::ValTy& Live) {
+                    const LiveVariables::LivenessValues &Live) {
 
     if (!VD->hasLocalStorage())
       return;
@@ -146,30 +146,29 @@ public:
     if (VD->getType()->getAs<ReferenceType>())
       return;
 
-    if (!Live(VD, AD) && 
+    if (!Live.isLive(VD) && 
         !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>()))
       Report(VD, dsk, Ex->getSourceRange().getBegin(),
              Val->getSourceRange());
   }
 
-  void CheckDeclRef(DeclRefExpr* DR, Expr* Val, DeadStoreKind dsk,
-                    const LiveVariables::AnalysisDataTy& AD,
-                    const LiveVariables::ValTy& Live) {
-    if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
-      CheckVarDecl(VD, DR, Val, dsk, AD, Live);
+  void CheckDeclRef(const DeclRefExpr* DR, const Expr* Val, DeadStoreKind dsk,
+                    const LiveVariables::LivenessValues& Live) {
+    if (const VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl()))
+      CheckVarDecl(VD, DR, Val, dsk, Live);
   }
 
-  bool isIncrement(VarDecl* VD, BinaryOperator* B) {
+  bool isIncrement(VarDecl* VD, const BinaryOperator* B) {
     if (B->isCompoundAssignmentOp())
       return true;
 
-    Expr* RHS = B->getRHS()->IgnoreParenCasts();
-    BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
+    const Expr* RHS = B->getRHS()->IgnoreParenCasts();
+    const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS);
 
     if (!BRHS)
       return false;
 
-    DeclRefExpr *DR;
+    const DeclRefExpr *DR;
 
     if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts())))
       if (DR->getDecl() == VD)
@@ -182,9 +181,8 @@ public:
     return false;
   }
 
-  virtual void ObserveStmt(Stmt* S, const CFGBlock *block,
-                           const LiveVariables::AnalysisDataTy& AD,
-                           const LiveVariables::ValTy& Live) {
+  virtual void observeStmt(const Stmt* S, const CFGBlock *block,
+                           const LiveVariables::LivenessValues &Live) {
 
     currentBlock = block;
     
@@ -194,7 +192,7 @@ public:
 
     // Only cover dead stores from regular assignments.  ++/-- dead stores
     // have never flagged a real bug.
-    if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
+    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
       if (!B->isAssignmentOp()) return; // Skip non-assignments.
 
       if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()))
@@ -220,26 +218,26 @@ public:
                               ? Enclosing
                               : (isIncrement(VD,B) ? DeadIncrement : Standard);
 
-          CheckVarDecl(VD, DR, B->getRHS(), dsk, AD, Live);
+          CheckVarDecl(VD, DR, B->getRHS(), dsk, Live);
         }
     }
-    else if (UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
+    else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) {
       if (!U->isIncrementOp() || U->isPrefix())
         return;
 
-      Stmt *parent = Parents.getParentIgnoreParenCasts(U);
+      const Stmt *parent = Parents.getParentIgnoreParenCasts(U);
       if (!parent || !isa<ReturnStmt>(parent))
         return;
 
-      Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
+      const Expr *Ex = U->getSubExpr()->IgnoreParenCasts();
 
-      if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
-        CheckDeclRef(DR, U, DeadIncrement, AD, Live);
+      if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(Ex))
+        CheckDeclRef(DR, U, DeadIncrement, Live);
     }
-    else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
+    else if (const DeclStmt* DS = dyn_cast<DeclStmt>(S))
       // Iterate through the decls.  Warn if any initializers are complex
       // expressions that are not live (never used).
-      for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
+      for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end();
            DI != DE; ++DI) {
 
         VarDecl* V = dyn_cast<VarDecl>(*DI);
@@ -265,7 +263,7 @@ public:
             // A dead initialization is a variable that is dead after it
             // is initialized.  We don't flag warnings for those variables
             // marked 'unused'.
-            if (!Live(V, AD) && V->getAttr<UnusedAttr>() == 0) {
+            if (!Live.isLive(V) && V->getAttr<UnusedAttr>() == 0) {
               // Special case: check for initializations with constants.
               //
               //  e.g. : int x = 0;
@@ -318,7 +316,7 @@ public:
 
   CFG& getCFG() { return *cfg; }
 
-  llvm::SmallPtrSet<VarDecl*, 20> Escaped;
+  llvm::SmallPtrSet<const VarDecl*, 20> Escaped;
 
   void VisitUnaryOperator(UnaryOperator* U) {
     // Check for '&'.  Any VarDecl whose value has its address-taken we
@@ -351,7 +349,7 @@ public:
       FindEscaped FS(&cfg);
       FS.getCFG().VisitBlockStmts(FS);
       DeadStoreObs A(cfg, BR.getContext(), BR, pmap, FS.Escaped);
-      L->runOnAllBlocks(cfg, &A);
+      L->runOnAllBlocks(A);
     }
   }
 };
diff --git a/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp b/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
index b540bce981..69081a93a6 100644
--- a/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
+++ b/lib/StaticAnalyzer/Checkers/UnreachableCodeChecker.cpp
@@ -111,13 +111,19 @@ void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G,
     // FIXME: This should be extended to include other unreachable markers,
     // such as llvm_unreachable.
     if (!CB->empty()) {
-      CFGElement First = CB->front();
-      if (const CFGStmt *S = First.getAs<CFGStmt>()) {
-        if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
-          if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable)
-            continue;
-        }
+      bool foundUnreachable = false;
+      for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end();
+           ci != ce; ++ci) {
+        if (const CFGStmt *S = (*ci).getAs<CFGStmt>())
+          if (const CallExpr *CE = dyn_cast<CallExpr>(S->getStmt())) {
+            if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable) {
+              foundUnreachable = true;
+              break;
+            }
+          }
       }
+      if (foundUnreachable)
+        continue;
     }
 
     // We found a block that wasn't covered - find the statement to report
diff --git a/lib/StaticAnalyzer/Core/AnalysisManager.cpp b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
index 274d7a6d5d..543388e4fb 100644
--- a/lib/StaticAnalyzer/Core/AnalysisManager.cpp
+++ b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
@@ -35,6 +35,7 @@ AnalysisManager::AnalysisManager(ASTContext &ctx, Diagnostic &diags,
     EagerlyAssume(eager), TrimGraph(trim), InlineCall(inlinecall),
     EagerlyTrimEGraph(eagerlyTrimEGraph)
 {
+  AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd();
 }
 
 AnalysisContext *
diff --git a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
index 8e31adead1..75e232f5bd 100644
--- a/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
+++ b/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp
@@ -39,8 +39,6 @@ const Stmt *bugreporter::GetDerefExpr(const ExplodedNode *N) {
     return ME->getBase()->IgnoreParenCasts();
   }
   else if (const ArraySubscriptExpr *AE = dyn_cast<ArraySubscriptExpr>(S)) {
-    // Retrieve the base for arrays since BasicStoreManager doesn't know how
-    // to reason about them.
     return AE->getBase();
   }
 
@@ -314,6 +312,21 @@ void bugreporter::registerTrackNullOrUndefValue(BugReporterContext& BRC,
     return;
 
   GRStateManager &StateMgr = BRC.getStateManager();
+  
+  // Walk through nodes until we get one that matches the statement
+  // exactly.
+  while (N) {
+    const ProgramPoint &pp = N->getLocation();
+    if (const PostStmt *ps = dyn_cast<PostStmt>(&pp)) {
+      if (ps->getStmt() == S)
+        break;
+    }
+    N = *N->pred_begin();
+  }
+
+  if (!N)
+    return;
+  
   const GRState *state = N->getState();
 
   // Walk through lvalue-to-rvalue conversions.  
diff --git a/lib/StaticAnalyzer/Core/Environment.cpp b/lib/StaticAnalyzer/Core/Environment.cpp
index 4a2d33d8d3..92c4a4c581 100644
--- a/lib/StaticAnalyzer/Core/Environment.cpp
+++ b/lib/StaticAnalyzer/Core/Environment.cpp
@@ -158,8 +158,6 @@ EnvironmentManager::removeDeadBindings(Environment Env,
                                        const GRState *ST,
                               SmallVectorImpl<const MemRegion*> &DRoots) {
 
-  CFG &C = *SymReaper.getLocationContext()->getCFG();
-
   // We construct a new Environment object entirely, as this is cheaper than
   // individually removing all the subexpression bindings (which will greatly
   // outnumber block-level expression bindings).
@@ -172,7 +170,6 @@ EnvironmentManager::removeDeadBindings(Environment Env,
        I != E; ++I) {
 
     const Stmt *BlkExpr = I.getKey();
-    
     // For recorded locations (used when evaluating loads and stores), we
     // consider them live only when their associated normal expression is
     // also live.
@@ -182,28 +179,8 @@ EnvironmentManager::removeDeadBindings(Environment Env,
       deferredLocations.push_back(std::make_pair(BlkExpr, I.getData()));
       continue;
     }
-    
     const SVal &X = I.getData();
 
-    // Block-level expressions in callers are assumed always live.
-    if (isBlockExprInCallers(BlkExpr, SymReaper.getLocationContext())) {
-      NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
-
-      if (isa<loc::MemRegionVal>(X)) {
-        const MemRegion* R = cast<loc::MemRegionVal>(X).getRegion();
-        DRoots.push_back(R);
-      }
-
-      // Mark all symbols in the block expr's value live.
-      MarkLiveCallback cb(SymReaper);
-      ST->scanReachableSymbols(X, cb);
-      continue;
-    }
-
-    // Not a block-level expression?
-    if (!C.isBlkExpr(BlkExpr))
-      continue;
-
     if (SymReaper.isLive(BlkExpr)) {
       // Copy the binding to the new map.
       NewEnv.ExprBindings = F.add(NewEnv.ExprBindings, BlkExpr, X);
diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 003c0f305d..2c7ad63bd1 100644
--- a/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -244,7 +244,7 @@ void ExprEngine::ProcessStmt(const CFGStmt S, StmtNodeBuilder& builder) {
 
   // Create the cleaned state.
   const LocationContext *LC = EntryNode->getLocationContext();
-  SymbolReaper SymReaper(LC, currentStmt, SymMgr);
+  SymbolReaper SymReaper(LC, currentStmt, SymMgr, getStoreManager());
 
   if (AMgr.shouldPurgeDead()) {
     const GRState *St = EntryNode->getState();
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))
diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index b55c96934e..7ae338e8d8 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;
@@ -272,7 +273,7 @@ static bool IsLiveRegion(SymbolReaper &Reaper, const MemRegion *MR) {
     return Reaper.isLive(SR->getSymbol());
 
   if (const VarRegion *VR = dyn_cast<VarRegion>(MR))
-    return Reaper.isLive(VR);
+    return Reaper.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,
@@ -331,13 +332,35 @@ bool SymbolReaper::isLive(const Stmt* ExprVal) const {
       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->getAnalysisContext()->getRelaxedLiveVariables()->
+          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);
 }