<commit_before>//===---------- 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.
//
//===----------------------------------------------------------------------===//

#include "SplitKit.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/VirtRegMap.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;

#define DEBUG_TYPE "regalloc"

STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple,   "Number of splits that were simple");
STATISTIC(NumCopies,   "Number of copies inserted for splitting");
STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");

//===----------------------------------------------------------------------===//
//                     Last Insert Point Analysis
//===----------------------------------------------------------------------===//

InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
                                         unsigned BBNum)
    : LIS(lis), LastInsertPoint(BBNum) {}

SlotIndex
InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
                                            const MachineBasicBlock &MBB) {
  unsigned Num = MBB.getNumber();
  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);

  SmallVector<const MachineBasicBlock *, 1> EHPadSucessors;
  for (const MachineBasicBlock *SMBB : MBB.successors())
    if (SMBB->isEHPad())
      EHPadSucessors.push_back(SMBB);

  // Compute insert points on the first call. The pair is independent of the
  // current live interval.
  if (!LIP.first.isValid()) {
    MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
    if (FirstTerm == MBB.end())
      LIP.first = MBBEnd;
    else
      LIP.first = LIS.getInstructionIndex(*FirstTerm);

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

  // If CurLI is live into a landing pad successor, move the last insert point
  // back to the call that may throw.
  if (!LIP.second)
    return LIP.first;

  if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) {
        return LIS.isLiveInToMBB(CurLI, EHPad);
      }))
    return LIP.first;

  // Find the value leaving MBB.
  const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
  if (!VNI)
    return LIP.first;

  // If the value leaving MBB was defined after the call in MBB, it can't
  // really be live-in to the landing pad.  This can happen if the landing pad
  // has a PHI, and this register is undef on the exceptional edge.
  // <rdar://problem/10664933>
  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
    return LIP.first;

  // Value is properly live-in to the landing pad.
  // Only allow inserts before the call.
  return LIP.second;
}

MachineBasicBlock::iterator
InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
                                            MachineBasicBlock &MBB) {
  SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
  if (LIP == LIS.getMBBEndIdx(&MBB))
    return MBB.end();
  return LIS.getInstructionFromIndex(LIP);
}

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

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

void SplitAnalysis::clear() {
  UseSlots.clear();
  UseBlocks.clear();
  ThroughBlocks.clear();
  CurLI = nullptr;
  DidRepairRange = false;
}

/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
void SplitAnalysis::analyzeUses() {
  assert(UseSlots.empty() && "Call clear first");

  // First get all the defs from the interval values. This provides the correct
  // slots for early clobbers.
  for (const VNInfo *VNI : CurLI->valnos)
    if (!VNI->isPHIDef() && !VNI->isUnused())
      UseSlots.push_back(VNI->def);

  // Get use slots form the use-def chain.
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
    if (!MO.isUndef())
      UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());

  array_pod_sort(UseSlots.begin(), UseSlots.end());

  // Remove duplicates, keeping the smaller slot for each instruction.
  // That is what we want for early clobbers.
  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
                             SlotIndex::isSameInstr),
                 UseSlots.end());

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

  DEBUG(dbgs() << "Analyze counted "
               << UseSlots.size() << " instrs in "
               << UseBlocks.size() << " blocks, through "
               << NumThroughBlocks << " blocks.\n");
}

