VirtRegRewriter.cpp

//===-- llvm/CodeGen/Rewriter.cpp -  Rewriter -----------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "virtregrewriter"
#include "VirtRegRewriter.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumDSE     , "Number of dead stores elided");
STATISTIC(NumDSS     , "Number of dead spill slots removed");
STATISTIC(NumCommutes, "Number of instructions commuted");
STATISTIC(NumDRM     , "Number of re-materializable defs elided");
STATISTIC(NumStores  , "Number of stores added");
STATISTIC(NumPSpills , "Number of physical register spills");
STATISTIC(NumOmitted , "Number of reloads omited");
STATISTIC(NumAvoided , "Number of reloads deemed unnecessary");
STATISTIC(NumCopified, "Number of available reloads turned into copies");
STATISTIC(NumReMats  , "Number of re-materialization");
STATISTIC(NumLoads   , "Number of loads added");
STATISTIC(NumReused  , "Number of values reused");
STATISTIC(NumDCE     , "Number of copies elided");
STATISTIC(NumSUnfold , "Number of stores unfolded");
STATISTIC(NumModRefUnfold, "Number of modref unfolded");

namespace {
  enum RewriterName { simple, local, trivial };
}

static cl::opt<RewriterName>
RewriterOpt("rewriter",
            cl::desc("Rewriter to use: (default: local)"),
            cl::Prefix,
            cl::values(clEnumVal(simple,  "simple rewriter"),
                       clEnumVal(local,   "local rewriter"),
                       clEnumVal(trivial, "trivial rewriter"),
                       clEnumValEnd),
            cl::init(local));

VirtRegRewriter::~VirtRegRewriter() {}

 
// ****************************** //
// Simple Spiller Implementation  //
// ****************************** //

struct VISIBILITY_HIDDEN SimpleRewriter : public VirtRegRewriter {

  bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
                            LiveIntervals* LIs) {
    DOUT << "********** REWRITE MACHINE CODE **********\n";
    DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
    const TargetMachine &TM = MF.getTarget();
    const TargetInstrInfo &TII = *TM.getInstrInfo();
    const TargetRegisterInfo &TRI = *TM.getRegisterInfo();


    // LoadedRegs - Keep track of which vregs are loaded, so that we only load
    // each vreg once (in the case where a spilled vreg is used by multiple
    // operands).  This is always smaller than the number of operands to the
    // current machine instr, so it should be small.
    std::vector<unsigned> LoadedRegs;

    for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end();
         MBBI != E; ++MBBI) {
      DOUT << MBBI->getBasicBlock()->getName() << ":\n";
      MachineBasicBlock &MBB = *MBBI;
      for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
           MII != E; ++MII) {
        MachineInstr &MI = *MII;
        for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
          MachineOperand &MO = MI.getOperand(i);
          if (MO.isReg() && MO.getReg()) {
            if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
              unsigned VirtReg = MO.getReg();
              unsigned SubIdx = MO.getSubReg();
              unsigned PhysReg = VRM.getPhys(VirtReg);
              unsigned RReg = SubIdx ? TRI.getSubReg(PhysReg, SubIdx) : PhysReg;
              if (!VRM.isAssignedReg(VirtReg)) {
                int StackSlot = VRM.getStackSlot(VirtReg);
                const TargetRegisterClass* RC = 
                                             MF.getRegInfo().getRegClass(VirtReg);
                
                if (MO.isUse() &&
                    std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg)
                             == LoadedRegs.end()) {
                  TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC);
                  MachineInstr *LoadMI = prior(MII);
                  VRM.addSpillSlotUse(StackSlot, LoadMI);
                  LoadedRegs.push_back(VirtReg);
                  ++NumLoads;
                  DOUT << '\t' << *LoadMI;
                }

                if (MO.isDef()) {
                  TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true,   
                                          StackSlot, RC);
                  MachineInstr *StoreMI = next(MII);
                  VRM.addSpillSlotUse(StackSlot, StoreMI);
                  ++NumStores;
                }
              }
              MF.getRegInfo().setPhysRegUsed(RReg);
              MI.getOperand(i).setReg(RReg);
              MI.getOperand(i).setSubReg(0);
            } else {
              MF.getRegInfo().setPhysRegUsed(MO.getReg());
            }
          }
        }

        DOUT << '\t' << MI;
        LoadedRegs.clear();
      }
    }
    return true;
  }

};
 
/// This class is intended for use with the new spilling framework only. It
/// rewrites vreg def/uses to use the assigned preg, but does not insert any
/// spill code.
struct VISIBILITY_HIDDEN TrivialRewriter : public VirtRegRewriter {

  bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
                            LiveIntervals* LIs) {
    DOUT << "********** REWRITE MACHINE CODE **********\n";
    DOUT << "********** Function: " << MF.getFunction()->getName() << '\n';
    MachineRegisterInfo *mri = &MF.getRegInfo();

    bool changed = false;

    for (LiveIntervals::iterator liItr = LIs->begin(), liEnd = LIs->end();
         liItr != liEnd; ++liItr) {

      if (TargetRegisterInfo::isVirtualRegister(liItr->first)) {
        if (VRM.hasPhys(liItr->first)) {
          unsigned preg = VRM.getPhys(liItr->first);
          mri->replaceRegWith(liItr->first, preg);
          mri->setPhysRegUsed(preg);
          changed = true;
        }
      }
      else {
        if (!liItr->second->empty()) {
          mri->setPhysRegUsed(liItr->first);
        }
      }
    }
    
    return changed;
  }

};

// ************************************************************************ //

/// AvailableSpills - As the local rewriter is scanning and rewriting an MBB
/// from top down, keep track of which spill slots or remat are available in
/// each register.
///
/// Note that not all physregs are created equal here.  In particular, some
/// physregs are reloads that we are allowed to clobber or ignore at any time.
/// Other physregs are values that the register allocated program is using
/// that we cannot CHANGE, but we can read if we like.  We keep track of this
/// on a per-stack-slot / remat id basis as the low bit in the value of the
/// SpillSlotsAvailable entries.  The predicate 'canClobberPhysReg()' checks
/// this bit and addAvailable sets it if.
class VISIBILITY_HIDDEN AvailableSpills {
  const TargetRegisterInfo *TRI;
  const TargetInstrInfo *TII;

  // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
  // or remat'ed virtual register values that are still available, due to
  // being loaded or stored to, but not invalidated yet.
  std::map<int, unsigned> SpillSlotsOrReMatsAvailable;

  // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
  // indicating which stack slot values are currently held by a physreg.  This
  // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
  // physreg is modified.
  std::multimap<unsigned, int> PhysRegsAvailable;

  void disallowClobberPhysRegOnly(unsigned PhysReg);

  void ClobberPhysRegOnly(unsigned PhysReg);
public:
  AvailableSpills(const TargetRegisterInfo *tri, const TargetInstrInfo *tii)
    : TRI(tri), TII(tii) {
  }

  /// clear - Reset the state.
  void clear() {
    SpillSlotsOrReMatsAvailable.clear();
    PhysRegsAvailable.clear();
  }

  const TargetRegisterInfo *getRegInfo() const { return TRI; }

  /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
  /// available in a physical register, return that PhysReg, otherwise
  /// return 0.
  unsigned getSpillSlotOrReMatPhysReg(int Slot) const {
    std::map<int, unsigned>::const_iterator I =
      SpillSlotsOrReMatsAvailable.find(Slot);
    if (I != SpillSlotsOrReMatsAvailable.end()) {
      return I->second >> 1;  // Remove the CanClobber bit.
    }
    return 0;
  }

  /// addAvailable - Mark that the specified stack slot / remat is available
  /// in the specified physreg.  If CanClobber is true, the physreg can be
  /// modified at any time without changing the semantics of the program.
  void addAvailable(int SlotOrReMat, unsigned Reg, bool CanClobber = true) {
    // If this stack slot is thought to be available in some other physreg, 
    // remove its record.
    ModifyStackSlotOrReMat(SlotOrReMat);

    PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat));
    SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) |
                                              (unsigned)CanClobber;

    if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
      DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1;
    else
      DOUT << "Remembering SS#" << SlotOrReMat;
    DOUT << " in physreg " << TRI->getName(Reg) << "\n";
  }

  /// canClobberPhysRegForSS - Return true if the spiller is allowed to change
  /// the value of the specified stackslot register if it desires. The
  /// specified stack slot must be available in a physreg for this query to
  /// make sense.
  bool canClobberPhysRegForSS(int SlotOrReMat) const {
    assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
           "Value not available!");
    return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
  }

  /// canClobberPhysReg - Return true if the spiller is allowed to clobber the
  /// physical register where values for some stack slot(s) might be
  /// available.
  bool canClobberPhysReg(unsigned PhysReg) const {
    std::multimap<unsigned, int>::const_iterator I =
      PhysRegsAvailable.lower_bound(PhysReg);
    while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
      int SlotOrReMat = I->second;
      I++;
      if (!canClobberPhysRegForSS(SlotOrReMat))
        return false;
    }
    return true;
  }

  /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
  /// stackslot register. The register is still available but is no longer
  /// allowed to be modifed.
  void disallowClobberPhysReg(unsigned PhysReg);

  /// ClobberPhysReg - This is called when the specified physreg changes
  /// value.  We use this to invalidate any info about stuff that lives in
  /// it and any of its aliases.
  void ClobberPhysReg(unsigned PhysReg);

  /// ModifyStackSlotOrReMat - This method is called when the value in a stack
  /// slot changes.  This removes information about which register the
  /// previous value for this slot lives in (as the previous value is dead
  /// now).
  void ModifyStackSlotOrReMat(int SlotOrReMat);

  /// AddAvailableRegsToLiveIn - Availability information is being kept coming
  /// into the specified MBB. Add available physical registers as potential
  /// live-in's. If they are reused in the MBB, they will be added to the
  /// live-in set to make register scavenger and post-allocation scheduler.
  void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
                                std::vector<MachineOperand*> &KillOps);
};

