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"
22 TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
23 TEMPLATE_INSTANTIATION(class DominatorTreeBase<MachineBasicBlock>);
26 char MachineDominatorTree::ID = 0;
28 INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
29 "MachineDominator Tree Construction", true, true)
31 char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
33 void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
35 MachineFunctionPass::getAnalysisUsage(AU);
38 bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
39 CriticalEdgesToSplit.clear();
46 MachineDominatorTree::MachineDominatorTree()
47 : MachineFunctionPass(ID) {
48 initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
49 DT = new DominatorTreeBase<MachineBasicBlock>(false);
52 MachineDominatorTree::~MachineDominatorTree() {
56 void MachineDominatorTree::releaseMemory() {
60 void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
64 void MachineDominatorTree::applySplitCriticalEdges() const {
65 // Bail out early if there is nothing to do.
66 if (CriticalEdgesToSplit.empty())
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);
76 // Collect all the dominance properties info, before invalidating
78 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
79 // Update dominator information.
80 MachineBasicBlock *Succ = Edge.ToBB;
81 MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
83 for (MachineBasicBlock *PredBB : Succ->predecessors()) {
84 if (PredBB == Edge.NewBB)
86 // If we are in this situation:
91 // ... Split1 Split2 ...
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();
104 if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
105 IsNewIDom[Idx] = false;
112 // Now, update DT with the collected dominance properties info.
114 for (CriticalEdge &Edge : CriticalEdgesToSplit) {
115 // We know FromBB dominates NewBB.
116 MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
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.
122 DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
126 CriticalEdgesToSplit.clear();