RegisterScavenging.cpp revision 1385758215bb31ba042a3d42e40d28e521616a0c
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 ImplicitDefed.reset(); 116 117 // All registers started out unused. 118 RegsAvailable.set(); 119 120 // Reserved registers are always used. 121 RegsAvailable ^= ReservedRegs; 122 123 // Live-in registers are in use. 124 if (!MBB->livein_empty()) 125 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 126 E = MBB->livein_end(); I != E; ++I) 127 setUsed(*I); 128 129 Tracking = false; 130} 131 132void RegScavenger::restoreScavengedReg() { 133 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 134 ScavengingFrameIndex, ScavengedRC); 135 MachineBasicBlock::iterator II = prior(MBBI); 136 TRI->eliminateFrameIndex(II, 0, this); 137 setUsed(ScavengedReg); 138 ScavengedReg = 0; 139 ScavengedRC = NULL; 140} 141 142/// isLiveInButUnusedBefore - Return true if register is livein the MBB not 143/// not used before it reaches the MI that defines register. 144static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 145 MachineBasicBlock *MBB, 146 const TargetRegisterInfo *TRI, 147 MachineRegisterInfo* MRI) { 148 // First check if register is livein. 149 bool isLiveIn = false; 150 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 151 E = MBB->livein_end(); I != E; ++I) 152 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 153 isLiveIn = true; 154 break; 155 } 156 if (!isLiveIn) 157 return false; 158 159 // Is there any use of it before the specified MI? 160 SmallPtrSet<MachineInstr*, 4> UsesInMBB; 161 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 162 UE = MRI->use_end(); UI != UE; ++UI) { 163 MachineInstr *UseMI = &*UI; 164 if (UseMI->getParent() == MBB) 165 UsesInMBB.insert(UseMI); 166 } 167 if (UsesInMBB.empty()) 168 return true; 169 170 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 171 if (UsesInMBB.count(&*I)) 172 return false; 173 return true; 174} 175 176void RegScavenger::forward() { 177 // Move ptr forward. 178 if (!Tracking) { 179 MBBI = MBB->begin(); 180 Tracking = true; 181 } else { 182 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 183 MBBI = next(MBBI); 184 } 185 186 MachineInstr *MI = MBBI; 187 DistanceMap.insert(std::make_pair(MI, CurrDist++)); 188 const TargetInstrDesc &TID = MI->getDesc(); 189 190 if (MI == ScavengeRestore) { 191 ScavengedReg = 0; 192 ScavengedRC = NULL; 193 ScavengeRestore = NULL; 194 } 195 196 bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 197 198 // Separate register operands into 3 classes: uses, defs, earlyclobbers. 199 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs; 200 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs; 201 SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs; 202 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 203 const MachineOperand &MO = MI->getOperand(i); 204 if (!MO.isReg() || MO.getReg() == 0) 205 continue; 206 if (MO.isUse()) 207 UseMOs.push_back(std::make_pair(&MO,i)); 208 else if (MO.isEarlyClobber()) 209 EarlyClobberMOs.push_back(std::make_pair(&MO,i)); 210 else 211 DefMOs.push_back(std::make_pair(&MO,i)); 212 } 213 214 // Process uses first. 215 BitVector UseRegs(NumPhysRegs); 216 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 217 const MachineOperand MO = *UseMOs[i].first; 218 unsigned Reg = MO.getReg(); 219 220 assert(isUsed(Reg) && "Using an undefined register!"); 221 222 if (MO.isKill() && !isReserved(Reg)) { 223 UseRegs.set(Reg); 224 225 // Mark sub-registers as used. 226 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 227 unsigned SubReg = *SubRegs; ++SubRegs) 228 UseRegs.set(SubReg); 229 } 230 } 231 232 // Change states of all registers after all the uses are processed to guard 233 // against multiple uses. 234 setUnused(UseRegs); 235 236 // Process early clobber defs then process defs. We can have a early clobber 237 // that is dead, it should not conflict with a def that happens one "slot" 238 // (see InstrSlots in LiveIntervalAnalysis.h) later. 239 unsigned NumECs = EarlyClobberMOs.size(); 240 unsigned NumDefs = DefMOs.size(); 241 242 for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) { 243 const MachineOperand &MO = (i < NumECs) 244 ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first; 245 unsigned Idx = (i < NumECs) 246 ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second; 247 unsigned Reg = MO.getReg(); 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 if (TID.findTiedToSrcOperand(Idx) != -1) { 257 assert(isUsed(Reg) && "Using an undefined register!"); 258 continue; 259 } 260 261 // Skip if this is merely redefining part of a super-register. 262 if (RedefinesSuperRegPart(MI, MO, TRI)) 263 continue; 264 265 // Implicit def is allowed to "re-define" any register. Similarly, 266 // implicitly defined registers can be clobbered. 267 assert((isReserved(Reg) || isUnused(Reg) || 268 IsImpDef || isImplicitlyDefined(Reg) || 269 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 270 "Re-defining a live register!"); 271 setUsed(Reg, IsImpDef); 272 } 273} 274 275void RegScavenger::backward() { 276 assert(Tracking && "Not tracking states!"); 277 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 278 // Move ptr backward. 279 MBBI = prior(MBBI); 280 281 MachineInstr *MI = MBBI; 282 DistanceMap.erase(MI); 283 --CurrDist; 284 const TargetInstrDesc &TID = MI->getDesc(); 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) 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 312 // Skip two-address destination operand. 313 if (TID.findTiedToSrcOperand(Idx) != -1) 314 continue; 315 316 unsigned Reg = MO.getReg(); 317 assert(isUsed(Reg)); 318 if (!isReserved(Reg)) 319 setUnused(Reg, MI); 320 } 321 322 // Process uses. 323 BitVector UseRegs(NumPhysRegs); 324 for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) { 325 const MachineOperand MO = *UseMOs[i].first; 326 unsigned Reg = MO.getReg(); 327 assert(isUnused(Reg) || isReserved(Reg)); 328 UseRegs.set(Reg); 329 330 // Set the sub-registers as "used". 331 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 332 unsigned SubReg = *SubRegs; ++SubRegs) 333 UseRegs.set(SubReg); 334 } 335 setUsed(UseRegs); 336} 337 338void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 339 if (includeReserved) 340 used = ~RegsAvailable; 341 else 342 used = ~RegsAvailable & ~ReservedRegs; 343} 344 345/// CreateRegClassMask - Set the bits that represent the registers in the 346/// TargetRegisterClass. 347static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 348 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 349 ++I) 350 Mask.set(*I); 351} 352 353unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 354 const BitVector &Candidates) const { 355 // Mask off the registers which are not in the TargetRegisterClass. 356 BitVector RegsAvailableCopy(NumPhysRegs, false); 357 CreateRegClassMask(RegClass, RegsAvailableCopy); 358 RegsAvailableCopy &= RegsAvailable; 359 360 // Restrict the search to candidates. 361 RegsAvailableCopy &= Candidates; 362 363 // Returns the first unused (bit is set) register, or 0 is none is found. 364 int Reg = RegsAvailableCopy.find_first(); 365 return (Reg == -1) ? 0 : Reg; 366} 367 368unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 369 bool ExCalleeSaved) const { 370 // Mask off the registers which are not in the TargetRegisterClass. 371 BitVector RegsAvailableCopy(NumPhysRegs, false); 372 CreateRegClassMask(RegClass, RegsAvailableCopy); 373 RegsAvailableCopy &= RegsAvailable; 374 375 // If looking for a non-callee-saved register, mask off all the callee-saved 376 // registers. 377 if (ExCalleeSaved) 378 RegsAvailableCopy &= ~CalleeSavedRegs; 379 380 // Returns the first unused (bit is set) register, or 0 is none is found. 381 int Reg = RegsAvailableCopy.find_first(); 382 return (Reg == -1) ? 0 : Reg; 383} 384 385/// findFirstUse - Calculate the distance to the first use of the 386/// specified register. 387MachineInstr* 388RegScavenger::findFirstUse(MachineBasicBlock *MBB, 389 MachineBasicBlock::iterator I, unsigned Reg, 390 unsigned &Dist) { 391 MachineInstr *UseMI = 0; 392 Dist = ~0U; 393 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 394 RE = MRI->reg_end(); RI != RE; ++RI) { 395 MachineInstr *UDMI = &*RI; 396 if (UDMI->getParent() != MBB) 397 continue; 398 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 399 if (DI == DistanceMap.end()) { 400 // If it's not in map, it's below current MI, let's initialize the 401 // map. 402 I = next(I); 403 unsigned Dist = CurrDist + 1; 404 while (I != MBB->end()) { 405 DistanceMap.insert(std::make_pair(I, Dist++)); 406 I = next(I); 407 } 408 } 409 DI = DistanceMap.find(UDMI); 410 if (DI->second > CurrDist && DI->second < Dist) { 411 Dist = DI->second; 412 UseMI = UDMI; 413 } 414 } 415 return UseMI; 416} 417 418unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 419 MachineBasicBlock::iterator I, 420 int SPAdj) { 421 assert(ScavengingFrameIndex >= 0 && 422 "Cannot scavenge a register without an emergency spill slot!"); 423 424 // Mask off the registers which are not in the TargetRegisterClass. 425 BitVector Candidates(NumPhysRegs, false); 426 CreateRegClassMask(RC, Candidates); 427 Candidates ^= ReservedRegs; // Do not include reserved registers. 428 429 // Exclude all the registers being used by the instruction. 430 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 431 MachineOperand &MO = I->getOperand(i); 432 if (MO.isReg()) 433 Candidates.reset(MO.getReg()); 434 } 435 436 // Find the register whose use is furthest away. 437 unsigned SReg = 0; 438 unsigned MaxDist = 0; 439 MachineInstr *MaxUseMI = 0; 440 int Reg = Candidates.find_first(); 441 while (Reg != -1) { 442 unsigned Dist; 443 MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist); 444 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 445 unsigned AsDist; 446 MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist); 447 if (AsDist < Dist) { 448 Dist = AsDist; 449 UseMI = AsUseMI; 450 } 451 } 452 if (Dist >= MaxDist) { 453 MaxDist = Dist; 454 MaxUseMI = UseMI; 455 SReg = Reg; 456 } 457 Reg = Candidates.find_next(Reg); 458 } 459 460 if (ScavengedReg != 0) { 461 assert(0 && "Scavenger slot is live, unable to scavenge another register!"); 462 abort(); 463 } 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