RegisterScavenging.cpp revision dffb051c21d32209c601ca0ca6baae75b6c6463f 
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/MachineFrameInfo.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Target/TargetRegisterInfo.h"
26#include "llvm/Target/TargetInstrInfo.h"
27#include "llvm/Target/TargetMachine.h"
28#include "llvm/ADT/SmallPtrSet.h"
29#include "llvm/ADT/SmallVector.h"
30#include "llvm/ADT/STLExtras.h"
31using namespace llvm;
32
33/// RedefinesSuperRegPart - Return true if the specified register is redefining
34/// part of a super-register.
35static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
36                                  const TargetRegisterInfo *TRI) {
37  bool SeenSuperUse = false;
38  bool SeenSuperDef = false;
39  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
40    const MachineOperand &MO = MI->getOperand(i);
41    if (!MO.isReg() || MO.isUndef())
42      continue;
43    if (TRI->isSuperRegister(SubReg, MO.getReg())) {
44      if (MO.isUse())
45        SeenSuperUse = true;
46      else if (MO.isImplicit())
47        SeenSuperDef = true;
48    }
49  }
50
51  return SeenSuperDef && SeenSuperUse;
52}
53
54bool RegScavenger::isSuperRegUsed(unsigned Reg) const {
55  for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg);
56       unsigned SuperReg = *SuperRegs; ++SuperRegs)
57    if (isUsed(SuperReg))
58      return true;
59  return false;
60}
61
62/// setUsed - Set the register and its sub-registers as being used.
63void RegScavenger::setUsed(unsigned Reg) {
64  RegsAvailable.reset(Reg);
65
66  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
67       unsigned SubReg = *SubRegs; ++SubRegs)
68    RegsAvailable.reset(SubReg);
69}
70
71/// setUnused - Set the register and its sub-registers as being unused.
72void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
73  RegsAvailable.set(Reg);
74
75  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
76       unsigned SubReg = *SubRegs; ++SubRegs)
77    if (!RedefinesSuperRegPart(MI, Reg, TRI))
78      RegsAvailable.set(SubReg);
79}
80
81void RegScavenger::initRegState() {
82  ScavengedReg = 0;
83  ScavengedRC = NULL;
84  ScavengeRestore = NULL;
85  CurrDist = 0;
86  DistanceMap.clear();
87
88  // All registers started out unused.
89  RegsAvailable.set();
90
91  // Reserved registers are always used.
92  RegsAvailable ^= ReservedRegs;
93
94  // Live-in registers are in use.
95  if (!MBB || MBB->livein_empty())
96    return;
97  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
98         E = MBB->livein_end(); I != E; ++I)
99    setUsed(*I);
100}
101
102void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
103  MachineFunction &MF = *mbb->getParent();
104  const TargetMachine &TM = MF.getTarget();
105  TII = TM.getInstrInfo();
106  TRI = TM.getRegisterInfo();
107  MRI = &MF.getRegInfo();
108
109  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
110         "Target changed?");
111
112  // Self-initialize.
113  if (!MBB) {
114    NumPhysRegs = TRI->getNumRegs();
115    RegsAvailable.resize(NumPhysRegs);
116
117    // Create reserved registers bitvector.
118    ReservedRegs = TRI->getReservedRegs(MF);
119
120    // Create callee-saved registers bitvector.
121    CalleeSavedRegs.resize(NumPhysRegs);
122    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
123    if (CSRegs != NULL)
124      for (unsigned i = 0; CSRegs[i]; ++i)
125        CalleeSavedRegs.set(CSRegs[i]);
126  }
127
128  // RS used within emit{Pro,Epi}logue()
129  if (mbb != MBB) {
130    MBB = mbb;
131    initRegState();
132  }
133
134  Tracking = false;
135}
136
137void RegScavenger::restoreScavengedReg() {
138  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
139                            ScavengingFrameIndex, ScavengedRC);
140  MachineBasicBlock::iterator II = prior(MBBI);
141  TRI->eliminateFrameIndex(II, 0, this);
142  setUsed(ScavengedReg);
143  ScavengedReg = 0;
144  ScavengedRC = NULL;
145}
146
147#ifndef NDEBUG
148/// isLiveInButUnusedBefore - Return true if register is livein the MBB not
149/// not used before it reaches the MI that defines register.
150static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
151                                    MachineBasicBlock *MBB,
152                                    const TargetRegisterInfo *TRI,
153                                    MachineRegisterInfo* MRI) {
154  // First check if register is livein.
155  bool isLiveIn = false;
156  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
157         E = MBB->livein_end(); I != E; ++I)
158    if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
159      isLiveIn = true;
160      break;
161    }
162  if (!isLiveIn)
163    return false;
164
165  // Is there any use of it before the specified MI?
166  SmallPtrSet<MachineInstr*, 4> UsesInMBB;
167  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
168         UE = MRI->use_end(); UI != UE; ++UI) {
169    MachineOperand &UseMO = UI.getOperand();
170    if (UseMO.isReg() && UseMO.isUndef())
171      continue;
172    MachineInstr *UseMI = &*UI;
173    if (UseMI->getParent() == MBB)
174      UsesInMBB.insert(UseMI);
175  }
176  if (UsesInMBB.empty())
177    return true;
178
179  for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
180    if (UsesInMBB.count(&*I))
181      return false;
182  return true;
183}
184#endif
185
186void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
187  BV.set(Reg);
188  for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
189    BV.set(*R);
190}
191
192void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
193  BV.set(Reg);
194  for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
195    BV.set(*R);
196}
197
198void RegScavenger::forward() {
199  // Move ptr forward.
200  if (!Tracking) {
201    MBBI = MBB->begin();
202    Tracking = true;
203  } else {
204    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
205    MBBI = next(MBBI);
206  }
207
208  MachineInstr *MI = MBBI;
209  DistanceMap.insert(std::make_pair(MI, CurrDist++));
210
211  if (MI == ScavengeRestore) {
212    ScavengedReg = 0;
213    ScavengedRC = NULL;
214    ScavengeRestore = NULL;
215  }
216
217  // Find out which registers are early clobbered, killed, defined, and marked
218  // def-dead in this instruction.
219  BitVector EarlyClobberRegs(NumPhysRegs);
220  BitVector KillRegs(NumPhysRegs);
221  BitVector DefRegs(NumPhysRegs);
222  BitVector DeadRegs(NumPhysRegs);
223  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
224    const MachineOperand &MO = MI->getOperand(i);
225    if (!MO.isReg() || MO.isUndef())
226      continue;
227    unsigned Reg = MO.getReg();
228    if (!Reg || isReserved(Reg))
229      continue;
230
231    if (MO.isUse()) {
232      // Two-address operands implicitly kill.
233      if (MO.isKill() || MI->isRegTiedToDefOperand(i))
234        addRegWithSubRegs(KillRegs, Reg);
235    } else {
236      assert(MO.isDef());
237      if (MO.isDead())
238        addRegWithSubRegs(DeadRegs, Reg);
239      else
240        addRegWithSubRegs(DefRegs, Reg);
241      if (MO.isEarlyClobber())
242        addRegWithAliases(EarlyClobberRegs, Reg);
243    }
244  }
245
246  // Verify uses and defs.
247  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
248    const MachineOperand &MO = MI->getOperand(i);
249    if (!MO.isReg() || MO.isUndef())
250      continue;
251    unsigned Reg = MO.getReg();
252    if (!Reg || isReserved(Reg))
253      continue;
254    if (MO.isUse()) {
255      assert(isUsed(Reg) && "Using an undefined register!");
256      assert(!EarlyClobberRegs.test(Reg) &&
257             "Using an early clobbered register!");
258    } else {
259      assert(MO.isDef());
260      assert((KillRegs.test(Reg) || isUnused(Reg) || isSuperRegUsed(Reg) ||
261              isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
262             "Re-defining a live register!");
263    }
264  }
265
266  // Commit the changes.
267  setUnused(KillRegs);
268  setUnused(DeadRegs);
269  setUsed(DefRegs);
270}
271
272void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
273  if (includeReserved)
274    used = ~RegsAvailable;
275  else
276    used = ~RegsAvailable & ~ReservedRegs;
277}
278
279/// CreateRegClassMask - Set the bits that represent the registers in the
280/// TargetRegisterClass.
281static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
282  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
283       ++I)
284    Mask.set(*I);
285}
286
287unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
288                                     const BitVector &Candidates) const {
289  // Mask off the registers which are not in the TargetRegisterClass.
290  BitVector RegsAvailableCopy(NumPhysRegs, false);
291  CreateRegClassMask(RegClass, RegsAvailableCopy);
292  RegsAvailableCopy &= RegsAvailable;
293
294  // Restrict the search to candidates.
295  RegsAvailableCopy &= Candidates;
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
302unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
303                                     bool ExCalleeSaved) const {
304  // Mask off the registers which are not in the TargetRegisterClass.
305  BitVector RegsAvailableCopy(NumPhysRegs, false);
306  CreateRegClassMask(RegClass, RegsAvailableCopy);
307  RegsAvailableCopy &= RegsAvailable;
308
309  // If looking for a non-callee-saved register, mask off all the callee-saved
310  // registers.
311  if (ExCalleeSaved)
312    RegsAvailableCopy &= ~CalleeSavedRegs;
313
314  // Returns the first unused (bit is set) register, or 0 is none is found.
315  int Reg = RegsAvailableCopy.find_first();
316  return (Reg == -1) ? 0 : Reg;
317}
318
319/// findFirstUse - Calculate the distance to the first use of the
320/// specified register.
321MachineInstr*
322RegScavenger::findFirstUse(MachineBasicBlock *MBB,
323                           MachineBasicBlock::iterator I, unsigned Reg,
324                           unsigned &Dist) {
325  MachineInstr *UseMI = 0;
326  Dist = ~0U;
327  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
328         RE = MRI->reg_end(); RI != RE; ++RI) {
329    MachineInstr *UDMI = &*RI;
330    if (UDMI->getParent() != MBB)
331      continue;
332    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
333    if (DI == DistanceMap.end()) {
334      // If it's not in map, it's below current MI, let's initialize the
335      // map.
336      I = next(I);
337      unsigned Dist = CurrDist + 1;
338      while (I != MBB->end()) {
339        DistanceMap.insert(std::make_pair(I, Dist++));
340        I = next(I);
341      }
342    }
343    DI = DistanceMap.find(UDMI);
344    if (DI->second > CurrDist && DI->second < Dist) {
345      Dist = DI->second;
346      UseMI = UDMI;
347    }
348  }
349  return UseMI;
350}
351
352unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
353                                        MachineBasicBlock::iterator I,
354                                        int SPAdj) {
355  assert(ScavengingFrameIndex >= 0 &&
356         "Cannot scavenge a register without an emergency spill slot!");
357
358  // Mask off the registers which are not in the TargetRegisterClass.
359  BitVector Candidates(NumPhysRegs, false);
360  CreateRegClassMask(RC, Candidates);
361  // Do not include reserved registers.
362  Candidates ^= ReservedRegs & Candidates;
363
364  // Exclude all the registers being used by the instruction.
365  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
366    MachineOperand &MO = I->getOperand(i);
367    if (MO.isReg())
368      Candidates.reset(MO.getReg());
369  }
370
371  // Find the register whose use is furthest away.
372  unsigned SReg = 0;
373  unsigned MaxDist = 0;
374  MachineInstr *MaxUseMI = 0;
375  int Reg = Candidates.find_first();
376  while (Reg != -1) {
377    unsigned Dist;
378    MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
379    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
380      unsigned AsDist;
381      MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
382      if (AsDist < Dist) {
383        Dist = AsDist;
384        UseMI = AsUseMI;
385      }
386    }
387    if (Dist >= MaxDist) {
388      MaxDist = Dist;
389      MaxUseMI = UseMI;
390      SReg = Reg;
391    }
392    Reg = Candidates.find_next(Reg);
393  }
394
395  assert(ScavengedReg == 0 &&
396         "Scavenger slot is live, unable to scavenge another register!");
397
398  // Avoid infinite regress
399  ScavengedReg = SReg;
400
401  // Make sure SReg is marked as used. It could be considered available
402  // if it is one of the callee saved registers, but hasn't been spilled.
403  if (!isUsed(SReg)) {
404    MBB->addLiveIn(SReg);
405    setUsed(SReg);
406  }
407
408  // Spill the scavenged register before I.
409  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
410  MachineBasicBlock::iterator II = prior(I);
411  TRI->eliminateFrameIndex(II, SPAdj, this);
412
413  // Restore the scavenged register before its use (or first terminator).
414  II = MaxUseMI
415    ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
416  TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
417  ScavengeRestore = prior(II);
418  // Doing this here leads to infinite regress.
419  // ScavengedReg = SReg;
420  ScavengedRC = RC;
421
422  return SReg;
423}
424