RegisterScavenging.cpp revision d68f47c6fd744e051f7f2d97b6366d40bf27c438 
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/Target/TargetRegisterInfo.h"
23#include "llvm/Target/TargetInstrInfo.h"
24#include "llvm/Target/TargetMachine.h"
25#include "llvm/ADT/STLExtras.h"
26using namespace llvm;
27
28/// RedefinesSuperRegPart - Return true if the specified register is redefining
29/// part of a super-register.
30static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
31                                  const TargetRegisterInfo *TRI) {
32  bool SeenSuperUse = false;
33  bool SeenSuperDef = false;
34  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
35    const MachineOperand &MO = MI->getOperand(i);
36    if (!MO.isRegister())
37      continue;
38    if (TRI->isSuperRegister(SubReg, MO.getReg()))
39      if (MO.isUse())
40        SeenSuperUse = true;
41      else if (MO.isImplicit())
42        SeenSuperDef = true;
43  }
44
45  return SeenSuperDef && SeenSuperUse;
46}
47
48static bool RedefinesSuperRegPart(const MachineInstr *MI,
49                                  const MachineOperand &MO,
50                                  const TargetRegisterInfo *TRI) {
51  assert(MO.isRegister() && MO.isDef() && "Not a register def!");
52  return RedefinesSuperRegPart(MI, MO.getReg(), TRI);
53}
54
55/// setUsed - Set the register and its sub-registers as being used.
56void RegScavenger::setUsed(unsigned Reg) {
57  RegsAvailable.reset(Reg);
58
59  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
60       unsigned SubReg = *SubRegs; ++SubRegs)
61    RegsAvailable.reset(SubReg);
62}
63
64/// setUnused - Set the register and its sub-registers as being unused.
65void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
66  RegsAvailable.set(Reg);
67
68  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
69       unsigned SubReg = *SubRegs; ++SubRegs)
70    if (!RedefinesSuperRegPart(MI, Reg, TRI))
71      RegsAvailable.set(SubReg);
72}
73
74void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
75  const MachineFunction &MF = *mbb->getParent();
76  const TargetMachine &TM = MF.getTarget();
77  TII = TM.getInstrInfo();
78  TRI = TM.getRegisterInfo();
79
80  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
81         "Target changed?");
82
83  if (!MBB) {
84    NumPhysRegs = TRI->getNumRegs();
85    RegsAvailable.resize(NumPhysRegs);
86
87    // Create reserved registers bitvector.
88    ReservedRegs = TRI->getReservedRegs(MF);
89
90    // Create callee-saved registers bitvector.
91    CalleeSavedRegs.resize(NumPhysRegs);
92    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
93    if (CSRegs != NULL)
94      for (unsigned i = 0; CSRegs[i]; ++i)
95        CalleeSavedRegs.set(CSRegs[i]);
96  }
97
98  MBB = mbb;
99  ScavengedReg = 0;
100  ScavengedRC = NULL;
101
102  // All registers started out unused.
103  RegsAvailable.set();
104
105  // Reserved registers are always used.
106  RegsAvailable ^= ReservedRegs;
107
108  // Live-in registers are in use.
109  if (!MBB->livein_empty())
110    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
111           E = MBB->livein_end(); I != E; ++I)
112      setUsed(*I);
113
114  Tracking = false;
115}
116
117void RegScavenger::restoreScavengedReg() {
118  if (!ScavengedReg)
119    return;
120
121  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
122                                ScavengingFrameIndex, ScavengedRC);
123  MachineBasicBlock::iterator II = prior(MBBI);
124  TRI->eliminateFrameIndex(II, 0, this);
125  setUsed(ScavengedReg);
126  ScavengedReg = 0;
127  ScavengedRC = NULL;
128}
129
130void RegScavenger::forward() {
131  // Move ptr forward.
132  if (!Tracking) {
133    MBBI = MBB->begin();
134    Tracking = true;
135  } else {
136    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
137    MBBI = next(MBBI);
138  }
139
140  MachineInstr *MI = MBBI;
141  const TargetInstrDesc &TID = MI->getDesc();
142
143  // Reaching a terminator instruction. Restore a scavenged register (which
144  // must be life out.
145  if (TID.isTerminator())
146    restoreScavengedReg();
147
148  // Process uses first.
149  BitVector ChangedRegs(NumPhysRegs);
150  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
151    const MachineOperand &MO = MI->getOperand(i);
152    if (!MO.isRegister() || !MO.isUse())
153      continue;
154
155    unsigned Reg = MO.getReg();
156    if (Reg == 0) continue;
157
158    if (!isUsed(Reg)) {
159      // Register has been scavenged. Restore it!
160      if (Reg != ScavengedReg)
161        assert(false && "Using an undefined register!");
162      else
163        restoreScavengedReg();
164    }
165
166    if (MO.isKill() && !isReserved(Reg)) {
167      ChangedRegs.set(Reg);
168
169      // Mark sub-registers as changed if they aren't defined in the same
170      // instruction.
171      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
172           unsigned SubReg = *SubRegs; ++SubRegs)
173        if (!RedefinesSuperRegPart(MI, Reg, TRI))
174          ChangedRegs.set(SubReg);
175    }
176  }
177
178  // Change states of all registers after all the uses are processed to guard
179  // against multiple uses.
180  setUnused(ChangedRegs);
181
182  // Process defs.
183  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
184    const MachineOperand &MO = MI->getOperand(i);
185
186    if (!MO.isRegister() || !MO.isDef())
187      continue;
188
189    unsigned Reg = MO.getReg();
190
191    // If it's dead upon def, then it is now free.
192    if (MO.isDead()) {
193      setUnused(Reg, MI);
194      continue;
195    }
196
197    // Skip two-address destination operand.
198    if (TID.findTiedToSrcOperand(i) != -1) {
199      assert(isUsed(Reg) && "Using an undefined register!");
200      continue;
201    }
202
203    // Skip is this is merely redefining part of a super-register.
204    if (RedefinesSuperRegPart(MI, MO, TRI))
205      continue;
206
207    assert((isUnused(Reg) || isReserved(Reg)) &&
208           "Re-defining a live register!");
209    setUsed(Reg);
210  }
211}
212
213void RegScavenger::backward() {
214  assert(Tracking && "Not tracking states!");
215  assert(MBBI != MBB->begin() && "Already at start of basic block!");
216  // Move ptr backward.
217  MBBI = prior(MBBI);
218
219  MachineInstr *MI = MBBI;
220  // Process defs first.
221  const TargetInstrDesc &TID = MI->getDesc();
222  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
223    const MachineOperand &MO = MI->getOperand(i);
224    if (!MO.isRegister() || !MO.isDef())
225      continue;
226    // Skip two-address destination operand.
227    if (TID.findTiedToSrcOperand(i) != -1)
228      continue;
229    unsigned Reg = MO.getReg();
230    assert(isUsed(Reg));
231    if (!isReserved(Reg))
232      setUnused(Reg, MI);
233  }
234
235  // Process uses.
236  BitVector ChangedRegs(NumPhysRegs);
237  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
238    const MachineOperand &MO = MI->getOperand(i);
239    if (!MO.isRegister() || !MO.isUse())
240      continue;
241    unsigned Reg = MO.getReg();
242    if (Reg == 0)
243      continue;
244    assert(isUnused(Reg) || isReserved(Reg));
245    ChangedRegs.set(Reg);
246
247    // Set the sub-registers as "used".
248    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
249         unsigned SubReg = *SubRegs; ++SubRegs)
250      ChangedRegs.set(SubReg);
251  }
252  setUsed(ChangedRegs);
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/// calcDistanceToUse - Calculate the distance to the first use of the
303/// specified register.
304static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
305                                  MachineBasicBlock::iterator I, unsigned Reg,
306                                  const TargetRegisterInfo *TRI) {
307  unsigned Dist = 0;
308  I = next(I);
309  while (I != MBB->end()) {
310    Dist++;
311    if (I->readsRegister(Reg, TRI))
312        return Dist;
313    I = next(I);
314  }
315  return Dist + 1;
316}
317
318unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
319                                        MachineBasicBlock::iterator I,
320                                        int SPAdj) {
321  assert(ScavengingFrameIndex >= 0 &&
322         "Cannot scavenge a register without an emergency spill slot!");
323
324  // Mask off the registers which are not in the TargetRegisterClass.
325  BitVector Candidates(NumPhysRegs, false);
326  CreateRegClassMask(RC, Candidates);
327  Candidates ^= ReservedRegs;  // Do not include reserved registers.
328
329  // Exclude all the registers being used by the instruction.
330  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
331    MachineOperand &MO = I->getOperand(i);
332    if (MO.isRegister())
333      Candidates.reset(MO.getReg());
334  }
335
336  // Find the register whose use is furthest away.
337  unsigned SReg = 0;
338  unsigned MaxDist = 0;
339  int Reg = Candidates.find_first();
340  while (Reg != -1) {
341    unsigned Dist = calcDistanceToUse(MBB, I, Reg, TRI);
342    if (Dist >= MaxDist) {
343      MaxDist = Dist;
344      SReg = Reg;
345    }
346    Reg = Candidates.find_next(Reg);
347  }
348
349  if (ScavengedReg != 0) {
350    // First restore previously scavenged register.
351    TII->loadRegFromStackSlot(*MBB, I, ScavengedReg,
352                              ScavengingFrameIndex, ScavengedRC);
353    MachineBasicBlock::iterator II = prior(I);
354    TRI->eliminateFrameIndex(II, SPAdj, this);
355  }
356
357  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
358  MachineBasicBlock::iterator II = prior(I);
359  TRI->eliminateFrameIndex(II, SPAdj, this);
360  ScavengedReg = SReg;
361  ScavengedRC = RC;
362
363  return SReg;
364}
365