RegAllocLocal.cpp

//===-- RegAllocLocal.cpp - A BasicBlock generic register allocator -------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This register allocator allocates registers to a basic block at a time,
// attempting to keep values in registers and reusing registers as appropriate.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regalloc"
#include "llvm/BasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;

STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads , "Number of loads added");

static RegisterRegAlloc
  localRegAlloc("local", "local register allocator",
                createLocalRegisterAllocator);

namespace {
  class VISIBILITY_HIDDEN RALocal : public MachineFunctionPass {
  public:
    static char ID;
    RALocal() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {}
  private:
    const TargetMachine *TM;
    MachineFunction *MF;
    const TargetRegisterInfo *TRI;
    const TargetInstrInfo *TII;

    // StackSlotForVirtReg - Maps virtual regs to the frame index where these
    // values are spilled.
    IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;

    // Virt2PhysRegMap - This map contains entries for each virtual register
    // that is currently available in a physical register.
    IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;

    unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
      return Virt2PhysRegMap[VirtReg];
    }

    // PhysRegsUsed - This array is effectively a map, containing entries for
    // each physical register that currently has a value (ie, it is in
    // Virt2PhysRegMap).  The value mapped to is the virtual register
    // corresponding to the physical register (the inverse of the
    // Virt2PhysRegMap), or 0.  The value is set to 0 if this register is pinned
    // because it is used by a future instruction, and to -2 if it is not
    // allocatable.  If the entry for a physical register is -1, then the
    // physical register is "not in the map".
    //
    std::vector<int> PhysRegsUsed;

    // PhysRegsUseOrder - This contains a list of the physical registers that
    // currently have a virtual register value in them.  This list provides an
    // ordering of registers, imposing a reallocation order.  This list is only
    // used if all registers are allocated and we have to spill one, in which
    // case we spill the least recently used register.  Entries at the front of
    // the list are the least recently used registers, entries at the back are
    // the most recently used.
    //
    std::vector<unsigned> PhysRegsUseOrder;

    // Virt2LastUseMap - This maps each virtual register to its last use
    // (MachineInstr*, operand index pair).
    IndexedMap<std::pair<MachineInstr*, unsigned>, VirtReg2IndexFunctor>
    Virt2LastUseMap;

    std::pair<MachineInstr*,unsigned>& getVirtRegLastUse(unsigned Reg) {
      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
      return Virt2LastUseMap[Reg];
    }

    // VirtRegModified - This bitset contains information about which virtual
    // registers need to be spilled back to memory when their registers are
    // scavenged.  If a virtual register has simply been rematerialized, there
    // is no reason to spill it to memory when we need the register back.
    //
    BitVector VirtRegModified;
    
    // UsedInMultipleBlocks - Tracks whether a particular register is used in
    // more than one block.
    BitVector UsedInMultipleBlocks;

    void markVirtRegModified(unsigned Reg, bool Val = true) {
      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
      Reg -= TargetRegisterInfo::FirstVirtualRegister;
      if (Val)
        VirtRegModified.set(Reg);
      else
        VirtRegModified.reset(Reg);
    }

    bool isVirtRegModified(unsigned Reg) const {
      assert(TargetRegisterInfo::isVirtualRegister(Reg) && "Illegal VirtReg!");
      assert(Reg - TargetRegisterInfo::FirstVirtualRegister < VirtRegModified.size()
             && "Illegal virtual register!");
      return VirtRegModified[Reg - TargetRegisterInfo::FirstVirtualRegister];
    }

    void AddToPhysRegsUseOrder(unsigned Reg) {
      std::vector<unsigned>::iterator It =
        std::find(PhysRegsUseOrder.begin(), PhysRegsUseOrder.end(), Reg);
      if (It != PhysRegsUseOrder.end())
        PhysRegsUseOrder.erase(It);
      PhysRegsUseOrder.push_back(Reg);
    }

    void MarkPhysRegRecentlyUsed(unsigned Reg) {
      if (PhysRegsUseOrder.empty() ||
          PhysRegsUseOrder.back() == Reg) return;  // Already most recently used

      for (unsigned i = PhysRegsUseOrder.size(); i != 0; --i)
        if (areRegsEqual(Reg, PhysRegsUseOrder[i-1])) {
          unsigned RegMatch = PhysRegsUseOrder[i-1];       // remove from middle
          PhysRegsUseOrder.erase(PhysRegsUseOrder.begin()+i-1);
          // Add it to the end of the list
          PhysRegsUseOrder.push_back(RegMatch);
          if (RegMatch == Reg)
            return;    // Found an exact match, exit early
        }
    }

  public:
    virtual const char *getPassName() const {
      return "Local Register Allocator";
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequiredID(PHIEliminationID);
      AU.addRequiredID(TwoAddressInstructionPassID);
      MachineFunctionPass::getAnalysisUsage(AU);
    }

  private:
    /// runOnMachineFunction - Register allocate the whole function
    bool runOnMachineFunction(MachineFunction &Fn);

    /// AllocateBasicBlock - Register allocate the specified basic block.
    void AllocateBasicBlock(MachineBasicBlock &MBB);


    /// areRegsEqual - This method returns true if the specified registers are
    /// related to each other.  To do this, it checks to see if they are equal
    /// or if the first register is in the alias set of the second register.
    ///
    bool areRegsEqual(unsigned R1, unsigned R2) const {
      if (R1 == R2) return true;
      for (const unsigned *AliasSet = TRI->getAliasSet(R2);
           *AliasSet; ++AliasSet) {
        if (*AliasSet == R1) return true;
      }
      return false;
    }

    /// getStackSpaceFor - This returns the frame index of the specified virtual
    /// register on the stack, allocating space if necessary.
    int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC);

    /// removePhysReg - This method marks the specified physical register as no
    /// longer being in use.
    ///
    void removePhysReg(unsigned PhysReg);

    /// spillVirtReg - This method spills the value specified by PhysReg into
    /// the virtual register slot specified by VirtReg.  It then updates the RA
    /// data structures to indicate the fact that PhysReg is now available.
    ///
    void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI,
                      unsigned VirtReg, unsigned PhysReg);

    /// spillPhysReg - This method spills the specified physical register into
    /// the virtual register slot associated with it.  If OnlyVirtRegs is set to
    /// true, then the request is ignored if the physical register does not
    /// contain a virtual register.
    ///