Index: llvm/include/llvm/Analysis/DDG.h =================================================================== --- llvm/include/llvm/Analysis/DDG.h +++ llvm/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 regions 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: @@ -182,14 +201,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 +224,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 region of + // the graph, to ensure all nodes are reachable in a graph walk. + NodeType *Root = nullptr; }; using DDGInfo = DependenceGraphInfo; @@ -217,6 +247,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 +266,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."); @@ -317,7 +359,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 +401,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/include/llvm/Analysis/DependenceGraphBuilder.h =================================================================== --- llvm/include/llvm/Analysis/DependenceGraphBuilder.h +++ llvm/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; Index: llvm/lib/Analysis/DDG.cpp =================================================================== --- llvm/lib/Analysis/DDG.cpp +++ llvm/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"); @@ -153,6 +156,17 @@ } } +bool DataDependenceGraph::addNode(DDGNode &N) { + if (!DDGBase::addNode(N)) + return false; + + if (isa(&N)) { + assert(!Root && "Adding more than one root node."); + Root = &N; + } + return true; +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) { for (auto *Node : G) OS << *Node << "\n"; Index: llvm/lib/Analysis/DependenceGraphBuilder.cpp =================================================================== --- llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -46,6 +46,22 @@ } } +template +void AbstractDependenceGraphBuilder::createAndConnectRootNode() { + // Create a root node that connects to every connected region of the graph. + // This is done to allow the SCC iterator to iterate over nodes that + // may not be reachable from an arbitrary node in the graph. + 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) + createDefUseEdge(RootNode, *N); + } +} + template void AbstractDependenceGraphBuilder::createDefUseEdges() { for (NodeType *N : Graph) { InstructionListType SrcIList; Index: llvm/test/Analysis/DDG/root-node.ll =================================================================== --- /dev/null +++ llvm/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: [def-use] to [[N1]] +; CHECK-NEXT: [def-use] to [[N2]] + + +;; // Two separate regions in the graph. Root node must link to both regions. +;; 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 +}