<commit_before>//===-- 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/Support/ErrorHandling.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 { local, trivial };
}

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

VirtRegRewriter::~VirtRegRewriter() {}


 
/// 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() || MO.isUndef())
      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.isUse() || !MO.isKill() || MO.isUndef())
      continue;
    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() || MO.isUndef())
      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) {
  MachineInstr *ReMatDefMI = VRM.getReMaterializedMI(Reg);
#ifdef NDEBUG
  const TargetInstrDesc &TID = ReMatDefMI->getDesc();
  assert(TID.getNumDefs() != 1 &&
         "Don't know how to remat instructions that define > 1 values!");
#endif<commit_msg>Fix inverted preprocessor conditional.<commit_after>//===-- 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/Support/ErrorHandling.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 { local, trivial };
}

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

VirtRegRewriter::~VirtRegRewriter() {}


 
/// 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() || MO.isUndef())
      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.isUse() || !MO.isKill() || MO.isUndef())
      continue;
    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() || MO.isUndef())
      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) {
  MachineInstr *ReMatDefMI = VRM.getReMaterializedMI(Reg);
#ifndef NDEBUG
  const TargetInstrDesc &TID = ReMatDefMI->getDesc();
  assert(TID.getNumDefs() != 1 &&
         "Don't know how to remat instructions that define > 1 values!");
#endif
{'fraction_non_alphanumeric': 0.12423030366822799, 'fraction_numerical': 0.0021577811694121363, 'mean_word_length': 2.616922051965356, 'pattern_counts': {'":': 0, '<': 97, '<?xml version=': 0, '>': 129, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6622680', 'n_tokens_mistral': 11719, 'n_tokens_neox': 11324, 'n_words': 3576}