LLVM  6.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/Support/Debug.h"
23 using namespace llvm;
24 
25 
26 /// \brief 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<unsigned, const MachineOperand*>> *Clobbers) {
32  SparseSet<unsigned>::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())
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())
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<unsigned, const MachineOperand*>> &Clobbers) {
86  // Remove killed registers from the set.
87  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
88  if (O->isReg()) {
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. They shouldn't be added to the set.
109  if (Reg.second->isReg() && Reg.second->isDead())
110  continue;
111  addReg(Reg.first);
112  }
113 }
114 
115 /// Prin 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  unsigned 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  unsigned 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  if (!MBB.succ_empty()) {
209  // To get the live-outs we simply merge the live-ins of all successors.
210  for (const MachineBasicBlock *Succ : MBB.successors())
211  addBlockLiveIns(*Succ);
212  } else if (MBB.isReturnBlock()) {
213  // For the return block: Add all callee saved registers that are saved and
214  // restored (somewhere); This does not include callee saved registers that
215  // are unused and hence not saved and restored; they are called pristine.
216  const MachineFunction &MF = *MBB.getParent();
217  const MachineFrameInfo &MFI = MF.getFrameInfo();
218  if (MFI.isCalleeSavedInfoValid()) {
219  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
220  if (Info.isRestored())
221  addReg(Info.getReg());
222  }
223  }
224 }
225 
227  const MachineFunction &MF = *MBB.getParent();
228  if (!MBB.succ_empty()) {
229  addPristines(MF);
231  } else if (MBB.isReturnBlock()) {
232  // For the return block: Add all callee saved registers.
233  const MachineFrameInfo &MFI = MF.getFrameInfo();
234  if (MFI.isCalleeSavedInfoValid())
235  addCalleeSavedRegs(*this, MF);
236  }
237 }
238 
240  const MachineFunction &MF = *MBB.getParent();
241  addPristines(MF);
242  addBlockLiveIns(MBB);
243 }
244 
246  const MachineBasicBlock &MBB) {
247  const MachineFunction &MF = *MBB.getParent();
248  const MachineRegisterInfo &MRI = MF.getRegInfo();
249  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
250  LiveRegs.init(TRI);
251  LiveRegs.addLiveOutsNoPristines(MBB);
252  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
253  LiveRegs.stepBackward(MI);
254 }
255 
256 void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
257  assert(MBB.livein_empty() && "Expected empty live-in list");
258  const MachineFunction &MF = *MBB.getParent();
259  const MachineRegisterInfo &MRI = MF.getRegInfo();
260  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
261  for (MCPhysReg Reg : LiveRegs) {
262  if (MRI.isReserved(Reg))
263  continue;
264  // Skip the register if we are about to add one of its super registers.
265  bool ContainsSuperReg = false;
266  for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); ++SReg) {
267  if (LiveRegs.contains(*SReg) && !MRI.isReserved(*SReg)) {
268  ContainsSuperReg = true;
269  break;
270  }
271  }
272  if (ContainsSuperReg)
273  continue;
274  MBB.addLiveIn(Reg);
275  }
276 }
277 
279  const MachineFunction &MF = *MBB.getParent();
280  const MachineRegisterInfo &MRI = MF.getRegInfo();
281  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
282 
283  // We walk through the block backwards and start with the live outs.
284  LivePhysRegs LiveRegs;
285  LiveRegs.init(TRI);
286  LiveRegs.addLiveOutsNoPristines(MBB);
287 
288  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
289  // Recompute dead flags.
290  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
291  if (!MO->isReg() || !MO->isDef() || MO->isDebug())
292  continue;
293 
294  unsigned Reg = MO->getReg();
295  if (Reg == 0)
296  continue;
298 
299  bool IsNotLive = LiveRegs.available(MRI, Reg);
300  MO->setIsDead(IsNotLive);
301  }
302 
303  // Step backward over defs.
304  LiveRegs.removeDefs(MI);
305 
306  // Recompute kill flags.
307  for (MIBundleOperands MO(MI); MO.isValid(); ++MO) {
308  if (!MO->isReg() || !MO->readsReg() || MO->isDebug())
309  continue;
310 
311  unsigned Reg = MO->getReg();
312  if (Reg == 0)
313  continue;
315 
316  bool IsNotLive = LiveRegs.available(MRI, Reg);
317  MO->setIsKill(IsNotLive);
318  }
319 
320  // Complete the stepbackward.
321  LiveRegs.addUses(MI);
322  }
323 }
324 
326  MachineBasicBlock &MBB) {
327  computeLiveIns(LiveRegs, MBB);
328  addLiveIns(MBB, LiveRegs);
329 }
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
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:449
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. ...
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.
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:42
Reg
All possible values of the reg field in the ModR/M byte.
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.
Printable PrintReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubRegIdx=0)
Prints virtual and physical registers with or without a TRI instance.
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: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: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: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.
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:59
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:123
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:44
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