LLVM 19.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"
30
31namespace llvm {
32
33class MachineBasicBlock;
34class 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).
41 uintptr_t Encoded;
43 explicit ReachingDef(uintptr_t Encoded) : Encoded(Encoded) {}
44
45public:
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
51template<>
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.
70private:
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.
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.
95
96 /// All reaching defs of a given RegUnit for a given MBB.
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
102 MBBReachingDefsInfo MBBReachingDefs;
103
104 /// Default values are 'nothing happened a long time ago'.
105 const int ReachingDefDefaultVal = -(1 << 21);
106
109
110public:
111 static char ID; // Pass identification, replacement for typeid
112
115 }
116 void releaseMemory() override;
117
118 void getAnalysisUsage(AnalysisUsage &AU) const override {
119 AU.setPreservesAll();
121 }
122
123 bool runOnMachineFunction(MachineFunction &MF) override;
124
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.
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.
155 MCRegister PhysReg) const;
156
157 /// If a single MachineInstr creates the reaching definition, then return it.
158 /// Otherwise return null.
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.
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.
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;
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.
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.
210 InstSet &Defs) const;
211
212 /// Return whether From can be moved forwards to just before To.
214
215 /// Return whether From can be moved backwards to just after To.
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.
240 InstSet &Ignore) const;
241
242private:
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
MachineBasicBlock & MBB
ReachingDefAnalysis InstSet & ToRemove
ReachingDefAnalysis InstSet InstSet & Ignore
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
Rewrite Partial Register Uses
IRTranslator LLVM IR MI
#define P(N)
This file defines the SmallVector class.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Properties which a MachineFunction may have at a given point in time.
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class provides the reaching def analysis.
void traverse()
Traverse the machine function, mapping definitions.
bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
bool getLiveInUses(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Uses) const
For the given block, collect the instructions that use the live-in value of the provided register.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
MachineInstr * getLocalLiveOutMIDef(MachineBasicBlock *MBB, MCRegister PhysReg) const
Return the local MI that produces the live out value for PhysReg, or nullptr for a non-live out or no...
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
void reset()
Re-run the analysis.
bool isRegUsedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is used after MI, whether it's a local use or a live out.
bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const
Provide whether the register has been defined in the same basic block as, and before,...
void init()
Initialize data structures.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of PhysReg and insert it into Defs.
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, MCRegister PhysReg) const
Return whether A and B use the same def of PhysReg.
void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Collect the users of the value stored in PhysReg, which is defined by MI.
void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is defined after MI.
int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI,...
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, InstSet &Defs) const
Collect all possible definitions of the value stored in PhysReg, which is used by MI.
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, MCRegister PhysReg) const
If a single MachineInstr creates the reaching definition, then return it.
bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const
Return whether the reaching def for MI also is live out of its parent block.
MachineFunctionProperties getRequiredProperties() const override
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
Thin wrapper around "int" used to store reaching definitions, using an encoding that makes it compati...
ReachingDef(std::nullptr_t)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
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...
Definition: TinyPtrVector.h:29
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void initializeReachingDefAnalysisPass(PassRegistry &)
static ReachingDef getFromVoidPointer(const void *P)
static ReachingDef getFromVoidPointer(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 ...