1//===- GenericDomTreeUpdater.h ----------------------------------*- 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 GenericDomTreeUpdater class, which provides a uniform
10// way to update dominator tree related data structures.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H
15#define LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H
16
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/Support/Compiler.h"
20
21namespace llvm {
22
23template <typename DerivedT, typename DomTreeT, typename PostDomTreeT>
24class GenericDomTreeUpdater {
25 DerivedT &derived() { return *static_cast<DerivedT *>(this); }
26 const DerivedT &derived() const {
27 return *static_cast<const DerivedT *>(this);
28 }
29
30public:
31 enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
32 using BasicBlockT = typename DomTreeT::NodeType;
33 using UpdateT = typename DomTreeT::UpdateType;
34
35 explicit GenericDomTreeUpdater(UpdateStrategy Strategy_)
36 : Strategy(Strategy_) {}
37 GenericDomTreeUpdater(DomTreeT &DT_, UpdateStrategy Strategy_)
38 : DT(&DT_), Strategy(Strategy_) {}
39 GenericDomTreeUpdater(DomTreeT *DT_, UpdateStrategy Strategy_)
40 : DT(DT_), Strategy(Strategy_) {}
41 GenericDomTreeUpdater(PostDomTreeT &PDT_, UpdateStrategy Strategy_)
42 : PDT(&PDT_), Strategy(Strategy_) {}
43 GenericDomTreeUpdater(PostDomTreeT *PDT_, UpdateStrategy Strategy_)
44 : PDT(PDT_), Strategy(Strategy_) {}
45 GenericDomTreeUpdater(DomTreeT &DT_, PostDomTreeT &PDT_,
46 UpdateStrategy Strategy_)
47 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
48 GenericDomTreeUpdater(DomTreeT *DT_, PostDomTreeT *PDT_,
49 UpdateStrategy Strategy_)
50 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
51
52 ~GenericDomTreeUpdater() {
53 // We cannot call into derived() here as it will already be destroyed.
54 assert(!hasPendingUpdates() &&
55 "Pending updates were not flushed by derived class.");
56 }
57
58 /// Returns true if the current strategy is Lazy.
59 bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }
60
61 /// Returns true if the current strategy is Eager.
62 bool isEager() const { return Strategy == UpdateStrategy::Eager; }
63
64 /// Returns true if it holds a DomTreeT.
65 bool hasDomTree() const { return DT != nullptr; }
66
67 /// Returns true if it holds a PostDomTreeT.
68 bool hasPostDomTree() const { return PDT != nullptr; }
69
70 /// Returns true if there is BasicBlockT awaiting deletion.
71 /// The deletion will only happen until a flush event and
72 /// all available trees are up-to-date.
73 /// Returns false under Eager UpdateStrategy.
74 bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
75
76 /// Returns true if DelBB is awaiting deletion.
77 /// Returns false under Eager UpdateStrategy.
78 bool isBBPendingDeletion(BasicBlockT *DelBB) const {
79 if (Strategy == UpdateStrategy::Eager || DeletedBBs.empty())
80 return false;
81 return DeletedBBs.contains(DelBB);
82 }
83
84 /// Returns true if either of DT or PDT is valid and the tree has at
85 /// least one update pending. If DT or PDT is nullptr it is treated
86 /// as having no pending updates. This function does not check
87 /// whether there is MachineBasicBlock awaiting deletion.
88 /// Returns false under Eager UpdateStrategy.
89 bool hasPendingUpdates() const {
90 return hasPendingDomTreeUpdates() || hasPendingPostDomTreeUpdates();
91 }
92
93 /// Returns true if there are DomTreeT updates queued.
94 /// Returns false under Eager UpdateStrategy or DT is nullptr.
95 bool hasPendingDomTreeUpdates() const {
96 if (!DT)
97 return false;
98 return PendUpdates.size() != PendDTUpdateIndex;
99 }
100
101 /// Returns true if there are PostDomTreeT updates queued.
102 /// Returns false under Eager UpdateStrategy or PDT is nullptr.
103 bool hasPendingPostDomTreeUpdates() const {
104 if (!PDT)
105 return false;
106 return PendUpdates.size() != PendPDTUpdateIndex;
107 }
108
109 ///@{
110 /// \name Mutation APIs
111 ///
112 /// These methods provide APIs for submitting updates to the DomTreeT and
113 /// the PostDominatorTree.
114 ///
115 /// Note: There are two strategies to update the DomTreeT and the
116 /// PostDominatorTree:
117 /// 1. Eager UpdateStrategy: Updates are submitted and then flushed
118 /// immediately.
119 /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you
120 /// explicitly call Flush APIs. It is recommended to use this update strategy
121 /// when you submit a bunch of updates multiple times which can then
122 /// add up to a large number of updates between two queries on the
123 /// DomTreeT. The incremental updater can reschedule the updates or
124 /// decide to recalculate the dominator tree in order to speedup the updating
125 /// process depending on the number of updates.
126 ///
127 /// Although GenericDomTree provides several update primitives,
128 /// it is not encouraged to use these APIs directly.
129
130 /// Notify DTU that the entry block was replaced.
131 /// Recalculate all available trees and flush all BasicBlocks
132 /// awaiting deletion immediately.
133 template <typename FuncT> void recalculate(FuncT &F);
134
135 /// Submit updates to all available trees.
136 /// The Eager Strategy flushes updates immediately while the Lazy Strategy
137 /// queues the updates.
138 ///
139 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
140 /// in sync with + all updates before that single update.
141 ///
142 /// CAUTION!
143 /// 1. It is required for the state of the LLVM IR to be updated
144 /// *before* submitting the updates because the internal update routine will
145 /// analyze the current state of the CFG to determine whether an update
146 /// is valid.
147 /// 2. It is illegal to submit any update that has already been submitted,
148 /// i.e., you are supposed not to insert an existent edge or delete a
149 /// nonexistent edge.
150 void applyUpdates(ArrayRef<UpdateT> Updates);
151
152 /// Apply updates that the critical edge (FromBB, ToBB) has been
153 /// split with NewBB.
154 void splitCriticalEdge(BasicBlockT *FromBB, BasicBlockT *ToBB,
155 BasicBlockT *NewBB);
156
157 /// Submit updates to all available trees. It will also
158 /// 1. discard duplicated updates,
159 /// 2. remove invalid updates. (Invalid updates means deletion of an edge that
160 /// still exists or insertion of an edge that does not exist.)
161 /// The Eager Strategy flushes updates immediately while the Lazy Strategy
162 /// queues the updates.
163 ///
164 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
165 /// in sync with + all updates before that single update.
166 ///
167 /// CAUTION!
168 /// 1. It is required for the state of the LLVM IR to be updated
169 /// *before* submitting the updates because the internal update routine will
170 /// analyze the current state of the CFG to determine whether an update
171 /// is valid.
172 /// 2. It is illegal to submit any update that has already been submitted,
173 /// i.e., you are supposed not to insert an existent edge or delete a
174 /// nonexistent edge.
175 /// 3. It is only legal to submit updates to an edge in the order CFG changes
176 /// are made. The order you submit updates on different edges is not
177 /// restricted.
178 void applyUpdatesPermissive(ArrayRef<UpdateT> Updates);
179
180 ///@}
181
182 ///@{
183 /// \name Flush APIs
184 ///
185 /// CAUTION! By the moment these flush APIs are called, the current CFG needs
186 /// to be the same as the CFG which DTU is in sync with + all updates
187 /// submitted.
188
189 /// Flush DomTree updates and return DomTree.
190 /// It flushes Deleted BBs if both trees are up-to-date.
191 /// It must only be called when it has a DomTree.
192 DomTreeT &getDomTree();
193
194 /// Flush PostDomTree updates and return PostDomTree.
195 /// It flushes Deleted BBs if both trees are up-to-date.
196 /// It must only be called when it has a PostDomTree.
197 PostDomTreeT &getPostDomTree();
198
199 /// Apply all pending updates to available trees and flush all BasicBlocks
200 /// awaiting deletion.
201
202 void flush() {
203 applyDomTreeUpdates();
204 applyPostDomTreeUpdates();
205 dropOutOfDateUpdates();
206 }
207
208 ///@}
209
210 /// Debug method to help view the internal state of this class.
211 LLVM_DUMP_METHOD void dump() const;
212
213protected:
214 /// Helper structure used to hold all the basic blocks
215 /// involved in the split of a critical edge.
216 struct CriticalEdge {
217 BasicBlockT *FromBB;
218 BasicBlockT *ToBB;
219 BasicBlockT *NewBB;
220 };
221
222 struct DomTreeUpdate {
223 bool IsCriticalEdgeSplit = false;
224 union {
225 UpdateT Update;
226 CriticalEdge EdgeSplit;
227 };
228 DomTreeUpdate(UpdateT Update) : Update(Update) {}
229 DomTreeUpdate(CriticalEdge E) : IsCriticalEdgeSplit(true), EdgeSplit(E) {}
230 };
231
232 SmallVector<DomTreeUpdate, 16> PendUpdates;
233 size_t PendDTUpdateIndex = 0;
234 size_t PendPDTUpdateIndex = 0;
235 DomTreeT *DT = nullptr;
236 PostDomTreeT *PDT = nullptr;
237 const UpdateStrategy Strategy;
238 SmallPtrSet<BasicBlockT *, 8> DeletedBBs;
239 bool IsRecalculatingDomTree = false;
240 bool IsRecalculatingPostDomTree = false;
241
242 /// Returns true if the update is self dominance.
243 bool isSelfDominance(UpdateT Update) const {
244 // Won't affect DomTree and PostDomTree.
245 return Update.getFrom() == Update.getTo();
246 }
247
248 /// Helper function to apply all pending DomTree updates.
249 void applyDomTreeUpdates() { applyUpdatesImpl<true>(); }
250
251 /// Helper function to apply all pending PostDomTree updates.
252 void applyPostDomTreeUpdates() { applyUpdatesImpl<false>(); }
253
254 /// Returns true if the update appears in the LLVM IR.
255 /// It is used to check whether an update is valid in
256 /// insertEdge/deleteEdge or is unnecessary in the batch update.
257 bool isUpdateValid(UpdateT Update) const;
258
259 /// Erase Basic Block node before it is unlinked from Function
260 /// in the DomTree and PostDomTree.
261 void eraseDelBBNode(BasicBlockT *DelBB);
262
263 /// Helper function to flush deleted BasicBlocks if all available
264 /// trees are up-to-date.
265 void tryFlushDeletedBB();
266
267 /// Drop all updates applied by all available trees and delete BasicBlocks if
268 /// all available trees are up-to-date.
269 void dropOutOfDateUpdates();
270
271private:
272 void splitDTCriticalEdges(ArrayRef<CriticalEdge> Updates);
273 void splitPDTCriticalEdges(ArrayRef<CriticalEdge> Updates);
274 template <bool IsForward> void applyUpdatesImpl();
275};
276
277} // namespace llvm
278
279#endif // LLVM_ANALYSIS_GENERICDOMTREEUPDATER_H
280