[analyzer] Skip printing trivial nodes in exploded graph

A node is considered to be trivial if it only has one successor, one
predecessor, and a state equal to the predecessor.
Can drastically (> 2x) reduce the size of the generated exploded
graph.

Differential Revision: https://reviews.llvm.org/D51665

llvm-svn: 341616

3 files changed, 58 insertions, 18 deletions

diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 29754c163ac..14aba374b00 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -242,6 +242,11 @@ public:
 
   int64_t getID(ExplodedGraph *G) const;
 
+  /// The node is trivial if it has only one successor, only one predecessor,
+  /// and its program state is the same as the program state of the previous
+  /// node.
+  bool isTrivial() const;
+
 private:
   void replaceSuccessor(ExplodedNode *node) { Succs.replaceNode(node); }
   void replacePredecessor(ExplodedNode *node) { Preds.replaceNode(node); }
@@ -463,9 +468,19 @@ namespace llvm {
 
     static NodeRef getEntryNode(NodeRef N) { return N; }
 
-    static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
+    static ChildIteratorType child_begin(NodeRef N) {
+      if (N->succ_size() == 1 && (*N->succ_begin())->isTrivial()) {
+        return child_begin(*N->succ_begin());
+      }
+      return N->succ_begin();
+    }
 
-    static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
+    static ChildIteratorType child_end(NodeRef N) {
+      if (N->succ_size() == 1 && (*N->succ_begin())->isTrivial()) {
+        return child_end(*N->succ_begin());
+      }
+      return N->succ_end();
+    }
 
     static nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
 
diff --git a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
index 66944c616b9..7d7b88a8118 100644
--- a/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp
@@ -290,6 +290,11 @@ int64_t ExplodedNode::getID(ExplodedGraph *G) const {
   return *Out / alignof(ExplodedNode);
 }
 
+bool ExplodedNode::isTrivial() const {
+  return pred_size() == 1 && succ_size() == 1 &&
+         (*pred_begin())->getState()->getID() == getState()->getID();
+}
+
 ExplodedNode *ExplodedGraph::getNode(const ProgramPoint &L,
                                      ProgramStateRef State,
                                      bool IsSink,
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
index 3b1afcb92c0..638fc5de10f 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -2974,6 +2974,7 @@ struct DOTGraphTraits<ExplodedNode*> : public DefaultDOTGraphTraits {
   }
 
   static void dumpProgramPoint(ProgramPoint Loc,
+                               const PrintingPolicy &PP,
                                llvm::raw_string_ostream &Out) {
     switch (Loc.getKind()) {
     case ProgramPoint::BlockEntranceKind:
@@ -3112,8 +3113,7 @@ struct DOTGraphTraits<ExplodedNode*> : public DefaultDOTGraphTraits {
       assert(S != nullptr && "Expecting non-null Stmt");
 
       Out << S->getStmtClassName() << ' ' << (const void *)S << ' ';
-      LangOptions LO; // FIXME.
-      S->printPretty(Out, nullptr, PrintingPolicy(LO));
+      S->printPretty(Out, nullptr, PP);
       printLocation(Out, S->getBeginLoc());
 
       if (Loc.getAs<PreStmt>())
@@ -3132,32 +3132,52 @@ struct DOTGraphTraits<ExplodedNode*> : public DefaultDOTGraphTraits {
     }
   }
 
+  static bool isNodeHidden(const ExplodedNode *N) {
+    return N->isTrivial();
+  }
+
   static std::string getNodeLabel(const ExplodedNode *N, void*){
     std::string sbuf;
     llvm::raw_string_ostream Out(sbuf);
 
-    // Program Location.
-    ProgramPoint Loc = N->getLocation();
+    // Find the first node which program point and tag has to be included in
+    // the output.
+    const ExplodedNode *FirstHiddenNode = N;
+    while (FirstHiddenNode->pred_size() == 1 &&
+           isNodeHidden(*FirstHiddenNode->pred_begin())) {
+      FirstHiddenNode = *FirstHiddenNode->pred_begin();
+    }
+
+    ProgramStateRef State = N->getState();
+    const auto &PP = State->getStateManager().getContext().getPrintingPolicy();
+
+    // Dump program point for all the previously skipped nodes.
+    const ExplodedNode *OtherNode = FirstHiddenNode;
+    while (true) {
+      dumpProgramPoint(OtherNode->getLocation(), PP, Out);
+
+      if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
+        Out << "\\lTag:" << Tag->getTagDescription();
+
+      if (OtherNode == N)
+        break;
+
+      OtherNode = *OtherNode->succ_begin();
+
+      Out << "\\l--------\\l";
+    }
 
-    dumpProgramPoint(Loc, Out);
+    Out << "\\l\\|";
 
-    ProgramStateRef state = N->getState();
     ExplodedGraph &Graph =
-        static_cast<ExprEngine *>(state->getStateManager().getOwningEngine())
+        static_cast<ExprEngine *>(State->getStateManager().getOwningEngine())
             ->getGraph();
 
-    Out << "\\|StateID: " << state->getID() << " (" << (const void *)state.get()
+    Out << "StateID: " << State->getID() << " (" << (const void *)State.get()
         << ")"
         << " NodeID: " << N->getID(&Graph) << " (" << (const void *)N << ")\\|";
 
-    state->printDOT(Out, N->getLocationContext());
-
-    Out << "\\l";
-
-    if (const ProgramPointTag *tag = Loc.getTag()) {
-      Out << "\\|Tag: " << tag->getTagDescription();
-      Out << "\\l";
-    }
+    State->printDOT(Out, N->getLocationContext());
     return Out.str();
   }
 };