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/Analysis/LoopInfo.h"
  13
  14 using namespace llvm;
  15
  16 #define DEBUG_TYPE "ddg"
  17
  18 template class llvm::DGEdge<DDGNode, DDGEdge>;
  19 template class llvm::DGNode<DDGNode, DDGEdge>;
  20 template class llvm::DirectedGraph<DDGNode, DDGEdge>;
  21
  22 //===--------------------------------------------------------------------===//
  23 // DDGNode implementation
  24 //===--------------------------------------------------------------------===//
  25 DDGNode::~DDGNode() {}
  26
  27 bool DDGNode::collectInstructions(
  28     llvm::function_ref<bool(Instruction *)> const &Pred,
  29     InstructionListType &IList) const {
  30   assert(IList.empty() && "Expected the IList to be empty on entry.");
  31   if (isa<SimpleDDGNode>(this)) {
  32     for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
  33       if (Pred(I))
  34         IList.push_back(I);
  35   } else
  36     llvm_unreachable("unimplemented type of node");
  37   return !IList.empty();
  38 }
  39
  40 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
  41   const char *Out;
  42   switch (K) {
  43   case DDGNode::NodeKind::SingleInstruction:
  44     Out = "single-instruction";
  45     break;
  46   case DDGNode::NodeKind::MultiInstruction:
  47     Out = "multi-instruction";
  48     break;
  49   case DDGNode::NodeKind::Root:
  50     Out = "root";
  51     break;
  52   case DDGNode::NodeKind::Unknown:
  53     Out = "??";
  54     break;
  55   }
  56   OS << Out;
  57   return OS;
  58 }
  59
  60 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
  61   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
  62   if (isa<SimpleDDGNode>(N)) {
  63     OS << " Instructions:\n";
  64     for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
  65       OS.indent(2) << *I << "\n";
  66   } else if (!isa<RootDDGNode>(N))
  67     llvm_unreachable("unimplemented type of node");
  68
  69   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
  70   for (auto &E : N.getEdges())
  71     OS.indent(2) << *E;
  72   return OS;
  73 }
  74
  75 //===--------------------------------------------------------------------===//
  76 // SimpleDDGNode implementation
  77 //===--------------------------------------------------------------------===//
  78
  79 SimpleDDGNode::SimpleDDGNode(Instruction &I)
  80   : DDGNode(NodeKind::SingleInstruction), InstList() {
  81   assert(InstList.empty() && "Expected empty list.");
  82   InstList.push_back(&I);
  83 }
  84
  85 SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
  86     : DDGNode(N), InstList(N.InstList) {
  87   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
  88           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
  89          "constructing from invalid simple node.");
  90 }
  91
  92 SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
  93     : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
  94   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
  95           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
  96          "constructing from invalid simple node.");
  97 }
  98
  99 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
 100
 101 //===--------------------------------------------------------------------===//
 102 // DDGEdge implementation
 103 //===--------------------------------------------------------------------===//
 104
 105 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
 106   const char *Out;
 107   switch (K) {
 108   case DDGEdge::EdgeKind::RegisterDefUse:
 109     Out = "def-use";
 110     break;
 111   case DDGEdge::EdgeKind::MemoryDependence:
 112     Out = "memory";
 113     break;
 114   case DDGEdge::EdgeKind::Rooted:
 115     Out = "rooted";
 116     break;
 117   case DDGEdge::EdgeKind::Unknown:
 118     Out = "??";
 119     break;
 120   }
 121   OS << Out;
 122   return OS;
 123 }
 124
 125 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
 126   OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
 127   return OS;
 128 }
 129
 130 //===--------------------------------------------------------------------===//
 131 // DataDependenceGraph implementation
 132 //===--------------------------------------------------------------------===//
 133 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
 134
 135 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
 136     : DependenceGraphInfo(F.getName().str(), D) {
 137   BasicBlockListType BBList;
 138   for (auto &BB : F.getBasicBlockList())
 139     BBList.push_back(&BB);
 140   DDGBuilder(*this, D, BBList).populate();
 141 }
 142
 143 DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
 144     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
 145                                 L.getHeader()->getName())
 146                               .str(),
 147                           D) {
 148   BasicBlockListType BBList;
 149   for (BasicBlock *BB : L.blocks())
 150     BBList.push_back(BB);
 151   DDGBuilder(*this, D, BBList).populate();
 152 }
 153
 154 DataDependenceGraph::~DataDependenceGraph() {
 155   for (auto *N : Nodes) {
 156     for (auto *E : *N)
 157       delete E;
 158     delete N;
 159   }
 160 }
 161
 162 bool DataDependenceGraph::addNode(DDGNode &N) {
 163   if (!DDGBase::addNode(N))
 164     return false;
 165
 166   // In general, if the root node is already created and linked, it is not safe
 167   // to add new nodes since they may be unreachable by the root.
 168   // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an
 169   // exception because they represent components that are already reachable by
 170   // root.
 171   assert(!Root && "Root node is already added. No more nodes can be added.");
 172   if (isa<RootDDGNode>(N))
 173     Root = &N;
 174
 175   return true;
 176 }
 177
 178 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
 179   for (auto *Node : G)
 180     OS << *Node << "\n";
 181   return OS;
 182 }
 183
 184 //===--------------------------------------------------------------------===//
 185 // DDG Analysis Passes
 186 //===--------------------------------------------------------------------===//
 187
 188 /// DDG as a loop pass.
 189 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
 190                                      LoopStandardAnalysisResults &AR) {
 191   Function *F = L.getHeader()->getParent();
 192   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
 193   return std::make_unique<DataDependenceGraph>(L, DI);
 194 }
 195 AnalysisKey DDGAnalysis::Key;
 196
 197 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
 198                                               LoopStandardAnalysisResults &AR,
 199                                               LPMUpdater &U) {
 200   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
 201   OS << *AM.getResult<DDGAnalysis>(L, AR);
 202   return PreservedAnalyses::all();
 203 }