contrib/llvm-project/llvm/lib/Analysis/DDG.cpp

   1 //===- DDG.cpp - Data Dependence Graph -------------------------------------==//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The implementation for the data dependence graph.
  10 //===----------------------------------------------------------------------===//
  11 #include "llvm/Analysis/DDG.h"
  12 #include "llvm/ADT/SCCIterator.h"
  13 #include "llvm/Analysis/LoopInfo.h"
  14 #include "llvm/Analysis/LoopIterator.h"
  15 #include "llvm/Support/CommandLine.h"
  16
  17 using namespace llvm;
  18
  19 static cl::opt<bool> SimplifyDDG(
  20     "ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore,
  21     cl::desc(
  22         "Simplify DDG by merging nodes that have less interesting edges."));
  23
  24 static cl::opt<bool>
  25     CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
  26                    cl::desc("Create pi-block nodes."));
  27
  28 #define DEBUG_TYPE "ddg"
  29
  30 template class llvm::DGEdge<DDGNode, DDGEdge>;
  31 template class llvm::DGNode<DDGNode, DDGEdge>;
  32 template class llvm::DirectedGraph<DDGNode, DDGEdge>;
  33
  34 //===--------------------------------------------------------------------===//
  35 // DDGNode implementation
  36 //===--------------------------------------------------------------------===//
  37 DDGNode::~DDGNode() {}
  38
  39 bool DDGNode::collectInstructions(
  40     llvm::function_ref<bool(Instruction *)> const &Pred,
  41     InstructionListType &IList) const {
  42   assert(IList.empty() && "Expected the IList to be empty on entry.");
  43   if (isa<SimpleDDGNode>(this)) {
  44     for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())
  45       if (Pred(I))
  46         IList.push_back(I);
  47   } else if (isa<PiBlockDDGNode>(this)) {
  48     for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {
  49       assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
  50       SmallVector<Instruction *, 8> TmpIList;
  51       PN->collectInstructions(Pred, TmpIList);
  52       IList.insert(IList.end(), TmpIList.begin(), TmpIList.end());
  53     }
  54   } else
  55     llvm_unreachable("unimplemented type of node");
  56   return !IList.empty();
  57 }
  58
  59 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
  60   const char *Out;
  61   switch (K) {
  62   case DDGNode::NodeKind::SingleInstruction:
  63     Out = "single-instruction";
  64     break;
  65   case DDGNode::NodeKind::MultiInstruction:
  66     Out = "multi-instruction";
  67     break;
  68   case DDGNode::NodeKind::PiBlock:
  69     Out = "pi-block";
  70     break;
  71   case DDGNode::NodeKind::Root:
  72     Out = "root";
  73     break;
  74   case DDGNode::NodeKind::Unknown:
  75     Out = "?? (error)";
  76     break;
  77   }
  78   OS << Out;
  79   return OS;
  80 }
  81
  82 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
  83   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
  84   if (isa<SimpleDDGNode>(N)) {
  85     OS << " Instructions:\n";
  86     for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())
  87       OS.indent(2) << *I << "\n";
  88   } else if (isa<PiBlockDDGNode>(&N)) {
  89     OS << "--- start of nodes in pi-block ---\n";
  90     auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();
  91     unsigned Count = 0;
  92     for (const DDGNode *N : Nodes)
  93       OS << *N << (++Count == Nodes.size() ? "" : "\n");
  94     OS << "--- end of nodes in pi-block ---\n";
  95   } else if (!isa<RootDDGNode>(N))
  96     llvm_unreachable("unimplemented type of node");
  97
  98   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
  99   for (auto &E : N.getEdges())
 100     OS.indent(2) << *E;
 101   return OS;
 102 }
 103
 104 //===--------------------------------------------------------------------===//
 105 // SimpleDDGNode implementation
 106 //===--------------------------------------------------------------------===//
 107
 108 SimpleDDGNode::SimpleDDGNode(Instruction &I)
 109   : DDGNode(NodeKind::SingleInstruction), InstList() {
 110   assert(InstList.empty() && "Expected empty list.");
 111   InstList.push_back(&I);
 112 }
 113
 114 SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
 115     : DDGNode(N), InstList(N.InstList) {
 116   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
 117           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
 118          "constructing from invalid simple node.");
 119 }
 120
 121 SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
 122     : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
 123   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
 124           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
 125          "constructing from invalid simple node.");
 126 }
 127
 128 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
 129
 130 //===--------------------------------------------------------------------===//
 131 // PiBlockDDGNode implementation
 132 //===--------------------------------------------------------------------===//
 133
 134 PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
 135     : DDGNode(NodeKind::PiBlock), NodeList(List) {
 136   assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
 137 }
 138
 139 PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
 140     : DDGNode(N), NodeList(N.NodeList) {
 141   assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
 142          "constructing from invalid pi-block node.");
 143 }
 144
 145 PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
 146     : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
 147   assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
 148          "constructing from invalid pi-block node.");
 149 }
 150
 151 PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
 152
 153 //===--------------------------------------------------------------------===//
 154 // DDGEdge implementation
 155 //===--------------------------------------------------------------------===//
 156
 157 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
 158   const char *Out;
 159   switch (K) {
 160   case DDGEdge::EdgeKind::RegisterDefUse:
 161     Out = "def-use";
 162     break;
 163   case DDGEdge::EdgeKind::MemoryDependence:
 164     Out = "memory";
 165     break;
 166   case DDGEdge::EdgeKind::Rooted:
 167     Out = "rooted";
 168     break;
 169   case DDGEdge::EdgeKind::Unknown:
 170     Out = "?? (error)";
 171     break;
 172   }
 173   OS << Out;
 174   return OS;
 175 }
 176
 177 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
 178   OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
 179   return OS;
 180 }
 181
 182 //===--------------------------------------------------------------------===//
 183 // DataDependenceGraph implementation
 184 //===--------------------------------------------------------------------===//
 185 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
 186
 187 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
 188     : DependenceGraphInfo(F.getName().str(), D) {
 189   // Put the basic blocks in program order for correct dependence
 190   // directions.
 191   BasicBlockListType BBList;
 192   for (auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
 193     for (BasicBlock * BB : SCC)
 194       BBList.push_back(BB);
 195   std::reverse(BBList.begin(), BBList.end());
 196   DDGBuilder(*this, D, BBList).populate();
 197 }
 198
 199 DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
 200                                          DependenceInfo &D)
 201     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
 202                                 L.getHeader()->getName())
 203                               .str(),
 204                           D) {
 205   // Put the basic blocks in program order for correct dependence
 206   // directions.
 207   LoopBlocksDFS DFS(&L);
 208   DFS.perform(&LI);
 209   BasicBlockListType BBList;
 210   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
 211     BBList.push_back(BB);
 212   DDGBuilder(*this, D, BBList).populate();
 213 }
 214
 215 DataDependenceGraph::~DataDependenceGraph() {
 216   for (auto *N : Nodes) {
 217     for (auto *E : *N)
 218       delete E;
 219     delete N;
 220   }
 221 }
 222
 223 bool DataDependenceGraph::addNode(DDGNode &N) {
 224   if (!DDGBase::addNode(N))
 225     return false;
 226
 227   // In general, if the root node is already created and linked, it is not safe
 228   // to add new nodes since they may be unreachable by the root. However,
 229   // pi-block nodes need to be added after the root node is linked, and they are
 230   // always reachable by the root, because they represent components that are
 231   // already reachable by root.
 232   auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
 233   assert((!Root || Pi) &&
 234          "Root node is already added. No more nodes can be added.");
 235
 236   if (isa<RootDDGNode>(N))
 237     Root = &N;
 238
 239   if (Pi)
 240     for (DDGNode *NI : Pi->getNodes())
 241       PiBlockMap.insert(std::make_pair(NI, Pi));
 242
 243   return true;
 244 }
 245
 246 const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
 247   if (PiBlockMap.find(&N) == PiBlockMap.end())
 248     return nullptr;
 249   auto *Pi = PiBlockMap.find(&N)->second;
 250   assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
 251          "Nested pi-blocks detected.");
 252   return Pi;
 253 }
 254
 255 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
 256   for (DDGNode *Node : G)
 257     // Avoid printing nodes that are part of a pi-block twice. They will get
 258     // printed when the pi-block is printed.
 259     if (!G.getPiBlock(*Node))
 260       OS << *Node << "\n";
 261   OS << "\n";
 262   return OS;
 263 }
 264
 265 //===--------------------------------------------------------------------===//
 266 // DDGBuilder implementation
 267 //===--------------------------------------------------------------------===//
 268
 269 bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
 270                                    const DDGNode &Tgt) const {
 271   // Only merge two nodes if they are both simple nodes and the consecutive
 272   // instructions after merging belong to the same BB.
 273   const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
 274   const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
 275   if (!SimpleSrc || !SimpleTgt)
 276     return false;
 277
 278   return SimpleSrc->getLastInstruction()->getParent() ==
 279          SimpleTgt->getFirstInstruction()->getParent();
 280 }
 281
 282 void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
 283   DDGEdge &EdgeToFold = A.back();
 284   assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
 285          "Expected A to have a single edge to B.");
 286   assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
 287          "Expected simple nodes");
 288
 289   // Copy instructions from B to the end of A.
 290   cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));
 291
 292   // Move to A any outgoing edges from B.
 293   for (DDGEdge *BE : B)
 294     Graph.connect(A, BE->getTargetNode(), *BE);
 295
 296   A.removeEdge(EdgeToFold);
 297   destroyEdge(EdgeToFold);
 298   Graph.removeNode(B);
 299   destroyNode(B);
 300 }
 301
 302 bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
 303
 304 bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }
 305
 306 //===--------------------------------------------------------------------===//
 307 // DDG Analysis Passes
 308 //===--------------------------------------------------------------------===//
 309
 310 /// DDG as a loop pass.
 311 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
 312                                      LoopStandardAnalysisResults &AR) {
 313   Function *F = L.getHeader()->getParent();
 314   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
 315   return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
 316 }
 317 AnalysisKey DDGAnalysis::Key;
 318
 319 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
 320                                               LoopStandardAnalysisResults &AR,
 321                                               LPMUpdater &U) {
 322   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
 323   OS << *AM.getResult<DDGAnalysis>(L, AR);
 324   return PreservedAnalyses::all();
 325 }