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