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