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;
72 // Live-in registers are in use.
73 if (!MBB || MBB->livein_empty())
75 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
76 E = MBB->livein_end(); I != E; ++I)
80 void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
81 MachineFunction &MF = *mbb->getParent();
82 const TargetMachine &TM = MF.getTarget();
83 TII = TM.getInstrInfo();
84 TRI = TM.getRegisterInfo();
85 MRI = &MF.getRegInfo();
87 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
92 NumPhysRegs = TRI->getNumRegs();
93 RegsAvailable.resize(NumPhysRegs);
95 // Create reserved registers bitvector.
96 ReservedRegs = TRI->getReservedRegs(MF);
98 // Create callee-saved registers bitvector.
99 CalleeSavedRegs.resize(NumPhysRegs);
100 const unsigned *CSRegs = TRI->getCalleeSavedRegs();
102 for (unsigned i = 0; CSRegs[i]; ++i)
103 CalleeSavedRegs.set(CSRegs[i]);
106 // RS used within emit{Pro,Epi}logue()
115 void RegScavenger::restoreScavengedReg() {
116 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
117 ScavengingFrameIndex, ScavengedRC);
118 MachineBasicBlock::iterator II = prior(MBBI);
119 TRI->eliminateFrameIndex(II, 0, this);
120 setUsed(ScavengedReg);
126 /// isLiveInButUnusedBefore - Return true if register is livein the MBB not
127 /// not used before it reaches the MI that defines register.
128 static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
129 MachineBasicBlock *MBB,
130 const TargetRegisterInfo *TRI,
131 MachineRegisterInfo* MRI) {
132 // First check if register is livein.
133 bool isLiveIn = false;
134 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
135 E = MBB->livein_end(); I != E; ++I)
136 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
143 // Is there any use of it before the specified MI?
144 SmallPtrSet<MachineInstr*, 4> UsesInMBB;
145 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
146 UE = MRI->use_end(); UI != UE; ++UI) {
147 MachineOperand &UseMO = UI.getOperand();
148 if (UseMO.isReg() && UseMO.isUndef())
150 MachineInstr *UseMI = &*UI;
151 if (UseMI->getParent() == MBB)
152 UsesInMBB.insert(UseMI);
154 if (UsesInMBB.empty())
157 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
158 if (UsesInMBB.count(&*I))
164 void RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) {
166 for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++)
170 void RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) {
172 for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++)
176 void RegScavenger::forward() {
182 assert(MBBI != MBB->end() && "Already at the end of the basic block!");
186 MachineInstr *MI = MBBI;
188 if (MI == ScavengeRestore) {
191 ScavengeRestore = NULL;
194 // Find out which registers are early clobbered, killed, defined, and marked
195 // def-dead in this instruction.
196 BitVector EarlyClobberRegs(NumPhysRegs);
197 BitVector KillRegs(NumPhysRegs);
198 BitVector DefRegs(NumPhysRegs);
199 BitVector DeadRegs(NumPhysRegs);
200 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
201 const MachineOperand &MO = MI->getOperand(i);
202 if (!MO.isReg() || MO.isUndef())
204 unsigned Reg = MO.getReg();
205 if (!Reg || isReserved(Reg))
209 // Two-address operands implicitly kill.
210 if (MO.isKill() || MI->isRegTiedToDefOperand(i))
211 addRegWithSubRegs(KillRegs, Reg);
215 addRegWithSubRegs(DeadRegs, Reg);
217 addRegWithSubRegs(DefRegs, Reg);
218 if (MO.isEarlyClobber())
219 addRegWithAliases(EarlyClobberRegs, Reg);
223 // Verify uses and defs.
224 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
225 const MachineOperand &MO = MI->getOperand(i);
226 if (!MO.isReg() || MO.isUndef())
228 unsigned Reg = MO.getReg();
229 if (!Reg || isReserved(Reg))
232 assert(isUsed(Reg) && "Using an undefined register!");
233 assert(!EarlyClobberRegs.test(Reg) &&
234 "Using an early clobbered register!");
237 assert((KillRegs.test(Reg) || isUnused(Reg) ||
238 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
239 "Re-defining a live register!");
243 // Commit the changes.
249 void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
251 used = ~RegsAvailable;
253 used = ~RegsAvailable & ~ReservedRegs;
256 /// CreateRegClassMask - Set the bits that represent the registers in the
257 /// TargetRegisterClass.
258 static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
259 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
264 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
265 const BitVector &Candidates) const {
266 // Mask off the registers which are not in the TargetRegisterClass.
267 BitVector RegsAvailableCopy(NumPhysRegs, false);
268 CreateRegClassMask(RegClass, RegsAvailableCopy);
269 RegsAvailableCopy &= RegsAvailable;
271 // Restrict the search to candidates.
272 RegsAvailableCopy &= Candidates;
274 // Returns the first unused (bit is set) register, or 0 is none is found.
275 int Reg = RegsAvailableCopy.find_first();
276 return (Reg == -1) ? 0 : Reg;
279 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
280 bool ExCalleeSaved) const {
281 // Mask off the registers which are not in the TargetRegisterClass.
282 BitVector RegsAvailableCopy(NumPhysRegs, false);
283 CreateRegClassMask(RegClass, RegsAvailableCopy);
284 RegsAvailableCopy &= RegsAvailable;
286 // If looking for a non-callee-saved register, mask off all the callee-saved
289 RegsAvailableCopy &= ~CalleeSavedRegs;
291 // Returns the first unused (bit is set) register, or 0 is none is found.
292 int Reg = RegsAvailableCopy.find_first();
293 return (Reg == -1) ? 0 : Reg;
296 /// DistanceMap - Keep track the distance of an MI from the current position.
297 typedef DenseMap<MachineInstr*, unsigned> DistanceMap;
299 /// Build a distance map for instructions from I to E.
300 static void buildDistanceMap(DistanceMap &DM,
301 MachineBasicBlock::iterator I,
302 MachineBasicBlock::iterator E) {
304 for (unsigned d = 0; I != E; ++I, ++d)
305 DM.insert(DistanceMap::value_type(I, d));
308 /// findFirstUse - Calculate the distance to the first use of the
309 /// specified register in the range covered by DM.
310 static MachineInstr *findFirstUse(const MachineBasicBlock *MBB,
311 const DistanceMap &DM,
314 const MachineRegisterInfo *MRI = &MBB->getParent()->getRegInfo();
315 MachineInstr *UseMI = 0;
317 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
318 RE = MRI->reg_end(); RI != RE; ++RI) {
319 MachineInstr *UDMI = &*RI;
320 if (UDMI->getParent() != MBB)
322 DistanceMap::const_iterator DI = DM.find(UDMI);
325 if (DI->second < Dist) {
333 unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
334 MachineBasicBlock::iterator I,
336 assert(ScavengingFrameIndex >= 0 &&
337 "Cannot scavenge a register without an emergency spill slot!");
339 // Mask off the registers which are not in the TargetRegisterClass.
340 BitVector Candidates(NumPhysRegs, false);
341 CreateRegClassMask(RC, Candidates);
342 // Do not include reserved registers.
343 Candidates ^= ReservedRegs & Candidates;
345 // Exclude all the registers being used by the instruction.
346 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
347 MachineOperand &MO = I->getOperand(i);
349 Candidates.reset(MO.getReg());
352 // Prepare to call findFirstUse() a number of times.
354 buildDistanceMap(DM, I, MBB->end());
356 // Find the register whose use is furthest away.
358 unsigned MaxDist = 0;
359 MachineInstr *MaxUseMI = 0;
360 int Reg = Candidates.find_first();
363 MachineInstr *UseMI = findFirstUse(MBB, DM, Reg, Dist);
364 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
366 MachineInstr *AsUseMI = findFirstUse(MBB, DM, *AS, AsDist);
373 // If we found an unused register that is defined by a later instruction,
374 // there is no reason to spill it. We have probably found a callee-saved
375 // register that has been saved in the prologue, but happens to be unused at
377 if (!isAliasUsed(Reg) && UseMI != NULL)
380 if (Dist >= MaxDist) {
385 Reg = Candidates.find_next(Reg);
388 assert(ScavengedReg == 0 &&
389 "Scavenger slot is live, unable to scavenge another register!");
391 // Avoid infinite regress
394 // Make sure SReg is marked as used. It could be considered available
395 // if it is one of the callee saved registers, but hasn't been spilled.
397 MBB->addLiveIn(SReg);
401 // Spill the scavenged register before I.
402 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
403 MachineBasicBlock::iterator II = prior(I);
404 TRI->eliminateFrameIndex(II, SPAdj, this);
406 // Restore the scavenged register before its use (or first terminator).
408 ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
409 TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
410 ScavengeRestore = prior(II);
411 // Doing this here leads to infinite regress.
412 // ScavengedReg = SReg;