LLVM  14.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"
25 #include "llvm/ADT/SmallVector.h"
26 #include "llvm/ADT/TinyPtrVector.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;
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<>
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.
70 private:
71  MachineFunction *MF;
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 
110 public:
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 
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
llvm::ReachingDefAnalysis::reset
void reset()
Re-run the analysis.
Definition: ReachingDefAnalysis.cpp:240
llvm::ReachingDefAnalysis::getLiveOuts
void getLiveOuts(MachineBasicBlock *MBB, MCRegister PhysReg, InstSet &Defs, BlockSet &VisitedBBs) const
Search MBB for a definition of PhysReg and insert it into Defs.
Definition: ReachingDefAnalysis.cpp:429
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm::ReachingDefAnalysis::hasSameReachingDef
bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, MCRegister PhysReg) const
Return whether A and B use the same def of PhysReg.
Definition: ReachingDefAnalysis.cpp:301
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ReachingDefAnalysis::isSafeToRemove
bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const
Return whether removing this instruction will have no effect on the program, returning the redundant ...
Definition: ReachingDefAnalysis.cpp:616
llvm::ReachingDefAnalysis::getUniqueReachingMIDef
MachineInstr * getUniqueReachingMIDef(MachineInstr *MI, MCRegister PhysReg) const
If a single MachineInstr creates the reaching definition, then return it.
Definition: ReachingDefAnalysis.cpp:449
llvm::ReachingDefAnalysis
This class provides the reaching def analysis.
Definition: ReachingDefAnalysis.h:69
llvm::ReachingDefAnalysis::getLiveInUses
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.
Definition: ReachingDefAnalysis.cpp:366
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
Ignore
ReachingDefAnalysis InstSet InstSet & Ignore
Definition: ARMLowOverheadLoops.cpp:536
llvm::SmallVector< TraversedMBBInfo, 4 >
llvm::PointerLikeTypeTraits< ReachingDef >::getAsVoidPointer
static void * getAsVoidPointer(const ReachingDef &RD)
Definition: ReachingDefAnalysis.h:55
llvm::PointerLikeTypeTraits< ReachingDef >::getFromVoidPointer
static ReachingDef getFromVoidPointer(void *P)
Definition: ReachingDefAnalysis.h:59
ToRemove
ReachingDefAnalysis InstSet & ToRemove
Definition: ARMLowOverheadLoops.cpp:536
llvm::ReachingDefAnalysis::getRequiredProperties
MachineFunctionProperties getRequiredProperties() const override
Definition: ReachingDefAnalysis.h:125
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
llvm::MachineFunctionProperties
Properties which a MachineFunction may have at a given point in time.
Definition: MachineFunction.h:111
llvm::ReachingDef::ReachingDef
ReachingDef(int Instr)
Definition: ReachingDefAnalysis.h:47
llvm::ReachingDefAnalysis::hasLocalDefBefore
bool hasLocalDefBefore(MachineInstr *MI, MCRegister PhysReg) const
Provide whether the register has been defined in the same basic block as, and before,...
Definition: ReachingDefAnalysis.cpp:336
llvm::ReachingDefAnalysis::getLocalLiveOutMIDef
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...
Definition: ReachingDefAnalysis.cpp:538
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
Uses
SmallPtrSet< MachineInstr *, 2 > Uses
Definition: ARMLowOverheadLoops.cpp:579
llvm::ReachingDefAnalysis::isSafeToMoveBackwards
bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved backwards to just after To.
Definition: ReachingDefAnalysis.cpp:606
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::ReachingDefAnalysis::getGlobalUses
void getGlobalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Collect the users of the value stored in PhysReg, which is defined by MI.
Definition: ReachingDefAnalysis.cpp:385
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::MachineFunctionProperties::set
MachineFunctionProperties & set(Property P)
Definition: MachineFunction.h:169
llvm::ReachingDefAnalysis::init
void init()
Initialize data structures.
Definition: ReachingDefAnalysis.cpp:246
LoopTraversal.h
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::ReachingDefAnalysis::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: ReachingDefAnalysis.cpp:232
llvm::MachineFunctionProperties::Property::NoVRegs
@ NoVRegs
llvm::ReachingDef
Thin wrapper around "int" used to store reaching definitions, using an encoding that makes it compati...
Definition: ReachingDefAnalysis.h:40
llvm::MachineFunctionProperties::Property::TracksLiveness
@ TracksLiveness
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::ReachingDefAnalysis::getReachingDef
int getReachingDef(MachineInstr *MI, MCRegister PhysReg) const
Provides the instruction id of the closest reaching def instruction of PhysReg that reaches MI,...
Definition: ReachingDefAnalysis.cpp:273
llvm::DenseMap
Definition: DenseMap.h:714
MachineFunctionPass.h
llvm::ReachingDefAnalysis::isRegDefinedAfter
bool isRegDefinedAfter(MachineInstr *MI, MCRegister PhysReg) const
Return whether the given register is defined after MI.
Definition: ReachingDefAnalysis.cpp:502
llvm::ReachingDefAnalysis::ID
static char ID
Definition: ReachingDefAnalysis.h:111
llvm::ReachingDef::ReachingDef
ReachingDef(std::nullptr_t)
Definition: ReachingDefAnalysis.h:46
TinyPtrVector.h
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::ReachingDefAnalysis::getReachingLocalUses
void getReachingLocalUses(MachineInstr *MI, MCRegister PhysReg, InstSet &Uses) const
Provides the uses, in the same block as MI, of register that MI defines.
Definition: ReachingDefAnalysis.cpp:341
llvm::ReachingDefAnalysis::traverse
void traverse()
Traverse the machine function, mapping definitions.
Definition: ReachingDefAnalysis.cpp:255
llvm::initializeReachingDefAnalysisPass
void initializeReachingDefAnalysisPass(PassRegistry &)
llvm::ReachingDefAnalysis::collectKilledOperands
void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const
Assuming MI is dead, recursively search the incoming operands which are killed by MI and collect thos...
Definition: ReachingDefAnalysis.cpp:660
llvm::ReachingDefAnalysis::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: ReachingDefAnalysis.h:118
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::PointerLikeTypeTraits< ReachingDef >::getFromVoidPointer
static ReachingDef getFromVoidPointer(const void *P)
Definition: ReachingDefAnalysis.h:63
llvm::ReachingDefAnalysis::isSafeToDefRegAt
bool isSafeToDefRegAt(MachineInstr *MI, MCRegister PhysReg) const
Return whether a MachineInstr could be inserted at MI and safely define the given register without af...
Definition: ReachingDefAnalysis.cpp:692
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::ReachingDefAnalysis::getGlobalReachingDefs
void getGlobalReachingDefs(MachineInstr *MI, MCRegister PhysReg, InstSet &Defs) const
Collect all possible definitions of the value stored in PhysReg, which is used by MI.
Definition: ReachingDefAnalysis.cpp:411
llvm::ReachingDefAnalysis::ReachingDefAnalysis
ReachingDefAnalysis()
Definition: ReachingDefAnalysis.h:113
llvm::RegState::Dead
@ Dead
Unused definition.
Definition: MachineInstrBuilder.h:50
llvm::PointerLikeTypeTraits
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
Definition: PointerLikeTypeTraits.h:25
SmallVector.h
llvm::ReachingDefAnalysis::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: ReachingDefAnalysis.cpp:223
llvm::ReachingDefAnalysis::isReachingDefLiveOut
bool isReachingDefLiveOut(MachineInstr *MI, MCRegister PhysReg) const
Return whether the reaching def for MI also is live out of its parent block.
Definition: ReachingDefAnalysis.cpp:516
llvm::SmallPtrSetImpl
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
llvm::ReachingDefAnalysis::getClearance
int getClearance(MachineInstr *MI, MCRegister PhysReg) const
Provides the clearance - the number of instructions since the closest reaching def instuction of Phys...
Definition: ReachingDefAnalysis.cpp:330
llvm::ReachingDefAnalysis::getMIOperand
MachineInstr * getMIOperand(MachineInstr *MI, unsigned Idx) const
If a single MachineInstr creates the reaching definition, for MIs operand at Idx, then return it.
Definition: ReachingDefAnalysis.cpp:469
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::TinyPtrVector
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
InitializePasses.h
llvm::LoopTraversal::TraversedMBBInfo
Definition: LoopTraversal.h:87
llvm::ReachingDefAnalysis::isRegUsedAfter
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.
Definition: ReachingDefAnalysis.cpp:481
llvm::ReachingDefAnalysis::isSafeToMoveForwards
bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const
Return whether From can be moved forwards to just before To.
Definition: ReachingDefAnalysis.cpp:596
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:23