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  unsigned 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  unsigned 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  unsigned 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  unsigned 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  unsigned 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?
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:473
void dump() const
Dumps the currently live registers to the debug output.
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.
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.
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
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...
iterator erase(iterator I)
erase - Erases an existing element identified by a valid iterator.
Definition: SparseSet.h:285
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const TargetRegisterInfo * getTargetRegisterInfo() const
unsigned const MachineRegisterInfo * MRI
unsigned getSubReg() const
Returns current sub-register.
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
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
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
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.
bool isReserved(unsigned PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.