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