/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
bool SplitAnalysis::calcLiveBlockInfo() {
  ThroughBlocks.resize(MF.getNumBlockIDs());
  NumThroughBlocks = NumGapBlocks = 0;
  if (CurLI->empty())
    return true;

  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)->getIterator();
  for (;;) {
    BlockInfo BI;
    BI.MBB = &*MFI;
    SlotIndex Start, Stop;
    std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);

    // If the block contains no uses, the range must be live through. At one
    // point, RegisterCoalescer could create dangling ranges that ended
    // mid-block.
    if (UseI == UseE || *UseI >= Stop) {
      ++NumThroughBlocks;
      ThroughBlocks.set(BI.MBB->getNumber());
      // The range shouldn't end mid-block if there are no uses. This shouldn't
      // happen.
      if (LVI->end < Stop)
        return false;
    } else {
      // This block has uses. Find the first and last uses in the block.
      BI.FirstInstr = *UseI;
      assert(BI.FirstInstr >= Start);
      do ++UseI;
      while (UseI != UseE && *UseI < Stop);
      BI.LastInstr = UseI[-1];
      assert(BI.LastInstr < Stop);

      // LVI is the first live segment overlapping MBB.
      BI.LiveIn = LVI->start <= Start;

      // When not live in, the first use should be a def.
      if (!BI.LiveIn) {
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
        assert(LVI->start == BI.FirstInstr && "First instr should be a def");
        BI.FirstDef = BI.FirstInstr;
      }

      // Look for gaps in the live range.
      BI.LiveOut = true;
      while (LVI->end < Stop) {
        SlotIndex LastStop = LVI->end;
        if (++LVI == LVE || LVI->start >= Stop) {
          BI.LiveOut = false;
          BI.LastInstr = LastStop;
          break;
        }

        if (LastStop < LVI->start) {
          // There is a gap in the live range. Create duplicate entries for the
          // live-in snippet and the live-out snippet.
          ++NumGapBlocks;

          // Push the Live-in part.
          BI.LiveOut = false;
          UseBlocks.push_back(BI);
          UseBlocks.back().LastInstr = LastStop;

          // Set up BI for the live-out part.
          BI.LiveIn = false;
          BI.LiveOut = true;
          BI.FirstInstr = BI.FirstDef = LVI->start;
        }

        // A Segment that starts in the middle of the block must be a def.
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
        if (!BI.FirstDef)
          BI.FirstDef = LVI->start;
      }

      UseBlocks.push_back(BI);

      // LVI is now at LVE or LVI->end >= Stop.
      if (LVI == LVE)
        break;
    }

    // Live segment ends exactly at Stop. Move to the next segment.
    if (LVI->end == Stop && ++LVI == LVE)
      break;

    // Pick the next basic block.
    if (LVI->start < Stop)
      ++MFI;
    else
      MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
  }

  assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
  return true;
}

unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
  if (cli->empty())
    return 0;
  LiveInterval *li = const_cast<LiveInterval*>(cli);
  LiveInterval::iterator LVI = li->begin();
  LiveInterval::iterator LVE = li->end();
  unsigned Count = 0;

  // Loop over basic blocks where li is live.
  MachineFunction::const_iterator MFI =
      LIS.getMBBFromIndex(LVI->start)->getIterator();
  SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
  for (;;) {
    ++Count;
    LVI = li->advanceTo(LVI, Stop);
    if (LVI == LVE)
      return Count;
    do {
      ++MFI;
      Stop = LIS.getMBBEndIdx(&*MFI);
    } while (Stop <= LVI->start);
  }
}

bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
  unsigned OrigReg = VRM.getOriginal(CurLI->reg);
  const LiveInterval &Orig = LIS.getInterval(OrigReg);
  assert(!Orig.empty() && "Splitting empty interval?");
  LiveInterval::const_iterator I = Orig.find(Idx);

  // Range containing Idx should begin at Idx.
  if (I != Orig.end() && I->start <= Idx)
    return I->start == Idx;

  // Range does not contain Idx, previous must end at Idx.
  return I != Orig.begin() && (--I)->end == Idx;
}

void SplitAnalysis::analyze(const LiveInterval *li) {
  clear();
  CurLI = li;
  analyzeUses();
}


//===----------------------------------------------------------------------===//
//                               Split Editor
//===----------------------------------------------------------------------===//

/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
                         LiveIntervals &lis, VirtRegMap &vrm,
                         MachineDominatorTree &mdt,
                         MachineBlockFrequencyInfo &mbfi)
    : SA(sa), AA(aa), LIS(lis), VRM(vrm),
      MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
      TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
      TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
      MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
      RegAssign(Allocator) {}

