LiveIntervalAnalysis.cpp

//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LiveInterval analysis pass which is used
// by the Linear Scan Register allocator. This pass linearizes the
// basic blocks of the function in DFS order and uses the
// LiveVariables pass to conservatively compute live intervals for
// each virtual and physical register.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "liveintervals"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "VirtRegMap.h"
#include "llvm/Value.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
using namespace llvm;

namespace {
  RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");

  static Statistic<> numIntervals
  ("liveintervals", "Number of original intervals");

  static Statistic<> numIntervalsAfter
  ("liveintervals", "Number of intervals after coalescing");

  static Statistic<> numJoins
  ("liveintervals", "Number of interval joins performed");

  static Statistic<> numPeep
  ("liveintervals", "Number of identity moves eliminated after coalescing");

  static Statistic<> numFolded
  ("liveintervals", "Number of loads/stores folded into instructions");

  static cl::opt<bool>
  EnableJoining("join-liveintervals",
                cl::desc("Coallesce copies (default=true)"),
                cl::init(true));
}

void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<LiveVariables>();
  AU.addPreservedID(PHIEliminationID);
  AU.addRequiredID(PHIEliminationID);
  AU.addRequiredID(TwoAddressInstructionPassID);
  AU.addRequired<LoopInfo>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void LiveIntervals::releaseMemory() {
  mi2iMap_.clear();
  i2miMap_.clear();
  r2iMap_.clear();
  r2rMap_.clear();
}


static bool isZeroLengthInterval(LiveInterval *li) {
  for (LiveInterval::Ranges::const_iterator
         i = li->ranges.begin(), e = li->ranges.end(); i != e; ++i)
    if (i->end - i->start > LiveIntervals::InstrSlots::NUM)
      return false;
  return true;
}


/// runOnMachineFunction - Register allocate the whole function
///
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  mf_ = &fn;
  tm_ = &fn.getTarget();
  mri_ = tm_->getRegisterInfo();
  tii_ = tm_->getInstrInfo();
  lv_ = &getAnalysis<LiveVariables>();
  allocatableRegs_ = mri_->getAllocatableSet(fn);
  r2rMap_.grow(mf_->getSSARegMap()->getLastVirtReg());

  // If this function has any live ins, insert a dummy instruction at the
  // beginning of the function that we will pretend "defines" the values.  This
  // is to make the interval analysis simpler by providing a number.
  if (fn.livein_begin() != fn.livein_end()) {
    unsigned FirstLiveIn = fn.livein_begin()->first;

    // Find a reg class that contains this live in.
    const TargetRegisterClass *RC = 0;
    for (MRegisterInfo::regclass_iterator RCI = mri_->regclass_begin(),
           E = mri_->regclass_end(); RCI != E; ++RCI)
      if ((*RCI)->contains(FirstLiveIn)) {
        RC = *RCI;
        break;
      }

    MachineInstr *OldFirstMI = fn.begin()->begin();
    mri_->copyRegToReg(*fn.begin(), fn.begin()->begin(),
                       FirstLiveIn, FirstLiveIn, RC);
    assert(OldFirstMI != fn.begin()->begin() &&
           "copyRetToReg didn't insert anything!");
  }

  // Number MachineInstrs and MachineBasicBlocks.
  // Initialize MBB indexes to a sentinal.
  MBB2IdxMap.resize(mf_->getNumBlockIDs(), ~0U);
  
  unsigned MIIndex = 0;
  for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
       MBB != E; ++MBB) {
    // Set the MBB2IdxMap entry for this MBB.
    MBB2IdxMap[MBB->getNumber()] = MIIndex;
    
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
         I != E; ++I) {
      bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
      assert(inserted && "multiple MachineInstr -> index mappings");
      i2miMap_.push_back(I);
      MIIndex += InstrSlots::NUM;
    }
  }

  // Note intervals due to live-in values.
  if (fn.livein_begin() != fn.livein_end()) {
    MachineBasicBlock *Entry = fn.begin();
    for (MachineFunction::livein_iterator I = fn.livein_begin(),
           E = fn.livein_end(); I != E; ++I) {
      handlePhysicalRegisterDef(Entry, Entry->begin(), 0,
                                getOrCreateInterval(I->first), 0);
      for (const unsigned* AS = mri_->getAliasSet(I->first); *AS; ++AS)
        handlePhysicalRegisterDef(Entry, Entry->begin(), 0,
                                  getOrCreateInterval(*AS), 0);
    }
  }

  computeIntervals();

  numIntervals += getNumIntervals();

  DOUT << "********** INTERVALS **********\n";
  for (iterator I = begin(), E = end(); I != E; ++I) {
    I->second.print(DOUT, mri_);
    DOUT << "\n";
  }

  // Join (coallesce) intervals if requested.
  if (EnableJoining) joinIntervals();

  numIntervalsAfter += getNumIntervals();
  

  // perform a final pass over the instructions and compute spill
  // weights, coalesce virtual registers and remove identity moves.
  const LoopInfo &loopInfo = getAnalysis<LoopInfo>();

  for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
       mbbi != mbbe; ++mbbi) {
    MachineBasicBlock* mbb = mbbi;
    unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());

    for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
         mii != mie; ) {
      // if the move will be an identity move delete it
      unsigned srcReg, dstReg, RegRep;
      if (tii_->isMoveInstr(*mii, srcReg, dstReg) &&
          (RegRep = rep(srcReg)) == rep(dstReg)) {
        // remove from def list
        getOrCreateInterval(RegRep);
        RemoveMachineInstrFromMaps(mii);
        mii = mbbi->erase(mii);
        ++numPeep;
      }
      else {
        for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
          const MachineOperand &mop = mii->getOperand(i);
          if (mop.isRegister() && mop.getReg() &&
              MRegisterInfo::isVirtualRegister(mop.getReg())) {
            // replace register with representative register
            unsigned reg = rep(mop.getReg());
            mii->getOperand(i).setReg(reg);

            LiveInterval &RegInt = getInterval(reg);
            RegInt.weight +=