RegisterScavenging.cpp revision f955cbf56f130cdeb4c6c8aaa4a2715d420c1327 
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(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(!MI->getOperand(UseIdx).isKill() &&
271             "Using an undefined register!");
272      continue;
273    }
274
275    // Skip if this is merely redefining part of a super-register.
276    if (RedefinesSuperRegPart(MI, MO, TRI))
277      continue;
278
279    assert((isReserved(Reg) || isUnused(Reg) || isSuperRegUsed(Reg) ||
280            isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
281           "Re-defining a live register!");
282    setUsed(Reg);
283  }
284}
285
286void RegScavenger::backward() {
287  assert(Tracking && "Not tracking states!");
288  assert(MBBI != MBB->begin() && "Already at start of basic block!");
289  // Move ptr backward.
290  MBBI = prior(MBBI);
291
292  MachineInstr *MI = MBBI;
293  DistanceMap.erase(MI);
294  --CurrDist;
295
296  // Separate register operands into 3 classes: uses, defs, earlyclobbers.
297  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
298  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
299  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
300  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
301    const MachineOperand &MO = MI->getOperand(i);
302    if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef())
303      continue;
304    if (MO.isUse())
305      UseMOs.push_back(std::make_pair(&MO,i));
306    else if (MO.isEarlyClobber())
307      EarlyClobberMOs.push_back(std::make_pair(&MO,i));
308    else
309      DefMOs.push_back(std::make_pair(&MO,i));
310  }
311
312
313  // Process defs first.
314  unsigned NumECs = EarlyClobberMOs.size();
315  unsigned NumDefs = DefMOs.size();
316  for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) {
317    const MachineOperand &MO = (i < NumDefs)
318      ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first;
319    unsigned Idx = (i < NumECs)
320      ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second;
321    if (MO.isUndef())
322      continue;
323
324    // Skip two-address destination operand.
325    if (MI->isRegTiedToUseOperand(Idx))
326      continue;
327
328    unsigned Reg = MO.getReg();
329    assert(isUsed(Reg));
330    if (!isReserved(Reg))
331      setUnused(Reg, MI);
332  }
333
334  // Process uses.
335  BitVector UseRegs(NumPhysRegs);
336  for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) {
337    const MachineOperand MO = *UseMOs[i].first;
338    unsigned Reg = MO.getReg();
339    assert(isUnused(Reg) || isReserved(Reg));
340    UseRegs.set(Reg);
341
342    // Set the sub-registers as "used".
343    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
344         unsigned SubReg = *SubRegs; ++SubRegs)
345      UseRegs.set(SubReg);
346  }
347  setUsed(UseRegs);
348}
349
350void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
351  if (includeReserved)
352    used = ~RegsAvailable;
353  else
354    used = ~RegsAvailable & ~ReservedRegs;
355}
356
357/// CreateRegClassMask - Set the bits that represent the registers in the
358/// TargetRegisterClass.
359static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
360  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
361       ++I)
362    Mask.set(*I);
363}
364
365unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
366                                     const BitVector &Candidates) const {
367  // Mask off the registers which are not in the TargetRegisterClass.
368  BitVector RegsAvailableCopy(NumPhysRegs, false);
369  CreateRegClassMask(RegClass, RegsAvailableCopy);
370  RegsAvailableCopy &= RegsAvailable;
371
372  // Restrict the search to candidates.
373  RegsAvailableCopy &= Candidates;
374
375  // Returns the first unused (bit is set) register, or 0 is none is found.
376  int Reg = RegsAvailableCopy.find_first();
377  return (Reg == -1) ? 0 : Reg;
378}
379
380unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
381                                     bool ExCalleeSaved) const {
382  // Mask off the registers which are not in the TargetRegisterClass.
383  BitVector RegsAvailableCopy(NumPhysRegs, false);
384  CreateRegClassMask(RegClass, RegsAvailableCopy);
385  RegsAvailableCopy &= RegsAvailable;
386
387  // If looking for a non-callee-saved register, mask off all the callee-saved
388  // registers.
389  if (ExCalleeSaved)
390    RegsAvailableCopy &= ~CalleeSavedRegs;
391
392  // Returns the first unused (bit is set) register, or 0 is none is found.
393  int Reg = RegsAvailableCopy.find_first();
394  return (Reg == -1) ? 0 : Reg;
395}
396
397/// findFirstUse - Calculate the distance to the first use of the
398/// specified register.
399MachineInstr*
400RegScavenger::findFirstUse(MachineBasicBlock *MBB,
401                           MachineBasicBlock::iterator I, unsigned Reg,
402                           unsigned &Dist) {
403  MachineInstr *UseMI = 0;
404  Dist = ~0U;
405  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
406         RE = MRI->reg_end(); RI != RE; ++RI) {
407    MachineInstr *UDMI = &*RI;
408    if (UDMI->getParent() != MBB)
409      continue;
410    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
411    if (DI == DistanceMap.end()) {
412      // If it's not in map, it's below current MI, let's initialize the
413      // map.
414      I = next(I);
415      unsigned Dist = CurrDist + 1;
416      while (I != MBB->end()) {
417        DistanceMap.insert(std::make_pair(I, Dist++));
418        I = next(I);
419      }
420    }
421    DI = DistanceMap.find(UDMI);
422    if (DI->second > CurrDist && DI->second < Dist) {
423      Dist = DI->second;
424      UseMI = UDMI;
425    }
426  }
427  return UseMI;
428}
429
430unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
431                                        MachineBasicBlock::iterator I,
432                                        int SPAdj) {
433  assert(ScavengingFrameIndex >= 0 &&
434         "Cannot scavenge a register without an emergency spill slot!");
435
436  // Mask off the registers which are not in the TargetRegisterClass.
437  BitVector Candidates(NumPhysRegs, false);
438  CreateRegClassMask(RC, Candidates);
439  Candidates ^= ReservedRegs & Candidates; // Do not include reserved registers.
440
441  // Exclude all the registers being used by the instruction.
442  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
443    MachineOperand &MO = I->getOperand(i);
444    if (MO.isReg())
445      Candidates.reset(MO.getReg());
446  }
447
448  // Find the register whose use is furthest away.
449  unsigned SReg = 0;
450  unsigned MaxDist = 0;
451  MachineInstr *MaxUseMI = 0;
452  int Reg = Candidates.find_first();
453  while (Reg != -1) {
454    unsigned Dist;
455    MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
456    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
457      unsigned AsDist;
458      MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
459      if (AsDist < Dist) {
460        Dist = AsDist;
461        UseMI = AsUseMI;
462      }
463    }
464    if (Dist >= MaxDist) {
465      MaxDist = Dist;
466      MaxUseMI = UseMI;
467      SReg = Reg;
468    }
469    Reg = Candidates.find_next(Reg);
470  }
471
472  assert(ScavengedReg == 0 &&
473         "Scavenger slot is live, unable to scavenge another register!");
474
475  // Make sure SReg is marked as used. It could be considered available if it is
476  // one of the callee saved registers, but hasn't been spilled.
477  if (!isUsed(SReg)) {
478    MBB->addLiveIn(SReg);
479    setUsed(SReg);
480  }
481
482  // Spill the scavenged register before I.
483  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
484  MachineBasicBlock::iterator II = prior(I);
485  TRI->eliminateFrameIndex(II, SPAdj, this);
486
487  // Restore the scavenged register before its use (or first terminator).
488  II = MaxUseMI
489    ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
490  TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
491  ScavengeRestore = prior(II);
492  ScavengedReg = SReg;
493  ScavengedRC = RC;
494
495  return SReg;
496}
497