Author: Bardia Mahjour Date: 2020-12-14T16:41:14-05:00 New Revision: fd4a10732c8bd646ccc621c0a9af512be252f33a
URL: https://github.com/llvm/llvm-project/commit/fd4a10732c8bd646ccc621c0a9af512be252f33a DIFF: https://github.com/llvm/llvm-project/commit/fd4a10732c8bd646ccc621c0a9af512be252f33a.diff LOG: [DDG] Data Dependence Graph - DOT printer This patch implements a DDG printer pass that generates a graph in the DOT description language, providing a more visually appealing representation of the DDG. Similar to the CFG DOT printer, this functionality is provided under an option called -dot-ddg and can be generated in a less verbose mode under -dot-ddg-only option. Differential Revision: https://reviews.llvm.org/D90159 Added: llvm/include/llvm/Analysis/DDGPrinter.h llvm/lib/Analysis/DDGPrinter.cpp Modified: clang/lib/StaticAnalyzer/Core/ExprEngine.cpp llvm/include/llvm/Analysis/CFGPrinter.h llvm/include/llvm/Analysis/DDG.h llvm/include/llvm/Support/DOTGraphTraits.h llvm/include/llvm/Support/GraphWriter.h llvm/lib/Analysis/CFGPrinter.cpp llvm/lib/Analysis/CMakeLists.txt llvm/lib/Analysis/CallPrinter.cpp llvm/lib/CodeGen/MachineScheduler.cpp llvm/lib/CodeGen/ScheduleDAGPrinter.cpp llvm/lib/Passes/PassBuilder.cpp llvm/lib/Passes/PassRegistry.def Removed: ################################################################################ diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 409741cdb6e4..f285b652c175 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3149,7 +3149,7 @@ struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { if (Stop(N)) return true; - if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc())) + if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc(), nullptr)) break; PostCallback(N); @@ -3158,7 +3158,7 @@ struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits { return false; } - static bool isNodeHidden(const ExplodedNode *N) { + static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) { return N->isTrivial(); } diff --git a/llvm/include/llvm/Analysis/CFGPrinter.h b/llvm/include/llvm/Analysis/CFGPrinter.h index bc6a19f2e2b9..53700798b6b3 100644 --- a/llvm/include/llvm/Analysis/CFGPrinter.h +++ b/llvm/include/llvm/Analysis/CFGPrinter.h @@ -295,7 +295,7 @@ struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits { " fillcolor=\"" + Color + "70\""; return Attrs; } - bool isNodeHidden(const BasicBlock *Node); + bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo); void computeHiddenNodes(const Function *F); }; } // End llvm namespace diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h index 9e2b7907eaec..8d225c155cd4 100644 --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -290,6 +290,12 @@ template <typename NodeType> class DependenceGraphInfo { bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const; + /// Return a string representing the type of dependence that the dependence + /// analysis identified between the two given nodes. This function assumes + /// that there is a memory dependence between the given two nodes. + const std::string getDependenceString(const NodeType &Src, + const NodeType &Dst) const; + protected: // Name of the graph. std::string Name; @@ -463,6 +469,26 @@ bool DependenceGraphInfo<NodeType>::getDependencies( return !Deps.empty(); } +template <typename NodeType> +const std::string +DependenceGraphInfo<NodeType>::getDependenceString(const NodeType &Src, + const NodeType &Dst) const { + std::string Str; + raw_string_ostream OS(Str); + DependenceList Deps; + if (!getDependencies(Src, Dst, Deps)) + return OS.str(); + interleaveComma(Deps, OS, [&](const std::unique_ptr<Dependence> &D) { + D->dump(OS); + // Remove the extra new-line character printed by the dump + // method + if (OS.str().back() == '\n') + OS.str().pop_back(); + }); + + return OS.str(); +} + //===--------------------------------------------------------------------===// // GraphTraits specializations for the DDG //===--------------------------------------------------------------------===// diff --git a/llvm/include/llvm/Analysis/DDGPrinter.h b/llvm/include/llvm/Analysis/DDGPrinter.h new file mode 100644 index 000000000000..5cfe2ce33c99 --- /dev/null +++ b/llvm/include/llvm/Analysis/DDGPrinter.h @@ -0,0 +1,91 @@ +//===- llvm/Analysis/DDGPrinter.h -------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// +// This file defines the DOT printer for the Data-Dependence Graph (DDG). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DDGPRINTER_H +#define LLVM_ANALYSIS_DDGPRINTER_H + +#include "llvm/Analysis/DDG.h" +#include "llvm/Pass.h" +#include "llvm/Support/DOTGraphTraits.h" + +namespace llvm { + +//===--------------------------------------------------------------------===// +// Implementation of DDG DOT Printer for a loop. +//===--------------------------------------------------------------------===// +class DDGDotPrinterPass : public PassInfoMixin<DDGDotPrinterPass> { +public: + PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &U); +}; + +//===--------------------------------------------------------------------===// +// Specialization of DOTGraphTraits. +//===--------------------------------------------------------------------===// +template <> +struct DOTGraphTraits<const DataDependenceGraph *> + : public DefaultDOTGraphTraits { + + DOTGraphTraits(bool IsSimple = false) : DefaultDOTGraphTraits(IsSimple) {} + + /// Generate a title for the graph in DOT format + std::string getGraphName(const DataDependenceGraph *G) { + assert(G && "expected a valid pointer to the graph."); + return "DDG for '" + std::string(G->getName()) + "'"; + } + + /// Print a DDG node either in concise form (-ddg-dot-only) or + /// verbose mode (-ddg-dot). + std::string getNodeLabel(const DDGNode *Node, + const DataDependenceGraph *Graph); + + /// Print attributes of an edge in the DDG graph. If the edge + /// is a MemoryDependence edge, then detailed dependence info + /// available from DependenceAnalysis is displayed. + std::string + getEdgeAttributes(const DDGNode *Node, + GraphTraits<const DDGNode *>::ChildIteratorType I, + const DataDependenceGraph *G); + + /// Do not print nodes that are part of a pi-block separately. They + /// will be printed when their containing pi-block is being printed. + bool isNodeHidden(const DDGNode *Node, const DataDependenceGraph *G); + +private: + /// Print a DDG node in concise form. + static std::string getSimpleNodeLabel(const DDGNode *Node, + const DataDependenceGraph *G); + + /// Print a DDG node with more information including containing instructions + /// and detailed information about the dependence edges. + static std::string getVerboseNodeLabel(const DDGNode *Node, + const DataDependenceGraph *G); + + /// Print a DDG edge in concise form. + static std::string getSimpleEdgeAttributes(const DDGNode *Src, + const DDGEdge *Edge, + const DataDependenceGraph *G); + + /// Print a DDG edge with more information including detailed information + /// about the dependence edges. + static std::string getVerboseEdgeAttributes(const DDGNode *Src, + const DDGEdge *Edge, + const DataDependenceGraph *G); +}; + +using DDGDotGraphTraits = struct DOTGraphTraits<const DataDependenceGraph *>; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_DDGPRINTER_H diff --git a/llvm/include/llvm/Support/DOTGraphTraits.h b/llvm/include/llvm/Support/DOTGraphTraits.h index ec01b7d9576a..a73538fa1462 100644 --- a/llvm/include/llvm/Support/DOTGraphTraits.h +++ b/llvm/include/llvm/Support/DOTGraphTraits.h @@ -60,7 +60,8 @@ struct DefaultDOTGraphTraits { /// isNodeHidden - If the function returns true, the given node is not /// displayed in the graph. - static bool isNodeHidden(const void *) { + template <typename GraphType> + static bool isNodeHidden(const void *, const GraphType &) { return false; } diff --git a/llvm/include/llvm/Support/GraphWriter.h b/llvm/include/llvm/Support/GraphWriter.h index f9241b1e8081..1f60fbc35126 100644 --- a/llvm/include/llvm/Support/GraphWriter.h +++ b/llvm/include/llvm/Support/GraphWriter.h @@ -158,9 +158,7 @@ class GraphWriter { writeNode(Node); } - bool isNodeHidden(NodeRef Node) { - return DTraits.isNodeHidden(Node); - } + bool isNodeHidden(NodeRef Node) { return DTraits.isNodeHidden(Node, G); } void writeNode(NodeRef Node) { std::string NodeAttributes = DTraits.getNodeAttributes(Node, G); @@ -228,10 +226,10 @@ class GraphWriter { child_iterator EI = GTraits::child_begin(Node); child_iterator EE = GTraits::child_end(Node); for (unsigned i = 0; EI != EE && i != 64; ++EI, ++i) - if (!DTraits.isNodeHidden(*EI)) + if (!DTraits.isNodeHidden(*EI, G)) writeEdge(Node, i, EI); for (; EI != EE; ++EI) - if (!DTraits.isNodeHidden(*EI)) + if (!DTraits.isNodeHidden(*EI, G)) writeEdge(Node, 64, EI); } diff --git a/llvm/lib/Analysis/CFGPrinter.cpp b/llvm/lib/Analysis/CFGPrinter.cpp index cf4afc8cfd9c..582e61b33f49 100644 --- a/llvm/lib/Analysis/CFGPrinter.cpp +++ b/llvm/lib/Analysis/CFGPrinter.cpp @@ -289,7 +289,8 @@ void DOTGraphTraits<DOTFuncInfo *>::computeHiddenNodes(const Function *F) { evaluateBB); } -bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node) { +bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node, + const DOTFuncInfo *CFGInfo) { // If both restricting flags are false, all nodes are displayed. if (!HideUnreachablePaths && !HideDeoptimizePaths) return false; diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index c7e20b2e90dd..b89b6b3c4c64 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -39,6 +39,7 @@ add_llvm_component_library(LLVMAnalysis CodeMetrics.cpp ConstantFolding.cpp DDG.cpp + DDGPrinter.cpp ConstraintSystem.cpp Delinearization.cpp DemandedBits.cpp diff --git a/llvm/lib/Analysis/CallPrinter.cpp b/llvm/lib/Analysis/CallPrinter.cpp index bb447411ec47..c3922d556023 100644 --- a/llvm/lib/Analysis/CallPrinter.cpp +++ b/llvm/lib/Analysis/CallPrinter.cpp @@ -143,7 +143,8 @@ struct DOTGraphTraits<CallGraphDOTInfo *> : public DefaultDOTGraphTraits { std::string(CGInfo->getModule()->getModuleIdentifier()); } - static bool isNodeHidden(const CallGraphNode *Node) { + static bool isNodeHidden(const CallGraphNode *Node, + const CallGraphDOTInfo *CGInfo) { if (CallMultiGraph || Node->getFunction()) return false; return true; diff --git a/llvm/lib/Analysis/DDGPrinter.cpp b/llvm/lib/Analysis/DDGPrinter.cpp new file mode 100644 index 000000000000..51bd54809857 --- /dev/null +++ b/llvm/lib/Analysis/DDGPrinter.cpp @@ -0,0 +1,150 @@ +//===- DDGPrinter.cpp - DOT printer for the data dependence graph ----------==// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +//===----------------------------------------------------------------------===// +// +// This file defines the `-dot-ddg` analysis pass, which emits DDG in DOT format +// in a file named `ddg.<graph-name>.dot` for each loop in a function. +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/DDGPrinter.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/GraphWriter.h" + +using namespace llvm; + +static cl::opt<bool> DotOnly("dot-ddg-only", cl::init(false), cl::Hidden, + cl::ZeroOrMore, cl::desc("simple ddg dot graph")); +static cl::opt<std::string> DDGDotFilenamePrefix( + "dot-ddg-filename-prefix", cl::init("ddg"), cl::Hidden, + cl::desc("The prefix used for the DDG dot file names.")); + +static void writeDDGToDotFile(DataDependenceGraph &G, bool DOnly = false); + +//===--------------------------------------------------------------------===// +// Implementation of DDG DOT Printer for a loop +//===--------------------------------------------------------------------===// +PreservedAnalyses DDGDotPrinterPass::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LPMUpdater &U) { + writeDDGToDotFile(*AM.getResult<DDGAnalysis>(L, AR), DotOnly); + return PreservedAnalyses::all(); +} + +static void writeDDGToDotFile(DataDependenceGraph &G, bool DOnly) { + std::string Filename = + Twine(DDGDotFilenamePrefix + "." + G.getName() + ".dot").str(); + errs() << "Writing '" << Filename << "'..."; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + + if (!EC) + // We only provide the constant verson of the DOTGraphTrait specialization, + // hence the conversion to const pointer + WriteGraph(File, (const DataDependenceGraph *)&G, DOnly); + else + errs() << " error opening file for writing!"; + errs() << "\n"; +} + +//===--------------------------------------------------------------------===// +// DDG DOT Printer Implementation +//===--------------------------------------------------------------------===// +std::string DDGDotGraphTraits::getNodeLabel(const DDGNode *Node, + const DataDependenceGraph *Graph) { + if (isSimple()) + return getSimpleNodeLabel(Node, Graph); + else + return getVerboseNodeLabel(Node, Graph); +} + +std::string DDGDotGraphTraits::getEdgeAttributes( + const DDGNode *Node, GraphTraits<const DDGNode *>::ChildIteratorType I, + const DataDependenceGraph *G) { + const DDGEdge *E = static_cast<const DDGEdge *>(*I.getCurrent()); + if (isSimple()) + return getSimpleEdgeAttributes(Node, E, G); + else + return getVerboseEdgeAttributes(Node, E, G); +} + +bool DDGDotGraphTraits::isNodeHidden(const DDGNode *Node, + const DataDependenceGraph *Graph) { + if (isSimple() && isa<RootDDGNode>(Node)) + return true; + assert(Graph && "expected a valid graph pointer"); + return Graph->getPiBlock(*Node) != nullptr; +} + +std::string +DDGDotGraphTraits::getSimpleNodeLabel(const DDGNode *Node, + const DataDependenceGraph *G) { + std::string Str; + raw_string_ostream OS(Str); + if (isa<SimpleDDGNode>(Node)) + for (auto *II : static_cast<const SimpleDDGNode *>(Node)->getInstructions()) + OS << *II << "\n"; + else if (isa<PiBlockDDGNode>(Node)) + OS << "pi-block\nwith\n" + << cast<PiBlockDDGNode>(Node)->getNodes().size() << " nodes\n"; + else if (isa<RootDDGNode>(Node)) + OS << "root\n"; + else + llvm_unreachable("Unimplemented type of node"); + return OS.str(); +} + +std::string +DDGDotGraphTraits::getVerboseNodeLabel(const DDGNode *Node, + const DataDependenceGraph *G) { + std::string Str; + raw_string_ostream OS(Str); + OS << "<kind:" << Node->getKind() << ">\n"; + if (isa<SimpleDDGNode>(Node)) + for (auto *II : static_cast<const SimpleDDGNode *>(Node)->getInstructions()) + OS << *II << "\n"; + else if (isa<PiBlockDDGNode>(Node)) { + OS << "--- start of nodes in pi-block ---\n"; + unsigned Count = 0; + const auto &PNodes = cast<PiBlockDDGNode>(Node)->getNodes(); + for (auto *PN : PNodes) { + OS << getVerboseNodeLabel(PN, G); + if (++Count != PNodes.size()) + OS << "\n"; + } + OS << "--- end of nodes in pi-block ---\n"; + } else if (isa<RootDDGNode>(Node)) + OS << "root\n"; + else + llvm_unreachable("Unimplemented type of node"); + return OS.str(); +} + +std::string DDGDotGraphTraits::getSimpleEdgeAttributes( + const DDGNode *Src, const DDGEdge *Edge, const DataDependenceGraph *G) { + std::string Str; + raw_string_ostream OS(Str); + DDGEdge::EdgeKind Kind = Edge->getKind(); + OS << "label=\"[" << Kind << "]\""; + return OS.str(); +} + +std::string DDGDotGraphTraits::getVerboseEdgeAttributes( + const DDGNode *Src, const DDGEdge *Edge, const DataDependenceGraph *G) { + std::string Str; + raw_string_ostream OS(Str); + DDGEdge::EdgeKind Kind = Edge->getKind(); + OS << "label=\"["; + if (Kind == DDGEdge::EdgeKind::MemoryDependence) + OS << G->getDependenceString(*Src, Edge->getTargetNode()); + else + OS << Kind; + OS << "]\""; + return OS.str(); +} diff --git a/llvm/lib/CodeGen/MachineScheduler.cpp b/llvm/lib/CodeGen/MachineScheduler.cpp index 5843f84b2a91..8d51bb26103a 100644 --- a/llvm/lib/CodeGen/MachineScheduler.cpp +++ b/llvm/lib/CodeGen/MachineScheduler.cpp @@ -3836,7 +3836,7 @@ struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits { return true; } - static bool isNodeHidden(const SUnit *Node) { + static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) { if (ViewMISchedCutoff == 0) return false; return (Node->Preds.size() > ViewMISchedCutoff diff --git a/llvm/lib/CodeGen/ScheduleDAGPrinter.cpp b/llvm/lib/CodeGen/ScheduleDAGPrinter.cpp index a113c30f851b..05b2a3764cca 100644 --- a/llvm/lib/CodeGen/ScheduleDAGPrinter.cpp +++ b/llvm/lib/CodeGen/ScheduleDAGPrinter.cpp @@ -35,7 +35,7 @@ namespace llvm { return true; } - static bool isNodeHidden(const SUnit *Node) { + static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) { return (Node->NumPreds > 10 || Node->NumSuccs > 10); } diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index d11725d7507c..a7ef8e3b8add 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -29,6 +29,7 @@ #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DDG.h" +#include "llvm/Analysis/DDGPrinter.h" #include "llvm/Analysis/Delinearization.h" #include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/DependenceAnalysis.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index ffd91bfdf8ac..f971027299d4 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -384,6 +384,7 @@ LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) #define LOOP_PASS(NAME, CREATE_PASS) #endif LOOP_PASS("canon-freeze", CanonicalizeFreezeInLoopsPass()) +LOOP_PASS("dot-ddg", DDGDotPrinterPass()) LOOP_PASS("invalidate<all>", InvalidateAllAnalysesPass()) LOOP_PASS("licm", LICMPass()) LOOP_PASS("loop-idiom", LoopIdiomRecognizePass()) _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
