LLVM  15.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"
17 #include "llvm/InitializePasses.h"
18 #include "llvm/Pass.h"
19 #include "llvm/PassRegistry.h"
21 
22 using namespace llvm;
23 
24 namespace llvm {
25 // Always verify dominfo if expensive checking is enabled.
26 #ifdef EXPENSIVE_CHECKS
27 bool VerifyMachineDomInfo = true;
28 #else
29 bool VerifyMachineDomInfo = false;
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 
37 namespace llvm {
39 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
40 }
41 
43 
44 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
45  "MachineDominator Tree Construction", true, true)
46 
48 
49 void 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 
89 void 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 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::VerifyMachineDomInfo
bool VerifyMachineDomInfo
Definition: MachineDominators.cpp:29
llvm::cl::location
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:447
Pass.h
VerifyMachineDomInfoX
static cl::opt< bool, true > VerifyMachineDomInfoX("verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden, cl::desc("Verify machine dominator info (time consuming)"))
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::errs
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
Definition: raw_ostream.cpp:893
PassRegistry.h
llvm::MachineDominatorTree::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: MachineDominators.cpp:54
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::SmallBitVector
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
Definition: SmallBitVector.h:35
CommandLine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
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::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
Passes.h
llvm::cl::opt
Definition: CommandLine.h:1392
llvm::MachineDominatorTree::print
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
Definition: MachineDominators.cpp:84
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::MachineBasicBlock::predecessors
iterator_range< pred_iterator > predecessors()
Definition: MachineBasicBlock.h:358
llvm::MachineFunction
Definition: MachineFunction.h:241
llvm::MachineDominatorTree::MachineDominatorTree
MachineDominatorTree()
Definition: MachineDominators.cpp:66
llvm::initializeMachineDominatorTreePass
void initializeMachineDominatorTreePass(PassRegistry &)
llvm::DominatorTreeBase
Core dominator tree base class.
Definition: LoopInfo.h:65
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::MachineDominatorTree::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: MachineDominators.cpp:76
llvm::DominatorTreeBase::VerificationLevel::Basic
@ Basic
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::MachineDominatorTree::calculate
void calculate(MachineFunction &F)
Definition: MachineDominators.cpp:59
SmallBitVector.h
llvm::MachineDominatorsID
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
abort
*Add support for compiling functions in both ARM and Thumb then taking the smallest *Add support for compiling individual basic blocks in thumb when in a larger ARM function This can be used for presumed cold like paths to abort(failure path of asserts)
llvm::cl::desc
Definition: CommandLine.h:405
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::MachineDominatorTree::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MachineDominators.cpp:71
InitializePasses.h
MachineDominators.h