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