1 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines classes mirroring those in llvm/Analysis/Dominators.h,
10 // but for target-specific code rather than target-independent IR.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
15 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
17 #include "llvm/ADT/SmallSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/CodeGen/MachineBasicBlock.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/Support/GenericDomTree.h"
23 #include "llvm/Support/GenericDomTreeConstruction.h"
31 inline void DominatorTreeBase
<MachineBasicBlock
, false>::addRoot(
32 MachineBasicBlock
*MBB
) {
33 this->Roots
.push_back(MBB
);
36 extern template class DomTreeNodeBase
<MachineBasicBlock
>;
37 extern template class DominatorTreeBase
<MachineBasicBlock
, false>; // DomTree
38 extern template class DominatorTreeBase
<MachineBasicBlock
, true>; // PostDomTree
40 using MachineDomTreeNode
= DomTreeNodeBase
<MachineBasicBlock
>;
42 //===-------------------------------------
43 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
44 /// compute a normal dominator tree.
46 class MachineDominatorTree
: public MachineFunctionPass
{
47 using DomTreeT
= DomTreeBase
<MachineBasicBlock
>;
49 /// Helper structure used to hold all the basic blocks
50 /// involved in the split of a critical edge.
52 MachineBasicBlock
*FromBB
;
53 MachineBasicBlock
*ToBB
;
54 MachineBasicBlock
*NewBB
;
57 /// Pile up all the critical edges to be split.
58 /// The splitting of a critical edge is local and thus, it is possible
59 /// to apply several of those changes at the same time.
60 mutable SmallVector
<CriticalEdge
, 32> CriticalEdgesToSplit
;
62 /// Remember all the basic blocks that are inserted during
64 /// Invariant: NewBBs == all the basic blocks contained in the NewBB
65 /// field of all the elements of CriticalEdgesToSplit.
66 /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
67 /// such as BB == elt.NewBB.
68 mutable SmallSet
<MachineBasicBlock
*, 32> NewBBs
;
70 /// The DominatorTreeBase that is used to compute a normal dominator tree.
71 std::unique_ptr
<DomTreeT
> DT
;
73 /// Apply all the recorded critical edges to the DT.
74 /// This updates the underlying DT information in a way that uses
75 /// the fast query path of DT as much as possible.
77 /// \post CriticalEdgesToSplit.empty().
78 void applySplitCriticalEdges() const;
81 static char ID
; // Pass ID, replacement for typeid
83 MachineDominatorTree();
86 if (!DT
) DT
.reset(new DomTreeT());
87 applySplitCriticalEdges();
91 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
93 /// getRoots - Return the root blocks of the current CFG. This may include
94 /// multiple blocks if we are computing post dominators. For forward
95 /// dominators, this will always be a single block (the entry node).
97 const SmallVectorImpl
<MachineBasicBlock
*> &getRoots() const {
98 applySplitCriticalEdges();
99 return DT
->getRoots();
102 MachineBasicBlock
*getRoot() const {
103 applySplitCriticalEdges();
104 return DT
->getRoot();
107 MachineDomTreeNode
*getRootNode() const {
108 applySplitCriticalEdges();
109 return DT
->getRootNode();
112 bool runOnMachineFunction(MachineFunction
&F
) override
;
114 bool dominates(const MachineDomTreeNode
*A
,
115 const MachineDomTreeNode
*B
) const {
116 applySplitCriticalEdges();
117 return DT
->dominates(A
, B
);
120 bool dominates(const MachineBasicBlock
*A
, const MachineBasicBlock
*B
) const {
121 applySplitCriticalEdges();
122 return DT
->dominates(A
, B
);
125 // dominates - Return true if A dominates B. This performs the
126 // special checks necessary if A and B are in the same basic block.
127 bool dominates(const MachineInstr
*A
, const MachineInstr
*B
) const {
128 applySplitCriticalEdges();
129 const MachineBasicBlock
*BBA
= A
->getParent(), *BBB
= B
->getParent();
130 if (BBA
!= BBB
) return DT
->dominates(BBA
, BBB
);
132 // Loop through the basic block until we find A or B.
133 MachineBasicBlock::const_iterator I
= BBA
->begin();
134 for (; &*I
!= A
&& &*I
!= B
; ++I
)
140 bool properlyDominates(const MachineDomTreeNode
*A
,
141 const MachineDomTreeNode
*B
) const {
142 applySplitCriticalEdges();
143 return DT
->properlyDominates(A
, B
);
146 bool properlyDominates(const MachineBasicBlock
*A
,
147 const MachineBasicBlock
*B
) const {
148 applySplitCriticalEdges();
149 return DT
->properlyDominates(A
, B
);
152 /// findNearestCommonDominator - Find nearest common dominator basic block
153 /// for basic block A and B. If there is no such block then return NULL.
154 MachineBasicBlock
*findNearestCommonDominator(MachineBasicBlock
*A
,
155 MachineBasicBlock
*B
) {
156 applySplitCriticalEdges();
157 return DT
->findNearestCommonDominator(A
, B
);
160 MachineDomTreeNode
*operator[](MachineBasicBlock
*BB
) const {
161 applySplitCriticalEdges();
162 return DT
->getNode(BB
);
165 /// getNode - return the (Post)DominatorTree node for the specified basic
166 /// block. This is the same as using operator[] on this class.
168 MachineDomTreeNode
*getNode(MachineBasicBlock
*BB
) const {
169 applySplitCriticalEdges();
170 return DT
->getNode(BB
);
173 /// addNewBlock - Add a new node to the dominator tree information. This
174 /// creates a new node as a child of DomBB dominator node,linking it into
175 /// the children list of the immediate dominator.
176 MachineDomTreeNode
*addNewBlock(MachineBasicBlock
*BB
,
177 MachineBasicBlock
*DomBB
) {
178 applySplitCriticalEdges();
179 return DT
->addNewBlock(BB
, DomBB
);
182 /// changeImmediateDominator - This method is used to update the dominator
183 /// tree information when a node's immediate dominator changes.
185 void changeImmediateDominator(MachineBasicBlock
*N
,
186 MachineBasicBlock
*NewIDom
) {
187 applySplitCriticalEdges();
188 DT
->changeImmediateDominator(N
, NewIDom
);
191 void changeImmediateDominator(MachineDomTreeNode
*N
,
192 MachineDomTreeNode
*NewIDom
) {
193 applySplitCriticalEdges();
194 DT
->changeImmediateDominator(N
, NewIDom
);
197 /// eraseNode - Removes a node from the dominator tree. Block must not
198 /// dominate any other blocks. Removes node from its immediate dominator's
199 /// children list. Deletes dominator node associated with basic block BB.
200 void eraseNode(MachineBasicBlock
*BB
) {
201 applySplitCriticalEdges();
205 /// splitBlock - BB is split and now it has one successor. Update dominator
206 /// tree to reflect this change.
207 void splitBlock(MachineBasicBlock
* NewBB
) {
208 applySplitCriticalEdges();
209 DT
->splitBlock(NewBB
);
212 /// isReachableFromEntry - Return true if A is dominated by the entry
213 /// block of the function containing it.
214 bool isReachableFromEntry(const MachineBasicBlock
*A
) {
215 applySplitCriticalEdges();
216 return DT
->isReachableFromEntry(A
);
219 void releaseMemory() override
;
221 void verifyAnalysis() const override
;
223 void print(raw_ostream
&OS
, const Module
*) const override
;
225 /// Record that the critical edge (FromBB, ToBB) has been
226 /// split with NewBB.
227 /// This is best to use this method instead of directly update the
228 /// underlying information, because this helps mitigating the
229 /// number of time the DT information is invalidated.
231 /// \note Do not use this method with regular edges.
233 /// \note To benefit from the compile time improvement incurred by this
234 /// method, the users of this method have to limit the queries to the DT
235 /// interface between two edges splitting. In other words, they have to
236 /// pack the splitting of critical edges as much as possible.
237 void recordSplitCriticalEdge(MachineBasicBlock
*FromBB
,
238 MachineBasicBlock
*ToBB
,
239 MachineBasicBlock
*NewBB
) {
240 bool Inserted
= NewBBs
.insert(NewBB
).second
;
243 "A basic block inserted via edge splitting cannot appear twice");
244 CriticalEdgesToSplit
.push_back({FromBB
, ToBB
, NewBB
});
248 //===-------------------------------------
249 /// DominatorTree GraphTraits specialization so the DominatorTree can be
250 /// iterable by generic graph iterators.
253 template <class Node
, class ChildIterator
>
254 struct MachineDomTreeGraphTraitsBase
{
255 using NodeRef
= Node
*;
256 using ChildIteratorType
= ChildIterator
;
258 static NodeRef
getEntryNode(NodeRef N
) { return N
; }
259 static ChildIteratorType
child_begin(NodeRef N
) { return N
->begin(); }
260 static ChildIteratorType
child_end(NodeRef N
) { return N
->end(); }
263 template <class T
> struct GraphTraits
;
266 struct GraphTraits
<MachineDomTreeNode
*>
267 : public MachineDomTreeGraphTraitsBase
<MachineDomTreeNode
,
268 MachineDomTreeNode::iterator
> {};
271 struct GraphTraits
<const MachineDomTreeNode
*>
272 : public MachineDomTreeGraphTraitsBase
<const MachineDomTreeNode
,
273 MachineDomTreeNode::const_iterator
> {
276 template <> struct GraphTraits
<MachineDominatorTree
*>
277 : public GraphTraits
<MachineDomTreeNode
*> {
278 static NodeRef
getEntryNode(MachineDominatorTree
*DT
) {
279 return DT
->getRootNode();
283 } // end namespace llvm
285 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H