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/GenericDomTreeUpdater.h" 18 #include "llvm/IR/Dominators.h" 19 #include "llvm/IR/ValueHandle.h" 20 #include "llvm/Support/Compiler.h" 21 #include <functional> 22 #include <vector> 23 24 namespace llvm { 25 26 class PostDominatorTree; 27 28 class DomTreeUpdater 29 : public GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, 30 PostDominatorTree> { 31 friend GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, 32 PostDominatorTree>; 33 34 public: 35 using Base = 36 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>; 37 using Base::Base; 38 39 ~DomTreeUpdater() { flush(); } 40 41 ///@{ 42 /// \name Mutation APIs 43 /// 44 /// These methods provide APIs for submitting updates to the DominatorTree and 45 /// the PostDominatorTree. 46 /// 47 /// Note: There are two strategies to update the DominatorTree and the 48 /// PostDominatorTree: 49 /// 1. Eager UpdateStrategy: Updates are submitted and then flushed 50 /// immediately. 51 /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you 52 /// explicitly call Flush APIs. It is recommended to use this update strategy 53 /// when you submit a bunch of updates multiple times which can then 54 /// add up to a large number of updates between two queries on the 55 /// DominatorTree. The incremental updater can reschedule the updates or 56 /// decide to recalculate the dominator tree in order to speedup the updating 57 /// process depending on the number of updates. 58 /// 59 /// Although GenericDomTree provides several update primitives, 60 /// it is not encouraged to use these APIs directly. 61 62 /// Delete DelBB. DelBB will be removed from its Parent and 63 /// erased from available trees if it exists and finally get deleted. 64 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 65 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 66 /// all available trees are up-to-date. Assert if any instruction of DelBB is 67 /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB 68 /// will be queued until flush() is called. 69 void deleteBB(BasicBlock *DelBB); 70 71 /// Delete DelBB. DelBB will be removed from its Parent and 72 /// erased from available trees if it exists. Then the callback will 73 /// be called. Finally, DelBB will be deleted. 74 /// Under Eager UpdateStrategy, DelBB will be processed immediately. 75 /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and 76 /// all available trees are up-to-date. Assert if any instruction of DelBB is 77 /// modified while awaiting deletion. Multiple callbacks can be queued for one 78 /// DelBB under Lazy UpdateStrategy. 79 void callbackDeleteBB(BasicBlock *DelBB, 80 std::function<void(BasicBlock *)> Callback); 81 82 ///@} 83 84 /// Debug method to help view the internal state of this class. 85 LLVM_DUMP_METHOD void dump() const; 86 87 private: 88 class CallBackOnDeletion final : public CallbackVH { 89 public: 90 CallBackOnDeletion(BasicBlock *V, 91 std::function<void(BasicBlock *)> Callback) 92 : CallbackVH(V), DelBB(V), Callback_(Callback) {} 93 94 private: 95 BasicBlock *DelBB = nullptr; 96 std::function<void(BasicBlock *)> Callback_; 97 98 void deleted() override { 99 Callback_(DelBB); 100 CallbackVH::deleted(); 101 } 102 }; 103 104 std::vector<CallBackOnDeletion> Callbacks; 105 106 /// First remove all the instructions of DelBB and then make sure DelBB has a 107 /// valid terminator instruction which is necessary to have when DelBB still 108 /// has to be inside of its parent Function while awaiting deletion under Lazy 109 /// UpdateStrategy to prevent other routines from asserting the state of the 110 /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors. 111 void validateDeleteBB(BasicBlock *DelBB); 112 113 /// Returns true if at least one BasicBlock is deleted. 114 bool forceFlushDeletedBB(); 115 }; 116 117 extern template class GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, 118 PostDominatorTree>; 119 120 extern template void 121 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, 122 PostDominatorTree>::recalculate(Function &F); 123 124 extern template void 125 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>:: 126 applyUpdatesImpl</*IsForward=*/true>(); 127 extern template void 128 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>:: 129 applyUpdatesImpl</*IsForward=*/false>(); 130 } // namespace llvm 131 132 #endif // LLVM_ANALYSIS_DOMTREEUPDATER_H 133