lib/CodeGen/VirtRegMap.cpp

   1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the VirtRegMap class.
  11 //
  12 // It also contains implementations of the the Spiller interface, which, given a
  13 // virtual register map and a machine function, eliminates all virtual
  14 // references by replacing them with physical register references - adding spill
  15 // code as necessary.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #define DEBUG_TYPE "spiller"
  20 #include "VirtRegMap.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/SSARegMap.h"
  25 #include "llvm/Target/TargetMachine.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/ADT/Statistic.h"
  31 #include "llvm/ADT/STLExtras.h"
  32 #include <algorithm>
  33 #include <iostream>
  34 using namespace llvm;
  35
  36 namespace {
  37   static Statistic<> NumSpills("spiller", "Number of register spills");
  38   static Statistic<> NumStores("spiller", "Number of stores added");
  39   static Statistic<> NumLoads ("spiller", "Number of loads added");
  40   static Statistic<> NumReused("spiller", "Number of values reused");
  41   static Statistic<> NumDSE   ("spiller", "Number of dead stores elided");
  42   static Statistic<> NumDCE   ("spiller", "Number of copies elided");
  43
  44   enum SpillerName { simple, local };
  45
  46   static cl::opt<SpillerName>
  47   SpillerOpt("spiller",
  48              cl::desc("Spiller to use: (default: local)"),
  49              cl::Prefix,
  50              cl::values(clEnumVal(simple, "  simple spiller"),
  51                         clEnumVal(local,  "  local spiller"),
  52                         clEnumValEnd),
  53              cl::init(local));
  54 }
  55
  56 //===----------------------------------------------------------------------===//
  57 //  VirtRegMap implementation
  58 //===----------------------------------------------------------------------===//
  59
  60 VirtRegMap::VirtRegMap(MachineFunction &mf)
  61   : TII(*mf.getTarget().getInstrInfo()), MF(mf),
  62     Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT) {
  63   grow();
  64 }
  65
  66 void VirtRegMap::grow() {
  67   Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg());
  68   Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg());
  69 }
  70
  71 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
  72   assert(MRegisterInfo::isVirtualRegister(virtReg));
  73   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  74          "attempt to assign stack slot to already spilled register");
  75   const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg);
  76   int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(),
  77                                                         RC->getAlignment());
  78   Virt2StackSlotMap[virtReg] = frameIndex;
  79   ++NumSpills;
  80   return frameIndex;
  81 }
  82
  83 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) {
  84   assert(MRegisterInfo::isVirtualRegister(virtReg));
  85   assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
  86          "attempt to assign stack slot to already spilled register");
  87   Virt2StackSlotMap[virtReg] = frameIndex;
  88 }
  89
  90 void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI,
  91                             unsigned OpNo, MachineInstr *NewMI) {
  92   // Move previous memory references folded to new instruction.
  93   MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI);
  94   for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI),
  95          E = MI2VirtMap.end(); I != E && I->first == OldMI; ) {
  96     MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second));
  97     MI2VirtMap.erase(I++);
  98   }
  99
 100   ModRef MRInfo;
 101   if (OpNo < 2 && TII.isTwoAddrInstr(OldMI->getOpcode())) {
 102     // Folded a two-address operand.
 103     MRInfo = isModRef;
 104   } else if (OldMI->getOperand(OpNo).isDef()) {
 105     MRInfo = isMod;
 106   } else {
 107     MRInfo = isRef;
 108   }
 109
 110   // add new memory reference
 111   MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo)));
 112 }
 113
 114 void VirtRegMap::print(std::ostream &OS) const {
 115   const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo();
 116
 117   OS << "********** REGISTER MAP **********\n";
 118   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 119          e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
 120     if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG)
 121       OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n";
 122
 123   }
 124
 125   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 126          e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i)
 127     if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT)
 128       OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n";
 129   OS << '\n';
 130 }
 131
 132 void VirtRegMap::dump() const { print(std::cerr); }
 133
 134
 135 //===----------------------------------------------------------------------===//
 136 // Simple Spiller Implementation
 137 //===----------------------------------------------------------------------===//
 138
 139 Spiller::~Spiller() {}
 140
 141 namespace {
 142   struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller {
 143     bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM);
 144   };
 145 }
 146
 147 bool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
 148   DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n");
 149   DEBUG(std::cerr << "********** Function: "
 150                   << MF.getFunction()->getName() << '\n');
 151   const TargetMachine &TM = MF.getTarget();
 152   const MRegisterInfo &MRI = *TM.getRegisterInfo();
 153   bool *PhysRegsUsed = MF.getUsedPhysregs();
 154
 155   // LoadedRegs - Keep track of which vregs are loaded, so that we only load
 156   // each vreg once (in the case where a spilled vreg is used by multiple
 157   // operands).  This is always smaller than the number of operands to the
 158   // current machine instr, so it should be small.
 159   std::vector<unsigned> LoadedRegs;
 160
 161   for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
 162        MBBI != E; ++MBBI) {
 163     DEBUG(std::cerr << MBBI->getBasicBlock()->getName() << ":\n");
 164     MachineBasicBlock &MBB = *MBBI;
 165     for (MachineBasicBlock::iterator MII = MBB.begin(),
 166            E = MBB.end(); MII != E; ++MII) {
 167       MachineInstr &MI = *MII;
 168       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 169         MachineOperand &MO = MI.getOperand(i);
 170         if (MO.isRegister() && MO.getReg())
 171           if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
 172             unsigned VirtReg = MO.getReg();
 173             unsigned PhysReg = VRM.getPhys(VirtReg);
 174             if (VRM.hasStackSlot(VirtReg)) {
 175               int StackSlot = VRM.getStackSlot(VirtReg);
 176               const TargetRegisterClass* RC =
 177                 MF.getSSARegMap()->getRegClass(VirtReg);
 178
 179               if (MO.isUse() &&
 180                   std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
 181                   == LoadedRegs.end()) {
 182                 MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
 183                 LoadedRegs.push_back(VirtReg);
 184                 ++NumLoads;
 185                 DEBUG(std::cerr << '\t' << *prior(MII));
 186               }
 187
 188               if (MO.isDef()) {
 189                 MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
 190                 ++NumStores;
 191               }
 192             }
 193             PhysRegsUsed[PhysReg] = true;
 194             MI.getOperand(i).setReg(PhysReg);
 195           } else {
 196             PhysRegsUsed[MO.getReg()] = true;
 197           }
 198       }
 199
 200       DEBUG(std::cerr << '\t' << MI);
 201       LoadedRegs.clear();
 202     }
 203   }
 204   return true;
 205 }
 206
 207 //===----------------------------------------------------------------------===//
 208 //  Local Spiller Implementation
 209 //===----------------------------------------------------------------------===//
 210
 211 namespace {
 212   /// LocalSpiller - This spiller does a simple pass over the machine basic
 213   /// block to attempt to keep spills in registers as much as possible for
 214   /// blocks that have low register pressure (the vreg may be spilled due to
 215   /// register pressure in other blocks).
 216   class VISIBILITY_HIDDEN LocalSpiller : public Spiller {
 217     const MRegisterInfo *MRI;
 218     const TargetInstrInfo *TII;
 219   public:
 220     bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) {
 221       MRI = MF.getTarget().getRegisterInfo();
 222       TII = MF.getTarget().getInstrInfo();
 223       DEBUG(std::cerr << "\n**** Local spiller rewriting function '"
 224                       << MF.getFunction()->getName() << "':\n");
 225
 226       for (MachineFunction::iterator MBB = MF.begin(), E = MF.end();
 227            MBB != E; ++MBB)
 228         RewriteMBB(*MBB, VRM);
 229       return true;
 230     }
 231   private:
 232     void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM);
 233     void ClobberPhysReg(unsigned PR, std::map<int, unsigned> &SpillSlots,
 234                         std::multimap<unsigned, int> &PhysRegs);
 235     void ClobberPhysRegOnly(unsigned PR, std::map<int, unsigned> &SpillSlots,
 236                             std::multimap<unsigned, int> &PhysRegs);
 237     void ModifyStackSlot(int Slot, std::map<int, unsigned> &SpillSlots,
 238                          std::multimap<unsigned, int> &PhysRegs);
 239   };
 240 }
 241
 242 /// AvailableSpills - As the local spiller is scanning and rewriting an MBB from
 243 /// top down, keep track of which spills slots are available in each register.
 244 ///
 245 /// Note that not all physregs are created equal here.  In particular, some
 246 /// physregs are reloads that we are allowed to clobber or ignore at any time.
 247 /// Other physregs are values that the register allocated program is using that
 248 /// we cannot CHANGE, but we can read if we like.  We keep track of this on a
 249 /// per-stack-slot basis as the low bit in the value of the SpillSlotsAvailable
 250 /// entries.  The predicate 'canClobberPhysReg()' checks this bit and
 251 /// addAvailable sets it if.
 252 namespace {
 253 class VISIBILITY_HIDDEN AvailableSpills {
 254   const MRegisterInfo *MRI;
 255   const TargetInstrInfo *TII;
 256
 257   // SpillSlotsAvailable - This map keeps track of all of the spilled virtual
 258   // register values that are still available, due to being loaded or stored to,
 259   // but not invalidated yet.
 260   std::map<int, unsigned> SpillSlotsAvailable;
 261
 262   // PhysRegsAvailable - This is the inverse of SpillSlotsAvailable, indicating
 263   // which stack slot values are currently held by a physreg.  This is used to
 264   // invalidate entries in SpillSlotsAvailable when a physreg is modified.
 265   std::multimap<unsigned, int> PhysRegsAvailable;
 266
 267   void ClobberPhysRegOnly(unsigned PhysReg);
 268 public:
 269   AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii)
 270     : MRI(mri), TII(tii) {
 271   }
 272
 273   /// getSpillSlotPhysReg - If the specified stack slot is available in a
 274   /// physical register, return that PhysReg, otherwise return 0.
 275   unsigned getSpillSlotPhysReg(int Slot) const {
 276     std::map<int, unsigned>::const_iterator I = SpillSlotsAvailable.find(Slot);
 277     if (I != SpillSlotsAvailable.end())
 278       return I->second >> 1;  // Remove the CanClobber bit.
 279     return 0;
 280   }
 281
 282   const MRegisterInfo *getRegInfo() const { return MRI; }
 283
 284   /// addAvailable - Mark that the specified stack slot is available in the
 285   /// specified physreg.  If CanClobber is true, the physreg can be modified at
 286   /// any time without changing the semantics of the program.
 287   void addAvailable(int Slot, unsigned Reg, bool CanClobber = true) {
 288     // If this stack slot is thought to be available in some other physreg,
 289     // remove its record.
 290     ModifyStackSlot(Slot);
 291
 292     PhysRegsAvailable.insert(std::make_pair(Reg, Slot));
 293     SpillSlotsAvailable[Slot] = (Reg << 1) | (unsigned)CanClobber;
 294
 295     DEBUG(std::cerr << "Remembering SS#" << Slot << " in physreg "
 296                     << MRI->getName(Reg) << "\n");
 297   }
 298
 299   /// canClobberPhysReg - Return true if the spiller is allowed to change the
 300   /// value of the specified stackslot register if it desires.  The specified
 301   /// stack slot must be available in a physreg for this query to make sense.
 302   bool canClobberPhysReg(int Slot) const {
 303     assert(SpillSlotsAvailable.count(Slot) && "Slot not available!");
 304     return SpillSlotsAvailable.find(Slot)->second & 1;
 305   }
 306
 307   /// ClobberPhysReg - This is called when the specified physreg changes
 308   /// value.  We use this to invalidate any info about stuff we thing lives in
 309   /// it and any of its aliases.
 310   void ClobberPhysReg(unsigned PhysReg);
 311
 312   /// ModifyStackSlot - This method is called when the value in a stack slot
 313   /// changes.  This removes information about which register the previous value
 314   /// for this slot lives in (as the previous value is dead now).
 315   void ModifyStackSlot(int Slot);
 316 };
 317 }
 318
 319 /// ClobberPhysRegOnly - This is called when the specified physreg changes
 320 /// value.  We use this to invalidate any info about stuff we thing lives in it.
 321 void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
 322   std::multimap<unsigned, int>::iterator I =
 323     PhysRegsAvailable.lower_bound(PhysReg);
 324   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
 325     int Slot = I->second;
 326     PhysRegsAvailable.erase(I++);
 327     assert((SpillSlotsAvailable[Slot] >> 1) == PhysReg &&
 328            "Bidirectional map mismatch!");
 329     SpillSlotsAvailable.erase(Slot);
 330     DEBUG(std::cerr << "PhysReg " << MRI->getName(PhysReg)
 331                     << " clobbered, invalidating SS#" << Slot << "\n");
 332   }
 333 }
 334
 335 /// ClobberPhysReg - This is called when the specified physreg changes
 336 /// value.  We use this to invalidate any info about stuff we thing lives in
 337 /// it and any of its aliases.
 338 void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
 339   for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS)
 340     ClobberPhysRegOnly(*AS);
 341   ClobberPhysRegOnly(PhysReg);
 342 }
 343
 344 /// ModifyStackSlot - This method is called when the value in a stack slot
 345 /// changes.  This removes information about which register the previous value
 346 /// for this slot lives in (as the previous value is dead now).
 347 void AvailableSpills::ModifyStackSlot(int Slot) {
 348   std::map<int, unsigned>::iterator It = SpillSlotsAvailable.find(Slot);
 349   if (It == SpillSlotsAvailable.end()) return;
 350   unsigned Reg = It->second >> 1;
 351   SpillSlotsAvailable.erase(It);
 352
 353   // This register may hold the value of multiple stack slots, only remove this
 354   // stack slot from the set of values the register contains.
 355   std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
 356   for (; ; ++I) {
 357     assert(I != PhysRegsAvailable.end() && I->first == Reg &&
 358            "Map inverse broken!");
 359     if (I->second == Slot) break;
 360   }
 361   PhysRegsAvailable.erase(I);
 362 }
 363
 364
 365
 366 // ReusedOp - For each reused operand, we keep track of a bit of information, in
 367 // case we need to rollback upon processing a new operand.  See comments below.
 368 namespace {
 369   struct ReusedOp {
 370     // The MachineInstr operand that reused an available value.
 371     unsigned Operand;
 372
 373     // StackSlot - The spill slot of the value being reused.
 374     unsigned StackSlot;
 375
 376     // PhysRegReused - The physical register the value was available in.
 377     unsigned PhysRegReused;
 378
 379     // AssignedPhysReg - The physreg that was assigned for use by the reload.
 380     unsigned AssignedPhysReg;
 381
 382     // VirtReg - The virtual register itself.
 383     unsigned VirtReg;
 384
 385     ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
 386              unsigned vreg)
 387       : Operand(o), StackSlot(ss), PhysRegReused(prr), AssignedPhysReg(apr),
 388       VirtReg(vreg) {}
 389   };
 390
 391   /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
 392   /// is reused instead of reloaded.
 393   class VISIBILITY_HIDDEN ReuseInfo {
 394     MachineInstr &MI;
 395     std::vector<ReusedOp> Reuses;
 396   public:
 397     ReuseInfo(MachineInstr &mi) : MI(mi) {}
 398
 399     bool hasReuses() const {
 400       return !Reuses.empty();
 401     }
 402
 403     /// addReuse - If we choose to reuse a virtual register that is already
 404     /// available instead of reloading it, remember that we did so.
 405     void addReuse(unsigned OpNo, unsigned StackSlot,
 406                   unsigned PhysRegReused, unsigned AssignedPhysReg,
 407                   unsigned VirtReg) {
 408       // If the reload is to the assigned register anyway, no undo will be
 409       // required.
 410       if (PhysRegReused == AssignedPhysReg) return;
 411
 412       // Otherwise, remember this.
 413       Reuses.push_back(ReusedOp(OpNo, StackSlot, PhysRegReused,
 414                                 AssignedPhysReg, VirtReg));
 415     }
 416
 417     /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 418     /// is some other operand that is using the specified register, either pick
 419     /// a new register to use, or evict the previous reload and use this reg.
 420     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 421                              AvailableSpills &Spills,
 422                              std::map<int, MachineInstr*> &MaybeDeadStores) {
 423       if (Reuses.empty()) return PhysReg;  // This is most often empty.
 424
 425       for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
 426         ReusedOp &Op = Reuses[ro];
 427         // If we find some other reuse that was supposed to use this register
 428         // exactly for its reload, we can change this reload to use ITS reload
 429         // register.
 430         if (Op.PhysRegReused == PhysReg) {
 431           // Yup, use the reload register that we didn't use before.
 432           unsigned NewReg = Op.AssignedPhysReg;
 433
 434           // Remove the record for the previous reuse.  We know it can never be
 435           // invalidated now.
 436           Reuses.erase(Reuses.begin()+ro);
 437           return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores);
 438         } else {
 439           // Otherwise, we might also have a problem if a previously reused
 440           // value aliases the new register.  If so, codegen the previous reload
 441           // and use this one.
 442           unsigned PRRU = Op.PhysRegReused;
 443           const MRegisterInfo *MRI = Spills.getRegInfo();
 444           if (MRI->areAliases(PRRU, PhysReg)) {
 445             // Okay, we found out that an alias of a reused register
 446             // was used.  This isn't good because it means we have
 447             // to undo a previous reuse.
 448             MachineBasicBlock *MBB = MI->getParent();
 449             const TargetRegisterClass *AliasRC =
 450               MBB->getParent()->getSSARegMap()->getRegClass(Op.VirtReg);
 451
 452             // Copy Op out of the vector and remove it, we're going to insert an
 453             // explicit load for it.
 454             ReusedOp NewOp = Op;
 455             Reuses.erase(Reuses.begin()+ro);
 456
 457             // Ok, we're going to try to reload the assigned physreg into the
 458             // slot that we were supposed to in the first place.  However, that
 459             // register could hold a reuse.  Check to see if it conflicts or
 460             // would prefer us to use a different register.
 461             unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg,
 462                                                   MI, Spills, MaybeDeadStores);
 463
 464             MRI->loadRegFromStackSlot(*MBB, MI, NewPhysReg,
 465                                       NewOp.StackSlot, AliasRC);
 466             Spills.ClobberPhysReg(NewPhysReg);
 467             Spills.ClobberPhysReg(NewOp.PhysRegReused);
 468
 469             // Any stores to this stack slot are not dead anymore.
 470             MaybeDeadStores.erase(NewOp.StackSlot);
 471
 472             MI->getOperand(NewOp.Operand).setReg(NewPhysReg);
 473
 474             Spills.addAvailable(NewOp.StackSlot, NewPhysReg);
 475             ++NumLoads;
 476             DEBUG(MachineBasicBlock::iterator MII = MI;
 477                   std::cerr << '\t' << *prior(MII));
 478
 479             DEBUG(std::cerr << "Reuse undone!\n");
 480             --NumReused;
 481
 482             // Finally, PhysReg is now available, go ahead and use it.
 483             return PhysReg;
 484           }
 485         }
 486       }
 487       return PhysReg;
 488     }
 489   };
 490 }
 491
 492
 493 /// rewriteMBB - Keep track of which spills are available even after the
 494 /// register allocator is done with them.  If possible, avoid reloading vregs.
 495 void LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) {
 496
 497   DEBUG(std::cerr << MBB.getBasicBlock()->getName() << ":\n");
 498
 499   // Spills - Keep track of which spilled values are available in physregs so
 500   // that we can choose to reuse the physregs instead of emitting reloads.
 501   AvailableSpills Spills(MRI, TII);
 502
 503   // MaybeDeadStores - When we need to write a value back into a stack slot,
 504   // keep track of the inserted store.  If the stack slot value is never read
 505   // (because the value was used from some available register, for example), and
 506   // subsequently stored to, the original store is dead.  This map keeps track
 507   // of inserted stores that are not used.  If we see a subsequent store to the
 508   // same stack slot, the original store is deleted.
 509   std::map<int, MachineInstr*> MaybeDeadStores;
 510
 511   bool *PhysRegsUsed = MBB.getParent()->getUsedPhysregs();
 512
 513   for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
 514        MII != E; ) {
 515     MachineInstr &MI = *MII;
 516     MachineBasicBlock::iterator NextMII = MII; ++NextMII;
 517
 518     /// ReusedOperands - Keep track of operand reuse in case we need to undo
 519     /// reuse.
 520     ReuseInfo ReusedOperands(MI);
 521
 522     // Process all of the spilled uses and all non spilled reg references.
 523     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 524       MachineOperand &MO = MI.getOperand(i);
 525       if (!MO.isRegister() || MO.getReg() == 0)
 526         continue;   // Ignore non-register operands.
 527
 528       if (MRegisterInfo::isPhysicalRegister(MO.getReg())) {
 529         // Ignore physregs for spilling, but remember that it is used by this
 530         // function.
 531         PhysRegsUsed[MO.getReg()] = true;
 532         continue;
 533       }
 534
 535       assert(MRegisterInfo::isVirtualRegister(MO.getReg()) &&
 536              "Not a virtual or a physical register?");
 537
 538       unsigned VirtReg = MO.getReg();
 539       if (!VRM.hasStackSlot(VirtReg)) {
 540         // This virtual register was assigned a physreg!
 541         unsigned Phys = VRM.getPhys(VirtReg);
 542         PhysRegsUsed[Phys] = true;
 543         MI.getOperand(i).setReg(Phys);
 544         continue;
 545       }
 546
 547       // This virtual register is now known to be a spilled value.
 548       if (!MO.isUse())
 549         continue;  // Handle defs in the loop below (handle use&def here though)
 550
 551       int StackSlot = VRM.getStackSlot(VirtReg);
 552       unsigned PhysReg;
 553
 554       // Check to see if this stack slot is available.
 555       if ((PhysReg = Spills.getSpillSlotPhysReg(StackSlot))) {
 556
 557         // This spilled operand might be part of a two-address operand.  If this
 558         // is the case, then changing it will necessarily require changing the
 559         // def part of the instruction as well.  However, in some cases, we
 560         // aren't allowed to modify the reused register.  If none of these cases
 561         // apply, reuse it.
 562         bool CanReuse = true;
 563         if (i == 1 && MI.getOperand(0).isReg() &&
 564             MI.getOperand(0).getReg() == VirtReg &&
 565             TII->isTwoAddrInstr(MI.getOpcode())) {
 566           // Okay, we have a two address operand.  We can reuse this physreg as
 567           // long as we are allowed to clobber the value.
 568           CanReuse = Spills.canClobberPhysReg(StackSlot);
 569         }
 570
 571         if (CanReuse) {
 572           // If this stack slot value is already available, reuse it!
 573           DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg "
 574                           << MRI->getName(PhysReg) << " for vreg"
 575                           << VirtReg <<" instead of reloading into physreg "
 576                           << MRI->getName(VRM.getPhys(VirtReg)) << "\n");
 577           MI.getOperand(i).setReg(PhysReg);
 578
 579           // The only technical detail we have is that we don't know that
 580           // PhysReg won't be clobbered by a reloaded stack slot that occurs
 581           // later in the instruction.  In particular, consider 'op V1, V2'.
 582           // If V1 is available in physreg R0, we would choose to reuse it
 583           // here, instead of reloading it into the register the allocator
 584           // indicated (say R1).  However, V2 might have to be reloaded
 585           // later, and it might indicate that it needs to live in R0.  When
 586           // this occurs, we need to have information available that
 587           // indicates it is safe to use R1 for the reload instead of R0.
 588           //
 589           // To further complicate matters, we might conflict with an alias,
 590           // or R0 and R1 might not be compatible with each other.  In this
 591           // case, we actually insert a reload for V1 in R1, ensuring that
 592           // we can get at R0 or its alias.
 593           ReusedOperands.addReuse(i, StackSlot, PhysReg,
 594                                   VRM.getPhys(VirtReg), VirtReg);
 595           ++NumReused;
 596           continue;
 597         }
 598
 599         // Otherwise we have a situation where we have a two-address instruction
 600         // whose mod/ref operand needs to be reloaded.  This reload is already
 601         // available in some register "PhysReg", but if we used PhysReg as the
 602         // operand to our 2-addr instruction, the instruction would modify
 603         // PhysReg.  This isn't cool if something later uses PhysReg and expects
 604         // to get its initial value.
 605         //
 606         // To avoid this problem, and to avoid doing a load right after a store,
 607         // we emit a copy from PhysReg into the designated register for this
 608         // operand.
 609         unsigned DesignatedReg = VRM.getPhys(VirtReg);
 610         assert(DesignatedReg && "Must map virtreg to physreg!");
 611
 612         // Note that, if we reused a register for a previous operand, the
 613         // register we want to reload into might not actually be
 614         // available.  If this occurs, use the register indicated by the
 615         // reuser.
 616         if (ReusedOperands.hasReuses())
 617           DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI,
 618                                                       Spills, MaybeDeadStores);
 619
 620         // If the mapped designated register is actually the physreg we have
 621         // incoming, we don't need to inserted a dead copy.
 622         if (DesignatedReg == PhysReg) {
 623           // If this stack slot value is already available, reuse it!
 624           DEBUG(std::cerr << "Reusing SS#" << StackSlot << " from physreg "
 625                           << MRI->getName(PhysReg) << " for vreg"
 626                           << VirtReg
 627                           << " instead of reloading into same physreg.\n");
 628           MI.getOperand(i).setReg(PhysReg);
 629           ++NumReused;
 630           continue;
 631         }
 632
 633         const TargetRegisterClass* RC =
 634           MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
 635
 636         PhysRegsUsed[DesignatedReg] = true;
 637         MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC);
 638
 639         // This invalidates DesignatedReg.
 640         Spills.ClobberPhysReg(DesignatedReg);
 641
 642         Spills.addAvailable(StackSlot, DesignatedReg);
 643         MI.getOperand(i).setReg(DesignatedReg);
 644         DEBUG(std::cerr << '\t' << *prior(MII));
 645         ++NumReused;
 646         continue;
 647       }
 648
 649       // Otherwise, reload it and remember that we have it.
 650       PhysReg = VRM.getPhys(VirtReg);
 651       assert(PhysReg && "Must map virtreg to physreg!");
 652       const TargetRegisterClass* RC =
 653         MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
 654
 655       // Note that, if we reused a register for a previous operand, the
 656       // register we want to reload into might not actually be
 657       // available.  If this occurs, use the register indicated by the
 658       // reuser.
 659       if (ReusedOperands.hasReuses())
 660         PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI,
 661                                                  Spills, MaybeDeadStores);
 662
 663       PhysRegsUsed[PhysReg] = true;
 664       MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
 665       // This invalidates PhysReg.
 666       Spills.ClobberPhysReg(PhysReg);
 667
 668       // Any stores to this stack slot are not dead anymore.
 669       MaybeDeadStores.erase(StackSlot);
 670       Spills.addAvailable(StackSlot, PhysReg);
 671       ++NumLoads;
 672       MI.getOperand(i).setReg(PhysReg);
 673       DEBUG(std::cerr << '\t' << *prior(MII));
 674     }
 675
 676     // Loop over all of the implicit defs, clearing them from our available
 677     // sets.
 678     const unsigned *ImpDef = TII->getImplicitDefs(MI.getOpcode());
 679     if (ImpDef) {
 680       for ( ; *ImpDef; ++ImpDef) {
 681         PhysRegsUsed[*ImpDef] = true;
 682         Spills.ClobberPhysReg(*ImpDef);
 683       }
 684     }
 685
 686     DEBUG(std::cerr << '\t' << MI);
 687
 688     // If we have folded references to memory operands, make sure we clear all
 689     // physical registers that may contain the value of the spilled virtual
 690     // register
 691     VirtRegMap::MI2VirtMapTy::const_iterator I, End;
 692     for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
 693       DEBUG(std::cerr << "Folded vreg: " << I->second.first << "  MR: "
 694                       << I->second.second);
 695       unsigned VirtReg = I->second.first;
 696       VirtRegMap::ModRef MR = I->second.second;
 697       if (!VRM.hasStackSlot(VirtReg)) {
 698         DEBUG(std::cerr << ": No stack slot!\n");
 699         continue;
 700       }
 701       int SS = VRM.getStackSlot(VirtReg);
 702       DEBUG(std::cerr << " - StackSlot: " << SS << "\n");
 703
 704       // If this folded instruction is just a use, check to see if it's a
 705       // straight load from the virt reg slot.
 706       if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
 707         int FrameIdx;
 708         if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
 709           // If this spill slot is available, turn it into a copy (or nothing)
 710           // instead of leaving it as a load!
 711           unsigned InReg;
 712           if (FrameIdx == SS && (InReg = Spills.getSpillSlotPhysReg(SS))) {
 713             DEBUG(std::cerr << "Promoted Load To Copy: " << MI);
 714             MachineFunction &MF = *MBB.getParent();
 715             if (DestReg != InReg) {
 716               MRI->copyRegToReg(MBB, &MI, DestReg, InReg,
 717                                 MF.getSSARegMap()->getRegClass(VirtReg));
 718               // Revisit the copy so we make sure to notice the effects of the
 719               // operation on the destreg (either needing to RA it if it's
 720               // virtual or needing to clobber any values if it's physical).
 721               NextMII = &MI;
 722               --NextMII;  // backtrack to the copy.
 723             }
 724             VRM.RemoveFromFoldedVirtMap(&MI);
 725             MBB.erase(&MI);
 726             goto ProcessNextInst;
 727           }
 728         }
 729       }
 730
 731       // If this reference is not a use, any previous store is now dead.
 732       // Otherwise, the store to this stack slot is not dead anymore.
 733       std::map<int, MachineInstr*>::iterator MDSI = MaybeDeadStores.find(SS);
 734       if (MDSI != MaybeDeadStores.end()) {
 735         if (MR & VirtRegMap::isRef)   // Previous store is not dead.
 736           MaybeDeadStores.erase(MDSI);
 737         else {
 738           // If we get here, the store is dead, nuke it now.
 739           assert(VirtRegMap::isMod && "Can't be modref!");
 740           DEBUG(std::cerr << "Removed dead store:\t" << *MDSI->second);
 741           MBB.erase(MDSI->second);
 742           VRM.RemoveFromFoldedVirtMap(MDSI->second);
 743           MaybeDeadStores.erase(MDSI);
 744           ++NumDSE;
 745         }
 746       }
 747
 748       // If the spill slot value is available, and this is a new definition of
 749       // the value, the value is not available anymore.
 750       if (MR & VirtRegMap::isMod) {
 751         // Notice that the value in this stack slot has been modified.
 752         Spills.ModifyStackSlot(SS);
 753
 754         // If this is *just* a mod of the value, check to see if this is just a
 755         // store to the spill slot (i.e. the spill got merged into the copy). If
 756         // so, realize that the vreg is available now, and add the store to the
 757         // MaybeDeadStore info.
 758         int StackSlot;
 759         if (!(MR & VirtRegMap::isRef)) {
 760           if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
 761             assert(MRegisterInfo::isPhysicalRegister(SrcReg) &&
 762                    "Src hasn't been allocated yet?");
 763             // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
 764             // this as a potentially dead store in case there is a subsequent
 765             // store into the stack slot without a read from it.
 766             MaybeDeadStores[StackSlot] = &MI;
 767
 768             // If the stack slot value was previously available in some other
 769             // register, change it now.  Otherwise, make the register available,
 770             // in PhysReg.
 771             Spills.addAvailable(StackSlot, SrcReg, false /*don't clobber*/);
 772           }
 773         }
 774       }
 775     }
 776
 777     // Process all of the spilled defs.
 778     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 779       MachineOperand &MO = MI.getOperand(i);
 780       if (MO.isRegister() && MO.getReg() && MO.isDef()) {
 781         unsigned VirtReg = MO.getReg();
 782
 783         if (!MRegisterInfo::isVirtualRegister(VirtReg)) {
 784           // Check to see if this is a noop copy.  If so, eliminate the
 785           // instruction before considering the dest reg to be changed.
 786           unsigned Src, Dst;
 787           if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
 788             ++NumDCE;
 789             DEBUG(std::cerr << "Removing now-noop copy: " << MI);
 790             MBB.erase(&MI);
 791             VRM.RemoveFromFoldedVirtMap(&MI);
 792             goto ProcessNextInst;
 793           }
 794           Spills.ClobberPhysReg(VirtReg);
 795           continue;
 796         }
 797
 798         // The only vregs left are stack slot definitions.
 799         int StackSlot = VRM.getStackSlot(VirtReg);
 800         const TargetRegisterClass *RC =
 801           MBB.getParent()->getSSARegMap()->getRegClass(VirtReg);
 802
 803         // If this def is part of a two-address operand, make sure to execute
 804         // the store from the correct physical register.
 805         unsigned PhysReg;
 806         if (i == 0 && TII->isTwoAddrInstr(MI.getOpcode()))
 807           PhysReg = MI.getOperand(1).getReg();
 808         else
 809           PhysReg = VRM.getPhys(VirtReg);
 810
 811         PhysRegsUsed[PhysReg] = true;
 812         MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, StackSlot, RC);
 813         DEBUG(std::cerr << "Store:\t" << *next(MII));
 814         MI.getOperand(i).setReg(PhysReg);
 815
 816         // Check to see if this is a noop copy.  If so, eliminate the
 817         // instruction before considering the dest reg to be changed.
 818         {
 819           unsigned Src, Dst;
 820           if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) {
 821             ++NumDCE;
 822             DEBUG(std::cerr << "Removing now-noop copy: " << MI);
 823             MBB.erase(&MI);
 824             VRM.RemoveFromFoldedVirtMap(&MI);
 825             goto ProcessNextInst;
 826           }
 827         }
 828
 829         // If there is a dead store to this stack slot, nuke it now.
 830         MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
 831         if (LastStore) {
 832           DEBUG(std::cerr << "Removed dead store:\t" << *LastStore);
 833           ++NumDSE;
 834           MBB.erase(LastStore);
 835           VRM.RemoveFromFoldedVirtMap(LastStore);
 836         }
 837         LastStore = next(MII);
 838
 839         // If the stack slot value was previously available in some other
 840         // register, change it now.  Otherwise, make the register available,
 841         // in PhysReg.
 842         Spills.ModifyStackSlot(StackSlot);
 843         Spills.ClobberPhysReg(PhysReg);
 844         Spills.addAvailable(StackSlot, PhysReg);
 845         ++NumStores;
 846       }
 847     }
 848   ProcessNextInst:
 849     MII = NextMII;
 850   }
 851 }
 852
 853
 854
 855 llvm::Spiller* llvm::createSpiller() {
 856   switch (SpillerOpt) {
 857   default: assert(0 && "Unreachable!");
 858   case local:
 859     return new LocalSpiller();
 860   case simple:
 861     return new SimpleSpiller();
 862   }
 863 }