[DDG] Data Dependence Graph - DOT printer

[bmahjour]

Summary

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.

[bmahjour]

ping!

[Meinersbur]

llvm/include/llvm/Analysis/DDG.h

476

[nit] The initializer ("") is useless? std::string default-initializes to an empty string.

481

[suggestion] Instead of count, you can use llvm::enumerate. I think it's nicer to check at for "not the first" at the beginning instead of the last element at the end.

There also is an interleave function in STLExtras.h for uses cases like this.

llvm/include/llvm/Analysis/DDGPrinter.h

22

[style] Space between includes and namespace?

46

Why does a getter set a field value?

llvm/lib/Analysis/DDGPrinter.cpp

110

Does this const_cast exist to add const qualifier?

118

Could you split this up?

if (Count != PNodes.size())
  OS << "\n";

[bmahjour]

Thanks for the review @Meinersbur and sorry for taking so long to address your comments.

[bmahjour]

llvm/include/llvm/Analysis/DDG.h

481

Interesting! Thanks for pointing out those utilities! I'll use interleave.

llvm/include/llvm/Analysis/DDGPrinter.h

46

Good question :)

When printing pi-blocks we would like to show the member nodes being enclosed by the pi-node. However, since the member nodes are also part of the graph, they will get visited during the walk and get dumped into the resulting dot file. To solve this, I'm trying to hide the member nodes from the walk (via isNodeHidden()) when they get visited and then print them as part of printing the pi-block node.

The problem I encountered was that, isNodeHidden() only takes a graph node as a parameter, but for me to know whether a node belongs to a pi-block I need to get access to the graph that contains the nodes. To get around this, I'm caching a pointer to the graph when the getGraphName gets called and use it when isNodeHidden is invoked....yikes!

A cleaner solution (and one that may have other uses in the future) is to make isNodeHidden() take a graph object as argument (similar to getNodeLabel(), and getGraphName()). I'll update the patch to include that change.

llvm/lib/Analysis/DDGPrinter.cpp

110

No. The static_cast is used because the getInstructions() is a member function of SimpleDDGNode but not DDGNode.

[Meinersbur]

Thanks, LGTM.

llvm/include/llvm/Analysis/DDG.h

489

llvm::interleaveComma does that without an additional lambda.

[bmahjour]

fix formatting and use interleaveComma instead of interleave.

[Meinersbur]

Thanks. Still LGTM.

[Meinersbur]

Can I help fixing the Windows build problem?

[bmahjour]

In D90159#2453805, @Meinersbur wrote:

Can I help fixing the Windows build problem?

I think I have a fix (please see the updated patch), but don't have access to a windows machine to verify. Would you be able to try building with MSVC and let me know if it passes?

[bmahjour]

In D90159#2454905, @bmahjour wrote:

In D90159#2453805, @Meinersbur wrote:

Can I help fixing the Windows build problem?

I think I have a fix (please see the updated patch), but don't have access to a windows machine to verify. Would you be able to try building with MSVC and let me know if it passes?

I'll try to recommit and watch the windows buildbots.

[MaskRay]

Should this have some tests? Even if guarded by REQUIRES: if some feature is needed.

[bmahjour]

In D90159#2466599, @MaskRay wrote:

Should this have some tests? Even if guarded by REQUIRES: if some feature is needed.

Test coverage for the DDG functionality has been added under LIT and unittests. I've opened https://reviews.llvm.org/D93949 to add a test and verify the formatting of the dot file produced when using -dot-ddg.

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp

static bool traverseHiddenNodes(
       llvm::function_ref<void(const ExplodedNode *)> PreCallback,
       llvm::function_ref<void(const ExplodedNode *)> PostCallback,
       llvm::function_ref<bool(const ExplodedNode *)> Stop) {
     while (true) {
       PreCallback(N);
       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);
 
       N = N->getFirstSucc();
     }
     return false;
   }
 
-  static bool isNodeHidden(const ExplodedNode *N) {
+  static bool isNodeHidden(const ExplodedNode *N, const ExplodedGraph *G) {
     return N->isTrivial();
   }
 
   static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
     std::string Buf;
     llvm::raw_string_ostream Out(Buf);
 
     const bool IsDot = true;

llvm/include/llvm/Analysis/CFGPrinter.h

std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
     std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
                                 ? (getHeatColor(0))
                                 : (getHeatColor(1));
 
     std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
                         " 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
 
 namespace llvm {
 class FunctionPass;
 FunctionPass *createCFGPrinterLegacyPassPass();
 FunctionPass *createCFGOnlyPrinterLegacyPassPass();
 } // End llvm namespace
 
 #endif

llvm/include/llvm/Analysis/DDG.h

public:
   }
 
   /// Collect all the data dependency infos coming from any pair of memory
   /// accesses from \p Src to \p Dst, and store them into \p Deps. Return true
   /// if a dependence exists, and false otherwise.
   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;
 
   // Store a copy of DependenceInfo in the graph, so that individual memory
   // dependencies don't need to be stored. Instead when the dependence is
   // queried it is recomputed using @DI.
   const DependenceInfo DI;
