[analyzer] Add an option to re-analyze a dead-end path without inlining.

The analyzer gives up path exploration under certain conditions. For
example, when the same basic block has been visited more than 4 times.
With inlining turned on, this could lead to decrease in code coverage.
Specifically, if we give up inside the inlined function, the rest of
parent's basic blocks will not get analyzed.

This commit introduces an option to enable re-run along the failed path,
in which we do not inline the last inlined call site. This is done by
enqueueing the node before the processing of the inlined call site
with a special policy encoded in the state. The policy tells us not to
inline the call site along the path.

This lead to ~10% increase in the number of paths analyzed. Even though
we expected a much greater coverage improvement. 

The option is turned off by default for now.

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

1 files changed, 50 insertions, 34 deletions

diff --git a/lib/StaticAnalyzer/Core/CoreEngine.cpp b/lib/StaticAnalyzer/Core/CoreEngine.cpp
index fac368c8f2..f303c7af3a 100644
--- a/lib/StaticAnalyzer/Core/CoreEngine.cpp
+++ b/lib/StaticAnalyzer/Core/CoreEngine.cpp
@@ -211,45 +211,56 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps,
     // Retrieve the node.
     ExplodedNode *Node = WU.getNode();
 
-    // Dispatch on the location type.
-    switch (Node->getLocation().getKind()) {
-      case ProgramPoint::BlockEdgeKind:
-        HandleBlockEdge(cast<BlockEdge>(Node->getLocation()), Node);
-        break;
-
-      case ProgramPoint::BlockEntranceKind:
-        HandleBlockEntrance(cast<BlockEntrance>(Node->getLocation()), Node);
-        break;
-
-      case ProgramPoint::BlockExitKind:
-        assert (false && "BlockExit location never occur in forward analysis.");
-        break;
+    dispatchWorkItem(Node, Node->getLocation(), WU);
+  }
+  SubEng.processEndWorklist(hasWorkRemaining());
+  return WList->hasWork();
+}
 
-      case ProgramPoint::CallEnterKind: {
-        CallEnter CEnter = cast<CallEnter>(Node->getLocation());
-        if (AnalyzedCallees)
-          if (const CallExpr* CE =
-              dyn_cast_or_null<CallExpr>(CEnter.getCallExpr()))
-            if (const Decl *CD = CE->getCalleeDecl())
-              AnalyzedCallees->insert(CD);
-        SubEng.processCallEnter(CEnter, Node);
-        break;
-      }
+void CoreEngine::dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
+                                  const WorkListUnit& WU) {
+  // Dispatch on the location type.
+  switch (Loc.getKind()) {
+    case ProgramPoint::BlockEdgeKind:
+      HandleBlockEdge(cast<BlockEdge>(Loc), Pred);
+      break;
+
+    case ProgramPoint::BlockEntranceKind:
+      HandleBlockEntrance(cast<BlockEntrance>(Loc), Pred);
+      break;
+
+    case ProgramPoint::BlockExitKind:
+      assert (false && "BlockExit location never occur in forward analysis.");
+      break;
+
+    case ProgramPoint::CallEnterKind: {
+      CallEnter CEnter = cast<CallEnter>(Loc);
+      if (AnalyzedCallees)
+        if (const CallExpr* CE =
+            dyn_cast_or_null<CallExpr>(CEnter.getCallExpr()))
+          if (const Decl *CD = CE->getCalleeDecl())
+            AnalyzedCallees->insert(CD);
+      SubEng.processCallEnter(CEnter, Pred);
+      break;
+    }
 
-      case ProgramPoint::CallExitKind:
-        SubEng.processCallExit(Node);
-        break;
+    case ProgramPoint::CallExitKind:
+      SubEng.processCallExit(Pred);
+      break;
 
-      default:
-        assert(isa<PostStmt>(Node->getLocation()) || 
-               isa<PostInitializer>(Node->getLocation()));
-        HandlePostStmt(WU.getBlock(), WU.getIndex(), Node);
-        break;
+    case ProgramPoint::EpsilonKind: {
+      assert(Pred->hasSinglePred() &&
+             "Assume epsilon has exactly one predecessor by construction");
+      ExplodedNode *PNode = Pred->getFirstPred();
+      dispatchWorkItem(Pred, PNode->getLocation(), WU);
+      break;
     }
+    default:
+      assert(isa<PostStmt>(Loc) ||
+             isa<PostInitializer>(Loc));
+      HandlePostStmt(WU.getBlock(), WU.getIndex(), Pred);
+      break;
   }
-
-  SubEng.processEndWorklist(hasWorkRemaining());
-  return WList->hasWork();
 }
 
 void CoreEngine::ExecuteWorkListWithInitialState(const LocationContext *L, 
@@ -491,6 +502,11 @@ void CoreEngine::enqueueStmtNode(ExplodedNode *N,
     return;
   }
 
+  if (isa<EpsilonPoint>(N->getLocation())) {
+    WList->enqueue(N, Block, Idx);
+    return;
+  }
+
   const CFGStmt *CS = (*Block)[Idx].getAs<CFGStmt>();
   const Stmt *St = CS ? CS->getStmt() : 0;
   PostStmt Loc(St, N->getLocationContext());