VirtRegMap.cpp revision 26eb14ba51c8eccdb3ac69370c6ac859d3be34a4
1//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the virtual register map. It also implements 11// the eliminateVirtRegs() function that given a virtual register map 12// and a machine function it eliminates all virtual references by 13// replacing them with physical register references and adds spill 14// code as necessary. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "regalloc" 19#include "VirtRegMap.h" 20#include "llvm/Function.h" 21#include "llvm/CodeGen/MachineFrameInfo.h" 22#include "llvm/CodeGen/MachineInstr.h" 23#include "llvm/Target/TargetMachine.h" 24#include "llvm/Target/TargetInstrInfo.h" 25#include "Support/CommandLine.h" 26#include "Support/Debug.h" 27#include "Support/DenseMap.h" 28#include "Support/Statistic.h" 29#include "Support/STLExtras.h" 30 31using namespace llvm; 32 33namespace { 34 Statistic<> numSpills("spiller", "Number of register spills"); 35 Statistic<> numStores("spiller", "Number of stores added"); 36 Statistic<> numLoads ("spiller", "Number of loads added"); 37 38 enum SpillerName { simple, local }; 39 40 cl::opt<SpillerName> 41 SpillerOpt("spiller", 42 cl::desc("Spiller to use: (default: local)"), 43 cl::Prefix, 44 cl::values(clEnumVal(simple, " simple spiller"), 45 clEnumVal(local, " local spiller"), 46 clEnumValEnd), 47 cl::init(local)); 48} 49 50int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) 51{ 52 assert(MRegisterInfo::isVirtualRegister(virtReg)); 53 assert(v2ssMap_[virtReg] == NO_STACK_SLOT && 54 "attempt to assign stack slot to already spilled register"); 55 const TargetRegisterClass* RC = 56 mf_->getSSARegMap()->getRegClass(virtReg); 57 int frameIndex = mf_->getFrameInfo()->CreateStackObject(RC->getSize(), 58 RC->getAlignment()); 59 v2ssMap_[virtReg] = frameIndex; 60 ++numSpills; 61 return frameIndex; 62} 63 64void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) 65{ 66 assert(MRegisterInfo::isVirtualRegister(virtReg)); 67 assert(v2ssMap_[virtReg] == NO_STACK_SLOT && 68 "attempt to assign stack slot to already spilled register"); 69 v2ssMap_[virtReg] = frameIndex; 70} 71 72void VirtRegMap::virtFolded(unsigned virtReg, 73 MachineInstr* oldMI, 74 MachineInstr* newMI) 75{ 76 // move previous memory references folded to new instruction 77 MI2VirtMap::iterator i, e; 78 std::vector<MI2VirtMap::mapped_type> regs; 79 for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) { 80 regs.push_back(i->second); 81 mi2vMap_.erase(i++); 82 } 83 for (unsigned i = 0, e = regs.size(); i != e; ++i) 84 mi2vMap_.insert(std::make_pair(newMI, i)); 85 86 // add new memory reference 87 mi2vMap_.insert(std::make_pair(newMI, virtReg)); 88} 89 90std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm) 91{ 92 const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo(); 93 94 std::cerr << "********** REGISTER MAP **********\n"; 95 for (unsigned i = MRegisterInfo::FirstVirtualRegister, 96 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 97 if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG) 98 std::cerr << "[reg" << i << " -> " 99 << mri->getName(vrm.v2pMap_[i]) << "]\n"; 100 } 101 for (unsigned i = MRegisterInfo::FirstVirtualRegister, 102 e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 103 if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT) 104 std::cerr << "[reg" << i << " -> fi#" 105 << vrm.v2ssMap_[i] << "]\n"; 106 } 107 return std::cerr << '\n'; 108} 109 110Spiller::~Spiller() 111{ 112 113} 114 115namespace { 116 117 class SimpleSpiller : public Spiller { 118 public: 119 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) { 120 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); 121 DEBUG(std::cerr << "********** Function: " 122 << mf.getFunction()->getName() << '\n'); 123 const TargetMachine& tm = mf.getTarget(); 124 const MRegisterInfo& mri = *tm.getRegisterInfo(); 125 126 typedef DenseMap<bool, VirtReg2IndexFunctor> Loaded; 127 Loaded loaded; 128 129 for (MachineFunction::iterator mbbi = mf.begin(), 130 mbbe = mf.end(); mbbi != mbbe; ++mbbi) { 131 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); 132 for (MachineBasicBlock::iterator mii = mbbi->begin(), 133 mie = mbbi->end(); mii != mie; ++mii) { 134 loaded.grow(mf.getSSARegMap()->getLastVirtReg()); 135 for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){ 136 MachineOperand& mop = mii->getOperand(i); 137 if (mop.isRegister() && mop.getReg() && 138 MRegisterInfo::isVirtualRegister(mop.getReg())) { 139 unsigned virtReg = mop.getReg(); 140 unsigned physReg = vrm.getPhys(virtReg); 141 if (mop.isUse() && 142 vrm.hasStackSlot(mop.getReg()) && 143 !loaded[virtReg]) { 144 mri.loadRegFromStackSlot( 145 *mbbi, 146 mii, 147 physReg, 148 vrm.getStackSlot(virtReg)); 149 loaded[virtReg] = true; 150 DEBUG(std::cerr << '\t'; 151 prior(mii)->print(std::cerr, &tm)); 152 ++numLoads; 153 } 154 if (mop.isDef() && 155 vrm.hasStackSlot(mop.getReg())) { 156 mri.storeRegToStackSlot( 157 *mbbi, 158 next(mii), 159 physReg, 160 vrm.getStackSlot(virtReg)); 161 ++numStores; 162 } 163 mii->SetMachineOperandReg(i, physReg); 164 } 165 } 166 DEBUG(std::cerr << '\t'; mii->print(std::cerr, &tm)); 167 loaded.clear(); 168 } 169 } 170 return true; 171 } 172 }; 173 174 class LocalSpiller : public Spiller { 175 typedef std::vector<unsigned> Phys2VirtMap; 176 typedef std::vector<bool> PhysFlag; 177 typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; 178 179 MachineFunction* mf_; 180 const TargetMachine* tm_; 181 const TargetInstrInfo* tii_; 182 const MRegisterInfo* mri_; 183 const VirtRegMap* vrm_; 184 Phys2VirtMap p2vMap_; 185 PhysFlag dirty_; 186 Virt2MI lastDef_; 187 188 public: 189 bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap& vrm) { 190 mf_ = &mf; 191 tm_ = &mf_->getTarget(); 192 tii_ = tm_->getInstrInfo(); 193 mri_ = tm_->getRegisterInfo(); 194 vrm_ = &vrm; 195 p2vMap_.assign(mri_->getNumRegs(), 0); 196 dirty_.assign(mri_->getNumRegs(), false); 197 198 DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); 199 DEBUG(std::cerr << "********** Function: " 200 << mf_->getFunction()->getName() << '\n'); 201 202 for (MachineFunction::iterator mbbi = mf_->begin(), 203 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 204 lastDef_.grow(mf_->getSSARegMap()->getLastVirtReg()); 205 DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); 206 eliminateVirtRegsInMbb(*mbbi); 207 // clear map, dirty flag and last ref 208 p2vMap_.assign(p2vMap_.size(), 0); 209 dirty_.assign(dirty_.size(), false); 210 lastDef_.clear(); 211 } 212 return true; 213 } 214 215 private: 216 void vacateJustPhysReg(MachineBasicBlock& mbb, 217 MachineBasicBlock::iterator mii, 218 unsigned physReg) { 219 unsigned virtReg = p2vMap_[physReg]; 220 if (dirty_[physReg] && vrm_->hasStackSlot(virtReg)) { 221 assert(lastDef_[virtReg] && "virtual register is mapped " 222 "to a register and but was not defined!"); 223 MachineBasicBlock::iterator lastDef = lastDef_[virtReg]; 224 MachineBasicBlock::iterator nextLastRef = next(lastDef); 225 mri_->storeRegToStackSlot(*lastDef->getParent(), 226 nextLastRef, 227 physReg, 228 vrm_->getStackSlot(virtReg)); 229 ++numStores; 230 DEBUG(std::cerr << "added: "; 231 prior(nextLastRef)->print(std::cerr, tm_); 232 std::cerr << "after: "; 233 lastDef->print(std::cerr, tm_)); 234 lastDef_[virtReg] = 0; 235 } 236 p2vMap_[physReg] = 0; 237 dirty_[physReg] = false; 238 } 239 240 void vacatePhysReg(MachineBasicBlock& mbb, 241 MachineBasicBlock::iterator mii, 242 unsigned physReg) { 243 vacateJustPhysReg(mbb, mii, physReg); 244 for (const unsigned* as = mri_->getAliasSet(physReg); *as; ++as) 245 vacateJustPhysReg(mbb, mii, *as); 246 } 247 248 void handleUse(MachineBasicBlock& mbb, 249 MachineBasicBlock::iterator mii, 250 unsigned virtReg, 251 unsigned physReg) { 252 // check if we are replacing a previous mapping 253 if (p2vMap_[physReg] != virtReg) { 254 vacatePhysReg(mbb, mii, physReg); 255 p2vMap_[physReg] = virtReg; 256 // load if necessary 257 if (vrm_->hasStackSlot(virtReg)) { 258 mri_->loadRegFromStackSlot(mbb, mii, physReg, 259 vrm_->getStackSlot(virtReg)); 260 ++numLoads; 261 DEBUG(std::cerr << "added: "; 262 prior(mii)->print(std::cerr, tm_)); 263 lastDef_[virtReg] = mii; 264 } 265 } 266 } 267 268 void handleDef(MachineBasicBlock& mbb, 269 MachineBasicBlock::iterator mii, 270 unsigned virtReg, 271 unsigned physReg) { 272 // check if we are replacing a previous mapping 273 if (p2vMap_[physReg] != virtReg) 274 vacatePhysReg(mbb, mii, physReg); 275 276 p2vMap_[physReg] = virtReg; 277 dirty_[physReg] = true; 278 lastDef_[virtReg] = mii; 279 } 280 281 void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) { 282 for (MachineBasicBlock::iterator mii = mbb.begin(), 283 mie = mbb.end(); mii != mie; ++mii) { 284 285 // if we have references to memory operands make sure 286 // we clear all physical registers that may contain 287 // the value of the spilled virtual register 288 VirtRegMap::MI2VirtMap::const_iterator i, e; 289 for (tie(i, e) = vrm_->getFoldedVirts(mii); i != e; ++i) { 290 if (vrm_->hasPhys(i->second)) 291 vacateJustPhysReg(mbb, mii, vrm_->getPhys(i->second)); 292 } 293 294 // rewrite all used operands 295 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 296 MachineOperand& op = mii->getOperand(i); 297 if (op.isRegister() && op.getReg() && op.isUse() && 298 MRegisterInfo::isVirtualRegister(op.getReg())) { 299 unsigned virtReg = op.getReg(); 300 unsigned physReg = vrm_->getPhys(virtReg); 301 handleUse(mbb, mii, virtReg, physReg); 302 mii->SetMachineOperandReg(i, physReg); 303 // mark as dirty if this is def&use 304 if (op.isDef()) { 305 dirty_[physReg] = true; 306 lastDef_[virtReg] = mii; 307 } 308 } 309 } 310 311 // spill implicit physical register defs 312 const TargetInstrDescriptor& tid = tii_->get(mii->getOpcode()); 313 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 314 vacatePhysReg(mbb, mii, *id); 315 316 // spill explicit physical register defs 317 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 318 MachineOperand& op = mii->getOperand(i); 319 if (op.isRegister() && op.getReg() && !op.isUse() && 320 MRegisterInfo::isPhysicalRegister(op.getReg())) 321 vacatePhysReg(mbb, mii, op.getReg()); 322 } 323 324 // rewrite def operands (def&use was handled with the 325 // uses so don't check for those here) 326 for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 327 MachineOperand& op = mii->getOperand(i); 328 if (op.isRegister() && op.getReg() && !op.isUse()) 329 if (MRegisterInfo::isPhysicalRegister(op.getReg())) 330 vacatePhysReg(mbb, mii, op.getReg()); 331 else { 332 unsigned physReg = vrm_->getPhys(op.getReg()); 333 handleDef(mbb, mii, op.getReg(), physReg); 334 mii->SetMachineOperandReg(i, physReg); 335 } 336 } 337 338 DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_)); 339 } 340 341 for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) 342 vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i); 343 344 } 345 }; 346} 347 348llvm::Spiller* llvm::createSpiller() 349{ 350 switch (SpillerOpt) { 351 default: 352 std::cerr << "no spiller selected"; 353 abort(); 354 case local: 355 return new LocalSpiller(); 356 case simple: 357 return new SimpleSpiller(); 358 } 359} 360