SimpleRegisterCoalescing.cpp

Go to the documentation of this file.

//===-- SimpleRegisterCoalescing.cpp - Register Coalescing ----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a simple register coalescing pass that attempts to
// aggressively coalesce every register copy that it can.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regcoalescing"
#include "SimpleRegisterCoalescing.h"
#include "VirtRegMap.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/Value.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/RegisterCoalescer.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/SmallSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include <algorithm>
#include <cmath>
using namespace llvm;

STATISTIC(numJoins    , "Number of interval joins performed");
STATISTIC(numSubJoins , "Number of subclass joins performed");
STATISTIC(numCommutes , "Number of instruction commuting performed");
STATISTIC(numExtends  , "Number of copies extended");
STATISTIC(NumReMats   , "Number of instructions re-materialized");
STATISTIC(numPeep     , "Number of identity moves eliminated after coalescing");
STATISTIC(numAborts   , "Number of times interval joining aborted");

char SimpleRegisterCoalescing::ID = 0;
static cl::opt<bool>
EnableJoining("join-liveintervals",
              cl::desc("Coalesce copies (default=true)"),
              cl::init(true));

static cl::opt<bool>
NewHeuristic("new-coalescer-heuristic",
             cl::desc("Use new coalescer heuristic"),
             cl::init(false), cl::Hidden);

static cl::opt<bool>
CrossClassJoin("join-subclass-copies",
               cl::desc("Coalesce copies to sub- register class"),
               cl::init(false), cl::Hidden);

static RegisterPass<SimpleRegisterCoalescing> 
X("simple-register-coalescing", "Simple Register Coalescing");

// Declare that we implement the RegisterCoalescer interface
static RegisterAnalysisGroup<RegisterCoalescer, true/*The Default*/> V(X);

const PassInfo *const llvm::SimpleRegisterCoalescingID = &X;

void SimpleRegisterCoalescing::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<LiveIntervals>();
  AU.addPreserved<LiveIntervals>();
  AU.addRequired<MachineLoopInfo>();
  AU.addPreserved<MachineLoopInfo>();
  AU.addPreservedID(MachineDominatorsID);
  if (StrongPHIElim)
    AU.addPreservedID(StrongPHIEliminationID);
  else
    AU.addPreservedID(PHIEliminationID);
  AU.addPreservedID(TwoAddressInstructionPassID);
  MachineFunctionPass::getAnalysisUsage(AU);
}

/// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA
/// being the source and IntB being the dest, thus this defines a value number
/// in IntB.  If the source value number (in IntA) is defined by a copy from B,
/// see if we can merge these two pieces of B into a single value number,
/// eliminating a copy.  For example:
///
///  A3 = B0
///    ...
///  B1 = A3      <- this copy
///
/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1
/// value number to be replaced with B0 (which simplifies the B liveinterval).
///
/// This returns true if an interval was modified.
///
bool SimpleRegisterCoalescing::AdjustCopiesBackFrom(LiveInterval &IntA,
                                                    LiveInterval &IntB,
                                                    MachineInstr *CopyMI) {
  unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));

  // BValNo is a value number in B that is defined by a copy from A.  'B3' in
  // the example above.
  LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
  if (BLR == IntB.end()) // Should never happen!
    return false;
  VNInfo *BValNo = BLR->valno;
  
  // Get the location that B is defined at.  Two options: either this value has
  // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
  // can't process it.
  if (!BValNo->copy) return false;
  assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
  
  // AValNo is the value number in A that defines the copy, A3 in the example.
  LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
  if (ALR == IntA.end()) // Should never happen!
    return false;
  VNInfo *AValNo = ALR->valno;
  
  // If AValNo is defined as a copy from IntB, we can potentially process this.  
  // Get the instruction that defines this value number.
  unsigned SrcReg = li_->getVNInfoSourceReg(AValNo);
  if (!SrcReg) return false;  // Not defined by a copy.
    
  // If the value number is not defined by a copy instruction, ignore it.

  // If the source register comes from an interval other than IntB, we can't
  // handle this.
  if (SrcReg != IntB.reg) return false;
  
  // Get the LiveRange in IntB that this value number starts with.
  LiveInterval::iterator ValLR = IntB.FindLiveRangeContaining(AValNo->def-1);
  if (ValLR == IntB.end()) // Should never happen!
    return false;
  
  // Make sure that the end of the live range is inside the same block as
  // CopyMI.
  MachineInstr *ValLREndInst = li_->getInstructionFromIndex(ValLR->end-1);
  if (!ValLREndInst || 
      ValLREndInst->getParent() != CopyMI->getParent()) return false;

  // Okay, we now know that ValLR ends in the same block that the CopyMI
  // live-range starts.  If there are no intervening live ranges between them in
  // IntB, we can merge them.
  if (ValLR+1 != BLR) return false;

  // If a live interval is a physical register, conservatively check if any
  // of its sub-registers is overlapping the live interval of the virtual
  // register. If so, do not coalesce.
  if (TargetRegisterInfo::isPhysicalRegister(IntB.reg) &&
      *tri_->getSubRegisters(IntB.reg)) {
    for (const unsigned* SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR)
      if (li_->hasInterval(*SR) && IntA.overlaps(li_->getInterval(*SR))) {
        DOUT << "Interfere with sub-register ";
        DEBUG(li_->getInterval(*SR).print(DOUT, tri_));
        return false;
      }
  }
  
  DOUT << "\nExtending: "; IntB.print(DOUT, tri_);
  
  unsigned FillerStart = ValLR->end, FillerEnd = BLR->start;
  // We are about to delete CopyMI, so need to remove it as the 'instruction
  // that defines this value #'. Update the the valnum with the new defining
  // instruction #.
  BValNo->def  = FillerStart;
  BValNo->copy = NULL;
  
  // Okay, we can merge them.  We need to insert a new liverange:
  // [ValLR.end, BLR.begin) of either value number, then we merge the
  // two value numbers.
  IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo));

  // If the IntB live range is assigned to a physical register, and if that
  // physreg has aliases, 
  if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) {
    // Update the liveintervals of sub-registers.
    for (const unsigned *AS = tri_->getSubRegisters(IntB.reg); *AS; ++AS) {
      LiveInterval &AliasLI = li_->getInterval(*AS);
      AliasLI.addRange(LiveRange(FillerStart, FillerEnd,
              AliasLI.getNextValue(FillerStart, 0, li_->getVNInfoAllocator())));
    }
  }

  // Okay, merge "B1" into the same value number as "B0".
  if (BValNo != ValLR->valno) {
    IntB.addKills(ValLR->valno, BValNo->kills);
    IntB.MergeValueNumberInto(BValNo, ValLR->valno);
  }
  DOUT << "   result = "; IntB.print(DOUT, tri_);
  DOUT << "\n";

  // If the source instruction was killing the source register before the
  // merge, unset the isKill marker given the live range has been extended.
  int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true);
  if (UIdx != -1) {
    ValLREndInst->getOperand(UIdx).setIsKill(false);
    IntB.removeKill(ValLR->valno, FillerStart);
  }

  ++numExtends;
  return true;
}

/// HasOtherReachingDefs - Return true if there are definitions of IntB
/// other than BValNo val# that can reach uses of AValno val# of IntA.
bool SimpleRegisterCoalescing::HasOtherReachingDefs(LiveInterval &IntA,
                                                    LiveInterval &IntB,
                                                    VNInfo *AValNo,
                                                    VNInfo *BValNo) {
  for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
       AI != AE; ++AI) {
    if (AI->valno != AValNo) continue;
    LiveInterval::Ranges::iterator BI =
      std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start);
    if (BI != IntB.ranges.begin())
      --BI;
    for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) {
      if (BI->valno == BValNo)
        continue;
      if (BI->start <= AI->start && BI->end > AI->start)
        return true;
      if (BI->start > AI->start && BI->start < AI->end)
        return true;
    }
  }
  return false;
}

