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/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);

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.addRequired<AliasAnalysis>();
  AU.addPreserved<AliasAnalysis>();
  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();
  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");
      i2miMap_.push_back(I);
      MIIndex += InstrSlots::NUM;
      FunctionSize++;
      
      // Insert an empty slot after every instruction.
      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 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 || LI->valno->def == ~0U) {
          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() && I->first > index) ||
                    (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 (LI->valno->hasPHIKill && !OldI2MI[index]) {
          // Special handling for when this was previously killed by a PHI, but
          // the PHI has now been removed.  We need to trim the live interval
          // to die at the end of the preceding block.
          std::vector<IdxMBBPair>::const_iterator I =
                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
          // Take the pair containing the index
          std::vector<IdxMBBPair>::const_iterator J =
                    ((I != OldI2MBB.end() && I->first > index) ||
                    (I == OldI2MBB.end() && OldI2MBB.size()>0)) ? (I-1): I;
          
          MachineBasicBlock* StartMBB = J->second;
          MachineBasicBlock* CurrMBB = J->second;
          
          while (CurrMBB == StartMBB) {
            while (index > 0 && !OldI2MI[index]) --index;
            CurrMBB = OldI2MI[index]->getParent();
            if (!StartMBB) StartMBB = CurrMBB;
            
            --index;
          }
          
          LI->end = getMBBEndIdx(CurrMBB) + 1;
        } else if (offset == InstrSlots::USE) {
          std::vector<IdxMBBPair>::const_iterator I =
                  std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end);
          // Take the pair containing the index
          std::vector<IdxMBBPair>::const_iterator J =
                    ((I != OldI2MBB.end() && I->first > index) ||
                    (I == OldI2MBB.end() && OldI2MBB.size()>0)) ? (I-1): I;
          
          LI->end = getMBBEndIdx(J->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();