LLVM 20.0.0git
MachineDominators.cpp
Go to the documentation of this file.
1//===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
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 implements simple dominator construction algorithms for finding
10// forward dominators on machine functions.
11//
12//===----------------------------------------------------------------------===//
13
16#include "llvm/CodeGen/Passes.h"
18#include "llvm/Pass.h"
19#include "llvm/PassRegistry.h"
22
23using namespace llvm;
24
25namespace llvm {
26// Always verify dominfo if expensive checking is enabled.
27#ifdef EXPENSIVE_CHECKS
28bool VerifyMachineDomInfo = true;
29#else
31#endif
32} // namespace llvm
33
35 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
36 cl::desc("Verify machine dominator info (time consuming)"));
37
38namespace llvm {
40template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
41
42namespace DomTreeBuilder {
43template void Calculate<MBBDomTree>(MBBDomTree &DT);
44template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U);
45
46template void InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
48
49template void DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
51
52template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &,
53 MBBDomTreeGraphDiff *);
54
55template bool Verify<MBBDomTree>(const MBBDomTree &DT,
56 MBBDomTree::VerificationLevel VL);
57} // namespace DomTreeBuilder
58}
59
63 // Check whether the analysis, all analyses on machine functions, or the
64 // machine function's CFG have been preserved.
66 return !PAC.preserved() &&
67 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
68 !PAC.preservedSet<CFGAnalyses>();
69}
70
71AnalysisKey MachineDominatorTreeAnalysis::Key;
72
76 return MachineDominatorTree(MF);
77}
78
82 OS << "MachineDominatorTree for machine function: " << MF.getName() << '\n';
85}
86
88
90 "MachineDominator Tree Construction", true, true)
91
96}
97
99 CriticalEdgesToSplit.clear();
100 NewBBs.clear();
101 recalculate(F);
102}
103
105
108 return false;
109}
110
112
114 if (VerifyMachineDomInfo && DT)
116 report_fatal_error("MachineDominatorTree verification failed!");
117}
118
120 const Module *) const {
121 if (DT)
122 DT->print(OS);
123}
124
125void MachineDominatorTree::applySplitCriticalEdges() const {
126 // Bail out early if there is nothing to do.
127 if (CriticalEdgesToSplit.empty())
128 return;
129
130 // For each element in CriticalEdgesToSplit, remember whether or not element
131 // is the new immediate domminator of its successor. The mapping is done by
132 // index, i.e., the information for the ith element of CriticalEdgesToSplit is
133 // the ith element of IsNewIDom.
134 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
135 size_t Idx = 0;
136
137 // Collect all the dominance properties info, before invalidating
138 // the underlying DT.
139 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
140 // Update dominator information.
141 MachineBasicBlock *Succ = Edge.ToBB;
142 MachineDomTreeNode *SuccDTNode = Base::getNode(Succ);
143
144 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
145 if (PredBB == Edge.NewBB)
146 continue;
147 // If we are in this situation:
148 // FromBB1 FromBB2
149 // + +
150 // + + + +
151 // + + + +
152 // ... Split1 Split2 ...
153 // + +
154 // + +
155 // +
156 // Succ
157 // Instead of checking the domiance property with Split2, we check it with
158 // FromBB2 since Split2 is still unknown of the underlying DT structure.
159 if (NewBBs.count(PredBB)) {
160 assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
161 "critical edge split has more "
162 "than one predecessor!");
163 PredBB = *PredBB->pred_begin();
164 }
165 if (!Base::dominates(SuccDTNode, Base::getNode(PredBB))) {
166 IsNewIDom[Idx] = false;
167 break;
168 }
169 }
170 ++Idx;
171 }
172
173 // Now, update DT with the collected dominance properties info.
174 Idx = 0;
175 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
176 // We know FromBB dominates NewBB.
177 MachineDomTreeNode *NewDTNode =
178 const_cast<MachineDominatorTree *>(this)->Base::addNewBlock(
179 Edge.NewBB, Edge.FromBB);
180
181 // If all the other predecessors of "Succ" are dominated by "Succ" itself
182 // then the new block is the new immediate dominator of "Succ". Otherwise,
183 // the new block doesn't dominate anything.
184 if (IsNewIDom[Idx])
186 Base::getNode(Edge.ToBB), NewDTNode);
187 ++Idx;
188 }
189 NewBBs.clear();
190 CriticalEdgesToSplit.clear();
191}
BlockVerifier::State From
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Generic dominator tree construction - this file provides routines to construct immediate dominator in...
#define F(x, y, z)
Definition: MD5.cpp:55
static cl::opt< bool, true > VerifyMachineDomInfoX("verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden, cl::desc("Verify machine dominator info (time consuming)"))
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements the SmallBitVector class.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:49
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:292
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
Base class for the actual dominator tree node.
Core dominator tree base class.
void changeImmediateDominator(DomTreeNodeBase< NodeT > *N, DomTreeNodeBase< NodeT > *NewIDom)
changeImmediateDominator - This method is used to update the dominator tree information when a node's...
DomTreeNodeBase< NodeT > * addNewBlock(NodeT *BB, NodeT *DomBB)
Add a new node to the dominator tree information.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
iterator_range< pred_iterator > predecessors()
Analysis pass which computes a MachineDominatorTree.
Result run(MachineFunction &MF, MachineFunctionAnalysisManager &)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
Analysis pass which computes a MachineDominatorTree.
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool invalidate(MachineFunction &, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
void calculate(MachineFunction &F)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:463
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:167
bool VerifyMachineDomInfo
void initializeMachineDominatorTreeWrapperPassPass(PassRegistry &)
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28