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