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