Coverage Report

Created: 2019-01-21 03:01

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/DominanceFrontier.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 DominanceFrontier class, which calculate and holds the
10
// dominance frontier for a function.
11
//
12
// This should be considered deprecated, don't add any more uses of this data
13
// structure.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H
18
#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
19
20
#include "llvm/ADT/GraphTraits.h"
21
#include "llvm/Config/llvm-config.h"
22
#include "llvm/IR/PassManager.h"
23
#include "llvm/Pass.h"
24
#include "llvm/Support/GenericDomTree.h"
25
#include <cassert>
26
#include <map>
27
#include <set>
28
#include <utility>
29
#include <vector>
30
31
namespace llvm {
32
33
class Function;
34
class raw_ostream;
35
36
//===----------------------------------------------------------------------===//
37
/// DominanceFrontierBase - Common base class for computing forward and inverse
38
/// dominance frontiers for a function.
39
///
40
template <class BlockT, bool IsPostDom>
41
class DominanceFrontierBase {
42
public:
43
  using DomSetType = std::set<BlockT *>;                // Dom set for a bb
44
  using DomSetMapType = std::map<BlockT *, DomSetType>; // Dom set map
45
46
protected:
47
  using BlockTraits = GraphTraits<BlockT *>;
48
49
  DomSetMapType Frontiers;
50
  // Postdominators can have multiple roots.
51
  SmallVector<BlockT *, IsPostDom ? 4 : 1> Roots;
52
  static constexpr bool IsPostDominators = IsPostDom;
53
54
public:
55
5.72k
  DominanceFrontierBase() = default;
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::DominanceFrontierBase()
Line
Count
Source
55
3.69k
  DominanceFrontierBase() = default;
llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::DominanceFrontierBase()
Line
Count
Source
55
2.03k
  DominanceFrontierBase() = default;
56
57
  /// getRoots - Return the root blocks of the current CFG.  This may include
58
  /// multiple blocks if we are computing post dominators.  For forward
59
  /// dominators, this will always be a single block (the entry node).
60
0
  const SmallVectorImpl<BlockT *> &getRoots() const { return Roots; }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::getRoots() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::getRoots() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::getRoots() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::getRoots() const
61
62
0
  BlockT *getRoot() const {
63
0
    assert(Roots.size() == 1 && "Should always have entry node!");
64
0
    return Roots[0];
65
0
  }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::getRoot() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::getRoot() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::getRoot() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::getRoot() const
66
67
  /// isPostDominator - Returns true if analysis based of postdoms
68
0
  bool isPostDominator() const {
69
0
    return IsPostDominators;
70
0
  }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::isPostDominator() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::isPostDominator() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::isPostDominator() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::isPostDominator() const
71
72
69.4k
  void releaseMemory() {
73
69.4k
    Frontiers.clear();
74
69.4k
  }
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::releaseMemory()
Line
Count
Source
72
48.9k
  void releaseMemory() {
73
48.9k
    Frontiers.clear();
74
48.9k
  }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::releaseMemory()
llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::releaseMemory()
Line
Count
Source
72
20.4k
  void releaseMemory() {
73
20.4k
    Frontiers.clear();
74
20.4k
  }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::releaseMemory()
75
76
  // Accessor interface:
77
  using iterator = typename DomSetMapType::iterator;
78
  using const_iterator = typename DomSetMapType::const_iterator;
79
80
0
  iterator begin() { return Frontiers.begin(); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::begin()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::begin()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::begin()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::begin()
81
2
  const_iterator begin() const { return Frontiers.begin(); }
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::begin() const
Line
Count
Source
81
2
  const_iterator begin() const { return Frontiers.begin(); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::begin() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::begin() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::begin() const
82
0
  iterator end() { return Frontiers.end(); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::end()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::end()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::end()
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::end()
83
21.6k
  const_iterator end() const { return Frontiers.end(); }
llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::end() const
Line
Count
Source
83
21.6k
  const_iterator end() const { return Frontiers.end(); }
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::end() const
Line
Count
Source
83
2
  const_iterator end() const { return Frontiers.end(); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::end() const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::end() const
84
24.6k
  iterator find(BlockT *B) { return Frontiers.find(B); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::find(llvm::MachineBasicBlock*)
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::find(llvm::BasicBlock*)
Line
Count
Source
84
24.6k
  iterator find(BlockT *B) { return Frontiers.find(B); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::find(llvm::BasicBlock*)
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::find(llvm::MachineBasicBlock*)
85
21.6k
  const_iterator find(BlockT *B) const { return Frontiers.find(B); }
llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::find(llvm::MachineBasicBlock*) const
Line
Count
Source
85
21.6k
  const_iterator find(BlockT *B) const { return Frontiers.find(B); }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::find(llvm::BasicBlock*) const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::find(llvm::BasicBlock*) const
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::find(llvm::MachineBasicBlock*) const
86
87
0
  iterator addBasicBlock(BlockT *BB, const DomSetType &frontier) {
88
0
    assert(find(BB) == end() && "Block already in DominanceFrontier!");
89
0
    return Frontiers.insert(std::make_pair(BB, frontier)).first;
90
0
  }
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::addBasicBlock(llvm::BasicBlock*, std::__1::set<llvm::BasicBlock*, std::__1::less<llvm::BasicBlock*>, std::__1::allocator<llvm::BasicBlock*> > const&)
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::addBasicBlock(llvm::BasicBlock*, std::__1::set<llvm::BasicBlock*, std::__1::less<llvm::BasicBlock*>, std::__1::allocator<llvm::BasicBlock*> > const&)
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::addBasicBlock(llvm::MachineBasicBlock*, std::__1::set<llvm::MachineBasicBlock*, std::__1::less<llvm::MachineBasicBlock*>, std::__1::allocator<llvm::MachineBasicBlock*> > const&)
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::addBasicBlock(llvm::MachineBasicBlock*, std::__1::set<llvm::MachineBasicBlock*, std::__1::less<llvm::MachineBasicBlock*>, std::__1::allocator<llvm::MachineBasicBlock*> > const&)
91
92
  /// removeBlock - Remove basic block BB's frontier.
93
  void removeBlock(BlockT *BB);
94
95
  void addToFrontier(iterator I, BlockT *Node);
96
97
  void removeFromFrontier(iterator I, BlockT *Node);
98
99
  /// compareDomSet - Return false if two domsets match. Otherwise
100
  /// return true;
101
  bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const;
102
103
  /// compare - Return true if the other dominance frontier base matches
104
  /// this dominance frontier base. Otherwise return false.
105
  bool compare(DominanceFrontierBase &Other) const;
106
107
  /// print - Convert to human readable form
108
  ///
109
  void print(raw_ostream &OS) const;
110
111
  /// dump - Dump the dominance frontier to dbgs().
112
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
113
  void dump() const;
114
#endif
115
};
116
117
//===-------------------------------------
118
/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
119
/// used to compute a forward dominator frontiers.
120
///
121
template <class BlockT>
122
class ForwardDominanceFrontierBase
123
    : public DominanceFrontierBase<BlockT, false> {
124
private:
125
  using BlockTraits = GraphTraits<BlockT *>;
126
127
public:
128
  using DomTreeT = DomTreeBase<BlockT>;
129
  using DomTreeNodeT = DomTreeNodeBase<BlockT>;
130
  using DomSetType = typename DominanceFrontierBase<BlockT, false>::DomSetType;
131
132
34.7k
  void analyze(DomTreeT &DT) {
133
34.7k
    assert(DT.getRoots().size() == 1 &&
134
34.7k
           "Only one entry block for forward domfronts!");
135
34.7k
    this->Roots = {DT.getRoot()};
136
34.7k
    calculate(DT, DT[this->Roots[0]]);
137
34.7k
  }
llvm::ForwardDominanceFrontierBase<llvm::BasicBlock>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false>&)
Line
Count
Source
132
24.5k
  void analyze(DomTreeT &DT) {
133
24.5k
    assert(DT.getRoots().size() == 1 &&
134
24.5k
           "Only one entry block for forward domfronts!");
135
24.5k
    this->Roots = {DT.getRoot()};
136
24.5k
    calculate(DT, DT[this->Roots[0]]);
137
24.5k
  }
llvm::ForwardDominanceFrontierBase<llvm::MachineBasicBlock>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>&)
Line
Count
Source
132
10.2k
  void analyze(DomTreeT &DT) {
133
10.2k
    assert(DT.getRoots().size() == 1 &&
134
10.2k
           "Only one entry block for forward domfronts!");
135
10.2k
    this->Roots = {DT.getRoot()};
136
10.2k
    calculate(DT, DT[this->Roots[0]]);
137
10.2k
  }
138
139
  const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node);
140
};
141
142
class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> {
143
public:
144
  using DomTreeT = DomTreeBase<BasicBlock>;
145
  using DomTreeNodeT = DomTreeNodeBase<BasicBlock>;
146
  using DomSetType = DominanceFrontierBase<BasicBlock, false>::DomSetType;
147
  using iterator = DominanceFrontierBase<BasicBlock, false>::iterator;
148
  using const_iterator =
149
      DominanceFrontierBase<BasicBlock, false>::const_iterator;
150
151
  /// Handle invalidation explicitly.
152
  bool invalidate(Function &F, const PreservedAnalyses &PA,
153
                  FunctionAnalysisManager::Invalidator &);
154
};
155
156
class DominanceFrontierWrapperPass : public FunctionPass {
157
  DominanceFrontier DF;
158
159
public:
160
  static char ID; // Pass ID, replacement for typeid
161
162
  DominanceFrontierWrapperPass();
163
164
24.4k
  DominanceFrontier &getDominanceFrontier() { return DF; }
165
0
  const DominanceFrontier &getDominanceFrontier() const { return DF;  }
166
167
  void releaseMemory() override;
168
169
  bool runOnFunction(Function &) override;
170
171
  void getAnalysisUsage(AnalysisUsage &AU) const override;
172
173
  void print(raw_ostream &OS, const Module * = nullptr) const override;
174
175
  void dump() const;
176
};
177
178
extern template class DominanceFrontierBase<BasicBlock, false>;
179
extern template class DominanceFrontierBase<BasicBlock, true>;
180
extern template class ForwardDominanceFrontierBase<BasicBlock>;
181
182
/// Analysis pass which computes a \c DominanceFrontier.
183
class DominanceFrontierAnalysis
184
    : public AnalysisInfoMixin<DominanceFrontierAnalysis> {
185
  friend AnalysisInfoMixin<DominanceFrontierAnalysis>;
186
187
  static AnalysisKey Key;
188
189
public:
190
  /// Provide the result type for this analysis pass.
191
  using Result = DominanceFrontier;
192
193
  /// Run the analysis pass over a function and produce a dominator tree.
194
  DominanceFrontier run(Function &F, FunctionAnalysisManager &AM);
195
};
196
197
/// Printer pass for the \c DominanceFrontier.
198
class DominanceFrontierPrinterPass
199
    : public PassInfoMixin<DominanceFrontierPrinterPass> {
200
  raw_ostream &OS;
201
202
public:
203
  explicit DominanceFrontierPrinterPass(raw_ostream &OS);
204
205
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
206
};
207
208
} // end namespace llvm
209
210
#endif // LLVM_ANALYSIS_DOMINANCEFRONTIER_H