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