LLVM  12.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_REACHINGDEFSANALYSIS_H
22 #define LLVM_CODEGEN_REACHINGDEFSANALYSIS_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, int PhysReg) const;
143 
144  /// Return whether A and B use the same def of PhysReg.
145  bool hasSameReachingDef(MachineInstr *A, MachineInstr *B, int PhysReg) const;
146 
147  /// Return whether the reaching def for MI also is live out of its parent
148  /// block.
149  bool isReachingDefLiveOut(MachineInstr *MI, int PhysReg) const;
150 
151  /// Return the local MI that produces the live out value for PhysReg, or
152  /// nullptr for a non-live out or non-local def.
153  MachineInstr *getLocalLiveOutMIDef(MachineBasicBlock *MBB,
154  int PhysReg) const;
155 
156  /// If a single MachineInstr creates the reaching definition, then return it.
157  /// Otherwise return null.
158  MachineInstr *getUniqueReachingMIDef(MachineInstr *MI, int PhysReg) const;
159 
160  /// If a single MachineInstr creates the reaching definition, for MIs operand
161  /// at Idx, then return it. Otherwise return null.
162  MachineInstr *getMIOperand(MachineInstr *MI, unsigned Idx) const;
163 
164  /// If a single MachineInstr creates the reaching definition, for MIs MO,
165  /// then return it. Otherwise return null.
166  MachineInstr *getMIOperand(MachineInstr *MI, MachineOperand &MO) const;
167 
168  /// Provide whether the register has been defined in the same basic block as,
169  /// and before, MI.
170  bool hasLocalDefBefore(MachineInstr *MI, int PhysReg) const;
171 
172  /// Return whether the given register is used after MI, whether it's a local
173  /// use or a live out.
174  bool isRegUsedAfter(MachineInstr *MI, int PhysReg) const;
175 
176  /// Return whether the given register is defined after MI.
177  bool isRegDefinedAfter(MachineInstr *MI, int PhysReg) const;
178 
179  /// Provides the clearance - the number of instructions since the closest
180  /// reaching def instuction of PhysReg that reaches MI.
181  int getClearance(MachineInstr *MI, MCPhysReg PhysReg) const;
182 
183  /// Provides the uses, in the same block as MI, of register that MI defines.
184  /// This does not consider live-outs.
185  void getReachingLocalUses(MachineInstr *MI, int PhysReg,
186  InstSet &Uses) const;
187 
188  /// Search MBB for a definition of PhysReg and insert it into Defs. If no
189  /// definition is found, recursively search the predecessor blocks for them.
190  void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs,
191  BlockSet &VisitedBBs) const;
192  void getLiveOuts(MachineBasicBlock *MBB, int PhysReg, InstSet &Defs) const;
193 
194  /// For the given block, collect the instructions that use the live-in
195  /// value of the provided register. Return whether the value is still
196  /// live on exit.
197  bool getLiveInUses(MachineBasicBlock *MBB, int PhysReg,
198  InstSet &Uses) const;
199 
200  /// Collect the users of the value stored in PhysReg, which is defined
201  /// by MI.
202  void getGlobalUses(MachineInstr *MI, int PhysReg,
203  InstSet &Uses) const;
204 
205  /// Return whether From can be moved forwards to just before To.
206  bool isSafeToMoveForwards(MachineInstr *From, MachineInstr *To) const;
207 
208  /// Return whether From can be moved backwards to just after To.
209  bool isSafeToMoveBackwards(MachineInstr *From, MachineInstr *To) const;
210 
211  /// Assuming MI is dead, recursively search the incoming operands which are
212  /// killed by MI and collect those that would become dead.
213  void collectKilledOperands(MachineInstr *MI, InstSet &Dead) const;
214 
215  /// Return whether removing this instruction will have no effect on the
216  /// program, returning the redundant use-def chain.
217  bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove) const;
218 
219  /// Return whether removing this instruction will have no effect on the
220  /// program, ignoring the possible effects on some instructions, returning
221  /// the redundant use-def chain.
222  bool isSafeToRemove(MachineInstr *MI, InstSet &ToRemove,
223  InstSet &Ignore) const;
224 
225  /// Return whether a MachineInstr could be inserted at MI and safely define
226  /// the given register without affecting the program.
227  bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg) const;
228 
229  /// Return whether a MachineInstr could be inserted at MI and safely define
230  /// the given register without affecting the program, ignoring any effects
231  /// on the provided instructions.
232  bool isSafeToDefRegAt(MachineInstr *MI, int PhysReg, InstSet &Ignore) const;
233 
234 private:
235  /// Set up LiveRegs by merging predecessor live-out values.
236  void enterBasicBlock(MachineBasicBlock *MBB);
237 
238  /// Update live-out values.
239  void leaveBasicBlock(MachineBasicBlock *MBB);
240 
241  /// Process he given basic block.
242  void processBasicBlock(const LoopTraversal::TraversedMBBInfo &TraversedMBB);
243 
244  /// Process block that is part of a loop again.
245  void reprocessBasicBlock(MachineBasicBlock *MBB);
246 
247  /// Update def-ages for registers defined by MI.
248  /// Also break dependencies on partial defs and undef uses.
249  void processDefs(MachineInstr *);
250 
251  /// Utility function for isSafeToMoveForwards/Backwards.
252  template<typename Iterator>
253  bool isSafeToMove(MachineInstr *From, MachineInstr *To) const;
254 
255  /// Return whether removing this instruction will have no effect on the
256  /// program, ignoring the possible effects on some instructions, returning
257  /// the redundant use-def chain.
258  bool isSafeToRemove(MachineInstr *MI, InstSet &Visited,
259  InstSet &ToRemove, InstSet &Ignore) const;
260 
261  /// Provides the MI, from the given block, corresponding to the Id or a
262  /// nullptr if the id does not refer to the block.
263  MachineInstr *getInstFromId(MachineBasicBlock *MBB, int InstId) const;
264 
265  /// Provides the instruction of the closest reaching def instruction of
266  /// PhysReg that reaches MI, relative to the begining of MI's basic block.
267  MachineInstr *getReachingLocalMIDef(MachineInstr *MI, int PhysReg) const;
268 };
269 
270 } // namespace llvm
271 
272 #endif // LLVM_CODEGEN_REACHINGDEFSANALYSIS_H
static ReachingDef getFromVoidPointer(void *P)
void initializeReachingDefAnalysisPass(PassRegistry &)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
static bool isSafeToMove(const MachineOperand *Def, const MachineOperand *Use, const MachineInstr *Insert, AliasAnalysis &AA, const WebAssemblyFunctionInfo &MFI, const MachineRegisterInfo &MRI)
unsigned const TargetRegisterInfo * TRI
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
This class provides the reaching def analysis.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
MachineBasicBlock & MBB
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
A traits type that is used to handle pointer types and things that are just wrappers for pointers as ...
static void * getAsVoidPointer(const ReachingDef &RD)
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:434
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
ReachingDef(std::nullptr_t)
Represent the analysis usage information of a pass.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
static ReachingDef getFromVoidPointer(const void *P)
BlockVerifier::State From
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineOperand class - Representation of each machine instruction operand.
void setPreservesAll()
Set by analyses that do not transform their input at all.
Thin wrapper around "int" used to store reaching definitions, using an encoding that makes it compati...
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:62
MachineFunctionProperties getRequiredProperties() const override
IRTranslator LLVM IR MI
Properties which a MachineFunction may have at a given point in time.