path: root/lib/CodeGen/SplitKit.cpp

//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains the SplitAnalysis class as well as mutator functions for
// live range splitting.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "regalloc"
#include "SplitKit.h"
#include "LiveRangeEdit.h"
#include "VirtRegMap.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/CalcSpillWeights.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"

using namespace llvm;

static cl::opt<bool>
AllowSplit("spiller-splits-edges",
           cl::desc("Allow critical edge splitting during spilling"));

STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple,   "Number of splits that were simple");

//===----------------------------------------------------------------------===//
//                                 Split Analysis
//===----------------------------------------------------------------------===//

SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
                             const LiveIntervals &lis,
                             const MachineLoopInfo &mli)
  : MF(vrm.getMachineFunction()),
    VRM(vrm),
    LIS(lis),
    Loops(mli),
    TII(*MF.getTarget().getInstrInfo()),
    CurLI(0) {}

void SplitAnalysis::clear() {
  UseSlots.clear();
  UsingInstrs.clear();
  UsingBlocks.clear();
  LiveBlocks.clear();
  CurLI = 0;
}

bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
  MachineBasicBlock *T, *F;
  SmallVector<MachineOperand, 4> Cond;
  return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
}

/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
void SplitAnalysis::analyzeUses() {
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg),
       E = MRI.reg_end(); I != E; ++I) {
    MachineOperand &MO = I.getOperand();
    if (MO.isUse() && MO.isUndef())
      continue;
    MachineInstr *MI = MO.getParent();
    if (MI->isDebugValue() || !UsingInstrs.insert(MI))
      continue;
    UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex());
    MachineBasicBlock *MBB = MI->getParent();
    UsingBlocks[MBB]++;
  }
  array_pod_sort(UseSlots.begin(), UseSlots.end());
  calcLiveBlockInfo();
  DEBUG(dbgs() << "  counted "
               << UsingInstrs.size() << " instrs, "
               << UsingBlocks.size() << " blocks.\n");
}

/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
void SplitAnalysis::calcLiveBlockInfo() {
  if (CurLI->empty())
    return;

  LiveInterval::const_iterator LVI = CurLI->begin();
  LiveInterval::const_iterator LVE = CurLI->end();

  SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
  UseI = UseSlots.begin();
  UseE = UseSlots.end();

  // Loop over basic blocks where CurLI is live.
  MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
  for (;;) {
    BlockInfo BI;
    BI.MBB = MFI;
    tie(BI.Start, BI.Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);

    // The last split point is the latest possible insertion point that dominates
    // all successor blocks. If interference reaches LastSplitPoint, it is not
    // possible to insert a split or reload that makes CurLI live in the
    // outgoing bundle.
    MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB);
    if (LSP == BI.MBB->end())
      BI.LastSplitPoint = BI.Stop;
    else
      BI.LastSplitPoint = LIS.getInstructionIndex(LSP);

    // LVI is the first live segment overlapping MBB.
    BI.LiveIn = LVI->start <= BI.Start;
    if (!BI.LiveIn)
      BI.Def = LVI->start;

    // Find the first and last uses in the block.
    BI.Uses = hasUses(MFI);
    if (BI.Uses && UseI != UseE) {
      BI.FirstUse = *UseI;
      assert(BI.FirstUse >= BI.Start);
      do ++UseI;
      while (UseI != UseE && *UseI < BI.Stop);
      BI.LastUse = UseI[-1];
      assert(BI.LastUse < BI.Stop);
    }

    // Look for gaps in the live range.
    bool hasGap = false;
    BI.LiveOut = true;
    while (LVI->