VirtRegMap.cpp revision 6b448092bff8d149769becaa14415bc1a3857e33
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 VirtRegMap class. 11// 12// It also contains implementations of the the Spiller interface, which, given a 13// virtual register map and a machine function, eliminates all virtual 14// references by replacing them with physical register references - adding spill 15// code as necessary. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "spiller" 20#include "VirtRegMap.h" 21#include "llvm/Function.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunction.h" 24#include "llvm/CodeGen/SSARegMap.h" 25#include "llvm/Target/TargetMachine.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Support/CommandLine.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/Compiler.h" 30#include "llvm/ADT/BitVector.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/ADT/STLExtras.h" 33#include "llvm/ADT/SmallSet.h" 34#include <algorithm> 35using namespace llvm; 36 37STATISTIC(NumSpills, "Number of register spills"); 38STATISTIC(NumStores, "Number of stores added"); 39STATISTIC(NumLoads , "Number of loads added"); 40STATISTIC(NumReused, "Number of values reused"); 41STATISTIC(NumDSE , "Number of dead stores elided"); 42STATISTIC(NumDCE , "Number of copies elided"); 43 44namespace { 45 enum SpillerName { simple, local }; 46 47 static cl::opt<SpillerName> 48 SpillerOpt("spiller", 49 cl::desc("Spiller to use: (default: local)"), 50 cl::Prefix, 51 cl::values(clEnumVal(simple, " simple spiller"), 52 clEnumVal(local, " local spiller"), 53 clEnumValEnd), 54 cl::init(local)); 55} 56 57//===----------------------------------------------------------------------===// 58// VirtRegMap implementation 59//===----------------------------------------------------------------------===// 60 61VirtRegMap::VirtRegMap(MachineFunction &mf) 62 : TII(*mf.getTarget().getInstrInfo()), MF(mf), 63 Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT) { 64 grow(); 65} 66 67void VirtRegMap::grow() { 68 Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg()); 69 Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg()); 70} 71 72int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 73 assert(MRegisterInfo::isVirtualRegister(virtReg)); 74 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 75 "attempt to assign stack slot to already spilled register"); 76 const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg); 77 int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(), 78 RC->getAlignment()); 79 Virt2StackSlotMap[virtReg] = frameIndex; 80 ++NumSpills; 81 return frameIndex; 82} 83 84void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) { 85 assert(MRegisterInfo::isVirtualRegister(virtReg)); 86 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 87 "attempt to assign stack slot to already spilled register"); 88 Virt2StackSlotMap[virtReg] = frameIndex; 89} 90 91void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, 92 unsigned OpNo, MachineInstr *NewMI) { 93 // Move previous memory references folded to new instruction. 94 MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI); 95 for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI), 96 E = MI2VirtMap.end(); I != E && I->first == OldMI; ) { 97 MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second)); 98 MI2VirtMap.erase(I++); 99 } 100 101 ModRef MRInfo; 102 const TargetInstrDescriptor *TID = OldMI->getInstrDescriptor(); 103 if (TID->getOperandConstraint(OpNo, TOI::TIED_TO) != -1 || 104 TID->findTiedToSrcOperand(OpNo) != -1) { 105 // Folded a two-address operand. 106 MRInfo = isModRef; 107 } else if (OldMI->getOperand(OpNo).isDef()) { 108 MRInfo = isMod; 109 } else { 110 MRInfo = isRef; 111 } 112 113 // add new memory reference 114 MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo))); 115} 116 117void VirtRegMap::print(std::ostream &OS) const { 118 const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo(); 119 120 OS << "********** REGISTER MAP **********\n"; 121 for (unsigned i = MRegisterInfo::FirstVirtualRegister, 122 e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 123 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) 124 OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n"; 125 126 } 127 128 for (unsigned i = MRegisterInfo::FirstVirtualRegister, 129 e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) 130 if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT) 131 OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n"; 132 OS << '\n'; 133} 134 135void VirtRegMap::dump() const { 136 print(DOUT); 137} 138 139 140//===----------------------------------------------------------------------===// 141// Simple Spiller Implementation 142//===----------------------------------------------------------------------===// 143 144Spiller::~Spiller() {} 145 146namespace { 147 struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller { 148 bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM); 149 }; 150} 151 152bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { 153 DOUT << "********** REWRITE MACHINE CODE **********\n"; 154 DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 155 const TargetMachine &TM = MF.getTarget(); 156 const MRegisterInfo &MRI = *TM.getRegisterInfo(); 157 bool *PhysRegsUsed = MF.getUsedPhysregs(); 158 159 // LoadedRegs - Keep track of which vregs are loaded, so that we only load 160 // each vreg once (in the case where a spilled vreg is used by multiple 161 // operands). This is always smaller than the number of operands to the 162 // current machine instr, so it should be small. 163 std::vector<unsigned> LoadedRegs; 164 165 for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 166 MBBI != E; ++MBBI) { 167 DOUT << MBBI->getBasicBlock()->getName() << ":\n"; 168 MachineBasicBlock &MBB = *MBBI; 169 for (MachineBasicBlock::iterator MII = MBB.begin(), 170 E = MBB.end(); MII != E; ++MII) { 171 MachineInstr &MI = *MII; 172 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 173 MachineOperand &MO = MI.getOperand(i); 174 if (MO.isRegister() && MO.getReg()) 175 if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 176 unsigned VirtReg = MO.getReg(); 177 unsigned PhysReg = VRM.getPhys(VirtReg); 178 if (VRM.hasStackSlot(VirtReg)) { 179 int StackSlot = VRM.getStackSlot(VirtReg); 180 const TargetRegisterClass* RC = 181 MF.getSSARegMap()->getRegClass(VirtReg); 182 183 if (MO.isUse() && 184 std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg) 185 == LoadedRegs.end()) { 186 MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); 187 LoadedRegs.push_back(VirtReg); 188 ++NumLoads; 189 DOUT << '\t' << *prior(MII); 190 } 191 192 if (MO.isDef()) { 193 MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC); 194 ++NumStores; 195 } 196 } 197 PhysRegsUsed[PhysReg] = true; 198 MI.getOperand(i).setReg(PhysReg); 199 } else { 200 PhysRegsUsed[MO.getReg()] = true; 201 } 202 } 203 204 DOUT << '\t' << MI; 205 LoadedRegs.clear(); 206 } 207 } 208 return true; 209} 210 211//===----------------------------------------------------------------------===// 212// Local Spiller Implementation 213//===----------------------------------------------------------------------===// 214 215namespace { 216 /// LocalSpiller - This spiller does a simple pass over the machine basic 217 /// block to attempt to keep spills in registers as much as possible for 218 /// blocks that have low register pressure (the vreg may be spilled due to 219 /// register pressure in other blocks). 220 class VISIBILITY_HIDDEN LocalSpiller : public Spiller { 221 const MRegisterInfo *MRI; 222 const TargetInstrInfo *TII; 223 public: 224 bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { 225 MRI = MF.getTarget().getRegisterInfo(); 226 TII = MF.getTarget().getInstrInfo(); 227 DOUT << "\n**** Local spiller rewriting function '" 228 << MF.getFunction()->getName() << "':\n"; 229 230 for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 231 MBB != E; ++MBB) 232 RewriteMBB(*MBB, VRM); 233 return true; 234 } 235 private: 236 void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); 237 }; 238} 239 240/// AvailableSpills - As the local spiller is scanning and rewriting an MBB from 241/// top down, keep track of which spills slots are available in each register. 242/// 243/// Note that not all physregs are created equal here. In particular, some 244/// physregs are reloads that we are allowed to clobber or ignore at any time. 245/// Other physregs are values that the register allocated program is using that 246/// we cannot CHANGE, but we can read if we like. We keep track of this on a 247/// per-stack-slot basis as the low bit in the value of the SpillSlotsAvailable 248/// entries. The predicate 'canClobberPhysReg()' checks this bit and 249/// addAvailable sets it if. 250namespace { 251class VISIBILITY_HIDDEN AvailableSpills { 252 const MRegisterInfo *MRI; 253 const TargetInstrInfo *TII; 254 255 // SpillSlotsAvailable - This map keeps track of all of the spilled virtual 256 // register values that are still available, due to being loaded or stored to, 257 // but not invalidated yet. It also tracks the instructions that defined 258 // or used the register. 259 typedef std::pair<unsigned, std::vector<MachineInstr*> > SSInfo; 260 std::map<int, SSInfo> SpillSlotsAvailable; 261 262 // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating 263 // which stack slot values are currently held by a physreg. This is used to 264 // invalidate entries in SpillSlotsAvailable when a physreg is modified. 265 std::multimap<unsigned, int> PhysRegsAvailable; 266 267 void disallowClobberPhysRegOnly(unsigned PhysReg); 268 269 void ClobberPhysRegOnly(unsigned PhysReg); 270public: 271 AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii) 272 : MRI(mri), TII(tii) { 273 } 274 275 const MRegisterInfo *getRegInfo() const { return MRI; } 276 277 /// getSpillSlotPhysReg - If the specified stack slot is available in a 278 /// physical register, return that PhysReg, otherwise return 0. It also 279 /// returns by reference the instruction that either defines or last uses 280 /// the register. 281 unsigned getSpillSlotPhysReg(int Slot, MachineInstr *&SSMI) const { 282 std::map<int, SSInfo>::const_iterator I = SpillSlotsAvailable.find(Slot); 283 if (I != SpillSlotsAvailable.end()) { 284 if (!I->second.second.empty()) 285 SSMI = I->second.second.back(); 286 return I->second.first >> 1; // Remove the CanClobber bit. 287 } 288 return 0; 289 } 290 291 /// addLastUse - Add the last use information of all stack slots whose 292 /// values are available in the specific register. 293 void addLastUse(unsigned PhysReg, MachineInstr *Use) { 294 std::multimap<unsigned, int>::iterator I = 295 PhysRegsAvailable.lower_bound(PhysReg); 296 while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 297 int Slot = I->second; 298 I++; 299 300 std::map<int, SSInfo>::iterator II = SpillSlotsAvailable.find(Slot); 301 assert(II != SpillSlotsAvailable.end() && "Slot not available!"); 302 unsigned Val = II->second.first; 303 assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!"); 304 II->second.second.push_back(Use); 305 } 306 } 307 308 /// removeLastUse - Remove the last use information of all stack slots whose 309 /// values are available in the specific register. 310 void removeLastUse(unsigned PhysReg, MachineInstr *Use) { 311 std::multimap<unsigned, int>::iterator I = 312 PhysRegsAvailable.lower_bound(PhysReg); 313 while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 314 int Slot = I->second; 315 I++; 316 317 std::map<int, SSInfo>::iterator II = SpillSlotsAvailable.find(Slot); 318 assert(II != SpillSlotsAvailable.end() && "Slot not available!"); 319 unsigned Val = II->second.first; 320 assert((Val >> 1) == PhysReg && "Bidirectional map mismatch!"); 321 if (II->second.second.back() == Use) 322 II->second.second.pop_back(); 323 } 324 } 325 326 /// addAvailable - Mark that the specified stack slot is available in the 327 /// specified physreg. If CanClobber is true, the physreg can be modified at 328 /// any time without changing the semantics of the program. 329 void addAvailable(int Slot, MachineInstr *MI, unsigned Reg, 330 bool CanClobber = true) { 331 // If this stack slot is thought to be available in some other physreg, 332 // remove its record. 333 ModifyStackSlot(Slot); 334 335 PhysRegsAvailable.insert(std::make_pair(Reg, Slot)); 336 std::vector<MachineInstr*> DefUses; 337 DefUses.push_back(MI); 338 SpillSlotsAvailable[Slot] = 339 std::make_pair((Reg << 1) | (unsigned)CanClobber, DefUses); 340 341 DOUT << "Remembering SS#" << Slot << " in physreg " 342 << MRI->getName(Reg) << "\n"; 343 } 344 345 /// canClobberPhysReg - Return true if the spiller is allowed to change the 346 /// value of the specified stackslot register if it desires. The specified 347 /// stack slot must be available in a physreg for this query to make sense. 348 bool canClobberPhysReg(int Slot) const { 349 assert(SpillSlotsAvailable.count(Slot) && "Slot not available!"); 350 return SpillSlotsAvailable.find(Slot)->second.first & 1; 351 } 352 353 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified 354 /// stackslot register. The register is still available but is no longer 355 /// allowed to be modifed. 356 void disallowClobberPhysReg(unsigned PhysReg); 357 358 /// ClobberPhysReg - This is called when the specified physreg changes 359 /// value. We use this to invalidate any info about stuff we thing lives in 360 /// it and any of its aliases. 361 void ClobberPhysReg(unsigned PhysReg); 362 363 /// ModifyStackSlot - This method is called when the value in a stack slot 364 /// changes. This removes information about which register the previous value 365 /// for this slot lives in (as the previous value is dead now). 366 void ModifyStackSlot(int Slot); 367}; 368} 369 370/// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified 371/// stackslot register. The register is still available but is no longer 372/// allowed to be modifed. 373void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) { 374 std::multimap<unsigned, int>::iterator I = 375 PhysRegsAvailable.lower_bound(PhysReg); 376 while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 377 int Slot = I->second; 378 I++; 379 assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg && 380 "Bidirectional map mismatch!"); 381 SpillSlotsAvailable[Slot].first &= ~1; 382 DOUT << "PhysReg " << MRI->getName(PhysReg) 383 << " copied, it is available for use but can no longer be modified\n"; 384 } 385} 386 387/// disallowClobberPhysReg - Unset the CanClobber bit of the specified 388/// stackslot register and its aliases. The register and its aliases may 389/// still available but is no longer allowed to be modifed. 390void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) { 391 for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 392 disallowClobberPhysRegOnly(*AS); 393 disallowClobberPhysRegOnly(PhysReg); 394} 395 396/// ClobberPhysRegOnly - This is called when the specified physreg changes 397/// value. We use this to invalidate any info about stuff we thing lives in it. 398void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { 399 std::multimap<unsigned, int>::iterator I = 400 PhysRegsAvailable.lower_bound(PhysReg); 401 while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 402 int Slot = I->second; 403 PhysRegsAvailable.erase(I++); 404 assert((SpillSlotsAvailable[Slot].first >> 1) == PhysReg && 405 "Bidirectional map mismatch!"); 406 SpillSlotsAvailable.erase(Slot); 407 DOUT << "PhysReg " << MRI->getName(PhysReg) 408 << " clobbered, invalidating SS#" << Slot << "\n"; 409 } 410} 411 412/// ClobberPhysReg - This is called when the specified physreg changes 413/// value. We use this to invalidate any info about stuff we thing lives in 414/// it and any of its aliases. 415void AvailableSpills::ClobberPhysReg(unsigned PhysReg) { 416 for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 417 ClobberPhysRegOnly(*AS); 418 ClobberPhysRegOnly(PhysReg); 419} 420 421/// ModifyStackSlot - This method is called when the value in a stack slot 422/// changes. This removes information about which register the previous value 423/// for this slot lives in (as the previous value is dead now). 424void AvailableSpills::ModifyStackSlot(int Slot) { 425 std::map<int, SSInfo>::iterator It = SpillSlotsAvailable.find(Slot); 426 if (It == SpillSlotsAvailable.end()) return; 427 unsigned Reg = It->second.first >> 1; 428 SpillSlotsAvailable.erase(It); 429 430 // This register may hold the value of multiple stack slots, only remove this 431 // stack slot from the set of values the register contains. 432 std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg); 433 for (; ; ++I) { 434 assert(I != PhysRegsAvailable.end() && I->first == Reg && 435 "Map inverse broken!"); 436 if (I->second == Slot) break; 437 } 438 PhysRegsAvailable.erase(I); 439} 440 441 442 443// ReusedOp - For each reused operand, we keep track of a bit of information, in 444// case we need to rollback upon processing a new operand. See comments below. 445namespace { 446 struct ReusedOp { 447 // The MachineInstr operand that reused an available value. 448 unsigned Operand; 449 450 // StackSlot - The spill slot of the value being reused. 451 unsigned StackSlot; 452 453 // PhysRegReused - The physical register the value was available in. 454 unsigned PhysRegReused; 455 456 // AssignedPhysReg - The physreg that was assigned for use by the reload. 457 unsigned AssignedPhysReg; 458 459 // VirtReg - The virtual register itself. 460 unsigned VirtReg; 461 462 ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr, 463 unsigned vreg) 464 : Operand(o), StackSlot(ss), PhysRegReused(prr), AssignedPhysReg(apr), 465 VirtReg(vreg) {} 466 }; 467 468 /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that 469 /// is reused instead of reloaded. 470 class VISIBILITY_HIDDEN ReuseInfo { 471 MachineInstr &MI; 472 std::vector<ReusedOp> Reuses; 473 BitVector PhysRegsClobbered; 474 public: 475 ReuseInfo(MachineInstr &mi, const MRegisterInfo *mri) : MI(mi) { 476 PhysRegsClobbered.resize(mri->getNumRegs()); 477 } 478 479 bool hasReuses() const { 480 return !Reuses.empty(); 481 } 482 483 /// addReuse - If we choose to reuse a virtual register that is already 484 /// available instead of reloading it, remember that we did so. 485 void addReuse(unsigned OpNo, unsigned StackSlot, 486 unsigned PhysRegReused, unsigned AssignedPhysReg, 487 unsigned VirtReg) { 488 // If the reload is to the assigned register anyway, no undo will be 489 // required. 490 if (PhysRegReused == AssignedPhysReg) return; 491 492 // Otherwise, remember this. 493 Reuses.push_back(ReusedOp(OpNo, StackSlot, PhysRegReused, 494 AssignedPhysReg, VirtReg)); 495 } 496 497 void markClobbered(unsigned PhysReg) { 498 PhysRegsClobbered.set(PhysReg); 499 } 500 501 bool isClobbered(unsigned PhysReg) const { 502 return PhysRegsClobbered.test(PhysReg); 503 } 504 505 /// GetRegForReload - We are about to emit a reload into PhysReg. If there 506 /// is some other operand that is using the specified register, either pick 507 /// a new register to use, or evict the previous reload and use this reg. 508 unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 509 AvailableSpills &Spills, 510 std::map<int, MachineInstr*> &MaybeDeadStores, 511 SmallSet<unsigned, 8> &Rejected) { 512 if (Reuses.empty()) return PhysReg; // This is most often empty. 513 514 for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) { 515 ReusedOp &Op = Reuses[ro]; 516 // If we find some other reuse that was supposed to use this register 517 // exactly for its reload, we can change this reload to use ITS reload 518 // register. That is, unless its reload register has already been 519 // considered and subsequently rejected because it has also been reused 520 // by another operand. 521 if (Op.PhysRegReused == PhysReg && 522 Rejected.count(Op.AssignedPhysReg) == 0) { 523 // Yup, use the reload register that we didn't use before. 524 unsigned NewReg = Op.AssignedPhysReg; 525 Rejected.insert(PhysReg); 526 return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected); 527 } else { 528 // Otherwise, we might also have a problem if a previously reused 529 // value aliases the new register. If so, codegen the previous reload 530 // and use this one. 531 unsigned PRRU = Op.PhysRegReused; 532 const MRegisterInfo *MRI = Spills.getRegInfo(); 533 if (MRI->areAliases(PRRU, PhysReg)) { 534 // Okay, we found out that an alias of a reused register 535 // was used. This isn't good because it means we have 536 // to undo a previous reuse. 537 MachineBasicBlock *MBB = MI->getParent(); 538 const TargetRegisterClass *AliasRC = 539 MBB->getParent()->getSSARegMap()->getRegClass(Op.VirtReg); 540 541 // Copy Op out of the vector and remove it, we're going to insert an 542 // explicit load for it. 543 ReusedOp NewOp = Op; 544 Reuses.erase(Reuses.begin()+ro); 545 546 // Ok, we're going to try to reload the assigned physreg into the 547 // slot that we were supposed to in the first place. However, that 548 // register could hold a reuse. Check to see if it conflicts or 549 // would prefer us to use a different register. 550 unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg, 551 MI, Spills, MaybeDeadStores, Rejected); 552 553 MRI->loadRegFromStackSlot(*MBB, MI, NewPhysReg, 554 NewOp.StackSlot, AliasRC); 555 Spills.ClobberPhysReg(NewPhysReg); 556 Spills.ClobberPhysReg(NewOp.PhysRegReused); 557 558 // Any stores to this stack slot are not dead anymore. 559 MaybeDeadStores.erase(NewOp.StackSlot); 560 561 MI->getOperand(NewOp.Operand).setReg(NewPhysReg); 562 563 Spills.addAvailable(NewOp.StackSlot, MI, NewPhysReg); 564 ++NumLoads; 565 DEBUG(MachineBasicBlock::iterator MII = MI; 566 DOUT << '\t' << *prior(MII)); 567 568 DOUT << "Reuse undone!\n"; 569 --NumReused; 570 571 // Finally, PhysReg is now available, go ahead and use it. 572 return PhysReg; 573 } 574 } 575 } 576 return PhysReg; 577 } 578 579 /// GetRegForReload - Helper for the above GetRegForReload(). Add a 580 /// 'Rejected' set to remember which registers have been considered and 581 /// rejected for the reload. This avoids infinite looping in case like 582 /// this: 583 /// t1 := op t2, t3 584 /// t2 <- assigned r0 for use by the reload but ended up reuse r1 585 /// t3 <- assigned r1 for use by the reload but ended up reuse r0 586 /// t1 <- desires r1 587 /// sees r1 is taken by t2, tries t2's reload register r0 588 /// sees r0 is taken by t3, tries t3's reload register r1 589 /// sees r1 is taken by t2, tries t2's reload register r0 ... 590 unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 591 AvailableSpills &Spills, 592 std::map<int, MachineInstr*> &MaybeDeadStores) { 593 SmallSet<unsigned, 8> Rejected; 594 return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected); 595 } 596 }; 597} 598 599 600/// rewriteMBB - Keep track of which spills are available even after the 601/// register allocator is done with them. If possible, avoid reloading vregs. 602void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { 603 604 DOUT << MBB.getBasicBlock()->getName() << ":\n"; 605 606 // Spills - Keep track of which spilled values are available in physregs so 607 // that we can choose to reuse the physregs instead of emitting reloads. 608 AvailableSpills Spills(MRI, TII); 609 610 // MaybeDeadStores - When we need to write a value back into a stack slot, 611 // keep track of the inserted store. If the stack slot value is never read 612 // (because the value was used from some available register, for example), and 613 // subsequently stored to, the original store is dead. This map keeps track 614 // of inserted stores that are not used. If we see a subsequent store to the 615 // same stack slot, the original store is deleted. 616 std::map<int, MachineInstr*> MaybeDeadStores; 617 618 bool *PhysRegsUsed = MBB.getParent()->getUsedPhysregs(); 619 620 for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); 621 MII != E; ) { 622 MachineInstr &MI = *MII; 623 MachineBasicBlock::iterator NextMII = MII; ++NextMII; 624 625 /// ReusedOperands - Keep track of operand reuse in case we need to undo 626 /// reuse. 627 ReuseInfo ReusedOperands(MI, MRI); 628 629 // Loop over all of the implicit defs, clearing them from our available 630 // sets. 631 const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); 632 const unsigned *ImpDef = TID->ImplicitDefs; 633 if (ImpDef) { 634 for ( ; *ImpDef; ++ImpDef) { 635 PhysRegsUsed[*ImpDef] = true; 636 ReusedOperands.markClobbered(*ImpDef); 637 Spills.ClobberPhysReg(*ImpDef); 638 } 639 } 640 641 // Process all of the spilled uses and all non spilled reg references. 642 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 643 MachineOperand &MO = MI.getOperand(i); 644 if (!MO.isRegister() || MO.getReg() == 0) 645 continue; // Ignore non-register operands. 646 647 if (MRegisterInfo::isPhysicalRegister(MO.getReg())) { 648 // Ignore physregs for spilling, but remember that it is used by this 649 // function. 650 PhysRegsUsed[MO.getReg()] = true; 651 ReusedOperands.markClobbered(MO.getReg()); 652 continue; 653 } 654 655 assert(MRegisterInfo::isVirtualRegister(MO.getReg()) && 656 "Not a virtual or a physical register?"); 657 658 unsigned VirtReg = MO.getReg(); 659 if (!VRM.hasStackSlot(VirtReg)) { 660 // This virtual register was assigned a physreg! 661 unsigned Phys = VRM.getPhys(VirtReg); 662 PhysRegsUsed[Phys] = true; 663 if (MO.isDef()) 664 ReusedOperands.markClobbered(Phys); 665 MI.getOperand(i).setReg(Phys); 666 continue; 667 } 668 669 // This virtual register is now known to be a spilled value. 670 if (!MO.isUse()) 671 continue; // Handle defs in the loop below (handle use&def here though) 672 673 int StackSlot = VRM.getStackSlot(VirtReg); 674 unsigned PhysReg; 675 676 // Check to see if this stack slot is available. 677 MachineInstr *SSMI = NULL; 678 if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot, SSMI))) { 679 // This spilled operand might be part of a two-address operand. If this 680 // is the case, then changing it will necessarily require changing the 681 // def part of the instruction as well. However, in some cases, we 682 // aren't allowed to modify the reused register. If none of these cases 683 // apply, reuse it. 684 bool CanReuse = true; 685 int ti = TID->getOperandConstraint(i, TOI::TIED_TO); 686 if (ti != -1 && 687 MI.getOperand(ti).isReg() && 688 MI.getOperand(ti).getReg() == VirtReg) { 689 // Okay, we have a two address operand. We can reuse this physreg as 690 // long as we are allowed to clobber the value and there isn't an 691 // earlier def that has already clobbered the physreg. 692 CanReuse = Spills.canClobberPhysReg(StackSlot) && 693 !ReusedOperands.isClobbered(PhysReg); 694 } 695 696 if (CanReuse) { 697 // If this stack slot value is already available, reuse it! 698 DOUT << "Reusing SS#" << StackSlot << " from physreg " 699 << MRI->getName(PhysReg) << " for vreg" 700 << VirtReg <<" instead of reloading into physreg " 701 << MRI->getName(VRM.getPhys(VirtReg)) << "\n"; 702 MI.getOperand(i).setReg(PhysReg); 703 704 // Extend the live range of the MI that last kill the register if 705 // necessary. 706 if (SSMI) { 707 MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true); 708 if (MOK) 709 MOK->unsetIsKill(); 710 } 711 if (ti == -1) { 712 // Unless it's the use of a two-address code, transfer the kill 713 // of the reused register to this use. 714 MI.getOperand(i).setIsKill(); 715 Spills.addLastUse(PhysReg, &MI); 716 } 717 718 // The only technical detail we have is that we don't know that 719 // PhysReg won't be clobbered by a reloaded stack slot that occurs 720 // later in the instruction. In particular, consider 'op V1, V2'. 721 // If V1 is available in physreg R0, we would choose to reuse it 722 // here, instead of reloading it into the register the allocator 723 // indicated (say R1). However, V2 might have to be reloaded 724 // later, and it might indicate that it needs to live in R0. When 725 // this occurs, we need to have information available that 726 // indicates it is safe to use R1 for the reload instead of R0. 727 // 728 // To further complicate matters, we might conflict with an alias, 729 // or R0 and R1 might not be compatible with each other. In this 730 // case, we actually insert a reload for V1 in R1, ensuring that 731 // we can get at R0 or its alias. 732 ReusedOperands.addReuse(i, StackSlot, PhysReg, 733 VRM.getPhys(VirtReg), VirtReg); 734 if (ti != -1) 735 // Only mark it clobbered if this is a use&def operand. 736 ReusedOperands.markClobbered(PhysReg); 737 ++NumReused; 738 continue; 739 } 740 741 // Otherwise we have a situation where we have a two-address instruction 742 // whose mod/ref operand needs to be reloaded. This reload is already 743 // available in some register "PhysReg", but if we used PhysReg as the 744 // operand to our 2-addr instruction, the instruction would modify 745 // PhysReg. This isn't cool if something later uses PhysReg and expects 746 // to get its initial value. 747 // 748 // To avoid this problem, and to avoid doing a load right after a store, 749 // we emit a copy from PhysReg into the designated register for this 750 // operand. 751 unsigned DesignatedReg = VRM.getPhys(VirtReg); 752 assert(DesignatedReg && "Must map virtreg to physreg!"); 753 754 // Note that, if we reused a register for a previous operand, the 755 // register we want to reload into might not actually be 756 // available. If this occurs, use the register indicated by the 757 // reuser. 758 if (ReusedOperands.hasReuses()) 759 DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI, 760 Spills, MaybeDeadStores); 761 762 // If the mapped designated register is actually the physreg we have 763 // incoming, we don't need to inserted a dead copy. 764 if (DesignatedReg == PhysReg) { 765 // If this stack slot value is already available, reuse it! 766 DOUT << "Reusing SS#" << StackSlot << " from physreg " 767 << MRI->getName(PhysReg) << " for vreg" 768 << VirtReg 769 << " instead of reloading into same physreg.\n"; 770 MI.getOperand(i).setReg(PhysReg); 771 ReusedOperands.markClobbered(PhysReg); 772 ++NumReused; 773 continue; 774 } 775 776 const TargetRegisterClass* RC = 777 MBB.getParent()->getSSARegMap()->getRegClass(VirtReg); 778 779 PhysRegsUsed[DesignatedReg] = true; 780 ReusedOperands.markClobbered(DesignatedReg); 781 MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC); 782 783 // Extend the live range of the MI that last kill the register if 784 // necessary. 785 if (SSMI) { 786 MachineOperand *MOK = SSMI->findRegisterUseOperand(PhysReg, true); 787 if (MOK) 788 MOK->unsetIsKill(); 789 } 790 MachineInstr *CopyMI = prior(MII); 791 MachineOperand *MOU = CopyMI->findRegisterUseOperand(PhysReg); 792 MOU->setIsKill(); 793 Spills.addLastUse(PhysReg, &MI); 794 795 // This invalidates DesignatedReg. 796 Spills.ClobberPhysReg(DesignatedReg); 797 798 Spills.addAvailable(StackSlot, &MI, DesignatedReg); 799 MI.getOperand(i).setReg(DesignatedReg); 800 DOUT << '\t' << *prior(MII); 801 ++NumReused; 802 continue; 803 } 804 805 // Otherwise, reload it and remember that we have it. 806 PhysReg = VRM.getPhys(VirtReg); 807 assert(PhysReg && "Must map virtreg to physreg!"); 808 const TargetRegisterClass* RC = 809 MBB.getParent()->getSSARegMap()->getRegClass(VirtReg); 810 811 // Note that, if we reused a register for a previous operand, the 812 // register we want to reload into might not actually be 813 // available. If this occurs, use the register indicated by the 814 // reuser. 815 if (ReusedOperands.hasReuses()) 816 PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 817 Spills, MaybeDeadStores); 818 819 PhysRegsUsed[PhysReg] = true; 820 ReusedOperands.markClobbered(PhysReg); 821 MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); 822 // This invalidates PhysReg. 823 Spills.ClobberPhysReg(PhysReg); 824 825 // Any stores to this stack slot are not dead anymore. 826 MaybeDeadStores.erase(StackSlot); 827 Spills.addAvailable(StackSlot, &MI, PhysReg); 828 // Assumes this is the last use. IsKill will be unset if reg is reused 829 // unless it's a two-address operand. 830 if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1) 831 MI.getOperand(i).setIsKill(); 832 ++NumLoads; 833 MI.getOperand(i).setReg(PhysReg); 834 DOUT << '\t' << *prior(MII); 835 } 836 837 DOUT << '\t' << MI; 838 839 // If we have folded references to memory operands, make sure we clear all 840 // physical registers that may contain the value of the spilled virtual 841 // register 842 VirtRegMap::MI2VirtMapTy::const_iterator I, End; 843 for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) { 844 DOUT << "Folded vreg: " << I->second.first << " MR: " 845 << I->second.second; 846 unsigned VirtReg = I->second.first; 847 VirtRegMap::ModRef MR = I->second.second; 848 if (!VRM.hasStackSlot(VirtReg)) { 849 DOUT << ": No stack slot!\n"; 850 continue; 851 } 852 int SS = VRM.getStackSlot(VirtReg); 853 DOUT << " - StackSlot: " << SS << "\n"; 854 855 // If this folded instruction is just a use, check to see if it's a 856 // straight load from the virt reg slot. 857 if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) { 858 int FrameIdx; 859 if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) { 860 if (FrameIdx == SS) { 861 // If this spill slot is available, turn it into a copy (or nothing) 862 // instead of leaving it as a load! 863 MachineInstr *SSMI = NULL; 864 if (unsigned InReg = Spills.getSpillSlotPhysReg(SS, SSMI)) { 865 DOUT << "Promoted Load To Copy: " << MI; 866 MachineFunction &MF = *MBB.getParent(); 867 if (DestReg != InReg) { 868 MRI->copyRegToReg(MBB, &MI, DestReg, InReg, 869 MF.getSSARegMap()->getRegClass(VirtReg)); 870 // Revisit the copy so we make sure to notice the effects of the 871 // operation on the destreg (either needing to RA it if it's 872 // virtual or needing to clobber any values if it's physical). 873 NextMII = &MI; 874 --NextMII; // backtrack to the copy. 875 } else 876 DOUT << "Removing now-noop copy: " << MI; 877 878 // Either way, the live range of the last kill of InReg has been 879 // extended. Remove its kill. 880 if (SSMI) { 881 MachineOperand *MOK = SSMI->findRegisterUseOperand(InReg, true); 882 if (MOK) 883 MOK->unsetIsKill(); 884 } 885 if (NextMII != MBB.end()) { 886 // If NextMII uses InReg (must be the copy?), mark it killed. 887 MachineOperand *MOU = NextMII->findRegisterUseOperand(InReg); 888 if (MOU) { 889 MOU->setIsKill(); 890 Spills.addLastUse(InReg, &(*NextMII)); 891 } 892 } 893 894 VRM.RemoveFromFoldedVirtMap(&MI); 895 MBB.erase(&MI); 896 goto ProcessNextInst; 897 } 898 } 899 } 900 } 901 902 // If this reference is not a use, any previous store is now dead. 903 // Otherwise, the store to this stack slot is not dead anymore. 904 std::map<int, MachineInstr*>::iterator MDSI = MaybeDeadStores.find(SS); 905 if (MDSI != MaybeDeadStores.end()) { 906 if (MR & VirtRegMap::isRef) // Previous store is not dead. 907 MaybeDeadStores.erase(MDSI); 908 else { 909 // If we get here, the store is dead, nuke it now. 910 assert(VirtRegMap::isMod && "Can't be modref!"); 911 DOUT << "Removed dead store:\t" << *MDSI->second; 912 MBB.erase(MDSI->second); 913 VRM.RemoveFromFoldedVirtMap(MDSI->second); 914 MaybeDeadStores.erase(MDSI); 915 ++NumDSE; 916 } 917 } 918 919 // If the spill slot value is available, and this is a new definition of 920 // the value, the value is not available anymore. 921 if (MR & VirtRegMap::isMod) { 922 // Notice that the value in this stack slot has been modified. 923 Spills.ModifyStackSlot(SS); 924 925 // If this is *just* a mod of the value, check to see if this is just a 926 // store to the spill slot (i.e. the spill got merged into the copy). If 927 // so, realize that the vreg is available now, and add the store to the 928 // MaybeDeadStore info. 929 int StackSlot; 930 if (!(MR & VirtRegMap::isRef)) { 931 if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) { 932 assert(MRegisterInfo::isPhysicalRegister(SrcReg) && 933 "Src hasn't been allocated yet?"); 934 // Okay, this is certainly a store of SrcReg to [StackSlot]. Mark 935 // this as a potentially dead store in case there is a subsequent 936 // store into the stack slot without a read from it. 937 MaybeDeadStores[StackSlot] = &MI; 938 939 // If the stack slot value was previously available in some other 940 // register, change it now. Otherwise, make the register available, 941 // in PhysReg. 942 Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/); 943 } 944 } 945 } 946 } 947 948 // Process all of the spilled defs. 949 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 950 MachineOperand &MO = MI.getOperand(i); 951 if (MO.isRegister() && MO.getReg() && MO.isDef()) { 952 unsigned VirtReg = MO.getReg(); 953 954 if (!MRegisterInfo::isVirtualRegister(VirtReg)) { 955 // Check to see if this is a noop copy. If so, eliminate the 956 // instruction before considering the dest reg to be changed. 957 unsigned Src, Dst; 958 if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 959 ++NumDCE; 960 DOUT << "Removing now-noop copy: " << MI; 961 Spills.removeLastUse(Src, &MI); 962 MBB.erase(&MI); 963 VRM.RemoveFromFoldedVirtMap(&MI); 964 Spills.disallowClobberPhysReg(VirtReg); 965 goto ProcessNextInst; 966 } 967 968 // If it's not a no-op copy, it clobbers the value in the destreg. 969 Spills.ClobberPhysReg(VirtReg); 970 ReusedOperands.markClobbered(VirtReg); 971 972 // Check to see if this instruction is a load from a stack slot into 973 // a register. If so, this provides the stack slot value in the reg. 974 int FrameIdx; 975 if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) { 976 assert(DestReg == VirtReg && "Unknown load situation!"); 977 978 // Otherwise, if it wasn't available, remember that it is now! 979 Spills.addAvailable(FrameIdx, &MI, DestReg); 980 goto ProcessNextInst; 981 } 982 983 continue; 984 } 985 986 // The only vregs left are stack slot definitions. 987 int StackSlot = VRM.getStackSlot(VirtReg); 988 const TargetRegisterClass *RC = 989 MBB.getParent()->getSSARegMap()->getRegClass(VirtReg); 990 991 // If this def is part of a two-address operand, make sure to execute 992 // the store from the correct physical register. 993 unsigned PhysReg; 994 int TiedOp = MI.getInstrDescriptor()->findTiedToSrcOperand(i); 995 if (TiedOp != -1) 996 PhysReg = MI.getOperand(TiedOp).getReg(); 997 else { 998 PhysReg = VRM.getPhys(VirtReg); 999 if (ReusedOperands.isClobbered(PhysReg)) { 1000 // Another def has taken the assigned physreg. It must have been a 1001 // use&def which got it due to reuse. Undo the reuse! 1002 PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 1003 Spills, MaybeDeadStores); 1004 } 1005 } 1006 1007 PhysRegsUsed[PhysReg] = true; 1008 ReusedOperands.markClobbered(PhysReg); 1009 MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC); 1010 DOUT << "Store:\t" << *next(MII); 1011 MI.getOperand(i).setReg(PhysReg); 1012 1013 // If there is a dead store to this stack slot, nuke it now. 1014 MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; 1015 if (LastStore) { 1016 DOUT << "Removed dead store:\t" << *LastStore; 1017 ++NumDSE; 1018 MBB.erase(LastStore); 1019 VRM.RemoveFromFoldedVirtMap(LastStore); 1020 } 1021 LastStore = next(MII); 1022 1023 // If the stack slot value was previously available in some other 1024 // register, change it now. Otherwise, make the register available, 1025 // in PhysReg. 1026 Spills.ModifyStackSlot(StackSlot); 1027 Spills.ClobberPhysReg(PhysReg); 1028 Spills.addAvailable(StackSlot, LastStore, PhysReg); 1029 ++NumStores; 1030 1031 // Check to see if this is a noop copy. If so, eliminate the 1032 // instruction before considering the dest reg to be changed. 1033 { 1034 unsigned Src, Dst; 1035 if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 1036 ++NumDCE; 1037 DOUT << "Removing now-noop copy: " << MI; 1038 MBB.erase(&MI); 1039 VRM.RemoveFromFoldedVirtMap(&MI); 1040 goto ProcessNextInst; 1041 } 1042 } 1043 } 1044 } 1045 ProcessNextInst: 1046 MII = NextMII; 1047 } 1048} 1049 1050 1051 1052llvm::Spiller* llvm::createSpiller() { 1053 switch (SpillerOpt) { 1054 default: assert(0 && "Unreachable!"); 1055 case local: 1056 return new LocalSpiller(); 1057 case simple: 1058 return new SimpleSpiller(); 1059 } 1060} 1061