[analyzer] Skip printing trivial nodes in exploded graph

[george.karpenkov]

Summary

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

[NoQ]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

246

its

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

3156

* -> *.

3170

Mmm, so would it dump all points separately and then dump all tags separately?

Maybe dump tags right after their respective points?

[NoQ]

Yeah, something like that :)

[xazax.hun]

I like that we print the program points for hidden nodes :) Great work!

clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

const_succ_iterator succ_begin() const {
     return const_cast<ExplodedNode*>(this)->succ_begin();
   }
   const_succ_iterator succ_end() const {
     return const_cast<ExplodedNode*>(this)->succ_end();
   }
 
   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); }
 };
 
 using InterExplodedGraphMap =
     llvm::DenseMap<const ExplodedNode *, const ExplodedNode *>;
 
namespace llvm {
 
   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
     using NodeRef = clang::ento::ExplodedNode *;
     using ChildIteratorType = clang::ento::ExplodedNode::succ_iterator;
     using nodes_iterator = llvm::df_iterator<NodeRef>;
 
     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); }
 
     static nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
   };
 
   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
     using NodeRef = const clang::ento::ExplodedNode *;

clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

 
 int64_t ExplodedNode::getID(ExplodedGraph *G) const {
   Optional<int64_t> Out = G->getAllocator().identifyObject(this);
   assert(Out && "Wrong allocator used");
   assert(*Out % alignof(ExplodedNode) == 0 && "Wrong alignment information");
   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,
                                      bool* IsNew) {
   // Profile 'State' to determine if we already have an existing node.
   llvm::FoldingSetNodeID profile;
   void *InsertPos = nullptr;
 

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

         << GraphPrintSourceManager->getExpansionLineNumber(SLoc)
         << " col="
         << GraphPrintSourceManager->getExpansionColumnNumber(SLoc)
         << "\\l";
     }
   }
 
   static void dumpProgramPoint(ProgramPoint Loc,
+                               const PrintingPolicy &PP,
                                llvm::raw_string_ostream &Out) {
     switch (Loc.getKind()) {
     case ProgramPoint::BlockEntranceKind:
       Out << "Block Entrance: B"
           << Loc.castAs<BlockEntrance>().getBlock()->getBlockID();
       break;
 
     case ProgramPoint::BlockExitKind:

       break;
     }
 
     default: {
       const Stmt *S = Loc.castAs<StmtPoint>().getStmt();
       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>())
         Out << "\\lPreStmt\\l;";
       else if (Loc.getAs<PostLoad>())
         Out << "\\lPostLoad\\l;";
       else if (Loc.getAs<PostStore>())
         Out << "\\lPostStore\\l";
       else if (Loc.getAs<PostLValue>())
         Out << "\\lPostLValue\\l";
       else if (Loc.getAs<PostAllocatorCall>())
         Out << "\\lPostAllocatorCall\\l";
 
       break;
     }
     }
   }
 
+  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();
   }
 };
 
 } // namespace llvm
 #endif
 
 void ExprEngine::ViewGraph(bool trim) {