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