Author: george.karpenkov Date: Thu Sep 6 17:42:32 2018 New Revision: 341616
URL: http://llvm.org/viewvc/llvm-project?rev=341616&view=rev Log: [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 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h cfe/trunk/lib/StaticAnalyzer/Core/ExplodedGraph.cpp cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h?rev=341616&r1=341615&r2=341616&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h Thu Sep 6 17:42:32 2018 @@ -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_end(NodeRef N) { return N->succ_end(); } + 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) { + 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); } Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExplodedGraph.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExplodedGraph.cpp?rev=341616&r1=341615&r2=341616&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExplodedGraph.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExplodedGraph.cpp Thu Sep 6 17:42:32 2018 @@ -290,6 +290,11 @@ int64_t ExplodedNode::getID(ExplodedGrap 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, Modified: cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp?rev=341616&r1=341615&r2=341616&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/ExprEngine.cpp Thu Sep 6 17:42:32 2018 @@ -2974,6 +2974,7 @@ struct DOTGraphTraits<ExplodedNode*> : p } 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*> : p 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*> : p } } + 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; - dumpProgramPoint(Loc, Out); + OtherNode = *OtherNode->succ_begin(); + + Out << "\\l--------\\l"; + } + + 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(); } }; _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits