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. 163 /// Under Lazy Strategy, available trees will only be recalculated if there 164 /// are pending updates or there is BasicBlock awaiting deletion. Returns true 165 /// if at least one tree is recalculated. 166 bool recalculate(Function &F); 167 168 /// Flush DomTree updates and return DomTree. 169 /// It also flush out of date updates applied by all available trees 170 /// and flush Deleted BBs if both trees are up-to-date. 171 /// It must only be called when it has a DomTree. 172 DominatorTree &getDomTree(); 173 174 /// Flush PostDomTree updates and return PostDomTree. 175 /// It also flush out of date updates applied by all available trees 176 /// and flush Deleted BBs if both trees are up-to-date. 177 /// It must only be called when it has a PostDomTree. 178 PostDominatorTree &getPostDomTree(); 179 180 /// Apply all pending updates to available trees and flush all BasicBlocks 181 /// awaiting deletion. 182 /// Does nothing under Eager UpdateStrategy. 183 void flush(); 184 185 /// Debug method to help view the internal state of this class. 186 LLVM_DUMP_METHOD void dump() const; 187 188 private: 189 class CallBackOnDeletion final : public CallbackVH { 190 public: CallBackOnDeletion(BasicBlock * V,std::function<void (BasicBlock *)> Callback)191 CallBackOnDeletion(BasicBlock *V, 192 std::function<void(BasicBlock *)> Callback) 193 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 194 195 private: 196 BasicBlock *DelBB = nullptr; 197 std::function<void(BasicBlock *)> Callback_; 198 deleted()199 void deleted() override { 200 Callback_(DelBB); 201 CallbackVH::deleted(); 202 } 203 }; 204 205 SmallVector<DominatorTree::UpdateType, 16> PendUpdates; 206 size_t PendDTUpdateIndex = 0; 207 size_t PendPDTUpdateIndex = 0; 208 DominatorTree *DT = nullptr; 209 PostDominatorTree *PDT = nullptr; 210 const UpdateStrategy Strategy; 211 SmallPtrSet<BasicBlock *, 8> DeletedBBs; 212 std::vector<CallBackOnDeletion> Callbacks; 213 bool IsRecalculatingDomTree = false; 214 bool IsRecalculatingPostDomTree = false; 215 216 /// First remove all the instructions of DelBB and then make sure DelBB has a 217 /// valid terminator instruction which is necessary to have when DelBB still 218 /// has to be inside of its parent Function while awaiting deletion under Lazy 219 /// UpdateStrategy to prevent other routines from asserting the state of the 220 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. 221 void validateDeleteBB(BasicBlock *DelBB); 222 223 /// Returns true if at least one BasicBlock is deleted. 224 bool forceFlushDeletedBB(); 225 226 /// Deduplicate and remove unnecessary updates (no-ops) when using Lazy 227 /// UpdateStrategy. Returns true if the update is queued for update. 228 bool applyLazyUpdate(DominatorTree::UpdateKind Kind, BasicBlock *From, 229 BasicBlock *To); 230 231 /// Helper function to apply all pending DomTree updates. 232 void applyDomTreeUpdates(); 233 234 /// Helper function to apply all pending PostDomTree updates. 235 void applyPostDomTreeUpdates(); 236 237 /// Helper function to flush deleted BasicBlocks if all available 238 /// trees are up-to-date. 239 void tryFlushDeletedBB(); 240 241 /// Drop all updates applied by all available trees and delete BasicBlocks if 242 /// all available trees are up-to-date. 243 void dropOutOfDateUpdates(); 244 245 /// Erase Basic Block node that has been unlinked from Function 246 /// in the DomTree and PostDomTree. 247 void eraseDelBBNode(BasicBlock *DelBB); 248 249 /// Returns true if the update appears in the LLVM IR. 250 /// It is used to check whether an update is valid in 251 /// insertEdge/deleteEdge or is unnecessary in the batch update. 252 bool isUpdateValid(DominatorTree::UpdateType Update) const; 253 254 /// Returns true if the update is self dominance. 255 bool isSelfDominance(DominatorTree::UpdateType Update) const; 256 }; 257 } // namespace llvm 258 259 #endif // LLVM_DOMTREEUPDATER_H 260