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