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 17 using namespace llvm; 18 19 namespace llvm { 20 template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase 21 22 extern bool VerifyMachineDomInfo; 23 } // namespace llvm 24 25 char MachinePostDominatorTree::ID = 0; 26 27 //declare initializeMachinePostDominatorTreePass 28 INITIALIZE_PASS(MachinePostDominatorTree, "machinepostdomtree", 29 "MachinePostDominator Tree Construction", true, true) 30 31 MachinePostDominatorTree::MachinePostDominatorTree() 32 : MachineFunctionPass(ID), PDT(nullptr) { 33 initializeMachinePostDominatorTreePass(*PassRegistry::getPassRegistry()); 34 } 35 36 FunctionPass *MachinePostDominatorTree::createMachinePostDominatorTreePass() { 37 return new MachinePostDominatorTree(); 38 } 39 40 bool MachinePostDominatorTree::runOnMachineFunction(MachineFunction &F) { 41 PDT = std::make_unique<PostDomTreeT>(); 42 PDT->recalculate(F); 43 return false; 44 } 45 46 void MachinePostDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { 47 AU.setPreservesAll(); 48 MachineFunctionPass::getAnalysisUsage(AU); 49 } 50 51 MachineBasicBlock *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 67 void 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 76 void MachinePostDominatorTree::print(llvm::raw_ostream &OS, 77 const Module *M) const { 78 PDT->print(OS); 79 } 80