void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
  Edit = &LRE;
  SpillMode = SM;
  OpenIdx = 0;
  RegAssign.clear();
  Values.clear();

  // Reset the LiveRangeCalc instances needed for this spill mode.
  LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                  &LIS.getVNInfoAllocator());
  if (SpillMode)
    LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                    &LIS.getVNInfoAllocator());

  // We don't need an AliasAnalysis since we will only be performing
  // cheap-as-a-copy remats anyway.
  Edit->anyRematerializable(nullptr);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void SplitEditor::dump() const {
  if (RegAssign.empty()) {
    dbgs() << " empty\n";
    return;
  }

  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
  dbgs() << '\n';
}
#endif

LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
                                                        LiveInterval &LI) {
  for (LiveInterval::SubRange &S : LI.subranges())
    if (S.LaneMask == LM)
      return S;
  llvm_unreachable("SubRange for this mask not found");
}

void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
  if (!LI.hasSubRanges()) {
    LI.createDeadDef(VNI);
    return;
  }

  SlotIndex Def = VNI->def;
  if (Original) {
    // If we are transferring a def from the original interval, make sure
    // to only update the subranges for which the original subranges had
    // a def at this location.
    for (LiveInterval::SubRange &S : LI.subranges()) {
      auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
      VNInfo *PV = PS.getVNInfoAt(Def);
      if (PV != nullptr && PV->def == Def)
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
    }
  } else {
    // This is a new def: either from rematerialization, or from an inserted
    // copy. Since rematerialization can regenerate a definition of a sub-
    // register, we need to check which subranges need to be updated.
    const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
    assert(DefMI != nullptr);
    LaneBitmask LM;
    for (const MachineOperand &DefOp : DefMI->defs()) {
      unsigned R = DefOp.getReg();
      if (R != LI.reg)
        continue;
      if (unsigned SR = DefOp.getSubReg())
        LM |= TRI.getSubRegIndexLaneMask(SR);
      else {
        LM = MRI.getMaxLaneMaskForVReg(R);
        break;
      }
    }
    for (LiveInterval::SubRange &S : LI.subranges())
      if ((S.LaneMask & LM).any())
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
  }
}

VNInfo *SplitEditor::defValue(unsigned RegIdx,
                              const VNInfo *ParentVNI,
                              SlotIndex Idx,
                              bool Original) {
  assert(ParentVNI && "Mapping  NULL value");
  assert(Idx.isValid() && "Invalid SlotIndex");
  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

  // Create a new value.
  VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());

  bool Force = LI->hasSubRanges();
  ValueForcePair FP(Force ? nullptr : VNI, Force);
  // Use insert for lookup, so we can add missing values with a second lookup.
  std::pair<ValueMap::iterator, bool> InsP =
    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));

  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
  // forced. Keep it as a simple def without any liveness.
  if (!Force && InsP.second)
    return VNI;

  // If the previous value was a simple mapping, add liveness for it now.
  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
    addDeadDef(*LI, OldVNI, Original);

    // No longer a simple mapping.  Switch to a complex mapping. If the
    // interval has subranges, make it a forced mapping.
    InsP.first->second = ValueForcePair(nullptr, Force);
  }

  // This is a complex mapping, add liveness for VNI
  addDeadDef(*LI, VNI, Original);
  return VNI;
}

void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
  assert(ParentVNI && "Mapping  NULL value");
  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
  VNInfo *VNI = VFP.getPointer();

  // ParentVNI was either unmapped or already complex mapped. Either way, just
  // set the force bit.
  if (!VNI) {
    VFP.setInt(true);
    return;
  }

  // This was previously a single mapping. Make sure the old def is represented
  // by a trivial live range.
  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);

  // Mark as complex mapped, forced.
  VFP = ValueForcePair(nullptr, true);
}

VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                   VNInfo *ParentVNI,
                                   SlotIndex UseIdx,
                                   MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator I) {
  MachineInstr *CopyMI = nullptr;
  SlotIndex Def;
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

  // We may be trying to avoid interference that ends at a deleted instruction,
  // so always begin RegIdx 0 early and all others late.
  bool Late = RegIdx != 0;

  // Attempt cheap-as-a-copy rematerialization.
  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
  LiveInterval &OrigLI = LIS.getInterval(Original);
  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);

  bool DidRemat = false;
  if (OrigVNI) {
    LiveRangeEdit::Remat RM(ParentVNI);
    RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
    if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
      Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
      ++NumRemats;
      DidRemat = true;
    }
  }
  if (!DidRemat) {
    // Can't remat, just insert a copy from parent.
    CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
               .addReg(Edit->getReg());
    Def = LIS.getSlotIndexes()
              ->insertMachineInstrInMaps(*CopyMI, Late)
              .getRegSlot();
    ++NumCopies;
  }

  // Define the value in Reg.
  return defValue(RegIdx, ParentVNI, Def, false);
}

/// Create a new virtual register and live interval.
unsigned SplitEditor::openIntv() {
  // Create the complement as index 0.
  if (Edit->empty())
    Edit->createEmptyInterval();

  // Create the open interval.
  OpenIdx = Edit->size();
  Edit->createEmptyInterval();
  return OpenIdx;<commit_msg>Fix regalloc assignment of overlapping registers<commit_after>//===---------- 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.
//
//===----------------------------------------------------------------------===//

#include "SplitKit.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
#include "llvm/CodeGen/LiveRangeEdit.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/VirtRegMap.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;

#define DEBUG_TYPE "regalloc"

STATISTIC(NumFinished, "Number of splits finished");
STATISTIC(NumSimple,   "Number of splits that were simple");
STATISTIC(NumCopies,   "Number of copies inserted for splitting");
STATISTIC(NumRemats,   "Number of rematerialized defs for splitting");
STATISTIC(NumRepairs,  "Number of invalid live ranges repaired");

//===----------------------------------------------------------------------===//
//                     Last Insert Point Analysis
//===----------------------------------------------------------------------===//

InsertPointAnalysis::InsertPointAnalysis(const LiveIntervals &lis,
                                         unsigned BBNum)
    : LIS(lis), LastInsertPoint(BBNum) {}

SlotIndex
InsertPointAnalysis::computeLastInsertPoint(const LiveInterval &CurLI,
                                            const MachineBasicBlock &MBB) {
  unsigned Num = MBB.getNumber();
  std::pair<SlotIndex, SlotIndex> &LIP = LastInsertPoint[Num];
  SlotIndex MBBEnd = LIS.getMBBEndIdx(&MBB);

  SmallVector<const MachineBasicBlock *, 1> EHPadSucessors;
  for (const MachineBasicBlock *SMBB : MBB.successors())
    if (SMBB->isEHPad())
      EHPadSucessors.push_back(SMBB);

  // Compute insert points on the first call. The pair is independent of the
  // current live interval.
  if (!LIP.first.isValid()) {
    MachineBasicBlock::const_iterator FirstTerm = MBB.getFirstTerminator();
    if (FirstTerm == MBB.end())
      LIP.first = MBBEnd;
    else
      LIP.first = LIS.getInstructionIndex(*FirstTerm);

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

  // If CurLI is live into a landing pad successor, move the last insert point
  // back to the call that may throw.
  if (!LIP.second)
    return LIP.first;

  if (none_of(EHPadSucessors, [&](const MachineBasicBlock *EHPad) {
        return LIS.isLiveInToMBB(CurLI, EHPad);
      }))
    return LIP.first;

  // Find the value leaving MBB.
  const VNInfo *VNI = CurLI.getVNInfoBefore(MBBEnd);
  if (!VNI)
    return LIP.first;

  // If the value leaving MBB was defined after the call in MBB, it can't
  // really be live-in to the landing pad.  This can happen if the landing pad
  // has a PHI, and this register is undef on the exceptional edge.
  // <rdar://problem/10664933>
  if (!SlotIndex::isEarlierInstr(VNI->def, LIP.second) && VNI->def < MBBEnd)
    return LIP.first;

  // Value is properly live-in to the landing pad.
  // Only allow inserts before the call.
  return LIP.second;
}

MachineBasicBlock::iterator
InsertPointAnalysis::getLastInsertPointIter(const LiveInterval &CurLI,
                                            MachineBasicBlock &MBB) {
  SlotIndex LIP = getLastInsertPoint(CurLI, MBB);
  if (LIP == LIS.getMBBEndIdx(&MBB))
    return MBB.end();
  return LIS.getInstructionFromIndex(LIP);
}

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

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

void SplitAnalysis::clear() {
  UseSlots.clear();
  UseBlocks.clear();
  ThroughBlocks.clear();
  CurLI = nullptr;
  DidRepairRange = false;
}

/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
void SplitAnalysis::analyzeUses() {
  assert(UseSlots.empty() && "Call clear first");

  // First get all the defs from the interval values. This provides the correct
  // slots for early clobbers.
  for (const VNInfo *VNI : CurLI->valnos)
    if (!VNI->isPHIDef() && !VNI->isUnused())
      UseSlots.push_back(VNI->def);

  // Get use slots form the use-def chain.
  const MachineRegisterInfo &MRI = MF.getRegInfo();
  for (MachineOperand &MO : MRI.use_nodbg_operands(CurLI->reg))
    if (!MO.isUndef())
      UseSlots.push_back(LIS.getInstructionIndex(*MO.getParent()).getRegSlot());

  array_pod_sort(UseSlots.begin(), UseSlots.end());

  // Remove duplicates, keeping the smaller slot for each instruction.
  // That is what we want for early clobbers.
  UseSlots.erase(std::unique(UseSlots.begin(), UseSlots.end(),
                             SlotIndex::isSameInstr),
                 UseSlots.end());

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

  DEBUG(dbgs() << "Analyze counted "
               << UseSlots.size() << " instrs in "
               << UseBlocks.size() << " blocks, through "
               << NumThroughBlocks << " blocks.\n");
}

/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
/// where CurLI is live.
bool SplitAnalysis::calcLiveBlockInfo() {
  ThroughBlocks.resize(MF.getNumBlockIDs());
  NumThroughBlocks = NumGapBlocks = 0;
  if (CurLI->empty())
    return true;

  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)->getIterator();
  for (;;) {
    BlockInfo BI;
    BI.MBB = &*MFI;
    SlotIndex Start, Stop;
    std::tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);

    // If the block contains no uses, the range must be live through. At one
    // point, RegisterCoalescer could create dangling ranges that ended
    // mid-block.
    if (UseI == UseE || *UseI >= Stop) {
      ++NumThroughBlocks;
      ThroughBlocks.set(BI.MBB->getNumber());
      // The range shouldn't end mid-block if there are no uses. This shouldn't
      // happen.
      if (LVI->end < Stop)
        return false;
    } else {
      // This block has uses. Find the first and last uses in the block.
      BI.FirstInstr = *UseI;
      assert(BI.FirstInstr >= Start);
      do ++UseI;
      while (UseI != UseE && *UseI < Stop);
      BI.LastInstr = UseI[-1];
      assert(BI.LastInstr < Stop);

      // LVI is the first live segment overlapping MBB.
      BI.LiveIn = LVI->start <= Start;

      // When not live in, the first use should be a def.
      if (!BI.LiveIn) {
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
        assert(LVI->start == BI.FirstInstr && "First instr should be a def");
        BI.FirstDef = BI.FirstInstr;
      }

      // Look for gaps in the live range.
      BI.LiveOut = true;
      while (LVI->end < Stop) {
        SlotIndex LastStop = LVI->end;
        if (++LVI == LVE || LVI->start >= Stop) {
          BI.LiveOut = false;
          BI.LastInstr = LastStop;
          break;
        }

        if (LastStop < LVI->start) {
          // There is a gap in the live range. Create duplicate entries for the
          // live-in snippet and the live-out snippet.
          ++NumGapBlocks;

          // Push the Live-in part.
          BI.LiveOut = false;
          UseBlocks.push_back(BI);
          UseBlocks.back().LastInstr = LastStop;

          // Set up BI for the live-out part.
          BI.LiveIn = false;
          BI.LiveOut = true;
          BI.FirstInstr = BI.FirstDef = LVI->start;
        }

        // A Segment that starts in the middle of the block must be a def.
        assert(LVI->start == LVI->valno->def && "Dangling Segment start");
        if (!BI.FirstDef)
          BI.FirstDef = LVI->start;
      }

      UseBlocks.push_back(BI);

      // LVI is now at LVE or LVI->end >= Stop.
      if (LVI == LVE)
        break;
    }

    // Live segment ends exactly at Stop. Move to the next segment.
    if (LVI->end == Stop && ++LVI == LVE)
      break;

    // Pick the next basic block.
    if (LVI->start < Stop)
      ++MFI;
    else
      MFI = LIS.getMBBFromIndex(LVI->start)->getIterator();
  }

  assert(getNumLiveBlocks() == countLiveBlocks(CurLI) && "Bad block count");
  return true;
}

