LLVM  9.0.0svn
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 
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/ValueHandle.h"
22 #include <functional>
23 #include <vector>
24 
25 namespace llvm {
27 public:
28  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
29 
30  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
32  : DT(&DT_), Strategy(Strategy_) {}
34  : DT(DT_), Strategy(Strategy_) {}
36  : PDT(&PDT_), Strategy(Strategy_) {}
38  : PDT(PDT_), Strategy(Strategy_) {}
40  UpdateStrategy Strategy_)
41  : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
43  UpdateStrategy Strategy_)
44  : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
45 
47 
48  /// Returns true if the current strategy is Lazy.
49  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  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.
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.
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.
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.
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  : CallbackVH(V), DelBB(V), Callback_(Callback) {}
249 
250  private:
251  BasicBlock *DelBB = nullptr;
252  std::function<void(BasicBlock *)> Callback_;
253 
254  void deleted() override {
255  Callback_(DelBB);
257  }
258  };
259 
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
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:464
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:57
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:409
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:417
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
This file defines a set of templates that efficiently compute a dominator tree over a generic graph...
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
DomTreeUpdater(UpdateStrategy Strategy_)
bool hasDomTree() const
Returns true if it holds a DominatorTree.