Restoring authorship annotation for <shadchin@yandex-team.ru>. Commit 1 of 2.

1 files changed, 1994 insertions, 1994 deletions

diff --git a/contrib/libs/llvm12/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp b/contrib/libs/llvm12/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
index e2daa46fe6..3d3d12a5b7 100644
--- a/contrib/libs/llvm12/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
+++ b/contrib/libs/llvm12/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
@@ -1,1994 +1,1994 @@
-//===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===//
-//
-// 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 VarLocBasedImpl.cpp
-///
-/// LiveDebugValues is an optimistic "available expressions" dataflow
-/// algorithm. The set of expressions is the set of machine locations
-/// (registers, spill slots, constants) that a variable fragment might be
-/// located, qualified by a DIExpression and indirect-ness flag, while each
-/// variable is identified by a DebugVariable object. The availability of an
-/// expression begins when a DBG_VALUE instruction specifies the location of a
-/// DebugVariable, and continues until that location is clobbered or
-/// re-specified by a different DBG_VALUE for the same DebugVariable.
-///
-/// The output of LiveDebugValues is additional DBG_VALUE instructions,
-/// placed to extend variable locations as far they're available. This file
-/// and the VarLocBasedLDV class is an implementation that explicitly tracks
-/// locations, using the VarLoc class.
-///
-/// The canonical "available expressions" problem doesn't have expression
-/// clobbering, instead when a variable is re-assigned, any expressions using
-/// that variable get invalidated. LiveDebugValues can map onto "available
-/// expressions" by having every register represented by a variable, which is
-/// used in an expression that becomes available at a DBG_VALUE instruction.
-/// When the register is clobbered, its variable is effectively reassigned, and
-/// expressions computed from it become unavailable. A similar construct is
-/// needed when a DebugVariable has its location re-specified, to invalidate
-/// all other locations for that DebugVariable.
-///
-/// Using the dataflow analysis to compute the available expressions, we create
-/// a DBG_VALUE at the beginning of each block where the expression is
-/// live-in. This propagates variable locations into every basic block where
-/// the location can be determined, rather than only having DBG_VALUEs in blocks
-/// where locations are specified due to an assignment or some optimization.
-/// Movements of values between registers and spill slots are annotated with
-/// DBG_VALUEs too to track variable values bewteen locations. All this allows
-/// DbgEntityHistoryCalculator to focus on only the locations within individual
-/// blocks, facilitating testing and improving modularity.
-///
-/// We follow an optimisic dataflow approach, with this lattice:
-///
-/// \verbatim
-///                    ┬ "Unknown"
-///                          |
-///                          v
-///                         True
-///                          |
-///                          v
-///                      ⊥ False
-/// \endverbatim With "True" signifying that the expression is available (and
-/// thus a DebugVariable's location is the corresponding register), while
-/// "False" signifies that the expression is unavailable. "Unknown"s never
-/// survive to the end of the analysis (see below).
-///
-/// Formally, all DebugVariable locations that are live-out of a block are
-/// initialized to \top.  A blocks live-in values take the meet of the lattice
-/// value for every predecessors live-outs, except for the entry block, where
-/// all live-ins are \bot. The usual dataflow propagation occurs: the transfer
-/// function for a block assigns an expression for a DebugVariable to be "True"
-/// if a DBG_VALUE in the block specifies it; "False" if the location is
-/// clobbered; or the live-in value if it is unaffected by the block. We
-/// visit each block in reverse post order until a fixedpoint is reached. The
-/// solution produced is maximal.
-///
-/// Intuitively, we start by assuming that every expression / variable location
-/// is at least "True", and then propagate "False" from the entry block and any
-/// clobbers until there are no more changes to make. This gives us an accurate
-/// solution because all incorrect locations will have a "False" propagated into
-/// them. It also gives us a solution that copes well with loops by assuming
-/// that variable locations are live-through every loop, and then removing those
-/// that are not through dataflow.
-///
-/// Within LiveDebugValues: each variable location is represented by a
-/// VarLoc object that identifies the source variable, its current
-/// machine-location, and the DBG_VALUE inst that specifies the location. Each
-/// VarLoc is indexed in the (function-scope) \p VarLocMap, giving each VarLoc a
-/// unique index. Rather than operate directly on machine locations, the
-/// dataflow analysis in this pass identifies locations by their index in the
-/// VarLocMap, meaning all the variable locations in a block can be described
-/// by a sparse vector of VarLocMap indicies.
-///
-/// All the storage for the dataflow analysis is local to the ExtendRanges
-/// method and passed down to helper methods. "OutLocs" and "InLocs" record the
-/// in and out lattice values for each block. "OpenRanges" maintains a list of
-/// variable locations and, with the "process" method, evaluates the transfer
-/// function of each block. "flushPendingLocs" installs DBG_VALUEs for each
-/// live-in location at the start of blocks, while "Transfers" records
-/// transfers of values between machine-locations.
-///
-/// We avoid explicitly representing the "Unknown" (\top) lattice value in the
-/// implementation. Instead, unvisited blocks implicitly have all lattice
-/// values set as "Unknown". After being visited, there will be path back to
-/// the entry block where the lattice value is "False", and as the transfer
-/// function cannot make new "Unknown" locations, there are no scenarios where
-/// a block can have an "Unknown" location after being visited. Similarly, we
-/// don't enumerate all possible variable locations before exploring the
-/// function: when a new location is discovered, all blocks previously explored
-/// were implicitly "False" but unrecorded, and become explicitly "False" when
-/// a new VarLoc is created with its bit not set in predecessor InLocs or
-/// OutLocs.
-///
-//===----------------------------------------------------------------------===//
-
-#include "LiveDebugValues.h"
-
-#include "llvm/ADT/CoalescingBitVector.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/UniqueVector.h"
-#include "llvm/CodeGen/LexicalScopes.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/MachineMemOperand.h"
-#include "llvm/CodeGen/MachineOperand.h"
-#include "llvm/CodeGen/PseudoSourceValue.h"
-#include "llvm/CodeGen/RegisterScavenging.h"
-#include "llvm/CodeGen/TargetFrameLowering.h"
-#include "llvm/CodeGen/TargetInstrInfo.h"
-#include "llvm/CodeGen/TargetLowering.h"
-#include "llvm/CodeGen/TargetPassConfig.h"
-#include "llvm/CodeGen/TargetRegisterInfo.h"
-#include "llvm/CodeGen/TargetSubtargetInfo.h"
-#include "llvm/Config/llvm-config.h"
-#include "llvm/IR/DIBuilder.h"
-#include "llvm/IR/DebugInfoMetadata.h"
-#include "llvm/IR/DebugLoc.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/Module.h"
-#include "llvm/InitializePasses.h"
-#include "llvm/MC/MCRegisterInfo.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/Compiler.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/TypeSize.h"
-#include "llvm/Support/raw_ostream.h"
-#include "llvm/Target/TargetMachine.h"
-#include <algorithm>
-#include <cassert>
-#include <cstdint>
-#include <functional>
-#include <queue>
-#include <tuple>
-#include <utility>
-#include <vector>
-
-using namespace llvm;
-
-#define DEBUG_TYPE "livedebugvalues"
-
-STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
-
-// Options to prevent pathological compile-time behavior. If InputBBLimit and
-// InputDbgValueLimit are both exceeded, range extension is disabled.
-static cl::opt<unsigned> InputBBLimit(
-    "livedebugvalues-input-bb-limit",
-    cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"),
-    cl::init(10000), cl::Hidden);
-static cl::opt<unsigned> InputDbgValueLimit(
-    "livedebugvalues-input-dbg-value-limit",
-    cl::desc(
-        "Maximum input DBG_VALUE insts supported by debug range extension"),
-    cl::init(50000), cl::Hidden);
-
-// If @MI is a DBG_VALUE with debug value described by a defined
-// register, returns the number of this register. In the other case, returns 0.
-static Register isDbgValueDescribedByReg(const MachineInstr &MI) {
-  assert(MI.isDebugValue() && "expected a DBG_VALUE");
-  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
-  // If location of variable is described using a register (directly
-  // or indirectly), this register is always a first operand.
-  return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg()
-                                       : Register();
-}
-
-/// If \p Op is a stack or frame register return true, otherwise return false.
-/// This is used to avoid basing the debug entry values on the registers, since
-/// we do not support it at the moment.
-static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
-                                  const MachineInstr &MI,
-                                  const TargetRegisterInfo *TRI) {
-  if (!Op.isReg())
-    return false;
-
-  const MachineFunction *MF = MI.getParent()->getParent();
-  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
-  Register SP = TLI->getStackPointerRegisterToSaveRestore();
-  Register FP = TRI->getFrameRegister(*MF);
-  Register Reg = Op.getReg();
-
-  return Reg && Reg != SP && Reg != FP;
-}
-
-namespace {
-
-// Max out the number of statically allocated elements in DefinedRegsSet, as
-// this prevents fallback to std::set::count() operations.
-using DefinedRegsSet = SmallSet<Register, 32>;
-
-using VarLocSet = CoalescingBitVector<uint64_t>;
-
-/// A type-checked pair of {Register Location (or 0), Index}, used to index
-/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
-/// for insertion into a \ref VarLocSet, and efficiently converted back. The
-/// type-checker helps ensure that the conversions aren't lossy.
-///
-/// Why encode a location /into/ the VarLocMap index? This makes it possible
-/// to find the open VarLocs killed by a register def very quickly. This is a
-/// performance-critical operation for LiveDebugValues.
-struct LocIndex {
-  using u32_location_t = uint32_t;
-  using u32_index_t = uint32_t;
-
-  u32_location_t Location; // Physical registers live in the range [1;2^30) (see
-                           // \ref MCRegister), so we have plenty of range left
-                           // here to encode non-register locations.
-  u32_index_t Index;
-
-  /// The first location greater than 0 that is not reserved for VarLocs of
-  /// kind RegisterKind.
-  static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30;
-
-  /// A special location reserved for VarLocs of kind SpillLocKind.
-  static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation;
-
-  /// A special location reserved for VarLocs of kind EntryValueBackupKind and
-  /// EntryValueCopyBackupKind.
-  static constexpr u32_location_t kEntryValueBackupLocation =
-      kFirstInvalidRegLocation + 1;
-
-  LocIndex(u32_location_t Location, u32_index_t Index)
-      : Location(Location), Index(Index) {}
-
-  uint64_t getAsRawInteger() const {
-    return (static_cast<uint64_t>(Location) << 32) | Index;
-  }
-
-  template<typename IntT> static LocIndex fromRawInteger(IntT ID) {
-    static_assert(std::is_unsigned<IntT>::value &&
-                      sizeof(ID) == sizeof(uint64_t),
-                  "Cannot convert raw integer to LocIndex");
-    return {static_cast<u32_location_t>(ID >> 32),
-            static_cast<u32_index_t>(ID)};
-  }
-
-  /// Get the start of the interval reserved for VarLocs of kind RegisterKind
-  /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1.
-  static uint64_t rawIndexForReg(uint32_t Reg) {
-    return LocIndex(Reg, 0).getAsRawInteger();
-  }
-
-  /// Return a range covering all set indices in the interval reserved for
-  /// \p Location in \p Set.
-  static auto indexRangeForLocation(const VarLocSet &Set,
-                                    u32_location_t Location) {
-    uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
-    uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
-    return Set.half_open_range(Start, End);
-  }
-};
-
-class VarLocBasedLDV : public LDVImpl {
-private:
-  const TargetRegisterInfo *TRI;
-  const TargetInstrInfo *TII;
-  const TargetFrameLowering *TFI;
-  TargetPassConfig *TPC;
-  BitVector CalleeSavedRegs;
-  LexicalScopes LS;
-  VarLocSet::Allocator Alloc;
-
-  enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore };
-
-  using FragmentInfo = DIExpression::FragmentInfo;
-  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
-
-  /// A pair of debug variable and value location.
-  struct VarLoc {
-    // The location at which a spilled variable resides. It consists of a
-    // register and an offset.
-    struct SpillLoc {
-      unsigned SpillBase;
-      StackOffset SpillOffset;
-      bool operator==(const SpillLoc &Other) const {
-        return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset;
-      }
-      bool operator!=(const SpillLoc &Other) const {
-        return !(*this == Other);
-      }
-    };
-
-    /// Identity of the variable at this location.
-    const DebugVariable Var;
-
-    /// The expression applied to this location.
-    const DIExpression *Expr;
-
-    /// DBG_VALUE to clone var/expr information from if this location
-    /// is moved.
-    const MachineInstr &MI;
-
-    enum VarLocKind {
-      InvalidKind = 0,
-      RegisterKind,
-      SpillLocKind,
-      ImmediateKind,
-      EntryValueKind,
-      EntryValueBackupKind,
-      EntryValueCopyBackupKind
-    } Kind = InvalidKind;
-
-    /// The value location. Stored separately to avoid repeatedly
-    /// extracting it from MI.
-    union LocUnion {
-      uint64_t RegNo;
-      SpillLoc SpillLocation;
-      uint64_t Hash;
-      int64_t Immediate;
-      const ConstantFP *FPImm;
-      const ConstantInt *CImm;
-      LocUnion() : Hash(0) {}
-    } Loc;
-
-    VarLoc(const MachineInstr &MI, LexicalScopes &LS)
-        : Var(MI.getDebugVariable(), MI.getDebugExpression(),
-              MI.getDebugLoc()->getInlinedAt()),
-          Expr(MI.getDebugExpression()), MI(MI) {
-      assert(MI.isDebugValue() && "not a DBG_VALUE");
-      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
-      if (int RegNo = isDbgValueDescribedByReg(MI)) {
-        Kind = RegisterKind;
-        Loc.RegNo = RegNo;
-      } else if (MI.getDebugOperand(0).isImm()) {
-        Kind = ImmediateKind;
-        Loc.Immediate = MI.getDebugOperand(0).getImm();
-      } else if (MI.getDebugOperand(0).isFPImm()) {
-        Kind = ImmediateKind;
-        Loc.FPImm = MI.getDebugOperand(0).getFPImm();
-      } else if (MI.getDebugOperand(0).isCImm()) {
-        Kind = ImmediateKind;
-        Loc.CImm = MI.getDebugOperand(0).getCImm();
-      }
-
-      // We create the debug entry values from the factory functions rather than
-      // from this ctor.
-      assert(Kind != EntryValueKind && !isEntryBackupLoc());
-    }
-
-    /// Take the variable and machine-location in DBG_VALUE MI, and build an
-    /// entry location using the given expression.
-    static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS,
-                                 const DIExpression *EntryExpr, Register Reg) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueKind;
-      VL.Expr = EntryExpr;
-      VL.Loc.RegNo = Reg;
-      return VL;
-    }
-
-    /// Take the variable and machine-location from the DBG_VALUE (from the
-    /// function entry), and build an entry value backup location. The backup
-    /// location will turn into the normal location if the backup is valid at
-    /// the time of the primary location clobbering.
-    static VarLoc CreateEntryBackupLoc(const MachineInstr &MI,
-                                       LexicalScopes &LS,
-                                       const DIExpression *EntryExpr) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueBackupKind;
-      VL.Expr = EntryExpr;
-      return VL;
-    }
-
-    /// Take the variable and machine-location from the DBG_VALUE (from the
-    /// function entry), and build a copy of an entry value backup location by
-    /// setting the register location to NewReg.
-    static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI,
-                                           LexicalScopes &LS,
-                                           const DIExpression *EntryExpr,
-                                           Register NewReg) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueCopyBackupKind;
-      VL.Expr = EntryExpr;
-      VL.Loc.RegNo = NewReg;
-      return VL;
-    }
-
-    /// Copy the register location in DBG_VALUE MI, updating the register to
-    /// be NewReg.
-    static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS,
-                                Register NewReg) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Loc.RegNo = NewReg;
-      return VL;
-    }
-
-    /// Take the variable described by DBG_VALUE MI, and create a VarLoc
-    /// locating it in the specified spill location.
-    static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase,
-                                 StackOffset SpillOffset, LexicalScopes &LS) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = SpillLocKind;
-      VL.Loc.SpillLocation = {SpillBase, SpillOffset};
-      return VL;
-    }
-
-    /// Create a DBG_VALUE representing this VarLoc in the given function.
-    /// Copies variable-specific information such as DILocalVariable and
-    /// inlining information from the original DBG_VALUE instruction, which may
-    /// have been several transfers ago.
-    MachineInstr *BuildDbgValue(MachineFunction &MF) const {
-      const DebugLoc &DbgLoc = MI.getDebugLoc();
-      bool Indirect = MI.isIndirectDebugValue();
-      const auto &IID = MI.getDesc();
-      const DILocalVariable *Var = MI.getDebugVariable();
-      const DIExpression *DIExpr = MI.getDebugExpression();
-      NumInserted++;
-
-      switch (Kind) {
-      case EntryValueKind:
-        // An entry value is a register location -- but with an updated
-        // expression. The register location of such DBG_VALUE is always the one
-        // from the entry DBG_VALUE, it does not matter if the entry value was
-        // copied in to another register due to some optimizations.
-        return BuildMI(MF, DbgLoc, IID, Indirect,
-                       MI.getDebugOperand(0).getReg(), Var, Expr);
-      case RegisterKind:
-        // Register locations are like the source DBG_VALUE, but with the
-        // register number from this VarLoc.
-        return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr);
-      case SpillLocKind: {
-        // Spills are indirect DBG_VALUEs, with a base register and offset.
-        // Use the original DBG_VALUEs expression to build the spilt location
-        // on top of. FIXME: spill locations created before this pass runs
-        // are not recognized, and not handled here.
-        auto *TRI = MF.getSubtarget().getRegisterInfo();
-        auto *SpillExpr = TRI->prependOffsetExpression(
-            DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset);
-        unsigned Base = Loc.SpillLocation.SpillBase;
-        return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr);
-      }
-      case ImmediateKind: {
-        MachineOperand MO = MI.getDebugOperand(0);
-        return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr);
-      }
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-      case InvalidKind:
-        llvm_unreachable(
-            "Tried to produce DBG_VALUE for invalid or backup VarLoc");
-      }
-      llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum");
-    }
-
-    /// Is the Loc field a constant or constant object?
-    bool isConstant() const { return Kind == ImmediateKind; }
-
-    /// Check if the Loc field is an entry backup location.
-    bool isEntryBackupLoc() const {
-      return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind;
-    }
-
-    /// If this variable is described by a register holding the entry value,
-    /// return it, otherwise return 0.
-    unsigned getEntryValueBackupReg() const {
-      if (Kind == EntryValueBackupKind)
-        return Loc.RegNo;
-      return 0;
-    }
-
-    /// If this variable is described by a register holding the copy of the
-    /// entry value, return it, otherwise return 0.
-    unsigned getEntryValueCopyBackupReg() const {
-      if (Kind == EntryValueCopyBackupKind)
-        return Loc.RegNo;
-      return 0;
-    }
-
-    /// If this variable is described by a register, return it,
-    /// otherwise return 0.
-    unsigned isDescribedByReg() const {
-      if (Kind == RegisterKind)
-        return Loc.RegNo;
-      return 0;
-    }
-
-    /// Determine whether the lexical scope of this value's debug location
-    /// dominates MBB.
-    bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const {
-      return LS.dominates(MI.getDebugLoc().get(), &MBB);
-    }
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-    // TRI can be null.
-    void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
-      Out << "VarLoc(";
-      switch (Kind) {
-      case RegisterKind:
-      case EntryValueKind:
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-        Out << printReg(Loc.RegNo, TRI);
-        break;
-      case SpillLocKind:
-        Out << printReg(Loc.SpillLocation.SpillBase, TRI);
-        Out << "[" << Loc.SpillLocation.SpillOffset.getFixed() << " + "
-            << Loc.SpillLocation.SpillOffset.getScalable() << "x vscale"
-            << "]";
-        break;
-      case ImmediateKind:
-        Out << Loc.Immediate;
-        break;
-      case InvalidKind:
-        llvm_unreachable("Invalid VarLoc in dump method");
-      }
-
-      Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
-      if (Var.getInlinedAt())
-        Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
-      else
-        Out << "(null))";
-
-      if (isEntryBackupLoc())
-        Out << " (backup loc)\n";
-      else
-        Out << "\n";
-    }
-#endif
-
-    bool operator==(const VarLoc &Other) const {
-      if (Kind != Other.Kind || !(Var == Other.Var) || Expr != Other.Expr)
-        return false;
-
-      switch (Kind) {
-      case SpillLocKind:
-        return Loc.SpillLocation == Other.Loc.SpillLocation;
-      case RegisterKind:
-      case ImmediateKind:
-      case EntryValueKind:
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-        return Loc.Hash == Other.Loc.Hash;
-      default:
-        llvm_unreachable("Invalid kind");
-      }
-    }
-
-    /// This operator guarantees that VarLocs are sorted by Variable first.
-    bool operator<(const VarLoc &Other) const {
-      switch (Kind) {
-      case SpillLocKind:
-        return std::make_tuple(Var, Kind, Loc.SpillLocation.SpillBase,
-                               Loc.SpillLocation.SpillOffset.getFixed(),
-                               Loc.SpillLocation.SpillOffset.getScalable(),
-                               Expr) <
-               std::make_tuple(
-                   Other.Var, Other.Kind, Other.Loc.SpillLocation.SpillBase,
-                   Other.Loc.SpillLocation.SpillOffset.getFixed(),
-                   Other.Loc.SpillLocation.SpillOffset.getScalable(),
-                   Other.Expr);
-      case RegisterKind:
-      case ImmediateKind:
-      case EntryValueKind:
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-        return std::tie(Var, Kind, Loc.Hash, Expr) <
-               std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr);
-      default:
-        llvm_unreachable("Invalid kind");
-      }
-    }
-  };
-
-  /// VarLocMap is used for two things:
-  /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to
-  ///    virtually insert a VarLoc into a VarLocSet.
-  /// 2) Given a LocIndex, look up the unique associated VarLoc.
-  class VarLocMap {
-    /// Map a VarLoc to an index within the vector reserved for its location
-    /// within Loc2Vars.
-    std::map<VarLoc, LocIndex::u32_index_t> Var2Index;
-
-    /// Map a location to a vector which holds VarLocs which live in that
-    /// location.
-    SmallDenseMap<LocIndex::u32_location_t, std::vector<VarLoc>> Loc2Vars;
-
-    /// Determine the 32-bit location reserved for \p VL, based on its kind.
-    static LocIndex::u32_location_t getLocationForVar(const VarLoc &VL) {
-      switch (VL.Kind) {
-      case VarLoc::RegisterKind:
-        assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) &&
-               "Physreg out of range?");
-        return VL.Loc.RegNo;
-      case VarLoc::SpillLocKind:
-        return LocIndex::kSpillLocation;
-      case VarLoc::EntryValueBackupKind:
-      case VarLoc::EntryValueCopyBackupKind:
-        return LocIndex::kEntryValueBackupLocation;
-      default:
-        return 0;
-      }
-    }
-
-  public:
-    /// Retrieve a unique LocIndex for \p VL.
-    LocIndex insert(const VarLoc &VL) {
-      LocIndex::u32_location_t Location = getLocationForVar(VL);
-      LocIndex::u32_index_t &Index = Var2Index[VL];
-      if (!Index) {
-        auto &Vars = Loc2Vars[Location];
-        Vars.push_back(VL);
-        Index = Vars.size();
-      }
-      return {Location, Index - 1};
-    }
-
-    /// Retrieve the unique VarLoc associated with \p ID.
-    const VarLoc &operator[](LocIndex ID) const {
-      auto LocIt = Loc2Vars.find(ID.Location);
-      assert(LocIt != Loc2Vars.end() && "Location not tracked");
-      return LocIt->second[ID.Index];
-    }
-  };
-
-  using VarLocInMBB =
-      SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>;
-  struct TransferDebugPair {
-    MachineInstr *TransferInst; ///< Instruction where this transfer occurs.
-    LocIndex LocationID;        ///< Location number for the transfer dest.
-  };
-  using TransferMap = SmallVector<TransferDebugPair, 4>;
-
-  // Types for recording sets of variable fragments that overlap. For a given
-  // local variable, we record all other fragments of that variable that could
-  // overlap it, to reduce search time.
-  using FragmentOfVar =
-      std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
-  using OverlapMap =
-      DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
-
-  // Helper while building OverlapMap, a map of all fragments seen for a given
-  // DILocalVariable.
-  using VarToFragments =
-      DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
-
-  /// This holds the working set of currently open ranges. For fast
-  /// access, this is done both as a set of VarLocIDs, and a map of
-  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all
-  /// previous open ranges for the same variable. In addition, we keep
-  /// two different maps (Vars/EntryValuesBackupVars), so erase/insert
-  /// methods act differently depending on whether a VarLoc is primary
-  /// location or backup one. In the case the VarLoc is backup location
-  /// we will erase/insert from the EntryValuesBackupVars map, otherwise
-  /// we perform the operation on the Vars.
-  class OpenRangesSet {
-    VarLocSet VarLocs;
-    // Map the DebugVariable to recent primary location ID.
-    SmallDenseMap<DebugVariable, LocIndex, 8> Vars;
-    // Map the DebugVariable to recent backup location ID.
-    SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars;
-    OverlapMap &OverlappingFragments;
-
-  public:
-    OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap)
-        : VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
-
-    const VarLocSet &getVarLocs() const { return VarLocs; }
-
-    /// Terminate all open ranges for VL.Var by removing it from the set.
-    void erase(const VarLoc &VL);
-
-    /// Terminate all open ranges listed in \c KillSet by removing
-    /// them from the set.
-    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs);
-
-    /// Insert a new range into the set.
-    void insert(LocIndex VarLocID, const VarLoc &VL);
-
-    /// Insert a set of ranges.
-    void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) {
-      for (uint64_t ID : ToLoad) {
-        LocIndex Idx = LocIndex::fromRawInteger(ID);
-        const VarLoc &VarL = Map[Idx];
-        insert(Idx, VarL);
-      }
-    }
-
-    llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var);
-
-    /// Empty the set.
-    void clear() {
-      VarLocs.clear();
-      Vars.clear();
-      EntryValuesBackupVars.clear();
-    }
-
-    /// Return whether the set is empty or not.
-    bool empty() const {
-      assert(Vars.empty() == EntryValuesBackupVars.empty() &&
-             Vars.empty() == VarLocs.empty() &&
-             "open ranges are inconsistent");
-      return VarLocs.empty();
-    }
-
-    /// Get an empty range of VarLoc IDs.
-    auto getEmptyVarLocRange() const {
-      return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(),
-                                                       getVarLocs().end());
-    }
-
-    /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg.
-    auto getRegisterVarLocs(Register Reg) const {
-      return LocIndex::indexRangeForLocation(getVarLocs(), Reg);
-    }
-
-    /// Get all set IDs for VarLocs of kind SpillLocKind.
-    auto getSpillVarLocs() const {
-      return LocIndex::indexRangeForLocation(getVarLocs(),
-                                             LocIndex::kSpillLocation);
-    }
-
-    /// Get all set IDs for VarLocs of kind EntryValueBackupKind or
-    /// EntryValueCopyBackupKind.
-    auto getEntryValueBackupVarLocs() const {
-      return LocIndex::indexRangeForLocation(
-          getVarLocs(), LocIndex::kEntryValueBackupLocation);
-    }
-  };
-
-  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind
-  /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs
-  /// into \p Collected.
-  void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs,
-                         const VarLocSet &CollectFrom) const;
-
-  /// Get the registers which are used by VarLocs of kind RegisterKind tracked
-  /// by \p CollectFrom.
-  void getUsedRegs(const VarLocSet &CollectFrom,
-                   SmallVectorImpl<uint32_t> &UsedRegs) const;
-
-  VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
-    std::unique_ptr<VarLocSet> &VLS = Locs[MBB];
-    if (!VLS)
-      VLS = std::make_unique<VarLocSet>(Alloc);
-    return *VLS.get();
-  }
-
-  const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB,
-                                   const VarLocInMBB &Locs) const {
-    auto It = Locs.find(MBB);
-    assert(It != Locs.end() && "MBB not in map");
-    return *It->second.get();
-  }
-
-  /// Tests whether this instruction is a spill to a stack location.
-  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
-
-  /// Decide if @MI is a spill instruction and return true if it is. We use 2
-  /// criteria to make this decision:
-  /// - Is this instruction a store to a spill slot?
-  /// - Is there a register operand that is both used and killed?
-  /// TODO: Store optimization can fold spills into other stores (including
-  /// other spills). We do not handle this yet (more than one memory operand).
-  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
-                       Register &Reg);
-
-  /// Returns true if the given machine instruction is a debug value which we
-  /// can emit entry values for.
-  ///
-  /// Currently, we generate debug entry values only for parameters that are
-  /// unmodified throughout the function and located in a register.
-  bool isEntryValueCandidate(const MachineInstr &MI,
-                             const DefinedRegsSet &Regs) const;
-
-  /// If a given instruction is identified as a spill, return the spill location
-  /// and set \p Reg to the spilled register.
-  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
-                                                  MachineFunction *MF,
-                                                  Register &Reg);
-  /// Given a spill instruction, extract the register and offset used to
-  /// address the spill location in a target independent way.
-  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
-  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                               TransferMap &Transfers, VarLocMap &VarLocIDs,
-                               LocIndex OldVarID, TransferKind Kind,
-                               Register NewReg = Register());
-
-  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
-                          VarLocMap &VarLocIDs);
-  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                                  VarLocMap &VarLocIDs, TransferMap &Transfers);
-  bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
-                        VarLocMap &VarLocIDs, const VarLoc &EntryVL);
-  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                       VarLocMap &VarLocIDs, TransferMap &Transfers,
-                       VarLocSet &KillSet);
-  void recordEntryValue(const MachineInstr &MI,
-                        const DefinedRegsSet &DefinedRegs,
-                        OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
-  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                            VarLocMap &VarLocIDs, TransferMap &Transfers);
-  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                           VarLocMap &VarLocIDs, TransferMap &Transfers);
-  bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,
-                          VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs);
-
-  void process(MachineInstr &MI, OpenRangesSet &OpenRanges,
-               VarLocMap &VarLocIDs, TransferMap &Transfers);
-
-  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments,
-                             OverlapMap &OLapMap);
-
-  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
-            const VarLocMap &VarLocIDs,
-            SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
-            SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks);
-
-  /// Create DBG_VALUE insts for inlocs that have been propagated but
-  /// had their instruction creation deferred.
-  void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs);
-
-  bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override;
-
-public:
-  /// Default construct and initialize the pass.
-  VarLocBasedLDV();
-
-  ~VarLocBasedLDV();
-
-  /// Print to ostream with a message.
-  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V,
-                        const VarLocMap &VarLocIDs, const char *msg,
-                        raw_ostream &Out) const;
-};
-
-} // end anonymous namespace
-
-//===----------------------------------------------------------------------===//
-//            Implementation
-//===----------------------------------------------------------------------===//
-
-VarLocBasedLDV::VarLocBasedLDV() { }
-
-VarLocBasedLDV::~VarLocBasedLDV() { }
-
-/// Erase a variable from the set of open ranges, and additionally erase any
-/// fragments that may overlap it. If the VarLoc is a backup location, erase
-/// the variable from the EntryValuesBackupVars set, indicating we should stop
-/// tracking its backup entry location. Otherwise, if the VarLoc is primary
-/// location, erase the variable from the Vars set.
-void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
-  // Erasure helper.
-  auto DoErase = [VL, this](DebugVariable VarToErase) {
-    auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-    auto It = EraseFrom->find(VarToErase);
-    if (It != EraseFrom->end()) {
-      LocIndex ID = It->second;
-      VarLocs.reset(ID.getAsRawInteger());
-      EraseFrom->erase(It);
-    }
-  };
-
-  DebugVariable Var = VL.Var;
-
-  // Erase the variable/fragment that ends here.
-  DoErase(Var);
-
-  // Extract the fragment. Interpret an empty fragment as one that covers all
-  // possible bits.
-  FragmentInfo ThisFragment = Var.getFragmentOrDefault();
-
-  // There may be fragments that overlap the designated fragment. Look them up
-  // in the pre-computed overlap map, and erase them too.
-  auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment});
-  if (MapIt != OverlappingFragments.end()) {
-    for (auto Fragment : MapIt->second) {
-      VarLocBasedLDV::OptFragmentInfo FragmentHolder;
-      if (!DebugVariable::isDefaultFragment(Fragment))
-        FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment);
-      DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
-    }
-  }
-}
-
-void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet,
-                                           const VarLocMap &VarLocIDs) {
-  VarLocs.intersectWithComplement(KillSet);
-  for (uint64_t ID : KillSet) {
-    const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)];
-    auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-    EraseFrom->erase(VL->Var);
-  }
-}
-
-void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID,
-                                            const VarLoc &VL) {
-  auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-  VarLocs.set(VarLocID.getAsRawInteger());
-  InsertInto->insert({VL.Var, VarLocID});
-}
-
-/// Return the Loc ID of an entry value backup location, if it exists for the
-/// variable.
-llvm::Optional<LocIndex>
-VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
-  auto It = EntryValuesBackupVars.find(Var);
-  if (It != EntryValuesBackupVars.end())
-    return It->second;
-
-  return llvm::None;
-}
-
-void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
-                                        const DefinedRegsSet &Regs,
-                                        const VarLocSet &CollectFrom) const {
-  assert(!Regs.empty() && "Nothing to collect");
-  SmallVector<uint32_t, 32> SortedRegs;
-  for (Register Reg : Regs)
-    SortedRegs.push_back(Reg);
-  array_pod_sort(SortedRegs.begin(), SortedRegs.end());
-  auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front()));
-  auto End = CollectFrom.end();
-  for (uint32_t Reg : SortedRegs) {
-    // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all
-    // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg.
-    uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg);
-    uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1);
-    It.advanceToLowerBound(FirstIndexForReg);
-
-    // Iterate through that half-open interval and collect all the set IDs.
-    for (; It != End && *It < FirstInvalidIndex; ++It)
-      Collected.set(*It);
-
-    if (It == End)
-      return;
-  }
-}
-
-void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
-                                  SmallVectorImpl<uint32_t> &UsedRegs) const {
-  // All register-based VarLocs are assigned indices greater than or equal to
-  // FirstRegIndex.
-  uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1);
-  uint64_t FirstInvalidIndex =
-      LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
-  for (auto It = CollectFrom.find(FirstRegIndex),
-            End = CollectFrom.find(FirstInvalidIndex);
-       It != End;) {
-    // We found a VarLoc ID for a VarLoc that lives in a register. Figure out
-    // which register and add it to UsedRegs.
-    uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location;
-    assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) &&
-           "Duplicate used reg");
-    UsedRegs.push_back(FoundReg);
-
-    // Skip to the next /set/ register. Note that this finds a lower bound, so
-    // even if there aren't any VarLocs living in `FoundReg+1`, we're still
-    // guaranteed to move on to the next register (or to end()).
-    uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1);
-    It.advanceToLowerBound(NextRegIndex);
-  }
-}
-
-//===----------------------------------------------------------------------===//
-//            Debug Range Extension Implementation
-//===----------------------------------------------------------------------===//
-
-#ifndef NDEBUG
-void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
-                                       const VarLocInMBB &V,
-                                       const VarLocMap &VarLocIDs,
-                                       const char *msg,
-                                       raw_ostream &Out) const {
-  Out << '\n' << msg << '\n';
-  for (const MachineBasicBlock &BB : MF) {
-    if (!V.count(&BB))
-      continue;
-    const VarLocSet &L = getVarLocsInMBB(&BB, V);
-    if (L.empty())
-      continue;
-    Out << "MBB: " << BB.getNumber() << ":\n";
-    for (uint64_t VLL : L) {
-      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
-      Out << " Var: " << VL.Var.getVariable()->getName();
-      Out << " MI: ";
-      VL.dump(TRI, Out);
-    }
-  }
-  Out << "\n";
-}
-#endif
-
-VarLocBasedLDV::VarLoc::SpillLoc
-VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {
-  assert(MI.hasOneMemOperand() &&
-         "Spill instruction does not have exactly one memory operand?");
-  auto MMOI = MI.memoperands_begin();
-  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
-  assert(PVal->kind() == PseudoSourceValue::FixedStack &&
-         "Inconsistent memory operand in spill instruction");
-  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
-  const MachineBasicBlock *MBB = MI.getParent();
-  Register Reg;
-  StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
-  return {Reg, Offset};
-}
-
-/// Try to salvage the debug entry value if we encounter a new debug value
-/// describing the same parameter, otherwise stop tracking the value. Return
-/// true if we should stop tracking the entry value, otherwise return false.
-bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
-                                       OpenRangesSet &OpenRanges,
-                                       VarLocMap &VarLocIDs,
-                                       const VarLoc &EntryVL) {
-  // Skip the DBG_VALUE which is the debug entry value itself.
-  if (MI.isIdenticalTo(EntryVL.MI))
-    return false;
-
-  // If the parameter's location is not register location, we can not track
-  // the entry value any more. In addition, if the debug expression from the
-  // DBG_VALUE is not empty, we can assume the parameter's value has changed
-  // indicating that we should stop tracking its entry value as well.
-  if (!MI.getDebugOperand(0).isReg() ||
-      MI.getDebugExpression()->getNumElements() != 0)
-    return true;
-
-  // If the DBG_VALUE comes from a copy instruction that copies the entry value,
-  // it means the parameter's value has not changed and we should be able to use
-  // its entry value.
-  bool TrySalvageEntryValue = false;
-  Register Reg = MI.getDebugOperand(0).getReg();
-  auto I = std::next(MI.getReverseIterator());
-  const MachineOperand *SrcRegOp, *DestRegOp;
-  if (I != MI.getParent()->rend()) {
-    // TODO: Try to keep tracking of an entry value if we encounter a propagated
-    // DBG_VALUE describing the copy of the entry value. (Propagated entry value
-    // does not indicate the parameter modification.)
-    auto DestSrc = TII->isCopyInstr(*I);
-    if (!DestSrc)
-      return true;
-
-    SrcRegOp = DestSrc->Source;
-    DestRegOp = DestSrc->Destination;
-    if (Reg != DestRegOp->getReg())
-      return true;
-    TrySalvageEntryValue = true;
-  }
-
-  if (TrySalvageEntryValue) {
-    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
-      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
-      if (VL.getEntryValueCopyBackupReg() == Reg &&
-          VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
-        return false;
-    }
-  }
-
-  return true;
-}
-
-/// End all previous ranges related to @MI and start a new range from @MI
-/// if it is a DBG_VALUE instr.
-void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
-                                         OpenRangesSet &OpenRanges,
-                                         VarLocMap &VarLocIDs) {
-  if (!MI.isDebugValue())
-    return;
-  const DILocalVariable *Var = MI.getDebugVariable();
-  const DIExpression *Expr = MI.getDebugExpression();
-  const DILocation *DebugLoc = MI.getDebugLoc();
-  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
-  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
-         "Expected inlined-at fields to agree");
-
-  DebugVariable V(Var, Expr, InlinedAt);
-
-  // Check if this DBG_VALUE indicates a parameter's value changing.
-  // If that is the case, we should stop tracking its entry value.
-  auto EntryValBackupID = OpenRanges.getEntryValueBackup(V);
-  if (Var->isParameter() && EntryValBackupID) {
-    const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
-    if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) {
-      LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
-                 MI.print(dbgs(), /*IsStandalone*/ false,
-                          /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
-                          /*AddNewLine*/ true, TII));
-      OpenRanges.erase(EntryVL);
-    }
-  }
-
-  if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() ||
-      MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) {
-    // Use normal VarLoc constructor for registers and immediates.
-    VarLoc VL(MI, LS);
-    // End all previous ranges of VL.Var.
-    OpenRanges.erase(VL);
-
-    LocIndex ID = VarLocIDs.insert(VL);
-    // Add the VarLoc to OpenRanges from this DBG_VALUE.
-    OpenRanges.insert(ID, VL);
-  } else if (MI.hasOneMemOperand()) {
-    llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?");
-  } else {
-    // This must be an undefined location. If it has an open range, erase it.
-    assert(MI.getDebugOperand(0).isReg() &&
-           MI.getDebugOperand(0).getReg() == 0 &&
-           "Unexpected non-undef DBG_VALUE encountered");
-    VarLoc VL(MI, LS);
-    OpenRanges.erase(VL);
-  }
-}
-
-/// Turn the entry value backup locations into primary locations.
-void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
-                                      OpenRangesSet &OpenRanges,
-                                      VarLocMap &VarLocIDs,
-                                      TransferMap &Transfers,
-                                      VarLocSet &KillSet) {
-  // Do not insert entry value locations after a terminator.
-  if (MI.isTerminator())
-    return;
-
-  for (uint64_t ID : KillSet) {
-    LocIndex Idx = LocIndex::fromRawInteger(ID);
-    const VarLoc &VL = VarLocIDs[Idx];
-    if (!VL.Var.getVariable()->isParameter())
-      continue;
-
-    auto DebugVar = VL.Var;
-    Optional<LocIndex> EntryValBackupID =
-        OpenRanges.getEntryValueBackup(DebugVar);
-
-    // If the parameter has the entry value backup, it means we should
-    // be able to use its entry value.
-    if (!EntryValBackupID)
-      continue;
-
-    const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
-    VarLoc EntryLoc =
-        VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo);
-    LocIndex EntryValueID = VarLocIDs.insert(EntryLoc);
-    Transfers.push_back({&MI, EntryValueID});
-    OpenRanges.insert(EntryValueID, EntryLoc);
-  }
-}
-
-/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
-/// with \p OldVarID should be deleted form \p OpenRanges and replaced with
-/// new VarLoc. If \p NewReg is different than default zero value then the
-/// new location will be register location created by the copy like instruction,
-/// otherwise it is variable's location on the stack.
-void VarLocBasedLDV::insertTransferDebugPair(
-    MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
-    VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
-    Register NewReg) {
-  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
-
-  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
-    LocIndex LocId = VarLocIDs.insert(VL);
-
-    // Close this variable's previous location range.
-    OpenRanges.erase(VL);
-
-    // Record the new location as an open range, and a postponed transfer
-    // inserting a DBG_VALUE for this location.
-    OpenRanges.insert(LocId, VL);
-    assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator");
-    TransferDebugPair MIP = {&MI, LocId};
-    Transfers.push_back(MIP);
-  };
-
-  // End all previous ranges of VL.Var.
-  OpenRanges.erase(VarLocIDs[OldVarID]);
-  switch (Kind) {
-  case TransferKind::TransferCopy: {
-    assert(NewReg &&
-           "No register supplied when handling a copy of a debug value");
-    // Create a DBG_VALUE instruction to describe the Var in its new
-    // register location.
-    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
-    ProcessVarLoc(VL);
-    LLVM_DEBUG({
-      dbgs() << "Creating VarLoc for register copy:";
-      VL.dump(TRI);
-    });
-    return;
-  }
-  case TransferKind::TransferSpill: {
-    // Create a DBG_VALUE instruction to describe the Var in its spilled
-    // location.
-    VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
-    VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase,
-                                       SpillLocation.SpillOffset, LS);
-    ProcessVarLoc(VL);
-    LLVM_DEBUG({
-      dbgs() << "Creating VarLoc for spill:";
-      VL.dump(TRI);
-    });
-    return;
-  }
-  case TransferKind::TransferRestore: {
-    assert(NewReg &&
-           "No register supplied when handling a restore of a debug value");
-    // DebugInstr refers to the pre-spill location, therefore we can reuse
-    // its expression.
-    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
-    ProcessVarLoc(VL);
-    LLVM_DEBUG({
-      dbgs() << "Creating VarLoc for restore:";
-      VL.dump(TRI);
-    });
-    return;
-  }
-  }
-  llvm_unreachable("Invalid transfer kind");
-}
-
-/// A definition of a register may mark the end of a range.
-void VarLocBasedLDV::transferRegisterDef(
-    MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs,
-    TransferMap &Transfers) {
-
-  // Meta Instructions do not affect the debug liveness of any register they
-  // define.
-  if (MI.isMetaInstruction())
-    return;
-
-  MachineFunction *MF = MI.getMF();
-  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
-  Register SP = TLI->getStackPointerRegisterToSaveRestore();
-
-  // Find the regs killed by MI, and find regmasks of preserved regs.
-  DefinedRegsSet DeadRegs;
-  SmallVector<const uint32_t *, 4> RegMasks;
-  for (const MachineOperand &MO : MI.operands()) {
-    // Determine whether the operand is a register def.
-    if (MO.isReg() && MO.isDef() && MO.getReg() &&
-        Register::isPhysicalRegister(MO.getReg()) &&
-        !(MI.isCall() && MO.getReg() == SP)) {
-      // Remove ranges of all aliased registers.
-      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)
-        // FIXME: Can we break out of this loop early if no insertion occurs?
-        DeadRegs.insert(*RAI);
-    } else if (MO.isRegMask()) {
-      RegMasks.push_back(MO.getRegMask());
-    }
-  }
-
-  // Erase VarLocs which reside in one of the dead registers. For performance
-  // reasons, it's critical to not iterate over the full set of open VarLocs.
-  // Iterate over the set of dying/used regs instead.
-  if (!RegMasks.empty()) {
-    SmallVector<uint32_t, 32> UsedRegs;
-    getUsedRegs(OpenRanges.getVarLocs(), UsedRegs);
-    for (uint32_t Reg : UsedRegs) {
-      // Remove ranges of all clobbered registers. Register masks don't usually
-      // list SP as preserved. Assume that call instructions never clobber SP,
-      // because some backends (e.g., AArch64) never list SP in the regmask.
-      // While the debug info may be off for an instruction or two around
-      // callee-cleanup calls, transferring the DEBUG_VALUE across the call is
-      // still a better user experience.
-      if (Reg == SP)
-        continue;
-      bool AnyRegMaskKillsReg =
-          any_of(RegMasks, [Reg](const uint32_t *RegMask) {
-            return MachineOperand::clobbersPhysReg(RegMask, Reg);
-          });
-      if (AnyRegMaskKillsReg)
-        DeadRegs.insert(Reg);
-    }
-  }
-
-  if (DeadRegs.empty())
-    return;
-
-  VarLocSet KillSet(Alloc);
-  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
-  OpenRanges.erase(KillSet, VarLocIDs);
-
-  if (TPC) {
-    auto &TM = TPC->getTM<TargetMachine>();
-    if (TM.Options.ShouldEmitDebugEntryValues())
-      emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
-  }
-}
-
-bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI,
-                                         MachineFunction *MF) {
-  // TODO: Handle multiple stores folded into one.
-  if (!MI.hasOneMemOperand())
-    return false;
-
-  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))
-    return false; // This is not a spill instruction, since no valid size was
-                  // returned from either function.
-
-  return true;
-}
-
-bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI,
-                                      MachineFunction *MF, Register &Reg) {
-  if (!isSpillInstruction(MI, MF))
-    return false;
-
-  auto isKilledReg = [&](const MachineOperand MO, Register &Reg) {
-    if (!MO.isReg() || !MO.isUse()) {
-      Reg = 0;
-      return false;
-    }
-    Reg = MO.getReg();
-    return MO.isKill();
-  };
-
-  for (const MachineOperand &MO : MI.operands()) {
-    // In a spill instruction generated by the InlineSpiller the spilled
-    // register has its kill flag set.
-    if (isKilledReg(MO, Reg))
-      return true;
-    if (Reg != 0) {
-      // Check whether next instruction kills the spilled register.
-      // FIXME: Current solution does not cover search for killed register in
-      // bundles and instructions further down the chain.
-      auto NextI = std::next(MI.getIterator());
-      // Skip next instruction that points to basic block end iterator.
-      if (MI.getParent()->end() == NextI)
-        continue;
-      Register RegNext;
-      for (const MachineOperand &MONext : NextI->operands()) {
-        // Return true if we came across the register from the
-        // previous spill instruction that is killed in NextI.
-        if (isKilledReg(MONext, RegNext) && RegNext == Reg)
-          return true;
-      }
-    }
-  }
-  // Return false if we didn't find spilled register.
-  return false;
-}
-
-Optional<VarLocBasedLDV::VarLoc::SpillLoc>
-VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI,
-                                      MachineFunction *MF, Register &Reg) {
-  if (!MI.hasOneMemOperand())
-    return None;
-
-  // FIXME: Handle folded restore instructions with more than one memory
-  // operand.
-  if (MI.getRestoreSize(TII)) {
-    Reg = MI.getOperand(0).getReg();
-    return extractSpillBaseRegAndOffset(MI);
-  }
-  return None;
-}
-
-/// A spilled register may indicate that we have to end the current range of
-/// a variable and create a new one for the spill location.
-/// A restored register may indicate the reverse situation.
-/// We don't want to insert any instructions in process(), so we just create
-/// the DBG_VALUE without inserting it and keep track of it in \p Transfers.
-/// It will be inserted into the BB when we're done iterating over the
-/// instructions.
-void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
-                                                 OpenRangesSet &OpenRanges,
-                                                 VarLocMap &VarLocIDs,
-                                                 TransferMap &Transfers) {
-  MachineFunction *MF = MI.getMF();
-  TransferKind TKind;
-  Register Reg;
-  Optional<VarLoc::SpillLoc> Loc;
-
-  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
-
-  // First, if there are any DBG_VALUEs pointing at a spill slot that is
-  // written to, then close the variable location. The value in memory
-  // will have changed.
-  VarLocSet KillSet(Alloc);
-  if (isSpillInstruction(MI, MF)) {
-    Loc = extractSpillBaseRegAndOffset(MI);
-    for (uint64_t ID : OpenRanges.getSpillVarLocs()) {
-      LocIndex Idx = LocIndex::fromRawInteger(ID);
-      const VarLoc &VL = VarLocIDs[Idx];
-      assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
-      if (VL.Loc.SpillLocation == *Loc) {
-        // This location is overwritten by the current instruction -- terminate
-        // the open range, and insert an explicit DBG_VALUE $noreg.
-        //
-        // Doing this at a later stage would require re-interpreting all
-        // DBG_VALUes and DIExpressions to identify whether they point at
-        // memory, and then analysing all memory writes to see if they
-        // overwrite that memory, which is expensive.
-        //
-        // At this stage, we already know which DBG_VALUEs are for spills and
-        // where they are located; it's best to fix handle overwrites now.
-        KillSet.set(ID);
-        VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0);
-        LocIndex UndefLocID = VarLocIDs.insert(UndefVL);
-        Transfers.push_back({&MI, UndefLocID});
-      }
-    }
-    OpenRanges.erase(KillSet, VarLocIDs);
-  }
-
-  // Try to recognise spill and restore instructions that may create a new
-  // variable location.
-  if (isLocationSpill(MI, MF, Reg)) {
-    TKind = TransferKind::TransferSpill;
-    LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
-    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
-                      << "\n");
-  } else {
-    if (!(Loc = isRestoreInstruction(MI, MF, Reg)))
-      return;
-    TKind = TransferKind::TransferRestore;
-    LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump(););
-    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
-                      << "\n");
-  }
-  // Check if the register or spill location is the location of a debug value.
-  auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
-  if (TKind == TransferKind::TransferSpill)
-    TransferCandidates = OpenRanges.getRegisterVarLocs(Reg);
-  else if (TKind == TransferKind::TransferRestore)
-    TransferCandidates = OpenRanges.getSpillVarLocs();
-  for (uint64_t ID : TransferCandidates) {
-    LocIndex Idx = LocIndex::fromRawInteger(ID);
-    const VarLoc &VL = VarLocIDs[Idx];
-    if (TKind == TransferKind::TransferSpill) {
-      assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?");
-      LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
-                        << VL.Var.getVariable()->getName() << ")\n");
-    } else {
-      assert(TKind == TransferKind::TransferRestore &&
-             VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
-      if (VL.Loc.SpillLocation != *Loc)
-        // The spill location is not the location of a debug value.
-        continue;
-      LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '('
-                        << VL.Var.getVariable()->getName() << ")\n");
-    }
-    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
-                            Reg);
-    // FIXME: A comment should explain why it's correct to return early here,
-    // if that is in fact correct.
-    return;
-  }
-}
-
-/// If \p MI is a register copy instruction, that copies a previously tracked
-/// value from one register to another register that is callee saved, we
-/// create new DBG_VALUE instruction  described with copy destination register.
-void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
-                                           OpenRangesSet &OpenRanges,
-                                           VarLocMap &VarLocIDs,
-                                           TransferMap &Transfers) {
-  auto DestSrc = TII->isCopyInstr(MI);
-  if (!DestSrc)
-    return;
-
-  const MachineOperand *DestRegOp = DestSrc->Destination;
-  const MachineOperand *SrcRegOp = DestSrc->Source;
-
-  if (!DestRegOp->isDef())
-    return;
-
-  auto isCalleeSavedReg = [&](Register Reg) {
-    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
-      if (CalleeSavedRegs.test(*RAI))
-        return true;
-    return false;
-  };
-
-  Register SrcReg = SrcRegOp->getReg();
-  Register DestReg = DestRegOp->getReg();
-
-  // We want to recognize instructions where destination register is callee
-  // saved register. If register that could be clobbered by the call is
-  // included, there would be a great chance that it is going to be clobbered
-  // soon. It is more likely that previous register location, which is callee
-  // saved, is going to stay unclobbered longer, even if it is killed.
-  if (!isCalleeSavedReg(DestReg))
-    return;
-
-  // Remember an entry value movement. If we encounter a new debug value of
-  // a parameter describing only a moving of the value around, rather then
-  // modifying it, we are still able to use the entry value if needed.
-  if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) {
-    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
-      LocIndex Idx = LocIndex::fromRawInteger(ID);
-      const VarLoc &VL = VarLocIDs[Idx];
-      if (VL.getEntryValueBackupReg() == SrcReg) {
-        LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump(););
-        VarLoc EntryValLocCopyBackup =
-            VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg);
-
-        // Stop tracking the original entry value.
-        OpenRanges.erase(VL);
-
-        // Start tracking the entry value copy.
-        LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup);
-        OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup);
-        break;
-      }
-    }
-  }
-
-  if (!SrcRegOp->isKill())
-    return;
-
-  for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) {
-    LocIndex Idx = LocIndex::fromRawInteger(ID);
-    assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?");
-    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
-                            TransferKind::TransferCopy, DestReg);
-    // FIXME: A comment should explain why it's correct to return early here,
-    // if that is in fact correct.
-    return;
-  }
-}
-
-/// Terminate all open ranges at the end of the current basic block.
-bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
-                                         OpenRangesSet &OpenRanges,
-                                         VarLocInMBB &OutLocs,
-                                         const VarLocMap &VarLocIDs) {
-  bool Changed = false;
-
-  LLVM_DEBUG(for (uint64_t ID
-                  : OpenRanges.getVarLocs()) {
-    // Copy OpenRanges to OutLocs, if not already present.
-    dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
-    VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI);
-  });
-  VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
-  Changed = VLS != OpenRanges.getVarLocs();
-  // New OutLocs set may be different due to spill, restore or register
-  // copy instruction processing.
-  if (Changed)
-    VLS = OpenRanges.getVarLocs();
-  OpenRanges.clear();
-  return Changed;
-}
-
-/// Accumulate a mapping between each DILocalVariable fragment and other
-/// fragments of that DILocalVariable which overlap. This reduces work during
-/// the data-flow stage from "Find any overlapping fragments" to "Check if the
-/// known-to-overlap fragments are present".
-/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for
-///           fragment usage.
-/// \param SeenFragments Map from DILocalVariable to all fragments of that
-///           Variable which are known to exist.
-/// \param OverlappingFragments The overlap map being constructed, from one
-///           Var/Fragment pair to a vector of fragments known to overlap.
-void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI,
-                                            VarToFragments &SeenFragments,
-                                            OverlapMap &OverlappingFragments) {
-  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),
-                      MI.getDebugLoc()->getInlinedAt());
-  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
-
-  // If this is the first sighting of this variable, then we are guaranteed
-  // there are currently no overlapping fragments either. Initialize the set
-  // of seen fragments, record no overlaps for the current one, and return.
-  auto SeenIt = SeenFragments.find(MIVar.getVariable());
-  if (SeenIt == SeenFragments.end()) {
-    SmallSet<FragmentInfo, 4> OneFragment;
-    OneFragment.insert(ThisFragment);
-    SeenFragments.insert({MIVar.getVariable(), OneFragment});
-
-    OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
-    return;
-  }
-
-  // If this particular Variable/Fragment pair already exists in the overlap
-  // map, it has already been accounted for.
-  auto IsInOLapMap =
-      OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});
-  if (!IsInOLapMap.second)
-    return;
-
-  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
-  auto &AllSeenFragments = SeenIt->second;
-
-  // Otherwise, examine all other seen fragments for this variable, with "this"
-  // fragment being a previously unseen fragment. Record any pair of
-  // overlapping fragments.
-  for (auto &ASeenFragment : AllSeenFragments) {
-    // Does this previously seen fragment overlap?
-    if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
-      // Yes: Mark the current fragment as being overlapped.
-      ThisFragmentsOverlaps.push_back(ASeenFragment);
-      // Mark the previously seen fragment as being overlapped by the current
-      // one.
-      auto ASeenFragmentsOverlaps =
-          OverlappingFragments.find({MIVar.getVariable(), ASeenFragment});
-      assert(ASeenFragmentsOverlaps != OverlappingFragments.end() &&
-             "Previously seen var fragment has no vector of overlaps");
-      ASeenFragmentsOverlaps->second.push_back(ThisFragment);
-    }
-  }
-
-  AllSeenFragments.insert(ThisFragment);
-}
-
-/// This routine creates OpenRanges.
-void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges,
-                              VarLocMap &VarLocIDs, TransferMap &Transfers) {
-  transferDebugValue(MI, OpenRanges, VarLocIDs);
-  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers);
-  transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers);
-  transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers);
-}
-
-/// This routine joins the analysis results of all incoming edges in @MBB by
-/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same
-/// source variable in all the predecessors of @MBB reside in the same location.
-bool VarLocBasedLDV::join(
-    MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs,
-    const VarLocMap &VarLocIDs,
-    SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
-    SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) {
-  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
-
-  VarLocSet InLocsT(Alloc); // Temporary incoming locations.
-
-  // For all predecessors of this MBB, find the set of VarLocs that
-  // can be joined.
-  int NumVisited = 0;
-  for (auto p : MBB.predecessors()) {
-    // Ignore backedges if we have not visited the predecessor yet. As the
-    // predecessor hasn't yet had locations propagated into it, most locations
-    // will not yet be valid, so treat them as all being uninitialized and
-    // potentially valid. If a location guessed to be correct here is
-    // invalidated later, we will remove it when we revisit this block.
-    if (!Visited.count(p)) {
-      LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber()
-                        << "\n");
-      continue;
-    }
-    auto OL = OutLocs.find(p);
-    // Join is null in case of empty OutLocs from any of the pred.
-    if (OL == OutLocs.end())
-      return false;
-
-    // Just copy over the Out locs to incoming locs for the first visited
-    // predecessor, and for all other predecessors join the Out locs.
-    VarLocSet &OutLocVLS = *OL->second.get();
-    if (!NumVisited)
-      InLocsT = OutLocVLS;
-    else
-      InLocsT &= OutLocVLS;
-
-    LLVM_DEBUG({
-      if (!InLocsT.empty()) {
-        for (uint64_t ID : InLocsT)
-          dbgs() << "  gathered candidate incoming var: "
-                 << VarLocIDs[LocIndex::fromRawInteger(ID)]
-                        .Var.getVariable()
-                        ->getName()
-                 << "\n";
-      }
-    });
-
-    NumVisited++;
-  }
-
-  // Filter out DBG_VALUES that are out of scope.
-  VarLocSet KillSet(Alloc);
-  bool IsArtificial = ArtificialBlocks.count(&MBB);
-  if (!IsArtificial) {
-    for (uint64_t ID : InLocsT) {
-      LocIndex Idx = LocIndex::fromRawInteger(ID);
-      if (!VarLocIDs[Idx].dominates(LS, MBB)) {
-        KillSet.set(ID);
-        LLVM_DEBUG({
-          auto Name = VarLocIDs[Idx].Var.getVariable()->getName();
-          dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n";
-        });
-      }
-    }
-  }
-  InLocsT.intersectWithComplement(KillSet);
-
-  // As we are processing blocks in reverse post-order we
-  // should have processed at least one predecessor, unless it
-  // is the entry block which has no predecessor.
-  assert((NumVisited || MBB.pred_empty()) &&
-         "Should have processed at least one predecessor");
-
-  VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs);
-  bool Changed = false;
-  if (ILS != InLocsT) {
-    ILS = InLocsT;
-    Changed = true;
-  }
-
-  return Changed;
-}
-
-void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
-                                       VarLocMap &VarLocIDs) {
-  // PendingInLocs records all locations propagated into blocks, which have
-  // not had DBG_VALUE insts created. Go through and create those insts now.
-  for (auto &Iter : PendingInLocs) {
-    // Map is keyed on a constant pointer, unwrap it so we can insert insts.
-    auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
-    VarLocSet &Pending = *Iter.second.get();
-
-    for (uint64_t ID : Pending) {
-      // The ID location is live-in to MBB -- work out what kind of machine
-      // location it is and create a DBG_VALUE.
-      const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)];
-      if (DiffIt.isEntryBackupLoc())
-        continue;
-      MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent());
-      MBB.insert(MBB.instr_begin(), MI);
-
-      (void)MI;
-      LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
-    }
-  }
-}
-
-bool VarLocBasedLDV::isEntryValueCandidate(
-    const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {
-  assert(MI.isDebugValue() && "This must be DBG_VALUE.");
-
-  // TODO: Add support for local variables that are expressed in terms of
-  // parameters entry values.
-  // TODO: Add support for modified arguments that can be expressed
-  // by using its entry value.
-  auto *DIVar = MI.getDebugVariable();
-  if (!DIVar->isParameter())
-    return false;
-
-  // Do not consider parameters that belong to an inlined function.
-  if (MI.getDebugLoc()->getInlinedAt())
-    return false;
-
-  // Only consider parameters that are described using registers. Parameters
-  // that are passed on the stack are not yet supported, so ignore debug
-  // values that are described by the frame or stack pointer.
-  if (!isRegOtherThanSPAndFP(MI.getDebugOperand(0), MI, TRI))
-    return false;
-
-  // If a parameter's value has been propagated from the caller, then the
-  // parameter's DBG_VALUE may be described using a register defined by some
-  // instruction in the entry block, in which case we shouldn't create an
-  // entry value.
-  if (DefinedRegs.count(MI.getDebugOperand(0).getReg()))
-    return false;
-
-  // TODO: Add support for parameters that have a pre-existing debug expressions
-  // (e.g. fragments).
-  if (MI.getDebugExpression()->getNumElements() > 0)
-    return false;
-
-  return true;
-}
-
-/// Collect all register defines (including aliases) for the given instruction.
-static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
-                           const TargetRegisterInfo *TRI) {
-  for (const MachineOperand &MO : MI.operands())
-    if (MO.isReg() && MO.isDef() && MO.getReg())
-      for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
-        Regs.insert(*AI);
-}
-
-/// This routine records the entry values of function parameters. The values
-/// could be used as backup values. If we loose the track of some unmodified
-/// parameters, the backup values will be used as a primary locations.
-void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
-                                       const DefinedRegsSet &DefinedRegs,
-                                       OpenRangesSet &OpenRanges,
-                                       VarLocMap &VarLocIDs) {
-  if (TPC) {
-    auto &TM = TPC->getTM<TargetMachine>();
-    if (!TM.Options.ShouldEmitDebugEntryValues())
-      return;
-  }
-
-  DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(),
-                  MI.getDebugLoc()->getInlinedAt());
-
-  if (!isEntryValueCandidate(MI, DefinedRegs) ||
-      OpenRanges.getEntryValueBackup(V))
-    return;
-
-  LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump(););
-
-  // Create the entry value and use it as a backup location until it is
-  // valid. It is valid until a parameter is not changed.
-  DIExpression *NewExpr =
-      DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
-  VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
-  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
-  OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
-}
-
-/// Calculate the liveness information for the given machine function and
-/// extend ranges across basic blocks.
-bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
-  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
-
-  if (!MF.getFunction().getSubprogram())
-    // VarLocBaseLDV will already have removed all DBG_VALUEs.
-    return false;
-
-  // Skip functions from NoDebug compilation units.
-  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() ==
-      DICompileUnit::NoDebug)
-    return false;
-
-  TRI = MF.getSubtarget().getRegisterInfo();
-  TII = MF.getSubtarget().getInstrInfo();
-  TFI = MF.getSubtarget().getFrameLowering();
-  TFI->getCalleeSaves(MF, CalleeSavedRegs);
-  this->TPC = TPC;
-  LS.initialize(MF);
-
-  bool Changed = false;
-  bool OLChanged = false;
-  bool MBBJoined = false;
-
-  VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
-  OverlapMap OverlapFragments; // Map of overlapping variable fragments.
-  OpenRangesSet OpenRanges(Alloc, OverlapFragments);
-                              // Ranges that are open until end of bb.
-  VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
-  VarLocInMBB InLocs;         // Ranges that are incoming after joining.
-  TransferMap Transfers;      // DBG_VALUEs associated with transfers (such as
-                              // spills, copies and restores).
-
-  VarToFragments SeenFragments;
-
-  // Blocks which are artificial, i.e. blocks which exclusively contain
-  // instructions without locations, or with line 0 locations.
-  SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
-
-  DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
-  DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
-  std::priority_queue<unsigned int, std::vector<unsigned int>,
-                      std::greater<unsigned int>>
-      Worklist;
-  std::priority_queue<unsigned int, std::vector<unsigned int>,
-                      std::greater<unsigned int>>
-      Pending;
-
-  // Set of register defines that are seen when traversing the entry block
-  // looking for debug entry value candidates.
-  DefinedRegsSet DefinedRegs;
-
-  // Only in the case of entry MBB collect DBG_VALUEs representing
-  // function parameters in order to generate debug entry values for them.
-  MachineBasicBlock &First_MBB = *(MF.begin());
-  for (auto &MI : First_MBB) {
-    collectRegDefs(MI, DefinedRegs, TRI);
-    if (MI.isDebugValue())
-      recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs);
-  }
-
-  // Initialize per-block structures and scan for fragment overlaps.
-  for (auto &MBB : MF)
-    for (auto &MI : MBB)
-      if (MI.isDebugValue())
-        accumulateFragmentMap(MI, SeenFragments, OverlapFragments);
-
-  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
-    if (const DebugLoc &DL = MI.getDebugLoc())
-      return DL.getLine() != 0;
-    return false;
-  };
-  for (auto &MBB : MF)
-    if (none_of(MBB.instrs(), hasNonArtificialLocation))
-      ArtificialBlocks.insert(&MBB);
-
-  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
-                              "OutLocs after initialization", dbgs()));
-
-  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
-  unsigned int RPONumber = 0;
-  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) {
-    OrderToBB[RPONumber] = *RI;
-    BBToOrder[*RI] = RPONumber;
-    Worklist.push(RPONumber);
-    ++RPONumber;
-  }
-
-  if (RPONumber > InputBBLimit) {
-    unsigned NumInputDbgValues = 0;
-    for (auto &MBB : MF)
-      for (auto &MI : MBB)
-        if (MI.isDebugValue())
-          ++NumInputDbgValues;
-    if (NumInputDbgValues > InputDbgValueLimit) {
-      LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName()
-                        << " has " << RPONumber << " basic blocks and "
-                        << NumInputDbgValues
-                        << " input DBG_VALUEs, exceeding limits.\n");
-      return false;
-    }
-  }
-
-  // This is a standard "union of predecessor outs" dataflow problem.
-  // To solve it, we perform join() and process() using the two worklist method
-  // until the ranges converge.
-  // Ranges have converged when both worklists are empty.
-  SmallPtrSet<const MachineBasicBlock *, 16> Visited;
-  while (!Worklist.empty() || !Pending.empty()) {
-    // We track what is on the pending worklist to avoid inserting the same
-    // thing twice.  We could avoid this with a custom priority queue, but this
-    // is probably not worth it.
-    SmallPtrSet<MachineBasicBlock *, 16> OnPending;
-    LLVM_DEBUG(dbgs() << "Processing Worklist\n");
-    while (!Worklist.empty()) {
-      MachineBasicBlock *MBB = OrderToBB[Worklist.top()];
-      Worklist.pop();
-      MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited,
-                       ArtificialBlocks);
-      MBBJoined |= Visited.insert(MBB).second;
-      if (MBBJoined) {
-        MBBJoined = false;
-        Changed = true;
-        // Now that we have started to extend ranges across BBs we need to
-        // examine spill, copy and restore instructions to see whether they
-        // operate with registers that correspond to user variables.
-        // First load any pending inlocs.
-        OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs);
-        for (auto &MI : *MBB)
-          process(MI, OpenRanges, VarLocIDs, Transfers);
-        OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs);
-
-        LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs,
-                                    "OutLocs after propagating", dbgs()));
-        LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs,
-                                    "InLocs after propagating", dbgs()));
-
-        if (OLChanged) {
-          OLChanged = false;
-          for (auto s : MBB->successors())
-            if (OnPending.insert(s).second) {
-              Pending.push(BBToOrder[s]);
-            }
-        }
-      }
-    }
-    Worklist.swap(Pending);
-    // At this point, pending must be empty, since it was just the empty
-    // worklist
-    assert(Pending.empty() && "Pending should be empty");
-  }
-
-  // Add any DBG_VALUE instructions created by location transfers.
-  for (auto &TR : Transfers) {
-    assert(!TR.TransferInst->isTerminator() &&
-           "Cannot insert DBG_VALUE after terminator");
-    MachineBasicBlock *MBB = TR.TransferInst->getParent();
-    const VarLoc &VL = VarLocIDs[TR.LocationID];
-    MachineInstr *MI = VL.BuildDbgValue(MF);
-    MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI);
-  }
-  Transfers.clear();
-
-  // Deferred inlocs will not have had any DBG_VALUE insts created; do
-  // that now.
-  flushPendingLocs(InLocs, VarLocIDs);
-
-  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs()));
-  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs()));
-  return Changed;
-}
-
-LDVImpl *
-llvm::makeVarLocBasedLiveDebugValues()
-{
-  return new VarLocBasedLDV();
-}
+//===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===// 
+// 
+// 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 VarLocBasedImpl.cpp 
+/// 
+/// LiveDebugValues is an optimistic "available expressions" dataflow 
+/// algorithm. The set of expressions is the set of machine locations 
+/// (registers, spill slots, constants) that a variable fragment might be 
+/// located, qualified by a DIExpression and indirect-ness flag, while each 
+/// variable is identified by a DebugVariable object. The availability of an 
+/// expression begins when a DBG_VALUE instruction specifies the location of a 
+/// DebugVariable, and continues until that location is clobbered or 
+/// re-specified by a different DBG_VALUE for the same DebugVariable. 
+/// 
+/// The output of LiveDebugValues is additional DBG_VALUE instructions, 
+/// placed to extend variable locations as far they're available. This file 
+/// and the VarLocBasedLDV class is an implementation that explicitly tracks 
+/// locations, using the VarLoc class. 
+/// 
+/// The canonical "available expressions" problem doesn't have expression 
+/// clobbering, instead when a variable is re-assigned, any expressions using 
+/// that variable get invalidated. LiveDebugValues can map onto "available 
+/// expressions" by having every register represented by a variable, which is 
+/// used in an expression that becomes available at a DBG_VALUE instruction. 
+/// When the register is clobbered, its variable is effectively reassigned, and 
+/// expressions computed from it become unavailable. A similar construct is 
+/// needed when a DebugVariable has its location re-specified, to invalidate 
+/// all other locations for that DebugVariable. 
+/// 
+/// Using the dataflow analysis to compute the available expressions, we create 
+/// a DBG_VALUE at the beginning of each block where the expression is 
+/// live-in. This propagates variable locations into every basic block where 
+/// the location can be determined, rather than only having DBG_VALUEs in blocks 
+/// where locations are specified due to an assignment or some optimization. 
+/// Movements of values between registers and spill slots are annotated with 
+/// DBG_VALUEs too to track variable values bewteen locations. All this allows 
+/// DbgEntityHistoryCalculator to focus on only the locations within individual 
+/// blocks, facilitating testing and improving modularity. 
+/// 
+/// We follow an optimisic dataflow approach, with this lattice: 
+/// 
+/// \verbatim 
+///                    ┬ "Unknown" 
+///                          | 
+///                          v 
+///                         True 
+///                          | 
+///                          v 
+///                      ⊥ False 
+/// \endverbatim With "True" signifying that the expression is available (and 
+/// thus a DebugVariable's location is the corresponding register), while 
+/// "False" signifies that the expression is unavailable. "Unknown"s never 
+/// survive to the end of the analysis (see below). 
+/// 
+/// Formally, all DebugVariable locations that are live-out of a block are 
+/// initialized to \top.  A blocks live-in values take the meet of the lattice 
+/// value for every predecessors live-outs, except for the entry block, where 
+/// all live-ins are \bot. The usual dataflow propagation occurs: the transfer 
+/// function for a block assigns an expression for a DebugVariable to be "True" 
+/// if a DBG_VALUE in the block specifies it; "False" if the location is 
+/// clobbered; or the live-in value if it is unaffected by the block. We 
+/// visit each block in reverse post order until a fixedpoint is reached. The 
+/// solution produced is maximal. 
+/// 
+/// Intuitively, we start by assuming that every expression / variable location 
+/// is at least "True", and then propagate "False" from the entry block and any 
+/// clobbers until there are no more changes to make. This gives us an accurate 
+/// solution because all incorrect locations will have a "False" propagated into 
+/// them. It also gives us a solution that copes well with loops by assuming 
+/// that variable locations are live-through every loop, and then removing those 
+/// that are not through dataflow. 
+/// 
+/// Within LiveDebugValues: each variable location is represented by a 
+/// VarLoc object that identifies the source variable, its current 
+/// machine-location, and the DBG_VALUE inst that specifies the location. Each 
+/// VarLoc is indexed in the (function-scope) \p VarLocMap, giving each VarLoc a 
+/// unique index. Rather than operate directly on machine locations, the 
+/// dataflow analysis in this pass identifies locations by their index in the 
+/// VarLocMap, meaning all the variable locations in a block can be described 
+/// by a sparse vector of VarLocMap indicies. 
+/// 
+/// All the storage for the dataflow analysis is local to the ExtendRanges 
+/// method and passed down to helper methods. "OutLocs" and "InLocs" record the 
+/// in and out lattice values for each block. "OpenRanges" maintains a list of 
+/// variable locations and, with the "process" method, evaluates the transfer 
+/// function of each block. "flushPendingLocs" installs DBG_VALUEs for each 
+/// live-in location at the start of blocks, while "Transfers" records 
+/// transfers of values between machine-locations. 
+/// 
+/// We avoid explicitly representing the "Unknown" (\top) lattice value in the 
+/// implementation. Instead, unvisited blocks implicitly have all lattice 
+/// values set as "Unknown". After being visited, there will be path back to 
+/// the entry block where the lattice value is "False", and as the transfer 
+/// function cannot make new "Unknown" locations, there are no scenarios where 
+/// a block can have an "Unknown" location after being visited. Similarly, we 
+/// don't enumerate all possible variable locations before exploring the 
+/// function: when a new location is discovered, all blocks previously explored 
+/// were implicitly "False" but unrecorded, and become explicitly "False" when 
+/// a new VarLoc is created with its bit not set in predecessor InLocs or 
+/// OutLocs. 
+/// 
+//===----------------------------------------------------------------------===// 
+ 
+#include "LiveDebugValues.h" 
+ 
+#include "llvm/ADT/CoalescingBitVector.h" 
+#include "llvm/ADT/DenseMap.h" 
+#include "llvm/ADT/PostOrderIterator.h" 
+#include "llvm/ADT/SmallPtrSet.h" 
+#include "llvm/ADT/SmallSet.h" 
+#include "llvm/ADT/SmallVector.h" 
+#include "llvm/ADT/Statistic.h" 
+#include "llvm/ADT/UniqueVector.h" 
+#include "llvm/CodeGen/LexicalScopes.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/MachineMemOperand.h" 
+#include "llvm/CodeGen/MachineOperand.h" 
+#include "llvm/CodeGen/PseudoSourceValue.h" 
+#include "llvm/CodeGen/RegisterScavenging.h" 
+#include "llvm/CodeGen/TargetFrameLowering.h" 
+#include "llvm/CodeGen/TargetInstrInfo.h" 
+#include "llvm/CodeGen/TargetLowering.h" 
+#include "llvm/CodeGen/TargetPassConfig.h" 
+#include "llvm/CodeGen/TargetRegisterInfo.h" 
+#include "llvm/CodeGen/TargetSubtargetInfo.h" 
+#include "llvm/Config/llvm-config.h" 
+#include "llvm/IR/DIBuilder.h" 
+#include "llvm/IR/DebugInfoMetadata.h" 
+#include "llvm/IR/DebugLoc.h" 
+#include "llvm/IR/Function.h" 
+#include "llvm/IR/Module.h" 
+#include "llvm/InitializePasses.h" 
+#include "llvm/MC/MCRegisterInfo.h" 
+#include "llvm/Pass.h" 
+#include "llvm/Support/Casting.h" 
+#include "llvm/Support/Compiler.h" 
+#include "llvm/Support/Debug.h" 
+#include "llvm/Support/TypeSize.h" 
+#include "llvm/Support/raw_ostream.h" 
+#include "llvm/Target/TargetMachine.h" 
+#include <algorithm> 
+#include <cassert> 
+#include <cstdint> 
+#include <functional> 
+#include <queue> 
+#include <tuple> 
+#include <utility> 
+#include <vector> 
+ 
+using namespace llvm; 
+ 
+#define DEBUG_TYPE "livedebugvalues" 
+ 
+STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); 
+ 
+// Options to prevent pathological compile-time behavior. If InputBBLimit and 
+// InputDbgValueLimit are both exceeded, range extension is disabled. 
+static cl::opt<unsigned> InputBBLimit( 
+    "livedebugvalues-input-bb-limit", 
+    cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), 
+    cl::init(10000), cl::Hidden); 
+static cl::opt<unsigned> InputDbgValueLimit( 
+    "livedebugvalues-input-dbg-value-limit", 
+    cl::desc( 
+        "Maximum input DBG_VALUE insts supported by debug range extension"), 
+    cl::init(50000), cl::Hidden); 
+ 
+// If @MI is a DBG_VALUE with debug value described by a defined 
+// register, returns the number of this register. In the other case, returns 0. 
+static Register isDbgValueDescribedByReg(const MachineInstr &MI) { 
+  assert(MI.isDebugValue() && "expected a DBG_VALUE"); 
+  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); 
+  // If location of variable is described using a register (directly 
+  // or indirectly), this register is always a first operand. 
+  return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg() 
+                                       : Register(); 
+} 
+ 
+/// If \p Op is a stack or frame register return true, otherwise return false. 
+/// This is used to avoid basing the debug entry values on the registers, since 
+/// we do not support it at the moment. 
+static bool isRegOtherThanSPAndFP(const MachineOperand &Op, 
+                                  const MachineInstr &MI, 
+                                  const TargetRegisterInfo *TRI) { 
+  if (!Op.isReg()) 
+    return false; 
+ 
+  const MachineFunction *MF = MI.getParent()->getParent(); 
+  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); 
+  Register SP = TLI->getStackPointerRegisterToSaveRestore(); 
+  Register FP = TRI->getFrameRegister(*MF); 
+  Register Reg = Op.getReg(); 
+ 
+  return Reg && Reg != SP && Reg != FP; 
+} 
+ 
+namespace { 
+ 
+// Max out the number of statically allocated elements in DefinedRegsSet, as 
+// this prevents fallback to std::set::count() operations. 
+using DefinedRegsSet = SmallSet<Register, 32>; 
+ 
+using VarLocSet = CoalescingBitVector<uint64_t>; 
+ 
+/// A type-checked pair of {Register Location (or 0), Index}, used to index 
+/// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int 
+/// for insertion into a \ref VarLocSet, and efficiently converted back. The 
+/// type-checker helps ensure that the conversions aren't lossy. 
+/// 
+/// Why encode a location /into/ the VarLocMap index? This makes it possible 
+/// to find the open VarLocs killed by a register def very quickly. This is a 
+/// performance-critical operation for LiveDebugValues. 
+struct LocIndex { 
+  using u32_location_t = uint32_t; 
+  using u32_index_t = uint32_t; 
+ 
+  u32_location_t Location; // Physical registers live in the range [1;2^30) (see 
+                           // \ref MCRegister), so we have plenty of range left 
+                           // here to encode non-register locations. 
+  u32_index_t Index; 
+ 
+  /// The first location greater than 0 that is not reserved for VarLocs of 
+  /// kind RegisterKind. 
+  static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30; 
+ 
+  /// A special location reserved for VarLocs of kind SpillLocKind. 
+  static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation; 
+ 
+  /// A special location reserved for VarLocs of kind EntryValueBackupKind and 
+  /// EntryValueCopyBackupKind. 
+  static constexpr u32_location_t kEntryValueBackupLocation = 
+      kFirstInvalidRegLocation + 1; 
+ 
+  LocIndex(u32_location_t Location, u32_index_t Index) 
+      : Location(Location), Index(Index) {} 
+ 
+  uint64_t getAsRawInteger() const { 
+    return (static_cast<uint64_t>(Location) << 32) | Index; 
+  } 
+ 
+  template<typename IntT> static LocIndex fromRawInteger(IntT ID) { 
+    static_assert(std::is_unsigned<IntT>::value && 
+                      sizeof(ID) == sizeof(uint64_t), 
+                  "Cannot convert raw integer to LocIndex"); 
+    return {static_cast<u32_location_t>(ID >> 32), 
+            static_cast<u32_index_t>(ID)}; 
+  } 
+ 
+  /// Get the start of the interval reserved for VarLocs of kind RegisterKind 
+  /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1. 
+  static uint64_t rawIndexForReg(uint32_t Reg) { 
+    return LocIndex(Reg, 0).getAsRawInteger(); 
+  } 
+ 
+  /// Return a range covering all set indices in the interval reserved for 
+  /// \p Location in \p Set. 
+  static auto indexRangeForLocation(const VarLocSet &Set, 
+                                    u32_location_t Location) { 
+    uint64_t Start = LocIndex(Location, 0).getAsRawInteger(); 
+    uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger(); 
+    return Set.half_open_range(Start, End); 
+  } 
+}; 
+ 
+class VarLocBasedLDV : public LDVImpl { 
+private: 
+  const TargetRegisterInfo *TRI; 
+  const TargetInstrInfo *TII; 
+  const TargetFrameLowering *TFI; 
+  TargetPassConfig *TPC; 
+  BitVector CalleeSavedRegs; 
+  LexicalScopes LS; 
+  VarLocSet::Allocator Alloc; 
+ 
+  enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore }; 
+ 
+  using FragmentInfo = DIExpression::FragmentInfo; 
+  using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; 
+ 
+  /// A pair of debug variable and value location. 
+  struct VarLoc { 
+    // The location at which a spilled variable resides. It consists of a 
+    // register and an offset. 
+    struct SpillLoc { 
+      unsigned SpillBase; 
+      StackOffset SpillOffset; 
+      bool operator==(const SpillLoc &Other) const { 
+        return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset; 
+      } 
+      bool operator!=(const SpillLoc &Other) const { 
+        return !(*this == Other); 
+      } 
+    }; 
+ 
+    /// Identity of the variable at this location. 
+    const DebugVariable Var; 
+ 
+    /// The expression applied to this location. 
+    const DIExpression *Expr; 
+ 
+    /// DBG_VALUE to clone var/expr information from if this location 
+    /// is moved. 
+    const MachineInstr &MI; 
+ 
+    enum VarLocKind { 
+      InvalidKind = 0, 
+      RegisterKind, 
+      SpillLocKind, 
+      ImmediateKind, 
+      EntryValueKind, 
+      EntryValueBackupKind, 
+      EntryValueCopyBackupKind 
+    } Kind = InvalidKind; 
+ 
+    /// The value location. Stored separately to avoid repeatedly 
+    /// extracting it from MI. 
+    union LocUnion { 
+      uint64_t RegNo; 
+      SpillLoc SpillLocation; 
+      uint64_t Hash; 
+      int64_t Immediate; 
+      const ConstantFP *FPImm; 
+      const ConstantInt *CImm; 
+      LocUnion() : Hash(0) {} 
+    } Loc; 
+ 
+    VarLoc(const MachineInstr &MI, LexicalScopes &LS) 
+        : Var(MI.getDebugVariable(), MI.getDebugExpression(), 
+              MI.getDebugLoc()->getInlinedAt()), 
+          Expr(MI.getDebugExpression()), MI(MI) { 
+      assert(MI.isDebugValue() && "not a DBG_VALUE"); 
+      assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); 
+      if (int RegNo = isDbgValueDescribedByReg(MI)) { 
+        Kind = RegisterKind; 
+        Loc.RegNo = RegNo; 
+      } else if (MI.getDebugOperand(0).isImm()) { 
+        Kind = ImmediateKind; 
+        Loc.Immediate = MI.getDebugOperand(0).getImm(); 
+      } else if (MI.getDebugOperand(0).isFPImm()) { 
+        Kind = ImmediateKind; 
+        Loc.FPImm = MI.getDebugOperand(0).getFPImm(); 
+      } else if (MI.getDebugOperand(0).isCImm()) { 
+        Kind = ImmediateKind; 
+        Loc.CImm = MI.getDebugOperand(0).getCImm(); 
+      } 
+ 
+      // We create the debug entry values from the factory functions rather than 
+      // from this ctor. 
+      assert(Kind != EntryValueKind && !isEntryBackupLoc()); 
+    } 
+ 
+    /// Take the variable and machine-location in DBG_VALUE MI, and build an 
+    /// entry location using the given expression. 
+    static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS, 
+                                 const DIExpression *EntryExpr, Register Reg) { 
+      VarLoc VL(MI, LS); 
+      assert(VL.Kind == RegisterKind); 
+      VL.Kind = EntryValueKind; 
+      VL.Expr = EntryExpr; 
+      VL.Loc.RegNo = Reg; 
+      return VL; 
+    } 
+ 
+    /// Take the variable and machine-location from the DBG_VALUE (from the 
+    /// function entry), and build an entry value backup location. The backup 
+    /// location will turn into the normal location if the backup is valid at 
+    /// the time of the primary location clobbering. 
+    static VarLoc CreateEntryBackupLoc(const MachineInstr &MI, 
+                                       LexicalScopes &LS, 
+                                       const DIExpression *EntryExpr) { 
+      VarLoc VL(MI, LS); 
+      assert(VL.Kind == RegisterKind); 
+      VL.Kind = EntryValueBackupKind; 
+      VL.Expr = EntryExpr; 
+      return VL; 
+    } 
+ 
+    /// Take the variable and machine-location from the DBG_VALUE (from the 
+    /// function entry), and build a copy of an entry value backup location by 
+    /// setting the register location to NewReg. 
+    static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI, 
+                                           LexicalScopes &LS, 
+                                           const DIExpression *EntryExpr, 
+                                           Register NewReg) { 
+      VarLoc VL(MI, LS); 
+      assert(VL.Kind == RegisterKind); 
+      VL.Kind = EntryValueCopyBackupKind; 
+      VL.Expr = EntryExpr; 
+      VL.Loc.RegNo = NewReg; 
+      return VL; 
+    } 
+ 
+    /// Copy the register location in DBG_VALUE MI, updating the register to 
+    /// be NewReg. 
+    static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS, 
+                                Register NewReg) { 
+      VarLoc VL(MI, LS); 
+      assert(VL.Kind == RegisterKind); 
+      VL.Loc.RegNo = NewReg; 
+      return VL; 
+    } 
+ 
+    /// Take the variable described by DBG_VALUE MI, and create a VarLoc 
+    /// locating it in the specified spill location. 
+    static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase, 
+                                 StackOffset SpillOffset, LexicalScopes &LS) { 
+      VarLoc VL(MI, LS); 
+      assert(VL.Kind == RegisterKind); 
+      VL.Kind = SpillLocKind; 
+      VL.Loc.SpillLocation = {SpillBase, SpillOffset}; 
+      return VL; 
+    } 
+ 
+    /// Create a DBG_VALUE representing this VarLoc in the given function. 
+    /// Copies variable-specific information such as DILocalVariable and 
+    /// inlining information from the original DBG_VALUE instruction, which may 
+    /// have been several transfers ago. 
+    MachineInstr *BuildDbgValue(MachineFunction &MF) const { 
+      const DebugLoc &DbgLoc = MI.getDebugLoc(); 
+      bool Indirect = MI.isIndirectDebugValue(); 
+      const auto &IID = MI.getDesc(); 
+      const DILocalVariable *Var = MI.getDebugVariable(); 
+      const DIExpression *DIExpr = MI.getDebugExpression(); 
+      NumInserted++; 
+ 
+      switch (Kind) { 
+      case EntryValueKind: 
+        // An entry value is a register location -- but with an updated 
+        // expression. The register location of such DBG_VALUE is always the one 
+        // from the entry DBG_VALUE, it does not matter if the entry value was 
+        // copied in to another register due to some optimizations. 
+        return BuildMI(MF, DbgLoc, IID, Indirect, 
+                       MI.getDebugOperand(0).getReg(), Var, Expr); 
+      case RegisterKind: 
+        // Register locations are like the source DBG_VALUE, but with the 
+        // register number from this VarLoc. 
+        return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr); 
+      case SpillLocKind: { 
+        // Spills are indirect DBG_VALUEs, with a base register and offset. 
+        // Use the original DBG_VALUEs expression to build the spilt location 
+        // on top of. FIXME: spill locations created before this pass runs 
+        // are not recognized, and not handled here. 
+        auto *TRI = MF.getSubtarget().getRegisterInfo(); 
+        auto *SpillExpr = TRI->prependOffsetExpression( 
+            DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset); 
+        unsigned Base = Loc.SpillLocation.SpillBase; 
+        return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr); 
+      } 
+      case ImmediateKind: { 
+        MachineOperand MO = MI.getDebugOperand(0); 
+        return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr); 
+      } 
+      case EntryValueBackupKind: 
+      case EntryValueCopyBackupKind: 
+      case InvalidKind: 
+        llvm_unreachable( 
+            "Tried to produce DBG_VALUE for invalid or backup VarLoc"); 
+      } 
+      llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum"); 
+    } 
+ 
+    /// Is the Loc field a constant or constant object? 
+    bool isConstant() const { return Kind == ImmediateKind; } 
+ 
+    /// Check if the Loc field is an entry backup location. 
+    bool isEntryBackupLoc() const { 
+      return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind; 
+    } 
+ 
+    /// If this variable is described by a register holding the entry value, 
+    /// return it, otherwise return 0. 
+    unsigned getEntryValueBackupReg() const { 
+      if (Kind == EntryValueBackupKind) 
+        return Loc.RegNo; 
+      return 0; 
+    } 
+ 
+    /// If this variable is described by a register holding the copy of the 
+    /// entry value, return it, otherwise return 0. 
+    unsigned getEntryValueCopyBackupReg() const { 
+      if (Kind == EntryValueCopyBackupKind) 
+        return Loc.RegNo; 
+      return 0; 
+    } 
+ 
+    /// If this variable is described by a register, return it, 
+    /// otherwise return 0. 
+    unsigned isDescribedByReg() const { 
+      if (Kind == RegisterKind) 
+        return Loc.RegNo; 
+      return 0; 
+    } 
+ 
+    /// Determine whether the lexical scope of this value's debug location 
+    /// dominates MBB. 
+    bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const { 
+      return LS.dominates(MI.getDebugLoc().get(), &MBB); 
+    } 
+ 
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 
+    // TRI can be null. 
+    void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const { 
+      Out << "VarLoc("; 
+      switch (Kind) { 
+      case RegisterKind: 
+      case EntryValueKind: 
+      case EntryValueBackupKind: 
+      case EntryValueCopyBackupKind: 
+        Out << printReg(Loc.RegNo, TRI); 
+        break; 
+      case SpillLocKind: 
+        Out << printReg(Loc.SpillLocation.SpillBase, TRI); 
+        Out << "[" << Loc.SpillLocation.SpillOffset.getFixed() << " + " 
+            << Loc.SpillLocation.SpillOffset.getScalable() << "x vscale" 
+            << "]"; 
+        break; 
+      case ImmediateKind: 
+        Out << Loc.Immediate; 
+        break; 
+      case InvalidKind: 
+        llvm_unreachable("Invalid VarLoc in dump method"); 
+      } 
+ 
+      Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", "; 
+      if (Var.getInlinedAt()) 
+        Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n"; 
+      else 
+        Out << "(null))"; 
+ 
+      if (isEntryBackupLoc()) 
+        Out << " (backup loc)\n"; 
+      else 
+        Out << "\n"; 
+    } 
+#endif 
+ 
+    bool operator==(const VarLoc &Other) const { 
+      if (Kind != Other.Kind || !(Var == Other.Var) || Expr != Other.Expr) 
+        return false; 
+ 
+      switch (Kind) { 
+      case SpillLocKind: 
+        return Loc.SpillLocation == Other.Loc.SpillLocation; 
+      case RegisterKind: 
+      case ImmediateKind: 
+      case EntryValueKind: 
+      case EntryValueBackupKind: 
+      case EntryValueCopyBackupKind: 
+        return Loc.Hash == Other.Loc.Hash; 
+      default: 
+        llvm_unreachable("Invalid kind"); 
+      } 
+    } 
+ 
+    /// This operator guarantees that VarLocs are sorted by Variable first. 
+    bool operator<(const VarLoc &Other) const { 
+      switch (Kind) { 
+      case SpillLocKind: 
+        return std::make_tuple(Var, Kind, Loc.SpillLocation.SpillBase, 
+                               Loc.SpillLocation.SpillOffset.getFixed(), 
+                               Loc.SpillLocation.SpillOffset.getScalable(), 
+                               Expr) < 
+               std::make_tuple( 
+                   Other.Var, Other.Kind, Other.Loc.SpillLocation.SpillBase, 
+                   Other.Loc.SpillLocation.SpillOffset.getFixed(), 
+                   Other.Loc.SpillLocation.SpillOffset.getScalable(), 
+                   Other.Expr); 
+      case RegisterKind: 
+      case ImmediateKind: 
+      case EntryValueKind: 
+      case EntryValueBackupKind: 
+      case EntryValueCopyBackupKind: 
+        return std::tie(Var, Kind, Loc.Hash, Expr) < 
+               std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr); 
+      default: 
+        llvm_unreachable("Invalid kind"); 
+      } 
+    } 
+  }; 
+ 
+  /// VarLocMap is used for two things: 
+  /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to 
+  ///    virtually insert a VarLoc into a VarLocSet. 
+  /// 2) Given a LocIndex, look up the unique associated VarLoc. 
+  class VarLocMap { 
+    /// Map a VarLoc to an index within the vector reserved for its location 
+    /// within Loc2Vars. 
+    std::map<VarLoc, LocIndex::u32_index_t> Var2Index; 
+ 
+    /// Map a location to a vector which holds VarLocs which live in that 
+    /// location. 
+    SmallDenseMap<LocIndex::u32_location_t, std::vector<VarLoc>> Loc2Vars; 
+ 
+    /// Determine the 32-bit location reserved for \p VL, based on its kind. 
+    static LocIndex::u32_location_t getLocationForVar(const VarLoc &VL) { 
+      switch (VL.Kind) { 
+      case VarLoc::RegisterKind: 
+        assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) && 
+               "Physreg out of range?"); 
+        return VL.Loc.RegNo; 
+      case VarLoc::SpillLocKind: 
+        return LocIndex::kSpillLocation; 
+      case VarLoc::EntryValueBackupKind: 
+      case VarLoc::EntryValueCopyBackupKind: 
+        return LocIndex::kEntryValueBackupLocation; 
+      default: 
+        return 0; 
+      } 
+    } 
+ 
+  public: 
+    /// Retrieve a unique LocIndex for \p VL. 
+    LocIndex insert(const VarLoc &VL) { 
+      LocIndex::u32_location_t Location = getLocationForVar(VL); 
+      LocIndex::u32_index_t &Index = Var2Index[VL]; 
+      if (!Index) { 
+        auto &Vars = Loc2Vars[Location]; 
+        Vars.push_back(VL); 
+        Index = Vars.size(); 
+      } 
+      return {Location, Index - 1}; 
+    } 
+ 
+    /// Retrieve the unique VarLoc associated with \p ID. 
+    const VarLoc &operator[](LocIndex ID) const { 
+      auto LocIt = Loc2Vars.find(ID.Location); 
+      assert(LocIt != Loc2Vars.end() && "Location not tracked"); 
+      return LocIt->second[ID.Index]; 
+    } 
+  }; 
+ 
+  using VarLocInMBB = 
+      SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>; 
+  struct TransferDebugPair { 
+    MachineInstr *TransferInst; ///< Instruction where this transfer occurs. 
+    LocIndex LocationID;        ///< Location number for the transfer dest. 
+  }; 
+  using TransferMap = SmallVector<TransferDebugPair, 4>; 
+ 
+  // Types for recording sets of variable fragments that overlap. For a given 
+  // local variable, we record all other fragments of that variable that could 
+  // overlap it, to reduce search time. 
+  using FragmentOfVar = 
+      std::pair<const DILocalVariable *, DIExpression::FragmentInfo>; 
+  using OverlapMap = 
+      DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>; 
+ 
+  // Helper while building OverlapMap, a map of all fragments seen for a given 
+  // DILocalVariable. 
+  using VarToFragments = 
+      DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; 
+ 
+  /// This holds the working set of currently open ranges. For fast 
+  /// access, this is done both as a set of VarLocIDs, and a map of 
+  /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all 
+  /// previous open ranges for the same variable. In addition, we keep 
+  /// two different maps (Vars/EntryValuesBackupVars), so erase/insert 
+  /// methods act differently depending on whether a VarLoc is primary 
+  /// location or backup one. In the case the VarLoc is backup location 
+  /// we will erase/insert from the EntryValuesBackupVars map, otherwise 
+  /// we perform the operation on the Vars. 
+  class OpenRangesSet { 
+    VarLocSet VarLocs; 
+    // Map the DebugVariable to recent primary location ID. 
+    SmallDenseMap<DebugVariable, LocIndex, 8> Vars; 
+    // Map the DebugVariable to recent backup location ID. 
+    SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars; 
+    OverlapMap &OverlappingFragments; 
+ 
+  public: 
+    OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap) 
+        : VarLocs(Alloc), OverlappingFragments(_OLapMap) {} 
+ 
+    const VarLocSet &getVarLocs() const { return VarLocs; } 
+ 
+    /// Terminate all open ranges for VL.Var by removing it from the set. 
+    void erase(const VarLoc &VL); 
+ 
+    /// Terminate all open ranges listed in \c KillSet by removing 
+    /// them from the set. 
+    void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs); 
+ 
+    /// Insert a new range into the set. 
+    void insert(LocIndex VarLocID, const VarLoc &VL); 
+ 
+    /// Insert a set of ranges. 
+    void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) { 
+      for (uint64_t ID : ToLoad) { 
+        LocIndex Idx = LocIndex::fromRawInteger(ID); 
+        const VarLoc &VarL = Map[Idx]; 
+        insert(Idx, VarL); 
+      } 
+    } 
+ 
+    llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var); 
+ 
+    /// Empty the set. 
+    void clear() { 
+      VarLocs.clear(); 
+      Vars.clear(); 
+      EntryValuesBackupVars.clear(); 
+    } 
+ 
+    /// Return whether the set is empty or not. 
+    bool empty() const { 
+      assert(Vars.empty() == EntryValuesBackupVars.empty() && 
+             Vars.empty() == VarLocs.empty() && 
+             "open ranges are inconsistent"); 
+      return VarLocs.empty(); 
+    } 
+ 
+    /// Get an empty range of VarLoc IDs. 
+    auto getEmptyVarLocRange() const { 
+      return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(), 
+                                                       getVarLocs().end()); 
+    } 
+ 
+    /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg. 
+    auto getRegisterVarLocs(Register Reg) const { 
+      return LocIndex::indexRangeForLocation(getVarLocs(), Reg); 
+    } 
+ 
+    /// Get all set IDs for VarLocs of kind SpillLocKind. 
+    auto getSpillVarLocs() const { 
+      return LocIndex::indexRangeForLocation(getVarLocs(), 
+                                             LocIndex::kSpillLocation); 
+    } 
+ 
+    /// Get all set IDs for VarLocs of kind EntryValueBackupKind or 
+    /// EntryValueCopyBackupKind. 
+    auto getEntryValueBackupVarLocs() const { 
+      return LocIndex::indexRangeForLocation( 
+          getVarLocs(), LocIndex::kEntryValueBackupLocation); 
+    } 
+  }; 
+ 
+  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind 
+  /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs 
+  /// into \p Collected. 
+  void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs, 
+                         const VarLocSet &CollectFrom) const; 
+ 
+  /// Get the registers which are used by VarLocs of kind RegisterKind tracked 
+  /// by \p CollectFrom. 
+  void getUsedRegs(const VarLocSet &CollectFrom, 
+                   SmallVectorImpl<uint32_t> &UsedRegs) const; 
+ 
+  VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) { 
+    std::unique_ptr<VarLocSet> &VLS = Locs[MBB]; 
+    if (!VLS) 
+      VLS = std::make_unique<VarLocSet>(Alloc); 
+    return *VLS.get(); 
+  } 
+ 
+  const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, 
+                                   const VarLocInMBB &Locs) const { 
+    auto It = Locs.find(MBB); 
+    assert(It != Locs.end() && "MBB not in map"); 
+    return *It->second.get(); 
+  } 
+ 
+  /// Tests whether this instruction is a spill to a stack location. 
+  bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); 
+ 
+  /// Decide if @MI is a spill instruction and return true if it is. We use 2 
+  /// criteria to make this decision: 
+  /// - Is this instruction a store to a spill slot? 
+  /// - Is there a register operand that is both used and killed? 
+  /// TODO: Store optimization can fold spills into other stores (including 
+  /// other spills). We do not handle this yet (more than one memory operand). 
+  bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, 
+                       Register &Reg); 
+ 
+  /// Returns true if the given machine instruction is a debug value which we 
+  /// can emit entry values for. 
+  /// 
+  /// Currently, we generate debug entry values only for parameters that are 
+  /// unmodified throughout the function and located in a register. 
+  bool isEntryValueCandidate(const MachineInstr &MI, 
+                             const DefinedRegsSet &Regs) const; 
+ 
+  /// If a given instruction is identified as a spill, return the spill location 
+  /// and set \p Reg to the spilled register. 
+  Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI, 
+                                                  MachineFunction *MF, 
+                                                  Register &Reg); 
+  /// Given a spill instruction, extract the register and offset used to 
+  /// address the spill location in a target independent way. 
+  VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); 
+  void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                               TransferMap &Transfers, VarLocMap &VarLocIDs, 
+                               LocIndex OldVarID, TransferKind Kind, 
+                               Register NewReg = Register()); 
+ 
+  void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                          VarLocMap &VarLocIDs); 
+  void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                                  VarLocMap &VarLocIDs, TransferMap &Transfers); 
+  bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                        VarLocMap &VarLocIDs, const VarLoc &EntryVL); 
+  void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                       VarLocMap &VarLocIDs, TransferMap &Transfers, 
+                       VarLocSet &KillSet); 
+  void recordEntryValue(const MachineInstr &MI, 
+                        const DefinedRegsSet &DefinedRegs, 
+                        OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs); 
+  void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                            VarLocMap &VarLocIDs, TransferMap &Transfers); 
+  void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                           VarLocMap &VarLocIDs, TransferMap &Transfers); 
+  bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges, 
+                          VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); 
+ 
+  void process(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+               VarLocMap &VarLocIDs, TransferMap &Transfers); 
+ 
+  void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, 
+                             OverlapMap &OLapMap); 
+ 
+  bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, 
+            const VarLocMap &VarLocIDs, 
+            SmallPtrSet<const MachineBasicBlock *, 16> &Visited, 
+            SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks); 
+ 
+  /// Create DBG_VALUE insts for inlocs that have been propagated but 
+  /// had their instruction creation deferred. 
+  void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs); 
+ 
+  bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override; 
+ 
+public: 
+  /// Default construct and initialize the pass. 
+  VarLocBasedLDV(); 
+ 
+  ~VarLocBasedLDV(); 
+ 
+  /// Print to ostream with a message. 
+  void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V, 
+                        const VarLocMap &VarLocIDs, const char *msg, 
+                        raw_ostream &Out) const; 
+}; 
+ 
+} // end anonymous namespace 
+ 
+//===----------------------------------------------------------------------===// 
+//            Implementation 
+//===----------------------------------------------------------------------===// 
+ 
+VarLocBasedLDV::VarLocBasedLDV() { } 
+ 
+VarLocBasedLDV::~VarLocBasedLDV() { } 
+ 
+/// Erase a variable from the set of open ranges, and additionally erase any 
+/// fragments that may overlap it. If the VarLoc is a backup location, erase 
+/// the variable from the EntryValuesBackupVars set, indicating we should stop 
+/// tracking its backup entry location. Otherwise, if the VarLoc is primary 
+/// location, erase the variable from the Vars set. 
+void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) { 
+  // Erasure helper. 
+  auto DoErase = [VL, this](DebugVariable VarToErase) { 
+    auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; 
+    auto It = EraseFrom->find(VarToErase); 
+    if (It != EraseFrom->end()) { 
+      LocIndex ID = It->second; 
+      VarLocs.reset(ID.getAsRawInteger()); 
+      EraseFrom->erase(It); 
+    } 
+  }; 
+ 
+  DebugVariable Var = VL.Var; 
+ 
+  // Erase the variable/fragment that ends here. 
+  DoErase(Var); 
+ 
+  // Extract the fragment. Interpret an empty fragment as one that covers all 
+  // possible bits. 
+  FragmentInfo ThisFragment = Var.getFragmentOrDefault(); 
+ 
+  // There may be fragments that overlap the designated fragment. Look them up 
+  // in the pre-computed overlap map, and erase them too. 
+  auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment}); 
+  if (MapIt != OverlappingFragments.end()) { 
+    for (auto Fragment : MapIt->second) { 
+      VarLocBasedLDV::OptFragmentInfo FragmentHolder; 
+      if (!DebugVariable::isDefaultFragment(Fragment)) 
+        FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment); 
+      DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()}); 
+    } 
+  } 
+} 
+ 
+void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet, 
+                                           const VarLocMap &VarLocIDs) { 
+  VarLocs.intersectWithComplement(KillSet); 
+  for (uint64_t ID : KillSet) { 
+    const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)]; 
+    auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; 
+    EraseFrom->erase(VL->Var); 
+  } 
+} 
+ 
+void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID, 
+                                            const VarLoc &VL) { 
+  auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; 
+  VarLocs.set(VarLocID.getAsRawInteger()); 
+  InsertInto->insert({VL.Var, VarLocID}); 
+} 
+ 
+/// Return the Loc ID of an entry value backup location, if it exists for the 
+/// variable. 
+llvm::Optional<LocIndex> 
+VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { 
+  auto It = EntryValuesBackupVars.find(Var); 
+  if (It != EntryValuesBackupVars.end()) 
+    return It->second; 
+ 
+  return llvm::None; 
+} 
+ 
+void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected, 
+                                        const DefinedRegsSet &Regs, 
+                                        const VarLocSet &CollectFrom) const { 
+  assert(!Regs.empty() && "Nothing to collect"); 
+  SmallVector<uint32_t, 32> SortedRegs; 
+  for (Register Reg : Regs) 
+    SortedRegs.push_back(Reg); 
+  array_pod_sort(SortedRegs.begin(), SortedRegs.end()); 
+  auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front())); 
+  auto End = CollectFrom.end(); 
+  for (uint32_t Reg : SortedRegs) { 
+    // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all 
+    // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg. 
+    uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg); 
+    uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1); 
+    It.advanceToLowerBound(FirstIndexForReg); 
+ 
+    // Iterate through that half-open interval and collect all the set IDs. 
+    for (; It != End && *It < FirstInvalidIndex; ++It) 
+      Collected.set(*It); 
+ 
+    if (It == End) 
+      return; 
+  } 
+} 
+ 
+void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom, 
+                                  SmallVectorImpl<uint32_t> &UsedRegs) const { 
+  // All register-based VarLocs are assigned indices greater than or equal to 
+  // FirstRegIndex. 
+  uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1); 
+  uint64_t FirstInvalidIndex = 
+      LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation); 
+  for (auto It = CollectFrom.find(FirstRegIndex), 
+            End = CollectFrom.find(FirstInvalidIndex); 
+       It != End;) { 
+    // We found a VarLoc ID for a VarLoc that lives in a register. Figure out 
+    // which register and add it to UsedRegs. 
+    uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location; 
+    assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) && 
+           "Duplicate used reg"); 
+    UsedRegs.push_back(FoundReg); 
+ 
+    // Skip to the next /set/ register. Note that this finds a lower bound, so 
+    // even if there aren't any VarLocs living in `FoundReg+1`, we're still 
+    // guaranteed to move on to the next register (or to end()). 
+    uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1); 
+    It.advanceToLowerBound(NextRegIndex); 
+  } 
+} 
+ 
+//===----------------------------------------------------------------------===// 
+//            Debug Range Extension Implementation 
+//===----------------------------------------------------------------------===// 
+ 
+#ifndef NDEBUG 
+void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF, 
+                                       const VarLocInMBB &V, 
+                                       const VarLocMap &VarLocIDs, 
+                                       const char *msg, 
+                                       raw_ostream &Out) const { 
+  Out << '\n' << msg << '\n'; 
+  for (const MachineBasicBlock &BB : MF) { 
+    if (!V.count(&BB)) 
+      continue; 
+    const VarLocSet &L = getVarLocsInMBB(&BB, V); 
+    if (L.empty()) 
+      continue; 
+    Out << "MBB: " << BB.getNumber() << ":\n"; 
+    for (uint64_t VLL : L) { 
+      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)]; 
+      Out << " Var: " << VL.Var.getVariable()->getName(); 
+      Out << " MI: "; 
+      VL.dump(TRI, Out); 
+    } 
+  } 
+  Out << "\n"; 
+} 
+#endif 
+ 
+VarLocBasedLDV::VarLoc::SpillLoc 
+VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { 
+  assert(MI.hasOneMemOperand() && 
+         "Spill instruction does not have exactly one memory operand?"); 
+  auto MMOI = MI.memoperands_begin(); 
+  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); 
+  assert(PVal->kind() == PseudoSourceValue::FixedStack && 
+         "Inconsistent memory operand in spill instruction"); 
+  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); 
+  const MachineBasicBlock *MBB = MI.getParent(); 
+  Register Reg; 
+  StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); 
+  return {Reg, Offset}; 
+} 
+ 
+/// Try to salvage the debug entry value if we encounter a new debug value 
+/// describing the same parameter, otherwise stop tracking the value. Return 
+/// true if we should stop tracking the entry value, otherwise return false. 
+bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI, 
+                                       OpenRangesSet &OpenRanges, 
+                                       VarLocMap &VarLocIDs, 
+                                       const VarLoc &EntryVL) { 
+  // Skip the DBG_VALUE which is the debug entry value itself. 
+  if (MI.isIdenticalTo(EntryVL.MI)) 
+    return false; 
+ 
+  // If the parameter's location is not register location, we can not track 
+  // the entry value any more. In addition, if the debug expression from the 
+  // DBG_VALUE is not empty, we can assume the parameter's value has changed 
+  // indicating that we should stop tracking its entry value as well. 
+  if (!MI.getDebugOperand(0).isReg() || 
+      MI.getDebugExpression()->getNumElements() != 0) 
+    return true; 
+ 
+  // If the DBG_VALUE comes from a copy instruction that copies the entry value, 
+  // it means the parameter's value has not changed and we should be able to use 
+  // its entry value. 
+  bool TrySalvageEntryValue = false; 
+  Register Reg = MI.getDebugOperand(0).getReg(); 
+  auto I = std::next(MI.getReverseIterator()); 
+  const MachineOperand *SrcRegOp, *DestRegOp; 
+  if (I != MI.getParent()->rend()) { 
+    // TODO: Try to keep tracking of an entry value if we encounter a propagated 
+    // DBG_VALUE describing the copy of the entry value. (Propagated entry value 
+    // does not indicate the parameter modification.) 
+    auto DestSrc = TII->isCopyInstr(*I); 
+    if (!DestSrc) 
+      return true; 
+ 
+    SrcRegOp = DestSrc->Source; 
+    DestRegOp = DestSrc->Destination; 
+    if (Reg != DestRegOp->getReg()) 
+      return true; 
+    TrySalvageEntryValue = true; 
+  } 
+ 
+  if (TrySalvageEntryValue) { 
+    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { 
+      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)]; 
+      if (VL.getEntryValueCopyBackupReg() == Reg && 
+          VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg()) 
+        return false; 
+    } 
+  } 
+ 
+  return true; 
+} 
+ 
+/// End all previous ranges related to @MI and start a new range from @MI 
+/// if it is a DBG_VALUE instr. 
+void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI, 
+                                         OpenRangesSet &OpenRanges, 
+                                         VarLocMap &VarLocIDs) { 
+  if (!MI.isDebugValue()) 
+    return; 
+  const DILocalVariable *Var = MI.getDebugVariable(); 
+  const DIExpression *Expr = MI.getDebugExpression(); 
+  const DILocation *DebugLoc = MI.getDebugLoc(); 
+  const DILocation *InlinedAt = DebugLoc->getInlinedAt(); 
+  assert(Var->isValidLocationForIntrinsic(DebugLoc) && 
+         "Expected inlined-at fields to agree"); 
+ 
+  DebugVariable V(Var, Expr, InlinedAt); 
+ 
+  // Check if this DBG_VALUE indicates a parameter's value changing. 
+  // If that is the case, we should stop tracking its entry value. 
+  auto EntryValBackupID = OpenRanges.getEntryValueBackup(V); 
+  if (Var->isParameter() && EntryValBackupID) { 
+    const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; 
+    if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) { 
+      LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: "; 
+                 MI.print(dbgs(), /*IsStandalone*/ false, 
+                          /*SkipOpers*/ false, /*SkipDebugLoc*/ false, 
+                          /*AddNewLine*/ true, TII)); 
+      OpenRanges.erase(EntryVL); 
+    } 
+  } 
+ 
+  if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() || 
+      MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) { 
+    // Use normal VarLoc constructor for registers and immediates. 
+    VarLoc VL(MI, LS); 
+    // End all previous ranges of VL.Var. 
+    OpenRanges.erase(VL); 
+ 
+    LocIndex ID = VarLocIDs.insert(VL); 
+    // Add the VarLoc to OpenRanges from this DBG_VALUE. 
+    OpenRanges.insert(ID, VL); 
+  } else if (MI.hasOneMemOperand()) { 
+    llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?"); 
+  } else { 
+    // This must be an undefined location. If it has an open range, erase it. 
+    assert(MI.getDebugOperand(0).isReg() && 
+           MI.getDebugOperand(0).getReg() == 0 && 
+           "Unexpected non-undef DBG_VALUE encountered"); 
+    VarLoc VL(MI, LS); 
+    OpenRanges.erase(VL); 
+  } 
+} 
+ 
+/// Turn the entry value backup locations into primary locations. 
+void VarLocBasedLDV::emitEntryValues(MachineInstr &MI, 
+                                      OpenRangesSet &OpenRanges, 
+                                      VarLocMap &VarLocIDs, 
+                                      TransferMap &Transfers, 
+                                      VarLocSet &KillSet) { 
+  // Do not insert entry value locations after a terminator. 
+  if (MI.isTerminator()) 
+    return; 
+ 
+  for (uint64_t ID : KillSet) { 
+    LocIndex Idx = LocIndex::fromRawInteger(ID); 
+    const VarLoc &VL = VarLocIDs[Idx]; 
+    if (!VL.Var.getVariable()->isParameter()) 
+      continue; 
+ 
+    auto DebugVar = VL.Var; 
+    Optional<LocIndex> EntryValBackupID = 
+        OpenRanges.getEntryValueBackup(DebugVar); 
+ 
+    // If the parameter has the entry value backup, it means we should 
+    // be able to use its entry value. 
+    if (!EntryValBackupID) 
+      continue; 
+ 
+    const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; 
+    VarLoc EntryLoc = 
+        VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo); 
+    LocIndex EntryValueID = VarLocIDs.insert(EntryLoc); 
+    Transfers.push_back({&MI, EntryValueID}); 
+    OpenRanges.insert(EntryValueID, EntryLoc); 
+  } 
+} 
+ 
+/// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc 
+/// with \p OldVarID should be deleted form \p OpenRanges and replaced with 
+/// new VarLoc. If \p NewReg is different than default zero value then the 
+/// new location will be register location created by the copy like instruction, 
+/// otherwise it is variable's location on the stack. 
+void VarLocBasedLDV::insertTransferDebugPair( 
+    MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers, 
+    VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind, 
+    Register NewReg) { 
+  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI; 
+ 
+  auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) { 
+    LocIndex LocId = VarLocIDs.insert(VL); 
+ 
+    // Close this variable's previous location range. 
+    OpenRanges.erase(VL); 
+ 
+    // Record the new location as an open range, and a postponed transfer 
+    // inserting a DBG_VALUE for this location. 
+    OpenRanges.insert(LocId, VL); 
+    assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator"); 
+    TransferDebugPair MIP = {&MI, LocId}; 
+    Transfers.push_back(MIP); 
+  }; 
+ 
+  // End all previous ranges of VL.Var. 
+  OpenRanges.erase(VarLocIDs[OldVarID]); 
+  switch (Kind) { 
+  case TransferKind::TransferCopy: { 
+    assert(NewReg && 
+           "No register supplied when handling a copy of a debug value"); 
+    // Create a DBG_VALUE instruction to describe the Var in its new 
+    // register location. 
+    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); 
+    ProcessVarLoc(VL); 
+    LLVM_DEBUG({ 
+      dbgs() << "Creating VarLoc for register copy:"; 
+      VL.dump(TRI); 
+    }); 
+    return; 
+  } 
+  case TransferKind::TransferSpill: { 
+    // Create a DBG_VALUE instruction to describe the Var in its spilled 
+    // location. 
+    VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI); 
+    VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase, 
+                                       SpillLocation.SpillOffset, LS); 
+    ProcessVarLoc(VL); 
+    LLVM_DEBUG({ 
+      dbgs() << "Creating VarLoc for spill:"; 
+      VL.dump(TRI); 
+    }); 
+    return; 
+  } 
+  case TransferKind::TransferRestore: { 
+    assert(NewReg && 
+           "No register supplied when handling a restore of a debug value"); 
+    // DebugInstr refers to the pre-spill location, therefore we can reuse 
+    // its expression. 
+    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); 
+    ProcessVarLoc(VL); 
+    LLVM_DEBUG({ 
+      dbgs() << "Creating VarLoc for restore:"; 
+      VL.dump(TRI); 
+    }); 
+    return; 
+  } 
+  } 
+  llvm_unreachable("Invalid transfer kind"); 
+} 
+ 
+/// A definition of a register may mark the end of a range. 
+void VarLocBasedLDV::transferRegisterDef( 
+    MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, 
+    TransferMap &Transfers) { 
+ 
+  // Meta Instructions do not affect the debug liveness of any register they 
+  // define. 
+  if (MI.isMetaInstruction()) 
+    return; 
+ 
+  MachineFunction *MF = MI.getMF(); 
+  const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); 
+  Register SP = TLI->getStackPointerRegisterToSaveRestore(); 
+ 
+  // Find the regs killed by MI, and find regmasks of preserved regs. 
+  DefinedRegsSet DeadRegs; 
+  SmallVector<const uint32_t *, 4> RegMasks; 
+  for (const MachineOperand &MO : MI.operands()) { 
+    // Determine whether the operand is a register def. 
+    if (MO.isReg() && MO.isDef() && MO.getReg() && 
+        Register::isPhysicalRegister(MO.getReg()) && 
+        !(MI.isCall() && MO.getReg() == SP)) { 
+      // Remove ranges of all aliased registers. 
+      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) 
+        // FIXME: Can we break out of this loop early if no insertion occurs? 
+        DeadRegs.insert(*RAI); 
+    } else if (MO.isRegMask()) { 
+      RegMasks.push_back(MO.getRegMask()); 
+    } 
+  } 
+ 
+  // Erase VarLocs which reside in one of the dead registers. For performance 
+  // reasons, it's critical to not iterate over the full set of open VarLocs. 
+  // Iterate over the set of dying/used regs instead. 
+  if (!RegMasks.empty()) { 
+    SmallVector<uint32_t, 32> UsedRegs; 
+    getUsedRegs(OpenRanges.getVarLocs(), UsedRegs); 
+    for (uint32_t Reg : UsedRegs) { 
+      // Remove ranges of all clobbered registers. Register masks don't usually 
+      // list SP as preserved. Assume that call instructions never clobber SP, 
+      // because some backends (e.g., AArch64) never list SP in the regmask. 
+      // While the debug info may be off for an instruction or two around 
+      // callee-cleanup calls, transferring the DEBUG_VALUE across the call is 
+      // still a better user experience. 
+      if (Reg == SP) 
+        continue; 
+      bool AnyRegMaskKillsReg = 
+          any_of(RegMasks, [Reg](const uint32_t *RegMask) { 
+            return MachineOperand::clobbersPhysReg(RegMask, Reg); 
+          }); 
+      if (AnyRegMaskKillsReg) 
+        DeadRegs.insert(Reg); 
+    } 
+  } 
+ 
+  if (DeadRegs.empty()) 
+    return; 
+ 
+  VarLocSet KillSet(Alloc); 
+  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs()); 
+  OpenRanges.erase(KillSet, VarLocIDs); 
+ 
+  if (TPC) { 
+    auto &TM = TPC->getTM<TargetMachine>(); 
+    if (TM.Options.ShouldEmitDebugEntryValues()) 
+      emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet); 
+  } 
+} 
+ 
+bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI, 
+                                         MachineFunction *MF) { 
+  // TODO: Handle multiple stores folded into one. 
+  if (!MI.hasOneMemOperand()) 
+    return false; 
+ 
+  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) 
+    return false; // This is not a spill instruction, since no valid size was 
+                  // returned from either function. 
+ 
+  return true; 
+} 
+ 
+bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI, 
+                                      MachineFunction *MF, Register &Reg) { 
+  if (!isSpillInstruction(MI, MF)) 
+    return false; 
+ 
+  auto isKilledReg = [&](const MachineOperand MO, Register &Reg) { 
+    if (!MO.isReg() || !MO.isUse()) { 
+      Reg = 0; 
+      return false; 
+    } 
+    Reg = MO.getReg(); 
+    return MO.isKill(); 
+  }; 
+ 
+  for (const MachineOperand &MO : MI.operands()) { 
+    // In a spill instruction generated by the InlineSpiller the spilled 
+    // register has its kill flag set. 
+    if (isKilledReg(MO, Reg)) 
+      return true; 
+    if (Reg != 0) { 
+      // Check whether next instruction kills the spilled register. 
+      // FIXME: Current solution does not cover search for killed register in 
+      // bundles and instructions further down the chain. 
+      auto NextI = std::next(MI.getIterator()); 
+      // Skip next instruction that points to basic block end iterator. 
+      if (MI.getParent()->end() == NextI) 
+        continue; 
+      Register RegNext; 
+      for (const MachineOperand &MONext : NextI->operands()) { 
+        // Return true if we came across the register from the 
+        // previous spill instruction that is killed in NextI. 
+        if (isKilledReg(MONext, RegNext) && RegNext == Reg) 
+          return true; 
+      } 
+    } 
+  } 
+  // Return false if we didn't find spilled register. 
+  return false; 
+} 
+ 
+Optional<VarLocBasedLDV::VarLoc::SpillLoc> 
+VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI, 
+                                      MachineFunction *MF, Register &Reg) { 
+  if (!MI.hasOneMemOperand()) 
+    return None; 
+ 
+  // FIXME: Handle folded restore instructions with more than one memory 
+  // operand. 
+  if (MI.getRestoreSize(TII)) { 
+    Reg = MI.getOperand(0).getReg(); 
+    return extractSpillBaseRegAndOffset(MI); 
+  } 
+  return None; 
+} 
+ 
+/// A spilled register may indicate that we have to end the current range of 
+/// a variable and create a new one for the spill location. 
+/// A restored register may indicate the reverse situation. 
+/// We don't want to insert any instructions in process(), so we just create 
+/// the DBG_VALUE without inserting it and keep track of it in \p Transfers. 
+/// It will be inserted into the BB when we're done iterating over the 
+/// instructions. 
+void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI, 
+                                                 OpenRangesSet &OpenRanges, 
+                                                 VarLocMap &VarLocIDs, 
+                                                 TransferMap &Transfers) { 
+  MachineFunction *MF = MI.getMF(); 
+  TransferKind TKind; 
+  Register Reg; 
+  Optional<VarLoc::SpillLoc> Loc; 
+ 
+  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); 
+ 
+  // First, if there are any DBG_VALUEs pointing at a spill slot that is 
+  // written to, then close the variable location. The value in memory 
+  // will have changed. 
+  VarLocSet KillSet(Alloc); 
+  if (isSpillInstruction(MI, MF)) { 
+    Loc = extractSpillBaseRegAndOffset(MI); 
+    for (uint64_t ID : OpenRanges.getSpillVarLocs()) { 
+      LocIndex Idx = LocIndex::fromRawInteger(ID); 
+      const VarLoc &VL = VarLocIDs[Idx]; 
+      assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); 
+      if (VL.Loc.SpillLocation == *Loc) { 
+        // This location is overwritten by the current instruction -- terminate 
+        // the open range, and insert an explicit DBG_VALUE $noreg. 
+        // 
+        // Doing this at a later stage would require re-interpreting all 
+        // DBG_VALUes and DIExpressions to identify whether they point at 
+        // memory, and then analysing all memory writes to see if they 
+        // overwrite that memory, which is expensive. 
+        // 
+        // At this stage, we already know which DBG_VALUEs are for spills and 
+        // where they are located; it's best to fix handle overwrites now. 
+        KillSet.set(ID); 
+        VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0); 
+        LocIndex UndefLocID = VarLocIDs.insert(UndefVL); 
+        Transfers.push_back({&MI, UndefLocID}); 
+      } 
+    } 
+    OpenRanges.erase(KillSet, VarLocIDs); 
+  } 
+ 
+  // Try to recognise spill and restore instructions that may create a new 
+  // variable location. 
+  if (isLocationSpill(MI, MF, Reg)) { 
+    TKind = TransferKind::TransferSpill; 
+    LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump();); 
+    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) 
+                      << "\n"); 
+  } else { 
+    if (!(Loc = isRestoreInstruction(MI, MF, Reg))) 
+      return; 
+    TKind = TransferKind::TransferRestore; 
+    LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump();); 
+    LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) 
+                      << "\n"); 
+  } 
+  // Check if the register or spill location is the location of a debug value. 
+  auto TransferCandidates = OpenRanges.getEmptyVarLocRange(); 
+  if (TKind == TransferKind::TransferSpill) 
+    TransferCandidates = OpenRanges.getRegisterVarLocs(Reg); 
+  else if (TKind == TransferKind::TransferRestore) 
+    TransferCandidates = OpenRanges.getSpillVarLocs(); 
+  for (uint64_t ID : TransferCandidates) { 
+    LocIndex Idx = LocIndex::fromRawInteger(ID); 
+    const VarLoc &VL = VarLocIDs[Idx]; 
+    if (TKind == TransferKind::TransferSpill) { 
+      assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?"); 
+      LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '(' 
+                        << VL.Var.getVariable()->getName() << ")\n"); 
+    } else { 
+      assert(TKind == TransferKind::TransferRestore && 
+             VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); 
+      if (VL.Loc.SpillLocation != *Loc) 
+        // The spill location is not the location of a debug value. 
+        continue; 
+      LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '(' 
+                        << VL.Var.getVariable()->getName() << ")\n"); 
+    } 
+    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind, 
+                            Reg); 
+    // FIXME: A comment should explain why it's correct to return early here, 
+    // if that is in fact correct. 
+    return; 
+  } 
+} 
+ 
+/// If \p MI is a register copy instruction, that copies a previously tracked 
+/// value from one register to another register that is callee saved, we 
+/// create new DBG_VALUE instruction  described with copy destination register. 
+void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI, 
+                                           OpenRangesSet &OpenRanges, 
+                                           VarLocMap &VarLocIDs, 
+                                           TransferMap &Transfers) { 
+  auto DestSrc = TII->isCopyInstr(MI); 
+  if (!DestSrc) 
+    return; 
+ 
+  const MachineOperand *DestRegOp = DestSrc->Destination; 
+  const MachineOperand *SrcRegOp = DestSrc->Source; 
+ 
+  if (!DestRegOp->isDef()) 
+    return; 
+ 
+  auto isCalleeSavedReg = [&](Register Reg) { 
+    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) 
+      if (CalleeSavedRegs.test(*RAI)) 
+        return true; 
+    return false; 
+  }; 
+ 
+  Register SrcReg = SrcRegOp->getReg(); 
+  Register DestReg = DestRegOp->getReg(); 
+ 
+  // We want to recognize instructions where destination register is callee 
+  // saved register. If register that could be clobbered by the call is 
+  // included, there would be a great chance that it is going to be clobbered 
+  // soon. It is more likely that previous register location, which is callee 
+  // saved, is going to stay unclobbered longer, even if it is killed. 
+  if (!isCalleeSavedReg(DestReg)) 
+    return; 
+ 
+  // Remember an entry value movement. If we encounter a new debug value of 
+  // a parameter describing only a moving of the value around, rather then 
+  // modifying it, we are still able to use the entry value if needed. 
+  if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) { 
+    for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { 
+      LocIndex Idx = LocIndex::fromRawInteger(ID); 
+      const VarLoc &VL = VarLocIDs[Idx]; 
+      if (VL.getEntryValueBackupReg() == SrcReg) { 
+        LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump();); 
+        VarLoc EntryValLocCopyBackup = 
+            VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg); 
+ 
+        // Stop tracking the original entry value. 
+        OpenRanges.erase(VL); 
+ 
+        // Start tracking the entry value copy. 
+        LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup); 
+        OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup); 
+        break; 
+      } 
+    } 
+  } 
+ 
+  if (!SrcRegOp->isKill()) 
+    return; 
+ 
+  for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) { 
+    LocIndex Idx = LocIndex::fromRawInteger(ID); 
+    assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?"); 
+    insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, 
+                            TransferKind::TransferCopy, DestReg); 
+    // FIXME: A comment should explain why it's correct to return early here, 
+    // if that is in fact correct. 
+    return; 
+  } 
+} 
+ 
+/// Terminate all open ranges at the end of the current basic block. 
+bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB, 
+                                         OpenRangesSet &OpenRanges, 
+                                         VarLocInMBB &OutLocs, 
+                                         const VarLocMap &VarLocIDs) { 
+  bool Changed = false; 
+ 
+  LLVM_DEBUG(for (uint64_t ID 
+                  : OpenRanges.getVarLocs()) { 
+    // Copy OpenRanges to OutLocs, if not already present. 
+    dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  "; 
+    VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI); 
+  }); 
+  VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs); 
+  Changed = VLS != OpenRanges.getVarLocs(); 
+  // New OutLocs set may be different due to spill, restore or register 
+  // copy instruction processing. 
+  if (Changed) 
+    VLS = OpenRanges.getVarLocs(); 
+  OpenRanges.clear(); 
+  return Changed; 
+} 
+ 
+/// Accumulate a mapping between each DILocalVariable fragment and other 
+/// fragments of that DILocalVariable which overlap. This reduces work during 
+/// the data-flow stage from "Find any overlapping fragments" to "Check if the 
+/// known-to-overlap fragments are present". 
+/// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for 
+///           fragment usage. 
+/// \param SeenFragments Map from DILocalVariable to all fragments of that 
+///           Variable which are known to exist. 
+/// \param OverlappingFragments The overlap map being constructed, from one 
+///           Var/Fragment pair to a vector of fragments known to overlap. 
+void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI, 
+                                            VarToFragments &SeenFragments, 
+                                            OverlapMap &OverlappingFragments) { 
+  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), 
+                      MI.getDebugLoc()->getInlinedAt()); 
+  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); 
+ 
+  // If this is the first sighting of this variable, then we are guaranteed 
+  // there are currently no overlapping fragments either. Initialize the set 
+  // of seen fragments, record no overlaps for the current one, and return. 
+  auto SeenIt = SeenFragments.find(MIVar.getVariable()); 
+  if (SeenIt == SeenFragments.end()) { 
+    SmallSet<FragmentInfo, 4> OneFragment; 
+    OneFragment.insert(ThisFragment); 
+    SeenFragments.insert({MIVar.getVariable(), OneFragment}); 
+ 
+    OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); 
+    return; 
+  } 
+ 
+  // If this particular Variable/Fragment pair already exists in the overlap 
+  // map, it has already been accounted for. 
+  auto IsInOLapMap = 
+      OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); 
+  if (!IsInOLapMap.second) 
+    return; 
+ 
+  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second; 
+  auto &AllSeenFragments = SeenIt->second; 
+ 
+  // Otherwise, examine all other seen fragments for this variable, with "this" 
+  // fragment being a previously unseen fragment. Record any pair of 
+  // overlapping fragments. 
+  for (auto &ASeenFragment : AllSeenFragments) { 
+    // Does this previously seen fragment overlap? 
+    if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) { 
+      // Yes: Mark the current fragment as being overlapped. 
+      ThisFragmentsOverlaps.push_back(ASeenFragment); 
+      // Mark the previously seen fragment as being overlapped by the current 
+      // one. 
+      auto ASeenFragmentsOverlaps = 
+          OverlappingFragments.find({MIVar.getVariable(), ASeenFragment}); 
+      assert(ASeenFragmentsOverlaps != OverlappingFragments.end() && 
+             "Previously seen var fragment has no vector of overlaps"); 
+      ASeenFragmentsOverlaps->second.push_back(ThisFragment); 
+    } 
+  } 
+ 
+  AllSeenFragments.insert(ThisFragment); 
+} 
+ 
+/// This routine creates OpenRanges. 
+void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges, 
+                              VarLocMap &VarLocIDs, TransferMap &Transfers) { 
+  transferDebugValue(MI, OpenRanges, VarLocIDs); 
+  transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers); 
+  transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers); 
+  transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers); 
+} 
+ 
+/// This routine joins the analysis results of all incoming edges in @MBB by 
+/// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same 
+/// source variable in all the predecessors of @MBB reside in the same location. 
+bool VarLocBasedLDV::join( 
+    MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, 
+    const VarLocMap &VarLocIDs, 
+    SmallPtrSet<const MachineBasicBlock *, 16> &Visited, 
+    SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) { 
+  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); 
+ 
+  VarLocSet InLocsT(Alloc); // Temporary incoming locations. 
+ 
+  // For all predecessors of this MBB, find the set of VarLocs that 
+  // can be joined. 
+  int NumVisited = 0; 
+  for (auto p : MBB.predecessors()) { 
+    // Ignore backedges if we have not visited the predecessor yet. As the 
+    // predecessor hasn't yet had locations propagated into it, most locations 
+    // will not yet be valid, so treat them as all being uninitialized and 
+    // potentially valid. If a location guessed to be correct here is 
+    // invalidated later, we will remove it when we revisit this block. 
+    if (!Visited.count(p)) { 
+      LLVM_DEBUG(dbgs() << "  ignoring unvisited pred MBB: " << p->getNumber() 
+                        << "\n"); 
+      continue; 
+    } 
+    auto OL = OutLocs.find(p); 
+    // Join is null in case of empty OutLocs from any of the pred. 
+    if (OL == OutLocs.end()) 
+      return false; 
+ 
+    // Just copy over the Out locs to incoming locs for the first visited 
+    // predecessor, and for all other predecessors join the Out locs. 
+    VarLocSet &OutLocVLS = *OL->second.get(); 
+    if (!NumVisited) 
+      InLocsT = OutLocVLS; 
+    else 
+      InLocsT &= OutLocVLS; 
+ 
+    LLVM_DEBUG({ 
+      if (!InLocsT.empty()) { 
+        for (uint64_t ID : InLocsT) 
+          dbgs() << "  gathered candidate incoming var: " 
+                 << VarLocIDs[LocIndex::fromRawInteger(ID)] 
+                        .Var.getVariable() 
+                        ->getName() 
+                 << "\n"; 
+      } 
+    }); 
+ 
+    NumVisited++; 
+  } 
+ 
+  // Filter out DBG_VALUES that are out of scope. 
+  VarLocSet KillSet(Alloc); 
+  bool IsArtificial = ArtificialBlocks.count(&MBB); 
+  if (!IsArtificial) { 
+    for (uint64_t ID : InLocsT) { 
+      LocIndex Idx = LocIndex::fromRawInteger(ID); 
+      if (!VarLocIDs[Idx].dominates(LS, MBB)) { 
+        KillSet.set(ID); 
+        LLVM_DEBUG({ 
+          auto Name = VarLocIDs[Idx].Var.getVariable()->getName(); 
+          dbgs() << "  killing " << Name << ", it doesn't dominate MBB\n"; 
+        }); 
+      } 
+    } 
+  } 
+  InLocsT.intersectWithComplement(KillSet); 
+ 
+  // As we are processing blocks in reverse post-order we 
+  // should have processed at least one predecessor, unless it 
+  // is the entry block which has no predecessor. 
+  assert((NumVisited || MBB.pred_empty()) && 
+         "Should have processed at least one predecessor"); 
+ 
+  VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs); 
+  bool Changed = false; 
+  if (ILS != InLocsT) { 
+    ILS = InLocsT; 
+    Changed = true; 
+  } 
+ 
+  return Changed; 
+} 
+ 
+void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs, 
+                                       VarLocMap &VarLocIDs) { 
+  // PendingInLocs records all locations propagated into blocks, which have 
+  // not had DBG_VALUE insts created. Go through and create those insts now. 
+  for (auto &Iter : PendingInLocs) { 
+    // Map is keyed on a constant pointer, unwrap it so we can insert insts. 
+    auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first); 
+    VarLocSet &Pending = *Iter.second.get(); 
+ 
+    for (uint64_t ID : Pending) { 
+      // The ID location is live-in to MBB -- work out what kind of machine 
+      // location it is and create a DBG_VALUE. 
+      const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)]; 
+      if (DiffIt.isEntryBackupLoc()) 
+        continue; 
+      MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent()); 
+      MBB.insert(MBB.instr_begin(), MI); 
+ 
+      (void)MI; 
+      LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump();); 
+    } 
+  } 
+} 
+ 
+bool VarLocBasedLDV::isEntryValueCandidate( 
+    const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const { 
+  assert(MI.isDebugValue() && "This must be DBG_VALUE."); 
+ 
+  // TODO: Add support for local variables that are expressed in terms of 
+  // parameters entry values. 
+  // TODO: Add support for modified arguments that can be expressed 
+  // by using its entry value. 
+  auto *DIVar = MI.getDebugVariable(); 
+  if (!DIVar->isParameter()) 
+    return false; 
+ 
+  // Do not consider parameters that belong to an inlined function. 
+  if (MI.getDebugLoc()->getInlinedAt()) 
+    return false; 
+ 
+  // Only consider parameters that are described using registers. Parameters 
+  // that are passed on the stack are not yet supported, so ignore debug 
+  // values that are described by the frame or stack pointer. 
+  if (!isRegOtherThanSPAndFP(MI.getDebugOperand(0), MI, TRI)) 
+    return false; 
+ 
+  // If a parameter's value has been propagated from the caller, then the 
+  // parameter's DBG_VALUE may be described using a register defined by some 
+  // instruction in the entry block, in which case we shouldn't create an 
+  // entry value. 
+  if (DefinedRegs.count(MI.getDebugOperand(0).getReg())) 
+    return false; 
+ 
+  // TODO: Add support for parameters that have a pre-existing debug expressions 
+  // (e.g. fragments). 
+  if (MI.getDebugExpression()->getNumElements() > 0) 
+    return false; 
+ 
+  return true; 
+} 
+ 
+/// Collect all register defines (including aliases) for the given instruction. 
+static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs, 
+                           const TargetRegisterInfo *TRI) { 
+  for (const MachineOperand &MO : MI.operands()) 
+    if (MO.isReg() && MO.isDef() && MO.getReg()) 
+      for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) 
+        Regs.insert(*AI); 
+} 
+ 
+/// This routine records the entry values of function parameters. The values 
+/// could be used as backup values. If we loose the track of some unmodified 
+/// parameters, the backup values will be used as a primary locations. 
+void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI, 
+                                       const DefinedRegsSet &DefinedRegs, 
+                                       OpenRangesSet &OpenRanges, 
+                                       VarLocMap &VarLocIDs) { 
+  if (TPC) { 
+    auto &TM = TPC->getTM<TargetMachine>(); 
+    if (!TM.Options.ShouldEmitDebugEntryValues()) 
+      return; 
+  } 
+ 
+  DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(), 
+                  MI.getDebugLoc()->getInlinedAt()); 
+ 
+  if (!isEntryValueCandidate(MI, DefinedRegs) || 
+      OpenRanges.getEntryValueBackup(V)) 
+    return; 
+ 
+  LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump();); 
+ 
+  // Create the entry value and use it as a backup location until it is 
+  // valid. It is valid until a parameter is not changed. 
+  DIExpression *NewExpr = 
+      DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue); 
+  VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr); 
+  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup); 
+  OpenRanges.insert(EntryValLocID, EntryValLocAsBackup); 
+} 
+ 
+/// Calculate the liveness information for the given machine function and 
+/// extend ranges across basic blocks. 
+bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) { 
+  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n"); 
+ 
+  if (!MF.getFunction().getSubprogram()) 
+    // VarLocBaseLDV will already have removed all DBG_VALUEs. 
+    return false; 
+ 
+  // Skip functions from NoDebug compilation units. 
+  if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() == 
+      DICompileUnit::NoDebug) 
+    return false; 
+ 
+  TRI = MF.getSubtarget().getRegisterInfo(); 
+  TII = MF.getSubtarget().getInstrInfo(); 
+  TFI = MF.getSubtarget().getFrameLowering(); 
+  TFI->getCalleeSaves(MF, CalleeSavedRegs); 
+  this->TPC = TPC; 
+  LS.initialize(MF); 
+ 
+  bool Changed = false; 
+  bool OLChanged = false; 
+  bool MBBJoined = false; 
+ 
+  VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors. 
+  OverlapMap OverlapFragments; // Map of overlapping variable fragments. 
+  OpenRangesSet OpenRanges(Alloc, OverlapFragments); 
+                              // Ranges that are open until end of bb. 
+  VarLocInMBB OutLocs;        // Ranges that exist beyond bb. 
+  VarLocInMBB InLocs;         // Ranges that are incoming after joining. 
+  TransferMap Transfers;      // DBG_VALUEs associated with transfers (such as 
+                              // spills, copies and restores). 
+ 
+  VarToFragments SeenFragments; 
+ 
+  // Blocks which are artificial, i.e. blocks which exclusively contain 
+  // instructions without locations, or with line 0 locations. 
+  SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; 
+ 
+  DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; 
+  DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; 
+  std::priority_queue<unsigned int, std::vector<unsigned int>, 
+                      std::greater<unsigned int>> 
+      Worklist; 
+  std::priority_queue<unsigned int, std::vector<unsigned int>, 
+                      std::greater<unsigned int>> 
+      Pending; 
+ 
+  // Set of register defines that are seen when traversing the entry block 
+  // looking for debug entry value candidates. 
+  DefinedRegsSet DefinedRegs; 
+ 
+  // Only in the case of entry MBB collect DBG_VALUEs representing 
+  // function parameters in order to generate debug entry values for them. 
+  MachineBasicBlock &First_MBB = *(MF.begin()); 
+  for (auto &MI : First_MBB) { 
+    collectRegDefs(MI, DefinedRegs, TRI); 
+    if (MI.isDebugValue()) 
+      recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs); 
+  } 
+ 
+  // Initialize per-block structures and scan for fragment overlaps. 
+  for (auto &MBB : MF) 
+    for (auto &MI : MBB) 
+      if (MI.isDebugValue()) 
+        accumulateFragmentMap(MI, SeenFragments, OverlapFragments); 
+ 
+  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { 
+    if (const DebugLoc &DL = MI.getDebugLoc()) 
+      return DL.getLine() != 0; 
+    return false; 
+  }; 
+  for (auto &MBB : MF) 
+    if (none_of(MBB.instrs(), hasNonArtificialLocation)) 
+      ArtificialBlocks.insert(&MBB); 
+ 
+  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, 
+                              "OutLocs after initialization", dbgs())); 
+ 
+  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); 
+  unsigned int RPONumber = 0; 
+  for (auto RI = RPOT.begin(), RE = RPOT.end(); RI != RE; ++RI) { 
+    OrderToBB[RPONumber] = *RI; 
+    BBToOrder[*RI] = RPONumber; 
+    Worklist.push(RPONumber); 
+    ++RPONumber; 
+  } 
+ 
+  if (RPONumber > InputBBLimit) { 
+    unsigned NumInputDbgValues = 0; 
+    for (auto &MBB : MF) 
+      for (auto &MI : MBB) 
+        if (MI.isDebugValue()) 
+          ++NumInputDbgValues; 
+    if (NumInputDbgValues > InputDbgValueLimit) { 
+      LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName() 
+                        << " has " << RPONumber << " basic blocks and " 
+                        << NumInputDbgValues 
+                        << " input DBG_VALUEs, exceeding limits.\n"); 
+      return false; 
+    } 
+  } 
+ 
+  // This is a standard "union of predecessor outs" dataflow problem. 
+  // To solve it, we perform join() and process() using the two worklist method 
+  // until the ranges converge. 
+  // Ranges have converged when both worklists are empty. 
+  SmallPtrSet<const MachineBasicBlock *, 16> Visited; 
+  while (!Worklist.empty() || !Pending.empty()) { 
+    // We track what is on the pending worklist to avoid inserting the same 
+    // thing twice.  We could avoid this with a custom priority queue, but this 
+    // is probably not worth it. 
+    SmallPtrSet<MachineBasicBlock *, 16> OnPending; 
+    LLVM_DEBUG(dbgs() << "Processing Worklist\n"); 
+    while (!Worklist.empty()) { 
+      MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; 
+      Worklist.pop(); 
+      MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, 
+                       ArtificialBlocks); 
+      MBBJoined |= Visited.insert(MBB).second; 
+      if (MBBJoined) { 
+        MBBJoined = false; 
+        Changed = true; 
+        // Now that we have started to extend ranges across BBs we need to 
+        // examine spill, copy and restore instructions to see whether they 
+        // operate with registers that correspond to user variables. 
+        // First load any pending inlocs. 
+        OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs); 
+        for (auto &MI : *MBB) 
+          process(MI, OpenRanges, VarLocIDs, Transfers); 
+        OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs); 
+ 
+        LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, 
+                                    "OutLocs after propagating", dbgs())); 
+        LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, 
+                                    "InLocs after propagating", dbgs())); 
+ 
+        if (OLChanged) { 
+          OLChanged = false; 
+          for (auto s : MBB->successors()) 
+            if (OnPending.insert(s).second) { 
+              Pending.push(BBToOrder[s]); 
+            } 
+        } 
+      } 
+    } 
+    Worklist.swap(Pending); 
+    // At this point, pending must be empty, since it was just the empty 
+    // worklist 
+    assert(Pending.empty() && "Pending should be empty"); 
+  } 
+ 
+  // Add any DBG_VALUE instructions created by location transfers. 
+  for (auto &TR : Transfers) { 
+    assert(!TR.TransferInst->isTerminator() && 
+           "Cannot insert DBG_VALUE after terminator"); 
+    MachineBasicBlock *MBB = TR.TransferInst->getParent(); 
+    const VarLoc &VL = VarLocIDs[TR.LocationID]; 
+    MachineInstr *MI = VL.BuildDbgValue(MF); 
+    MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI); 
+  } 
+  Transfers.clear(); 
+ 
+  // Deferred inlocs will not have had any DBG_VALUE insts created; do 
+  // that now. 
+  flushPendingLocs(InLocs, VarLocIDs); 
+ 
+  LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); 
+  LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); 
+  return Changed; 
+} 
+ 
+LDVImpl * 
+llvm::makeVarLocBasedLiveDebugValues() 
+{ 
+  return new VarLocBasedLDV(); 
+}