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