lib/CodeGen/VirtRegRewriter.cpp

   1 //===-- llvm/CodeGen/Rewriter.cpp -  Rewriter -----------------------------===//
   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 "virtregrewriter"
  11 #include "VirtRegRewriter.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(NumAvoided , "Number of reloads deemed unnecessary");
  27 STATISTIC(NumCopified, "Number of available reloads turned into copies");
  28 STATISTIC(NumReMats  , "Number of re-materialization");
  29 STATISTIC(NumLoads   , "Number of loads added");
  30 STATISTIC(NumReused  , "Number of values reused");
  31 STATISTIC(NumDCE     , "Number of copies elided");
  32 STATISTIC(NumSUnfold , "Number of stores unfolded");
  33 STATISTIC(NumModRefUnfold, "Number of modref unfolded");
  34
  35 namespace {
  36   enum RewriterName { simple, local, trivial };
  37 }
  38
  39 static cl::opt<RewriterName>
  40 RewriterOpt("rewriter",
  41             cl::desc("Rewriter to use: (default: local)"),
  42             cl::Prefix,
  43             cl::values(clEnumVal(simple,  "simple rewriter"),
  44                        clEnumVal(local,   "local rewriter"),
  45                        clEnumVal(trivial, "trivial rewriter"),
  46                        clEnumValEnd),
  47             cl::init(local));
  48
  49 VirtRegRewriter::~VirtRegRewriter() {}
  50
  51
  52 // ****************************** //
  53 // Simple Spiller Implementation  //
  54 // ****************************** //
  55
  56 struct VISIBILITY_HIDDEN SimpleRewriter : public VirtRegRewriter {
  57
  58   bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
  59                             LiveIntervals* LIs) {
  60     DOUT << "********** REWRITE MACHINE CODE **********\n";
  61     DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
  62     const TargetMachine &TM = MF.getTarget();
  63     const TargetInstrInfo &TII = *TM.getInstrInfo();
  64     const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
  65
  66
  67     // LoadedRegs - Keep track of which vregs are loaded, so that we only load
  68     // each vreg once (in the case where a spilled vreg is used by multiple
  69     // operands).  This is always smaller than the number of operands to the
  70     // current machine instr, so it should be small.
  71     std::vector<unsigned> LoadedRegs;
  72
  73     for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
  74          MBBI != E; ++MBBI) {
  75       DOUT << MBBI->getBasicBlock()->getName() << ":\n";
  76       MachineBasicBlock &MBB = *MBBI;
  77       for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
  78            MII != E; ++MII) {
  79         MachineInstr &MI = *MII;
  80         for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
  81           MachineOperand &MO = MI.getOperand(i);
  82           if (MO.isReg() && MO.getReg()) {
  83             if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
  84               unsigned VirtReg = MO.getReg();
  85               unsigned SubIdx = MO.getSubReg();
  86               unsigned PhysReg = VRM.getPhys(VirtReg);
  87               unsigned RReg = SubIdx ? TRI.getSubReg(PhysReg, SubIdx) : PhysReg;
  88               if (!VRM.isAssignedReg(VirtReg)) {
  89                 int StackSlot = VRM.getStackSlot(VirtReg);
  90                 const TargetRegisterClass* RC =
  91                                              MF.getRegInfo().getRegClass(VirtReg);
  92
  93                 if (MO.isUse() &&
  94                     std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
  95                              == LoadedRegs.end()) {
  96                   TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
  97                   MachineInstr *LoadMI = prior(MII);
  98                   VRM.addSpillSlotUse(StackSlot, LoadMI);
  99                   LoadedRegs.push_back(VirtReg);
 100                   ++NumLoads;
 101                   DOUT << '\t' << *LoadMI;
 102                 }
 103
 104                 if (MO.isDef()) {
 105                   TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true,
 106                                           StackSlot, RC);
 107                   MachineInstr *StoreMI = next(MII);
 108                   VRM.addSpillSlotUse(StackSlot, StoreMI);
 109                   ++NumStores;
 110                 }
 111               }
 112               MF.getRegInfo().setPhysRegUsed(RReg);
 113               MI.getOperand(i).setReg(RReg);
 114               MI.getOperand(i).setSubReg(0);
 115             } else {
 116               MF.getRegInfo().setPhysRegUsed(MO.getReg());
 117             }
 118           }
 119         }
 120
 121         DOUT << '\t' << MI;
 122         LoadedRegs.clear();
 123       }
 124     }
 125     return true;
 126   }
 127
 128 };
 129
 130 /// This class is intended for use with the new spilling framework only. It
 131 /// rewrites vreg def/uses to use the assigned preg, but does not insert any
 132 /// spill code.
 133 struct VISIBILITY_HIDDEN TrivialRewriter : public VirtRegRewriter {
 134
 135   bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
 136                             LiveIntervals* LIs) {
 137     DOUT << "********** REWRITE MACHINE CODE **********\n";
 138     DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
 139     MachineRegisterInfo *mri = &MF.getRegInfo();
 140
 141     bool changed = false;
 142
 143     for (LiveIntervals::iterator liItr = LIs->begin(), liEnd = LIs->end();
 144          liItr != liEnd; ++liItr) {
 145
 146       if (TargetRegisterInfo::isVirtualRegister(liItr->first)) {
 147         if (VRM.hasPhys(liItr->first)) {
 148           unsigned preg = VRM.getPhys(liItr->first);
 149           mri->replaceRegWith(liItr->first, preg);
 150           mri->setPhysRegUsed(preg);
 151           changed = true;
 152         }
 153       }
 154       else {
 155         if (!liItr->second->empty()) {
 156           mri->setPhysRegUsed(liItr->first);
 157         }
 158       }
 159     }
 160
 161     return changed;
 162   }
 163
 164 };
 165
 166 // ************************************************************************ //
 167
 168 /// AvailableSpills - As the local rewriter is scanning and rewriting an MBB
 169 /// from top down, keep track of which spill slots or remat are available in
 170 /// each register.
 171 ///
 172 /// Note that not all physregs are created equal here.  In particular, some
 173 /// physregs are reloads that we are allowed to clobber or ignore at any time.
 174 /// Other physregs are values that the register allocated program is using
 175 /// that we cannot CHANGE, but we can read if we like.  We keep track of this
 176 /// on a per-stack-slot / remat id basis as the low bit in the value of the
 177 /// SpillSlotsAvailable entries.  The predicate 'canClobberPhysReg()' checks
 178 /// this bit and addAvailable sets it if.
 179 class VISIBILITY_HIDDEN AvailableSpills {
 180   const TargetRegisterInfo *TRI;
 181   const TargetInstrInfo *TII;
 182
 183   // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
 184   // or remat'ed virtual register values that are still available, due to
 185   // being loaded or stored to, but not invalidated yet.
 186   std::map<int, unsigned> SpillSlotsOrReMatsAvailable;
 187
 188   // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
 189   // indicating which stack slot values are currently held by a physreg.  This
 190   // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
 191   // physreg is modified.
 192   std::multimap<unsigned, int> PhysRegsAvailable;
 193
 194   void disallowClobberPhysRegOnly(unsigned PhysReg);
 195
 196   void ClobberPhysRegOnly(unsigned PhysReg);
 197 public:
 198   AvailableSpills(const TargetRegisterInfo *tri, const TargetInstrInfo *tii)
 199     : TRI(tri), TII(tii) {
 200   }
 201
 202   /// clear - Reset the state.
 203   void clear() {
 204     SpillSlotsOrReMatsAvailable.clear();
 205     PhysRegsAvailable.clear();
 206   }
 207
 208   const TargetRegisterInfo *getRegInfo() const { return TRI; }
 209
 210   /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
 211   /// available in a physical register, return that PhysReg, otherwise
 212   /// return 0.
 213   unsigned getSpillSlotOrReMatPhysReg(int Slot) const {
 214     std::map<int, unsigned>::const_iterator I =
 215       SpillSlotsOrReMatsAvailable.find(Slot);
 216     if (I != SpillSlotsOrReMatsAvailable.end()) {
 217       return I->second >> 1;  // Remove the CanClobber bit.
 218     }
 219     return 0;
 220   }
 221
 222   /// addAvailable - Mark that the specified stack slot / remat is available
 223   /// in the specified physreg.  If CanClobber is true, the physreg can be
 224   /// modified at any time without changing the semantics of the program.
 225   void addAvailable(int SlotOrReMat, unsigned Reg, bool CanClobber = true) {
 226     // If this stack slot is thought to be available in some other physreg,
 227     // remove its record.
 228     ModifyStackSlotOrReMat(SlotOrReMat);
 229
 230     PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat));
 231     SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) |
 232                                               (unsigned)CanClobber;
 233
 234     if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
 235       DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1;
 236     else
 237       DOUT << "Remembering SS#" << SlotOrReMat;
 238     DOUT << " in physreg " << TRI->getName(Reg) << "\n";
 239   }
 240
 241   /// canClobberPhysRegForSS - Return true if the spiller is allowed to change
 242   /// the value of the specified stackslot register if it desires. The
 243   /// specified stack slot must be available in a physreg for this query to
 244   /// make sense.
 245   bool canClobberPhysRegForSS(int SlotOrReMat) const {
 246     assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
 247            "Value not available!");
 248     return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
 249   }
 250
 251   /// canClobberPhysReg - Return true if the spiller is allowed to clobber the
 252   /// physical register where values for some stack slot(s) might be
 253   /// available.
 254   bool canClobberPhysReg(unsigned PhysReg) const {
 255     std::multimap<unsigned, int>::const_iterator I =
 256       PhysRegsAvailable.lower_bound(PhysReg);
 257     while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 258       int SlotOrReMat = I->second;
 259       I++;
 260       if (!canClobberPhysRegForSS(SlotOrReMat))
 261         return false;
 262     }
 263     return true;
 264   }
 265
 266   /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
 267   /// stackslot register. The register is still available but is no longer
 268   /// allowed to be modifed.
 269   void disallowClobberPhysReg(unsigned PhysReg);
 270
 271   /// ClobberPhysReg - This is called when the specified physreg changes
 272   /// value.  We use this to invalidate any info about stuff that lives in
 273   /// it and any of its aliases.
 274   void ClobberPhysReg(unsigned PhysReg);
 275
 276   /// ModifyStackSlotOrReMat - This method is called when the value in a stack
 277   /// slot changes.  This removes information about which register the
 278   /// previous value for this slot lives in (as the previous value is dead
 279   /// now).
 280   void ModifyStackSlotOrReMat(int SlotOrReMat);
 281
 282   /// AddAvailableRegsToLiveIn - Availability information is being kept coming
 283   /// into the specified MBB. Add available physical registers as potential
 284   /// live-in's. If they are reused in the MBB, they will be added to the
 285   /// live-in set to make register scavenger and post-allocation scheduler.
 286   void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
 287                                 std::vector<MachineOperand*> &KillOps);
 288 };
 289
 290 // ************************************************************************ //
 291
 292 // ReusedOp - For each reused operand, we keep track of a bit of information,
 293 // in case we need to rollback upon processing a new operand.  See comments
 294 // below.
 295 struct ReusedOp {
 296   // The MachineInstr operand that reused an available value.
 297   unsigned Operand;
 298
 299   // StackSlotOrReMat - The spill slot or remat id of the value being reused.
 300   unsigned StackSlotOrReMat;
 301
 302   // PhysRegReused - The physical register the value was available in.
 303   unsigned PhysRegReused;
 304
 305   // AssignedPhysReg - The physreg that was assigned for use by the reload.
 306   unsigned AssignedPhysReg;
 307
 308   // VirtReg - The virtual register itself.
 309   unsigned VirtReg;
 310
 311   ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
 312            unsigned vreg)
 313     : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
 314       AssignedPhysReg(apr), VirtReg(vreg) {}
 315 };
 316
 317 /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
 318 /// is reused instead of reloaded.
 319 class VISIBILITY_HIDDEN ReuseInfo {
 320   MachineInstr &MI;
 321   std::vector<ReusedOp> Reuses;
 322   BitVector PhysRegsClobbered;
 323 public:
 324   ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
 325     PhysRegsClobbered.resize(tri->getNumRegs());
 326   }
 327
 328   bool hasReuses() const {
 329     return !Reuses.empty();
 330   }
 331
 332   /// addReuse - If we choose to reuse a virtual register that is already
 333   /// available instead of reloading it, remember that we did so.
 334   void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
 335                 unsigned PhysRegReused, unsigned AssignedPhysReg,
 336                 unsigned VirtReg) {
 337     // If the reload is to the assigned register anyway, no undo will be
 338     // required.
 339     if (PhysRegReused == AssignedPhysReg) return;
 340
 341     // Otherwise, remember this.
 342     Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused,
 343                               AssignedPhysReg, VirtReg));
 344   }
 345
 346   void markClobbered(unsigned PhysReg) {
 347     PhysRegsClobbered.set(PhysReg);
 348   }
 349
 350   bool isClobbered(unsigned PhysReg) const {
 351     return PhysRegsClobbered.test(PhysReg);
 352   }
 353
 354   /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 355   /// is some other operand that is using the specified register, either pick
 356   /// a new register to use, or evict the previous reload and use this reg.
 357   unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 358                            AvailableSpills &Spills,
 359                            std::vector<MachineInstr*> &MaybeDeadStores,
 360                            SmallSet<unsigned, 8> &Rejected,
 361                            BitVector &RegKills,
 362                            std::vector<MachineOperand*> &KillOps,
 363                            VirtRegMap &VRM);
 364
 365   /// GetRegForReload - Helper for the above GetRegForReload(). Add a
 366   /// 'Rejected' set to remember which registers have been considered and
 367   /// rejected for the reload. This avoids infinite looping in case like
 368   /// this:
 369   /// t1 := op t2, t3
 370   /// t2 <- assigned r0 for use by the reload but ended up reuse r1
 371   /// t3 <- assigned r1 for use by the reload but ended up reuse r0
 372   /// t1 <- desires r1
 373   ///       sees r1 is taken by t2, tries t2's reload register r0
 374   ///       sees r0 is taken by t3, tries t3's reload register r1
 375   ///       sees r1 is taken by t2, tries t2's reload register r0 ...
 376   unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 377                            AvailableSpills &Spills,
 378                            std::vector<MachineInstr*> &MaybeDeadStores,
 379                            BitVector &RegKills,
 380                            std::vector<MachineOperand*> &KillOps,
 381                            VirtRegMap &VRM) {
 382     SmallSet<unsigned, 8> Rejected;
 383     return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
 384                            RegKills, KillOps, VRM);
 385   }
 386 };
 387
 388
 389 // ****************** //
 390 // Utility Functions  //
 391 // ****************** //
 392
 393 /// findSinglePredSuccessor - Return via reference a vector of machine basic
 394 /// blocks each of which is a successor of the specified BB and has no other
 395 /// predecessor.
 396 static void findSinglePredSuccessor(MachineBasicBlock *MBB,
 397                                    SmallVectorImpl<MachineBasicBlock *> &Succs) {
 398   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
 399          SE = MBB->succ_end(); SI != SE; ++SI) {
 400     MachineBasicBlock *SuccMBB = *SI;
 401     if (SuccMBB->pred_size() == 1)
 402       Succs.push_back(SuccMBB);
 403   }
 404 }
 405
 406 /// InvalidateKill - Invalidate register kill information for a specific
 407 /// register. This also unsets the kills marker on the last kill operand.
 408 static void InvalidateKill(unsigned Reg,
 409                            const TargetRegisterInfo* TRI,
 410                            BitVector &RegKills,
 411                            std::vector<MachineOperand*> &KillOps) {
 412   if (RegKills[Reg]) {
 413     KillOps[Reg]->setIsKill(false);
 414     // KillOps[Reg] might be a def of a super-register.
 415     unsigned KReg = KillOps[Reg]->getReg();
 416     KillOps[KReg] = NULL;
 417     RegKills.reset(KReg);
 418     for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
 419       if (RegKills[*SR]) {
 420         KillOps[*SR]->setIsKill(false);
 421         KillOps[*SR] = NULL;
 422         RegKills.reset(*SR);
 423       }
 424     }
 425   }
 426 }
 427
 428 /// InvalidateKills - MI is going to be deleted. If any of its operands are
 429 /// marked kill, then invalidate the information.
 430 static void InvalidateKills(MachineInstr &MI,
 431                             const TargetRegisterInfo* TRI,
 432                             BitVector &RegKills,
 433                             std::vector<MachineOperand*> &KillOps,
 434                             SmallVector<unsigned, 2> *KillRegs = NULL) {
 435   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 436     MachineOperand &MO = MI.getOperand(i);
 437     if (!MO.isReg() || !MO.isUse() || !MO.isKill())
 438       continue;
 439     unsigned Reg = MO.getReg();
 440     if (TargetRegisterInfo::isVirtualRegister(Reg))
 441       continue;
 442     if (KillRegs)
 443       KillRegs->push_back(Reg);
 444     assert(Reg < KillOps.size());
 445     if (KillOps[Reg] == &MO) {
 446       KillOps[Reg] = NULL;
 447       RegKills.reset(Reg);
 448       for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
 449         if (RegKills[*SR]) {
 450           KillOps[*SR] = NULL;
 451           RegKills.reset(*SR);
 452         }
 453       }
 454     }
 455   }
 456 }
 457
 458 /// InvalidateRegDef - If the def operand of the specified def MI is now dead
 459 /// (since it's spill instruction is removed), mark it isDead. Also checks if
 460 /// the def MI has other definition operands that are not dead. Returns it by
 461 /// reference.
 462 static bool InvalidateRegDef(MachineBasicBlock::iterator I,
 463                              MachineInstr &NewDef, unsigned Reg,
 464                              bool &HasLiveDef) {
 465   // Due to remat, it's possible this reg isn't being reused. That is,
 466   // the def of this reg (by prev MI) is now dead.
 467   MachineInstr *DefMI = I;
 468   MachineOperand *DefOp = NULL;
 469   for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
 470     MachineOperand &MO = DefMI->getOperand(i);
 471     if (MO.isReg() && MO.isDef()) {
 472       if (MO.getReg() == Reg)
 473         DefOp = &MO;
 474       else if (!MO.isDead())
 475         HasLiveDef = true;
 476     }
 477   }
 478   if (!DefOp)
 479     return false;
 480
 481   bool FoundUse = false, Done = false;
 482   MachineBasicBlock::iterator E = &NewDef;
 483   ++I; ++E;
 484   for (; !Done && I != E; ++I) {
 485     MachineInstr *NMI = I;
 486     for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) {
 487       MachineOperand &MO = NMI->getOperand(j);
 488       if (!MO.isReg() || MO.getReg() != Reg)
 489         continue;
 490       if (MO.isUse())
 491         FoundUse = true;
 492       Done = true; // Stop after scanning all the operands of this MI.
 493     }
 494   }
 495   if (!FoundUse) {
 496     // Def is dead!
 497     DefOp->setIsDead();
 498     return true;
 499   }
 500   return false;
 501 }
 502
 503 /// UpdateKills - Track and update kill info. If a MI reads a register that is
 504 /// marked kill, then it must be due to register reuse. Transfer the kill info
 505 /// over.
 506 static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI,
 507                         BitVector &RegKills,
 508                         std::vector<MachineOperand*> &KillOps) {
 509   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 510     MachineOperand &MO = MI.getOperand(i);
 511     if (!MO.isReg() || !MO.isUse())
 512       continue;
 513     unsigned Reg = MO.getReg();
 514     if (Reg == 0)
 515       continue;
 516
 517     if (RegKills[Reg] && KillOps[Reg]->getParent() != &MI) {
 518       // That can't be right. Register is killed but not re-defined and it's
 519       // being reused. Let's fix that.
 520       KillOps[Reg]->setIsKill(false);
 521       // KillOps[Reg] might be a def of a super-register.
 522       unsigned KReg = KillOps[Reg]->getReg();
 523       KillOps[KReg] = NULL;
 524       RegKills.reset(KReg);
 525
 526       // Must be a def of a super-register. Its other sub-regsters are no
 527       // longer killed as well.
 528       for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
 529         KillOps[*SR] = NULL;
 530         RegKills.reset(*SR);
 531       }
 532
 533       if (!MI.isRegTiedToDefOperand(i))
 534         // Unless it's a two-address operand, this is the new kill.
 535         MO.setIsKill();
 536     }
 537     if (MO.isKill()) {
 538       RegKills.set(Reg);
 539       KillOps[Reg] = &MO;
 540       for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
 541         RegKills.set(*SR);
 542         KillOps[*SR] = &MO;
 543       }
 544     }
 545   }
 546
 547   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 548     const MachineOperand &MO = MI.getOperand(i);
 549     if (!MO.isReg() || !MO.isDef())
 550       continue;
 551     unsigned Reg = MO.getReg();
 552     RegKills.reset(Reg);
 553     KillOps[Reg] = NULL;
 554     // It also defines (or partially define) aliases.
 555     for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
 556       RegKills.reset(*SR);
 557       KillOps[*SR] = NULL;
 558     }
 559   }
 560 }
 561
 562 /// ReMaterialize - Re-materialize definition for Reg targetting DestReg.
 563 ///
 564 static void ReMaterialize(MachineBasicBlock &MBB,
 565                           MachineBasicBlock::iterator &MII,
 566                           unsigned DestReg, unsigned Reg,
 567                           const TargetInstrInfo *TII,
 568                           const TargetRegisterInfo *TRI,
 569                           VirtRegMap &VRM) {
 570   TII->reMaterialize(MBB, MII, DestReg, VRM.getReMaterializedMI(Reg));
 571   MachineInstr *NewMI = prior(MII);
 572   for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
 573     MachineOperand &MO = NewMI->getOperand(i);
 574     if (!MO.isReg() || MO.getReg() == 0)
 575       continue;
 576     unsigned VirtReg = MO.getReg();
 577     if (TargetRegisterInfo::isPhysicalRegister(VirtReg))
 578       continue;
 579     assert(MO.isUse());
 580     unsigned SubIdx = MO.getSubReg();
 581     unsigned Phys = VRM.getPhys(VirtReg);
 582     assert(Phys);
 583     unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
 584     MO.setReg(RReg);
 585     MO.setSubReg(0);
 586   }
 587   ++NumReMats;
 588 }
 589
 590 /// findSuperReg - Find the SubReg's super-register of given register class
 591 /// where its SubIdx sub-register is SubReg.
 592 static unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg,
 593                              unsigned SubIdx, const TargetRegisterInfo *TRI) {
 594   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
 595        I != E; ++I) {
 596     unsigned Reg = *I;
 597     if (TRI->getSubReg(Reg, SubIdx) == SubReg)
 598       return Reg;
 599   }
 600   return 0;
 601 }
 602
 603 // ******************************** //
 604 // Available Spills Implementation  //
 605 // ******************************** //
 606
 607 /// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified
 608 /// stackslot register. The register is still available but is no longer
 609 /// allowed to be modifed.
 610 void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) {
 611   std::multimap<unsigned, int>::iterator I =
 612     PhysRegsAvailable.lower_bound(PhysReg);
 613   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 614     int SlotOrReMat = I->second;
 615     I++;
 616     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
 617            "Bidirectional map mismatch!");
 618     SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1;
 619     DOUT << "PhysReg " << TRI->getName(PhysReg)
 620          << " copied, it is available for use but can no longer be modified\n";
 621   }
 622 }
 623
 624 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
 625 /// stackslot register and its aliases. The register and its aliases may
 626 /// still available but is no longer allowed to be modifed.
 627 void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) {
 628   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
 629     disallowClobberPhysRegOnly(*AS);
 630   disallowClobberPhysRegOnly(PhysReg);
 631 }
 632
 633 /// ClobberPhysRegOnly - This is called when the specified physreg changes
 634 /// value.  We use this to invalidate any info about stuff we thing lives in it.
 635 void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
 636   std::multimap<unsigned, int>::iterator I =
 637     PhysRegsAvailable.lower_bound(PhysReg);
 638   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 639     int SlotOrReMat = I->second;
 640     PhysRegsAvailable.erase(I++);
 641     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
 642            "Bidirectional map mismatch!");
 643     SpillSlotsOrReMatsAvailable.erase(SlotOrReMat);
 644     DOUT << "PhysReg " << TRI->getName(PhysReg)
 645          << " clobbered, invalidating ";
 646     if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
 647       DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
 648     else
 649       DOUT << "SS#" << SlotOrReMat << "\n";
 650   }
 651 }
 652
 653 /// ClobberPhysReg - This is called when the specified physreg changes
 654 /// value.  We use this to invalidate any info about stuff we thing lives in
 655 /// it and any of its aliases.
 656 void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
 657   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
 658     ClobberPhysRegOnly(*AS);
 659   ClobberPhysRegOnly(PhysReg);
 660 }
 661
 662 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
 663 /// into the specified MBB. Add available physical registers as potential
 664 /// live-in's. If they are reused in the MBB, they will be added to the
 665 /// live-in set to make register scavenger and post-allocation scheduler.
 666 void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock &MBB,
 667                                         BitVector &RegKills,
 668                                         std::vector<MachineOperand*> &KillOps) {
 669   std::set<unsigned> NotAvailable;
 670   for (std::multimap<unsigned, int>::iterator
 671          I = PhysRegsAvailable.begin(), E = PhysRegsAvailable.end();
 672        I != E; ++I) {
 673     unsigned Reg = I->first;
 674     const TargetRegisterClass* RC = TRI->getPhysicalRegisterRegClass(Reg);
 675     // FIXME: A temporary workaround. We can't reuse available value if it's
 676     // not safe to move the def of the virtual register's class. e.g.
 677     // X86::RFP* register classes. Do not add it as a live-in.
 678     if (!TII->isSafeToMoveRegClassDefs(RC))
 679       // This is no longer available.
 680       NotAvailable.insert(Reg);
 681     else {
 682       MBB.addLiveIn(Reg);
 683       InvalidateKill(Reg, TRI, RegKills, KillOps);
 684     }
 685
 686     // Skip over the same register.
 687     std::multimap<unsigned, int>::iterator NI = next(I);
 688     while (NI != E && NI->first == Reg) {
 689       ++I;
 690       ++NI;
 691     }
 692   }
 693
 694   for (std::set<unsigned>::iterator I = NotAvailable.begin(),
 695          E = NotAvailable.end(); I != E; ++I) {
 696     ClobberPhysReg(*I);
 697     for (const unsigned *SubRegs = TRI->getSubRegisters(*I);
 698        *SubRegs; ++SubRegs)
 699       ClobberPhysReg(*SubRegs);
 700   }
 701 }
 702
 703 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
 704 /// slot changes.  This removes information about which register the previous
 705 /// value for this slot lives in (as the previous value is dead now).
 706 void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) {
 707   std::map<int, unsigned>::iterator It =
 708     SpillSlotsOrReMatsAvailable.find(SlotOrReMat);
 709   if (It == SpillSlotsOrReMatsAvailable.end()) return;
 710   unsigned Reg = It->second >> 1;
 711   SpillSlotsOrReMatsAvailable.erase(It);
 712
 713   // This register may hold the value of multiple stack slots, only remove this
 714   // stack slot from the set of values the register contains.
 715   std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
 716   for (; ; ++I) {
 717     assert(I != PhysRegsAvailable.end() && I->first == Reg &&
 718            "Map inverse broken!");
 719     if (I->second == SlotOrReMat) break;
 720   }
 721   PhysRegsAvailable.erase(I);
 722 }
 723
 724 // ************************** //
 725 // Reuse Info Implementation  //
 726 // ************************** //
 727
 728 /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 729 /// is some other operand that is using the specified register, either pick
 730 /// a new register to use, or evict the previous reload and use this reg.
 731 unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 732                          AvailableSpills &Spills,
 733                          std::vector<MachineInstr*> &MaybeDeadStores,
 734                          SmallSet<unsigned, 8> &Rejected,
 735                          BitVector &RegKills,
 736                          std::vector<MachineOperand*> &KillOps,
 737                          VirtRegMap &VRM) {
 738   const TargetInstrInfo* TII = MI->getParent()->getParent()->getTarget()
 739                                .getInstrInfo();
 740
 741   if (Reuses.empty()) return PhysReg;  // This is most often empty.
 742
 743   for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
 744     ReusedOp &Op = Reuses[ro];
 745     // If we find some other reuse that was supposed to use this register
 746     // exactly for its reload, we can change this reload to use ITS reload
 747     // register. That is, unless its reload register has already been
 748     // considered and subsequently rejected because it has also been reused
 749     // by another operand.
 750     if (Op.PhysRegReused == PhysReg &&
 751         Rejected.count(Op.AssignedPhysReg) == 0) {
 752       // Yup, use the reload register that we didn't use before.
 753       unsigned NewReg = Op.AssignedPhysReg;
 754       Rejected.insert(PhysReg);
 755       return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected,
 756                              RegKills, KillOps, VRM);
 757     } else {
 758       // Otherwise, we might also have a problem if a previously reused
 759       // value aliases the new register.  If so, codegen the previous reload
 760       // and use this one.
 761       unsigned PRRU = Op.PhysRegReused;
 762       const TargetRegisterInfo *TRI = Spills.getRegInfo();
 763       if (TRI->areAliases(PRRU, PhysReg)) {
 764         // Okay, we found out that an alias of a reused register
 765         // was used.  This isn't good because it means we have
 766         // to undo a previous reuse.
 767         MachineBasicBlock *MBB = MI->getParent();
 768         const TargetRegisterClass *AliasRC =
 769           MBB->getParent()->getRegInfo().getRegClass(Op.VirtReg);
 770
 771         // Copy Op out of the vector and remove it, we're going to insert an
 772         // explicit load for it.
 773         ReusedOp NewOp = Op;
 774         Reuses.erase(Reuses.begin()+ro);
 775
 776         // Ok, we're going to try to reload the assigned physreg into the
 777         // slot that we were supposed to in the first place.  However, that
 778         // register could hold a reuse.  Check to see if it conflicts or
 779         // would prefer us to use a different register.
 780         unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg,
 781                                               MI, Spills, MaybeDeadStores,
 782                                           Rejected, RegKills, KillOps, VRM);
 783
 784         MachineBasicBlock::iterator MII = MI;
 785         if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) {
 786           ReMaterialize(*MBB, MII, NewPhysReg, NewOp.VirtReg, TII, TRI,VRM);
 787         } else {
 788           TII->loadRegFromStackSlot(*MBB, MII, NewPhysReg,
 789                                     NewOp.StackSlotOrReMat, AliasRC);
 790           MachineInstr *LoadMI = prior(MII);
 791           VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI);
 792           // Any stores to this stack slot are not dead anymore.
 793           MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL;
 794           ++NumLoads;
 795         }
 796         Spills.ClobberPhysReg(NewPhysReg);
 797         Spills.ClobberPhysReg(NewOp.PhysRegReused);
 798
 799         unsigned SubIdx = MI->getOperand(NewOp.Operand).getSubReg();
 800         unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) : NewPhysReg;
 801         MI->getOperand(NewOp.Operand).setReg(RReg);
 802         MI->getOperand(NewOp.Operand).setSubReg(0);
 803
 804         Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg);
 805         --MII;
 806         UpdateKills(*MII, TRI, RegKills, KillOps);
 807         DOUT << '\t' << *MII;
 808
 809         DOUT << "Reuse undone!\n";
 810         --NumReused;
 811
 812         // Finally, PhysReg is now available, go ahead and use it.
 813         return PhysReg;
 814       }
 815     }
 816   }
 817   return PhysReg;
 818 }
 819
 820 // ************************************************************************ //
 821
 822 /// FoldsStackSlotModRef - Return true if the specified MI folds the specified
 823 /// stack slot mod/ref. It also checks if it's possible to unfold the
 824 /// instruction by having it define a specified physical register instead.
 825 static bool FoldsStackSlotModRef(MachineInstr &MI, int SS, unsigned PhysReg,
 826                                  const TargetInstrInfo *TII,
 827                                  const TargetRegisterInfo *TRI,
 828                                  VirtRegMap &VRM) {
 829   if (VRM.hasEmergencySpills(&MI) || VRM.isSpillPt(&MI))
 830     return false;
 831
 832   bool Found = false;
 833   VirtRegMap::MI2VirtMapTy::const_iterator I, End;
 834   for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
 835     unsigned VirtReg = I->second.first;
 836     VirtRegMap::ModRef MR = I->second.second;
 837     if (MR & VirtRegMap::isModRef)
 838       if (VRM.getStackSlot(VirtReg) == SS) {
 839         Found= TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), true, true) != 0;
 840         break;
 841       }
 842   }
 843   if (!Found)
 844     return false;
 845
 846   // Does the instruction uses a register that overlaps the scratch register?
 847   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 848     MachineOperand &MO = MI.getOperand(i);
 849     if (!MO.isReg() || MO.getReg() == 0)
 850       continue;
 851     unsigned Reg = MO.getReg();
 852     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
 853       if (!VRM.hasPhys(Reg))
 854         continue;
 855       Reg = VRM.getPhys(Reg);
 856     }
 857     if (TRI->regsOverlap(PhysReg, Reg))
 858       return false;
 859   }
 860   return true;
 861 }
 862
 863 /// FindFreeRegister - Find a free register of a given register class by looking
 864 /// at (at most) the last two machine instructions.
 865 static unsigned FindFreeRegister(MachineBasicBlock::iterator MII,
 866                                  MachineBasicBlock &MBB,
 867                                  const TargetRegisterClass *RC,
 868                                  const TargetRegisterInfo *TRI,
 869                                  BitVector &AllocatableRegs) {
 870   BitVector Defs(TRI->getNumRegs());
 871   BitVector Uses(TRI->getNumRegs());
 872   SmallVector<unsigned, 4> LocalUses;
 873   SmallVector<unsigned, 4> Kills;
 874
 875   // Take a look at 2 instructions at most.
 876   for (unsigned Count = 0; Count < 2; ++Count) {
 877     if (MII == MBB.begin())
 878       break;
 879     MachineInstr *PrevMI = prior(MII);
 880     for (unsigned i = 0, e = PrevMI->getNumOperands(); i != e; ++i) {
 881       MachineOperand &MO = PrevMI->getOperand(i);
 882       if (!MO.isReg() || MO.getReg() == 0)
 883         continue;
 884       unsigned Reg = MO.getReg();
 885       if (MO.isDef()) {
 886         Defs.set(Reg);
 887         for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
 888           Defs.set(*AS);
 889       } else  {
 890         LocalUses.push_back(Reg);
 891         if (MO.isKill() && AllocatableRegs[Reg])
 892           Kills.push_back(Reg);
 893       }
 894     }
 895
 896     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
 897       unsigned Kill = Kills[i];
 898       if (!Defs[Kill] && !Uses[Kill] &&
 899           TRI->getPhysicalRegisterRegClass(Kill) == RC)
 900         return Kill;
 901     }
 902     for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
 903       unsigned Reg = LocalUses[i];
 904       Uses.set(Reg);
 905       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
 906         Uses.set(*AS);
 907     }
 908
 909     MII = PrevMI;
 910   }
 911
 912   return 0;
 913 }
 914
 915 static
 916 void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg) {
 917   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
 918     MachineOperand &MO = MI->getOperand(i);
 919     if (MO.isReg() && MO.getReg() == VirtReg)
 920       MO.setReg(PhysReg);
 921   }
 922 }
 923
 924 namespace {
 925   struct RefSorter {
 926     bool operator()(const std::pair<MachineInstr*, int> &A,
 927                     const std::pair<MachineInstr*, int> &B) {
 928       return A.second < B.second;
 929     }
 930   };
 931 }
 932
 933 // ***************************** //
 934 // Local Spiller Implementation  //
 935 // ***************************** //
 936
 937 class VISIBILITY_HIDDEN LocalRewriter : public VirtRegRewriter {
 938   MachineRegisterInfo *RegInfo;
 939   const TargetRegisterInfo *TRI;
 940   const TargetInstrInfo *TII;
 941   BitVector AllocatableRegs;
 942   DenseMap<MachineInstr*, unsigned> DistanceMap;
 943 public:
 944
 945   bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
 946                             LiveIntervals* LIs) {
 947     RegInfo = &MF.getRegInfo();
 948     TRI = MF.getTarget().getRegisterInfo();
 949     TII = MF.getTarget().getInstrInfo();
 950     AllocatableRegs = TRI->getAllocatableSet(MF);
 951     DOUT << "\n**** Local spiller rewriting function '"
 952          << MF.getFunction()->getName() << "':\n";
 953     DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)"
 954             " ****\n";
 955     DEBUG(MF.dump());
 956
 957     // Spills - Keep track of which spilled values are available in physregs
 958     // so that we can choose to reuse the physregs instead of emitting
 959     // reloads. This is usually refreshed per basic block.
 960     AvailableSpills Spills(TRI, TII);
 961
 962     // Keep track of kill information.
 963     BitVector RegKills(TRI->getNumRegs());
 964     std::vector<MachineOperand*> KillOps;
 965     KillOps.resize(TRI->getNumRegs(), NULL);
 966
 967     // SingleEntrySuccs - Successor blocks which have a single predecessor.
 968     SmallVector<MachineBasicBlock*, 4> SinglePredSuccs;
 969     SmallPtrSet<MachineBasicBlock*,16> EarlyVisited;
 970
 971     // Traverse the basic blocks depth first.
 972     MachineBasicBlock *Entry = MF.begin();
 973     SmallPtrSet<MachineBasicBlock*,16> Visited;
 974     for (df_ext_iterator<MachineBasicBlock*,
 975            SmallPtrSet<MachineBasicBlock*,16> >
 976            DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
 977          DFI != E; ++DFI) {
 978       MachineBasicBlock *MBB = *DFI;
 979       if (!EarlyVisited.count(MBB))
 980         RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
 981
 982       // If this MBB is the only predecessor of a successor. Keep the
 983       // availability information and visit it next.
 984       do {
 985         // Keep visiting single predecessor successor as long as possible.
 986         SinglePredSuccs.clear();
 987         findSinglePredSuccessor(MBB, SinglePredSuccs);
 988         if (SinglePredSuccs.empty())
 989           MBB = 0;
 990         else {
 991           // FIXME: More than one successors, each of which has MBB has
 992           // the only predecessor.
 993           MBB = SinglePredSuccs[0];
 994           if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
 995             Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
 996             RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
 997           }
 998         }
 999       } while (MBB);
