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 25 namespace llvm { 26 class PostDominatorTree; 27 28 class DomTreeUpdater { 29 public: 30 enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 }; 31 DomTreeUpdater(UpdateStrategy Strategy_)32 explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} DomTreeUpdater(DominatorTree & DT_,UpdateStrategy Strategy_)33 DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) 34 : DT(&DT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree * DT_,UpdateStrategy Strategy_)35 DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) 36 : DT(DT_), Strategy(Strategy_) {} DomTreeUpdater(PostDominatorTree & PDT_,UpdateStrategy Strategy_)37 DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) 38 : PDT(&PDT_), Strategy(Strategy_) {} DomTreeUpdater(PostDominatorTree * PDT_,UpdateStrategy Strategy_)39 DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) 40 : PDT(PDT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree & DT_,PostDominatorTree & PDT_,UpdateStrategy Strategy_)41 DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, 42 UpdateStrategy Strategy_) 43 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree * DT_,PostDominatorTree * PDT_,UpdateStrategy Strategy_)44 DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, 45 UpdateStrategy Strategy_) 46 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} 47 ~DomTreeUpdater()48 ~DomTreeUpdater() { flush(); } 49 50 /// Returns true if the current strategy is Lazy. isLazy()51 bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; 52 53 /// Returns true if the current strategy is Eager. isEager()54 bool isEager() const { return Strategy == UpdateStrategy::Eager; }; 55 56 /// Returns true if it holds a DominatorTree. hasDomTree()57 bool hasDomTree() const { return DT != nullptr; } 58 59 /// Returns true if it holds a PostDominatorTree. hasPostDomTree()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. hasPendingDeletedBB()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 /// \deprecated { Submit an edge insertion to all available trees. The Eager 154 /// Strategy flushes this update immediately while the Lazy Strategy queues 155 /// the update. An internal function checks if the edge exists in the CFG in 156 /// DEBUG mode. CAUTION! This function has to be called *after* making the 157 /// update on the actual CFG. It is illegal to submit any update that has 158 /// already been applied. } 159 LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To), 160 "Use applyUpdates() instead."); 161 162 /// \deprecated {Submit an edge insertion to all available trees. 163 /// Under either Strategy, an invalid update will be discard silently. 164 /// Invalid update means inserting an edge that does not exist in the CFG. 165 /// The Eager Strategy flushes this update immediately while the Lazy Strategy 166 /// queues the update. It is only recommended to use this method when you 167 /// want to discard an invalid update. 168 /// CAUTION! It is illegal to submit any update that has already been 169 /// submitted. } 170 LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From, 171 BasicBlock *To), 172 "Use applyUpdatesPermissive() instead."); 173 174 /// \deprecated { Submit an edge deletion to all available trees. The Eager 175 /// Strategy flushes this update immediately while the Lazy Strategy queues 176 /// the update. An internal function checks if the edge doesn't exist in the 177 /// CFG in DEBUG mode. 178 /// CAUTION! This function has to be called *after* making the update on the 179 /// actual CFG. It is illegal to submit any update that has already been 180 /// submitted. } 181 LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To), 182 "Use applyUpdates() instead."); 183 184 /// \deprecated { Submit an edge deletion to all available trees. 185 /// Under either Strategy, an invalid update will be discard silently. 186 /// Invalid update means deleting an edge that exists in the CFG. 187 /// The Eager Strategy flushes this update immediately while the Lazy Strategy 188 /// queues the update. It is only recommended to use this method when you 189 /// want to discard an invalid update. 190 /// CAUTION! It is illegal to submit any update that has already been 191 /// submitted. } 192 LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From, 193 BasicBlock *To), 194 "Use applyUpdatesPermissive() instead."); 195 196 /// Delete DelBB. DelBB will be removed from its Parent and 197 /// erased from available trees if it exists and finally get deleted. 198 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 199 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 200 /// all available trees are up-to-date. Assert if any instruction of DelBB is 201 /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB 202 /// will be queued until flush() is called. 203 void deleteBB(BasicBlock *DelBB); 204 205 /// Delete DelBB. DelBB will be removed from its Parent and 206 /// erased from available trees if it exists. Then the callback will 207 /// be called. Finally, DelBB will be deleted. 208 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 209 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 210 /// all available trees are up-to-date. Assert if any instruction of DelBB is 211 /// modified while awaiting deletion. Multiple callbacks can be queued for one 212 /// DelBB under Lazy UpdateStrategy. 213 void callbackDeleteBB(BasicBlock *DelBB, 214 std::function<void(BasicBlock *)> Callback); 215 216 ///@} 217 218 ///@{ 219 /// \name Flush APIs 220 /// 221 /// CAUTION! By the moment these flush APIs are called, the current CFG needs 222 /// to be the same as the CFG which DTU is in sync with + all updates 223 /// submitted. 224 225 /// Flush DomTree updates and return DomTree. 226 /// It flushes Deleted BBs if both trees are up-to-date. 227 /// It must only be called when it has a DomTree. 228 DominatorTree &getDomTree(); 229 230 /// Flush PostDomTree updates and return PostDomTree. 231 /// It flushes Deleted BBs if both trees are up-to-date. 232 /// It must only be called when it has a PostDomTree. 233 PostDominatorTree &getPostDomTree(); 234 235 /// Apply all pending updates to available trees and flush all BasicBlocks 236 /// awaiting deletion. 237 238 void flush(); 239 240 ///@} 241 242 /// Debug method to help view the internal state of this class. 243 LLVM_DUMP_METHOD void dump() const; 244 245 private: 246 class CallBackOnDeletion final : public CallbackVH { 247 public: CallBackOnDeletion(BasicBlock * V,std::function<void (BasicBlock *)> Callback)248 CallBackOnDeletion(BasicBlock *V, 249 std::function<void(BasicBlock *)> Callback) 250 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 251 252 private: 253 BasicBlock *DelBB = nullptr; 254 std::function<void(BasicBlock *)> Callback_; 255 deleted()256 void deleted() override { 257 Callback_(DelBB); 258 CallbackVH::deleted(); 259 } 260 }; 261 262 SmallVector<DominatorTree::UpdateType, 16> PendUpdates; 263 size_t PendDTUpdateIndex = 0; 264 size_t PendPDTUpdateIndex = 0; 265 DominatorTree *DT = nullptr; 266 PostDominatorTree *PDT = nullptr; 267 const UpdateStrategy Strategy; 268 SmallPtrSet<BasicBlock *, 8> DeletedBBs; 269 std::vector<CallBackOnDeletion> Callbacks; 270 bool IsRecalculatingDomTree = false; 271 bool IsRecalculatingPostDomTree = false; 272 273 /// First remove all the instructions of DelBB and then make sure DelBB has a 274 /// valid terminator instruction which is necessary to have when DelBB still 275 /// has to be inside of its parent Function while awaiting deletion under Lazy 276 /// UpdateStrategy to prevent other routines from asserting the state of the 277 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. 278 void validateDeleteBB(BasicBlock *DelBB); 279 280 /// Returns true if at least one BasicBlock is deleted. 281 bool forceFlushDeletedBB(); 282 283 /// Helper function to apply all pending DomTree updates. 284 void applyDomTreeUpdates(); 285 286 /// Helper function to apply all pending PostDomTree updates. 287 void applyPostDomTreeUpdates(); 288 289 /// Helper function to flush deleted BasicBlocks if all available 290 /// trees are up-to-date. 291 void tryFlushDeletedBB(); 292 293 /// Drop all updates applied by all available trees and delete BasicBlocks if 294 /// all available trees are up-to-date. 295 void dropOutOfDateUpdates(); 296 297 /// Erase Basic Block node that has been unlinked from Function 298 /// in the DomTree and PostDomTree. 299 void eraseDelBBNode(BasicBlock *DelBB); 300 301 /// Returns true if the update appears in the LLVM IR. 302 /// It is used to check whether an update is valid in 303 /// insertEdge/deleteEdge or is unnecessary in the batch update. 304 bool isUpdateValid(DominatorTree::UpdateType Update) const; 305 306 /// Returns true if the update is self dominance. 307 bool isSelfDominance(DominatorTree::UpdateType Update) const; 308 }; 309 } // namespace llvm 310 311 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H 312