Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/IR/Dominators.h
Line
Count
Source (jump to first uncovered line)
1
//===- Dominators.h - Dominator Info 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 the DominatorTree class, which provides fast and efficient
10
// dominance queries.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_IR_DOMINATORS_H
15
#define LLVM_IR_DOMINATORS_H
16
17
#include "llvm/ADT/DenseMapInfo.h"
18
#include "llvm/ADT/DepthFirstIterator.h"
19
#include "llvm/ADT/GraphTraits.h"
20
#include "llvm/ADT/Hashing.h"
21
#include "llvm/IR/BasicBlock.h"
22
#include "llvm/IR/CFG.h"
23
#include "llvm/IR/PassManager.h"
24
#include "llvm/Pass.h"
25
#include "llvm/Support/GenericDomTree.h"
26
#include <utility>
27
28
namespace llvm {
29
30
class Function;
31
class Instruction;
32
class Module;
33
class raw_ostream;
34
35
extern template class DomTreeNodeBase<BasicBlock>;
36
extern template class DominatorTreeBase<BasicBlock, false>; // DomTree
37
extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree
38
39
extern template class cfg::Update<BasicBlock *>;
40
41
namespace DomTreeBuilder {
42
using BBDomTree = DomTreeBase<BasicBlock>;
43
using BBPostDomTree = PostDomTreeBase<BasicBlock>;
44
45
using BBUpdates = ArrayRef<llvm::cfg::Update<BasicBlock *>>;
46
47
extern template void Calculate<BBDomTree>(BBDomTree &DT);
48
extern template void CalculateWithUpdates<BBDomTree>(BBDomTree &DT,
49
                                                     BBUpdates U);
50
51
extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT);
52
53
extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
54
                                           BasicBlock *To);
55
extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT,
56
                                               BasicBlock *From,
57
                                               BasicBlock *To);
58
59
extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From,
60
                                           BasicBlock *To);
61
extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT,
62
                                               BasicBlock *From,
63
                                               BasicBlock *To);
64
65
extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates);
66
extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates);
67
68
extern template bool Verify<BBDomTree>(const BBDomTree &DT,
69
                                       BBDomTree::VerificationLevel VL);
70
extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT,
71
                                           BBPostDomTree::VerificationLevel VL);
72
}  // namespace DomTreeBuilder
73
74
using DomTreeNode = DomTreeNodeBase<BasicBlock>;
75
76
class BasicBlockEdge {
77
  const BasicBlock *Start;
78
  const BasicBlock *End;
79
80
public:
81
  BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) :
82
13.0M
    Start(Start_), End(End_) {}
83
84
  BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair)
85
146k
      : Start(Pair.first), End(Pair.second) {}
86
87
  BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair)
88
0
      : Start(Pair.first), End(Pair.second) {}
89
90
13.0M
  const BasicBlock *getStart() const {
91
13.0M
    return Start;
92
13.0M
  }
93
94
26.0M
  const BasicBlock *getEnd() const {
95
26.0M
    return End;
96
26.0M
  }
97
98
  /// Check if this is the only edge between Start and End.
99
  bool isSingleEdge() const;
100
};
101
102
template <> struct DenseMapInfo<BasicBlockEdge> {
103
  using BBInfo = DenseMapInfo<const BasicBlock *>;
104
105
  static unsigned getHashValue(const BasicBlockEdge *V);
106
107
5.96k
  static inline BasicBlockEdge getEmptyKey() {
108
5.96k
    return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey());
109
5.96k
  }
110
111
4.65k
  static inline BasicBlockEdge getTombstoneKey() {
112
4.65k
    return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey());
113
4.65k
  }
114
115
2.91k
  static unsigned getHashValue(const BasicBlockEdge &Edge) {
116
2.91k
    return hash_combine(BBInfo::getHashValue(Edge.getStart()),
117
2.91k
                        BBInfo::getHashValue(Edge.getEnd()));
118
2.91k
  }
119
120
33.7k
  static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) {
121
33.7k
    return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) &&
122
33.7k
           
BBInfo::isEqual(LHS.getEnd(), RHS.getEnd())29.5k
;
123
33.7k
  }
124
};
125
126
/// Concrete subclass of DominatorTreeBase that is used to compute a
127
/// normal dominator tree.
128
///
129
/// Definition: A block is said to be forward statically reachable if there is
130
/// a path from the entry of the function to the block.  A statically reachable
131
/// block may become statically unreachable during optimization.
132
///
133
/// A forward unreachable block may appear in the dominator tree, or it may
134
/// not.  If it does, dominance queries will return results as if all reachable
135
/// blocks dominate it.  When asking for a Node corresponding to a potentially
136
/// unreachable block, calling code must handle the case where the block was
137
/// unreachable and the result of getNode() is nullptr.
138
///
139
/// Generally, a block known to be unreachable when the dominator tree is
140
/// constructed will not be in the tree.  One which becomes unreachable after
141
/// the dominator tree is initially constructed may still exist in the tree,
142
/// even if the tree is properly updated. Calling code should not rely on the
143
/// preceding statements; this is stated only to assist human understanding.
144
class DominatorTree : public DominatorTreeBase<BasicBlock, false> {
145
 public:
146
  using Base = DominatorTreeBase<BasicBlock, false>;
147
148
1.15M
  DominatorTree() = default;
149
5.92k
  explicit DominatorTree(Function &F) { recalculate(F); }
150
52
  explicit DominatorTree(DominatorTree &DT, DomTreeBuilder::BBUpdates U) {
151
52
    recalculate(*DT.Parent, U);
152
52
  }
153
154
  /// Handle invalidation explicitly.
155
  bool invalidate(Function &F, const PreservedAnalyses &PA,
156
                  FunctionAnalysisManager::Invalidator &);
157
158
  // Ensure base-class overloads are visible.
159
  using Base::dominates;
160
161
  /// Return true if Def dominates a use in User.
162
  ///
163
  /// This performs the special checks necessary if Def and User are in the same
164
  /// basic block. Note that Def doesn't dominate a use in Def itself!
165
  bool dominates(const Instruction *Def, const Use &U) const;
166
  bool dominates(const Instruction *Def, const Instruction *User) const;
167
  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
168
169
  /// Return true if an edge dominates a use.
170
  ///
171
  /// If BBE is not a unique edge between start and end of the edge, it can
172
  /// never dominate the use.
173
  bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
174
  bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
175
176
  // Ensure base class overloads are visible.
177
  using Base::isReachableFromEntry;
178
179
  /// Provide an overload for a Use.
180
  bool isReachableFromEntry(const Use &U) const;
181
182
  // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`.
183
  void viewGraph(const Twine &Name, const Twine &Title);
184
  void viewGraph();
185
};
186
187
//===-------------------------------------
188
// DominatorTree GraphTraits specializations so the DominatorTree can be
189
// iterable by generic graph iterators.
190
191
template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
192
  using NodeRef = Node *;
