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 /// InvalidateKills - MI is going to be deleted. If any of its operands are
 430 /// marked kill, then invalidate the information.
 431 static void InvalidateKills(MachineInstr &MI, BitVector &RegKills,
 432                            std::vector<MachineOperand*> &KillOps) {
 433   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 434     MachineOperand &MO = MI.getOperand(i);
 435     if (!MO.isReg() || !MO.isUse() || !MO.isKill())
 436       continue;
 437     unsigned Reg = MO.getReg();
 438     if (KillOps[Reg] == &MO) {
 439       RegKills.reset(Reg);
 440       KillOps[Reg] = NULL;
 441     }
 442   }
 443 }
 444
 445 /// UpdateKills - Track and update kill info. If a MI reads a register that is
 446 /// marked kill, then it must be due to register reuse. Transfer the kill info
 447 /// over.
 448 static void UpdateKills(MachineInstr &MI, BitVector &RegKills,
 449                         std::vector<MachineOperand*> &KillOps) {
 450   const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
 451   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 452     MachineOperand &MO = MI.getOperand(i);
 453     if (!MO.isReg() || !MO.isUse())
 454       continue;
 455     unsigned Reg = MO.getReg();
 456     if (Reg == 0)
 457       continue;
 458
 459     if (RegKills[Reg]) {
 460       // That can't be right. Register is killed but not re-defined and it's
 461       // being reused. Let's fix that.
 462       KillOps[Reg]->unsetIsKill();
 463       if (i < TID->numOperands &&
 464           TID->getOperandConstraint(i, TOI::TIED_TO) == -1)
 465         // Unless it's a two-address operand, this is the new kill.
 466         MO.setIsKill();
 467     }
 468
 469     if (MO.isKill()) {
 470       RegKills.set(Reg);
 471       KillOps[Reg] = &MO;
 472     }
 473   }
 474
 475   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 476     const MachineOperand &MO = MI.getOperand(i);
 477     if (!MO.isReg() || !MO.isDef())
 478       continue;
 479     unsigned Reg = MO.getReg();
 480     RegKills.reset(Reg);
 481     KillOps[Reg] = NULL;
 482   }
 483 }
 484
 485
 486 // ReusedOp - For each reused operand, we keep track of a bit of information, in
 487 // case we need to rollback upon processing a new operand.  See comments below.
 488 namespace {
 489   struct ReusedOp {
 490     // The MachineInstr operand that reused an available value.
 491     unsigned Operand;
 492
 493     // StackSlot - The spill slot of the value being reused.
 494     unsigned StackSlot;
 495
 496     // PhysRegReused - The physical register the value was available in.
 497     unsigned PhysRegReused;
 498
 499     // AssignedPhysReg - The physreg that was assigned for use by the reload.
 500     unsigned AssignedPhysReg;
 501
 502     // VirtReg - The virtual register itself.
 503     unsigned VirtReg;
 504
 505     ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
 506              unsigned vreg)
 507       : Operand(o), StackSlot(ss), PhysRegReused(prr), AssignedPhysReg(apr),
 508       VirtReg(vreg) {}
 509   };
 510
 511   /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
 512   /// is reused instead of reloaded.
 513   class VISIBILITY_HIDDEN ReuseInfo {
 514     MachineInstr &MI;
 515     std::vector<ReusedOp> Reuses;
 516     BitVector PhysRegsClobbered;
 517   public:
 518     ReuseInfo(MachineInstr &mi, const MRegisterInfo *mri) : MI(mi) {
 519       PhysRegsClobbered.resize(mri->getNumRegs());
 520     }
 521
 522     bool hasReuses() const {
 523       return !Reuses.empty();
 524     }
 525
 526     /// addReuse - If we choose to reuse a virtual register that is already
 527     /// available instead of reloading it, remember that we did so.
 528     void addReuse(unsigned OpNo, unsigned StackSlot,
 529                   unsigned PhysRegReused, unsigned AssignedPhysReg,
 530                   unsigned VirtReg) {
 531       // If the reload is to the assigned register anyway, no undo will be
 532       // required.
 533       if (PhysRegReused == AssignedPhysReg) return;
 534
 535       // Otherwise, remember this.
 536       Reuses.push_back(ReusedOp(OpNo, StackSlot, PhysRegReused,
 537                                 AssignedPhysReg, VirtReg));
 538     }
 539
 540     void markClobbered(unsigned PhysReg) {
 541       PhysRegsClobbered.set(PhysReg);
 542     }
 543
 544     bool isClobbered(unsigned PhysReg) const {
 545       return PhysRegsClobbered.test(PhysReg);
 546     }
 547
 548     /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 549     /// is some other operand that is using the specified register, either pick
 550     /// a new register to use, or evict the previous reload and use this reg.
 551     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 552                              AvailableSpills &Spills,
 553                              std::map<int, MachineInstr*> &MaybeDeadStores,
 554                              SmallSet<unsigned, 8> &Rejected,
 555                              BitVector &RegKills,
 556                              std::vector<MachineOperand*> &KillOps) {
 557       if (Reuses.empty()) return PhysReg;  // This is most often empty.
 558
 559       for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
 560         ReusedOp &Op = Reuses[ro];
 561         // If we find some other reuse that was supposed to use this register
 562         // exactly for its reload, we can change this reload to use ITS reload
 563         // register. That is, unless its reload register has already been
 564         // considered and subsequently rejected because it has also been reused
 565         // by another operand.
 566         if (Op.PhysRegReused == PhysReg &&
 567             Rejected.count(Op.AssignedPhysReg) == 0) {
 568           // Yup, use the reload register that we didn't use before.
 569           unsigned NewReg = Op.AssignedPhysReg;
 570           Rejected.insert(PhysReg);
 571           return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected,
 572                                  RegKills, KillOps);
 573         } else {
 574           // Otherwise, we might also have a problem if a previously reused
 575           // value aliases the new register.  If so, codegen the previous reload
 576           // and use this one.
 577           unsigned PRRU = Op.PhysRegReused;
 578           const MRegisterInfo *MRI = Spills.getRegInfo();
 579           if (MRI->areAliases(PRRU, PhysReg)) {
 580             // Okay, we found out that an alias of a reused register
 581             // was used.  This isn't good because it means we have
 582             // to undo a previous reuse.
 583             MachineBasicBlock *MBB = MI->getParent();
 584             const TargetRegisterClass *AliasRC =
 585               MBB->getParent()->getSSARegMap()->getRegClass(Op.VirtReg);
 586
 587             // Copy Op out of the vector and remove it, we're going to insert an
 588             // explicit load for it.
 589             ReusedOp NewOp = Op;
 590             Reuses.erase(Reuses.begin()+ro);
 591
 592             // Ok, we're going to try to reload the assigned physreg into the
 593             // slot that we were supposed to in the first place.  However, that
 594             // register could hold a reuse.  Check to see if it conflicts or
 595             // would prefer us to use a different register.
 596             unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg,
 597                                                   MI, Spills, MaybeDeadStores,
 598                                                   Rejected, RegKills, KillOps);
 599
 600             MRI->loadRegFromStackSlot(*MBB, MI, NewPhysReg,
 601                                       NewOp.StackSlot, AliasRC);
 602             Spills.ClobberPhysReg(NewPhysReg);
 603             Spills.ClobberPhysReg(NewOp.PhysRegReused);
 604
 605             // Any stores to this stack slot are not dead anymore.
 606             MaybeDeadStores.erase(NewOp.StackSlot);
 607
 608             MI->getOperand(NewOp.Operand).setReg(NewPhysReg);
 609
 610             Spills.addAvailable(NewOp.StackSlot, MI, NewPhysReg);
 611             ++NumLoads;
 612             MachineBasicBlock::iterator MII = MI;
 613             --MII;
 614             UpdateKills(*MII, RegKills, KillOps);
 615             DOUT << '\t' << *MII;
 616
 617             DOUT << "Reuse undone!\n";
 618             --NumReused;
 619
 620             // Finally, PhysReg is now available, go ahead and use it.
 621             return PhysReg;
 622           }
 623         }
 624       }
 625       return PhysReg;
 626     }
 627
 628     /// GetRegForReload - Helper for the above GetRegForReload(). Add a
 629     /// 'Rejected' set to remember which registers have been considered and
 630     /// rejected for the reload. This avoids infinite looping in case like
 631     /// this:
 632     /// t1 := op t2, t3
 633     /// t2 <- assigned r0 for use by the reload but ended up reuse r1
 634     /// t3 <- assigned r1 for use by the reload but ended up reuse r0
 635     /// t1 <- desires r1
 636     ///       sees r1 is taken by t2, tries t2's reload register r0
 637     ///       sees r0 is taken by t3, tries t3's reload register r1
 638     ///       sees r1 is taken by t2, tries t2's reload register r0 ...
 639     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 640                              AvailableSpills &Spills,
 641                              std::map<int, MachineInstr*> &MaybeDeadStores,
 642                              BitVector &RegKills,
 643                              std::vector<MachineOperand*> &KillOps) {
 644       SmallSet<unsigned, 8> Rejected;
 645       return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
 646                              RegKills, KillOps);
 647     }
 648   };
 649 }
 650
 651
 652 /// rewriteMBB - Keep track of which spills are available even after the
 653 /// register allocator is done with them.  If possible, avoid reloading vregs.
 654 void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
 655                               std::vector<MachineInstr*> &ReMatedMIs) {
 656   DOUT << MBB.getBasicBlock()->getName() << ":\n";
 657
 658   // Spills - Keep track of which spilled values are available in physregs so
 659   // that we can choose to reuse the physregs instead of emitting reloads.
 660   AvailableSpills Spills(MRI, TII);
 661
 662   // MaybeDeadStores - When we need to write a value back into a stack slot,
 663   // keep track of the inserted store.  If the stack slot value is never read
 664   // (because the value was used from some available register, for example), and
 665   // subsequently stored to, the original store is dead.  This map keeps track
 666   // of inserted stores that are not used.  If we see a subsequent store to the
 667   // same stack slot, the original store is deleted.
 668   std::map<int, MachineInstr*> MaybeDeadStores;
 669
 670   // Keep track of kill information.
 671   BitVector RegKills(MRI->getNumRegs());
 672   std::vector<MachineOperand*>  KillOps;
 673   KillOps.resize(MRI->getNumRegs(), NULL);
 674
 675   MachineFunction &MF = *MBB.getParent();
 676   for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
 677        MII != E; ) {
 678     MachineInstr &MI = *MII;
 679     MachineBasicBlock::iterator NextMII = MII; ++NextMII;
 680     VirtRegMap::MI2VirtMapTy::const_iterator I, End;
 681
 682     bool Erased = false;
 683     bool BackTracked = false;
 684
 685     /// ReusedOperands - Keep track of operand reuse in case we need to undo
 686     /// reuse.
 687     ReuseInfo ReusedOperands(MI, MRI);
 688
 689     // Loop over all of the implicit defs, clearing them from our available
 690     // sets.
 691     const TargetInstrDescriptor *TID = MI.getInstrDescriptor();
 692
 693     // If this instruction is being rematerialized, just remove it!
 694     int FrameIdx;
 695     if (TII->isTriviallyReMaterializable(&MI) ||
 696         TII->isLoadFromStackSlot(&MI, FrameIdx)) {
 697       Erased = true;
 698       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 699         MachineOperand &MO = MI.getOperand(i);
 700         if (!MO.isRegister() || MO.getReg() == 0)
 701           continue;   // Ignore non-register operands.
 702         if (MO.isDef() && !VRM.isReMaterialized(MO.getReg())) {
 703           Erased = false;
 704           break;
 705         }
 706       }
 707       if (Erased) {
 708         VRM.RemoveFromFoldedVirtMap(&MI);
 709         ReMatedMIs.push_back(MI.removeFromParent());
 710         goto ProcessNextInst;
 711       }
 712     }
 713
 714     if (TID->ImplicitDefs) {
 715       const unsigned *ImpDef = TID->ImplicitDefs;
 716       for ( ; *ImpDef; ++ImpDef) {
 717         MF.setPhysRegUsed(*ImpDef);
 718         ReusedOperands.markClobbered(*ImpDef);
 719         Spills.ClobberPhysReg(*ImpDef);
 720       }
 721     }
 722
 723     // Process all of the spilled uses and all non spilled reg references.
 724     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 725       MachineOperand &MO = MI.getOperand(i);
 726       if (!MO.isRegister() || MO.getReg() == 0)
 727         continue;   // Ignore non-register operands.
 728
 729       if (MRegisterInfo::isPhysicalRegister(MO.getReg())) {
 730         // Ignore physregs for spilling, but remember that it is used by this
 731         // function.
 732         MF.setPhysRegUsed(MO.getReg());
 733         ReusedOperands.markClobbered(MO.getReg());
 734         continue;
 735       }
 736
 737       assert(MRegisterInfo::isVirtualRegister(MO.getReg()) &&
 738              "Not a virtual or a physical register?");
 739
 740       unsigned VirtReg = MO.getReg();
 741       if (!VRM.hasStackSlot(VirtReg)) {
 742         // This virtual register was assigned a physreg!
 743         unsigned Phys = VRM.getPhys(VirtReg);
 744         MF.setPhysRegUsed(Phys);
 745         if (MO.isDef())
 746           ReusedOperands.markClobbered(Phys);
 747         MI.getOperand(i).setReg(Phys);
 748         continue;
 749       }
 750
 751       // This virtual register is now known to be a spilled value.
 752       if (!MO.isUse())
 753         continue;  // Handle defs in the loop below (handle use&def here though)
 754
 755       bool doReMat = VRM.isReMaterialized(VirtReg);
 756       int StackSlot = VRM.getStackSlot(VirtReg);
 757       unsigned PhysReg;
 758
 759       // Check to see if this stack slot is available.
 760       if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot))) {
 761         // This spilled operand might be part of a two-address operand.  If this
 762         // is the case, then changing it will necessarily require changing the
 763         // def part of the instruction as well.  However, in some cases, we
 764         // aren't allowed to modify the reused register.  If none of these cases
 765         // apply, reuse it.
 766         bool CanReuse = true;
 767         int ti = TID->getOperandConstraint(i, TOI::TIED_TO);
 768         if (ti != -1 &&
 769             MI.getOperand(ti).isReg() &&
 770             MI.getOperand(ti).getReg() == VirtReg) {
 771           // Okay, we have a two address operand.  We can reuse this physreg as
 772           // long as we are allowed to clobber the value and there isn't an
 773           // earlier def that has already clobbered the physreg.
 774           CanReuse = Spills.canClobberPhysReg(StackSlot) &&
 775             !ReusedOperands.isClobbered(PhysReg);
 776         }
 777
 778         if (CanReuse) {
 779           // If this stack slot value is already available, reuse it!
 780           if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
 781             DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
 782           else
 783             DOUT << "Reusing SS#" << StackSlot;
 784           DOUT << " from physreg "
 785                << MRI->getName(PhysReg) << " for vreg"
 786                << VirtReg <<" instead of reloading into physreg "
 787                << MRI->getName(VRM.getPhys(VirtReg)) << "\n";
 788           MI.getOperand(i).setReg(PhysReg);
 789
 790           // The only technical detail we have is that we don't know that
 791           // PhysReg won't be clobbered by a reloaded stack slot that occurs
 792           // later in the instruction.  In particular, consider 'op V1, V2'.
 793           // If V1 is available in physreg R0, we would choose to reuse it
 794           // here, instead of reloading it into the register the allocator
 795           // indicated (say R1).  However, V2 might have to be reloaded
 796           // later, and it might indicate that it needs to live in R0.  When
 797           // this occurs, we need to have information available that
 798           // indicates it is safe to use R1 for the reload instead of R0.
 799           //
 800           // To further complicate matters, we might conflict with an alias,
 801           // or R0 and R1 might not be compatible with each other.  In this
 802           // case, we actually insert a reload for V1 in R1, ensuring that
 803           // we can get at R0 or its alias.
 804           ReusedOperands.addReuse(i, StackSlot, PhysReg,
 805                                   VRM.getPhys(VirtReg), VirtReg);
 806           if (ti != -1)
 807             // Only mark it clobbered if this is a use&def operand.
 808             ReusedOperands.markClobbered(PhysReg);
 809           ++NumReused;
 810           continue;
 811         }
 812
 813         // Otherwise we have a situation where we have a two-address instruction
 814         // whose mod/ref operand needs to be reloaded.  This reload is already
 815         // available in some register "PhysReg", but if we used PhysReg as the
 816         // operand to our 2-addr instruction, the instruction would modify
 817         // PhysReg.  This isn't cool if something later uses PhysReg and expects
 818         // to get its initial value.
 819         //
 820         // To avoid this problem, and to avoid doing a load right after a store,
 821         // we emit a copy from PhysReg into the designated register for this
 822         // operand.
 823         unsigned DesignatedReg = VRM.getPhys(VirtReg);
 824         assert(DesignatedReg && "Must map virtreg to physreg!");
 825
 826         // Note that, if we reused a register for a previous operand, the
 827         // register we want to reload into might not actually be
 828         // available.  If this occurs, use the register indicated by the
 829         // reuser.
 830         if (ReusedOperands.hasReuses())
 831           DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI,
 832                                     Spills, MaybeDeadStores, RegKills, KillOps);
 833
 834         // If the mapped designated register is actually the physreg we have
 835         // incoming, we don't need to inserted a dead copy.
 836         if (DesignatedReg == PhysReg) {
 837           // If this stack slot value is already available, reuse it!
 838           if (StackSlot > VirtRegMap::MAX_STACK_SLOT)
 839             DOUT << "Reusing RM#" << StackSlot-VirtRegMap::MAX_STACK_SLOT-1;
 840           else
 841             DOUT << "Reusing SS#" << StackSlot;
 842           DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg"
 843                << VirtReg
 844                << " instead of reloading into same physreg.\n";
 845           MI.getOperand(i).setReg(PhysReg);
 846           ReusedOperands.markClobbered(PhysReg);
 847           ++NumReused;
 848           continue;
 849         }
 850
 851         const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
 852         MF.setPhysRegUsed(DesignatedReg);
 853         ReusedOperands.markClobbered(DesignatedReg);
 854         MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC);
 855
 856         MachineInstr *CopyMI = prior(MII);
 857         UpdateKills(*CopyMI, RegKills, KillOps);
 858
 859         // This invalidates DesignatedReg.
 860         Spills.ClobberPhysReg(DesignatedReg);
 861
 862         Spills.addAvailable(StackSlot, &MI, DesignatedReg);
 863         MI.getOperand(i).setReg(DesignatedReg);
 864         DOUT << '\t' << *prior(MII);
 865         ++NumReused;
 866         continue;
 867       }
 868
 869       // Otherwise, reload it and remember that we have it.
 870       PhysReg = VRM.getPhys(VirtReg);
 871       assert(PhysReg && "Must map virtreg to physreg!");
 872       const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(VirtReg);
 873
 874       // Note that, if we reused a register for a previous operand, the
 875       // register we want to reload into might not actually be
 876       // available.  If this occurs, use the register indicated by the
 877       // reuser.
 878       if (ReusedOperands.hasReuses())
 879         PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
 880                                     Spills, MaybeDeadStores, RegKills, KillOps);
 881
 882       MF.setPhysRegUsed(PhysReg);
 883       ReusedOperands.markClobbered(PhysReg);
 884       if (doReMat) {
 885         MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg));
 886         ++NumReMats;
 887       } else {
 888         MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
 889         ++NumLoads;
 890       }
 891       // This invalidates PhysReg.
 892       Spills.ClobberPhysReg(PhysReg);
 893
 894       // Any stores to this stack slot are not dead anymore.
 895       if (!doReMat)
 896         MaybeDeadStores.erase(StackSlot);
 897       Spills.addAvailable(StackSlot, &MI, PhysReg);
 898       // Assumes this is the last use. IsKill will be unset if reg is reused
 899       // unless it's a two-address operand.
 900       if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1)
 901         MI.getOperand(i).setIsKill();
 902       MI.getOperand(i).setReg(PhysReg);
 903       UpdateKills(*prior(MII), RegKills, KillOps);
 904       DOUT << '\t' << *prior(MII);
 905     }
 906
 907     DOUT << '\t' << MI;
 908
 909     // If we have folded references to memory operands, make sure we clear all
 910     // physical registers that may contain the value of the spilled virtual
 911     // register
 912     for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
 913       DOUT << "Folded vreg: " << I->second.first << "  MR: "
 914            << I->second.second;
 915       unsigned VirtReg = I->second.first;
 916       VirtRegMap::ModRef MR = I->second.second;
 917       if (!VRM.hasStackSlot(VirtReg)) {
 918         DOUT << ": No stack slot!\n";
 919         continue;
 920       }
 921       int SS = VRM.getStackSlot(VirtReg);
 922       DOUT << " - StackSlot: " << SS << "\n";
 923
 924       // If this folded instruction is just a use, check to see if it's a
 925       // straight load from the virt reg slot.
 926       if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
 927         int FrameIdx;
 928         if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
 929           if (FrameIdx == SS) {
 930             // If this spill slot is available, turn it into a copy (or nothing)
 931             // instead of leaving it as a load!
 932             if (unsigned InReg = Spills.getSpillSlotPhysReg(SS)) {
 933               DOUT << "Promoted Load To Copy: " << MI;
 934               if (DestReg != InReg) {
 935                 MRI->copyRegToReg(MBB, &MI, DestReg, InReg,
 936                                   MF.getSSARegMap()->getRegClass(VirtReg));
 937                 // Revisit the copy so we make sure to notice the effects of the
 938                 // operation on the destreg (either needing to RA it if it's
 939                 // virtual or needing to clobber any values if it's physical).
 940                 NextMII = &MI;
 941                 --NextMII;  // backtrack to the copy.
 942                 BackTracked = true;
 943               } else
 944                 DOUT << "Removing now-noop copy: " << MI;
 945
 946               VRM.RemoveFromFoldedVirtMap(&MI);
 947               MBB.erase(&MI);
 948               Erased = true;
 949               goto ProcessNextInst;
 950             }
 951           }
 952         }
 953       }
 954
 955       // If this reference is not a use, any previous store is now dead.
 956       // Otherwise, the store to this stack slot is not dead anymore.
 957       std::map<int, MachineInstr*>::iterator MDSI = MaybeDeadStores.find(SS);
 958       if (MDSI != MaybeDeadStores.end()) {
 959         if (MR & VirtRegMap::isRef)   // Previous store is not dead.
 960           MaybeDeadStores.erase(MDSI);
 961         else {
 962           // If we get here, the store is dead, nuke it now.
 963           assert(VirtRegMap::isMod && "Can't be modref!");
 964           DOUT << "Removed dead store:\t" << *MDSI->second;
 965           InvalidateKills(*MDSI->second, RegKills, KillOps);
 966           MBB.erase(MDSI->second);
 967           VRM.RemoveFromFoldedVirtMap(MDSI->second);
 968           MaybeDeadStores.erase(MDSI);
 969           ++NumDSE;
 970         }
 971       }
 972
 973       // If the spill slot value is available, and this is a new definition of
 974       // the value, the value is not available anymore.
 975       if (MR & VirtRegMap::isMod) {
 976         // Notice that the value in this stack slot has been modified.
 977         Spills.ModifyStackSlot(SS);
 978
 979         // If this is *just* a mod of the value, check to see if this is just a
 980         // store to the spill slot (i.e. the spill got merged into the copy). If
 981         // so, realize that the vreg is available now, and add the store to the
 982         // MaybeDeadStore info.
 983         int StackSlot;
 984         if (!(MR & VirtRegMap::isRef)) {
 985           if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
 986             assert(MRegisterInfo::isPhysicalRegister(SrcReg) &&
 987                    "Src hasn't been allocated yet?");
 988             // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
 989             // this as a potentially dead store in case there is a subsequent
 990             // store into the stack slot without a read from it.
 991             MaybeDeadStores[StackSlot] = &MI;
 992
 993             // If the stack slot value was previously available in some other
 994             // register, change it now.  Otherwise, make the register available,
 995             // in PhysReg.
 996             Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/);
 997           }
 998         }
 999       }
