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