unsigned SplitAnalysis::countLiveBlocks(const LiveInterval *cli) const {
  if (cli->empty())
    return 0;
  LiveInterval *li = const_cast<LiveInterval*>(cli);
  LiveInterval::iterator LVI = li->begin();
  LiveInterval::iterator LVE = li->end();
  unsigned Count = 0;

  // Loop over basic blocks where li is live.
  MachineFunction::const_iterator MFI =
      LIS.getMBBFromIndex(LVI->start)->getIterator();
  SlotIndex Stop = LIS.getMBBEndIdx(&*MFI);
  for (;;) {
    ++Count;
    LVI = li->advanceTo(LVI, Stop);
    if (LVI == LVE)
      return Count;
    do {
      ++MFI;
      Stop = LIS.getMBBEndIdx(&*MFI);
    } while (Stop <= LVI->start);
  }
}

bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
  unsigned OrigReg = VRM.getOriginal(CurLI->reg);
  const LiveInterval &Orig = LIS.getInterval(OrigReg);
  assert(!Orig.empty() && "Splitting empty interval?");
  LiveInterval::const_iterator I = Orig.find(Idx);

  // Range containing Idx should begin at Idx.
  if (I != Orig.end() && I->start <= Idx)
    return I->start == Idx;

  // Range does not contain Idx, previous must end at Idx.
  return I != Orig.begin() && (--I)->end == Idx;
}

