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/Analysis/PostDominators.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/Instructions.h" 20 #include "llvm/IR/ValueHandle.h" 21 #include "llvm/Support/GenericDomTree.h" 22 #include <functional> 23 #include <vector> 24 25 namespace llvm { 26 class DomTreeUpdater { 27 public: 28 enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; 29 30 explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} 31 DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) 32 : DT(&DT_), Strategy(Strategy_) {} 33 DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) 34 : DT(DT_), Strategy(Strategy_) {} 35 DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) 36 : PDT(&PDT_), Strategy(Strategy_) {} 37 DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) 38 : PDT(PDT_), Strategy(Strategy_) {} 39 DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, 40 UpdateStrategy Strategy_) 41 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} 42 DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, 43 UpdateStrategy Strategy_) 44 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} 45 46 ~DomTreeUpdater() { flush(); } 47 48 /// Returns true if the current strategy is Lazy. 49 bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; 50 51 /// Returns true if the current strategy is Eager. 52 bool isEager() const { return Strategy == UpdateStrategy::Eager; }; 53 54 /// Returns true if it holds a DominatorTree. 55 bool hasDomTree() const { return DT != nullptr; } 56 57 /// Returns true if it holds a PostDominatorTree. 58 bool hasPostDomTree() const { return PDT != nullptr; } 59 60 /// Returns true if there is BasicBlock awaiting deletion. 61 /// The deletion will only happen until a flush event and 62 /// all available trees are up-to-date. 63 /// Returns false under Eager UpdateStrategy. 64 bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); } 65 66 /// Returns true if DelBB is awaiting deletion. 67 /// Returns false under Eager UpdateStrategy. 68 bool isBBPendingDeletion(BasicBlock *DelBB) const; 69 70 /// Returns true if either of DT or PDT is valid and the tree has at 71 /// least one update pending. If DT or PDT is nullptr it is treated 72 /// as having no pending updates. This function does not check 73 /// whether there is BasicBlock awaiting deletion. 74 /// Returns false under Eager UpdateStrategy. 75 bool hasPendingUpdates() const; 76 77 /// Returns true if there are DominatorTree updates queued. 78 /// Returns false under Eager UpdateStrategy or DT is nullptr. 79 bool hasPendingDomTreeUpdates() const; 80 81 /// Returns true if there are PostDominatorTree updates queued. 82 /// Returns false under Eager UpdateStrategy or PDT is nullptr. 83 bool hasPendingPostDomTreeUpdates() const; 84 85 ///@{ 86 /// \name Mutation APIs 87 /// 88 /// These methods provide APIs for submitting updates to the DominatorTree and 89 /// the PostDominatorTree. 90 /// 91 /// Note: There are two strategies to update the DominatorTree and the 92 /// PostDominatorTree: 93 /// 1. Eager UpdateStrategy: Updates are submitted and then flushed 94 /// immediately. 95 /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you 96 /// explicitly call Flush APIs. It is recommended to use this update strategy 97 /// when you submit a bunch of updates multiple times which can then 98 /// add up to a large number of updates between two queries on the 99 /// DominatorTree. The incremental updater can reschedule the updates or 100 /// decide to recalculate the dominator tree in order to speedup the updating 101 /// process depending on the number of updates. 102 /// 103 /// Although GenericDomTree provides several update primitives, 104 /// it is not encouraged to use these APIs directly. 105 106 /// Submit updates to all available trees. 107 /// The Eager Strategy flushes updates immediately while the Lazy Strategy 108 /// queues the updates. 109 /// 110 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is 111 /// in sync with + all updates before that single update. 112 /// 113 /// CAUTION! 114 /// 1. It is required for the state of the LLVM IR to be updated 115 /// *before* submitting the updates because the internal update routine will 116 /// analyze the current state of the CFG to determine whether an update 117 /// is valid. 118 /// 2. It is illegal to submit any update that has already been submitted, 119 /// i.e., you are supposed not to insert an existent edge or delete a 120 /// nonexistent edge. 121 void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates); 122 123 /// Submit updates to all available trees. It will also 124 /// 1. discard duplicated updates, 125 /// 2. remove invalid updates. (Invalid updates means deletion of an edge that 126 /// still exists or insertion of an edge that does not exist.) 127 /// The Eager Strategy flushes updates immediately while the Lazy Strategy 128 /// queues the updates. 129 /// 130 /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is 131 /// in sync with + all updates before that single update. 132 /// 133 /// CAUTION! 134 /// 1. It is required for the state of the LLVM IR to be updated 135 /// *before* submitting the updates because the internal update routine will 136 /// analyze the current state of the CFG to determine whether an update 137 /// is valid. 138 /// 2. It is illegal to submit any update that has already been submitted, 139 /// i.e., you are supposed not to insert an existent edge or delete a 140 /// nonexistent edge. 141 /// 3. It is only legal to submit updates to an edge in the order CFG changes 142 /// are made. The order you submit updates on different edges is not 143 /// restricted. 144 void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates); 145 146 /// Notify DTU that the entry block was replaced. 147 /// Recalculate all available trees and flush all BasicBlocks 148 /// awaiting deletion immediately. 149 void recalculate(Function &F); 150 151 /// \deprecated { Submit an edge insertion to all available trees. The Eager 152 /// Strategy flushes this update immediately while the Lazy Strategy queues 153 /// the update. An internal function checks if the edge exists in the CFG in 154 /// DEBUG mode. CAUTION! This function has to be called *after* making the 155 /// update on the actual CFG. It is illegal to submit any update that has 156 /// already been applied. } 157 LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To), 158 "Use applyUpdates() instead."); 159 160 /// \deprecated {Submit an edge insertion to all available trees. 161 /// Under either Strategy, an invalid update will be discard silently. 162 /// Invalid update means inserting an edge that does not exist in the CFG. 163 /// The Eager Strategy flushes this update immediately while the Lazy Strategy 164 /// queues the update. It is only recommended to use this method when you 165 /// want to discard an invalid update. 166 /// CAUTION! It is illegal to submit any update that has already been 167 /// submitted. } 168 LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From, 169 BasicBlock *To), 170 "Use applyUpdatesPermissive() instead."); 171 172 /// \deprecated { Submit an edge deletion to all available trees. The Eager 173 /// Strategy flushes this update immediately while the Lazy Strategy queues 174 /// the update. An internal function checks if the edge doesn't exist in the 175 /// CFG in DEBUG mode. 176 /// CAUTION! This function has to be called *after* making the update on the 177 /// actual CFG. It is illegal to submit any update that has already been 178 /// submitted. } 179 LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To), 180 "Use applyUpdates() instead."); 181 182 /// \deprecated { Submit an edge deletion to all available trees. 183 /// Under either Strategy, an invalid update will be discard silently. 184 /// Invalid update means deleting an edge that exists in the CFG. 185 /// The Eager Strategy flushes this update immediately while the Lazy Strategy 186 /// queues the update. It is only recommended to use this method when you 187 /// want to discard an invalid update. 188 /// CAUTION! It is illegal to submit any update that has already been 189 /// submitted. } 190 LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From, 191 BasicBlock *To), 192 "Use applyUpdatesPermissive() instead."); 193 194 /// Delete DelBB. DelBB will be removed from its Parent and 195 /// erased from available trees if it exists and finally get deleted. 196 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 197 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 198 /// all available trees are up-to-date. Assert if any instruction of DelBB is 199 /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB 200 /// will be queued until flush() is called. 201 void deleteBB(BasicBlock *DelBB); 202 203 /// Delete DelBB. DelBB will be removed from its Parent and 204 /// erased from available trees if it exists. Then the callback will 205 /// be called. Finally, DelBB will be deleted. 206 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 207 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 208 /// all available trees are up-to-date. Assert if any instruction of DelBB is 209 /// modified while awaiting deletion. Multiple callbacks can be queued for one 210 /// DelBB under Lazy UpdateStrategy. 211 void callbackDeleteBB(BasicBlock *DelBB, 212 std::function<void(BasicBlock *)> Callback); 213 214 ///@} 215 216 ///@{ 217 /// \name Flush APIs 218 /// 219 /// CAUTION! By the moment these flush APIs are called, the current CFG needs 220 /// to be the same as the CFG which DTU is in sync with + all updates 221 /// submitted. 222 223 /// Flush DomTree updates and return DomTree. 224 /// It flushes Deleted BBs if both trees are up-to-date. 225 /// It must only be called when it has a DomTree. 226 DominatorTree &getDomTree(); 227 228 /// Flush PostDomTree updates and return PostDomTree. 229 /// It flushes Deleted BBs if both trees are up-to-date. 230 /// It must only be called when it has a PostDomTree. 231 PostDominatorTree &getPostDomTree(); 232 233 /// Apply all pending updates to available trees and flush all BasicBlocks 234 /// awaiting deletion. 235 236 void flush(); 237 238 ///@} 239 240 /// Debug method to help view the internal state of this class. 241 LLVM_DUMP_METHOD void dump() const; 242 243 private: 244 class CallBackOnDeletion final : public CallbackVH { 245 public: 246 CallBackOnDeletion(BasicBlock *V, 247 std::function<void(BasicBlock *)> Callback) 248 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 249 250 private: 251 BasicBlock *DelBB = nullptr; 252 std::function<void(BasicBlock *)> Callback_; 253 254 void deleted() override { 255 Callback_(DelBB); 256 CallbackVH::deleted(); 257 } 258 }; 259 260 SmallVector<DominatorTree::UpdateType, 16> PendUpdates; 261 size_t PendDTUpdateIndex = 0; 262 size_t PendPDTUpdateIndex = 0; 263 DominatorTree *DT = nullptr; 264 PostDominatorTree *PDT = nullptr; 265 const UpdateStrategy Strategy; 266 SmallPtrSet<BasicBlock *, 8> DeletedBBs; 267 std::vector<CallBackOnDeletion> Callbacks; 268 bool IsRecalculatingDomTree = false; 269 bool IsRecalculatingPostDomTree = false; 270 271 /// First remove all the instructions of DelBB and then make sure DelBB has a 272 /// valid terminator instruction which is necessary to have when DelBB still 273 /// has to be inside of its parent Function while awaiting deletion under Lazy 274 /// UpdateStrategy to prevent other routines from asserting the state of the 275 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. 276 void validateDeleteBB(BasicBlock *DelBB); 277 278 /// Returns true if at least one BasicBlock is deleted. 279 bool forceFlushDeletedBB(); 280 281 /// Helper function to apply all pending DomTree updates. 282 void applyDomTreeUpdates(); 283 284 /// Helper function to apply all pending PostDomTree updates. 285 void applyPostDomTreeUpdates(); 286 287 /// Helper function to flush deleted BasicBlocks if all available 288 /// trees are up-to-date. 289 void tryFlushDeletedBB(); 290 291 /// Drop all updates applied by all available trees and delete BasicBlocks if 292 /// all available trees are up-to-date. 293 void dropOutOfDateUpdates(); 294 295 /// Erase Basic Block node that has been unlinked from Function 296 /// in the DomTree and PostDomTree. 297 void eraseDelBBNode(BasicBlock *DelBB); 298 299 /// Returns true if the update appears in the LLVM IR. 300 /// It is used to check whether an update is valid in 301 /// insertEdge/deleteEdge or is unnecessary in the batch update. 302 bool isUpdateValid(DominatorTree::UpdateType Update) const; 303 304 /// Returns true if the update is self dominance. 305 bool isSelfDominance(DominatorTree::UpdateType Update) const; 306 }; 307 } // namespace llvm 308 309 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H 310