// ************************************************************************ //

// ReusedOp - For each reused operand, we keep track of a bit of information,
// in case we need to rollback upon processing a new operand.  See comments
// below.
struct ReusedOp {
  // The MachineInstr operand that reused an available value.
  unsigned Operand;

  // StackSlotOrReMat - The spill slot or remat id of the value being reused.
  unsigned StackSlotOrReMat;

  // PhysRegReused - The physical register the value was available in.
  unsigned PhysRegReused;

  // AssignedPhysReg - The physreg that was assigned for use by the reload.
  unsigned AssignedPhysReg;
  
  // VirtReg - The virtual register itself.
  unsigned VirtReg;

  ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
           unsigned vreg)
    : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
      AssignedPhysReg(apr), VirtReg(vreg) {}
};

/// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
/// is reused instead of reloaded.
class VISIBILITY_HIDDEN ReuseInfo {
  MachineInstr &MI;
  std::vector<ReusedOp> Reuses;
  BitVector PhysRegsClobbered;
public:
  ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
    PhysRegsClobbered.resize(tri->getNumRegs());
  }
  
  bool hasReuses() const {
    return !Reuses.empty();
  }
  
  /// addReuse - If we choose to reuse a virtual register that is already
  /// available instead of reloading it, remember that we did so.
  void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
                unsigned PhysRegReused, unsigned AssignedPhysReg,
                unsigned VirtReg) {
    // If the reload is to the assigned register anyway, no undo will be
    // required.
    if (PhysRegReused == AssignedPhysReg) return;
    
    // Otherwise, remember this.
    Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused, 
                              AssignedPhysReg, VirtReg));
  }

  void markClobbered(unsigned PhysReg) {
    PhysRegsClobbered.set(PhysReg);
  }

  bool isClobbered(unsigned PhysReg) const {
    return PhysRegsClobbered.test(PhysReg);
  }
  
  /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
  /// is some other operand that is using the specified register, either pick
  /// a new register to use, or evict the previous reload and use this reg. 
  unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
                           AvailableSpills &Spills,
                           std::vector<MachineInstr*> &MaybeDeadStores,
                           SmallSet<unsigned, 8> &Rejected,
                           BitVector &RegKills,
                           std::vector<MachineOperand*> &KillOps,
                           VirtRegMap &VRM);

  /// GetRegForReload - Helper for the above GetRegForReload(). Add a
  /// 'Rejected' set to remember which registers have been considered and
  /// rejected for the reload. This avoids infinite looping in case like
  /// this:
  /// t1 := op t2, t3
  /// t2 <- assigned r0 for use by the reload but ended up reuse r1
  /// t3 <- assigned r1 for use by the reload but ended up reuse r0
  /// t1 <- desires r1
  ///       sees r1 is taken by t2, tries t2's reload register r0
  ///       sees r0 is taken by t3, tries t3's reload register r1
  ///       sees r1 is taken by t2, tries t2's reload register r0 ...
  unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
                           AvailableSpills &Spills,
                           std::vector<MachineInstr*> &MaybeDeadStores,
                           BitVector &RegKills,
                           std::vector<MachineOperand*> &KillOps,
                           VirtRegMap &VRM) {
    SmallSet<unsigned, 8> Rejected;
    return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
                           RegKills, KillOps, VRM);
  }
};


// ****************** //
// Utility Functions  //
// ****************** //