void SplitAnalysis::analyze(const LiveInterval *li) {
  clear();
  CurLI = li;
  analyzeUses();
}


//===----------------------------------------------------------------------===//
//                               Split Editor
//===----------------------------------------------------------------------===//

/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
SplitEditor::SplitEditor(SplitAnalysis &sa, AliasAnalysis &aa,
                         LiveIntervals &lis, VirtRegMap &vrm,
                         MachineDominatorTree &mdt,
                         MachineBlockFrequencyInfo &mbfi)
    : SA(sa), AA(aa), LIS(lis), VRM(vrm),
      MRI(vrm.getMachineFunction().getRegInfo()), MDT(mdt),
      TII(*vrm.getMachineFunction().getSubtarget().getInstrInfo()),
      TRI(*vrm.getMachineFunction().getSubtarget().getRegisterInfo()),
      MBFI(mbfi), Edit(nullptr), OpenIdx(0), SpillMode(SM_Partition),
      RegAssign(Allocator) {}

void SplitEditor::reset(LiveRangeEdit &LRE, ComplementSpillMode SM) {
  Edit = &LRE;
  SpillMode = SM;
  OpenIdx = 0;
  RegAssign.clear();
  Values.clear();

  // Reset the LiveRangeCalc instances needed for this spill mode.
  LRCalc[0].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                  &LIS.getVNInfoAllocator());
  if (SpillMode)
    LRCalc[1].reset(&VRM.getMachineFunction(), LIS.getSlotIndexes(), &MDT,
                    &LIS.getVNInfoAllocator());

  // We don't need an AliasAnalysis since we will only be performing
  // cheap-as-a-copy remats anyway.
  Edit->anyRematerializable(nullptr);
}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void SplitEditor::dump() const {
  if (RegAssign.empty()) {
    dbgs() << " empty\n";
    return;
  }

  for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
    dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
  dbgs() << '\n';
}
#endif