1000     }
1001
1002     // Process all of the spilled defs.
1003     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1004       MachineOperand &MO = MI.getOperand(i);
1005       if (MO.isRegister() && MO.getReg() && MO.isDef()) {
1006         unsigned VirtReg = MO.getReg();
1007
1008         if (!MRegisterInfo::isVirtualRegister(VirtReg)) {
1009           // Check to see if this is a noop copy.  If so, eliminate the
1010           // instruction before considering the dest reg to be changed.
1011           unsigned Src, Dst;
1012           if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
1013             ++NumDCE;
1014             DOUT << "Removing now-noop copy: " << MI;
1015             MBB.erase(&MI);
1016             Erased = true;
1017             VRM.RemoveFromFoldedVirtMap(&MI);
1018             Spills.disallowClobberPhysReg(VirtReg);
1019             goto ProcessNextInst;
1020           }
1021
1022           // If it's not a no-op copy, it clobbers the value in the destreg.
1023           Spills.ClobberPhysReg(VirtReg);
1024           ReusedOperands.markClobbered(VirtReg);
1025
1026           // Check to see if this instruction is a load from a stack slot into
1027           // a register.  If so, this provides the stack slot value in the reg.
1028           int FrameIdx;
1029           if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
1030             assert(DestReg == VirtReg && "Unknown load situation!");
1031
1032             // Otherwise, if it wasn't available, remember that it is now!
1033             Spills.addAvailable(FrameIdx, &MI, DestReg);
1034             goto ProcessNextInst;
1035           }
1036
1037           continue;
1038         }
1039
1040         // The only vregs left are stack slot definitions.
1041         int StackSlot = VRM.getStackSlot(VirtReg);
1042         const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(VirtReg);
1043
1044         // If this def is part of a two-address operand, make sure to execute
1045         // the store from the correct physical register.
1046         unsigned PhysReg;
1047         int TiedOp = MI.getInstrDescriptor()->findTiedToSrcOperand(i);
1048         if (TiedOp != -1)
1049           PhysReg = MI.getOperand(TiedOp).getReg();
1050         else {
1051           PhysReg = VRM.getPhys(VirtReg);
1052           if (ReusedOperands.isClobbered(PhysReg)) {
1053             // Another def has taken the assigned physreg. It must have been a
1054             // use&def which got it due to reuse. Undo the reuse!
1055             PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
1056                                     Spills, MaybeDeadStores, RegKills, KillOps);
1057           }
1058         }
1059
1060         MF.setPhysRegUsed(PhysReg);
1061         ReusedOperands.markClobbered(PhysReg);
1062         MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
1063         DOUT << "Store:\t" << *next(MII);
1064         MI.getOperand(i).setReg(PhysReg);
1065
1066         // If there is a dead store to this stack slot, nuke it now.
1067         MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
1068         if (LastStore) {
1069           DOUT << "Removed dead store:\t" << *LastStore;
1070           ++NumDSE;
1071           InvalidateKills(*LastStore, RegKills, KillOps);
1072           MBB.erase(LastStore);
1073           VRM.RemoveFromFoldedVirtMap(LastStore);
1074         }
1075         LastStore = next(MII);
1076
1077         // If the stack slot value was previously available in some other
1078         // register, change it now.  Otherwise, make the register available,
1079         // in PhysReg.
1080         Spills.ModifyStackSlot(StackSlot);
1081         Spills.ClobberPhysReg(PhysReg);
1082         Spills.addAvailable(StackSlot, LastStore, PhysReg);
1083         ++NumStores;
1084
1085         // Check to see if this is a noop copy.  If so, eliminate the
1086         // instruction before considering the dest reg to be changed.
1087         {
1088           unsigned Src, Dst;
1089           if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
1090             ++NumDCE;
1091             DOUT << "Removing now-noop copy: " << MI;
1092             MBB.erase(&MI);
1093             Erased = true;
1094             VRM.RemoveFromFoldedVirtMap(&MI);
1095             UpdateKills(*LastStore, RegKills, KillOps);
1096             goto ProcessNextInst;
1097           }
1098         }
1099       }
1100     }
1101   ProcessNextInst:
1102     if (!Erased && !BackTracked)
1103       for (MachineBasicBlock::iterator II = MI; II != NextMII; ++II)
1104         UpdateKills(*II, RegKills, KillOps);
1105     MII = NextMII;
1106   }
1107 }
1108
1109
1110 llvm::Spiller* llvm::createSpiller() {
1111   switch (SpillerOpt) {
1112   default: assert(0 && "Unreachable!");
1113   case local:
1114     return new LocalSpiller();
1115   case simple:
1116     return new SimpleSpiller();
1117   }
1118 }