/// findSinglePredSuccessor - Return via reference a vector of machine basic
/// blocks each of which is a successor of the specified BB and has no other
/// predecessor.
static void findSinglePredSuccessor(MachineBasicBlock *MBB,
                                   SmallVectorImpl<MachineBasicBlock *> &Succs) {
  for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
         SE = MBB->succ_end(); SI != SE; ++SI) {
    MachineBasicBlock *SuccMBB = *SI;
    if (SuccMBB->pred_size() == 1)
      Succs.push_back(SuccMBB);
  }
}

/// InvalidateKill - Invalidate register kill information for a specific
/// register. This also unsets the kills marker on the last kill operand.
static void InvalidateKill(unsigned Reg,
                           const TargetRegisterInfo* TRI,
                           BitVector &RegKills,
                           std::vector<MachineOperand*> &KillOps) {
  if (RegKills[Reg]) {
    KillOps[Reg]->setIsKill(false);
    // KillOps[Reg] might be a def of a super-register.
    unsigned KReg = KillOps[Reg]->getReg();
    KillOps[KReg] = NULL;
    RegKills.reset(KReg);
    for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
      if (RegKills[*SR]) {
        KillOps[*SR]->setIsKill(false);
        KillOps[*SR] = NULL;
        RegKills.reset(*SR);
      }
    }
  }
}

/// InvalidateKills - MI is going to be deleted. If any of its operands are
/// marked kill, then invalidate the information.
static void InvalidateKills(MachineInstr &MI,
                            const TargetRegisterInfo* TRI,
                            BitVector &RegKills,
                            std::vector<MachineOperand*> &KillOps,
                            SmallVector<unsigned, 2> *KillRegs = NULL) {
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || !MO.isUse() || !MO.isKill())
      continue;
    unsigned Reg = MO.getReg();
    if (TargetRegisterInfo::isVirtualRegister(Reg))
      continue;
    if (KillRegs)
      KillRegs->push_back(Reg);
    assert(Reg < KillOps.size());
    if (KillOps[Reg] == &MO) {
      KillOps[Reg] = NULL;
      RegKills.reset(Reg);
      for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
        if (RegKills[*SR]) {
          KillOps[*SR] = NULL;
          RegKills.reset(*SR);
        }
      }
    }
  }
}

/// InvalidateRegDef - If the def operand of the specified def MI is now dead
/// (since it's spill instruction is removed), mark it isDead. Also checks if
/// the def MI has other definition operands that are not dead. Returns it by
/// reference.
static bool InvalidateRegDef(MachineBasicBlock::iterator I,
                             MachineInstr &NewDef, unsigned Reg,
                             bool &HasLiveDef) {
  // Due to remat, it's possible this reg isn't being reused. That is,
  // the def of this reg (by prev MI) is now dead.
  MachineInstr *DefMI = I;
  MachineOperand *DefOp = NULL;
  for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = DefMI->getOperand(i);
    if (MO.isReg() && MO.isDef()) {
      if (MO.getReg() == Reg)
        DefOp = &MO;
      else if (!MO.isDead())
        HasLiveDef = true;
    }
  }
  if (!DefOp)
    return false;

  bool FoundUse = false, Done = false;
  MachineBasicBlock::iterator E = &NewDef;
  ++I; ++E;
  for (; !Done && I != E; ++I) {
    MachineInstr *NMI = I;
    for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) {
      MachineOperand &MO = NMI->getOperand(j);
      if (!MO.isReg() || MO.getReg() != Reg)
        continue;
      if (MO.isUse())
        FoundUse = true;
      Done = true; // Stop after scanning all the operands of this MI.
    }
  }
  if (!FoundUse) {
    // Def is dead!
    DefOp->setIsDead();
    return true;
  }
  return false;
}

