RegisterScavenging.cpp revision 159abc0158542e0a7fe3a1200e93df0af32e163c 
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/MachineFunction.h"
20#include "llvm/CodeGen/MachineBasicBlock.h"
21#include "llvm/CodeGen/MachineInstr.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Target/TargetRegisterInfo.h"
25#include "llvm/Target/TargetInstrInfo.h"
26#include "llvm/Target/TargetMachine.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/SmallVector.h"
29#include "llvm/ADT/STLExtras.h"
30using namespace llvm;
31
32/// RedefinesSuperRegPart - Return true if the specified register is redefining
33/// part of a super-register.
34static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
35                                  const TargetRegisterInfo *TRI) {
36  bool SeenSuperUse = false;
37  bool SeenSuperDef = false;
38  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
39    const MachineOperand &MO = MI->getOperand(i);
40    if (!MO.isReg() || MO.isUndef())
41      continue;
42    if (TRI->isSuperRegister(SubReg, MO.getReg())) {
43      if (MO.isUse())
44        SeenSuperUse = true;
45      else if (MO.isImplicit())
46        SeenSuperDef = true;
47    }
48  }
49
50  return SeenSuperDef && SeenSuperUse;
51}
52
53static bool RedefinesSuperRegPart(const MachineInstr *MI,
54                                  const MachineOperand &MO,
55                                  const TargetRegisterInfo *TRI) {
56  assert(MO.isReg() && MO.isDef() && "Not a register def!");
57  return RedefinesSuperRegPart(MI, MO.getReg(), TRI);
58}
59
60bool RegScavenger::isSuperRegUsed(unsigned Reg) const {
61  for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg);
62       unsigned SuperReg = *SuperRegs; ++SuperRegs)
63    if (isUsed(SuperReg))
64      return true;
65  return false;
66}
67
68/// setUsed - Set the register and its sub-registers as being used.
69void RegScavenger::setUsed(unsigned Reg) {
70  RegsAvailable.reset(Reg);
71
72  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
73       unsigned SubReg = *SubRegs; ++SubRegs)
74    RegsAvailable.reset(SubReg);
75}
76
77/// setUnused - Set the register and its sub-registers as being unused.
78void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
79  RegsAvailable.set(Reg);
80
81  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
82       unsigned SubReg = *SubRegs; ++SubRegs)
83    if (!RedefinesSuperRegPart(MI, Reg, TRI))
84      RegsAvailable.set(SubReg);
85}
86
87void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
88  MachineFunction &MF = *mbb->getParent();
89  const TargetMachine &TM = MF.getTarget();
90  TII = TM.getInstrInfo();
91  TRI = TM.getRegisterInfo();
92  MRI = &MF.getRegInfo();
93
94  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
95         "Target changed?");
96
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  MBB = mbb;
113  ScavengedReg = 0;
114  ScavengedRC = NULL;
115  ScavengeRestore = NULL;
116  CurrDist = 0;
117  DistanceMap.clear();
118
119  // All registers started out unused.
120  RegsAvailable.set();
121
122  // Reserved registers are always used.
123  RegsAvailable ^= ReservedRegs;
124
125  // Live-in registers are in use.
126  if (!MBB->livein_empty())
127    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
128           E = MBB->livein_end(); I != E; ++I)
129      setUsed(*I);
130
131  Tracking = false;
132}
133
134void RegScavenger::restoreScavengedReg() {
135  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
136                            ScavengingFrameIndex, ScavengedRC);
137  MachineBasicBlock::iterator II = prior(MBBI);
138  TRI->eliminateFrameIndex(II, 0, this);
139  setUsed(ScavengedReg);
140  ScavengedReg = 0;
141  ScavengedRC = NULL;
142}
143
144#ifndef NDEBUG
145/// isLiveInButUnusedBefore - Return true if register is livein the MBB not
146/// not used before it reaches the MI that defines register.
147static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
148                                    MachineBasicBlock *MBB,
149                                    const TargetRegisterInfo *TRI,
150                                    MachineRegisterInfo* MRI) {
151  // First check if register is livein.
152  bool isLiveIn = false;
153  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
154         E = MBB->livein_end(); I != E; ++I)
155    if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
156      isLiveIn = true;
157      break;
158    }
159  if (!isLiveIn)
160    return false;
161
162  // Is there any use of it before the specified MI?
163  SmallPtrSet<MachineInstr*, 4> UsesInMBB;
164  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
165         UE = MRI->use_end(); UI != UE; ++UI) {
166    MachineOperand &UseMO = UI.getOperand();
167    if (UseMO.isReg() && UseMO.isUndef())
168      continue;
169    MachineInstr *UseMI = &*UI;
170    if (UseMI->getParent() == MBB)
171      UsesInMBB.insert(UseMI);
172  }
173  if (UsesInMBB.empty())
174    return true;
175
176  for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
177    if (UsesInMBB.count(&*I))
178      return false;
179  return true;
180}
181#endif
182
183void RegScavenger::forward() {
184  // Move ptr forward.
185  if (!Tracking) {
186    MBBI = MBB->begin();
187    Tracking = true;
188  } else {
189    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
190    MBBI = next(MBBI);
191  }
192
193  MachineInstr *MI = MBBI;
194  DistanceMap.insert(std::make_pair(MI, CurrDist++));
195
196  if (MI == ScavengeRestore) {
197    ScavengedReg = 0;
198    ScavengedRC = NULL;
199    ScavengeRestore = NULL;
200  }
201
202#if 0
203  if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF)
204    return;
205#endif
206
207  // Separate register operands into 3 classes: uses, defs, earlyclobbers.
208  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
209  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
210  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
211  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
212    const MachineOperand &MO = MI->getOperand(i);
213    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
214      continue;
215    if (MO.isUse())
216      UseMOs.push_back(std::make_pair(&MO,i));
217    else if (MO.isEarlyClobber())
218      EarlyClobberMOs.push_back(std::make_pair(&MO,i));
219    else
220      DefMOs.push_back(std::make_pair(&MO,i));
221  }
222
223  // Process uses first.
224  BitVector KillRegs(NumPhysRegs);
225  for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) {
226    const MachineOperand MO = *UseMOs[i].first;
227    unsigned Reg = MO.getReg();
228
229    assert((MO.isImplicit() || isUsed(Reg)) && "Using an undefined register!");
230
231    if (MO.isKill() && !isReserved(Reg)) {
232      KillRegs.set(Reg);
233
234      // Mark sub-registers as used.
235      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
236           unsigned SubReg = *SubRegs; ++SubRegs)
237        KillRegs.set(SubReg);
238    }
239  }
240
241  // Change states of all registers after all the uses are processed to guard
242  // against multiple uses.
243  setUnused(KillRegs);
244
245  // Process early clobber defs then process defs. We can have a early clobber
246  // that is dead, it should not conflict with a def that happens one "slot"
247  // (see InstrSlots in LiveIntervalAnalysis.h) later.
248  unsigned NumECs = EarlyClobberMOs.size();
249  unsigned NumDefs = DefMOs.size();
250
251  for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) {
252    const MachineOperand &MO = (i < NumECs)
253      ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first;
254    unsigned Idx = (i < NumECs)
255      ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second;
256    unsigned Reg = MO.getReg();
257    if (MO.isUndef())
258      continue;
259
260    // If it's dead upon def, then it is now free.
261    if (MO.isDead()) {
262      setUnused(Reg, MI);
263      continue;
264    }
265
266    // Skip two-address destination operand.
267    unsigned UseIdx;
268    if (MI->isRegTiedToUseOperand(Idx, &UseIdx) &&
269        !MI->getOperand(UseIdx).isUndef()) {
270      assert(isUsed(Reg) && "Using an undefined register!");
271      continue;
272    }
273
274    // Skip if this is merely redefining part of a super-register.
275    if (RedefinesSuperRegPart(MI, MO, TRI))
276      continue;
277
278    // Implicit def is allowed to "re-define" any register. Similarly,
279    // implicitly defined registers can be clobbered.
280    assert((MO.isImplicit() || isReserved(Reg) || isUnused(Reg) ||
281            isSuperRegUsed(Reg) ||
282            isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
283           "Re-defining a live register!");
284    setUsed(Reg);
285  }
286}
287
288void RegScavenger::backward() {
289  assert(Tracking && "Not tracking states!");
290  assert(MBBI != MBB->begin() && "Already at start of basic block!");
291  // Move ptr backward.
292  MBBI = prior(MBBI);
293
294  MachineInstr *MI = MBBI;
295  DistanceMap.erase(MI);
296  --CurrDist;
297
298  // Separate register operands into 3 classes: uses, defs, earlyclobbers.
299  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
300  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
301  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
302  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
303    const MachineOperand &MO = MI->getOperand(i);
304    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
305      continue;
306    if (MO.isUse())
307      UseMOs.push_back(std::make_pair(&MO,i));
308    else if (MO.isEarlyClobber())
309      EarlyClobberMOs.push_back(std::make_pair(&MO,i));
310    else
311      DefMOs.push_back(std::make_pair(&MO,i));
312  }
313
314
315  // Process defs first.
316  unsigned NumECs = EarlyClobberMOs.size();
317  unsigned NumDefs = DefMOs.size();
318  for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) {
319    const MachineOperand &MO = (i < NumDefs)
320      ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first;
321    unsigned Idx = (i < NumECs)
322      ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second;
323    if (MO.isUndef())
324      continue;
325
326    // Skip two-address destination operand.
327    if (MI->isRegTiedToUseOperand(Idx))
328      continue;
329
330    unsigned Reg = MO.getReg();
331    assert(isUsed(Reg));
332    if (!isReserved(Reg))
333      setUnused(Reg, MI);
334  }
335
336  // Process uses.
337  BitVector UseRegs(NumPhysRegs);
338  for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) {
339    const MachineOperand MO = *UseMOs[i].first;
340    unsigned Reg = MO.getReg();
341    assert(isUnused(Reg) || isReserved(Reg));
342    UseRegs.set(Reg);
343
344    // Set the sub-registers as "used".
345    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
346         unsigned SubReg = *SubRegs; ++SubRegs)
347      UseRegs.set(SubReg);
348  }
349  setUsed(UseRegs);
350}
351
352void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
353  if (includeReserved)
354    used = ~RegsAvailable;
355  else
356    used = ~RegsAvailable & ~ReservedRegs;
357}
358
359/// CreateRegClassMask - Set the bits that represent the registers in the
360/// TargetRegisterClass.
361static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
362  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
363       ++I)
364    Mask.set(*I);
365}
366
367unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
368                                     const BitVector &Candidates) const {
369  // Mask off the registers which are not in the TargetRegisterClass.
370  BitVector RegsAvailableCopy(NumPhysRegs, false);
371  CreateRegClassMask(RegClass, RegsAvailableCopy);
372  RegsAvailableCopy &= RegsAvailable;
373
374  // Restrict the search to candidates.
375  RegsAvailableCopy &= Candidates;
376
377  // Returns the first unused (bit is set) register, or 0 is none is found.
378  int Reg = RegsAvailableCopy.find_first();
379  return (Reg == -1) ? 0 : Reg;
380}
381
382unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
383                                     bool ExCalleeSaved) const {
384  // Mask off the registers which are not in the TargetRegisterClass.
385  BitVector RegsAvailableCopy(NumPhysRegs, false);
386  CreateRegClassMask(RegClass, RegsAvailableCopy);
387  RegsAvailableCopy &= RegsAvailable;
388
389  // If looking for a non-callee-saved register, mask off all the callee-saved
390  // registers.
391  if (ExCalleeSaved)
392    RegsAvailableCopy &= ~CalleeSavedRegs;
393
394  // Returns the first unused (bit is set) register, or 0 is none is found.
395  int Reg = RegsAvailableCopy.find_first();
396  return (Reg == -1) ? 0 : Reg;
397}
398
399/// findFirstUse - Calculate the distance to the first use of the
400/// specified register.
401MachineInstr*
402RegScavenger::findFirstUse(MachineBasicBlock *MBB,
403                           MachineBasicBlock::iterator I, unsigned Reg,
404                           unsigned &Dist) {
405  MachineInstr *UseMI = 0;
406  Dist = ~0U;
407  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
408         RE = MRI->reg_end(); RI != RE; ++RI) {
409    MachineInstr *UDMI = &*RI;
410    if (UDMI->getParent() != MBB)
411      continue;
412    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
413    if (DI == DistanceMap.end()) {
414      // If it's not in map, it's below current MI, let's initialize the
415      // map.
416      I = next(I);
417      unsigned Dist = CurrDist + 1;
418      while (I != MBB->end()) {
419        DistanceMap.insert(std::make_pair(I, Dist++));
420        I = next(I);
421      }
422    }
423    DI = DistanceMap.find(UDMI);
424    if (DI->second > CurrDist && DI->second < Dist) {
425      Dist = DI->second;
426      UseMI = UDMI;
427    }
428  }
429  return UseMI;
430}
431
432unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
433                                        MachineBasicBlock::iterator I,
434                                        int SPAdj) {
435  assert(ScavengingFrameIndex >= 0 &&
436         "Cannot scavenge a register without an emergency spill slot!");
437
438  // Mask off the registers which are not in the TargetRegisterClass.
439  BitVector Candidates(NumPhysRegs, false);
440  CreateRegClassMask(RC, Candidates);
441  Candidates ^= ReservedRegs & Candidates; // Do not include reserved registers.
442
443  // Exclude all the registers being used by the instruction.
444  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
445    MachineOperand &MO = I->getOperand(i);
446    if (MO.isReg())
447      Candidates.reset(MO.getReg());
448  }
449
450  // Find the register whose use is furthest away.
451  unsigned SReg = 0;
452  unsigned MaxDist = 0;
453  MachineInstr *MaxUseMI = 0;
454  int Reg = Candidates.find_first();
455  while (Reg != -1) {
456    unsigned Dist;
457    MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
458    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
459      unsigned AsDist;
460      MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
461      if (AsDist < Dist) {
462        Dist = AsDist;
463        UseMI = AsUseMI;
464      }
465    }
466    if (Dist >= MaxDist) {
467      MaxDist = Dist;
468      MaxUseMI = UseMI;
469      SReg = Reg;
470    }
471    Reg = Candidates.find_next(Reg);
472  }
473
474  assert(ScavengedReg == 0 &&
475         "Scavenger slot is live, unable to scavenge another register!");
476
477  // Make sure SReg is marked as used. It could be considered available if it is
478  // one of the callee saved registers, but hasn't been spilled.
479  if (!isUsed(SReg)) {
480    MBB->addLiveIn(SReg);
481    setUsed(SReg);
482  }
483
484  // Spill the scavenged register before I.
485  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
486  MachineBasicBlock::iterator II = prior(I);
487  TRI->eliminateFrameIndex(II, SPAdj, this);
488
489  // Restore the scavenged register before its use (or first terminator).
490  II = MaxUseMI
491    ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
492  TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
493  ScavengeRestore = prior(II);
494  ScavengedReg = SReg;
495  ScavengedRC = RC;
496
497  return SReg;
498}
499