[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
GitOrigin-RevId: fd4a10732c8bd646ccc621c0a9af512be252f33a
diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h
index bc6a19f..5370079 100644
--- a/include/llvm/Analysis/CFGPrinter.h
+++ b/include/llvm/Analysis/CFGPrinter.h
@@ -295,7 +295,7 @@
" 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/include/llvm/Analysis/DDG.h b/include/llvm/Analysis/DDG.h
index 9e2b790..8d225c1 100644
--- a/include/llvm/Analysis/DDG.h
+++ b/include/llvm/Analysis/DDG.h
@@ -290,6 +290,12 @@
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 @@
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/include/llvm/Analysis/DDGPrinter.h b/include/llvm/Analysis/DDGPrinter.h
new file mode 100644
index 0000000..5cfe2ce
--- /dev/null
+++ b/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/include/llvm/Support/DOTGraphTraits.h b/include/llvm/Support/DOTGraphTraits.h
index ec01b7d..a73538f 100644
--- a/include/llvm/Support/DOTGraphTraits.h
+++ b/include/llvm/Support/DOTGraphTraits.h
@@ -60,7 +60,8 @@
/// 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/include/llvm/Support/GraphWriter.h b/include/llvm/Support/GraphWriter.h
index f9241b1..1f60fbc 100644
--- a/include/llvm/Support/GraphWriter.h
+++ b/include/llvm/Support/GraphWriter.h
@@ -158,9 +158,7 @@
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 @@
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/lib/Analysis/CFGPrinter.cpp b/lib/Analysis/CFGPrinter.cpp
index cf4afc8..582e61b 100644
--- a/lib/Analysis/CFGPrinter.cpp
+++ b/lib/Analysis/CFGPrinter.cpp
@@ -289,7 +289,8 @@
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/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index c7e20b2..b89b6b3 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -39,6 +39,7 @@
CodeMetrics.cpp
ConstantFolding.cpp
DDG.cpp
+ DDGPrinter.cpp
ConstraintSystem.cpp
Delinearization.cpp
DemandedBits.cpp
diff --git a/lib/Analysis/CallPrinter.cpp b/lib/Analysis/CallPrinter.cpp
index bb44741..c3922d5 100644
--- a/lib/Analysis/CallPrinter.cpp
+++ b/lib/Analysis/CallPrinter.cpp
@@ -143,7 +143,8 @@
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/lib/Analysis/DDGPrinter.cpp b/lib/Analysis/DDGPrinter.cpp
new file mode 100644
index 0000000..51bd548
--- /dev/null
+++ b/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/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp
index 5843f84..8d51bb2 100644
--- a/lib/CodeGen/MachineScheduler.cpp
+++ b/lib/CodeGen/MachineScheduler.cpp
@@ -3836,7 +3836,7 @@
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/lib/CodeGen/ScheduleDAGPrinter.cpp b/lib/CodeGen/ScheduleDAGPrinter.cpp
index a113c30..05b2a37 100644
--- a/lib/CodeGen/ScheduleDAGPrinter.cpp
+++ b/lib/CodeGen/ScheduleDAGPrinter.cpp
@@ -35,7 +35,7 @@
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/lib/Passes/PassBuilder.cpp b/lib/Passes/PassBuilder.cpp
index d11725d..a7ef8e3 100644
--- a/lib/Passes/PassBuilder.cpp
+++ b/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/lib/Passes/PassRegistry.def b/lib/Passes/PassRegistry.def
index ffd91bf..f971027 100644
--- a/lib/Passes/PassRegistry.def
+++ b/lib/Passes/PassRegistry.def
@@ -384,6 +384,7 @@
#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())
