LLVM API Documentation

VirtRegRewriter.cpp

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/Rewriter.cpp -  Rewriter -----------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 
00010 #define DEBUG_TYPE "virtregrewriter"
00011 #include "VirtRegRewriter.h"
00012 #include "llvm/Support/Compiler.h"
00013 #include "llvm/Support/ErrorHandling.h"
00014 #include "llvm/Support/raw_ostream.h"
00015 #include "llvm/Target/TargetLowering.h"
00016 #include "llvm/ADT/DepthFirstIterator.h"
00017 #include "llvm/ADT/Statistic.h"
00018 #include "llvm/ADT/STLExtras.h"
00019 #include <algorithm>
00020 using namespace llvm;
00021 
00022 STATISTIC(NumDSE     , "Number of dead stores elided");
00023 STATISTIC(NumDSS     , "Number of dead spill slots removed");
00024 STATISTIC(NumCommutes, "Number of instructions commuted");
00025 STATISTIC(NumDRM     , "Number of re-materializable defs elided");
00026 STATISTIC(NumStores  , "Number of stores added");
00027 STATISTIC(NumPSpills , "Number of physical register spills");
00028 STATISTIC(NumOmitted , "Number of reloads omited");
00029 STATISTIC(NumAvoided , "Number of reloads deemed unnecessary");
00030 STATISTIC(NumCopified, "Number of available reloads turned into copies");
00031 STATISTIC(NumReMats  , "Number of re-materialization");
00032 STATISTIC(NumLoads   , "Number of loads added");
00033 STATISTIC(NumReused  , "Number of values reused");
00034 STATISTIC(NumDCE     , "Number of copies elided");
00035 STATISTIC(NumSUnfold , "Number of stores unfolded");
00036 STATISTIC(NumModRefUnfold, "Number of modref unfolded");
00037 
00038 namespace {
00039   enum RewriterName { local, trivial };
00040 }
00041 
00042 static cl::opt<RewriterName>
00043 RewriterOpt("rewriter",
00044             cl::desc("Rewriter to use: (default: local)"),
00045             cl::Prefix,
00046             cl::values(clEnumVal(local,   "local rewriter"),
00047                        clEnumVal(trivial, "trivial rewriter"),
00048                        clEnumValEnd),
00049             cl::init(local));
00050 
00051 static cl::opt<bool>
00052 ScheduleSpills("schedule-spills",
00053                cl::desc("Schedule spill code"),
00054                cl::init(false));
00055 
00056 VirtRegRewriter::~VirtRegRewriter() {}
00057 
00058 namespace {
00059 
00060 /// This class is intended for use with the new spilling framework only. It
00061 /// rewrites vreg def/uses to use the assigned preg, but does not insert any
00062 /// spill code.
00063 struct VISIBILITY_HIDDEN TrivialRewriter : public VirtRegRewriter {
00064 
00065   bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
00066                             LiveIntervals* LIs) {
00067     DOUT << "********** REWRITE MACHINE CODE **********\n";
00068     DEBUG(errs() << "********** Function: " 
00069           << MF.getFunction()->getName() << '\n');
00070     DOUT << "**** Machine Instrs"
00071          << "(NOTE! Does not include spills and reloads!) ****\n";
00072     DEBUG(MF.dump());
00073 
00074     MachineRegisterInfo *mri = &MF.getRegInfo();
00075 
00076     bool changed = false;
00077 
00078     for (LiveIntervals::iterator liItr = LIs->begin(), liEnd = LIs->end();
00079          liItr != liEnd; ++liItr) {
00080 
00081       if (TargetRegisterInfo::isVirtualRegister(liItr->first)) {
00082         if (VRM.hasPhys(liItr->first)) {
00083           unsigned preg = VRM.getPhys(liItr->first);
00084           mri->replaceRegWith(liItr->first, preg);
00085           mri->setPhysRegUsed(preg);
00086           changed = true;
00087         }
00088       }
00089       else {
00090         if (!liItr->second->empty()) {
00091           mri->setPhysRegUsed(liItr->first);
00092         }
00093       }
00094     }
00095 
00096     
00097     DOUT << "**** Post Machine Instrs ****\n";
00098     DEBUG(MF.dump());
00099     
00100     return changed;
00101   }
00102 
00103 };
00104 
00105 }
00106 
00107 // ************************************************************************ //
00108 
00109 namespace {
00110 
00111 /// AvailableSpills - As the local rewriter is scanning and rewriting an MBB
00112 /// from top down, keep track of which spill slots or remat are available in
00113 /// each register.
00114 ///
00115 /// Note that not all physregs are created equal here.  In particular, some
00116 /// physregs are reloads that we are allowed to clobber or ignore at any time.
00117 /// Other physregs are values that the register allocated program is using
00118 /// that we cannot CHANGE, but we can read if we like.  We keep track of this
00119 /// on a per-stack-slot / remat id basis as the low bit in the value of the
00120 /// SpillSlotsAvailable entries.  The predicate 'canClobberPhysReg()' checks
00121 /// this bit and addAvailable sets it if.
00122 class VISIBILITY_HIDDEN AvailableSpills {
00123   const TargetRegisterInfo *TRI;
00124   const TargetInstrInfo *TII;
00125 
00126   // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
00127   // or remat'ed virtual register values that are still available, due to
00128   // being loaded or stored to, but not invalidated yet.
00129   std::map<int, unsigned> SpillSlotsOrReMatsAvailable;
00130 
00131   // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
00132   // indicating which stack slot values are currently held by a physreg.  This
00133   // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
00134   // physreg is modified.
00135   std::multimap<unsigned, int> PhysRegsAvailable;
00136 
00137   void disallowClobberPhysRegOnly(unsigned PhysReg);
00138 
00139   void ClobberPhysRegOnly(unsigned PhysReg);
00140 public:
00141   AvailableSpills(const TargetRegisterInfo *tri, const TargetInstrInfo *tii)
00142     : TRI(tri), TII(tii) {
00143   }
00144 
00145   /// clear - Reset the state.
00146   void clear() {
00147     SpillSlotsOrReMatsAvailable.clear();
00148     PhysRegsAvailable.clear();
00149   }
00150 
00151   const TargetRegisterInfo *getRegInfo() const { return TRI; }
00152 
00153   /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
00154   /// available in a physical register, return that PhysReg, otherwise
00155   /// return 0.
00156   unsigned getSpillSlotOrReMatPhysReg(int Slot) const {
00157     std::map<int, unsigned>::const_iterator I =
00158       SpillSlotsOrReMatsAvailable.find(Slot);
00159     if (I != SpillSlotsOrReMatsAvailable.end()) {
00160       return I->second >> 1;  // Remove the CanClobber bit.
00161     }
00162     return 0;
00163   }
00164 
00165   /// addAvailable - Mark that the specified stack slot / remat is available
00166   /// in the specified physreg.  If CanClobber is true, the physreg can be
00167   /// modified at any time without changing the semantics of the program.
00168   void addAvailable(int SlotOrReMat, unsigned Reg, bool CanClobber = true) {
00169     // If this stack slot is thought to be available in some other physreg, 
00170     // remove its record.
00171     ModifyStackSlotOrReMat(SlotOrReMat);
00172 
00173     PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat));
00174     SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) |
00175                                               (unsigned)CanClobber;
00176 
00177     if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
00178       DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1;
00179     else
00180       DOUT << "Remembering SS#" << SlotOrReMat;
00181     DOUT << " in physreg " << TRI->getName(Reg) << "\n";
00182   }
00183 
00184   /// canClobberPhysRegForSS - Return true if the spiller is allowed to change
00185   /// the value of the specified stackslot register if it desires. The
00186   /// specified stack slot must be available in a physreg for this query to
00187   /// make sense.
00188   bool canClobberPhysRegForSS(int SlotOrReMat) const {
00189     assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
00190            "Value not available!");
00191     return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
00192   }
00193 
00194   /// canClobberPhysReg - Return true if the spiller is allowed to clobber the
00195   /// physical register where values for some stack slot(s) might be
00196   /// available.
00197   bool canClobberPhysReg(unsigned PhysReg) const {
00198     std::multimap<unsigned, int>::const_iterator I =
00199       PhysRegsAvailable.lower_bound(PhysReg);
00200     while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
00201       int SlotOrReMat = I->second;
00202       I++;
00203       if (!canClobberPhysRegForSS(SlotOrReMat))
00204         return false;
00205     }
00206     return true;
00207   }
00208 
00209   /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
00210   /// stackslot register. The register is still available but is no longer
00211   /// allowed to be modifed.
00212   void disallowClobberPhysReg(unsigned PhysReg);
00213 
00214   /// ClobberPhysReg - This is called when the specified physreg changes
00215   /// value.  We use this to invalidate any info about stuff that lives in
00216   /// it and any of its aliases.
00217   void ClobberPhysReg(unsigned PhysReg);
00218 
00219   /// ModifyStackSlotOrReMat - This method is called when the value in a stack
00220   /// slot changes.  This removes information about which register the
00221   /// previous value for this slot lives in (as the previous value is dead
00222   /// now).
00223   void ModifyStackSlotOrReMat(int SlotOrReMat);
00224 
00225   /// AddAvailableRegsToLiveIn - Availability information is being kept coming
00226   /// into the specified MBB. Add available physical registers as potential
00227   /// live-in's. If they are reused in the MBB, they will be added to the
00228   /// live-in set to make register scavenger and post-allocation scheduler.
00229   void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
00230                                 std::vector<MachineOperand*> &KillOps);
00231 };
00232 
00233 }
00234 
00235 // ************************************************************************ //
00236 
00237 // Given a location where a reload of a spilled register or a remat of
00238 // a constant is to be inserted, attempt to find a safe location to
00239 // insert the load at an earlier point in the basic-block, to hide
00240 // latency of the load and to avoid address-generation interlock
00241 // issues.
00242 static MachineBasicBlock::iterator
00243 ComputeReloadLoc(MachineBasicBlock::iterator const InsertLoc,
00244                  MachineBasicBlock::iterator const Begin,
00245                  unsigned PhysReg,
00246                  const TargetRegisterInfo *TRI,
00247                  bool DoReMat,
00248                  int SSorRMId,
00249                  const TargetInstrInfo *TII,
00250                  const MachineFunction &MF)
00251 {
00252   if (!ScheduleSpills)
00253     return InsertLoc;
00254 
00255   // Spill backscheduling is of primary interest to addresses, so
00256   // don't do anything if the register isn't in the register class
00257   // used for pointers.
00258 
00259   const TargetLowering *TL = MF.getTarget().getTargetLowering();
00260 
00261   if (!TL->isTypeLegal(TL->getPointerTy()))
00262     // Believe it or not, this is true on PIC16.
00263     return InsertLoc;
00264 
00265   const TargetRegisterClass *ptrRegClass =
00266     TL->getRegClassFor(TL->getPointerTy());
00267   if (!ptrRegClass->contains(PhysReg))
00268     return InsertLoc;
00269 
00270   // Scan upwards through the preceding instructions. If an instruction doesn't
00271   // reference the stack slot or the register we're loading, we can
00272   // backschedule the reload up past it.
00273   MachineBasicBlock::iterator NewInsertLoc = InsertLoc;
00274   while (NewInsertLoc != Begin) {
00275     MachineBasicBlock::iterator Prev = prior(NewInsertLoc);
00276     for (unsigned i = 0; i < Prev->getNumOperands(); ++i) {
00277       MachineOperand &Op = Prev->getOperand(i);
00278       if (!DoReMat && Op.isFI() && Op.getIndex() == SSorRMId)
00279         goto stop;
00280     }
00281     if (Prev->findRegisterUseOperandIdx(PhysReg) != -1 ||
00282         Prev->findRegisterDefOperand(PhysReg))
00283       goto stop;
00284     for (const unsigned *Alias = TRI->getAliasSet(PhysReg); *Alias; ++Alias)
00285       if (Prev->findRegisterUseOperandIdx(*Alias) != -1 ||
00286           Prev->findRegisterDefOperand(*Alias))
00287         goto stop;
00288     NewInsertLoc = Prev;
00289   }
00290 stop:;
00291 
00292   // If we made it to the beginning of the block, turn around and move back
00293   // down just past any existing reloads. They're likely to be reloads/remats
00294   // for instructions earlier than what our current reload/remat is for, so
00295   // they should be scheduled earlier.
00296   if (NewInsertLoc == Begin) {
00297     int FrameIdx;
00298     while (InsertLoc != NewInsertLoc &&
00299            (TII->isLoadFromStackSlot(NewInsertLoc, FrameIdx) ||
00300             TII->isTriviallyReMaterializable(NewInsertLoc)))
00301       ++NewInsertLoc;
00302   }
00303 
00304   return NewInsertLoc;
00305 }
00306 
00307 namespace {
00308 
00309 // ReusedOp - For each reused operand, we keep track of a bit of information,
00310 // in case we need to rollback upon processing a new operand.  See comments
00311 // below.
00312 struct ReusedOp {
00313   // The MachineInstr operand that reused an available value.
00314   unsigned Operand;
00315 
00316   // StackSlotOrReMat - The spill slot or remat id of the value being reused.
00317   unsigned StackSlotOrReMat;
00318 
00319   // PhysRegReused - The physical register the value was available in.
00320   unsigned PhysRegReused;
00321 
00322   // AssignedPhysReg - The physreg that was assigned for use by the reload.
00323   unsigned AssignedPhysReg;
00324   
00325   // VirtReg - The virtual register itself.
00326   unsigned VirtReg;
00327 
00328   ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
00329            unsigned vreg)
00330     : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
00331       AssignedPhysReg(apr), VirtReg(vreg) {}
00332 };
00333 
00334 /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
00335 /// is reused instead of reloaded.
00336 class VISIBILITY_HIDDEN ReuseInfo {
00337   MachineInstr &MI;
00338   std::vector<ReusedOp> Reuses;
00339   BitVector PhysRegsClobbered;
00340 public:
00341   ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
00342     PhysRegsClobbered.resize(tri->getNumRegs());
00343   }
00344   
00345   bool hasReuses() const {
00346     return !Reuses.empty();
00347   }
00348   
00349   /// addReuse - If we choose to reuse a virtual register that is already
00350   /// available instead of reloading it, remember that we did so.
00351   void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
00352                 unsigned PhysRegReused, unsigned AssignedPhysReg,
00353                 unsigned VirtReg) {
00354     // If the reload is to the assigned register anyway, no undo will be
00355     // required.
00356     if (PhysRegReused == AssignedPhysReg) return;
00357     
00358     // Otherwise, remember this.
00359     Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused, 
00360                               AssignedPhysReg, VirtReg));
00361   }
00362 
00363   void markClobbered(unsigned PhysReg) {
00364     PhysRegsClobbered.set(PhysReg);
00365   }
00366 
00367   bool isClobbered(unsigned PhysReg) const {
00368     return PhysRegsClobbered.test(PhysReg);
00369   }
00370   
00371   /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
00372   /// is some other operand that is using the specified register, either pick
00373   /// a new register to use, or evict the previous reload and use this reg. 
00374   unsigned GetRegForReload(const TargetRegisterClass *RC, unsigned PhysReg,
00375                            MachineFunction &MF, MachineInstr *MI,
00376                            AvailableSpills &Spills,
00377                            std::vector<MachineInstr*> &MaybeDeadStores,
00378                            SmallSet<unsigned, 8> &Rejected,
00379                            BitVector &RegKills,
00380                            std::vector<MachineOperand*> &KillOps,
00381                            VirtRegMap &VRM);
00382 
00383   /// GetRegForReload - Helper for the above GetRegForReload(). Add a
00384   /// 'Rejected' set to remember which registers have been considered and
00385   /// rejected for the reload. This avoids infinite looping in case like
00386   /// this:
00387   /// t1 := op t2, t3
00388   /// t2 <- assigned r0 for use by the reload but ended up reuse r1
00389   /// t3 <- assigned r1 for use by the reload but ended up reuse r0
00390   /// t1 <- desires r1
00391   ///       sees r1 is taken by t2, tries t2's reload register r0
00392   ///       sees r0 is taken by t3, tries t3's reload register r1
00393   ///       sees r1 is taken by t2, tries t2's reload register r0 ...
00394   unsigned GetRegForReload(unsigned VirtReg, unsigned PhysReg, MachineInstr *MI,
00395                            AvailableSpills &Spills,
00396                            std::vector<MachineInstr*> &MaybeDeadStores,
00397                            BitVector &RegKills,
00398                            std::vector<MachineOperand*> &KillOps,
00399                            VirtRegMap &VRM) {
00400     SmallSet<unsigned, 8> Rejected;
00401     MachineFunction &MF = *MI->getParent()->getParent();
00402     const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(VirtReg);
00403     return GetRegForReload(RC, PhysReg, MF, MI, Spills, MaybeDeadStores,
00404                            Rejected, RegKills, KillOps, VRM);
00405   }
00406 };
00407 
00408 }
00409 
00410 // ****************** //
00411 // Utility Functions  //
00412 // ****************** //
00413 
00414 /// findSinglePredSuccessor - Return via reference a vector of machine basic
00415 /// blocks each of which is a successor of the specified BB and has no other
00416 /// predecessor.
00417 static void findSinglePredSuccessor(MachineBasicBlock *MBB,
00418                                    SmallVectorImpl<MachineBasicBlock *> &Succs) {
00419   for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00420          SE = MBB->succ_end(); SI != SE; ++SI) {
00421     MachineBasicBlock *SuccMBB = *SI;
00422     if (SuccMBB->pred_size() == 1)
00423       Succs.push_back(SuccMBB);
00424   }
00425 }
00426 
00427 /// InvalidateKill - Invalidate register kill information for a specific
00428 /// register. This also unsets the kills marker on the last kill operand.
00429 static void InvalidateKill(unsigned Reg,
00430                            const TargetRegisterInfo* TRI,
00431                            BitVector &RegKills,
00432                            std::vector<MachineOperand*> &KillOps) {
00433   if (RegKills[Reg]) {
00434     KillOps[Reg]->setIsKill(false);
00435     // KillOps[Reg] might be a def of a super-register.
00436     unsigned KReg = KillOps[Reg]->getReg();
00437     KillOps[KReg] = NULL;
00438     RegKills.reset(KReg);
00439     for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
00440       if (RegKills[*SR]) {
00441         KillOps[*SR]->setIsKill(false);
00442         KillOps[*SR] = NULL;
00443         RegKills.reset(*SR);
00444       }
00445     }
00446   }
00447 }
00448 
00449 /// InvalidateKills - MI is going to be deleted. If any of its operands are
00450 /// marked kill, then invalidate the information.
00451 static void InvalidateKills(MachineInstr &MI,
00452                             const TargetRegisterInfo* TRI,
00453                             BitVector &RegKills,
00454                             std::vector<MachineOperand*> &KillOps,
00455                             SmallVector<unsigned, 2> *KillRegs = NULL) {
00456   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
00457     MachineOperand &MO = MI.getOperand(i);
00458     if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
00459       continue;
00460     unsigned Reg = MO.getReg();
00461     if (TargetRegisterInfo::isVirtualRegister(Reg))
00462       continue;
00463     if (KillRegs)
00464       KillRegs->push_back(Reg);
00465     assert(Reg < KillOps.size());
00466     if (KillOps[Reg] == &MO) {
00467       KillOps[Reg] = NULL;
00468       RegKills.reset(Reg);
00469       for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
00470         if (RegKills[*SR]) {
00471           KillOps[*SR] = NULL;
00472           RegKills.reset(*SR);
00473         }
00474       }
00475     }
00476   }
00477 }
00478 
00479 /// InvalidateRegDef - If the def operand of the specified def MI is now dead
00480 /// (since it's spill instruction is removed), mark it isDead. Also checks if
00481 /// the def MI has other definition operands that are not dead. Returns it by
00482 /// reference.
00483 static bool InvalidateRegDef(MachineBasicBlock::iterator I,
00484                              MachineInstr &NewDef, unsigned Reg,
00485                              bool &HasLiveDef) {
00486   // Due to remat, it's possible this reg isn't being reused. That is,
00487   // the def of this reg (by prev MI) is now dead.
00488   MachineInstr *DefMI = I;
00489   MachineOperand *DefOp = NULL;
00490   for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
00491     MachineOperand &MO = DefMI->getOperand(i);
00492     if (!MO.isReg() || !MO.isUse() || !MO.isKill() || MO.isUndef())
00493       continue;
00494     if (MO.getReg() == Reg)
00495       DefOp = &MO;
00496     else if (!MO.isDead())
00497       HasLiveDef = true;
00498   }
00499   if (!DefOp)
00500     return false;
00501 
00502   bool FoundUse = false, Done = false;
00503   MachineBasicBlock::iterator E = &NewDef;
00504   ++I; ++E;
00505   for (; !Done && I != E; ++I) {
00506     MachineInstr *NMI = I;
00507     for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) {
00508       MachineOperand &MO = NMI->getOperand(j);
00509       if (!MO.isReg() || MO.getReg() != Reg)
00510         continue;
00511       if (MO.isUse())
00512         FoundUse = true;
00513       Done = true; // Stop after scanning all the operands of this MI.
00514     }
00515   }
00516   if (!FoundUse) {
00517     // Def is dead!
00518     DefOp->setIsDead();
00519     return true;
00520   }
00521   return false;
00522 }
00523 
00524 /// UpdateKills - Track and update kill info. If a MI reads a register that is
00525 /// marked kill, then it must be due to register reuse. Transfer the kill info
00526 /// over.
00527 static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI,
00528                         BitVector &RegKills,
00529                         std::vector<MachineOperand*> &KillOps) {
00530   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
00531     MachineOperand &MO = MI.getOperand(i);
00532     if (!MO.isReg() || !MO.isUse() || MO.isUndef())
00533       continue;
00534     unsigned Reg = MO.getReg();
00535     if (Reg == 0)
00536       continue;
00537     
00538     if (RegKills[Reg] && KillOps[Reg]->getParent() != &MI) {
00539       // That can't be right. Register is killed but not re-defined and it's
00540       // being reused. Let's fix that.
00541       KillOps[Reg]->setIsKill(false);
00542       // KillOps[Reg] might be a def of a super-register.
00543       unsigned KReg = KillOps[Reg]->getReg();
00544       KillOps[KReg] = NULL;
00545       RegKills.reset(KReg);
00546 
00547       // Must be a def of a super-register. Its other sub-regsters are no
00548       // longer killed as well.
00549       for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
00550         KillOps[*SR] = NULL;
00551         RegKills.reset(*SR);
00552       }
00553 
00554       if (!MI.isRegTiedToDefOperand(i))
00555         // Unless it's a two-address operand, this is the new kill.
00556         MO.setIsKill();
00557     }
00558     if (MO.isKill()) {
00559       RegKills.set(Reg);
00560       KillOps[Reg] = &MO;
00561       for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
00562         RegKills.set(*SR);
00563         KillOps[*SR] = &MO;
00564       }
00565     }
00566   }
00567 
00568   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
00569     const MachineOperand &MO = MI.getOperand(i);
00570     if (!MO.isReg() || !MO.isDef())
00571       continue;
00572     unsigned Reg = MO.getReg();
00573     RegKills.reset(Reg);
00574     KillOps[Reg] = NULL;
00575     // It also defines (or partially define) aliases.
00576     for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
00577       RegKills.reset(*SR);
00578       KillOps[*SR] = NULL;
00579     }
00580   }
00581 }
00582 
00583 /// ReMaterialize - Re-materialize definition for Reg targetting DestReg.
00584 ///
00585 static void ReMaterialize(MachineBasicBlock &MBB,
00586                           MachineBasicBlock::iterator &MII,
00587                           unsigned DestReg, unsigned Reg,
00588                           const TargetInstrInfo *TII,
00589                           const TargetRegisterInfo *TRI,
00590                           VirtRegMap &VRM) {
00591   MachineInstr *ReMatDefMI = VRM.getReMaterializedMI(Reg);
00592 #ifndef NDEBUG
00593   const TargetInstrDesc &TID = ReMatDefMI->getDesc();
00594   assert(TID.getNumDefs() == 1 &&
00595          "Don't know how to remat instructions that define > 1 values!");
00596 #endif
00597   TII->reMaterialize(MBB, MII, DestReg,
00598                      ReMatDefMI->getOperand(0).getSubReg(), ReMatDefMI);
00599   MachineInstr *NewMI = prior(MII);
00600   for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
00601     MachineOperand &MO = NewMI->getOperand(i);
00602     if (!MO.isReg() || MO.getReg() == 0)
00603       continue;
00604     unsigned VirtReg = MO.getReg();
00605     if (TargetRegisterInfo::isPhysicalRegister(VirtReg))
00606       continue;
00607     assert(MO.isUse());
00608     unsigned SubIdx = MO.getSubReg();
00609     unsigned Phys = VRM.getPhys(VirtReg);
00610     assert(Phys);
00611     unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
00612     MO.setReg(RReg);
00613     MO.setSubReg(0);
00614   }
00615   ++NumReMats;
00616 }
00617 
00618 /// findSuperReg - Find the SubReg's super-register of given register class
00619 /// where its SubIdx sub-register is SubReg.
00620 static unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg,
00621                              unsigned SubIdx, const TargetRegisterInfo *TRI) {
00622   for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
00623        I != E; ++I) {
00624     unsigned Reg = *I;
00625     if (TRI->getSubReg(Reg, SubIdx) == SubReg)
00626       return Reg;
00627   }
00628   return 0;
00629 }
00630 
00631 // ******************************** //
00632 // Available Spills Implementation  //
00633 // ******************************** //
00634 
00635 /// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified
00636 /// stackslot register. The register is still available but is no longer
00637 /// allowed to be modifed.
00638 void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) {
00639   std::multimap<unsigned, int>::iterator I =
00640     PhysRegsAvailable.lower_bound(PhysReg);
00641   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
00642     int SlotOrReMat = I->second;
00643     I++;
00644     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
00645            "Bidirectional map mismatch!");
00646     SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1;
00647     DOUT << "PhysReg " << TRI->getName(PhysReg)
00648          << " copied, it is available for use but can no longer be modified\n";
00649   }
00650 }
00651 
00652 /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
00653 /// stackslot register and its aliases. The register and its aliases may
00654 /// still available but is no longer allowed to be modifed.
00655 void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) {
00656   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
00657     disallowClobberPhysRegOnly(*AS);
00658   disallowClobberPhysRegOnly(PhysReg);
00659 }
00660 
00661 /// ClobberPhysRegOnly - This is called when the specified physreg changes
00662 /// value.  We use this to invalidate any info about stuff we thing lives in it.
00663 void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
00664   std::multimap<unsigned, int>::iterator I =
00665     PhysRegsAvailable.lower_bound(PhysReg);
00666   while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
00667     int SlotOrReMat = I->second;
00668     PhysRegsAvailable.erase(I++);
00669     assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
00670            "Bidirectional map mismatch!");
00671     SpillSlotsOrReMatsAvailable.erase(SlotOrReMat);
00672     DOUT << "PhysReg " << TRI->getName(PhysReg)
00673          << " clobbered, invalidating ";
00674     if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
00675       DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
00676     else
00677       DOUT << "SS#" << SlotOrReMat << "\n";
00678   }
00679 }
00680 
00681 /// ClobberPhysReg - This is called when the specified physreg changes
00682 /// value.  We use this to invalidate any info about stuff we thing lives in
00683 /// it and any of its aliases.
00684 void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
00685   for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
00686     ClobberPhysRegOnly(*AS);
00687   ClobberPhysRegOnly(PhysReg);
00688 }
00689 
00690 /// AddAvailableRegsToLiveIn - Availability information is being kept coming
00691 /// into the specified MBB. Add available physical registers as potential
00692 /// live-in's. If they are reused in the MBB, they will be added to the
00693 /// live-in set to make register scavenger and post-allocation scheduler.
00694 void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock &MBB,
00695                                         BitVector &RegKills,
00696                                         std::vector<MachineOperand*> &KillOps) {
00697   std::set<unsigned> NotAvailable;
00698   for (std::multimap<unsigned, int>::iterator
00699          I = PhysRegsAvailable.begin(), E = PhysRegsAvailable.end();
00700        I != E; ++I) {
00701     unsigned Reg = I->first;
00702     const TargetRegisterClass* RC = TRI->getPhysicalRegisterRegClass(Reg);
00703     // FIXME: A temporary workaround. We can't reuse available value if it's
00704     // not safe to move the def of the virtual register's class. e.g.
00705     // X86::RFP* register classes. Do not add it as a live-in.
00706     if (!TII->isSafeToMoveRegClassDefs(RC))
00707       // This is no longer available.
00708       NotAvailable.insert(Reg);
00709     else {
00710       MBB.addLiveIn(Reg);
00711       InvalidateKill(Reg, TRI, RegKills, KillOps);
00712     }
00713 
00714     // Skip over the same register.
00715     std::multimap<unsigned, int>::iterator NI = next(I);
00716     while (NI != E && NI->first == Reg) {
00717       ++I;
00718       ++NI;
00719     }
00720   }
00721 
00722   for (std::set<unsigned>::iterator I = NotAvailable.begin(),
00723          E = NotAvailable.end(); I != E; ++I) {
00724     ClobberPhysReg(*I);
00725     for (const unsigned *SubRegs = TRI->getSubRegisters(*I);
00726        *SubRegs; ++SubRegs)
00727       ClobberPhysReg(*SubRegs);
00728   }
00729 }
00730 
00731 /// ModifyStackSlotOrReMat - This method is called when the value in a stack
00732 /// slot changes.  This removes information about which register the previous
00733 /// value for this slot lives in (as the previous value is dead now).
00734 void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) {
00735   std::map<int, unsigned>::iterator It =
00736     SpillSlotsOrReMatsAvailable.find(SlotOrReMat);
00737   if (It == SpillSlotsOrReMatsAvailable.end()) return;
00738   unsigned Reg = It->second >> 1;
00739   SpillSlotsOrReMatsAvailable.erase(It);
00740   
00741   // This register may hold the value of multiple stack slots, only remove this
00742   // stack slot from the set of values the register contains.
00743   std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
00744   for (; ; ++I) {
00745     assert(I != PhysRegsAvailable.end() && I->first == Reg &&
00746            "Map inverse broken!");
00747     if (I->second == SlotOrReMat) break;
00748   }
00749   PhysRegsAvailable.erase(I);
00750 }
00751 
00752 // ************************** //
00753 // Reuse Info Implementation  //
00754 // ************************** //
00755 
00756 /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
00757 /// is some other operand that is using the specified register, either pick
00758 /// a new register to use, or evict the previous reload and use this reg.
00759 unsigned ReuseInfo::GetRegForReload(const TargetRegisterClass *RC,
00760                          unsigned PhysReg,
00761                          MachineFunction &MF,
00762                          MachineInstr *MI, AvailableSpills &Spills,
00763                          std::vector<MachineInstr*> &MaybeDeadStores,
00764                          SmallSet<unsigned, 8> &Rejected,
00765                          BitVector &RegKills,
00766                          std::vector<MachineOperand*> &KillOps,
00767                          VirtRegMap &VRM) {
00768   const TargetInstrInfo* TII = MF.getTarget().getInstrInfo();
00769   const TargetRegisterInfo *TRI = Spills.getRegInfo();
00770   
00771   if (Reuses.empty()) return PhysReg;  // This is most often empty.
00772 
00773   for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
00774     ReusedOp &Op = Reuses[ro];
00775     // If we find some other reuse that was supposed to use this register
00776     // exactly for its reload, we can change this reload to use ITS reload
00777     // register. That is, unless its reload register has already been
00778     // considered and subsequently rejected because it has also been reused
00779     // by another operand.
00780     if (Op.PhysRegReused == PhysReg &&
00781         Rejected.count(Op.AssignedPhysReg) == 0 &&
00782         RC->contains(Op.AssignedPhysReg)) {
00783       // Yup, use the reload register that we didn't use before.
00784       unsigned NewReg = Op.AssignedPhysReg;
00785       Rejected.insert(PhysReg);
00786       return GetRegForReload(RC, NewReg, MF, MI, Spills, MaybeDeadStores, Rejected,
00787                              RegKills, KillOps, VRM);
00788     } else {
00789       // Otherwise, we might also have a problem if a previously reused
00790       // value aliases the new register. If so, codegen the previous reload
00791       // and use this one.          
00792       unsigned PRRU = Op.PhysRegReused;
00793       if (TRI->regsOverlap(PRRU, PhysReg)) {
00794         // Okay, we found out that an alias of a reused register
00795         // was used.  This isn't good because it means we have
00796         // to undo a previous reuse.
00797         MachineBasicBlock *MBB = MI->getParent();
00798         const TargetRegisterClass *AliasRC =
00799           MBB->getParent()->getRegInfo().getRegClass(Op.VirtReg);
00800 
00801         // Copy Op out of the vector and remove it, we're going to insert an
00802         // explicit load for it.
00803         ReusedOp NewOp = Op;
00804         Reuses.erase(Reuses.begin()+ro);
00805 
00806         // MI may be using only a sub-register of PhysRegUsed.
00807         unsigned RealPhysRegUsed = MI->getOperand(NewOp.Operand).getReg();
00808         unsigned SubIdx = 0;
00809         assert(TargetRegisterInfo::isPhysicalRegister(RealPhysRegUsed) &&
00810                "A reuse cannot be a virtual register");
00811         if (PRRU != RealPhysRegUsed) {
00812           // What was the sub-register index?
00813           unsigned SubReg;
00814           for (SubIdx = 1; (SubReg = TRI->getSubReg(PRRU, SubIdx)); SubIdx++)
00815             if (SubReg == RealPhysRegUsed)
00816               break;
00817           assert(SubReg == RealPhysRegUsed &&
00818                  "Operand physreg is not a sub-register of PhysRegUsed");
00819         }
00820 
00821         // Ok, we're going to try to reload the assigned physreg into the
00822         // slot that we were supposed to in the first place.  However, that
00823         // register could hold a reuse.  Check to see if it conflicts or
00824         // would prefer us to use a different register.
00825         unsigned NewPhysReg = GetRegForReload(RC, NewOp.AssignedPhysReg,
00826                                               MF, MI, Spills, MaybeDeadStores,
00827                                               Rejected, RegKills, KillOps, VRM);
00828 
00829         bool DoReMat = NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT;
00830         int SSorRMId = DoReMat
00831           ? VRM.getReMatId(NewOp.VirtReg) : NewOp.StackSlotOrReMat;
00832 
00833         // Back-schedule reloads and remats.
00834         MachineBasicBlock::iterator InsertLoc =
00835           ComputeReloadLoc(MI, MBB->begin(), PhysReg, TRI,
00836                            DoReMat, SSorRMId, TII, MF);
00837 
00838         if (DoReMat) {
00839           ReMaterialize(*MBB, InsertLoc, NewPhysReg, NewOp.VirtReg, TII,
00840                         TRI, VRM);
00841         } else { 
00842           TII->loadRegFromStackSlot(*MBB, InsertLoc, NewPhysReg,
00843                                     NewOp.StackSlotOrReMat, AliasRC);
00844           MachineInstr *LoadMI = prior(InsertLoc);
00845           VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI);
00846           // Any stores to this stack slot are not dead anymore.
00847           MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL;            
00848           ++NumLoads;
00849         }
00850         Spills.ClobberPhysReg(NewPhysReg);
00851         Spills.ClobberPhysReg(NewOp.PhysRegReused);
00852 
00853         unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) : NewPhysReg;
00854         MI->getOperand(NewOp.Operand).setReg(RReg);
00855         MI->getOperand(NewOp.Operand).setSubReg(0);
00856 
00857         Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg);
00858         UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps);
00859         DOUT << '\t' << *prior(InsertLoc);
00860         
00861         DOUT << "Reuse undone!\n";
00862         --NumReused;
00863         
00864         // Finally, PhysReg is now available, go ahead and use it.
00865         return PhysReg;
00866       }
00867     }
00868   }
00869   return PhysReg;
00870 }
00871 
00872 // ************************************************************************ //
00873 
00874 /// FoldsStackSlotModRef - Return true if the specified MI folds the specified
00875 /// stack slot mod/ref. It also checks if it's possible to unfold the
00876 /// instruction by having it define a specified physical register instead.
00877 static bool FoldsStackSlotModRef(MachineInstr &MI, int SS, unsigned PhysReg,
00878                                  const TargetInstrInfo *TII,
00879                                  const TargetRegisterInfo *TRI,
00880                                  VirtRegMap &VRM) {
00881   if (VRM.hasEmergencySpills(&MI) || VRM.isSpillPt(&MI))
00882     return false;
00883 
00884   bool Found = false;
00885   VirtRegMap::MI2VirtMapTy::const_iterator I, End;
00886   for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
00887     unsigned VirtReg = I->second.first;
00888     VirtRegMap::ModRef MR = I->second.second;
00889     if (MR & VirtRegMap::isModRef)
00890       if (VRM.getStackSlot(VirtReg) == SS) {
00891         Found= TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), true, true) != 0;
00892         break;
00893       }
00894   }
00895   if (!Found)
00896     return false;
00897 
00898   // Does the instruction uses a register that overlaps the scratch register?
00899   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
00900     MachineOperand &MO = MI.getOperand(i);
00901     if (!MO.isReg() || MO.getReg() == 0)
00902       continue;
00903     unsigned Reg = MO.getReg();
00904     if (TargetRegisterInfo::isVirtualRegister(Reg)) {
00905       if (!VRM.hasPhys(Reg))
00906         continue;
00907       Reg = VRM.getPhys(Reg);
00908     }
00909     if (TRI->regsOverlap(PhysReg, Reg))
00910       return false;
00911   }
00912   return true;
00913 }
00914 
00915 /// FindFreeRegister - Find a free register of a given register class by looking
00916 /// at (at most) the last two machine instructions.
00917 static unsigned FindFreeRegister(MachineBasicBlock::iterator MII,
00918                                  MachineBasicBlock &MBB,
00919                                  const TargetRegisterClass *RC,
00920                                  const TargetRegisterInfo *TRI,
00921                                  BitVector &AllocatableRegs) {
00922   BitVector Defs(TRI->getNumRegs());
00923   BitVector Uses(TRI->getNumRegs());
00924   SmallVector<unsigned, 4> LocalUses;
00925   SmallVector<unsigned, 4> Kills;
00926 
00927   // Take a look at 2 instructions at most.
00928   for (unsigned Count = 0; Count < 2; ++Count) {
00929     if (MII == MBB.begin())
00930       break;
00931     MachineInstr *PrevMI = prior(MII);
00932     for (unsigned i = 0, e = PrevMI->getNumOperands(); i != e; ++i) {
00933       MachineOperand &MO = PrevMI->getOperand(i);
00934       if (!MO.isReg() || MO.getReg() == 0)
00935         continue;
00936       unsigned Reg = MO.getReg();
00937       if (MO.isDef()) {
00938         Defs.set(Reg);
00939         for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
00940           Defs.set(*AS);
00941       } else  {
00942         LocalUses.push_back(Reg);
00943         if (MO.isKill() && AllocatableRegs[Reg])
00944           Kills.push_back(Reg);
00945       }
00946     }
00947 
00948     for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
00949       unsigned Kill = Kills[i];
00950       if (!Defs[Kill] && !Uses[Kill] &&
00951           TRI->getPhysicalRegisterRegClass(Kill) == RC)
00952         return Kill;
00953     }
00954     for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
00955       unsigned Reg = LocalUses[i];
00956       Uses.set(Reg);
00957       for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
00958         Uses.set(*AS);
00959     }
00960 
00961     MII = PrevMI;
00962   }
00963 
00964   return 0;
00965 }
00966 
00967 static
00968 void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg) {
00969   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
00970     MachineOperand &MO = MI->getOperand(i);
00971     if (MO.isReg() && MO.getReg() == VirtReg)
00972       MO.setReg(PhysReg);
00973   }
00974 }
00975 
00976 namespace {
00977   struct RefSorter {
00978     bool operator()(const std::pair<MachineInstr*, int> &A,
00979                     const std::pair<MachineInstr*, int> &B) {
00980       return A.second < B.second;
00981     }
00982   };
00983 }
00984 
00985 // ***************************** //
00986 // Local Spiller Implementation  //
00987 // ***************************** //
00988 
00989 namespace {
00990 
00991 class VISIBILITY_HIDDEN LocalRewriter : public VirtRegRewriter {
00992   MachineRegisterInfo *RegInfo;
00993   const TargetRegisterInfo *TRI;
00994   const TargetInstrInfo *TII;
00995   BitVector AllocatableRegs;
00996   DenseMap<MachineInstr*, unsigned> DistanceMap;
00997 public:
00998 
00999   bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
01000                             LiveIntervals* LIs) {
01001     RegInfo = &MF.getRegInfo(); 
01002     TRI = MF.getTarget().getRegisterInfo();
01003     TII = MF.getTarget().getInstrInfo();
01004     AllocatableRegs = TRI->getAllocatableSet(MF);
01005     DEBUG(errs() << "\n**** Local spiller rewriting function '"
01006           << MF.getFunction()->getName() << "':\n");
01007     DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)"
01008             " ****\n";
01009     DEBUG(MF.dump());
01010 
01011     // Spills - Keep track of which spilled values are available in physregs
01012     // so that we can choose to reuse the physregs instead of emitting
01013     // reloads. This is usually refreshed per basic block.
01014     AvailableSpills Spills(TRI, TII);
01015 
01016     // Keep track of kill information.
01017     BitVector RegKills(TRI->getNumRegs());
01018     std::vector<MachineOperand*> KillOps;
01019     KillOps.resize(TRI->getNumRegs(), NULL);
01020 
01021     // SingleEntrySuccs - Successor blocks which have a single predecessor.
01022     SmallVector<MachineBasicBlock*, 4> SinglePredSuccs;
01023     SmallPtrSet<MachineBasicBlock*,16> EarlyVisited;
01024 
01025     // Traverse the basic blocks depth first.
01026     MachineBasicBlock *Entry = MF.begin();
01027     SmallPtrSet<MachineBasicBlock*,16> Visited;
01028     for (df_ext_iterator<MachineBasicBlock*,
01029            SmallPtrSet<MachineBasicBlock*,16> >
01030            DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
01031          DFI != E; ++DFI) {
01032       MachineBasicBlock *MBB = *DFI;
01033       if (!EarlyVisited.count(MBB))
01034         RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
01035 
01036       // If this MBB is the only predecessor of a successor. Keep the
01037       // availability information and visit it next.
01038       do {
01039         // Keep visiting single predecessor successor as long as possible.
01040         SinglePredSuccs.clear();
01041         findSinglePredSuccessor(MBB, SinglePredSuccs);
01042         if (SinglePredSuccs.empty())
01043           MBB = 0;
01044         else {
01045           // FIXME: More than one successors, each of which has MBB has
01046           // the only predecessor.
01047           MBB = SinglePredSuccs[0];
01048           if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
01049             Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
01050             RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
01051           }
01052         }
01053       } while (MBB);
01054 
01055       // Clear the availability info.
01056       Spills.clear();
01057     }
01058 
01059     DOUT << "**** Post Machine Instrs ****\n";
01060     DEBUG(MF.dump());
01061 
01062     // Mark unused spill slots.
01063     MachineFrameInfo *MFI = MF.getFrameInfo();
01064     int SS = VRM.getLowSpillSlot();
01065     if (SS != VirtRegMap::NO_STACK_SLOT)
01066       for (int e = VRM.getHighSpillSlot(); SS <= e; ++SS)
01067         if (!VRM.isSpillSlotUsed(SS)) {
01068           MFI->RemoveStackObject(SS);
01069           ++NumDSS;
01070         }
01071 
01072     return true;
01073   }
01074 
01075 private:
01076 
01077   /// OptimizeByUnfold2 - Unfold a series of load / store folding instructions if
01078   /// a scratch register is available.
01079   ///     xorq  %r12<kill>, %r13
01080   ///     addq  %rax, -184(%rbp)
01081   ///     addq  %r13, -184(%rbp)
01082   /// ==>
01083   ///     xorq  %r12<kill>, %r13
01084   ///     movq  -184(%rbp), %r12
01085   ///     addq  %rax, %r12
01086   ///     addq  %r13, %r12
01087   ///     movq  %r12, -184(%rbp)
01088   bool OptimizeByUnfold2(unsigned VirtReg, int SS,
01089                          MachineBasicBlock &MBB,
01090                          MachineBasicBlock::iterator &MII,
01091                          std::vector<MachineInstr*> &MaybeDeadStores,
01092                          AvailableSpills &Spills,
01093                          BitVector &RegKills,
01094                          std::vector<MachineOperand*> &KillOps,
01095                          VirtRegMap &VRM) {
01096 
01097     MachineBasicBlock::iterator NextMII = next(MII);
01098     if (NextMII == MBB.end())
01099       return false;
01100 
01101     if (TII->getOpcodeAfterMemoryUnfold(MII->getOpcode(), true, true) == 0)
01102       return false;
01103 
01104     // Now let's see if the last couple of instructions happens to have freed up
01105     // a register.
01106     const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01107     unsigned PhysReg = FindFreeRegister(MII, MBB, RC, TRI, AllocatableRegs);
01108     if (!PhysReg)
01109       return false;
01110 
01111     MachineFunction &MF = *MBB.getParent();
01112     TRI = MF.getTarget().getRegisterInfo();
01113     MachineInstr &MI = *MII;
01114     if (!FoldsStackSlotModRef(MI, SS, PhysReg, TII, TRI, VRM))
01115       return false;
01116 
01117     // If the next instruction also folds the same SS modref and can be unfoled,
01118     // then it's worthwhile to issue a load from SS into the free register and
01119     // then unfold these instructions.
01120     if (!FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM))
01121       return false;
01122 
01123     // Back-schedule reloads and remats.
01124     MachineBasicBlock::iterator InsertLoc =
01125       ComputeReloadLoc(MII, MBB.begin(), PhysReg, TRI, false, SS, TII, MF);
01126 
01127     // Load from SS to the spare physical register.
01128     TII->loadRegFromStackSlot(MBB, MII, PhysReg, SS, RC);
01129     // This invalidates Phys.
01130     Spills.ClobberPhysReg(PhysReg);
01131     // Remember it's available.
01132     Spills.addAvailable(SS, PhysReg);
01133     MaybeDeadStores[SS] = NULL;
01134 
01135     // Unfold current MI.
01136     SmallVector<MachineInstr*, 4> NewMIs;
01137     if (!TII->unfoldMemoryOperand(MF, &MI, VirtReg, false, false, NewMIs))
01138       llvm_unreachable("Unable unfold the load / store folding instruction!");
01139     assert(NewMIs.size() == 1);
01140     AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
01141     VRM.transferRestorePts(&MI, NewMIs[0]);
01142     MII = MBB.insert(MII, NewMIs[0]);
01143     InvalidateKills(MI, TRI, RegKills, KillOps);
01144     VRM.RemoveMachineInstrFromMaps(&MI);
01145     MBB.erase(&MI);
01146     ++NumModRefUnfold;
01147 
01148     // Unfold next instructions that fold the same SS.
01149     do {
01150       MachineInstr &NextMI = *NextMII;
01151       NextMII = next(NextMII);
01152       NewMIs.clear();
01153       if (!TII->unfoldMemoryOperand(MF, &NextMI, VirtReg, false, false, NewMIs))
01154         llvm_unreachable("Unable unfold the load / store folding instruction!");
01155       assert(NewMIs.size() == 1);
01156       AssignPhysToVirtReg(NewMIs[0], VirtReg, PhysReg);
01157       VRM.transferRestorePts(&NextMI, NewMIs[0]);
01158       MBB.insert(NextMII, NewMIs[0]);
01159       InvalidateKills(NextMI, TRI, RegKills, KillOps);
01160       VRM.RemoveMachineInstrFromMaps(&NextMI);
01161       MBB.erase(&NextMI);
01162       ++NumModRefUnfold;
01163       if (NextMII == MBB.end())
01164         break;
01165     } while (FoldsStackSlotModRef(*NextMII, SS, PhysReg, TII, TRI, VRM));
01166 
01167     // Store the value back into SS.
01168     TII->storeRegToStackSlot(MBB, NextMII, PhysReg, true, SS, RC);
01169     MachineInstr *StoreMI = prior(NextMII);
01170     VRM.addSpillSlotUse(SS, StoreMI);
01171     VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
01172 
01173     return true;
01174   }
01175 
01176   /// OptimizeByUnfold - Turn a store folding instruction into a load folding
01177   /// instruction. e.g.
01178   ///     xorl  %edi, %eax
01179   ///     movl  %eax, -32(%ebp)
01180   ///     movl  -36(%ebp), %eax
01181   ///     orl   %eax, -32(%ebp)
01182   /// ==>
01183   ///     xorl  %edi, %eax
01184   ///     orl   -36(%ebp), %eax
01185   ///     mov   %eax, -32(%ebp)
01186   /// This enables unfolding optimization for a subsequent instruction which will
01187   /// also eliminate the newly introduced store instruction.
01188   bool OptimizeByUnfold(MachineBasicBlock &MBB,
01189                         MachineBasicBlock::iterator &MII,
01190                         std::vector<MachineInstr*> &MaybeDeadStores,
01191                         AvailableSpills &Spills,
01192                         BitVector &RegKills,
01193                         std::vector<MachineOperand*> &KillOps,
01194                         VirtRegMap &VRM) {
01195     MachineFunction &MF = *MBB.getParent();
01196     MachineInstr &MI = *MII;
01197     unsigned UnfoldedOpc = 0;
01198     unsigned UnfoldPR = 0;
01199     unsigned UnfoldVR = 0;
01200     int FoldedSS = VirtRegMap::NO_STACK_SLOT;
01201     VirtRegMap::MI2VirtMapTy::const_iterator I, End;
01202     for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
01203       // Only transform a MI that folds a single register.
01204       if (UnfoldedOpc)
01205         return false;
01206       UnfoldVR = I->second.first;
01207       VirtRegMap::ModRef MR = I->second.second;
01208       // MI2VirtMap be can updated which invalidate the iterator.
01209       // Increment the iterator first.
01210       ++I; 
01211       if (VRM.isAssignedReg(UnfoldVR))
01212         continue;
01213       // If this reference is not a use, any previous store is now dead.
01214       // Otherwise, the store to this stack slot is not dead anymore.
01215       FoldedSS = VRM.getStackSlot(UnfoldVR);
01216       MachineInstr* DeadStore = MaybeDeadStores[FoldedSS];
01217       if (DeadStore && (MR & VirtRegMap::isModRef)) {
01218         unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS);
01219         if (!PhysReg || !DeadStore->readsRegister(PhysReg))
01220           continue;
01221         UnfoldPR = PhysReg;
01222         UnfoldedOpc = TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(),
01223                                                       false, true);
01224       }
01225     }
01226 
01227     if (!UnfoldedOpc) {
01228       if (!UnfoldVR)
01229         return false;
01230 
01231       // Look for other unfolding opportunities.
01232       return OptimizeByUnfold2(UnfoldVR, FoldedSS, MBB, MII,
01233                                MaybeDeadStores, Spills, RegKills, KillOps, VRM);
01234     }
01235 
01236     for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
01237       MachineOperand &MO = MI.getOperand(i);
01238       if (!MO.isReg() || MO.getReg() == 0 || !MO.isUse())
01239         continue;
01240       unsigned VirtReg = MO.getReg();
01241       if (TargetRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg())
01242         continue;
01243       if (VRM.isAssignedReg(VirtReg)) {
01244         unsigned PhysReg = VRM.getPhys(VirtReg);
01245         if (PhysReg && TRI->regsOverlap(PhysReg, UnfoldPR))
01246           return false;
01247       } else if (VRM.isReMaterialized(VirtReg))
01248         continue;
01249       int SS = VRM.getStackSlot(VirtReg);
01250       unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
01251       if (PhysReg) {
01252         if (TRI->regsOverlap(PhysReg, UnfoldPR))
01253           return false;
01254         continue;
01255       }
01256       if (VRM.hasPhys(VirtReg)) {
01257         PhysReg = VRM.getPhys(VirtReg);
01258         if (!TRI->regsOverlap(PhysReg, UnfoldPR))
01259           continue;
01260       }
01261 
01262       // Ok, we'll need to reload the value into a register which makes
01263       // it impossible to perform the store unfolding optimization later.
01264       // Let's see if it is possible to fold the load if the store is
01265       // unfolded. This allows us to perform the store unfolding
01266       // optimization.
01267       SmallVector<MachineInstr*, 4> NewMIs;
01268       if (TII->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) {
01269         assert(NewMIs.size() == 1);
01270         MachineInstr *NewMI = NewMIs.back();
01271         NewMIs.clear();
01272         int Idx = NewMI->findRegisterUseOperandIdx(VirtReg, false);
01273         assert(Idx != -1);
01274         SmallVector<unsigned, 1> Ops;
01275         Ops.push_back(Idx);
01276         MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, NewMI, Ops, SS);
01277         if (FoldedMI) {
01278           VRM.addSpillSlotUse(SS, FoldedMI);
01279           if (!VRM.hasPhys(UnfoldVR))
01280             VRM.assignVirt2Phys(UnfoldVR, UnfoldPR);
01281           VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
01282           MII = MBB.insert(MII, FoldedMI);
01283           InvalidateKills(MI, TRI, RegKills, KillOps);
01284           VRM.RemoveMachineInstrFromMaps(&MI);
01285           MBB.erase(&MI);
01286           MF.DeleteMachineInstr(NewMI);
01287           return true;
01288         }
01289         MF.DeleteMachineInstr(NewMI);
01290       }
01291     }
01292 
01293     return false;
01294   }
01295 
01296   /// CommuteChangesDestination - We are looking for r0 = op r1, r2 and
01297   /// where SrcReg is r1 and it is tied to r0. Return true if after
01298   /// commuting this instruction it will be r0 = op r2, r1.
01299   static bool CommuteChangesDestination(MachineInstr *DefMI,
01300                                         const TargetInstrDesc &TID,
01301                                         unsigned SrcReg,
01302                                         const TargetInstrInfo *TII,
01303                                         unsigned &DstIdx) {
01304     if (TID.getNumDefs() != 1 && TID.getNumOperands() != 3)
01305       return false;
01306     if (!DefMI->getOperand(1).isReg() ||
01307         DefMI->getOperand(1).getReg() != SrcReg)
01308       return false;
01309     unsigned DefIdx;
01310     if (!DefMI->isRegTiedToDefOperand(1, &DefIdx) || DefIdx != 0)
01311       return false;
01312     unsigned SrcIdx1, SrcIdx2;
01313     if (!TII->findCommutedOpIndices(DefMI, SrcIdx1, SrcIdx2))
01314       return false;
01315     if (SrcIdx1 == 1 && SrcIdx2 == 2) {
01316       DstIdx = 2;
01317       return true;
01318     }
01319     return false;
01320   }
01321 
01322   /// CommuteToFoldReload -
01323   /// Look for
01324   /// r1 = load fi#1
01325   /// r1 = op r1, r2<kill>
01326   /// store r1, fi#1
01327   ///
01328   /// If op is commutable and r2 is killed, then we can xform these to
01329   /// r2 = op r2, fi#1
01330   /// store r2, fi#1
01331   bool CommuteToFoldReload(MachineBasicBlock &MBB,
01332                            MachineBasicBlock::iterator &MII,
01333                            unsigned VirtReg, unsigned SrcReg, int SS,
01334                            AvailableSpills &Spills,
01335                            BitVector &RegKills,
01336                            std::vector<MachineOperand*> &KillOps,
01337                            const TargetRegisterInfo *TRI,
01338                            VirtRegMap &VRM) {
01339     if (MII == MBB.begin() || !MII->killsRegister(SrcReg))
01340       return false;
01341 
01342     MachineFunction &MF = *MBB.getParent();
01343     MachineInstr &MI = *MII;
01344     MachineBasicBlock::iterator DefMII = prior(MII);
01345     MachineInstr *DefMI = DefMII;
01346     const TargetInstrDesc &TID = DefMI->getDesc();
01347     unsigned NewDstIdx;
01348     if (DefMII != MBB.begin() &&
01349         TID.isCommutable() &&
01350         CommuteChangesDestination(DefMI, TID, SrcReg, TII, NewDstIdx)) {
01351       MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
01352       unsigned NewReg = NewDstMO.getReg();
01353       if (!NewDstMO.isKill() || TRI->regsOverlap(NewReg, SrcReg))
01354         return false;
01355       MachineInstr *ReloadMI = prior(DefMII);
01356       int FrameIdx;
01357       unsigned DestReg = TII->isLoadFromStackSlot(ReloadMI, FrameIdx);
01358       if (DestReg != SrcReg || FrameIdx != SS)
01359         return false;
01360       int UseIdx = DefMI->findRegisterUseOperandIdx(DestReg, false);
01361       if (UseIdx == -1)
01362         return false;
01363       unsigned DefIdx;
01364       if (!MI.isRegTiedToDefOperand(UseIdx, &DefIdx))
01365         return false;
01366       assert(DefMI->getOperand(DefIdx).isReg() &&
01367              DefMI->getOperand(DefIdx).getReg() == SrcReg);
01368 
01369       // Now commute def instruction.
01370       MachineInstr *CommutedMI = TII->commuteInstruction(DefMI, true);
01371       if (!CommutedMI)
01372         return false;
01373       SmallVector<unsigned, 1> Ops;
01374       Ops.push_back(NewDstIdx);
01375       MachineInstr *FoldedMI = TII->foldMemoryOperand(MF, CommutedMI, Ops, SS);
01376       // Not needed since foldMemoryOperand returns new MI.
01377       MF.DeleteMachineInstr(CommutedMI);
01378       if (!FoldedMI)
01379         return false;
01380 
01381       VRM.addSpillSlotUse(SS, FoldedMI);
01382       VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef);
01383       // Insert new def MI and spill MI.
01384       const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01385       TII->storeRegToStackSlot(MBB, &MI, NewReg, true, SS, RC);
01386       MII = prior(MII);
01387       MachineInstr *StoreMI = MII;
01388       VRM.addSpillSlotUse(SS, StoreMI);
01389       VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
01390       MII = MBB.insert(MII, FoldedMI);  // Update MII to backtrack.
01391 
01392       // Delete all 3 old instructions.
01393       InvalidateKills(*ReloadMI, TRI, RegKills, KillOps);
01394       VRM.RemoveMachineInstrFromMaps(ReloadMI);
01395       MBB.erase(ReloadMI);
01396       InvalidateKills(*DefMI, TRI, RegKills, KillOps);
01397       VRM.RemoveMachineInstrFromMaps(DefMI);
01398       MBB.erase(DefMI);
01399       InvalidateKills(MI, TRI, RegKills, KillOps);
01400       VRM.RemoveMachineInstrFromMaps(&MI);
01401       MBB.erase(&MI);
01402 
01403       // If NewReg was previously holding value of some SS, it's now clobbered.
01404       // This has to be done now because it's a physical register. When this
01405       // instruction is re-visited, it's ignored.
01406       Spills.ClobberPhysReg(NewReg);
01407 
01408       ++NumCommutes;
01409       return true;
01410     }
01411 
01412     return false;
01413   }
01414 
01415   /// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if
01416   /// the last store to the same slot is now dead. If so, remove the last store.
01417   void SpillRegToStackSlot(MachineBasicBlock &MBB,
01418                            MachineBasicBlock::iterator &MII,
01419                            int Idx, unsigned PhysReg, int StackSlot,
01420                            const TargetRegisterClass *RC,
01421                            bool isAvailable, MachineInstr *&LastStore,
01422                            AvailableSpills &Spills,
01423                            SmallSet<MachineInstr*, 4> &ReMatDefs,
01424                            BitVector &RegKills,
01425                            std::vector<MachineOperand*> &KillOps,
01426                            VirtRegMap &VRM) {
01427 
01428     TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC);
01429     MachineInstr *StoreMI = next(MII);
01430     VRM.addSpillSlotUse(StackSlot, StoreMI);
01431     DOUT << "Store:\t" << *StoreMI;
01432 
01433     // If there is a dead store to this stack slot, nuke it now.
01434     if (LastStore) {
01435       DOUT << "Removed dead store:\t" << *LastStore;
01436       ++NumDSE;
01437       SmallVector<unsigned, 2> KillRegs;
01438       InvalidateKills(*LastStore, TRI, RegKills, KillOps, &KillRegs);
01439       MachineBasicBlock::iterator PrevMII = LastStore;
01440       bool CheckDef = PrevMII != MBB.begin();
01441       if (CheckDef)
01442         --PrevMII;
01443       VRM.RemoveMachineInstrFromMaps(LastStore);
01444       MBB.erase(LastStore);
01445       if (CheckDef) {
01446         // Look at defs of killed registers on the store. Mark the defs
01447         // as dead since the store has been deleted and they aren't
01448         // being reused.
01449         for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) {
01450           bool HasOtherDef = false;
01451           if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) {
01452             MachineInstr *DeadDef = PrevMII;
01453             if (ReMatDefs.count(DeadDef) && !HasOtherDef) {
01454               // FIXME: This assumes a remat def does not have side effects.
01455               VRM.RemoveMachineInstrFromMaps(DeadDef);
01456               MBB.erase(DeadDef);
01457               ++NumDRM;
01458             }
01459           }
01460         }
01461       }
01462     }
01463 
01464     LastStore = next(MII);
01465 
01466     // If the stack slot value was previously available in some other
01467     // register, change it now.  Otherwise, make the register available,
01468     // in PhysReg.
01469     Spills.ModifyStackSlotOrReMat(StackSlot);
01470     Spills.ClobberPhysReg(PhysReg);
01471     Spills.addAvailable(StackSlot, PhysReg, isAvailable);
01472     ++NumStores;
01473   }
01474 
01475   /// TransferDeadness - A identity copy definition is dead and it's being
01476   /// removed. Find the last def or use and mark it as dead / kill.
01477   void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
01478                         unsigned Reg, BitVector &RegKills,
01479                         std::vector<MachineOperand*> &KillOps,
01480                         VirtRegMap &VRM) {
01481     SmallPtrSet<MachineInstr*, 4> Seens;
01482     SmallVector<std::pair<MachineInstr*, int>,8> Refs;
01483     for (MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(Reg),
01484            RE = RegInfo->reg_end(); RI != RE; ++RI) {
01485       MachineInstr *UDMI = &*RI;
01486       if (UDMI->getParent() != MBB)
01487         continue;
01488       DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
01489       if (DI == DistanceMap.end() || DI->second > CurDist)
01490         continue;
01491       if (Seens.insert(UDMI))
01492         Refs.push_back(std::make_pair(UDMI, DI->second));
01493     }
01494 
01495     if (Refs.empty())
01496       return;
01497     std::sort(Refs.begin(), Refs.end(), RefSorter());
01498 
01499     while (!Refs.empty()) {
01500       MachineInstr *LastUDMI = Refs.back().first;
01501       Refs.pop_back();
01502 
01503       MachineOperand *LastUD = NULL;
01504       for (unsigned i = 0, e = LastUDMI->getNumOperands(); i != e; ++i) {
01505         MachineOperand &MO = LastUDMI->getOperand(i);
01506         if (!MO.isReg() || MO.getReg() != Reg)
01507           continue;
01508         if (!LastUD || (LastUD->isUse() && MO.isDef()))
01509           LastUD = &MO;
01510         if (LastUDMI->isRegTiedToDefOperand(i))
01511           break;
01512       }
01513       if (LastUD->isDef()) {
01514         // If the instruction has no side effect, delete it and propagate
01515         // backward further. Otherwise, mark is dead and we are done.
01516         if (!TII->isDeadInstruction(LastUDMI)) {
01517           LastUD->setIsDead();
01518           break;
01519         }
01520         VRM.RemoveMachineInstrFromMaps(LastUDMI);
01521         MBB->erase(LastUDMI);
01522       } else {
01523         LastUD->setIsKill();
01524         RegKills.set(Reg);
01525         KillOps[Reg] = LastUD;
01526         break;
01527       }
01528     }
01529   }
01530 
01531   /// rewriteMBB - Keep track of which spills are available even after the
01532   /// register allocator is done with them.  If possible, avid reloading vregs.
01533   void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
01534                   LiveIntervals *LIs,
01535                   AvailableSpills &Spills, BitVector &RegKills,
01536                   std::vector<MachineOperand*> &KillOps) {
01537 
01538     DEBUG(errs() << "\n**** Local spiller rewriting MBB '"
01539           << MBB.getBasicBlock()->getName() << "':\n");
01540 
01541     MachineFunction &MF = *MBB.getParent();
01542     
01543     // MaybeDeadStores - When we need to write a value back into a stack slot,
01544     // keep track of the inserted store.  If the stack slot value is never read
01545     // (because the value was used from some available register, for example), and
01546     // subsequently stored to, the original store is dead.  This map keeps track
01547     // of inserted stores that are not used.  If we see a subsequent store to the
01548     // same stack slot, the original store is deleted.
01549     std::vector<MachineInstr*> MaybeDeadStores;
01550     MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL);
01551 
01552     // ReMatDefs - These are rematerializable def MIs which are not deleted.
01553     SmallSet<MachineInstr*, 4> ReMatDefs;
01554 
01555     // Clear kill info.
01556     SmallSet<unsigned, 2> KilledMIRegs;
01557     RegKills.reset();
01558     KillOps.clear();
01559     KillOps.resize(TRI->getNumRegs(), NULL);
01560 
01561     unsigned Dist = 0;
01562     DistanceMap.clear();
01563     for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
01564          MII != E; ) {
01565       MachineBasicBlock::iterator NextMII = next(MII);
01566 
01567       VirtRegMap::MI2VirtMapTy::const_iterator I, End;
01568       bool Erased = false;
01569       bool BackTracked = false;
01570       if (OptimizeByUnfold(MBB, MII,
01571                            MaybeDeadStores, Spills, RegKills, KillOps, VRM))
01572         NextMII = next(MII);
01573 
01574       MachineInstr &MI = *MII;
01575 
01576       if (VRM.hasEmergencySpills(&MI)) {
01577         // Spill physical register(s) in the rare case the allocator has run out
01578         // of registers to allocate.
01579         SmallSet<int, 4> UsedSS;
01580         std::vector<unsigned> &EmSpills = VRM.getEmergencySpills(&MI);
01581         for (unsigned i = 0, e = EmSpills.size(); i != e; ++i) {
01582           unsigned PhysReg = EmSpills[i];
01583           const TargetRegisterClass *RC =
01584             TRI->getPhysicalRegisterRegClass(PhysReg);
01585           assert(RC && "Unable to determine register class!");
01586           int SS = VRM.getEmergencySpillSlot(RC);
01587           if (UsedSS.count(SS))
01588             llvm_unreachable("Need to spill more than one physical registers!");
01589           UsedSS.insert(SS);
01590           TII->storeRegToStackSlot(MBB, MII, PhysReg, true, SS, RC);
01591           MachineInstr *StoreMI = prior(MII);
01592           VRM.addSpillSlotUse(SS, StoreMI);
01593 
01594           // Back-schedule reloads and remats.
01595           MachineBasicBlock::iterator InsertLoc =
01596             ComputeReloadLoc(next(MII), MBB.begin(), PhysReg, TRI, false,
01597                              SS, TII, MF);
01598 
01599           TII->loadRegFromStackSlot(MBB, InsertLoc, PhysReg, SS, RC);
01600 
01601           MachineInstr *LoadMI = prior(InsertLoc);
01602           VRM.addSpillSlotUse(SS, LoadMI);
01603           ++NumPSpills;
01604           DistanceMap.insert(std::make_pair(LoadMI, Dist++));
01605         }
01606         NextMII = next(MII);
01607       }
01608 
01609       // Insert restores here if asked to.
01610       if (VRM.isRestorePt(&MI)) {
01611         std::vector<unsigned> &RestoreRegs = VRM.getRestorePtRestores(&MI);
01612         for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) {
01613           unsigned VirtReg = RestoreRegs[e-i-1];  // Reverse order.
01614           if (!VRM.getPreSplitReg(VirtReg))
01615             continue; // Split interval spilled again.
01616           unsigned Phys = VRM.getPhys(VirtReg);
01617           RegInfo->setPhysRegUsed(Phys);
01618 
01619           // Check if the value being restored if available. If so, it must be
01620           // from a predecessor BB that fallthrough into this BB. We do not
01621           // expect:
01622           // BB1:
01623           // r1 = load fi#1
01624           // ...
01625           //    = r1<kill>
01626           // ... # r1 not clobbered
01627           // ...
01628           //    = load fi#1
01629           bool DoReMat = VRM.isReMaterialized(VirtReg);
01630           int SSorRMId = DoReMat
01631             ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
01632           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01633           unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
01634           if (InReg == Phys) {
01635             // If the value is already available in the expected register, save
01636             // a reload / remat.
01637             if (SSorRMId)
01638               DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
01639             else
01640               DOUT << "Reusing SS#" << SSorRMId;
01641             DOUT << " from physreg "
01642                  << TRI->getName(InReg) << " for vreg"
01643                  << VirtReg <<" instead of reloading into physreg "
01644                  << TRI->getName(Phys) << "\n";
01645             ++NumOmitted;
01646             continue;
01647           } else if (InReg && InReg != Phys) {
01648             if (SSorRMId)
01649               DOUT << "Reusing RM#" << SSorRMId-VirtRegMap::MAX_STACK_SLOT-1;
01650             else
01651               DOUT << "Reusing SS#" << SSorRMId;
01652             DOUT << " from physreg "
01653                  << TRI->getName(InReg) << " for vreg"
01654                  << VirtReg <<" by copying it into physreg "
01655                  << TRI->getName(Phys) << "\n";
01656 
01657             // If the reloaded / remat value is available in another register,
01658             // copy it to the desired register.
01659 
01660             // Back-schedule reloads and remats.
01661             MachineBasicBlock::iterator InsertLoc =
01662               ComputeReloadLoc(MII, MBB.begin(), Phys, TRI, DoReMat,
01663                                SSorRMId, TII, MF);
01664 
01665             TII->copyRegToReg(MBB, InsertLoc, Phys, InReg, RC, RC);
01666 
01667             // This invalidates Phys.
01668             Spills.ClobberPhysReg(Phys);
01669             // Remember it's available.
01670             Spills.addAvailable(SSorRMId, Phys);
01671 
01672             // Mark is killed.
01673             MachineInstr *CopyMI = prior(InsertLoc);
01674             MachineOperand *KillOpnd = CopyMI->findRegisterUseOperand(InReg);
01675             KillOpnd->setIsKill();
01676             UpdateKills(*CopyMI, TRI, RegKills, KillOps);
01677 
01678             DOUT << '\t' << *CopyMI;
01679             ++NumCopified;
01680             continue;
01681           }
01682 
01683           // Back-schedule reloads and remats.
01684           MachineBasicBlock::iterator InsertLoc =
01685             ComputeReloadLoc(MII, MBB.begin(), Phys, TRI, DoReMat,
01686                              SSorRMId, TII, MF);
01687 
01688           if (VRM.isReMaterialized(VirtReg)) {
01689             ReMaterialize(MBB, InsertLoc, Phys, VirtReg, TII, TRI, VRM);
01690           } else {
01691             const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01692             TII->loadRegFromStackSlot(MBB, InsertLoc, Phys, SSorRMId, RC);
01693             MachineInstr *LoadMI = prior(InsertLoc);
01694             VRM.addSpillSlotUse(SSorRMId, LoadMI);
01695             ++NumLoads;
01696             DistanceMap.insert(std::make_pair(LoadMI, Dist++));
01697           }
01698 
01699           // This invalidates Phys.
01700           Spills.ClobberPhysReg(Phys);
01701           // Remember it's available.
01702           Spills.addAvailable(SSorRMId, Phys);
01703 
01704           UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps);
01705           DOUT << '\t' << *prior(MII);
01706         }
01707       }
01708 
01709       // Insert spills here if asked to.
01710       if (VRM.isSpillPt(&MI)) {
01711         std::vector<std::pair<unsigned,bool> > &SpillRegs =
01712           VRM.getSpillPtSpills(&MI);
01713         for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) {
01714           unsigned VirtReg = SpillRegs[i].first;
01715           bool isKill = SpillRegs[i].second;
01716           if (!VRM.getPreSplitReg(VirtReg))
01717             continue; // Split interval spilled again.
01718           const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
01719           unsigned Phys = VRM.getPhys(VirtReg);
01720           int StackSlot = VRM.getStackSlot(VirtReg);
01721           TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC);
01722           MachineInstr *StoreMI = next(MII);
01723           VRM.addSpillSlotUse(StackSlot, StoreMI);
01724           DOUT << "Store:\t" << *StoreMI;
01725           VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod);
01726         }
01727         NextMII = next(MII);
01728       }
01729 
01730       /// ReusedOperands - Keep track of operand reuse in case we need to undo
01731       /// reuse.
01732       ReuseInfo ReusedOperands(MI, TRI);
01733       SmallVector<unsigned, 4> VirtUseOps;
01734       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
01735         MachineOperand &MO = MI.getOperand(i);
01736         if (!MO.isReg() || MO.getReg() == 0)
01737           continue;   // Ignore non-register operands.
01738         
01739         unsigned VirtReg = MO.getReg();
01740         if (TargetRegisterInfo::isPhysicalRegister(VirtReg)) {
01741           // Ignore physregs for spilling, but remember that it is used by this
01742           // function.
01743           RegInfo->setPhysRegUsed(VirtReg);
01744           continue;
01745         }
01746 
01747         // We want to process implicit virtual register uses first.
01748         if (MO.isImplicit())
01749           // If the virtual register is implicitly defined, emit a implicit_def
01750           // before so scavenger knows it's "defined".
01751           // FIXME: This is a horrible hack done the by register allocator to
01752           // remat a definition with virtual register operand.
01753           VirtUseOps.insert(VirtUseOps.begin(), i);
01754         else
01755           VirtUseOps.push_back(i);
01756       }
01757 
01758       // Process all of the spilled uses and all non spilled reg references.
01759       SmallVector<int, 2> PotentialDeadStoreSlots;
01760       KilledMIRegs.clear();
01761       for (unsigned j = 0, e = VirtUseOps.size(); j != e; ++j) {
01762         unsigned i = VirtUseOps[j];
01763         MachineOperand &MO = MI.getOperand(i);
01764         unsigned VirtReg = MO.getReg();
01765         assert(TargetRegisterInfo::isVirtualRegister(VirtReg) &&
01766                "Not a virtual register?");
01767 
01768         unsigned SubIdx = MO.getSubReg();
01769         if (VRM.isAssignedReg(VirtReg)) {
01770           // This virtual register was assigned a physreg!
01771           unsigned Phys = VRM.getPhys(VirtReg);
01772           RegInfo->setPhysRegUsed(Phys);
01773           if (MO.isDef())
01774             ReusedOperands.markClobbered(Phys);
01775           unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
01776           MI.getOperand(i).setReg(RReg);
01777           MI.getOperand(i).setSubReg(0);
01778           if (VRM.isImplicitlyDefined(VirtReg))
01779             // FIXME: Is this needed?
01780             BuildMI(MBB, &MI, MI.getDebugLoc(),
01781                     TII->get(TargetInstrInfo::IMPLICIT_DEF), RReg);
01782           continue;
01783         }
01784         
01785         // This virtual register is now known to be a spilled value.
01786         if (!MO.isUse())
01787           continue;  // Handle defs in the loop below (handle use&def here though)
01788 
01789         bool AvoidReload = MO.isUndef();
01790         // Check if it is defined by an implicit def. It should not be spilled.
01791         // Note, this is for correctness reason. e.g.
01792         // 8   %reg1024<def> = IMPLICIT_DEF
01793         // 12  %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
01794         // The live range [12, 14) are not part of the r1024 live interval since
01795         // it's defined by an implicit def. It will not conflicts with live
01796         // interval of r1025. Now suppose both registers are spilled, you can
01797         // easily see a situation where both registers are reloaded before
01798         // the INSERT_SUBREG and both target registers that would overlap.
01799         bool DoReMat = VRM.isReMaterialized(VirtReg);
01800         int SSorRMId = DoReMat
01801           ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg);
01802         int ReuseSlot = SSorRMId;
01803 
01804         // Check to see if this stack slot is available.
01805         unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId);
01806 
01807         // If this is a sub-register use, make sure the reuse register is in the
01808         // right register class. For example, for x86 not all of the 32-bit
01809         // registers have accessible sub-registers.
01810         // Similarly so for EXTRACT_SUBREG. Consider this:
01811         // EDI = op
01812         // MOV32_mr fi#1, EDI
01813         // ...
01814         //       = EXTRACT_SUBREG fi#1
01815         // fi#1 is available in EDI, but it cannot be reused because it's not in
01816         // the right register file.
01817         if (PhysReg && !AvoidReload &&
01818             (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) {
01819           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01820           if (!RC->contains(PhysReg))
01821             PhysReg = 0;
01822         }
01823 
01824         if (PhysReg && !AvoidReload) {
01825           // This spilled operand might be part of a two-address operand.  If this
01826           // is the case, then changing it will necessarily require changing the 
01827           // def part of the instruction as well.  However, in some cases, we
01828           // aren't allowed to modify the reused register.  If none of these cases
01829           // apply, reuse it.
01830           bool CanReuse = true;
01831           bool isTied = MI.isRegTiedToDefOperand(i);
01832           if (isTied) {
01833             // Okay, we have a two address operand.  We can reuse this physreg as
01834             // long as we are allowed to clobber the value and there isn't an
01835             // earlier def that has already clobbered the physreg.
01836             CanReuse = !ReusedOperands.isClobbered(PhysReg) &&
01837               Spills.canClobberPhysReg(PhysReg);
01838           }
01839           
01840           if (CanReuse) {
01841             // If this stack slot value is already available, reuse it!
01842             if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
01843               DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
01844             else
01845               DOUT << "Reusing SS#" << ReuseSlot;
01846             DOUT << " from physreg "
01847                  << TRI->getName(PhysReg) << " for vreg"
01848                  << VirtReg <<" instead of reloading into physreg "
01849                  << TRI->getName(VRM.getPhys(VirtReg)) << "\n";
01850             unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
01851             MI.getOperand(i).setReg(RReg);
01852             MI.getOperand(i).setSubReg(0);
01853 
01854             // The only technical detail we have is that we don't know that
01855             // PhysReg won't be clobbered by a reloaded stack slot that occurs
01856             // later in the instruction.  In particular, consider 'op V1, V2'.
01857             // If V1 is available in physreg R0, we would choose to reuse it
01858             // here, instead of reloading it into the register the allocator
01859             // indicated (say R1).  However, V2 might have to be reloaded
01860             // later, and it might indicate that it needs to live in R0.  When
01861             // this occurs, we need to have information available that
01862             // indicates it is safe to use R1 for the reload instead of R0.
01863             //
01864             // To further complicate matters, we might conflict with an alias,
01865             // or R0 and R1 might not be compatible with each other.  In this
01866             // case, we actually insert a reload for V1 in R1, ensuring that
01867             // we can get at R0 or its alias.
01868             ReusedOperands.addReuse(i, ReuseSlot, PhysReg,
01869                                     VRM.getPhys(VirtReg), VirtReg);
01870             if (isTied)
01871               // Only mark it clobbered if this is a use&def operand.
01872               ReusedOperands.markClobbered(PhysReg);
01873             ++NumReused;
01874 
01875             if (MI.getOperand(i).isKill() &&
01876                 ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) {
01877 
01878               // The store of this spilled value is potentially dead, but we
01879               // won't know for certain until we've confirmed that the re-use
01880               // above is valid, which means waiting until the other operands
01881               // are processed. For now we just track the spill slot, we'll
01882               // remove it after the other operands are processed if valid.
01883 
01884               PotentialDeadStoreSlots.push_back(ReuseSlot);
01885             }
01886 
01887             // Mark is isKill if it's there no other uses of the same virtual
01888             // register and it's not a two-address operand. IsKill will be
01889             // unset if reg is reused.
01890             if (!isTied && KilledMIRegs.count(VirtReg) == 0) {
01891               MI.getOperand(i).setIsKill();
01892               KilledMIRegs.insert(VirtReg);
01893             }
01894 
01895             continue;
01896           }  // CanReuse
01897           
01898           // Otherwise we have a situation where we have a two-address instruction
01899           // whose mod/ref operand needs to be reloaded.  This reload is already
01900           // available in some register "PhysReg", but if we used PhysReg as the
01901           // operand to our 2-addr instruction, the instruction would modify
01902           // PhysReg.  This isn't cool if something later uses PhysReg and expects
01903           // to get its initial value.
01904           //
01905           // To avoid this problem, and to avoid doing a load right after a store,
01906           // we emit a copy from PhysReg into the designated register for this
01907           // operand.
01908           unsigned DesignatedReg = VRM.getPhys(VirtReg);
01909           assert(DesignatedReg && "Must map virtreg to physreg!");
01910 
01911           // Note that, if we reused a register for a previous operand, the
01912           // register we want to reload into might not actually be
01913           // available.  If this occurs, use the register indicated by the
01914           // reuser.
01915           if (ReusedOperands.hasReuses())
01916             DesignatedReg = ReusedOperands.GetRegForReload(VirtReg,
01917                                                            DesignatedReg, &MI, 
01918                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
01919           
01920           // If the mapped designated register is actually the physreg we have
01921           // incoming, we don't need to inserted a dead copy.
01922           if (DesignatedReg == PhysReg) {
01923             // If this stack slot value is already available, reuse it!
01924             if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT)
01925               DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1;
01926             else
01927               DOUT << "Reusing SS#" << ReuseSlot;
01928             DOUT << " from physreg " << TRI->getName(PhysReg)
01929                  << " for vreg" << VirtReg
01930                  << " instead of reloading into same physreg.\n";
01931             unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
01932             MI.getOperand(i).setReg(RReg);
01933             MI.getOperand(i).setSubReg(0);
01934             ReusedOperands.markClobbered(RReg);
01935             ++NumReused;
01936             continue;
01937           }
01938           
01939           const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01940           RegInfo->setPhysRegUsed(DesignatedReg);
01941           ReusedOperands.markClobbered(DesignatedReg);
01942 
01943           // Back-schedule reloads and remats.
01944           MachineBasicBlock::iterator InsertLoc =
01945             ComputeReloadLoc(&MI, MBB.begin(), PhysReg, TRI, DoReMat,
01946                              SSorRMId, TII, MF);
01947 
01948           TII->copyRegToReg(MBB, InsertLoc, DesignatedReg, PhysReg, RC, RC);
01949 
01950           MachineInstr *CopyMI = prior(InsertLoc);
01951           UpdateKills(*CopyMI, TRI, RegKills, KillOps);
01952 
01953           // This invalidates DesignatedReg.
01954           Spills.ClobberPhysReg(DesignatedReg);
01955           
01956           Spills.addAvailable(ReuseSlot, DesignatedReg);
01957           unsigned RReg =
01958             SubIdx ? TRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg;
01959           MI.getOperand(i).setReg(RReg);
01960           MI.getOperand(i).setSubReg(0);
01961           DOUT << '\t' << *prior(MII);
01962           ++NumReused;
01963           continue;
01964         } // if (PhysReg)
01965         
01966         // Otherwise, reload it and remember that we have it.
01967         PhysReg = VRM.getPhys(VirtReg);
01968         assert(PhysReg && "Must map virtreg to physreg!");
01969 
01970         // Note that, if we reused a register for a previous operand, the
01971         // register we want to reload into might not actually be
01972         // available.  If this occurs, use the register indicated by the
01973         // reuser.
01974         if (ReusedOperands.hasReuses())
01975           PhysReg = ReusedOperands.GetRegForReload(VirtReg, PhysReg, &MI, 
01976                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
01977         
01978         RegInfo->setPhysRegUsed(PhysReg);
01979         ReusedOperands.markClobbered(PhysReg);
01980         if (AvoidReload)
01981           ++NumAvoided;
01982         else {
01983           // Back-schedule reloads and remats.
01984           MachineBasicBlock::iterator InsertLoc =
01985             ComputeReloadLoc(MII, MBB.begin(), PhysReg, TRI, DoReMat,
01986                              SSorRMId, TII, MF);
01987 
01988           if (DoReMat) {
01989             ReMaterialize(MBB, InsertLoc, PhysReg, VirtReg, TII, TRI, VRM);
01990           } else {
01991             const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg);
01992             TII->loadRegFromStackSlot(MBB, InsertLoc, PhysReg, SSorRMId, RC);
01993             MachineInstr *LoadMI = prior(InsertLoc);
01994             VRM.addSpillSlotUse(SSorRMId, LoadMI);
01995             ++NumLoads;
01996             DistanceMap.insert(std::make_pair(LoadMI, Dist++));
01997           }
01998           // This invalidates PhysReg.
01999           Spills.ClobberPhysReg(PhysReg);
02000 
02001           // Any stores to this stack slot are not dead anymore.
02002           if (!DoReMat)
02003             MaybeDeadStores[SSorRMId] = NULL;
02004           Spills.addAvailable(SSorRMId, PhysReg);
02005           // Assumes this is the last use. IsKill will be unset if reg is reused
02006           // unless it's a two-address operand.
02007           if (!MI.isRegTiedToDefOperand(i) &&
02008               KilledMIRegs.count(VirtReg) == 0) {
02009             MI.getOperand(i).setIsKill();
02010             KilledMIRegs.insert(VirtReg);
02011           }
02012 
02013           UpdateKills(*prior(InsertLoc), TRI, RegKills, KillOps);
02014           DOUT << '\t' << *prior(InsertLoc);
02015         }
02016         unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
02017         MI.getOperand(i).setReg(RReg);
02018         MI.getOperand(i).setSubReg(0);
02019       }
02020 
02021       // Ok - now we can remove stores that have been confirmed dead.
02022       for (unsigned j = 0, e = PotentialDeadStoreSlots.size(); j != e; ++j) {
02023         // This was the last use and the spilled value is still available
02024         // for reuse. That means the spill was unnecessary!
02025         int PDSSlot = PotentialDeadStoreSlots[j];
02026         MachineInstr* DeadStore = MaybeDeadStores[PDSSlot];
02027         if (DeadStore) {
02028           DOUT << "Removed dead store:\t" << *DeadStore;
02029           InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
02030           VRM.RemoveMachineInstrFromMaps(DeadStore);
02031           MBB.erase(DeadStore);
02032           MaybeDeadStores[PDSSlot] = NULL;
02033           ++NumDSE;
02034         }
02035       }
02036 
02037 
02038       DOUT << '\t' << MI;
02039 
02040 
02041       // If we have folded references to memory operands, make sure we clear all
02042       // physical registers that may contain the value of the spilled virtual
02043       // register
02044       SmallSet<int, 2> FoldedSS;
02045       for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ) {
02046         unsigned VirtReg = I->second.first;
02047         VirtRegMap::ModRef MR = I->second.second;
02048         DOUT << "Folded vreg: " << VirtReg << "  MR: " << MR;
02049 
02050         // MI2VirtMap be can updated which invalidate the iterator.
02051         // Increment the iterator first.
02052         ++I;
02053         int SS = VRM.getStackSlot(VirtReg);
02054         if (SS == VirtRegMap::NO_STACK_SLOT)
02055           continue;
02056         FoldedSS.insert(SS);
02057         DOUT << " - StackSlot: " << SS << "\n";
02058         
02059         // If this folded instruction is just a use, check to see if it's a
02060         // straight load from the virt reg slot.
02061         if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) {
02062           int FrameIdx;
02063           unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx);
02064           if (DestReg && FrameIdx == SS) {
02065             // If this spill slot is available, turn it into a copy (or nothing)
02066             // instead of leaving it as a load!
02067             if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) {
02068               DOUT << "Promoted Load To Copy: " << MI;
02069               if (DestReg != InReg) {
02070                 const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
02071                 TII->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC);
02072                 MachineOperand *DefMO = MI.findRegisterDefOperand(DestReg);
02073                 unsigned SubIdx = DefMO->getSubReg();
02074                 // Revisit the copy so we make sure to notice the effects of the
02075                 // operation on the destreg (either needing to RA it if it's 
02076                 // virtual or needing to clobber any values if it's physical).
02077                 NextMII = &MI;
02078                 --NextMII;  // backtrack to the copy.
02079                 // Propagate the sub-register index over.
02080                 if (SubIdx) {
02081                   DefMO = NextMII->findRegisterDefOperand(DestReg);
02082                   DefMO->setSubReg(SubIdx);
02083                 }
02084 
02085                 // Mark is killed.
02086                 MachineOperand *KillOpnd = NextMII->findRegisterUseOperand(InReg);
02087                 KillOpnd->setIsKill();
02088 
02089                 BackTracked = true;
02090               } else {
02091                 DOUT << "Removing now-noop copy: " << MI;
02092                 // Unset last kill since it's being reused.
02093                 InvalidateKill(InReg, TRI, RegKills, KillOps);
02094                 Spills.disallowClobberPhysReg(InReg);
02095               }
02096 
02097               InvalidateKills(MI, TRI, RegKills, KillOps);
02098               VRM.RemoveMachineInstrFromMaps(&MI);
02099               MBB.erase(&MI);
02100               Erased = true;
02101               goto ProcessNextInst;
02102             }
02103           } else {
02104             unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
02105             SmallVector<MachineInstr*, 4> NewMIs;
02106             if (PhysReg &&
02107                 TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) {
02108               MBB.insert(MII, NewMIs[0]);
02109               InvalidateKills(MI, TRI, RegKills, KillOps);
02110               VRM.RemoveMachineInstrFromMaps(&MI);
02111               MBB.erase(&MI);
02112               Erased = true;
02113               --NextMII;  // backtrack to the unfolded instruction.
02114               BackTracked = true;
02115               goto ProcessNextInst;
02116             }
02117           }
02118         }
02119 
02120         // If this reference is not a use, any previous store is now dead.
02121         // Otherwise, the store to this stack slot is not dead anymore.
02122         MachineInstr* DeadStore = MaybeDeadStores[SS];
02123         if (DeadStore) {
02124           bool isDead = !(MR & VirtRegMap::isRef);
02125           MachineInstr *NewStore = NULL;
02126           if (MR & VirtRegMap::isModRef) {
02127             unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS);
02128             SmallVector<MachineInstr*, 4> NewMIs;
02129             // We can reuse this physreg as long as we are allowed to clobber
02130             // the value and there isn't an earlier def that has already clobbered
02131             // the physreg.
02132             if (PhysReg &&
02133                 !ReusedOperands.isClobbered(PhysReg) &&
02134                 Spills.canClobberPhysReg(PhysReg) &&
02135                 !TII->isStoreToStackSlot(&MI, SS)) { // Not profitable!
02136               MachineOperand *KillOpnd =
02137                 DeadStore->findRegisterUseOperand(PhysReg, true);
02138               // Note, if the store is storing a sub-register, it's possible the
02139               // super-register is needed below.
02140               if (KillOpnd && !KillOpnd->getSubReg() &&
02141                   TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, true,NewMIs)){
02142                 MBB.insert(MII, NewMIs[0]);
02143                 NewStore = NewMIs[1];
02144                 MBB.insert(MII, NewStore);
02145                 VRM.addSpillSlotUse(SS, NewStore);
02146                 InvalidateKills(MI, TRI, RegKills, KillOps);
02147                 VRM.RemoveMachineInstrFromMaps(&MI);
02148                 MBB.erase(&MI);
02149                 Erased = true;
02150                 --NextMII;
02151                 --NextMII;  // backtrack to the unfolded instruction.
02152                 BackTracked = true;
02153                 isDead = true;
02154                 ++NumSUnfold;
02155               }
02156             }
02157           }
02158 
02159           if (isDead) {  // Previous store is dead.
02160             // If we get here, the store is dead, nuke it now.
02161             DOUT << "Removed dead store:\t" << *DeadStore;
02162             InvalidateKills(*DeadStore, TRI, RegKills, KillOps);
02163             VRM.RemoveMachineInstrFromMaps(DeadStore);
02164             MBB.erase(DeadStore);
02165             if (!NewStore)
02166               ++NumDSE;
02167           }
02168 
02169           MaybeDeadStores[SS] = NULL;
02170           if (NewStore) {
02171             // Treat this store as a spill merged into a copy. That makes the
02172             // stack slot value available.
02173             VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod);
02174             goto ProcessNextInst;
02175           }
02176         }
02177 
02178         // If the spill slot value is available, and this is a new definition of
02179         // the value, the value is not available anymore.
02180         if (MR & VirtRegMap::isMod) {
02181           // Notice that the value in this stack slot has been modified.
02182           Spills.ModifyStackSlotOrReMat(SS);
02183           
02184           // If this is *just* a mod of the value, check to see if this is just a
02185           // store to the spill slot (i.e. the spill got merged into the copy). If
02186           // so, realize that the vreg is available now, and add the store to the
02187           // MaybeDeadStore info.
02188           int StackSlot;
02189           if (!(MR & VirtRegMap::isRef)) {
02190             if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) {
02191               assert(TargetRegisterInfo::isPhysicalRegister(SrcReg) &&
02192                      "Src hasn't been allocated yet?");
02193 
02194               if (CommuteToFoldReload(MBB, MII, VirtReg, SrcReg, StackSlot,
02195                                       Spills, RegKills, KillOps, TRI, VRM)) {
02196                 NextMII = next(MII);
02197                 BackTracked = true;
02198                 goto ProcessNextInst;
02199               }
02200 
02201               // Okay, this is certainly a store of SrcReg to [StackSlot].  Mark
02202               // this as a potentially dead store in case there is a subsequent
02203               // store into the stack slot without a read from it.
02204               MaybeDeadStores[StackSlot] = &MI;
02205 
02206               // If the stack slot value was previously available in some other
02207               // register, change it now.  Otherwise, make the register
02208               // available in PhysReg.
02209               Spills.addAvailable(StackSlot, SrcReg, MI.killsRegister(SrcReg));
02210             }
02211           }
02212         }
02213       }
02214 
02215       // Process all of the spilled defs.
02216       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
02217         MachineOperand &MO = MI.getOperand(i);
02218         if (!(MO.isReg() && MO.getReg() && MO.isDef()))
02219           continue;
02220 
02221         unsigned VirtReg = MO.getReg();
02222         if (!TargetRegisterInfo::isVirtualRegister(VirtReg)) {
02223           // Check to see if this is a noop copy.  If so, eliminate the
02224           // instruction before considering the dest reg to be changed.
02225           // Also check if it's copying from an "undef", if so, we can't
02226           // eliminate this or else the undef marker is lost and it will
02227           // confuses the scavenger. This is extremely rare.
02228           unsigned Src, Dst, SrcSR, DstSR;
02229           if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst &&
02230               !MI.findRegisterUseOperand(Src)->isUndef()) {
02231             ++NumDCE;
02232             DOUT << "Removing now-noop copy: " << MI;
02233             SmallVector<unsigned, 2> KillRegs;
02234             InvalidateKills(MI, TRI, RegKills, KillOps, &KillRegs);
02235             if (MO.isDead() && !KillRegs.empty()) {
02236               // Source register or an implicit super/sub-register use is killed.
02237               assert(KillRegs[0] == Dst ||
02238                      TRI->isSubRegister(KillRegs[0], Dst) ||
02239                      TRI->isSuperRegister(KillRegs[0], Dst));
02240               // Last def is now dead.
02241               TransferDeadness(&MBB, Dist, Src, RegKills, KillOps, VRM);
02242             }
02243             VRM.RemoveMachineInstrFromMaps(&MI);
02244             MBB.erase(&MI);
02245             Erased = true;
02246             Spills.disallowClobberPhysReg(VirtReg);
02247             goto ProcessNextInst;
02248           }
02249 
02250           // If it's not a no-op copy, it clobbers the value in the destreg.
02251           Spills.ClobberPhysReg(VirtReg);
02252           ReusedOperands.markClobbered(VirtReg);
02253    
02254           // Check to see if this instruction is a load from a stack slot into
02255           // a register.  If so, this provides the stack slot value in the reg.
02256           int FrameIdx;
02257           if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) {
02258             assert(DestReg == VirtReg && "Unknown load situation!");
02259 
02260             // If it is a folded reference, then it's not safe to clobber.
02261             bool Folded = FoldedSS.count(FrameIdx);
02262             // Otherwise, if it wasn't available, remember that it is now!
02263             Spills.addAvailable(FrameIdx, DestReg, !Folded);
02264             goto ProcessNextInst;
02265           }
02266               
02267           continue;
02268         }
02269 
02270         unsigned SubIdx = MO.getSubReg();
02271         bool DoReMat = VRM.isReMaterialized(VirtReg);
02272         if (DoReMat)
02273           ReMatDefs.insert(&MI);
02274 
02275         // The only vregs left are stack slot definitions.
02276         int StackSlot = VRM.getStackSlot(VirtReg);
02277         const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg);
02278 
02279         // If this def is part of a two-address operand, make sure to execute
02280         // the store from the correct physical register.
02281         unsigned PhysReg;
02282         unsigned TiedOp;
02283         if (MI.isRegTiedToUseOperand(i, &TiedOp)) {
02284           PhysReg = MI.getOperand(TiedOp).getReg();
02285           if (SubIdx) {
02286             unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, TRI);
02287             assert(SuperReg && TRI->getSubReg(SuperReg, SubIdx) == PhysReg &&
02288                    "Can't find corresponding super-register!");
02289             PhysReg = SuperReg;
02290           }
02291         } else {
02292           PhysReg = VRM.getPhys(VirtReg);
02293           if (ReusedOperands.isClobbered(PhysReg)) {
02294             // Another def has taken the assigned physreg. It must have been a
02295             // use&def which got it due to reuse. Undo the reuse!
02296             PhysReg = ReusedOperands.GetRegForReload(VirtReg, PhysReg, &MI, 
02297                                Spills, MaybeDeadStores, RegKills, KillOps, VRM);
02298           }
02299         }
02300 
02301         assert(PhysReg && "VR not assigned a physical register?");
02302         RegInfo->setPhysRegUsed(PhysReg);
02303         unsigned RReg = SubIdx ? TRI->getSubReg(PhysReg, SubIdx) : PhysReg;
02304         ReusedOperands.markClobbered(RReg);
02305         MI.getOperand(i).setReg(RReg);
02306         MI.getOperand(i).setSubReg(0);
02307 
02308         if (!MO.isDead()) {
02309           MachineInstr *&LastStore = MaybeDeadStores[StackSlot];
02310           SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true,
02311                             LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM);
02312           NextMII = next(MII);
02313 
02314           // Check to see if this is a noop copy.  If so, eliminate the
02315           // instruction before considering the dest reg to be changed.
02316           {
02317             unsigned Src, Dst, SrcSR, DstSR;
02318             if (TII->isMoveInstr(MI, Src, Dst, SrcSR, DstSR) && Src == Dst) {
02319               ++NumDCE;
02320               DOUT << "Removing now-noop copy: " << MI;
02321               InvalidateKills(MI, TRI, RegKills, KillOps);
02322               VRM.RemoveMachineInstrFromMaps(&MI);
02323               MBB.erase(&MI);
02324               Erased = true;
02325               UpdateKills(*LastStore, TRI, RegKills, KillOps);
02326               goto ProcessNextInst;
02327             }
02328           }
02329         }    
02330       }
02331     ProcessNextInst:
02332       // Delete dead instructions without side effects.
02333       if (!Erased && !BackTracked && TII->isDeadInstruction(&MI)) {
02334         InvalidateKills(MI, TRI, RegKills, KillOps);
02335         VRM.RemoveMachineInstrFromMaps(&MI);
02336         MBB.erase(&MI);
02337         Erased = true;
02338       }
02339       if (!Erased)
02340         DistanceMap.insert(std::make_pair(&MI, Dist++));
02341       if (!Erased && !BackTracked) {
02342         for (MachineBasicBlock::iterator II = &MI; II != NextMII; ++II)
02343           UpdateKills(*II, TRI, RegKills, KillOps);
02344       }
02345       MII = NextMII;
02346     }
02347 
02348   }
02349 
02350 };
02351 
02352 }
02353 
02354 llvm::VirtRegRewriter* llvm::createVirtRegRewriter() {
02355   switch (RewriterOpt) {
02356   default: llvm_unreachable("Unreachable!");
02357   case local:
02358     return new LocalRewriter();
02359   case trivial:
02360     return new TrivialRewriter();
02361   }
02362 }