//===- LiveIntervals.cpp - Live Interval Analysis -------------------------===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

/// \file 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 computes live intervals for

/// each virtual and physical register.

//

//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/LiveIntervals.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/DepthFirstIterator.h"

#include "llvm/ADT/SmallPtrSet.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/CodeGen/LiveInterval.h"

#include "llvm/CodeGen/LiveIntervalCalc.h"

#include "llvm/CodeGen/LiveVariables.h"

#include "llvm/CodeGen/MachineBasicBlock.h"

#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"

#include "llvm/CodeGen/MachineDominators.h"

#include "llvm/CodeGen/MachineFunction.h"

#include "llvm/CodeGen/MachineInstr.h"

#include "llvm/CodeGen/MachineInstrBundle.h"

#include "llvm/CodeGen/MachineOperand.h"

#include "llvm/CodeGen/MachineRegisterInfo.h"

#include "llvm/CodeGen/Passes.h"

#include "llvm/CodeGen/SlotIndexes.h"

#include "llvm/CodeGen/StackMaps.h"

#include "llvm/CodeGen/TargetRegisterInfo.h"

#include "llvm/CodeGen/TargetSubtargetInfo.h"

#include "llvm/CodeGen/VirtRegMap.h"

#include "llvm/Config/llvm-config.h"

#include "llvm/IR/Statepoint.h"

#include "llvm/MC/LaneBitmask.h"

#include "llvm/MC/MCRegisterInfo.h"

#include "llvm/Pass.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/MathExtras.h"

#include "llvm/Support/raw_ostream.h"

#include <algorithm>

#include <cassert>

#include <cstdint>

#include <iterator>

#include <tuple>

#include <utility>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

char LiveIntervals::ID = 0;

char &llvm::LiveIntervalsID = LiveIntervals::ID;

INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", "Live Interval Analysis",

                      false, false)

INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)

INITIALIZE_PASS_DEPENDENCY(SlotIndexes)

INITIALIZE_PASS_END(LiveIntervals, "liveintervals",

                "Live Interval Analysis", false, false)

#ifndef NDEBUG

static cl::opt<bool> EnablePrecomputePhysRegs(

  "precompute-phys-liveness", cl::Hidden,

  cl::desc("Eagerly compute live intervals for all physreg units."));

#else

static bool EnablePrecomputePhysRegs = false;

#endif // NDEBUG

namespace llvm {

cl::opt<bool> UseSegmentSetForPhysRegs(

    "use-segment-set-for-physregs", cl::Hidden, cl::init(true),

    cl::desc(

        "Use segment set for the computation of the live ranges of physregs."));

} // end namespace llvm

void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {

  AU.setPreservesCFG();

  AU.addPreserved<LiveVariables>();

  AU.addPreservedID(MachineLoopInfoID);

  AU.addRequiredTransitiveID(MachineDominatorsID);

  AU.addPreservedID(MachineDominatorsID);

  AU.addPreserved<SlotIndexes>();

  AU.addRequiredTransitive<SlotIndexes>();

  MachineFunctionPass::getAnalysisUsage(AU);

}

LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {

  initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());

}

LiveIntervals::~LiveIntervals() { delete LICalc; }

void LiveIntervals::releaseMemory() {

  // Free the live intervals themselves.

  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)

    delete VirtRegIntervals[Register::index2VirtReg(i)];

  VirtRegIntervals.clear();

  RegMaskSlots.clear();

  RegMaskBits.clear();

  RegMaskBlocks.clear();

  for (LiveRange *LR : RegUnitRanges)

    delete LR;

  RegUnitRanges.clear();

  // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.

  VNInfoAllocator.Reset();

}

bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {

  MF = &fn;

  MRI = &MF->getRegInfo();

  TRI = MF->getSubtarget().getRegisterInfo();

  TII = MF->getSubtarget().getInstrInfo();

  Indexes = &getAnalysis<SlotIndexes>();

  DomTree = &getAnalysis<MachineDominatorTree>();

  if (!LICalc)

    LICalc = new LiveIntervalCalc();

  // Allocate space for all virtual registers.

  VirtRegIntervals.resize(MRI->getNumVirtRegs());

  computeVirtRegs();

  computeRegMasks();

  computeLiveInRegUnits();

  if (EnablePrecomputePhysRegs) {

    // For stress testing, precompute live ranges of all physical register

    // units, including reserved registers.

    for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)

      getRegUnit(i);

  }

  LLVM_DEBUG(dump());

  return false;

}

