1 //===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements simple dominator construction algorithms for finding
11 // forward dominators on machine functions.
13 //===----------------------------------------------------------------------===//
15 #include "llvm/CodeGen/MachineDominators.h"
16 #include "llvm/CodeGen/Passes.h"
17 #include "llvm/ADT/SmallBitVector.h"
18 #include "llvm/Support/CommandLine.h"
22 // Always verify dominfo if expensive checking is enabled.
23 #ifdef EXPENSIVE_CHECKS
24 static bool VerifyMachineDomInfo = true;
26 static bool VerifyMachineDomInfo = false;
28 static cl::opt<bool, true> VerifyMachineDomInfoX(
29 "verify-machine-dom-info", cl::location(VerifyMachineDomInfo),
30 cl::desc("Verify machine dominator info (time consuming)"));
33 template class DomTreeNodeBase<MachineBasicBlock>;
34 template class DominatorTreeBase<MachineBasicBlock>;
37 char MachineDominatorTree::ID = 0;
39 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
40 "MachineDominator Tree Construction", true, true)
42 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
44 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
46 MachineFunctionPass::getAnalysisUsage(AU);
49 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
50 CriticalEdgesToSplit.clear();
57 MachineDominatorTree::MachineDominatorTree()
58 : MachineFunctionPass(ID) {
59 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
60 DT = new DominatorTreeBase<MachineBasicBlock>(false);
63 MachineDominatorTree::~MachineDominatorTree() {
67 void MachineDominatorTree::releaseMemory() {
71 void MachineDominatorTree::verifyAnalysis() const {
72 if (VerifyMachineDomInfo)
76 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
80 void MachineDominatorTree::applySplitCriticalEdges() const {
81 // Bail out early if there is nothing to do.
82 if (CriticalEdgesToSplit.empty())
85 // For each element in CriticalEdgesToSplit, remember whether or not element
86 // is the new immediate domminator of its successor. The mapping is done by
87 // index, i.e., the information for the ith element of CriticalEdgesToSplit is
88 // the ith element of IsNewIDom.
89 SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
92 // Collect all the dominance properties info, before invalidating
94 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
95 // Update dominator information.
96 MachineBasicBlock *Succ = Edge.ToBB;
97 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
99 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
100 if (PredBB == Edge.NewBB)
102 // If we are in this situation:
107 // ... Split1 Split2 ...
112 // Instead of checking the domiance property with Split2, we check it with
113 // FromBB2 since Split2 is still unknown of the underlying DT structure.
114 if (NewBBs.count(PredBB)) {
115 assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
116 "critical edge split has more "
117 "than one predecessor!");
118 PredBB = *PredBB->pred_begin();
120 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
121 IsNewIDom[Idx] = false;
128 // Now, update DT with the collected dominance properties info.
130 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
131 // We know FromBB dominates NewBB.
132 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
134 // If all the other predecessors of "Succ" are dominated by "Succ" itself
135 // then the new block is the new immediate dominator of "Succ". Otherwise,
136 // the new block doesn't dominate anything.
138 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
142 CriticalEdgesToSplit.clear();
145 void MachineDominatorTree::verifyDomTree() const {
146 MachineFunction &F = *getRoot()->getParent();
148 MachineDominatorTree OtherDT;
149 OtherDT.DT->recalculate(F);
150 if (compare(OtherDT)) {
151 errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
152 print(errs(), nullptr);
153 errs() << "\nActual:\n";
154 OtherDT.print(errs(), nullptr);