[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

5 files changed, 182 insertions, 71 deletions

diff --git a/lib/StaticAnalyzer/Core/AnalysisManager.cpp b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
index 139bc88de9..057a5d490a 100644
--- a/lib/StaticAnalyzer/Core/AnalysisManager.cpp
+++ b/lib/StaticAnalyzer/Core/AnalysisManager.cpp
@@ -33,7 +33,8 @@ AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags,
                                  AnalysisIPAMode ipa,
                                  unsigned inlineMaxStack,
                                  unsigned inlineMaxFunctionSize,
-                                 AnalysisInliningMode IMode)
+                                 AnalysisInliningMode IMode,
+                                 bool retry)
   : AnaCtxMgr(useUnoptimizedCFG, addImplicitDtors, addInitializers),
     Ctx(ctx), Diags(diags), LangOpts(lang), PD(pd),
     CreateStoreMgr(storemgr), CreateConstraintMgr(constraintmgr),
@@ -45,7 +46,8 @@ AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags,
     IPAMode(ipa),
     InlineMaxStackDepth(inlineMaxStack),
     InlineMaxFunctionSize(inlineMaxFunctionSize),
-    InliningMode(IMode)
+    InliningMode(IMode),
+    RetryExhausted(retry)
 {
   AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd();
 }
@@ -73,7 +75,8 @@ AnalysisManager::AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags,
     IPAMode(ParentAM.IPAMode),
     InlineMaxStackDepth(ParentAM.InlineMaxStackDepth),
     InlineMaxFunctionSize(ParentAM.InlineMaxFunctionSize),
-    InliningMode(ParentAM.InliningMode)
+    InliningMode(ParentAM.InliningMode),
+    RetryExhausted(ParentAM.RetryExhausted)
 {
   AnaCtxMgr.getCFGBuildOptions().setAllAlwaysAdd();
 }
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());
diff --git a/lib/StaticAnalyzer/Core/ExprEngine.cpp b/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 1bbcf1e689..c47b7f4eb5 100644
--- a/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -50,6 +50,13 @@ STATISTIC(NumMaxBlockCountReached,
 STATISTIC(NumMaxBlockCountReachedInInlined,
             "The # of aborted paths due to reaching the maximum block count in "
             "an inlined function");
+STATISTIC(NumTimesRetriedWithoutInlining,
+            "The # of times we re-evaluated a call without inlining");
+
+STATISTIC(NumNotNew,
+            "Cached out");
+STATISTIC(NumNull,
+            "Null node");
 
 //===----------------------------------------------------------------------===//
 // Utility functions.
@@ -972,6 +979,64 @@ void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
   }
 }
 
+bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
+                                       const LocationContext *CalleeLC) {
+  const StackFrameContext *CalleeSF = CalleeLC->getCurrentStackFrame();
+  const StackFrameContext *CallerSF = CalleeSF->getParent()->getCurrentStackFrame();
+  assert(CalleeSF && CallerSF);
+  ExplodedNode *BeforeProcessingCall = 0;
+
+  // Find the first node before we started processing the call expression.
+  while (N) {
+    ProgramPoint L = N->getLocation();
+    BeforeProcessingCall = N;
+    N = N->pred_empty() ? NULL : *(N->pred_begin());
+
+    // Skip the nodes corresponding to the inlined code.
+    if (L.getLocationContext()->getCurrentStackFrame() != CallerSF)
+      continue;
+    // We reached the caller. Find the node right before we started
+    // processing the CallExpr.
+    if (isa<PostPurgeDeadSymbols>(L))
+      continue;
+    if (const StmtPoint *SP = dyn_cast<StmtPoint>(&L))
+      if (SP->getStmt() == CalleeSF->getCallSite())
+        continue;
+    break;
+  }
+
+  if (!BeforeProcessingCall) {
+    NumNull++;
+    return false;
+  }
+
+  // TODO: Clean up the unneeded nodes.
+
+  // Build an Epsilon node from which we will restart the analyzes.
+  const Stmt *CE = CalleeSF->getCallSite();
+  ProgramPoint NewNodeLoc =
+               EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
+  // Add the special flag to GDM to signal retrying with no inlining.
+  // Note, changing the state ensures that we are not going to cache out.
+  ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
+  NewNodeState = NewNodeState->set<ReplayWithoutInlining>((void*)CE);
+
+  // Make the new node a successor of BeforeProcessingCall.
+  bool IsNew = false;
+  ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
+  if (!IsNew) {
+    NumNotNew++;
+    return false;
+  }
+  NewNode->addPredecessor(BeforeProcessingCall, G);
+
+  // Add the new node to the work list.
+  Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
+                                  CalleeSF->getIndex());
+  NumTimesRetriedWithoutInlining++;
+  return true;
+}
+
 /// Block entrance.  (Update counters).
 void ExprEngine::processCFGBlockEntrance(NodeBuilderWithSinks &nodeBuilder) {
   
@@ -984,10 +1049,17 @@ void ExprEngine::processCFGBlockEntrance(NodeBuilderWithSinks &nodeBuilder) {
 
     // Check if we stopped at the top level function or not.
     // Root node should have the location context of the top most function.
-    if ((*G.roots_begin())->getLocation().getLocationContext() !=
-        pred->getLocation().getLocationContext())
-      NumMaxBlockCountReachedInInlined++;
-    else
+    const LocationContext *CalleeLC = pred->getLocation().getLocationContext();
+    const LocationContext *RootLC =
+                        (*G.roots_begin())->getLocation().getLocationContext();
+    if (RootLC->getCurrentStackFrame() != CalleeLC->getCurrentStackFrame()) {
+      // Re-run the call evaluation without inlining it, by storing the
+      // no-inlining policy in the state and enqueuing the new work item on
+      // the list. Replay should almost never fail. Use the stats to catch it
+      // if it does.
+      if (!(AMgr.RetryExhausted && replayWithoutInlining(pred, CalleeLC)))
+        NumMaxBlockCountReachedInInlined++;
+    } else
       NumMaxBlockCountReached++;
   }
 }
@@ -1788,6 +1860,10 @@ struct DOTGraphTraits<ExplodedNode*> :
         Out << "CallExit";
         break;
 