void LiveIntervals::print(raw_ostream &OS, const Module* ) const {

  OS << "********** INTERVALS **********\n";

  // Dump the regunits.

  for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)

    if (LiveRange *LR = RegUnitRanges[Unit])

      OS << printRegUnit(Unit, TRI) << ' ' << *LR << '\n';

  // Dump the virtregs.

  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {

    Register Reg = Register::index2VirtReg(i);

    if (hasInterval(Reg))

      OS << getInterval(Reg) << '\n';

  }

  OS << "RegMasks:";

  for (SlotIndex Idx : RegMaskSlots)

    OS << ' ' << Idx;

  OS << '\n';

  printInstrs(OS);

}

void LiveIntervals::printInstrs(raw_ostream &OS) const {

  OS << "********** MACHINEINSTRS **********\n";

  MF->print(OS, Indexes);

}

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {

  printInstrs(dbgs());

}

#endif

LiveInterval *LiveIntervals::createInterval(Register reg) {

  float Weight = reg.isPhysical() ? huge_valf : 0.0F;

  return new LiveInterval(reg, Weight);

}

/// Compute the live interval of a virtual register, based on defs and uses.

bool LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {

  assert(LICalc && "LICalc not initialized.");

  assert(LI.empty() && "Should only compute empty intervals.");

  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());

  LICalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg()));

  return computeDeadValues(LI, nullptr);

}

void LiveIntervals::computeVirtRegs() {

  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {

    Register Reg = Register::index2VirtReg(i);

    if (MRI->reg_nodbg_empty(Reg))

      continue;

    LiveInterval &LI = createEmptyInterval(Reg);

    bool NeedSplit = computeVirtRegInterval(LI);

    if (NeedSplit) {

      SmallVector<LiveInterval*, 8> SplitLIs;

      splitSeparateComponents(LI, SplitLIs);

    }

  }

}

void LiveIntervals::computeRegMasks() {

  RegMaskBlocks.resize(MF->getNumBlockIDs());

  // Find all instructions with regmask operands.

  for (const MachineBasicBlock &MBB : *MF) {

    std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];

    RMB.first = RegMaskSlots.size();

    // Some block starts, such as EH funclets, create masks.

    if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {

      RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));

      RegMaskBits.push_back(Mask);

    }

    // Unwinders may clobber additional registers.

    // FIXME: This functionality can possibly be merged into

    // MachineBasicBlock::getBeginClobberMask().

    if (MBB.isEHPad())

      if (auto *Mask = TRI->getCustomEHPadPreservedMask(*MBB.getParent())) {

        RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));

        RegMaskBits.push_back(Mask);

      }

    for (const MachineInstr &MI : MBB) {

      for (const MachineOperand &MO : MI.operands()) {

        if (!MO.isRegMask())

          continue;

        RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());

        RegMaskBits.push_back(MO.getRegMask());

      }

    }

    // Some block ends, such as funclet returns, create masks. Put the mask on

    // the last instruction of the block, because MBB slot index intervals are

    // half-open.

    if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {

      assert(!MBB.empty() && "empty return block?");

      RegMaskSlots.push_back(

          Indexes->getInstructionIndex(MBB.back()).getRegSlot());

      RegMaskBits.push_back(Mask);

    }

    // Compute the number of register mask instructions in this block.

    RMB.second = RegMaskSlots.size() - RMB.first;

  }

}

//===----------------------------------------------------------------------===//

//                           Register Unit Liveness

//===----------------------------------------------------------------------===//

//

// Fixed interference typically comes from ABI boundaries: Function arguments

// and return values are passed in fixed registers, and so are exception

// pointers entering landing pads. Certain instructions require values to be

// present in specific registers. That is also represented through fixed

// interference.

//

/// Compute the live range of a register unit, based on the uses and defs of

/// aliasing registers.  The range should be empty, or contain only dead

/// phi-defs from ABI blocks.

