//===- RegAllocFast.cpp - A fast register allocator for debug code --------===//
//
// 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 A block-local register allocator. No virtual register stays in a
/// register across a block boundary. A value live across one gets a stack slot:
/// spilled after its def and reloaded above its uses in each block, at the top
/// of the block or just after an intervening instruction that evicts it.
/// There is no dataflow liveness analysis, only a bounded scan of def and use
/// lists, and no live range splitting, interference graph or coalescer, only a
/// copy hint plus removal of COPYs that end up identity or dead.
///
/// Each block is walked backwards: a use is the first reference reached and
/// acquires a register, a def is the last and releases one.
///
/// Where the target enables it, TwoAddressInstructionPass is left out of the
/// pipeline: this pass lowers tied operands and expands REG_SEQUENCE and
/// INSERT_SUBREG itself.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/RegAllocFast.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegAllocCommon.h"
#include "llvm/CodeGen/RegAllocRegistry.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <tuple>
#include <vector>

using namespace llvm;

#define DEBUG_TYPE "regalloc"

STATISTIC(NumStores, "Number of stores added");
STATISTIC(NumLoads, "Number of loads added");
STATISTIC(NumCoalesced, "Number of copies coalesced");

static RegisterRegAlloc fastRegAlloc("fast", "fast register allocator",
                                     createFastRegisterAllocator);

namespace {

/// Assign ascending index for instructions in machine basic block. The index
/// can be used to determine dominance between instructions in same MBB.
class InstrPosIndexes {
public:
  void unsetInitialized() { IsInitialized = false; }

  void init(const MachineBasicBlock &MBB) {
    CurMBB = &MBB;
    Instr2PosIndex.clear();
    uint64_t LastIndex = 0;
    for (const MachineInstr &MI : MBB) {
      LastIndex += InstrDist;
      Instr2PosIndex[&MI] = LastIndex;
    }
  }

  /// Set \p Index to index of \p MI. If \p MI is new inserted, it try to assign
  /// index without affecting existing instruction's index. Return true if all
  /// instructions index has been reassigned.
  bool getIndex(const MachineInstr &MI, uint64_t &Index) {
    if (!IsInitialized) {
      init(*MI.getParent());
      IsInitialized = true;
      Index = Instr2PosIndex.at(&MI);
      return true;
    }

    assert(MI.getParent() == CurMBB && "MI is not in CurMBB");
    auto It = Instr2PosIndex.find(&MI);
    if (It != Instr2PosIndex.end()) {
      Index = It->second;
      return false;
    }

    // Distance is the number of consecutive unassigned instructions including
    // MI. Start is the first instruction of them. End is the next of last
    // instruction of them.
    // e.g.
    // |Instruction|  A   |  B   |  C   |  MI  |  D   |  E   |
    // |   Index   | 1024 |      |      |      |      | 2048 |
    //
    // In this case, B, C, MI, D are unassigned. Distance is 4, Start is B, End
    // is E.
    unsigned Distance = 1;
    MachineBasicBlock::const_iterator Start = MI.getIterator(),
                                      End = std::next(Start);
    while (Start != CurMBB->begin() &&
           !Instr2PosIndex.count(&*std::prev(Start))) {
      --Start;
      ++Distance;
    }
    while (End != CurMBB->end() && !Instr2PosIndex.count(&*(End))) {
      ++End;
      ++Distance;
    }

    // LastIndex is initialized to last used index prior to MI or zero.
    // In previous example, LastIndex is 1024, EndIndex is 2048;
    uint64_t LastIndex =
        Start == CurMBB->begin() ? 0 : Instr2PosIndex.at(&*std::prev(Start));
    uint64_t Step;
    if (End == CurMBB->end())
      Step = static_cast<uint64_t>(InstrDist);
    else {
      // No instruction uses index zero.
      uint64_t EndIndex = Instr2PosIndex.at(&*End);
      assert(EndIndex > LastIndex && "Index must be ascending order");
      unsigned NumAvailableIndexes = EndIndex - LastIndex - 1;
      // We want index gap between two adjacent MI is as same as possible. Given
      // total A available indexes, D is number of consecutive unassigned
      // instructions, S is the step.
      // |<- S-1 -> MI <- S-1 -> MI <- A-S*D ->|
      // There're S-1 available indexes between unassigned instruction and its
      // predecessor. There're A-S*D available indexes between the last
      // unassigned instruction and its successor.
      // Ideally, we want
      //    S-1 = A-S*D
      // then
      //    S = (A+1)/(D+1)
      // An valid S must be integer greater than zero, so
      //    S <= (A+1)/(D+1)
      // =>
      //    A-S*D >= 0
      // That means we can safely use (A+1)/(D+1) as step.
      // In previous example, Step is 204, Index of B, C, MI, D is 1228, 1432,
      // 1636, 1840.
      Step = (NumAvailableIndexes + 1) / (Distance + 1);
    }

    // Reassign index for all instructions if number of new inserted
    // instructions exceed slot or all instructions are new.
    if (LLVM_UNLIKELY(!Step || (!LastIndex && Step == InstrDist))) {
      init(*CurMBB);
      Index = Instr2PosIndex.at(&MI);
      return true;
    }

    for (auto I = Start; I != End; ++I) {
      LastIndex += Step;
      Instr2PosIndex[&*I] = LastIndex;
    }
    Index = Instr2PosIndex.at(&MI);
    return false;
  }

private:
  bool IsInitialized = false;
  enum { InstrDist = 1024 };
  const MachineBasicBlock *CurMBB = nullptr;
  DenseMap<const MachineInstr *, uint64_t> Instr2PosIndex;
};

class RegAllocFastImpl {
public:
  RegAllocFastImpl(const RegAllocFilterFunc F = nullptr,
                   bool ClearVirtRegs_ = true)
      : ShouldAllocateRegisterImpl(F), StackSlotForVirtReg(-1),
        ClearVirtRegs(ClearVirtRegs_) {}

private:
  MachineFrameInfo *MFI = nullptr;
  MachineRegisterInfo *MRI = nullptr;
  const TargetRegisterInfo *TRI = nullptr;
  const TargetInstrInfo *TII = nullptr;
  RegisterClassInfo RegClassInfo;
  const RegAllocFilterFunc ShouldAllocateRegisterImpl;

  /// Tied operands reach this pass unrewritten (TwoAddressInstructionPass was
  /// left out of the pipeline): lower them here.
  bool LowerTiedOps = false;

  /// Basic block currently being allocated.
  MachineBasicBlock *MBB = nullptr;

  /// Maps virtual regs to the frame index where these values are spilled.
  IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg;

  /// A virtual register live at the current point of the backward walk.
  /// Created at its last reference, cleared only when the block is done.
  struct LiveReg {
    MachineInstr *LastUse = nullptr; ///< Last instr to use reg.
    Register VirtReg;                ///< Virtual register number.
    MCRegister PhysReg;              ///< Currently held here, 0 if none.
    bool LiveOut = false;            ///< May be live out; the def spills.
    bool Reloaded = false;           ///< Reloaded below; the def spills.
    bool Error = false;              ///< Could not allocate.

    explicit LiveReg(Register VirtReg) : VirtReg(VirtReg) {}
    explicit LiveReg() = default;

    unsigned getSparseSetIndex() const { return VirtReg.virtRegIndex(); }
  };

  using LiveRegMap = SparseSet<LiveReg, unsigned, identity, uint16_t>;
  /// This map contains entries for each virtual register that is currently
  /// available in a physical register.
  LiveRegMap LiveVirtRegs;

  /// Stores assigned virtual registers present in the bundle MI.
  DenseMap<Register, LiveReg> BundleVirtRegsMap;

  DenseMap<Register, SmallVector<MachineOperand *, 2>> LiveDbgValueMap;
  /// List of DBG_VALUE that we encountered without the vreg being assigned
  /// because they were placed after the last use of the vreg.
  DenseMap<Register, SmallVector<MachineInstr *, 1>> DanglingDbgValues;

  /// Has a bit set for every virtual register for which it was determined
  /// that it is alive across blocks.
  BitVector MayLiveAcrossBlocks;

  /// What occupies a register unit. Registers interfere exactly when their
  /// unit sets intersect, so overlap needs no alias walk.
  enum RegUnitState {
    /// Not in use; a register is allocatable iff all of its units are free.
    regFree,

    /// Not available to the allocator and not a virtual register: a physreg
    /// operand or a block live-out. Cannot be spilled.
    regPreAssigned,

    /// Scratch marker: reloadAtBegin() stamps MBB.liveins() over the finished
    /// map, and a virtual register left in a live-in register is not reloaded.
    regLiveIn,

    /// Any other value is a virtual register number (>= VirtualRegFlag);
    /// LiveVirtRegs holds the inverse mapping.
  };

  /// State of each register unit, indexed by MCRegUnit.
  std::vector<unsigned> RegUnitStates;

  SmallVector<MachineInstr *, 32> Coalesced;

  /// Track register units that are used in the current instruction, and so
  /// cannot be allocated.
  ///
  /// In the first phase (tied defs/early clobber), we consider also physical
  /// uses, afterwards, we don't. If the lowest bit isn't set, it's a solely
  /// physical use (markPhysRegUsedInInstr), otherwise, it's a normal use. To
  /// avoid resetting the entire vector after every instruction, we track the
  /// instruction "generation" in the remaining 31 bits -- this means, that if
  /// UsedInInstr[Idx] < InstrGen, the register unit is unused. InstrGen is
  /// never zero and always incremented by two.
  ///
  /// Don't allocate inline storage: the number of register units is typically
  /// quite large (e.g., AArch64 > 100, X86 > 200, AMDGPU > 1000).
  uint32_t InstrGen;
  SmallVector<unsigned, 0> UsedInInstr;

  /// Physical registers with a non-dead def on the current instruction.
  SmallVector<MCRegister, 4> LiveDefRegs;

  SmallVector<unsigned, 8> DefOperandIndexes;
  // Register masks attached to the current instruction.
  SmallVector<const uint32_t *> RegMasks;

  // Assign index for each instruction to quickly determine dominance.
  InstrPosIndexes PosIndexes;

  void setRegUnitState(MCRegUnit Unit, unsigned NewState);
  unsigned getRegUnitState(MCRegUnit Unit) const;

  void setPhysRegState(MCRegister PhysReg, unsigned NewState);
  bool isPhysRegFree(MCRegister PhysReg) const;

  /// Mark a physreg as used in this instruction.
  void markRegUsedInInstr(MCRegister PhysReg) {
    for (MCRegUnit Unit : TRI->regunits(PhysReg))
      UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen | 1;
  }

