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