void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {

  assert(LICalc && "LICalc not initialized.");

  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());

  // The physregs aliasing Unit are the roots and their super-registers.

  // Create all values as dead defs before extending to uses. Note that roots

  // may share super-registers. That's OK because createDeadDefs() is

  // idempotent. It is very rare for a register unit to have multiple roots, so

  // uniquing super-registers is probably not worthwhile.

  bool IsReserved = false;

  for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {

    bool IsRootReserved = true;

    for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {

      if (!MRI->reg_empty(Reg))

        LICalc->createDeadDefs(LR, Reg);

      // A register unit is considered reserved if all its roots and all their

      // super registers are reserved.

      if (!MRI->isReserved(Reg))

        IsRootReserved = false;

    }

    IsReserved |= IsRootReserved;

  }

  assert(IsReserved == MRI->isReservedRegUnit(Unit) &&

         "reserved computation mismatch");

  // Now extend LR to reach all uses.

  // Ignore uses of reserved registers. We only track defs of those.

  if (!IsReserved) {

    for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {

      for (MCPhysReg Reg : TRI->superregs_inclusive(*Root)) {

        if (!MRI->reg_empty(Reg))

          LICalc->extendToUses(LR, Reg);

      }

    }

  }

  // Flush the segment set to the segment vector.

  if (UseSegmentSetForPhysRegs)

    LR.flushSegmentSet();

}

/// Precompute the live ranges of any register units that are live-in to an ABI

/// block somewhere. Register values can appear without a corresponding def when

/// entering the entry block or a landing pad.

void LiveIntervals::computeLiveInRegUnits() {

  RegUnitRanges.resize(TRI->getNumRegUnits());

  LLVM_DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");

  // Keep track of the live range sets allocated.

  SmallVector<unsigned, 8> NewRanges;

  // Check all basic blocks for live-ins.

  for (const MachineBasicBlock &MBB : *MF) {

    // We only care about ABI blocks: Entry + landing pads.

    if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())

      continue;

    // Create phi-defs at Begin for all live-in registers.

    SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);

    LLVM_DEBUG(dbgs() << Begin << "\t" << printMBBReference(MBB));

    for (const auto &LI : MBB.liveins()) {

      for (MCRegUnit Unit : TRI->regunits(LI.PhysReg)) {

        LiveRange *LR = RegUnitRanges[Unit];

        if (!LR) {

          // Use segment set to speed-up initial computation of the live range.

          LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);

          NewRanges.push_back(Unit);

        }

        VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());

        (void)VNI;

        LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << '#' << VNI->id);

      }

    }

    LLVM_DEBUG(dbgs() << '\n');

  }

  LLVM_DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");

  // Compute the 'normal' part of the ranges.

  for (unsigned Unit : NewRanges)

    computeRegUnitRange(*RegUnitRanges[Unit], Unit);

}

static void createSegmentsForValues(LiveRange &LR,

    iterator_range<LiveInterval::vni_iterator> VNIs) {

  for (VNInfo *VNI : VNIs) {

    if (VNI->isUnused())

      continue;

    SlotIndex Def = VNI->def;

    LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));

  }

}

void LiveIntervals::extendSegmentsToUses(LiveRange &Segments,

                                         ShrinkToUsesWorkList &WorkList,

                                         Register Reg, LaneBitmask LaneMask) {

  // Keep track of the PHIs that are in use.

  SmallPtrSet<VNInfo*, 8> UsedPHIs;

  // Blocks that have already been added to WorkList as live-out.

  SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;

  auto getSubRange = [](const LiveInterval &I, LaneBitmask M)

        -> const LiveRange& {

    if (M.none())

      return I;

    for (const LiveInterval::SubRange &SR : I.subranges()) {

      if ((SR.LaneMask & M).any()) {

        assert(SR.LaneMask == M && "Expecting lane masks to match exactly");

        return SR;

      }

    }

    llvm_unreachable("Subrange for mask not found");

  };

  const LiveInterval &LI = getInterval(Reg);

  const LiveRange &OldRange = getSubRange(LI, LaneMask);

  // Extend intervals to reach all uses in WorkList.

  while (!WorkList.empty()) {

    SlotIndex Idx = WorkList.back().first;

    VNInfo *VNI = WorkList.back().second;

    WorkList.pop_back();

    const MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Idx.getPrevSlot());

    SlotIndex BlockStart = Indexes->getMBBStartIdx(MBB);

    // Extend the live range for VNI to be live at Idx.

    if (VNInfo *ExtVNI = Segments.extendInBlock(BlockStart, Idx)) {

      assert(ExtVNI == VNI && "Unexpected existing value number");

      (void)ExtVNI;

      // Is this a PHIDef we haven't seen before?

      if (!VNI->isPHIDef() || VNI->def != BlockStart ||

          !UsedPHIs.insert(VNI).second)

        continue;

      // The PHI is live, make sure the predecessors are live-out.

      for (const MachineBasicBlock *Pred : MBB->predecessors()) {

        if (!LiveOut.insert(Pred).second)

          continue;

        SlotIndex Stop = Indexes->getMBBEndIdx(Pred);

        // A predecessor is not required to have a live-out value for a PHI.

        if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))

          WorkList.push_back(std::make_pair(Stop, PVNI));

      }

      continue;

    }

    // VNI is live-in to MBB.

    LLVM_DEBUG(dbgs() << " live-in at " << BlockStart << '\n');

    Segments.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));

    // Make sure VNI is live-out from the predecessors.

    for (const MachineBasicBlock *Pred : MBB->predecessors()) {

      if (!LiveOut.insert(Pred).second)

        continue;

      SlotIndex Stop = Indexes->getMBBEndIdx(Pred);

      if (VNInfo *OldVNI = OldRange.getVNInfoBefore(Stop)) {

        assert(OldVNI == VNI && "Wrong value out of predecessor");

        (void)OldVNI;

        WorkList.push_back(std::make_pair(Stop, VNI));

      } else {

#ifndef NDEBUG

        // There was no old VNI. Verify that Stop is jointly dominated

        // by <undef>s for this live range.

        assert(LaneMask.any() &&

               "Missing value out of predecessor for main range");

        SmallVector<SlotIndex,8> Undefs;

        LI.computeSubRangeUndefs(Undefs, LaneMask, *MRI, *Indexes);

        assert(LiveRangeCalc::isJointlyDominated(Pred, Undefs, *Indexes) &&

               "Missing value out of predecessor for subrange");

#endif

      }

    }

  }

}

