LLVM  13.0.0git
MachineDominators.h
Go to the documentation of this file.
1 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==//
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 // This file defines classes mirroring those in llvm/Analysis/Dominators.h,
10 // but for target-specific code rather than target-independent IR.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
15 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
16 
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/SmallVector.h"
24 #include <cassert>
25 #include <memory>
26 
27 namespace llvm {
28 
29 template <>
32  this->Roots.push_back(MBB);
33 }
34 
35 extern template class DomTreeNodeBase<MachineBasicBlock>;
36 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
37 extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
38 
40 
41 //===-------------------------------------
42 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
43 /// compute a normal dominator tree.
44 ///
47 
48  /// Helper structure used to hold all the basic blocks
49  /// involved in the split of a critical edge.
50  struct CriticalEdge {
51  MachineBasicBlock *FromBB;
52  MachineBasicBlock *ToBB;
53  MachineBasicBlock *NewBB;
54  };
55 
56  /// Pile up all the critical edges to be split.
57  /// The splitting of a critical edge is local and thus, it is possible
58  /// to apply several of those changes at the same time.
59  mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
60 
61  /// Remember all the basic blocks that are inserted during
62  /// edge splitting.
63  /// Invariant: NewBBs == all the basic blocks contained in the NewBB
64  /// field of all the elements of CriticalEdgesToSplit.
65  /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
66  /// such as BB == elt.NewBB.
67  mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
68 
69  /// The DominatorTreeBase that is used to compute a normal dominator tree.
70  std::unique_ptr<DomTreeT> DT;
71 
72  /// Apply all the recorded critical edges to the DT.
73  /// This updates the underlying DT information in a way that uses
74  /// the fast query path of DT as much as possible.
75  ///
76  /// \post CriticalEdgesToSplit.empty().
77  void applySplitCriticalEdges() const;
78 
79 public:
80  static char ID; // Pass ID, replacement for typeid
81 
84  calculate(MF);
85  }
86 
88  if (!DT) DT.reset(new DomTreeT());
89  applySplitCriticalEdges();
90  return *DT;
91  }
92 
93  void getAnalysisUsage(AnalysisUsage &AU) const override;
94 
96  applySplitCriticalEdges();
97  return DT->getRoot();
98  }
99 
101  applySplitCriticalEdges();
102  return DT->getRootNode();
103  }
104 
105  bool runOnMachineFunction(MachineFunction &F) override;
106 
107  void calculate(MachineFunction &F);
108 
110  const MachineDomTreeNode *B) const {
111  applySplitCriticalEdges();
112  return DT->dominates(A, B);
113  }
114 
115  bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
116  applySplitCriticalEdges();
117  return DT->dominates(A, B);
118  }
119 
120  // dominates - Return true if A dominates B. This performs the
121  // special checks necessary if A and B are in the same basic block.
122  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
123  applySplitCriticalEdges();
124  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
125  if (BBA != BBB) return DT->dominates(BBA, BBB);
126 
127  // Loop through the basic block until we find A or B.
129  for (; &*I != A && &*I != B; ++I)
130  /*empty*/ ;
131 
132  return &*I == A;
133  }
134 
136  const MachineDomTreeNode *B) const {
137  applySplitCriticalEdges();
138  return DT->properlyDominates(A, B);
139  }
140 
142  const MachineBasicBlock *B) const {
143  applySplitCriticalEdges();
144  return DT->properlyDominates(A, B);
145  }
146 
147  /// findNearestCommonDominator - Find nearest common dominator basic block
148  /// for basic block A and B. If there is no such block then return NULL.
150  MachineBasicBlock *B) {
151  applySplitCriticalEdges();
152  return DT->findNearestCommonDominator(A, B);
153  }
154 
156  applySplitCriticalEdges();
157  return DT->getNode(BB);
158  }
159 
160  /// getNode - return the (Post)DominatorTree node for the specified basic
161  /// block. This is the same as using operator[] on this class.
162  ///
164  applySplitCriticalEdges();
165  return DT->getNode(BB);
166  }
167 
168  /// addNewBlock - Add a new node to the dominator tree information. This
169  /// creates a new node as a child of DomBB dominator node,linking it into
170  /// the children list of the immediate dominator.
172  MachineBasicBlock *DomBB) {
173  applySplitCriticalEdges();
174  return DT->addNewBlock(BB, DomBB);
175  }
176 
177  /// changeImmediateDominator - This method is used to update the dominator
178  /// tree information when a node's immediate dominator changes.
179  ///
181  MachineBasicBlock *NewIDom) {
182  applySplitCriticalEdges();
183  DT->changeImmediateDominator(N, NewIDom);
184  }
185 
187  MachineDomTreeNode *NewIDom) {
188  applySplitCriticalEdges();
189  DT->changeImmediateDominator(N, NewIDom);
190  }
191 
192  /// eraseNode - Removes a node from the dominator tree. Block must not
193  /// dominate any other blocks. Removes node from its immediate dominator's
194  /// children list. Deletes dominator node associated with basic block BB.
196  applySplitCriticalEdges();
197  DT->eraseNode(BB);
198  }
199 
200  /// splitBlock - BB is split and now it has one successor. Update dominator
201  /// tree to reflect this change.
203  applySplitCriticalEdges();
204  DT->splitBlock(NewBB);
205  }
206 
207  /// isReachableFromEntry - Return true if A is dominated by the entry
208  /// block of the function containing it.
210  applySplitCriticalEdges();
211  return DT->isReachableFromEntry(A);
212  }
213 
214  void releaseMemory() override;
215 
216  void verifyAnalysis() const override;
217 
218  void print(raw_ostream &OS, const Module*) const override;
219 
220  /// Record that the critical edge (FromBB, ToBB) has been
221  /// split with NewBB.
222  /// This is best to use this method instead of directly update the
223  /// underlying information, because this helps mitigating the
224  /// number of time the DT information is invalidated.
225  ///
226  /// \note Do not use this method with regular edges.
227  ///
228  /// \note To benefit from the compile time improvement incurred by this
229  /// method, the users of this method have to limit the queries to the DT
230  /// interface between two edges splitting. In other words, they have to
231  /// pack the splitting of critical edges as much as possible.
233  MachineBasicBlock *ToBB,
234  MachineBasicBlock *NewBB) {
235  bool Inserted = NewBBs.insert(NewBB).second;
236  (void)Inserted;
237  assert(Inserted &&
238  "A basic block inserted via edge splitting cannot appear twice");
239  CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
240  }
241 };
242 
243 //===-------------------------------------
244 /// DominatorTree GraphTraits specialization so the DominatorTree can be
245 /// iterable by generic graph iterators.
246 ///
247 
248 template <class Node, class ChildIterator>
250  using NodeRef = Node *;
251  using ChildIteratorType = ChildIterator;
252 
253  static NodeRef getEntryNode(NodeRef N) { return N; }
254  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
255  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
256 };
257 
258 template <class T> struct GraphTraits;
259 
260 template <>
264 };
265 
266 template <>
270 };
271 
272 template <> struct GraphTraits<MachineDominatorTree*>
275  return DT->getRootNode();
276  }
277 };
278 
279 } // end namespace llvm
280 
281 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H
llvm::MachineDominatorTree::findNearestCommonDominator
MachineBasicBlock * findNearestCommonDominator(MachineBasicBlock *A, MachineBasicBlock *B)
findNearestCommonDominator - Find nearest common dominator basic block for basic block A and B.
Definition: MachineDominators.h:149
MachineInstr.h
llvm
Definition: AllocatorList.h:23
llvm::MachineDominatorTree::changeImmediateDominator
void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode *NewIDom)
Definition: MachineDominators.h:186
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:147
llvm::MachineDominatorTree::dominates
bool dominates(const MachineInstr *A, const MachineInstr *B) const
Definition: MachineDominators.h:122
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:135
llvm::SmallVector< CriticalEdge, 32 >
llvm::GraphTraits< MachineDominatorTree * >::getEntryNode
static NodeRef getEntryNode(MachineDominatorTree *DT)
Definition: MachineDominators.h:274
llvm::MachineDomTreeGraphTraitsBase::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineDominators.h:254
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
MachineBasicBlock.h
llvm::DominatorTreeBase::addRoot
void addRoot(NodeT *BB)
Definition: GenericDomTree.h:816
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::MachineDominatorTree::getRootNode
MachineDomTreeNode * getRootNode() const
Definition: MachineDominators.h:100
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:109
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MachineDominatorTree::addNewBlock
MachineDomTreeNode * addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB)
addNewBlock - Add a new node to the dominator tree information.
Definition: MachineDominators.h:171
llvm::MachineDominatorTree::isReachableFromEntry
bool isReachableFromEntry(const MachineBasicBlock *A)
isReachableFromEntry - Return true if A is dominated by the entry block of the function containing it...
Definition: MachineDominators.h:209
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::MachineDominatorTree::changeImmediateDominator
void changeImmediateDominator(MachineBasicBlock *N, MachineBasicBlock *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
Definition: MachineDominators.h:180
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::MachineDominatorTree::getRoot
MachineBasicBlock * getRoot() const
Definition: MachineDominators.h:95
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineDomTreeNode
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
Definition: LiveIntervalCalc.h:26
llvm::MachineDominatorTree::getBase
DomTreeT & getBase()
Definition: MachineDominators.h:87
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineDomTreeGraphTraitsBase::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: MachineDominators.h:253
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::MachineDominatorTree::getNode
MachineDomTreeNode * getNode(MachineBasicBlock *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Definition: MachineDominators.h:163
I
#define I(x, y, z)
Definition: MD5.cpp:59
MachineFunctionPass.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MachineDomTreeGraphTraitsBase< const MachineDomTreeNode, MachineDomTreeNode::const_iterator >::ChildIteratorType
MachineDomTreeNode::const_iterator ChildIteratorType
Definition: MachineDominators.h:251
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::DominatorTreeBase::reset
void reset()
Definition: GenericDomTree.h:806
llvm::MachineDominatorTree::eraseNode
void eraseNode(MachineBasicBlock *BB)
eraseNode - Removes a node from the dominator tree.
Definition: MachineDominators.h:195
llvm::MachineDominatorTree::operator[]
MachineDomTreeNode * operator[](MachineBasicBlock *BB) const
Definition: MachineDominators.h:155
llvm::MachineDominatorTree::splitBlock
void splitBlock(MachineBasicBlock *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: MachineDominators.h:202
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
Node
Definition: ItaniumDemangle.h:114
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:180
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::MachineDominatorTree::dominates
bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
Definition: MachineDominators.h:115
GenericDomTree.h
llvm::MachineDominatorTree::MachineDominatorTree
MachineDominatorTree(MachineFunction &MF)
Definition: MachineDominators.h:83
llvm::MachineDominatorTree::recordSplitCriticalEdge
void recordSplitCriticalEdge(MachineBasicBlock *FromBB, MachineBasicBlock *ToBB, MachineBasicBlock *NewBB)
Record that the critical edge (FromBB, ToBB) has been split with NewBB.
Definition: MachineDominators.h:232
GenericDomTreeConstruction.h
llvm::DomTreeNodeBase::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
SmallVector.h
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:268
N
#define N
llvm::GraphTraits< MachineDomTreeNode * >
Definition: MachineDominators.h:261
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::MachineDominatorTree::ID
static char ID
Definition: MachineDominators.h:80
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::MachineDomTreeGraphTraitsBase::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineDominators.h:255
llvm::MachineDomTreeGraphTraitsBase
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: MachineDominators.h:249
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
Definition: MachineDominators.h:141
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38