LiveIntervalAnalysis.cpp

//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file 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/AliasAnalysis.h"
#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/ProcessImplicitDefs.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <limits>
#include <cmath>
using namespace llvm;

// Hidden options for help debugging.
static cl::opt<bool> DisableReMat("disable-rematerialization", 
                                  cl::init(false), cl::Hidden);

static cl::opt<bool> EnableFastSpilling("fast-spill",
                                        cl::init(false), cl::Hidden);

STATISTIC(numIntervals , "Number of original intervals");
STATISTIC(numFolds     , "Number of loads/stores folded into instructions");
STATISTIC(numSplits    , "Number of intervals split");

char LiveIntervals::ID = 0;
static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");

void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesCFG();
  AU.addRequired<AliasAnalysis>();
  AU.addPreserved<AliasAnalysis>();
  AU.addPreserved<LiveVariables>();
  AU.addRequired<LiveVariables>();
  AU.addPreservedID(MachineLoopInfoID);
  AU.addPreservedID(MachineDominatorsID);
  
  if (!StrongPHIElim) {
    AU.addPreservedID(PHIEliminationID);
    AU.addRequiredID(PHIEliminationID);
  }
  
  AU.addRequiredID(TwoAddressInstructionPassID);
  AU.addPreserved<ProcessImplicitDefs>();
  AU.addRequired<ProcessImplicitDefs>();
  AU.addPreserved<SlotIndexes>();
  AU.addRequiredTransitive<SlotIndexes>();
  MachineFunctionPass::getAnalysisUsage(AU);
}

void LiveIntervals::releaseMemory() {
  // Free the live intervals themselves.
  for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
       E = r2iMap_.end(); I != E; ++I)
    delete I->second;
  
  r2iMap_.clear();

  // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
  VNInfoAllocator.DestroyAll();
  while (!CloneMIs.empty()) {
    MachineInstr *MI = CloneMIs.back();
    CloneMIs.pop_back();
    mf_->DeleteMachineInstr(MI);
  }
}

/// runOnMachineFunction - Register allocate the whole function
///
bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
  mf_ = &fn;
  mri_ = &mf_->getRegInfo();
  tm_ = &fn.getTarget();
  tri_ = tm_->getRegisterInfo();
  tii_ = tm_->getInstrInfo();
  aa_ = &getAnalysis<AliasAnalysis>();
  lv_ = &getAnalysis<LiveVariables>();
  indexes_ = &getAnalysis<SlotIndexes>();
  allocatableRegs_ = tri_->getAllocatableSet(fn);

  computeIntervals();

  numIntervals += getNumIntervals();

  DEBUG(dump());
  return true;
}

/// print - Implement the dump method.
void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
  OS << "********** INTERVALS **********\n";
  for (const_iterator I = begin(), E = end(); I != E; ++I) {
    I->second->print(OS, tri_);
    OS << "\n";
  }

  printInstrs(OS);
}

void LiveIntervals::printInstrs(raw_ostream &OS) const {
  OS << "********** MACHINEINSTRS **********\n";

  for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
       mbbi != mbbe; ++mbbi) {
    OS << "BB#" << mbbi->getNumber()
       << ":\t\t# derived from " << mbbi->getName() << "\n";
    for (MachineBasicBlock::iterator mii = mbbi->begin(),
           mie = mbbi->end(); mii != mie; ++mii) {
      if (mii->isDebugValue())
        OS << "    \t" << *mii;
      else
        OS << getInstructionIndex(mii) << '\t' << *mii;
    }
  }
}

void LiveIntervals::dumpInstrs() const {
  printInstrs(dbgs());
}

bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,
                                         VirtRegMap &vrm, unsigned reg) {
  // We don't handle fancy stuff crossing basic block boundaries
  if (li.ranges.size() != 1)
    return true;
  const LiveRange &range = li.ranges.front();
  SlotIndex idx = range.start.getBaseIndex();
  SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();

  // Skip deleted instructions
  MachineInstr *firstMI = getInstructionFromIndex(idx);
  while (!firstMI && idx != end) {
    idx = idx.getNextIndex();
    firstMI = getInstructionFromIndex(idx);
  }
  if (!firstMI)
    return false;

  // Find last instruction in range
  SlotIndex lastIdx = end.getPrevIndex();
  MachineInstr *lastMI = getInstructionFromIndex(lastIdx);
  while (!lastMI && lastIdx != idx) {
    lastIdx = lastIdx.getPrevIndex();
    lastMI = getInstructionFromIndex(lastIdx);
  }
  if (!lastMI)
    return false;

  // Range cannot cross basic block boundaries or terminators
  MachineBasicBlock *MBB = firstMI->getParent();
  if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())
    return true;

  MachineBasicBlock::const_iterator E = lastMI;
  ++E;
  for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {
    const MachineInstr &MI = *I;

    // Allow copies to and from li.reg
    unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
    if (tii_->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
      if (SrcReg == li.reg || DstReg == li.reg)
        continue;

    // Check for operands using reg
    for (unsigned i = 0, e = MI.getNumOperands(); i != e;  ++i) {