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 "VirtRegMap.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
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));

static cl::opt<bool>
ScheduleSpills("schedule-spills",
               cl::desc("Schedule spill code"),
               cl::init(false));

VirtRegRewriter::~VirtRegRewriter() {}

/// substitutePhysReg - Replace virtual register in MachineOperand with a
/// physical register. Do the right thing with the sub-register index.
/// Note that operands may be added, so the MO reference is no longer valid.
static void substitutePhysReg(MachineOperand &MO, unsigned Reg,
                              const TargetRegisterInfo &TRI) {
  if (MO.getSubReg()) {
    MO.substPhysReg(Reg, TRI);

    // Any kill flags apply to the full virtual register, so they also apply to
    // the full physical register.
    // We assume that partial defs have already been decorated with a super-reg
    // <imp-def> operand by LiveIntervals.
    MachineInstr &MI = *MO.getParent();
    if (MO.isUse() && !MO.isUndef() &&
        (MO.isKill() || MI.isRegTiedToDefOperand(&MO-&MI.getOperand(0))))
      MI.addRegisterKilled(Reg, &TRI, /*AddIfNotFound=*/ true);
  } else {
    MO.setReg(Reg);
  }
}

namespace {

/// 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 TrivialRewriter : public VirtRegRewriter {

  bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM,
                            LiveIntervals* LIs) {
    DEBUG(dbgs() << "********** REWRITE MACHINE CODE **********\n");
    DEBUG(dbgs() << "********** Function: "
          << MF.getFunction()->getName() << '\n');
    DEBUG(dbgs() << "**** Machine Instrs"
          << "(NOTE! Does not include spills and reloads!) ****\n");
    DEBUG(MF.dump());

    MachineRegisterInfo *mri = &MF.getRegInfo();
    const TargetRegisterInfo *tri = MF.getTarget().getRegisterInfo();

    bool changed = false;

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

      const LiveInterval *li = liItr->second;
      unsigned reg = li->reg;

      if (TargetRegisterInfo::isPhysicalRegister(reg)) {
        if (!li->empty())
          mri->setPhysRegUsed(reg);
      }
      else {
        if (!VRM.hasPhys(reg))
          continue;
        unsigned pReg = VRM.getPhys(reg);
        mri->setPhysRegUsed(pReg);
        // Copy the register use-list before traversing it.
        SmallVector<std::pair<MachineInstr*, unsigned>, 32> reglist;
        for (MachineRegisterInfo::reg_iterator I = mri->reg_begin(reg),
               E = mri->reg_end(); I != E; ++I)
          reglist.push_back(std::make_pair(&*I, I.getOperandNo()));
        for (unsigned N=0; N != reglist.size(); ++N)
          substitutePhysReg(reglist[N].first->getOperand(reglist[N].second),
                            pReg, *tri);
        changed |= !reglist.empty();
      }
    }

    DEBUG(dbgs() << "**** Post Machine Instrs ****\n");
    DEBUG(MF.dump());

    return changed;
  }

};

}

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

namespace {

/// 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 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;
  }