bool LiveIntervals::shrinkToUses(LiveInterval *li,

                                 SmallVectorImpl<MachineInstr*> *dead) {

  LLVM_DEBUG(dbgs() << "Shrink: " << *li << '\n');

  assert(li->reg().isVirtual() && "Can only shrink virtual registers");

  // Shrink subregister live ranges.

  bool NeedsCleanup = false;

  for (LiveInterval::SubRange &S : li->subranges()) {

    shrinkToUses(S, li->reg());

    if (S.empty())

      NeedsCleanup = true;

  }

  if (NeedsCleanup)

    li->removeEmptySubRanges();

  // Find all the values used, including PHI kills.

  ShrinkToUsesWorkList WorkList;

  // Visit all instructions reading li->reg().

  Register Reg = li->reg();

  for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {

    if (UseMI.isDebugInstr() || !UseMI.readsVirtualRegister(Reg))

      continue;

    SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();

    LiveQueryResult LRQ = li->Query(Idx);

    VNInfo *VNI = LRQ.valueIn();

    if (!VNI) {

      // This shouldn't happen: readsVirtualRegister returns true, but there is

      // no live value. It is likely caused by a target getting <undef> flags

      // wrong.

      LLVM_DEBUG(

          dbgs() << Idx << '\t' << UseMI

                 << "Warning: Instr claims to read non-existent value in "

                 << *li << '\n');

      continue;

    }

    // Special case: An early-clobber tied operand reads and writes the

    // register one slot early.

    if (VNInfo *DefVNI = LRQ.valueDefined())

      Idx = DefVNI->def;

    WorkList.push_back(std::make_pair(Idx, VNI));

  }

  // Create new live ranges with only minimal live segments per def.

  LiveRange NewLR;

  createSegmentsForValues(NewLR, li->vnis());

  extendSegmentsToUses(NewLR, WorkList, Reg, LaneBitmask::getNone());

  // Move the trimmed segments back.

  li->segments.swap(NewLR.segments);

  // Handle dead values.

  bool CanSeparate = computeDeadValues(*li, dead);

  LLVM_DEBUG(dbgs() << "Shrunk: " << *li << '\n');

  return CanSeparate;

}

bool LiveIntervals::computeDeadValues(LiveInterval &LI,

                                      SmallVectorImpl<MachineInstr*> *dead) {

  bool MayHaveSplitComponents = false;

  for (VNInfo *VNI : LI.valnos) {

    if (VNI->isUnused())

      continue;

    SlotIndex Def = VNI->def;

    LiveRange::iterator I = LI.FindSegmentContaining(Def);

    assert(I != LI.end() && "Missing segment for VNI");

    // Is the register live before? Otherwise we may have to add a read-undef

    // flag for subregister defs.

    Register VReg = LI.reg();

    if (MRI->shouldTrackSubRegLiveness(VReg)) {

      if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {

        MachineInstr *MI = getInstructionFromIndex(Def);

        MI->setRegisterDefReadUndef(VReg);

      }

    }

    if (I->end != Def.getDeadSlot())

      continue;

    if (VNI->isPHIDef()) {

      // This is a dead PHI. Remove it.

      VNI->markUnused();

      LI.removeSegment(I);

      LLVM_DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");

    } else {

      // This is a dead def. Make sure the instruction knows.

      MachineInstr *MI = getInstructionFromIndex(Def);

      assert(MI && "No instruction defining live value");

      MI->addRegisterDead(LI.reg(), TRI);

      if (dead && MI->allDefsAreDead()) {

        LLVM_DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);

        dead->push_back(MI);

      }

    }

    MayHaveSplitComponents = true;

  }

  return MayHaveSplitComponents;

}

