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