[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

8 files changed, 67 insertions, 6 deletions

diff --git a/include/clang/Analysis/ProgramPoint.h b/include/clang/Analysis/ProgramPoint.h
index 413b3cf4ea..e7bcf19bde 100644
--- a/include/clang/Analysis/ProgramPoint.h
+++ b/include/clang/Analysis/ProgramPoint.h
@@ -51,7 +51,8 @@ public:
               CallEnterKind,
               CallExitKind,
               MinPostStmtKind = PostStmtKind,
-              MaxPostStmtKind = CallExitKind };
+              MaxPostStmtKind = CallExitKind,
+              EpsilonKind};
 
 private:
   std::pair<const void *, const void *> Data;
@@ -380,6 +381,21 @@ public:
   }
 };
 
+/// This is a meta program point, which should be skipped by all the diagnostic
+/// reasoning etc.
+class EpsilonPoint : public ProgramPoint {
+public:
+  EpsilonPoint(const LocationContext *L, const void *Data1,
+               const void *Data2 = 0, const ProgramPointTag *tag = 0)
+    : ProgramPoint(Data1, Data2, EpsilonKind, L, tag) {}
+
+  const void *getData() const { return getData1(); }
+
+  static bool classof(const ProgramPoint* Location) {
+    return Location->getKind() == EpsilonKind;
+  }
+};
+
 /// ProgramPoints can be "tagged" as representing points specific to a given
 /// analysis entity.  Tags are abstract annotations, with an associated
 /// description and potentially other information.
diff --git a/include/clang/Driver/CC1Options.td b/include/clang/Driver/CC1Options.td
index e8ec822715..46c4ed89b5 100644
--- a/include/clang/Driver/CC1Options.td
+++ b/include/clang/Driver/CC1Options.td
@@ -98,6 +98,9 @@ def analyzer_ipa_EQ : Joined<"-analyzer-ipa=">, Alias<analyzer_ipa>;
 def analyzer_inlining_mode : Separate<"-analyzer-inlining-mode">,
   HelpText<"Specify the function selection heuristic used during inlining">;
 def analyzer_inlining_mode_EQ : Joined<"-analyzer-inlining-mode=">, Alias<analyzer_inlining_mode>;
+
+def analyzer_retry_exhausted : Flag<"-analyzer-retry-exhausted">,
+  HelpText<"Re-analyze paths leading to exhausted nodes with a different strategy for better code coverage">;
   
 def analyzer_max_nodes : Separate<"-analyzer-max-nodes">,
   HelpText<"The maximum number of nodes the analyzer can generate (150000 default, 0 = no limit)">;
diff --git a/include/clang/Frontend/AnalyzerOptions.h b/include/clang/Frontend/AnalyzerOptions.h
index 4199df0b6e..f152f63968 100644
--- a/include/clang/Frontend/AnalyzerOptions.h
+++ b/include/clang/Frontend/AnalyzerOptions.h
@@ -99,6 +99,7 @@ public:
   unsigned CFGAddInitializers : 1;
   unsigned EagerlyTrimEGraph : 1;
   unsigned PrintStats : 1;
+  unsigned RetryExhausted : 1;
   unsigned InlineMaxStackDepth;
   unsigned InlineMaxFunctionSize;
   AnalysisInliningMode InliningMode;
@@ -123,6 +124,7 @@ public:
     CFGAddInitializers = 0;
     EagerlyTrimEGraph = 0;
     PrintStats = 0;
+    RetryExhausted = 0;
     // Cap the stack depth at 4 calls (5 stack frames, base + 4 calls).
     InlineMaxStackDepth = 5;
     InlineMaxFunctionSize = 200;
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h
index 3e19b26328..b77e069041 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h
@@ -91,6 +91,10 @@ public:
   /// \brief The mode of function selection used during inlining.
   AnalysisInliningMode InliningMode;
 
