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