124 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements simple dominator construction algorithms for finding10// 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 18using namespace llvm;19 20namespace llvm {21template class LLVM_EXPORT_TEMPLATE22 DominatorTreeBase<MachineBasicBlock, true>; // PostDomTreeBase23 24namespace DomTreeBuilder {25 26template LLVM_EXPORT_TEMPLATE void27Calculate<MBBPostDomTree>(MBBPostDomTree &DT);28template LLVM_EXPORT_TEMPLATE void29InsertEdge<MBBPostDomTree>(MBBPostDomTree &DT, MachineBasicBlock *From,30 MachineBasicBlock *To);31template LLVM_EXPORT_TEMPLATE void32DeleteEdge<MBBPostDomTree>(MBBPostDomTree &DT, MachineBasicBlock *From,33 MachineBasicBlock *To);34template LLVM_EXPORT_TEMPLATE void35ApplyUpdates<MBBPostDomTree>(MBBPostDomTree &DT, MBBPostDomTreeGraphDiff &,36 MBBPostDomTreeGraphDiff *);37template LLVM_EXPORT_TEMPLATE bool38Verify<MBBPostDomTree>(const MBBPostDomTree &DT,39 MBBPostDomTree::VerificationLevel VL);40 41} // namespace DomTreeBuilder42extern bool VerifyMachineDomInfo;43} // namespace llvm44 45AnalysisKey MachinePostDominatorTreeAnalysis::Key;46 47MachinePostDominatorTreeAnalysis::Result48MachinePostDominatorTreeAnalysis::run(MachineFunction &MF,49 MachineFunctionAnalysisManager &) {50 return MachinePostDominatorTree(MF);51}52 53PreservedAnalyses54MachinePostDominatorTreePrinterPass::run(MachineFunction &MF,55 MachineFunctionAnalysisManager &MFAM) {56 OS << "MachinePostDominatorTree for machine function: " << MF.getName()57 << '\n';58 MFAM.getResult<MachinePostDominatorTreeAnalysis>(MF).print(OS);59 return PreservedAnalyses::all();60}61 62char MachinePostDominatorTreeWrapperPass::ID = 0;63 64//declare initializeMachinePostDominatorTreePass65INITIALIZE_PASS(MachinePostDominatorTreeWrapperPass, "machinepostdomtree",66 "MachinePostDominator Tree Construction", true, true)67 68MachinePostDominatorTreeWrapperPass::MachinePostDominatorTreeWrapperPass()69 : MachineFunctionPass(ID), PDT() {70 initializeMachinePostDominatorTreeWrapperPassPass(71 *PassRegistry::getPassRegistry());72}73 74bool MachinePostDominatorTreeWrapperPass::runOnMachineFunction(75 MachineFunction &F) {76 PDT = MachinePostDominatorTree();77 PDT->recalculate(F);78 return false;79}80 81void MachinePostDominatorTreeWrapperPass::getAnalysisUsage(82 AnalysisUsage &AU) const {83 AU.setPreservesAll();84 MachineFunctionPass::getAnalysisUsage(AU);85}86 87bool MachinePostDominatorTree::invalidate(88 MachineFunction &, const PreservedAnalyses &PA,89 MachineFunctionAnalysisManager::Invalidator &) {90 // Check whether the analysis, all analyses on machine functions, or the91 // machine function's CFG have been preserved.92 auto PAC = PA.getChecker<MachinePostDominatorTreeAnalysis>();93 return !PAC.preserved() &&94 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&95 !PAC.preservedSet<CFGAnalyses>();96}97 98MachineBasicBlock *MachinePostDominatorTree::findNearestCommonDominator(99 ArrayRef<MachineBasicBlock *> Blocks) const {100 assert(!Blocks.empty());101 102 MachineBasicBlock *NCD = Blocks.consume_front();103 for (MachineBasicBlock *BB : Blocks) {104 NCD = Base::findNearestCommonDominator(NCD, BB);105 106 // Stop when the root is reached.107 if (isVirtualRoot(getNode(NCD)))108 return nullptr;109 }110 111 return NCD;112}113 114void MachinePostDominatorTreeWrapperPass::verifyAnalysis() const {115 if (VerifyMachineDomInfo && PDT &&116 !PDT->verify(MachinePostDominatorTree::VerificationLevel::Basic))117 report_fatal_error("MachinePostDominatorTree verification failed!");118}119 120void MachinePostDominatorTreeWrapperPass::print(llvm::raw_ostream &OS,121 const Module *M) const {122 PDT->print(OS);123}124