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