/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with IntA
/// being the source and IntB being the dest, thus this defines a value number
/// in IntB.  If the source value number (in IntA) is defined by a commutable
/// instruction and its other operand is coalesced to the copy dest register,
/// see if we can transform the copy into a noop by commuting the definition. For
/// example,
///
///  A3 = op A2 B0<kill>
///    ...
///  B1 = A3      <- this copy
///    ...
///     = op A3   <- more uses
///
/// ==>
///
///  B2 = op B0 A2<kill>
///    ...
///  B1 = B2      <- now an identify copy
///    ...
///     = op B2   <- more uses
///
/// This returns true if an interval was modified.
///
bool SimpleRegisterCoalescing::RemoveCopyByCommutingDef(LiveInterval &IntA,
                                                        LiveInterval &IntB,
                                                        MachineInstr *CopyMI) {
  unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));

  // FIXME: For now, only eliminate the copy by commuting its def when the
  // source register is a virtual register. We want to guard against cases
  // where the copy is a back edge copy and commuting the def lengthen the
  // live interval of the source register to the entire loop.
  if (TargetRegisterInfo::isPhysicalRegister(IntA.reg))
    return false;

  // BValNo is a value number in B that is defined by a copy from A. 'B3' in
  // the example above.
  LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx);
  if (BLR == IntB.end()) // Should never happen!
    return false;
  VNInfo *BValNo = BLR->valno;
  
  // Get the location that B is defined at.  Two options: either this value has
  // an unknown definition point or it is defined at CopyIdx.  If unknown, we 
  // can't process it.
  if (!BValNo->copy) return false;
  assert(BValNo->def == CopyIdx && "Copy doesn't define the value?");
  
  // AValNo is the value number in A that defines the copy, A3 in the example.
  LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyIdx-1);
  if (ALR == IntA.end()) // Should never happen!
    return false;
  VNInfo *AValNo = ALR->valno;
  // If other defs can reach uses of this def, then it's not safe to perform
  // the optimization.
  if (AValNo->def == ~0U || AValNo->def == ~1U || AValNo->hasPHIKill)
    return false;
  MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def);
  const TargetInstrDesc &TID = DefMI->getDesc();
  unsigned NewDstIdx;
  if (!TID.isCommutable() ||
      !tii_->CommuteChangesDestination(DefMI, NewDstIdx))
    return false;

  MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx);
  unsigned NewReg = NewDstMO.getReg();
  if (NewReg != IntB.reg || !NewDstMO.isKill())
    return false;

  // Make sure there are no other definitions of IntB that would reach the
  // uses which the new definition can reach.
  if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo))
    return false;

  // If some of the uses of IntA.reg is already coalesced away, return false.
  // It's not possible to determine whether it's safe to perform the coalescing.
  for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
         UE = mri_->use_end(); UI != UE; ++UI) {
    MachineInstr *UseMI = &*UI;
    unsigned UseIdx = li_->getInstructionIndex(UseMI);
    LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
    if (ULR == IntA.end())
      continue;
    if (ULR->valno == AValNo && JoinedCopies.count(UseMI))
      return false;
  }

  // At this point we have decided that it is legal to do this
  // transformation.  Start by commuting the instruction.
  MachineBasicBlock *MBB = DefMI->getParent();
  MachineInstr *NewMI = tii_->commuteInstruction(DefMI);
  if (!NewMI)
    return false;
  if (NewMI != DefMI) {
    li_->ReplaceMachineInstrInMaps(DefMI, NewMI);
    MBB->insert(DefMI, NewMI);
    MBB->erase(DefMI);
  }
  unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false);
  NewMI->getOperand(OpIdx).setIsKill();

  bool BHasPHIKill = BValNo->hasPHIKill;
  SmallVector<VNInfo*, 4> BDeadValNos;
  SmallVector<unsigned, 4> BKills;
  std::map<unsigned, unsigned> BExtend;

  // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g.
  // A = or A, B
  // ...
  // B = A
  // ...
  // C = A<kill>
  // ...
  //   = B
  //
  // then do not add kills of A to the newly created B interval.
  bool Extended = BLR->end > ALR->end && ALR->end != ALR->start;
  if (Extended)
    BExtend[ALR->end] = BLR->end;

  // Update uses of IntA of the specific Val# with IntB.
  for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg),
         UE = mri_->use_end(); UI != UE;) {
    MachineOperand &UseMO = UI.getOperand();
    MachineInstr *UseMI = &*UI;
    ++UI;
    if (JoinedCopies.count(UseMI))
      continue;
    unsigned UseIdx = li_->getInstructionIndex(UseMI);
    LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx);
    if (ULR == IntA.end() || ULR->valno != AValNo)
      continue;
    UseMO.setReg(NewReg);
    if (UseMI == CopyMI)
      continue;
    if (UseMO.isKill()) {
      if (Extended)
        UseMO.setIsKill(false);
      else
        BKills.push_back(li_->getUseIndex(UseIdx)+1);
    }
    unsigned SrcReg, DstReg;
    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg))
      continue;
    if (DstReg == IntB.reg) {
      // This copy will become a noop. If it's defining a new val#,
      // remove that val# as well. However this live range is being
      // extended to the end of the existing live range defined by the copy.
      unsigned DefIdx = li_->getDefIndex(UseIdx);
      const LiveRange *DLR = IntB.getLiveRangeContaining(DefIdx);
      BHasPHIKill |= DLR->valno->hasPHIKill;
      assert(DLR->valno->def == DefIdx);
      BDeadValNos.push_back(DLR->valno);
      BExtend[DLR->start] = DLR->end;
      JoinedCopies.insert(UseMI);
      // If this is a kill but it's going to be removed, the last use
      // of the same val# is the new kill.
      if (UseMO.isKill())
        BKills.pop_back();
    }
  }

  // We need to insert a new liverange: [ALR.start, LastUse). It may be we can
  // simply extend BLR if CopyMI doesn't end the range.
  DOUT << "\nExtending: "; IntB.print(DOUT, tri_);

  // Remove val#'s defined by copies that will be coalesced away.
  for (unsigned i = 0, e = BDeadValNos.size(); i != e; ++i)
    IntB.removeValNo(BDeadValNos[i]);

  // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition
  // is updated. Kills are also updated.
  VNInfo *ValNo = BValNo;
  ValNo->def = AValNo->def;
  ValNo->copy = NULL;
  for (unsigned j = 0, ee = ValNo->kills.size(); j != ee; ++j) {
    unsigned Kill = ValNo->kills[j];
    if (Kill != BLR->end)
      BKills.push_back(Kill);
  }
  ValNo->kills.clear();
  for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end();
       AI != AE; ++AI) {
    if (AI->valno != AValNo) continue;
    unsigned End = AI->end;
    std::map<unsigned, unsigned>::iterator EI = BExtend.find(End);
    if (EI != BExtend.end())
      End = EI->second;
    IntB.addRange(LiveRange(AI->start, End, ValNo));
  }
  IntB.addKills(ValNo, BKills);
  ValNo->hasPHIKill = BHasPHIKill;

  DOUT << "   result = "; IntB.print(DOUT, tri_);
  DOUT << "\n";

  DOUT << "\nShortening: "; IntA.print(DOUT, tri_);
  IntA.removeValNo(AValNo);
  DOUT << "   result = "; IntA.print(DOUT, tri_);
  DOUT << "\n";

  ++numCommutes;
  return true;
}

/// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial
/// computation, replace the copy by rematerialize the definition.
bool SimpleRegisterCoalescing::ReMaterializeTrivialDef(LiveInterval &SrcInt,
                                                       unsigned DstReg,
                                                       MachineInstr *CopyMI) {
  unsigned CopyIdx = li_->getUseIndex(li_->getInstructionIndex(CopyMI));
  LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx);
  if (SrcLR == SrcInt.end()) // Should never happen!
    return false;
  VNInfo *ValNo = SrcLR->valno;
  // If other defs can reach uses of this def, then it's not safe to perform
  // the optimization.
  if (ValNo->def == ~0U || ValNo->def == ~1U || ValNo->hasPHIKill)
    return false;
  MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def);
  const TargetInstrDesc &TID = DefMI->getDesc();
  if (!TID.isAsCheapAsAMove())
    return false;
  bool SawStore = false;
  if (!DefMI->isSafeToMove(tii_, SawStore))
    return false;

  unsigned DefIdx = li_->getDefIndex(CopyIdx);
  const LiveRange *DLR= li_->getInterval(DstReg).getLiveRangeContaining(DefIdx);
  DLR->valno->copy = NULL;

  MachineBasicBlock::iterator MII = CopyMI;
  MachineBasicBlock *MBB = CopyMI->getParent();
  tii_->reMaterialize(*MBB, MII, DstReg, DefMI);
  MachineInstr *NewMI = prior(MII);
  // CopyMI may have implicit instructions, transfer them over to the newly
  // rematerialized instruction. And update implicit def interval valnos.
  for (unsigned i = CopyMI->getDesc().getNumOperands(),
         e = CopyMI->getNumOperands(); i != e; ++i) {
    MachineOperand &MO = CopyMI->getOperand(i);
    if (MO.isReg() && MO.isImplicit())
      NewMI->addOperand(MO);
    if (MO.isDef() && li_->hasInterval(MO.getReg())) {
      unsigned Reg = MO.getReg();
      DLR = li_->getInterval(Reg).getLiveRangeContaining(DefIdx);
      if (DLR && DLR->valno->copy == CopyMI)
        DLR->valno->copy = NULL;
    }
  }

  li_->ReplaceMachineInstrInMaps(CopyMI, NewMI);
  CopyMI->eraseFromParent();
  ReMatCopies.insert(CopyMI);
  ReMatDefs.insert(DefMI);
  ++NumReMats;
  return true;
}

/// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
///
bool SimpleRegisterCoalescing::isBackEdgeCopy(MachineInstr *CopyMI,
                                              unsigned DstReg) const {
  MachineBasicBlock *MBB = CopyMI->getParent();
  const MachineLoop *L = loopInfo->getLoopFor(MBB);
  if (!L)
    return false;
  if (MBB != L->getLoopLatch())
    return false;

  LiveInterval &LI = li_->getInterval(DstReg);
  unsigned DefIdx = li_->getInstructionIndex(CopyMI);
  LiveInterval::const_iterator DstLR =
    LI.FindLiveRangeContaining(li_->getDefIndex(DefIdx));
  if (DstLR == LI.end())
    return false;
  unsigned KillIdx = li_->getMBBEndIdx(MBB) + 1;
  if (DstLR->valno->kills.size() == 1 &&
      DstLR->valno->kills[0] == KillIdx && DstLR->valno->hasPHIKill)
    return true;
  return false;
}

/// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and
/// update the subregister number if it is not zero. If DstReg is a
/// physical register and the existing subregister number of the def / use
/// being updated is not zero, make sure to set it to the correct physical
/// subregister.
void
SimpleRegisterCoalescing::UpdateRegDefsUses(unsigned SrcReg, unsigned DstReg,
                                            unsigned SubIdx) {
  bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg);
  if (DstIsPhys && SubIdx) {
    // Figure out the real physical register we are updating with.
    DstReg = tri_->getSubReg(DstReg, SubIdx);
    SubIdx = 0;
  }

  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg),
         E = mri_->reg_end(); I != E; ) {
    MachineOperand &O = I.getOperand();
    MachineInstr *UseMI = &*I;
    ++I;
    unsigned OldSubIdx = O.getSubReg();
    if (DstIsPhys) {
      unsigned UseDstReg = DstReg;
      if (OldSubIdx)
          UseDstReg = tri_->getSubReg(DstReg, OldSubIdx);

      unsigned CopySrcReg, CopyDstReg;
      if (tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
          CopySrcReg != CopyDstReg &&
          CopySrcReg == SrcReg && CopyDstReg != UseDstReg) {
        // If the use is a copy and it won't be coalesced away, and its source
        // is defined by a trivial computation, try to rematerialize it instead.
        if (ReMaterializeTrivialDef(li_->getInterval(SrcReg), CopyDstReg,UseMI))
          continue;
      }

      O.setReg(UseDstReg);
      O.setSubReg(0);
      continue;
    }

    // Sub-register indexes goes from small to large. e.g.
    // RAX: 1 -> AL, 2 -> AX, 3 -> EAX
    // EAX: 1 -> AL, 2 -> AX
    // So RAX's sub-register 2 is AX, RAX's sub-regsiter 3 is EAX, whose
    // sub-register 2 is also AX.
    if (SubIdx && OldSubIdx && SubIdx != OldSubIdx)
      assert(OldSubIdx < SubIdx && "Conflicting sub-register index!");
    else if (SubIdx)
      O.setSubReg(SubIdx);
    // Remove would-be duplicated kill marker.
    if (O.isKill() && UseMI->killsRegister(DstReg))
      O.setIsKill(false);
    O.setReg(DstReg);

    // After updating the operand, check if the machine instruction has
    // become a copy. If so, update its val# information.
    const TargetInstrDesc &TID = UseMI->getDesc();
    unsigned CopySrcReg, CopyDstReg;
    if (TID.getNumDefs() == 1 && TID.getNumOperands() > 2 &&
        tii_->isMoveInstr(*UseMI, CopySrcReg, CopyDstReg) &&
        CopySrcReg != CopyDstReg &&
        (TargetRegisterInfo::isVirtualRegister(CopyDstReg) ||
         allocatableRegs_[CopyDstReg])) {
      LiveInterval &LI = li_->getInterval(CopyDstReg);
      unsigned DefIdx = li_->getDefIndex(li_->getInstructionIndex(UseMI));
      const LiveRange *DLR = LI.getLiveRangeContaining(DefIdx);
      if (DLR->valno->def == DefIdx)
        DLR->valno->copy = UseMI;
    }
  }
}