LiveInterval::SubRange &SplitEditor::getSubRangeForMask(LaneBitmask LM,
                                                        LiveInterval &LI) {
  for (LiveInterval::SubRange &S : LI.subranges())
    if (S.LaneMask == LM)
      return S;
  llvm_unreachable("SubRange for this mask not found");
}

void SplitEditor::addDeadDef(LiveInterval &LI, VNInfo *VNI, bool Original) {
  if (!LI.hasSubRanges()) {
    LI.createDeadDef(VNI);
    return;
  }

  SlotIndex Def = VNI->def;
  if (Original) {
    // If we are transferring a def from the original interval, make sure
    // to only update the subranges for which the original subranges had
    // a def at this location.
    for (LiveInterval::SubRange &S : LI.subranges()) {
      auto &PS = getSubRangeForMask(S.LaneMask, Edit->getParent());
      VNInfo *PV = PS.getVNInfoAt(Def);
      if (PV != nullptr && PV->def == Def)
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
    }
  } else {
    // This is a new def: either from rematerialization, or from an inserted
    // copy. Since rematerialization can regenerate a definition of a sub-
    // register, we need to check which subranges need to be updated.
    const MachineInstr *DefMI = LIS.getInstructionFromIndex(Def);
    assert(DefMI != nullptr);
    LaneBitmask LM;
    for (const MachineOperand &DefOp : DefMI->defs()) {
      unsigned R = DefOp.getReg();
      if (R != LI.reg)
        continue;
      if (unsigned SR = DefOp.getSubReg())
        LM |= TRI.getSubRegIndexLaneMask(SR);
      else {
        LM = MRI.getMaxLaneMaskForVReg(R);
        break;
      }
    }
    for (LiveInterval::SubRange &S : LI.subranges())
      if ((S.LaneMask & LM).any())
        S.createDeadDef(Def, LIS.getVNInfoAllocator());
  }
}

VNInfo *SplitEditor::defValue(unsigned RegIdx,
                              const VNInfo *ParentVNI,
                              SlotIndex Idx,
                              bool Original) {
  assert(ParentVNI && "Mapping  NULL value");
  assert(Idx.isValid() && "Invalid SlotIndex");
  assert(Edit->getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

  // Create a new value.
  VNInfo *VNI = LI->getNextValue(Idx, LIS.getVNInfoAllocator());

  bool Force = LI->hasSubRanges();
  ValueForcePair FP(Force ? nullptr : VNI, Force);
  // Use insert for lookup, so we can add missing values with a second lookup.
  std::pair<ValueMap::iterator, bool> InsP =
    Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), FP));

  // This was the first time (RegIdx, ParentVNI) was mapped, and it is not
  // forced. Keep it as a simple def without any liveness.
  if (!Force && InsP.second)
    return VNI;

  // If the previous value was a simple mapping, add liveness for it now.
  if (VNInfo *OldVNI = InsP.first->second.getPointer()) {
    addDeadDef(*LI, OldVNI, Original);

    // No longer a simple mapping.  Switch to a complex mapping. If the
    // interval has subranges, make it a forced mapping.
    InsP.first->second = ValueForcePair(nullptr, Force);
  }

  // This is a complex mapping, add liveness for VNI
  addDeadDef(*LI, VNI, Original);
  return VNI;
}

