RegisterScavenging.cpp revision 6130f66eaae89f8878590796977678afa8448926
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 register at any point in a machine basic block. 12// It also provides a mechanism to make registers availbale by evicting them 13// to 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/Target/TargetRegisterInfo.h" 23#include "llvm/Target/TargetInstrInfo.h" 24#include "llvm/Target/TargetMachine.h" 25#include "llvm/ADT/STLExtras.h" 26using namespace llvm; 27 28/// setUsed - Set the register and its sub-registers as being used. 29void RegScavenger::setUsed(unsigned Reg) { 30 RegsAvailable.reset(Reg); 31 32 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 33 unsigned SubReg = *SubRegs; ++SubRegs) 34 RegsAvailable.reset(SubReg); 35} 36 37/// setUnused - Set the register and its sub-registers as being unused. 38void RegScavenger::setUnused(unsigned Reg) { 39 RegsAvailable.set(Reg); 40 41 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 42 unsigned SubReg = *SubRegs; ++SubRegs) 43 RegsAvailable.set(SubReg); 44} 45 46void RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 47 const MachineFunction &MF = *mbb->getParent(); 48 const TargetMachine &TM = MF.getTarget(); 49 TII = TM.getInstrInfo(); 50 TRI = TM.getRegisterInfo(); 51 52 assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 53 "Target changed?"); 54 55 if (!MBB) { 56 NumPhysRegs = TRI->getNumRegs(); 57 RegsAvailable.resize(NumPhysRegs); 58 59 // Create reserved registers bitvector. 60 ReservedRegs = TRI->getReservedRegs(MF); 61 62 // Create callee-saved registers bitvector. 63 CalleeSavedRegs.resize(NumPhysRegs); 64 const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 65 if (CSRegs != NULL) 66 for (unsigned i = 0; CSRegs[i]; ++i) 67 CalleeSavedRegs.set(CSRegs[i]); 68 } 69 70 MBB = mbb; 71 ScavengedReg = 0; 72 ScavengedRC = NULL; 73 74 // All registers started out unused. 75 RegsAvailable.set(); 76 77 // Reserved registers are always used. 78 RegsAvailable ^= ReservedRegs; 79 80 // Live-in registers are in use. 81 if (!MBB->livein_empty()) 82 for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(), 83 E = MBB->livein_end(); I != E; ++I) 84 setUsed(*I); 85 86 Tracking = false; 87} 88 89void RegScavenger::restoreScavengedReg() { 90 if (!ScavengedReg) 91 return; 92 93 TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 94 ScavengingFrameIndex, ScavengedRC); 95 MachineBasicBlock::iterator II = prior(MBBI); 96 TRI->eliminateFrameIndex(II, 0, this); 97 setUsed(ScavengedReg); 98 ScavengedReg = 0; 99 ScavengedRC = NULL; 100} 101 102void RegScavenger::forward() { 103 // Move ptr forward. 104 if (!Tracking) { 105 MBBI = MBB->begin(); 106 Tracking = true; 107 } else { 108 assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 109 MBBI = next(MBBI); 110 } 111 112 MachineInstr *MI = MBBI; 113 const TargetInstrDesc &TID = MI->getDesc(); 114 115 // Reaching a terminator instruction. Restore a scavenged register (which 116 // must be life out. 117 if (TID.isTerminator()) 118 restoreScavengedReg(); 119 120 // Process uses first. 121 BitVector ChangedRegs(NumPhysRegs); 122 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 123 const MachineOperand &MO = MI->getOperand(i); 124 if (!MO.isRegister() || !MO.isUse()) 125 continue; 126 127 unsigned Reg = MO.getReg(); 128 if (Reg == 0) continue; 129 130 if (!isUsed(Reg)) { 131 // Register has been scavenged. Restore it! 132 if (Reg != ScavengedReg) 133 assert(false && "Using an undefined register!"); 134 else 135 restoreScavengedReg(); 136 } 137 138 if (MO.isKill() && !isReserved(Reg)) { 139 ChangedRegs.set(Reg); 140 141 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 142 unsigned SubReg = *SubRegs; ++SubRegs) 143 ChangedRegs.set(SubReg); 144 } 145 } 146 147 // Change states of all registers after all the uses are processed to guard 148 // against multiple uses. 149 setUnused(ChangedRegs); 150 151 // Process defs. 152 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 153 const MachineOperand &MO = MI->getOperand(i); 154 155 if (!MO.isRegister() || !MO.isDef()) 156 continue; 157 158 unsigned Reg = MO.getReg(); 159 160 // If it's dead upon def, then it is now free. 161 if (MO.isDead()) { 162 setUnused(Reg); 163 continue; 164 } 165 166 // Skip two-address destination operand. 167 if (TID.findTiedToSrcOperand(i) != -1) { 168 assert(isUsed(Reg) && "Using an undefined register!"); 169 continue; 170 } 171 172 assert((isUnused(Reg) || isReserved(Reg)) && 173 "Re-defining a live register!"); 174 setUsed(Reg); 175 } 176} 177 178void RegScavenger::backward() { 179 assert(Tracking && "Not tracking states!"); 180 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 181 // Move ptr backward. 182 MBBI = prior(MBBI); 183 184 MachineInstr *MI = MBBI; 185 // Process defs first. 186 const TargetInstrDesc &TID = MI->getDesc(); 187 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 188 const MachineOperand &MO = MI->getOperand(i); 189 if (!MO.isRegister() || !MO.isDef()) 190 continue; 191 // Skip two-address destination operand. 192 if (TID.findTiedToSrcOperand(i) != -1) 193 continue; 194 unsigned Reg = MO.getReg(); 195 assert(isUsed(Reg)); 196 if (!isReserved(Reg)) 197 setUnused(Reg); 198 } 199 200 // Process uses. 201 BitVector ChangedRegs(NumPhysRegs); 202 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 203 const MachineOperand &MO = MI->getOperand(i); 204 if (!MO.isRegister() || !MO.isUse()) 205 continue; 206 unsigned Reg = MO.getReg(); 207 if (Reg == 0) 208 continue; 209 assert(isUnused(Reg) || isReserved(Reg)); 210 ChangedRegs.set(Reg); 211 212 // Set the sub-registers as "used". 213 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 214 unsigned SubReg = *SubRegs; ++SubRegs) 215 ChangedRegs.set(SubReg); 216 } 217 setUsed(ChangedRegs); 218} 219 220void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 221 if (includeReserved) 222 used = ~RegsAvailable; 223 else 224 used = ~RegsAvailable & ~ReservedRegs; 225} 226 227/// CreateRegClassMask - Set the bits that represent the registers in the 228/// TargetRegisterClass. 229static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 230 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 231 ++I) 232 Mask.set(*I); 233} 234 235unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 236 const BitVector &Candidates) const { 237 // Mask off the registers which are not in the TargetRegisterClass. 238 BitVector RegsAvailableCopy(NumPhysRegs, false); 239 CreateRegClassMask(RegClass, RegsAvailableCopy); 240 RegsAvailableCopy &= RegsAvailable; 241 242 // Restrict the search to candidates. 243 RegsAvailableCopy &= Candidates; 244 245 // Returns the first unused (bit is set) register, or 0 is none is found. 246 int Reg = RegsAvailableCopy.find_first(); 247 return (Reg == -1) ? 0 : Reg; 248} 249 250unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 251 bool ExCalleeSaved) const { 252 // Mask off the registers which are not in the TargetRegisterClass. 253 BitVector RegsAvailableCopy(NumPhysRegs, false); 254 CreateRegClassMask(RegClass, RegsAvailableCopy); 255 RegsAvailableCopy &= RegsAvailable; 256 257 // If looking for a non-callee-saved register, mask off all the callee-saved 258 // registers. 259 if (ExCalleeSaved) 260 RegsAvailableCopy &= ~CalleeSavedRegs; 261 262 // Returns the first unused (bit is set) register, or 0 is none is found. 263 int Reg = RegsAvailableCopy.find_first(); 264 return (Reg == -1) ? 0 : Reg; 265} 266 267/// calcDistanceToUse - Calculate the distance to the first use of the 268/// specified register. 269static unsigned calcDistanceToUse(MachineBasicBlock *MBB, 270 MachineBasicBlock::iterator I, unsigned Reg, 271 const TargetRegisterInfo *TRI) { 272 unsigned Dist = 0; 273 I = next(I); 274 while (I != MBB->end()) { 275 Dist++; 276 if (I->readsRegister(Reg, TRI)) 277 return Dist; 278 I = next(I); 279 } 280 return Dist + 1; 281} 282 283unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 284 MachineBasicBlock::iterator I, 285 int SPAdj) { 286 assert(ScavengingFrameIndex >= 0 && 287 "Cannot scavenge a register without an emergency spill slot!"); 288 289 // Mask off the registers which are not in the TargetRegisterClass. 290 BitVector Candidates(NumPhysRegs, false); 291 CreateRegClassMask(RC, Candidates); 292 Candidates ^= ReservedRegs; // Do not include reserved registers. 293 294 // Exclude all the registers being used by the instruction. 295 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 296 MachineOperand &MO = I->getOperand(i); 297 if (MO.isRegister()) 298 Candidates.reset(MO.getReg()); 299 } 300 301 // Find the register whose use is furthest away. 302 unsigned SReg = 0; 303 unsigned MaxDist = 0; 304 int Reg = Candidates.find_first(); 305 while (Reg != -1) { 306 unsigned Dist = calcDistanceToUse(MBB, I, Reg, TRI); 307 if (Dist >= MaxDist) { 308 MaxDist = Dist; 309 SReg = Reg; 310 } 311 Reg = Candidates.find_next(Reg); 312 } 313 314 if (ScavengedReg != 0) { 315 // First restore previously scavenged register. 316 TII->loadRegFromStackSlot(*MBB, I, ScavengedReg, 317 ScavengingFrameIndex, ScavengedRC); 318 MachineBasicBlock::iterator II = prior(I); 319 TRI->eliminateFrameIndex(II, SPAdj, this); 320 } 321 322 TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC); 323 MachineBasicBlock::iterator II = prior(I); 324 TRI->eliminateFrameIndex(II, SPAdj, this); 325 ScavengedReg = SReg; 326 ScavengedRC = RC; 327 328 return SReg; 329} 330