RegisterScavenging.cpp revision d735b8019b0f297d7c14b55adcd887af24d8e602
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 113 // All registers started out unused. 114 RegsAvailable.set(); 115 116 // Reserved registers are always used. 117 RegsAvailable ^= ReservedRegs; 118 119 // Live-in registers are in use. 120 if (!MBB->livein_empty()) 121 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 122 E = MBB->livein_end(); I != E; ++I) 123 setUsed(*I); 124 125 Tracking = false; 126} 127 128void RegScavenger::restoreScavengedReg() { 129 if (!ScavengedReg) 130 return; 131 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 const TargetInstrDesc &TID = MI->getDesc(); 187 188 // Reaching a terminator instruction. Restore a scavenged register (which 189 // must be life out. 190 if (TID.isTerminator()) 191 restoreScavengedReg(); 192 193 // Process uses first. 194 BitVector ChangedRegs(NumPhysRegs); 195 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 196 const MachineOperand &MO = MI->getOperand(i); 197 if (!MO.isReg() || !MO.isUse()) 198 continue; 199 200 unsigned Reg = MO.getReg(); 201 if (Reg == 0) continue; 202 203 if (!isUsed(Reg)) { 204 // Register has been scavenged. Restore it! 205 if (Reg != ScavengedReg) 206 assert(false && "Using an undefined register!"); 207 else 208 restoreScavengedReg(); 209 } 210 211 if (MO.isKill() && !isReserved(Reg)) { 212 ChangedRegs.set(Reg); 213 214 // Mark sub-registers as changed if they aren't defined in the same 215 // instruction. 216 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 217 unsigned SubReg = *SubRegs; ++SubRegs) 218 ChangedRegs.set(SubReg); 219 } 220 } 221 222 // Change states of all registers after all the uses are processed to guard 223 // against multiple uses. 224 setUnused(ChangedRegs); 225 226 // Process defs. 227 bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF; 228 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 229 const MachineOperand &MO = MI->getOperand(i); 230 231 if (!MO.isReg() || !MO.isDef()) 232 continue; 233 234 unsigned Reg = MO.getReg(); 235 236 // If it's dead upon def, then it is now free. 237 if (MO.isDead()) { 238 setUnused(Reg, MI); 239 continue; 240 } 241 242 // Skip two-address destination operand. 243 if (TID.findTiedToSrcOperand(i) != -1) { 244 assert(isUsed(Reg) && "Using an undefined register!"); 245 continue; 246 } 247 248 // Skip is this is merely redefining part of a super-register. 249 if (RedefinesSuperRegPart(MI, MO, TRI)) 250 continue; 251 252 // Implicit def is allowed to "re-define" any register. Similarly, 253 // implicitly defined registers can be clobbered. 254 assert((isReserved(Reg) || isUnused(Reg) || 255 IsImpDef || isImplicitlyDefined(Reg) || 256 isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 257 "Re-defining a live register!"); 258 setUsed(Reg, IsImpDef); 259 } 260} 261 262void RegScavenger::backward() { 263 assert(Tracking && "Not tracking states!"); 264 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 265 // Move ptr backward. 266 MBBI = prior(MBBI); 267 268 MachineInstr *MI = MBBI; 269 // Process defs first. 270 const TargetInstrDesc &TID = MI->getDesc(); 271 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 272 const MachineOperand &MO = MI->getOperand(i); 273 if (!MO.isReg() || !MO.isDef()) 274 continue; 275 // Skip two-address destination operand. 276 if (TID.findTiedToSrcOperand(i) != -1) 277 continue; 278 unsigned Reg = MO.getReg(); 279 assert(isUsed(Reg)); 280 if (!isReserved(Reg)) 281 setUnused(Reg, MI); 282 } 283 284 // Process uses. 285 BitVector ChangedRegs(NumPhysRegs); 286 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 287 const MachineOperand &MO = MI->getOperand(i); 288 if (!MO.isReg() || !MO.isUse()) 289 continue; 290 unsigned Reg = MO.getReg(); 291 if (Reg == 0) 292 continue; 293 assert(isUnused(Reg) || isReserved(Reg)); 294 ChangedRegs.set(Reg); 295 296 // Set the sub-registers as "used". 297 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 298 unsigned SubReg = *SubRegs; ++SubRegs) 299 ChangedRegs.set(SubReg); 300 } 301 setUsed(ChangedRegs); 302} 303 304void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 305 if (includeReserved) 306 used = ~RegsAvailable; 307 else 308 used = ~RegsAvailable & ~ReservedRegs; 309} 310 311/// CreateRegClassMask - Set the bits that represent the registers in the 312/// TargetRegisterClass. 313static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 314 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 315 ++I) 316 Mask.set(*I); 317} 318 319unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 320 const BitVector &Candidates) const { 321 // Mask off the registers which are not in the TargetRegisterClass. 322 BitVector RegsAvailableCopy(NumPhysRegs, false); 323 CreateRegClassMask(RegClass, RegsAvailableCopy); 324 RegsAvailableCopy &= RegsAvailable; 325 326 // Restrict the search to candidates. 327 RegsAvailableCopy &= Candidates; 328 329 // Returns the first unused (bit is set) register, or 0 is none is found. 330 int Reg = RegsAvailableCopy.find_first(); 331 return (Reg == -1) ? 0 : Reg; 332} 333 334unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 335 bool ExCalleeSaved) const { 336 // Mask off the registers which are not in the TargetRegisterClass. 337 BitVector RegsAvailableCopy(NumPhysRegs, false); 338 CreateRegClassMask(RegClass, RegsAvailableCopy); 339 RegsAvailableCopy &= RegsAvailable; 340 341 // If looking for a non-callee-saved register, mask off all the callee-saved 342 // registers. 343 if (ExCalleeSaved) 344 RegsAvailableCopy &= ~CalleeSavedRegs; 345 346 // Returns the first unused (bit is set) register, or 0 is none is found. 347 int Reg = RegsAvailableCopy.find_first(); 348 return (Reg == -1) ? 0 : Reg; 349} 350 351/// calcDistanceToUse - Calculate the distance to the first use of the 352/// specified register. 353static unsigned calcDistanceToUse(MachineBasicBlock *MBB, 354 MachineBasicBlock::iterator I, unsigned Reg, 355 const TargetRegisterInfo *TRI) { 356 unsigned Dist = 0; 357 I = next(I); 358 while (I != MBB->end()) { 359 Dist++; 360 if (I->readsRegister(Reg, TRI)) 361 return Dist; 362 I = next(I); 363 } 364 return Dist + 1; 365} 366 367unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 368 MachineBasicBlock::iterator I, 369 int SPAdj) { 370 assert(ScavengingFrameIndex >= 0 && 371 "Cannot scavenge a register without an emergency spill slot!"); 372 373 // Mask off the registers which are not in the TargetRegisterClass. 374 BitVector Candidates(NumPhysRegs, false); 375 CreateRegClassMask(RC, Candidates); 376 Candidates ^= ReservedRegs; // Do not include reserved registers. 377 378 // Exclude all the registers being used by the instruction. 379 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 380 MachineOperand &MO = I->getOperand(i); 381 if (MO.isReg()) 382 Candidates.reset(MO.getReg()); 383 } 384 385 // Find the register whose use is furthest away. 386 unsigned SReg = 0; 387 unsigned MaxDist = 0; 388 int Reg = Candidates.find_first(); 389 while (Reg != -1) { 390 unsigned Dist = calcDistanceToUse(MBB, I, Reg, TRI); 391 if (Dist >= MaxDist) { 392 MaxDist = Dist; 393 SReg = Reg; 394 } 395 Reg = Candidates.find_next(Reg); 396 } 397 398 if (ScavengedReg != 0) { 399 // First restore previously scavenged register. 400 TII->loadRegFromStackSlot(*MBB, I, ScavengedReg, 401 ScavengingFrameIndex, ScavengedRC); 402 MachineBasicBlock::iterator II = prior(I); 403 TRI->eliminateFrameIndex(II, SPAdj, this); 404 } 405 406 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 407 MachineBasicBlock::iterator II = prior(I); 408 TRI->eliminateFrameIndex(II, SPAdj, this); 409 ScavengedReg = SReg; 410 ScavengedRC = RC; 411 412 return SReg; 413} 414