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