LLVM  10.0.0svn
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 
19 using namespace llvm;
20 
21 namespace llvm {
22 // Always verify dominfo if expensive checking is enabled.
23 #ifdef EXPENSIVE_CHECKS
24 bool VerifyMachineDomInfo = true;
25 #else
26 bool VerifyMachineDomInfo = false;
27 #endif
28 } // namespace llvm
29 
31  "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
32  cl::desc("Verify machine dominator info (time consuming)"));
33 
34 namespace llvm {
36 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
37 }
38 
40 
41 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
42  "MachineDominator Tree Construction", true, true)
43 
45 
46 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
47  AU.setPreservesAll();
49 }
50 
52  CriticalEdgesToSplit.clear();
53  NewBBs.clear();
54  DT.reset(new DomTreeBase<MachineBasicBlock>());
55  DT->recalculate(F);
56  return false;
57 }
58 
60  : MachineFunctionPass(ID) {
62 }
63 
65  CriticalEdgesToSplit.clear();
66  DT.reset(nullptr);
67 }
68 
70  if (DT && VerifyMachineDomInfo)
71  if (!DT->verify(DomTreeT::VerificationLevel::Basic)) {
72  errs() << "MachineDominatorTree verification failed\n";
73  abort();
74  }
75 }
76 
78  if (DT)
79  DT->print(OS);
80 }
81 
82 void MachineDominatorTree::applySplitCriticalEdges() const {
83  // Bail out early if there is nothing to do.
84  if (CriticalEdgesToSplit.empty())
85  return;
86 
87  // For each element in CriticalEdgesToSplit, remember whether or not element
88  // is the new immediate domminator of its successor. The mapping is done by
89  // index, i.e., the information for the ith element of CriticalEdgesToSplit is
90  // the ith element of IsNewIDom.
91  SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
92  size_t Idx = 0;
93 
94  // Collect all the dominance properties info, before invalidating
95  // the underlying DT.
96  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
97  // Update dominator information.
98  MachineBasicBlock *Succ = Edge.ToBB;
99  MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
100 
101  for (MachineBasicBlock *PredBB : Succ->predecessors()) {
102  if (PredBB == Edge.NewBB)
103  continue;
104  // If we are in this situation:
105  // FromBB1 FromBB2
106  // + +
107  // + + + +
108  // + + + +
109  // ... Split1 Split2 ...
110  // + +
111  // + +
112  // +
113  // Succ
114  // Instead of checking the domiance property with Split2, we check it with
115  // FromBB2 since Split2 is still unknown of the underlying DT structure.
116  if (NewBBs.count(PredBB)) {
117  assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
118  "critical edge split has more "
119  "than one predecessor!");
120  PredBB = *PredBB->pred_begin();
121  }
122  if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
123  IsNewIDom[Idx] = false;
124  break;
125  }
126  }
127  ++Idx;
128  }
129 
130  // Now, update DT with the collected dominance properties info.
131  Idx = 0;
132  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
133  // We know FromBB dominates NewBB.
134  MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
135 
136  // If all the other predecessors of "Succ" are dominated by "Succ" itself
137  // then the new block is the new immediate dominator of "Succ". Otherwise,
138  // the new block doesn't dominate anything.
139  if (IsNewIDom[Idx])
140  DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
141  ++Idx;
142  }
143  NewBBs.clear();
144  CriticalEdgesToSplit.clear();
145 }
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This is a &#39;bitvector&#39; (really, a variable-sized bit array), optimized for the case when the array is ...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:66
char & MachineDominatorsID
MachineDominators - This pass is a machine dominators analysis pass.
F(f)
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
static cl::opt< bool, true > VerifyMachineDomInfoX("verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden, cl::desc("Verify machine dominator info (time consuming)"))
Base class for the actual dominator tree node.
Definition: LiveRangeCalc.h:37
Core dominator tree base class.
Definition: LoopInfo.h:66
void initializeMachineDominatorTreePass(PassRegistry &)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Represent the analysis usage information of a pass.
iterator_range< pred_iterator > predecessors()
size_t size() const
Definition: SmallVector.h:52
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool VerifyMachineDomInfo
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
LocationClass< Ty > location(Ty &L)
Definition: CommandLine.h:448