/// UpdateKills - Track and update kill info. If a MI reads a register that is
/// marked kill, then it must be due to register reuse. Transfer the kill info
/// over.
static void UpdateKills(MachineInstr &MI, const TargetRegisterInfo* TRI,
                        BitVector &RegKills,
                        std::vector<MachineOperand*> &KillOps) {
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || !MO.isUse())
      continue;
    unsigned Reg = MO.getReg();
    if (Reg == 0)
      continue;
    
    if (RegKills[Reg] && KillOps[Reg]->getParent() != &MI) {
      // That can't be right. Register is killed but not re-defined and it's
      // being reused. Let's fix that.
      KillOps[Reg]->setIsKill(false);
      // KillOps[Reg] might be a def of a super-register.
      unsigned KReg = KillOps[Reg]->getReg();
      KillOps[KReg] = NULL;
      RegKills.reset(KReg);

      // Must be a def of a super-register. Its other sub-regsters are no
      // longer killed as well.
      for (const unsigned *SR = TRI->getSubRegisters(KReg); *SR; ++SR) {
        KillOps[*SR] = NULL;
        RegKills.reset(*SR);
      }

      if (!MI.isRegTiedToDefOperand(i))
        // Unless it's a two-address operand, this is the new kill.
        MO.setIsKill();
    }
    if (MO.isKill()) {
      RegKills.set(Reg);
      KillOps[Reg] = &MO;
      for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
        RegKills.set(*SR);
        KillOps[*SR] = &MO;
      }
    }
  }

  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    const MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || !MO.isDef())
      continue;
    unsigned Reg = MO.getReg();
    RegKills.reset(Reg);
    KillOps[Reg] = NULL;
    // It also defines (or partially define) aliases.
    for (const unsigned *SR = TRI->getSubRegisters(Reg); *SR; ++SR) {
      RegKills.reset(*SR);
      KillOps[*SR] = NULL;
    }
  }
}

/// ReMaterialize - Re-materialize definition for Reg targetting DestReg.
///
static void ReMaterialize(MachineBasicBlock &MBB,
                          MachineBasicBlock::iterator &MII,
                          unsigned DestReg, unsigned Reg,
                          const TargetInstrInfo *TII,
                          const TargetRegisterInfo *TRI,
                          VirtRegMap &VRM) {
  TII->reMaterialize(MBB, MII, DestReg, VRM.getReMaterializedMI(Reg));
  MachineInstr *NewMI = prior(MII);
  for (unsigned i = 0, e = NewMI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = NewMI->getOperand(i);
    if (!MO.isReg() || MO.getReg() == 0)
      continue;
    unsigned VirtReg = MO.getReg();
    if (TargetRegisterInfo::isPhysicalRegister(VirtReg))
      continue;
    assert(MO.isUse());
    unsigned SubIdx = MO.getSubReg();
    unsigned Phys = VRM.getPhys(VirtReg);
    assert(Phys);
    unsigned RReg = SubIdx ? TRI->getSubReg(Phys, SubIdx) : Phys;
    MO.setReg(RReg);
    MO.setSubReg(0);
  }
  ++NumReMats;
}

/// findSuperReg - Find the SubReg's super-register of given register class
/// where its SubIdx sub-register is SubReg.
static unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg,
                             unsigned SubIdx, const TargetRegisterInfo *TRI) {
  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end();
       I != E; ++I) {
    unsigned Reg = *I;
    if (TRI->getSubReg(Reg, SubIdx) == SubReg)
      return Reg;
  }
  return 0;
}

// ******************************** //
// Available Spills Implementation  //
// ******************************** //

/// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified
/// stackslot register. The register is still available but is no longer
/// allowed to be modifed.
void AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) {
  std::multimap<unsigned, int>::iterator I =
    PhysRegsAvailable.lower_bound(PhysReg);
  while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
    int SlotOrReMat = I->second;
    I++;
    assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
           "Bidirectional map mismatch!");
    SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1;
    DOUT << "PhysReg " << TRI->getName(PhysReg)
         << " copied, it is available for use but can no longer be modified\n";
  }
}

/// disallowClobberPhysReg - Unset the CanClobber bit of the specified
/// stackslot register and its aliases. The register and its aliases may
/// still available but is no longer allowed to be modifed.
void AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) {
  for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
    disallowClobberPhysRegOnly(*AS);
  disallowClobberPhysRegOnly(PhysReg);
}

/// ClobberPhysRegOnly - This is called when the specified physreg changes
/// value.  We use this to invalidate any info about stuff we thing lives in it.
void AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) {
  std::multimap<unsigned, int>::iterator I =
    PhysRegsAvailable.lower_bound(PhysReg);
  while (I != PhysRegsAvailable.end() && I->first == PhysReg) {
    int SlotOrReMat = I->second;
    PhysRegsAvailable.erase(I++);
    assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg &&
           "Bidirectional map mismatch!");
    SpillSlotsOrReMatsAvailable.erase(SlotOrReMat);
    DOUT << "PhysReg " << TRI->getName(PhysReg)
         << " clobbered, invalidating ";
    if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
      DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n";
    else
      DOUT << "SS#" << SlotOrReMat << "\n";
  }
}