  // Check if physreg is clobbered by instruction's regmask(s).
  bool isClobberedByRegMasks(MCRegister PhysReg) const {
    return llvm::any_of(RegMasks, [PhysReg](const uint32_t *Mask) {
      return MachineOperand::clobbersPhysReg(Mask, PhysReg);
    });
  }

  /// Check if a physreg or any of its aliases are used in this instruction.
  bool isRegUsedInInstr(MCRegister PhysReg, bool LookAtPhysRegUses) const {
    if (LookAtPhysRegUses && isClobberedByRegMasks(PhysReg))
      return true;
    for (MCRegUnit Unit : TRI->regunits(PhysReg))
      if (UsedInInstr[static_cast<unsigned>(Unit)] >=
          (InstrGen | !LookAtPhysRegUses))
        return true;
    return false;
  }

  /// Mark physical register as being used in a register use operand.
  /// This is only used by the special livethrough handling code.
  void markPhysRegUsedInInstr(MCRegister PhysReg) {
    for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
      assert(UsedInInstr[static_cast<unsigned>(Unit)] <= InstrGen &&
             "non-phys use before phys use?");
      UsedInInstr[static_cast<unsigned>(Unit)] = InstrGen;
    }
  }

  /// Remove mark of physical register being used in the instruction.
  void unmarkRegUsedInInstr(MCRegister PhysReg) {
    for (MCRegUnit Unit : TRI->regunits(PhysReg))
      UsedInInstr[static_cast<unsigned>(Unit)] = 0;
  }

  /// Check if \p PhysReg or a super-register has a non-dead def on the current
  /// instruction.
  bool hasLiveDefOfSuperReg(MCRegister PhysReg) const {
    return any_of(LiveDefRegs, [&](MCRegister LiveReg) {
      return TRI->isSuperRegisterEq(PhysReg, LiveReg);
    });
  }

  enum : unsigned {
    spillClean = 50,
    spillDirty = 100,
    spillPrefBonus = 20,
    spillImpossible = ~0u
  };

public:
  bool ClearVirtRegs;

  bool runOnMachineFunction(MachineFunction &MF);

private:
  void allocateBasicBlock(MachineBasicBlock &MBB);
  void expandSubregPseudo(MachineInstr &MI);

  void addRegClassDefCounts(MutableArrayRef<unsigned> RegClassDefCounts,
                            Register Reg) const;

  void findAndSortDefOperandIndexes(const MachineInstr &MI);

  void allocateInstruction(MachineInstr &MI);
  void handleDebugValue(MachineInstr &MI);
  void handleBundle(MachineInstr &MI);

  bool usePhysReg(MachineInstr &MI, MCRegister PhysReg);
  bool definePhysReg(MachineInstr &MI, MCRegister PhysReg);
  bool displacePhysReg(MachineInstr &MI, MCRegister PhysReg);
  void freePhysReg(MCRegister PhysReg);

  unsigned calcSpillCost(MCPhysReg PhysReg) const;

  LiveRegMap::iterator findLiveVirtReg(Register VirtReg) {
    return LiveVirtRegs.find(VirtReg.virtRegIndex());
  }

  LiveRegMap::const_iterator findLiveVirtReg(Register VirtReg) const {
    return LiveVirtRegs.find(VirtReg.virtRegIndex());
  }

  void assignVirtToPhysReg(MachineInstr &MI, LiveReg &, MCRegister PhysReg);
  void allocVirtReg(MachineInstr &MI, LiveReg &LR, Register Hint,
                    bool LookAtPhysRegUses = false);
  void allocVirtRegUndef(MachineOperand &MO);
  void assignDanglingDebugValues(MachineInstr &Def, Register VirtReg,
                                 MCRegister Reg);
  bool defineLiveThroughVirtReg(MachineInstr &MI, unsigned OpNum,
                                Register VirtReg);
  bool defineVirtReg(MachineInstr &MI, unsigned OpNum, Register VirtReg,
                     bool LookAtPhysRegUses = false);
  bool useVirtReg(MachineInstr &MI, MachineOperand &MO, Register VirtReg);
  bool lowerTiedUse(MachineInstr &MI, MachineOperand &MO, LiveReg &LR);

  MCPhysReg getErrorAssignment(const LiveReg &LR, MachineInstr &MI,
                               const TargetRegisterClass &RC);

  MachineBasicBlock::iterator
  getMBBBeginInsertionPoint(MachineBasicBlock &MBB,
                            SmallSet<Register, 2> &PrologLiveIns) const;

  void reloadAtBegin(MachineBasicBlock &MBB);
  bool setPhysReg(MachineInstr &MI, MachineOperand &MO,
                  const LiveReg &Assignment);

  Register traceCopies(Register VirtReg) const;
  Register traceCopyChain(Register Reg) const;

  bool shouldAllocateRegister(const Register Reg) const;
  int getStackSpaceFor(Register VirtReg);
  void spill(MachineBasicBlock::iterator Before, Register VirtReg,
             MCRegister AssignedReg, bool Kill, bool LiveOut);
  void reload(MachineBasicBlock::iterator Before, Register VirtReg,
              MCRegister PhysReg);

  bool mayLiveOut(Register VirtReg);
  bool mayLiveIn(Register VirtReg);

  bool mayBeSpillFromInlineAsmBr(const MachineInstr &MI) const;

  void dumpState() const;
};

class RegAllocFast : public MachineFunctionPass {
  RegAllocFastImpl Impl;

public:
  static char ID;

  RegAllocFast(const RegAllocFilterFunc F = nullptr, bool ClearVirtRegs_ = true)
      : MachineFunctionPass(ID), Impl(F, ClearVirtRegs_) {}

  bool runOnMachineFunction(MachineFunction &MF) override {
    return Impl.runOnMachineFunction(MF);
  }

  StringRef getPassName() const override { return "Fast Register Allocator"; }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesCFG();
    MachineFunctionPass::getAnalysisUsage(AU);
  }

  MachineFunctionProperties getRequiredProperties() const override {
    return MachineFunctionProperties().setNoPHIs();
  }

  MachineFunctionProperties getSetProperties() const override {
    MachineFunctionProperties P;
    if (Impl.ClearVirtRegs)
      P.setNoVRegs().setTiedOpsRewritten();
    return P;
  }

  MachineFunctionProperties getClearedProperties() const override {
    return MachineFunctionProperties().setIsSSA();
  }
};

} // end anonymous namespace

char RegAllocFast::ID = 0;

INITIALIZE_PASS(RegAllocFast, "regallocfast", "Fast Register Allocator", false,
                false)

bool RegAllocFastImpl::shouldAllocateRegister(const Register Reg) const {
  assert(Reg.isVirtual());
  if (!ShouldAllocateRegisterImpl)
    return true;

  return ShouldAllocateRegisterImpl(*TRI, *MRI, Reg);
}

void RegAllocFastImpl::setRegUnitState(MCRegUnit Unit, unsigned NewState) {
  RegUnitStates[static_cast<unsigned>(Unit)] = NewState;
}

unsigned RegAllocFastImpl::getRegUnitState(MCRegUnit Unit) const {
  return RegUnitStates[static_cast<unsigned>(Unit)];
}

void RegAllocFastImpl::setPhysRegState(MCRegister PhysReg, unsigned NewState) {
  for (MCRegUnit Unit : TRI->regunits(PhysReg))
    setRegUnitState(Unit, NewState);
}

bool RegAllocFastImpl::isPhysRegFree(MCRegister PhysReg) const {
  for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
    if (getRegUnitState(Unit) != regFree)
      return false;
  }
  return true;
}

/// This allocates space for the specified virtual register to be held on the
/// stack.
int RegAllocFastImpl::getStackSpaceFor(Register VirtReg) {
  // Find the location Reg would belong...
  int SS = StackSlotForVirtReg[VirtReg];
  // Already has space allocated?
  if (SS != -1)
    return SS;

  // Allocate a new stack object for this spill location...
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
  unsigned Size = TRI->getSpillSize(RC);
  Align Alignment = TRI->getSpillAlign(RC);

  const MachineFunction &MF = MRI->getMF();
  auto &ST = MF.getSubtarget();
  Align CurrentAlign = ST.getFrameLowering()->getStackAlign();
  if (Alignment > CurrentAlign && !TRI->canRealignStack(MF))
    Alignment = CurrentAlign;

  int FrameIdx =
      MFI->CreateSpillStackObject(Size, Alignment, TRI->getSpillStackID(RC));

  // Assign the slot.
  StackSlotForVirtReg[VirtReg] = FrameIdx;
  return FrameIdx;
}

static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A,
                      const MachineInstr &B) {
  uint64_t IndexA, IndexB;
  PosIndexes.getIndex(A, IndexA);
  // getIndex() returns true when it renumbered the block, invalidating IndexA.
  if (LLVM_UNLIKELY(PosIndexes.getIndex(B, IndexB)))
    PosIndexes.getIndex(A, IndexA);
  return IndexA < IndexB;
}

/// Returns true if \p MI is a spill of a live-in physical register in a block
/// targeted by an INLINEASM_BR. Such spills must precede reloads of live-in
/// virtual registers, so that we do not reload from an uninitialized stack
/// slot.
bool RegAllocFastImpl::mayBeSpillFromInlineAsmBr(const MachineInstr &MI) const {
  int FI;
  auto *MBB = MI.getParent();
  if (MBB->isInlineAsmBrIndirectTarget() && TII->isStoreToStackSlot(MI, FI) &&
      MFI->isSpillSlotObjectIndex(FI))
    for (const auto &Op : MI.operands())
      if (Op.isReg() && Op.getReg().isValid() && MBB->isLiveIn(Op.getReg()))
        return true;
  return false;
}

