summaryrefslogtreecommitdiffstats
path: root/llvm
diff options
context:
space:
mode:
Diffstat (limited to 'llvm')
-rw-r--r--llvm/include/llvm/Analysis/DDG.h9
-rw-r--r--llvm/include/llvm/Analysis/DependenceGraphBuilder.h8
-rw-r--r--llvm/lib/Analysis/DDG.cpp21
-rw-r--r--llvm/lib/Analysis/DependenceGraphBuilder.cpp29
-rw-r--r--llvm/test/Analysis/DDG/basic-a.ll165
-rw-r--r--llvm/test/Analysis/DDG/basic-b.ll164
-rw-r--r--llvm/test/Analysis/DDG/basic-loopnest.ll371
-rw-r--r--llvm/test/Analysis/DDG/root-node.ll5
8 files changed, 417 insertions, 355 deletions
diff --git a/llvm/include/llvm/Analysis/DDG.h b/llvm/include/llvm/Analysis/DDG.h
index 7a572afccd6..22df60efd84 100644
--- a/llvm/include/llvm/Analysis/DDG.h
+++ b/llvm/include/llvm/Analysis/DDG.h
@@ -300,6 +300,7 @@ using DDGInfo = DependenceGraphInfo<DDGNode>;
/// Data Dependency Graph
class DataDependenceGraph : public DDGBase, public DDGInfo {
+ friend AbstractDependenceGraphBuilder<DataDependenceGraph>;
friend class DDGBuilder;
public:
@@ -311,7 +312,7 @@ public:
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 @@ public:
return *E;
}
+ const NodeListType &getNodesInPiBlock(const DDGNode &N) final override {
+ auto *PiNode = dyn_cast<const PiBlockDDGNode>(&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
index 876ccbc5c9a..99465ef39a0 100644
--- a/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
+++ b/llvm/include/llvm/Analysis/DependenceGraphBuilder.h
@@ -59,6 +59,7 @@ public:
createMemoryDependencyEdges();
createAndConnectRootNode();
createPiBlocks();
+ sortNodesTopologically();
}
/// Create fine grained nodes. These are typically atomic nodes that
@@ -84,6 +85,9 @@ public:
/// 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 @@ protected:
/// 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
index 82ccea06f28..90ce13e6f65 100644
--- 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 @@ using BasicBlockListType = SmallVector<BasicBlock *, 8>;
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 @@ DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR) {
Function *F = L.getHeader()->getParent();
DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
- return std::make_unique<DataDependenceGraph>(L, DI);
+ return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
}
AnalysisKey DDGAnalysis::Key;
diff --git a/llvm/lib/Analysis/DependenceGraphBuilder.cpp b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
index 115f5d6e814..98bb09d792b 100644
--- a/llvm/lib/Analysis/DependenceGraphBuilder.cpp
+++ b/llvm/lib/Analysis/DependenceGraphBuilder.cpp
@@ -353,5 +353,34 @@ void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() {
}
}
+template <class G>
+void AbstractDependenceGraphBuilder<G>::sortNodesTopologically() {
+
+ // If we don't create pi-blocks, then we may not have a DAG.
+ if (!shouldCreatePiBlocks())
+ return;
+
+ SmallVector<NodeType *, 64> 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<DataDependenceGraph>;
template class llvm::DependenceGraphInfo<DDGNode>;
diff --git a/llvm/test/Analysis/DDG/basic-a.ll b/llvm/test/Analysis/DDG/basic-a.ll
index 920e71f6717..a52e8c258f5 100644
--- 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<ddg>" 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 @@ for.end: ; preds = %test1.for.body, %en
; 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
index f83f7fe92f3..757c706193a 100644
--- 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<ddg>" 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 @@ for.end: ; preds = %test1.for.body, %en
}
; 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 @@ for.end: ; preds = %test1.for.body, %en
; 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
index aded488ef23..41c2cbbdc7a 100644
--- 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 @@ for.end14: ; preds = %for.inc12, %entry
; 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 @@ for.end14: ; preds = %for.inc12, %entry
; 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 @@ for.end14: ; preds = %for.inc12, %entry
; 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 @@ for.end14: ; preds = %for.inc12, %entry
; 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
index 34d6437ef9c..868fb72d452 100644
--- 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) {
OpenPOWER on IntegriCloud