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/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),
    LastSplitPoint(MF.getNumBlockIDs()) {}

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

SlotIndex SplitAnalysis::computeLastSplitPoint(unsigned Num) {
  const MachineBasicBlock *MBB = MF.getBlockNumbered(Num);
  const MachineBasicBlock *LPad = MBB->getLandingPadSuccessor();
  std::pair<SlotIndex, SlotIndex> &LSP = LastSplitPoint[Num];

  // Compute split points on the first call. The pair is independent of the
  // current live interval.
  if (!LSP.first.isValid()) {
    MachineBasicBlock::const_iterator FirstTerm = MBB->getFirstTerminator();
    if (FirstTerm == MBB->end())
      LSP.first = LIS.getMBBEndIdx(MBB);
    else
      LSP.first = LIS.getInstructionIndex(FirstTerm);

    // If there is a landing pad successor, also find the call instruction.
    if (!LPad)
      return LSP.first;
    // There may not be a call instruction (?) in which case we ignore LPad.
    LSP.second = LSP.first;
    for (MachineBasicBlock::const_iterator I = FirstTerm, E = MBB->begin();
         I != E; --I)
      if (I->getDesc().isCall()) {
        LSP.second = LIS.getInstructionIndex(I);
        break;
      }
  }

  // If CurLI is live into a landing pad successor, move the last split point
  // back to the call that may throw.
  if (LPad && LSP.second.isValid() && !LIS.isLiveInToMBB(*CurLI, LPad))
    return LSP.second;
  else
    return LSP.first;
}

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

  // Compute per-live block info.
  if (!calcLiveBlockInfo()) {
    // FIXME: calcLiveBlockInfo found inconsistencies in the live range.
    // I am looking at you, SimpleRegisterCoalescing!
    DEBUG(dbgs() << "*** Fixing inconsistent live interval! ***\n");
    const_cast<LiveIntervals&>(LIS)
      .shrinkToUses(const_cast<LiveInterval*>(CurLI));
    LiveBlocks.clear();
    bool fixed = calcLiveBlockInfo();
    (void)fixed;
    assert(fixed && "Couldn't fix broken live interval");
  }

  DEBUG(dbgs() << "Analyze counted "
               << UsingInstrs.size() << " instrs, "
               << UsingBlocks.size() << " blocks, "
               << LiveBlocks.size() << " spanned.\n");
}

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

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