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/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/PseudoSourceValue.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/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);

static cl::opt<bool> EnableAggressiveRemat("aggressive-remat", 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.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);
  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;
  
  MBB2IdxMap.clear();
  Idx2MBBMap.clear();
  mi2iMap_.clear();
  i2miMap_.clear();
  r2iMap_.clear();
  // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
  VNInfoAllocator.Reset();
  while (!ClonedMIs.empty()) {
    MachineInstr *MI = ClonedMIs.back();
    ClonedMIs.pop_back();
    mf_->DeleteMachineInstr(MI);
  }
}

void LiveIntervals::computeNumbering() {
  Index2MiMap OldI2MI = i2miMap_;
  std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap;
  
  Idx2MBBMap.clear();
  MBB2IdxMap.clear();
  mi2iMap_.clear();
  i2miMap_.clear();
  
  FunctionSize = 0;
  
  // 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;

    // Insert an empty slot at the beginning of each block.
    MIIndex += InstrSlots::NUM;
    i2miMap_.push_back(0);

    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");
      inserted = true;
      i2miMap_.push_back(I);
      MIIndex += InstrSlots::NUM;
      FunctionSize++;
      
      // Insert max(1, numdefs) empty slots after every instruction.
      unsigned Slots = I->getDesc().getNumDefs();
      if (Slots == 0)
        Slots = 1;
      MIIndex += InstrSlots::NUM * Slots;
      while (Slots--)
        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 OI = begin(), OE = end(); OI != OE; ++OI) {
      for (LiveInterval::iterator LI = OI->second->begin(),
           LE = OI->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 index = LI->start / InstrSlots::NUM;
        unsigned offset = LI->start % InstrSlots::NUM;
        if (offset == InstrSlots::LOAD) {
          std::vector<IdxMBBPair>::const_iterator I =
                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start);
          // Take the pair containing the index
          std::vector<IdxMBBPair>::const_iterator J =
                    (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I;
          
          LI->start = getMBBStartIdx(J->second);
        } else {
          LI->start = mi2iMap_[OldI2MI[index]] + 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.
        index = (LI->end - 1) / InstrSlots::NUM;
        offset  = LI->end % InstrSlots::NUM;
        if (offset == InstrSlots::LOAD) {
          // VReg dies at end of block.
          std::vector<IdxMBBPair>::const_iterator I =
                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
          --I;
          
          LI->end = getMBBEndIdx(I->second) + 1;
        } else {
          unsigned idx = index;
          while (index < OldI2MI.size() && !OldI2MI[index]) ++index;
          
          if (index != OldI2MI.size())
            LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0);
          else
            LI->end = InstrSlots::NUM * i2miMap_.size();
        }
      }
      
      for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(),
           VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 
        VNInfo* vni = *VNI;
        
        // Remap the VNInfo def index, which works the same as the
        // start indices above. VN's with special sentinel defs
        // don't need to be remapped.