lib/CodeGen/Spiller.cpp

   1 //===-- llvm/CodeGen/Spiller.cpp -  Spiller -------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #define DEBUG_TYPE "spiller"
  11 #include "Spiller.h"
  12 #include "llvm/Support/Compiler.h"
  13 #include "llvm/ADT/DepthFirstIterator.h"
  14 #include "llvm/ADT/Statistic.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include <algorithm>
  17 using namespace llvm;
  18
  19 STATISTIC(NumDSE     , "Number of dead stores elided");
  20 STATISTIC(NumDSS     , "Number of dead spill slots removed");
  21 STATISTIC(NumCommutes, "Number of instructions commuted");
  22 STATISTIC(NumDRM     , "Number of re-materializable defs elided");
  23 STATISTIC(NumStores  , "Number of stores added");
  24 STATISTIC(NumPSpills , "Number of physical register spills");
  25 STATISTIC(NumOmitted , "Number of reloads omited");
  26 STATISTIC(NumCopified, "Number of available reloads turned into copies");
  27 STATISTIC(NumReMats  , "Number of re-materialization");
  28 STATISTIC(NumLoads   , "Number of loads added");
  29 STATISTIC(NumReused  , "Number of values reused");
  30 STATISTIC(NumDCE     , "Number of copies elided");
  31 STATISTIC(NumSUnfold , "Number of stores unfolded");
  32
  33 namespace {
  34   enum SpillerName { simple, local };
  35 }
  36
  37 static cl::opt<SpillerName>
  38 SpillerOpt("spiller",
  39            cl::desc("Spiller to use: (default: local)"),
  40            cl::Prefix,
  41            cl::values(clEnumVal(simple, "simple spiller"),
  42                       clEnumVal(local,  "local spiller"),
  43                       clEnumValEnd),
  44            cl::init(local));
  45
  46 // ****************************** //
  47 // Simple Spiller Implementation  //
  48 // ****************************** //
  49
  50 Spiller::~Spiller() {}
  51
  52 bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
  53   DOUT << "********** REWRITE MACHINE CODE **********\n";
  54   DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
  55   const TargetMachine &TM = MF.getTarget();
  56   const TargetInstrInfo &TII = *TM.getInstrInfo();
  57   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
  58
  59
  60   // LoadedRegs - Keep track of which vregs are loaded, so that we only load
  61   // each vreg once (in the case where a spilled vreg is used by multiple
  62   // operands).  This is always smaller than the number of operands to the
  63   // current machine instr, so it should be small.
  64   std::vector<unsigned> LoadedRegs;
  65
  66   for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
  67        MBBI != E; ++MBBI) {
  68     DOUT << MBBI->getBasicBlock()->getName() << ":\n";
  69     MachineBasicBlock &MBB = *MBBI;
  70     for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
  71          MII != E; ++MII) {
  72       MachineInstr &MI = *MII;
  73       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
  74         MachineOperand &MO = MI.getOperand(i);
  75         if (MO.isReg() && MO.getReg()) {
  76           if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
  77             unsigned VirtReg = MO.getReg();
  78             unsigned SubIdx = MO.getSubReg();
  79             unsigned PhysReg = VRM.getPhys(VirtReg);
  80             unsigned RReg = SubIdx ? TRI.getSubReg(PhysReg, SubIdx) : PhysReg;
  81             if (!VRM.isAssignedReg(VirtReg)) {
  82               int StackSlot = VRM.getStackSlot(VirtReg);
  83               const TargetRegisterClass* RC =
  84                                            MF.getRegInfo().getRegClass(VirtReg);
  85
  86               if (MO.isUse() &&
  87                   std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
  88                            == LoadedRegs.end()) {
  89                 TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
  90                 MachineInstr *LoadMI = prior(MII);
  91                 VRM.addSpillSlotUse(StackSlot, LoadMI);
  92                 LoadedRegs.push_back(VirtReg);
  93                 ++NumLoads;
  94                 DOUT << '\t' << *LoadMI;
  95               }
  96
  97               if (MO.isDef()) {
  98                 TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true,
  99                                         StackSlot, RC);
 100                 MachineInstr *StoreMI = next(MII);
 101                 VRM.addSpillSlotUse(StackSlot, StoreMI);
 102                 ++NumStores;
 103               }
 104             }
 105             MF.getRegInfo().setPhysRegUsed(RReg);
 106             MI.getOperand(i).setReg(RReg);
 107           } else {
 108             MF.getRegInfo().setPhysRegUsed(MO.getReg());
 109           }
 110         }
 111       }
 112
 113       DOUT << '\t' << MI;
 114       LoadedRegs.clear();
 115     }
 116   }
 117   return true;
 118 }
 119
 120 // ****************** //
 121 // Utility Functions  //
 122 // ****************** //
 123
 124 /// InvalidateKill - A MI that defines the specified register is being deleted,
 125 /// invalidate the register kill information.
 126 static void InvalidateKill(unsigned Reg, BitVector &RegKills,
 127                            std::vector<MachineOperand*> &KillOps) {
 128   if (RegKills[Reg]) {
 129     KillOps[Reg]->setIsKill(false);
 130     KillOps[Reg] = NULL;
 131     RegKills.reset(Reg);
 132   }
 133 }
 134
 135 /// findSinglePredSuccessor - Return via reference a vector of machine basic
 136 /// blocks each of which is a successor of the specified BB and has no other
 137 /// predecessor.
 138 static void findSinglePredSuccessor(MachineBasicBlock *MBB,
 139                                    SmallVectorImpl<MachineBasicBlock *> &Succs) {
 140   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 141          SE = MBB->succ_end(); SI != SE; ++SI) {
 142     MachineBasicBlock *SuccMBB = *SI;
 143     if (SuccMBB->pred_size() == 1)
 144       Succs.push_back(SuccMBB);
 145   }
 146 }
 147
 148 /// InvalidateKills - MI is going to be deleted. If any of its operands are
 149 /// marked kill, then invalidate the information.
 150 static void InvalidateKills(MachineInstr &MI, BitVector &RegKills,
 151                             std::vector<MachineOperand*> &KillOps,
 152                             SmallVector<unsigned, 2> *KillRegs = NULL) {
 153   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 154     MachineOperand &MO = MI.getOperand(i);
 155     if (!MO.isReg() || !MO.isUse() || !MO.isKill())
 156       continue;
 157     unsigned Reg = MO.getReg();
 158     if (TargetRegisterInfo::isVirtualRegister(Reg))
 159       continue;
 160     if (KillRegs)
 161       KillRegs->push_back(Reg);
 162     assert(Reg < KillOps.size());
 163     if (KillOps[Reg] == &MO) {
 164       RegKills.reset(Reg);
 165       KillOps[Reg] = NULL;
 166     }
 167   }
 168 }
 169
 170 /// InvalidateRegDef - If the def operand of the specified def MI is now dead
 171 /// (since it's spill instruction is removed), mark it isDead. Also checks if
 172 /// the def MI has other definition operands that are not dead. Returns it by
 173 /// reference.
 174 static bool InvalidateRegDef(MachineBasicBlock::iterator I,
 175                              MachineInstr &NewDef, unsigned Reg,
 176                              bool &HasLiveDef) {
 177   // Due to remat, it's possible this reg isn't being reused. That is,
 178   // the def of this reg (by prev MI) is now dead.
 179   MachineInstr *DefMI = I;
 180   MachineOperand *DefOp = NULL;
 181   for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
 182     MachineOperand &MO = DefMI->getOperand(i);
 183     if (MO.isReg() && MO.isDef()) {
 184       if (MO.getReg() == Reg)
 185         DefOp = &MO;
 186       else if (!MO.isDead())
 187         HasLiveDef = true;
 188     }
 189   }
 190   if (!DefOp)
 191     return false;
 192
 193   bool FoundUse = false, Done = false;
 194   MachineBasicBlock::iterator E = &NewDef;
 195   ++I; ++E;
 196   for (; !Done && I != E; ++I) {
 197     MachineInstr *NMI = I;
 198     for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) {
 199       MachineOperand &MO = NMI->getOperand(j);
 200       if (!MO.isReg() || MO.getReg() != Reg)
 201         continue;
 202       if (MO.isUse())
 203         FoundUse = true;
 204       Done = true; // Stop after scanning all the operands of this MI.
 205     }
 206   }
 207   if (!FoundUse) {
 208     // Def is dead!
 209     DefOp->setIsDead();
 210     return true;
 211   }
 212   return false;
 213 }
 214
 215 /// UpdateKills - Track and update kill info. If a MI reads a register that is
 216 /// marked kill, then it must be due to register reuse. Transfer the kill info
 217 /// over.
 218 static void UpdateKills(MachineInstr &MI, BitVector &RegKills,
 219                         std::vector<MachineOperand*> &KillOps,
 220                         const TargetRegisterInfo* TRI) {
 221   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 222     MachineOperand &MO = MI.getOperand(i);
 223     if (!MO.isReg() || !MO.isUse())
 224       continue;
 225     unsigned Reg = MO.getReg();
 226     if (Reg == 0)
 227       continue;
 228
 229     if (RegKills[Reg] && KillOps[Reg]->getParent() != &MI) {
 230       // That can't be right. Register is killed but not re-defined and it's
 231       // being reused. Let's fix that.
 232       KillOps[Reg]->setIsKill(false);
 233       KillOps[Reg] = NULL;
 234       RegKills.reset(Reg);
 235       if (!MI.isRegTiedToDefOperand(i))
 236         // Unless it's a two-address operand, this is the new kill.
 237         MO.setIsKill();
 238     }
 239     if (MO.isKill()) {
 240       RegKills.set(Reg);
 241       KillOps[Reg] = &MO;
 242     }
 243   }
 244
 245   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 246     const MachineOperand &MO = MI.getOperand(i);
 247     if (!MO.isReg() || !MO.isDef())
 248       continue;
 249     unsigned Reg = MO.getReg();
 250     RegKills.reset(Reg);
 251     KillOps[Reg] = NULL;
 252     // It also defines (or partially define) aliases.
 253     for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
 254       RegKills.reset(*AS);
 255       KillOps[*AS] = NULL;
 256     }
 257   }
 258 }
 259
 260 /// ReMaterialize - Re-materialize definition for Reg targetting DestReg.
 261 ///
 262 static void ReMaterialize(MachineBasicBlock &MBB,
 263                           MachineBasicBlock::iterator &MII,
 264                           unsigned DestReg, unsigned Reg,
 265                           const TargetInstrInfo *TII,
 266                           const TargetRegisterInfo *TRI,
 267                           VirtRegMap &VRM) {
 268   TII->reMaterialize(MBB, MII, DestReg, VRM.getReMaterializedMI(Reg));
 269   MachineInstr *NewMI = prior(MII);
 270   for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
 271     MachineOperand &MO = NewMI->getOperand(i);
 272     if (!MO.isReg() || MO.getReg() == 0)
 273       continue;
 274     unsigned VirtReg = MO.getReg();
 275     if (TargetRegisterInfo::isPhysicalRegister(VirtReg))
 276       continue;
 277     assert(MO.isUse());
 278     unsigned SubIdx = MO.getSubReg();
 279     unsigned Phys = VRM.getPhys(VirtReg);
 280     assert(Phys);
 281     unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
 282     MO.setReg(RReg);
 283   }
 284   ++NumReMats;
 285 }
 286
 287 /// findSuperReg - Find the SubReg's super-register of given register class
 288 /// where its SubIdx sub-register is SubReg.
 289 static unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg,
 290                              unsigned SubIdx, const TargetRegisterInfo *TRI) {
 291   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
 292        I != E; ++I) {
 293     unsigned Reg = *I;
 294     if (TRI->getSubReg(Reg, SubIdx) == SubReg)
 295       return Reg;
 296   }
 297   return 0;
 298 }
 299
 300 // ******************************** //
 301 // Available Spills Implementation  //
 302 // ******************************** //
 303
 304 /// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified
 305 /// stackslot register. The register is still available but is no longer
 306 /// allowed to be modifed.
 307 void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) {
 308   std::multimap<unsigned, int>::iterator I =
 309     PhysRegsAvailable.lower_bound(PhysReg);
 310   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 311     int SlotOrReMat = I->second;
 312     I++;
 313     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
 314            "Bidirectional map mismatch!");
 315     SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1;
 316     DOUT << "PhysReg " << TRI->getName(PhysReg)
 317          << " copied, it is available for use but can no longer be modified\n";
 318   }
 319 }
 320
 321 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
 322 /// stackslot register and its aliases. The register and its aliases may
 323 /// still available but is no longer allowed to be modifed.
 324 void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) {
 325   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
 326     disallowClobberPhysRegOnly(*AS);
 327   disallowClobberPhysRegOnly(PhysReg);
 328 }
 329
 330 /// ClobberPhysRegOnly - This is called when the specified physreg changes
 331 /// value.  We use this to invalidate any info about stuff we thing lives in it.
 332 void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
 333   std::multimap<unsigned, int>::iterator I =
 334     PhysRegsAvailable.lower_bound(PhysReg);
 335   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 336     int SlotOrReMat = I->second;
 337     PhysRegsAvailable.erase(I++);
 338     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
 339            "Bidirectional map mismatch!");
 340     SpillSlotsOrReMatsAvailable.erase(SlotOrReMat);
 341     DOUT << "PhysReg " << TRI->getName(PhysReg)
 342          << " clobbered, invalidating ";
 343     if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
 344       DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
 345     else
 346       DOUT << "SS#" << SlotOrReMat << "\n";
 347   }
 348 }
 349
 350 /// ClobberPhysReg - This is called when the specified physreg changes
 351 /// value.  We use this to invalidate any info about stuff we thing lives in
 352 /// it and any of its aliases.
 353 void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
 354   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
 355     ClobberPhysRegOnly(*AS);
 356   ClobberPhysRegOnly(PhysReg);
 357 }
 358
 359 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
 360 /// into the specified MBB. Add available physical registers as potential
 361 /// live-in's. If they are reused in the MBB, they will be added to the
 362 /// live-in set to make register scavenger and post-allocation scheduler.
 363 void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock &MBB,
 364                                         BitVector &RegKills,
 365                                         std::vector<MachineOperand*> &KillOps) {
 366   std::set<unsigned> NotAvailable;
 367   for (std::multimap<unsigned, int>::iterator
 368          I = PhysRegsAvailable.begin(), E = PhysRegsAvailable.end();
 369        I != E; ++I) {
 370     unsigned Reg = I->first;
 371     const TargetRegisterClass* RC = TRI->getPhysicalRegisterRegClass(Reg);
 372     // FIXME: A temporary workaround. We can't reuse available value if it's
 373     // not safe to move the def of the virtual register's class. e.g.
 374     // X86::RFP* register classes. Do not add it as a live-in.
 375     if (!TII->isSafeToMoveRegClassDefs(RC))
 376       // This is no longer available.
 377       NotAvailable.insert(Reg);
 378     else {
 379       MBB.addLiveIn(Reg);
 380       InvalidateKill(Reg, RegKills, KillOps);
 381     }
 382
 383     // Skip over the same register.
 384     std::multimap<unsigned, int>::iterator NI = next(I);
 385     while (NI != E && NI->first == Reg) {
 386       ++I;
 387       ++NI;
 388     }
 389   }
 390
 391   for (std::set<unsigned>::iterator I = NotAvailable.begin(),
 392          E = NotAvailable.end(); I != E; ++I) {
 393     ClobberPhysReg(*I);
 394     for (const unsigned *SubRegs = TRI->getSubRegisters(*I);
 395        *SubRegs; ++SubRegs)
 396       ClobberPhysReg(*SubRegs);
 397   }
 398 }
 399
 400 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
 401 /// slot changes.  This removes information about which register the previous
 402 /// value for this slot lives in (as the previous value is dead now).
 403 void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) {
 404   std::map<int, unsigned>::iterator It =
 405     SpillSlotsOrReMatsAvailable.find(SlotOrReMat);
 406   if (It == SpillSlotsOrReMatsAvailable.end()) return;
 407   unsigned Reg = It->second >> 1;
 408   SpillSlotsOrReMatsAvailable.erase(It);
 409
 410   // This register may hold the value of multiple stack slots, only remove this
 411   // stack slot from the set of values the register contains.
 412   std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
 413   for (; ; ++I) {
 414     assert(I != PhysRegsAvailable.end() && I->first == Reg &&
 415            "Map inverse broken!");
 416     if (I->second == SlotOrReMat) break;
 417   }
 418   PhysRegsAvailable.erase(I);
 419 }
 420
 421 // ************************** //
 422 // Reuse Info Implementation  //
 423 // ************************** //
 424
 425 /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 426 /// is some other operand that is using the specified register, either pick
 427 /// a new register to use, or evict the previous reload and use this reg.
 428 unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 429                          AvailableSpills &Spills,
 430                          std::vector<MachineInstr*> &MaybeDeadStores,
 431                          SmallSet<unsigned, 8> &Rejected,
 432                          BitVector &RegKills,
 433                          std::vector<MachineOperand*> &KillOps,
 434                          VirtRegMap &VRM) {
 435   const TargetInstrInfo* TII = MI->getParent()->getParent()->getTarget()
 436                                .getInstrInfo();
 437
 438   if (Reuses.empty()) return PhysReg;  // This is most often empty.
 439
 440   for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
 441     ReusedOp &Op = Reuses[ro];
 442     // If we find some other reuse that was supposed to use this register
 443     // exactly for its reload, we can change this reload to use ITS reload
 444     // register. That is, unless its reload register has already been
 445     // considered and subsequently rejected because it has also been reused
 446     // by another operand.
 447     if (Op.PhysRegReused == PhysReg &&
 448         Rejected.count(Op.AssignedPhysReg) == 0) {
 449       // Yup, use the reload register that we didn't use before.
 450       unsigned NewReg = Op.AssignedPhysReg;
 451       Rejected.insert(PhysReg);
 452       return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected,
 453                              RegKills, KillOps, VRM);
 454     } else {
 455       // Otherwise, we might also have a problem if a previously reused
 456       // value aliases the new register.  If so, codegen the previous reload
 457       // and use this one.
 458       unsigned PRRU = Op.PhysRegReused;
 459       const TargetRegisterInfo *TRI = Spills.getRegInfo();
 460       if (TRI->areAliases(PRRU, PhysReg)) {
 461         // Okay, we found out that an alias of a reused register
 462         // was used.  This isn't good because it means we have
 463         // to undo a previous reuse.
 464         MachineBasicBlock *MBB = MI->getParent();
 465         const TargetRegisterClass *AliasRC =
 466           MBB->getParent()->getRegInfo().getRegClass(Op.VirtReg);
 467
 468         // Copy Op out of the vector and remove it, we're going to insert an
 469         // explicit load for it.
 470         ReusedOp NewOp = Op;
 471         Reuses.erase(Reuses.begin()+ro);
 472
 473         // Ok, we're going to try to reload the assigned physreg into the
 474         // slot that we were supposed to in the first place.  However, that
 475         // register could hold a reuse.  Check to see if it conflicts or
 476         // would prefer us to use a different register.
 477         unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg,
 478                                               MI, Spills, MaybeDeadStores,
 479                                           Rejected, RegKills, KillOps, VRM);
 480
 481         MachineBasicBlock::iterator MII = MI;
 482         if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) {
 483           ReMaterialize(*MBB, MII, NewPhysReg, NewOp.VirtReg, TII, TRI,VRM);
 484         } else {
 485           TII->loadRegFromStackSlot(*MBB, MII, NewPhysReg,
 486                                     NewOp.StackSlotOrReMat, AliasRC);
 487           MachineInstr *LoadMI = prior(MII);
 488           VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI);
 489           // Any stores to this stack slot are not dead anymore.
 490           MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL;
 491           ++NumLoads;
 492         }
 493         Spills.ClobberPhysReg(NewPhysReg);
 494         Spills.ClobberPhysReg(NewOp.PhysRegReused);
 495
 496         unsigned SubIdx = MI->getOperand(NewOp.Operand).getSubReg();
 497         unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) : NewPhysReg;
 498         MI->getOperand(NewOp.Operand).setReg(RReg);
 499
 500         Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg);
 501         --MII;
 502         UpdateKills(*MII, RegKills, KillOps, TRI);
 503         DOUT << '\t' << *MII;
 504
 505         DOUT << "Reuse undone!\n";
 506         --NumReused;
 507
 508         // Finally, PhysReg is now available, go ahead and use it.
 509         return PhysReg;
 510       }
 511     }
 512   }
 513   return PhysReg;
 514 }
 515
 516 // ***************************** //
 517 // Local Spiller Implementation  //
 518 // ***************************** //
 519
 520 bool LocalSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
 521   RegInfo = &MF.getRegInfo();
 522   TRI = MF.getTarget().getRegisterInfo();
 523   TII = MF.getTarget().getInstrInfo();
 524   DOUT << "\n**** Local spiller rewriting function '"
 525        << MF.getFunction()->getName() << "':\n";
 526   DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)"
 527           " ****\n";
 528   DEBUG(MF.dump());
 529
 530   // Spills - Keep track of which spilled values are available in physregs
 531   // so that we can choose to reuse the physregs instead of emitting
 532   // reloads. This is usually refreshed per basic block.
 533   AvailableSpills Spills(TRI, TII);
 534
 535   // Keep track of kill information.
 536   BitVector RegKills(TRI->getNumRegs());
 537   std::vector<MachineOperand*> KillOps;
 538   KillOps.resize(TRI->getNumRegs(), NULL);
 539
 540   // SingleEntrySuccs - Successor blocks which have a single predecessor.
 541   SmallVector<MachineBasicBlock*, 4> SinglePredSuccs;
 542   SmallPtrSet<MachineBasicBlock*,16> EarlyVisited;
 543
 544   // Traverse the basic blocks depth first.
 545   MachineBasicBlock *Entry = MF.begin();
 546   SmallPtrSet<MachineBasicBlock*,16> Visited;
 547   for (df_ext_iterator<MachineBasicBlock*,
 548          SmallPtrSet<MachineBasicBlock*,16> >
 549          DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
 550        DFI != E; ++DFI) {
 551     MachineBasicBlock *MBB = *DFI;
 552     if (!EarlyVisited.count(MBB))
 553       RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps);
 554
 555     // If this MBB is the only predecessor of a successor. Keep the
 556     // availability information and visit it next.
 557     do {
 558       // Keep visiting single predecessor successor as long as possible.
 559       SinglePredSuccs.clear();
 560       findSinglePredSuccessor(MBB, SinglePredSuccs);
 561       if (SinglePredSuccs.empty())
 562         MBB = 0;
 563       else {
 564         // FIXME: More than one successors, each of which has MBB has
 565         // the only predecessor.
 566         MBB = SinglePredSuccs[0];
 567         if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
 568           Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
 569           RewriteMBB(*MBB, VRM, Spills, RegKills, KillOps);
 570         }
 571       }
 572     } while (MBB);
 573
 574     // Clear the availability info.
 575     Spills.clear();
 576   }
 577
 578   DOUT << "**** Post Machine Instrs ****\n";
 579   DEBUG(MF.dump());
 580
 581   // See if any of the spills we added are actually dead and can be deleted.
 582   for (std::vector<MachineInstr*> >::iterator
 583          I = AddedSpills.begin(), E = AddedSpills.end(); I != E; ++I) {
 584     MachineInstr *MI = *I;
 585
 586     if (VRM.OnlyUseOfStackSlot(MI)) {
 587       MachineBasicBlock *MBB = MI->getParent();
 588       DOUT << "Removed dead store:\t" << *MI;
 589       VRM.RemoveMachineInstrFromMaps(MI);
 590       MBB->erase(MI);
 591       ++NumDSE;
 592     }
 593   }
 594
 595   // Mark unused spill slots.
 596   MachineFrameInfo *MFI = MF.getFrameInfo();
 597   int SS = VRM.getLowSpillSlot();
 598   if (SS != VirtRegMap::NO_STACK_SLOT)
 599     for (int e = VRM.getHighSpillSlot(); SS <= e; ++SS)
 600       if (!VRM.isSpillSlotUsed(SS)) {
 601         MFI->RemoveStackObject(SS);
 602         ++NumDSS;
 603       }
 604
 605   AddedSpills.clear();
 606   return true;
 607 }
 608
 609
 610 /// PrepForUnfoldOpti - Turn a store folding instruction into a load folding
 611 /// instruction. e.g.
 612 ///     xorl  %edi, %eax
 613 ///     movl  %eax, -32(%ebp)
 614 ///     movl  -36(%ebp), %eax
 615 ///     orl   %eax, -32(%ebp)
 616 /// ==>
 617 ///     xorl  %edi, %eax
 618 ///     orl   -36(%ebp), %eax
 619 ///     mov   %eax, -32(%ebp)
 620 /// This enables unfolding optimization for a subsequent instruction which will
 621 /// also eliminate the newly introduced store instruction.
 622 bool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB,
 623                                     MachineBasicBlock::iterator &MII,
 624                                     std::vector<MachineInstr*> &MaybeDeadStores,
 625                                     AvailableSpills &Spills,
 626                                     BitVector &RegKills,
 627                                     std::vector<MachineOperand*> &KillOps,
 628                                     VirtRegMap &VRM) {
 629   MachineFunction &MF = *MBB.getParent();
 630   MachineInstr &MI = *MII;
 631   unsigned UnfoldedOpc = 0;
 632   unsigned UnfoldPR = 0;
 633   unsigned UnfoldVR = 0;
 634   int FoldedSS = VirtRegMap::NO_STACK_SLOT;
 635   VirtRegMap::MI2VirtMapTy::const_iterator I, End;
 636   for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
 637     // Only transform a MI that folds a single register.
 638     if (UnfoldedOpc)
 639       return false;
 640     UnfoldVR = I->second.first;
 641     VirtRegMap::ModRef MR = I->second.second;
 642     // MI2VirtMap be can updated which invalidate the iterator.
 643     // Increment the iterator first.
 644     ++I;
 645     if (VRM.isAssignedReg(UnfoldVR))
 646       continue;
 647     // If this reference is not a use, any previous store is now dead.
 648     // Otherwise, the store to this stack slot is not dead anymore.
 649     FoldedSS = VRM.getStackSlot(UnfoldVR);
 650     MachineInstr* DeadStore = MaybeDeadStores[FoldedSS];
 651     if (DeadStore && (MR & VirtRegMap::isModRef)) {
 652       unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS);
 653       if (!PhysReg || !DeadStore->readsRegister(PhysReg))
 654         continue;
 655       UnfoldPR = PhysReg;
 656       UnfoldedOpc = TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
 657                                                     false, true);
 658     }
 659   }
 660
 661   if (!UnfoldedOpc)
 662     return false;
 663
 664   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 665     MachineOperand &MO = MI.getOperand(i);
 666     if (!MO.isReg() || MO.getReg() == 0 || !MO.isUse())
 667       continue;
 668     unsigned VirtReg = MO.getReg();
 669     if (TargetRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg())
 670       continue;
 671     if (VRM.isAssignedReg(VirtReg)) {
 672       unsigned PhysReg = VRM.getPhys(VirtReg);
 673       if (PhysReg && TRI->regsOverlap(PhysReg, UnfoldPR))
 674         return false;
 675     } else if (VRM.isReMaterialized(VirtReg))
 676       continue;
 677     int SS = VRM.getStackSlot(VirtReg);
 678     unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
 679     if (PhysReg) {
 680       if (TRI->regsOverlap(PhysReg, UnfoldPR))
 681         return false;
 682       continue;
 683     }
 684     if (VRM.hasPhys(VirtReg)) {
 685       PhysReg = VRM.getPhys(VirtReg);
 686       if (!TRI->regsOverlap(PhysReg, UnfoldPR))
 687         continue;
 688     }
 689
 690     // Ok, we'll need to reload the value into a register which makes
 691     // it impossible to perform the store unfolding optimization later.
 692     // Let's see if it is possible to fold the load if the store is
 693     // unfolded. This allows us to perform the store unfolding
 694     // optimization.
 695     SmallVector<MachineInstr*, 4> NewMIs;
 696     if (TII->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) {
 697       assert(NewMIs.size() == 1);
 698       MachineInstr *NewMI = NewMIs.back();
 699       NewMIs.clear();
 700       int Idx = NewMI->findRegisterUseOperandIdx(VirtReg, false);
 701       assert(Idx != -1);
 702       SmallVector<unsigned, 1> Ops;
 703       Ops.push_back(Idx);
 704       MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, NewMI, Ops, SS);
 705       if (FoldedMI) {
 706         VRM.addSpillSlotUse(SS, FoldedMI);
 707         if (!VRM.hasPhys(UnfoldVR))
 708           VRM.assignVirt2Phys(UnfoldVR, UnfoldPR);
 709         VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
 710         MII = MBB.insert(MII, FoldedMI);
 711         InvalidateKills(MI, RegKills, KillOps);
 712         VRM.RemoveMachineInstrFromMaps(&MI);
 713         MBB.erase(&MI);
 714         MF.DeleteMachineInstr(NewMI);
 715         return true;
 716       }
 717       MF.DeleteMachineInstr(NewMI);
 718     }
 719   }
 720   return false;
 721 }
 722
 723 /// CommuteToFoldReload -
 724 /// Look for
 725 /// r1 = load fi#1
 726 /// r1 = op r1, r2<kill>
 727 /// store r1, fi#1
 728 ///
 729 /// If op is commutable and r2 is killed, then we can xform these to
 730 /// r2 = op r2, fi#1
 731 /// store r2, fi#1
 732 bool LocalSpiller::CommuteToFoldReload(MachineBasicBlock &MBB,
 733                                     MachineBasicBlock::iterator &MII,
 734                                     unsigned VirtReg, unsigned SrcReg, int SS,
 735                                     AvailableSpills &Spills,
 736                                     BitVector &RegKills,
 737                                     std::vector<MachineOperand*> &KillOps,
 738                                     const TargetRegisterInfo *TRI,
 739                                     VirtRegMap &VRM) {
 740   if (MII == MBB.begin() || !MII->killsRegister(SrcReg))
 741     return false;
 742
 743   MachineFunction &MF = *MBB.getParent();
 744   MachineInstr &MI = *MII;
 745   MachineBasicBlock::iterator DefMII = prior(MII);
 746   MachineInstr *DefMI = DefMII;
 747   const TargetInstrDesc &TID = DefMI->getDesc();
 748   unsigned NewDstIdx;
 749   if (DefMII != MBB.begin() &&
 750       TID.isCommutable() &&
 751       TII->CommuteChangesDestination(DefMI, NewDstIdx)) {
 752     MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
 753     unsigned NewReg = NewDstMO.getReg();
 754     if (!NewDstMO.isKill() || TRI->regsOverlap(NewReg, SrcReg))
 755       return false;
 756     MachineInstr *ReloadMI = prior(DefMII);
 757     int FrameIdx;
 758     unsigned DestReg = TII->isLoadFromStackSlot(ReloadMI, FrameIdx);
 759     if (DestReg != SrcReg || FrameIdx != SS)
 760       return false;
 761     int UseIdx = DefMI->findRegisterUseOperandIdx(DestReg, false);
 762     if (UseIdx == -1)
 763       return false;
 764     unsigned DefIdx;
 765     if (!MI.isRegTiedToDefOperand(UseIdx, &DefIdx))
 766       return false;
 767     assert(DefMI->getOperand(DefIdx).isReg() &&
 768            DefMI->getOperand(DefIdx).getReg() == SrcReg);
 769
 770     // Now commute def instruction.
 771     MachineInstr *CommutedMI = TII->commuteInstruction(DefMI, true);
 772     if (!CommutedMI)
 773       return false;
 774     SmallVector<unsigned, 1> Ops;
 775     Ops.push_back(NewDstIdx);
 776     MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, CommutedMI, Ops, SS);
 777     // Not needed since foldMemoryOperand returns new MI.
 778     MF.DeleteMachineInstr(CommutedMI);
 779     if (!FoldedMI)
 780       return false;
 781
 782     VRM.addSpillSlotUse(SS, FoldedMI);
 783     VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
 784     // Insert new def MI and spill MI.
 785     const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(VirtReg);
 786     TII->storeRegToStackSlot(MBB, &MI, NewReg, true, SS, RC);
 787     MII = prior(MII);
 788     MachineInstr *StoreMI = MII;
 789     VRM.addSpillSlotUse(SS, StoreMI);
 790     VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
 791     MII = MBB.insert(MII, FoldedMI);  // Update MII to backtrack.
 792
 793     // Delete all 3 old instructions.
 794     InvalidateKills(*ReloadMI, RegKills, KillOps);
 795     VRM.RemoveMachineInstrFromMaps(ReloadMI);
 796     MBB.erase(ReloadMI);
 797     InvalidateKills(*DefMI, RegKills, KillOps);
 798     VRM.RemoveMachineInstrFromMaps(DefMI);
 799     MBB.erase(DefMI);
 800     InvalidateKills(MI, RegKills, KillOps);
 801     VRM.RemoveMachineInstrFromMaps(&MI);
 802     MBB.erase(&MI);
 803
 804     // If NewReg was previously holding value of some SS, it's now clobbered.
 805     // This has to be done now because it's a physical register. When this
 806     // instruction is re-visited, it's ignored.
 807     Spills.ClobberPhysReg(NewReg);
 808
 809     ++NumCommutes;
 810     return true;
 811   }
 812
 813   return false;
 814 }
 815
 816 void LocalSpiller::RemoveDeadStore(MachineInstr *Store,
 817                                    MachineBasicBlock &MBB,
 818                                    MachineBasicBlock::iterator &MII,
 819                                    SmallSet<MachineInstr*, 4> &ReMatDefs,
 820                                    BitVector &RegKills,
 821                                    std::vector<MachineOperand*> &KillOps,
 822                                    VirtRegMap &VRM) {
 823   // If there is a dead store to this stack slot, nuke it now.
 824   DOUT << "Removed dead store:\t" << *Store;
 825   ++NumDSE;
 826   SmallVector<unsigned, 2> KillRegs;
 827   InvalidateKills(*Store, RegKills, KillOps, &KillRegs);
 828
 829   MachineBasicBlock::iterator PrevMII = Store;
 830   bool CheckDef = PrevMII != MBB.begin();
 831   if (CheckDef) --PrevMII;
 832
 833   VRM.RemoveMachineInstrFromMaps(Store);
 834   MBB.erase(Store);
 835
 836   if (CheckDef) {
 837     // Look at defs of killed registers on the store. Mark the defs as dead
 838     // since the store has been deleted and they aren't being reused.
 839     for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) {
 840       bool HasOtherDef = false;
 841
 842       if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
 843         MachineInstr *DeadDef = PrevMII;
 844
 845         if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
 846           // FIXME: This assumes a remat def does not have side effects.
 847           VRM.RemoveMachineInstrFromMaps(DeadDef);
 848           MBB.erase(DeadDef);
 849           ++NumDRM;
 850         }
 851       }
 852     }
 853   }
 854 }
 855
 856 /// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if
 857 /// the last store to the same slot is now dead. If so, remove the last store.
 858 void
 859 LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB,
 860                                   MachineBasicBlock::iterator &MII,
 861                                   int Idx, unsigned PhysReg, int StackSlot,
 862                                   const TargetRegisterClass *RC,
 863                                   bool isAvailable, MachineInstr *&LastStore,
 864                                   AvailableSpills &Spills,
 865                                   SmallSet<MachineInstr*, 4> &ReMatDefs,
 866                                   BitVector &RegKills,
 867                                   std::vector<MachineOperand*> &KillOps,
 868                                   VirtRegMap &VRM) {
 869   TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC);
 870   MachineInstr *StoreMI = next(MII);
 871   VRM.addSpillSlotUse(StackSlot, StoreMI);
 872   DOUT << "Store:\t" << *StoreMI;
 873
 874   // If there is a dead store to this stack slot, nuke it now.
 875   if (LastStore)
 876     RemoveDeadStore(LastStore, MBB, MII, ReMatDefs, RegKills, KillOps, VRM);
 877
 878   LastStore = next(MII);
 879
 880   // If the stack slot value was previously available in some other
 881   // register, change it now.  Otherwise, make the register available,
 882   // in PhysReg.
 883   Spills.ModifyStackSlotOrReMat(StackSlot);
 884   Spills.ClobberPhysReg(PhysReg);
 885   Spills.addAvailable(StackSlot, PhysReg, isAvailable);
 886   ++NumStores;
 887 }
 888
 889 /// TransferDeadness - A identity copy definition is dead and it's being
 890 /// removed. Find the last def or use and mark it as dead / kill.
 891 void LocalSpiller::TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
 892                                     unsigned Reg, BitVector &RegKills,
 893                                     std::vector<MachineOperand*> &KillOps) {
 894   int LastUDDist = -1;
 895   MachineInstr *LastUDMI = NULL;
 896   for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg),
 897          RE = RegInfo->reg_end(); RI != RE; ++RI) {
 898     MachineInstr *UDMI = &*RI;
 899     if (UDMI->getParent() != MBB)
 900       continue;
 901     DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
 902     if (DI == DistanceMap.end() || DI->second > CurDist)
 903       continue;
 904     if ((int)DI->second < LastUDDist)
 905       continue;
 906     LastUDDist = DI->second;
 907     LastUDMI = UDMI;
 908   }
 909
 910   if (LastUDMI) {
 911     MachineOperand *LastUD = NULL;
 912     for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
 913       MachineOperand &MO = LastUDMI->getOperand(i);
 914       if (!MO.isReg() || MO.getReg() != Reg)
 915         continue;
 916       if (!LastUD || (LastUD->isUse() && MO.isDef()))
 917         LastUD = &MO;
 918       if (LastUDMI->isRegTiedToDefOperand(i))
 919         return;
 920     }
 921     if (LastUD->isDef())
 922       LastUD->setIsDead();
 923     else {
 924       LastUD->setIsKill();
 925       RegKills.set(Reg);
 926       KillOps[Reg] = LastUD;
 927     }
 928   }
 929 }
 930
 931 /// rewriteMBB - Keep track of which spills are available even after the
 932 /// register allocator is done with them.  If possible, avid reloading vregs.
 933 void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
 934                               AvailableSpills &Spills, BitVector &RegKills,
 935                               std::vector<MachineOperand*> &KillOps) {
 936   DOUT << "\n**** Local spiller rewriting MBB '"
 937        << MBB.getBasicBlock()->getName() << "':\n";
 938
 939   MachineFunction &MF = *MBB.getParent();
 940
 941   // MaybeDeadStores - When we need to write a value back into a stack slot,
 942   // keep track of the inserted store.  If the stack slot value is never read
 943   // (because the value was used from some available register, for example), and
 944   // subsequently stored to, the original store is dead.  This map keeps track
 945   // of inserted stores that are not used.  If we see a subsequent store to the
 946   // same stack slot, the original store is deleted.
 947   std::vector<MachineInstr*> MaybeDeadStores;
 948   MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL);
 949
 950   // ReMatDefs - These are rematerializable def MIs which are not deleted.
 951   SmallSet<MachineInstr*, 4> ReMatDefs;
 952
 953   // Clear kill info.
 954   SmallSet<unsigned, 2> KilledMIRegs;
 955   RegKills.reset();
 956   KillOps.clear();
 957   KillOps.resize(TRI->getNumRegs(), NULL);
 958
 959   unsigned Dist = 0;
 960   DistanceMap.clear();
 961   for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
 962        MII != E; ) {
 963     MachineBasicBlock::iterator NextMII = MII; ++NextMII;
 964
 965     VirtRegMap::MI2VirtMapTy::const_iterator I, End;
 966     bool Erased = false;
 967     bool BackTracked = false;
 968     if (PrepForUnfoldOpti(MBB, MII,
 969                           MaybeDeadStores, Spills, RegKills, KillOps, VRM))
 970       NextMII = next(MII);
 971
 972     MachineInstr &MI = *MII;
 973
 974     if (VRM.hasEmergencySpills(&MI)) {
 975       // Spill physical register(s) in the rare case the allocator has run out
 976       // of registers to allocate.
 977       SmallSet<int, 4> UsedSS;
 978       std::vector<unsigned> &EmSpills = VRM.getEmergencySpills(&MI);
 979       for (unsigned i = 0, e = EmSpills.size(); i != e; ++i) {
 980         unsigned PhysReg = EmSpills[i];
 981         const TargetRegisterClass *RC =
 982           TRI->getPhysicalRegisterRegClass(PhysReg);
 983         assert(RC && "Unable to determine register class!");
 984         int SS = VRM.getEmergencySpillSlot(RC);
 985         if (UsedSS.count(SS))
 986           assert(0 && "Need to spill more than one physical registers!");
 987         UsedSS.insert(SS);
 988         TII->storeRegToStackSlot(MBB, MII, PhysReg, true, SS, RC);
 989         MachineInstr *StoreMI = prior(MII);
 990         VRM.addSpillSlotUse(SS, StoreMI);
 991         TII->loadRegFromStackSlot(MBB, next(MII), PhysReg, SS, RC);
 992         MachineInstr *LoadMI = next(MII);
 993         VRM.addSpillSlotUse(SS, LoadMI);
 994         ++NumPSpills;
 995       }
 996       NextMII = next(MII);
 997     }
 998
 999     // Insert restores here if asked to.
1000     if (VRM.isRestorePt(&MI)) {
1001       std::vector<unsigned> &RestoreRegs = VRM.getRestorePtRestores(&MI);
1002       for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) {
1003         unsigned VirtReg = RestoreRegs[e-i-1];  // Reverse order.
1004         if (!VRM.getPreSplitReg(VirtReg))
1005           continue; // Split interval spilled again.
1006         unsigned Phys = VRM.getPhys(VirtReg);
1007         RegInfo->setPhysRegUsed(Phys);
1008
1009         // Check if the value being restored if available. If so, it must be
1010         // from a predecessor BB that fallthrough into this BB. We do not
1011         // expect:
1012         // BB1:
1013         // r1 = load fi#1
1014         // ...
1015         //    = r1<kill>
1016         // ... # r1 not clobbered
1017         // ...
1018         //    = load fi#1
1019         bool DoReMat = VRM.isReMaterialized(VirtReg);
1020         int SSorRMId = DoReMat
1021           ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
1022         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1023         unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
1024         if (InReg == Phys) {
1025           // If the value is already available in the expected register, save
1026           // a reload / remat.
1027           if (SSorRMId)
1028             DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
1029           else
1030             DOUT << "Reusing SS#" << SSorRMId;
1031           DOUT << " from physreg "
1032                << TRI->getName(InReg) << " for vreg"
1033                << VirtReg <<" instead of reloading into physreg "
1034                << TRI->getName(Phys) << "\n";
1035           ++NumOmitted;
1036           continue;
1037         } else if (InReg && InReg != Phys) {
1038           if (SSorRMId)
1039             DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
1040           else
1041             DOUT << "Reusing SS#" << SSorRMId;
1042           DOUT << " from physreg "
1043                << TRI->getName(InReg) << " for vreg"
1044                << VirtReg <<" by copying it into physreg "
1045                << TRI->getName(Phys) << "\n";
1046
1047           // If the reloaded / remat value is available in another register,
1048           // copy it to the desired register.
1049           TII->copyRegToReg(MBB, &MI, Phys, InReg, RC, RC);
1050
1051           // This invalidates Phys.
1052           Spills.ClobberPhysReg(Phys);
1053           // Remember it's available.
1054           Spills.addAvailable(SSorRMId, Phys);
1055
1056           // Mark is killed.
1057           MachineInstr *CopyMI = prior(MII);
1058           MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg);
1059           KillOpnd->setIsKill();
1060           UpdateKills(*CopyMI, RegKills, KillOps, TRI);
1061
1062           DOUT << '\t' << *CopyMI;
1063           ++NumCopified;
1064           continue;
1065         }
1066
1067         if (VRM.isReMaterialized(VirtReg)) {
1068           ReMaterialize(MBB, MII, Phys, VirtReg, TII, TRI, VRM);
1069         } else {
1070           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1071           TII->loadRegFromStackSlot(MBB, &MI, Phys, SSorRMId, RC);
1072           MachineInstr *LoadMI = prior(MII);
1073           VRM.addSpillSlotUse(SSorRMId, LoadMI);
1074           ++NumLoads;
1075         }
1076
1077         // This invalidates Phys.
1078         Spills.ClobberPhysReg(Phys);
1079         // Remember it's available.
1080         Spills.addAvailable(SSorRMId, Phys);
1081
1082         UpdateKills(*prior(MII), RegKills, KillOps, TRI);
1083         DOUT << '\t' << *prior(MII);
1084       }
1085     }
1086
1087     // Insert spills here if asked to.
1088     if (VRM.isSpillPt(&MI)) {
1089       std::vector<std::pair<unsigned,bool> > &SpillRegs =
1090         VRM.getSpillPtSpills(&MI);
1091
1092       for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
1093         unsigned VirtReg = SpillRegs[i].first;
1094         bool isKill = SpillRegs[i].second;
1095         if (!VRM.getPreSplitReg(VirtReg))
1096           continue; // Split interval spilled again.
1097         const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
1098         unsigned Phys = VRM.getPhys(VirtReg);
1099         int StackSlot = VRM.getStackSlot(VirtReg);
1100         TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC);
1101         MachineInstr *StoreMI = next(MII);
1102         VRM.addSpillSlotUse(StackSlot, StoreMI);
1103         DOUT << "Store:\t" << *StoreMI;
1104         VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
1105         AddedSpills.push_back(StoreMI);
1106       }
1107
1108       NextMII = next(MII);
1109     }
1110
1111     /// ReusedOperands - Keep track of operand reuse in case we need to undo
1112     /// reuse.
1113     ReuseInfo ReusedOperands(MI, TRI);
1114     SmallVector<unsigned, 4> VirtUseOps;
1115     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1116       MachineOperand &MO = MI.getOperand(i);
1117       if (!MO.isReg() || MO.getReg() == 0)
1118         continue;   // Ignore non-register operands.
1119
1120       unsigned VirtReg = MO.getReg();
1121       if (TargetRegisterInfo::isPhysicalRegister(VirtReg)) {
1122         // Ignore physregs for spilling, but remember that it is used by this
1123         // function.
1124         RegInfo->setPhysRegUsed(VirtReg);
1125         continue;
1126       }
1127
1128       // We want to process implicit virtual register uses first.
1129       if (MO.isImplicit())
1130         // If the virtual register is implicitly defined, emit a implicit_def
1131         // before so scavenger knows it's "defined".
1132         VirtUseOps.insert(VirtUseOps.begin(), i);
1133       else
1134         VirtUseOps.push_back(i);
1135     }
1136
1137     // Process all of the spilled uses and all non spilled reg references.
1138     SmallVector<int, 2> PotentialDeadStoreSlots;
1139     KilledMIRegs.clear();
1140     for (unsigned j = 0, e = VirtUseOps.size(); j != e; ++j) {
1141       unsigned i = VirtUseOps[j];
1142       MachineOperand &MO = MI.getOperand(i);
1143       unsigned VirtReg = MO.getReg();
1144       assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
1145              "Not a virtual register?");
1146
1147       unsigned SubIdx = MO.getSubReg();
1148       if (VRM.isAssignedReg(VirtReg)) {
1149         // This virtual register was assigned a physreg!
1150         unsigned Phys = VRM.getPhys(VirtReg);
1151         RegInfo->setPhysRegUsed(Phys);
1152         if (MO.isDef())
1153           ReusedOperands.markClobbered(Phys);
1154         unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
1155         MI.getOperand(i).setReg(RReg);
1156         if (VRM.isImplicitlyDefined(VirtReg))
1157           BuildMI(MBB, &MI, MI.getDebugLoc(),
1158                   TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
1159         continue;
1160       }
1161
1162       // This virtual register is now known to be a spilled value.
1163       if (!MO.isUse())
1164         continue;  // Handle defs in the loop below (handle use&def here though)
1165
1166       bool DoReMat = VRM.isReMaterialized(VirtReg);
1167       int SSorRMId = DoReMat
1168         ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
1169       int ReuseSlot = SSorRMId;
1170
1171       // Check to see if this stack slot is available.
1172       unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
1173
1174       // If this is a sub-register use, make sure the reuse register is in the
1175       // right register class. For example, for x86 not all of the 32-bit
1176       // registers have accessible sub-registers.
1177       // Similarly so for EXTRACT_SUBREG. Consider this:
1178       // EDI = op
1179       // MOV32_mr fi#1, EDI
1180       // ...
1181       //       = EXTRACT_SUBREG fi#1
1182       // fi#1 is available in EDI, but it cannot be reused because it's not in
1183       // the right register file.
1184       if (PhysReg &&
1185           (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) {
1186         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1187         if (!RC->contains(PhysReg))
1188           PhysReg = 0;
1189       }
1190
1191       if (PhysReg) {
1192         // This spilled operand might be part of a two-address operand.  If this
1193         // is the case, then changing it will necessarily require changing the
1194         // def part of the instruction as well.  However, in some cases, we
1195         // aren't allowed to modify the reused register.  If none of these cases
1196         // apply, reuse it.
1197         bool CanReuse = true;
1198         bool isTied = MI.isRegTiedToDefOperand(i);
1199         if (isTied) {
1200           // Okay, we have a two address operand.  We can reuse this physreg as
1201           // long as we are allowed to clobber the value and there isn't an
1202           // earlier def that has already clobbered the physreg.
1203           CanReuse = !ReusedOperands.isClobbered(PhysReg) &&
1204             Spills.canClobberPhysReg(PhysReg);
1205         }
1206
1207         if (CanReuse) {
1208           // If this stack slot value is already available, reuse it!
1209           if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
1210             DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
1211           else
1212             DOUT << "Reusing SS#" << ReuseSlot;
1213           DOUT << " from physreg "
1214                << TRI->getName(PhysReg) << " for vreg"
1215                << VirtReg <<" instead of reloading into physreg "
1216                << TRI->getName(VRM.getPhys(VirtReg)) << "\n";
1217           unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1218           MI.getOperand(i).setReg(RReg);
1219
1220           // The only technical detail we have is that we don't know that
1221           // PhysReg won't be clobbered by a reloaded stack slot that occurs
1222           // later in the instruction.  In particular, consider 'op V1, V2'.
1223           // If V1 is available in physreg R0, we would choose to reuse it
1224           // here, instead of reloading it into the register the allocator
1225           // indicated (say R1).  However, V2 might have to be reloaded
1226           // later, and it might indicate that it needs to live in R0.  When
1227           // this occurs, we need to have information available that
1228           // indicates it is safe to use R1 for the reload instead of R0.
1229           //
1230           // To further complicate matters, we might conflict with an alias,
1231           // or R0 and R1 might not be compatible with each other.  In this
1232           // case, we actually insert a reload for V1 in R1, ensuring that
1233           // we can get at R0 or its alias.
1234           ReusedOperands.addReuse(i, ReuseSlot, PhysReg,
1235                                   VRM.getPhys(VirtReg), VirtReg);
1236           if (isTied)
1237             // Only mark it clobbered if this is a use&def operand.
1238             ReusedOperands.markClobbered(PhysReg);
1239           ++NumReused;
1240
1241           if (MI.getOperand(i).isKill() &&
1242               ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) {
1243
1244             // The store of this spilled value is potentially dead, but we
1245             // won't know for certain until we've confirmed that the re-use
1246             // above is valid, which means waiting until the other operands
1247             // are processed. For now we just track the spill slot, we'll
1248             // remove it after the other operands are processed if valid.
1249
1250             PotentialDeadStoreSlots.push_back(ReuseSlot);
1251           }
1252
1253           // Mark is isKill if it's there no other uses of the same virtual
1254           // register and it's not a two-address operand. IsKill will be
1255           // unset if reg is reused.
1256           if (!isTied && KilledMIRegs.count(VirtReg) == 0) {
1257             MI.getOperand(i).setIsKill();
1258             KilledMIRegs.insert(VirtReg);
1259           }
1260
1261           continue;
1262         }  // CanReuse
1263
1264         // Otherwise we have a situation where we have a two-address instruction
1265         // whose mod/ref operand needs to be reloaded.  This reload is already
1266         // available in some register "PhysReg", but if we used PhysReg as the
1267         // operand to our 2-addr instruction, the instruction would modify
1268         // PhysReg.  This isn't cool if something later uses PhysReg and expects
1269         // to get its initial value.
1270         //
1271         // To avoid this problem, and to avoid doing a load right after a store,
1272         // we emit a copy from PhysReg into the designated register for this
1273         // operand.
1274         unsigned DesignatedReg = VRM.getPhys(VirtReg);
1275         assert(DesignatedReg && "Must map virtreg to physreg!");
1276
1277         // Note that, if we reused a register for a previous operand, the
1278         // register we want to reload into might not actually be
1279         // available.  If this occurs, use the register indicated by the
1280         // reuser.
1281         if (ReusedOperands.hasReuses())
1282           DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI,
1283                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
1284
1285         // If the mapped designated register is actually the physreg we have
1286         // incoming, we don't need to inserted a dead copy.
1287         if (DesignatedReg == PhysReg) {
1288           // If this stack slot value is already available, reuse it!
1289           if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
1290             DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
1291           else
1292             DOUT << "Reusing SS#" << ReuseSlot;
1293           DOUT << " from physreg " << TRI->getName(PhysReg)
1294                << " for vreg" << VirtReg
1295                << " instead of reloading into same physreg.\n";
1296           unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1297           MI.getOperand(i).setReg(RReg);
1298           ReusedOperands.markClobbered(RReg);
1299           ++NumReused;
1300           continue;
1301         }
1302
1303         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1304         RegInfo->setPhysRegUsed(DesignatedReg);
1305         ReusedOperands.markClobbered(DesignatedReg);
1306         TII->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC);
1307
1308         MachineInstr *CopyMI = prior(MII);
1309         UpdateKills(*CopyMI, RegKills, KillOps, TRI);
1310
1311         // This invalidates DesignatedReg.
1312         Spills.ClobberPhysReg(DesignatedReg);
1313
1314         Spills.addAvailable(ReuseSlot, DesignatedReg);
1315         unsigned RReg =
1316           SubIdx ? TRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg;
1317         MI.getOperand(i).setReg(RReg);
1318         DOUT << '\t' << *prior(MII);
1319         ++NumReused;
1320         continue;
1321       } // if (PhysReg)
1322
1323       // Otherwise, reload it and remember that we have it.
1324       PhysReg = VRM.getPhys(VirtReg);
1325       assert(PhysReg && "Must map virtreg to physreg!");
1326
1327       // Note that, if we reused a register for a previous operand, the
1328       // register we want to reload into might not actually be
1329       // available.  If this occurs, use the register indicated by the
1330       // reuser.
1331       if (ReusedOperands.hasReuses())
1332         PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
1333                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
1334
1335       RegInfo->setPhysRegUsed(PhysReg);
1336       ReusedOperands.markClobbered(PhysReg);
1337       if (DoReMat) {
1338         ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM);
1339       } else {
1340         const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1341         TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
1342         MachineInstr *LoadMI = prior(MII);
1343         VRM.addSpillSlotUse(SSorRMId, LoadMI);
1344         ++NumLoads;
1345       }
1346       // This invalidates PhysReg.
1347       Spills.ClobberPhysReg(PhysReg);
1348
1349       // Any stores to this stack slot are not dead anymore.
1350       if (!DoReMat)
1351         MaybeDeadStores[SSorRMId] = NULL;
1352       Spills.addAvailable(SSorRMId, PhysReg);
1353       // Assumes this is the last use. IsKill will be unset if reg is reused
1354       // unless it's a two-address operand.
1355       if (!MI.isRegTiedToDefOperand(i) &&
1356           KilledMIRegs.count(VirtReg) == 0) {
1357         MI.getOperand(i).setIsKill();
1358         KilledMIRegs.insert(VirtReg);
1359       }
1360       unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1361       MI.getOperand(i).setReg(RReg);
1362       UpdateKills(*prior(MII), RegKills, KillOps, TRI);
1363       DOUT << '\t' << *prior(MII);
1364     }
1365
1366     // Ok - now we can remove stores that have been confirmed dead.
1367     for (unsigned j = 0, e = PotentialDeadStoreSlots.size(); j != e; ++j) {
1368       // This was the last use and the spilled value is still available
1369       // for reuse. That means the spill was unnecessary!
1370       int PDSSlot = PotentialDeadStoreSlots[j];
1371       MachineInstr* DeadStore = MaybeDeadStores[PDSSlot];
1372       if (DeadStore) {
1373         DOUT << "Removed dead store:\t" << *DeadStore;
1374         InvalidateKills(*DeadStore, RegKills, KillOps);
1375         VRM.RemoveMachineInstrFromMaps(DeadStore);
1376         MBB.erase(DeadStore);
1377         MaybeDeadStores[PDSSlot] = NULL;
1378         ++NumDSE;
1379       }
1380     }
1381
1382
1383     DOUT << '\t' << MI;
1384
1385
1386     // If we have folded references to memory operands, make sure we clear all
1387     // physical registers that may contain the value of the spilled virtual
1388     // register
1389     SmallSet<int, 2> FoldedSS;
1390     for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
1391       unsigned VirtReg = I->second.first;
1392       VirtRegMap::ModRef MR = I->second.second;
1393       DOUT << "Folded vreg: " << VirtReg << "  MR: " << MR;
1394
1395       // MI2VirtMap be can updated which invalidate the iterator.
1396       // Increment the iterator first.
1397       ++I;
1398       int SS = VRM.getStackSlot(VirtReg);
1399       if (SS == VirtRegMap::NO_STACK_SLOT)
1400         continue;
1401       FoldedSS.insert(SS);
1402       DOUT << " - StackSlot: " << SS << "\n";
1403
1404       // If this folded instruction is just a use, check to see if it's a
1405       // straight load from the virt reg slot.
1406       if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
1407         int FrameIdx;
1408         unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx);
1409         if (DestReg && FrameIdx == SS) {
1410           // If this spill slot is available, turn it into a copy (or nothing)
1411           // instead of leaving it as a load!
1412           if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) {
1413             DOUT << "Promoted Load To Copy: " << MI;
1414             if (DestReg != InReg) {
1415               const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
1416               TII->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC);
1417               MachineOperand *DefMO = MI.findRegisterDefOperand(DestReg);
1418               unsigned SubIdx = DefMO->getSubReg();
1419               // Revisit the copy so we make sure to notice the effects of the
1420               // operation on the destreg (either needing to RA it if it's
1421               // virtual or needing to clobber any values if it's physical).
1422               NextMII = &MI;
1423               --NextMII;  // backtrack to the copy.
1424               // Propagate the sub-register index over.
1425               if (SubIdx) {
1426                 DefMO = NextMII->findRegisterDefOperand(DestReg);
1427                 DefMO->setSubReg(SubIdx);
1428               }
1429
1430               // Mark is killed.
1431               MachineOperand *KillOpnd = NextMII->findRegisterUseOperand(InReg);
1432               KillOpnd->setIsKill();
1433
1434               BackTracked = true;
1435             } else {
1436               DOUT << "Removing now-noop copy: " << MI;
1437               // Unset last kill since it's being reused.
1438               InvalidateKill(InReg, RegKills, KillOps);
1439               Spills.disallowClobberPhysReg(InReg);
1440             }
1441
1442             InvalidateKills(MI, RegKills, KillOps);
1443             VRM.RemoveMachineInstrFromMaps(&MI);
1444             MBB.erase(&MI);
1445             Erased = true;
1446             goto ProcessNextInst;
1447           }
1448         } else {
1449           unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
1450           SmallVector<MachineInstr*, 4> NewMIs;
1451           if (PhysReg &&
1452               TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) {
1453             MBB.insert(MII, NewMIs[0]);
1454             InvalidateKills(MI, RegKills, KillOps);
1455             VRM.RemoveMachineInstrFromMaps(&MI);
1456             MBB.erase(&MI);
1457             Erased = true;
1458             --NextMII;  // backtrack to the unfolded instruction.
1459             BackTracked = true;
1460             goto ProcessNextInst;
1461           }
1462         }
1463       }
1464
1465       // If this reference is not a use, any previous store is now dead.
1466       // Otherwise, the store to this stack slot is not dead anymore.
1467       MachineInstr* DeadStore = MaybeDeadStores[SS];
1468       if (DeadStore) {
1469         bool isDead = !(MR & VirtRegMap::isRef);
1470         MachineInstr *NewStore = NULL;
1471         if (MR & VirtRegMap::isModRef) {
1472           unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
1473           SmallVector<MachineInstr*, 4> NewMIs;
1474           // We can reuse this physreg as long as we are allowed to clobber
1475           // the value and there isn't an earlier def that has already clobbered
1476           // the physreg.
1477           if (PhysReg &&
1478               !ReusedOperands.isClobbered(PhysReg) &&
1479               Spills.canClobberPhysReg(PhysReg) &&
1480               !TII->isStoreToStackSlot(&MI, SS)) { // Not profitable!
1481             MachineOperand *KillOpnd =
1482               DeadStore->findRegisterUseOperand(PhysReg, true);
1483             // Note, if the store is storing a sub-register, it's possible the
1484             // super-register is needed below.
1485             if (KillOpnd && !KillOpnd->getSubReg() &&
1486                 TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, true,NewMIs)){
1487               MBB.insert(MII, NewMIs[0]);
1488               NewStore = NewMIs[1];
1489               MBB.insert(MII, NewStore);
1490               VRM.addSpillSlotUse(SS, NewStore);
1491               InvalidateKills(MI, RegKills, KillOps);
1492               VRM.RemoveMachineInstrFromMaps(&MI);
1493               MBB.erase(&MI);
1494               Erased = true;
1495               --NextMII;
1496               --NextMII;  // backtrack to the unfolded instruction.
1497               BackTracked = true;
1498               isDead = true;
1499               ++NumSUnfold;
1500             }
1501           }
1502         }
1503
1504         if (isDead) {  // Previous store is dead.
1505           // If we get here, the store is dead, nuke it now.
1506           DOUT << "Removed dead store:\t" << *DeadStore;
1507           InvalidateKills(*DeadStore, RegKills, KillOps);
1508           VRM.RemoveMachineInstrFromMaps(DeadStore);
1509           MBB.erase(DeadStore);
1510           if (!NewStore)
1511             ++NumDSE;
1512         }
1513
1514         MaybeDeadStores[SS] = NULL;
1515         if (NewStore) {
1516           // Treat this store as a spill merged into a copy. That makes the
1517           // stack slot value available.
1518           VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod);
1519           goto ProcessNextInst;
1520         }
1521       }
1522
1523       // If the spill slot value is available, and this is a new definition of
1524       // the value, the value is not available anymore.
1525       if (MR & VirtRegMap::isMod) {
1526         // Notice that the value in this stack slot has been modified.
1527         Spills.ModifyStackSlotOrReMat(SS);
1528
1529         // If this is *just* a mod of the value, check to see if this is just a
1530         // store to the spill slot (i.e. the spill got merged into the copy). If
1531         // so, realize that the vreg is available now, and add the store to the
1532         // MaybeDeadStore info.
1533         int StackSlot;
1534         if (!(MR & VirtRegMap::isRef)) {
1535           if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
1536             assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
1537                    "Src hasn't been allocated yet?");
1538
1539             if (CommuteToFoldReload(MBB, MII, VirtReg, SrcReg, StackSlot,
1540                                     Spills, RegKills, KillOps, TRI, VRM)) {
1541               NextMII = next(MII);
1542               BackTracked = true;
1543               goto ProcessNextInst;
1544             }
1545
1546             // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
1547             // this as a potentially dead store in case there is a subsequent
1548             // store into the stack slot without a read from it.
1549             MaybeDeadStores[StackSlot] = &MI;
1550
1551             // If the stack slot value was previously available in some other
1552             // register, change it now.  Otherwise, make the register
1553             // available in PhysReg.
1554             Spills.addAvailable(StackSlot, SrcReg, MI.killsRegister(SrcReg));
1555           }
1556         }
1557       }
1558     }
1559
1560     // Process all of the spilled defs.
1561     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1562       MachineOperand &MO = MI.getOperand(i);
1563       if (!(MO.isReg() && MO.getReg() && MO.isDef()))
1564         continue;
1565
1566       unsigned VirtReg = MO.getReg();
1567       if (!TargetRegisterInfo::isVirtualRegister(VirtReg)) {
1568         // Check to see if this is a noop copy.  If so, eliminate the
1569         // instruction before considering the dest reg to be changed.
1570         unsigned Src, Dst, SrcSR, DstSR;
1571         if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
1572           ++NumDCE;
1573           DOUT << "Removing now-noop copy: " << MI;
1574           SmallVector<unsigned, 2> KillRegs;
1575           InvalidateKills(MI, RegKills, KillOps, &KillRegs);
1576           if (MO.isDead() && !KillRegs.empty()) {
1577             // Source register or an implicit super/sub-register use is killed.
1578             assert(KillRegs[0] == Dst ||
1579                    TRI->isSubRegister(KillRegs[0], Dst) ||
1580                    TRI->isSuperRegister(KillRegs[0], Dst));
1581             // Last def is now dead.
1582             TransferDeadness(&MBB, Dist, Src, RegKills, KillOps);
1583           }
1584           VRM.RemoveMachineInstrFromMaps(&MI);
1585           MBB.erase(&MI);
1586           Erased = true;
1587           Spills.disallowClobberPhysReg(VirtReg);
1588           goto ProcessNextInst;
1589         }
1590
1591         // If it's not a no-op copy, it clobbers the value in the destreg.
1592         Spills.ClobberPhysReg(VirtReg);
1593         ReusedOperands.markClobbered(VirtReg);
1594
1595         // Check to see if this instruction is a load from a stack slot into
1596         // a register.  If so, this provides the stack slot value in the reg.
1597         int FrameIdx;
1598         if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
1599           assert(DestReg == VirtReg && "Unknown load situation!");
1600
1601           // If it is a folded reference, then it's not safe to clobber.
1602           bool Folded = FoldedSS.count(FrameIdx);
1603           // Otherwise, if it wasn't available, remember that it is now!
1604           Spills.addAvailable(FrameIdx, DestReg, !Folded);
1605           goto ProcessNextInst;
1606         }
1607
1608         continue;
1609       }
1610
1611       unsigned SubIdx = MO.getSubReg();
1612       bool DoReMat = VRM.isReMaterialized(VirtReg);
1613       if (DoReMat)
1614         ReMatDefs.insert(&MI);
1615
1616       // The only vregs left are stack slot definitions.
1617       int StackSlot = VRM.getStackSlot(VirtReg);
1618       const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
1619
1620       // If this def is part of a two-address operand, make sure to execute
1621       // the store from the correct physical register.
1622       unsigned PhysReg;
1623       int TiedOp = MI.getDesc().findTiedToSrcOperand(i);
1624       if (TiedOp != -1) {
1625         PhysReg = MI.getOperand(TiedOp).getReg();
1626         if (SubIdx) {
1627           unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, TRI);
1628           assert(SuperReg && TRI->getSubReg(SuperReg, SubIdx) == PhysReg &&
1629                  "Can't find corresponding super-register!");
1630           PhysReg = SuperReg;
1631         }
1632       } else {
1633         PhysReg = VRM.getPhys(VirtReg);
1634         if (ReusedOperands.isClobbered(PhysReg)) {
1635           // Another def has taken the assigned physreg. It must have been a
1636           // use&def which got it due to reuse. Undo the reuse!
1637           PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
1638                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
1639         }
1640       }
1641
1642       assert(PhysReg && "VR not assigned a physical register?");
1643       RegInfo->setPhysRegUsed(PhysReg);
1644       unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1645       ReusedOperands.markClobbered(RReg);
1646       MI.getOperand(i).setReg(RReg);
1647
1648       if (!MO.isDead()) {
1649         MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
1650         SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true,
1651                           LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
1652         NextMII = next(MII);
1653
1654         // Check to see if this is a noop copy.  If so, eliminate the
1655         // instruction before considering the dest reg to be changed.
1656         {
1657           unsigned Src, Dst, SrcSR, DstSR;
1658           if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
1659             ++NumDCE;
1660             DOUT << "Removing now-noop copy: " << MI;
1661             InvalidateKills(MI, RegKills, KillOps);
1662             VRM.RemoveMachineInstrFromMaps(&MI);
1663             MBB.erase(&MI);
1664             Erased = true;
1665             UpdateKills(*LastStore, RegKills, KillOps, TRI);
1666             goto ProcessNextInst;
1667           }
1668         }
1669       }
1670     }
1671   ProcessNextInst:
1672     DistanceMap.insert(std::make_pair(&MI, Dist++));
1673     if (!Erased && !BackTracked) {
1674       for (MachineBasicBlock::iterator II = &MI; II != NextMII; ++II)
1675         UpdateKills(*II, RegKills, KillOps, TRI);
1676     }
1677     MII = NextMII;
1678   }
1679
1680 }
1681
1682 llvm::Spiller* llvm::createSpiller() {
1683   switch (SpillerOpt) {
1684   default: assert(0 && "Unreachable!");
1685   case local:
1686     return new LocalSpiller();
1687   case simple:
1688     return new SimpleSpiller();
1689   }
1690 }