RegisterScavenging.cpp revision a0a570cec647b860a724f4f70a191bc83cdcc947 
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 register at any point in a machine basic block.
12// It also provides a mechanism to make registers availbale by evicting them
13// to 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/// setUsed - Set the register and its sub-registers as being used.
29void RegScavenger::setUsed(unsigned Reg) {
30  RegsAvailable.reset(Reg);
31
32  for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
33       unsigned SubReg = *SubRegs; ++SubRegs)
34    RegsAvailable.reset(SubReg);
35}
36
37/// setUnused - Set the register and its sub-registers as being unused.
38void RegScavenger::setUnused(unsigned Reg) {
39  RegsAvailable.set(Reg);
40
41  for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
42       unsigned SubReg = *SubRegs; ++SubRegs)
43    RegsAvailable.set(SubReg);
44}
45
46void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
47  const MachineFunction &MF = *mbb->getParent();
48  const TargetMachine &TM = MF.getTarget();
49  TII = TM.getInstrInfo();
50  RegInfo = TM.getRegisterInfo();
51
52  assert((NumPhysRegs == 0 || NumPhysRegs == RegInfo->getNumRegs()) &&
53         "Target changed?");
54
55  if (!MBB) {
56    NumPhysRegs = RegInfo->getNumRegs();
57    RegsAvailable.resize(NumPhysRegs);
58
59    // Create reserved registers bitvector.
60    ReservedRegs = RegInfo->getReservedRegs(MF);
61
62    // Create callee-saved registers bitvector.
63    CalleeSavedRegs.resize(NumPhysRegs);
64    const unsigned *CSRegs = RegInfo->getCalleeSavedRegs();
65    if (CSRegs != NULL)
66      for (unsigned i = 0; CSRegs[i]; ++i)
67        CalleeSavedRegs.set(CSRegs[i]);
68  }
69
70  MBB = mbb;
71  ScavengedReg = 0;
72  ScavengedRC = NULL;
73
74  // All registers started out unused.
75  RegsAvailable.set();
76
77  // Reserved registers are always used.
78  RegsAvailable ^= ReservedRegs;
79
80  // Live-in registers are in use.
81  if (!MBB->livein_empty())
82    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
83           E = MBB->livein_end(); I != E; ++I)
84      setUsed(*I);
85
86  Tracking = false;
87}
88
89void RegScavenger::restoreScavengedReg() {
90  if (!ScavengedReg)
91    return;
92
93  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
94                                ScavengingFrameIndex, ScavengedRC);
95  MachineBasicBlock::iterator II = prior(MBBI);
96  RegInfo->eliminateFrameIndex(II, 0, this);
97  setUsed(ScavengedReg);
98  ScavengedReg = 0;
99  ScavengedRC = NULL;
100}
101
102void RegScavenger::forward() {
103  // Move ptr forward.
104  if (!Tracking) {
105    MBBI = MBB->begin();
106    Tracking = true;
107  } else {
108    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
109    MBBI = next(MBBI);
110  }
111
112  MachineInstr *MI = MBBI;
113  const TargetInstrDesc &TID = MI->getDesc();
114
115  // Reaching a terminator instruction. Restore a scavenged register (which
116  // must be life out.
117  if (TID.isTerminator())
118    restoreScavengedReg();
119
120  // Process uses first.
121  BitVector ChangedRegs(NumPhysRegs);
122  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
123    const MachineOperand &MO = MI->getOperand(i);
124    if (!MO.isRegister() || !MO.isUse())
125      continue;
126
127    unsigned Reg = MO.getReg();
128    if (Reg == 0) continue;
129
130    if (!isUsed(Reg)) {
131      // Register has been scavenged. Restore it!
132      if (Reg != ScavengedReg)
133        assert(false && "Using an undefined register!");
134      else
135        restoreScavengedReg();
136    }
137
138    if (MO.isKill() && !isReserved(Reg)) {
139      ChangedRegs.set(Reg);
140
141      for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
142           unsigned SubReg = *SubRegs; ++SubRegs)
143        ChangedRegs.set(SubReg);
144    }
145  }
146
147  // Change states of all registers after all the uses are processed to guard
148  // against multiple uses.
149  setUnused(ChangedRegs);
150
151  // Process defs.
152  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
153    const MachineOperand &MO = MI->getOperand(i);
154
155    if (!MO.isRegister() || !MO.isDef())
156      continue;
157
158    unsigned Reg = MO.getReg();
159
160    // If it's dead upon def, then it is now free.
161    if (MO.isDead()) {
162      setUnused(Reg);
163      continue;
164    }
165
166    // Skip two-address destination operand.
167    if (TID.findTiedToSrcOperand(i) != -1) {
168      assert(isUsed(Reg) && "Using an undefined register!");
169      continue;
170    }
171
172    assert((isUnused(Reg) || isReserved(Reg)) &&
173           "Re-defining a live register!");
174    setUsed(Reg);
175  }
176}
177
178void RegScavenger::backward() {
179  assert(Tracking && "Not tracking states!");
180  assert(MBBI != MBB->begin() && "Already at start of basic block!");
181  // Move ptr backward.
182  MBBI = prior(MBBI);
183
184  MachineInstr *MI = MBBI;
185  // Process defs first.
186  const TargetInstrDesc &TID = MI->getDesc();
187  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
188    const MachineOperand &MO = MI->getOperand(i);
189    if (!MO.isRegister() || !MO.isDef())
190      continue;
191    // Skip two-address destination operand.
192    if (TID.findTiedToSrcOperand(i) != -1)
193      continue;
194    unsigned Reg = MO.getReg();
195    assert(isUsed(Reg));
196    if (!isReserved(Reg))
197      setUnused(Reg);
198  }
199
200  // Process uses.
201  BitVector ChangedRegs(NumPhysRegs);
202  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
203    const MachineOperand &MO = MI->getOperand(i);
204    if (!MO.isRegister() || !MO.isUse())
205      continue;
206    unsigned Reg = MO.getReg();
207    if (Reg == 0)
208      continue;
209    assert(isUnused(Reg) || isReserved(Reg));
210    ChangedRegs.set(Reg);
211
212    // Set the sub-registers as "used".
213    for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg);
214         unsigned SubReg = *SubRegs; ++SubRegs)
215      ChangedRegs.set(SubReg);
216  }
217  setUsed(ChangedRegs);
218}
219
220void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
221  if (includeReserved)
222    used = ~RegsAvailable;
223  else
224    used = ~RegsAvailable & ~ReservedRegs;
225}
226
227/// CreateRegClassMask - Set the bits that represent the registers in the
228/// TargetRegisterClass.
229static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
230  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
231       ++I)
232    Mask.set(*I);
233}
234
235unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
236                                     const BitVector &Candidates) const {
237  // Mask off the registers which are not in the TargetRegisterClass.
238  BitVector RegsAvailableCopy(NumPhysRegs, false);
239  CreateRegClassMask(RegClass, RegsAvailableCopy);
240  RegsAvailableCopy &= RegsAvailable;
241
242  // Restrict the search to candidates.
243  RegsAvailableCopy &= Candidates;
244
245  // Returns the first unused (bit is set) register, or 0 is none is found.
246  int Reg = RegsAvailableCopy.find_first();
247  return (Reg == -1) ? 0 : Reg;
248}
249
250unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
251                                     bool ExCalleeSaved) const {
252  // Mask off the registers which are not in the TargetRegisterClass.
253  BitVector RegsAvailableCopy(NumPhysRegs, false);
254  CreateRegClassMask(RegClass, RegsAvailableCopy);
255  RegsAvailableCopy &= RegsAvailable;
256
257  // If looking for a non-callee-saved register, mask off all the callee-saved
258  // registers.
259  if (ExCalleeSaved)
260    RegsAvailableCopy &= ~CalleeSavedRegs;
261
262  // Returns the first unused (bit is set) register, or 0 is none is found.
263  int Reg = RegsAvailableCopy.find_first();
264  return (Reg == -1) ? 0 : Reg;
265}
266
267/// calcDistanceToUse - Calculate the distance to the first use of the
268/// specified register.
269static unsigned calcDistanceToUse(MachineBasicBlock *MBB,
270                                  MachineBasicBlock::iterator I, unsigned Reg) {
271  unsigned Dist = 0;
272  I = next(I);
273  while (I != MBB->end()) {
274    Dist++;
275    if (I->findRegisterUseOperandIdx(Reg) != -1)
276        return Dist;
277    I = next(I);
278  }
279  return Dist + 1;
280}
281
282unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
283                                        MachineBasicBlock::iterator I,
284                                        int SPAdj) {
285  assert(ScavengingFrameIndex >= 0 &&
286         "Cannot scavenge a register without an emergency spill slot!");
287
288  // Mask off the registers which are not in the TargetRegisterClass.
289  BitVector Candidates(NumPhysRegs, false);
290  CreateRegClassMask(RC, Candidates);
291  Candidates ^= ReservedRegs;  // Do not include reserved registers.
292
293  // Exclude all the registers being used by the instruction.
294  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
295    MachineOperand &MO = I->getOperand(i);
296    if (MO.isRegister())
297      Candidates.reset(MO.getReg());
298  }
299
300  // Find the register whose use is furthest away.
301  unsigned SReg = 0;
302  unsigned MaxDist = 0;
303  int Reg = Candidates.find_first();
304  while (Reg != -1) {
305    unsigned Dist = calcDistanceToUse(MBB, I, Reg);
306    if (Dist >= MaxDist) {
307      MaxDist = Dist;
308      SReg = Reg;
309    }
310    Reg = Candidates.find_next(Reg);
311  }
312
313  if (ScavengedReg != 0) {
314    // First restore previously scavenged register.
315    TII->loadRegFromStackSlot(*MBB, I, ScavengedReg,
316                              ScavengingFrameIndex, ScavengedRC);
317    MachineBasicBlock::iterator II = prior(I);
318    RegInfo->eliminateFrameIndex(II, SPAdj, this);
319  }
320
321  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
322  MachineBasicBlock::iterator II = prior(I);
323  RegInfo->eliminateFrameIndex(II, SPAdj, this);
324  ScavengedReg = SReg;
325  ScavengedRC = RC;
326
327  return SReg;
328}
329