/// RemoveDeadImpDef - Remove implicit_def instructions which are "re-defining"
/// registers due to insert_subreg coalescing. e.g.
/// r1024 = op
/// r1025 = implicit_def
/// r1025 = insert_subreg r1025, r1024
///       = op r1025
/// =>
/// r1025 = op
/// r1025 = implicit_def
/// r1025 = insert_subreg r1025, r1025
///       = op r1025
void
SimpleRegisterCoalescing::RemoveDeadImpDef(unsigned Reg, LiveInterval &LI) {
  for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
         E = mri_->reg_end(); I != E; ) {
    MachineOperand &O = I.getOperand();
    MachineInstr *DefMI = &*I;
    ++I;
    if (!O.isDef())
      continue;
    if (DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF)
      continue;
    if (!LI.liveBeforeAndAt(li_->getInstructionIndex(DefMI)))
      continue;
    li_->RemoveMachineInstrFromMaps(DefMI);
    DefMI->eraseFromParent();
  }
}

/// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate
/// due to live range lengthening as the result of coalescing.
void SimpleRegisterCoalescing::RemoveUnnecessaryKills(unsigned Reg,
                                                      LiveInterval &LI) {
  for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(Reg),
         UE = mri_->use_end(); UI != UE; ++UI) {
    MachineOperand &UseMO = UI.getOperand();
    if (UseMO.isKill()) {
      MachineInstr *UseMI = UseMO.getParent();
      unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
      if (JoinedCopies.count(UseMI))
        continue;
      const LiveRange *UI = LI.getLiveRangeContaining(UseIdx);
      if (!UI || !LI.isKill(UI->valno, UseIdx+1))
        UseMO.setIsKill(false);
    }
  }
}

/// removeRange - Wrapper for LiveInterval::removeRange. This removes a range
/// from a physical register live interval as well as from the live intervals
/// of its sub-registers.
static void removeRange(LiveInterval &li, unsigned Start, unsigned End,
                        LiveIntervals *li_, const TargetRegisterInfo *tri_) {
  li.removeRange(Start, End, true);
  if (TargetRegisterInfo::isPhysicalRegister(li.reg)) {
    for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
      if (!li_->hasInterval(*SR))
        continue;
      LiveInterval &sli = li_->getInterval(*SR);
      unsigned RemoveEnd = Start;
      while (RemoveEnd != End) {
        LiveInterval::iterator LR = sli.FindLiveRangeContaining(Start);
        if (LR == sli.end())
          break;
        RemoveEnd = (LR->end < End) ? LR->end : End;
        sli.removeRange(Start, RemoveEnd, true);
        Start = RemoveEnd;
      }
    }
  }
}