/// Returns false if \p VirtReg is known to not live out of the current block.
bool RegAllocFastImpl::mayLiveOut(Register VirtReg) {
  if (MayLiveAcrossBlocks.test(VirtReg.virtRegIndex())) {
    // Cannot be live-out if there are no successors.
    return !MBB->succ_empty();
  }

  const MachineInstr *SelfLoopDef = nullptr;

  // If this block loops back to itself, it is necessary to check whether the
  // use comes after the def.
  if (MBB->isSuccessor(MBB)) {
    // Find the first def in the self loop MBB.
    for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
      if (DefInst.getParent() != MBB) {
        MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
        return true;
      } else {
        if (!SelfLoopDef || dominates(PosIndexes, DefInst, *SelfLoopDef))
          SelfLoopDef = &DefInst;
      }
    }
    if (!SelfLoopDef) {
      MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
      return true;
    }
  }

  // See if the first \p Limit uses of the register are all in the current
  // block.
  static const unsigned Limit = 8;
  unsigned C = 0;
  for (const MachineInstr &UseInst : MRI->use_nodbg_instructions(VirtReg)) {
    if (UseInst.getParent() != MBB || ++C >= Limit) {
      MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
      // Cannot be live-out if there are no successors.
      return !MBB->succ_empty();
    }

    if (SelfLoopDef) {
      // Try to handle some simple cases to avoid spilling and reloading every
      // value inside a self looping block.
      if (SelfLoopDef == &UseInst ||
          !dominates(PosIndexes, *SelfLoopDef, UseInst)) {
        MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
        return true;
      }
    }
  }

  return false;
}

/// Returns false if \p VirtReg is known to not be live into the current block.
bool RegAllocFastImpl::mayLiveIn(Register VirtReg) {
  if (MayLiveAcrossBlocks.test(VirtReg.virtRegIndex()))
    return !MBB->pred_empty();

  // See if the first \p Limit def of the register are all in the current block.
  static const unsigned Limit = 8;
  unsigned C = 0;
  for (const MachineInstr &DefInst : MRI->def_instructions(VirtReg)) {
    if (DefInst.getParent() != MBB || ++C >= Limit) {
      MayLiveAcrossBlocks.set(VirtReg.virtRegIndex());
      return !MBB->pred_empty();
    }
  }

  return false;
}

/// Insert spill instruction for \p AssignedReg before \p Before. Update
/// DBG_VALUEs with \p VirtReg operands with the stack slot.
void RegAllocFastImpl::spill(MachineBasicBlock::iterator Before,
                             Register VirtReg, MCRegister AssignedReg,
                             bool Kill, bool LiveOut) {
  LLVM_DEBUG(dbgs() << "Spilling " << printReg(VirtReg, TRI) << " in "
                    << printReg(AssignedReg, TRI));
  int FI = getStackSpaceFor(VirtReg);
  LLVM_DEBUG(dbgs() << " to stack slot #" << FI << '\n');

  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
  TII->storeRegToStackSlot(*MBB, Before, AssignedReg, Kill, FI, &RC, VirtReg);
  ++NumStores;

  MachineBasicBlock::iterator FirstTerm = MBB->getFirstTerminator();

  // When we spill a virtual register, we will have spill instructions behind
  // every definition of it, meaning we can switch all the DBG_VALUEs over
  // to just reference the stack slot.
  SmallVectorImpl<MachineOperand *> &LRIDbgOperands = LiveDbgValueMap[VirtReg];
  SmallMapVector<MachineInstr *, SmallVector<const MachineOperand *>, 2>
      SpilledOperandsMap;
  for (MachineOperand *MO : LRIDbgOperands)
    SpilledOperandsMap[MO->getParent()].push_back(MO);
  for (const auto &MISpilledOperands : SpilledOperandsMap) {
    MachineInstr &DBG = *MISpilledOperands.first;
    // We don't have enough support for tracking operands of DBG_VALUE_LISTs.
    if (DBG.isDebugValueList())
      continue;
    MachineInstr *NewDV = buildDbgValueForSpill(
        *MBB, Before, *MISpilledOperands.first, FI, MISpilledOperands.second);
    assert(NewDV->getParent() == MBB && "dangling parent pointer");
    (void)NewDV;
    LLVM_DEBUG(dbgs() << "Inserting debug info due to spill:\n" << *NewDV);

    if (LiveOut) {
      // We need to insert a DBG_VALUE at the end of the block if the spill slot
      // is live out, but there is another use of the value after the
      // spill. This will allow LiveDebugValues to see the correct live out
      // value to propagate to the successors.
      MachineInstr *ClonedDV = MBB->getParent()->CloneMachineInstr(NewDV);
      MBB->insert(FirstTerm, ClonedDV);
      LLVM_DEBUG(dbgs() << "Cloning debug info due to live out spill\n");
    }

    // Rewrite unassigned dbg_values to use the stack slot.
    // TODO We can potentially do this for list debug values as well if we know
    // how the dbg_values are getting unassigned.
    if (DBG.isNonListDebugValue()) {
      MachineOperand &MO = DBG.getDebugOperand(0);
      if (MO.isReg() && !MO.getReg()) {
        updateDbgValueForSpill(DBG, FI, Register());
      }
    }
  }
  // Now this register is spilled there is should not be any DBG_VALUE
  // pointing to this register because they are all pointing to spilled value
  // now.
  LRIDbgOperands.clear();
}

/// Insert reload instruction for \p PhysReg before \p Before.
void RegAllocFastImpl::reload(MachineBasicBlock::iterator Before,
                              Register VirtReg, MCRegister PhysReg) {
  LLVM_DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
                    << printReg(PhysReg, TRI) << '\n');
  int FI = getStackSpaceFor(VirtReg);
  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
  TII->loadRegFromStackSlot(*MBB, Before, PhysReg, FI, &RC, VirtReg);
  ++NumLoads;
}

/// Get basic block begin insertion point.
/// This is not just MBB.begin() because surprisingly we have EH_LABEL
/// instructions marking the begin of a basic block. This means we must insert
/// new instructions after such labels...
MachineBasicBlock::iterator RegAllocFastImpl::getMBBBeginInsertionPoint(
    MachineBasicBlock &MBB, SmallSet<Register, 2> &PrologLiveIns) const {
  MachineBasicBlock::iterator I = MBB.begin();
  while (I != MBB.end()) {
    if (I->isLabel()) {
      ++I;
      continue;
    }

    // Skip prologues and inlineasm_br spills to place reloads afterwards.
    if (!TII->isBasicBlockPrologue(*I) && !mayBeSpillFromInlineAsmBr(*I))
      break;

    // However if a prolog instruction reads a register that needs to be
    // reloaded, the reload should be inserted before the prolog.
    for (MachineOperand &MO : I->operands()) {
      if (MO.isReg())
        PrologLiveIns.insert(MO.getReg());
    }

    ++I;
  }

  return I;
}

/// Reload all currently assigned virtual registers.
void RegAllocFastImpl::reloadAtBegin(MachineBasicBlock &MBB) {
  if (LiveVirtRegs.empty())
    return;

  // Mark live-in registers so the loop below skips reloads into them. The
  // virtual register mappings this overwrites are not needed anymore.
  for (MachineBasicBlock::RegisterMaskPair P : MBB.liveins())
    setPhysRegState(P.PhysReg, regLiveIn);

  SmallSet<Register, 2> PrologLiveIns;

  // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
  // of spilling here is deterministic, if arbitrary.
  MachineBasicBlock::iterator InsertBefore =
      getMBBBeginInsertionPoint(MBB, PrologLiveIns);
  for (const LiveReg &LR : LiveVirtRegs) {
    MCRegister PhysReg = LR.PhysReg;
    if (!PhysReg || LR.Error)
      continue;

    MCRegUnit FirstUnit = *TRI->regunits(PhysReg).begin();
    if (getRegUnitState(FirstUnit) == regLiveIn)
      continue;

    assert(&MBB != &MBB.getParent()->front() &&
           "no reload in start block. Missing vreg def?");

    if (PrologLiveIns.count(PhysReg)) {
      // FIXME: Theoretically this should use an insert point skipping labels
      // but I'm not sure how labels should interact with prolog instruction
      // that need reloads.
      reload(MBB.begin(), LR.VirtReg, PhysReg);
    } else
      reload(InsertBefore, LR.VirtReg, PhysReg);
  }
  LiveVirtRegs.clear();
}

/// Handle the direct use of a physical register. Displace whatever occupies it
/// and mark it pre-assigned: backwards, a use means live from here upward.
/// Returns false if nothing was displaced, so the use is a kill. This may add
/// implicit kills to MO->getParent() and invalidate MO.
bool RegAllocFastImpl::usePhysReg(MachineInstr &MI, MCRegister Reg) {
  assert(Reg.isPhysical() && "expected physreg");
  bool displacedAny = displacePhysReg(MI, Reg);
  setPhysRegState(Reg, regPreAssigned);
  markRegUsedInInstr(Reg);
  return displacedAny;
}

/// Displace whatever holds \p Reg and reserve it, so a virtual register def
/// cannot land on a register this instruction already writes. Released in the
/// free-def-operands step, after the uses for an early clobber, or by
/// lowerTiedUse(); if the instruction also reads \p Reg it ends up reserved
/// for the code above.
bool RegAllocFastImpl::definePhysReg(MachineInstr &MI, MCRegister Reg) {
  bool displacedAny = displacePhysReg(MI, Reg);
  setPhysRegState(Reg, regPreAssigned);
  return displacedAny;
}

/// Mark PhysReg as reserved or free after spilling any virtregs. This is very
/// similar to defineVirtReg except the physreg is reserved instead of
/// allocated.
bool RegAllocFastImpl::displacePhysReg(MachineInstr &MI, MCRegister PhysReg) {
  bool displacedAny = false;

  for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
    switch (unsigned VirtReg = getRegUnitState(Unit)) {
    default: {
      LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
      assert(LRI != LiveVirtRegs.end() && "datastructures in sync");
      MachineBasicBlock::iterator ReloadBefore =
          std::next((MachineBasicBlock::iterator)MI.getIterator());
      while (mayBeSpillFromInlineAsmBr(*ReloadBefore))
        ++ReloadBefore;
      reload(ReloadBefore, VirtReg, LRI->PhysReg);

      setPhysRegState(LRI->PhysReg, regFree);
      LRI->PhysReg = MCRegister();
      LRI->Reloaded = true;
      displacedAny = true;
      break;
    }
    case regPreAssigned:
      setRegUnitState(Unit, regFree);
      displacedAny = true;
      break;
    case regFree:
      break;
    }
  }
  return displacedAny;
}

void RegAllocFastImpl::freePhysReg(MCRegister PhysReg) {
  LLVM_DEBUG(dbgs() << "Freeing " << printReg(PhysReg, TRI) << ':');

  MCRegUnit FirstUnit = *TRI->regunits(PhysReg).begin();
  switch (unsigned VirtReg = getRegUnitState(FirstUnit)) {
  case regFree:
    LLVM_DEBUG(dbgs() << '\n');
    return;
  case regPreAssigned:
    LLVM_DEBUG(dbgs() << '\n');
    setPhysRegState(PhysReg, regFree);
    return;
  default: {
    LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
    assert(LRI != LiveVirtRegs.end());
    LLVM_DEBUG(dbgs() << ' ' << printReg(LRI->VirtReg, TRI) << '\n');
    setPhysRegState(LRI->PhysReg, regFree);
    LRI->PhysReg = MCRegister();
  }
    return;
  }
}