void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, Register Reg) {

  LLVM_DEBUG(dbgs() << "Shrink: " << SR << '\n');

  assert(Reg.isVirtual() && "Can only shrink virtual registers");

  // Find all the values used, including PHI kills.

  ShrinkToUsesWorkList WorkList;

  // Visit all instructions reading Reg.

  SlotIndex LastIdx;

  for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {

    // Skip "undef" uses.

    if (!MO.readsReg())

      continue;

    // Maybe the operand is for a subregister we don't care about.

    unsigned SubReg = MO.getSubReg();

    if (SubReg != 0) {

      LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);

      if ((LaneMask & SR.LaneMask).none())

        continue;

    }

    // We only need to visit each instruction once.

    MachineInstr *UseMI = MO.getParent();

    SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();

    if (Idx == LastIdx)

      continue;

    LastIdx = Idx;

    LiveQueryResult LRQ = SR.Query(Idx);

    VNInfo *VNI = LRQ.valueIn();

    // For Subranges it is possible that only undef values are left in that

    // part of the subregister, so there is no real liverange at the use

    if (!VNI)

      continue;

    // Special case: An early-clobber tied operand reads and writes the

    // register one slot early.

    if (VNInfo *DefVNI = LRQ.valueDefined())

      Idx = DefVNI->def;

    WorkList.push_back(std::make_pair(Idx, VNI));

  }

  // Create a new live ranges with only minimal live segments per def.

  LiveRange NewLR;

  createSegmentsForValues(NewLR, SR.vnis());

  extendSegmentsToUses(NewLR, WorkList, Reg, SR.LaneMask);

  // Move the trimmed ranges back.

  SR.segments.swap(NewLR.segments);

  // Remove dead PHI value numbers

  for (VNInfo *VNI : SR.valnos) {

    if (VNI->isUnused())

      continue;

    const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);

    assert(Segment != nullptr && "Missing segment for VNI");

    if (Segment->end != VNI->def.getDeadSlot())

      continue;

    if (VNI->isPHIDef()) {

      // This is a dead PHI. Remove it.

      LLVM_DEBUG(dbgs() << "Dead PHI at " << VNI->def

                        << " may separate interval\n");

      VNI->markUnused();

      SR.removeSegment(*Segment);

    }

  }

  LLVM_DEBUG(dbgs() << "Shrunk: " << SR << '\n');

}

void LiveIntervals::extendToIndices(LiveRange &LR,

                                    ArrayRef<SlotIndex> Indices,

                                    ArrayRef<SlotIndex> Undefs) {

  assert(LICalc && "LICalc not initialized.");

  LICalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());

  for (SlotIndex Idx : Indices)

    LICalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);

}

void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,

                               SmallVectorImpl<SlotIndex> *EndPoints) {

  LiveQueryResult LRQ = LR.Query(Kill);

  VNInfo *VNI = LRQ.valueOutOrDead();

  if (!VNI)

    return;

  MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);

  SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);

  // If VNI isn't live out from KillMBB, the value is trivially pruned.

  if (LRQ.endPoint() < MBBEnd) {

    LR.removeSegment(Kill, LRQ.endPoint());

    if (EndPoints) EndPoints->push_back(LRQ.endPoint());

    return;

  }

  // VNI is live out of KillMBB.

  LR.removeSegment(Kill, MBBEnd);

  if (EndPoints) EndPoints->push_back(MBBEnd);

  // Find all blocks that are reachable from KillMBB without leaving VNI's live

  // range. It is possible that KillMBB itself is reachable, so start a DFS

  // from each successor.

  using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;

  VisitedTy Visited;

  for (MachineBasicBlock *Succ : KillMBB->successors()) {

    for (df_ext_iterator<MachineBasicBlock*, VisitedTy>

         I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);

         I != E;) {

      MachineBasicBlock *MBB = *I;

      // Check if VNI is live in to MBB.

      SlotIndex MBBStart, MBBEnd;

      std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);

      LiveQueryResult LRQ = LR.Query(MBBStart);

      if (LRQ.valueIn() != VNI) {

        // This block isn't part of the VNI segment. Prune the search.

        I.skipChildren();

        continue;

      }

      // Prune the search if VNI is killed in MBB.

      if (LRQ.endPoint() < MBBEnd) {

        LR.removeSegment(MBBStart, LRQ.endPoint());

        if (EndPoints) EndPoints->push_back(LRQ.endPoint());

        I.skipChildren();

        continue;

      }

      // VNI is live through MBB.

      LR.removeSegment(MBBStart, MBBEnd);

      if (EndPoints) EndPoints->push_back(MBBEnd);

      ++I;

    }

  }

}

