1 //===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
15 //===----------------------------------------------------------------------===//
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/DenseMap.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/STLExtras.h"
34 /// setUsed - Set the register and its sub-registers as being used.
35 void RegScavenger::setUsed(unsigned Reg) {
36 RegsAvailable.reset(Reg);
38 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
39 unsigned SubReg = *SubRegs; ++SubRegs)
40 RegsAvailable.reset(SubReg);
43 /// setUnused - Set the register and its sub-registers as being unused.
44 void RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
45 RegsAvailable.set(Reg);
47 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
48 unsigned SubReg = *SubRegs; ++SubRegs)
49 RegsAvailable.set(SubReg);
52 bool RegScavenger::isAliasUsed(unsigned Reg) const {
55 for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R)
61 void RegScavenger::initRegState() {
64 ScavengeRestore = NULL;
66 // All registers started out unused.
69 // Reserved registers are always used.
70 RegsAvailable ^= ReservedRegs;
75 // Live-in registers are in use.
76 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
77 E = MBB->livein_end(); I != E; ++I)
80 // Pristine CSRs are also unavailable.
81 BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
82 for (int I = PR.find_first(); I>0; I = PR.find_next(I))
86 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
87 MachineFunction &MF = *mbb->getParent();
88 const TargetMachine &TM = MF.getTarget();
89 TII = TM.getInstrInfo();
90 TRI = TM.getRegisterInfo();
91 MRI = &MF.getRegInfo();
93 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
98 NumPhysRegs = TRI->getNumRegs();
99 RegsAvailable.resize(NumPhysRegs);
101 // Create reserved registers bitvector.
102 ReservedRegs = TRI->getReservedRegs(MF);
104 // Create callee-saved registers bitvector.
105 CalleeSavedRegs.resize(NumPhysRegs);
106 const unsigned *CSRegs = TRI->getCalleeSavedRegs();
108 for (unsigned i = 0; CSRegs[i]; ++i)
109 CalleeSavedRegs.set(CSRegs[i]);
112 // RS used within emit{Pro,Epi}logue()
121 void RegScavenger::restoreScavengedReg() {
122 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
123 ScavengingFrameIndex, ScavengedRC);
124 MachineBasicBlock::iterator II = prior(MBBI);
125 TRI->eliminateFrameIndex(II, 0, this);
126 setUsed(ScavengedReg);
132 /// isLiveInButUnusedBefore - Return true if register is livein the MBB not
133 /// not used before it reaches the MI that defines register.
134 static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
135 MachineBasicBlock *MBB,
136 const TargetRegisterInfo *TRI,
137 MachineRegisterInfo* MRI) {
138 // First check if register is livein.
139 bool isLiveIn = false;
140 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
141 E = MBB->livein_end(); I != E; ++I)
142 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
149 // Is there any use of it before the specified MI?
150 SmallPtrSet<MachineInstr*, 4> UsesInMBB;
151 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
152 UE = MRI->use_end(); UI != UE; ++UI) {
153 MachineOperand &UseMO = UI.getOperand();
154 if (UseMO.isReg() && UseMO.isUndef())
156 MachineInstr *UseMI = &*UI;
157 if (UseMI->getParent() == MBB)
158 UsesInMBB.insert(UseMI);
160 if (UsesInMBB.empty())
163 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
164 if (UsesInMBB.count(&*I))
170 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
172 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
176 void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
178 for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
182 void RegScavenger::forward() {
188 assert(MBBI != MBB->end() && "Already at the end of the basic block!");
192 MachineInstr *MI = MBBI;
194 if (MI == ScavengeRestore) {
197 ScavengeRestore = NULL;
200 // Find out which registers are early clobbered, killed, defined, and marked
201 // def-dead in this instruction.
202 BitVector EarlyClobberRegs(NumPhysRegs);
203 BitVector KillRegs(NumPhysRegs);
204 BitVector DefRegs(NumPhysRegs);
205 BitVector DeadRegs(NumPhysRegs);
206 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
207 const MachineOperand &MO = MI->getOperand(i);
208 if (!MO.isReg() || MO.isUndef())
210 unsigned Reg = MO.getReg();
211 if (!Reg || isReserved(Reg))
215 // Two-address operands implicitly kill.
216 if (MO.isKill() || MI->isRegTiedToDefOperand(i))
217 addRegWithSubRegs(KillRegs, Reg);
221 addRegWithSubRegs(DeadRegs, Reg);
223 addRegWithSubRegs(DefRegs, Reg);
224 if (MO.isEarlyClobber())
225 addRegWithAliases(EarlyClobberRegs, Reg);
229 // Verify uses and defs.
230 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
231 const MachineOperand &MO = MI->getOperand(i);
232 if (!MO.isReg() || MO.isUndef())
234 unsigned Reg = MO.getReg();
235 if (!Reg || isReserved(Reg))
238 assert(isUsed(Reg) && "Using an undefined register!");
239 assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) &&
240 "Using an early clobbered register!");
243 assert((KillRegs.test(Reg) || isUnused(Reg) ||
244 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
245 "Re-defining a live register!");
249 // Commit the changes.
255 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
257 used = ~RegsAvailable;
259 used = ~RegsAvailable & ~ReservedRegs;
262 /// CreateRegClassMask - Set the bits that represent the registers in the
263 /// TargetRegisterClass.
264 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
265 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
270 unsigned 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;
277 // Restrict the search to candidates.
278 RegsAvailableCopy &= Candidates;
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;
285 unsigned 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;
292 // If looking for a non-callee-saved register, mask off all the callee-saved
295 RegsAvailableCopy &= ~CalleeSavedRegs;
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;
302 /// DistanceMap - Keep track the distance of an MI from the current position.
303 typedef DenseMap<MachineInstr*, unsigned> DistanceMap;
305 /// Build a distance map for instructions from I to E.
306 static void buildDistanceMap(DistanceMap &DM,
307 MachineBasicBlock::iterator I,
308 MachineBasicBlock::iterator E) {
310 for (unsigned d = 0; I != E; ++I, ++d)
311 DM.insert(DistanceMap::value_type(I, d));
314 /// findFirstUse - Calculate the distance to the first use of the
315 /// specified register in the range covered by DM.
316 static MachineInstr *findFirstUse(const MachineBasicBlock *MBB,
317 const DistanceMap &DM,
320 const MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
321 MachineInstr *UseMI = 0;
323 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
324 RE = MRI->reg_end(); RI != RE; ++RI) {
325 MachineInstr *UDMI = &*RI;
326 if (UDMI->getParent() != MBB)
328 DistanceMap::const_iterator DI = DM.find(UDMI);
331 if (DI->second < Dist) {
339 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
340 MachineBasicBlock::iterator I,
342 assert(ScavengingFrameIndex >= 0 &&
343 "Cannot scavenge a register without an emergency spill slot!");
345 // Mask off the registers which are not in the TargetRegisterClass.
346 BitVector Candidates(NumPhysRegs, false);
347 CreateRegClassMask(RC, Candidates);
348 // Do not include reserved registers.
349 Candidates ^= ReservedRegs & Candidates;
351 // Exclude all the registers being used by the instruction.
352 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
353 MachineOperand &MO = I->getOperand(i);
355 Candidates.reset(MO.getReg());
358 // Prepare to call findFirstUse() a number of times.
360 buildDistanceMap(DM, I, MBB->end());
362 // Find the register whose use is furthest away.
364 unsigned MaxDist = 0;
365 MachineInstr *MaxUseMI = 0;
366 int Reg = Candidates.find_first();
369 MachineInstr *UseMI = findFirstUse(MBB, DM, Reg, Dist);
370 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
372 MachineInstr *AsUseMI = findFirstUse(MBB, DM, *AS, AsDist);
379 // If we found an unused register there is no reason to spill it. We have
380 // probably found a callee-saved register that has been saved in the
381 // prologue, but happens to be unused at this point.
382 if (!isAliasUsed(Reg))
385 if (Dist >= MaxDist) {
390 Reg = Candidates.find_next(Reg);
393 assert(ScavengedReg == 0 &&
394 "Scavenger slot is live, unable to scavenge another register!");
396 // Avoid infinite regress
399 // Spill the scavenged register before I.
400 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
401 MachineBasicBlock::iterator II = prior(I);
402 TRI->eliminateFrameIndex(II, SPAdj, this);
404 // Restore the scavenged register before its use (or first terminator).
406 ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
407 TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
408 ScavengeRestore = prior(II);
409 // Doing this here leads to infinite regress.
410 // ScavengedReg = SReg;