/// Return the cost of spilling clearing out PhysReg and aliases so it is free
/// for allocation. Returns 0 when PhysReg is free or disabled with all aliases
/// disabled - it can be allocated directly.
/// \returns spillImpossible when PhysReg or an alias can't be spilled.
unsigned RegAllocFastImpl::calcSpillCost(MCPhysReg PhysReg) const {
  for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
    switch (unsigned VirtReg = getRegUnitState(Unit)) {
    case regFree:
      break;
    case regPreAssigned:
      LLVM_DEBUG(dbgs() << "Cannot spill pre-assigned "
                        << printReg(PhysReg, TRI) << '\n');
      return spillImpossible;
    default: {
      bool SureSpill = StackSlotForVirtReg[VirtReg] != -1 ||
                       findLiveVirtReg(VirtReg)->LiveOut;
      return SureSpill ? spillClean : spillDirty;
    }
    }
  }
  return 0;
}

void RegAllocFastImpl::assignDanglingDebugValues(MachineInstr &Definition,
                                                 Register VirtReg,
                                                 MCRegister Reg) {
  auto UDBGValIter = DanglingDbgValues.find(VirtReg);
  if (UDBGValIter == DanglingDbgValues.end())
    return;

  SmallVectorImpl<MachineInstr *> &Dangling = UDBGValIter->second;
  for (MachineInstr *DbgValue : Dangling) {
    assert(DbgValue->isDebugValue());
    if (!DbgValue->hasDebugOperandForReg(VirtReg))
      continue;

    // Test whether the physreg survives from the definition to the DBG_VALUE.
    // A tied use that took over its def's register is assigned at an
    // instruction that overwrites it, so start the scan there.
    MCRegister SetToReg = Reg;
    unsigned Limit = 20;
    MachineBasicBlock::iterator I = Definition.getIterator();
    if (!Definition.definesRegister(Reg, TRI))
      ++I;
    for (MachineBasicBlock::iterator E = DbgValue->getIterator(); I != E; ++I) {
      if (I->modifiesRegister(Reg, TRI) || --Limit == 0) {
        LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
                          << '\n');
        SetToReg = MCRegister();
        break;
      }
    }
    for (MachineOperand &MO : DbgValue->getDebugOperandsForReg(VirtReg)) {
      MO.setReg(SetToReg);
      if (SetToReg)
        MO.setIsRenamable();
    }
  }
  Dangling.clear();
}

/// This method updates local state so that we know that PhysReg is the
/// proper container for VirtReg now.  The physical register must not be used
/// for anything else when this is called.
void RegAllocFastImpl::assignVirtToPhysReg(MachineInstr &AtMI, LiveReg &LR,
                                           MCRegister PhysReg) {
  Register VirtReg = LR.VirtReg;
  LLVM_DEBUG(dbgs() << "Assigning " << printReg(VirtReg, TRI) << " to "
                    << printReg(PhysReg, TRI) << '\n');
  assert(!LR.PhysReg && "Already assigned a physreg");
  assert(PhysReg && "Trying to assign no register");
  LR.PhysReg = PhysReg;
  setPhysRegState(PhysReg, VirtReg.id());

  assignDanglingDebugValues(AtMI, VirtReg, PhysReg);
}

static bool isCoalescable(const MachineInstr &MI) { return MI.isFullCopy(); }

/// The operand \p MO is tied to.
static const MachineOperand &getTiedOperand(const MachineInstr &MI,
                                            const MachineOperand &MO) {
  return MI.getOperand(MI.findTiedOperandIdx(MI.getOperandNo(&MO)));
}

/// The register \p DefMO's tied use reads, when the two end up in the same
/// register: a subregister index on either side makes them differ.
static Register getTiedUseReg(const MachineInstr &MI,
                              const MachineOperand &DefMO) {
  if (!DefMO.isTied() || DefMO.getSubReg())
    return Register();
  const MachineOperand &UseMO = getTiedOperand(MI, DefMO);
  return UseMO.getSubReg() ? Register() : UseMO.getReg();
}

Register RegAllocFastImpl::traceCopyChain(Register Reg) const {
  static const unsigned ChainLengthLimit = 3;
  for (unsigned C = 0; C <= ChainLengthLimit; ++C) {
    if (Reg.isPhysical())
      return Reg;
    assert(Reg.isVirtual());

    const MachineOperand *DefMO = MRI->getOneDef(Reg);
    if (!DefMO)
      return Register();
    const MachineInstr *Def = DefMO->getParent();
    if (isCoalescable(*Def)) {
      Reg = Def->getOperand(1).getReg();
      continue;
    }
    // A two-address instruction's def and tied use end up in the same
    // register, so the tie continues the chain.
    Reg = LowerTiedOps ? getTiedUseReg(*Def, *DefMO) : Register();
    if (!Reg)
      return Register();
  }
  return Register();
}

/// Check if any of \p VirtReg's definitions is a copy or a tied def. If it is
/// follow the chain of copies to check whether we reach a physical register we
/// can coalesce with.
Register RegAllocFastImpl::traceCopies(Register VirtReg) const {
  static const unsigned DefLimit = 3;
  unsigned C = 0;
  for (const MachineOperand &DefMO : MRI->def_operands(VirtReg)) {
    const MachineInstr &MI = *DefMO.getParent();
    Register Reg;
    if (isCoalescable(MI))
      Reg = MI.getOperand(1).getReg();
    else if (LowerTiedOps)
      Reg = getTiedUseReg(MI, DefMO);
    if (Reg) {
      Reg = traceCopyChain(Reg);
      if (Reg.isValid())
        return Reg;
    }

    if (++C >= DefLimit)
      break;
  }
  return Register();
}

/// Allocates a physical register for VirtReg.
void RegAllocFastImpl::allocVirtReg(MachineInstr &MI, LiveReg &LR,
                                    Register Hint0, bool LookAtPhysRegUses) {
  const Register VirtReg = LR.VirtReg;
  assert(!LR.PhysReg);

  const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
  LLVM_DEBUG(dbgs() << "Search register for " << printReg(VirtReg)
                    << " in class " << TRI->getRegClassName(&RC)
                    << " with hint " << printReg(Hint0, TRI) << '\n');

  // Take hint when possible.
  if (Hint0.isPhysical() && MRI->isAllocatable(Hint0) && RC.contains(Hint0) &&
      !isRegUsedInInstr(Hint0, LookAtPhysRegUses)) {
    // Take hint if the register is currently free.
    if (isPhysRegFree(Hint0)) {
      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint0, TRI)
                        << '\n');
      assignVirtToPhysReg(MI, LR, Hint0);
      return;
    } else {
      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint0, TRI)
                        << " occupied\n");
    }
  } else {
    Hint0 = Register();
  }

  // Try other hint.
  Register Hint1 = traceCopies(VirtReg);
  if (Hint1.isPhysical() && MRI->isAllocatable(Hint1) && RC.contains(Hint1) &&
      !isRegUsedInInstr(Hint1, LookAtPhysRegUses)) {
    // Take hint if the register is currently free.
    if (isPhysRegFree(Hint1)) {
      LLVM_DEBUG(dbgs() << "\tPreferred Register 0: " << printReg(Hint1, TRI)
                        << '\n');
      assignVirtToPhysReg(MI, LR, Hint1);
      return;
    } else {
      LLVM_DEBUG(dbgs() << "\tPreferred Register 1: " << printReg(Hint1, TRI)
                        << " occupied\n");
    }
  } else {
    Hint1 = Register();
  }

  MCPhysReg BestReg = 0;
  unsigned BestCost = spillImpossible;
  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
  for (MCPhysReg PhysReg : AllocationOrder) {
    LLVM_DEBUG(dbgs() << "\tRegister: " << printReg(PhysReg, TRI) << ' ');
    if (isRegUsedInInstr(PhysReg, LookAtPhysRegUses)) {
      LLVM_DEBUG(dbgs() << "already used in instr.\n");
      continue;
    }

    unsigned Cost = calcSpillCost(PhysReg);
    LLVM_DEBUG(dbgs() << "Cost: " << Cost << " BestCost: " << BestCost << '\n');
    // Immediate take a register with cost 0.
    if (Cost == 0) {
      assignVirtToPhysReg(MI, LR, PhysReg);
      return;
    }

    if (PhysReg == Hint0 || PhysReg == Hint1)
      Cost -= spillPrefBonus;

    if (Cost < BestCost) {
      BestReg = PhysReg;
      BestCost = Cost;
    }
  }

  if (!BestReg) {
    // Nothing we can do: Report an error and keep going with an invalid
    // allocation.
    LR.PhysReg = getErrorAssignment(LR, MI, RC);
    LR.Error = true;
    return;
  }

  displacePhysReg(MI, BestReg);
  assignVirtToPhysReg(MI, LR, BestReg);
}

void RegAllocFastImpl::allocVirtRegUndef(MachineOperand &MO) {
  assert(MO.isUndef() && "expected undef use");
  Register VirtReg = MO.getReg();
  assert(VirtReg.isVirtual() && "Expected virtreg");
  if (!shouldAllocateRegister(VirtReg))
    return;

  // If there are multiple undef uses, give them the same register. The def is
  // already freed, so take the register from the tie, not the lookup below.
  MachineInstr &MI = *MO.getParent();
  for (const MachineOperand &Tied : MI.all_uses()) {
    if (!Tied.isTied() || Tied.getReg() != VirtReg)
      continue;
    MCRegister DefReg = getTiedOperand(MI, Tied).getReg().asMCReg();
    for (MachineOperand &O : MI.all_uses()) {
      if (O.getReg() != VirtReg)
        continue;
      // The def is already narrowed, so a tie takes its register whole.
      unsigned SubIdx = O.isTied() ? 0 : O.getSubReg();
      O.setReg(SubIdx ? TRI->getSubReg(DefReg, SubIdx) : DefReg);
      O.setSubReg(0);
      O.setIsRenamable(!MRI->isReserved(O.getReg()));
    }
    return;
  }

  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
  MCRegister PhysReg;
  bool IsRenamable = true;
  if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
    PhysReg = LRI->PhysReg;
  } else {
    const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
    ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
    if (AllocationOrder.empty()) {
      // All registers in the class were reserved.
      //
      // It might be OK to take any entry from the class as this is an undef
      // use, but accepting this would give different behavior than greedy and
      // basic.
      PhysReg = getErrorAssignment(*LRI, *MO.getParent(), RC);
      LRI->Error = true;
      IsRenamable = false;
    } else
      PhysReg = AllocationOrder.front();
  }

  unsigned SubRegIdx = MO.getSubReg();
  if (SubRegIdx != 0) {
    PhysReg = TRI->getSubReg(PhysReg, SubRegIdx);
    MO.setSubReg(0);
  }
  MO.setReg(PhysReg);
  MO.setIsRenamable(IsRenamable);
}

