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