llvm/CodeGen/MachineDominators.h

0001 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines classes mirroring those in llvm/Analysis/Dominators.h,
0010 // but for target-specific code rather than target-independent IR.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H
0015 #define LLVM_CODEGEN_MACHINEDOMINATORS_H
0016
0017 #include "llvm/ADT/SmallSet.h"
0018 #include "llvm/ADT/SmallVector.h"
0019 #include "llvm/CodeGen/MachineBasicBlock.h"
0020 #include "llvm/CodeGen/MachineFunctionPass.h"
0021 #include "llvm/CodeGen/MachineInstr.h"
0022 #include "llvm/CodeGen/MachineInstrBundleIterator.h"
0023 #include "llvm/CodeGen/MachinePassManager.h"
0024 #include "llvm/Support/GenericDomTree.h"
0025 #include <cassert>
0026 #include <memory>
0027 #include <optional>
0028
0029 namespace llvm {
0030 class AnalysisUsage;
0031 class MachineFunction;
0032 class Module;
0033 class raw_ostream;
0034
0035 template <>
0036 inline void DominatorTreeBase<MachineBasicBlock, false>::addRoot(
0037     MachineBasicBlock *MBB) {
0038   this->Roots.push_back(MBB);
0039 }
0040
0041 extern template class DomTreeNodeBase<MachineBasicBlock>;
0042 extern template class DominatorTreeBase<MachineBasicBlock, false>; // DomTree
0043
0044 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
0045
0046 namespace DomTreeBuilder {
0047 using MBBDomTree = DomTreeBase<MachineBasicBlock>;
0048 using MBBUpdates = ArrayRef<llvm::cfg::Update<MachineBasicBlock *>>;
0049 using MBBDomTreeGraphDiff = GraphDiff<MachineBasicBlock *, false>;
0050
0051 extern template void Calculate<MBBDomTree>(MBBDomTree &DT);
0052 extern template void CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT,
0053                                                       MBBUpdates U);
0054
0055 extern template void InsertEdge<MBBDomTree>(MBBDomTree &DT,
0056                                             MachineBasicBlock *From,
0057                                             MachineBasicBlock *To);
0058
0059 extern template void DeleteEdge<MBBDomTree>(MBBDomTree &DT,
0060                                             MachineBasicBlock *From,
0061                                             MachineBasicBlock *To);
0062
0063 extern template void ApplyUpdates<MBBDomTree>(MBBDomTree &DT,
0064                                               MBBDomTreeGraphDiff &,
0065                                               MBBDomTreeGraphDiff *);
0066
0067 extern template bool Verify<MBBDomTree>(const MBBDomTree &DT,
0068                                         MBBDomTree::VerificationLevel VL);
0069 } // namespace DomTreeBuilder
0070
0071 //===-------------------------------------
0072 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
0073 /// compute a normal dominator tree.
0074 ///
0075 class MachineDominatorTree : public DomTreeBase<MachineBasicBlock> {
0076
0077 public:
0078   using Base = DomTreeBase<MachineBasicBlock>;
0079
0080   MachineDominatorTree() = default;
0081   explicit MachineDominatorTree(MachineFunction &MF) { recalculate(MF); }
0082
0083   /// Handle invalidation explicitly.
0084   bool invalidate(MachineFunction &, const PreservedAnalyses &PA,
0085                   MachineFunctionAnalysisManager::Invalidator &);
0086
0087   using Base::dominates;
0088
0089   // dominates - Return true if A dominates B. This performs the
0090   // special checks necessary if A and B are in the same basic block.
0091   bool dominates(const MachineInstr *A, const MachineInstr *B) const {
0092     const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
0093     if (BBA != BBB)
0094       return Base::dominates(BBA, BBB);
0095
0096     // Loop through the basic block until we find A or B.
0097     MachineBasicBlock::const_iterator I = BBA->begin();
0098     for (; &*I != A && &*I != B; ++I)
0099       /*empty*/ ;
0100
0101     return &*I == A;
0102   }
0103 };
0104
0105 /// \brief Analysis pass which computes a \c MachineDominatorTree.
0106 class MachineDominatorTreeAnalysis
0107     : public AnalysisInfoMixin<MachineDominatorTreeAnalysis> {
0108   friend AnalysisInfoMixin<MachineDominatorTreeAnalysis>;
0109
0110   static AnalysisKey Key;
0111
0112 public:
0113   using Result = MachineDominatorTree;
0114
0115   Result run(MachineFunction &MF, MachineFunctionAnalysisManager &);
0116 };
0117
0118 /// \brief Machine function pass which print \c MachineDominatorTree.
0119 class MachineDominatorTreePrinterPass
0120     : public PassInfoMixin<MachineDominatorTreePrinterPass> {
0121   raw_ostream &OS;
0122
0123 public:
0124   explicit MachineDominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
0125   PreservedAnalyses run(MachineFunction &MF,
0126                         MachineFunctionAnalysisManager &MFAM);
0127   static bool isRequired() { return true; }
0128 };
0129
0130 /// \brief Analysis pass which computes a \c MachineDominatorTree.
0131 class MachineDominatorTreeWrapperPass : public MachineFunctionPass {
0132   // MachineFunctionPass may verify the analysis result without running pass,
0133   // e.g. when `F.hasAvailableExternallyLinkage` is true.
0134   std::optional<MachineDominatorTree> DT;
0135
0136 public:
0137   static char ID;
0138
0139   MachineDominatorTreeWrapperPass();
0140
0141   MachineDominatorTree &getDomTree() { return *DT; }
0142   const MachineDominatorTree &getDomTree() const { return *DT; }
0143
0144   bool runOnMachineFunction(MachineFunction &MF) override;
0145
0146   void verifyAnalysis() const override;
0147
0148   void getAnalysisUsage(AnalysisUsage &AU) const override {
0149     AU.setPreservesAll();
0150     MachineFunctionPass::getAnalysisUsage(AU);
0151   }
0152
0153   void releaseMemory() override;
0154
0155   void print(raw_ostream &OS, const Module *M = nullptr) const override;
0156 };
0157
0158 //===-------------------------------------
0159 /// DominatorTree GraphTraits specialization so the DominatorTree can be
0160 /// iterable by generic graph iterators.
0161 ///
0162
0163 template <class Node, class ChildIterator>
0164 struct MachineDomTreeGraphTraitsBase {
0165   using NodeRef = Node *;
0166   using ChildIteratorType = ChildIterator;
0167
0168   static NodeRef getEntryNode(NodeRef N) { return N; }
0169   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
0170   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
0171 };
0172
0173 template <class T> struct GraphTraits;
0174
0175 template <>
0176 struct GraphTraits<MachineDomTreeNode *>
0177     : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
0178                                            MachineDomTreeNode::const_iterator> {
0179 };
0180
0181 template <>
0182 struct GraphTraits<const MachineDomTreeNode *>
0183     : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
0184                                            MachineDomTreeNode::const_iterator> {
0185 };
0186
0187 template <> struct GraphTraits<MachineDominatorTree*>
0188   : public GraphTraits<MachineDomTreeNode *> {
0189   static NodeRef getEntryNode(MachineDominatorTree *DT) {
0190     return DT->getRootNode();
0191   }
0192 };
0193
0194 } // end namespace llvm
0195
0196 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H