RegisterScavenging.cpp revision 5d3600f5766e93cb459ef6108fba00c052aa6388
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.isRegister()) 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 return SeenSuperDef && SeenSuperUse; 48} 49 50static bool RedefinesSuperRegPart(const MachineInstr *MI, 51 const MachineOperand &MO, 52 const TargetRegisterInfo *TRI) { 53 assert(MO.isRegister() && MO.isDef() && "Not a register def!"); 54 return RedefinesSuperRegPart(MI, MO.getReg(), TRI); 55} 56 57/// setUsed - Set the register and its sub-registers as being used. 58void RegScavenger::setUsed(unsigned Reg, bool ImpDef) { 59 RegsAvailable.reset(Reg); 60 ImplicitDefed[Reg] = ImpDef; 61 62 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 63 unsigned SubReg = *SubRegs; ++SubRegs) { 64 RegsAvailable.reset(SubReg); 65 ImplicitDefed[SubReg] = ImpDef; 66 } 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 ImplicitDefed.reset(Reg); 73 74 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 75 unsigned SubReg = *SubRegs; ++SubRegs) 76 if (!RedefinesSuperRegPart(MI, Reg, TRI)) { 77 RegsAvailable.set(SubReg); 78 ImplicitDefed.reset(SubReg); 79 } 80} 81 82void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 83 const MachineFunction &MF = *mbb->getParent(); 84 const TargetMachine &TM = MF.getTarget(); 85 TII = TM.getInstrInfo(); 86 TRI = TM.getRegisterInfo(); 87 MRI = &MF.getRegInfo(); 88 89 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 90 "Target changed?"); 91 92 if (!MBB) { 93 NumPhysRegs = TRI->getNumRegs(); 94 RegsAvailable.resize(NumPhysRegs); 95 ImplicitDefed.resize(NumPhysRegs); 96 97 // Create reserved registers bitvector. 98 ReservedRegs = TRI->getReservedRegs(MF); 99 100 // Create callee-saved registers bitvector. 101 CalleeSavedRegs.resize(NumPhysRegs); 102 const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 103 if (CSRegs != NULL) 104 for (unsigned i = 0; CSRegs[i]; ++i) 105 CalleeSavedRegs.set(CSRegs[i]); 106 } 107 108 MBB = mbb; 109 ScavengedReg = 0; 110 ScavengedRC = NULL; 111 112 // All registers started out unused. 113 RegsAvailable.set(); 114 115 // Reserved registers are always used. 116 RegsAvailable ^= ReservedRegs; 117 118 // Live-in registers are in use. 119 if (!MBB->livein_empty()) 120 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 121 E = MBB->livein_end(); I != E; ++I) 122 setUsed(*I); 123 124 Tracking = false; 125} 126 127void RegScavenger::restoreScavengedReg() { 128 if (!ScavengedReg) 129 return; 130 131 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 132 ScavengingFrameIndex, ScavengedRC); 133 MachineBasicBlock::iterator II = prior(MBBI); 134 TRI->eliminateFrameIndex(II, 0, this); 135 setUsed(ScavengedReg); 136 ScavengedReg = 0; 137 ScavengedRC = NULL; 138} 139 140/// isLiveInButUnusedBefore - Return true if register is livein the MBB not 141/// not used before it reaches the MI that defines register. 142static bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI, 143 MachineBasicBlock *MBB, 144 const TargetRegisterInfo *TRI, 145 MachineRegisterInfo* MRI) { 146 // First check if register is livein. 147 bool isLiveIn = false; 148 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 149 E = MBB->livein_end(); I != E; ++I) 150 if (Reg == *I || TRI->isSuperRegister(Reg, *I)) { 151 isLiveIn = true; 152 break; 153 } 154 if (!isLiveIn) 155 return false; 156 157 // Is there any use of it before the specified MI? 158 SmallPtrSet<MachineInstr*, 4> UsesInMBB; 159 for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), 160 UE = MRI->use_end(); UI != UE; ++UI) { 161 MachineInstr *UseMI = &*UI; 162 if (UseMI->getParent() == MBB) 163 UsesInMBB.insert(UseMI); 164 } 165 if (UsesInMBB.empty()) 166 return true; 167 168 for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I) 169 if (UsesInMBB.count(&*I)) 170 return false; 171 return true; 172} 173 174void RegScavenger::forward() { 175 // Move ptr forward. 176 if (!Tracking) { 177 MBBI = MBB->begin(); 178 Tracking = true; 179 } else { 180 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 181 MBBI = next(MBBI); 182 } 183 184 MachineInstr *MI = MBBI; 185 const TargetInstrDesc &TID = MI->getDesc(); 186 187 // Reaching a terminator instruction. Restore a scavenged register (which 188 // must be life out. 189 if (TID.isTerminator()) 190 restoreScavengedReg(); 191 192 // Process uses first. 193 BitVector ChangedRegs(NumPhysRegs); 194 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 195 const MachineOperand &MO = MI->getOperand(i); 196 if (!MO.isRegister() || !MO.isUse()) 197 continue; 198 199 unsigned Reg = MO.getReg(); 200 if (Reg == 0) continue; 201 202 if (!isUsed(Reg)) { 203 // Register has been scavenged. Restore it! 204 if (Reg != ScavengedReg) 205 assert(false && "Using an undefined register!"); 206 else 207 restoreScavengedReg(); 208 } 209 210 if (MO.isKill() && !isReserved(Reg)) { 211 ChangedRegs.set(Reg); 212 213 // Mark sub-registers as changed if they aren't defined in the same 214 // instruction. 215 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 216 unsigned SubReg = *SubRegs; ++SubRegs) 217 ChangedRegs.set(SubReg); 218 } 219 } 220 221 // Change states of all registers after all the uses are processed to guard 222 // against multiple uses. 223 setUnused(ChangedRegs); 224 225 // Process defs. 226 bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 227 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 228 const MachineOperand &MO = MI->getOperand(i); 229 230 if (!MO.isRegister() || !MO.isDef()) 231 continue; 232 233 unsigned Reg = MO.getReg(); 234 235 // If it's dead upon def, then it is now free. 236 if (MO.isDead()) { 237 setUnused(Reg, MI); 238 continue; 239 } 240 241 // Skip two-address destination operand. 242 if (TID.findTiedToSrcOperand(i) != -1) { 243 assert(isUsed(Reg) && "Using an undefined register!"); 244 continue; 245 } 246 247 // Skip is this is merely redefining part of a super-register. 248 if (RedefinesSuperRegPart(MI, MO, TRI)) 249 continue; 250 251 // Implicit def is allowed to "re-define" any register. Similarly, 252 // implicitly defined registers can be clobbered. 253 assert((isReserved(Reg) || isUnused(Reg) || 254 IsImpDef || isImplicitlyDefined(Reg) || 255 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 256 "Re-defining a live register!"); 257 setUsed(Reg, IsImpDef); 258 } 259} 260 261void RegScavenger::backward() { 262 assert(Tracking && "Not tracking states!"); 263 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 264 // Move ptr backward. 265 MBBI = prior(MBBI); 266 267 MachineInstr *MI = MBBI; 268 // Process defs first. 269 const TargetInstrDesc &TID = MI->getDesc(); 270 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 271 const MachineOperand &MO = MI->getOperand(i); 272 if (!MO.isRegister() || !MO.isDef()) 273 continue; 274 // Skip two-address destination operand. 275 if (TID.findTiedToSrcOperand(i) != -1) 276 continue; 277 unsigned Reg = MO.getReg(); 278 assert(isUsed(Reg)); 279 if (!isReserved(Reg)) 280 setUnused(Reg, MI); 281 } 282 283 // Process uses. 284 BitVector ChangedRegs(NumPhysRegs); 285 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 286 const MachineOperand &MO = MI->getOperand(i); 287 if (!MO.isRegister() || !MO.isUse()) 288 continue; 289 unsigned Reg = MO.getReg(); 290 if (Reg == 0) 291 continue; 292 assert(isUnused(Reg) || isReserved(Reg)); 293 ChangedRegs.set(Reg); 294 295 // Set the sub-registers as "used". 296 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 297 unsigned SubReg = *SubRegs; ++SubRegs) 298 ChangedRegs.set(SubReg); 299 } 300 setUsed(ChangedRegs); 301} 302 303void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 304 if (includeReserved) 305 used = ~RegsAvailable; 306 else 307 used = ~RegsAvailable & ~ReservedRegs; 308} 309 310/// CreateRegClassMask - Set the bits that represent the registers in the 311/// TargetRegisterClass. 312static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 313 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 314 ++I) 315 Mask.set(*I); 316} 317 318unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 319 const BitVector &Candidates) const { 320 // Mask off the registers which are not in the TargetRegisterClass. 321 BitVector RegsAvailableCopy(NumPhysRegs, false); 322 CreateRegClassMask(RegClass, RegsAvailableCopy); 323 RegsAvailableCopy &= RegsAvailable; 324 325 // Restrict the search to candidates. 326 RegsAvailableCopy &= Candidates; 327 328 // Returns the first unused (bit is set) register, or 0 is none is found. 329 int Reg = RegsAvailableCopy.find_first(); 330 return (Reg == -1) ? 0 : Reg; 331} 332 333unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 334 bool ExCalleeSaved) const { 335 // Mask off the registers which are not in the TargetRegisterClass. 336 BitVector RegsAvailableCopy(NumPhysRegs, false); 337 CreateRegClassMask(RegClass, RegsAvailableCopy); 338 RegsAvailableCopy &= RegsAvailable; 339 340 // If looking for a non-callee-saved register, mask off all the callee-saved 341 // registers. 342 if (ExCalleeSaved) 343 RegsAvailableCopy &= ~CalleeSavedRegs; 344 345 // Returns the first unused (bit is set) register, or 0 is none is found. 346 int Reg = RegsAvailableCopy.find_first(); 347 return (Reg == -1) ? 0 : Reg; 348} 349 350/// calcDistanceToUse - Calculate the distance to the first use of the 351/// specified register. 352static unsigned calcDistanceToUse(MachineBasicBlock *MBB, 353 MachineBasicBlock::iterator I, unsigned Reg, 354 const TargetRegisterInfo *TRI) { 355 unsigned Dist = 0; 356 I = next(I); 357 while (I != MBB->end()) { 358 Dist++; 359 if (I->readsRegister(Reg, TRI)) 360 return Dist; 361 I = next(I); 362 } 363 return Dist + 1; 364} 365 366unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 367 MachineBasicBlock::iterator I, 368 int SPAdj) { 369 assert(ScavengingFrameIndex >= 0 && 370 "Cannot scavenge a register without an emergency spill slot!"); 371 372 // Mask off the registers which are not in the TargetRegisterClass. 373 BitVector Candidates(NumPhysRegs, false); 374 CreateRegClassMask(RC, Candidates); 375 Candidates ^= ReservedRegs; // Do not include reserved registers. 376 377 // Exclude all the registers being used by the instruction. 378 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 379 MachineOperand &MO = I->getOperand(i); 380 if (MO.isRegister()) 381 Candidates.reset(MO.getReg()); 382 } 383 384 // Find the register whose use is furthest away. 385 unsigned SReg = 0; 386 unsigned MaxDist = 0; 387 int Reg = Candidates.find_first(); 388 while (Reg != -1) { 389 unsigned Dist = calcDistanceToUse(MBB, I, Reg, TRI); 390 if (Dist >= MaxDist) { 391 MaxDist = Dist; 392 SReg = Reg; 393 } 394 Reg = Candidates.find_next(Reg); 395 } 396 397 if (ScavengedReg != 0) { 398 // First restore previously scavenged register. 399 TII->loadRegFromStackSlot(*MBB, I, ScavengedReg, 400 ScavengingFrameIndex, ScavengedRC); 401 MachineBasicBlock::iterator II = prior(I); 402 TRI->eliminateFrameIndex(II, SPAdj, this); 403 } 404 405 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 406 MachineBasicBlock::iterator II = prior(I); 407 TRI->eliminateFrameIndex(II, SPAdj, this); 408 ScavengedReg = SReg; 409 ScavengedRC = RC; 410 411 return SReg; 412} 413