1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
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 implements simple dominator construction algorithms for finding
10 // forward dominators on machine functions.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/CodeGen/MachineDominators.h"
15 #include "llvm/ADT/SmallBitVector.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/Support/CommandLine.h"
21 // Always verify dominfo if expensive checking is enabled.
22 #ifdef EXPENSIVE_CHECKS
23 static bool VerifyMachineDomInfo = true;
25 static bool VerifyMachineDomInfo = false;
27 static cl::opt<bool, true> VerifyMachineDomInfoX(
28 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
29 cl::desc("Verify machine dominator info (time consuming)"));
32 template class DomTreeNodeBase<MachineBasicBlock>;
33 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
36 char MachineDominatorTree::ID = 0;
38 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
39 "MachineDominator Tree Construction", true, true)
41 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
43 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
45 MachineFunctionPass::getAnalysisUsage(AU);
48 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
49 CriticalEdgesToSplit.clear();
51 DT.reset(new DomTreeBase<MachineBasicBlock>());
56 MachineDominatorTree::MachineDominatorTree()
57 : MachineFunctionPass(ID) {
58 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
61 void MachineDominatorTree::releaseMemory() {
62 CriticalEdgesToSplit.clear();
66 void MachineDominatorTree::verifyAnalysis() const {
67 if (DT && VerifyMachineDomInfo) {
68 MachineFunction &F = *getRoot()->getParent();
70 DomTreeBase<MachineBasicBlock> OtherDT;
71 OtherDT.recalculate(F);
72 if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
73 DT->compare(OtherDT)) {
74 errs() << "MachineDominatorTree for function " << F.getName()
75 << " is not up to date!\nComputed:\n";
77 errs() << "\nActual:\n";
78 OtherDT.print(errs());
84 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
89 void MachineDominatorTree::applySplitCriticalEdges() const {
90 // Bail out early if there is nothing to do.
91 if (CriticalEdgesToSplit.empty())
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);
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);
108 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
109 if (PredBB == Edge.NewBB)
111 // If we are in this situation:
116 // ... Split1 Split2 ...
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();
129 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
130 IsNewIDom[Idx] = false;
137 // Now, update DT with the collected dominance properties info.
139 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
140 // We know FromBB dominates NewBB.
141 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
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.
147 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
151 CriticalEdgesToSplit.clear();