RegisterScavenging.cpp revision 5d3600f5766e93cb459ef6108fba00c052aa6388 
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/Target/TargetRegisterInfo.h"
24#include "llvm/Target/TargetInstrInfo.h"
25#include "llvm/Target/TargetMachine.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/STLExtras.h"
28using namespace llvm;
29
30/// RedefinesSuperRegPart - Return true if the specified register is redefining
31/// part of a super-register.
32static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
33                                  const TargetRegisterInfo *TRI) {
34  bool SeenSuperUse = false;
35  bool SeenSuperDef = false;
36  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
37    const MachineOperand &MO = MI->getOperand(i);
38    if (!MO.isRegister())
39      continue;
40    if (TRI->isSuperRegister(SubReg, MO.getReg()))
41      if (MO.isUse())
42        SeenSuperUse = true;
43      else if (MO.isImplicit())
44        SeenSuperDef = true;
45  }
46
47  return SeenSuperDef && SeenSuperUse;
48}
49
50static bool RedefinesSuperRegPart(const MachineInstr *MI,
51                                  const MachineOperand &MO,
52                                  const TargetRegisterInfo *TRI) {
53  assert(MO.isRegister() && MO.isDef() && "Not a register def!");
54  return RedefinesSuperRegPart(MI, MO.getReg(), TRI);
55}
56
57/// setUsed - Set the register and its sub-registers as being used.
58void RegScavenger::setUsed(unsigned Reg, bool ImpDef) {
59  RegsAvailable.reset(Reg);
60  ImplicitDefed[Reg] = ImpDef;
61
62  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
63       unsigned SubReg = *SubRegs; ++SubRegs) {
64    RegsAvailable.reset(SubReg);
65    ImplicitDefed[SubReg] = ImpDef;
66  }
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  ImplicitDefed.reset(Reg);
73
74  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
75       unsigned SubReg = *SubRegs; ++SubRegs)
76    if (!RedefinesSuperRegPart(MI, Reg, TRI)) {
77      RegsAvailable.set(SubReg);
78      ImplicitDefed.reset(SubReg);
79    }
80}
81
82void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
83  const MachineFunction &MF = *mbb->getParent();
84  const TargetMachine &TM = MF.getTarget();
85  TII = TM.getInstrInfo();
86  TRI = TM.getRegisterInfo();
87  MRI = &MF.getRegInfo();
88
89  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
90         "Target changed?");
91
92  if (!MBB) {
93    NumPhysRegs = TRI->getNumRegs();
94    RegsAvailable.resize(NumPhysRegs);
95    ImplicitDefed.resize(NumPhysRegs);
96
97    // Create reserved registers bitvector.
98    ReservedRegs = TRI->getReservedRegs(MF);
99
100    // Create callee-saved registers bitvector.
101    CalleeSavedRegs.resize(NumPhysRegs);
102    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
103    if (CSRegs != NULL)
104      for (unsigned i = 0; CSRegs[i]; ++i)
105        CalleeSavedRegs.set(CSRegs[i]);
106  }
107
108  MBB = mbb;
109  ScavengedReg = 0;
110  ScavengedRC = NULL;
111
112  // All registers started out unused.
113  RegsAvailable.set();
114
115  // Reserved registers are always used.
116  RegsAvailable ^= ReservedRegs;
117
118  // Live-in registers are in use.
119  if (!MBB->livein_empty())
120    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
121           E = MBB->livein_end(); I != E; ++I)
122      setUsed(*I);
123
124  Tracking = false;
125}
126
127void RegScavenger::restoreScavengedReg() {
128  if (!ScavengedReg)
129    return;
130
131  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
132                            ScavengingFrameIndex, ScavengedRC);
133  MachineBasicBlock::iterator II = prior(MBBI);
134  TRI->eliminateFrameIndex(II, 0, this);
135  setUsed(ScavengedReg);
136  ScavengedReg = 0;
137  ScavengedRC = NULL;
138}
139
140/// isLiveInButUnusedBefore - Return true if register is livein the MBB not
141/// not used before it reaches the MI that defines register.
142static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
143                                    MachineBasicBlock *MBB,
144                                    const TargetRegisterInfo *TRI,
145                                    MachineRegisterInfo* MRI) {
146  // First check if register is livein.
147  bool isLiveIn = false;
148  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
149         E = MBB->livein_end(); I != E; ++I)
150    if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
151      isLiveIn = true;
152      break;
153    }
154  if (!isLiveIn)
155    return false;
156
157  // Is there any use of it before the specified MI?
158  SmallPtrSet<MachineInstr*, 4> UsesInMBB;
159  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
160         UE = MRI->use_end(); UI != UE; ++UI) {
161    MachineInstr *UseMI = &*UI;
162    if (UseMI->getParent() == MBB)
163      UsesInMBB.insert(UseMI);
164  }
165  if (UsesInMBB.empty())
166    return true;
167
168  for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
169    if (UsesInMBB.count(&*I))
170      return false;
171  return true;
172}
173
174void RegScavenger::forward() {
175  // Move ptr forward.
176  if (!Tracking) {
177    MBBI = MBB->begin();
178    Tracking = true;
179  } else {
180    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
181    MBBI = next(MBBI);
182  }
183
184  MachineInstr *MI = MBBI;
185  const TargetInstrDesc &TID = MI->getDesc();
186
187  // Reaching a terminator instruction. Restore a scavenged register (which
188  // must be life out.
189  if (TID.isTerminator())
190    restoreScavengedReg();
191
192  // Process uses first.
193  BitVector ChangedRegs(NumPhysRegs);
194  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
195    const MachineOperand &MO = MI->getOperand(i);
196    if (!MO.isRegister() || !MO.isUse())
197      continue;
198
199    unsigned Reg = MO.getReg();
200    if (Reg == 0) continue;
201
202    if (!isUsed(Reg)) {
203      // Register has been scavenged. Restore it!
204      if (Reg != ScavengedReg)
205        assert(false && "Using an undefined register!");
206      else
207        restoreScavengedReg();
208    }
209
210    if (MO.isKill() && !isReserved(Reg)) {
211      ChangedRegs.set(Reg);
212
213      // Mark sub-registers as changed if they aren't defined in the same
214      // instruction.
215      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
216           unsigned SubReg = *SubRegs; ++SubRegs)
217        ChangedRegs.set(SubReg);
218    }
219  }
220
221  // Change states of all registers after all the uses are processed to guard
222  // against multiple uses.
223  setUnused(ChangedRegs);
224
225  // Process defs.
226  bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF;
227  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
228    const MachineOperand &MO = MI->getOperand(i);
229
230    if (!MO.isRegister() || !MO.isDef())
231      continue;
232
233    unsigned Reg = MO.getReg();
234
235    // If it's dead upon def, then it is now free.
236    if (MO.isDead()) {
237      setUnused(Reg, MI);
238      continue;
239    }
240
241    // Skip two-address destination operand.
242    if (TID.findTiedToSrcOperand(i) != -1) {
243      assert(isUsed(Reg) && "Using an undefined register!");
244      continue;
245    }
246
247    // Skip is this is merely redefining part of a super-register.
248    if (RedefinesSuperRegPart(MI, MO, TRI))
249      continue;
250
251    // Implicit def is allowed to "re-define" any register. Similarly,
252    // implicitly defined registers can be clobbered.
253    assert((isReserved(Reg) || isUnused(Reg) ||
254            IsImpDef || isImplicitlyDefined(Reg) ||
255            isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
256           "Re-defining a live register!");
257    setUsed(Reg, IsImpDef);
258  }
259}
260
261void RegScavenger::backward() {
262  assert(Tracking && "Not tracking states!");
263  assert(MBBI != MBB->begin() && "Already at start of basic block!");
264  // Move ptr backward.
265  MBBI = prior(MBBI);
266
267  MachineInstr *MI = MBBI;
268  // Process defs first.
269  const TargetInstrDesc &TID = MI->getDesc();
270  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
271    const MachineOperand &MO = MI->getOperand(i);
272    if (!MO.isRegister() || !MO.isDef())
273      continue;
274    // Skip two-address destination operand.
275    if (TID.findTiedToSrcOperand(i) != -1)
276      continue;
277    unsigned Reg = MO.getReg();
278    assert(isUsed(Reg));
279    if (!isReserved(Reg))
280      setUnused(Reg, MI);
281  }
282
283  // Process uses.
284  BitVector ChangedRegs(NumPhysRegs);
285  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
286    const MachineOperand &MO = MI->getOperand(i);
287    if (!MO.isRegister() || !MO.isUse())
288      continue;
289    unsigned Reg = MO.getReg();
290    if (Reg == 0)
291      continue;
292    assert(isUnused(Reg) || isReserved(Reg));
293    ChangedRegs.set(Reg);
294
295    // Set the sub-registers as "used".
296    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
297         unsigned SubReg = *SubRegs; ++SubRegs)
298      ChangedRegs.set(SubReg);
299  }
300  setUsed(ChangedRegs);
301}
302
303void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
304  if (includeReserved)
305    used = ~RegsAvailable;
306  else
307    used = ~RegsAvailable & ~ReservedRegs;
308}
309
310/// CreateRegClassMask - Set the bits that represent the registers in the
311/// TargetRegisterClass.
312static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
313  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
314       ++I)
315    Mask.set(*I);
316}
317
318unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
319                                     const BitVector &Candidates) const {
320  // Mask off the registers which are not in the TargetRegisterClass.
321  BitVector RegsAvailableCopy(NumPhysRegs, false);
322  CreateRegClassMask(RegClass, RegsAvailableCopy);
323  RegsAvailableCopy &= RegsAvailable;
324
325  // Restrict the search to candidates.
326  RegsAvailableCopy &= Candidates;
327
328  // Returns the first unused (bit is set) register, or 0 is none is found.
329  int Reg = RegsAvailableCopy.find_first();
330  return (Reg == -1) ? 0 : Reg;
331}
332
333unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
334                                     bool ExCalleeSaved) const {
335  // Mask off the registers which are not in the TargetRegisterClass.
336  BitVector RegsAvailableCopy(NumPhysRegs, false);
337  CreateRegClassMask(RegClass, RegsAvailableCopy);
338  RegsAvailableCopy &= RegsAvailable;
339
340  // If looking for a non-callee-saved register, mask off all the callee-saved
341  // registers.
342  if (ExCalleeSaved)
343    RegsAvailableCopy &= ~CalleeSavedRegs;
344
345  // Returns the first unused (bit is set) register, or 0 is none is found.
346  int Reg = RegsAvailableCopy.find_first();
347  return (Reg == -1) ? 0 : Reg;
348}
349
350/// calcDistanceToUse - Calculate the distance to the first use of the
351/// specified register.
352static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
353                                  MachineBasicBlock::iterator I, unsigned Reg,
354                                  const TargetRegisterInfo *TRI) {
355  unsigned Dist = 0;
356  I = next(I);
357  while (I != MBB->end()) {
358    Dist++;
359    if (I->readsRegister(Reg, TRI))
360        return Dist;
361    I = next(I);
362  }
363  return Dist + 1;
364}
365
366unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
367                                        MachineBasicBlock::iterator I,
368                                        int SPAdj) {
369  assert(ScavengingFrameIndex >= 0 &&
370         "Cannot scavenge a register without an emergency spill slot!");
371
372  // Mask off the registers which are not in the TargetRegisterClass.
373  BitVector Candidates(NumPhysRegs, false);
374  CreateRegClassMask(RC, Candidates);
375  Candidates ^= ReservedRegs;  // Do not include reserved registers.
376
377  // Exclude all the registers being used by the instruction.
378  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
379    MachineOperand &MO = I->getOperand(i);
380    if (MO.isRegister())
381      Candidates.reset(MO.getReg());
382  }
383
384  // Find the register whose use is furthest away.
385  unsigned SReg = 0;
386  unsigned MaxDist = 0;
387  int Reg = Candidates.find_first();
388  while (Reg != -1) {
389    unsigned Dist = calcDistanceToUse(MBB, I, Reg, TRI);
390    if (Dist >= MaxDist) {
391      MaxDist = Dist;
392      SReg = Reg;
393    }
394    Reg = Candidates.find_next(Reg);
395  }
396
397  if (ScavengedReg != 0) {
398    // First restore previously scavenged register.
399    TII->loadRegFromStackSlot(*MBB, I, ScavengedReg,
400                              ScavengingFrameIndex, ScavengedRC);
401    MachineBasicBlock::iterator II = prior(I);
402    TRI->eliminateFrameIndex(II, SPAdj, this);
403  }
404
405  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
406  MachineBasicBlock::iterator II = prior(I);
407  TRI->eliminateFrameIndex(II, SPAdj, this);
408  ScavengedReg = SReg;
409  ScavengedRC = RC;
410
411  return SReg;
412}
413