MachinePostDominators.cpp revision 360784
1//===- MachinePostDominators.cpp -Machine Post Dominator Calculation ------===// 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 simple dominator construction algorithms for finding 10// post dominators on machine functions. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/CodeGen/MachinePostDominators.h" 15#include "llvm/InitializePasses.h" 16 17using namespace llvm; 18 19namespace llvm { 20template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase 21 22extern bool VerifyMachineDomInfo; 23} // namespace llvm 24 25char MachinePostDominatorTree::ID = 0; 26 27//declare initializeMachinePostDominatorTreePass 28INITIALIZE_PASS(MachinePostDominatorTree, "machinepostdomtree", 29 "MachinePostDominator Tree Construction", true, true) 30 31MachinePostDominatorTree::MachinePostDominatorTree() 32 : MachineFunctionPass(ID), PDT(nullptr) { 33 initializeMachinePostDominatorTreePass(*PassRegistry::getPassRegistry()); 34} 35 36FunctionPass *MachinePostDominatorTree::createMachinePostDominatorTreePass() { 37 return new MachinePostDominatorTree(); 38} 39 40bool MachinePostDominatorTree::runOnMachineFunction(MachineFunction &F) { 41 PDT = std::make_unique<PostDomTreeT>(); 42 PDT->recalculate(F); 43 return false; 44} 45 46void MachinePostDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { 47 AU.setPreservesAll(); 48 MachineFunctionPass::getAnalysisUsage(AU); 49} 50 51MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator( 52 ArrayRef<MachineBasicBlock *> Blocks) const { 53 assert(!Blocks.empty()); 54 55 MachineBasicBlock *NCD = Blocks.front(); 56 for (MachineBasicBlock *BB : Blocks.drop_front()) { 57 NCD = PDT->findNearestCommonDominator(NCD, BB); 58 59 // Stop when the root is reached. 60 if (PDT->isVirtualRoot(PDT->getNode(NCD))) 61 return nullptr; 62 } 63 64 return NCD; 65} 66 67void MachinePostDominatorTree::verifyAnalysis() const { 68 if (PDT && VerifyMachineDomInfo) 69 if (!PDT->verify(PostDomTreeT::VerificationLevel::Basic)) { 70 errs() << "MachinePostDominatorTree verification failed\n"; 71 72 abort(); 73 } 74} 75 76void MachinePostDominatorTree::print(llvm::raw_ostream &OS, 77 const Module *M) const { 78 PDT->print(OS); 79} 80