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       llvm::append_range(IList, TmpIList);
  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     append_range(BBList, SCC);
 194   std::reverse(BBList.begin(), BBList.end());
 195   DDGBuilder(*this, D, BBList).populate();
 196 }
 197
 198 DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
 199                                          DependenceInfo &D)
 200     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
 201                                 L.getHeader()->getName())
 202                               .str(),
 203                           D) {
 204   // Put the basic blocks in program order for correct dependence
 205   // directions.
 206   LoopBlocksDFS DFS(&L);
 207   DFS.perform(&LI);
 208   BasicBlockListType BBList;
 209   append_range(BBList, make_range(DFS.beginRPO(), DFS.endRPO()));
 210   DDGBuilder(*this, D, BBList).populate();
 211 }
 212
 213 DataDependenceGraph::~DataDependenceGraph() {
 214   for (auto *N : Nodes) {
 215     for (auto *E : *N)
 216       delete E;
 217     delete N;
 218   }
 219 }
 220
 221 bool DataDependenceGraph::addNode(DDGNode &N) {
 222   if (!DDGBase::addNode(N))
 223     return false;
 224
 225   // In general, if the root node is already created and linked, it is not safe
 226   // to add new nodes since they may be unreachable by the root. However,
 227   // pi-block nodes need to be added after the root node is linked, and they are
 228   // always reachable by the root, because they represent components that are
 229   // already reachable by root.
 230   auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
 231   assert((!Root || Pi) &&
 232          "Root node is already added. No more nodes can be added.");
 233
 234   if (isa<RootDDGNode>(N))
 235     Root = &N;
 236
 237   if (Pi)
 238     for (DDGNode *NI : Pi->getNodes())
 239       PiBlockMap.insert(std::make_pair(NI, Pi));
 240
 241   return true;
 242 }
 243
 244 const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
 245   if (PiBlockMap.find(&N) == PiBlockMap.end())
 246     return nullptr;
 247   auto *Pi = PiBlockMap.find(&N)->second;
 248   assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
 249          "Nested pi-blocks detected.");
 250   return Pi;
 251 }
 252
 253 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
 254   for (DDGNode *Node : G)
 255     // Avoid printing nodes that are part of a pi-block twice. They will get
 256     // printed when the pi-block is printed.
 257     if (!G.getPiBlock(*Node))
 258       OS << *Node << "\n";
 259   OS << "\n";
 260   return OS;
 261 }
 262
 263 //===--------------------------------------------------------------------===//
 264 // DDGBuilder implementation
 265 //===--------------------------------------------------------------------===//
 266
 267 bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
 268                                    const DDGNode &Tgt) const {
 269   // Only merge two nodes if they are both simple nodes and the consecutive
 270   // instructions after merging belong to the same BB.
 271   const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
 272   const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
 273   if (!SimpleSrc || !SimpleTgt)
 274     return false;
 275
 276   return SimpleSrc->getLastInstruction()->getParent() ==
 277          SimpleTgt->getFirstInstruction()->getParent();
 278 }
 279
 280 void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
 281   DDGEdge &EdgeToFold = A.back();
 282   assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
 283          "Expected A to have a single edge to B.");
 284   assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
 285          "Expected simple nodes");
 286
 287   // Copy instructions from B to the end of A.
 288   cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));
 289
 290   // Move to A any outgoing edges from B.
 291   for (DDGEdge *BE : B)
 292     Graph.connect(A, BE->getTargetNode(), *BE);
 293
 294   A.removeEdge(EdgeToFold);
 295   destroyEdge(EdgeToFold);
 296   Graph.removeNode(B);
 297   destroyNode(B);
 298 }
 299
 300 bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
 301
 302 bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }
 303
 304 //===--------------------------------------------------------------------===//
 305 // DDG Analysis Passes
 306 //===--------------------------------------------------------------------===//
 307
 308 /// DDG as a loop pass.
 309 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
 310                                      LoopStandardAnalysisResults &AR) {
 311   Function *F = L.getHeader()->getParent();
 312   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
 313   return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
 314 }
 315 AnalysisKey DDGAnalysis::Key;
 316
 317 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
 318                                               LoopStandardAnalysisResults &AR,
 319                                               LPMUpdater &U) {
 320   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
 321   OS << *AM.getResult<DDGAnalysis>(L, AR);
 322   return PreservedAnalyses::all();
 323 }