RegisterScavenging.cpp revision d68a07650cdb2e18f18f362ba533459aa10e01b6
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()) 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 const TargetInstrDesc &TID = MI->getDesc(); 192 193 if (MI == ScavengeRestore) { 194 ScavengedReg = 0; 195 ScavengedRC = NULL; 196 ScavengeRestore = NULL; 197 } 198 199 bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 200 201 // Separate register operands into 3 classes: uses, defs, earlyclobbers. 202 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 203 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 204 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 205 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 206 const MachineOperand &MO = MI->getOperand(i); 207 if (!MO.isReg() || MO.getReg() == 0) 208 continue; 209 if (MO.isUse()) 210 UseMOs.push_back(std::make_pair(&MO,i)); 211 else if (MO.isEarlyClobber()) 212 EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 213 else 214 DefMOs.push_back(std::make_pair(&MO,i)); 215 } 216 217 // Process uses first. 218 BitVector UseRegs(NumPhysRegs); 219 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 220 const MachineOperand MO = *UseMOs[i].first; 221 unsigned Reg = MO.getReg(); 222 223 assert(isUsed(Reg) && "Using an undefined register!"); 224 225 if (MO.isKill() && !isReserved(Reg)) { 226 UseRegs.set(Reg); 227 228 // Mark sub-registers as used. 229 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 230 unsigned SubReg = *SubRegs; ++SubRegs) 231 UseRegs.set(SubReg); 232 } 233 } 234 235 // Change states of all registers after all the uses are processed to guard 236 // against multiple uses. 237 setUnused(UseRegs); 238 239 // Process early clobber defs then process defs. We can have a early clobber 240 // that is dead, it should not conflict with a def that happens one "slot" 241 // (see InstrSlots in LiveIntervalAnalysis.h) later. 242 unsigned NumECs = EarlyClobberMOs.size(); 243 unsigned NumDefs = DefMOs.size(); 244 245 for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 246 const MachineOperand &MO = (i < NumECs) 247 ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 248 unsigned Idx = (i < NumECs) 249 ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 250 unsigned Reg = MO.getReg(); 251 252 // If it's dead upon def, then it is now free. 253 if (MO.isDead()) { 254 setUnused(Reg, MI); 255 continue; 256 } 257 258 // Skip two-address destination operand. 259 if (TID.findTiedToSrcOperand(Idx) != -1) { 260 assert(isUsed(Reg) && "Using an undefined register!"); 261 continue; 262 } 263 264 // Skip if this is merely redefining part of a super-register. 265 if (RedefinesSuperRegPart(MI, MO, TRI)) 266 continue; 267 268 // Implicit def is allowed to "re-define" any register. Similarly, 269 // implicitly defined registers can be clobbered. 270 assert((isReserved(Reg) || isUnused(Reg) || 271 IsImpDef || isImplicitlyDefined(Reg) || 272 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 273 "Re-defining a live register!"); 274 setUsed(Reg, IsImpDef); 275 } 276} 277 278void RegScavenger::backward() { 279 assert(Tracking && "Not tracking states!"); 280 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 281 // Move ptr backward. 282 MBBI = prior(MBBI); 283 284 MachineInstr *MI = MBBI; 285 DistanceMap.erase(MI); 286 --CurrDist; 287 const TargetInstrDesc &TID = MI->getDesc(); 288 289 // Separate register operands into 3 classes: uses, defs, earlyclobbers. 290 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 291 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 292 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 293 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 294 const MachineOperand &MO = MI->getOperand(i); 295 if (!MO.isReg() || MO.getReg() == 0) 296 continue; 297 if (MO.isUse()) 298 UseMOs.push_back(std::make_pair(&MO,i)); 299 else if (MO.isEarlyClobber()) 300 EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 301 else 302 DefMOs.push_back(std::make_pair(&MO,i)); 303 } 304 305 306 // Process defs first. 307 unsigned NumECs = EarlyClobberMOs.size(); 308 unsigned NumDefs = DefMOs.size(); 309 for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 310 const MachineOperand &MO = (i < NumDefs) 311 ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first; 312 unsigned Idx = (i < NumECs) 313 ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second; 314 315 // Skip two-address destination operand. 316 if (TID.findTiedToSrcOperand(Idx) != -1) 317 continue; 318 319 unsigned Reg = MO.getReg(); 320 assert(isUsed(Reg)); 321 if (!isReserved(Reg)) 322 setUnused(Reg, MI); 323 } 324 325 // Process uses. 326 BitVector UseRegs(NumPhysRegs); 327 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 328 const MachineOperand MO = *UseMOs[i].first; 329 unsigned Reg = MO.getReg(); 330 assert(isUnused(Reg) || isReserved(Reg)); 331 UseRegs.set(Reg); 332 333 // Set the sub-registers as "used". 334 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 335 unsigned SubReg = *SubRegs; ++SubRegs) 336 UseRegs.set(SubReg); 337 } 338 setUsed(UseRegs); 339} 340 341void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 342 if (includeReserved) 343 used = ~RegsAvailable; 344 else 345 used = ~RegsAvailable & ~ReservedRegs; 346} 347 348/// CreateRegClassMask - Set the bits that represent the registers in the 349/// TargetRegisterClass. 350static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 351 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 352 ++I) 353 Mask.set(*I); 354} 355 356unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 357 const BitVector &Candidates) const { 358 // Mask off the registers which are not in the TargetRegisterClass. 359 BitVector RegsAvailableCopy(NumPhysRegs, false); 360 CreateRegClassMask(RegClass, RegsAvailableCopy); 361 RegsAvailableCopy &= RegsAvailable; 362 363 // Restrict the search to candidates. 364 RegsAvailableCopy &= Candidates; 365 366 // Returns the first unused (bit is set) register, or 0 is none is found. 367 int Reg = RegsAvailableCopy.find_first(); 368 return (Reg == -1) ? 0 : Reg; 369} 370 371unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 372 bool ExCalleeSaved) const { 373 // Mask off the registers which are not in the TargetRegisterClass. 374 BitVector RegsAvailableCopy(NumPhysRegs, false); 375 CreateRegClassMask(RegClass, RegsAvailableCopy); 376 RegsAvailableCopy &= RegsAvailable; 377 378 // If looking for a non-callee-saved register, mask off all the callee-saved 379 // registers. 380 if (ExCalleeSaved) 381 RegsAvailableCopy &= ~CalleeSavedRegs; 382 383 // Returns the first unused (bit is set) register, or 0 is none is found. 384 int Reg = RegsAvailableCopy.find_first(); 385 return (Reg == -1) ? 0 : Reg; 386} 387 388/// findFirstUse - Calculate the distance to the first use of the 389/// specified register. 390MachineInstr* 391RegScavenger::findFirstUse(MachineBasicBlock *MBB, 392 MachineBasicBlock::iterator I, unsigned Reg, 393 unsigned &Dist) { 394 MachineInstr *UseMI = 0; 395 Dist = ~0U; 396 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 397 RE = MRI->reg_end(); RI != RE; ++RI) { 398 MachineInstr *UDMI = &*RI; 399 if (UDMI->getParent() != MBB) 400 continue; 401 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 402 if (DI == DistanceMap.end()) { 403 // If it's not in map, it's below current MI, let's initialize the 404 // map. 405 I = next(I); 406 unsigned Dist = CurrDist + 1; 407 while (I != MBB->end()) { 408 DistanceMap.insert(std::make_pair(I, Dist++)); 409 I = next(I); 410 } 411 } 412 DI = DistanceMap.find(UDMI); 413 if (DI->second > CurrDist && DI->second < Dist) { 414 Dist = DI->second; 415 UseMI = UDMI; 416 } 417 } 418 return UseMI; 419} 420 421unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 422 MachineBasicBlock::iterator I, 423 int SPAdj) { 424 assert(ScavengingFrameIndex >= 0 && 425 "Cannot scavenge a register without an emergency spill slot!"); 426 427 // Mask off the registers which are not in the TargetRegisterClass. 428 BitVector Candidates(NumPhysRegs, false); 429 CreateRegClassMask(RC, Candidates); 430 Candidates ^= ReservedRegs; // Do not include reserved registers. 431 432 // Exclude all the registers being used by the instruction. 433 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 434 MachineOperand &MO = I->getOperand(i); 435 if (MO.isReg()) 436 Candidates.reset(MO.getReg()); 437 } 438 439 // Find the register whose use is furthest away. 440 unsigned SReg = 0; 441 unsigned MaxDist = 0; 442 MachineInstr *MaxUseMI = 0; 443 int Reg = Candidates.find_first(); 444 while (Reg != -1) { 445 unsigned Dist; 446 MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 447 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 448 unsigned AsDist; 449 MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 450 if (AsDist < Dist) { 451 Dist = AsDist; 452 UseMI = AsUseMI; 453 } 454 } 455 if (Dist >= MaxDist) { 456 MaxDist = Dist; 457 MaxUseMI = UseMI; 458 SReg = Reg; 459 } 460 Reg = Candidates.find_next(Reg); 461 } 462 463 if (ScavengedReg != 0) { 464 assert(0 && "Scavenger slot is live, unable to scavenge another register!"); 465 abort(); 466 } 467 468 // Spill the scavenged register before I. 469 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 470 MachineBasicBlock::iterator II = prior(I); 471 TRI->eliminateFrameIndex(II, SPAdj, this); 472 473 // Restore the scavenged register before its use (or first terminator). 474 II = MaxUseMI 475 ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator(); 476 TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC); 477 ScavengeRestore = prior(II); 478 ScavengedReg = SReg; 479 ScavengedRC = RC; 480 481 return SReg; 482} 483