lib/CodeGen/VirtRegRewriter.cpp

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