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
25namespace llvm {
26class PostDominatorTree;
27
28class DomTreeUpdater {
29public:
30 enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
31
32 explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
33 DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
34 : DT(&DT_), Strategy(Strategy_) {}
35 DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
36 : DT(DT_), Strategy(Strategy_) {}
37 DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
38 : PDT(&PDT_), Strategy(Strategy_) {}
39 DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
40 : PDT(PDT_), Strategy(Strategy_) {}
41 DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
42 UpdateStrategy Strategy_)
43 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
44 DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
45 UpdateStrategy Strategy_)
46 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
47
48 ~DomTreeUpdater() { flush(); }
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.
123 void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
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.
146 void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);
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.
185 DominatorTree &getDomTree();
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.
190 PostDominatorTree &getPostDomTree();
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
202private:
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);
215 CallbackVH::deleted();
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
269

source code of llvm/include/llvm/Analysis/DomTreeUpdater.h