1ac9a064cSDimitry Andric //===- MachineDomTreeUpdater.cpp -----------------------------------------===// 2ac9a064cSDimitry Andric // 3ac9a064cSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4ac9a064cSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5ac9a064cSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6ac9a064cSDimitry Andric // 7ac9a064cSDimitry Andric //===----------------------------------------------------------------------===// 8ac9a064cSDimitry Andric // 9ac9a064cSDimitry Andric // This file implements the MachineDomTreeUpdater class, which provides a 10ac9a064cSDimitry Andric // uniform way to update dominator tree related data structures. 11ac9a064cSDimitry Andric // 12ac9a064cSDimitry Andric //===----------------------------------------------------------------------===// 13ac9a064cSDimitry Andric 14ac9a064cSDimitry Andric #include "llvm/CodeGen/MachineDomTreeUpdater.h" 15ac9a064cSDimitry Andric #include "llvm/ADT/SmallSet.h" 16ac9a064cSDimitry Andric #include "llvm/Analysis/GenericDomTreeUpdaterImpl.h" 17ac9a064cSDimitry Andric #include "llvm/CodeGen/MachinePostDominators.h" 18ac9a064cSDimitry Andric #include "llvm/Support/GenericDomTree.h" 19ac9a064cSDimitry Andric #include <algorithm> 20ac9a064cSDimitry Andric #include <functional> 21ac9a064cSDimitry Andric #include <utility> 22ac9a064cSDimitry Andric 23ac9a064cSDimitry Andric namespace llvm { 24ac9a064cSDimitry Andric 25ac9a064cSDimitry Andric template class GenericDomTreeUpdater< 26ac9a064cSDimitry Andric MachineDomTreeUpdater, MachineDominatorTree, MachinePostDominatorTree>; 27ac9a064cSDimitry Andric 28ac9a064cSDimitry Andric template void 29ac9a064cSDimitry Andric GenericDomTreeUpdater<MachineDomTreeUpdater, MachineDominatorTree, 30ac9a064cSDimitry Andric MachinePostDominatorTree>::recalculate(MachineFunction 31ac9a064cSDimitry Andric &MF); 32ac9a064cSDimitry Andric forceFlushDeletedBB()33ac9a064cSDimitry Andricbool MachineDomTreeUpdater::forceFlushDeletedBB() { 34ac9a064cSDimitry Andric if (DeletedBBs.empty()) 35ac9a064cSDimitry Andric return false; 36ac9a064cSDimitry Andric 37ac9a064cSDimitry Andric for (auto *BB : DeletedBBs) { 38ac9a064cSDimitry Andric eraseDelBBNode(BB); 39ac9a064cSDimitry Andric BB->eraseFromParent(); 40ac9a064cSDimitry Andric } 41ac9a064cSDimitry Andric DeletedBBs.clear(); 42ac9a064cSDimitry Andric return true; 43ac9a064cSDimitry Andric } 44ac9a064cSDimitry Andric 45ac9a064cSDimitry Andric // The DT and PDT require the nodes related to updates 46ac9a064cSDimitry Andric // are not deleted when update functions are called. 47ac9a064cSDimitry Andric // So MachineBasicBlock deletions must be pended when the 48ac9a064cSDimitry Andric // UpdateStrategy is Lazy. When the UpdateStrategy is 49ac9a064cSDimitry Andric // Eager, the MachineBasicBlock will be deleted immediately. deleteBB(MachineBasicBlock * DelBB)50ac9a064cSDimitry Andricvoid MachineDomTreeUpdater::deleteBB(MachineBasicBlock *DelBB) { 51ac9a064cSDimitry Andric validateDeleteBB(DelBB); 52ac9a064cSDimitry Andric if (Strategy == UpdateStrategy::Lazy) { 53ac9a064cSDimitry Andric DeletedBBs.insert(DelBB); 54ac9a064cSDimitry Andric return; 55ac9a064cSDimitry Andric } 56ac9a064cSDimitry Andric 57ac9a064cSDimitry Andric eraseDelBBNode(DelBB); 58ac9a064cSDimitry Andric DelBB->eraseFromParent(); 59ac9a064cSDimitry Andric } 60ac9a064cSDimitry Andric validateDeleteBB(MachineBasicBlock * DelBB)61ac9a064cSDimitry Andricvoid MachineDomTreeUpdater::validateDeleteBB(MachineBasicBlock *DelBB) { 62ac9a064cSDimitry Andric assert(DelBB && "Invalid push_back of nullptr DelBB."); 63ac9a064cSDimitry Andric assert(DelBB->pred_empty() && "DelBB has one or more predecessors."); 64ac9a064cSDimitry Andric } 65ac9a064cSDimitry Andric 66ac9a064cSDimitry Andric } // namespace llvm 67