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