1//===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
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 machine register scavenger. It can provide
11// information, such as unused registers, at any point in a machine basic block.
12// It also provides a mechanism to make registers available by evicting them to
13// spill slots.
14//
15//===----------------------------------------------------------------------===//
16
17#define DEBUG_TYPE "reg-scavenging"
18#include "llvm/CodeGen/RegisterScavenging.h"
19#include "llvm/CodeGen/MachineFrameInfo.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27#include "llvm/Target/TargetRegisterInfo.h"
28#include "llvm/Target/TargetInstrInfo.h"
29#include "llvm/Target/TargetMachine.h"
30#include "llvm/ADT/DenseMap.h"
31#include "llvm/ADT/SmallPtrSet.h"
32#include "llvm/ADT/SmallVector.h"
33#include "llvm/ADT/STLExtras.h"
34using namespace llvm;
35
36/// setUsed - Set the register and its sub-registers as being used.
37void RegScavenger::setUsed(unsigned Reg) {
38  RegsAvailable.reset(Reg);
39
40  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
41    RegsAvailable.reset(*SubRegs);
42}
43
44bool RegScavenger::isAliasUsed(unsigned Reg) const {
45  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI)
46    if (isUsed(*AI))
47      return true;
48  return false;
49}
50
51void RegScavenger::initRegState() {
52  ScavengedReg = 0;
53  ScavengedRC = NULL;
54  ScavengeRestore = NULL;
55
56  // All registers started out unused.
57  RegsAvailable.set();
58
59  if (!MBB)
60    return;
61
62  // Live-in registers are in use.
63  for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(),
64         E = MBB->livein_end(); I != E; ++I)
65    setUsed(*I);
66
67  // Pristine CSRs are also unavailable.
68  BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
69  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
70    setUsed(I);
71}
72
73void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
74  MachineFunction &MF = *mbb->getParent();
75  const TargetMachine &TM = MF.getTarget();
76  TII = TM.getInstrInfo();
77  TRI = TM.getRegisterInfo();
78  MRI = &MF.getRegInfo();
79
80  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
81         "Target changed?");
82
83  // It is not possible to use the register scavenger after late optimization
84  // passes that don't preserve accurate liveness information.
85  assert(MRI->tracksLiveness() &&
86         "Cannot use register scavenger with inaccurate liveness");
87
88  // Self-initialize.
89  if (!MBB) {
90    NumPhysRegs = TRI->getNumRegs();
91    RegsAvailable.resize(NumPhysRegs);
92    KillRegs.resize(NumPhysRegs);
93    DefRegs.resize(NumPhysRegs);
94
95    // Create reserved registers bitvector.
96    ReservedRegs = TRI->getReservedRegs(MF);
97
98    // Create callee-saved registers bitvector.
99    CalleeSavedRegs.resize(NumPhysRegs);
100    const uint16_t *CSRegs = TRI->getCalleeSavedRegs(&MF);
101    if (CSRegs != NULL)
102      for (unsigned i = 0; CSRegs[i]; ++i)
103        CalleeSavedRegs.set(CSRegs[i]);
104  }
105
106  MBB = mbb;
107  initRegState();
108
109  Tracking = false;
110}
111
112void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
113  BV.set(Reg);
114  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
115    BV.set(*SubRegs);
116}
117
118void RegScavenger::forward() {
119  // Move ptr forward.
120  if (!Tracking) {
121    MBBI = MBB->begin();
122    Tracking = true;
123  } else {
124    assert(MBBI != MBB->end() && "Already past the end of the basic block!");
125    MBBI = llvm::next(MBBI);
126  }
127  assert(MBBI != MBB->end() && "Already at the end of the basic block!");
128
129  MachineInstr *MI = MBBI;
130
131  if (MI == ScavengeRestore) {
132    ScavengedReg = 0;
133    ScavengedRC = NULL;
134    ScavengeRestore = NULL;
135  }
136
137  if (MI->isDebugValue())
138    return;
139
140  // Find out which registers are early clobbered, killed, defined, and marked
141  // def-dead in this instruction.
142  // FIXME: The scavenger is not predication aware. If the instruction is
143  // predicated, conservatively assume "kill" markers do not actually kill the
144  // register. Similarly ignores "dead" markers.
145  bool isPred = TII->isPredicated(MI);
146  KillRegs.reset();
147  DefRegs.reset();
148  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
149    const MachineOperand &MO = MI->getOperand(i);
150    if (MO.isRegMask())
151      (isPred ? DefRegs : KillRegs).setBitsNotInMask(MO.getRegMask());
152    if (!MO.isReg())
153      continue;
154    unsigned Reg = MO.getReg();
155    if (!Reg || isReserved(Reg))
156      continue;
157
158    if (MO.isUse()) {
159      // Ignore undef uses.
160      if (MO.isUndef())
161        continue;
162      if (!isPred && MO.isKill())
163        addRegWithSubRegs(KillRegs, Reg);
164    } else {
165      assert(MO.isDef());
166      if (!isPred && MO.isDead())
167        addRegWithSubRegs(KillRegs, Reg);
168      else
169        addRegWithSubRegs(DefRegs, Reg);
170    }
171  }
172
173  // Verify uses and defs.
174#ifndef NDEBUG
175  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
176    const MachineOperand &MO = MI->getOperand(i);
177    if (!MO.isReg())
178      continue;
179    unsigned Reg = MO.getReg();
180    if (!Reg || isReserved(Reg))
181      continue;
182    if (MO.isUse()) {
183      if (MO.isUndef())
184        continue;
185      if (!isUsed(Reg)) {
186        // Check if it's partial live: e.g.
187        // D0 = insert_subreg D0<undef>, S0
188        // ... D0
189        // The problem is the insert_subreg could be eliminated. The use of
190        // D0 is using a partially undef value. This is not *incorrect* since
191        // S1 is can be freely clobbered.
192        // Ideally we would like a way to model this, but leaving the
193        // insert_subreg around causes both correctness and performance issues.
194        bool SubUsed = false;
195        for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs)
196          if (isUsed(*SubRegs)) {
197            SubUsed = true;
198            break;
199          }
200        if (!SubUsed) {
201          MBB->getParent()->verify(NULL, "In Register Scavenger");
202          llvm_unreachable("Using an undefined register!");
203        }
204        (void)SubUsed;
205      }
206    } else {
207      assert(MO.isDef());
208#if 0
209      // FIXME: Enable this once we've figured out how to correctly transfer
210      // implicit kills during codegen passes like the coalescer.
211      assert((KillRegs.test(Reg) || isUnused(Reg) ||
212              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
213             "Re-defining a live register!");
214#endif
215    }
216  }
217#endif // NDEBUG
218
219  // Commit the changes.
220  setUnused(KillRegs);
221  setUsed(DefRegs);
222}
223
224void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
225  used = RegsAvailable;
226  used.flip();
227  if (includeReserved)
228    used |= ReservedRegs;
229  else
230    used.reset(ReservedRegs);
231}
232
233unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
234  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
235       I != E; ++I)
236    if (!isAliasUsed(*I)) {
237      DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) <<
238            "\n");
239      return *I;
240    }
241  return 0;
242}
243
244/// getRegsAvailable - Return all available registers in the register class
245/// in Mask.
246BitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) {
247  BitVector Mask(TRI->getNumRegs());
248  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
249       I != E; ++I)
250    if (!isAliasUsed(*I))
251      Mask.set(*I);
252  return Mask;
253}
254
255/// findSurvivorReg - Return the candidate register that is unused for the
256/// longest after StargMII. UseMI is set to the instruction where the search
257/// stopped.
258///
259/// No more than InstrLimit instructions are inspected.
260///
261unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI,
262                                       BitVector &Candidates,
263                                       unsigned InstrLimit,
264                                       MachineBasicBlock::iterator &UseMI) {
265  int Survivor = Candidates.find_first();
266  assert(Survivor > 0 && "No candidates for scavenging");
267
268  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
269  assert(StartMI != ME && "MI already at terminator");
270  MachineBasicBlock::iterator RestorePointMI = StartMI;
271  MachineBasicBlock::iterator MI = StartMI;
272
273  bool inVirtLiveRange = false;
274  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
275    if (MI->isDebugValue()) {
276      ++InstrLimit; // Don't count debug instructions
277      continue;
278    }
279    bool isVirtKillInsn = false;
280    bool isVirtDefInsn = false;
281    // Remove any candidates touched by instruction.
282    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
283      const MachineOperand &MO = MI->getOperand(i);
284      if (MO.isRegMask())
285        Candidates.clearBitsNotInMask(MO.getRegMask());
286      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
287        continue;
288      if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
289        if (MO.isDef())
290          isVirtDefInsn = true;
291        else if (MO.isKill())
292          isVirtKillInsn = true;
293        continue;
294      }
295      for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
296        Candidates.reset(*AI);
297    }
298    // If we're not in a virtual reg's live range, this is a valid
299    // restore point.
300    if (!inVirtLiveRange) RestorePointMI = MI;
301
302    // Update whether we're in the live range of a virtual register
303    if (isVirtKillInsn) inVirtLiveRange = false;
304    if (isVirtDefInsn) inVirtLiveRange = true;
305
306    // Was our survivor untouched by this instruction?
307    if (Candidates.test(Survivor))
308      continue;
309
310    // All candidates gone?
311    if (Candidates.none())
312      break;
313
314    Survivor = Candidates.find_first();
315  }
316  // If we ran off the end, that's where we want to restore.
317  if (MI == ME) RestorePointMI = ME;
318  assert (RestorePointMI != StartMI &&
319          "No available scavenger restore location!");
320
321  // We ran out of candidates, so stop the search.
322  UseMI = RestorePointMI;
323  return Survivor;
324}
325
326unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
327                                        MachineBasicBlock::iterator I,
328                                        int SPAdj) {
329  // Consider all allocatable registers in the register class initially
330  BitVector Candidates =
331    TRI->getAllocatableSet(*I->getParent()->getParent(), RC);
332
333  // Exclude all the registers being used by the instruction.
334  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
335    MachineOperand &MO = I->getOperand(i);
336    if (MO.isReg() && MO.getReg() != 0 &&
337        !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
338      Candidates.reset(MO.getReg());
339  }
340
341  // Try to find a register that's unused if there is one, as then we won't
342  // have to spill. Search explicitly rather than masking out based on
343  // RegsAvailable, as RegsAvailable does not take aliases into account.
344  // That's what getRegsAvailable() is for.
345  BitVector Available = getRegsAvailable(RC);
346  Available &= Candidates;
347  if (Available.any())
348    Candidates = Available;
349
350  // Find the register whose use is furthest away.
351  MachineBasicBlock::iterator UseMI;
352  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
353
354  // If we found an unused register there is no reason to spill it.
355  if (!isAliasUsed(SReg)) {
356    DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n");
357    return SReg;
358  }
359
360  assert(ScavengedReg == 0 &&
361         "Scavenger slot is live, unable to scavenge another register!");
362
363  // Avoid infinite regress
364  ScavengedReg = SReg;
365
366  // If the target knows how to save/restore the register, let it do so;
367  // otherwise, use the emergency stack spill slot.
368  if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) {
369    // Spill the scavenged register before I.
370    assert(ScavengingFrameIndex >= 0 &&
371           "Cannot scavenge register without an emergency spill slot!");
372    TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI);
373    MachineBasicBlock::iterator II = prior(I);
374    TRI->eliminateFrameIndex(II, SPAdj, this);
375
376    // Restore the scavenged register before its use (or first terminator).
377    TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI);
378    II = prior(UseMI);
379    TRI->eliminateFrameIndex(II, SPAdj, this);
380  }
381
382  ScavengeRestore = prior(UseMI);
383
384  // Doing this here leads to infinite regress.
385  // ScavengedReg = SReg;
386  ScavengedRC = RC;
387
388  DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) <<
389        "\n");
390
391  return SReg;
392}
393