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 32 explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} 33 DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) 34 : DT(&DT_), Strategy(Strategy_) {} 35 DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) 36 : DT(DT_), Strategy(Strategy_) {} 37 DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) 38 : PDT(&PDT_), Strategy(Strategy_) {} 39 DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) 40 : PDT(PDT_), Strategy(Strategy_) {} 41 DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, 42 UpdateStrategy Strategy_) 43 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} 44 DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, 45 UpdateStrategy Strategy_) 46 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} 47 48 ~DomTreeUpdater() { flush(); } 49 50 /// Returns true if the current strategy is Lazy. 51 bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; 52 53 /// Returns true if the current strategy is Eager. 54 bool isEager() const { return Strategy == UpdateStrategy::Eager; }; 55 56 /// Returns true if it holds a DominatorTree. 57 bool hasDomTree() const { return DT != nullptr; } 58 59 /// Returns true if it holds a PostDominatorTree. 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. 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 /// Delete DelBB. DelBB will be removed from its Parent and 154 /// erased from available trees if it exists and finally get deleted. 155 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 156 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 157 /// all available trees are up-to-date. Assert if any instruction of DelBB is 158 /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB 159 /// will be queued until flush() is called. 160 void deleteBB(BasicBlock *DelBB); 161 162 /// Delete DelBB. DelBB will be removed from its Parent and 163 /// erased from available trees if it exists. Then the callback will 164 /// be called. Finally, DelBB will be deleted. 165 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 166 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 167 /// all available trees are up-to-date. Assert if any instruction of DelBB is 168 /// modified while awaiting deletion. Multiple callbacks can be queued for one 169 /// DelBB under Lazy UpdateStrategy. 170 void callbackDeleteBB(BasicBlock *DelBB, 171 std::function<void(BasicBlock *)> Callback); 172 173 ///@} 174 175 ///@{ 176 /// \name Flush APIs 177 /// 178 /// CAUTION! By the moment these flush APIs are called, the current CFG needs 179 /// to be the same as the CFG which DTU is in sync with + all updates 180 /// submitted. 181 182 /// Flush DomTree updates and return DomTree. 183 /// It flushes Deleted BBs if both trees are up-to-date. 184 /// It must only be called when it has a DomTree. 185 DominatorTree &getDomTree(); 186 187 /// Flush PostDomTree updates and return PostDomTree. 188 /// It flushes Deleted BBs if both trees are up-to-date. 189 /// It must only be called when it has a PostDomTree. 190 PostDominatorTree &getPostDomTree(); 191 192 /// Apply all pending updates to available trees and flush all BasicBlocks 193 /// awaiting deletion. 194 195 void flush(); 196 197 ///@} 198 199 /// Debug method to help view the internal state of this class. 200 LLVM_DUMP_METHOD void dump() const; 201 202 private: 203 class CallBackOnDeletion final : public CallbackVH { 204 public: 205 CallBackOnDeletion(BasicBlock *V, 206 std::function<void(BasicBlock *)> Callback) 207 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 208 209 private: 210 BasicBlock *DelBB = nullptr; 211 std::function<void(BasicBlock *)> Callback_; 212 213 void deleted() override { 214 Callback_(DelBB); 215 CallbackVH::deleted(); 216 } 217 }; 218 219 SmallVector<DominatorTree::UpdateType, 16> PendUpdates; 220 size_t PendDTUpdateIndex = 0; 221 size_t PendPDTUpdateIndex = 0; 222 DominatorTree *DT = nullptr; 223 PostDominatorTree *PDT = nullptr; 224 const UpdateStrategy Strategy; 225 SmallPtrSet<BasicBlock *, 8> DeletedBBs; 226 std::vector<CallBackOnDeletion> Callbacks; 227 bool IsRecalculatingDomTree = false; 228 bool IsRecalculatingPostDomTree = false; 229 230 /// First remove all the instructions of DelBB and then make sure DelBB has a 231 /// valid terminator instruction which is necessary to have when DelBB still 232 /// has to be inside of its parent Function while awaiting deletion under Lazy 233 /// UpdateStrategy to prevent other routines from asserting the state of the 234 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. 235 void validateDeleteBB(BasicBlock *DelBB); 236 237 /// Returns true if at least one BasicBlock is deleted. 238 bool forceFlushDeletedBB(); 239 240 /// Helper function to apply all pending DomTree updates. 241 void applyDomTreeUpdates(); 242 243 /// Helper function to apply all pending PostDomTree updates. 244 void applyPostDomTreeUpdates(); 245 246 /// Helper function to flush deleted BasicBlocks if all available 247 /// trees are up-to-date. 248 void tryFlushDeletedBB(); 249 250 /// Drop all updates applied by all available trees and delete BasicBlocks if 251 /// all available trees are up-to-date. 252 void dropOutOfDateUpdates(); 253 254 /// Erase Basic Block node that has been unlinked from Function 255 /// in the DomTree and PostDomTree. 256 void eraseDelBBNode(BasicBlock *DelBB); 257 258 /// Returns true if the update appears in the LLVM IR. 259 /// It is used to check whether an update is valid in 260 /// insertEdge/deleteEdge or is unnecessary in the batch update. 261 bool isUpdateValid(DominatorTree::UpdateType Update) const; 262 263 /// Returns true if the update is self dominance. 264 bool isSelfDominance(DominatorTree::UpdateType Update) const; 265 }; 266 } // namespace llvm 267 268 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H 269