/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Analysis/DominanceFrontier.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- 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 the DominanceFrontier class, which calculate and holds the |
11 | | // dominance frontier for a function. |
12 | | // |
13 | | // This should be considered deprecated, don't add any more uses of this data |
14 | | // structure. |
15 | | // |
16 | | //===----------------------------------------------------------------------===// |
17 | | |
18 | | #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H |
19 | | #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H |
20 | | |
21 | | #include "llvm/ADT/GraphTraits.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 | 3.77k | DominanceFrontierBase() = default; llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::DominanceFrontierBase() Line | Count | Source | 55 | 801 | DominanceFrontierBase() = default; |
llvm::DominanceFrontierBase<llvm::BasicBlock, false>::DominanceFrontierBase() Line | Count | Source | 55 | 2.97k | 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, true>::getRoot() const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::getRoot() const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::getRoot() const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::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::MachineBasicBlock, false>::isPostDominator() const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::isPostDominator() const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::isPostDominator() const |
71 | | |
72 | 40.1k | void releaseMemory() { |
73 | 40.1k | Frontiers.clear(); |
74 | 40.1k | } llvm::DominanceFrontierBase<llvm::BasicBlock, false>::releaseMemory() Line | Count | Source | 72 | 36.6k | void releaseMemory() { | 73 | 36.6k | Frontiers.clear(); | 74 | 36.6k | } |
Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::releaseMemory() Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::releaseMemory() llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::releaseMemory() Line | Count | Source | 72 | 3.43k | void releaseMemory() { | 73 | 3.43k | Frontiers.clear(); | 74 | 3.43k | } |
|
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, true>::begin() Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::begin() Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::begin() Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::begin() |
81 | 2 | const_iterator begin() const { return Frontiers.begin(); } Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::begin() const 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, 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 | 9.47k | const_iterator end() const { return Frontiers.end(); } llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::end() const Line | Count | Source | 83 | 9.47k | 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 | 22.2k | 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 | 22.2k | 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 | 9.47k | const_iterator find(BlockT *B) const { return Frontiers.find(B); } Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::MachineBasicBlock, true>::find(llvm::MachineBasicBlock*) const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, true>::find(llvm::BasicBlock*) const Unexecuted instantiation: llvm::DominanceFrontierBase<llvm::BasicBlock, false>::find(llvm::BasicBlock*) const llvm::DominanceFrontierBase<llvm::MachineBasicBlock, false>::find(llvm::MachineBasicBlock*) const Line | Count | Source | 85 | 9.47k | const_iterator find(BlockT *B) const { return Frontiers.find(B); } |
|
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::MachineBasicBlock, true>::addBasicBlock(llvm::MachineBasicBlock*, std::__1::set<llvm::MachineBasicBlock*, std::__1::less<llvm::MachineBasicBlock*>, std::__1::allocator<llvm::MachineBasicBlock*> > 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::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::MachineBasicBlock, false>::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 | 20.0k | void analyze(DomTreeT &DT) { |
133 | 20.0k | assert(DT.getRoots().size() == 1 && |
134 | 20.0k | "Only one entry block for forward domfronts!"); |
135 | 20.0k | this->Roots = {DT.getRoot()}; |
136 | 20.0k | calculate(DT, DT[this->Roots[0]]); |
137 | 20.0k | } llvm::ForwardDominanceFrontierBase<llvm::BasicBlock>::analyze(llvm::DominatorTreeBase<llvm::BasicBlock, false>&) Line | Count | Source | 132 | 18.3k | void analyze(DomTreeT &DT) { | 133 | 18.3k | assert(DT.getRoots().size() == 1 && | 134 | 18.3k | "Only one entry block for forward domfronts!"); | 135 | 18.3k | this->Roots = {DT.getRoot()}; | 136 | 18.3k | calculate(DT, DT[this->Roots[0]]); | 137 | 18.3k | } |
llvm::ForwardDominanceFrontierBase<llvm::MachineBasicBlock>::analyze(llvm::DominatorTreeBase<llvm::MachineBasicBlock, false>&) Line | Count | Source | 132 | 1.71k | void analyze(DomTreeT &DT) { | 133 | 1.71k | assert(DT.getRoots().size() == 1 && | 134 | 1.71k | "Only one entry block for forward domfronts!"); | 135 | 1.71k | this->Roots = {DT.getRoot()}; | 136 | 1.71k | calculate(DT, DT[this->Roots[0]]); | 137 | 1.71k | } |
|
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 | 18.3k | 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 | | /// \brief 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 | | /// \brief Provide the result type for this analysis pass. |
191 | | using Result = DominanceFrontier; |
192 | | |
193 | | /// \brief Run the analysis pass over a function and produce a dominator tree. |
194 | | DominanceFrontier run(Function &F, FunctionAnalysisManager &AM); |
195 | | }; |
196 | | |
197 | | /// \brief 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 |