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

static cl::opt<bool> EarlyCoalescing("early-coalescing", cl::init(false));

static cl::opt<int> CoalescingLimit("early-coalescing-limit",
                                    cl::init(-1), cl::Hidden);

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

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);
  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();
  terminatorGaps.clear();
  phiJoinCopies.clear();

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

static bool CanTurnIntoImplicitDef(MachineInstr *MI, unsigned Reg,
                                   unsigned OpIdx, const TargetInstrInfo *tii_){
  unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
  if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg) &&
      Reg == SrcReg)
    return true;

  if (OpIdx == 2 && MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG)
    return true;
  if (OpIdx == 1 && MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
    return true;
  return false;
}

/// processImplicitDefs - Process IMPLICIT_DEF instructions and make sure
/// there is one implicit_def for each use. Add isUndef marker to
/// implicit_def defs and their uses.
void LiveIntervals::processImplicitDefs() {
  SmallSet<unsigned, 8> ImpDefRegs;
  SmallVector<MachineInstr*, 8> ImpDefMIs;
  MachineBasicBlock *Entry = mf_->begin();
  SmallPtrSet<MachineBasicBlock*,16> Visited;
  for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> >
         DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited);
       DFI != E; ++DFI) {
    MachineBasicBlock *MBB = *DFI;
    for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
         I != E; ) {
      MachineInstr *MI = &*I;
      ++I;
      if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) {
        unsigned Reg = MI->getOperand(0).getReg();
        ImpDefRegs.insert(Reg);
        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
          for (const unsigned *SS = tri_->getSubRegisters(Reg); *SS; ++SS)
            ImpDefRegs.insert(*SS);
        }
        ImpDefMIs.push_back(MI);
        continue;
      }

      if (MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG) {
        MachineOperand &MO = MI->getOperand(2);
        if (ImpDefRegs.count(MO.getReg())) {
          // %reg1032<def> = INSERT_SUBREG %reg1032, undef, 2
          // This is an identity copy, eliminate it now.
          if (MO.isKill()) {
            LiveVariables::VarInfo& vi = lv_->getVarInfo(MO.getReg());
            vi.removeKill(MI);
          }
          MI->eraseFromParent();
          continue;
        }
      }

      bool ChangedToImpDef = false;
      for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
        MachineOperand& MO = MI->getOperand(i);
        if (!MO.isReg() || !MO.isUse() || MO.isUndef())
          continue;
        unsigned Reg = MO.getReg();
        if (!Reg)
          continue;
        if (!ImpDefRegs.count(Reg))
          continue;
        // Use is a copy, just turn it into an implicit_def.
        if (CanTurnIntoImplicitDef(MI, Reg, i, tii_)) {
          bool isKill = MO.isKill();
          MI->setDesc(tii_->get(TargetInstrInfo::IMPLICIT_DEF));
          for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j)
            MI->RemoveOperand(j);
          if (isKill) {
            ImpDefRegs.erase(Reg);
            LiveVariables::VarInfo& vi = lv_->getVarInfo(Reg);
            vi.removeKill(MI);
          }
          ChangedToImpDef = true;
          break;
        }

        MO.setIsUndef();
        if (MO.isKill() || MI->isRegTiedToDefOperand(i)) {
          // Make sure other uses of 
          for (unsigned j = i+1; j != e; ++j) {
            MachineOperand &MOJ = MI->getOperand(j);
            if (MOJ.isReg() && MOJ.isUse() && MOJ.getReg() == Reg)
              MOJ.setIsUndef();
          }
          ImpDefRegs.erase(Reg);
        }
      }