+      case ProgramPoint::EpsilonKind:
+        Out << "Epsilon Point";
+        break;
+
       default: {
         if (StmtPoint *L = dyn_cast<StmtPoint>(&Loc)) {
           const Stmt *S = L->getStmt();
diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index 66842050af..1746b5c529 100644
--- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -129,8 +129,7 @@ static unsigned getNumberStackFrames(const LocationContext *LCtx) {
 }
 
 // Determine if we should inline the call.
-static bool shouldInline(const FunctionDecl *FD, ExplodedNode *Pred,
-                         AnalysisManager &AMgr) {
+bool ExprEngine::shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred) {
   AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD);
   const CFG *CalleeCFG = CalleeADC->getCFG();
 
@@ -144,9 +143,35 @@ static bool shouldInline(const FunctionDecl *FD, ExplodedNode *Pred,
   return true;
 }
 
+// For now, skip inlining variadic functions.
+// We also don't inline blocks.
+static bool shouldInlineCallExpr(const CallExpr *CE, ExprEngine *E) {
+  if (!E->getAnalysisManager().shouldInlineCall())
+    return false;
+  QualType callee = CE->getCallee()->getType();
+  const FunctionProtoType *FT = 0;
+  if (const PointerType *PT = callee->getAs<PointerType>())
+    FT = dyn_cast<FunctionProtoType>(PT->getPointeeType());
+  else if (const BlockPointerType *BT = callee->getAs<BlockPointerType>()) {
+    // FIXME: inline blocks.
+    // FT = dyn_cast<FunctionProtoType>(BT->getPointeeType());
+    (void) BT;
+    return false;
+  }
+  // If we have no prototype, assume the function is okay.
+  if (!FT)
+    return true;
+
+  // Skip inlining of variadic functions.
+  return !FT->isVariadic();
+}
+
 bool ExprEngine::InlineCall(ExplodedNodeSet &Dst,
                             const CallExpr *CE, 
                             ExplodedNode *Pred) {
+  if (!shouldInlineCallExpr(CE, this))
+    return false;
+
   ProgramStateRef state = Pred->getState();
   const Expr *Callee = CE->getCallee();
   const FunctionDecl *FD =
@@ -159,7 +184,7 @@ bool ExprEngine::InlineCall(ExplodedNodeSet &Dst,
       // FIXME: Handle C++.
       break;
     case Stmt::CallExprClass: {
-      if (!shouldInline(FD, Pred, AMgr))
+      if (!shouldInlineDecl(FD, Pred))
         return false;
 
       // Construct a new stack frame for the callee.
@@ -346,28 +371,16 @@ ExprEngine::invalidateArguments(ProgramStateRef State,
 
 }
 
-// For now, skip inlining variadic functions.
-// We also don't inline blocks.
-static bool shouldInlineCall(const CallExpr *CE, ExprEngine &Eng) {
-  if (!Eng.getAnalysisManager().shouldInlineCall())
-    return false;
-  QualType callee = CE->getCallee()->getType();
-  const FunctionProtoType *FT = 0;
-  if (const PointerType *PT = callee->getAs<PointerType>())
-    FT = dyn_cast<FunctionProtoType>(PT->getPointeeType());
-  else if (const BlockPointerType *BT = callee->getAs<BlockPointerType>()) {
-    // FIXME: inline blocks.
-    // FT = dyn_cast<FunctionProtoType>(BT->getPointeeType());
-    (void) BT;
-    return false;
+static ProgramStateRef getReplayWithoutInliningState(ExplodedNode *&N,
+                                                     const CallExpr *CE) {
+  void *ReplayState = N->getState()->get<ReplayWithoutInlining>();
+  if (!ReplayState)
+    return 0;
+  const CallExpr *ReplayCE = reinterpret_cast<const CallExpr*>(ReplayState);
+  if (CE == ReplayCE) {
+    return N->getState()->remove<ReplayWithoutInlining>();
   }
-
-  // If we have no prototype, assume the function is okay.
-  if (!FT)
-    return true;
-  
-  // Skip inlining of variadic functions.
-  return !FT->isVariadic();
+  return 0;
 }
 
 void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
@@ -385,18 +398,20 @@ void ExprEngine::VisitCallExpr(const CallExpr *CE, ExplodedNode *Pred,
     DefaultEval(ExprEngine &eng, const CallExpr *ce)
     : Eng(eng), CE(ce) {}
     virtual void expandGraph(ExplodedNodeSet &Dst, ExplodedNode *Pred) {
-      // Should we inline the call?
-      if (shouldInlineCall(CE, Eng) &&
-          Eng.InlineCall(Dst, CE, Pred)) {
+
+      ProgramStateRef state = getReplayWithoutInliningState(Pred, CE);
+
+      // First, try to inline the call.
+      if (state == 0 && Eng.InlineCall(Dst, CE, Pred))
         return;
-      }
 
       // First handle the return value.
       StmtNodeBuilder Bldr(Pred, Dst, *Eng.currentBuilderContext);
 
       // Get the callee.
       const Expr *Callee = CE->getCallee()->IgnoreParens();
-      ProgramStateRef state = Pred->getState();
+      if (state == 0)
+        state = Pred->getState();
       SVal L = state->getSVal(Callee, Pred->getLocationContext());
 
       // Figure out the result type. We do this dance to handle references.
diff --git a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
index 2b8e77745e..3665955d61 100644
--- a/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
+++ b/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp
@@ -203,7 +203,8 @@ public:
                                   Opts.IPAMode,
                                   Opts.InlineMaxStackDepth,
                                   Opts.InlineMaxFunctionSize,
-                                  Opts.InliningMode));
+                                  Opts.InliningMode,
+                                  Opts.RetryExhausted));
   }
 
   virtual void HandleTranslationUnit(ASTContext &C);