LLVM 19.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"
21
22using namespace llvm;
23
24namespace llvm {
25// Always verify dominfo if expensive checking is enabled.
26#ifdef EXPENSIVE_CHECKS
27bool VerifyMachineDomInfo = true;
28#else
30#endif
31} // namespace llvm
32
34 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
35 cl::desc("Verify machine dominator info (time consuming)"));
36
37namespace llvm {
39template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
40}
41
43
45 "MachineDominator Tree Construction", true, true)
46
48
49void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
50 AU.setPreservesAll();
52}
53
55 calculate(F);
56 return false;
57}
58
60 CriticalEdgesToSplit.clear();
61 NewBBs.clear();
62 DT.reset(new DomTreeBase<MachineBasicBlock>());
63 DT->recalculate(F);
64}
65
69}
70
72 CriticalEdgesToSplit.clear();
73 DT.reset(nullptr);
74}
75
77 if (DT && VerifyMachineDomInfo)
79 errs() << "MachineDominatorTree verification failed\n";
80 abort();
81 }
82}
83
85 if (DT)
86 DT->print(OS);
87}
88
89void MachineDominatorTree::applySplitCriticalEdges() const {
90 // Bail out early if there is nothing to do.
91 if (CriticalEdgesToSplit.empty())
92 return;
93
94 // For each element in CriticalEdgesToSplit, remember whether or not element
95 // is the new immediate domminator of its successor. The mapping is done by
96 // index, i.e., the information for the ith element of CriticalEdgesToSplit is
97 // the ith element of IsNewIDom.
98 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
99 size_t Idx = 0;
100
101 // Collect all the dominance properties info, before invalidating
102 // the underlying DT.
103 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
104 // Update dominator information.
105 MachineBasicBlock *Succ = Edge.ToBB;
106 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
107
108 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
109 if (PredBB == Edge.NewBB)
110 continue;
111 // If we are in this situation:
112 // FromBB1 FromBB2
113 // + +
114 // + + + +
115 // + + + +
116 // ... Split1 Split2 ...
117 // + +
118 // + +
119 // +
120 // Succ
121 // Instead of checking the domiance property with Split2, we check it with
122 // FromBB2 since Split2 is still unknown of the underlying DT structure.
123 if (NewBBs.count(PredBB)) {
124 assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
125 "critical edge split has more "
126 "than one predecessor!");
127 PredBB = *PredBB->pred_begin();
128 }
129 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
130 IsNewIDom[Idx] = false;
131 break;
132 }
133 }
134 ++Idx;
135 }
136
137 // Now, update DT with the collected dominance properties info.
138 Idx = 0;
139 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
140 // We know FromBB dominates NewBB.
141 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
142
143 // If all the other predecessors of "Succ" are dominated by "Succ" itself
144 // then the new block is the new immediate dominator of "Succ". Otherwise,
145 // the new block doesn't dominate anything.
146 if (IsNewIDom[Idx])
147 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
148 ++Idx;
149 }
150 NewBBs.clear();
151 CriticalEdgesToSplit.clear();
152}
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
#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.
Represent the analysis usage information of a pass.
Base class for the actual dominator tree node.
Core dominator tree base class.
iterator_range< pred_iterator > predecessors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
void calculate(MachineFunction &F)
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
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...
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:470
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.
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
void initializeMachineDominatorTreePass(PassRegistry &)
bool VerifyMachineDomInfo