1 //===- DomTreeUpdater.cpp - 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 implements the DomTreeUpdater class, which provides a uniform way 10 // to update dominator tree related data structures. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/DomTreeUpdater.h" 15 #include "llvm/Analysis/GenericDomTreeUpdaterImpl.h" 16 #include "llvm/Analysis/PostDominators.h" 17 #include "llvm/IR/Constants.h" 18 #include "llvm/IR/Instructions.h" 19 #include "llvm/Support/Compiler.h" 20 #include "llvm/Support/GenericDomTree.h" 21 #include <functional> 22 23 namespace llvm { 24 25 template class LLVM_EXPORT_TEMPLATE 26 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>; 27 28 template LLVM_EXPORT_TEMPLATE void 29 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, 30 PostDominatorTree>::recalculate(Function &F); 31 32 template LLVM_EXPORT_TEMPLATE void 33 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>:: 34 applyUpdatesImpl</*IsForward=*/true>(); 35 template LLVM_EXPORT_TEMPLATE void 36 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>:: 37 applyUpdatesImpl</*IsForward=*/false>(); 38 39 bool DomTreeUpdater::forceFlushDeletedBB() { 40 if (DeletedBBs.empty()) 41 return false; 42 43 for (auto *BB : DeletedBBs) { 44 // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy, 45 // validateDeleteBB() removes all instructions of DelBB and adds an 46 // UnreachableInst as its terminator. So we check whether the BasicBlock to 47 // delete only has an UnreachableInst inside. 48 assert(BB->size() == 1 && isa<UnreachableInst>(BB->getTerminator()) && 49 "DelBB has been modified while awaiting deletion."); 50 eraseDelBBNode(BB); 51 BB->eraseFromParent(); 52 } 53 DeletedBBs.clear(); 54 Callbacks.clear(); 55 return true; 56 } 57 58 // The DT and PDT require the nodes related to updates 59 // are not deleted when update functions are called. 60 // So BasicBlock deletions must be pended when the 61 // UpdateStrategy is Lazy. When the UpdateStrategy is 62 // Eager, the BasicBlock will be deleted immediately. 63 void DomTreeUpdater::deleteBB(BasicBlock *DelBB) { 64 validateDeleteBB(DelBB); 65 if (Strategy == UpdateStrategy::Lazy) { 66 DeletedBBs.insert(DelBB); 67 return; 68 } 69 70 eraseDelBBNode(DelBB); 71 DelBB->eraseFromParent(); 72 } 73 74 void DomTreeUpdater::callbackDeleteBB( 75 BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) { 76 validateDeleteBB(DelBB); 77 if (Strategy == UpdateStrategy::Lazy) { 78 Callbacks.push_back(CallBackOnDeletion(DelBB, Callback)); 79 DeletedBBs.insert(DelBB); 80 return; 81 } 82 83 eraseDelBBNode(DelBB); 84 DelBB->removeFromParent(); 85 Callback(DelBB); 86 delete DelBB; 87 } 88 89 void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) { 90 assert(DelBB && "Invalid push_back of nullptr DelBB."); 91 assert(pred_empty(DelBB) && "DelBB has one or more predecessors."); 92 // DelBB is unreachable and all its instructions are dead. 93 while (!DelBB->empty()) { 94 Instruction &I = DelBB->back(); 95 // Replace used instructions with an arbitrary value (poison). 96 if (!I.use_empty()) 97 I.replaceAllUsesWith(PoisonValue::get(I.getType())); 98 DelBB->back().eraseFromParent(); 99 } 100 // Make sure DelBB has a valid terminator instruction. As long as DelBB is a 101 // Child of Function F it must contain valid IR. 102 new UnreachableInst(DelBB->getContext(), DelBB); 103 } 104 105 LLVM_DUMP_METHOD 106 void DomTreeUpdater::dump() const { 107 Base::dump(); 108 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 109 raw_ostream &OS = dbgs(); 110 OS << "Pending Callbacks:\n"; 111 int Index = 0; 112 for (const auto &BB : Callbacks) { 113 OS << " " << Index << " : "; 114 ++Index; 115 if (BB->hasName()) 116 OS << BB->getName() << "("; 117 else 118 OS << "(no_name)("; 119 OS << BB << ")\n"; 120 } 121 #endif 122 } 123 124 } // namespace llvm 125