/// removeIntervalIfEmpty - Check if the live interval of a physical register
/// is empty, if so remove it and also remove the empty intervals of its
/// sub-registers. Return true if live interval is removed.
static bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_,
                                  const TargetRegisterInfo *tri_) {
  if (li.empty()) {
    if (TargetRegisterInfo::isPhysicalRegister(li.reg))
      for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) {
        if (!li_->hasInterval(*SR))
          continue;
        LiveInterval &sli = li_->getInterval(*SR);
        if (sli.empty())
          li_->removeInterval(*SR);
      }
    li_->removeInterval(li.reg);
    return true;
  }
  return false;
}

/// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy.
/// Return true if live interval is removed.
bool SimpleRegisterCoalescing::ShortenDeadCopyLiveRange(LiveInterval &li,
                                                        MachineInstr *CopyMI) {
  unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
  LiveInterval::iterator MLR =
    li.FindLiveRangeContaining(li_->getDefIndex(CopyIdx));
  if (MLR == li.end())
    return false;  // Already removed by ShortenDeadCopySrcLiveRange.
  unsigned RemoveStart = MLR->start;
  unsigned RemoveEnd = MLR->end;
  // Remove the liverange that's defined by this.
  if (RemoveEnd == li_->getDefIndex(CopyIdx)+1) {
    removeRange(li, RemoveStart, RemoveEnd, li_, tri_);
    return removeIntervalIfEmpty(li, li_, tri_);
  }
  return false;
}

/// PropagateDeadness - Propagate the dead marker to the instruction which
/// defines the val#.
static void PropagateDeadness(LiveInterval &li, MachineInstr *CopyMI,
                              unsigned &LRStart, LiveIntervals *li_,
                              const TargetRegisterInfo* tri_) {
  MachineInstr *DefMI =
    li_->getInstructionFromIndex(li_->getDefIndex(LRStart));
  if (DefMI && DefMI != CopyMI) {
    int DeadIdx = DefMI->findRegisterDefOperandIdx(li.reg, false, tri_);
    if (DeadIdx != -1) {
      DefMI->getOperand(DeadIdx).setIsDead();
      // A dead def should have a single cycle interval.
      ++LRStart;
    }
  }
}

/// isSameOrFallThroughBB - Return true if MBB == SuccMBB or MBB simply
/// fallthoughs to SuccMBB.
static bool isSameOrFallThroughBB(MachineBasicBlock *MBB,
                                  MachineBasicBlock *SuccMBB,
                                  const TargetInstrInfo *tii_) {
  if (MBB == SuccMBB)
    return true;
  MachineBasicBlock *TBB = 0, *FBB = 0;
  SmallVector<MachineOperand, 4> Cond;
  return !tii_->AnalyzeBranch(*MBB, TBB, FBB, Cond) && !TBB && !FBB &&
    MBB->isSuccessor(SuccMBB);
}

