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/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetRegisterInfo.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>
using namespace llvm;

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

static cl::opt<bool> SplitAtBB("split-intervals-at-bb", 
                               cl::init(true), cl::Hidden);
static cl::opt<int> SplitLimit("split-limit",
                               cl::init(-1), cl::Hidden);

STATISTIC(numIntervals, "Number of original intervals");
STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
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.addPreserved<LiveVariables>();
  AU.addRequired<LiveVariables>();
  AU.addPreservedID(MachineLoopInfoID);
  AU.addPreservedID(MachineDominatorsID);
  AU.addPreservedID(PHIEliminationID);
  AU.addRequiredID(PHIEliminationID);
  AU.addRequiredID(TwoAddressInstructionPassID);
  MachineFunctionPass::getAnalysisUsage(AU);
}

void LiveIntervals::releaseMemory() {
  MBB2IdxMap.clear();
  Idx2MBBMap.clear();
  mi2iMap_.clear();
  i2miMap_.clear();
  r2iMap_.clear();
  // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
  VNInfoAllocator.Reset();
  for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
    mf_->DeleteMachineInstr(ClonedMIs[i]);
}

void LiveIntervals::computeNumbering() {
  Index2MiMap OldI2MI = i2miMap_;
  
  Idx2MBBMap.clear();
  MBB2IdxMap.clear();
  mi2iMap_.clear();
  i2miMap_.clear();
  
  // Number MachineInstrs and MachineBasicBlocks.
  // Initialize MBB indexes to a sentinal.
  MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
  
  unsigned MIIndex = 0;
  for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
       MBB != E; ++MBB) {
    unsigned StartIdx = 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;
    }
    
    if (StartIdx == MIIndex) {
      // Empty MBB
      MIIndex += InstrSlots::NUM;
      i2miMap_.push_back(0);
    }
    // Set the MBB2IdxMap entry for this MBB.
    MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
    Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
  }
  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
  
  if (!OldI2MI.empty())
    for (iterator I = begin(), E = end(); I != E; ++I)
      for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end();
           LI != LE; ++LI) {
        
        // Remap the start index of the live range to the corresponding new
        // number, or our best guess at what it _should_ correspond to if the
        // original instruction has been erased.  This is either the following
        // instruction or its predecessor.
        unsigned offset = LI->start % InstrSlots::NUM;
        if (OldI2MI[LI->start / InstrSlots::NUM])
          LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset;
        else {
          unsigned i = 0;
          MachineInstr* newInstr = 0;
          do {
            newInstr = OldI2MI[LI->start / InstrSlots::NUM + i];
            i++;
          } while (!newInstr);
          
          if (mi2iMap_[newInstr] ==
              MBB2IdxMap[newInstr->getParent()->getNumber()].first)
            LI->start = mi2iMap_[newInstr];
          else
            LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
        }
        
        // Remap the ending index in the same way that we remapped the start,
        // except for the final step where we always map to the immediately
        // following instruction.
        if (LI->end / InstrSlots::NUM < OldI2MI.size()) {
          offset = LI->end % InstrSlots::NUM;
          if (OldI2MI[LI->end / InstrSlots::NUM])
            LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset;
          else {
            unsigned i = 0;
            MachineInstr* newInstr = 0;
            do {
              newInstr = OldI2MI[LI->end / InstrSlots::NUM + i];
              i++;
            } while (!newInstr);
            
            LI->end = mi2iMap_[newInstr];
          }
        } else {
          LI->end = i2miMap_.size() * InstrSlots::NUM;
        }
        
        // Remap the VNInfo def index, which works the same as the
        // start indices above.
        VNInfo* vni = LI->valno;
        offset = vni->def % InstrSlots::NUM;
        if (OldI2MI[vni->def / InstrSlots::NUM])
          vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset;
        else {
          unsigned i = 0;
          MachineInstr* newInstr = 0;
          do {
            newInstr = OldI2MI[vni->def / InstrSlots::NUM + i];
            i++;
          } while (!newInstr);
          
          if (mi2iMap_[newInstr] ==
              MBB2IdxMap[newInstr->getParent()->getNumber()].first)
            vni->def = mi2iMap_[newInstr];
          else
            vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset;
        }
        
        // Remap the VNInfo kill indices, which works the same as
        // the end indices above.
        for (size_t i = 0; i < vni->kills.size(); ++i) {
          offset = vni->kills[i] % InstrSlots::NUM;
          if (OldI2MI[vni->kills[i] / InstrSlots::NUM])
            vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] +
                            offset;
          else {
            unsigned e = 0;
            MachineInstr* newInstr = 0;
            do {
              newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e];
              e++;
            } while (!newInstr);
            
            vni->kills[i] = mi2iMap_[newInstr];
          }