Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineDominators.cpp
Line
Count
Source (jump to first uncovered line)
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),
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
INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
40
                "MachineDominator Tree Construction", true, true)
41
42
char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
43
44
204k
void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
45
204k
  AU.setPreservesAll();
46
204k
  MachineFunctionPass::getAnalysisUsage(AU);
47
204k
}
48
49
3.66M
bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
50
3.66M
  CriticalEdgesToSplit.clear();
51
3.66M
  NewBBs.clear();
52
3.66M
  DT.reset(new DomTreeBase<MachineBasicBlock>());
53
3.66M
  DT->recalculate(F);
54
3.66M
  return false;
55
3.66M
}
56
57
MachineDominatorTree::MachineDominatorTree()
58
207k
    : MachineFunctionPass(ID) {
59
207k
  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
60
207k
}
61
62
3.66M
void MachineDominatorTree::releaseMemory() {
63
3.66M
  CriticalEdgesToSplit.clear();
64
3.66M
  DT.reset(nullptr);
65
3.66M
}
66
67
0
void MachineDominatorTree::verifyAnalysis() const {
68
0
  if (
DT && 0
VerifyMachineDomInfo0
)
69
0
    verifyDomTree();
70
0
}
71
72
0
void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
73
0
  if (DT)
74
0
    DT->print(OS);
75
0
}
76
77
40.4M
void MachineDominatorTree::applySplitCriticalEdges() const {
78
40.4M
  // Bail out early if there is nothing to do.
79
40.4M
  if (CriticalEdgesToSplit.empty())
80
40.3M
    return;
81
146k
82
146k
  // For each element in CriticalEdgesToSplit, remember whether or not element
83
146k
  // is the new immediate domminator of its successor. The mapping is done by
84
146k
  // index, i.e., the information for the ith element of CriticalEdgesToSplit is
85
146k
  // the ith element of IsNewIDom.
86
146k
  SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
87
146k
  size_t Idx = 0;
88
146k
89
146k
  // Collect all the dominance properties info, before invalidating
90
146k
  // the underlying DT.
91
467k
  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
92
467k
    // Update dominator information.
93
467k
    MachineBasicBlock *Succ = Edge.ToBB;
94
467k
    MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
95
467k
96
511k
    for (MachineBasicBlock *PredBB : Succ->predecessors()) {
97
511k
      if (PredBB == Edge.NewBB)
98
36.5k
        continue;
99
474k
      // If we are in this situation:
100
474k
      // FromBB1        FromBB2
101
474k
      //    +              +
102
474k
      //   + +            + +
103
474k
      //  +   +          +   +
104
474k
      // ...  Split1  Split2 ...
105
474k
      //           +   +
106
474k
      //            + +
107
474k
      //             +
108
474k
      //            Succ
109
474k
      // Instead of checking the domiance property with Split2, we check it with
110
474k
      // FromBB2 since Split2 is still unknown of the underlying DT structure.
111
474k
      
if (474k
NewBBs.count(PredBB)474k
) {
112
36.9k
        assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
113
36.9k
                                           "critical edge split has more "
114
36.9k
                                           "than one predecessor!");
115
36.9k
        PredBB = *PredBB->pred_begin();
116
36.9k
      }
117
474k
      if (
!DT->dominates(SuccDTNode, DT->getNode(PredBB))474k
) {
118
443k
        IsNewIDom[Idx] = false;
119
443k
        break;
120
443k
      }
121
467k
    }
122
467k
    ++Idx;
123
467k
  }
124
146k
125
146k
  // Now, update DT with the collected dominance properties info.
126
146k
  Idx = 0;
127
467k
  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
128
467k
    // We know FromBB dominates NewBB.
129
467k
    MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
130
467k
131
467k
    // If all the other predecessors of "Succ" are dominated by "Succ" itself
132
467k
    // then the new block is the new immediate dominator of "Succ". Otherwise,
133
467k
    // the new block doesn't dominate anything.
134
467k
    if (IsNewIDom[Idx])
135
23.9k
      DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
136
467k
    ++Idx;
137
467k
  }
138
40.4M
  NewBBs.clear();
139
40.4M
  CriticalEdgesToSplit.clear();
140
40.4M
}
141
142
0
void MachineDominatorTree::verifyDomTree() const {
143
0
  if (!DT)
144
0
    return;
145
0
  MachineFunction &F = *getRoot()->getParent();
146
0
147
0
  DomTreeBase<MachineBasicBlock> OtherDT;
148
0
  OtherDT.recalculate(F);
149
0
  if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
150
0
      
DT->compare(OtherDT)0
) {
151
0
    errs() << "MachineDominatorTree is not up to date!\nComputed:\n";
152
0
    DT->print(errs());
153
0
    errs() << "\nActual:\n";
154
0
    OtherDT.print(errs());
155
0
    abort();
156
0
  }
157
0
}