1 | //==--- llvm/CodeGen/ReachingDefAnalysis.h - Reaching Def Analysis -*- 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 | /// \file Reaching Defs Analysis pass. |
10 | /// |
11 | /// This pass tracks for each instruction what is the "closest" reaching def of |
12 | /// a given register. It is used by BreakFalseDeps (for clearance calculation) |
13 | /// and ExecutionDomainFix (for arbitrating conflicting domains). |
14 | /// |
15 | /// Note that this is different from the usual definition notion of liveness. |
16 | /// The CPU doesn't care whether or not we consider a register killed. |
17 | /// |
18 | // |
19 | //===----------------------------------------------------------------------===// |
20 | |
21 | #ifndef LLVM_CODEGEN_REACHINGDEFANALYSIS_H |
22 | #define LLVM_CODEGEN_REACHINGDEFANALYSIS_H |
23 | |
24 | #include "llvm/ADT/DenseMap.h" |
25 | #include "llvm/ADT/SmallVector.h" |
26 | #include "llvm/ADT/TinyPtrVector.h" |
27 | #include "llvm/CodeGen/LoopTraversal.h" |
28 | #include "llvm/CodeGen/MachineFunctionPass.h" |
29 | #include "llvm/InitializePasses.h" |
30 | |
31 | namespace llvm { |
32 | |
33 | class MachineBasicBlock; |
34 | class MachineInstr; |
35 | |
36 | /// Thin wrapper around "int" used to store reaching definitions, |
37 | /// using an encoding that makes it compatible with TinyPtrVector. |
38 | /// The 0th LSB is forced zero (and will be used for pointer union tagging), |
39 | /// The 1st LSB is forced one (to make sure the value is non-zero). |
40 | class ReachingDef { |
41 | uintptr_t Encoded; |
42 | friend struct PointerLikeTypeTraits<ReachingDef>; |
43 | explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {} |
44 | |
45 | public: |
46 | ReachingDef(std::nullptr_t) : Encoded(0) {} |
47 | ReachingDef(int Instr) : Encoded(((uintptr_t) Instr << 2) | 2) {} |
48 | operator int() const { return ((int) Encoded) >> 2; } |
49 | }; |
50 | |
51 | template<> |
52 | struct PointerLikeTypeTraits<ReachingDef> { |
53 | static constexpr int NumLowBitsAvailable = 1; |
54 | |
55 | static inline void *getAsVoidPointer(const ReachingDef &RD) { |
56 | return reinterpret_cast<void *>(RD.Encoded); |
57 | } |
58 | |
59 | static inline ReachingDef getFromVoidPointer(void *P) { |
60 | return ReachingDef(reinterpret_cast<uintptr_t>(P)); |
61 | } |
62 | |
63 | static inline ReachingDef getFromVoidPointer(const void *P) { |
64 | return ReachingDef(reinterpret_cast<uintptr_t>(P)); |
65 | } |
66 | }; |
67 | |
68 | /// This class provides the reaching def analysis. |
69 | class ReachingDefAnalysis : public MachineFunctionPass { |
70 | private: |
71 | MachineFunction *MF = nullptr; |
72 | const TargetRegisterInfo *TRI = nullptr; |
73 | LoopTraversal::TraversalOrder TraversedMBBOrder; |
74 | unsigned NumRegUnits = 0; |
75 | /// Instruction that defined each register, relative to the beginning of the |
76 | /// current basic block. When a LiveRegsDefInfo is used to represent a |
77 | /// live-out register, this value is relative to the end of the basic block, |
78 | /// so it will be a negative number. |
79 | using LiveRegsDefInfo = std::vector<int>; |
80 | LiveRegsDefInfo LiveRegs; |
81 | |
82 | /// Keeps clearance information for all registers. Note that this |
83 | /// is different from the usual definition notion of liveness. The CPU |
84 | /// doesn't care whether or not we consider a register killed. |
85 | using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>; |
86 | OutRegsInfoMap MBBOutRegsInfos; |
87 | |
88 | /// Current instruction number. |
89 | /// The first instruction in each basic block is 0. |
90 | int CurInstr = -1; |
91 | |
92 | /// Maps instructions to their instruction Ids, relative to the beginning of |
93 | /// their basic blocks. |
94 | DenseMap<MachineInstr *, int> InstIds; |
95 | |
96 | /// All reaching defs of a given RegUnit for a given MBB. |
97 | using MBBRegUnitDefs = TinyPtrVector<ReachingDef>; |
98 | /// All reaching defs of all reg units for a given MBB |
99 | using MBBDefsInfo = std::vector<MBBRegUnitDefs>; |
100 | /// All reaching defs of all reg units for a all MBBs |
101 | using MBBReachingDefsInfo = SmallVector<MBBDefsInfo, 4>; |
102 | MBBReachingDefsInfo MBBReachingDefs; |
103 | |
104 | /// Default values are 'nothing happened a long time ago'. |
105 | const int ReachingDefDefaultVal = -(1 << 21); |
106 | |
107 | using InstSet = SmallPtrSetImpl<MachineInstr*>; |
108 | using BlockSet = SmallPtrSetImpl<MachineBasicBlock*>; |
109 | |
110 | public: |
111 | static char ID; // Pass identification, replacement for typeid |
112 | |
113 | ReachingDefAnalysis() : MachineFunctionPass(ID) { |
114 | initializeReachingDefAnalysisPass(*PassRegistry::getPassRegistry()); |
115 | } |
116 | void releaseMemory() override; |
117 | |
118 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
119 | AU.setPreservesAll(); |
120 | MachineFunctionPass::getAnalysisUsage(AU); |
121 | } |
122 | |
123 | bool runOnMachineFunction(MachineFunction &MF) override; |
124 | |
125 | MachineFunctionProperties getRequiredProperties() const override { |
126 | return MachineFunctionProperties().set( |
127 | MachineFunctionProperties::Property::NoVRegs).set( |
128 | MachineFunctionProperties::Property::TracksLiveness); |
129 | } |
130 | |
131 | /// Re-run the analysis. |
132 | void reset(); |
133 | |
134 | /// Initialize data structures. |
135 | void init(); |
136 | |
137 | /// Traverse the machine function, mapping definitions. |
138 | void traverse(); |
139 | |
140 | /// Provides the instruction id of the closest reaching def instruction of |
141 | /// PhysReg that reaches MI, relative to the begining of MI's basic block. |
142 | int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const; |
143 | |
144 | /// Return whether A and B use the same def of PhysReg. |
145 | bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, |
146 | MCRegister PhysReg) const; |
147 | |
148 | /// Return whether the reaching def for MI also is live out of its parent |
149 | /// block. |
150 | bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const; |
151 | |
152 | /// Return the local MI that produces the live out value for PhysReg, or |
153 | /// nullptr for a non-live out or non-local def. |
154 | MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB, |
155 | MCRegister PhysReg) const; |
156 | |
157 | /// If a single MachineInstr creates the reaching definition, then return it. |
158 | /// Otherwise return null. |
159 | MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, |
160 | MCRegister PhysReg) const; |
161 | |
162 | /// If a single MachineInstr creates the reaching definition, for MIs operand |
163 | /// at Idx, then return it. Otherwise return null. |
164 | MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const; |
165 | |
166 | /// If a single MachineInstr creates the reaching definition, for MIs MO, |
167 | /// then return it. Otherwise return null. |
168 | MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const; |
169 | |
170 | /// Provide whether the register has been defined in the same basic block as, |
171 | /// and before, MI. |
172 | bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const; |
173 | |
174 | /// Return whether the given register is used after MI, whether it's a local |
175 | /// use or a live out. |
176 | bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const; |
177 | |
178 | /// Return whether the given register is defined after MI. |
179 | bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const; |
180 | |
181 | /// Provides the clearance - the number of instructions since the closest |
182 | /// reaching def instuction of PhysReg that reaches MI. |
183 | int getClearance(MachineInstr *MI, MCRegister PhysReg) const; |
184 | |
185 | /// Provides the uses, in the same block as MI, of register that MI defines. |
186 | /// This does not consider live-outs. |
187 | void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, |
188 | InstSet &Uses) const; |
189 | |
190 | /// Search MBB for a definition of PhysReg and insert it into Defs. If no |
191 | /// definition is found, recursively search the predecessor blocks for them. |
192 | void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, |
193 | BlockSet &VisitedBBs) const; |
194 | void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, |
195 | InstSet &Defs) const; |
196 | |
197 | /// For the given block, collect the instructions that use the live-in |
198 | /// value of the provided register. Return whether the value is still |
199 | /// live on exit. |
200 | bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, |
201 | InstSet &Uses) const; |
202 | |
203 | /// Collect the users of the value stored in PhysReg, which is defined |
204 | /// by MI. |
205 | void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const; |
206 | |
207 | /// Collect all possible definitions of the value stored in PhysReg, which is |
208 | /// used by MI. |
209 | void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, |
210 | InstSet &Defs) const; |
211 | |
212 | /// Return whether From can be moved forwards to just before To. |
213 | bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const; |
214 | |
215 | /// Return whether From can be moved backwards to just after To. |
216 | bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const; |
217 | |
218 | /// Assuming MI is dead, recursively search the incoming operands which are |
219 | /// killed by MI and collect those that would become dead. |
220 | void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const; |
221 | |
222 | /// Return whether removing this instruction will have no effect on the |
223 | /// program, returning the redundant use-def chain. |
224 | bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const; |
225 | |
226 | /// Return whether removing this instruction will have no effect on the |
227 | /// program, ignoring the possible effects on some instructions, returning |
228 | /// the redundant use-def chain. |
229 | bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove, |
230 | InstSet &Ignore) const; |
231 | |
232 | /// Return whether a MachineInstr could be inserted at MI and safely define |
233 | /// the given register without affecting the program. |
234 | bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const; |
235 | |
236 | /// Return whether a MachineInstr could be inserted at MI and safely define |
237 | /// the given register without affecting the program, ignoring any effects |
238 | /// on the provided instructions. |
239 | bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg, |
240 | InstSet &Ignore) const; |
241 | |
242 | private: |
243 | /// Set up LiveRegs by merging predecessor live-out values. |
244 | void enterBasicBlock(MachineBasicBlock *MBB); |
245 | |
246 | /// Update live-out values. |
247 | void leaveBasicBlock(MachineBasicBlock *MBB); |
248 | |
249 | /// Process he given basic block. |
250 | void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB); |
251 | |
252 | /// Process block that is part of a loop again. |
253 | void reprocessBasicBlock(MachineBasicBlock *MBB); |
254 | |
255 | /// Update def-ages for registers defined by MI. |
256 | /// Also break dependencies on partial defs and undef uses. |
257 | void processDefs(MachineInstr *); |
258 | |
259 | /// Utility function for isSafeToMoveForwards/Backwards. |
260 | template<typename Iterator> |
261 | bool isSafeToMove(MachineInstr *From, MachineInstr *To) const; |
262 | |
263 | /// Return whether removing this instruction will have no effect on the |
264 | /// program, ignoring the possible effects on some instructions, returning |
265 | /// the redundant use-def chain. |
266 | bool isSafeToRemove(MachineInstr *MI, InstSet &Visited, |
267 | InstSet &ToRemove, InstSet &Ignore) const; |
268 | |
269 | /// Provides the MI, from the given block, corresponding to the Id or a |
270 | /// nullptr if the id does not refer to the block. |
271 | MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const; |
272 | |
273 | /// Provides the instruction of the closest reaching def instruction of |
274 | /// PhysReg that reaches MI, relative to the begining of MI's basic block. |
275 | MachineInstr *getReachingLocalMIDef(MachineInstr *MI, |
276 | MCRegister PhysReg) const; |
277 | }; |
278 | |
279 | } // namespace llvm |
280 | |
281 | #endif // LLVM_CODEGEN_REACHINGDEFANALYSIS_H |
282 | |