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