diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h --- a/llvm/include/llvm/Analysis/DDG.h +++ b/llvm/include/llvm/Analysis/DDG.h @@ -300,6 +300,7 @@ /// Data Dependency Graph class DataDependenceGraph : public DDGBase, public DDGInfo { + friend AbstractDependenceGraphBuilder; friend class DDGBuilder; public: @@ -311,7 +312,7 @@ DataDependenceGraph(DataDependenceGraph &&G) : DDGBase(std::move(G)), DDGInfo(std::move(G)) {} DataDependenceGraph(Function &F, DependenceInfo &DI); - DataDependenceGraph(const Loop &L, DependenceInfo &DI); + DataDependenceGraph(Loop &L, LoopInfo &LI, DependenceInfo &DI); ~DataDependenceGraph(); /// If node \p N belongs to a pi-block return a pointer to the pi-block, @@ -381,6 +382,12 @@ return *E; } + const NodeListType &getNodesInPiBlock(const DDGNode &N) final override { + auto *PiNode = dyn_cast(&N); + assert(PiNode && "Expected a pi-block node."); + return PiNode->getNodes(); + } + bool shouldCreatePiBlocks() const final override; }; diff --git a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h --- a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h +++ b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h @@ -59,6 +59,7 @@ createMemoryDependencyEdges(); createAndConnectRootNode(); createPiBlocks(); + sortNodesTopologically(); } /// Create fine grained nodes. These are typically atomic nodes that @@ -84,6 +85,9 @@ /// the dependence graph into an acyclic graph. void createPiBlocks(); + /// Topologically sort the graph nodes. + void sortNodesTopologically(); + protected: /// Create the root node of the graph. virtual NodeType &createRootNode() = 0; @@ -104,6 +108,10 @@ /// Create a rooted edge going from \p Src to \p Tgt . virtual EdgeType &createRootedEdge(NodeType &Src, NodeType &Tgt) = 0; + /// Given a pi-block node, return a vector of all the nodes contained within + /// it. + virtual const NodeListType &getNodesInPiBlock(const NodeType &N) = 0; + /// Deallocate memory of edge \p E. virtual void destroyEdge(EdgeType &E) { delete &E; } diff --git a/llvm/lib/Analysis/DDG.cpp b/llvm/lib/Analysis/DDG.cpp --- a/llvm/lib/Analysis/DDG.cpp +++ b/llvm/lib/Analysis/DDG.cpp @@ -9,7 +9,9 @@ // The implementation for the data dependence graph. //===----------------------------------------------------------------------===// #include "llvm/Analysis/DDG.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Support/CommandLine.h" using namespace llvm; @@ -179,19 +181,28 @@ DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D) : DependenceGraphInfo(F.getName().str(), D) { + // Put the basic blocks in program order for correct dependence + // directions. BasicBlockListType BBList; - for (auto &BB : F.getBasicBlockList()) - BBList.push_back(&BB); + for (auto &SCC : make_range(scc_begin(&F), scc_end(&F))) + for (BasicBlock * BB : SCC) + BBList.push_back(BB); + std::reverse(BBList.begin(), BBList.end()); DDGBuilder(*this, D, BBList).populate(); } -DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D) +DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI, + DependenceInfo &D) : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." + L.getHeader()->getName()) .str(), D) { + // Put the basic blocks in program order for correct dependence + // directions. + LoopBlocksDFS DFS(&L); + DFS.perform(&LI); BasicBlockListType BBList; - for (BasicBlock *BB : L.blocks()) + for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO())) BBList.push_back(BB); DDGBuilder(*this, D, BBList).populate(); } @@ -259,7 +270,7 @@ LoopStandardAnalysisResults &AR) { Function *F = L.getHeader()->getParent(); DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI); - return std::make_unique(L, DI); + return std::make_unique(L, AR.LI, DI); } AnalysisKey DDGAnalysis::Key; diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp --- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -353,5 +353,34 @@ } } +template +void AbstractDependenceGraphBuilder::sortNodesTopologically() { + + // If we don't create pi-blocks, then we may not have a DAG. + if (!shouldCreatePiBlocks()) + return; + + SmallVector NodesInPO; + using NodeKind = typename NodeType::NodeKind; + for (NodeType *N : post_order(&Graph)) { + if (N->getKind() == NodeKind::PiBlock) { + // Put members of the pi-block right after the pi-block itself, for + // convenience. + const NodeListType &PiBlockMembers = getNodesInPiBlock(*N); + NodesInPO.insert(NodesInPO.end(), PiBlockMembers.begin(), + PiBlockMembers.end()); + } + NodesInPO.push_back(N); + } + + size_t OldSize = Graph.Nodes.size(); + Graph.Nodes.clear(); + for (NodeType *N : reverse(NodesInPO)) + Graph.Nodes.push_back(N); + if (Graph.Nodes.size() != OldSize) + assert(false && + "Expected the number of nodes to stay the same after the sort"); +} + template class llvm::AbstractDependenceGraphBuilder; template class llvm::DependenceGraphInfo; diff --git a/llvm/test/Analysis/DDG/basic-a.ll b/llvm/test/Analysis/DDG/basic-a.ll --- a/llvm/test/Analysis/DDG/basic-a.ll +++ b/llvm/test/Analysis/DDG/basic-a.ll @@ -1,7 +1,44 @@ ; 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: Node Address:[[PI:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT: --- start of nodes in pi-block --- +; CHECK-NEXT: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %inc = add i64 %i.02, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N11]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ] +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N10]] +; CHECK-NEXT: --- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N1:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N7]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %exitcond = icmp ne i64 %inc, %n +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N8]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: br i1 %exitcond, label %test1.for.body, label %for.end.loopexit +; CHECK-NEXT: Edges:none! + +; CHECK: Node Address:[[N6]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N1]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: @@ -23,12 +60,6 @@ ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add = fadd float %0, %conv ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02 -; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N5]] ; CHECK: Node Address:[[N5]]:single-instruction @@ -36,36 +67,6 @@ ; CHECK-NEXT: store float %add, float* %arrayidx1, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %exitcond = icmp ne i64 %inc, %n -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N8]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %exitcond, label %test1.for.body, label %for.end.loopexit -; CHECK-NEXT: Edges:none! - -; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT: --- start of nodes in pi-block --- -; CHECK-NEXT: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N11]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 0, %test1.for.body.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N10]] -; CHECK-NEXT: --- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N1]] -; CHECK-NEXT: [def-use] to [[N6]] -; CHECK-NEXT: [def-use] to [[N7]] - ;; No memory dependencies. ;; void test1(unsigned long n, float * restrict a, float * restrict b) { @@ -96,78 +97,80 @@ ; CHECK-LABEL: 'DDG' for loop 'test2.for.body': -; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[PI:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT: --- start of nodes in pi-block --- +; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 +; CHECK-NEXT: %inc = add i64 %i.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N12]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ] ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N11]] +; CHECK-NEXT: --- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N1:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N5]]:single-instruction +; CHECK: Node Address:[[N8]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %1 = load float, float* %arrayidx1, align 4 +; CHECK-NEXT: %exitcond = icmp ne i64 %inc, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N3]] -; CHECK-NEXT: [memory] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N9]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %add = fadd float %0, %1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6]] +; CHECK-NEXT: br i1 %exitcond, label %test2.for.body, label %for.end.loopexit +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, float* %a, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: store float %add, float* %arrayidx2, align 4 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %arrayidx1 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %exitcond = icmp ne i64 %inc, %n +; CHECK-NEXT: %1 = load float, float* %arrayidx1, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] +; CHECK-NEXT: [memory] to [[N6]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N1]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %exitcond, label %test2.for.body, label %for.end.loopexit -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT: --- start of nodes in pi-block --- -; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 +; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N12]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test2.for.body ], [ 0, %test2.for.body.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N11]] -; CHECK-NEXT: --- end of nodes in pi-block --- +; CHECK-NEXT: %add = fadd float %0, %1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N1]] -; CHECK-NEXT: [def-use] to [[N4]] -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [def-use] to [[N8]] +; CHECK-NEXT: [def-use] to [[N6]] + +; CHECK: Node Address:[[N6]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: store float %add, float* %arrayidx2, align 4 +; CHECK-NEXT: Edges:none! + ;; Loop-independent memory dependencies. diff --git a/llvm/test/Analysis/DDG/basic-b.ll b/llvm/test/Analysis/DDG/basic-b.ll --- a/llvm/test/Analysis/DDG/basic-b.ll +++ b/llvm/test/Analysis/DDG/basic-b.ll @@ -1,19 +1,45 @@ ; 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: Node Address:[[N9:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 +; CHECK-NEXT: %inc = add i64 %i.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[N14]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 +; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ] +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N13]] +; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N1:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N7]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N8]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit +; CHECK-NEXT: Edges:none! + +; CHECK: Node Address:[[N6]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 ; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %sub1 = add i64 %i.02, -1 ; CHECK-NEXT: Edges: @@ -25,22 +51,17 @@ ; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N1]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N3]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub +; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N8]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: [def-use] to [[N3]] ; CHECK: Node Address:[[N3]]:pi-block ; CHECK-NEXT: --- start of nodes in pi-block --- @@ -64,25 +85,6 @@ ; CHECK-NEXT:--- end of nodes in pi-block --- ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N14]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N13]] -; CHECK-NEXT:--- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N1]] -; CHECK-NEXT: [def-use] to [[N4]] -; CHECK-NEXT: [def-use] to [[N6]] -; CHECK-NEXT: [def-use] to [[N7]] ;; Loop-carried dependence requiring edge-reversal to expose a cycle @@ -117,19 +119,45 @@ } ; CHECK-LABEL: 'DDG' for loop 'test2.for.body': -; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction + +; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 +; CHECK-NEXT: %inc = add i64 %i.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[N13]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 +; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ] ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12]] +; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N1:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N9]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N10]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: br i1 %cmp, label %test2.for.body, label %for.end.loopexit +; CHECK-NEXT: Edges:none! + +; CHECK: Node Address:[[N8]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add1 = add i64 %i.02, 1 ; CHECK-NEXT: Edges: @@ -145,57 +173,33 @@ ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %1 = load float, float* %arrayidx2, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N3]] -; CHECK-NEXT: [memory] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] +; CHECK-NEXT: [memory] to [[N7]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N1]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %add = fadd float %0, %1 +; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] +; CHECK-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N7]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: store float %add, float* %arrayidx3, align 4 -; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub +; CHECK-NEXT: %add = fadd float %0, %1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N10]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp, label %test2.for.body, label %for.end.loopexit +; CHECK-NEXT: store float %add, float* %arrayidx3, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N11:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N13]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test2.for.body ], [ 1, %test2.for.body.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12]] -; CHECK-NEXT:--- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N1]] -; CHECK-NEXT: [def-use] to [[N4]] -; CHECK-NEXT: [def-use] to [[N8]] -; CHECK-NEXT: [def-use] to [[N9]] - ;; Forward loop-carried dependence *not* causing a cycle. ;; void test2(unsigned long n, float * restrict a, float * restrict b) { diff --git a/llvm/test/Analysis/DDG/basic-loopnest.ll b/llvm/test/Analysis/DDG/basic-loopnest.ll --- a/llvm/test/Analysis/DDG/basic-loopnest.ll +++ b/llvm/test/Analysis/DDG/basic-loopnest.ll @@ -2,73 +2,65 @@ ; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader': -; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %sub = add i64 %n, -1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N29:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub +; CHECK-NEXT: %inc = add i64 %j.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N4]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: [def-use] to [[N30:0x[0-9a-f]*]] -; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N30]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n +; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ] ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N6]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 +; CHECK-NEXT: [def-use] to [[N29]] +; CHECK-NEXT:--- end of nodes in pi-block --- ; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N13]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 +; CHECK-NEXT: %sub7 = add i64 %j.02, -1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N26:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4 +; CHECK-NEXT: %inc13 = add i64 %i.04, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]] -; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N27]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n +; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ] ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N11]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 +; CHECK-NEXT: [def-use] to [[N26]] +; CHECK-NEXT:--- end of nodes in pi-block --- ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] -; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N18]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %sub7 = add i64 %j.02, -1 +; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12]] +; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] -; CHECK: Node Address:[[N12]]:single-instruction +; CHECK: Node Address:[[N19]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9]] +; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N14:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N14]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: @@ -78,45 +70,55 @@ ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N16]] ; CHECK: Node Address:[[N16]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[N10]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub +; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] -; CHECK: Node Address:[[N17]]:single-instruction +; CHECK: Node Address:[[N11]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N12]] -; CHECK: Node Address:[[N18:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N12]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n +; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9]] -; CHECK: Node Address:[[N19]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br label %for.body4 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N21:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br label %for.inc12 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N8]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N9]] ; CHECK: Node Address:[[N9]]:pi-block ; CHECK-NEXT:--- start of nodes in pi-block --- @@ -140,46 +142,44 @@ ; CHECK-NEXT:--- end of nodes in pi-block --- ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N26:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N21:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc13 = add i64 %i.04, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]] +; CHECK-NEXT: br label %for.inc12 +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N27]]:single-instruction +; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test1.for.cond1.preheader.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N26]] -; CHECK-NEXT:--- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N5]] -; CHECK-NEXT: [def-use] to [[N10]] -; CHECK-NEXT: [def-use] to [[N14]] -; CHECK-NEXT: [def-use] to [[N18]] +; CHECK-NEXT: br label %for.body4 +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N29:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %j.02, 1 +; CHECK-NEXT: %sub = add i64 %n, -1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N30:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N2]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N30]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ] +; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N29]] -; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N4]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 +; CHECK-NEXT: Edges:none! + +; CHECK: Node Address:[[N2]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [def-use] to [[N13]] -; CHECK-NEXT: [def-use] to [[N16]] -; CHECK-NEXT: [def-use] to [[N2]] +; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] +; CHECK: Node Address:[[N17]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit +; CHECK-NEXT: Edges:none! ;; This test has a cycle. @@ -232,49 +232,83 @@ ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader': -; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction + +; CHECK: Node Address:[[PI1:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %sub = add i64 %n, -1 +; CHECK-NEXT: %inc = add i64 %j.02, 1 ; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N29:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N29]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ] +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N28]] +; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] ; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N13]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub +; CHECK-NEXT: %add7 = add i64 %j.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %inc13 = add i64 %i.04, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]] -; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N26]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n +; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ] ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N25]] +; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N20]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 +; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N21]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 +; CHECK-NEXT: br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit +; CHECK-NEXT: Edges:none! + +; CHECK: Node Address:[[N16]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N17]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4 +; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N18]] -; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N18]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N10]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: @@ -284,12 +318,6 @@ ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %add7 = add i64 %j.02, 1 -; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N12]] ; CHECK: Node Address:[[N12]]:single-instruction @@ -302,58 +330,47 @@ ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9]] -; CHECK-NEXT: [memory] to [[N15:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [memory] to [[N15]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %add = fadd float %1, %3 +; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N15]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N16:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n +; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N17]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 +; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N18]]:single-instruction +; CHECK: Node Address:[[N8]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02 +; CHECK-NEXT: %1 = load float, float* %arrayidx5, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N15]] - -; CHECK: Node Address:[[N15]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: store float %add, float* %arrayidx11, align 4 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: [def-use] to [[N9]] -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[N9]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub +; CHECK-NEXT: %add = fadd float %1, %3 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N15]] -; CHECK: Node Address:[[N19]]:single-instruction +; CHECK: Node Address:[[N15]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit +; CHECK-NEXT: store float %add, float* %arrayidx11, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N21]]:single-instruction +; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit +; CHECK-NEXT: br label %for.inc12 ; CHECK-NEXT: Edges:none! ; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction @@ -361,50 +378,34 @@ ; CHECK-NEXT: br label %for.body4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br label %for.inc12 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %sub = add i64 %n, -1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N2]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc13 = add i64 %i.04, 1 +; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; CHECK: Node Address:[[N26]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N25]] -; CHECK-NEXT:--- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N5]] -; CHECK-NEXT: [def-use] to [[N10]] -; CHECK-NEXT: [def-use] to [[N16]] -; CHECK-NEXT: [def-use] to [[N20]] +; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N27:0x[0-9a-f]*]]:pi-block -; CHECK-NEXT:--- start of nodes in pi-block --- -; CHECK: Node Address:[[N28:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %j.02, 1 +; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N29:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] -; CHECK: Node Address:[[N29]]:single-instruction +; CHECK: Node Address:[[N19]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %j.02 = phi i64 [ %inc, %for.body4 ], [ 1, %for.body4.preheader ] -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N28]] -; CHECK-NEXT:--- end of nodes in pi-block --- -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [def-use] to [[N13]] -; CHECK-NEXT: [def-use] to [[N18]] -; CHECK-NEXT: [def-use] to [[N2]] +; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit +; CHECK-NEXT: Edges:none! ;; This test has no cycles. diff --git a/llvm/test/Analysis/DDG/root-node.ll b/llvm/test/Analysis/DDG/root-node.ll --- a/llvm/test/Analysis/DDG/root-node.ll +++ b/llvm/test/Analysis/DDG/root-node.ll @@ -7,12 +7,11 @@ ; CHECK-NEXT: [rooted] to [[N1:0x[0-9a-f]*]] ; CHECK-NEXT: [rooted] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N1]]:pi-block -; CHECK: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ] - ; CHECK: Node Address:[[N2]]:pi-block ; CHECK: %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ] +; CHECK: Node Address:[[N1]]:pi-block +; CHECK: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ] ;; // Two separate components in the graph. Root node must link to both. ;; void test1(unsigned long n, float * restrict a, float * restrict b) {