LLVM 17.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:
72 const TargetRegisterInfo *TRI;
73 LoopTraversal::TraversalOrder TraversedMBBOrder;
74 unsigned NumRegUnits;
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;
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 << 20);
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
SmallPtrSet< MachineInstr *, 2 > Uses
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.
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:24
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:68
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:344
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 ...