+  /// \brief Re-analyze paths leading to exhausted nodes with a different
+  /// strategy for better code coverage.
+  bool RetryExhausted;
+
 public:
   AnalysisManager(ASTContext &ctx, DiagnosticsEngine &diags, 
                   const LangOptions &lang, PathDiagnosticConsumer *pd,
@@ -107,7 +111,8 @@ public:
                   AnalysisIPAMode ipa,
                   unsigned inlineMaxStack,
                   unsigned inlineMaxFunctionSize,
-                  AnalysisInliningMode inliningMode);
+                  AnalysisInliningMode inliningMode,
+                  bool retry);
 
   /// Construct a clone of the given AnalysisManager with the given ASTContext
   /// and DiagnosticsEngine.
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
index 18ad0078c6..a9a4ae4230 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h
@@ -98,9 +98,6 @@ private:
   CoreEngine(const CoreEngine&); // Do not implement.
   CoreEngine& operator=(const CoreEngine&);
 
-  void enqueueStmtNode(ExplodedNode *N,
-                       const CFGBlock *Block, unsigned Idx);
-
   ExplodedNode *generateCallExitNode(ExplodedNode *N);
 
 public:
@@ -132,6 +129,11 @@ public:
                                        ProgramStateRef InitState, 
                                        ExplodedNodeSet &Dst);
 
+  /// Dispatch the work list item based on the given location information.
+  /// Use Pred parameter as the predecessor state.
+  void dispatchWorkItem(ExplodedNode* Pred, ProgramPoint Loc,
+                        const WorkListUnit& WU);
+
   // Functions for external checking of whether we have unfinished work
   bool wasBlockAborted() const { return !blocksAborted.empty(); }
   bool wasBlocksExhausted() const { return !blocksExhausted.empty(); }
@@ -170,6 +172,9 @@ public:
   /// \brief enqueue the nodes corresponding to the end of function onto the
   /// end of path / work list.
   void enqueueEndOfFunction(ExplodedNodeSet &Set);
+
+  /// \brief Enqueue a single node created as a result of statement processing.
+  void enqueueStmtNode(ExplodedNode *N, const CFGBlock *Block, unsigned Idx);
 };
 
 // TODO: Turn into a calss.
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 1c81af9586..46fbb88212 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -173,6 +173,10 @@ public:
 
   bool isSink() const { return Succs.getFlag(); }
 
+   bool hasSinglePred() const {
+    return (pred_size() == 1);
+  }
+
   ExplodedNode *getFirstPred() {
     return pred_empty() ? NULL : *(pred_begin());
   }
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
index e8c4688293..2c144109b2 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
@@ -20,6 +20,7 @@
 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/Type.h"
@@ -455,7 +456,19 @@ private:
                     ProgramStateRef St, SVal location,
                     const ProgramPointTag *tag, bool isLoad);
 
+  bool shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred);
   bool InlineCall(ExplodedNodeSet &Dst, const CallExpr *CE, ExplodedNode *Pred);
+
+  bool replayWithoutInlining(ExplodedNode *P, const LocationContext *CalleeLC);
+};
+
+/// Traits for storing the call processing policy inside GDM.
+/// The GDM stores the corresponding CallExpr pointer.
+struct ReplayWithoutInlining{};
+template <>
+struct ProgramStateTrait<ReplayWithoutInlining> :
+  public ProgramStatePartialTrait<void*> {
+  static void *GDMIndex() { static int index = 0; return &index; }
 };
 
 } // end ento namespace
diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h
index e79b593584..1c7bedb82f 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h
@@ -176,7 +176,20 @@ namespace ento {
       return (void*) (uintptr_t) d;
     }
   };
-  
+
+  // Partial specialization for void*.
+  template <> struct ProgramStatePartialTrait<void*> {
+    typedef void *data_type;
+
+    static inline data_type MakeData(void *const* p) {
+      return p ? *p
+               : data_type();
+    }
+    static inline void *MakeVoidPtr(data_type d) {
+      return d;
+    }
+  };
+
 } // end GR namespace
 
 } // end clang namespace