Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineDominators.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MachineDominators.cpp - Machine Dominator Calculation --------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements simple dominator construction algorithms for finding
10
// forward dominators on machine functions.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/MachineDominators.h"
15
#include "llvm/ADT/SmallBitVector.h"
16
#include "llvm/CodeGen/Passes.h"
17
#include "llvm/Support/CommandLine.h"
18
19
using namespace llvm;
20
21
// Always verify dominfo if expensive checking is enabled.
22
#ifdef EXPENSIVE_CHECKS
23
static bool VerifyMachineDomInfo = true;
24
#else
25
static bool VerifyMachineDomInfo = false;
26
#endif
27
static cl::opt<bool, true> VerifyMachineDomInfoX(
28
    "verify-machine-dom-info", cl::location(VerifyMachineDomInfo), cl::Hidden,
29
    cl::desc("Verify machine dominator info (time consuming)"));
30
31
namespace llvm {
32
template class DomTreeNodeBase<MachineBasicBlock>;
33
template class DominatorTreeBase<MachineBasicBlock, false>; // DomTreeBase
34
}
35
36
char MachineDominatorTree::ID = 0;
37
38
INITIALIZE_PASS(MachineDominatorTree, "machinedomtree",
39
                "MachineDominator Tree Construction", true, true)
40
41
char &llvm::MachineDominatorsID = MachineDominatorTree::ID;
42
43
180k
void MachineDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const {
44
180k
  AU.setPreservesAll();
45
180k
  MachineFunctionPass::getAnalysisUsage(AU);
46
180k
}
47
48
2.40M
bool MachineDominatorTree::runOnMachineFunction(MachineFunction &F) {
49
2.40M
  CriticalEdgesToSplit.clear();
50
2.40M
  NewBBs.clear();
51
2.40M
  DT.reset(new DomTreeBase<MachineBasicBlock>());
52
2.40M
  DT->recalculate(F);
53
2.40M
  return false;
54
2.40M
}
55
56
MachineDominatorTree::MachineDominatorTree()
57
398k
    : MachineFunctionPass(ID) {
58
398k
  initializeMachineDominatorTreePass(*PassRegistry::getPassRegistry());
59
398k
}
60
61
2.39M
void MachineDominatorTree::releaseMemory() {
62
2.39M
  CriticalEdgesToSplit.clear();
63
2.39M
  DT.reset(nullptr);
64
2.39M
}
65
66
0
void MachineDominatorTree::verifyAnalysis() const {
67
0
  if (DT && VerifyMachineDomInfo) {
68
0
    MachineFunction &F = *getRoot()->getParent();
69
0
70
0
    DomTreeBase<MachineBasicBlock> OtherDT;
71
0
    OtherDT.recalculate(F);
72
0
    if (getRootNode()->getBlock() != OtherDT.getRootNode()->getBlock() ||
73
0
        DT->compare(OtherDT)) {
74
0
      errs() << "MachineDominatorTree for function " << F.getName()
75
0
            << " is not up to date!\nComputed:\n";
76
0
      DT->print(errs());
77
0
      errs() << "\nActual:\n";
78
0
      OtherDT.print(errs());
79
0
      abort();
80
0
    }
81
0
  }
82
0
}
83
84
0
void MachineDominatorTree::print(raw_ostream &OS, const Module*) const {
85
0
  if (DT)
86
0
    DT->print(OS);
87
0
}
88
89
33.8M
void MachineDominatorTree::applySplitCriticalEdges() const {
90
33.8M
  // Bail out early if there is nothing to do.
91
33.8M
  if (CriticalEdgesToSplit.empty())
92
33.7M
    return;
93
80.5k
94
80.5k
  // For each element in CriticalEdgesToSplit, remember whether or not element
95
80.5k
  // is the new immediate domminator of its successor. The mapping is done by
96
80.5k
  // index, i.e., the information for the ith element of CriticalEdgesToSplit is
97
80.5k
  // the ith element of IsNewIDom.
98
80.5k
  SmallBitVector IsNewIDom(CriticalEdgesToSplit.size(), true);
99
80.5k
  size_t Idx = 0;
100
80.5k
101
80.5k
  // Collect all the dominance properties info, before invalidating
102
80.5k
  // the underlying DT.
103
252k
  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
104
252k
    // Update dominator information.
105
252k
    MachineBasicBlock *Succ = Edge.ToBB;
106
252k
    MachineDomTreeNode *SuccDTNode = DT->getNode(Succ);
107
252k
108
284k
    for (MachineBasicBlock *PredBB : Succ->predecessors()) {
109
284k
      if (PredBB == Edge.NewBB)
110
27.5k
        continue;
111
256k
      // If we are in this situation:
112
256k
      // FromBB1        FromBB2
113
256k
      //    +              +
114
256k
      //   + +            + +
115
256k
      //  +   +          +   +
116
256k
      // ...  Split1  Split2 ...
117
256k
      //           +   +
118
256k
      //            + +
119
256k
      //             +
120
256k
      //            Succ
121
256k
      // Instead of checking the domiance property with Split2, we check it with
122
256k
      // FromBB2 since Split2 is still unknown of the underlying DT structure.
123
256k
      if (NewBBs.count(PredBB)) {
124
57.3k
        assert(PredBB->pred_size() == 1 && "A basic block resulting from a "
125
57.3k
                                           "critical edge split has more "
126
57.3k
                                           "than one predecessor!");
127
57.3k
        PredBB = *PredBB->pred_begin();
128
57.3k
      }
129
256k
      if (!DT->dominates(SuccDTNode, DT->getNode(PredBB))) {
130
231k
        IsNewIDom[Idx] = false;
131
231k
        break;
132
231k
      }
133
256k
    }
134
252k
    ++Idx;
135
252k
  }
136
80.5k
137
80.5k
  // Now, update DT with the collected dominance properties info.
138
80.5k
  Idx = 0;
139
252k
  for (CriticalEdge &Edge : CriticalEdgesToSplit) {
140
252k
    // We know FromBB dominates NewBB.
141
252k
    MachineDomTreeNode *NewDTNode = DT->addNewBlock(Edge.NewBB, Edge.FromBB);
142
252k
143
252k
    // If all the other predecessors of "Succ" are dominated by "Succ" itself
144
252k
    // then the new block is the new immediate dominator of "Succ". Otherwise,
145
252k
    // the new block doesn't dominate anything.
146
252k
    if (IsNewIDom[Idx])
147
21.0k
      DT->changeImmediateDominator(DT->getNode(Edge.ToBB), NewDTNode);
148
252k
    ++Idx;
149
252k
  }
150
80.5k
  NewBBs.clear();
151
80.5k
  CriticalEdgesToSplit.clear();
152
80.5k
}