/// ShortenDeadCopySrcLiveRange - Shorten a live range as it's artificially
/// extended by a dead copy. Mark the last use (if any) of the val# as kill as
/// ends the live range there. If there isn't another use, then this live range
/// is dead. Return true if live interval is removed.
bool
SimpleRegisterCoalescing::ShortenDeadCopySrcLiveRange(LiveInterval &li,
                                                      MachineInstr *CopyMI) {
  unsigned CopyIdx = li_->getInstructionIndex(CopyMI);
  if (CopyIdx == 0) {
    // FIXME: special case: function live in. It can be a general case if the
    // first instruction index starts at > 0 value.
    assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
    // Live-in to the function but dead. Remove it from entry live-in set.
    if (mf_->begin()->isLiveIn(li.reg))
      mf_->begin()->removeLiveIn(li.reg);
    const LiveRange *LR = li.getLiveRangeContaining(CopyIdx);
    removeRange(li, LR->start, LR->end, li_, tri_);
    return removeIntervalIfEmpty(li, li_, tri_);
  }

  LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx-1);
  if (LR == li.end())
    // Livein but defined by a phi.
    return false;

  unsigned RemoveStart = LR->start;
  unsigned RemoveEnd = li_->getDefIndex(CopyIdx)+1;
  if (LR->end > RemoveEnd)
    // More uses past this copy? Nothing to do.
    return false;

  MachineBasicBlock *CopyMBB = CopyMI->getParent();
  unsigned MBBStart = li_->getMBBStartIdx(CopyMBB);
  unsigned LastUseIdx;
  MachineOperand *LastUse = lastRegisterUse(LR->start, CopyIdx-1, li.reg,
                                            LastUseIdx);
  if (LastUse) {
    MachineInstr *LastUseMI = LastUse->getParent();
    if (!isSameOrFallThroughBB(LastUseMI->getParent(), CopyMBB, tii_)) {
      // r1024 = op
      // ...
      // BB1:
      //       = r1024
      //
      // BB2:
      // r1025<dead> = r1024<kill>
      if (MBBStart < LR->end)
        removeRange(li, MBBStart, LR->end, li_, tri_);
      return false;
    }

    // There are uses before the copy, just shorten the live range to the end
    // of last use.
    LastUse->setIsKill();
    removeRange(li, li_->getDefIndex(LastUseIdx), LR->end, li_, tri_);
    unsigned SrcReg, DstReg;
    if (tii_->isMoveInstr(*LastUseMI, SrcReg, DstReg) &&
        DstReg == li.reg) {
      // Last use is itself an identity code.
      int DeadIdx = LastUseMI->findRegisterDefOperandIdx(li.reg, false, tri_);
      LastUseMI->getOperand(DeadIdx).setIsDead();
    }
    return false;
  }

  // Is it livein?
  if (LR->start <= MBBStart && LR->end > MBBStart) {
    if (LR->start == 0) {
      assert(TargetRegisterInfo::isPhysicalRegister(li.reg));
      // Live-in to the function but dead. Remove it from entry live-in set.
      mf_->begin()->removeLiveIn(li.reg);
    }
    // FIXME: Shorten intervals in BBs that reaches this BB.
  }

  if (LR->valno->def == RemoveStart)
    // If the def MI defines the val#, propagate the dead marker.
    PropagateDeadness(li, CopyMI, RemoveStart, li_, tri_);

  removeRange(li, RemoveStart, LR->end, li_, tri_);
  return removeIntervalIfEmpty(li, li_, tri_);
}

/// CanCoalesceWithImpDef - Returns true if the specified copy instruction
/// from an implicit def to another register can be coalesced away.
bool SimpleRegisterCoalescing::CanCoalesceWithImpDef(MachineInstr *CopyMI,
                                                     LiveInterval &li,
                                                     LiveInterval &ImpLi) const{
  if (!CopyMI->killsRegister(ImpLi.reg))
    return false;
  unsigned CopyIdx = li_->getDefIndex(li_->getInstructionIndex(CopyMI));
  LiveInterval::iterator LR = li.FindLiveRangeContaining(CopyIdx);
  if (LR == li.end())
    return false;
  if (LR->valno->hasPHIKill)
    return false;
  if (LR->valno->def != CopyIdx)
    return false;
  // Make sure all of val# uses are copies.
  for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(li.reg),
         UE = mri_->use_end(); UI != UE;) {
    MachineInstr *UseMI = &*UI;
    ++UI;
    if (JoinedCopies.count(UseMI))
      continue;
    unsigned UseIdx = li_->getUseIndex(li_->getInstructionIndex(UseMI));
    LiveInterval::iterator ULR = li.FindLiveRangeContaining(UseIdx);
    if (ULR == li.end() || ULR->valno != LR->valno)
      continue;
    // If the use is not a use, then it's not safe to coalesce the move.
    unsigned SrcReg, DstReg;
    if (!tii_->isMoveInstr(*UseMI, SrcReg, DstReg)) {
      if (UseMI->getOpcode() == TargetInstrInfo::INSERT_SUBREG &&
          UseMI->getOperand(1).getReg() == li.reg)
        continue;
      return false;
    }
  }
  return true;
}


/// RemoveCopiesFromValNo - The specified value# is defined by an implicit
/// def and it is being removed. Turn all copies from this value# into
/// identity copies so they will be removed.
void SimpleRegisterCoalescing::RemoveCopiesFromValNo(LiveInterval &li,
                                                     VNInfo *VNI) {
  SmallVector<MachineInstr*, 4> ImpDefs;
  MachineOperand *LastUse = NULL;
  unsigned LastUseIdx = li_->getUseIndex(VNI->def);
  for (