LLVM  15.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  /// Delete DelBB. DelBB will be removed from its Parent and
154  /// erased from available trees if it exists and finally get deleted.
155  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
156  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
157  /// all available trees are up-to-date. Assert if any instruction of DelBB is
158  /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
159  /// will be queued until flush() is called.
160  void deleteBB(BasicBlock *DelBB);
161 
162  /// Delete DelBB. DelBB will be removed from its Parent and
163  /// erased from available trees if it exists. Then the callback will
164  /// be called. Finally, DelBB will be deleted.
165  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
166  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
167  /// all available trees are up-to-date. Assert if any instruction of DelBB is
168  /// modified while awaiting deletion. Multiple callbacks can be queued for one
169  /// DelBB under Lazy UpdateStrategy.
170  void callbackDeleteBB(BasicBlock *DelBB,
171  std::function<void(BasicBlock *)> Callback);
172 
173  ///@}
174 
175  ///@{
176  /// \name Flush APIs
177  ///
178  /// CAUTION! By the moment these flush APIs are called, the current CFG needs
179  /// to be the same as the CFG which DTU is in sync with + all updates
180  /// submitted.
181 
182  /// Flush DomTree updates and return DomTree.
183  /// It flushes Deleted BBs if both trees are up-to-date.
184  /// It must only be called when it has a DomTree.
186 
187  /// Flush PostDomTree updates and return PostDomTree.
188  /// It flushes Deleted BBs if both trees are up-to-date.
189  /// It must only be called when it has a PostDomTree.
191 
192  /// Apply all pending updates to available trees and flush all BasicBlocks
193  /// awaiting deletion.
194 
195  void flush();
196 
197  ///@}
198 
199  /// Debug method to help view the internal state of this class.
200  LLVM_DUMP_METHOD void dump() const;
201 
202 private:
203  class CallBackOnDeletion final : public CallbackVH {
204  public:
205  CallBackOnDeletion(BasicBlock *V,
206  std::function<void(BasicBlock *)> Callback)
207  : CallbackVH(V), DelBB(V), Callback_(Callback) {}
208 
209  private:
210  BasicBlock *DelBB = nullptr;
211  std::function<void(BasicBlock *)> Callback_;
212 
213  void deleted() override {
214  Callback_(DelBB);
216  }
217  };
218 
219  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
220  size_t PendDTUpdateIndex = 0;
221  size_t PendPDTUpdateIndex = 0;
222  DominatorTree *DT = nullptr;
223  PostDominatorTree *PDT = nullptr;
224  const UpdateStrategy Strategy;
225  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
226  std::vector<CallBackOnDeletion> Callbacks;
227  bool IsRecalculatingDomTree = false;
228  bool IsRecalculatingPostDomTree = false;
229 
230  /// First remove all the instructions of DelBB and then make sure DelBB has a
231  /// valid terminator instruction which is necessary to have when DelBB still
232  /// has to be inside of its parent Function while awaiting deletion under Lazy
233  /// UpdateStrategy to prevent other routines from asserting the state of the
234  /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
235  void validateDeleteBB(BasicBlock *DelBB);
236 
237  /// Returns true if at least one BasicBlock is deleted.
238  bool forceFlushDeletedBB();
239 
240  /// Helper function to apply all pending DomTree updates.
241  void applyDomTreeUpdates();
242 
243  /// Helper function to apply all pending PostDomTree updates.
244  void applyPostDomTreeUpdates();
245 
246  /// Helper function to flush deleted BasicBlocks if all available
247  /// trees are up-to-date.
248  void tryFlushDeletedBB();
249 
250  /// Drop all updates applied by all available trees and delete BasicBlocks if
251  /// all available trees are up-to-date.
252  void dropOutOfDateUpdates();
253 
254  /// Erase Basic Block node that has been unlinked from Function
255  /// in the DomTree and PostDomTree.
256  void eraseDelBBNode(BasicBlock *DelBB);
257 
258  /// Returns true if the update appears in the LLVM IR.
259  /// It is used to check whether an update is valid in
260  /// insertEdge/deleteEdge or is unnecessary in the batch update.
261  bool isUpdateValid(DominatorTree::UpdateType Update) const;
262 
263  /// Returns true if the update is self dominance.
264  bool isSelfDominance(DominatorTree::UpdateType Update) const;
265 };
266 } // namespace llvm
267 
268 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H
llvm::DomTreeUpdater::UpdateStrategy
UpdateStrategy
Definition: DomTreeUpdater.h:30
llvm::DomTreeUpdater::hasPendingDeletedBB
bool hasPendingDeletedBB() const
Returns true if there is BasicBlock awaiting deletion.
Definition: DomTreeUpdater.h:66
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:494
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:44
llvm::DomTreeUpdater::deleteBB
void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Definition: DomTreeUpdater.cpp:178
llvm::CallbackVH::deleted
virtual void deleted()
Callback for Value destruction.
Definition: ValueHandle.h:414
llvm::DomTreeUpdater::isEager
bool isEager() const
Returns true if the current strategy is Eager.
Definition: DomTreeUpdater.h:54
llvm::DomTreeUpdater::applyUpdates
void applyUpdates(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:231
llvm::Function
Definition: Function.h:60
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::DomTreeUpdater::hasPendingUpdates
bool hasPendingUpdates() const
Returns true if either of DT or PDT is valid and the tree has at least one update pending.
Definition: DomTreeUpdater.cpp:151
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DomTreeUpdater::UpdateStrategy::Lazy
@ Lazy
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::DomTreeUpdater::hasPendingPostDomTreeUpdates
bool hasPendingPostDomTreeUpdates() const
Returns true if there are PostDominatorTree updates queued.
Definition: DomTreeUpdater.cpp:161
llvm::DomTreeUpdater::callbackDeleteBB
void callbackDeleteBB(BasicBlock *DelBB, std::function< void(BasicBlock *)> Callback)
Delete DelBB.
Definition: DomTreeUpdater.cpp:190
llvm::DomTreeUpdater::isBBPendingDeletion
bool isBBPendingDeletion(BasicBlock *DelBB) const
Returns true if DelBB is awaiting deletion.
Definition: DomTreeUpdater.cpp:167
llvm::DomTreeUpdater::dump
LLVM_DUMP_METHOD void dump() const
Debug method to help view the internal state of this class.
Definition: DomTreeUpdater.cpp:341
llvm::DominatorTreeBase< BasicBlock, false >::UpdateType
cfg::Update< NodePtr > UpdateType
Definition: GenericDomTree.h:240
llvm::DomTreeUpdater::hasPendingDomTreeUpdates
bool hasPendingDomTreeUpdates() const
Returns true if there are DominatorTree updates queued.
Definition: DomTreeUpdater.cpp:155
llvm::DomTreeUpdater::recalculate
void recalculate(Function &F)
Notify DTU that the entry block was replaced.
Definition: DomTreeUpdater.cpp:121
llvm::DomTreeUpdater::~DomTreeUpdater
~DomTreeUpdater()
Definition: DomTreeUpdater.h:48
llvm::DomTreeUpdater
Definition: DomTreeUpdater.h:28
SmallPtrSet.h
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:32
llvm::DomTreeUpdater::hasDomTree
bool hasDomTree() const
Returns true if it holds a DominatorTree.
Definition: DomTreeUpdater.h:57
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:33
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:35
llvm::DomTreeUpdater::getDomTree
DominatorTree & getDomTree()
Flush DomTree updates and return DomTree.
Definition: DomTreeUpdater.cpp:304
llvm::DomTreeUpdater::hasPostDomTree
bool hasPostDomTree() const
Returns true if it holds a PostDominatorTree.
Definition: DomTreeUpdater.h:60
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:82
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:37
llvm::PostDominatorTree
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Definition: PostDominators.h:28
Compiler.h
llvm::DomTreeUpdater::UpdateStrategy::Eager
@ Eager
llvm::DomTreeUpdater::flush
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
Definition: DomTreeUpdater.cpp:73
ValueHandle.h
llvm::DomTreeUpdater::isLazy
bool isLazy() const
Returns true if the current strategy is Lazy.
Definition: DomTreeUpdater.h:51
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:39
llvm::CallbackVH
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:383
llvm::DomTreeUpdater::getPostDomTree
PostDominatorTree & getPostDomTree()
Flush PostDomTree updates and return PostDomTree.
Definition: DomTreeUpdater.cpp:311
Dominators.h
llvm::DomTreeUpdater::applyUpdatesPermissive
void applyUpdatesPermissive(ArrayRef< DominatorTree::UpdateType > Updates)
Submit updates to all available trees.
Definition: DomTreeUpdater.cpp:250
llvm::DomTreeUpdater::DomTreeUpdater
DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, UpdateStrategy Strategy_)
Definition: DomTreeUpdater.h:41