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