/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/DomTreeUpdater.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- 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 DomTreeUpdater class, which provides a uniform way to |
10 | | // update dominator tree related data structures. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_ANALYSIS_DOMTREEUPDATER_H |
15 | | #define LLVM_ANALYSIS_DOMTREEUPDATER_H |
16 | | |
17 | | #include "llvm/Analysis/PostDominators.h" |
18 | | #include "llvm/IR/Dominators.h" |
19 | | #include "llvm/IR/Instructions.h" |
20 | | #include "llvm/IR/ValueHandle.h" |
21 | | #include "llvm/Support/GenericDomTree.h" |
22 | | #include <functional> |
23 | | #include <vector> |
24 | | |
25 | | namespace llvm { |
26 | | class DomTreeUpdater { |
27 | | public: |
28 | | enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; |
29 | | |
30 | | explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} |
31 | | DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) |
32 | 974k | : DT(&DT_), Strategy(Strategy_) {} |
33 | | DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) |
34 | 1.10M | : DT(DT_), Strategy(Strategy_) {} |
35 | | DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) |
36 | | : PDT(&PDT_), Strategy(Strategy_) {} |
37 | | DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) |
38 | 0 | : PDT(PDT_), Strategy(Strategy_) {} |
39 | | DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, |
40 | | UpdateStrategy Strategy_) |
41 | 46 | : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} |
42 | | DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, |
43 | | UpdateStrategy Strategy_) |
44 | 1.18M | : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} |
45 | | |
46 | 3.26M | ~DomTreeUpdater() { flush(); } |
47 | | |
48 | | /// Returns true if the current strategy is Lazy. |
49 | 2.66M | bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; |
50 | | |
51 | | /// Returns true if the current strategy is Eager. |
52 | | bool isEager() const { return Strategy == UpdateStrategy::Eager; }; |
53 | | |
54 | | /// Returns true if it holds a DominatorTree. |
55 | 4.10k | bool hasDomTree() const { return DT != nullptr; } |
56 | | |
57 | | /// Returns true if it holds a PostDominatorTree. |
58 | | bool hasPostDomTree() const { return PDT != nullptr; } |
59 | | |
60 | | /// Returns true if there is BasicBlock awaiting deletion. |
61 | | /// The deletion will only happen until a flush event and |
62 | | /// all available trees are up-to-date. |
63 | | /// Returns false under Eager UpdateStrategy. |
64 | | bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); } |
65 | | |
66 | | /// Returns true if DelBB is awaiting deletion. |
67 | | /// Returns false under Eager UpdateStrategy. |
68 | | bool isBBPendingDeletion(BasicBlock *DelBB) const; |
69 | | |
70 | | /// Returns true if either of DT or PDT is valid and the tree has at |
71 | | /// least one update pending. If DT or PDT is nullptr it is treated |
72 | | /// as having no pending updates. This function does not check |
73 | | /// whether there is BasicBlock awaiting deletion. |
74 | | /// Returns false under Eager UpdateStrategy. |
75 | | bool hasPendingUpdates() const; |
76 | | |
77 | | /// Returns true if there are DominatorTree updates queued. |
78 | | /// Returns false under Eager UpdateStrategy or DT is nullptr. |
79 | | bool hasPendingDomTreeUpdates() const; |
80 | | |
81 | | /// Returns true if there are PostDominatorTree updates queued. |
82 | | /// Returns false under Eager UpdateStrategy or PDT is nullptr. |
83 | | bool hasPendingPostDomTreeUpdates() const; |
84 | | |
85 | | ///@{ |
86 | | /// \name Mutation APIs |
87 | | /// |
88 | | /// These methods provide APIs for submitting updates to the DominatorTree and |
89 | | /// the PostDominatorTree. |
90 | | /// |
91 | | /// Note: There are two strategies to update the DominatorTree and the |
92 | | /// PostDominatorTree: |
93 | | /// 1. Eager UpdateStrategy: Updates are submitted and then flushed |
94 | | /// immediately. |
95 | | /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you |
96 | | /// explicitly call Flush APIs. It is recommended to use this update strategy |
97 | | /// when you submit a bunch of updates multiple times which can then |
98 | | /// add up to a large number of updates between two queries on the |
99 | | /// DominatorTree. The incremental updater can reschedule the updates or |
100 | | /// decide to recalculate the dominator tree in order to speedup the updating |
101 | | /// process depending on the number of updates. |
102 | | /// |
103 | | /// Although GenericDomTree provides several update primitives, |
104 | | /// it is not encouraged to use these APIs directly. |
105 | | |
106 | | /// Submit updates to all available trees. |
107 | | /// The Eager Strategy flushes updates immediately while the Lazy Strategy |
108 | | /// queues the updates. |
109 | | /// |
110 | | /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is |
111 | | /// in sync with + all updates before that single update. |
112 | | /// |
113 | | /// CAUTION! |
114 | | /// 1. It is required for the state of the LLVM IR to be updated |
115 | | /// *before* submitting the updates because the internal update routine will |
116 | | /// analyze the current state of the CFG to determine whether an update |
117 | | /// is valid. |
118 | | /// 2. It is illegal to submit any update that has already been submitted, |
119 | | /// i.e., you are supposed not to insert an existent edge or delete a |
120 | | /// nonexistent edge. |
121 | | void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates); |
122 | | |
123 | | /// Submit updates to all available trees. It will also |
124 | | /// 1. discard duplicated updates, |
125 | | /// 2. remove invalid updates. (Invalid updates means deletion of an edge that |
126 | | /// still exists or insertion of an edge that does not exist.) |
127 | | /// The Eager Strategy flushes updates immediately while the Lazy Strategy |
128 | | /// queues the updates. |
129 | | /// |
130 | | /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is |
131 | | /// in sync with + all updates before that single update. |
132 | | /// |
133 | | /// CAUTION! |
134 | | /// 1. It is required for the state of the LLVM IR to be updated |
135 | | /// *before* submitting the updates because the internal update routine will |
136 | | /// analyze the current state of the CFG to determine whether an update |
137 | | /// is valid. |
138 | | /// 2. It is illegal to submit any update that has already been submitted, |
139 | | /// i.e., you are supposed not to insert an existent edge or delete a |
140 | | /// nonexistent edge. |
141 | | /// 3. It is only legal to submit updates to an edge in the order CFG changes |
142 | | /// are made. The order you submit updates on different edges is not |
143 | | /// restricted. |
144 | | void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates); |
145 | | |
146 | | /// Notify DTU that the entry block was replaced. |
147 | | /// Recalculate all available trees and flush all BasicBlocks |
148 | | /// awaiting deletion immediately. |
149 | | void recalculate(Function &F); |
150 | | |
151 | | /// \deprecated { Submit an edge insertion to all available trees. The Eager |
152 | | /// Strategy flushes this update immediately while the Lazy Strategy queues |
153 | | /// the update. An internal function checks if the edge exists in the CFG in |
154 | | /// DEBUG mode. CAUTION! This function has to be called *after* making the |
155 | | /// update on the actual CFG. It is illegal to submit any update that has |
156 | | /// already been applied. } |
157 | | LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To), |
158 | | "Use applyUpdates() instead."); |
159 | | |
160 | | /// \deprecated {Submit an edge insertion to all available trees. |
161 | | /// Under either Strategy, an invalid update will be discard silently. |
162 | | /// Invalid update means inserting an edge that does not exist in the CFG. |
163 | | /// The Eager Strategy flushes this update immediately while the Lazy Strategy |
164 | | /// queues the update. It is only recommended to use this method when you |
165 | | /// want to discard an invalid update. |
166 | | /// CAUTION! It is illegal to submit any update that has already been |
167 | | /// submitted. } |
168 | | LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From, |
169 | | BasicBlock *To), |
170 | | "Use applyUpdatesPermissive() instead."); |
171 | | |
172 | | /// \deprecated { Submit an edge deletion to all available trees. The Eager |
173 | | /// Strategy flushes this update immediately while the Lazy Strategy queues |
174 | | /// the update. An internal function checks if the edge doesn't exist in the |
175 | | /// CFG in DEBUG mode. |
176 | | /// CAUTION! This function has to be called *after* making the update on the |
177 | | /// actual CFG. It is illegal to submit any update that has already been |
178 | | /// submitted. } |
179 | | LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To), |
180 | | "Use applyUpdates() instead."); |
181 | | |
182 | | /// \deprecated { Submit an edge deletion to all available trees. |
183 | | /// Under either Strategy, an invalid update will be discard silently. |
184 | | /// Invalid update means deleting an edge that exists in the CFG. |
185 | | /// The Eager Strategy flushes this update immediately while the Lazy Strategy |
186 | | /// queues the update. It is only recommended to use this method when you |
187 | | /// want to discard an invalid update. |
188 | | /// CAUTION! It is illegal to submit any update that has already been |
189 | | /// submitted. } |
190 | | LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From, |
191 | | BasicBlock *To), |
192 | | "Use applyUpdatesPermissive() instead."); |
193 | | |
194 | | /// Delete DelBB. DelBB will be removed from its Parent and |
195 | | /// erased from available trees if it exists and finally get deleted. |
196 | | /// Under Eager UpdateStrategy, DelBB will be processed immediately. |
197 | | /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and |
198 | | /// all available trees are up-to-date. Assert if any instruction of DelBB is |
199 | | /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB |
200 | | /// will be queued until flush() is called. |
201 | | void deleteBB(BasicBlock *DelBB); |
202 | | |
203 | | /// Delete DelBB. DelBB will be removed from its Parent and |
204 | | /// erased from available trees if it exists. Then the callback will |
205 | | /// be called. Finally, DelBB will be deleted. |
206 | | /// Under Eager UpdateStrategy, DelBB will be processed immediately. |
207 | | /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and |
208 | | /// all available trees are up-to-date. Assert if any instruction of DelBB is |
209 | | /// modified while awaiting deletion. Multiple callbacks can be queued for one |
210 | | /// DelBB under Lazy UpdateStrategy. |
211 | | void callbackDeleteBB(BasicBlock *DelBB, |
212 | | std::function<void(BasicBlock *)> Callback); |
213 | | |
214 | | ///@} |
215 | | |
216 | | ///@{ |
217 | | /// \name Flush APIs |
218 | | /// |
219 | | /// CAUTION! By the moment these flush APIs are called, the current CFG needs |
220 | | /// to be the same as the CFG which DTU is in sync with + all updates |
221 | | /// submitted. |
222 | | |
223 | | /// Flush DomTree updates and return DomTree. |
224 | | /// It flushes Deleted BBs if both trees are up-to-date. |
225 | | /// It must only be called when it has a DomTree. |
226 | | DominatorTree &getDomTree(); |
227 | | |
228 | | /// Flush PostDomTree updates and return PostDomTree. |
229 | | /// It flushes Deleted BBs if both trees are up-to-date. |
230 | | /// It must only be called when it has a PostDomTree. |
231 | | PostDominatorTree &getPostDomTree(); |
232 | | |
233 | | /// Apply all pending updates to available trees and flush all BasicBlocks |
234 | | /// awaiting deletion. |
235 | | |
236 | | void flush(); |
237 | | |
238 | | ///@} |
239 | | |
240 | | /// Debug method to help view the internal state of this class. |
241 | | LLVM_DUMP_METHOD void dump() const; |
242 | | |
243 | | private: |
244 | | class CallBackOnDeletion final : public CallbackVH { |
245 | | public: |
246 | | CallBackOnDeletion(BasicBlock *V, |
247 | | std::function<void(BasicBlock *)> Callback) |
248 | 3 | : CallbackVH(V), DelBB(V), Callback_(Callback) {} |
249 | | |
250 | | private: |
251 | | BasicBlock *DelBB = nullptr; |
252 | | std::function<void(BasicBlock *)> Callback_; |
253 | | |
254 | 3 | void deleted() override { |
255 | 3 | Callback_(DelBB); |
256 | 3 | CallbackVH::deleted(); |
257 | 3 | } |
258 | | }; |
259 | | |
260 | | SmallVector<DominatorTree::UpdateType, 16> PendUpdates; |
261 | | size_t PendDTUpdateIndex = 0; |
262 | | size_t PendPDTUpdateIndex = 0; |
263 | | DominatorTree *DT = nullptr; |
264 | | PostDominatorTree *PDT = nullptr; |
265 | | const UpdateStrategy Strategy; |
266 | | SmallPtrSet<BasicBlock *, 8> DeletedBBs; |
267 | | std::vector<CallBackOnDeletion> Callbacks; |
268 | | bool IsRecalculatingDomTree = false; |
269 | | bool IsRecalculatingPostDomTree = false; |
270 | | |
271 | | /// First remove all the instructions of DelBB and then make sure DelBB has a |
272 | | /// valid terminator instruction which is necessary to have when DelBB still |
273 | | /// has to be inside of its parent Function while awaiting deletion under Lazy |
274 | | /// UpdateStrategy to prevent other routines from asserting the state of the |
275 | | /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. |
276 | | void validateDeleteBB(BasicBlock *DelBB); |
277 | | |
278 | | /// Returns true if at least one BasicBlock is deleted. |
279 | | bool forceFlushDeletedBB(); |
280 | | |
281 | | /// Helper function to apply all pending DomTree updates. |
282 | | void applyDomTreeUpdates(); |
283 | | |
284 | | /// Helper function to apply all pending PostDomTree updates. |
285 | | void applyPostDomTreeUpdates(); |
286 | | |
287 | | /// Helper function to flush deleted BasicBlocks if all available |
288 | | /// trees are up-to-date. |
289 | | void tryFlushDeletedBB(); |
290 | | |
291 | | /// Drop all updates applied by all available trees and delete BasicBlocks if |
292 | | /// all available trees are up-to-date. |
293 | | void dropOutOfDateUpdates(); |
294 | | |
295 | | /// Erase Basic Block node that has been unlinked from Function |
296 | | /// in the DomTree and PostDomTree. |
297 | | void eraseDelBBNode(BasicBlock *DelBB); |
298 | | |
299 | | /// Returns true if the update appears in the LLVM IR. |
300 | | /// It is used to check whether an update is valid in |
301 | | /// insertEdge/deleteEdge or is unnecessary in the batch update. |
302 | | bool isUpdateValid(DominatorTree::UpdateType Update) const; |
303 | | |
304 | | /// Returns true if the update is self dominance. |
305 | | bool isSelfDominance(DominatorTree::UpdateType Update) const; |
306 | | }; |
307 | | } // namespace llvm |
308 | | |
309 | | #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H |