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 bool RegScavenger::isAliasUsed(unsigned Reg) const {
46 for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R)
52 void RegScavenger::initRegState() {
55 ScavengeRestore = NULL;
57 // All registers started out unused.
60 // Reserved registers are always used.
61 RegsAvailable ^= ReservedRegs;
66 // Live-in registers are in use.
67 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
68 E = MBB->livein_end(); I != E; ++I)
71 // Pristine CSRs are also unavailable.
72 BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB);
73 for (int I = PR.find_first(); I>0; I = PR.find_next(I))
77 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
78 MachineFunction &MF = *mbb->getParent();
79 const TargetMachine &TM = MF.getTarget();
80 TII = TM.getInstrInfo();
81 TRI = TM.getRegisterInfo();
82 MRI = &MF.getRegInfo();
84 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
89 NumPhysRegs = TRI->getNumRegs();
90 RegsAvailable.resize(NumPhysRegs);
92 // Create reserved registers bitvector.
93 ReservedRegs = TRI->getReservedRegs(MF);
95 // Create callee-saved registers bitvector.
96 CalleeSavedRegs.resize(NumPhysRegs);
97 const unsigned *CSRegs = TRI->getCalleeSavedRegs();
99 for (unsigned i = 0; CSRegs[i]; ++i)
100 CalleeSavedRegs.set(CSRegs[i]);
103 // RS used within emit{Pro,Epi}logue()
113 /// isLiveInButUnusedBefore - Return true if register is livein the MBB not
114 /// not used before it reaches the MI that defines register.
115 static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
116 MachineBasicBlock *MBB,
117 const TargetRegisterInfo *TRI,
118 MachineRegisterInfo* MRI) {
119 // First check if register is livein.
120 bool isLiveIn = false;
121 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
122 E = MBB->livein_end(); I != E; ++I)
123 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
130 // Is there any use of it before the specified MI?
131 SmallPtrSet<MachineInstr*, 4> UsesInMBB;
132 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
133 UE = MRI->use_end(); UI != UE; ++UI) {
134 MachineOperand &UseMO = UI.getOperand();
135 if (UseMO.isReg() && UseMO.isUndef())
137 MachineInstr *UseMI = &*UI;
138 if (UseMI->getParent() == MBB)
139 UsesInMBB.insert(UseMI);
141 if (UsesInMBB.empty())
144 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
145 if (UsesInMBB.count(&*I))
151 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
153 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
157 void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
159 for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
163 void RegScavenger::forward() {
169 assert(MBBI != MBB->end() && "Already at the end of the basic block!");
173 MachineInstr *MI = MBBI;
175 if (MI == ScavengeRestore) {
178 ScavengeRestore = NULL;
181 // Find out which registers are early clobbered, killed, defined, and marked
182 // def-dead in this instruction.
183 BitVector EarlyClobberRegs(NumPhysRegs);
184 BitVector KillRegs(NumPhysRegs);
185 BitVector DefRegs(NumPhysRegs);
186 BitVector DeadRegs(NumPhysRegs);
187 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
188 const MachineOperand &MO = MI->getOperand(i);
189 if (!MO.isReg() || MO.isUndef())
191 unsigned Reg = MO.getReg();
192 if (!Reg || isReserved(Reg))
196 // Two-address operands implicitly kill.
197 if (MO.isKill() || MI->isRegTiedToDefOperand(i))
198 addRegWithSubRegs(KillRegs, Reg);
202 addRegWithSubRegs(DeadRegs, Reg);
204 addRegWithSubRegs(DefRegs, Reg);
205 if (MO.isEarlyClobber())
206 addRegWithAliases(EarlyClobberRegs, Reg);
210 // Verify uses and defs.
211 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
212 const MachineOperand &MO = MI->getOperand(i);
213 if (!MO.isReg() || MO.isUndef())
215 unsigned Reg = MO.getReg();
216 if (!Reg || isReserved(Reg))
219 assert(isUsed(Reg) && "Using an undefined register!");
220 assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) &&
221 "Using an early clobbered register!");
224 assert((KillRegs.test(Reg) || isUnused(Reg) ||
225 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
226 "Re-defining a live register!");
230 // Commit the changes.
236 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
238 used = ~RegsAvailable;
240 used = ~RegsAvailable & ~ReservedRegs;
243 /// CreateRegClassMask - Set the bits that represent the registers in the
244 /// TargetRegisterClass.
245 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
246 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
251 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
252 const BitVector &Candidates) const {
253 // Mask off the registers which are not in the TargetRegisterClass.
254 BitVector RegsAvailableCopy(NumPhysRegs, false);
255 CreateRegClassMask(RegClass, RegsAvailableCopy);
256 RegsAvailableCopy &= RegsAvailable;
258 // Restrict the search to candidates.
259 RegsAvailableCopy &= Candidates;
261 // Returns the first unused (bit is set) register, or 0 is none is found.
262 int Reg = RegsAvailableCopy.find_first();
263 return (Reg == -1) ? 0 : Reg;
266 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
267 bool ExCalleeSaved) const {
268 // Mask off the registers which are not in the TargetRegisterClass.
269 BitVector RegsAvailableCopy(NumPhysRegs, false);
270 CreateRegClassMask(RegClass, RegsAvailableCopy);
271 RegsAvailableCopy &= RegsAvailable;
273 // If looking for a non-callee-saved register, mask off all the callee-saved
276 RegsAvailableCopy &= ~CalleeSavedRegs;
278 // Returns the first unused (bit is set) register, or 0 is none is found.
279 int Reg = RegsAvailableCopy.find_first();
280 return (Reg == -1) ? 0 : Reg;
283 /// DistanceMap - Keep track the distance of an MI from the current position.
284 typedef DenseMap<MachineInstr*, unsigned> DistanceMap;
286 /// Build a distance map for instructions from I to E.
287 static void buildDistanceMap(DistanceMap &DM,
288 MachineBasicBlock::iterator I,
289 MachineBasicBlock::iterator E) {
291 for (unsigned d = 0; I != E; ++I, ++d)
292 DM.insert(DistanceMap::value_type(I, d));
295 /// findFirstUse - Calculate the distance to the first use of the
296 /// specified register in the range covered by DM.
297 static MachineInstr *findFirstUse(const MachineBasicBlock *MBB,
298 const DistanceMap &DM,
301 const MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
302 MachineInstr *UseMI = 0;
304 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
305 RE = MRI->reg_end(); RI != RE; ++RI) {
306 MachineInstr *UDMI = &*RI;
307 if (UDMI->getParent() != MBB)
309 DistanceMap::const_iterator DI = DM.find(UDMI);
312 if (DI->second < Dist) {
320 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
321 MachineBasicBlock::iterator I,
323 assert(ScavengingFrameIndex >= 0 &&
324 "Cannot scavenge a register without an emergency spill slot!");
326 // Mask off the registers which are not in the TargetRegisterClass.
327 BitVector Candidates(NumPhysRegs, false);
328 CreateRegClassMask(RC, Candidates);
329 // Do not include reserved registers.
330 Candidates ^= ReservedRegs & Candidates;
332 // Exclude all the registers being used by the instruction.
333 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
334 MachineOperand &MO = I->getOperand(i);
336 Candidates.reset(MO.getReg());
339 // Prepare to call findFirstUse() a number of times.
341 buildDistanceMap(DM, I, MBB->end());
343 // Find the register whose use is furthest away.
345 unsigned MaxDist = 0;
346 MachineInstr *MaxUseMI = 0;
347 int Reg = Candidates.find_first();
350 MachineInstr *UseMI = findFirstUse(MBB, DM, Reg, Dist);
351 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
353 MachineInstr *AsUseMI = findFirstUse(MBB, DM, *AS, AsDist);
360 // If we found an unused register there is no reason to spill it. We have
361 // probably found a callee-saved register that has been saved in the
362 // prologue, but happens to be unused at this point.
363 if (!isAliasUsed(Reg))
366 if (Dist >= MaxDist) {
371 Reg = Candidates.find_next(Reg);
374 assert(ScavengedReg == 0 &&
375 "Scavenger slot is live, unable to scavenge another register!");
377 // Avoid infinite regress
380 // Spill the scavenged register before I.
381 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
382 MachineBasicBlock::iterator II = prior(I);
383 TRI->eliminateFrameIndex(II, SPAdj, this);
385 // Restore the scavenged register before its use (or first terminator).
387 ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
388 TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
389 ScavengeRestore = prior(II);
390 // Doing this here leads to infinite regress.
391 // ScavengedReg = SReg;