1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators on machine functions.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "llvm/CodeGen/MachineDominators.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/ADT/SmallBitVector.h"
18 
19 using namespace llvm;
20 
21 namespace llvm {
22 template class DomTreeNodeBase<MachineBasicBlock>;
23 template class DominatorTreeBase<MachineBasicBlock>;
24 }
25 
26 char MachineDominatorTree::ID = 0;
27 
28 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
29                 "MachineDominator Tree Construction", true, true)
30 
31 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
32 
getAnalysisUsage(AnalysisUsage & AU) const33 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
34   AU.setPreservesAll();
35   MachineFunctionPass::getAnalysisUsage(AU);
36 }
37 
runOnMachineFunction(MachineFunction & F)38 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
39   CriticalEdgesToSplit.clear();
40   NewBBs.clear();
41   DT->recalculate(F);
42 
43   return false;
44 }
45 
MachineDominatorTree()46 MachineDominatorTree::MachineDominatorTree()
47     : MachineFunctionPass(ID) {
48   initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
49   DT = new DominatorTreeBase<MachineBasicBlock>(false);
50 }
51 
~MachineDominatorTree()52 MachineDominatorTree::~MachineDominatorTree() {
53   delete DT;
54 }
55 
releaseMemory()56 void MachineDominatorTree::releaseMemory() {
57   DT->releaseMemory();
58 }
59 
print(raw_ostream & OS,const Module *) const60 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
61   DT->print(OS);
62 }
63 
applySplitCriticalEdges() const64 void MachineDominatorTree::applySplitCriticalEdges() const {
65   // Bail out early if there is nothing to do.
66   if (CriticalEdgesToSplit.empty())
67     return;
68 
69   // For each element in CriticalEdgesToSplit, remember whether or not element
70   // is the new immediate domminator of its successor. The mapping is done by
71   // index, i.e., the information for the ith element of CriticalEdgesToSplit is
72   // the ith element of IsNewIDom.
73   SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
74   size_t Idx = 0;
75 
76   // Collect all the dominance properties info, before invalidating
77   // the underlying DT.
78   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
79     // Update dominator information.
80     MachineBasicBlock *Succ = Edge.ToBB;
81     MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
82 
83     for (MachineBasicBlock *PredBB : Succ->predecessors()) {
84       if (PredBB == Edge.NewBB)
85         continue;
86       // If we are in this situation:
87       // FromBB1        FromBB2
88       //    +              +
89       //   + +            + +
90       //  +   +          +   +
91       // ...  Split1  Split2 ...
92       //           +   +
93       //            + +
94       //             +
95       //            Succ
96       // Instead of checking the domiance property with Split2, we check it with
97       // FromBB2 since Split2 is still unknown of the underlying DT structure.
98       if (NewBBs.count(PredBB)) {
99         assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
100                                            "critical edge split has more "
101                                            "than one predecessor!");
102         PredBB = *PredBB->pred_begin();
103       }
104       if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
105         IsNewIDom[Idx] = false;
106         break;
107       }
108     }
109     ++Idx;
110   }
111 
112   // Now, update DT with the collected dominance properties info.
113   Idx = 0;
114   for (CriticalEdge &Edge : CriticalEdgesToSplit) {
115     // We know FromBB dominates NewBB.
116     MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
117 
118     // If all the other predecessors of "Succ" are dominated by "Succ" itself
119     // then the new block is the new immediate dominator of "Succ". Otherwise,
120     // the new block doesn't dominate anything.
121     if (IsNewIDom[Idx])
122       DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
123     ++Idx;
124   }
125   NewBBs.clear();
126   CriticalEdgesToSplit.clear();
127 }
128