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