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

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"),
                       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;
  }

};
 
// ************************************************************************ //

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