LLVM  10.0.0svn
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 
20 #include "llvm/Config/llvm-config.h"
21 #include "llvm/Support/Debug.h"
23 using namespace llvm;
24 
25 
26 /// Remove all registers from the set that get clobbered by the register
27 /// mask.
28 /// The clobbers set will be the list of live registers clobbered
29 /// by the regmask.
31  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
32  RegisterSet::iterator LRI = LiveRegs.begin();
33  while (LRI != LiveRegs.end()) {
34  if (MO.clobbersPhysReg(*LRI)) {
35  if (Clobbers)
36  Clobbers->push_back(std::make_pair(*LRI, &MO));
37  LRI = LiveRegs.erase(LRI);
38  } else
39  ++LRI;
40  }
41 }
42 
43 /// Remove defined registers and regmask kills from the set.
45  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
46  if (O->isReg()) {
47  if (!O->isDef() || O->isDebug())
48  continue;
49  Register Reg = O->getReg();
51  continue;
52  removeReg(Reg);
53  } else if (O->isRegMask())
55  }
56 }
57 
58 /// Add uses to the set.
60  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
61  if (!O->isReg() || !O->readsReg() || O->isDebug())
62  continue;
63  Register Reg = O->getReg();
65  continue;
66  addReg(Reg);
67  }
68 }
69 
70 /// Simulates liveness when stepping backwards over an instruction(bundle):
71 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
73  // Remove defined registers and regmask kills from the set.
74  removeDefs(MI);
75 
76  // Add uses to the set.
77  addUses(MI);
78 }
79 
80 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
81 /// killed-uses, add defs. This is the not recommended way, because it depends
82 /// on accurate kill flags. If possible use stepBackward() instead of this
83 /// function.
85  SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
86  // Remove killed registers from the set.
87  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
88  if (O->isReg() && !O->isDebug()) {
89  Register Reg = O->getReg();
91  continue;
92  if (O->isDef()) {
93  // Note, dead defs are still recorded. The caller should decide how to
94  // handle them.
95  Clobbers.push_back(std::make_pair(Reg, &*O));
96  } else {
97  if (!O->isKill())
98  continue;
99  assert(O->isUse());
100  removeReg(Reg);
101  }
102  } else if (O->isRegMask())
103  removeRegsInMask(*O, &Clobbers);
104  }
105 
106  // Add defs to the set.
107  for (auto Reg : Clobbers) {
108  // Skip dead defs and registers clobbered by regmasks. They shouldn't
109  // be added to the set.
110  if (Reg.second->isReg() && Reg.second->isDead())
111  continue;
112  if (Reg.second->isRegMask() &&
113  MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
114  continue;
115  addReg(Reg.first);
116  }
117 }
118 
119 /// Prin the currently live registers to OS.
121  OS << "Live Registers:";
122  if (!TRI) {
123  OS << " (uninitialized)\n";
124  return;
125  }
126 
127  if (empty()) {
128  OS << " (empty)\n";
129  return;
130  }
131 
132  for (const_iterator I = begin(), E = end(); I != E; ++I)
133  OS << " " << printReg(*I, TRI);
134  OS << "\n";
135 }
136 
137 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
139  dbgs() << " " << *this;
140 }
141 #endif
142 
144  MCPhysReg Reg) const {
145  if (LiveRegs.count(Reg))
146  return false;
147  if (MRI.isReserved(Reg))
148  return false;
149  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
150  if (LiveRegs.count(*R))
151  return false;
152  }
153  return true;
154 }
155 
156 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
157 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
158  for (const auto &LI : MBB.liveins()) {
159  MCPhysReg Reg = LI.PhysReg;
160  LaneBitmask Mask = LI.LaneMask;
161  MCSubRegIndexIterator S(Reg, TRI);
162  assert(Mask.any() && "Invalid livein mask");
163  if (Mask.all() || !S.isValid()) {
164  addReg(Reg);
165  continue;
166  }
167  for (; S.isValid(); ++S) {
168  unsigned SI = S.getSubRegIndex();
169  if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
170  addReg(S.getSubReg());
171  }
172  }
173 }
174 
175 /// Adds all callee saved registers to \p LiveRegs.
176 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
177  const MachineFunction &MF) {
178  const MachineRegisterInfo &MRI = MF.getRegInfo();
179  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
180  LiveRegs.addReg(*CSR);
181 }
182 
183 void LivePhysRegs::addPristines(const MachineFunction &MF) {
184  const MachineFrameInfo &MFI = MF.getFrameInfo();
185  if (!MFI.isCalleeSavedInfoValid())
186  return;
187  /// This function will usually be called on an empty object, handle this
188  /// as a special case.
189  if (empty()) {
190  /// Add all callee saved regs, then remove the ones that are saved and
191  /// restored.
192  addCalleeSavedRegs(*this, MF);
193  /// Remove the ones that are not saved/restored; they are pristine.
194  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
195  removeReg(Info.getReg());
196  return;
197  }
198  /// If a callee-saved register that is not pristine is already present
199  /// in the set, we should make sure that it stays in it. Precompute the
200  /// set of pristine registers in a separate object.
201  /// Add all callee saved regs, then remove the ones that are saved+restored.
202  LivePhysRegs Pristine(*TRI);
203  addCalleeSavedRegs(Pristine, MF);
204  /// Remove the ones that are not saved/restored; they are pristine.
205  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
206  Pristine.removeReg(Info.getReg());
207  for (MCPhysReg R : Pristine)
208  addReg(R);
209 }
210 
212  // To get the live-outs we simply merge the live-ins of all successors.
213  for (const MachineBasicBlock *Succ : MBB.successors())
214  addBlockLiveIns(*Succ);
215  if (MBB.isReturnBlock()) {
216  // Return blocks are a special case because we currently don't mark up
217  // return instructions completely: specifically, there is no explicit
218  // use for callee-saved registers. So we add all callee saved registers
219  // that are saved and restored (somewhere). This does not include
220  // callee saved registers that are unused and hence not saved and
221  // restored; they are called pristine.
222  // FIXME: PEI should add explicit markings to return instructions
223  // instead of implicitly handling them here.
224  const MachineFunction &MF = *MBB.getParent();
225  const MachineFrameInfo &MFI = MF.getFrameInfo();
226  if (MFI.isCalleeSavedInfoValid()) {
227  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
228  if (Info.isRestored())
229  addReg(Info.getReg());
230  }
231  }
232 }
233 
235  const MachineFunction &MF = *MBB.getParent();
236  addPristines(MF);
238 }
239 
241  const MachineFunction &MF = *MBB.getParent();
242  addPristines(MF);
243  addBlockLiveIns(MBB);
244 }
245 
247  const MachineBasicBlock &MBB) {
248  const MachineFunction &MF = *MBB.getParent();
249  const MachineRegisterInfo &MRI = MF.getRegInfo();
250  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
251  LiveRegs.init(TRI);
252  LiveRegs.addLiveOutsNoPristines(MBB);
253  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
254  LiveRegs.stepBackward(MI);
255 }
256 
257 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
258  assert(MBB.livein_empty() && "Expected empty live-in list");
259  const MachineFunction &MF = *MBB.getParent();
260  const MachineRegisterInfo &MRI = MF.getRegInfo();
261  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
262  for (MCPhysReg Reg : LiveRegs) {
263  if (MRI.isReserved(Reg))
264  continue;
265  // Skip the register if we are about to add one of its super registers.
266  bool ContainsSuperReg = false;
267  for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
268  if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
269  ContainsSuperReg = true;
270  break;
271  }
272  }
273  if (ContainsSuperReg)
274  continue;
275  MBB.addLiveIn(Reg);
276  }
277 }
278 
280  const MachineFunction &MF = *MBB.getParent();
281  const MachineRegisterInfo &MRI = MF.getRegInfo();
282  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
283 
284  // We walk through the block backwards and start with the live outs.
285  LivePhysRegs LiveRegs;
286  LiveRegs.init(TRI);
287  LiveRegs.addLiveOutsNoPristines(MBB);
288 
289  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
290  // Recompute dead flags.
291  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
292  if (!MO->isReg() || !MO->isDef() || MO->isDebug())
293  continue;
294 
295  Register Reg = MO->getReg();
296  if (Reg == 0)
297  continue;
299 
300  bool IsNotLive = LiveRegs.available(MRI, Reg);
301  MO->setIsDead(IsNotLive);
302  }
303 
304  // Step backward over defs.
305  LiveRegs.removeDefs(MI);
306 
307  // Recompute kill flags.
308  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
309  if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
310  continue;
311 
312  Register Reg = MO->getReg();
313  if (Reg == 0)
314  continue;
316 
317  bool IsNotLive = LiveRegs.available(MRI, Reg);
318  MO->setIsKill(IsNotLive);
319  }
320 
321  // Complete the stepbackward.
322  LiveRegs.addUses(MI);
323  }
324 }
325 
327  MachineBasicBlock &MBB) {
328  computeLiveIns(LiveRegs, MBB);
329  addLiveIns(MBB, LiveRegs);
330 }
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:476
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
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:148
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:41
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
bool isValid() const
isValid - Returns true until all the operands have been visited.
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:20
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).
constexpr bool all() const
Definition: LaneBitmask.h:53
RegisterSet::const_iterator const_iterator
Definition: LivePhysRegs.h:146
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
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...
static bool clobbersPhysReg(const uint32_t *RegMask, unsigned PhysReg)
clobbersPhysReg - Returns true if this RegMask clobbers PhysReg.
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:64
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:58
constexpr bool any() const
Definition: LaneBitmask.h:52
const_iterator end() const
Definition: LivePhysRegs.h:149
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
std::underlying_type< E >::type 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
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
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).
void recomputeLivenessFlags(MachineBasicBlock &MBB)
Recomputes dead and kill flags in MBB.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19