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