LLVM  14.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 
117  applySplitCriticalEdges();
118  DT->getDescendants(A, Result);
119  }
120 
121  bool dominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const {
122  applySplitCriticalEdges();
123  return DT->dominates(A, B);
124  }
125 
126  // dominates - Return true if A dominates B. This performs the
127  // special checks necessary if A and B are in the same basic block.
128  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
129  applySplitCriticalEdges();
130  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
131  if (BBA != BBB) return DT->dominates(BBA, BBB);
132 
133  // Loop through the basic block until we find A or B.
135  for (; &*I != A && &*I != B; ++I)
136  /*empty*/ ;
137 
138  return &*I == A;
139  }
140 
142  const MachineDomTreeNode *B) const {
143  applySplitCriticalEdges();
144  return DT->properlyDominates(A, B);
145  }
146 
148  const MachineBasicBlock *B) const {
149  applySplitCriticalEdges();
150  return DT->properlyDominates(A, B);
151  }
152 
153  /// findNearestCommonDominator - Find nearest common dominator basic block
154  /// for basic block A and B. If there is no such block then return NULL.
156  MachineBasicBlock *B) {
157  applySplitCriticalEdges();
158  return DT->findNearestCommonDominator(A, B);
159  }
160 
162  applySplitCriticalEdges();
163  return DT->getNode(BB);
164  }
165 
166  /// getNode - return the (Post)DominatorTree node for the specified basic
167  /// block. This is the same as using operator[] on this class.
168  ///
170  applySplitCriticalEdges();
171  return DT->getNode(BB);
172  }
173 
174  /// addNewBlock - Add a new node to the dominator tree information. This
175  /// creates a new node as a child of DomBB dominator node,linking it into
176  /// the children list of the immediate dominator.
178  MachineBasicBlock *DomBB) {
179  applySplitCriticalEdges();
180  return DT->addNewBlock(BB, DomBB);
181  }
182 
183  /// changeImmediateDominator - This method is used to update the dominator
184  /// tree information when a node's immediate dominator changes.
185  ///
187  MachineBasicBlock *NewIDom) {
188  applySplitCriticalEdges();
189  DT->changeImmediateDominator(N, NewIDom);
190  }
191 
193  MachineDomTreeNode *NewIDom) {
194  applySplitCriticalEdges();
195  DT->changeImmediateDominator(N, NewIDom);
196  }
197 
198  /// eraseNode - Removes a node from the dominator tree. Block must not
199  /// dominate any other blocks. Removes node from its immediate dominator's
200  /// children list. Deletes dominator node associated with basic block BB.
202  applySplitCriticalEdges();
203  DT->eraseNode(BB);
204  }
205 
206  /// splitBlock - BB is split and now it has one successor. Update dominator
207  /// tree to reflect this change.
209  applySplitCriticalEdges();
210  DT->splitBlock(NewBB);
211  }
212 
213  /// isReachableFromEntry - Return true if A is dominated by the entry
214  /// block of the function containing it.
216  applySplitCriticalEdges();
217  return DT->isReachableFromEntry(A);
218  }
219 
220  void releaseMemory() override;
221 
222  void verifyAnalysis() const override;
223 
224  void print(raw_ostream &OS, const Module*) const override;
225 
226  /// Record that the critical edge (FromBB, ToBB) has been
227  /// split with NewBB.
228  /// This is best to use this method instead of directly update the
229  /// underlying information, because this helps mitigating the
230  /// number of time the DT information is invalidated.
231  ///
232  /// \note Do not use this method with regular edges.
233  ///
234  /// \note To benefit from the compile time improvement incurred by this
235  /// method, the users of this method have to limit the queries to the DT
236  /// interface between two edges splitting. In other words, they have to
237  /// pack the splitting of critical edges as much as possible.
239  MachineBasicBlock *ToBB,
240  MachineBasicBlock *NewBB) {
241  bool Inserted = NewBBs.insert(NewBB).second;
242  (void)Inserted;
243  assert(Inserted &&
244  "A basic block inserted via edge splitting cannot appear twice");
245  CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
246  }
247 };
248 
249 //===-------------------------------------
250 /// DominatorTree GraphTraits specialization so the DominatorTree can be
251 /// iterable by generic graph iterators.
252 ///
253 
254 template <class Node, class ChildIterator>
256  using NodeRef = Node *;
257  using ChildIteratorType = ChildIterator;
258 
259  static NodeRef getEntryNode(NodeRef N) { return N; }
260  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
261  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
262 };
263 
264 template <class T> struct GraphTraits;
265 
266 template <>
270 };
271 
272 template <>
276 };
277 
278 template <> struct GraphTraits<MachineDominatorTree*>
281  return DT->getRootNode();
282  }
283 };
284 
285 } // end namespace llvm
286 
287 #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:155
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::MachineDominatorTree::changeImmediateDominator
void changeImmediateDominator(MachineDomTreeNode *N, MachineDomTreeNode *NewIDom)
Definition: MachineDominators.h:192
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:128
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
Definition: MachineDominators.h:141
llvm::SmallVector< CriticalEdge, 32 >
llvm::GraphTraits< MachineDominatorTree * >::getEntryNode
static NodeRef getEntryNode(MachineDominatorTree *DT)
Definition: MachineDominators.h:280
llvm::MachineDomTreeGraphTraitsBase::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineDominators.h:260
llvm::MachineDominatorTree::getDescendants
void getDescendants(MachineBasicBlock *A, SmallVectorImpl< MachineBasicBlock * > &Result)
Definition: MachineDominators.h:115
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:177
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:215
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:186
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:53
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:259
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:169
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:257
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:234
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:201
llvm::MachineDominatorTree::operator[]
MachineDomTreeNode * operator[](MachineBasicBlock *BB) const
Definition: MachineDominators.h:161
llvm::MachineDominatorTree::splitBlock
void splitBlock(MachineBasicBlock *NewBB)
splitBlock - BB is split and now it has one successor.
Definition: MachineDominators.h:208
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
Node
Definition: ItaniumDemangle.h:235
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:121
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:238
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::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::GraphTraits< MachineDomTreeNode * >
Definition: MachineDominators.h:267
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:261
llvm::MachineDomTreeGraphTraitsBase
DominatorTree GraphTraits specialization so the DominatorTree can be iterable by generic graph iterat...
Definition: MachineDominators.h:255
llvm::MachineDominatorTree::properlyDominates
bool properlyDominates(const MachineBasicBlock *A, const MachineBasicBlock *B) const
Definition: MachineDominators.h:147
SmallSet.h
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37