| //===- DDG.cpp - Data Dependence Graph -------------------------------------==// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // 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; |
| |
| static cl::opt<bool> SimplifyDDG( |
| "ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore, |
| cl::desc( |
| "Simplify DDG by merging nodes that have less interesting edges.")); |
| |
| static cl::opt<bool> |
| 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<DDGNode, DDGEdge>; |
| template class llvm::DGNode<DDGNode, DDGEdge>; |
| template class llvm::DirectedGraph<DDGNode, DDGEdge>; |
| |
| //===--------------------------------------------------------------------===// |
| // DDGNode implementation |
| //===--------------------------------------------------------------------===// |
| DDGNode::~DDGNode() {} |
| |
| bool DDGNode::collectInstructions( |
| llvm::function_ref<bool(Instruction *)> const &Pred, |
| InstructionListType &IList) const { |
| assert(IList.empty() && "Expected the IList to be empty on entry."); |
| if (isa<SimpleDDGNode>(this)) { |
| for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions()) |
| if (Pred(I)) |
| IList.push_back(I); |
| } else if (isa<PiBlockDDGNode>(this)) { |
| for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) { |
| assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported."); |
| SmallVector<Instruction *, 8> TmpIList; |
| PN->collectInstructions(Pred, TmpIList); |
| llvm::append_range(IList, TmpIList); |
| } |
| } else |
| llvm_unreachable("unimplemented type of node"); |
| return !IList.empty(); |
| } |
| |
| raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) { |
| const char *Out; |
| switch (K) { |
| case DDGNode::NodeKind::SingleInstruction: |
| Out = "single-instruction"; |
| break; |
| 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 = "?? (error)"; |
| break; |
| } |
| OS << Out; |
| return OS; |
| } |
| |
| raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) { |
| OS << "Node Address:" << &N << ":" << N.getKind() << "\n"; |
| if (isa<SimpleDDGNode>(N)) { |
| OS << " Instructions:\n"; |
| for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions()) |
| OS.indent(2) << *I << "\n"; |
| } else if (isa<PiBlockDDGNode>(&N)) { |
| OS << "--- start of nodes in pi-block ---\n"; |
| auto &Nodes = cast<const PiBlockDDGNode>(&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<RootDDGNode>(N)) |
| llvm_unreachable("unimplemented type of node"); |
| |
| OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n"); |
| for (auto &E : N.getEdges()) |
| OS.indent(2) << *E; |
| return OS; |
| } |
| |
| //===--------------------------------------------------------------------===// |
| // SimpleDDGNode implementation |
| //===--------------------------------------------------------------------===// |
| |
| SimpleDDGNode::SimpleDDGNode(Instruction &I) |
| : DDGNode(NodeKind::SingleInstruction), InstList() { |
| assert(InstList.empty() && "Expected empty list."); |
| InstList.push_back(&I); |
| } |
| |
| SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N) |
| : DDGNode(N), InstList(N.InstList) { |
| assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) || |
| (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) && |
| "constructing from invalid simple node."); |
| } |
| |
| SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N) |
| : DDGNode(std::move(N)), InstList(std::move(N.InstList)) { |
| assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) || |
| (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) && |
| "constructing from invalid simple node."); |
| } |
| |
| 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 |
| //===--------------------------------------------------------------------===// |
| |
| raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) { |
| const char *Out; |
| switch (K) { |
| case DDGEdge::EdgeKind::RegisterDefUse: |
| Out = "def-use"; |
| break; |
| case DDGEdge::EdgeKind::MemoryDependence: |
| Out = "memory"; |
| break; |
| case DDGEdge::EdgeKind::Rooted: |
| Out = "rooted"; |
| break; |
| case DDGEdge::EdgeKind::Unknown: |
| Out = "?? (error)"; |
| break; |
| } |
| OS << Out; |
| return OS; |
| } |
| |
| raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) { |
| OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n"; |
| return OS; |
| } |
| |
| //===--------------------------------------------------------------------===// |
| // DataDependenceGraph implementation |
| //===--------------------------------------------------------------------===// |
| 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 &SCC : make_range(scc_begin(&F), scc_end(&F))) |
| append_range(BBList, SCC); |
| std::reverse(BBList.begin(), BBList.end()); |
| DDGBuilder(*this, D, BBList).populate(); |
| } |
| |
| 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; |
| append_range(BBList, make_range(DFS.beginRPO(), DFS.endRPO())); |
| DDGBuilder(*this, D, BBList).populate(); |
| } |
| |
| DataDependenceGraph::~DataDependenceGraph() { |
| for (auto *N : Nodes) { |
| for (auto *E : *N) |
| delete E; |
| delete N; |
| } |
| } |
| |
| bool DataDependenceGraph::addNode(DDGNode &N) { |
| if (!DDGBase::addNode(N)) |
| return false; |
| |
| // In general, if the root node is already created and linked, it is not safe |
| // to add new nodes since they may be unreachable by the root. 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<PiBlockDDGNode>(&N); |
| assert((!Root || Pi) && |
| "Root node is already added. No more nodes can be added."); |
| |
| if (isa<RootDDGNode>(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 (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; |
| } |
| |
| //===--------------------------------------------------------------------===// |
| // DDGBuilder implementation |
| //===--------------------------------------------------------------------===// |
| |
| bool DDGBuilder::areNodesMergeable(const DDGNode &Src, |
| const DDGNode &Tgt) const { |
| // Only merge two nodes if they are both simple nodes and the consecutive |
| // instructions after merging belong to the same BB. |
| const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src); |
| const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt); |
| if (!SimpleSrc || !SimpleTgt) |
| return false; |
| |
| return SimpleSrc->getLastInstruction()->getParent() == |
| SimpleTgt->getFirstInstruction()->getParent(); |
| } |
| |
| void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) { |
| DDGEdge &EdgeToFold = A.back(); |
| assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B && |
| "Expected A to have a single edge to B."); |
| assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) && |
| "Expected simple nodes"); |
| |
| // Copy instructions from B to the end of A. |
| cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B)); |
| |
| // Move to A any outgoing edges from B. |
| for (DDGEdge *BE : B) |
| Graph.connect(A, BE->getTargetNode(), *BE); |
| |
| A.removeEdge(EdgeToFold); |
| destroyEdge(EdgeToFold); |
| Graph.removeNode(B); |
| destroyNode(B); |
| } |
| |
| bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; } |
| |
| bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; } |
| |
| //===--------------------------------------------------------------------===// |
| // DDG Analysis Passes |
| //===--------------------------------------------------------------------===// |
| |
| /// DDG as a loop pass. |
| 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, AR.LI, DI); |
| } |
| AnalysisKey DDGAnalysis::Key; |
| |
| PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM, |
| LoopStandardAnalysisResults &AR, |
| LPMUpdater &U) { |
| OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n"; |
| OS << *AM.getResult<DDGAnalysis>(L, AR); |
| return PreservedAnalyses::all(); |
| } |