RegisterScavenging.cpp revision faa510726f4b40aa4495e60e4d341c6467e3fb01
1//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the Evan Cheng and is distributed under the 6// University of Illinois Open Source 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/MRegisterInfo.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 RegInfo->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg, 76 ScavengingFrameIndex, ScavengedRC); 77 MachineBasicBlock::iterator II = prior(MBBI); 78 RegInfo->eliminateFrameIndex(II, 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 96 // Reaching a terminator instruction. Restore a scavenged register (which 97 // must be life out. 98 if (TII->isTerminatorInstr(MI->getOpcode())) 99 restoreScavengedReg(); 100 101 // Process uses first. 102 BitVector ChangedRegs(NumPhysRegs); 103 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 104 const MachineOperand &MO = MI->getOperand(i); 105 if (!MO.isReg() || !MO.isUse()) 106 continue; 107 unsigned Reg = MO.getReg(); 108 if (Reg == 0) 109 continue; 110 if (!isUsed(Reg)) { 111 // Register has been scavenged. Restore it! 112 if (Reg != ScavengedReg) 113 assert(false); 114 else 115 restoreScavengedReg(); 116 } 117 if (MO.isKill() && !isReserved(Reg)) 118 ChangedRegs.set(Reg); 119 } 120 // Change states of all registers after all the uses are processed to guard 121 // against multiple uses. 122 setUnused(ChangedRegs); 123 124 // Process defs. 125 const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 126 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 127 const MachineOperand &MO = MI->getOperand(i); 128 if (!MO.isReg() || !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)); 139 continue; 140 } 141 assert(isUnused(Reg) || isReserved(Reg)); 142 setUsed(Reg); 143 } 144} 145 146void RegScavenger::backward() { 147 assert(Tracking && "Not tracking states!"); 148 assert(MBBI != MBB->begin() && "Already at start of basic block!"); 149 // Move ptr backward. 150 MBBI = prior(MBBI); 151 152 MachineInstr *MI = MBBI; 153 // Process defs first. 154 const TargetInstrDescriptor *TID = MI->getInstrDescriptor(); 155 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 156 const MachineOperand &MO = MI->getOperand(i); 157 if (!MO.isReg() || !MO.isDef()) 158 continue; 159 // Skip two-address destination operand. 160 if (TID->findTiedToSrcOperand(i) != -1) 161 continue; 162 unsigned Reg = MO.getReg(); 163 assert(isUsed(Reg)); 164 if (!isReserved(Reg)) 165 setUnused(Reg); 166 } 167 168 // Process uses. 169 BitVector ChangedRegs(NumPhysRegs); 170 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 171 const MachineOperand &MO = MI->getOperand(i); 172 if (!MO.isReg() || !MO.isUse()) 173 continue; 174 unsigned Reg = MO.getReg(); 175 if (Reg == 0) 176 continue; 177 assert(isUnused(Reg) || isReserved(Reg)); 178 ChangedRegs.set(Reg); 179 } 180 setUsed(ChangedRegs); 181} 182 183void RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 184 if (includeReserved) 185 used = ~RegsAvailable; 186 else 187 used = ~RegsAvailable & ~ReservedRegs; 188} 189 190/// CreateRegClassMask - Set the bits that represent the registers in the 191/// TargetRegisterClass. 192static void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) { 193 for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E; 194 ++I) 195 Mask.set(*I); 196} 197 198unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 199 const BitVector &Candidates) const { 200 // Mask off the registers which are not in the TargetRegisterClass. 201 BitVector RegsAvailableCopy(NumPhysRegs, false); 202 CreateRegClassMask(RegClass, RegsAvailableCopy); 203 RegsAvailableCopy &= RegsAvailable; 204 205 // Restrict the search to candidates. 206 RegsAvailableCopy &= Candidates; 207 208 // Returns the first unused (bit is set) register, or 0 is none is found. 209 int Reg = RegsAvailableCopy.find_first(); 210 return (Reg == -1) ? 0 : Reg; 211} 212 213unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass, 214 bool ExCalleeSaved) const { 215 // Mask off the registers which are not in the TargetRegisterClass. 216 BitVector RegsAvailableCopy(NumPhysRegs, false); 217 CreateRegClassMask(RegClass, RegsAvailableCopy); 218 RegsAvailableCopy &= RegsAvailable; 219 220 // If looking for a non-callee-saved register, mask off all the callee-saved 221 // registers. 222 if (ExCalleeSaved) 223 RegsAvailableCopy &= ~CalleeSavedRegs; 224 225 // Returns the first unused (bit is set) register, or 0 is none is found. 226 int Reg = RegsAvailableCopy.find_first(); 227 return (Reg == -1) ? 0 : Reg; 228} 229 230/// calcDistanceToUse - Calculate the distance to the first use of the 231/// specified register. 232static unsigned calcDistanceToUse(MachineBasicBlock *MBB, 233 MachineBasicBlock::iterator I, unsigned Reg) { 234 unsigned Dist = 0; 235 I = next(I); 236 while (I != MBB->end()) { 237 Dist++; 238 if (I->findRegisterUseOperandIdx(Reg) != -1) 239 return Dist; 240 I = next(I); 241 } 242 return Dist + 1; 243} 244 245unsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 246 MachineBasicBlock::iterator I) { 247 assert(ScavengingFrameIndex >= 0 && 248 "Cannot scavenge a register without an emergency spill slot!"); 249 250 // Mask off the registers which are not in the TargetRegisterClass. 251 BitVector Candidates(NumPhysRegs, false); 252 CreateRegClassMask(RC, Candidates); 253 Candidates ^= ReservedRegs; // Do not include reserved registers. 254 255 // Exclude all the registers being used by the instruction. 256 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 257 MachineOperand &MO = I->getOperand(i); 258 if (MO.isReg()) 259 Candidates.reset(MO.getReg()); 260 } 261 262 // Find the register whose use is furtherest aaway. 263 unsigned SReg = 0; 264 unsigned MaxDist = 0; 265 int Reg = Candidates.find_first(); 266 while (Reg != -1) { 267 unsigned Dist = calcDistanceToUse(MBB, I, Reg); 268 if (Dist >= MaxDist) { 269 MaxDist = Dist; 270 SReg = Reg; 271 } 272 Reg = Candidates.find_next(Reg); 273 } 274 275 if (ScavengedReg != 0) { 276 // First restore previously scavenged register. 277 RegInfo->loadRegFromStackSlot(*MBB, I, ScavengedReg, 278 ScavengingFrameIndex, ScavengedRC); 279 MachineBasicBlock::iterator II = prior(I); 280 RegInfo->eliminateFrameIndex(II, this); 281 } 282 283 RegInfo->storeRegToStackSlot(*MBB, I, SReg, ScavengingFrameIndex, RC); 284 MachineBasicBlock::iterator II = prior(I); 285 RegInfo->eliminateFrameIndex(II, this); 286 ScavengedReg = SReg; 287 ScavengedRC = RC; 288 289 return SReg; 290} 291