/// ClobberPhysReg - This is called when the specified physreg changes
/// value.  We use this to invalidate any info about stuff we thing lives in
/// it and any of its aliases.
void AvailableSpills::ClobberPhysReg(unsigned PhysReg) {
  for (const unsigned *AS = TRI->getAliasSet(PhysReg); *AS; ++AS)
    ClobberPhysRegOnly(*AS);
  ClobberPhysRegOnly(PhysReg);
}

/// AddAvailableRegsToLiveIn - Availability information is being kept coming
/// into the specified MBB. Add available physical registers as potential
/// live-in's. If they are reused in the MBB, they will be added to the
/// live-in set to make register scavenger and post-allocation scheduler.
void AvailableSpills::AddAvailableRegsToLiveIn(MachineBasicBlock &MBB,
                                        BitVector &RegKills,
                                        std::vector<MachineOperand*> &KillOps) {
  std::set<unsigned> NotAvailable;
  for (std::multimap<unsigned, int>::iterator
         I = PhysRegsAvailable.begin(), E = PhysRegsAvailable.end();
       I != E; ++I) {
    unsigned Reg = I->first;
    const TargetRegisterClass* RC = TRI->getPhysicalRegisterRegClass(Reg);
    // FIXME: A temporary workaround. We can't reuse available value if it's
    // not safe to move the def of the virtual register's class. e.g.
    // X86::RFP* register classes. Do not add it as a live-in.
    if (!TII->isSafeToMoveRegClassDefs(RC))
      // This is no longer available.
      NotAvailable.insert(Reg);
    else {
      MBB.addLiveIn(Reg);
      InvalidateKill(Reg, TRI, RegKills, KillOps);
    }

    // Skip over the same register.
    std::multimap<unsigned, int>::iterator NI = next(I);
    while (NI != E && NI->first == Reg) {
      ++I;
      ++NI;
    }
  }

  for (std::set<unsigned>::iterator I = NotAvailable.begin(),
         E = NotAvailable.end(); I != E; ++I) {
    ClobberPhysReg(*I);
    for (const unsigned *SubRegs = TRI->getSubRegisters(*I);
       *SubRegs; ++SubRegs)
      ClobberPhysReg(*SubRegs);
  }
}

/// ModifyStackSlotOrReMat - This method is called when the value in a stack
/// slot changes.  This removes information about which register the previous
/// value for this slot lives in (as the previous value is dead now).
void AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) {
  std::map<int, unsigned>::iterator It =
    SpillSlotsOrReMatsAvailable.find(SlotOrReMat);
  if (It == SpillSlotsOrReMatsAvailable.end()) return;
  unsigned Reg = It->second >> 1;
  SpillSlotsOrReMatsAvailable.erase(It);
  
  // This register may hold the value of multiple stack slots, only remove this
  // stack slot from the set of values the register contains.
  std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg);
  for (; ; ++I) {
    assert(I != PhysRegsAvailable.end() && I->first == Reg &&
           "Map inverse broken!");
    if (I->second == SlotOrReMat) break;
  }
  PhysRegsAvailable.erase(I);
}

// ************************** //
// Reuse Info Implementation  //
// ************************** //