/// Variation of defineVirtReg() with special handling for livethrough regs
/// (tied or earlyclobber) that may interfere with preassigned uses.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::defineLiveThroughVirtReg(MachineInstr &MI,
                                                unsigned OpNum,
                                                Register VirtReg) {
  if (!shouldAllocateRegister(VirtReg))
    return false;
  LiveRegMap::iterator LRI = findLiveVirtReg(VirtReg);
  if (LRI != LiveVirtRegs.end()) {
    MCRegister PrevReg = LRI->PhysReg;
    if (PrevReg && isRegUsedInInstr(PrevReg, true)) {
      LLVM_DEBUG(dbgs() << "Need new assignment for " << printReg(PrevReg, TRI)
                        << " (tied/earlyclobber resolution)\n");
      freePhysReg(PrevReg);
      LRI->PhysReg = MCRegister();
      allocVirtReg(MI, *LRI, Register(), true);
      MachineBasicBlock::iterator InsertBefore =
          std::next((MachineBasicBlock::iterator)MI.getIterator());
      LLVM_DEBUG(dbgs() << "Copy " << printReg(LRI->PhysReg, TRI) << " to "
                        << printReg(PrevReg, TRI) << '\n');
      BuildMI(*MBB, InsertBefore, MI.getDebugLoc(),
              TII->get(TargetOpcode::COPY), PrevReg)
          .addReg(LRI->PhysReg, llvm::RegState::Kill);
    }
    MachineOperand &MO = MI.getOperand(OpNum);
    if (MO.getSubReg() && !MO.isUndef()) {
      LRI->LastUse = &MI;
    }
  }
  return defineVirtReg(MI, OpNum, VirtReg, true);
}

/// Allocates a register for VirtReg definition. Typically the register is
/// already assigned from a use of the virtreg, however we still need to
/// perform an allocation if:
/// - It is a dead definition without any uses.
/// - The value is live out and all uses are in different basic blocks.
///
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::defineVirtReg(MachineInstr &MI, unsigned OpNum,
                                     Register VirtReg, bool LookAtPhysRegUses) {
  assert(VirtReg.isVirtual() && "Not a virtual register");
  if (!shouldAllocateRegister(VirtReg))
    return false;
  MachineOperand &MO = MI.getOperand(OpNum);
  LiveRegMap::iterator LRI;
  bool New;
  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
  if (New) {
    if (!MO.isDead()) {
      if (mayLiveOut(VirtReg)) {
        LRI->LiveOut = true;
      } else {
        // It is a dead def without the dead flag; add the flag now.
        MO.setIsDead(true);
      }
    }
  }
  if (!LRI->PhysReg) {
    allocVirtReg(MI, *LRI, Register(), LookAtPhysRegUses);
  } else {
    assert((!isRegUsedInInstr(LRI->PhysReg, LookAtPhysRegUses) || LRI->Error) &&
           "TODO: preassign mismatch");
    LLVM_DEBUG(dbgs() << "In def of " << printReg(VirtReg, TRI)
                      << " use existing assignment to "
                      << printReg(LRI->PhysReg, TRI) << '\n');
  }

  MCRegister PhysReg = LRI->PhysReg;
  // Either flag means a reader below depends on the slot.
  if (LRI->Reloaded || LRI->LiveOut) {
    if (!MI.isImplicitDef()) {
      MachineBasicBlock::iterator SpillBefore =
          std::next((MachineBasicBlock::iterator)MI.getIterator());
      LLVM_DEBUG(dbgs() << "Spill Reason: LO: " << LRI->LiveOut
                        << " RL: " << LRI->Reloaded << '\n');
      bool Kill = LRI->LastUse == nullptr;
      spill(SpillBefore, VirtReg, PhysReg, Kill, LRI->LiveOut);

      // We need to place additional spills for each indirect destination of an
      // INLINEASM_BR.
      if (MI.getOpcode() == TargetOpcode::INLINEASM_BR) {
        int FI = StackSlotForVirtReg[VirtReg];
        const TargetRegisterClass &RC = *MRI->getRegClass(VirtReg);
        for (MachineOperand &MO : MI.operands()) {
          if (MO.isMBB()) {
            MachineBasicBlock *Succ = MO.getMBB();
            TII->storeRegToStackSlot(*Succ, Succ->begin(), PhysReg, Kill, FI,
                                     &RC, VirtReg);
            ++NumStores;
            Succ->addLiveIn(PhysReg);
          }
        }
      }

      LRI->LastUse = nullptr;
    } else if (!LRI->LastUse) {
      // No spill was inserted, so nothing below reads this def.
      MO.setIsDead(true);
    }
    // A def above spills only if a displacement above reloads again.
    LRI->LiveOut = false;
    LRI->Reloaded = false;
  }
  if (MI.getOpcode() == TargetOpcode::BUNDLE) {
    BundleVirtRegsMap[VirtReg] = *LRI;
  }
  markRegUsedInInstr(PhysReg);
  return setPhysReg(MI, MO, *LRI);
}

/// Place MO's value in its tied def's register, by taking the register over or
/// copying into it. Return false if useVirtReg() should finish MO.
bool RegAllocFastImpl::lowerTiedUse(MachineInstr &MI, MachineOperand &MO,
                                    LiveReg &LR) {
  const MachineOperand &DefMO = getTiedOperand(MI, MO);
  assert(DefMO.getReg().isPhysical() && "tied def allocated before its use");
  MCRegister DefReg = DefMO.getReg().asMCReg();
  unsigned SubReg = MO.getSubReg();
  if (!LR.PhysReg) {
    // No register holds the value below MI, so it can live in DefReg, unless
    // MO reads a subregister, DefReg cannot hold the value, or an early-clobber
    // def would overwrite DefReg before another operand reads the value.
    bool MustCopy = SubReg || !MRI->isAllocatable(DefReg) ||
                    !MRI->getRegClass(LR.VirtReg)->contains(DefReg) ||
                    (DefMO.isEarlyClobber() &&
                     any_of(MI.all_uses(), [&](const MachineOperand &O) {
                       return &O != &MO && O.getReg() == LR.VirtReg;
                     }));
    if (!MustCopy) {
      // The def is not live above MI, so the value can occupy DefReg there.
      freePhysReg(DefReg);
      assignVirtToPhysReg(MI, LR, DefReg);
      return false;
    }
    allocVirtReg(MI, LR, Register(), false);
    // The def phase marked DefReg used in MI, so allocVirtReg skips it.
    assert((LR.Error || !TRI->regsOverlap(LR.PhysReg, DefReg)) &&
           "copy source overlaps the tied def");
  }

  MCRegister SrcReg = SubReg ? TRI->getSubReg(LR.PhysReg, SubReg) : LR.PhysReg;
  // Only an already rewritten tie (%x = OP %x) finds the value in DefReg.
  if (SrcReg == DefReg)
    return false;

  // The copy reads SrcReg above MI, so no other operand may take it.
  BuildMI(*MBB, MI, MI.getDebugLoc(), TII->get(TargetOpcode::COPY), DefReg)
      .addReg(SrcReg);
  LR.LastUse = &MI;
  markRegUsedInInstr(LR.PhysReg);

  bool Renamable = !MRI->isReserved(DefReg);
  auto ReadDefReg = [&](MachineOperand &O) {
    O.setReg(DefReg);
    O.setSubReg(0);
    O.setIsRenamable(Renamable);
  };
  ReadDefReg(MO);
  // The other reads of the value follow it into DefReg, so SrcReg dies at the
  // copy. They cannot when an early-clobber def overwrites DefReg first, and a
  // read tied to another def owes that def's register.
  if (!DefMO.isEarlyClobber()) {
    for (MachineOperand &O : MI.all_uses()) {
      if (O.isTied() || O.getReg() != LR.VirtReg || O.getSubReg() != SubReg)
        continue;
      ReadDefReg(O);
      O.setIsKill(false);
    }
  }

  // The free-defs step skips tied defs, so DefReg still holds the def.
  freePhysReg(DefReg);
  return true;
}

/// Allocates a register for a VirtReg use.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::useVirtReg(MachineInstr &MI, MachineOperand &MO,
                                  Register VirtReg) {
  assert(VirtReg.isVirtual() && "Not a virtual register");
  if (!shouldAllocateRegister(VirtReg))
    return false;
  LiveRegMap::iterator LRI;
  bool New;
  std::tie(LRI, New) = LiveVirtRegs.insert(LiveReg(VirtReg));
  if (New) {
    if (!MO.isKill()) {
      if (mayLiveOut(VirtReg)) {
        LRI->LiveOut = true;
      } else {
        // It is a last (killing) use without the kill flag; add the flag now.
        MO.setIsKill(true);
      }
    }
  } else {
    assert((!MO.isKill() || LRI->LastUse == &MI) && "Invalid kill flag");
  }

  if (LowerTiedOps && MO.isTied() && lowerTiedUse(MI, MO, *LRI))
    return false;

  // If necessary allocate a register.
  if (!LRI->PhysReg) {
    assert(!MO.isTied() && "tied op should be allocated");
    Register Hint;
    if (MI.isCopy() && MI.getOperand(1).getSubReg() == 0) {
      Hint = MI.getOperand(0).getReg();
      if (Hint.isVirtual()) {
        assert(!shouldAllocateRegister(Hint));
        Hint = Register();
      } else {
        assert(Hint.isPhysical() &&
               "Copy destination should already be assigned");
      }
    }
    allocVirtReg(MI, *LRI, Hint, false);
  }

  LRI->LastUse = &MI;

  if (MI.getOpcode() == TargetOpcode::BUNDLE) {
    BundleVirtRegsMap[VirtReg] = *LRI;
  }
  markRegUsedInInstr(LRI->PhysReg);
  return setPhysReg(MI, MO, *LRI);
}

