LLVM  15.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"
25 #include <cassert>
26 #include <memory>
27 
28 namespace llvm {
29 class AnalysisUsage;
30 class MachineFunction;
31 class Module;
32 class raw_ostream;
33 
34 template <>
37  this->Roots.push_back(MBB);
38 }
39 
40 extern template class DomTreeNodeBase<MachineBasicBlock>;
41 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
42 extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
43 
46 
47 //===-------------------------------------
48 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
49 /// compute a normal dominator tree.
50 ///
52  /// Helper structure used to hold all the basic blocks
53  /// involved in the split of a critical edge.
54  struct CriticalEdge {
55  MachineBasicBlock *FromBB;
56  MachineBasicBlock *ToBB;
57  MachineBasicBlock *NewBB;
58  };
59 
60  /// Pile up all the critical edges to be split.
61  /// The splitting of a critical edge is local and thus, it is possible
62  /// to apply several of those changes at the same time.
63  mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
64 
65  /// Remember all the basic blocks that are inserted during
66  /// edge splitting.
67  /// Invariant: NewBBs == all the basic blocks contained in the NewBB
68  /// field of all the elements of CriticalEdgesToSplit.
69  /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
70  /// such as BB == elt.NewBB.
71  mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
72 
73  /// The DominatorTreeBase that is used to compute a normal dominator tree.
74  std::unique_ptr<MachineDomTree> DT;
75 
76  /// Apply all the recorded critical edges to the DT.
77  /// This updates the underlying DT information in a way that uses
78  /// the fast query path of DT as much as possible.
79  ///
80  /// \post CriticalEdgesToSplit.empty().
81  void applySplitCriticalEdges() const;
82 
83 public:
84  static char ID; // Pass ID, replacement for typeid
85 
88  calculate(MF);
89  }
90 
92  if (!DT)
93  DT.reset(new MachineDomTree());
94  applySplitCriticalEdges();
95  return *DT;
96  }
97 
98  void getAnalysisUsage(AnalysisUsage &AU) const override;
99 
101  applySplitCriticalEdges();
102  return DT->getRoot();
103  }
104 
106  applySplitCriticalEdges();
107  return DT->getRootNode();
108  }
109 
110  bool runOnMachineFunction(MachineFunction &F) override;
111 
112  void calculate(MachineFunction &F);
113 
115  const MachineDomTreeNode *B) const {
116  applySplitCriticalEdges();
117  return DT->dominates(A, B);
118  }
119 
122  applySplitCriticalEdges();
123  DT->getDescendants(A, Result);
124  }
125 
126  bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
127  applySplitCriticalEdges();
128  return DT->dominates(A, B);
129  }
130 
131  // dominates - Return true if A dominates B. This performs the
132  // special checks necessary if A and B are in the same basic block.
133  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
134  applySplitCriticalEdges();
135  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
136  if (BBA != BBB) return DT->dominates(BBA, BBB);
137 
138  // Loop through the basic block until we find A or B.
140  for (; &*I != A && &*I != B; ++I)
141  /*empty*/ ;
142 
143  return &*I == A;
144  }
145 
147  const MachineDomTreeNode *B) const {
148  applySplitCriticalEdges();
149  return DT->properlyDominates(A, B);
150  }
151 
153  const MachineBasicBlock *B) const {
154  applySplitCriticalEdges();
155  return DT->properlyDominates(A, B);
156  }
157 
158  /// findNearestCommonDominator - Find nearest common dominator basic block
159  /// for basic block A and B. If there is no such block then return NULL.
161  MachineBasicBlock *B) {
162  applySplitCriticalEdges();
163  return DT->findNearestCommonDominator(A, B);
164  }
165 
167  applySplitCriticalEdges();
168  return DT->getNode(BB);
169  }
170 
171  /// getNode - return the (Post)DominatorTree node for the specified basic
172  /// block. This is the same as using operator[] on this class.
173  ///
175  applySplitCriticalEdges();
176  return DT->getNode(BB);
177  }
178 
179  /// addNewBlock - Add a new node to the dominator tree information. This
180  /// creates a new node as a child of DomBB dominator node,linking it into
181  /// the children list of the immediate dominator.
183  MachineBasicBlock *DomBB) {
184  applySplitCriticalEdges();
185  return DT->addNewBlock(BB, DomBB);
186  }
187 
188  /// changeImmediateDominator - This method is used to update the dominator
189  /// tree information when a node's immediate dominator changes.
190  ///
192  MachineBasicBlock *NewIDom) {
193  applySplitCriticalEdges();
194  DT->changeImmediateDominator(N, NewIDom);
195  }
196 
198  MachineDomTreeNode *NewIDom) {
199  applySplitCriticalEdges();
200  DT->changeImmediateDominator(N, NewIDom);
201  }
202 
203  /// eraseNode - Removes a node from the dominator tree. Block must not
204  /// dominate any other blocks. Removes node from its immediate dominator's
205  /// children list. Deletes dominator node associated with basic block BB.
207  applySplitCriticalEdges();
208  DT->eraseNode(BB);
209  }
210 
211  /// splitBlock - BB is split and now it has one successor. Update dominator
212  /// tree to reflect this change.
214  applySplitCriticalEdges();
215  DT->splitBlock(NewBB);
216  }
217 
218  /// isReachableFromEntry - Return true if A is dominated by the entry
219  /// block of the function containing it.
221  applySplitCriticalEdges();
222  return DT->isReachableFromEntry(A);
223  }
224 
225  void releaseMemory() override;
226 
227  void verifyAnalysis() const override;
228 
229  void print(raw_ostream &OS, const Module*) const override;
230 
231  /// Record that the critical edge (FromBB, ToBB) has been
232  /// split with NewBB.
233  /// This is best to use this method instead of directly update the
234  /// underlying information, because this helps mitigating the
235  /// number of time the DT information is invalidated.
236  ///
237  /// \note Do not use this method with regular edges.
238  ///
239  /// \note To benefit from the compile time improvement incurred by this
240  /// method, the users of this method have to limit the queries to the DT
241  /// interface between two edges splitting. In other words, they have to
242  /// pack the splitting of critical edges as much as possible.
244  MachineBasicBlock *ToBB,
245  MachineBasicBlock *NewBB) {
246  bool Inserted = NewBBs.insert(NewBB).second;
247  (void)Inserted;
248  assert(Inserted &&
249  "A basic block inserted via edge splitting cannot appear twice");
250  CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
251  }
252 };
253 
254 //===-------------------------------------
255 /// DominatorTree GraphTraits specialization so the DominatorTree can be
256 /// iterable by generic graph iterators.
257 ///
258 
259 template <class Node, class ChildIterator>
261  using NodeRef = Node *;
262  using ChildIteratorType = ChildIterator;
263 
264  static NodeRef getEntryNode(NodeRef N) { return N; }
265  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
266  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
267 };
268 
269 template <class T> struct GraphTraits;
270 
271 template <>
275 };
276 
277 template <>
281 };
282 
283 template <> struct GraphTraits<MachineDominatorTree*>
286  return DT->getRootNode();
287  }
288 };
289 
290 } // end namespace llvm
291 
292 #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:160
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::MachineDominatorTree::changeImmediateDominator
void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode *NewIDom)
Definition: MachineDominators.h:197
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::MachineDominatorTree::dominates
bool dominates(const MachineInstr *A, const MachineInstr *B) const
Definition: MachineDominators.h:133
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:146
llvm::SmallVector< CriticalEdge, 32 >
llvm::GraphTraits< MachineDominatorTree * >::getEntryNode
static NodeRef getEntryNode(MachineDominatorTree *DT)
Definition: MachineDominators.h:285
llvm::MachineDomTreeGraphTraitsBase::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineDominators.h:265
llvm::MachineDominatorTree::getDescendants
void getDescendants(MachineBasicBlock *A, SmallVectorImpl< MachineBasicBlock * > &Result)
Definition: MachineDominators.h:120
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:136
llvm::MachineDominatorTree::getRootNode
MachineDomTreeNode * getRootNode() const
Definition: MachineDominators.h:105
llvm::MachineDominatorTree::dominates
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:114
llvm::MachineDomTree
DomTreeBase< MachineBasicBlock > MachineDomTree
Definition: MachineDominators.h:44
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MachineDominatorTree::addNewBlock
MachineDomTreeNode * addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB)
addNewBlock - Add a new node to the dominator tree information.
Definition: MachineDominators.h:182
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:220
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:191
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:54
llvm::MachineDominatorTree::getRoot
MachineBasicBlock * getRoot() const
Definition: MachineDominators.h:100
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::MachineDomTreeNode
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
Definition: LiveIntervalCalc.h:26
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineDomTreeGraphTraitsBase::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: MachineDominators.h:264
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:174
I
#define I(x, y, z)
Definition: MD5.cpp:58
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:262
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MachineFunction
Definition: MachineFunction.h:241
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:206
llvm::MachineDominatorTree::operator[]
MachineDomTreeNode * operator[](MachineBasicBlock *BB) const
Definition: MachineDominators.h:166
A
* A
Definition: README_ALTIVEC.txt:89
MachineInstrBundleIterator.h
llvm::MachineDominatorTree::splitBlock
void splitBlock(MachineBasicBlock *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: MachineDominators.h:213
Module
Machine Check Debug Module
Definition: MachineCheckDebugify.cpp:122
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
Node
Definition: ItaniumDemangle.h:155
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:182
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:126
GenericDomTree.h
llvm::MachineDominatorTree::MachineDominatorTree
MachineDominatorTree(MachineFunction &MF)
Definition: MachineDominators.h:87
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:243
GenericDomTreeConstruction.h
llvm::DomTreeNodeBase::const_iterator
typename SmallVector< DomTreeNodeBase *, 4 >::const_iterator const_iterator
Definition: GenericDomTree.h:73
SmallVector.h
llvm::MachineDominatorTree::getBase
MachineDomTree & getBase()
Definition: MachineDominators.h:91
llvm::MachineBasicBlock::begin
iterator begin()
Definition: MachineBasicBlock.h:277
N
#define N
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::GraphTraits< MachineDomTreeNode * >
Definition: MachineDominators.h:272
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:37
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:51
llvm::MachineDominatorTree::ID
static char ID
Definition: MachineDominators.h:84
llvm::MachineInstrBundleIterator< const MachineInstr >
llvm::MachineDomTreeGraphTraitsBase::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineDominators.h:266
llvm::MachineDomTreeGraphTraitsBase
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: MachineDominators.h:260
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
Definition: MachineDominators.h:152
SmallSet.h