/// GetRegForReload - We are about to emit a reload into PhysReg.  If there
/// is some other operand that is using the specified register, either pick
/// a new register to use, or evict the previous reload and use this reg.
unsigned ReuseInfo::GetRegForReload(unsigned PhysReg, MachineInstr *MI,
                         AvailableSpills &Spills,
                         std::vector<MachineInstr*> &MaybeDeadStores,
                         SmallSet<unsigned, 8> &Rejected,
                         BitVector &RegKills,
                         std::vector<MachineOperand*> &KillOps,
                         VirtRegMap &VRM) {
  const TargetInstrInfo* TII = MI->getParent()->getParent()->getTarget()
                               .getInstrInfo();
  
  if (Reuses.empty()) return PhysReg;  // This is most often empty.

  for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) {
    ReusedOp &Op = Reuses[ro];
    // If we find some other reuse that was supposed to use this register
    // exactly for its reload, we can change this reload to use ITS reload
    // register. That is, unless its reload register has already been
    // considered and subsequently rejected because it has also been reused
    // by another operand.
    if (Op.PhysRegReused == PhysReg &&
        Rejected.count(Op.AssignedPhysReg) == 0) {
      // Yup, use the reload register that we didn't use before.
      unsigned NewReg = Op.AssignedPhysReg;
      Rejected.insert(PhysReg);
      return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected,
                             RegKills, KillOps, VRM);
    } else {
      // Otherwise, we might also have a problem if a previously reused
      // value aliases the new register.  If so, codegen the previous reload
      // and use this one.          
      unsigned PRRU = Op.PhysRegReused;
      const TargetRegisterInfo *TRI = Spills.getRegInfo();
      if (TRI->areAliases(PRRU, PhysReg)) {
        // Okay, we found out that an alias of a reused register
        // was used.  This isn't good because it means we have
        // to undo a previous reuse.
        MachineBasicBlock *MBB = MI->getParent();
        const TargetRegisterClass *AliasRC =
          MBB->getParent()->getRegInfo().getRegClass(Op.VirtReg);

        // Copy Op out of the vector and remove it, we're going to insert an
        // explicit load for it.
        ReusedOp NewOp = Op;
        Reuses.erase(Reuses.begin()+ro);

        // Ok, we're going to try to reload the assigned physreg into the
        // slot that we were supposed to in the first place.  However, that
        // register could hold a reuse.  Check to see if it conflicts or
        // would prefer us to use a different register.
        unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg,
                                              MI, Spills, MaybeDeadStores,
                                          Rejected, RegKills, KillOps, VRM);
        
        MachineBasicBlock::iterator MII = MI;
        if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) {
          ReMaterialize(*MBB, MII, NewPhysReg, NewOp.VirtReg, TII, TRI,VRM);
        } else {
          TII->loadRegFromStackSlot(*MBB, MII, NewPhysReg,
                                    NewOp.StackSlotOrReMat, AliasRC);
          MachineInstr *LoadMI = prior(MII);
          VRM.addSpillSlotUse(NewOp.StackSlotOrReMat, LoadMI);
          // Any stores to this stack slot are not dead anymore.
          MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL;            
          ++NumLoads;
        }
        Spills.ClobberPhysReg(NewPhysReg);
        Spills.ClobberPhysReg(NewOp.PhysRegReused);

        unsigned SubIdx = MI->getOperand(NewOp.Operand).getSubReg();
        unsigned RReg = SubIdx ? TRI->getSubReg(NewPhysReg, SubIdx) : NewPhysReg;
        MI->getOperand(NewOp.Operand).setReg(RReg);
        MI->getOperand(NewOp.Operand).setSubReg(0);

        Spills.addAvailable(NewOp.StackSlotOrReMat, NewPhysReg);
        --MII;
        UpdateKills(*MII, TRI, RegKills, KillOps);
        DOUT << '\t' << *MII;
        
        DOUT << "Reuse undone!\n";
        --NumReused;
        
        // Finally, PhysReg is now available, go ahead and use it.
        return PhysReg;
      }
    }
  }
  return PhysReg;
}

// ************************************************************************ //

/// FoldsStackSlotModRef - Return true if the specified MI folds the specified
/// stack slot mod/ref. It also checks if it's possible to unfold the
/// instruction by having it define a specified physical register instead.
static bool FoldsStackSlotModRef(MachineInstr &MI, int SS, unsigned PhysReg,
                                 const TargetInstrInfo *TII,
                                 const TargetRegisterInfo *TRI,
                                 VirtRegMap &VRM) {
  if (VRM.hasEmergencySpills(&MI) || VRM.isSpillPt(&MI))
    return false;

  bool Found = false;
  VirtRegMap::MI2VirtMapTy::const_iterator I, End;
  for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) {
    unsigned VirtReg = I->second.first;
    VirtRegMap::ModRef MR = I->second.second;
    if (MR & VirtRegMap::isModRef)
      if (VRM.getStackSlot(VirtReg) == SS) {
        Found= TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), true, true) != 0;
        break;
      }
  }
  if (!Found)
    return false;

  // Does the instruction uses a register that overlaps the scratch register?
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI.getOperand(i);
    if (!MO.isReg() || MO.getReg() == 0)
      continue;
    unsigned Reg = MO.getReg();
    if (TargetRegisterInfo::isVirtualRegister(Reg)) {
      if (!VRM.hasPhys(Reg))
        continue;
      Reg = VRM.getPhys(Reg);
    }
    if (TRI->regsOverlap(PhysReg, Reg))
      return false;
  }
  return true;
}