//===----------------------------------------------------------------------===//

// Register allocator hooks.

//

void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {

  // Keep track of regunit ranges.

  SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;

  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {

    Register Reg = Register::index2VirtReg(i);

    if (MRI->reg_nodbg_empty(Reg))

      continue;

    const LiveInterval &LI = getInterval(Reg);

    if (LI.empty())

      continue;

    // Target may have not allocated this yet.

    Register PhysReg = VRM->getPhys(Reg);

    if (!PhysReg)

      continue;

    // Find the regunit intervals for the assigned register. They may overlap

    // the virtual register live range, cancelling any kills.

    RU.clear();

    for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

      const LiveRange &RURange = getRegUnit(Unit);

      if (RURange.empty())

        continue;

      RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));

    }

    // Every instruction that kills Reg corresponds to a segment range end

    // point.

    for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;

         ++RI) {

      // A block index indicates an MBB edge.

      if (RI->end.isBlock())

        continue;

      MachineInstr *MI = getInstructionFromIndex(RI->end);

      if (!MI)

        continue;

      // Check if any of the regunits are live beyond the end of RI. That could

      // happen when a physreg is defined as a copy of a virtreg:

      //

      //   %eax = COPY %5

      //   FOO %5             <--- MI, cancel kill because %eax is live.

      //   BAR killed %eax

      //

      // There should be no kill flag on FOO when %5 is rewritten as %eax.

      for (auto &RUP : RU) {

        const LiveRange &RURange = *RUP.first;

        LiveRange::const_iterator &I = RUP.second;

        if (I == RURange.end())

          continue;

        I = RURange.advanceTo(I, RI->end);

        if (I == RURange.end() || I->start >= RI->end)

          continue;

        // I is overlapping RI.

        goto CancelKill;

      }

      if (MRI->subRegLivenessEnabled()) {

        // When reading a partial undefined value we must not add a kill flag.

        // The regalloc might have used the undef lane for something else.

        // Example:

        //     %1 = ...                  ; R32: %1

        //     %2:high16 = ...           ; R64: %2

        //        = read killed %2        ; R64: %2

        //        = read %1              ; R32: %1

        // The <kill> flag is correct for %2, but the register allocator may

        // assign R0L to %1, and R0 to %2 because the low 32bits of R0

        // are actually never written by %2. After assignment the <kill>

        // flag at the read instruction is invalid.

        LaneBitmask DefinedLanesMask;

        if (LI.hasSubRanges()) {

          // Compute a mask of lanes that are defined.

          DefinedLanesMask = LaneBitmask::getNone();

          for (const LiveInterval::SubRange &SR : LI.subranges())

            for (const LiveRange::Segment &Segment : SR.segments) {

              if (Segment.start >= RI->end)

                break;

              if (Segment.end == RI->end) {

                DefinedLanesMask |= SR.LaneMask;

                break;

              }

            }

        } else

          DefinedLanesMask = LaneBitmask::getAll();

        bool IsFullWrite = false;

        for (const MachineOperand &MO : MI->operands()) {

          if (!MO.isReg() || MO.getReg() != Reg)

            continue;

          if (MO.isUse()) {

            // Reading any undefined lanes?

            unsigned SubReg = MO.getSubReg();

            LaneBitmask UseMask = SubReg ? TRI->getSubRegIndexLaneMask(SubReg)

                                         : MRI->getMaxLaneMaskForVReg(Reg);

            if ((UseMask & ~DefinedLanesMask).any())

              goto CancelKill;

          } else if (MO.getSubReg() == 0) {

            // Writing to the full register?

            assert(MO.isDef());

            IsFullWrite = true;

          }

        }

        // If an instruction writes to a subregister, a new segment starts in

        // the LiveInterval. But as this is only overriding part of the register

        // adding kill-flags is not correct here after registers have been

        // assigned.

        if (!IsFullWrite) {

          // Next segment has to be adjacent in the subregister write case.

          LiveRange::const_iterator N = std::next(RI);

          if (N != LI.end() && N->start == RI->end)

            goto CancelKill;

        }

      }

      MI->addRegisterKilled(Reg, nullptr);

      continue;

CancelKill:

      MI->clearRegisterKills(Reg, nullptr);

    }

  }

}

