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