/// FindFreeRegister - Find a free register of a given register class by looking
/// at (at most) the last two machine instructions.
static unsigned FindFreeRegister(MachineBasicBlock::iterator MII,
                                 MachineBasicBlock &MBB,
                                 const TargetRegisterClass *RC,
                                 const TargetRegisterInfo *TRI,
                                 BitVector &AllocatableRegs) {
  BitVector Defs(TRI->getNumRegs());
  BitVector Uses(TRI->getNumRegs());
  SmallVector<unsigned, 4> LocalUses;
  SmallVector<unsigned, 4> Kills;

  // Take a look at 2 instructions at most.
  for (unsigned Count = 0; Count < 2; ++Count) {
    if (MII == MBB.begin())
      break;
    MachineInstr *PrevMI = prior(MII);
    for (unsigned i = 0, e = PrevMI->getNumOperands(); i != e; ++i) {
      MachineOperand &MO = PrevMI->getOperand(i);
      if (!MO.isReg() || MO.getReg() == 0)
        continue;
      unsigned Reg = MO.getReg();
      if (MO.isDef()) {
        Defs.set(Reg);
        for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
          Defs.set(*AS);
      } else  {
        LocalUses.push_back(Reg);
        if (MO.isKill() && AllocatableRegs[Reg])
          Kills.push_back(Reg);
      }
    }

    for (unsigned i = 0, e = Kills.size(); i != e; ++i) {
      unsigned Kill = Kills[i];
      if (!Defs[Kill] && !Uses[Kill] &&
          TRI->getPhysicalRegisterRegClass(Kill) == RC)
        return Kill;
    }
    for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
      unsigned Reg = LocalUses[i];
      Uses.set(Reg);
      for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS)
        Uses.set(*AS);
    }

    MII = PrevMI;
  }

  return 0;
}

static
void AssignPhysToVirtReg(MachineInstr *MI, unsigned VirtReg, unsigned PhysReg) {
  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = MI->getOperand(i);
    if (MO.isReg() && MO.getReg() == VirtReg)
      MO.setReg(PhysReg);
  }
}

namespace {
  struct RefSorter {
    bool operator()(const std::pair<MachineInstr*, int> &A,
                    const std::pair<MachineInstr*, int> &B) {
      return A.second < B.second;
    }
  };
}

// ***************************** //
// Local Spiller Implementation  //
// ***************************** //

class VISIBILITY_HIDDEN LocalRewriter : public VirtRegRewriter {
  MachineRegisterInfo *RegInfo;
  const TargetRegisterInfo *TRI;
  const TargetInstrInfo *TII;
  BitVector AllocatableRegs;
  DenseMap<MachineInstr*, unsigned> DistanceMap;
public:

  bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
                            LiveIntervals* LIs) {
    RegInfo = &MF.getRegInfo(); 
    TRI = MF.getTarget().getRegisterInfo();
    TII = MF.getTarget().getInstrInfo();
    AllocatableRegs = TRI->getAllocatableSet(MF);
    DOUT << "\n**** Local spiller rewriting function '"
         << MF.getFunction()->getName() << "':\n";
    DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)"
            " ****\n";
    DEBUG(MF.dump());

    // Spills - Keep track of which spilled values are available in physregs
    // so that we can choose to reuse the physregs instead of emitting
    // reloads. This is usually refreshed per basic block.
    AvailableSpills Spills(TRI, TII);

    // Keep track of kill information.
    BitVector RegKills(TRI->getNumRegs());
    std::vector<MachineOperand*> KillOps;
    KillOps.resize(TRI->getNumRegs(), NULL);

    // SingleEntrySuccs - Successor blocks which have a single predecessor.
    SmallVector<MachineBasicBlock*, 4> SinglePredSuccs;
    SmallPtrSet<MachineBasicBlock*,16> EarlyVisited;

    // Traverse the basic blocks depth first.
    MachineBasicBlock *Entry = MF.begin();
    SmallPtrSet<MachineBasicBlock*,16> Visited;
    for (df_ext_iterator<MachineBasicBlock*,
           SmallPtrSet<MachineBasicBlock*,16> >
           DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
         DFI != E; ++DFI) {
      MachineBasicBlock *MBB = *DFI;
      if (!EarlyVisited.count(MBB))
        RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);

      // If this MBB is the only predecessor of a successor. Keep the
      // availability information and visit it next.
      do {
        // Keep visiting single predecessor successor as long as possible.
        SinglePredSuccs.clear();
        findSinglePredSuccessor(MBB, SinglePredSuccs);
        if (SinglePredSuccs.empty())
          MBB = 0;
        else {
          // FIXME: More than one successors, each of which has MBB has
          // the only predecessor.
          MBB = SinglePredSuccs[0];
          if (!Visited.count(MBB) && EarlyVisited.insert(MBB)) {
            Spills.AddAvailableRegsToLiveIn(*MBB, RegKills, KillOps);
            RewriteMBB(*MBB, VRM, LIs, Spills, RegKills, KillOps);
          }
        }
      } while (MBB);