/// Query a physical register to use as a filler in contexts where the
/// allocation has failed. This will raise an error, but not abort the
/// compilation.
MCPhysReg RegAllocFastImpl::getErrorAssignment(const LiveReg &LR,
                                               MachineInstr &MI,
                                               const TargetRegisterClass &RC) {
  MachineFunction &MF = *MI.getMF();

  // Avoid repeating the error every time a register is used.
  bool EmitError = !MF.getProperties().hasFailedRegAlloc();
  if (EmitError)
    MF.getProperties().setFailedRegAlloc();

  // If the allocation order was empty, all registers in the class were
  // probably reserved. Fall back to taking the first register in the class,
  // even if it's reserved.
  ArrayRef<MCPhysReg> AllocationOrder = RegClassInfo.getOrder(&RC);
  if (AllocationOrder.empty()) {
    const Function &Fn = MF.getFunction();
    if (EmitError) {
      Fn.getContext().diagnose(DiagnosticInfoRegAllocFailure(
          "no registers from class available to allocate", Fn,
          MI.getDebugLoc()));
    }

    ArrayRef<MCPhysReg> RawRegs = RC.getRegisters();
    assert(!RawRegs.empty() && "register classes cannot have no registers");
    return RawRegs.front();
  }

  if (!LR.Error && EmitError) {
    // Nothing we can do: Report an error and keep going with an invalid
    // allocation.
    if (MI.isInlineAsm()) {
      MI.emitInlineAsmError(
          "inline assembly requires more registers than available");
    } else {
      const Function &Fn = MBB->getParent()->getFunction();
      Fn.getContext().diagnose(DiagnosticInfoRegAllocFailure(
          "ran out of registers during register allocation", Fn,
          MI.getDebugLoc()));
    }
  }

  return AllocationOrder.front();
}

/// Changes operand OpNum in MI the refer the PhysReg, considering subregs.
/// \return true if MI's MachineOperands were re-arranged/invalidated.
bool RegAllocFastImpl::setPhysReg(MachineInstr &MI, MachineOperand &MO,
                                  const LiveReg &Assignment) {
  MCRegister PhysReg = Assignment.PhysReg;
  assert(PhysReg && "assignments should always be to a valid physreg");

  if (LLVM_UNLIKELY(Assignment.Error)) {
    // Make sure we don't set renamable in error scenarios, as we may have
    // assigned to a reserved register.
    if (MO.isUse())
      MO.setIsUndef(true);
  }

  if (!MO.getSubReg()) {
    MO.setReg(PhysReg);
    MO.setIsRenamable(!Assignment.Error);
    return false;
  }

  // Handle subregister index.
  MO.setReg(TRI->getSubReg(PhysReg, MO.getSubReg()));
  MO.setIsRenamable(!Assignment.Error);

  // Note: We leave the subreg number around a little longer in case of defs.
  // This is so that the register freeing logic in allocateInstruction can still
  // recognize this as subregister defs. The code there will clear the number.
  if (!MO.isDef())
    MO.setSubReg(0);

  // A kill flag implies killing the full register. Add corresponding super
  // register kill.
  if (MO.isKill()) {
    MI.addRegisterKilled(PhysReg, TRI, true);
    // Conservatively assume implicit MOs were re-arranged
    return true;
  }

  // A <def,read-undef> of a sub-register requires an implicit def of the full
  // register.
  if (MO.isDef() && MO.isUndef()) {
    if (MO.isDead())
      MI.addRegisterDead(PhysReg, TRI, true);
    else
      MI.addRegisterDefined(PhysReg, TRI);
    // Conservatively assume implicit MOs were re-arranged
    return true;
  }
  return false;
}

#ifndef NDEBUG

void RegAllocFastImpl::dumpState() const {
  for (MCRegUnit Unit : TRI->regunits()) {
    switch (unsigned VirtReg = getRegUnitState(Unit)) {
    case regFree:
      break;
    case regPreAssigned:
      dbgs() << " " << printRegUnit(Unit, TRI) << "[P]";
      break;
    case regLiveIn:
      llvm_unreachable("Should not have regLiveIn in map");
    default: {
      dbgs() << ' ' << printRegUnit(Unit, TRI) << '=' << printReg(VirtReg);
      LiveRegMap::const_iterator I = findLiveVirtReg(VirtReg);
      assert(I != LiveVirtRegs.end() && "have LiveVirtRegs entry");
      if (I->LiveOut || I->Reloaded) {
        dbgs() << '[';
        if (I->LiveOut)
          dbgs() << 'O';
        if (I->Reloaded)
          dbgs() << 'R';
        dbgs() << ']';
      }
      assert(TRI->hasRegUnit(I->PhysReg, Unit) && "inverse mapping present");
      break;
    }
    }
  }
  dbgs() << '\n';
  // Check that LiveVirtRegs is the inverse.
  for (const LiveReg &LR : LiveVirtRegs) {
    Register VirtReg = LR.VirtReg;
    assert(VirtReg.isVirtual() && "Bad map key");
    MCRegister PhysReg = LR.PhysReg;
    if (PhysReg) {
      assert(PhysReg.isPhysical() && "mapped to physreg");
      for (MCRegUnit Unit : TRI->regunits(PhysReg)) {
        assert(getRegUnitState(Unit) == VirtReg && "inverse map valid");
      }
    }
  }
}
#endif

/// Count number of defs consumed from each register class by \p Reg
void RegAllocFastImpl::addRegClassDefCounts(
    MutableArrayRef<unsigned> RegClassDefCounts, Register Reg) const {
  assert(RegClassDefCounts.size() == TRI->getNumRegClasses());

  if (Reg.isVirtual()) {
    if (!shouldAllocateRegister(Reg))
      return;
    const TargetRegisterClass *OpRC = MRI->getRegClass(Reg);
    for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
         RCIdx != RCIdxEnd; ++RCIdx) {
      const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
      // FIXME: Consider aliasing sub/super registers.
      if (OpRC->hasSubClassEq(IdxRC))
        ++RegClassDefCounts[RCIdx];
    }

    return;
  }

  for (unsigned RCIdx = 0, RCIdxEnd = TRI->getNumRegClasses();
       RCIdx != RCIdxEnd; ++RCIdx) {
    const TargetRegisterClass *IdxRC = TRI->getRegClass(RCIdx);
    for (MCRegAliasIterator Alias(Reg, TRI, true); Alias.isValid(); ++Alias) {
      if (IdxRC->contains(*Alias)) {
        ++RegClassDefCounts[RCIdx];
        break;
      }
    }
  }
}

/// Early clobber, partial def, or tied to a use that carries a value: the
/// register is occupied while the uses are read.
static bool isLiveThroughDef(const MachineInstr &MI, const MachineOperand &MO) {
  assert(MO.isDef() && "expected def operand");
  if (MO.isEarlyClobber() || MO.readsReg())
    return true;
  return MO.isTied() &&
         !MI.getOperand(MI.findTiedOperandIdx(MI.getOperandNo(&MO))).isUndef();
}

/// Compute \ref DefOperandIndexes so it contains the indices of "def" operands
/// that are to be allocated. Those are ordered in a way that small classes,
/// early clobbers and livethroughs are allocated first.
void RegAllocFastImpl::findAndSortDefOperandIndexes(const MachineInstr &MI) {
  DefOperandIndexes.clear();

  LLVM_DEBUG(dbgs() << "Need to assign livethroughs\n");
  for (unsigned I = 0, E = MI.getNumOperands(); I < E; ++I) {
    const MachineOperand &MO = MI.getOperand(I);
    if (!MO.isReg())
      continue;
    Register Reg = MO.getReg();
    if (MO.readsReg()) {
      if (Reg.isPhysical()) {
        LLVM_DEBUG(dbgs() << "mark extra used: " << printReg(Reg, TRI) << '\n');
        markPhysRegUsedInInstr(Reg);
      }
    }

    if (MO.isDef() && Reg.isVirtual() && shouldAllocateRegister(Reg))
      DefOperandIndexes.push_back(I);
  }

  // Most instructions only have one virtual def, so there's no point in
  // computing the possible number of defs for every register class.
  if (DefOperandIndexes.size() <= 1)
    return;

  // Track number of defs which may consume a register from the class. This is
  // used to assign registers for possibly-too-small classes first. Example:
  // defs are eax, 3 * gr32_abcd, 2 * gr32 => we want to assign the gr32_abcd
  // registers first so that the gr32 don't use the gr32_abcd registers before
  // we assign these.
  SmallVector<unsigned> RegClassDefCounts(TRI->getNumRegClasses(), 0);

  for (const MachineOperand &MO : MI.all_defs())
    addRegClassDefCounts(RegClassDefCounts, MO.getReg());

  llvm::sort(DefOperandIndexes, [&](unsigned I0, unsigned I1) {
    const MachineOperand &MO0 = MI.getOperand(I0);
    const MachineOperand &MO1 = MI.getOperand(I1);
    Register Reg0 = MO0.getReg();
    Register Reg1 = MO1.getReg();
    const TargetRegisterClass &RC0 = *MRI->getRegClass(Reg0);
    const TargetRegisterClass &RC1 = *MRI->getRegClass(Reg1);

    // Identify regclass that are easy to use up completely just in this
    // instruction.
    unsigned ClassSize0 = RegClassInfo.getOrder(&RC0).size();
    unsigned ClassSize1 = RegClassInfo.getOrder(&RC1).size();

    bool SmallClass0 = ClassSize0 < RegClassDefCounts[RC0.getID()];
    bool SmallClass1 = ClassSize1 < RegClassDefCounts[RC1.getID()];
    if (SmallClass0 > SmallClass1)
      return true;
    if (SmallClass0 < SmallClass1)
      return false;

    // Allocate early clobbers and livethrough operands first.
    bool Livethrough0 = isLiveThroughDef(MI, MO0);
    bool Livethrough1 = isLiveThroughDef(MI, MO1);
    if (Livethrough0 > Livethrough1)
      return true;
    if (Livethrough0 < Livethrough1)
      return false;

    // Tie-break rule: operand index.
    return I0 < I1;
  });
}