MachineBasicBlock*

LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {

  assert(!LI.empty() && "LiveInterval is empty.");

  // A local live range must be fully contained inside the block, meaning it is

  // defined and killed at instructions, not at block boundaries. It is not

  // live in or out of any block.

  //

  // It is technically possible to have a PHI-defined live range identical to a

  // single block, but we are going to return false in that case.

  SlotIndex Start = LI.beginIndex();

  if (Start.isBlock())

    return nullptr;

  SlotIndex Stop = LI.endIndex();

  if (Stop.isBlock())

    return nullptr;

  // getMBBFromIndex doesn't need to search the MBB table when both indexes

  // belong to proper instructions.

  MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);

  MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);

  return MBB1 == MBB2 ? MBB1 : nullptr;

}

bool

LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {

  for (const VNInfo *PHI : LI.valnos) {

    if (PHI->isUnused() || !PHI->isPHIDef())

      continue;

    const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);

    // Conservatively return true instead of scanning huge predecessor lists.

    if (PHIMBB->pred_size() > 100)

      return true;

    for (const MachineBasicBlock *Pred : PHIMBB->predecessors())

      if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))

        return true;

  }

  return false;

}

float LiveIntervals::getSpillWeight(bool isDef, bool isUse,

                                    const MachineBlockFrequencyInfo *MBFI,

                                    const MachineInstr &MI) {

  return getSpillWeight(isDef, isUse, MBFI, MI.getParent());

}

float LiveIntervals::getSpillWeight(bool isDef, bool isUse,

                                    const MachineBlockFrequencyInfo *MBFI,

                                    const MachineBasicBlock *MBB) {

  return (isDef + isUse) * MBFI->getBlockFreqRelativeToEntryBlock(MBB);

}

LiveRange::Segment

LiveIntervals::addSegmentToEndOfBlock(Register Reg, MachineInstr &startInst) {

  LiveInterval &Interval = getOrCreateEmptyInterval(Reg);

  VNInfo *VN = Interval.getNextValue(

      SlotIndex(getInstructionIndex(startInst).getRegSlot()),

      getVNInfoAllocator());

  LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),

                       getMBBEndIdx(startInst.getParent()), VN);

  Interval.addSegment(S);

  return S;

}

//===----------------------------------------------------------------------===//

//                          Register mask functions

//===----------------------------------------------------------------------===//

/// Check whether use of reg in MI is live-through. Live-through means that

/// the value is alive on exit from Machine instruction. The example of such

/// use is a deopt value in statepoint instruction.

static bool hasLiveThroughUse(const MachineInstr *MI, Register Reg) {

  if (MI->getOpcode() != TargetOpcode::STATEPOINT)

    return false;

  StatepointOpers SO(MI);

  if (SO.getFlags() & (uint64_t)StatepointFlags::DeoptLiveIn)

    return false;

  for (unsigned Idx = SO.getNumDeoptArgsIdx(), E = SO.getNumGCPtrIdx(); Idx < E;

       ++Idx) {

    const MachineOperand &MO = MI->getOperand(Idx);

    if (MO.isReg() && MO.getReg() == Reg)

      return true;

  }

  return false;

}

