1 //==- llvm/CodeGen/MachineDominators.h - Machine Dom Calculation -*- C++ -*-==// 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 defines classes mirroring those in llvm/Analysis/Dominators.h, 10 // but for target-specific code rather than target-independent IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_MACHINEDOMINATORS_H 15 #define LLVM_CODEGEN_MACHINEDOMINATORS_H 16 17 #include "llvm/ADT/SmallSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/CodeGen/MachineBasicBlock.h" 20 #include "llvm/CodeGen/MachineFunctionPass.h" 21 #include "llvm/CodeGen/MachineInstr.h" 22 #include "llvm/CodeGen/MachineInstrBundleIterator.h" 23 #include "llvm/CodeGen/MachinePassManager.h" 24 #include "llvm/Support/Compiler.h" 25 #include "llvm/Support/GenericDomTree.h" 26 #include <cassert> 27 #include <memory> 28 #include <optional> 29 30 namespace llvm { 31 class AnalysisUsage; 32 class MachineFunction; 33 class Module; 34 class raw_ostream; 35 36 extern template class LLVM_TEMPLATE_ABI DomTreeNodeBase<MachineBasicBlock>; 37 extern template class LLVM_TEMPLATE_ABI 38 DominatorTreeBase<MachineBasicBlock, false>; // DomTree 39 40 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>; 41 42 namespace DomTreeBuilder { 43 using MBBDomTree = DomTreeBase<MachineBasicBlock>; 44 using MBBUpdates = ArrayRef<llvm::cfg::Update<MachineBasicBlock *>>; 45 using MBBDomTreeGraphDiff = GraphDiff<MachineBasicBlock *, false>; 46 47 extern template LLVM_TEMPLATE_ABI void Calculate<MBBDomTree>(MBBDomTree &DT); 48 extern template LLVM_TEMPLATE_ABI void 49 CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U); 50 51 extern template LLVM_TEMPLATE_ABI void 52 InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 53 MachineBasicBlock *To); 54 55 extern template LLVM_TEMPLATE_ABI void 56 DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From, 57 MachineBasicBlock *To); 58 59 extern template LLVM_TEMPLATE_ABI void 60 ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &, 61 MBBDomTreeGraphDiff *); 62 63 extern template LLVM_TEMPLATE_ABI bool 64 Verify<MBBDomTree>(const MBBDomTree &DT, MBBDomTree::VerificationLevel VL); 65 } // namespace DomTreeBuilder 66 67 //===------------------------------------- 68 /// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to 69 /// compute a normal dominator tree. 70 /// 71 class MachineDominatorTree : public DomTreeBase<MachineBasicBlock> { 72 73 public: 74 using Base = DomTreeBase<MachineBasicBlock>; 75 76 MachineDominatorTree() = default; MachineDominatorTree(MachineFunction & MF)77 explicit MachineDominatorTree(MachineFunction &MF) { recalculate(MF); } 78 79 /// Handle invalidation explicitly. 80 LLVM_ABI bool invalidate(MachineFunction &, const PreservedAnalyses &PA, 81 MachineFunctionAnalysisManager::Invalidator &); 82 83 using Base::dominates; 84 85 // dominates - Return true if A dominates B. This performs the 86 // special checks necessary if A and B are in the same basic block. dominates(const MachineInstr * A,const MachineInstr * B)87 bool dominates(const MachineInstr *A, const MachineInstr *B) const { 88 const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent(); 89 if (BBA != BBB) 90 return Base::dominates(BBA, BBB); 91 92 // Loop through the basic block until we find A or B. 93 MachineBasicBlock::const_iterator I = BBA->begin(); 94 for (; &*I != A && &*I != B; ++I) 95 /*empty*/ ; 96 97 return &*I == A; 98 } 99 }; 100 101 /// \brief Analysis pass which computes a \c MachineDominatorTree. 102 class MachineDominatorTreeAnalysis 103 : public AnalysisInfoMixin<MachineDominatorTreeAnalysis> { 104 friend AnalysisInfoMixin<MachineDominatorTreeAnalysis>; 105 106 LLVM_ABI static AnalysisKey Key; 107 108 public: 109 using Result = MachineDominatorTree; 110 111 LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &); 112 }; 113 114 /// \brief Machine function pass which print \c MachineDominatorTree. 115 class MachineDominatorTreePrinterPass 116 : public PassInfoMixin<MachineDominatorTreePrinterPass> { 117 raw_ostream &OS; 118 119 public: MachineDominatorTreePrinterPass(raw_ostream & OS)120 explicit MachineDominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {} 121 LLVM_ABI PreservedAnalyses run(MachineFunction &MF, 122 MachineFunctionAnalysisManager &MFAM); isRequired()123 static bool isRequired() { return true; } 124 }; 125 126 /// \brief Analysis pass which computes a \c MachineDominatorTree. 127 class LLVM_ABI MachineDominatorTreeWrapperPass : public MachineFunctionPass { 128 // MachineFunctionPass may verify the analysis result without running pass, 129 // e.g. when `F.hasAvailableExternallyLinkage` is true. 130 std::optional<MachineDominatorTree> DT; 131 132 public: 133 static char ID; 134 135 MachineDominatorTreeWrapperPass(); 136 getDomTree()137 MachineDominatorTree &getDomTree() { return *DT; } getDomTree()138 const MachineDominatorTree &getDomTree() const { return *DT; } 139 140 bool runOnMachineFunction(MachineFunction &MF) override; 141 142 void verifyAnalysis() const override; 143 getAnalysisUsage(AnalysisUsage & AU)144 void getAnalysisUsage(AnalysisUsage &AU) const override { 145 AU.setPreservesAll(); 146 MachineFunctionPass::getAnalysisUsage(AU); 147 } 148 149 void releaseMemory() override; 150 151 void print(raw_ostream &OS, const Module *M = nullptr) const override; 152 }; 153 154 //===------------------------------------- 155 /// DominatorTree GraphTraits specialization so the DominatorTree can be 156 /// iterable by generic graph iterators. 157 /// 158 159 template <class Node, class ChildIterator> 160 struct MachineDomTreeGraphTraitsBase { 161 using NodeRef = Node *; 162 using ChildIteratorType = ChildIterator; 163 getEntryNodeMachineDomTreeGraphTraitsBase164 static NodeRef getEntryNode(NodeRef N) { return N; } child_beginMachineDomTreeGraphTraitsBase165 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } child_endMachineDomTreeGraphTraitsBase166 static ChildIteratorType child_end(NodeRef N) { return N->end(); } 167 }; 168 169 template <class T> struct GraphTraits; 170 171 template <> 172 struct GraphTraits<MachineDomTreeNode *> 173 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode, 174 MachineDomTreeNode::const_iterator> { 175 }; 176 177 template <> 178 struct GraphTraits<const MachineDomTreeNode *> 179 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode, 180 MachineDomTreeNode::const_iterator> { 181 }; 182 183 template <> struct GraphTraits<MachineDominatorTree*> 184 : public GraphTraits<MachineDomTreeNode *> { 185 static NodeRef getEntryNode(MachineDominatorTree *DT) { 186 return DT->getRootNode(); 187 } 188 }; 189 190 } // end namespace llvm 191 192 #endif // LLVM_CODEGEN_MACHINEDOMINATORS_H 193