void RegAllocFastImpl::allocateInstruction(MachineInstr &MI) {
  // Backwards, a def frees a register and a use occupies it. The phases:
  // * pre-assigned physreg defs
  // * virtual register defs
  // * free the def operands' registers
  // * displace registers clobbered by regmasks
  // * pre-assigned physreg uses
  // * virtual register uses, inserting reloads and tied-operand copies
  // * undef uses
  // * free early-clobber defs
  //
  // Freeing follows the def allocation so a def is not handed a register this
  // instruction also writes, and precedes the uses so a use may take one. It
  // skips tied defs, whose register the tied use reads, and early-clobber defs,
  // freed last so that no use lands on them.

  InstrGen += 2;
  // In the event we ever get more than 2**31 instructions...
  if (LLVM_UNLIKELY(InstrGen == 0)) {
    UsedInInstr.assign(UsedInInstr.size(), 0);
    InstrGen = 2;
  }
  RegMasks.clear();
  LiveDefRegs.clear();
  BundleVirtRegsMap.clear();

  // Scan for special cases; Apply pre-assigned register defs to state.
  bool HasPhysRegUse = false;
  bool HasRegMask = false;
  bool HasVRegDef = false;
  bool HasDef = false;
  bool HasEarlyClobber = false;
  bool HasTiedDef = false;
  bool NeedToAssignLiveThroughs = false;
  for (MachineOperand &MO : MI.operands()) {
    if (MO.isReg()) {
      Register Reg = MO.getReg();
      if (Reg.isVirtual()) {
        if (!shouldAllocateRegister(Reg))
          continue;
        if (MO.isDef()) {
          HasDef = true;
          HasVRegDef = true;
          if (MO.isEarlyClobber())
            HasEarlyClobber = true;
          if (LowerTiedOps && MO.isTied())
            HasTiedDef = true;
          if (isLiveThroughDef(MI, MO))
            NeedToAssignLiveThroughs = true;
        }
      } else if (Reg.isPhysical()) {
        if (!MRI->isReserved(Reg)) {
          if (MO.isDef()) {
            HasDef = true;
            bool displacedAny = definePhysReg(MI, Reg);
            if (MO.isEarlyClobber())
              HasEarlyClobber = true;
            if (!displacedAny)
              MO.setIsDead(true);
            if (!MO.isDead())
              LiveDefRegs.push_back(Reg.asMCReg());
          }
          if (MO.readsReg())
            HasPhysRegUse = true;
        }
      }
    } else if (MO.isRegMask()) {
      HasRegMask = true;
      RegMasks.push_back(MO.getRegMask());
    }
  }

  // Allocate virtreg defs.
  if (HasDef) {
    if (HasVRegDef) {
      // Note that Implicit MOs can get re-arranged by defineVirtReg(), so loop
      // multiple times to ensure no operand is missed.
      bool ReArrangedImplicitOps = true;

      // Special handling for early clobbers, tied operands or subregister defs:
      // Compared to "normal" defs these:
      // - Must not use a register that is pre-assigned for a use operand.
      // - In order to solve tricky inline assembly constraints we change the
      //   heuristic to figure out a good operand order before doing
      //   assignments.
      if (NeedToAssignLiveThroughs) {
        while (ReArrangedImplicitOps) {
          ReArrangedImplicitOps = false;
          findAndSortDefOperandIndexes(MI);
          for (unsigned OpIdx : DefOperandIndexes) {
            MachineOperand &MO = MI.getOperand(OpIdx);
            LLVM_DEBUG(dbgs() << "Allocating " << MO << '\n');
            Register Reg = MO.getReg();
            if (isLiveThroughDef(MI, MO)) {
              ReArrangedImplicitOps = defineLiveThroughVirtReg(MI, OpIdx, Reg);
            } else {
              ReArrangedImplicitOps = defineVirtReg(MI, OpIdx, Reg);
            }
            // Implicit operands of MI were re-arranged,
            // re-compute DefOperandIndexes.
            if (ReArrangedImplicitOps)
              break;
          }
        }
      } else {
        // Assign virtual register defs.
        while (ReArrangedImplicitOps) {
          ReArrangedImplicitOps = false;
          for (MachineOperand &MO : MI.all_defs()) {
            Register Reg = MO.getReg();
            if (Reg.isVirtual()) {
              ReArrangedImplicitOps =
                  defineVirtReg(MI, MI.getOperandNo(&MO), Reg);
              if (ReArrangedImplicitOps)
                break;
            }
          }
        }
      }
    }

    // Free registers occupied by defs.
    // Iterate operands in reverse order, so we see the implicit super register
    // defs first (we added them earlier in case of <def,read-undef>).
    for (MachineOperand &MO : reverse(MI.all_defs())) {
      Register Reg = MO.getReg();

      // A dead def is kept alive by a non-dead def of the same register or a
      // super-register, so clear the inconsistent dead flag.
      if (Reg.isPhysical() && MO.isDead() &&
          hasLiveDefOfSuperReg(Reg.asMCReg()))
        MO.setIsDead(false);

      // subreg defs don't free the full register. We left the subreg number
      // around as a marker in setPhysReg() to recognize this case here.
      if (Reg.isPhysical() && MO.getSubReg() != 0) {
        MO.setSubReg(0);
        continue;
      }

      assert((!MO.isTied() || !isClobberedByRegMasks(MO.getReg())) &&
             "tied def assigned to clobbered register");

      // Do not free live-through defs.
      if (isLiveThroughDef(MI, MO))
        continue;
      if (!Reg)
        continue;
      if (Reg.isVirtual()) {
        assert(!shouldAllocateRegister(Reg));
        continue;
      }
      assert(Reg.isPhysical());
      if (MRI->isReserved(Reg))
        continue;
      freePhysReg(Reg);
      unmarkRegUsedInInstr(Reg);
    }
  }

  // A regmask is a def of every clobbered register: reload what lives in one
  // below MI. Nothing is reserved, so the uses may still take those registers.
  if (HasRegMask) {
    assert(!RegMasks.empty() && "expected RegMask");
    // MRI bookkeeping.
    for (const auto *RM : RegMasks)
      MRI->addPhysRegsUsedFromRegMask(RM);

    for (const LiveReg &LR : LiveVirtRegs) {
      MCRegister PhysReg = LR.PhysReg;
      if (PhysReg && isClobberedByRegMasks(PhysReg))
        displacePhysReg(MI, PhysReg);
    }
  }

  // Apply pre-assigned register uses to state.
  if (HasPhysRegUse) {
    for (MachineOperand &MO : MI.operands()) {
      if (!MO.isReg() || !MO.readsReg())
        continue;
      Register Reg = MO.getReg();
      if (!Reg.isPhysical())
        continue;
      if (MRI->isReserved(Reg))
        continue;
      if (!usePhysReg(MI, Reg))
        MO.setIsKill(true);
    }
  }

  // Allocate virtreg uses and insert reloads as necessary.
  // Implicit MOs can get moved/removed by useVirtReg(), so loop multiple
  // times to ensure no operand is missed.
  bool HasUndefUse = false;
  bool TiedOnly = HasTiedDef;
  bool ReArrangedImplicitMOs = true;
  while (ReArrangedImplicitMOs) {
    ReArrangedImplicitMOs = false;
    for (MachineOperand &MO : MI.operands()) {
      if (!MO.isReg() || !MO.isUse())
        continue;
      Register Reg = MO.getReg();
      if (!Reg.isVirtual() || !shouldAllocateRegister(Reg) ||
          (TiedOnly && !MO.isTied()))
        continue;

      if (MO.isUndef()) {
        HasUndefUse = true;
        continue;
      }

      // Populate MayLiveAcrossBlocks now: these uses are about to be rewritten
      // to physregs, so a def block allocated later can no longer see them.
      mayLiveIn(Reg);

      assert(!MO.isInternalRead() && "Bundles not supported");
      assert(MO.readsReg() && "reading use");
      ReArrangedImplicitMOs = useVirtReg(MI, MO, Reg);
      if (ReArrangedImplicitMOs)
        break;
    }
    // Given %1 = OP %0, %0(tied-def 0), allocate tied %0 first, so that %0
    // takes %1's register. In operand order, the untied %0 would take another
    // register and the tied use would need a copy.
    if (TiedOnly && !ReArrangedImplicitMOs) {
      TiedOnly = false;
      ReArrangedImplicitMOs = true;
    }
  }

  // Allocate undef operands. This is a separate step because in a situation
  // like  ` = OP undef %X, %X`    both operands need the same register assign
  // so we should perform the normal assignment first.
  if (HasUndefUse) {
    for (MachineOperand &MO : MI.all_uses()) {
      Register Reg = MO.getReg();
      if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
        continue;

      assert(MO.isUndef() && "Should only have undef virtreg uses left");
      allocVirtRegUndef(MO);
    }
  }

  // Free early clobbers. Last, because they must not share a register with any
  // use.
  if (HasEarlyClobber) {
    for (MachineOperand &MO : reverse(MI.all_defs())) {
      if (!MO.isEarlyClobber())
        continue;
      assert(!MO.getSubReg() && "should be already handled in def processing");

      Register Reg = MO.getReg();
      if (!Reg)
        continue;
      if (Reg.isVirtual()) {
        assert(!shouldAllocateRegister(Reg));
        continue;
      }
      assert(Reg.isPhysical() && "should have register assigned");

      // We sometimes get odd situations like:
      //    early-clobber %x0 = INSTRUCTION %x0
      // which is semantically questionable as the early-clobber should
      // apply before the use. But in practice we consider the use to
      // happen before the early clobber now. Don't free the early clobber
      // register in this case.
      if (MI.readsRegister(Reg, TRI))
        continue;

      freePhysReg(Reg);
    }
  }

  LLVM_DEBUG(dbgs() << "<< " << MI);
  if (MI.isCopy() &&
      (MI.getOperand(0).getReg() == MI.getOperand(1).getReg() ||
       MI.getOperand(0).isDead()) &&
      MI.getNumOperands() == 2) {
    LLVM_DEBUG(dbgs() << "Mark unnecessary copy for removal: " << MI);
    Coalesced.push_back(&MI);
  }
}

void RegAllocFastImpl::handleDebugValue(MachineInstr &MI) {
  // Ignore DBG_VALUEs that aren't based on virtual registers. These are
  // mostly constants and frame indices.
  assert(MI.isDebugValue() && "not a DBG_VALUE*");
  for (const auto &MO : MI.debug_operands()) {
    if (!MO.isReg())
      continue;
    Register Reg = MO.getReg();
    if (!Reg.isVirtual())
      continue;
    if (!shouldAllocateRegister(Reg))
      continue;

    // Already spilled to a stackslot?
    int SS = StackSlotForVirtReg[Reg];
    if (SS != -1) {
      // Modify DBG_VALUE now that the value is in a spill slot.
      updateDbgValueForSpill(MI, SS, Reg);
      LLVM_DEBUG(dbgs() << "Rewrite DBG_VALUE for spilled memory: " << MI);
      continue;
    }

    // See if this virtual register has already been allocated to a physical
    // register or spilled to a stack slot.
    LiveRegMap::iterator LRI = findLiveVirtReg(Reg);
    SmallVector<MachineOperand *> DbgOps(
        llvm::make_pointer_range(MI.getDebugOperandsForReg(Reg)));

    if (LRI != LiveVirtRegs.end() && LRI->PhysReg) {
      // Update every use of Reg within MI.
      for (auto &RegMO : DbgOps)
        setPhysReg(MI, *RegMO, *LRI);
    } else {
      DanglingDbgValues[Reg].push_back(&MI);
    }

    // If Reg hasn't been spilled, put this DBG_VALUE in LiveDbgValueMap so
    // that future spills of Reg will have DBG_VALUEs.
    LiveDbgValueMap[Reg].append(DbgOps.begin(), DbgOps.end());
  }
}