for (auto *SrcI : SrcIList)
     for (auto *DstI : DstIList)
       if (auto Dep =
               const_cast<DependenceInfo *>(&DI)->depends(SrcI, DstI, true))
         Deps.push_back(std::move(Dep));
 
   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
 //===--------------------------------------------------------------------===//
 
 /// non-const versions of the grapth trait specializations for DDG
 template <> struct GraphTraits<DDGNode *> {
   using NodeRef = DDGNode *;
 

llvm/include/llvm/Analysis/DDGPrinter.h

+//===- 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

llvm/include/llvm/Support/DOTGraphTraits.h

public:
   /// emitted bottom-up instead of top-down.  This requires graphviz 2.0 to work
   /// though.
   static bool renderGraphFromBottomUp() {
     return false;
   }
 
   /// 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;
   }
 
   /// getNodeLabel - Given a node and a pointer to the top level graph, return
   /// the label to print in the node.
   template<typename GraphType>
   std::string getNodeLabel(const void *, const GraphType &) {
     return "";

llvm/include/llvm/Support/GraphWriter.h

public:
 
   void writeNodes() {
     // Loop over the graph, printing it out...
     for (const auto Node : nodes<GraphType>(G))
       if (!isNodeHidden(Node))
         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);
 
     O << "\tNode" << static_cast<const void*>(Node) << " [shape=record,";
     if (!NodeAttributes.empty()) O << NodeAttributes << ",";
     O << "label=\"{";
 
void writeNode(NodeRef Node) {
     }
 
     O << "}\"];\n";   // Finish printing the "node" line
 
     // Output all of the edges now
     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);
   }
 
   void writeEdge(NodeRef Node, unsigned edgeidx, child_iterator EI) {
     if (NodeRef TargetNode = *EI) {
       int DestPort = -1;
       if (DTraits.edgeTargetsEdgeSource(Node, EI)) {
         child_iterator TargetIt = DTraits.getEdgeTarget(Node, EI);

llvm/lib/Analysis/CFGPrinter.cpp

isHiddenBasicBlock[Node] = std::all_of(
         [this](const BasicBlock *BB) { return isHiddenBasicBlock[BB]; });
   };
   /// The post order traversal iteration is done to know the status of
   /// isHiddenBasicBlock for all the successors on the current BB.
   for_each(po_begin(&F->getEntryBlock()), po_end(&F->getEntryBlock()),
            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;
   if (isHiddenBasicBlock.find(Node) == isHiddenBasicBlock.end())
     computeHiddenNodes(Node->getParent());
   return isHiddenBasicBlock[Node];
 }

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
   DDG.cpp
+  DDGPrinter.cpp
   ConstraintSystem.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DependenceGraphBuilder.cpp
   DevelopmentModeInlineAdvisor.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp

llvm/lib/Analysis/CallPrinter.cpp

struct DOTGraphTraits<CallGraphDOTInfo *> : public DefaultDOTGraphTraits {
 
   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   static std::string getGraphName(CallGraphDOTInfo *CGInfo) {
     return "Call graph: " +
            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;
   }
 
   std::string getNodeLabel(const CallGraphNode *Node,
                            CallGraphDOTInfo *CGInfo) {
     if (Node == CGInfo->getCallGraph()->getExternalCallingNode())

llvm/lib/Analysis/DDGPrinter.cpp

+//===- 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();
+}

llvm/lib/CodeGen/MachineScheduler.cpp

struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits {
   static std::string getGraphName(const ScheduleDAG *G) {
     return std::string(G->MF.getName());
   }
 
   static bool renderGraphFromBottomUp() {
     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
          || Node->Succs.size() > ViewMISchedCutoff);
   }
 
   /// If you want to override the dot attributes printed for a particular
   /// edge, override this method.

llvm/lib/CodeGen/ScheduleDAGPrinter.cpp

DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
     static std::string getGraphName(const ScheduleDAG *G) {
       return std::string(G->MF.getName());
     }
 
     static bool renderGraphFromBottomUp() {
       return true;
     }
 
-    static bool isNodeHidden(const SUnit *Node) {
+    static bool isNodeHidden(const SUnit *Node, const ScheduleDAG *G) {
       return (Node->NumPreds > 10 || Node->NumSuccs > 10);
     }
 
     static std::string getNodeIdentifierLabel(const SUnit *Node,
                                               const ScheduleDAG *Graph) {
       std::string R;
       raw_string_ostream OS(R);
       OS << static_cast<const void *>(Node);

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #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"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IRSimilarityIdentifier.h"
 #include "llvm/Analysis/IVUsers.h"

llvm/lib/Passes/PassRegistry.def

 LOOP_ANALYSIS("iv-users", IVUsersAnalysis())
 LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))
 #undef LOOP_ANALYSIS
 
 #ifndef LOOP_PASS
 #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())
 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("loop-interchange", LoopInterchangePass())
 LOOP_PASS("loop-rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))