LLVM  11.0.0git
LivePhysRegs.cpp
Go to the documentation of this file.
1 //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
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 // This file implements the LivePhysRegs utility for tracking liveness of
10 // physical registers across machine instructions in forward or backward order.
11 // A more detailed description can be found in the corresponding header file.
12 //
13 //===----------------------------------------------------------------------===//
14 
21 #include "llvm/Config/llvm-config.h"
22 #include "llvm/Support/Debug.h"
24 using namespace llvm;
25 
26 
27 /// Remove all registers from the set that get clobbered by the register
28 /// mask.
29 /// The clobbers set will be the list of live registers clobbered
30 /// by the regmask.
32  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
33  RegisterSet::iterator LRI = LiveRegs.begin();
34  while (LRI != LiveRegs.end()) {
35  if (MO.clobbersPhysReg(*LRI)) {
36  if (Clobbers)
37  Clobbers->push_back(std::make_pair(*LRI, &MO));
38  LRI = LiveRegs.erase(LRI);
39  } else
40  ++LRI;
41  }
42 }
43 
44 /// Remove defined registers and regmask kills from the set.
46  for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
47  if (MOP.isRegMask()) {
48  removeRegsInMask(MOP);
49  continue;
50  }
51 
52  if (MOP.isDef())
53  removeReg(MOP.getReg());
54  }
55 }
56 
57 /// Add uses to the set.
59  for (const MachineOperand &MOP : phys_regs_and_masks(MI)) {
60  if (!MOP.isReg() || !MOP.readsReg())
61  continue;
62  addReg(MOP.getReg());
63  }
64 }
65 
66 /// Simulates liveness when stepping backwards over an instruction(bundle):
67 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
69  // Remove defined registers and regmask kills from the set.
70  removeDefs(MI);
71 
72  // Add uses to the set.
73  addUses(MI);
74 }
75 
76 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
77 /// killed-uses, add defs. This is the not recommended way, because it depends
78 /// on accurate kill flags. If possible use stepBackward() instead of this
79 /// function.
81  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
82  // Remove killed registers from the set.
83  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
84  if (O->isReg() && !O->isDebug()) {
85  Register Reg = O->getReg();
87  continue;
88  if (O->isDef()) {
89  // Note, dead defs are still recorded. The caller should decide how to
90  // handle them.
91  Clobbers.push_back(std::make_pair(Reg, &*O));
92  } else {
93  if (!O->isKill())
94  continue;
95  assert(O->isUse());
96  removeReg(Reg);
97  }
98  } else if (O->isRegMask())
99  removeRegsInMask(*O, &Clobbers);
100  }
101 
102  // Add defs to the set.
103  for (auto Reg : Clobbers) {
104  // Skip dead defs and registers clobbered by regmasks. They shouldn't
105  // be added to the set.
106  if (Reg.second->isReg() && Reg.second->isDead())
107  continue;
108  if (Reg.second->isRegMask() &&
109  MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
110  continue;
111  addReg(Reg.first);
112  }
113 }
114 
115 /// Print the currently live registers to OS.
117  OS << "Live Registers:";
118  if (!TRI) {
119  OS << " (uninitialized)\n";
120  return;
121  }
122 
123  if (empty()) {
124  OS << " (empty)\n";
125  return;
126  }
127 
128  for (const_iterator I = begin(), E = end(); I != E; ++I)
129  OS << " " << printReg(*I, TRI);
130  OS << "\n";
131 }
132 
133 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
135  dbgs() << " " << *this;
136 }
137 #endif
138 
140  MCPhysReg Reg) const {
141  if (LiveRegs.count(Reg))
142  return false;
143  if (MRI.isReserved(Reg))
144  return false;
145  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
146  if (LiveRegs.count(*R))
147  return false;
148  }
149  return true;
150 }
151 
152 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
153 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
154  for (const auto &LI : MBB.liveins()) {
155  MCPhysReg Reg = LI.PhysReg;
156  LaneBitmask Mask = LI.LaneMask;
157  MCSubRegIndexIterator S(Reg, TRI);
158  assert(Mask.any() && "Invalid livein mask");
159  if (Mask.all() || !S.isValid()) {
160  addReg(Reg);
161  continue;
162  }
163  for (; S.isValid(); ++S) {
164  unsigned SI = S.getSubRegIndex();
165  if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
166  addReg(S.getSubReg());
167  }
168  }
169 }
170 
171 /// Adds all callee saved registers to \p LiveRegs.
172 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
173  const MachineFunction &MF) {
174  const MachineRegisterInfo &MRI = MF.getRegInfo();
175  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
176  LiveRegs.addReg(*CSR);
177 }
178 
179 void LivePhysRegs::addPristines(const MachineFunction &MF) {
180  const MachineFrameInfo &MFI = MF.getFrameInfo();
181  if (!MFI.isCalleeSavedInfoValid())
182  return;
183  /// This function will usually be called on an empty object, handle this
184  /// as a special case.
185  if (empty()) {
186  /// Add all callee saved regs, then remove the ones that are saved and
187  /// restored.
188  addCalleeSavedRegs(*this, MF);
189  /// Remove the ones that are not saved/restored; they are pristine.
190  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
191  removeReg(Info.getReg());
192  return;
193  }
194  /// If a callee-saved register that is not pristine is already present
195  /// in the set, we should make sure that it stays in it. Precompute the
196  /// set of pristine registers in a separate object.
197  /// Add all callee saved regs, then remove the ones that are saved+restored.
198  LivePhysRegs Pristine(*TRI);
199  addCalleeSavedRegs(Pristine, MF);
200  /// Remove the ones that are not saved/restored; they are pristine.
201  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
202  Pristine.removeReg(Info.getReg());
203  for (MCPhysReg R : Pristine)
204  addReg(R);
205 }
206 
208  // To get the live-outs we simply merge the live-ins of all successors.
209  for (const MachineBasicBlock *Succ : MBB.successors())
210  addBlockLiveIns(*Succ);
211  if (MBB.isReturnBlock()) {
212  // Return blocks are a special case because we currently don't mark up
213  // return instructions completely: specifically, there is no explicit
214  // use for callee-saved registers. So we add all callee saved registers
215  // that are saved and restored (somewhere). This does not include
216  // callee saved registers that are unused and hence not saved and
217  // restored; they are called pristine.
218  // FIXME: PEI should add explicit markings to return instructions
219  // instead of implicitly handling them here.
220  const MachineFunction &MF = *MBB.getParent();
221  const MachineFrameInfo &MFI = MF.getFrameInfo();
222  if (MFI.isCalleeSavedInfoValid()) {
223  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
224  if (Info.isRestored())
225  addReg(Info.getReg());
226  }
227  }
228 }
229 
231  const MachineFunction &MF = *MBB.getParent();
232  addPristines(MF);
234 }
235 
237  const MachineFunction &MF = *MBB.getParent();
238  addPristines(MF);
239  addBlockLiveIns(MBB);
240 }
241 
243  const MachineBasicBlock &MBB) {
244  const MachineFunction &MF = *MBB.getParent();
245  const MachineRegisterInfo &MRI = MF.getRegInfo();
246  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
247  LiveRegs.init(TRI);
248  LiveRegs.addLiveOutsNoPristines(MBB);
249  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
250  LiveRegs.stepBackward(MI);
251 }
252 
253 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
254  assert(MBB.livein_empty() && "Expected empty live-in list");
255  const MachineFunction &MF = *MBB.getParent();
256  const MachineRegisterInfo &MRI = MF.getRegInfo();
257  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
258  for (MCPhysReg Reg : LiveRegs) {
259  if (MRI.isReserved(Reg))
260  continue;
261  // Skip the register if we are about to add one of its super registers.
262  bool ContainsSuperReg = false;
263  for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
264  if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
265  ContainsSuperReg = true;
266  break;
267  }
268  }
269  if (ContainsSuperReg)
270  continue;
271  MBB.addLiveIn(Reg);
272  }
273 }
274 
276  const MachineFunction &MF = *MBB.getParent();
277  const MachineRegisterInfo &MRI = MF.getRegInfo();
278  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
279  const MachineFrameInfo &MFI = MF.getFrameInfo();
280 
281  // We walk through the block backwards and start with the live outs.
282  LivePhysRegs LiveRegs;
283  LiveRegs.init(TRI);
284  LiveRegs.addLiveOutsNoPristines(MBB);
285 
286  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
287  // Recompute dead flags.
288  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
289  if (!MO->isReg() || !MO->isDef() || MO->isDebug())
290  continue;
291 
292  Register Reg = MO->getReg();
293  if (Reg == 0)
294  continue;
296 
297  bool IsNotLive = LiveRegs.available(MRI, Reg);
298 
299  // Special-case return instructions for cases when a return is not
300  // the last instruction in the block.
301  if (MI.isReturn() && MFI.isCalleeSavedInfoValid()) {
302  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo()) {
303  if (Info.getReg() == Reg) {
304  IsNotLive = !Info.isRestored();
305  break;
306  }
307  }
308  }
309 
310  MO->setIsDead(IsNotLive);
311  }
312 
313  // Step backward over defs.
314  LiveRegs.removeDefs(MI);
315 
316  // Recompute kill flags.
317  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
318  if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
319  continue;
320 
321  Register Reg = MO->getReg();
322  if (Reg == 0)
323  continue;
325 
326  bool IsNotLive = LiveRegs.available(MRI, Reg);
327  MO->setIsKill(IsNotLive);
328  }
329 
330  // Complete the stepbackward.
331  LiveRegs.addUses(MI);
332  }
333 }
334 
336  MachineBasicBlock &MBB) {
337  computeLiveIns(LiveRegs, MBB);
338  addLiveIns(MBB, LiveRegs);
339 }
static bool clobbersPhysReg(const uint32_t *RegMask, MCRegister PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
bool isCalleeSavedInfoValid() const
Has the callee saved info been calculated yet?
bool isReserved(Register PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:508
void dump() const
Dumps the currently live registers to the debug output.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:63
MIBundleOperands - Iterate over all operands in a bundle of machine instructions. ...
unsigned Reg
bool isValid() const
isValid - Returns true until all the operands have been visited.
static void addCalleeSavedRegs(LivePhysRegs &LiveRegs, const MachineFunction &MF)
Adds all callee saved registers to LiveRegs.
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
const_iterator begin() const
Definition: LivePhysRegs.h:151
iterator_range< succ_iterator > successors()
bool empty() const
Returns true if the set is empty.
Definition: LivePhysRegs.h:76
bool isReturnBlock() const
Convenience function that returns true if the block ends in a return instruction. ...
MCSuperRegIterator enumerates all super-registers of Reg.
size_type count(const KeyT &Key) const
count - Returns 1 if this set contains an element identified by Key, 0 otherwise. ...
Definition: SparseSet.h:235
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
void addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs)
Adds registers contained in LiveRegs to the block live-in list of MBB.
unsigned getSubRegIndex() const
Returns sub-register index of the current sub-register.
reverse_iterator rend()
reverse_iterator rbegin()
Analysis containing CSE Info
Definition: CSEInfo.cpp:25
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:19
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:285
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const TargetRegisterInfo * getTargetRegisterInfo() const
unsigned const MachineRegisterInfo * MRI
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void addLiveOuts(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB.
void addLiveIns(const MachineBasicBlock &MBB)
Adds all live-in registers of basic block MBB.
void addUses(const MachineInstr &MI)
Add uses to the set.
void init(const TargetRegisterInfo &TRI)
(re-)initializes and clears the set.
Definition: LivePhysRegs.h:66
MCRegAliasIterator enumerates all registers aliasing Reg.
void stepBackward(const MachineInstr &MI)
Simulates liveness when stepping backwards over an instruction(bundle).
A set of register units.
constexpr bool all() const
Definition: LaneBitmask.h:53
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:149
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
void addLiveOutsNoPristines(const MachineBasicBlock &MBB)
Adds all live-out registers of basic block MBB but skips pristine registers.
const_iterator end() const
Definition: SparseSet.h:175
Predicate any(Predicate P0, Predicate P1)
True iff P0 or P1 are true.
void computeLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB)
Computes registers live-in to MBB assuming all of its successors live-in lists are up-to-date...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
bool isValid() const
Returns true if this iterator is not yet at the end.
bool available(const MachineRegisterInfo &MRI, MCPhysReg Reg) const
Returns true if register Reg and no aliasing register is in the set.
MachineOperand class - Representation of each machine instruction operand.
const_iterator begin() const
Definition: SparseSet.h:174
LaneBitmask getSubRegIndexLaneMask(unsigned SubIdx) const
Return a bitmask representing the parts of a register that are covered by SubIdx. ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
The CalleeSavedInfo class tracks the information need to locate where a callee saved register is in t...
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
void computeAndAddLiveIns(LivePhysRegs &LiveRegs, MachineBasicBlock &MBB)
Convenience function combining computeLiveIns() and addLiveIns().
void print(raw_ostream &OS) const
Prints the currently live registers to OS.
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:62
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
const std::vector< CalleeSavedInfo > & getCalleeSavedInfo() const
Returns a reference to call saved info vector for the current function.
#define I(x, y, z)
Definition: MD5.cpp:59
constexpr bool any() const
Definition: LaneBitmask.h:52
const_iterator end() const
Definition: LivePhysRegs.h:152
iterator_range< livein_iterator > liveins() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand *>> *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
void addReg(MCPhysReg Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:79
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
MCRegister getSubReg() const
Returns current sub-register.
IRTranslator LLVM IR MI
void removeReg(MCPhysReg Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set...
Definition: LivePhysRegs.h:89
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< MCPhysReg, const MachineOperand *>> &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
iterator_range< filter_iterator< ConstMIBundleOperands, std::function< bool(const MachineOperand &)> > > phys_regs_and_masks(const MachineInstr &MI)
Returns an iterator range over all physical register and mask operands for MI and bundled instruction...
Definition: LiveRegUnits.h:167
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19