193
  using ChildIteratorType = ChildIterator;
194
  using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>;
195
196
8.74M
  static NodeRef getEntryNode(NodeRef N) { return N; }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::getEntryNode(llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
196
1.56M
  static NodeRef getEntryNode(NodeRef N) { return N; }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::getEntryNode(llvm::DomTreeNodeBase<llvm::BasicBlock> const*)
Line
Count
Source
196
7.18M
  static NodeRef getEntryNode(NodeRef N) { return N; }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::VPBlockBase> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::VPBlockBase>* const*> >::getEntryNode(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*)
Line
Count
Source
196
25
  static NodeRef getEntryNode(NodeRef N) { return N; }
197
49.8M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::child_begin(llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
197
8.35M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::child_begin(llvm::DomTreeNodeBase<llvm::BasicBlock> const*)
Line
Count
Source
197
41.4M
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::VPBlockBase> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::VPBlockBase>* const*> >::child_begin(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*)
Line
Count
Source
197
111
  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
198
90.3M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::child_end(llvm::DomTreeNodeBase<llvm::BasicBlock>*)
Line
Count
Source
198
14.5M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::child_end(llvm::DomTreeNodeBase<llvm::BasicBlock> const*)
Line
Count
Source
198
75.7M
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::VPBlockBase> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::VPBlockBase>* const*> >::child_end(llvm::DomTreeNodeBase<llvm::VPBlockBase> const*)
Line
Count
Source
198
197
  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
199
200
  static nodes_iterator nodes_begin(NodeRef N) {
201
    return df_begin(getEntryNode(N));
202
  }
203
204
  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
205
};
206
207
template <>
208
struct GraphTraits<DomTreeNode *>
209
    : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
210
211
template <>
212
struct GraphTraits<const DomTreeNode *>
213
    : public DomTreeGraphTraitsBase<const DomTreeNode,
214
                                    DomTreeNode::const_iterator> {};
215
216
template <> struct GraphTraits<DominatorTree*>
217
  : public GraphTraits<DomTreeNode*> {
218
95.7k
  static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
219
220
333
  static nodes_iterator nodes_begin(DominatorTree *N) {
221
333
    return df_begin(getEntryNode(N));
222
333
  }
223
224
333
  static nodes_iterator nodes_end(DominatorTree *N) {
225
333
    return df_end(getEntryNode(N));
226
333
  }
227
};
228
229
/// Analysis pass which computes a \c DominatorTree.
230
class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> {
231
  friend AnalysisInfoMixin<DominatorTreeAnalysis>;
232
  static AnalysisKey Key;
233
234
public:
235
  /// Provide the result typedef for this analysis pass.
236
  using Result = DominatorTree;
237
238
  /// Run the analysis pass over a function and produce a dominator tree.
239
  DominatorTree run(Function &F, FunctionAnalysisManager &);
240
};
241
242
/// Printer pass for the \c DominatorTree.
243
class DominatorTreePrinterPass
244
    : public PassInfoMixin<DominatorTreePrinterPass> {
245
  raw_ostream &OS;
246
247
public:
248
  explicit DominatorTreePrinterPass(raw_ostream &OS);
249
250
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
251
};
252
253
/// Verifier pass for the \c DominatorTree.
254
struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> {
255
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
256
};
257
258
/// Legacy analysis pass which computes a \c DominatorTree.
259
class DominatorTreeWrapperPass : public FunctionPass {
260
  DominatorTree DT;
261
262
public:
263
  static char ID;
264
265
484k
  DominatorTreeWrapperPass() : FunctionPass(ID) {
266
484k
    initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
267
484k
  }
268
269
52.6M
  DominatorTree &getDomTree() { return DT; }
270
0
  const DominatorTree &getDomTree() const { return DT; }
271
272
  bool runOnFunction(Function &F) override;
273
274
  void verifyAnalysis() const override;
275
276
444k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
277
444k
    AU.setPreservesAll();
278
444k
  }
279
280
9.23M
  void releaseMemory() override { DT.releaseMemory(); }
281
282
  void print(raw_ostream &OS, const Module *M = nullptr) const override;
283
};
284
} // end namespace llvm
285
286
#endif // LLVM_IR_DOMINATORS_H