LLVM 24.0.0git
ReachingDefAnalysis.h
Go to the documentation of this file.
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"
31
32namespace llvm {
33
35class MachineInstr;
36
37/// Thin wrapper around "int" used to store reaching definitions,
38/// using an encoding that makes it compatible with TinyPtrVector.
39/// The 0th LSB is forced zero (and will be used for pointer union tagging),
40/// The 1st LSB is forced one (to make sure the value is non-zero).
41class ReachingDef {
42 uintptr_t Encoded;
43 friend struct PointerLikeTypeTraits<ReachingDef>;
44 explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {}
45
46public:
47 ReachingDef(std::nullptr_t) : Encoded(0) {}
48 ReachingDef(int Instr) : Encoded(((uintptr_t) Instr << 2) | 2) {}
49 operator int() const { return ((int) Encoded) >> 2; }
50};
51
52template<>
54 static constexpr int NumLowBitsAvailable = 1;
55
56 static inline void *getAsVoidPointer(const ReachingDef &RD) {
57 return reinterpret_cast<void *>(RD.Encoded);
58 }
59
60 static inline ReachingDef getFromVoidPointer(void *P) {
61 return ReachingDef(reinterpret_cast<uintptr_t>(P));
62 }
63
64 static inline ReachingDef getFromVoidPointer(const void *P) {
65 return ReachingDef(reinterpret_cast<uintptr_t>(P));
66 }
67};
68
69// The storage for all reaching definitions.
71public:
72 void init(unsigned NumBlockIDs) { AllReachingDefs.resize(NumBlockIDs); }
73
74 unsigned numBlockIDs() const { return AllReachingDefs.size(); }
75
76 void startBasicBlock(unsigned MBBNumber, unsigned NumRegUnits) {
77 AllReachingDefs[MBBNumber].resize(NumRegUnits);
78 }
79
80 void append(unsigned MBBNumber, MCRegUnit Unit, int Def) {
81 AllReachingDefs[MBBNumber][static_cast<unsigned>(Unit)].push_back(Def);
82 }
83
84 void prepend(unsigned MBBNumber, MCRegUnit Unit, int Def) {
85 auto &Defs = AllReachingDefs[MBBNumber][static_cast<unsigned>(Unit)];
86 Defs.insert(Defs.begin(), Def);
87 }
88
89 void replaceFront(unsigned MBBNumber, MCRegUnit Unit, int Def) {
90 assert(!AllReachingDefs[MBBNumber][static_cast<unsigned>(Unit)].empty());
91 *AllReachingDefs[MBBNumber][static_cast<unsigned>(Unit)].begin() = Def;
92 }
93
94 void clear() { AllReachingDefs.clear(); }
95
96 ArrayRef<ReachingDef> defs(unsigned MBBNumber, MCRegUnit Unit) const {
97 if (AllReachingDefs[MBBNumber].empty())
98 // Block IDs are not necessarily dense.
99 return ArrayRef<ReachingDef>();
100 return AllReachingDefs[MBBNumber][static_cast<unsigned>(Unit)];
101 }
102
103private:
104 /// All reaching defs of a given RegUnit for a given MBB.
105 using MBBRegUnitDefs = TinyPtrVector<ReachingDef>;
106 /// All reaching defs of all reg units for a given MBB
107 using MBBDefsInfo = std::vector<MBBRegUnitDefs>;
108
109 /// All reaching defs of all reg units for all MBBs
110 SmallVector<MBBDefsInfo, 4> AllReachingDefs;
111};
112
113/// This class provides the reaching def analysis.
115private:
116 MachineFunction *MF = nullptr;
117 const TargetRegisterInfo *TRI = nullptr;
118 const TargetInstrInfo *TII = nullptr;
119 LoopTraversal::TraversalOrder TraversedMBBOrder;
120 unsigned NumRegUnits = 0;
121 /// Instruction that defined each register, relative to the beginning of the
122 /// current basic block. When a LiveRegsDefInfo is used to represent a
123 /// live-out register, this value is relative to the end of the basic block,
124 /// so it will be a negative number.
125 using LiveRegsDefInfo = std::vector<int>;
126 LiveRegsDefInfo LiveRegs;
127
128 /// Keeps clearance information for all registers. Note that this
129 /// is different from the usual definition notion of liveness. The CPU
130 /// doesn't care whether or not we consider a register killed.
131 using OutRegsInfoMap = SmallVector<LiveRegsDefInfo, 4>;
132 OutRegsInfoMap MBBOutRegsInfos;
133
134 /// Current instruction number.
135 /// The first instruction in each basic block is 0.
136 int CurInstr = -1;
137
138 /// Maps instructions to their instruction Ids, relative to the beginning of
139 /// their basic blocks.
141
142 MBBReachingDefsInfo MBBReachingDefs;
143
144 /// MBBFrameObjsReachingDefs[{i, j}] is a list of instruction indices
145 /// (relative to begining of MBB i) that define frame index j in MBB i. This
146 /// is used in answering reaching definition queries.
147 using MBBFrameObjsReachingDefsInfo =
149 MBBFrameObjsReachingDefsInfo MBBFrameObjsReachingDefs;
150
151 /// Default values are 'nothing happened a long time ago'.
152 static constexpr int ReachingDefDefaultVal = -(1 << 21);
153 /// Special values for function live-ins.
154 static constexpr int FunctionLiveInMarker = -1;
155
156 using InstSet = SmallPtrSetImpl<MachineInstr*>;
158
159public:
163 /// Handle invalidation explicitly.
165 MachineFunctionAnalysisManager::Invalidator &);
166
167 LLVM_ABI void run(MachineFunction &mf);
168 LLVM_ABI void print(raw_ostream &OS);
169 LLVM_ABI void releaseMemory();
170
171 /// Re-run the analysis.
172 LLVM_ABI void reset();
173
174 /// Initialize data structures.
175 LLVM_ABI void init();
176
177 /// Traverse the machine function, mapping definitions.
178 LLVM_ABI void traverse();
179
180 /// Provides the instruction id of the closest reaching def instruction of
181 /// Reg that reaches MI, relative to the begining of MI's basic block.
182 /// Note that Reg may represent a stack slot.
184
185 /// Return whether A and B use the same def of Reg.
187 Register Reg) const;
188
189 /// Return whether the reaching def for MI also is live out of its parent
190 /// block.
192
193 /// Return the local MI that produces the live out value for Reg, or
194 /// nullptr for a non-live out or non-local def.
196 Register Reg) const;
197
198 /// If a single MachineInstr creates the reaching definition, then return it.
199 /// Otherwise return null.
201 Register Reg) const;
202
203 /// If a single MachineInstr creates the reaching definition, for MIs operand
204 /// at Idx, then return it. Otherwise return null.
205 LLVM_ABI MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const;
206
207 /// If a single MachineInstr creates the reaching definition, for MIs MO,
208 /// then return it. Otherwise return null.
210 MachineOperand &MO) const;
211
212 /// Provide whether the register has been defined in the same basic block as,
213 /// and before, MI.
215
216 /// Return whether the given register is used after MI, whether it's a local
217 /// use or a live out.
219
220 /// Return whether the given register is defined after MI.
222
223 /// Provides the clearance - the number of instructions since the closest
224 /// reaching def instruction of Reg that reaches MI.
226
227 /// Provides the uses, in the same block as MI, of register that MI defines.
228 /// This does not consider live-outs.
230 InstSet &Uses) const;
231
232 /// Search MBB for a definition of Reg and insert it into Defs. If no
233 /// definition is found, recursively search the predecessor blocks for them.
235 BlockSet &VisitedBBs) const;
237 InstSet &Defs) const;
238
239 /// For the given block, collect the instructions that use the live-in
240 /// value of the provided register. Return whether the value is still
241 /// live on exit.
243 InstSet &Uses) const;
244
245 /// Collect the users of the value stored in Reg, which is defined
246 /// by MI.
248 InstSet &Uses) const;
249
250 /// Collect all possible definitions of the value stored in Reg, which is
251 /// used by MI.
253 InstSet &Defs) const;
254
255 /// Return whether From can be moved forwards to just before To.
257 MachineInstr *To) const;
258
259 /// Return whether From can be moved backwards to just after To.
261 MachineInstr *To) const;
262
263 /// Assuming MI is dead, recursively search the incoming operands which are
264 /// killed by MI and collect those that would become dead.
265 LLVM_ABI void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const;
266
267 /// Return whether removing this instruction will have no effect on the
268 /// program, returning the redundant use-def chain.
269 LLVM_ABI bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const;
270
271 /// Return whether removing this instruction will have no effect on the
272 /// program, ignoring the possible effects on some instructions, returning
273 /// the redundant use-def chain.
275 InstSet &Ignore) const;
276
277 /// Return whether a MachineInstr could be inserted at MI and safely define
278 /// the given register without affecting the program.
280
281 /// Return whether a MachineInstr could be inserted at MI and safely define
282 /// the given register without affecting the program, ignoring any effects
283 /// on the provided instructions.
285 InstSet &Ignore) const;
286
287private:
288 /// Set up LiveRegs by merging predecessor live-out values.
289 void enterBasicBlock(MachineBasicBlock *MBB);
290
291 /// Update live-out values.
292 void leaveBasicBlock(MachineBasicBlock *MBB);
293
294 /// Process he given basic block.
295 void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
296
297 /// Process block that is part of a loop again.
298 void reprocessBasicBlock(MachineBasicBlock *MBB);
299
300 /// Update def-ages for registers defined by MI.
301 /// Also break dependencies on partial defs and undef uses.
302 void processDefs(MachineInstr *);
303
304 /// Utility function for isSafeToMoveForwards/Backwards.
305 template<typename Iterator>
306 bool isSafeToMove(MachineInstr *From, MachineInstr *To) const;
307
308 /// Return whether removing this instruction will have no effect on the
309 /// program, ignoring the possible effects on some instructions, returning
310 /// the redundant use-def chain.
311 bool isSafeToRemove(MachineInstr *MI, InstSet &Visited,
312 InstSet &ToRemove, InstSet &Ignore) const;
313
314 /// Provides the MI, from the given block, corresponding to the Id or a
315 /// nullptr if the id does not refer to the block.
316 MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const;
317
318 /// Provides the instruction of the closest reaching def instruction of
319 /// Reg that reaches MI, relative to the begining of MI's basic block.
320 /// Note that Reg may represent a stack slot.
321 MachineInstr *getReachingLocalMIDef(MachineInstr *MI, Register Reg) const;
322};
323
324class ReachingDefAnalysis : public AnalysisInfoMixin<ReachingDefAnalysis> {
326 static AnalysisKey Key;
327
328public:
330
333};
334
335/// Printer pass for the \c ReachingDefInfo results.
337 : public RequiredPassInfoMixin<ReachingDefPrinterPass> {
338 raw_ostream &OS;
339
340public:
341 explicit ReachingDefPrinterPass(raw_ostream &OS) : OS(OS) {}
342
345};
346
348 ReachingDefInfo RDI;
349
350public:
351 static char ID;
352
354
355 void getAnalysisUsage(AnalysisUsage &AU) const override;
357 bool runOnMachineFunction(MachineFunction &F) override;
358 void releaseMemory() override { RDI.releaseMemory(); }
359
360 ReachingDefInfo &getRDI() { return RDI; }
361 const ReachingDefInfo &getRDI() const { return RDI; }
362};
363
364} // namespace llvm
365
366#endif // LLVM_CODEGEN_REACHINGDEFANALYSIS_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
ReachingDefInfo InstSet & ToRemove
MachineBasicBlock & MBB
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseMap class.
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition MD5.cpp:54
Register Reg
#define P(N)
Remove Loads Into Fake Uses
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
SmallVector< TraversedMBBInfo, 4 > TraversalOrder
Identifies basic blocks that are part of loops and should to be visited twice and returns efficient t...
void prepend(unsigned MBBNumber, MCRegUnit Unit, int Def)
void replaceFront(unsigned MBBNumber, MCRegUnit Unit, int Def)
ArrayRef< ReachingDef > defs(unsigned MBBNumber, MCRegUnit Unit) const
void init(unsigned NumBlockIDs)
void append(unsigned MBBNumber, MCRegUnit Unit, int Def)
void startBasicBlock(unsigned MBBNumber, unsigned NumRegUnits)
Properties which a MachineFunction may have at a given point in time.
Representation of each machine instruction.
MachineOperand class - Representation of each machine instruction operand.
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const ReachingDefInfo & getRDI() const
MachineFunctionProperties getRequiredProperties() const override
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
This class provides the reaching def analysis.
LLVM_ABI MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, Register Reg) const
If a single MachineInstr creates the reaching definition, then return it.
LLVM_ABI bool isReachingDefLiveOut(MachineInstr *MI, Register Reg) const
Return whether the reaching def for MI also is live out of its parent block.
LLVM_ABI bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
LLVM_ABI int getReachingDef(MachineInstr *MI, Register Reg) const
Provides the instruction id of the closest reaching def instruction of Reg that reaches MI,...
LLVM_ABI void run(MachineFunction &mf)
LLVM_ABI void getReachingLocalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
LLVM_ABI int getClearance(MachineInstr *MI, Register Reg) const
Provides the clearance - the number of instructions since the closest reaching def instruction of Reg...
LLVM_ABI bool isRegDefinedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is defined after MI.
LLVM_ABI void init()
Initialize data structures.
LLVM_ABI void print(raw_ostream &OS)
LLVM_ABI bool hasLocalDefBefore(MachineInstr *MI, Register Reg) const
Provide whether the register has been defined in the same basic block as, and before,...
LLVM_ABI void reset()
Re-run the analysis.
LLVM_ABI void getGlobalUses(MachineInstr *MI, Register Reg, InstSet &Uses) const
Collect the users of the value stored in Reg, which is defined by MI.
LLVM_ABI MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
LLVM_ABI void getLiveOuts(MachineBasicBlock *MBB, Register Reg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of Reg and insert it into Defs.
LLVM_ABI void traverse()
Traverse the machine function, mapping definitions.
LLVM_ABI ReachingDefInfo()
LLVM_ABI bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
LLVM_ABI void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
LLVM_ABI ~ReachingDefInfo()
LLVM_ABI bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, Register Reg) const
Return whether A and B use the same def of Reg.
LLVM_ABI bool isRegUsedAfter(MachineInstr *MI, Register Reg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
LLVM_ABI void getGlobalReachingDefs(MachineInstr *MI, Register Reg, InstSet &Defs) const
Collect all possible definitions of the value stored in Reg, which is used by MI.
LLVM_ABI bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
LLVM_ABI ReachingDefInfo(ReachingDefInfo &&)
LLVM_ABI MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, Register Reg) const
Return the local MI that produces the live out value for Reg, or nullptr for a non-live out or non-lo...
LLVM_ABI bool invalidate(MachineFunction &F, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
LLVM_ABI bool getLiveInUses(MachineBasicBlock *MBB, Register Reg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
LLVM_ABI bool isSafeToDefRegAt(MachineInstr *MI, Register Reg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
Thin wrapper around "int" used to store reaching definitions, using an encoding that makes it compati...
ReachingDef(std::nullptr_t)
Wrapper class representing virtual and physical registers.
Definition Register.h:20
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
This is an optimization pass for GlobalISel generic memory operations.
@ Dead
Unused definition.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
ArrayRef(const T &OneElt) -> ArrayRef< T >
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
static ReachingDef getFromVoidPointer(const void *P)
static void * getAsVoidPointer(const ReachingDef &RD)
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
A CRTP mix-in for passes that should not be skipped.