Line data Source code
1 : //===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines the DomTreeUpdater class, which provides a uniform way to
11 : // update dominator tree related data structures.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_DOMTREEUPDATER_H
16 : #define LLVM_DOMTREEUPDATER_H
17 :
18 : #include "llvm/Analysis/PostDominators.h"
19 : #include "llvm/IR/Dominators.h"
20 : #include "llvm/IR/Instructions.h"
21 : #include "llvm/IR/ValueHandle.h"
22 : #include "llvm/Support/GenericDomTree.h"
23 : #include <functional>
24 : #include <vector>
25 :
26 : namespace llvm {
27 : class DomTreeUpdater {
28 : public:
29 : enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
30 :
31 : explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
32 : DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
33 271227 : : DT(&DT_), Strategy(Strategy_) {}
34 : DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
35 137592 : : DT(DT_), Strategy(Strategy_) {}
36 : DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
37 : : PDT(&PDT_), Strategy(Strategy_) {}
38 : DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
39 : : PDT(PDT_), Strategy(Strategy_) {}
40 : DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
41 : UpdateStrategy Strategy_)
42 12 : : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
43 : DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
44 : UpdateStrategy Strategy_)
45 131541 : : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
46 :
47 180167 : ~DomTreeUpdater() { flush(); }
48 :
49 : /// Returns true if the current strategy is Lazy.
50 5 : bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
51 :
52 : /// Returns true if the current strategy is Eager.
53 2 : bool isEager() const { return Strategy == UpdateStrategy::Eager; };
54 :
55 : /// Returns true if it holds a DominatorTree.
56 0 : bool hasDomTree() const { return DT != nullptr; }
57 :
58 : /// Returns true if it holds a PostDominatorTree.
59 5 : bool hasPostDomTree() const { return PDT != nullptr; }
60 :
61 : /// Returns true if there is BasicBlock awaiting deletion.
62 : /// The deletion will only happen until a flush event and
63 : /// all available trees are up-to-date.
64 : /// Returns false under Eager UpdateStrategy.
65 4 : bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
66 :
67 : /// Returns true if DelBB is awaiting deletion.
68 : /// Returns false under Eager UpdateStrategy.
69 : bool isBBPendingDeletion(BasicBlock *DelBB) const;
70 :
71 : /// Returns true if either of DT or PDT is valid and the tree has at
72 : /// least one update pending. If DT or PDT is nullptr it is treated
73 : /// as having no pending updates. This function does not check
74 : /// whether there is BasicBlock awaiting deletion.
75 : /// Returns false under Eager UpdateStrategy.
76 : bool hasPendingUpdates() const;
77 :
78 : /// Returns true if there are DominatorTree updates queued.
79 : /// Returns false under Eager UpdateStrategy or DT is nullptr.
80 : bool hasPendingDomTreeUpdates() const;
81 :
82 : /// Returns true if there are PostDominatorTree updates queued.
83 : /// Returns false under Eager UpdateStrategy or PDT is nullptr.
84 : bool hasPendingPostDomTreeUpdates() const;
85 :
86 : /// Apply updates on all available trees. Under Eager UpdateStrategy with
87 : /// ForceRemoveDuplicates enabled or under Lazy UpdateStrategy, it will
88 : /// discard duplicated updates and self-dominance updates. If both DT and PDT
89 : /// are nullptrs, this function discards all updates. The Eager Strategy
90 : /// applies the updates immediately while the Lazy Strategy queues the
91 : /// updates. It is required for the state of the LLVM IR to be updated
92 : /// *before* applying the Updates because the internal update routine will
93 : /// analyze the current state of the relationship between a pair of (From, To)
94 : /// BasicBlocks to determine whether a single update needs to be discarded.
95 : void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates,
96 : bool ForceRemoveDuplicates = false);
97 :
98 : /// Notify all available trees on an edge insertion. If both DT and PDT are
99 : /// nullptrs, this function discards the update. Under either Strategy,
100 : /// self-dominance update will be removed. The Eager Strategy applies
101 : /// the update immediately while the Lazy Strategy queues the update.
102 : /// It is recommended to only use this method when you have exactly one
103 : /// insertion (and no deletions). It is recommended to use applyUpdates() in
104 : /// all other cases. This function has to be called *after* making the update
105 : /// on the actual CFG. An internal functions checks if the edge exists in the
106 : /// CFG in DEBUG mode.
107 : void insertEdge(BasicBlock *From, BasicBlock *To);
108 :
109 : /// Notify all available trees on an edge insertion.
110 : /// Under either Strategy, the following updates will be discard silently
111 : /// 1. Invalid - Inserting an edge that does not exist in the CFG.
112 : /// 2. Self-dominance update.
113 : /// 3. Both DT and PDT are nullptrs.
114 : /// The Eager Strategy applies the update immediately while the Lazy Strategy
115 : /// queues the update. It is recommended to only use this method when you have
116 : /// exactly one insertion (and no deletions) and want to discard an invalid
117 : /// update.
118 : void insertEdgeRelaxed(BasicBlock *From, BasicBlock *To);
119 :
120 : /// Notify all available trees on an edge deletion. If both DT and PDT are
121 : /// nullptrs, this function discards the update. Under either Strategy,
122 : /// self-dominance update will be removed. The Eager Strategy applies
123 : /// the update immediately while the Lazy Strategy queues the update.
124 : /// It is recommended to only use this method when you have exactly one
125 : /// deletion (and no insertions). It is recommended to use applyUpdates() in
126 : /// all other cases. This function has to be called *after* making the update
127 : /// on the actual CFG. An internal functions checks if the edge doesn't exist
128 : /// in the CFG in DEBUG mode.
129 : void deleteEdge(BasicBlock *From, BasicBlock *To);
130 :
131 : /// Notify all available trees on an edge deletion.
132 : /// Under either Strategy, the following updates will be discard silently
133 : /// 1. Invalid - Deleting an edge that still exists in the CFG.
134 : /// 2. Self-dominance update.
135 : /// 3. Both DT and PDT are nullptrs.
136 : /// The Eager Strategy applies the update immediately while the Lazy Strategy
137 : /// queues the update. It is recommended to only use this method when you have
138 : /// exactly one deletion (and no insertions) and want to discard an invalid
139 : /// update.
140 : void deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To);
141 :
142 : /// Delete DelBB. DelBB will be removed from its Parent and
143 : /// erased from available trees if it exists and finally get deleted.
144 : /// Under Eager UpdateStrategy, DelBB will be processed immediately.
145 : /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
146 : /// all available trees are up-to-date. Assert if any instruction of DelBB is
147 : /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
148 : /// will be queued until flush() is called.
149 : void deleteBB(BasicBlock *DelBB);
150 :
151 : /// Delete DelBB. DelBB will be removed from its Parent and
152 : /// erased from available trees if it exists. Then the callback will
153 : /// be called. Finally, DelBB will be deleted.
154 : /// Under Eager UpdateStrategy, DelBB will be processed immediately.
155 : /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
156 : /// all available trees are up-to-date. Assert if any instruction of DelBB is
157 : /// modified while awaiting deletion. Multiple callbacks can be queued for one
158 : /// DelBB under Lazy UpdateStrategy.
159 : void callbackDeleteBB(BasicBlock *DelBB,
160 : std::function<void(BasicBlock *)> Callback);
161 :
162 : /// Recalculate all available trees and flush all BasicBlocks
163 : /// awaiting deletion immediately.
164 : void recalculate(Function &F);
165 :
166 : /// Flush DomTree updates and return DomTree.
167 : /// It also flush out of date updates applied by all available trees
168 : /// and flush Deleted BBs if both trees are up-to-date.
169 : /// It must only be called when it has a DomTree.
170 : DominatorTree &getDomTree();
171 :
172 : /// Flush PostDomTree updates and return PostDomTree.
173 : /// It also flush out of date updates applied by all available trees
174 : /// and flush Deleted BBs if both trees are up-to-date.
175 : /// It must only be called when it has a PostDomTree.
176 : PostDominatorTree &getPostDomTree();
177 :
178 : /// Apply all pending updates to available trees and flush all BasicBlocks
179 : /// awaiting deletion.
180 : /// Does nothing under Eager UpdateStrategy.
181 : void flush();
182 :
183 : /// Debug method to help view the internal state of this class.
184 : LLVM_DUMP_METHOD void dump() const;
185 :
186 : private:
187 : class CallBackOnDeletion final : public CallbackVH {
188 : public:
189 3 : CallBackOnDeletion(BasicBlock *V,
190 : std::function<void(BasicBlock *)> Callback)
191 6 : : CallbackVH(V), DelBB(V), Callback_(Callback) {}
192 :
193 : private:
194 : BasicBlock *DelBB = nullptr;
195 : std::function<void(BasicBlock *)> Callback_;
196 :
197 3 : void deleted() override {
198 6 : Callback_(DelBB);
199 : CallbackVH::deleted();
200 3 : }
201 : };
202 :
203 : SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
204 : size_t PendDTUpdateIndex = 0;
205 : size_t PendPDTUpdateIndex = 0;
206 : DominatorTree *DT = nullptr;
207 : PostDominatorTree *PDT = nullptr;
208 : const UpdateStrategy Strategy;
209 : SmallPtrSet<BasicBlock *, 8> DeletedBBs;
210 : std::vector<CallBackOnDeletion> Callbacks;
211 : bool IsRecalculatingDomTree = false;
212 : bool IsRecalculatingPostDomTree = false;
213 :
214 : /// First remove all the instructions of DelBB and then make sure DelBB has a
215 : /// valid terminator instruction which is necessary to have when DelBB still
216 : /// has to be inside of its parent Function while awaiting deletion under Lazy
217 : /// UpdateStrategy to prevent other routines from asserting the state of the
218 : /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
219 : void validateDeleteBB(BasicBlock *DelBB);
220 :
221 : /// Returns true if at least one BasicBlock is deleted.
222 : bool forceFlushDeletedBB();
223 :
224 : /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy
225 : /// UpdateStrategy. Returns true if the update is queued for update.
226 : bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From,
227 : BasicBlock *To);
228 :
229 : /// Helper function to apply all pending DomTree updates.
230 : void applyDomTreeUpdates();
231 :
232 : /// Helper function to apply all pending PostDomTree updates.
233 : void applyPostDomTreeUpdates();
234 :
235 : /// Helper function to flush deleted BasicBlocks if all available
236 : /// trees are up-to-date.
237 : void tryFlushDeletedBB();
238 :
239 : /// Drop all updates applied by all available trees and delete BasicBlocks if
240 : /// all available trees are up-to-date.
241 : void dropOutOfDateUpdates();
242 :
243 : /// Erase Basic Block node that has been unlinked from Function
244 : /// in the DomTree and PostDomTree.
245 : void eraseDelBBNode(BasicBlock *DelBB);
246 :
247 : /// Returns true if the update appears in the LLVM IR.
248 : /// It is used to check whether an update is valid in
249 : /// insertEdge/deleteEdge or is unnecessary in the batch update.
250 : bool isUpdateValid(DominatorTree::UpdateType Update) const;
251 :
252 : /// Returns true if the update is self dominance.
253 : bool isSelfDominance(DominatorTree::UpdateType Update) const;
254 : };
255 : } // namespace llvm
256 :
257 : #endif // LLVM_DOMTREEUPDATER_H
|
