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