path: root/lib/CodeGen/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>
#include <cmath>
#include <iostream>
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("Join compatible live intervals"),
                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
  unsigned miIndex = 0;
  for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end();
       mbb != mbbEnd; ++mbb)
    for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
         mi != miEnd; ++mi) {
      bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second;
      assert(inserted && "multiple MachineInstr -> index mappings");
      i2miMap_.push_back(mi);
      miIndex += InstrSlots::NUM;
    }

  // Note intervals due to live-in values.
  if (fn.livein_begin() != fn.livein_end()) {
    MachineBasicBlock *Entry = fn.begin();
    for (