RegisterScavenging.cpp revision 50564ebc9e3d7ff806062023e6511e91065df0d2
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/MachineFunction.h" 20#include "llvm/CodeGen/MachineBasicBlock.h" 21#include "llvm/CodeGen/MachineInstr.h" 22#include "llvm/CodeGen/MachineRegisterInfo.h" 23#include "llvm/Target/TargetRegisterInfo.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "llvm/Target/TargetMachine.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/ADT/SmallVector.h" 28#include "llvm/ADT/STLExtras.h" 29using namespace llvm; 30 31/// RedefinesSuperRegPart - Return true if the specified register is redefining 32/// part of a super-register. 33static bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg, 34 const TargetRegisterInfo *TRI) { 35 bool SeenSuperUse = false; 36 bool SeenSuperDef = false; 37 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 38 const MachineOperand &MO = MI->getOperand(i); 39 if (!MO.isReg() || MO.isUndef()) 40 continue; 41 if (TRI->isSuperRegister(SubReg, MO.getReg())) { 42 if (MO.isUse()) 43 SeenSuperUse = true; 44 else if (MO.isImplicit()) 45 SeenSuperDef = true; 46 } 47 } 48 49 return SeenSuperDef && SeenSuperUse; 50} 51 52static bool RedefinesSuperRegPart(const MachineInstr *MI, 53 const MachineOperand &MO, 54 const TargetRegisterInfo *TRI) { 55 assert(MO.isReg() && MO.isDef() && "Not a register def!"); 56 return RedefinesSuperRegPart(MI, MO.getReg(), TRI); 57} 58 59/// setUsed - Set the register and its sub-registers as being used. 60void RegScavenger::setUsed(unsigned Reg, bool ImpDef) { 61 RegsAvailable.reset(Reg); 62 ImplicitDefed[Reg] = ImpDef; 63 64 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 65 unsigned SubReg = *SubRegs; ++SubRegs) { 66 RegsAvailable.reset(SubReg); 67 ImplicitDefed[SubReg] = ImpDef; 68 } 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 ImplicitDefed.reset(Reg); 75 76 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 77 unsigned SubReg = *SubRegs; ++SubRegs) 78 if (!RedefinesSuperRegPart(MI, Reg, TRI)) { 79 RegsAvailable.set(SubReg); 80 ImplicitDefed.reset(SubReg); 81 } 82} 83 84void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 85 MachineFunction &MF = *mbb->getParent(); 86 const TargetMachine &TM = MF.getTarget(); 87 TII = TM.getInstrInfo(); 88 TRI = TM.getRegisterInfo(); 89 MRI = &MF.getRegInfo(); 90 91 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 92 "Target changed?"); 93 94 if (!MBB) { 95 NumPhysRegs = TRI->getNumRegs(); 96 RegsAvailable.resize(NumPhysRegs); 97 ImplicitDefed.resize(NumPhysRegs); 98 99 // Create reserved registers bitvector. 100 ReservedRegs = TRI->getReservedRegs(MF); 101 102 // Create callee-saved registers bitvector. 103 CalleeSavedRegs.resize(NumPhysRegs); 104 const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 105 if (CSRegs != NULL) 106 for (unsigned i = 0; CSRegs[i]; ++i) 107 CalleeSavedRegs.set(CSRegs[i]); 108 } 109 110 MBB = mbb; 111 ScavengedReg = 0; 112 ScavengedRC = NULL; 113 ScavengeRestore = NULL; 114 CurrDist = 0; 115 DistanceMap.clear(); 116 ImplicitDefed.reset(); 117 118 // All registers started out unused. 119 RegsAvailable.set(); 120 121 // Reserved registers are always used. 122 RegsAvailable ^= ReservedRegs; 123 124 // Live-in registers are in use. 125 if (!MBB->livein_empty()) 126 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 127 E = MBB->livein_end(); I != E; ++I) 128 setUsed(*I); 129 130 Tracking = false; 131} 132 133void RegScavenger::restoreScavengedReg() { 134 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 135 ScavengingFrameIndex, ScavengedRC); 136 MachineBasicBlock::iterator II = prior(MBBI); 137 TRI->eliminateFrameIndex(II, 0, this); 138 setUsed(ScavengedReg); 139 ScavengedReg = 0; 140 ScavengedRC = NULL; 141} 142 143#ifndef NDEBUG 144/// isLiveInButUnusedBefore - Return true if register is livein the MBB not 145/// not used before it reaches the MI that defines register. 146static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 147 MachineBasicBlock *MBB, 148 const TargetRegisterInfo *TRI, 149 MachineRegisterInfo* MRI) { 150 // First check if register is livein. 151 bool isLiveIn = false; 152 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 153 E = MBB->livein_end(); I != E; ++I) 154 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 155 isLiveIn = true; 156 break; 157 } 158 if (!isLiveIn) 159 return false; 160 161 // Is there any use of it before the specified MI? 162 SmallPtrSet<MachineInstr*, 4> UsesInMBB; 163 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 164 UE = MRI->use_end(); UI != UE; ++UI) { 165 MachineInstr *UseMI = &*UI; 166 if (UseMI->getParent() == MBB) 167 UsesInMBB.insert(UseMI); 168 } 169 if (UsesInMBB.empty()) 170 return true; 171 172 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 173 if (UsesInMBB.count(&*I)) 174 return false; 175 return true; 176} 177#endif 178 179void RegScavenger::forward() { 180 // Move ptr forward. 181 if (!Tracking) { 182 MBBI = MBB->begin(); 183 Tracking = true; 184 } else { 185 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 186 MBBI = next(MBBI); 187 } 188 189 MachineInstr *MI = MBBI; 190 DistanceMap.insert(std::make_pair(MI, CurrDist++)); 191 192 if (MI == ScavengeRestore) { 193 ScavengedReg = 0; 194 ScavengedRC = NULL; 195 ScavengeRestore = NULL; 196 } 197 198 bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 199 200 // Separate register operands into 3 classes: uses, defs, earlyclobbers. 201 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 202 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 203 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 204 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 205 const MachineOperand &MO = MI->getOperand(i); 206 if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef()) 207 continue; 208 if (MO.isUse()) 209 UseMOs.push_back(std::make_pair(&MO,i)); 210 else if (MO.isEarlyClobber()) 211 EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 212 else 213 DefMOs.push_back(std::make_pair(&MO,i)); 214 } 215 216 // Process uses first. 217 BitVector KillRegs(NumPhysRegs); 218 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 219 const MachineOperand MO = *UseMOs[i].first; 220 unsigned Reg = MO.getReg(); 221 222 assert(isUsed(Reg) && "Using an undefined register!"); 223 224 // Kill of implicit_def defined registers are ignored. e.g. 225 // entry: 0x2029ab8, LLVM BB @0x1b06080, ID#0: 226 // Live Ins: %R0 227 // %R0<def> = IMPLICIT_DEF 228 // %R0<def> = IMPLICIT_DEF 229 // STR %R0<kill>, %R0, %reg0, 0, 14, %reg0, Mem:ST(4,4) [0x1b06510 + 0] 230 // %R1<def> = LDR %R0, %reg0, 24, 14, %reg0, Mem:LD(4,4) [0x1b065bc + 0] 231 if (MO.isKill() && !isReserved(Reg) && !isImplicitlyDefined(Reg)) { 232 KillRegs.set(Reg); 233 234 // Mark sub-registers as used. 235 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 236 unsigned SubReg = *SubRegs; ++SubRegs) 237 KillRegs.set(SubReg); 238 } 239 } 240 241 // Change states of all registers after all the uses are processed to guard 242 // against multiple uses. 243 setUnused(KillRegs); 244 245 // Process early clobber defs then process defs. We can have a early clobber 246 // that is dead, it should not conflict with a def that happens one "slot" 247 // (see InstrSlots in LiveIntervalAnalysis.h) later. 248 unsigned NumECs = EarlyClobberMOs.size(); 249 unsigned NumDefs = DefMOs.size(); 250 251 for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 252 const MachineOperand &MO = (i < NumECs) 253 ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 254 unsigned Idx = (i < NumECs) 255 ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 256 unsigned Reg = MO.getReg(); 257 258 // If it's dead upon def, then it is now free. 259 if (MO.isDead()) { 260 setUnused(Reg, MI); 261 continue; 262 } 263 264 // Skip two-address destination operand. 265 if (MI->isRegTiedToUseOperand(Idx)) { 266 assert(isUsed(Reg) && "Using an undefined register!"); 267 continue; 268 } 269 270 // Skip if this is merely redefining part of a super-register. 271 if (RedefinesSuperRegPart(MI, MO, TRI)) 272 continue; 273 274 // Implicit def is allowed to "re-define" any register. Similarly, 275 // implicitly defined registers can be clobbered. 276 assert((isReserved(Reg) || isUnused(Reg) || 277 IsImpDef || isImplicitlyDefined(Reg) || 278 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 279 "Re-defining a live register!"); 280 setUsed(Reg, IsImpDef); 281 } 282} 283 284void RegScavenger::backward() { 285 assert(Tracking && "Not tracking states!"); 286 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 287 // Move ptr backward. 288 MBBI = prior(MBBI); 289 290 MachineInstr *MI = MBBI; 291 DistanceMap.erase(MI); 292 --CurrDist; 293 294 // Separate register operands into 3 classes: uses, defs, earlyclobbers. 295 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 296 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 297 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 298 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 299 const MachineOperand &MO = MI->getOperand(i); 300 if (!MO.isReg() || MO.getReg() == 0 || MO.isUndef()) 301 continue; 302 if (MO.isUse()) 303 UseMOs.push_back(std::make_pair(&MO,i)); 304 else if (MO.isEarlyClobber()) 305 EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 306 else 307 DefMOs.push_back(std::make_pair(&MO,i)); 308 } 309 310 311 // Process defs first. 312 unsigned NumECs = EarlyClobberMOs.size(); 313 unsigned NumDefs = DefMOs.size(); 314 for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 315 const MachineOperand &MO = (i < NumDefs) 316 ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first; 317 unsigned Idx = (i < NumECs) 318 ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second; 319 320 // Skip two-address destination operand. 321 if (MI->isRegTiedToUseOperand(Idx)) 322 continue; 323 324 unsigned Reg = MO.getReg(); 325 assert(isUsed(Reg)); 326 if (!isReserved(Reg)) 327 setUnused(Reg, MI); 328 } 329 330 // Process uses. 331 BitVector UseRegs(NumPhysRegs); 332 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 333 const MachineOperand MO = *UseMOs[i].first; 334 unsigned Reg = MO.getReg(); 335 assert(isUnused(Reg) || isReserved(Reg)); 336 UseRegs.set(Reg); 337 338 // Set the sub-registers as "used". 339 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 340 unsigned SubReg = *SubRegs; ++SubRegs) 341 UseRegs.set(SubReg); 342 } 343 setUsed(UseRegs); 344} 345 346void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 347 if (includeReserved) 348 used = ~RegsAvailable; 349 else 350 used = ~RegsAvailable & ~ReservedRegs; 351} 352 353/// CreateRegClassMask - Set the bits that represent the registers in the 354/// TargetRegisterClass. 355static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 356 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 357 ++I) 358 Mask.set(*I); 359} 360 361unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 362 const BitVector &Candidates) const { 363 // Mask off the registers which are not in the TargetRegisterClass. 364 BitVector RegsAvailableCopy(NumPhysRegs, false); 365 CreateRegClassMask(RegClass, RegsAvailableCopy); 366 RegsAvailableCopy &= RegsAvailable; 367 368 // Restrict the search to candidates. 369 RegsAvailableCopy &= Candidates; 370 371 // Returns the first unused (bit is set) register, or 0 is none is found. 372 int Reg = RegsAvailableCopy.find_first(); 373 return (Reg == -1) ? 0 : Reg; 374} 375 376unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 377 bool ExCalleeSaved) const { 378 // Mask off the registers which are not in the TargetRegisterClass. 379 BitVector RegsAvailableCopy(NumPhysRegs, false); 380 CreateRegClassMask(RegClass, RegsAvailableCopy); 381 RegsAvailableCopy &= RegsAvailable; 382 383 // If looking for a non-callee-saved register, mask off all the callee-saved 384 // registers. 385 if (ExCalleeSaved) 386 RegsAvailableCopy &= ~CalleeSavedRegs; 387 388 // Returns the first unused (bit is set) register, or 0 is none is found. 389 int Reg = RegsAvailableCopy.find_first(); 390 return (Reg == -1) ? 0 : Reg; 391} 392 393/// findFirstUse - Calculate the distance to the first use of the 394/// specified register. 395MachineInstr* 396RegScavenger::findFirstUse(MachineBasicBlock *MBB, 397 MachineBasicBlock::iterator I, unsigned Reg, 398 unsigned &Dist) { 399 MachineInstr *UseMI = 0; 400 Dist = ~0U; 401 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 402 RE = MRI->reg_end(); RI != RE; ++RI) { 403 MachineInstr *UDMI = &*RI; 404 if (UDMI->getParent() != MBB) 405 continue; 406 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 407 if (DI == DistanceMap.end()) { 408 // If it's not in map, it's below current MI, let's initialize the 409 // map. 410 I = next(I); 411 unsigned Dist = CurrDist + 1; 412 while (I != MBB->end()) { 413 DistanceMap.insert(std::make_pair(I, Dist++)); 414 I = next(I); 415 } 416 } 417 DI = DistanceMap.find(UDMI); 418 if (DI->second > CurrDist && DI->second < Dist) { 419 Dist = DI->second; 420 UseMI = UDMI; 421 } 422 } 423 return UseMI; 424} 425 426unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 427 MachineBasicBlock::iterator I, 428 int SPAdj) { 429 assert(ScavengingFrameIndex >= 0 && 430 "Cannot scavenge a register without an emergency spill slot!"); 431 432 // Mask off the registers which are not in the TargetRegisterClass. 433 BitVector Candidates(NumPhysRegs, false); 434 CreateRegClassMask(RC, Candidates); 435 Candidates ^= ReservedRegs; // Do not include reserved registers. 436 437 // Exclude all the registers being used by the instruction. 438 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 439 MachineOperand &MO = I->getOperand(i); 440 if (MO.isReg()) 441 Candidates.reset(MO.getReg()); 442 } 443 444 // Find the register whose use is furthest away. 445 unsigned SReg = 0; 446 unsigned MaxDist = 0; 447 MachineInstr *MaxUseMI = 0; 448 int Reg = Candidates.find_first(); 449 while (Reg != -1) { 450 unsigned Dist; 451 MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 452 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 453 unsigned AsDist; 454 MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 455 if (AsDist < Dist) { 456 Dist = AsDist; 457 UseMI = AsUseMI; 458 } 459 } 460 if (Dist >= MaxDist) { 461 MaxDist = Dist; 462 MaxUseMI = UseMI; 463 SReg = Reg; 464 } 465 Reg = Candidates.find_next(Reg); 466 } 467 468 if (ScavengedReg != 0) { 469 assert(0 && "Scavenger slot is live, unable to scavenge another register!"); 470 abort(); 471 } 472 473 // Spill the scavenged register before I. 474 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 475 MachineBasicBlock::iterator II = prior(I); 476 TRI->eliminateFrameIndex(II, SPAdj, this); 477 478 // Restore the scavenged register before its use (or first terminator). 479 II = MaxUseMI 480 ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator(); 481 TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC); 482 ScavengeRestore = prior(II); 483 ScavengedReg = SReg; 484 ScavengedRC = RC; 485 486 return SReg; 487} 488