125 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the DomTreeUpdater class, which provides a uniform way10// 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 23namespace llvm {24 25template class LLVM_EXPORT_TEMPLATE26 GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>;27 28template LLVM_EXPORT_TEMPLATE void29GenericDomTreeUpdater<DomTreeUpdater, DominatorTree,30 PostDominatorTree>::recalculate(Function &F);31 32template LLVM_EXPORT_TEMPLATE void33GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>::34 applyUpdatesImpl</*IsForward=*/true>();35template LLVM_EXPORT_TEMPLATE void36GenericDomTreeUpdater<DomTreeUpdater, DominatorTree, PostDominatorTree>::37 applyUpdatesImpl</*IsForward=*/false>();38 39bool 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 an46 // UnreachableInst as its terminator. So we check whether the BasicBlock to47 // 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 updates59// are not deleted when update functions are called.60// So BasicBlock deletions must be pended when the61// UpdateStrategy is Lazy. When the UpdateStrategy is62// Eager, the BasicBlock will be deleted immediately.63void 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 74void 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 89void 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 a101 // Child of Function F it must contain valid IR.102 new UnreachableInst(DelBB->getContext(), DelBB);103}104 105LLVM_DUMP_METHOD106void 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 else118 OS << "(no_name)(";119 OS << BB << ")\n";120 }121#endif122}123 124} // namespace llvm125