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::Unknown:
  50     Out = "??";
  51     break;
  52   }
  53   OS << Out;
  54   return OS;
  55 }
  56
  57 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
  58   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
  59   if (isa<SimpleDDGNode>(N)) {
  60     OS << " Instructions:\n";
  61     for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
  62       OS.indent(2) << *I << "\n";
  63   } else
  64     llvm_unreachable("unimplemented type of node");
  65
  66   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
  67   for (auto &E : N.getEdges())
  68     OS.indent(2) << *E;
  69   return OS;
  70 }
  71
  72 //===--------------------------------------------------------------------===//
  73 // SimpleDDGNode implementation
  74 //===--------------------------------------------------------------------===//
  75
  76 SimpleDDGNode::SimpleDDGNode(Instruction &I)
  77   : DDGNode(NodeKind::SingleInstruction), InstList() {
  78   assert(InstList.empty() && "Expected empty list.");
  79   InstList.push_back(&I);
  80 }
  81
  82 SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
  83     : DDGNode(N), InstList(N.InstList) {
  84   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
  85           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
  86          "constructing from invalid simple node.");
  87 }
  88
  89 SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
  90     : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
  91   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
  92           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
  93          "constructing from invalid simple node.");
  94 }
  95
  96 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
  97
  98 //===--------------------------------------------------------------------===//
  99 // DDGEdge implementation
 100 //===--------------------------------------------------------------------===//
 101
 102 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
 103   const char *Out;
 104   switch (K) {
 105   case DDGEdge::EdgeKind::RegisterDefUse:
 106     Out = "def-use";
 107     break;
 108   case DDGEdge::EdgeKind::MemoryDependence:
 109     Out = "memory";
 110     break;
 111   case DDGEdge::EdgeKind::Unknown:
 112     Out = "??";
 113     break;
 114   }
 115   OS << Out;
 116   return OS;
 117 }
 118
 119 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
 120   OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
 121   return OS;
 122 }
 123
 124 //===--------------------------------------------------------------------===//
 125 // DataDependenceGraph implementation
 126 //===--------------------------------------------------------------------===//
 127 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
 128
 129 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
 130     : DependenceGraphInfo(F.getName().str(), D) {
 131   BasicBlockListType BBList;
 132   for (auto &BB : F.getBasicBlockList())
 133     BBList.push_back(&BB);
 134   DDGBuilder(*this, D, BBList).populate();
 135 }
 136
 137 DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
 138     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
 139                                 L.getHeader()->getName())
 140                               .str(),
 141                           D) {
 142   BasicBlockListType BBList;
 143   for (BasicBlock *BB : L.blocks())
 144     BBList.push_back(BB);
 145   DDGBuilder(*this, D, BBList).populate();
 146 }
 147
 148 DataDependenceGraph::~DataDependenceGraph() {
 149   for (auto *N : Nodes) {
 150     for (auto *E : *N)
 151       delete E;
 152     delete N;
 153   }
 154 }
 155
 156 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
 157   for (auto *Node : G)
 158     OS << *Node << "\n";
 159   return OS;
 160 }
 161
 162 //===--------------------------------------------------------------------===//
 163 // DDG Analysis Passes
 164 //===--------------------------------------------------------------------===//
 165
 166 /// DDG as a loop pass.
 167 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
 168                                      LoopStandardAnalysisResults &AR) {
 169   Function *F = L.getHeader()->getParent();
 170   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
 171   return std::make_unique<DataDependenceGraph>(L, DI);
 172 }
 173 AnalysisKey DDGAnalysis::Key;
 174
 175 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
 176                                               LoopStandardAnalysisResults &AR,
 177                                               LPMUpdater &U) {
 178   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
 179   OS << *AM.getResult<DDGAnalysis>(L, AR);
 180   return PreservedAnalyses::all();
 181 }