bool LiveIntervals::checkRegMaskInterference(const LiveInterval &LI,

                                             BitVector &UsableRegs) {

  if (LI.empty())

    return false;

  LiveInterval::const_iterator LiveI = LI.begin(), LiveE = LI.end();

  // Use a smaller arrays for local live ranges.

  ArrayRef<SlotIndex> Slots;

  ArrayRef<const uint32_t*> Bits;

  if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {

    Slots = getRegMaskSlotsInBlock(MBB->getNumber());

    Bits = getRegMaskBitsInBlock(MBB->getNumber());

  } else {

    Slots = getRegMaskSlots();

    Bits = getRegMaskBits();

  }

  // We are going to enumerate all the register mask slots contained in LI.

  // Start with a binary search of RegMaskSlots to find a starting point.

  ArrayRef<SlotIndex>::iterator SlotI = llvm::lower_bound(Slots, LiveI->start);

  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();

  // No slots in range, LI begins after the last call.

  if (SlotI == SlotE)

    return false;

  bool Found = false;

  // Utility to union regmasks.

  auto unionBitMask = [&](unsigned Idx) {

      if (!Found) {

        // This is the first overlap. Initialize UsableRegs to all ones.

        UsableRegs.clear();

        UsableRegs.resize(TRI->getNumRegs(), true);

        Found = true;

      }

      // Remove usable registers clobbered by this mask.

      UsableRegs.clearBitsNotInMask(Bits[Idx]);

  };

  while (true) {

    assert(*SlotI >= LiveI->start);

    // Loop over all slots overlapping this segment.

    while (*SlotI < LiveI->end) {

      // *SlotI overlaps LI. Collect mask bits.

      unionBitMask(SlotI - Slots.begin());

      if (++SlotI == SlotE)

        return Found;

    }

    // If segment ends with live-through use we need to collect its regmask.

    if (*SlotI == LiveI->end)

      if (MachineInstr *MI = getInstructionFromIndex(*SlotI))

        if (hasLiveThroughUse(MI, LI.reg()))

          unionBitMask(SlotI++ - Slots.begin());

    // *SlotI is beyond the current LI segment.

    // Special advance implementation to not miss next LiveI->end.

    if (++LiveI == LiveE || SlotI == SlotE || *SlotI > LI.endIndex())

      return Found;

    while (LiveI->end < *SlotI)

      ++LiveI;

    // Advance SlotI until it overlaps.

    while (*SlotI < LiveI->start)

      if (++SlotI == SlotE)

        return Found;

  }

}

//===----------------------------------------------------------------------===//

//                         IntervalUpdate class.

//===----------------------------------------------------------------------===//

/// Toolkit used by handleMove to trim or extend live intervals.

class LiveIntervals::HMEditor {

private:

  LiveIntervals& LIS;

  const MachineRegisterInfo& MRI;

  const TargetRegisterInfo& TRI;

  SlotIndex OldIdx;

  SlotIndex NewIdx;

  SmallPtrSet<LiveRange*, 8> Updated;

  bool UpdateFlags;

public:

  HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,

           const TargetRegisterInfo& TRI,

           SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)

    : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),

      UpdateFlags(UpdateFlags) {}

  // FIXME: UpdateFlags is a workaround that creates live intervals for all

  // physregs, even those that aren't needed for regalloc, in order to update

  // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill

  // flags, and postRA passes will use a live register utility instead.

  LiveRange *getRegUnitLI(unsigned Unit) {

    if (UpdateFlags && !MRI.isReservedRegUnit(Unit))

      return &LIS.getRegUnit(Unit);

    return LIS.getCachedRegUnit(Unit);

  }

  /// Update all live ranges touched by MI, assuming a move from OldIdx to

  /// NewIdx.

  void updateAllRanges(MachineInstr *MI) {

    LLVM_DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": "

                      << *MI);

    bool hasRegMask = false;

    for (MachineOperand &MO : MI->operands()) {

      if (MO.isRegMask())

        hasRegMask = true;

      if (!MO.isReg())

        continue;

      if (MO.isUse()) {

        if (!MO.readsReg())

          continue;

        // Aggressively clear all kill flags.

        // They are reinserted by VirtRegRewriter.

        MO.setIsKill(false);

      }

      Register Reg = MO.getReg();

      if (!Reg)

        continue;

      if (Reg.isVirtual()) {

        LiveInterval &LI = LIS.getInterval(Reg);

        if (LI.hasSubRanges()) {

          unsigned SubReg = MO.getSubReg();

          LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)

                                        : MRI.getMaxLaneMaskForVReg(Reg);

          for (LiveInterval::SubRange &S : LI.subranges()) {

            if ((S.LaneMask & LaneMask).none())

              continue;

            updateRange(S, Reg, S.LaneMask);

          }

        }

        updateRange(LI, Reg, LaneBitmask::getNone());

        // If main range has a hole and we are moving a subrange use across

        // the hole updateRange() cannot properly handle it since it only

        // gets the LiveRange and not the whole LiveInterval. As a result

        // we may end up with a main range not covering all subranges.

        // This is extremely rare case, so let's check and reconstruct the

        // main range.