Index: llvm/include/llvm/ADT/EnumeratedArray.h =================================================================== --- /dev/null +++ llvm/include/llvm/ADT/EnumeratedArray.h @@ -0,0 +1,48 @@ +//===- llvm/ADT/EnumeratedArray.h - Enumerated Array-------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines an array type that can be indexed using scoped enum values. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ENUMERATEDARRAY_H +#define LLVM_ADT_ENUMERATEDARRAY_H + +#include + +namespace llvm { + +template (LargestEnum)> +class EnumeratedArray { +public: + EnumeratedArray() = default; + EnumeratedArray(ValueType V) { + for (IndexType IX = 0; IX < Size; ++IX) { + Underlying[IX] = V; + } + } + inline const ValueType &operator[](const Enumeration Index) const { + auto IX = static_cast(Index); + assert(IX >= 0 && IX < Size && "Index is out of bounds."); + return Underlying[IX]; + } + inline ValueType &operator[](const Enumeration Index) { + return const_cast( + static_cast &>(*this)[Index]); + } + +private: + ValueType Underlying[Size]; +}; + +} // namespace llvm + +#endif // LLVM_ADT_ENUMERATEDARRAY_H Index: llvm/include/llvm/Analysis/DDG.h =================================================================== --- llvm/include/llvm/Analysis/DDG.h +++ llvm/include/llvm/Analysis/DDG.h @@ -13,12 +13,12 @@ #ifndef LLVM_ANALYSIS_DDG_H #define LLVM_ANALYSIS_DDG_H +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DirectedGraph.h" #include "llvm/Analysis/DependenceAnalysis.h" #include "llvm/Analysis/DependenceGraphBuilder.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/IR/Instructions.h" -#include namespace llvm { class DDGNode; @@ -33,7 +33,11 @@ /// 1. Single instruction node containing just one instruction. /// 2. Multiple instruction node where two or more instructions from /// the same basic block are merged into one node. -/// 3. Root node is a special node that connects to all components such that +/// 3. Pi-block node which is a group of other DDG nodes that are part of a +/// strongly-connected component of the graph. +/// A pi-block node contains more than one single or multiple instruction +/// nodes. The root node cannot be part of a pi-block. +/// 4. Root node is a special node that connects to all components such that /// there is always a path from it to any node in the graph. class DDGNode : public DDGNodeBase { public: @@ -43,6 +47,7 @@ Unknown, SingleInstruction, MultiInstruction, + PiBlock, Root, }; @@ -155,6 +160,55 @@ SmallVector InstList; }; +/// Subclass of DDGNode representing a pi-block. A pi-block represents a group +/// of DDG nodes that are part of a strongly-connected component of the graph. +/// Replacing all the SCCs with pi-blocks results in an acyclic representation +/// of the DDG. For example if we have: +/// {a -> b}, {b -> c, d}, {c -> a} +/// the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows: +/// {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a} +class PiBlockDDGNode : public DDGNode { +public: + using PiNodeList = SmallVector; + + PiBlockDDGNode() = delete; + PiBlockDDGNode(const PiNodeList &List); + PiBlockDDGNode(const PiBlockDDGNode &N); + PiBlockDDGNode(PiBlockDDGNode &&N); + ~PiBlockDDGNode(); + + PiBlockDDGNode &operator=(const PiBlockDDGNode &N) { + DDGNode::operator=(N); + NodeList = N.NodeList; + return *this; + } + + PiBlockDDGNode &operator=(PiBlockDDGNode &&N) { + DDGNode::operator=(std::move(N)); + NodeList = std::move(N.NodeList); + return *this; + } + + /// Get the list of nodes in this pi-block. + const PiNodeList &getNodes() const { + assert(!NodeList.empty() && "Node list is empty."); + return NodeList; + } + PiNodeList &getNodes() { + return const_cast( + static_cast(this)->getNodes()); + } + + /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. + static bool classof(const DDGNode *N) { + return N->getKind() == NodeKind::PiBlock; + } + +private: + /// List of nodes in this pi-block. + PiNodeList NodeList; +}; + /// Data Dependency Graph Edge. /// An edge in the DDG can represent a def-use relationship or /// a memory dependence based on the result of DependenceAnalysis. @@ -163,7 +217,13 @@ class DDGEdge : public DDGEdgeBase { public: /// The kind of edge in the DDG - enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted }; + enum class EdgeKind { + Unknown, + RegisterDefUse, + MemoryDependence, + Rooted, + Last = Rooted // Must be equal to the largest enum value. + }; explicit DDGEdge(DDGNode &N) = delete; DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {} @@ -254,11 +314,22 @@ DataDependenceGraph(const Loop &L, DependenceInfo &DI); ~DataDependenceGraph(); + /// If node \p N belongs to a pi-block return a pointer to the pi-block, + /// otherwise return null. + const PiBlockDDGNode *getPiBlock(const NodeType &N) const; + 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. + /// Add node \p N to the graph, if it's not added yet, and keep track of the + /// root node as well as pi-blocks and their members. Return true if node is + /// successfully added. bool addNode(NodeType &N); +private: + using PiBlockMapType = DenseMap; + + /// Mapping from graph nodes to their containing pi-blocks. If a node is not + /// part of a pi-block, it will not appear in this map. + PiBlockMapType PiBlockMap; }; /// Concrete implementation of a pure data dependence graph builder. This class @@ -284,6 +355,12 @@ Graph.addNode(*SN); return *SN; } + DDGNode &createPiBlock(const NodeListType &L) final override { + auto *Pi = new PiBlockDDGNode(L); + assert(Pi && "Failed to allocate memory for pi-block node."); + Graph.addNode(*Pi); + return *Pi; + } DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override { auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse); assert(E && "Failed to allocate memory for edge"); @@ -304,6 +381,7 @@ return *E; } + bool shouldCreatePiBlocks() const final override; }; raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N); Index: llvm/include/llvm/Analysis/DependenceGraphBuilder.h =================================================================== --- llvm/include/llvm/Analysis/DependenceGraphBuilder.h +++ llvm/include/llvm/Analysis/DependenceGraphBuilder.h @@ -44,7 +44,9 @@ /// The main entry to the graph construction algorithm. It starts by /// creating nodes in increasing order of granularity and then - /// adds def-use and memory edges. + /// adds def-use and memory edges. As one of the final stages, it + /// also creates pi-block nodes to facilitate codegen in transformations + /// that use dependence graphs. /// /// The algorithmic complexity of this implementation is O(V^2 * I^2), where V /// is the number of vertecies (nodes) and I is the number of instructions in @@ -56,6 +58,7 @@ createDefUseEdges(); createMemoryDependencyEdges(); createAndConnectRootNode(); + createPiBlocks(); } /// Create fine grained nodes. These are typically atomic nodes that @@ -74,6 +77,13 @@ /// reachable from the root. void createAndConnectRootNode(); + /// Apply graph abstraction to groups of nodes that belong to a strongly + /// connected component of the graph to create larger compound nodes + /// called pi-blocks. The purpose of this abstraction is to isolate sets of + /// program elements that need to stay together during codegen and turn + /// the dependence graph into an acyclic graph. + void createPiBlocks(); + protected: /// Create the root node of the graph. virtual NodeType &createRootNode() = 0; @@ -81,6 +91,10 @@ /// Create an atomic node in the graph given a single instruction. virtual NodeType &createFineGrainedNode(Instruction &I) = 0; + /// Create a pi-block node in the graph representing a group of nodes in an + /// SCC of the graph. + virtual NodeType &createPiBlock(const NodeListType &L) = 0; + /// Create a def-use edge going from \p Src to \p Tgt. virtual EdgeType &createDefUseEdge(NodeType &Src, NodeType &Tgt) = 0; @@ -96,6 +110,10 @@ /// Deallocate memory of node \p N. virtual void destroyNode(NodeType &N) { delete &N; } + /// Return true if creation of pi-blocks are supported and desired, + /// and false otherwise. + virtual bool shouldCreatePiBlocks() const { return true; } + /// Map types to map instructions to nodes used when populating the graph. using InstToNodeMap = DenseMap; Index: llvm/lib/Analysis/DDG.cpp =================================================================== --- llvm/lib/Analysis/DDG.cpp +++ llvm/lib/Analysis/DDG.cpp @@ -13,6 +13,10 @@ using namespace llvm; +static cl::opt + CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore, + cl::desc("Create pi-block nodes.")); + #define DEBUG_TYPE "ddg" template class llvm::DGEdge; @@ -29,9 +33,16 @@ InstructionListType &IList) const { assert(IList.empty() && "Expected the IList to be empty on entry."); if (isa(this)) { - for (auto *I : cast(this)->getInstructions()) + for (Instruction *I : cast(this)->getInstructions()) if (Pred(I)) IList.push_back(I); + } else if (isa(this)) { + for (const DDGNode *PN : cast(this)->getNodes()) { + assert(!isa(PN) && "Nested PiBlocks are not supported."); + SmallVector TmpIList; + PN->collectInstructions(Pred, TmpIList); + IList.insert(IList.end(), TmpIList.begin(), TmpIList.end()); + } } else llvm_unreachable("unimplemented type of node"); return !IList.empty(); @@ -46,11 +57,14 @@ case DDGNode::NodeKind::MultiInstruction: Out = "multi-instruction"; break; + case DDGNode::NodeKind::PiBlock: + Out = "pi-block"; + break; case DDGNode::NodeKind::Root: Out = "root"; break; case DDGNode::NodeKind::Unknown: - Out = "??"; + Out = "?? (error)"; break; } OS << Out; @@ -61,8 +75,15 @@ OS << "Node Address:" << &N << ":" << N.getKind() << "\n"; if (isa(N)) { OS << " Instructions:\n"; - for (auto *I : cast(N).getInstructions()) + for (const Instruction *I : cast(N).getInstructions()) OS.indent(2) << *I << "\n"; + } else if (isa(&N)) { + OS << "--- start of nodes in pi-block ---\n"; + auto &Nodes = cast(&N)->getNodes(); + unsigned Count = 0; + for (const DDGNode *N : Nodes) + OS << *N << (++Count == Nodes.size() ? "" : "\n"); + OS << "--- end of nodes in pi-block ---\n"; } else if (!isa(N)) llvm_unreachable("unimplemented type of node"); @@ -98,6 +119,29 @@ SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); } +//===--------------------------------------------------------------------===// +// PiBlockDDGNode implementation +//===--------------------------------------------------------------------===// + +PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List) + : DDGNode(NodeKind::PiBlock), NodeList(List) { + assert(!NodeList.empty() && "pi-block node constructed with an empty list."); +} + +PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N) + : DDGNode(N), NodeList(N.NodeList) { + assert(getKind() == NodeKind::PiBlock && !NodeList.empty() && + "constructing from invalid pi-block node."); +} + +PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N) + : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) { + assert(getKind() == NodeKind::PiBlock && !NodeList.empty() && + "constructing from invalid pi-block node."); +} + +PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); } + //===--------------------------------------------------------------------===// // DDGEdge implementation //===--------------------------------------------------------------------===// @@ -115,7 +159,7 @@ Out = "rooted"; break; case DDGEdge::EdgeKind::Unknown: - Out = "??"; + Out = "?? (error)"; break; } OS << Out; @@ -164,23 +208,46 @@ return false; // In general, if the root node is already created and linked, it is not safe - // to add new nodes since they may be unreachable by the root. - // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an - // exception because they represent components that are already reachable by - // root. - assert(!Root && "Root node is already added. No more nodes can be added."); + // to add new nodes since they may be unreachable by the root. However, + // pi-block nodes need to be added after the root node is linked, and they are + // always reachable by the root, because they represent components that are + // already reachable by root. + auto *Pi = dyn_cast(&N); + assert(!Root || Pi && "Root node is already added. No more nodes can be added."); + if (isa(N)) Root = &N; + if (Pi) + for (DDGNode *NI : Pi->getNodes()) + PiBlockMap.insert(std::make_pair(NI, Pi)); + return true; } +const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const { + if (PiBlockMap.find(&N) == PiBlockMap.end()) + return nullptr; + auto *Pi = PiBlockMap.find(&N)->second; + assert(PiBlockMap.find(Pi) == PiBlockMap.end() && + "Nested pi-blocks detected."); + return Pi; +} + raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) { - for (auto *Node : G) - OS << *Node << "\n"; + for (DDGNode *Node : G) + // Avoid printing nodes that are part of a pi-block twice. They will get + // printed when the pi-block is printed. + if (!G.getPiBlock(*Node)) + OS << *Node << "\n"; + OS << "\n"; return OS; } +bool DDGBuilder::shouldCreatePiBlocks() const { + return CreatePiBlocks; +} + //===--------------------------------------------------------------------===// // DDG Analysis Passes //===--------------------------------------------------------------------===// Index: llvm/lib/Analysis/DependenceGraphBuilder.cpp =================================================================== --- llvm/lib/Analysis/DependenceGraphBuilder.cpp +++ llvm/lib/Analysis/DependenceGraphBuilder.cpp @@ -10,6 +10,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/DependenceGraphBuilder.h" +#include "llvm/ADT/EnumeratedArray.h" #include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/DDG.h" @@ -22,6 +23,7 @@ STATISTIC(TotalDefUseEdges, "Number of def-use edges created."); STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created."); STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created."); +STATISTIC(TotalPiBlockNodes, "Number of pi-block nodes created."); STATISTIC(TotalConfusedEdges, "Number of confused memory dependencies between two nodes."); STATISTIC(TotalEdgeReversals, @@ -74,6 +76,133 @@ } } +template void AbstractDependenceGraphBuilder::createPiBlocks() { + if (!shouldCreatePiBlocks()) + return; + + LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n"); + + // The overall algorithm is as follows: + // 1. Identify SCCs and for each SCC create a pi-block node containing all + // the nodes in that SCC. + // 2. Identify incoming edges incident to the nodes inside of the SCC and + // reconnect them to the pi-block node. + // 3. Identify outgoing edges from the nodes inside of the SCC to nodes + // outside of it and reconnect them so that the edges are coming out of the + // SCC node instead. + + // Adding nodes as we iterate through the SCCs cause the SCC + // iterators to get invalidated. To prevent this invalidation, we first + // collect a list of nodes that are part of an SCC, and then iterate over + // those lists to create the pi-block nodes. Each element of the list is a + // list of nodes in an SCC. Note: trivial SCCs containing a single node are + // ignored. + SmallVector ListOfSCCs; + for (auto &SCC : make_range(scc_begin(&Graph), scc_end(&Graph))) { + if (SCC.size() > 1) + ListOfSCCs.emplace_back(SCC.begin(), SCC.end()); + } + + for (NodeListType &NL : ListOfSCCs) { + LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size() + << " nodes in it.\n"); + + NodeType &PiNode = createPiBlock(NL); + ++TotalPiBlockNodes; + + // Build a set to speed up the lookup for edges whose targets + // are inside the SCC. + SmallPtrSet NodesInSCC(NL.begin(), NL.end()); + + // We have the set of nodes in the SCC. We go through the set of nodes + // that are outside of the SCC and look for edges that cross the two sets. + for (NodeType *N : Graph) { + + // Skip the SCC node and all the nodes inside of it. + if (*N == PiNode || NodesInSCC.count(N)) + continue; + + for (NodeType *SCCNode : NL) { + + enum Direction { + Incoming, // Incoming edges to the SCC + Outgoing, // Edges going ot of the SCC + DirectionCount // To make the enum usable as an array index. + }; + + // Use these flags to help us avoid creating redundant edges. If there + // are more than one edges from an outside node to inside nodes, we only + // keep one edge from that node to the pi-block node. Similarly, if + // there are more than one edges from inside nodes to an outside node, + // we only keep one edge from the pi-block node to the outside node. + // There is a flag defined for each direction (incoming vs outgoing) and + // for each type of edge supported, using a two-dimensional boolean + // array. + using EdgeKind = typename EdgeType::EdgeKind; + EnumeratedArray EdgeAlreadyCreated[DirectionCount]{ + false, false}; + + auto createEdgeOfKind = [this](NodeType &Src, NodeType &Dst, + const EdgeKind K) { + switch (K) { + case EdgeKind::RegisterDefUse: + createDefUseEdge(Src, Dst); + break; + case EdgeKind::MemoryDependence: + createMemoryEdge(Src, Dst); + break; + case EdgeKind::Rooted: + createRootedEdge(Src, Dst); + break; + default: + llvm_unreachable("Unsupported type of edge."); + } + }; + + auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New, + const Direction Dir) { + if (!Src->hasEdgeTo(*Dst)) + return; + LLVM_DEBUG(dbgs() + << "reconnecting(" + << (Dir == Direction::Incoming ? "incoming)" : "outgoing)") + << ":\nSrc:" << *Src << "\nDst:" << *Dst + << "\nNew:" << *New << "\n"); + assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) && + "Invalid direction."); + + SmallVector EL; + Src->findEdgesTo(*Dst, EL); + for (EdgeType *OldEdge : EL) { + EdgeKind Kind = OldEdge->getKind(); + if (!EdgeAlreadyCreated[Dir][Kind]) { + if (Dir == Direction::Incoming) { + createEdgeOfKind(*Src, *New, Kind); + LLVM_DEBUG(dbgs() << "created edge from Src to New.\n"); + } else if (Dir == Direction::Outgoing) { + createEdgeOfKind(*New, *Dst, Kind); + LLVM_DEBUG(dbgs() << "created edge from New to Dst.\n"); + } + EdgeAlreadyCreated[Dir][Kind] = true; + } + Src->removeEdge(*OldEdge); + destroyEdge(*OldEdge); + LLVM_DEBUG(dbgs() << "removed old edge between Src and Dst.\n\n"); + } + }; + + // Process incoming edges incident to the pi-block node. + reconnectEdges(N, SCCNode, &PiNode, Direction::Incoming); + + // Process edges that are coming out of the pi-block node. + reconnectEdges(SCCNode, N, &PiNode, Direction::Outgoing); + } + } + } + + LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n"); +} + template void AbstractDependenceGraphBuilder::createDefUseEdges() { for (NodeType *N : Graph) { InstructionListType SrcIList; Index: llvm/test/Analysis/DDG/basic-a.ll =================================================================== --- llvm/test/Analysis/DDG/basic-a.ll +++ llvm/test/Analysis/DDG/basic-a.ll @@ -3,65 +3,70 @@ ; CHECK-LABEL: 'DDG' for loop 'test1.for.body': ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]: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 [[N2:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N4]]:single-instruction -; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N5]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %conv = uitofp i64 %n to float ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6]] +; CHECK-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add = fadd float %0, %conv ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; 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 [[N8]] +; CHECK-NEXT: [def-use] to [[N5]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: store float %add, float* %arrayidx1, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N2]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N1]] - -; CHECK: Node Address:[[N9]]:single-instruction +; 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 [[N10:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N10]]:single-instruction +; 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) { ;; for (unsigned long i = 0; i < n; i++) @@ -93,73 +98,78 @@ ; CHECK-LABEL: 'DDG' for loop 'test2.for.body': ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]: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 [[N2:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N5]]:single-instruction -; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N4: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 [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %1 = load float, float* %arrayidx1, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [memory] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3]] +; CHECK-NEXT: [memory] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add = fadd float %0, %1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9]] +; CHECK-NEXT: [def-use] to [[N6]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, float* %a, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9]] +; CHECK-NEXT: [def-use] to [[N6]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: store float %add, float* %arrayidx2, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N2]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %i.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N1]] - -; CHECK: Node Address:[[N10]]:single-instruction +; CHECK: Node Address:[[N8: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 [[N11:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK: Node Address:[[N11]]:single-instruction +; CHECK: Node Address:[[N9]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: br i1 %exitcond, label %test2.for.body, label %for.end.loopexit ; CHECK-NEXT: Edges:none! +; 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-NEXT: Instructions: +; CHECK-NEXT: %inc = add i64 %i.02, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N12]]: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: 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]] + + ;; Loop-independent memory dependencies. ;; void test2(unsigned long n, float * restrict a, float * restrict b) { ;; for (unsigned long i = 0; i < n; i++) Index: llvm/test/Analysis/DDG/basic-b.ll =================================================================== --- llvm/test/Analysis/DDG/basic-b.ll +++ llvm/test/Analysis/DDG/basic-b.ll @@ -3,78 +3,87 @@ ; CHECK-LABEL: 'DDG' for loop 'test1.for.body': ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.02 = phi i64 [ %inc, %test1.for.body ], [ 1, %test1.for.body.preheader ] +; 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-NEXT: Instructions: +; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 +; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %sub1 = add i64 %i.02, -1 +; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] ; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 +; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N6:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 +; 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-NEXT: [def-use] to [[N3]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N7:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %sub1 = add i64 %i.02, -1 +; 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: %arrayidx2 = getelementptr inbounds float, float* %a, i64 %sub1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N9]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %1 = load float, float* %arrayidx2, align 4 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] +; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N3]]:pi-block +; CHECK-NEXT: --- start of nodes in pi-block --- +; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; 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 [[N11:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N12:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 +; CHECK-NEXT: %1 = load float, float* %arrayidx2, align 4 ; CHECK-NEXT: Edges: ; CHECK-NEXT: [def-use] to [[N10]] -; CHECK: Node Address:[[N10]]:single-instruction +; CHECK: Node Address:[[N11]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: store float %add, float* %arrayidx3, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [memory] to [[N9]] +; CHECK-NEXT: [memory] to [[N12]] +; CHECK-NEXT:--- end of nodes in pi-block --- +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N2]]: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: %inc = add i64 %i.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N1]] +; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] -; CHECK: Node Address:[[N11]]:single-instruction +; CHECK: Node Address:[[N14]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub +; 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 [[N12:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N1]] +; CHECK-NEXT: [def-use] to [[N4]] +; CHECK-NEXT: [def-use] to [[N6]] +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N12]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp, label %test1.for.body, label %for.end.loopexit -; CHECK-NEXT: Edges:none! ;; Loop-carried dependence requiring edge-reversal to expose a cycle ;; in the graph. @@ -107,83 +116,86 @@ ret void } - ; CHECK-LABEL: 'DDG' for loop 'test2.for.body': ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]: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 [[N2:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N5]]:single-instruction -; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N2:0x[0-9a-f]*]] -; CHECK: Node Address:[[N6]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %0 = load float, float* %arrayidx, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N4:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add1 = add i64 %i.02, 1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N5:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N5]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx2 = getelementptr inbounds float, float* %a, i64 %add1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %1 = load float, float* %arrayidx2, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [memory] to [[N10:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N3]] +; CHECK-NEXT: [memory] to [[N7:0x[0-9a-f]*]] -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add = fadd float %0, %1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N10]] +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N8:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx3 = getelementptr inbounds float, float* %a, i64 %i.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N10]] +; CHECK-NEXT: [def-use] to [[N7]] -; CHECK: Node Address:[[N10]]:single-instruction +; 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:[[N2]]: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-NEXT: [def-use] to [[N1]] - -; CHECK: Node Address:[[N11]]:single-instruction +; CHECK: Node Address:[[N9:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %cmp = icmp ult i64 %inc, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N10:0x[0-9a-f]*]] -; CHECK: Node Address:[[N12]]:single-instruction +; 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:[[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) { Index: llvm/test/Analysis/DDG/basic-loopnest.ll =================================================================== --- llvm/test/Analysis/DDG/basic-loopnest.ll +++ llvm/test/Analysis/DDG/basic-loopnest.ll @@ -4,169 +4,181 @@ ; CHECK-LABEL: 'DDG' for loop 'test1.for.cond1.preheader': ; CHECK: Node Address:[[N1: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: %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-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; 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: %sub = add i64 %n, -1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub +; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 +; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N10:0x[0-9a-f]*]]: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 [[N11:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N5]]:single-instruction +; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N15]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N14]] +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] -; CHECK: Node Address:[[N14]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N16]]:single-instruction +; 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 [[N17:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] -; CHECK: Node Address:[[N18]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 +; CHECK: Node Address:[[N11]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK: Node Address:[[N13]]:single-instruction +; CHECK: Node Address:[[N13:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %sub7 = add i64 %j.02, -1 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N19]] +; CHECK-NEXT: [def-use] to [[N12]] -; CHECK: Node Address:[[N19]]:single-instruction +; CHECK: Node Address:[[N12]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %sub7 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9]] -; CHECK: Node Address:[[N20]]:single-instruction +; CHECK: Node Address:[[N14:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4 +; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N17]] +; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]] -; CHECK: Node Address:[[N17]]:single-instruction +; CHECK: Node Address:[[N15]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %add = fadd float %1, %3 +; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N16]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n +; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9]] -; CHECK: Node Address:[[N27]]:single-instruction +; CHECK: Node Address:[[N2]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 +; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12]] +; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] -; CHECK: Node Address:[[N12]]:single-instruction +; CHECK: Node Address:[[N17]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx11 = getelementptr inbounds float, float* %arrayidx10, i64 %j.02 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N26]] +; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N26]]:single-instruction +; CHECK: Node Address:[[N18:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: store float %add, float* %arrayidx11, align 4 +; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [memory] to [[N20]] +; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] -; CHECK: Node Address:[[N11]]:single-instruction +; CHECK: Node Address:[[N19]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %j.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [def-use] to [[N10]] +; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N7]]:single-instruction +; CHECK: Node Address:[[N20:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp2 = icmp ult i64 %inc, %sub -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]] +; CHECK-NEXT: br label %for.body4 +; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N21]]:single-instruction +; CHECK: Node Address:[[N21:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit +; CHECK-NEXT: br label %for.inc12 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N2]]:single-instruction +; CHECK: Node Address:[[N9]]:pi-block +; CHECK-NEXT:--- start of nodes in pi-block --- +; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc13 = add i64 %i.04, 1 +; CHECK-NEXT: %add = fadd float %1, %3 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N22:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N1]] +; CHECK-NEXT: [def-use] to [[N23:0x[0-9a-f]*]] -; CHECK: Node Address:[[N22]]:single-instruction +; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %exitcond = icmp ne i64 %inc13, %n +; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N23:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N22]] ; CHECK: Node Address:[[N23]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %exitcond, label %test1.for.cond1.preheader, label %for.end14.loopexit +; CHECK-NEXT: store float %add, float* %arrayidx11, align 4 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [memory] to [[N24]] +; CHECK-NEXT:--- end of nodes in pi-block --- ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N24:0x[0-9a-f]*]]: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: br label %for.body4 -; CHECK-NEXT: Edges:none! +; CHECK-NEXT: %inc13 = add i64 %i.04, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]] -; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N27]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br label %for.inc12 -; CHECK-NEXT: Edges:none! +; 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: 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: %inc = add i64 %j.02, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N30:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N30]]: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 [[N29]] +; 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 [[N16]] +; CHECK-NEXT: [def-use] to [[N2]] @@ -222,170 +234,179 @@ ; CHECK-LABEL: 'DDG' for loop 'test2.for.cond1.preheader': ; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i.04 = phi i64 [ %inc13, %for.inc12 ], [ 0, %test2.for.cond1.preheader.preheader ] +; 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-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; 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: %sub = add i64 %n, -1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N8]]:single-instruction +; CHECK: Node Address:[[N3]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub +; CHECK-NEXT: %cmp21 = icmp ult i64 1, %sub ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N4:0x[0-9a-f]*]] -; CHECK: Node Address:[[N9]]:single-instruction +; CHECK: Node Address:[[N4]]:single-instruction ; CHECK-NEXT: Instructions: -; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 +; CHECK-NEXT: br i1 %cmp21, label %for.body4.preheader, label %for.inc12 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N10:0x[0-9a-f]*]]: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 [[N11:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N13:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] - -; CHECK: Node Address:[[N5]]:single-instruction +; CHECK: Node Address:[[N5:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %0 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N15:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N6:0x[0-9a-f]*]] -; CHECK: Node Address:[[N15]]:single-instruction +; CHECK: Node Address:[[N6]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx = getelementptr inbounds float, float* %b, i64 %0 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N14]] +; CHECK-NEXT: [def-use] to [[N7:0x[0-9a-f]*]] -; CHECK: Node Address:[[N14]]:single-instruction +; CHECK: Node Address:[[N7]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx5 = getelementptr inbounds float, float* %arrayidx, i64 %j.02 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N16:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N8:0x[0-9a-f]*]] -; CHECK: Node Address:[[N16]]:single-instruction +; 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 [[N17:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9:0x[0-9a-f]*]] -; CHECK: Node Address:[[N4]]:single-instruction +; CHECK: Node Address:[[N10:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %2 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N11:0x[0-9a-f]*]] -; CHECK: Node Address:[[N18]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 +; CHECK: Node Address:[[N11]]:single-instruction +; CHECK-NEXT: Instructions: +; CHECK-NEXT: %arrayidx6 = getelementptr inbounds float, float* %a, i64 %2 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N12:0x[0-9a-f]*]] -; CHECK: Node Address:[[N13]]:single-instruction +; 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 [[N19]] +; CHECK-NEXT: [def-use] to [[N12]] -; CHECK: Node Address:[[N19]]:single-instruction +; CHECK: Node Address:[[N12]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx8 = getelementptr inbounds float, float* %arrayidx6, i64 %add7 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N20:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N14:0x[0-9a-f]*]] -; CHECK: Node Address:[[N20]]:single-instruction +; CHECK: Node Address:[[N14]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %3 = load float, float* %arrayidx8, align 4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N17]] -; CHECK-NEXT: [memory] to [[N26:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N9]] +; CHECK-NEXT: [memory] to [[N15:0x[0-9a-f]*]] -; CHECK: Node Address:[[N17]]:single-instruction +; CHECK: Node Address:[[N9]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %add = fadd float %1, %3 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N26]] +; CHECK-NEXT: [def-use] to [[N15]] -; CHECK: Node Address:[[N3]]:single-instruction +; CHECK: Node Address:[[N16:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %4 = mul nsw i64 %i.04, %n ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N27:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N17:0x[0-9a-f]*]] -; CHECK: Node Address:[[N27]]:single-instruction +; CHECK: Node Address:[[N17]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: %arrayidx10 = getelementptr inbounds float, float* %a, i64 %4 ; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N12]] +; CHECK-NEXT: [def-use] to [[N18:0x[0-9a-f]*]] -; CHECK: Node Address:[[N12]]: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 [[N26]] +; CHECK-NEXT: [def-use] to [[N15]] -; CHECK: Node Address:[[N26]]:single-instruction +; CHECK: Node Address:[[N15]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: store float %add, float* %arrayidx11, align 4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N11]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc = add i64 %j.02, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N7]] -; CHECK-NEXT: [def-use] to [[N10]] - -; CHECK: Node Address:[[N7]]:single-instruction +; 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 [[N21:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N19:0x[0-9a-f]*]] -; CHECK: Node Address:[[N21]]:single-instruction +; CHECK: Node Address:[[N19]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: br i1 %cmp2, label %for.body4, label %for.inc12.loopexit ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N2]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %inc13 = add i64 %i.04, 1 -; CHECK-NEXT: Edges: -; CHECK-NEXT: [def-use] to [[N22:0x[0-9a-f]*]] -; CHECK-NEXT: [def-use] to [[N1]] - -; CHECK: Node Address:[[N22]]:single-instruction +; 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 [[N23:0x[0-9a-f]*]] +; CHECK-NEXT: [def-use] to [[N21:0x[0-9a-f]*]] -; CHECK: Node Address:[[N23]]:single-instruction +; CHECK: Node Address:[[N21]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: br i1 %exitcond, label %test2.for.cond1.preheader, label %for.end14.loopexit ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N24:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N22:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: br label %for.body4 ; CHECK-NEXT: Edges:none! -; CHECK: Node Address:[[N25:0x[0-9a-f]*]]:single-instruction +; CHECK: Node Address:[[N23:0x[0-9a-f]*]]:single-instruction ; CHECK-NEXT: Instructions: ; CHECK-NEXT: br label %for.inc12 ; CHECK-NEXT: Edges:none! +; 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: %inc13 = add i64 %i.04, 1 +; CHECK-NEXT: Edges: +; CHECK-NEXT: [def-use] to [[N26:0x[0-9a-f]*]] + +; CHECK: Node Address:[[N26]]: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: 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-NEXT: Instructions: +; 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]] +; CHECK-NEXT: [def-use] to [[N13]] +; CHECK-NEXT: [def-use] to [[N18]] +; CHECK-NEXT: [def-use] to [[N2]] + + ;; This test has no cycles. ;; void test2(unsigned long n, float a[][n], float b[][n]) { ;; for (unsigned long i = 0; i < n; i++) Index: llvm/test/Analysis/DDG/root-node.ll =================================================================== --- llvm/test/Analysis/DDG/root-node.ll +++ llvm/test/Analysis/DDG/root-node.ll @@ -2,18 +2,16 @@ ; CHECK-LABEL: 'DDG' for loop 'test1.for.body': -; CHECK: Node Address:[[N1:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i2.03 = phi i64 [ 0, %for.body.lr.ph ], [ %inc2, %test1.for.body ] - -; CHECK: Node Address:[[N2:0x[0-9a-f]*]]:single-instruction -; CHECK-NEXT: Instructions: -; CHECK-NEXT: %i1.02 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %test1.for.body ] - ; CHECK: Node Address:[[ROOT:0x[0-9a-f]*]]:root ; CHECK-NEXT: Edges: -; CHECK-NEXT: [rooted] to [[N1]] -; CHECK-NEXT: [rooted] to [[N2]] +; 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 ] ;; // Two separate components in the graph. Root node must link to both. Index: llvm/unittests/ADT/CMakeLists.txt =================================================================== --- llvm/unittests/ADT/CMakeLists.txt +++ llvm/unittests/ADT/CMakeLists.txt @@ -18,6 +18,7 @@ DenseSetTest.cpp DepthFirstIteratorTest.cpp DirectedGraphTest.cpp + EnumeratedArrayTest.cpp EquivalenceClassesTest.cpp FallibleIteratorTest.cpp FoldingSet.cpp Index: llvm/unittests/ADT/EnumeratedArrayTest.cpp =================================================================== --- /dev/null +++ llvm/unittests/ADT/EnumeratedArrayTest.cpp @@ -0,0 +1,51 @@ +//===- llvm/unittest/ADT/EnumeratedArrayTest.cpp ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// EnumeratedArray unit tests. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/EnumeratedArray.h" +#include "gtest/gtest.h" + +namespace llvm { + +//===--------------------------------------------------------------------===// +// Test initialization and use of operator[] for both read and write. +//===--------------------------------------------------------------------===// + +TEST(EnumeratedArray, InitAndIndex) { + + enum class Colors { Red, Blue, Green, Last = Green }; + + EnumeratedArray Array1; + + Array1[Colors::Red] = 1.0; + Array1[Colors::Blue] = 2.0; + Array1[Colors::Green] = 3.0; + + EXPECT_EQ(Array1[Colors::Red], 1.0); + EXPECT_EQ(Array1[Colors::Blue], 2.0); + EXPECT_EQ(Array1[Colors::Green], 3.0); + + EnumeratedArray Array2(true); + + EXPECT_TRUE(Array2[Colors::Red]); + EXPECT_TRUE(Array2[Colors::Blue]); + EXPECT_TRUE(Array2[Colors::Green]); + + Array2[Colors::Red] = true; + Array2[Colors::Blue] = false; + Array2[Colors::Green] = true; + + EXPECT_TRUE(Array2[Colors::Red]); + EXPECT_FALSE(Array2[Colors::Blue]); + EXPECT_TRUE(Array2[Colors::Green]); +} + +} // namespace llvm