RegisterScavenging.cpp revision 66a39699fb6b862e674415b32d307263812e996e 
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/ErrorHandling.h"
25#include "llvm/Target/TargetRegisterInfo.h"
26#include "llvm/Target/TargetInstrInfo.h"
27#include "llvm/Target/TargetMachine.h"
28#include "llvm/ADT/DenseMap.h"
29#include "llvm/ADT/SmallPtrSet.h"
30#include "llvm/ADT/SmallVector.h"
31#include "llvm/ADT/STLExtras.h"
32using namespace llvm;
33
34/// setUsed - Set the register and its sub-registers as being used.
35void RegScavenger::setUsed(unsigned Reg) {
36  RegsAvailable.reset(Reg);
37
38  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
39       unsigned SubReg = *SubRegs; ++SubRegs)
40    RegsAvailable.reset(SubReg);
41}
42
43bool RegScavenger::isAliasUsed(unsigned Reg) const {
44  if (isUsed(Reg))
45    return true;
46  for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R)
47    if (isUsed(*R))
48      return true;
49  return false;
50}
51
52void RegScavenger::initRegState() {
53  ScavengedReg = 0;
54  ScavengedRC = NULL;
55  ScavengeRestore = NULL;
56
57  // All registers started out unused.
58  RegsAvailable.set();
59
60  // Reserved registers are always used.
61  RegsAvailable ^= ReservedRegs;
62
63  if (!MBB)
64    return;
65
66  // Live-in registers are in use.
67  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
68         E = MBB->livein_end(); I != E; ++I)
69    setUsed(*I);
70
71  // Pristine CSRs are also unavailable.
72  BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
73  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
74    setUsed(I);
75}
76
77void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
78  MachineFunction &MF = *mbb->getParent();
79  const TargetMachine &TM = MF.getTarget();
80  TII = TM.getInstrInfo();
81  TRI = TM.getRegisterInfo();
82  MRI = &MF.getRegInfo();
83
84  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
85         "Target changed?");
86
87  // Self-initialize.
88  if (!MBB) {
89    NumPhysRegs = TRI->getNumRegs();
90    RegsAvailable.resize(NumPhysRegs);
91
92    // Create reserved registers bitvector.
93    ReservedRegs = TRI->getReservedRegs(MF);
94
95    // Create callee-saved registers bitvector.
96    CalleeSavedRegs.resize(NumPhysRegs);
97    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
98    if (CSRegs != NULL)
99      for (unsigned i = 0; CSRegs[i]; ++i)
100        CalleeSavedRegs.set(CSRegs[i]);
101  }
102
103  // RS used within emit{Pro,Epi}logue()
104  if (mbb != MBB) {
105    MBB = mbb;
106    initRegState();
107  }
108
109  Tracking = false;
110}
111
112#ifndef NDEBUG
113/// isLiveInButUnusedBefore - Return true if register is livein the MBB not
114/// not used before it reaches the MI that defines register.
115static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
116                                    MachineBasicBlock *MBB,
117                                    const TargetRegisterInfo *TRI,
118                                    MachineRegisterInfo* MRI) {
119  // First check if register is livein.
120  bool isLiveIn = false;
121  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
122         E = MBB->livein_end(); I != E; ++I)
123    if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
124      isLiveIn = true;
125      break;
126    }
127  if (!isLiveIn)
128    return false;
129
130  // Is there any use of it before the specified MI?
131  SmallPtrSet<MachineInstr*, 4> UsesInMBB;
132  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
133         UE = MRI->use_end(); UI != UE; ++UI) {
134    MachineOperand &UseMO = UI.getOperand();
135    if (UseMO.isReg() && UseMO.isUndef())
136      continue;
137    MachineInstr *UseMI = &*UI;
138    if (UseMI->getParent() == MBB)
139      UsesInMBB.insert(UseMI);
140  }
141  if (UsesInMBB.empty())
142    return true;
143
144  for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
145    if (UsesInMBB.count(&*I))
146      return false;
147  return true;
148}
149#endif
150
151void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
152  BV.set(Reg);
153  for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
154    BV.set(*R);
155}
156
157void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
158  BV.set(Reg);
159  for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
160    BV.set(*R);
161}
162
163void RegScavenger::forward() {
164  // Move ptr forward.
165  if (!Tracking) {
166    MBBI = MBB->begin();
167    Tracking = true;
168  } else {
169    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
170    MBBI = next(MBBI);
171  }
172
173  MachineInstr *MI = MBBI;
174
175  if (MI == ScavengeRestore) {
176    ScavengedReg = 0;
177    ScavengedRC = NULL;
178    ScavengeRestore = NULL;
179  }
180
181  // Find out which registers are early clobbered, killed, defined, and marked
182  // def-dead in this instruction.
183  BitVector EarlyClobberRegs(NumPhysRegs);
184  BitVector KillRegs(NumPhysRegs);
185  BitVector DefRegs(NumPhysRegs);
186  BitVector DeadRegs(NumPhysRegs);
187  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
188    const MachineOperand &MO = MI->getOperand(i);
189    if (!MO.isReg() || MO.isUndef())
190      continue;
191    unsigned Reg = MO.getReg();
192    if (!Reg || isReserved(Reg))
193      continue;
194
195    if (MO.isUse()) {
196      // Two-address operands implicitly kill.
197      if (MO.isKill() || MI->isRegTiedToDefOperand(i))
198        addRegWithSubRegs(KillRegs, Reg);
199    } else {
200      assert(MO.isDef());
201      if (MO.isDead())
202        addRegWithSubRegs(DeadRegs, Reg);
203      else
204        addRegWithSubRegs(DefRegs, Reg);
205      if (MO.isEarlyClobber())
206        addRegWithAliases(EarlyClobberRegs, Reg);
207    }
208  }
209
210  // Verify uses and defs.
211  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
212    const MachineOperand &MO = MI->getOperand(i);
213    if (!MO.isReg() || MO.isUndef())
214      continue;
215    unsigned Reg = MO.getReg();
216    if (!Reg || isReserved(Reg))
217      continue;
218    if (MO.isUse()) {
219      assert(isUsed(Reg) && "Using an undefined register!");
220      assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) &&
221             "Using an early clobbered register!");
222    } else {
223      assert(MO.isDef());
224      assert((KillRegs.test(Reg) || isUnused(Reg) ||
225              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
226             "Re-defining a live register!");
227    }
228  }
229
230  // Commit the changes.
231  setUnused(KillRegs);
232  setUnused(DeadRegs);
233  setUsed(DefRegs);
234}
235
236void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
237  if (includeReserved)
238    used = ~RegsAvailable;
239  else
240    used = ~RegsAvailable & ~ReservedRegs;
241}
242
243/// CreateRegClassMask - Set the bits that represent the registers in the
244/// TargetRegisterClass.
245static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
246  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
247       ++I)
248    Mask.set(*I);
249}
250
251unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
252                                     const BitVector &Candidates) const {
253  // Mask off the registers which are not in the TargetRegisterClass.
254  BitVector RegsAvailableCopy(NumPhysRegs, false);
255  CreateRegClassMask(RegClass, RegsAvailableCopy);
256  RegsAvailableCopy &= RegsAvailable;
257
258  // Restrict the search to candidates.
259  RegsAvailableCopy &= Candidates;
260
261  // Returns the first unused (bit is set) register, or 0 is none is found.
262  int Reg = RegsAvailableCopy.find_first();
263  return (Reg == -1) ? 0 : Reg;
264}
265
266unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
267                                     bool ExCalleeSaved) const {
268  // Mask off the registers which are not in the TargetRegisterClass.
269  BitVector RegsAvailableCopy(NumPhysRegs, false);
270  CreateRegClassMask(RegClass, RegsAvailableCopy);
271  RegsAvailableCopy &= RegsAvailable;
272
273  // If looking for a non-callee-saved register, mask off all the callee-saved
274  // registers.
275  if (ExCalleeSaved)
276    RegsAvailableCopy &= ~CalleeSavedRegs;
277
278  // Returns the first unused (bit is set) register, or 0 is none is found.
279  int Reg = RegsAvailableCopy.find_first();
280  return (Reg == -1) ? 0 : Reg;
281}
282
283/// findSurvivorReg - Return the candidate register that is unused for the
284/// longest after MBBI. UseMI is set to the instruction where the search
285/// stopped.
286///
287/// No more than InstrLimit instructions are inspected.
288///
289unsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator MI,
290                                       BitVector &Candidates,
291                                       unsigned InstrLimit,
292                                       MachineBasicBlock::iterator &UseMI) {
293  int Survivor = Candidates.find_first();
294  assert(Survivor > 0 && "No candidates for scavenging");
295
296  MachineBasicBlock::iterator ME = MBB->getFirstTerminator();
297  assert(MI != ME && "MI already at terminator");
298
299  for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) {
300    // Remove any candidates touched by instruction.
301    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
302      const MachineOperand &MO = MI->getOperand(i);
303      if (!MO.isReg() || MO.isUndef() || !MO.getReg())
304        continue;
305      Candidates.reset(MO.getReg());
306      for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++)
307        Candidates.reset(*R);
308    }
309
310    // Was our survivor untouched by this instruction?
311    if (Candidates.test(Survivor))
312      continue;
313
314    // All candidates gone?
315    if (Candidates.none())
316      break;
317
318    Survivor = Candidates.find_first();
319  }
320
321  // We ran out of candidates, so stop the search.
322  UseMI = MI;
323  return Survivor;
324}
325
326unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
327                                        MachineBasicBlock::iterator I,
328                                        int SPAdj) {
329  assert(ScavengingFrameIndex >= 0 &&
330         "Cannot scavenge a register without an emergency spill slot!");
331
332  // Mask off the registers which are not in the TargetRegisterClass.
333  BitVector Candidates(NumPhysRegs, false);
334  CreateRegClassMask(RC, Candidates);
335  // Do not include reserved registers.
336  Candidates ^= ReservedRegs & Candidates;
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())
342      Candidates.reset(MO.getReg());
343  }
344
345  // Find the register whose use is furthest away.
346  MachineBasicBlock::iterator UseMI;
347  unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI);
348
349  // If we found an unused register there is no reason to spill it. We have
350  // probably found a callee-saved register that has been saved in the
351  // prologue, but happens to be unused at this point.
352  if (!isAliasUsed(SReg))
353    return SReg;
354
355  assert(ScavengedReg == 0 &&
356         "Scavenger slot is live, unable to scavenge another register!");
357
358  // Avoid infinite regress
359  ScavengedReg = SReg;
360
361  // Spill the scavenged register before I.
362  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
363  MachineBasicBlock::iterator II = prior(I);
364  TRI->eliminateFrameIndex(II, SPAdj, this);
365
366  // Restore the scavenged register before its use (or first terminator).
367  TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC);
368  ScavengeRestore = prior(UseMI);
369  // Doing this here leads to infinite regress.
370  // ScavengedReg = SReg;
371  ScavengedRC = RC;
372
373  return SReg;
374}
375