LLVM  8.0.0svn
LivePhysRegs.cpp
Go to the documentation of this file.
1 //===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LivePhysRegs utility for tracking liveness of
11 // physical registers across machine instructions in forward or backward order.
12 // A more detailed description can be found in the corresponding header file.
13 //
14 //===----------------------------------------------------------------------===//
15 
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<unsigned, const MachineOperand*>> *Clobbers) {
33  SparseSet<unsigned>::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 (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
47  if (O->isReg()) {
48  if (!O->isDef() || O->isDebug())
49  continue;
50  unsigned Reg = O->getReg();
52  continue;
53  removeReg(Reg);
54  } else if (O->isRegMask())
56  }
57 }
58 
59 /// Add uses to the set.
61  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
62  if (!O->isReg() || !O->readsReg() || O->isDebug())
63  continue;
64  unsigned Reg = O->getReg();
66  continue;
67  addReg(Reg);
68  }
69 }
70 
71 /// Simulates liveness when stepping backwards over an instruction(bundle):
72 /// Remove Defs, add uses. This is the recommended way of calculating liveness.
74  // Remove defined registers and regmask kills from the set.
75  removeDefs(MI);
76 
77  // Add uses to the set.
78  addUses(MI);
79 }
80 
81 /// Simulates liveness when stepping forward over an instruction(bundle): Remove
82 /// killed-uses, add defs. This is the not recommended way, because it depends
83 /// on accurate kill flags. If possible use stepBackward() instead of this
84 /// function.
86  SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
87  // Remove killed registers from the set.
88  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
89  if (O->isReg() && !O->isDebug()) {
90  unsigned Reg = O->getReg();
92  continue;
93  if (O->isDef()) {
94  // Note, dead defs are still recorded. The caller should decide how to
95  // handle them.
96  Clobbers.push_back(std::make_pair(Reg, &*O));
97  } else {
98  if (!O->isKill())
99  continue;
100  assert(O->isUse());
101  removeReg(Reg);
102  }
103  } else if (O->isRegMask())
104  removeRegsInMask(*O, &Clobbers);
105  }
106 
107  // Add defs to the set.
108  for (auto Reg : Clobbers) {
109  // Skip dead defs and registers clobbered by regmasks. They shouldn't
110  // be added to the set.
111  if (Reg.second->isReg() && Reg.second->isDead())
112  continue;
113  if (Reg.second->isRegMask() &&
114  MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first))
115  continue;
116  addReg(Reg.first);
117  }
118 }
119 
120 /// Prin the currently live registers to OS.
122  OS << "Live Registers:";
123  if (!TRI) {
124  OS << " (uninitialized)\n";
125  return;
126  }
127 
128  if (empty()) {
129  OS << " (empty)\n";
130  return;
131  }
132 
133  for (const_iterator I = begin(), E = end(); I != E; ++I)
134  OS << " " << printReg(*I, TRI);
135  OS << "\n";
136 }
137 
138 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
140  dbgs() << " " << *this;
141 }
142 #endif
143 
145  unsigned Reg) const {
146  if (LiveRegs.count(Reg))
147  return false;
148  if (MRI.isReserved(Reg))
149  return false;
150  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
151  if (LiveRegs.count(*R))
152  return false;
153  }
154  return true;
155 }
156 
157 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
158 void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
159  for (const auto &LI : MBB.liveins()) {
160  unsigned Reg = LI.PhysReg;
161  LaneBitmask Mask = LI.LaneMask;
162  MCSubRegIndexIterator S(Reg, TRI);
163  assert(Mask.any() && "Invalid livein mask");
164  if (Mask.all() || !S.isValid()) {
165  addReg(Reg);
166  continue;
167  }
168  for (; S.isValid(); ++S) {
169  unsigned SI = S.getSubRegIndex();
170  if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
171  addReg(S.getSubReg());
172  }
173  }
174 }
175 
176 /// Adds all callee saved registers to \p LiveRegs.
177 static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
178  const MachineFunction &MF) {
179  const MachineRegisterInfo &MRI = MF.getRegInfo();
180  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); CSR && *CSR; ++CSR)
181  LiveRegs.addReg(*CSR);
182 }
183 
184 void LivePhysRegs::addPristines(const MachineFunction &MF) {
185  const MachineFrameInfo &MFI = MF.getFrameInfo();
186  if (!MFI.isCalleeSavedInfoValid())
187  return;
188  /// This function will usually be called on an empty object, handle this
189  /// as a special case.
190  if (empty()) {
191  /// Add all callee saved regs, then remove the ones that are saved and
192  /// restored.
193  addCalleeSavedRegs(*this, MF);
194  /// Remove the ones that are not saved/restored; they are pristine.
195  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
196  removeReg(Info.getReg());
197  return;
198  }
199  /// If a callee-saved register that is not pristine is already present
200  /// in the set, we should make sure that it stays in it. Precompute the
201  /// set of pristine registers in a separate object.
202  /// Add all callee saved regs, then remove the ones that are saved+restored.
203  LivePhysRegs Pristine(*TRI);
204  addCalleeSavedRegs(Pristine, MF);
205  /// Remove the ones that are not saved/restored; they are pristine.
206  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
207  Pristine.removeReg(Info.getReg());
208  for (MCPhysReg R : Pristine)
209  addReg(R);
210 }
211 
213  // To get the live-outs we simply merge the live-ins of all successors.
214  for (const MachineBasicBlock *Succ : MBB.successors())
215  addBlockLiveIns(*Succ);
216  if (MBB.isReturnBlock()) {
217  // Return blocks are a special case because we currently don't mark up
218  // return instructions completely: specifically, there is no explicit
219  // use for callee-saved registers. So we add all callee saved registers
220  // that are saved and restored (somewhere). This does not include
221  // callee saved registers that are unused and hence not saved and
222  // restored; they are called pristine.
223  // FIXME: PEI should add explicit markings to return instructions
224  // instead of implicitly handling them here.
225  const MachineFunction &MF = *MBB.getParent();
226  const MachineFrameInfo &MFI = MF.getFrameInfo();
227  if (MFI.isCalleeSavedInfoValid()) {
228  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
229  if (Info.isRestored())
230  addReg(Info.getReg());
231  }
232  }
233 }
234 
236  const MachineFunction &MF = *MBB.getParent();
237  addPristines(MF);
239 }
240 
242  const MachineFunction &MF = *MBB.getParent();
243  addPristines(MF);
244  addBlockLiveIns(MBB);
245 }
246 
248  const MachineBasicBlock &MBB) {
249  const MachineFunction &MF = *MBB.getParent();
250  const MachineRegisterInfo &MRI = MF.getRegInfo();
251  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
252  LiveRegs.init(TRI);
253  LiveRegs.addLiveOutsNoPristines(MBB);
254  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
255  LiveRegs.stepBackward(MI);
256 }
257 
258 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
259  assert(MBB.livein_empty() && "Expected empty live-in list");
260  const MachineFunction &MF = *MBB.getParent();
261  const MachineRegisterInfo &MRI = MF.getRegInfo();
262  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
263  for (MCPhysReg Reg : LiveRegs) {
264  if (MRI.isReserved(Reg))
265  continue;
266  // Skip the register if we are about to add one of its super registers.
267  bool ContainsSuperReg = false;
268  for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
269  if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
270  ContainsSuperReg = true;
271  break;
272  }
273  }
274  if (ContainsSuperReg)
275  continue;
276  MBB.addLiveIn(Reg);
277  }
278 }
279 
281  const MachineFunction &MF = *MBB.getParent();
282  const MachineRegisterInfo &MRI = MF.getRegInfo();
283  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
284 
285  // We walk through the block backwards and start with the live outs.
286  LivePhysRegs LiveRegs;
287  LiveRegs.init(TRI);
288  LiveRegs.addLiveOutsNoPristines(MBB);
289 
290  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
291  // Recompute dead flags.
292  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
293  if (!MO->isReg() || !MO->isDef() || MO->isDebug())
294  continue;
295 
296  unsigned Reg = MO->getReg();
297  if (Reg == 0)
298  continue;
300 
301  bool IsNotLive = LiveRegs.available(MRI, Reg);
302  MO->setIsDead(IsNotLive);
303  }
304 
305  // Step backward over defs.
306  LiveRegs.removeDefs(MI);
307 
308  // Recompute kill flags.
309  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
310  if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
311  continue;
312 
313  unsigned Reg = MO->getReg();
314  if (Reg == 0)
315  continue;
317 
318  bool IsNotLive = LiveRegs.available(MRI, Reg);
319  MO->setIsKill(IsNotLive);
320  }
321 
322  // Complete the stepbackward.
323  LiveRegs.addUses(MI);
324  }
325 }
326 
328  MachineBasicBlock &MBB) {
329  computeLiveIns(LiveRegs, MBB);
330  addLiveIns(MBB, LiveRegs);
331 }
bool isCalleeSavedInfoValid() const
Has the callee saved info been calculated yet?
void stepForward(const MachineInstr &MI, SmallVectorImpl< std::pair< unsigned, const MachineOperand *>> &Clobbers)
Simulates liveness when stepping forward over an instruction(bundle).
bool available(const MachineRegisterInfo &MRI, unsigned Reg) const
Returns true if register Reg and no aliasing register is in the set.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void dump() const
Dumps the currently live registers to the debug output.
void removeRegsInMask(const MachineOperand &MO, SmallVectorImpl< std::pair< unsigned, const MachineOperand *>> *Clobbers=nullptr)
Removes physical registers clobbered by the regmask operand MO.
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:236
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
#define LLVM_DUMP_METHOD
Definition: Compiler.h:74
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()
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:286
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:54
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:176
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.
MachineOperand class - Representation of each machine instruction operand.
const_iterator begin() const
Definition: SparseSet.h:175
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:133
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 removeReg(unsigned Reg)
Removes a physical register, all its sub-registers, and all its super-registers from the set...
Definition: LivePhysRegs.h:89
void removeDefs(const MachineInstr &MI)
Remove defined registers and regmask kills from the set.
SparseSet - Fast set implmentation for objects that can be identified by small unsigned keys...
Definition: SparseSet.h:124
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:49
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:53
const_iterator end() const
Definition: LivePhysRegs.h:149
SparseSet< unsigned >::const_iterator const_iterator
Definition: LivePhysRegs.h:146
iterator_range< livein_iterator > liveins() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const MCPhysReg * getCalleeSavedRegs() const
Returns list of callee saved registers.
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:81
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
IRTranslator LLVM IR MI
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.
void addReg(unsigned Reg)
Adds a physical register and all its sub-registers to the set.
Definition: LivePhysRegs.h:79