lib/CodeGen/VirtRegMap.cpp

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