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
30namespace llvm {
31class AnalysisUsage;
32class MachineFunction;
33class Module;
34class raw_ostream;
35
36extern template class LLVM_TEMPLATE_ABI DomTreeNodeBase<MachineBasicBlock>;
37extern template class LLVM_TEMPLATE_ABI
38 DominatorTreeBase<MachineBasicBlock, false>; // DomTree
39
40using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
41
42namespace DomTreeBuilder {
43using MBBDomTree = DomTreeBase<MachineBasicBlock>;
44using MBBUpdates = ArrayRef<llvm::cfg::Update<MachineBasicBlock *>>;
45using MBBDomTreeGraphDiff = GraphDiff<MachineBasicBlock *, false>;
46
47extern template LLVM_TEMPLATE_ABI void Calculate<MBBDomTree>(MBBDomTree &DT);
48extern template LLVM_TEMPLATE_ABI void
49CalculateWithUpdates<MBBDomTree>(MBBDomTree &DT, MBBUpdates U);
50
51extern template LLVM_TEMPLATE_ABI void
52InsertEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
53 MachineBasicBlock *To);
54
55extern template LLVM_TEMPLATE_ABI void
56DeleteEdge<MBBDomTree>(MBBDomTree &DT, MachineBasicBlock *From,
57 MachineBasicBlock *To);
58
59extern template LLVM_TEMPLATE_ABI void
60ApplyUpdates<MBBDomTree>(MBBDomTree &DT, MBBDomTreeGraphDiff &,
61 MBBDomTreeGraphDiff *);
62
63extern template LLVM_TEMPLATE_ABI bool
64Verify<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///
71class MachineDominatorTree : public DomTreeBase<MachineBasicBlock> {
72
73public:
74 using Base = DomTreeBase<MachineBasicBlock>;
75
76 MachineDominatorTree() = default;
77 explicit MachineDominatorTree(MachineFunction &MF) { recalculate(Func&: 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.
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(A: BBA, B: 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.
102class MachineDominatorTreeAnalysis
103 : public AnalysisInfoMixin<MachineDominatorTreeAnalysis> {
104 friend AnalysisInfoMixin<MachineDominatorTreeAnalysis>;
105
106 LLVM_ABI static AnalysisKey Key;
107
108public:
109 using Result = MachineDominatorTree;
110
111 LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &);
112};
113
114/// \brief Machine function pass which print \c MachineDominatorTree.
115class MachineDominatorTreePrinterPass
116 : public PassInfoMixin<MachineDominatorTreePrinterPass> {
117 raw_ostream &OS;
118
119public:
120 explicit MachineDominatorTreePrinterPass(raw_ostream &OS) : OS(OS) {}
121 LLVM_ABI PreservedAnalyses run(MachineFunction &MF,
122 MachineFunctionAnalysisManager &MFAM);
123 static bool isRequired() { return true; }
124};
125
126/// \brief Analysis pass which computes a \c MachineDominatorTree.
127class 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
132public:
133 static char ID;
134
135 MachineDominatorTreeWrapperPass();
136
137 MachineDominatorTree &getDomTree() { return *DT; }
138 const MachineDominatorTree &getDomTree() const { return *DT; }
139
140 bool runOnMachineFunction(MachineFunction &MF) override;
141
142 void verifyAnalysis() const override;
143
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
159template <class Node, class ChildIterator>
160struct MachineDomTreeGraphTraitsBase {
161 using NodeRef = Node *;
162 using ChildIteratorType = ChildIterator;
163
164 static NodeRef getEntryNode(NodeRef N) { return N; }
165 static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
166 static ChildIteratorType child_end(NodeRef N) { return N->end(); }
167};
168
169template <class T> struct GraphTraits;
170
171template <>
172struct GraphTraits<MachineDomTreeNode *>
173 : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
174 MachineDomTreeNode::const_iterator> {
175};
176
177template <>
178struct GraphTraits<const MachineDomTreeNode *>
179 : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
180 MachineDomTreeNode::const_iterator> {
181};
182
183template <> 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