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 // Always verify dominfo if expensive checking is enabled.
22 #ifdef EXPENSIVE_CHECKS
23 static bool VerifyMachineDomInfo = true;
24 #else
25 static bool VerifyMachineDomInfo = false;
26 #endif
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)"));
30 
31 namespace llvm {
32 template class DomTreeNodeBase<MachineBasicBlock>;
33 template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
34 }
35 
36 char MachineDominatorTree::ID = 0;
37 
38 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
39                 "MachineDominator Tree Construction", true, true)
40 
41 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
42 
43 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
44   AU.setPreservesAll();
45   MachineFunctionPass::getAnalysisUsage(AU);
46 }
47 
48 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
49   CriticalEdgesToSplit.clear();
50   NewBBs.clear();
51   DT.reset(new DomTreeBase<MachineBasicBlock>());
52   DT->recalculate(F);
53   return false;
54 }
55 
56 MachineDominatorTree::MachineDominatorTree()
57     : MachineFunctionPass(ID) {
58   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
59 }
60 
61 void MachineDominatorTree::releaseMemory() {
62   CriticalEdgesToSplit.clear();
63   DT.reset(nullptr);
64 }
65 
66 void MachineDominatorTree::verifyAnalysis() const {
67   if (DT && VerifyMachineDomInfo) {
68     MachineFunction &F = *getRoot()->getParent();
69 
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";
76       DT->print(errs());
77       errs() << "\nActual:\n";
78       OtherDT.print(errs());
79       abort();
80     }
81   }
82 }
83 
84 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
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 }
153