void SplitEditor::forceRecompute(unsigned RegIdx, const VNInfo *ParentVNI) {
  assert(ParentVNI && "Mapping  NULL value");
  ValueForcePair &VFP = Values[std::make_pair(RegIdx, ParentVNI->id)];
  VNInfo *VNI = VFP.getPointer();

  // ParentVNI was either unmapped or already complex mapped. Either way, just
  // set the force bit.
  if (!VNI) {
    VFP.setInt(true);
    return;
  }

  // This was previously a single mapping. Make sure the old def is represented
  // by a trivial live range.
  addDeadDef(LIS.getInterval(Edit->get(RegIdx)), VNI, false);

  // Mark as complex mapped, forced.
  VFP = ValueForcePair(nullptr, true);
}

VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
                                   VNInfo *ParentVNI,
                                   SlotIndex UseIdx,
                                   MachineBasicBlock &MBB,
                                   MachineBasicBlock::iterator I) {
  MachineInstr *CopyMI = nullptr;
  SlotIndex Def;
  LiveInterval *LI = &LIS.getInterval(Edit->get(RegIdx));

  // We may be trying to avoid interference that ends at a deleted instruction,
  // so always begin RegIdx 0 early and all others late.
  bool Late = RegIdx != 0;

  // Attempt cheap-as-a-copy rematerialization.
  unsigned Original = VRM.getOriginal(Edit->get(RegIdx));
  LiveInterval &OrigLI = LIS.getInterval(Original);
  VNInfo *OrigVNI = OrigLI.getVNInfoAt(UseIdx);

  bool DidRemat = false;
  if (OrigVNI) {
    LiveRangeEdit::Remat RM(ParentVNI);
    RM.OrigMI = LIS.getInstructionFromIndex(OrigVNI->def);
    if (Edit->canRematerializeAt(RM, OrigVNI, UseIdx, true)) {
      Def = Edit->rematerializeAt(MBB, I, LI->reg, RM, TRI, Late);
      ++NumRemats;
      DidRemat = true;
    }
  }
  if (!DidRemat) {
    // Can't remat, just insert a copy from parent.
    CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
               .addReg(Edit->getReg());
    Def = LIS.getSlotIndexes()
              ->insertMachineInstrInMaps(*CopyMI, Late)
              .getRegSlot();
    if (LI->hasSubRanges()) {
      LaneBitmask LM = LaneBitmask::getNone();
      for (LiveInterval::SubRange &S : LI->subranges())
        LM |= S.LaneMask;

      if (MRI.getMaxLaneMaskForVReg(LI->reg) != LM) {
        // Find subreg for the lane mask.
        unsigned SubIdx = 0;
        for (unsigned I = 1, E = TRI.getNumSubRegIndices(); I < E; ++I) {
          if (TRI.getSubRegIndexLaneMask(I) == LM) {
            SubIdx = I;
            break;
          }
        }
        if (SubIdx == 0)
          report_fatal_error("Cannot find subreg index to cover all alive lanes");
        CopyMI->getOperand(0).setSubReg(SubIdx);
        CopyMI->getOperand(1).setSubReg(SubIdx);
        CopyMI->getOperand(0).setIsUndef(true);
      }
    }
    ++NumCopies;
  }

  // Define the value in Reg.
  return defValue(RegIdx, ParentVNI, Def, false);
}

/// Create a new virtual register and live interval.
unsigned SplitEditor::openIntv() {
  // Create the complement as index 0.
  if (Edit->empty())
    Edit->createEmptyInterval();

  // Create the open interval.
  OpenIdx = Edit->size();
  Edit->createEmptyInterval();
  return OpenIdx;
{'fraction_non_alphanumeric': 0.15785918420368927, 'fraction_numerical': 0.0011951156144453105, 'mean_word_length': 2.478311946502801, 'pattern_counts': {'":': 0, '<': 104, '<?xml version=': 0, '>': 181, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '779304', 'n_tokens_mistral': 12209, 'n_tokens_neox': 11782, 'n_words': 3177}