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
19using namespace llvm;
20
21namespace llvm {
22template class DomTreeNodeBase<MachineBasicBlock>;
23template class DominatorTreeBase<MachineBasicBlock>;
24}
25
26char MachineDominatorTree::ID = 0;
27
28INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
29                "MachineDominator Tree Construction", true, true)
30
31char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
32
33void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
34  AU.setPreservesAll();
35  MachineFunctionPass::getAnalysisUsage(AU);
36}
37
38bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
39  CriticalEdgesToSplit.clear();
40  NewBBs.clear();
41  DT->recalculate(F);
42
43  return false;
44}
45
46MachineDominatorTree::MachineDominatorTree()
47    : MachineFunctionPass(ID) {
48  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
49  DT = new DominatorTreeBase<MachineBasicBlock>(false);
50}
51
52MachineDominatorTree::~MachineDominatorTree() {
53  delete DT;
54}
55
56void MachineDominatorTree::releaseMemory() {
57  DT->releaseMemory();
58}
59
60void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
61  DT->print(OS);
62}
63
64void 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