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 
14 #include "llvm/CodeGen/MachineDominators.h"
15 #include "llvm/ADT/SmallBitVector.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/Support/CommandLine.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 
30 static cl::opt<bool, true> VerifyMachineDomInfoX(
31     "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
32     cl::desc("Verify machine dominator info (time consuming)"));
33 
34 namespace llvm {
35 template class DomTreeNodeBase<MachineBasicBlock>;
36 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
37 }
38 
39 char MachineDominatorTree::ID = 0;
40 
41 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
42                 "MachineDominator Tree Construction", true, true)
43 
44 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
45 
46 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
47   AU.setPreservesAll();
48   MachineFunctionPass::getAnalysisUsage(AU);
49 }
50 
51 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
52   calculate(F);
53   return false;
54 }
55 
56 void MachineDominatorTree::calculate(MachineFunction &F) {
57   CriticalEdgesToSplit.clear();
58   NewBBs.clear();
59   DT.reset(new DomTreeBase<MachineBasicBlock>());
60   DT->recalculate(F);
61 }
62 
63 MachineDominatorTree::MachineDominatorTree()
64     : MachineFunctionPass(ID) {
65   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
66 }
67 
68 void MachineDominatorTree::releaseMemory() {
69   CriticalEdgesToSplit.clear();
70   DT.reset(nullptr);
71 }
72 
73 void MachineDominatorTree::verifyAnalysis() const {
74   if (DT && VerifyMachineDomInfo)
75     if (!DT->verify(DomTreeT::VerificationLevel::Basic)) {
76       errs() << "MachineDominatorTree verification failed\n";
77       abort();
78     }
79 }
80 
81 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
82   if (DT)
83     DT->print(OS);
84 }
85 
86 void MachineDominatorTree::applySplitCriticalEdges() const {
87   // Bail out early if there is nothing to do.
88   if (CriticalEdgesToSplit.empty())
89     return;
90 
91   // For each element in CriticalEdgesToSplit, remember whether or not element
92   // is the new immediate domminator of its successor. The mapping is done by
93   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
94   // the ith element of IsNewIDom.
95   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
96   size_t Idx = 0;
97 
98   // Collect all the dominance properties info, before invalidating
99   // the underlying DT.
100   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
101     // Update dominator information.
102     MachineBasicBlock *Succ = Edge.ToBB;
103     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
104 
105     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
106       if (PredBB == Edge.NewBB)
107         continue;
108       // If we are in this situation:
109       // FromBB1        FromBB2
110       //    +              +
111       //   + +            + +
112       //  +   +          +   +
113       // ...  Split1  Split2 ...
114       //           +   +
115       //            + +
116       //             +
117       //            Succ
118       // Instead of checking the domiance property with Split2, we check it with
119       // FromBB2 since Split2 is still unknown of the underlying DT structure.
120       if (NewBBs.count(PredBB)) {
121         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
122                                            "critical edge split has more "
123                                            "than one predecessor!");
124         PredBB = *PredBB->pred_begin();
125       }
126       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
127         IsNewIDom[Idx] = false;
128         break;
129       }
130     }
131     ++Idx;
132   }
133 
134   // Now, update DT with the collected dominance properties info.
135   Idx = 0;
136   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
137     // We know FromBB dominates NewBB.
138     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
139 
140     // If all the other predecessors of "Succ" are dominated by "Succ" itself
141     // then the new block is the new immediate dominator of "Succ". Otherwise,
142     // the new block doesn't dominate anything.
143     if (IsNewIDom[Idx])
144       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
145     ++Idx;
146   }
147   NewBBs.clear();
148   CriticalEdgesToSplit.clear();
149 }
150