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 DomTreeUpdater(UpdateStrategy Strategy_)31 explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {} DomTreeUpdater(DominatorTree & DT_,UpdateStrategy Strategy_)32 DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_) 33 : DT(&DT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree * DT_,UpdateStrategy Strategy_)34 DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_) 35 : DT(DT_), Strategy(Strategy_) {} DomTreeUpdater(PostDominatorTree & PDT_,UpdateStrategy Strategy_)36 DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_) 37 : PDT(&PDT_), Strategy(Strategy_) {} DomTreeUpdater(PostDominatorTree * PDT_,UpdateStrategy Strategy_)38 DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_) 39 : PDT(PDT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree & DT_,PostDominatorTree & PDT_,UpdateStrategy Strategy_)40 DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_, 41 UpdateStrategy Strategy_) 42 : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {} DomTreeUpdater(DominatorTree * DT_,PostDominatorTree * PDT_,UpdateStrategy Strategy_)43 DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_, 44 UpdateStrategy Strategy_) 45 : DT(DT_), PDT(PDT_), Strategy(Strategy_) {} 46 ~DomTreeUpdater()47 ~DomTreeUpdater() { flush(); } 48 49 /// Returns true if the current strategy is Lazy. isLazy()50 bool isLazy() const { return Strategy == UpdateStrategy::Lazy; }; 51 52 /// Returns true if the current strategy is Eager. isEager()53 bool isEager() const { return Strategy == UpdateStrategy::Eager; }; 54 55 /// Returns true if it holds a DominatorTree. hasDomTree()56 bool hasDomTree() const { return DT != nullptr; } 57 58 /// Returns true if it holds a PostDominatorTree. hasPostDomTree()59 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. hasPendingDeletedBB()65 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: CallBackOnDeletion(BasicBlock * V,std::function<void (BasicBlock *)> Callback)189 CallBackOnDeletion(BasicBlock *V, 190 std::function<void(BasicBlock *)> Callback) 191 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 192 193 private: 194 BasicBlock *DelBB = nullptr; 195 std::function<void(BasicBlock *)> Callback_; 196 deleted()197 void deleted() override { 198 Callback_(DelBB); 199 CallbackVH::deleted(); 200 } 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 258