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 #include "llvm/Support/GenericDomTreeConstruction.h" 17 18 using namespace llvm; 19 20 namespace llvm { 21 template class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase 22 23 namespace DomTreeBuilder { 24 25 template void Calculate<MBBPostDomTree>(MBBPostDomTree &DT); 26 template void InsertEdge<MBBPostDomTree>(MBBPostDomTree &DT, 27 MachineBasicBlock *From, 28 MachineBasicBlock *To); 29 template void DeleteEdge<MBBPostDomTree>(MBBPostDomTree &DT, 30 MachineBasicBlock *From, 31 MachineBasicBlock *To); 32 template void ApplyUpdates<MBBPostDomTree>(MBBPostDomTree &DT, 33 MBBPostDomTreeGraphDiff &, 34 MBBPostDomTreeGraphDiff *); 35 template bool Verify<MBBPostDomTree>(const MBBPostDomTree &DT, 36 MBBPostDomTree::VerificationLevel VL); 37 38 } // namespace DomTreeBuilder 39 extern bool VerifyMachineDomInfo; 40 } // namespace llvm 41 42 char MachinePostDominatorTreeWrapperPass::ID = 0; 43 44 //declare initializeMachinePostDominatorTreePass 45 INITIALIZE_PASS(MachinePostDominatorTreeWrapperPass, "machinepostdomtree", 46 "MachinePostDominator Tree Construction", true, true) 47 48 MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass() 49 : MachineFunctionPass(ID), PDT() { 50 initializeMachinePostDominatorTreeWrapperPassPass( 51 *PassRegistry::getPassRegistry()); 52 } 53 54 bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction( 55 MachineFunction &F) { 56 PDT = MachinePostDominatorTree(); 57 PDT->recalculate(F); 58 return false; 59 } 60 61 void MachinePostDominatorTreeWrapperPass::getAnalysisUsage( 62 AnalysisUsage &AU) const { 63 AU.setPreservesAll(); 64 MachineFunctionPass::getAnalysisUsage(AU); 65 } 66 67 MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator( 68 ArrayRef<MachineBasicBlock *> Blocks) const { 69 assert(!Blocks.empty()); 70 71 MachineBasicBlock *NCD = Blocks.front(); 72 for (MachineBasicBlock *BB : Blocks.drop_front()) { 73 NCD = Base::findNearestCommonDominator(NCD, BB); 74 75 // Stop when the root is reached. 76 if (isVirtualRoot(getNode(NCD))) 77 return nullptr; 78 } 79 80 return NCD; 81 } 82 83 void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const { 84 if (VerifyMachineDomInfo && PDT && 85 !PDT->verify(MachinePostDominatorTree::VerificationLevel::Basic)) 86 report_fatal_error("MachinePostDominatorTree verification failed!"); 87 } 88 89 void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS, 90 const Module *M) const { 91 PDT->print(OS); 92 } 93