| 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(Registry&: *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(Func&: 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(A: NCD, B: BB); |
| 58 | |
| 59 | // Stop when the root is reached. |
| 60 | if (PDT->isVirtualRoot(A: PDT->getNode(BB: NCD))) |
| 61 | return nullptr; |
| 62 | } |
| 63 | |
| 64 | return NCD; |
| 65 | } |
| 66 | |
| 67 | void MachinePostDominatorTree::verifyAnalysis() const { |
| 68 | if (PDT && VerifyMachineDomInfo) |
| 69 | if (!PDT->verify(VL: 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(O&: OS); |
| 79 | } |
| 80 |