Coverage Report

Created: 2019-02-15 18:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/MachineDominators.h
Line
Count
Source (jump to first uncovered line)
1
//==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==//
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 defines classes mirroring those in llvm/Analysis/Dominators.h,
10
// but for target-specific code rather than target-independent IR.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
15
#define LLVM_CODEGEN_MACHINEDOMINATORS_H
16
17
#include "llvm/ADT/SmallSet.h"
18
#include "llvm/ADT/SmallVector.h"
19
#include "llvm/CodeGen/MachineBasicBlock.h"
20
#include "llvm/CodeGen/MachineFunctionPass.h"
21
#include "llvm/CodeGen/MachineInstr.h"
22
#include "llvm/Support/GenericDomTree.h"
23
#include "llvm/Support/GenericDomTreeConstruction.h"
24
#include <cassert>
25
#include <memory>
26
#include <vector>
27
28
namespace llvm {
29
30
template <>
31
inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
32
0
    MachineBasicBlock *MBB) {
33
0
  this->Roots.push_back(MBB);
34
0
}
35
36
extern template class DomTreeNodeBase<MachineBasicBlock>;
37
extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
38
extern template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTree
39
40
using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
41
42
//===-------------------------------------
43
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
44
/// compute a normal dominator tree.
45
///
46
class MachineDominatorTree : public MachineFunctionPass {
47
  /// Helper structure used to hold all the basic blocks
48
  /// involved in the split of a critical edge.
49
  struct CriticalEdge {
50
    MachineBasicBlock *FromBB;
51
    MachineBasicBlock *ToBB;
52
    MachineBasicBlock *NewBB;
53
  };
54
55
  /// Pile up all the critical edges to be split.
56
  /// The splitting of a critical edge is local and thus, it is possible
57
  /// to apply several of those changes at the same time.
58
  mutable SmallVector<CriticalEdge, 32> CriticalEdgesToSplit;
59
60
  /// Remember all the basic blocks that are inserted during
61
  /// edge splitting.
62
  /// Invariant: NewBBs == all the basic blocks contained in the NewBB
63
  /// field of all the elements of CriticalEdgesToSplit.
64
  /// I.e., forall elt in CriticalEdgesToSplit, it exists BB in NewBBs
65
  /// such as BB == elt.NewBB.
66
  mutable SmallSet<MachineBasicBlock *, 32> NewBBs;
67
68
  /// The DominatorTreeBase that is used to compute a normal dominator tree
69
  std::unique_ptr<DomTreeBase<MachineBasicBlock>> DT;
70
71
  /// Apply all the recorded critical edges to the DT.
72
  /// This updates the underlying DT information in a way that uses
73
  /// the fast query path of DT as much as possible.
74
  ///
75
  /// \post CriticalEdgesToSplit.empty().
76
  void applySplitCriticalEdges() const;
77
78
public:
79
  static char ID; // Pass ID, replacement for typeid
80
81
  MachineDominatorTree();
82
83
2.86M
  DomTreeBase<MachineBasicBlock> &getBase() {
84
2.86M
    if (!DT) 
DT.reset(new DomTreeBase<MachineBasicBlock>())191k
;
85
2.86M
    applySplitCriticalEdges();
86
2.86M
    return *DT;
87
2.86M
  }
88
89
  void getAnalysisUsage(AnalysisUsage &AU) const override;
90
91
  /// getRoots -  Return the root blocks of the current CFG.  This may include
92
  /// multiple blocks if we are computing post dominators.  For forward
93
  /// dominators, this will always be a single block (the entry node).
94
  ///
95
0
  inline const SmallVectorImpl<MachineBasicBlock*> &getRoots() const {
96
0
    applySplitCriticalEdges();
97
0
    return DT->getRoots();
98
0
  }
99
100
3.33k
  inline MachineBasicBlock *getRoot() const {
101
3.33k
    applySplitCriticalEdges();
102
3.33k
    return DT->getRoot();
103
3.33k
  }
104
105
1.30M
  inline MachineDomTreeNode *getRootNode() const {
106
1.30M
    applySplitCriticalEdges();
107
1.30M
    return DT->getRootNode();
108
1.30M
  }
109
110
  bool runOnMachineFunction(MachineFunction &F) override;
111
112
  inline bool dominates(const MachineDomTreeNode* A,
113
616k
                        const MachineDomTreeNode* B) const {
114
616k
    applySplitCriticalEdges();
115
616k
    return DT->dominates(A, B);
116
616k
  }
117
118
  inline bool dominates(const MachineBasicBlock* A,
119
17.8M
                        const MachineBasicBlock* B) const {
120
17.8M
    applySplitCriticalEdges();
121
17.8M
    return DT->dominates(A, B);
122
17.8M
  }
123
124
  // dominates - Return true if A dominates B. This performs the
125
  // special checks necessary if A and B are in the same basic block.
126
31.4k
  bool dominates(const MachineInstr *A, const MachineInstr *B) const {
127
31.4k
    applySplitCriticalEdges();
128
31.4k
    const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
129
31.4k
    if (BBA != BBB) 
return DT->dominates(BBA, BBB)403
;
130
31.0k
131
31.0k
    // Loop through the basic block until we find A or B.
132
31.0k
    MachineBasicBlock::const_iterator I = BBA->begin();
133
4.38M
    for (; &*I != A && 
&*I != B4.37M
;
++I4.35M
)
134
4.35M
      /*empty*/ ;
135
31.0k
136
31.0k
    //if(!DT.IsPostDominators) {
137
31.0k
      // A dominates B if it is found first in the basic block.
138
31.0k
      return &*I == A;
139
31.0k
    //} else {
140
31.0k
    //  // A post-dominates B if B is found first in the basic block.
141
31.0k
    //  return &*I == B;
142
31.0k
    //}
143
31.0k
  }
144
145
  inline bool properlyDominates(const MachineDomTreeNode* A,
146
0
                                const MachineDomTreeNode* B) const {
147
0
    applySplitCriticalEdges();
148
0
    return DT->properlyDominates(A, B);
149
0
  }
150
151
  inline bool properlyDominates(const MachineBasicBlock* A,
152
13.7k
                                const MachineBasicBlock* B) const {
153
13.7k
    applySplitCriticalEdges();
154
13.7k
    return DT->properlyDominates(A, B);
155
13.7k
  }
156
157
  /// findNearestCommonDominator - Find nearest common dominator basic block
158
  /// for basic block A and B. If there is no such block then return NULL.
159
  inline MachineBasicBlock *findNearestCommonDominator(MachineBasicBlock *A,
160
124k
                                                       MachineBasicBlock *B) {
161
124k
    applySplitCriticalEdges();
162
124k
    return DT->findNearestCommonDominator(A, B);
163
124k
  }
164
165
1.63M
  inline MachineDomTreeNode *operator[](MachineBasicBlock *BB) const {
166
1.63M
    applySplitCriticalEdges();
167
1.63M
    return DT->getNode(BB);
168
1.63M
  }
169
170
  /// getNode - return the (Post)DominatorTree node for the specified basic
171
  /// block.  This is the same as using operator[] on this class.
172
  ///
173
5.59M
  inline MachineDomTreeNode *getNode(MachineBasicBlock *BB) const {
174
5.59M
    applySplitCriticalEdges();
175
5.59M
    return DT->getNode(BB);
176
5.59M
  }
177
178
  /// addNewBlock - Add a new node to the dominator tree information.  This
179
  /// creates a new node as a child of DomBB dominator node,linking it into
180
  /// the children list of the immediate dominator.
181
  inline MachineDomTreeNode *addNewBlock(MachineBasicBlock *BB,
182
44
                                         MachineBasicBlock *DomBB) {
183
44
    applySplitCriticalEdges();
184
44
    return DT->addNewBlock(BB, DomBB);
185
44
  }
186
187
  /// changeImmediateDominator - This method is used to update the dominator
188
  /// tree information when a node's immediate dominator changes.
189
  ///
190
  inline void changeImmediateDominator(MachineBasicBlock *N,
191
31
                                       MachineBasicBlock* NewIDom) {
192
31
    applySplitCriticalEdges();
193
31
    DT->changeImmediateDominator(N, NewIDom);
194
31
  }
195
196
  inline void changeImmediateDominator(MachineDomTreeNode *N,
197
2.21k
                                       MachineDomTreeNode* NewIDom) {
198
2.21k
    applySplitCriticalEdges();
199
2.21k
    DT->changeImmediateDominator(N, NewIDom);
200
2.21k
  }
201
202
  /// eraseNode - Removes a node from  the dominator tree. Block must not
203
  /// dominate any other blocks. Removes node from its immediate dominator's
204
  /// children list. Deletes dominator node associated with basic block BB.
205
11.3k
  inline void eraseNode(MachineBasicBlock *BB) {
206
11.3k
    applySplitCriticalEdges();
207
11.3k
    DT->eraseNode(BB);
208
11.3k
  }
209
210
  /// splitBlock - BB is split and now it has one successor. Update dominator
211
  /// tree to reflect this change.
212
0
  inline void splitBlock(MachineBasicBlock* NewBB) {
213
0
    applySplitCriticalEdges();
214
0
    DT->splitBlock(NewBB);
215
0
  }
216
217
  /// isReachableFromEntry - Return true if A is dominated by the entry
218
  /// block of the function containing it.
219
3.12M
  bool isReachableFromEntry(const MachineBasicBlock *A) {
220
3.12M
    applySplitCriticalEdges();
221
3.12M
    return DT->isReachableFromEntry(A);
222
3.12M
  }
223
224
  void releaseMemory() override;
225
226
  void verifyAnalysis() const override;
227
228
  void print(raw_ostream &OS, const Module*) const override;
229
230
  /// Record that the critical edge (FromBB, ToBB) has been
231
  /// split with NewBB.
232
  /// This is best to use this method instead of directly update the
233
  /// underlying information, because this helps mitigating the
234
  /// number of time the DT information is invalidated.
235
  ///
236
  /// \note Do not use this method with regular edges.
237
  ///
238
  /// \note To benefit from the compile time improvement incurred by this
239
  /// method, the users of this method have to limit the queries to the DT
240
  /// interface between two edges splitting. In other words, they have to
241
  /// pack the splitting of critical edges as much as possible.
242
  void recordSplitCriticalEdge(MachineBasicBlock *FromBB,
243
                              MachineBasicBlock *ToBB,
244
260k
                              MachineBasicBlock *NewBB) {
245
260k
    bool Inserted = NewBBs.insert(NewBB).second;
246
260k
    (void)Inserted;
247
260k
    assert(Inserted &&
248
260k
           "A basic block inserted via edge splitting cannot appear twice");
249
260k
    CriticalEdgesToSplit.push_back({FromBB, ToBB, NewBB});
250
260k
  }
251
};
252
253
//===-------------------------------------
254
/// DominatorTree GraphTraits specialization so the DominatorTree can be
255
/// iterable by generic graph iterators.
256
///
257
258
template <class Node, class ChildIterator>
259
struct MachineDomTreeGraphTraitsBase {
260
  using NodeRef = Node *;
261
  using ChildIteratorType = ChildIterator;
262
263
2.18M
  static NodeRef getEntryNode(NodeRef N) { return N; }
llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>* const*> >::getEntryNode(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*)
Line
Count
Source
263
2.18M
  static NodeRef getEntryNode(NodeRef N) { return N; }
Unexecuted instantiation: llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>**> >::getEntryNode(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
264
17.5M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>**> >::child_begin(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Line
Count
Source
264
6.16M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>* const*> >::child_begin(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*)
Line
Count
Source
264
11.3M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
265
31.9M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>**> >::child_end(llvm::DomTreeNodeBase<llvm::MachineBasicBlock>*)
Line
Count
Source
265
11.4M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
llvm::MachineDomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::MachineBasicBlock>* const*> >::child_end(llvm::DomTreeNodeBase<llvm::MachineBasicBlock> const*)
Line
Count
Source
265
20.5M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
266
};
267
268
template <class T> struct GraphTraits;
269
270
template <>
271
struct GraphTraits<MachineDomTreeNode *>
272
    : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
273
                                           MachineDomTreeNode::iterator> {};
274
275
template <>
276
struct GraphTraits<const MachineDomTreeNode *>
277
    : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
278
                                           MachineDomTreeNode::const_iterator> {
279
};
280
281
template <> struct GraphTraits<MachineDominatorTree*>
282
  : public GraphTraits<MachineDomTreeNode *> {
283
790k
  static NodeRef getEntryNode(MachineDominatorTree *DT) {
284
790k
    return DT->getRootNode();
285
790k
  }
286
};
287
288
} // end namespace llvm
289
290
#endif // LLVM_CODEGEN_MACHINEDOMINATORS_H