void RegAllocFastImpl::handleBundle(MachineInstr &MI) {
  MachineBasicBlock::instr_iterator BundledMI = MI.getIterator();
  ++BundledMI;
  while (BundledMI->isBundledWithPred()) {
    for (MachineOperand &MO : BundledMI->operands()) {
      if (!MO.isReg())
        continue;

      Register Reg = MO.getReg();
      if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
        continue;

      auto DI = BundleVirtRegsMap.find(Reg);
      assert(DI != BundleVirtRegsMap.end() && "Unassigned virtual register");

      setPhysReg(MI, MO, DI->second);
    }

    ++BundledMI;
  }
}

void RegAllocFastImpl::allocateBasicBlock(MachineBasicBlock &MBB) {
  this->MBB = &MBB;
  LLVM_DEBUG(dbgs() << "\nAllocating " << MBB);

  PosIndexes.unsetInitialized();
  RegUnitStates.assign(TRI->getNumRegUnits(), regFree);
  assert(LiveVirtRegs.empty() && "Mapping not cleared from last block?");

  for (const auto &LiveReg : MBB.liveouts())
    setPhysRegState(LiveReg.PhysReg, regPreAssigned);

  Coalesced.clear();

  // Lowering a tied operand inserts a copy ahead of MI. Its registers are
  // already assigned, so visiting it would evict what still lives in the
  // source.
  for (MachineInstr &MI : make_early_inc_range(reverse(MBB))) {
    LLVM_DEBUG(dbgs() << "\n>> " << MI << "Regs:"; dumpState());

    // Special handling for debug values. Note that they are not allowed to
    // affect codegen of the other instructions in any way.
    if (MI.isDebugValue()) {
      handleDebugValue(MI);
      continue;
    }

    allocateInstruction(MI);

    // Once BUNDLE header is assigned registers, same assignments need to be
    // done for bundled MIs.
    if (MI.getOpcode() == TargetOpcode::BUNDLE) {
      handleBundle(MI);
    }
  }

  LLVM_DEBUG(dbgs() << "Begin Regs:"; dumpState());

  // Spill all physical registers holding virtual registers now.
  LLVM_DEBUG(dbgs() << "Loading live registers at begin of block.\n");
  reloadAtBegin(MBB);

  // Erase all the coalesced copies. We are delaying it until now because
  // LiveVirtRegs might refer to the instrs.
  for (MachineInstr *MI : Coalesced)
    MBB.erase(MI);
  NumCoalesced += Coalesced.size();

  for (auto &UDBGPair : DanglingDbgValues) {
    for (MachineInstr *DbgValue : UDBGPair.second) {
      assert(DbgValue->isDebugValue() && "expected DBG_VALUE");
      // Nothing to do if the vreg was spilled in the meantime.
      if (!DbgValue->hasDebugOperandForReg(UDBGPair.first))
        continue;
      LLVM_DEBUG(dbgs() << "Register did not survive for " << *DbgValue
                        << '\n');
      DbgValue->setDebugValueUndef();
    }
  }
  DanglingDbgValues.clear();

  LLVM_DEBUG(MBB.dump());
}

/// Expand REG_SEQUENCE and INSERT_SUBREG into subregister COPYs: the lowering
/// TwoAddressInstructionPass performs when it runs before allocation, plus the
/// base-value copy its tie processing provides.
void RegAllocFastImpl::expandSubregPseudo(MachineInstr &MI) {
  MachineBasicBlock &MBB = *MI.getParent();
  const DebugLoc &DL = MI.getDebugLoc();
  if (MI.isInsertSubreg()) {
    // %d = INSERT_SUBREG %base, %sub, idx  ->  %d = COPY %base
    //                                          %d.idx = COPY %sub
    const MachineOperand &BaseMO = MI.getOperand(1);
    if (!BaseMO.isUndef())
      BuildMI(MBB, MI, DL, TII->get(TargetOpcode::COPY),
              MI.getOperand(0).getReg())
          .addReg(BaseMO.getReg(), RegState::NoFlags, BaseMO.getSubReg());
    unsigned SubIdx = MI.getOperand(3).getImm();
    MI.removeOperand(3);
    assert(MI.getOperand(0).getSubReg() == 0 && "Unexpected subreg idx");
    MI.getOperand(0).setSubReg(SubIdx);
    MI.getOperand(0).setIsUndef(MI.getOperand(1).isUndef());
    MI.removeOperand(1);
    MI.setDesc(TII->get(TargetOpcode::COPY));
    return;
  }

  // %d = REG_SEQUENCE %s1, idx1, ...  ->  undef %d.idx1 = COPY %s1
  //                                       %d.idx2 = COPY %s2 ...
  assert(MI.isRegSequence());
  Register Dst = MI.getOperand(0).getReg();
  // An undef source needs no copy: the read-undef flag on the first copy
  // defines the whole register. One is still needed where a use reads that
  // lane on its own, which would otherwise read an undefined subregister.
  LaneBitmask ReadLanes = LaneBitmask::getNone();
  for (const MachineOperand &Use : MRI->use_nodbg_operands(Dst))
    if (unsigned UseSubIdx = Use.getSubReg())
      ReadLanes |= TRI->getSubRegIndexLaneMask(UseSubIdx);

  bool DefEmitted = false;
  for (unsigned I = 1, E = MI.getNumOperands(); I + 1 < E; I += 2) {
    const MachineOperand &SrcMO = MI.getOperand(I);
    unsigned SubIdx = MI.getOperand(I + 1).getImm();
    if (SrcMO.isUndef() &&
        (ReadLanes & TRI->getSubRegIndexLaneMask(SubIdx)).none())
      continue;
    BuildMI(MBB, MI, DL, TII->get(TargetOpcode::COPY))
        .addReg(Dst, RegState::Define | getUndefRegState(!DefEmitted), SubIdx)
        .addReg(SrcMO.getReg(), getUndefRegState(SrcMO.isUndef()),
                SrcMO.getSubReg());
    DefEmitted = true;
  }
  // Every source was undef: uses of Dst still need a definition.
  if (!DefEmitted) {
    MI.setDesc(TII->get(TargetOpcode::IMPLICIT_DEF));
    while (MI.getNumOperands() > 1)
      MI.removeOperand(MI.getNumOperands() - 1);
    return;
  }
  MI.eraseFromParent();
}

bool RegAllocFastImpl::runOnMachineFunction(MachineFunction &MF) {
  LLVM_DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
                    << "********** Function: " << MF.getName() << '\n');
  MRI = &MF.getRegInfo();
  const TargetSubtargetInfo &STI = MF.getSubtarget();
  TRI = STI.getRegisterInfo();
  TII = STI.getInstrInfo();
  MFI = &MF.getFrameInfo();
  MRI->freezeReservedRegs();
  RegClassInfo.runOnMachineFunction(MF);
  unsigned NumRegUnits = TRI->getNumRegUnits();
  InstrGen = 0;
  UsedInInstr.assign(NumRegUnits, 0);

  // MIR that already went through TwoAddressInstructionPass carries
  // TiedOpsRewritten, so partial pipelines (-run-pass, -start-before) follow
  // the input they are given.
  LowerTiedOps = !MF.getProperties().hasTiedOpsRewritten();
  if (LowerTiedOps) {
    for (MachineBasicBlock &MBB : MF)
      for (MachineInstr &MI : make_early_inc_range(MBB))
        if (MI.isRegSequence() || MI.isInsertSubreg())
          expandSubregPseudo(MI);
  }

  // initialize the virtual->physical register map to have a 'null'
  // mapping for all virtual registers
  unsigned NumVirtRegs = MRI->getNumVirtRegs();
  StackSlotForVirtReg.resize(NumVirtRegs);
  LiveVirtRegs.setUniverse(NumVirtRegs);
  MayLiveAcrossBlocks.clear();
  MayLiveAcrossBlocks.resize(NumVirtRegs);

  // Loop over all of the basic blocks, eliminating virtual register references
  for (MachineBasicBlock &MBB : MF)
    allocateBasicBlock(MBB);

  if (ClearVirtRegs) {
    // All machine operands and other references to virtual registers have been
    // replaced. Remove the virtual registers.
    MRI->clearVirtRegs();
  }

  StackSlotForVirtReg.clear();
  LiveDbgValueMap.clear();
  return true;
}

PreservedAnalyses RegAllocFastPass::run(MachineFunction &MF,
                                        MachineFunctionAnalysisManager &) {
  MFPropsModifier _(*this, MF);
  RegAllocFastImpl Impl(Opts.Filter, Opts.ClearVRegs);
  bool Changed = Impl.runOnMachineFunction(MF);
  if (!Changed)
    return PreservedAnalyses::all();
  auto PA = getMachineFunctionPassPreservedAnalyses();
  PA.preserveSet<CFGAnalyses>();
  return PA;
}

void RegAllocFastPass::printPipeline(
    raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
  bool PrintFilterName = Opts.FilterName != "all";
  bool PrintNoClearVRegs = !Opts.ClearVRegs;
  bool PrintSemicolon = PrintFilterName && PrintNoClearVRegs;

  OS << "regallocfast";
  if (PrintFilterName || PrintNoClearVRegs) {
    OS << '<';
    if (PrintFilterName)
      OS << "filter=" << Opts.FilterName;
    if (PrintSemicolon)
      OS << ';';
    if (PrintNoClearVRegs)
      OS << "no-clear-vregs";
    OS << '>';
  }
}

FunctionPass *llvm::createFastRegisterAllocator() { return new RegAllocFast(); }

FunctionPass *llvm::createFastRegisterAllocator(RegAllocFilterFunc Ftor,
                                                bool ClearVirtRegs) {
  return new RegAllocFast(Ftor, ClearVirtRegs);
}