Coverage Report

Created: 2018-11-16 02:38

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