Index: llvm/trunk/include/llvm/Analysis/DDG.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DDG.h +++ llvm/trunk/include/llvm/Analysis/DDG.h @@ -33,6 +33,8 @@ /// 1. Single instruction node containing just one instruction. /// 2. Multiple instruction node where two or more instructions from /// the same basic block are merged into one node. +/// 3. Root node is a special node that connects to all components such that +/// there is always a path from it to any node in the graph. class DDGNode : public DDGNodeBase { public: using InstructionListType = SmallVectorImpl; @@ -41,6 +43,7 @@ Unknown, SingleInstruction, MultiInstruction, + Root, }; DDGNode() = delete; @@ -78,6 +81,22 @@ NodeKind Kind; }; +/// Subclass of DDGNode representing the root node of the graph. +/// There should only be one such node in a given graph. +class RootDDGNode : public DDGNode { +public: + RootDDGNode() : DDGNode(NodeKind::Root) {} + RootDDGNode(const RootDDGNode &N) = delete; + RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {} + ~RootDDGNode() {} + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const DDGNode *N) { + return N->getKind() == NodeKind::Root; + } + static bool classof(const RootDDGNode *N) { return true; } +}; + /// Subclass of DDGNode representing single or multi-instruction nodes. class SimpleDDGNode : public DDGNode { public: @@ -139,10 +158,12 @@ /// Data Dependency Graph Edge. /// An edge in the DDG can represent a def-use relationship or /// a memory dependence based on the result of DependenceAnalysis. +/// A rooted edge connects the root node to one of the components +/// of the graph. class DDGEdge : public DDGEdgeBase { public: /// The kind of edge in the DDG - enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence }; + enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted }; explicit DDGEdge(DDGNode &N) = delete; DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {} @@ -169,6 +190,10 @@ /// Return true if this is a memory dependence edge, and false otherwise. bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; } + /// Return true if this is an edge stemming from the root node, and false + /// otherwise. + bool isRooted() const { return Kind == EdgeKind::Rooted; } + private: EdgeKind Kind; }; @@ -182,14 +207,21 @@ DependenceGraphInfo() = delete; DependenceGraphInfo(const DependenceGraphInfo &G) = delete; DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo) - : Name(N), DI(DepInfo) {} + : Name(N), DI(DepInfo), Root(nullptr) {} DependenceGraphInfo(DependenceGraphInfo &&G) - : Name(std::move(G.Name)), DI(std::move(G.DI)) {} + : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {} virtual ~DependenceGraphInfo() {} /// Return the label that is used to name this graph. const StringRef getName() const { return Name; } + /// Return the root node of the graph. + NodeType &getRoot() const { + assert(Root && "Root node is not available yet. Graph construction may " + "still be in progress\n"); + return *Root; + } + protected: // Name of the graph. std::string Name; @@ -198,6 +230,10 @@ // dependencies don't need to be stored. Instead when the dependence is // queried it is recomputed using @DI. const DependenceInfo DI; + + // A special node in the graph that has an edge to every connected component of + // the graph, to ensure all nodes are reachable in a graph walk. + NodeType *Root = nullptr; }; using DDGInfo = DependenceGraphInfo; @@ -217,6 +253,12 @@ DataDependenceGraph(Function &F, DependenceInfo &DI); DataDependenceGraph(const Loop &L, DependenceInfo &DI); ~DataDependenceGraph(); + +protected: + /// Add node \p N to the graph, if it's not added yet, and keep track of + /// the root node. Return true if node is successfully added. + bool addNode(NodeType &N); + }; /// Concrete implementation of a pure data dependence graph builder. This class @@ -230,6 +272,12 @@ DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs) : AbstractDependenceGraphBuilder(G, D, BBs) {} + DDGNode &createRootNode() final override { + auto *RN = new RootDDGNode(); + assert(RN && "Failed to allocate memory for DDG root node."); + Graph.addNode(*RN); + return *RN; + } DDGNode &createFineGrainedNode(Instruction &I) final override { auto *SN = new SimpleDDGNode(I); assert(SN && "Failed to allocate memory for simple DDG node."); @@ -248,6 +296,14 @@ Graph.connect(Src, Tgt, *E); return *E; } + DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override { + auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted); + assert(E && "Failed to allocate memory for edge"); + assert(isa(Src) && "Expected root node"); + Graph.connect(Src, Tgt, *E); + return *E; + } + }; raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N); @@ -317,7 +373,9 @@ template <> struct GraphTraits : public GraphTraits { using nodes_iterator = DataDependenceGraph::iterator; - static NodeRef getEntryNode(DataDependenceGraph *DG) { return *DG->begin(); } + static NodeRef getEntryNode(DataDependenceGraph *DG) { + return &DG->getRoot(); + } static nodes_iterator nodes_begin(DataDependenceGraph *DG) { return DG->begin(); } @@ -357,7 +415,7 @@ : public GraphTraits { using nodes_iterator = DataDependenceGraph::const_iterator; static NodeRef getEntryNode(const DataDependenceGraph *DG) { - return *DG->begin(); + return &DG->getRoot(); } static nodes_iterator nodes_begin(const DataDependenceGraph *DG) { return DG->begin(); Index: llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h +++ llvm/trunk/include/llvm/Analysis/DependenceGraphBuilder.h @@ -55,6 +55,7 @@ createFineGrainedNodes(); createDefUseEdges(); createMemoryDependencyEdges(); + createAndConnectRootNode(); } /// Create fine grained nodes. These are typically atomic nodes that @@ -69,7 +70,14 @@ /// in the graph nodes and create edges between them. void createMemoryDependencyEdges(); + /// Create a root node and add edges such that each node in the graph is + /// reachable from the root. + void createAndConnectRootNode(); + protected: + /// Create the root node of the graph. + virtual NodeType &createRootNode() = 0; + /// Create an atomic node in the graph given a single instruction. virtual NodeType &createFineGrainedNode(Instruction &I) = 0; @@ -79,6 +87,9 @@ /// Create a memory dependence edge going from \p Src to \p Tgt. virtual EdgeType &createMemoryEdge(NodeType &Src, NodeType &Tgt) = 0; + /// Create a rooted edge going from \p Src to \p Tgt . + virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0; + /// Deallocate memory of edge \p E. virtual void destroyEdge(EdgeType &E) { delete &E; } Index: llvm/trunk/lib/Analysis/DDG.cpp =================================================================== --- llvm/trunk/lib/Analysis/DDG.cpp +++ llvm/trunk/lib/Analysis/DDG.cpp @@ -46,6 +46,9 @@ case DDGNode::NodeKind::MultiInstruction: Out = "multi-instruction"; break; + case DDGNode::NodeKind::Root: + Out = "root"; + break; case DDGNode::NodeKind::Unknown: Out = "??"; break; @@ -60,7 +63,7 @@ OS << " Instructions:\n"; for (auto *I : cast(N).getInstructions()) OS.indent(2) << *I << "\n"; - } else + } else if (!isa(N)) llvm_unreachable("unimplemented type of node"); OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n"); @@ -108,6 +111,9 @@ case DDGEdge::EdgeKind::MemoryDependence: Out = "memory"; break; + case DDGEdge::EdgeKind::Rooted: + Out = "rooted"; + break; case DDGEdge::EdgeKind::Unknown: Out = "??"; break; @@ -153,6 +159,22 @@ } } +bool DataDependenceGraph::addNode(DDGNode &N) { + if (!DDGBase::addNode(N)) + return false; + + // In general, if the root node is already created and linked, it is not safe + // to add new nodes since they may be unreachable by the root. + // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an + // exception because they represent components that are already reachable by + // root. + assert(!Root && "Root node is already added. No more nodes can be added."); + if (isa(N)) + Root = &N; + + return true; +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) { for (auto *Node : G) OS << *Node << "\n"; Index: llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp =================================================================== --- llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp +++ llvm/trunk/lib/Analysis/DependenceGraphBuilder.cpp @@ -46,6 +46,34 @@ } } +template +void AbstractDependenceGraphBuilder::createAndConnectRootNode() { + // Create a root node that connects to every connected component of the graph. + // This is done to allow graph iterators to visit all the disjoint components + // of the graph, in a single walk. + // + // This algorithm works by going through each node of the graph and for each + // node N, do a DFS starting from N. A rooted edge is established between the + // root node and N (if N is not yet visited). All the nodes reachable from N + // are marked as visited and are skipped in the DFS of subsequent nodes. + // + // Note: This algorithm tries to limit the number of edges out of the root + // node to some extent, but there may be redundant edges created depending on + // the iteration order. For example for a graph {A -> B}, an edge from the + // root node is added to both nodes if B is visited before A. While it does + // not result in minimal number of edges, this approach saves compile-time + // while keeping the number of edges in check. + auto &RootNode = createRootNode(); + df_iterator_default_set Visited; + for (auto *N : Graph) { + if (*N == RootNode) + continue; + for (auto I : depth_first_ext(N, Visited)) + if (I == N) + createRootedEdge(RootNode, *N); + } +} + template void AbstractDependenceGraphBuilder::createDefUseEdges() { for (NodeType *N : Graph) { InstructionListType SrcIList; Index: llvm/trunk/test/Analysis/DDG/root-node.ll =================================================================== --- llvm/trunk/test/Analysis/DDG/root-node.ll +++ llvm/trunk/test/Analysis/DDG/root-node.ll @@ -0,0 +1,52 @@ +; RUN: opt < %s -disable-output "-passes=print" 2>&1 | FileCheck %s + +; CHECK-LABEL: 'DDG' for loop 'test1.for.body': + +; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ] + +; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ] + +; CHECK: Node Address:[[ROOT:0x[0-9a-f]*]]:root +; CHECK-NEXT: Edges: +; CHECK-NEXT: [rooted] to [[N1]] +; CHECK-NEXT: [rooted] to [[N2]] + + +;; // Two separate components in the graph. Root node must link to both. +;; void test1(unsigned long n, float * restrict a, float * restrict b) { +;; for (unsigned long i1 = 0, i2 = 0; i1 < n; i1++, i2++) { +;; a[i1] = 1; +;; b[i2] = -1; +;; } +;; } + +define void @test1(i64 %n, float* noalias %a, float* noalias %b) { +entry: + %cmp1 = icmp ult i64 0, %n + br i1 %cmp1, label %for.body.lr.ph, label %for.end + +for.body.lr.ph: ; preds = %entry + br label %test1.for.body + +test1.for.body: ; preds = %for.body.lr.ph, %test1.for.body + %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ] + %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ] + %arrayidx = getelementptr inbounds float, float* %a, i64 %i1.02 + store float 1.000000e+00, float* %arrayidx, align 4 + %arrayidx1 = getelementptr inbounds float, float* %b, i64 %i2.03 + store float -1.000000e+00, float* %arrayidx1, align 4 + %inc = add i64 %i1.02, 1 + %inc2 = add i64 %i2.03, 1 + %cmp = icmp ult i64 %inc, %n + br i1 %cmp, label %test1.for.body, label %for.cond.for.end_crit_edge + +for.cond.for.end_crit_edge: ; preds = %test1.for.body + br label %for.end + +for.end: ; preds = %for.cond.for.end_crit_edge, %entry + ret void +}