1243789Sdim//===- MachinePostDominators.cpp -Machine Post Dominator Calculation ------===// 2243789Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6243789Sdim// 7243789Sdim//===----------------------------------------------------------------------===// 8243789Sdim// 9243789Sdim// This file implements simple dominator construction algorithms for finding 10243789Sdim// post dominators on machine functions. 11243789Sdim// 12243789Sdim//===----------------------------------------------------------------------===// 13243789Sdim 14243789Sdim#include "llvm/CodeGen/MachinePostDominators.h" 15360784Sdim#include "llvm/InitializePasses.h" 16243789Sdim 17243789Sdimusing namespace llvm; 18243789Sdim 19321369Sdimnamespace llvm { 20321369Sdimtemplate class DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase 21321369Sdim 22360784Sdimextern bool VerifyMachineDomInfo; 23360784Sdim} // namespace llvm 24360784Sdim 25243789Sdimchar MachinePostDominatorTree::ID = 0; 26243789Sdim 27243789Sdim//declare initializeMachinePostDominatorTreePass 28243789SdimINITIALIZE_PASS(MachinePostDominatorTree, "machinepostdomtree", 29243789Sdim "MachinePostDominator Tree Construction", true, true) 30243789Sdim 31360784SdimMachinePostDominatorTree::MachinePostDominatorTree() 32360784Sdim : MachineFunctionPass(ID), PDT(nullptr) { 33243789Sdim initializeMachinePostDominatorTreePass(*PassRegistry::getPassRegistry()); 34243789Sdim} 35243789Sdim 36360784SdimFunctionPass *MachinePostDominatorTree::createMachinePostDominatorTreePass() { 37243789Sdim return new MachinePostDominatorTree(); 38243789Sdim} 39243789Sdim 40360784Sdimbool MachinePostDominatorTree::runOnMachineFunction(MachineFunction &F) { 41360784Sdim PDT = std::make_unique<PostDomTreeT>(); 42360784Sdim PDT->recalculate(F); 43243789Sdim return false; 44243789Sdim} 45243789Sdim 46360784Sdimvoid MachinePostDominatorTree::getAnalysisUsage(AnalysisUsage &AU) const { 47243789Sdim AU.setPreservesAll(); 48243789Sdim MachineFunctionPass::getAnalysisUsage(AU); 49243789Sdim} 50243789Sdim 51360784SdimMachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator( 52360784Sdim ArrayRef<MachineBasicBlock *> Blocks) const { 53360784Sdim assert(!Blocks.empty()); 54360784Sdim 55360784Sdim MachineBasicBlock *NCD = Blocks.front(); 56360784Sdim for (MachineBasicBlock *BB : Blocks.drop_front()) { 57360784Sdim NCD = PDT->findNearestCommonDominator(NCD, BB); 58360784Sdim 59360784Sdim // Stop when the root is reached. 60360784Sdim if (PDT->isVirtualRoot(PDT->getNode(NCD))) 61360784Sdim return nullptr; 62360784Sdim } 63360784Sdim 64360784Sdim return NCD; 65243789Sdim} 66360784Sdim 67360784Sdimvoid MachinePostDominatorTree::verifyAnalysis() const { 68360784Sdim if (PDT && VerifyMachineDomInfo) 69360784Sdim if (!PDT->verify(PostDomTreeT::VerificationLevel::Basic)) { 70360784Sdim errs() << "MachinePostDominatorTree verification failed\n"; 71360784Sdim 72360784Sdim abort(); 73360784Sdim } 74360784Sdim} 75360784Sdim 76360784Sdimvoid MachinePostDominatorTree::print(llvm::raw_ostream &OS, 77360784Sdim const Module *M) const { 78360784Sdim PDT->print(OS); 79360784Sdim} 80