1000
1001       // Clear the availability info.
1002       Spills.clear();
1003     }
1004
1005     DOUT << "**** Post Machine Instrs ****\n";
1006     DEBUG(MF.dump());
1007
1008     // Mark unused spill slots.
1009     MachineFrameInfo *MFI = MF.getFrameInfo();
1010     int SS = VRM.getLowSpillSlot();
1011     if (SS != VirtRegMap::NO_STACK_SLOT)
1012       for (int e = VRM.getHighSpillSlot(); SS <= e; ++SS)
1013         if (!VRM.isSpillSlotUsed(SS)) {
1014           MFI->RemoveStackObject(SS);
1015           ++NumDSS;
1016         }
1017
1018     return true;
1019   }
1020
1021 private:
1022
1023   /// OptimizeByUnfold2 - Unfold a series of load / store folding instructions if
1024   /// a scratch register is available.
1025   ///     xorq  %r12<kill>, %r13
1026   ///     addq  %rax, -184(%rbp)
1027   ///     addq  %r13, -184(%rbp)
1028   /// ==>
1029   ///     xorq  %r12<kill>, %r13
1030   ///     movq  -184(%rbp), %r12
1031   ///     addq  %rax, %r12
1032   ///     addq  %r13, %r12
1033   ///     movq  %r12, -184(%rbp)
1034   bool OptimizeByUnfold2(unsigned VirtReg, int SS,
1035                          MachineBasicBlock &MBB,
1036                          MachineBasicBlock::iterator &MII,
1037                          std::vector<MachineInstr*> &MaybeDeadStores,
1038                          AvailableSpills &Spills,
1039                          BitVector &RegKills,
1040                          std::vector<MachineOperand*> &KillOps,
1041                          VirtRegMap &VRM) {
1042
1043     MachineBasicBlock::iterator NextMII = next(MII);
1044     if (NextMII == MBB.end())
1045       return false;
1046
1047     if (TII->getOpcodeAfterMemoryUnfold(MII->getOpcode(), true, true) == 0)
1048       return false;
1049
1050     // Now let's see if the last couple of instructions happens to have freed up
1051     // a register.
1052     const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1053     unsigned PhysReg = FindFreeRegister(MII, MBB, RC, TRI, AllocatableRegs);
1054     if (!PhysReg)
1055       return false;
1056
1057     MachineFunction &MF = *MBB.getParent();
1058     TRI = MF.getTarget().getRegisterInfo();
1059     MachineInstr &MI = *MII;
1060     if (!FoldsStackSlotModRef(MI, SS, PhysReg, TII, TRI, VRM))
1061       return false;
1062
1063     // If the next instruction also folds the same SS modref and can be unfoled,
1064     // then it's worthwhile to issue a load from SS into the free register and
1065     // then unfold these instructions.
1066     if (!FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM))
1067       return false;
1068
1069     // Load from SS to the spare physical register.
1070     TII->loadRegFromStackSlot(MBB, MII, PhysReg, SS, RC);
1071     // This invalidates Phys.
1072     Spills.ClobberPhysReg(PhysReg);
1073     // Remember it's available.
1074     Spills.addAvailable(SS, PhysReg);
1075     MaybeDeadStores[SS] = NULL;
1076
1077     // Unfold current MI.
1078     SmallVector<MachineInstr*, 4> NewMIs;
1079     if (!TII->unfoldMemoryOperand(MF, &MI, VirtReg, false, false, NewMIs))
1080       assert(0 && "Unable unfold the load / store folding instruction!");
1081     assert(NewMIs.size() == 1);
1082     AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
1083     VRM.transferRestorePts(&MI, NewMIs[0]);
1084     MII = MBB.insert(MII, NewMIs[0]);
1085     InvalidateKills(MI, TRI, RegKills, KillOps);
1086     VRM.RemoveMachineInstrFromMaps(&MI);
1087     MBB.erase(&MI);
1088     ++NumModRefUnfold;
1089
1090     // Unfold next instructions that fold the same SS.
1091     do {
1092       MachineInstr &NextMI = *NextMII;
1093       NextMII = next(NextMII);
1094       NewMIs.clear();
1095       if (!TII->unfoldMemoryOperand(MF, &NextMI, VirtReg, false, false, NewMIs))
1096         assert(0 && "Unable unfold the load / store folding instruction!");
1097       assert(NewMIs.size() == 1);
1098       AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
1099       VRM.transferRestorePts(&NextMI, NewMIs[0]);
1100       MBB.insert(NextMII, NewMIs[0]);
1101       InvalidateKills(NextMI, TRI, RegKills, KillOps);
1102       VRM.RemoveMachineInstrFromMaps(&NextMI);
1103       MBB.erase(&NextMI);
1104       ++NumModRefUnfold;
1105       if (NextMII == MBB.end())
1106         break;
1107     } while (FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM));
1108
1109     // Store the value back into SS.
1110     TII->storeRegToStackSlot(MBB, NextMII, PhysReg, true, SS, RC);
1111     MachineInstr *StoreMI = prior(NextMII);
1112     VRM.addSpillSlotUse(SS, StoreMI);
1113     VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
1114
1115     return true;
1116   }
1117
1118   /// OptimizeByUnfold - Turn a store folding instruction into a load folding
1119   /// instruction. e.g.
1120   ///     xorl  %edi, %eax
1121   ///     movl  %eax, -32(%ebp)
1122   ///     movl  -36(%ebp), %eax
1123   ///     orl   %eax, -32(%ebp)
1124   /// ==>
1125   ///     xorl  %edi, %eax
1126   ///     orl   -36(%ebp), %eax
1127   ///     mov   %eax, -32(%ebp)
1128   /// This enables unfolding optimization for a subsequent instruction which will
1129   /// also eliminate the newly introduced store instruction.
1130   bool OptimizeByUnfold(MachineBasicBlock &MBB,
1131                         MachineBasicBlock::iterator &MII,
1132                         std::vector<MachineInstr*> &MaybeDeadStores,
1133                         AvailableSpills &Spills,
1134                         BitVector &RegKills,
1135                         std::vector<MachineOperand*> &KillOps,
1136                         VirtRegMap &VRM) {
1137     MachineFunction &MF = *MBB.getParent();
1138     MachineInstr &MI = *MII;
1139     unsigned UnfoldedOpc = 0;
1140     unsigned UnfoldPR = 0;
1141     unsigned UnfoldVR = 0;
1142     int FoldedSS = VirtRegMap::NO_STACK_SLOT;
1143     VirtRegMap::MI2VirtMapTy::const_iterator I, End;
1144     for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
1145       // Only transform a MI that folds a single register.
1146       if (UnfoldedOpc)
1147         return false;
1148       UnfoldVR = I->second.first;
1149       VirtRegMap::ModRef MR = I->second.second;
1150       // MI2VirtMap be can updated which invalidate the iterator.
1151       // Increment the iterator first.
1152       ++I;
1153       if (VRM.isAssignedReg(UnfoldVR))
1154         continue;
1155       // If this reference is not a use, any previous store is now dead.
1156       // Otherwise, the store to this stack slot is not dead anymore.
1157       FoldedSS = VRM.getStackSlot(UnfoldVR);
1158       MachineInstr* DeadStore = MaybeDeadStores[FoldedSS];
1159       if (DeadStore && (MR & VirtRegMap::isModRef)) {
1160         unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS);
1161         if (!PhysReg || !DeadStore->readsRegister(PhysReg))
1162           continue;
1163         UnfoldPR = PhysReg;
1164         UnfoldedOpc = TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
1165                                                       false, true);
1166       }
1167     }
1168
1169     if (!UnfoldedOpc) {
1170       if (!UnfoldVR)
1171         return false;
1172
1173       // Look for other unfolding opportunities.
1174       return OptimizeByUnfold2(UnfoldVR, FoldedSS, MBB, MII,
1175                                MaybeDeadStores, Spills, RegKills, KillOps, VRM);
1176     }
1177
1178     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1179       MachineOperand &MO = MI.getOperand(i);
1180       if (!MO.isReg() || MO.getReg() == 0 || !MO.isUse())
1181         continue;
1182       unsigned VirtReg = MO.getReg();
1183       if (TargetRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg())
1184         continue;
1185       if (VRM.isAssignedReg(VirtReg)) {
1186         unsigned PhysReg = VRM.getPhys(VirtReg);
1187         if (PhysReg && TRI->regsOverlap(PhysReg, UnfoldPR))
1188           return false;
1189       } else if (VRM.isReMaterialized(VirtReg))
1190         continue;
1191       int SS = VRM.getStackSlot(VirtReg);
1192       unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
1193       if (PhysReg) {
1194         if (TRI->regsOverlap(PhysReg, UnfoldPR))
1195           return false;
1196         continue;
1197       }
1198       if (VRM.hasPhys(VirtReg)) {
1199         PhysReg = VRM.getPhys(VirtReg);
1200         if (!TRI->regsOverlap(PhysReg, UnfoldPR))
1201           continue;
1202       }
1203
1204       // Ok, we'll need to reload the value into a register which makes
1205       // it impossible to perform the store unfolding optimization later.
1206       // Let's see if it is possible to fold the load if the store is
1207       // unfolded. This allows us to perform the store unfolding
1208       // optimization.
1209       SmallVector<MachineInstr*, 4> NewMIs;
1210       if (TII->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) {
1211         assert(NewMIs.size() == 1);
1212         MachineInstr *NewMI = NewMIs.back();
1213         NewMIs.clear();
1214         int Idx = NewMI->findRegisterUseOperandIdx(VirtReg, false);
1215         assert(Idx != -1);
1216         SmallVector<unsigned, 1> Ops;
1217         Ops.push_back(Idx);
1218         MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, NewMI, Ops, SS);
1219         if (FoldedMI) {
1220           VRM.addSpillSlotUse(SS, FoldedMI);
1221           if (!VRM.hasPhys(UnfoldVR))
1222             VRM.assignVirt2Phys(UnfoldVR, UnfoldPR);
1223           VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
1224           MII = MBB.insert(MII, FoldedMI);
1225           InvalidateKills(MI, TRI, RegKills, KillOps);
1226           VRM.RemoveMachineInstrFromMaps(&MI);
1227           MBB.erase(&MI);
1228           MF.DeleteMachineInstr(NewMI);
1229           return true;
1230         }
1231         MF.DeleteMachineInstr(NewMI);
1232       }
1233     }
1234
1235     return false;
1236   }
1237
1238   /// CommuteToFoldReload -
1239   /// Look for
1240   /// r1 = load fi#1
1241   /// r1 = op r1, r2<kill>
1242   /// store r1, fi#1
1243   ///
1244   /// If op is commutable and r2 is killed, then we can xform these to
1245   /// r2 = op r2, fi#1
1246   /// store r2, fi#1
1247   bool CommuteToFoldReload(MachineBasicBlock &MBB,
1248                            MachineBasicBlock::iterator &MII,
1249                            unsigned VirtReg, unsigned SrcReg, int SS,
1250                            AvailableSpills &Spills,
1251                            BitVector &RegKills,
1252                            std::vector<MachineOperand*> &KillOps,
1253                            const TargetRegisterInfo *TRI,
1254                            VirtRegMap &VRM) {
1255     if (MII == MBB.begin() || !MII->killsRegister(SrcReg))
1256       return false;
1257
1258     MachineFunction &MF = *MBB.getParent();
1259     MachineInstr &MI = *MII;
1260     MachineBasicBlock::iterator DefMII = prior(MII);
1261     MachineInstr *DefMI = DefMII;
1262     const TargetInstrDesc &TID = DefMI->getDesc();
1263     unsigned NewDstIdx;
1264     if (DefMII != MBB.begin() &&
1265         TID.isCommutable() &&
1266         TII->CommuteChangesDestination(DefMI, NewDstIdx)) {
1267       MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
1268       unsigned NewReg = NewDstMO.getReg();
1269       if (!NewDstMO.isKill() || TRI->regsOverlap(NewReg, SrcReg))
1270         return false;
1271       MachineInstr *ReloadMI = prior(DefMII);
1272       int FrameIdx;
1273       unsigned DestReg = TII->isLoadFromStackSlot(ReloadMI, FrameIdx);
1274       if (DestReg != SrcReg || FrameIdx != SS)
1275         return false;
1276       int UseIdx = DefMI->findRegisterUseOperandIdx(DestReg, false);
1277       if (UseIdx == -1)
1278         return false;
1279       unsigned DefIdx;
1280       if (!MI.isRegTiedToDefOperand(UseIdx, &DefIdx))
1281         return false;
1282       assert(DefMI->getOperand(DefIdx).isReg() &&
1283              DefMI->getOperand(DefIdx).getReg() == SrcReg);
1284
1285       // Now commute def instruction.
1286       MachineInstr *CommutedMI = TII->commuteInstruction(DefMI, true);
1287       if (!CommutedMI)
1288         return false;
1289       SmallVector<unsigned, 1> Ops;
1290       Ops.push_back(NewDstIdx);
1291       MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, CommutedMI, Ops, SS);
1292       // Not needed since foldMemoryOperand returns new MI.
1293       MF.DeleteMachineInstr(CommutedMI);
1294       if (!FoldedMI)
1295         return false;
1296
1297       VRM.addSpillSlotUse(SS, FoldedMI);
1298       VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
1299       // Insert new def MI and spill MI.
1300       const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1301       TII->storeRegToStackSlot(MBB, &MI, NewReg, true, SS, RC);
1302       MII = prior(MII);
1303       MachineInstr *StoreMI = MII;
1304       VRM.addSpillSlotUse(SS, StoreMI);
1305       VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
1306       MII = MBB.insert(MII, FoldedMI);  // Update MII to backtrack.
1307
1308       // Delete all 3 old instructions.
1309       InvalidateKills(*ReloadMI, TRI, RegKills, KillOps);
1310       VRM.RemoveMachineInstrFromMaps(ReloadMI);
1311       MBB.erase(ReloadMI);
1312       InvalidateKills(*DefMI, TRI, RegKills, KillOps);
1313       VRM.RemoveMachineInstrFromMaps(DefMI);
1314       MBB.erase(DefMI);
1315       InvalidateKills(MI, TRI, RegKills, KillOps);
1316       VRM.RemoveMachineInstrFromMaps(&MI);
1317       MBB.erase(&MI);
1318
1319       // If NewReg was previously holding value of some SS, it's now clobbered.
1320       // This has to be done now because it's a physical register. When this
1321       // instruction is re-visited, it's ignored.
1322       Spills.ClobberPhysReg(NewReg);
1323
1324       ++NumCommutes;
1325       return true;
1326     }
1327
1328     return false;
1329   }
1330
1331   /// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if
1332   /// the last store to the same slot is now dead. If so, remove the last store.
1333   void SpillRegToStackSlot(MachineBasicBlock &MBB,
1334                            MachineBasicBlock::iterator &MII,
1335                            int Idx, unsigned PhysReg, int StackSlot,
1336                            const TargetRegisterClass *RC,
1337                            bool isAvailable, MachineInstr *&LastStore,
1338                            AvailableSpills &Spills,
1339                            SmallSet<MachineInstr*, 4> &ReMatDefs,
1340                            BitVector &RegKills,
1341                            std::vector<MachineOperand*> &KillOps,
1342                            VirtRegMap &VRM) {
1343
1344     TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC);
1345     MachineInstr *StoreMI = next(MII);
1346     VRM.addSpillSlotUse(StackSlot, StoreMI);
1347     DOUT << "Store:\t" << *StoreMI;
1348
1349     // If there is a dead store to this stack slot, nuke it now.
1350     if (LastStore) {
1351       DOUT << "Removed dead store:\t" << *LastStore;
1352       ++NumDSE;
1353       SmallVector<unsigned, 2> KillRegs;
1354       InvalidateKills(*LastStore, TRI, RegKills, KillOps, &KillRegs);
1355       MachineBasicBlock::iterator PrevMII = LastStore;
1356       bool CheckDef = PrevMII != MBB.begin();
1357       if (CheckDef)
1358         --PrevMII;
1359       VRM.RemoveMachineInstrFromMaps(LastStore);
1360       MBB.erase(LastStore);
1361       if (CheckDef) {
1362         // Look at defs of killed registers on the store. Mark the defs
1363         // as dead since the store has been deleted and they aren't
1364         // being reused.
1365         for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) {
1366           bool HasOtherDef = false;
1367           if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
1368             MachineInstr *DeadDef = PrevMII;
1369             if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
1370               // FIXME: This assumes a remat def does not have side
1371               // effects.
1372               VRM.RemoveMachineInstrFromMaps(DeadDef);
1373               MBB.erase(DeadDef);
1374               ++NumDRM;
1375             }
1376           }
1377         }
1378       }
1379     }
1380
1381     LastStore = next(MII);
1382
1383     // If the stack slot value was previously available in some other
1384     // register, change it now.  Otherwise, make the register available,
1385     // in PhysReg.
1386     Spills.ModifyStackSlotOrReMat(StackSlot);
1387     Spills.ClobberPhysReg(PhysReg);
1388     Spills.addAvailable(StackSlot, PhysReg, isAvailable);
1389     ++NumStores;
1390   }
1391
1392   /// TransferDeadness - A identity copy definition is dead and it's being
1393   /// removed. Find the last def or use and mark it as dead / kill.
1394   void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
1395                         unsigned Reg, BitVector &RegKills,
1396                         std::vector<MachineOperand*> &KillOps,
1397                         VirtRegMap &VRM) {
1398     SmallPtrSet<MachineInstr*, 4> Seens;
1399     SmallVector<std::pair<MachineInstr*, int>,8> Refs;
1400     for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg),
1401            RE = RegInfo->reg_end(); RI != RE; ++RI) {
1402       MachineInstr *UDMI = &*RI;
1403       if (UDMI->getParent() != MBB)
1404         continue;
1405       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
1406       if (DI == DistanceMap.end() || DI->second > CurDist)
1407         continue;
1408       if (Seens.insert(UDMI))
1409         Refs.push_back(std::make_pair(UDMI, DI->second));
1410     }
1411
1412     if (Refs.empty())
1413       return;
1414     std::sort(Refs.begin(), Refs.end(), RefSorter());
1415
1416     while (!Refs.empty()) {
1417       MachineInstr *LastUDMI = Refs.back().first;
1418       Refs.pop_back();
1419
1420       MachineOperand *LastUD = NULL;
1421       for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
1422         MachineOperand &MO = LastUDMI->getOperand(i);
1423         if (!MO.isReg() || MO.getReg() != Reg)
1424           continue;
1425         if (!LastUD || (LastUD->isUse() && MO.isDef()))
1426           LastUD = &MO;
1427         if (LastUDMI->isRegTiedToDefOperand(i))
1428           break;
1429       }
1430       if (LastUD->isDef()) {
1431         // If the instruction has no side effect, delete it and propagate
1432         // backward further. Otherwise, mark is dead and we are done.
1433         const TargetInstrDesc &TID = LastUDMI->getDesc();
1434         if (TID.mayStore() || TID.isCall() || TID.isTerminator() ||
1435             TID.hasUnmodeledSideEffects()) {
1436           LastUD->setIsDead();
1437           break;
1438         }
1439         VRM.RemoveMachineInstrFromMaps(LastUDMI);
1440         MBB->erase(LastUDMI);
1441       } else {
1442         LastUD->setIsKill();
1443         RegKills.set(Reg);
1444         KillOps[Reg] = LastUD;
1445         break;
1446       }
1447     }
1448   }
1449
1450   /// rewriteMBB - Keep track of which spills are available even after the
1451   /// register allocator is done with them.  If possible, avid reloading vregs.
1452   void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
1453                   LiveIntervals *LIs,
1454                   AvailableSpills &Spills, BitVector &RegKills,
1455                   std::vector<MachineOperand*> &KillOps) {
1456
1457     DOUT << "\n**** Local spiller rewriting MBB '"
1458          << MBB.getBasicBlock()->getName() << "':\n";
1459
1460     MachineFunction &MF = *MBB.getParent();
1461
1462     // MaybeDeadStores - When we need to write a value back into a stack slot,
1463     // keep track of the inserted store.  If the stack slot value is never read
1464     // (because the value was used from some available register, for example), and
1465     // subsequently stored to, the original store is dead.  This map keeps track
1466     // of inserted stores that are not used.  If we see a subsequent store to the
1467     // same stack slot, the original store is deleted.
1468     std::vector<MachineInstr*> MaybeDeadStores;
1469     MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL);
1470
1471     // ReMatDefs - These are rematerializable def MIs which are not deleted.
1472     SmallSet<MachineInstr*, 4> ReMatDefs;
1473
1474     // Clear kill info.
1475     SmallSet<unsigned, 2> KilledMIRegs;
1476     RegKills.reset();
1477     KillOps.clear();
1478     KillOps.resize(TRI->getNumRegs(), NULL);
1479
1480     unsigned Dist = 0;
1481     DistanceMap.clear();
1482     for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
1483          MII != E; ) {
1484       MachineBasicBlock::iterator NextMII = next(MII);
1485
1486       VirtRegMap::MI2VirtMapTy::const_iterator I, End;
1487       bool Erased = false;
1488       bool BackTracked = false;
1489       if (OptimizeByUnfold(MBB, MII,
1490                            MaybeDeadStores, Spills, RegKills, KillOps, VRM))
1491         NextMII = next(MII);
1492
1493       MachineInstr &MI = *MII;
1494
1495       if (VRM.hasEmergencySpills(&MI)) {
1496         // Spill physical register(s) in the rare case the allocator has run out
1497         // of registers to allocate.
1498         SmallSet<int, 4> UsedSS;
1499         std::vector<unsigned> &EmSpills = VRM.getEmergencySpills(&MI);
1500         for (unsigned i = 0, e = EmSpills.size(); i != e; ++i) {
1501           unsigned PhysReg = EmSpills[i];
1502           const TargetRegisterClass *RC =
1503             TRI->getPhysicalRegisterRegClass(PhysReg);
1504           assert(RC && "Unable to determine register class!");
1505           int SS = VRM.getEmergencySpillSlot(RC);
1506           if (UsedSS.count(SS))
1507             assert(0 && "Need to spill more than one physical registers!");
1508           UsedSS.insert(SS);
1509           TII->storeRegToStackSlot(MBB, MII, PhysReg, true, SS, RC);
1510           MachineInstr *StoreMI = prior(MII);
1511           VRM.addSpillSlotUse(SS, StoreMI);
1512           TII->loadRegFromStackSlot(MBB, next(MII), PhysReg, SS, RC);
1513           MachineInstr *LoadMI = next(MII);
1514           VRM.addSpillSlotUse(SS, LoadMI);
1515           ++NumPSpills;
1516         }
1517         NextMII = next(MII);
1518       }
1519
1520       // Insert restores here if asked to.
1521       if (VRM.isRestorePt(&MI)) {
1522         std::vector<unsigned> &RestoreRegs = VRM.getRestorePtRestores(&MI);
1523         for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) {
1524           unsigned VirtReg = RestoreRegs[e-i-1];  // Reverse order.
1525           if (!VRM.getPreSplitReg(VirtReg))
1526             continue; // Split interval spilled again.
1527           unsigned Phys = VRM.getPhys(VirtReg);
1528           RegInfo->setPhysRegUsed(Phys);
1529
1530           // Check if the value being restored if available. If so, it must be
1531           // from a predecessor BB that fallthrough into this BB. We do not
1532           // expect:
1533           // BB1:
1534           // r1 = load fi#1
1535           // ...
1536           //    = r1<kill>
1537           // ... # r1 not clobbered
1538           // ...
1539           //    = load fi#1
1540           bool DoReMat = VRM.isReMaterialized(VirtReg);
1541           int SSorRMId = DoReMat
1542             ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
1543           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1544           unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
1545           if (InReg == Phys) {
1546             // If the value is already available in the expected register, save
1547             // a reload / remat.
1548             if (SSorRMId)
1549               DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
1550             else
1551               DOUT << "Reusing SS#" << SSorRMId;
1552             DOUT << " from physreg "
1553                  << TRI->getName(InReg) << " for vreg"
1554                  << VirtReg <<" instead of reloading into physreg "
1555                  << TRI->getName(Phys) << "\n";
1556             ++NumOmitted;
1557             continue;
1558           } else if (InReg && InReg != Phys) {
1559             if (SSorRMId)
1560               DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
1561             else
1562               DOUT << "Reusing SS#" << SSorRMId;
1563             DOUT << " from physreg "
1564                  << TRI->getName(InReg) << " for vreg"
1565                  << VirtReg <<" by copying it into physreg "
1566                  << TRI->getName(Phys) << "\n";
1567
1568             // If the reloaded / remat value is available in another register,
1569             // copy it to the desired register.
1570             TII->copyRegToReg(MBB, &MI, Phys, InReg, RC, RC);
1571
1572             // This invalidates Phys.
1573             Spills.ClobberPhysReg(Phys);
1574             // Remember it's available.
1575             Spills.addAvailable(SSorRMId, Phys);
1576
1577             // Mark is killed.
1578             MachineInstr *CopyMI = prior(MII);
1579             MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg);
1580             KillOpnd->setIsKill();
1581             UpdateKills(*CopyMI, TRI, RegKills, KillOps);
1582
1583             DOUT << '\t' << *CopyMI;
1584             ++NumCopified;
1585             continue;
1586           }
1587
1588           if (VRM.isReMaterialized(VirtReg)) {
1589             ReMaterialize(MBB, MII, Phys, VirtReg, TII, TRI, VRM);
1590           } else {
1591             const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1592             TII->loadRegFromStackSlot(MBB, &MI, Phys, SSorRMId, RC);
1593             MachineInstr *LoadMI = prior(MII);
1594             VRM.addSpillSlotUse(SSorRMId, LoadMI);
1595             ++NumLoads;
1596           }
1597
1598           // This invalidates Phys.
1599           Spills.ClobberPhysReg(Phys);
1600           // Remember it's available.
1601           Spills.addAvailable(SSorRMId, Phys);
1602
1603           UpdateKills(*prior(MII), TRI, RegKills, KillOps);
1604           DOUT << '\t' << *prior(MII);
1605         }
1606       }
1607
1608       // Insert spills here if asked to.
1609       if (VRM.isSpillPt(&MI)) {
1610         std::vector<std::pair<unsigned,bool> > &SpillRegs =
1611           VRM.getSpillPtSpills(&MI);
1612         for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
1613           unsigned VirtReg = SpillRegs[i].first;
1614           bool isKill = SpillRegs[i].second;
1615           if (!VRM.getPreSplitReg(VirtReg))
1616             continue; // Split interval spilled again.
1617           const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
1618           unsigned Phys = VRM.getPhys(VirtReg);
1619           int StackSlot = VRM.getStackSlot(VirtReg);
1620           TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC);
1621           MachineInstr *StoreMI = next(MII);
1622           VRM.addSpillSlotUse(StackSlot, StoreMI);
1623           DOUT << "Store:\t" << *StoreMI;
1624           VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
1625         }
1626         NextMII = next(MII);
1627       }
1628
1629       /// ReusedOperands - Keep track of operand reuse in case we need to undo
1630       /// reuse.
1631       ReuseInfo ReusedOperands(MI, TRI);
1632       SmallVector<unsigned, 4> VirtUseOps;
1633       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
1634         MachineOperand &MO = MI.getOperand(i);
1635         if (!MO.isReg() || MO.getReg() == 0)
1636           continue;   // Ignore non-register operands.
1637
1638         unsigned VirtReg = MO.getReg();
1639         if (TargetRegisterInfo::isPhysicalRegister(VirtReg)) {
1640           // Ignore physregs for spilling, but remember that it is used by this
1641           // function.
1642           RegInfo->setPhysRegUsed(VirtReg);
1643           continue;
1644         }
1645
1646         // We want to process implicit virtual register uses first.
1647         if (MO.isImplicit())
1648           // If the virtual register is implicitly defined, emit a implicit_def
1649           // before so scavenger knows it's "defined".
1650           VirtUseOps.insert(VirtUseOps.begin(), i);
1651         else
1652           VirtUseOps.push_back(i);
1653       }
1654
1655       // Process all of the spilled uses and all non spilled reg references.
1656       SmallVector<int, 2> PotentialDeadStoreSlots;
1657       KilledMIRegs.clear();
1658       for (unsigned j = 0, e = VirtUseOps.size(); j != e; ++j) {
1659         unsigned i = VirtUseOps[j];
1660         MachineOperand &MO = MI.getOperand(i);
1661         unsigned VirtReg = MO.getReg();
1662         assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
1663                "Not a virtual register?");
1664
1665         unsigned SubIdx = MO.getSubReg();
1666         if (VRM.isAssignedReg(VirtReg)) {
1667           // This virtual register was assigned a physreg!
1668           unsigned Phys = VRM.getPhys(VirtReg);
1669           RegInfo->setPhysRegUsed(Phys);
1670           if (MO.isDef())
1671             ReusedOperands.markClobbered(Phys);
1672           unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
1673           MI.getOperand(i).setReg(RReg);
1674           MI.getOperand(i).setSubReg(0);
1675           if (VRM.isImplicitlyDefined(VirtReg))
1676             BuildMI(MBB, &MI, MI.getDebugLoc(),
1677                     TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
1678           continue;
1679         }
1680
1681         // This virtual register is now known to be a spilled value.
1682         if (!MO.isUse())
1683           continue;  // Handle defs in the loop below (handle use&def here though)
1684
1685         bool AvoidReload = false;
1686         if (LIs->hasInterval(VirtReg)) {
1687           LiveInterval &LI = LIs->getInterval(VirtReg);
1688           if (!LI.liveAt(LIs->getUseIndex(LI.beginNumber())))
1689             // Must be defined by an implicit def. It should not be spilled. Note,
1690             // this is for correctness reason. e.g.
1691             // 8   %reg1024<def> = IMPLICIT_DEF
1692             // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1693             // The live range [12, 14) are not part of the r1024 live interval since
1694             // it's defined by an implicit def. It will not conflicts with live
1695             // interval of r1025. Now suppose both registers are spilled, you can
1696             // easily see a situation where both registers are reloaded before
1697             // the INSERT_SUBREG and both target registers that would overlap.
1698             AvoidReload = true;
1699         }
1700
1701         bool DoReMat = VRM.isReMaterialized(VirtReg);
1702         int SSorRMId = DoReMat
1703           ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
1704         int ReuseSlot = SSorRMId;
1705
1706         // Check to see if this stack slot is available.
1707         unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
1708
1709         // If this is a sub-register use, make sure the reuse register is in the
1710         // right register class. For example, for x86 not all of the 32-bit
1711         // registers have accessible sub-registers.
1712         // Similarly so for EXTRACT_SUBREG. Consider this:
1713         // EDI = op
1714         // MOV32_mr fi#1, EDI
1715         // ...
1716         //       = EXTRACT_SUBREG fi#1
1717         // fi#1 is available in EDI, but it cannot be reused because it's not in
1718         // the right register file.
1719         if (PhysReg && !AvoidReload &&
1720             (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) {
1721           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1722           if (!RC->contains(PhysReg))
1723             PhysReg = 0;
1724         }
1725
1726         if (PhysReg && !AvoidReload) {
1727           // This spilled operand might be part of a two-address operand.  If this
1728           // is the case, then changing it will necessarily require changing the
1729           // def part of the instruction as well.  However, in some cases, we
1730           // aren't allowed to modify the reused register.  If none of these cases
1731           // apply, reuse it.
1732           bool CanReuse = true;
1733           bool isTied = MI.isRegTiedToDefOperand(i);
1734           if (isTied) {
1735             // Okay, we have a two address operand.  We can reuse this physreg as
1736             // long as we are allowed to clobber the value and there isn't an
1737             // earlier def that has already clobbered the physreg.
1738             CanReuse = !ReusedOperands.isClobbered(PhysReg) &&
1739               Spills.canClobberPhysReg(PhysReg);
1740           }
1741
1742           if (CanReuse) {
1743             // If this stack slot value is already available, reuse it!
1744             if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
1745               DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
1746             else
1747               DOUT << "Reusing SS#" << ReuseSlot;
1748             DOUT << " from physreg "
1749                  << TRI->getName(PhysReg) << " for vreg"
1750                  << VirtReg <<" instead of reloading into physreg "
1751                  << TRI->getName(VRM.getPhys(VirtReg)) << "\n";
1752             unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1753             MI.getOperand(i).setReg(RReg);
1754             MI.getOperand(i).setSubReg(0);
1755
1756             // The only technical detail we have is that we don't know that
1757             // PhysReg won't be clobbered by a reloaded stack slot that occurs
1758             // later in the instruction.  In particular, consider 'op V1, V2'.
1759             // If V1 is available in physreg R0, we would choose to reuse it
1760             // here, instead of reloading it into the register the allocator
1761             // indicated (say R1).  However, V2 might have to be reloaded
1762             // later, and it might indicate that it needs to live in R0.  When
1763             // this occurs, we need to have information available that
1764             // indicates it is safe to use R1 for the reload instead of R0.
1765             //
1766             // To further complicate matters, we might conflict with an alias,
1767             // or R0 and R1 might not be compatible with each other.  In this
1768             // case, we actually insert a reload for V1 in R1, ensuring that
1769             // we can get at R0 or its alias.
1770             ReusedOperands.addReuse(i, ReuseSlot, PhysReg,
1771                                     VRM.getPhys(VirtReg), VirtReg);
1772             if (isTied)
1773               // Only mark it clobbered if this is a use&def operand.
1774               ReusedOperands.markClobbered(PhysReg);
1775             ++NumReused;
1776
1777             if (MI.getOperand(i).isKill() &&
1778                 ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) {
1779
1780               // The store of this spilled value is potentially dead, but we
1781               // won't know for certain until we've confirmed that the re-use
1782               // above is valid, which means waiting until the other operands
1783               // are processed. For now we just track the spill slot, we'll
1784               // remove it after the other operands are processed if valid.
1785
1786               PotentialDeadStoreSlots.push_back(ReuseSlot);
1787             }
1788
1789             // Mark is isKill if it's there no other uses of the same virtual
1790             // register and it's not a two-address operand. IsKill will be
1791             // unset if reg is reused.
1792             if (!isTied && KilledMIRegs.count(VirtReg) == 0) {
1793               MI.getOperand(i).setIsKill();
1794               KilledMIRegs.insert(VirtReg);
1795             }
1796
1797             continue;
1798           }  // CanReuse
1799
1800           // Otherwise we have a situation where we have a two-address instruction
1801           // whose mod/ref operand needs to be reloaded.  This reload is already
1802           // available in some register "PhysReg", but if we used PhysReg as the
1803           // operand to our 2-addr instruction, the instruction would modify
1804           // PhysReg.  This isn't cool if something later uses PhysReg and expects
1805           // to get its initial value.
1806           //
1807           // To avoid this problem, and to avoid doing a load right after a store,
1808           // we emit a copy from PhysReg into the designated register for this
1809           // operand.
1810           unsigned DesignatedReg = VRM.getPhys(VirtReg);
1811           assert(DesignatedReg && "Must map virtreg to physreg!");
1812
1813           // Note that, if we reused a register for a previous operand, the
1814           // register we want to reload into might not actually be
1815           // available.  If this occurs, use the register indicated by the
1816           // reuser.
1817           if (ReusedOperands.hasReuses())
1818             DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI,
1819                                  Spills, MaybeDeadStores, RegKills, KillOps, VRM);
1820
1821           // If the mapped designated register is actually the physreg we have
1822           // incoming, we don't need to inserted a dead copy.
1823           if (DesignatedReg == PhysReg) {
1824             // If this stack slot value is already available, reuse it!
1825             if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
1826               DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
1827             else
1828               DOUT << "Reusing SS#" << ReuseSlot;
1829             DOUT << " from physreg " << TRI->getName(PhysReg)
1830                  << " for vreg" << VirtReg
1831                  << " instead of reloading into same physreg.\n";
1832             unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1833             MI.getOperand(i).setReg(RReg);
1834             MI.getOperand(i).setSubReg(0);
1835             ReusedOperands.markClobbered(RReg);
1836             ++NumReused;
1837             continue;
1838           }
1839
1840           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1841           RegInfo->setPhysRegUsed(DesignatedReg);
1842           ReusedOperands.markClobbered(DesignatedReg);
1843           TII->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC);
1844
1845           MachineInstr *CopyMI = prior(MII);
1846           UpdateKills(*CopyMI, TRI, RegKills, KillOps);
1847
1848           // This invalidates DesignatedReg.
1849           Spills.ClobberPhysReg(DesignatedReg);
1850
1851           Spills.addAvailable(ReuseSlot, DesignatedReg);
1852           unsigned RReg =
1853             SubIdx ? TRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg;
1854           MI.getOperand(i).setReg(RReg);
1855           MI.getOperand(i).setSubReg(0);
1856           DOUT << '\t' << *prior(MII);
1857           ++NumReused;
1858           continue;
1859         } // if (PhysReg)
1860
1861         // Otherwise, reload it and remember that we have it.
1862         PhysReg = VRM.getPhys(VirtReg);
1863         assert(PhysReg && "Must map virtreg to physreg!");
1864
1865         // Note that, if we reused a register for a previous operand, the
1866         // register we want to reload into might not actually be
1867         // available.  If this occurs, use the register indicated by the
1868         // reuser.
1869         if (ReusedOperands.hasReuses())
1870           PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
1871                                  Spills, MaybeDeadStores, RegKills, KillOps, VRM);
1872
1873         RegInfo->setPhysRegUsed(PhysReg);
1874         ReusedOperands.markClobbered(PhysReg);
1875         if (AvoidReload)
1876           ++NumAvoided;
1877         else {
1878           if (DoReMat) {
1879             ReMaterialize(MBB, MII, PhysReg, VirtReg, TII, TRI, VRM);
1880           } else {
1881             const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
1882             TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC);
1883             MachineInstr *LoadMI = prior(MII);
1884             VRM.addSpillSlotUse(SSorRMId, LoadMI);
1885             ++NumLoads;
1886           }
1887           // This invalidates PhysReg.
1888           Spills.ClobberPhysReg(PhysReg);
1889
1890           // Any stores to this stack slot are not dead anymore.
1891           if (!DoReMat)
1892             MaybeDeadStores[SSorRMId] = NULL;
1893           Spills.addAvailable(SSorRMId, PhysReg);
1894           // Assumes this is the last use. IsKill will be unset if reg is reused
1895           // unless it's a two-address operand.
1896           if (!MI.isRegTiedToDefOperand(i) &&
1897               KilledMIRegs.count(VirtReg) == 0) {
1898             MI.getOperand(i).setIsKill();
1899             KilledMIRegs.insert(VirtReg);
1900           }
1901
1902           UpdateKills(*prior(MII), TRI, RegKills, KillOps);
1903           DOUT << '\t' << *prior(MII);
1904         }
1905         unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
1906         MI.getOperand(i).setReg(RReg);
1907         MI.getOperand(i).setSubReg(0);
1908       }
1909
1910       // Ok - now we can remove stores that have been confirmed dead.
1911       for (unsigned j = 0, e = PotentialDeadStoreSlots.size(); j != e; ++j) {
1912         // This was the last use and the spilled value is still available
1913         // for reuse. That means the spill was unnecessary!
1914         int PDSSlot = PotentialDeadStoreSlots[j];
1915         MachineInstr* DeadStore = MaybeDeadStores[PDSSlot];
1916         if (DeadStore) {
1917           DOUT << "Removed dead store:\t" << *DeadStore;
1918           InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
1919           VRM.RemoveMachineInstrFromMaps(DeadStore);
1920           MBB.erase(DeadStore);
1921           MaybeDeadStores[PDSSlot] = NULL;
1922           ++NumDSE;
1923         }
1924       }
1925
1926
1927       DOUT << '\t' << MI;
1928
1929
1930       // If we have folded references to memory operands, make sure we clear all
1931       // physical registers that may contain the value of the spilled virtual
1932       // register
1933       SmallSet<int, 2> FoldedSS;
1934       for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
1935         unsigned VirtReg = I->second.first;
1936         VirtRegMap::ModRef MR = I->second.second;
1937         DOUT << "Folded vreg: " << VirtReg << "  MR: " << MR;
1938
1939         // MI2VirtMap be can updated which invalidate the iterator.
1940         // Increment the iterator first.
1941         ++I;
1942         int SS = VRM.getStackSlot(VirtReg);
1943         if (SS == VirtRegMap::NO_STACK_SLOT)
1944           continue;
1945         FoldedSS.insert(SS);
1946         DOUT << " - StackSlot: " << SS << "\n";
1947
1948         // If this folded instruction is just a use, check to see if it's a
1949         // straight load from the virt reg slot.
1950         if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
1951           int FrameIdx;
1952           unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx);
1953           if (DestReg && FrameIdx == SS) {
1954             // If this spill slot is available, turn it into a copy (or nothing)
1955             // instead of leaving it as a load!
1956             if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) {
1957               DOUT << "Promoted Load To Copy: " << MI;
1958               if (DestReg != InReg) {
1959                 const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
1960                 TII->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC);
1961                 MachineOperand *DefMO = MI.findRegisterDefOperand(DestReg);
1962                 unsigned SubIdx = DefMO->getSubReg();
1963                 // Revisit the copy so we make sure to notice the effects of the
1964                 // operation on the destreg (either needing to RA it if it's
1965                 // virtual or needing to clobber any values if it's physical).
1966                 NextMII = &MI;
1967                 --NextMII;  // backtrack to the copy.
1968                 // Propagate the sub-register index over.
1969                 if (SubIdx) {
1970                   DefMO = NextMII->findRegisterDefOperand(DestReg);
1971                   DefMO->setSubReg(SubIdx);
1972                 }
1973
1974                 // Mark is killed.
1975                 MachineOperand *KillOpnd = NextMII->findRegisterUseOperand(InReg);
1976                 KillOpnd->setIsKill();
1977
1978                 BackTracked = true;
1979               } else {
1980                 DOUT << "Removing now-noop copy: " << MI;
1981                 // Unset last kill since it's being reused.
1982                 InvalidateKill(InReg, TRI, RegKills, KillOps);
1983                 Spills.disallowClobberPhysReg(InReg);
1984               }
1985
1986               InvalidateKills(MI, TRI, RegKills, KillOps);
1987               VRM.RemoveMachineInstrFromMaps(&MI);
1988               MBB.erase(&MI);
1989               Erased = true;
1990               goto ProcessNextInst;
1991             }
1992           } else {
1993             unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
1994             SmallVector<MachineInstr*, 4> NewMIs;
1995             if (PhysReg &&
1996                 TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) {
1997               MBB.insert(MII, NewMIs[0]);
1998               InvalidateKills(MI, TRI, RegKills, KillOps);
1999               VRM.RemoveMachineInstrFromMaps(&MI);
2000               MBB.erase(&MI);
2001               Erased = true;
2002               --NextMII;  // backtrack to the unfolded instruction.
2003               BackTracked = true;
2004               goto ProcessNextInst;
2005             }
2006           }
2007         }
2008
2009         // If this reference is not a use, any previous store is now dead.
2010         // Otherwise, the store to this stack slot is not dead anymore.
2011         MachineInstr* DeadStore = MaybeDeadStores[SS];
2012         if (DeadStore) {
2013           bool isDead = !(MR & VirtRegMap::isRef);
2014           MachineInstr *NewStore = NULL;
2015           if (MR & VirtRegMap::isModRef) {
2016             unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
2017             SmallVector<MachineInstr*, 4> NewMIs;
2018             // We can reuse this physreg as long as we are allowed to clobber
2019             // the value and there isn't an earlier def that has already clobbered
2020             // the physreg.
2021             if (PhysReg &&
2022                 !ReusedOperands.isClobbered(PhysReg) &&
2023                 Spills.canClobberPhysReg(PhysReg) &&
2024                 !TII->isStoreToStackSlot(&MI, SS)) { // Not profitable!
2025               MachineOperand *KillOpnd =
2026                 DeadStore->findRegisterUseOperand(PhysReg, true);
2027               // Note, if the store is storing a sub-register, it's possible the
2028               // super-register is needed below.
2029               if (KillOpnd && !KillOpnd->getSubReg() &&
2030                   TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, true,NewMIs)){
2031                 MBB.insert(MII, NewMIs[0]);
2032                 NewStore = NewMIs[1];
2033                 MBB.insert(MII, NewStore);
2034                 VRM.addSpillSlotUse(SS, NewStore);
2035                 InvalidateKills(MI, TRI, RegKills, KillOps);
2036                 VRM.RemoveMachineInstrFromMaps(&MI);
2037                 MBB.erase(&MI);
2038                 Erased = true;
2039                 --NextMII;
2040                 --NextMII;  // backtrack to the unfolded instruction.
2041                 BackTracked = true;
2042                 isDead = true;
2043                 ++NumSUnfold;
2044               }
2045             }
2046           }
2047
2048           if (isDead) {  // Previous store is dead.
2049             // If we get here, the store is dead, nuke it now.
2050             DOUT << "Removed dead store:\t" << *DeadStore;
2051             InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
2052             VRM.RemoveMachineInstrFromMaps(DeadStore);
2053             MBB.erase(DeadStore);
2054             if (!NewStore)
2055               ++NumDSE;
2056           }
2057
2058           MaybeDeadStores[SS] = NULL;
2059           if (NewStore) {
2060             // Treat this store as a spill merged into a copy. That makes the
2061             // stack slot value available.
2062             VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod);
2063             goto ProcessNextInst;
2064           }
2065         }
2066
2067         // If the spill slot value is available, and this is a new definition of
2068         // the value, the value is not available anymore.
2069         if (MR & VirtRegMap::isMod) {
2070           // Notice that the value in this stack slot has been modified.
2071           Spills.ModifyStackSlotOrReMat(SS);
2072
2073           // If this is *just* a mod of the value, check to see if this is just a
2074           // store to the spill slot (i.e. the spill got merged into the copy). If
2075           // so, realize that the vreg is available now, and add the store to the
2076           // MaybeDeadStore info.
2077           int StackSlot;
2078           if (!(MR & VirtRegMap::isRef)) {
2079             if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
2080               assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
2081                      "Src hasn't been allocated yet?");
2082
2083               if (CommuteToFoldReload(MBB, MII, VirtReg, SrcReg, StackSlot,
2084                                       Spills, RegKills, KillOps, TRI, VRM)) {
2085                 NextMII = next(MII);
2086                 BackTracked = true;
2087                 goto ProcessNextInst;
2088               }
2089
2090               // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
2091               // this as a potentially dead store in case there is a subsequent
2092               // store into the stack slot without a read from it.
2093               MaybeDeadStores[StackSlot] = &MI;
2094
2095               // If the stack slot value was previously available in some other
2096               // register, change it now.  Otherwise, make the register
2097               // available in PhysReg.
2098               Spills.addAvailable(StackSlot, SrcReg, MI.killsRegister(SrcReg));
2099             }
2100           }
2101         }
2102       }
2103
2104       // Process all of the spilled defs.
2105       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
2106         MachineOperand &MO = MI.getOperand(i);
2107         if (!(MO.isReg() && MO.getReg() && MO.isDef()))
2108           continue;
2109
2110         unsigned VirtReg = MO.getReg();
2111         if (!TargetRegisterInfo::isVirtualRegister(VirtReg)) {
2112           // Check to see if this is a noop copy.  If so, eliminate the
2113           // instruction before considering the dest reg to be changed.
2114           unsigned Src, Dst, SrcSR, DstSR;
2115           if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
2116             ++NumDCE;
2117             DOUT << "Removing now-noop copy: " << MI;
2118             SmallVector<unsigned, 2> KillRegs;
2119             InvalidateKills(MI, TRI, RegKills, KillOps, &KillRegs);
2120             if (MO.isDead() && !KillRegs.empty()) {
2121               // Source register or an implicit super/sub-register use is killed.
2122               assert(KillRegs[0] == Dst ||
2123                      TRI->isSubRegister(KillRegs[0], Dst) ||
2124                      TRI->isSuperRegister(KillRegs[0], Dst));
2125               // Last def is now dead.
2126               TransferDeadness(&MBB, Dist, Src, RegKills, KillOps, VRM);
2127             }
2128             VRM.RemoveMachineInstrFromMaps(&MI);
2129             MBB.erase(&MI);
2130             Erased = true;
2131             Spills.disallowClobberPhysReg(VirtReg);
2132             goto ProcessNextInst;
2133           }
2134
2135           // If it's not a no-op copy, it clobbers the value in the destreg.
2136           Spills.ClobberPhysReg(VirtReg);
2137           ReusedOperands.markClobbered(VirtReg);
2138
2139           // Check to see if this instruction is a load from a stack slot into
2140           // a register.  If so, this provides the stack slot value in the reg.
2141           int FrameIdx;
2142           if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
2143             assert(DestReg == VirtReg && "Unknown load situation!");
2144
2145             // If it is a folded reference, then it's not safe to clobber.
2146             bool Folded = FoldedSS.count(FrameIdx);
2147             // Otherwise, if it wasn't available, remember that it is now!
2148             Spills.addAvailable(FrameIdx, DestReg, !Folded);
2149             goto ProcessNextInst;
2150           }
2151
2152           continue;
2153         }
2154
2155         unsigned SubIdx = MO.getSubReg();
2156         bool DoReMat = VRM.isReMaterialized(VirtReg);
2157         if (DoReMat)
2158           ReMatDefs.insert(&MI);
2159
2160         // The only vregs left are stack slot definitions.
2161         int StackSlot = VRM.getStackSlot(VirtReg);
2162         const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
2163
2164         // If this def is part of a two-address operand, make sure to execute
2165         // the store from the correct physical register.
2166         unsigned PhysReg;
2167         unsigned TiedOp;
2168         if (MI.isRegTiedToUseOperand(i, &TiedOp)) {
2169           PhysReg = MI.getOperand(TiedOp).getReg();
2170           if (SubIdx) {
2171             unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, TRI);
2172             assert(SuperReg && TRI->getSubReg(SuperReg, SubIdx) == PhysReg &&
2173                    "Can't find corresponding super-register!");
2174             PhysReg = SuperReg;
2175           }
2176         } else {
2177           PhysReg = VRM.getPhys(VirtReg);
2178           if (ReusedOperands.isClobbered(PhysReg)) {
2179             // Another def has taken the assigned physreg. It must have been a
2180             // use&def which got it due to reuse. Undo the reuse!
2181             PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
2182                                  Spills, MaybeDeadStores, RegKills, KillOps, VRM);
2183           }
2184         }
2185
2186         assert(PhysReg && "VR not assigned a physical register?");
2187         RegInfo->setPhysRegUsed(PhysReg);
2188         unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
2189         ReusedOperands.markClobbered(RReg);
2190         MI.getOperand(i).setReg(RReg);
2191         MI.getOperand(i).setSubReg(0);
2192
2193         if (!MO.isDead()) {
2194           MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
2195           SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true,
2196                             LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
2197           NextMII = next(MII);
2198
2199           // Check to see if this is a noop copy.  If so, eliminate the
2200           // instruction before considering the dest reg to be changed.
2201           {
2202             unsigned Src, Dst, SrcSR, DstSR;
2203             if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
2204               ++NumDCE;
2205               DOUT << "Removing now-noop copy: " << MI;
2206               InvalidateKills(MI, TRI, RegKills, KillOps);
2207               VRM.RemoveMachineInstrFromMaps(&MI);
2208               MBB.erase(&MI);
2209               Erased = true;
2210               UpdateKills(*LastStore, TRI, RegKills, KillOps);
2211               goto ProcessNextInst;
2212             }
2213           }
2214         }
2215       }
2216     ProcessNextInst:
2217       DistanceMap.insert(std::make_pair(&MI, Dist++));
2218       if (!Erased && !BackTracked) {
2219         for (MachineBasicBlock::iterator II = &MI; II != NextMII; ++II)
2220           UpdateKills(*II, TRI, RegKills, KillOps);
2221       }
2222       MII = NextMII;
2223     }
2224
2225   }
2226
2227 };
2228
2229 llvm::VirtRegRewriter* llvm::createVirtRegRewriter() {
2230   switch (RewriterOpt) {
2231   default: assert(0 && "Unreachable!");
2232   case local:
2233     return new LocalRewriter();
2234   case simple:
2235     return new SimpleRewriter();
2236   case trivial:
2237     return new TrivialRewriter();
2238   }
2239 }