vendor/llvm-project/llvmorg-13-init-16847-g88e66fa60ae5vendor/llvm-project/llvmorg-12.0.1-rc2-0-ge7dac564cd0evendor/llvm-project/llvmorg-12.0.1-0-gfed41342a82f

4 files changed, 1397 insertions, 435 deletions

diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
index 18ffe8ba0669..dc9907058340 100644
--- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
+++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
@@ -148,6 +148,7 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -160,6 +161,7 @@
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineInstrBundle.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
@@ -184,6 +186,8 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TypeSize.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
@@ -199,23 +203,16 @@
 
 using namespace llvm;
 
+// SSAUpdaterImple sets DEBUG_TYPE, change it.
+#undef DEBUG_TYPE
 #define DEBUG_TYPE "livedebugvalues"
 
-STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted");
-STATISTIC(NumRemoved, "Number of DBG_VALUE instructions removed");
-
 // Act more like the VarLoc implementation, by propagating some locations too
 // far and ignoring some transfers.
 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
                                    cl::desc("Act like old LiveDebugValues did"),
                                    cl::init(false));
 
-// Rely on isStoreToStackSlotPostFE and similar to observe all stack spills.
-static cl::opt<bool>
-    ObserveAllStackops("observe-all-stack-ops", cl::Hidden,
-                       cl::desc("Allow non-kill spill and restores"),
-                       cl::init(false));
-
 namespace {
 
 // The location at which a spilled value resides. It consists of a register and
@@ -959,25 +956,27 @@ public:
 class TransferTracker {
 public:
   const TargetInstrInfo *TII;
+  const TargetLowering *TLI;
   /// This machine location tracker is assumed to always contain the up-to-date
   /// value mapping for all machine locations. TransferTracker only reads
   /// information from it. (XXX make it const?)
   MLocTracker *MTracker;
   MachineFunction &MF;
+  bool ShouldEmitDebugEntryValues;
 
   /// Record of all changes in variable locations at a block position. Awkwardly
   /// we allow inserting either before or after the point: MBB != nullptr
   /// indicates it's before, otherwise after.
   struct Transfer {
-    MachineBasicBlock::iterator Pos; /// Position to insert DBG_VALUes
-    MachineBasicBlock *MBB;          /// non-null if we should insert after.
+    MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
+    MachineBasicBlock *MBB; /// non-null if we should insert after.
     SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
   };
 
-  typedef struct {
+  struct LocAndProperties {
     LocIdx Loc;
     DbgValueProperties Properties;
-  } LocAndProperties;
+  };
 
   /// Collection of transfers (DBG_VALUEs) to be inserted.
   SmallVector<Transfer, 32> Transfers;
@@ -1027,9 +1026,13 @@ public:
 
   TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
                   MachineFunction &MF, const TargetRegisterInfo &TRI,
-                  const BitVector &CalleeSavedRegs)
+                  const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
       : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
-        CalleeSavedRegs(CalleeSavedRegs) {}
+        CalleeSavedRegs(CalleeSavedRegs) {
+    TLI = MF.getSubtarget().getTargetLowering();
+    auto &TM = TPC.getTM<TargetMachine>();
+    ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
+  }
 
   /// Load object with live-in variable values. \p mlocs contains the live-in
   /// values in each machine location, while \p vlocs the live-in variable
@@ -1097,6 +1100,8 @@ public:
         // use-before-def to be resolved as we step through the block.
         if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
           addUseBeforeDef(Var.first, Var.second.Properties, Num);
+        else
+          recoverAsEntryValue(Var.first, Var.second.Properties, Num);
         continue;
       }
 
@@ -1152,10 +1157,73 @@ public:
 
   /// Helper to move created DBG_VALUEs into Transfers collection.
   void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
-    if (PendingDbgValues.size() > 0) {
-      Transfers.push_back({Pos, MBB, PendingDbgValues});
-      PendingDbgValues.clear();
-    }
+    if (PendingDbgValues.size() == 0)
+      return;
+
+    // Pick out the instruction start position.
+    MachineBasicBlock::instr_iterator BundleStart;
+    if (MBB && Pos == MBB->begin())
+      BundleStart = MBB->instr_begin();
+    else
+      BundleStart = getBundleStart(Pos->getIterator());
+
+    Transfers.push_back({BundleStart, MBB, PendingDbgValues});
+    PendingDbgValues.clear();
+  }
+
+  bool isEntryValueVariable(const DebugVariable &Var,
+                            const DIExpression *Expr) const {
+    if (!Var.getVariable()->isParameter())
+      return false;
+
+    if (Var.getInlinedAt())
+      return false;
+
+    if (Expr->getNumElements() > 0)
+      return false;
+
+    return true;
+  }
+
+  bool isEntryValueValue(const ValueIDNum &Val) const {
+    // Must be in entry block (block number zero), and be a PHI / live-in value.
+    if (Val.getBlock() || !Val.isPHI())
+      return false;
+
+    // Entry values must enter in a register.
+    if (MTracker->isSpill(Val.getLoc()))
+      return false;
+
+    Register SP = TLI->getStackPointerRegisterToSaveRestore();
+    Register FP = TRI.getFrameRegister(MF);
+    Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
+    return Reg != SP && Reg != FP;
+  }
+
+  bool recoverAsEntryValue(const DebugVariable &Var, DbgValueProperties &Prop,
+                           const ValueIDNum &Num) {
+    // Is this variable location a candidate to be an entry value. First,
+    // should we be trying this at all?
+    if (!ShouldEmitDebugEntryValues)
+      return false;
+
+    // Is the variable appropriate for entry values (i.e., is a parameter).
+    if (!isEntryValueVariable(Var, Prop.DIExpr))
+      return false;
+
+    // Is the value assigned to this variable still the entry value?
+    if (!isEntryValueValue(Num))
+      return false;
+
+    // Emit a variable location using an entry value expression.
+    DIExpression *NewExpr =
+        DIExpression::prepend(Prop.DIExpr, DIExpression::EntryValue);
+    Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
+    MachineOperand MO = MachineOperand::CreateReg(Reg, false);
+    MO.setIsDebug(true);
+
+    PendingDbgValues.push_back(emitMOLoc(MO, Var, {NewExpr, Prop.Indirect}));
+    return true;
   }
 
   /// Change a variable value after encountering a DBG_VALUE inside a block.
@@ -1224,26 +1292,70 @@ public:
     }
   }
 
-  /// Explicitly terminate variable locations based on \p mloc. Creates undef
-  /// DBG_VALUEs for any variables that were located there, and clears
-  /// #ActiveMLoc / #ActiveVLoc tracking information for that location.
-  void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos) {
-    assert(MTracker->isSpill(MLoc));
+  /// Account for a location \p mloc being clobbered. Examine the variable
+  /// locations that will be terminated: and try to recover them by using
+  /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
+  /// explicitly terminate a location if it can't be recovered.
+  void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
+                   bool MakeUndef = true) {
     auto ActiveMLocIt = ActiveMLocs.find(MLoc);
     if (ActiveMLocIt == ActiveMLocs.end())
       return;
 
+    // What was the old variable value?
+    ValueIDNum OldValue = VarLocs[MLoc.asU64()];
     VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
 
+    // Examine the remaining variable locations: if we can find the same value
+    // again, we can recover the location.
+    Optional<LocIdx> NewLoc = None;
+    for (auto Loc : MTracker->locations())
+      if (Loc.Value == OldValue)
+        NewLoc = Loc.Idx;
+
+    // If there is no location, and we weren't asked to make the variable
+    // explicitly undef, then stop here.
+    if (!NewLoc && !MakeUndef) {
+      // Try and recover a few more locations with entry values.
+      for (auto &Var : ActiveMLocIt->second) {
+        auto &Prop = ActiveVLocs.find(Var)->second.Properties;
+        recoverAsEntryValue(Var, Prop, OldValue);
+      }
+      flushDbgValues(Pos, nullptr);
+      return;
+    }
+
+    // Examine all the variables based on this location.
+    DenseSet<DebugVariable> NewMLocs;
     for (auto &Var : ActiveMLocIt->second) {
       auto ActiveVLocIt = ActiveVLocs.find(Var);
-      // Create an undef. We can't feed in a nullptr DIExpression alas,
-      // so use the variables last expression. Pass None as the location.
+      // Re-state the variable location: if there's no replacement then NewLoc
+      // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
+      // identifying the alternative location will be emitted.
       const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
       DbgValueProperties Properties(Expr, false);
-      PendingDbgValues.push_back(MTracker->emitLoc(None, Var, Properties));
-      ActiveVLocs.erase(ActiveVLocIt);
+      PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));
+
+      // Update machine locations <=> variable locations maps. Defer updating
+      // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
+      if (!NewLoc) {
+        ActiveVLocs.erase(ActiveVLocIt);
+      } else {
+        ActiveVLocIt->second.Loc = *NewLoc;
+        NewMLocs.insert(Var);
+      }
     }
+
+    // Commit any deferred ActiveMLoc changes.
+    if (!NewMLocs.empty())
+      for (auto &Var : NewMLocs)
+        ActiveMLocs[*NewLoc].insert(Var);
+
+    // We lazily track what locations have which values; if we've found a new
+    // location for the clobbered value, remember it.
+    if (NewLoc)
+      VarLocs[NewLoc->asU64()] = OldValue;
+
     flushDbgValues(Pos, nullptr);
 
     ActiveMLocIt->second.clear();
@@ -1332,6 +1444,7 @@ private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
+  const MachineFrameInfo *MFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
   TargetPassConfig *TPC;
@@ -1372,6 +1485,23 @@ private:
   /// instruction numbers in DBG_INSTR_REFs into machine value numbers.
   std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;
 
+  /// Record of where we observed a DBG_PHI instruction.
+  class DebugPHIRecord {
+  public:
+    uint64_t InstrNum;      ///< Instruction number of this DBG_PHI.
+    MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred.
+    ValueIDNum ValueRead;   ///< The value number read by the DBG_PHI.
+    LocIdx ReadLoc;         ///< Register/Stack location the DBG_PHI reads.
+
+    operator unsigned() const { return InstrNum; }
+  };
+
+  /// Map from instruction numbers defined by DBG_PHIs to a record of what that
+  /// DBG_PHI read and where. Populated and edited during the machine value
+  /// location problem -- we use LLVMs SSA Updater to fix changes by
+  /// optimizations that destroy PHI instructions.
+  SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;
+
   // Map of overlapping variable fragments.
   OverlapMap OverlapFragments;
   VarToFragments SeenFragments;
@@ -1398,7 +1528,8 @@ private:
   SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
 
   /// Observe a single instruction while stepping through a block.
-  void process(MachineInstr &MI);
+  void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr,
+               ValueIDNum **MLiveIns = nullptr);
 
   /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
   /// \returns true if MI was recognized and processed.
@@ -1406,7 +1537,13 @@ private:
 
   /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
   /// \returns true if MI was recognized and processed.
-  bool transferDebugInstrRef(MachineInstr &MI);
+  bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts,
+                             ValueIDNum **MLiveIns);
+
+  /// Stores value-information about where this PHI occurred, and what
+  /// instruction number is associated with it.
+  /// \returns true if MI was recognized and processed.
+  bool transferDebugPHI(MachineInstr &MI);
 
   /// Examines whether \p MI is copy instruction, and notifies trackers.
   /// \returns true if MI was recognized and processed.
@@ -1425,6 +1562,18 @@ private:
 
   void accumulateFragmentMap(MachineInstr &MI);
 
+  /// Determine the machine value number referred to by (potentially several)
+  /// DBG_PHI instructions. Block duplication and tail folding can duplicate
+  /// DBG_PHIs, shifting the position where values in registers merge, and
+  /// forming another mini-ssa problem to solve.
+  /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
+  /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
+  /// \returns The machine value number at position Here, or None.
+  Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
+                                      ValueIDNum **MLiveOuts,
+                                      ValueIDNum **MLiveIns, MachineInstr &Here,
+                                      uint64_t InstrNum);
+
   /// Step through the function, recording register definitions and movements
   /// in an MLocTracker. Convert the observations into a per-block transfer
   /// function in \p MLocTransfer, suitable for using with the machine value
@@ -1527,8 +1676,9 @@ private:
   /// right now "order of appearence in function, when explored in RPO", so
   /// that we can compare explictly against VarLocBasedImpl.
   void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
-                     ValueIDNum **MInLocs,
-                     DenseMap<DebugVariable, unsigned> &AllVarsNumbering);
+                     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
+                     DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
+                     const TargetPassConfig &TPC);
 
   /// Boilerplate computation of some initial sets, artifical blocks and
   /// RPOT block ordering.
@@ -1640,7 +1790,9 @@ bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
   return true;
 }
 
-bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
+bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
+                                             ValueIDNum **MLiveOuts,
+                                             ValueIDNum **MLiveIns) {
   if (!MI.isDebugRef())
     return false;
 
@@ -1669,12 +1821,22 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
 
   // Various optimizations may have happened to the value during codegen,
   // recorded in the value substitution table. Apply any substitutions to
-  // the instruction / operand number in this DBG_INSTR_REF.
-  auto Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
-  while (Sub != MF.DebugValueSubstitutions.end()) {
-    InstNo = Sub->second.first;
-    OpNo = Sub->second.second;
-    Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
+  // the instruction / operand number in this DBG_INSTR_REF, and collect
+  // any subregister extractions performed during optimization.
+
+  // Create dummy substitution with Src set, for lookup.
+  auto SoughtSub =
+      MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);
+
+  SmallVector<unsigned, 4> SeenSubregs;
+  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
+  while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&
+         LowerBoundIt->Src == SoughtSub.Src) {
+    std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
+    SoughtSub.Src = LowerBoundIt->Dest;
+    if (unsigned Subreg = LowerBoundIt->Subreg)
+      SeenSubregs.push_back(Subreg);
+    LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);
   }
 
   // Default machine value number is <None> -- if no instruction defines
@@ -1682,8 +1844,10 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
   Optional<ValueIDNum> NewID = None;
 
   // Try to lookup the instruction number, and find the machine value number
-  // that it defines.
+  // that it defines. It could be an instruction, or a PHI.
   auto InstrIt = DebugInstrNumToInstr.find(InstNo);
+  auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
+                                DebugPHINumToValue.end(), InstNo);
   if (InstrIt != DebugInstrNumToInstr.end()) {
     const MachineInstr &TargetInstr = *InstrIt->second.first;
     uint64_t BlockNo = TargetInstr.getParent()->getNumber();
@@ -1698,6 +1862,82 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
     unsigned LocID = MTracker->getLocID(MO.getReg(), false);
     LocIdx L = MTracker->LocIDToLocIdx[LocID];
     NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
+  } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
+    // It's actually a PHI value. Which value it is might not be obvious, use
+    // the resolver helper to find out.
+    NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
+                           MI, InstNo);
+  }
+
+  // Apply any subregister extractions, in reverse. We might have seen code
+  // like this:
+  //    CALL64 @foo, implicit-def $rax
+  //    %0:gr64 = COPY $rax
+  //    %1:gr32 = COPY %0.sub_32bit
+  //    %2:gr16 = COPY %1.sub_16bit
+  //    %3:gr8  = COPY %2.sub_8bit
+  // In which case each copy would have been recorded as a substitution with
+  // a subregister qualifier. Apply those qualifiers now.
+  if (NewID && !SeenSubregs.empty()) {
+    unsigned Offset = 0;
+    unsigned Size = 0;
+
+    // Look at each subregister that we passed through, and progressively
+    // narrow in, accumulating any offsets that occur. Substitutions should
+    // only ever be the same or narrower width than what they read from;
+    // iterate in reverse order so that we go from wide to small.
+    for (unsigned Subreg : reverse(SeenSubregs)) {
+      unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
+      unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
+      Offset += ThisOffset;
+      Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);
+    }
+
+    // If that worked, look for an appropriate subregister with the register
+    // where the define happens. Don't look at values that were defined during
+    // a stack write: we can't currently express register locations within
+    // spills.
+    LocIdx L = NewID->getLoc();
+    if (NewID && !MTracker->isSpill(L)) {
+      // Find the register class for the register where this def happened.
+      // FIXME: no index for this?
+      Register Reg = MTracker->LocIdxToLocID[L];
+      const TargetRegisterClass *TRC = nullptr;
+      for (auto *TRCI : TRI->regclasses())
+        if (TRCI->contains(Reg))
+          TRC = TRCI;
+      assert(TRC && "Couldn't find target register class?");
+
+      // If the register we have isn't the right size or in the right place,
+      // Try to find a subregister inside it.
+      unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
+      if (Size != MainRegSize || Offset) {
+        // Enumerate all subregisters, searching.
+        Register NewReg = 0;
+        for (MCSubRegIterator SRI(Reg, TRI, false); SRI.isValid(); ++SRI) {
+          unsigned Subreg = TRI->getSubRegIndex(Reg, *SRI);
+          unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
+          unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
+          if (SubregSize == Size && SubregOffset == Offset) {
+            NewReg = *SRI;
+            break;
+          }
+        }
+
+        // If we didn't find anything: there's no way to express our value.
+        if (!NewReg) {
+          NewID = None;
+        } else {
+          // Re-state the value as being defined within the subregister
+          // that we found.
+          LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
+          NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
+        }
+      }
+    } else {
+      // If we can't handle subregisters, unset the new value.
+      NewID = None;
+    }
   }
 
   // We, we have a value number or None. Tell the variable value tracker about
@@ -1752,6 +1992,55 @@ bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
   MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
   TTracker->PendingDbgValues.push_back(DbgMI);
   TTracker->flushDbgValues(MI.getIterator(), nullptr);
+  return true;
+}
+
+bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
+  if (!MI.isDebugPHI())
+    return false;
+
+  // Analyse these only when solving the machine value location problem.
+  if (VTracker || TTracker)
+    return true;
+
+  // First operand is the value location, either a stack slot or register.
+  // Second is the debug instruction number of the original PHI.
+  const MachineOperand &MO = MI.getOperand(0);
+  unsigned InstrNum = MI.getOperand(1).getImm();
+
+  if (MO.isReg()) {
+    // The value is whatever's currently in the register. Read and record it,
+    // to be analysed later.
+    Register Reg = MO.getReg();
+    ValueIDNum Num = MTracker->readReg(Reg);
+    auto PHIRec = DebugPHIRecord(
+        {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
+    DebugPHINumToValue.push_back(PHIRec);
+  } else {
+    // The value is whatever's in this stack slot.
+    assert(MO.isFI());
+    unsigned FI = MO.getIndex();
+
+    // If the stack slot is dead, then this was optimized away.
+    // FIXME: stack slot colouring should account for slots that get merged.
+    if (MFI->isDeadObjectIndex(FI))
+      return true;
+
+    // Identify this spill slot.
+    Register Base;
+    StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
+    SpillLoc SL = {Base, Offs};
+    Optional<ValueIDNum> Num = MTracker->readSpill(SL);
+
+    if (!Num)
+      // Nothing ever writes to this slot. Curious, but nothing we can do.
+      return true;
+
+    // Record this DBG_PHI for later analysis.
+    auto DbgPHI = DebugPHIRecord(
+        {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)});
+    DebugPHINumToValue.push_back(DbgPHI);
+  }
 
   return true;
 }
@@ -1803,6 +2092,32 @@ void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
 
   for (auto *MO : RegMaskPtrs)
     MTracker->writeRegMask(MO, CurBB, CurInst);
+
+  if (!TTracker)
+    return;
+
+  // When committing variable values to locations: tell transfer tracker that
+  // we've clobbered things. It may be able to recover the variable from a
+  // different location.
+
+  // Inform TTracker about any direct clobbers.
+  for (uint32_t DeadReg : DeadRegs) {
+    LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
+    TTracker->clobberMloc(Loc, MI.getIterator(), false);
+  }
+
+  // Look for any clobbers performed by a register mask. Only test locations
+  // that are actually being tracked.
+  for (auto L : MTracker->locations()) {
+    // Stack locations can't be clobbered by regmasks.
+    if (MTracker->isSpill(L.Idx))
+      continue;
+
+    Register Reg = MTracker->LocIdxToLocID[L.Idx];
+    for (auto *MO : RegMaskPtrs)
+      if (MO->clobbersPhysReg(Reg))
+        TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
+  }
 }
 
 void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
@@ -1871,47 +2186,9 @@ bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,
   if (!isSpillInstruction(MI, MF))
     return false;
 
-  // XXX FIXME: On x86, isStoreToStackSlotPostFE returns '1' instead of an
-  // actual register number.
-  if (ObserveAllStackops) {
-    int FI;
-    Reg = TII->isStoreToStackSlotPostFE(MI, FI);
-    return Reg != 0;
-  }
-
-  auto isKilledReg = [&](const MachineOperand MO, unsigned &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;
-      unsigned 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;
+  int FI;
+  Reg = TII->isStoreToStackSlotPostFE(MI, FI);
+  return Reg != 0;
 }
 
 Optional<SpillLoc>
@@ -1950,8 +2227,12 @@ bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {
 
     if (TTracker) {
       Optional<LocIdx> MLoc = MTracker->getSpillMLoc(*Loc);
-      if (MLoc)
+      if (MLoc) {
+        // Un-set this location before clobbering, so that we don't salvage
+        // the variable location back to the same place.
+        MTracker->setMLoc(*MLoc, ValueIDNum::EmptyValue);
         TTracker->clobberMloc(*MLoc, MI.getIterator());
+      }
     }
   }
 
@@ -2066,6 +2347,15 @@ bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
   if (EmulateOldLDV && SrcReg != DestReg)
     MTracker->defReg(SrcReg, CurBB, CurInst);
 
+  // Finally, the copy might have clobbered variables based on the destination
+  // register. Tell TTracker about it, in case a backup location exists.
+  if (TTracker) {
+    for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
+      LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
+      TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
+    }
+  }
+
   return true;
 }
 
@@ -2124,13 +2414,16 @@ void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {
   AllSeenFragments.insert(ThisFragment);
 }
 
-void InstrRefBasedLDV::process(MachineInstr &MI) {
+void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts,
+                               ValueIDNum **MLiveIns) {
   // Try to interpret an MI as a debug or transfer instruction. Only if it's
   // none of these should we interpret it's register defs as new value
   // definitions.
   if (transferDebugValue(MI))
     return;
-  if (transferDebugInstrRef(MI))
+  if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
+    return;
+  if (transferDebugPHI(MI))
     return;
   if (transferRegisterCopy(MI))
     return;
@@ -2641,9 +2934,7 @@ std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
   auto &ILS = *ILSIt->second;
 
   // Order predecessors by RPOT order, for exploring them in that order.
-  SmallVector<MachineBasicBlock *, 8> BlockOrders;
-  for (auto p : MBB.predecessors())
-    BlockOrders.push_back(p);
+  SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
 
   auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
     return BBToOrder[A] < BBToOrder[B];
@@ -3128,9 +3419,10 @@ void InstrRefBasedLDV::dump_mloc_transfer(
 #endif
 
 void InstrRefBasedLDV::emitLocations(
-    MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MInLocs,
-    DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
-  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs);
+    MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
+    ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering,
+    const TargetPassConfig &TPC) {
+  TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
   unsigned NumLocs = MTracker->getNumLocs();
 
   // For each block, load in the machine value locations and variable value
@@ -3146,7 +3438,7 @@ void InstrRefBasedLDV::emitLocations(
     CurBB = bbnum;
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       TTracker->checkInstForNewValues(CurInst, MI.getIterator());
       ++CurInst;
     }
@@ -3178,9 +3470,14 @@ void InstrRefBasedLDV::emitLocations(
         MBB.insert(P.Pos, MI);
       }
     } else {
+      // Terminators, like tail calls, can clobber things. Don't try and place
+      // transfers after them.
+      if (P.Pos->isTerminator())
+        continue;
+
       MachineBasicBlock &MBB = *P.Pos->getParent();
       for (auto *MI : P.Insts) {
-        MBB.insertAfter(P.Pos, MI);
+        MBB.insertAfterBundle(P.Pos, MI);
       }
     }
   }
@@ -3201,12 +3498,27 @@ void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   // Compute mappings of block <=> RPO order.
   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;
-    BBNumToRPO[(*RI)->getNumber()] = RPONumber;
+  for (MachineBasicBlock *MBB : RPOT) {
+    OrderToBB[RPONumber] = MBB;
+    BBToOrder[MBB] = RPONumber;
+    BBNumToRPO[MBB->getNumber()] = RPONumber;
     ++RPONumber;
   }
+
+  // Order value substitutions by their "source" operand pair, for quick lookup.
+  llvm::sort(MF.DebugValueSubstitutions);
+
+#ifdef EXPENSIVE_CHECKS
+  // As an expensive check, test whether there are any duplicate substitution
+  // sources in the collection.
+  if (MF.DebugValueSubstitutions.size() > 2) {
+    for (auto It = MF.DebugValueSubstitutions.begin();
+         It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
+      assert(It->Src != std::next(It)->Src && "Duplicate variable location "
+                                              "substitution seen");
+    }
+  }
+#endif
 }
 
 /// Calculate the liveness information for the given machine function and
@@ -3224,6 +3536,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   TII = MF.getSubtarget().getInstrInfo();
   TFI = MF.getSubtarget().getFrameLowering();
   TFI->getCalleeSaves(MF, CalleeSavedRegs);
+  MFI = &MF.getFrameInfo();
   LS.initialize(MF);
 
   MTracker =
@@ -3266,6 +3579,21 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   // dataflow problem.
   mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
 
+  // Patch up debug phi numbers, turning unknown block-live-in values into
+  // either live-through machine values, or PHIs.
+  for (auto &DBG_PHI : DebugPHINumToValue) {
+    // Identify unresolved block-live-ins.
+    ValueIDNum &Num = DBG_PHI.ValueRead;
+    if (!Num.isPHI())
+      continue;
+
+    unsigned BlockNo = Num.getBlock();
+    LocIdx LocNo = Num.getLoc();
+    Num = MInLocs[BlockNo][LocNo.asU64()];
+  }
+  // Later, we'll be looking up ranges of instruction numbers.
+  llvm::sort(DebugPHINumToValue);
+
   // Walk back through each block / instruction, collecting DBG_VALUE
   // instructions and recording what machine value their operands refer to.
   for (auto &OrderPair : OrderToBB) {
@@ -3276,7 +3604,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
     MTracker->loadFromArray(MInLocs[CurBB], CurBB);
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       ++CurInst;
     }
     MTracker->reset();
@@ -3331,7 +3659,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   // Using the computed value locations and variable values for each block,
   // create the DBG_VALUE instructions representing the extended variable
   // locations.
-  emitLocations(MF, SavedLiveIns, MInLocs, AllVarsNumbering);
+  emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering, *TPC);
 
   for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
     delete[] MOutLocs[Idx];
@@ -3354,6 +3682,7 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   BBToOrder.clear();
   BBNumToRPO.clear();
   DebugInstrNumToInstr.clear();
+  DebugPHINumToValue.clear();
 
   return Changed;
 }
@@ -3361,3 +3690,389 @@ bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }
+
+namespace {
+class LDVSSABlock;
+class LDVSSAUpdater;
+
+// Pick a type to identify incoming block values as we construct SSA. We
+// can't use anything more robust than an integer unfortunately, as SSAUpdater
+// expects to zero-initialize the type.
+typedef uint64_t BlockValueNum;
+
+/// Represents an SSA PHI node for the SSA updater class. Contains the block
+/// this PHI is in, the value number it would have, and the expected incoming
+/// values from parent blocks.
+class LDVSSAPhi {
+public:
+  SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;
+  LDVSSABlock *ParentBlock;
+  BlockValueNum PHIValNum;
+  LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
+      : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
+
+  LDVSSABlock *getParent() { return ParentBlock; }
+};
+
+/// Thin wrapper around a block predecessor iterator. Only difference from a
+/// normal block iterator is that it dereferences to an LDVSSABlock.
+class LDVSSABlockIterator {
+public:
+  MachineBasicBlock::pred_iterator PredIt;
+  LDVSSAUpdater &Updater;
+
+  LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
+                      LDVSSAUpdater &Updater)
+      : PredIt(PredIt), Updater(Updater) {}
+
+  bool operator!=(const LDVSSABlockIterator &OtherIt) const {
+    return OtherIt.PredIt != PredIt;
+  }
+
+  LDVSSABlockIterator &operator++() {
+    ++PredIt;
+    return *this;
+  }
+
+  LDVSSABlock *operator*();
+};
+
+/// Thin wrapper around a block for SSA Updater interface. Necessary because
+/// we need to track the PHI value(s) that we may have observed as necessary
+/// in this block.
+class LDVSSABlock {
+public:
+  MachineBasicBlock &BB;
+  LDVSSAUpdater &Updater;
+  using PHIListT = SmallVector<LDVSSAPhi, 1>;
+  /// List of PHIs in this block. There should only ever be one.
+  PHIListT PHIList;
+
+  LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
+      : BB(BB), Updater(Updater) {}
+
+  LDVSSABlockIterator succ_begin() {
+    return LDVSSABlockIterator(BB.succ_begin(), Updater);
+  }
+
+  LDVSSABlockIterator succ_end() {
+    return LDVSSABlockIterator(BB.succ_end(), Updater);
+  }
+
+  /// SSAUpdater has requested a PHI: create that within this block record.
+  LDVSSAPhi *newPHI(BlockValueNum Value) {
+    PHIList.emplace_back(Value, this);
+    return &PHIList.back();
+  }
+
+  /// SSAUpdater wishes to know what PHIs already exist in this block.
+  PHIListT &phis() { return PHIList; }
+};
+
+/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
+/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
+// SSAUpdaterTraits<LDVSSAUpdater>.
+class LDVSSAUpdater {
+public:
+  /// Map of value numbers to PHI records.
+  DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;
+  /// Map of which blocks generate Undef values -- blocks that are not
+  /// dominated by any Def.
+  DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap;
+  /// Map of machine blocks to our own records of them.
+  DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;
+  /// Machine location where any PHI must occur.
+  LocIdx Loc;
+  /// Table of live-in machine value numbers for blocks / locations.
+  ValueIDNum **MLiveIns;
+
+  LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {}
+
+  void reset() {
+    for (auto &Block : BlockMap)
+      delete Block.second;
+
+    PHIs.clear();
+    UndefMap.clear();
+    BlockMap.clear();
+  }
+
+  ~LDVSSAUpdater() { reset(); }
+
+  /// For a given MBB, create a wrapper block for it. Stores it in the
+  /// LDVSSAUpdater block map.
+  LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
+    auto it = BlockMap.find(BB);
+    if (it == BlockMap.end()) {
+      BlockMap[BB] = new LDVSSABlock(*BB, *this);
+      it = BlockMap.find(BB);
+    }
+    return it->second;
+  }
+
+  /// Find the live-in value number for the given block. Looks up the value at
+  /// the PHI location on entry.
+  BlockValueNum getValue(LDVSSABlock *LDVBB) {
+    return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
+  }
+};
+
+LDVSSABlock *LDVSSABlockIterator::operator*() {
+  return Updater.getSSALDVBlock(*PredIt);
+}
+
+#ifndef NDEBUG
+
+raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
+  out << "SSALDVPHI " << PHI.PHIValNum;
+  return out;
+}
+
+#endif
+
+} // namespace
+
+namespace llvm {
+
+/// Template specialization to give SSAUpdater access to CFG and value
+/// information. SSAUpdater calls methods in these traits, passing in the
+/// LDVSSAUpdater object, to learn about blocks and the values they define.
+/// It also provides methods to create PHI nodes and track them.
+template <> class SSAUpdaterTraits<LDVSSAUpdater> {
+public:
+  using BlkT = LDVSSABlock;
+  using ValT = BlockValueNum;
+  using PhiT = LDVSSAPhi;
+  using BlkSucc_iterator = LDVSSABlockIterator;
+
+  // Methods to access block successors -- dereferencing to our wrapper class.
+  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
+  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
+
+  /// Iterator for PHI operands.
+  class PHI_iterator {
+  private:
+    LDVSSAPhi *PHI;
+    unsigned Idx;
+
+  public:
+    explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
+        : PHI(P), Idx(0) {}
+    PHI_iterator(LDVSSAPhi *P, bool) // end iterator
+        : PHI(P), Idx(PHI->IncomingValues.size()) {}
+
+    PHI_iterator &operator++() {
+      Idx++;
+      return *this;
+    }
+    bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
+    bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
+
+    BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
+
+    LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
+  };
+
+  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
+
+  static inline PHI_iterator PHI_end(PhiT *PHI) {
+    return PHI_iterator(PHI, true);
+  }
+
+  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
+  /// vector.
+  static void FindPredecessorBlocks(LDVSSABlock *BB,
+                                    SmallVectorImpl<LDVSSABlock *> *Preds) {
+    for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(),
+                                          E = BB->BB.pred_end();
+         PI != E; ++PI)
+      Preds->push_back(BB->Updater.getSSALDVBlock(*PI));
+  }
+
+  /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
+  /// register. For LiveDebugValues, represents a block identified as not having
+  /// any DBG_PHI predecessors.
+  static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
+    // Create a value number for this block -- it needs to be unique and in the
+    // "undef" collection, so that we know it's not real. Use a number
+    // representing a PHI into this block.
+    BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
+    Updater->UndefMap[&BB->BB] = Num;
+    return Num;
+  }
+
+  /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
+  /// SSAUpdater will populate it with information about incoming values. The
+  /// value number of this PHI is whatever the  machine value number problem
+  /// solution determined it to be. This includes non-phi values if SSAUpdater
+  /// tries to create a PHI where the incoming values are identical.
+  static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
+                                   LDVSSAUpdater *Updater) {
+    BlockValueNum PHIValNum = Updater->getValue(BB);
+    LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
+    Updater->PHIs[PHIValNum] = PHI;
+    return PHIValNum;
+  }
+
+  /// AddPHIOperand - Add the specified value as an operand of the PHI for
+  /// the specified predecessor block.
+  static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
+    PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
+  }
+
+  /// ValueIsPHI - Check if the instruction that defines the specified value
+  /// is a PHI instruction.
+  static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
+    auto PHIIt = Updater->PHIs.find(Val);
+    if (PHIIt == Updater->PHIs.end())
+      return nullptr;
+    return PHIIt->second;
+  }
+
+  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
+  /// operands, i.e., it was just added.
+  static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
+    LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
+    if (PHI && PHI->IncomingValues.size() == 0)
+      return PHI;
+    return nullptr;
+  }
+
+  /// GetPHIValue - For the specified PHI instruction, return the value
+  /// that it defines.
+  static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
+};
+
+} // end namespace llvm
+
+Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
+                                                      ValueIDNum **MLiveOuts,
+                                                      ValueIDNum **MLiveIns,
+                                                      MachineInstr &Here,
+                                                      uint64_t InstrNum) {
+  // Pick out records of DBG_PHI instructions that have been observed. If there
+  // are none, then we cannot compute a value number.
+  auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
+                                    DebugPHINumToValue.end(), InstrNum);
+  auto LowerIt = RangePair.first;
+  auto UpperIt = RangePair.second;
+
+  // No DBG_PHI means there can be no location.
+  if (LowerIt == UpperIt)
+    return None;
+
+  // If there's only one DBG_PHI, then that is our value number.
+  if (std::distance(LowerIt, UpperIt) == 1)
+    return LowerIt->ValueRead;
+
+  auto DBGPHIRange = make_range(LowerIt, UpperIt);
+
+  // Pick out the location (physreg, slot) where any PHIs must occur. It's
+  // technically possible for us to merge values in different registers in each
+  // block, but highly unlikely that LLVM will generate such code after register
+  // allocation.
+  LocIdx Loc = LowerIt->ReadLoc;
+
+  // We have several DBG_PHIs, and a use position (the Here inst). All each
+  // DBG_PHI does is identify a value at a program position. We can treat each
+  // DBG_PHI like it's a Def of a value, and the use position is a Use of a
+  // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
+  // determine which Def is used at the Use, and any PHIs that happen along
+  // the way.
+  // Adapted LLVM SSA Updater:
+  LDVSSAUpdater Updater(Loc, MLiveIns);
+  // Map of which Def or PHI is the current value in each block.
+  DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;
+  // Set of PHIs that we have created along the way.
+  SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
+
+  // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
+  // for the SSAUpdater.
+  for (const auto &DBG_PHI : DBGPHIRange) {
+    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
+    const ValueIDNum &Num = DBG_PHI.ValueRead;
+    AvailableValues.insert(std::make_pair(Block, Num.asU64()));
+  }
+
+  LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
+  const auto &AvailIt = AvailableValues.find(HereBlock);
+  if (AvailIt != AvailableValues.end()) {
+    // Actually, we already know what the value is -- the Use is in the same
+    // block as the Def.
+    return ValueIDNum::fromU64(AvailIt->second);
+  }
+
+  // Otherwise, we must use the SSA Updater. It will identify the value number
+  // that we are to use, and the PHIs that must happen along the way.
+  SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
+  BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
+  ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
+
+  // We have the number for a PHI, or possibly live-through value, to be used
+  // at this Use. There are a number of things we have to check about it though:
+  //  * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
+  //    Use was not completely dominated by DBG_PHIs and we should abort.
+  //  * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
+  //    we've left SSA form. Validate that the inputs to each PHI are the
+  //    expected values.
+  //  * Is a PHI we've created actually a merging of values, or are all the
+  //    predecessor values the same, leading to a non-PHI machine value number?
+  //    (SSAUpdater doesn't know that either). Remap validated PHIs into the
+  //    the ValidatedValues collection below to sort this out.
+  DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
+
+  // Define all the input DBG_PHI values in ValidatedValues.
+  for (const auto &DBG_PHI : DBGPHIRange) {
+    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
+    const ValueIDNum &Num = DBG_PHI.ValueRead;
+    ValidatedValues.insert(std::make_pair(Block, Num));
+  }
+
+  // Sort PHIs to validate into RPO-order.
+  SmallVector<LDVSSAPhi *, 8> SortedPHIs;
+  for (auto &PHI : CreatedPHIs)
+    SortedPHIs.push_back(PHI);
+
+  std::sort(
+      SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
+        return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
+      });
+
+  for (auto &PHI : SortedPHIs) {
+    ValueIDNum ThisBlockValueNum =
+        MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
+
+    // Are all these things actually defined?
+    for (auto &PHIIt : PHI->IncomingValues) {
+      // Any undef input means DBG_PHIs didn't dominate the use point.
+      if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
+        return None;
+
+      ValueIDNum ValueToCheck;
+      ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
+
+      auto VVal = ValidatedValues.find(PHIIt.first);
+      if (VVal == ValidatedValues.end()) {
+        // We cross a loop, and this is a backedge. LLVMs tail duplication
+        // happens so late that DBG_PHI instructions should not be able to
+        // migrate into loops -- meaning we can only be live-through this
+        // loop.
+        ValueToCheck = ThisBlockValueNum;
+      } else {
+        // Does the block have as a live-out, in the location we're examining,
+        // the value that we expect? If not, it's been moved or clobbered.
+        ValueToCheck = VVal->second;
+      }
+
+      if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
+        return None;
+    }
+
+    // Record this value as validated.
+    ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
+  }
+
+  // All the PHIs are valid: we can return what the SSAUpdater said our value
+  // number was.
+  return Result;
+}
diff --git a/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp b/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp
index 770c46ec8436..38e803d1abb5 100644
--- a/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp
+++ b/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp
@@ -14,6 +14,7 @@
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetMachine.h"
 
 /// \file LiveDebugValues.cpp
@@ -33,6 +34,12 @@
 
 using namespace llvm;
 
+static cl::opt<bool>
+    ForceInstrRefLDV("force-instr-ref-livedebugvalues", cl::Hidden,
+                     cl::desc("Use instruction-ref based LiveDebugValues with "
+                              "normal DBG_VALUE inputs"),
+                     cl::init(false));
+
 /// Generic LiveDebugValues pass. Calls through to VarLocBasedLDV or
 /// InstrRefBasedLDV to perform location propagation, via the LDVImpl
 /// base class.
@@ -87,6 +94,9 @@ bool LiveDebugValues::runOnMachineFunction(MachineFunction &MF) {
       InstrRefBased = TM.Options.ValueTrackingVariableLocations;
     }
 
+    // Allow the user to force selection of InstrRef LDV.
+    InstrRefBased |= ForceInstrRefLDV;
+
     if (InstrRefBased)
       TheImpl = llvm::makeInstrRefBasedLiveDebugValues();
     else
diff --git a/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h b/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h
index 6b05bc68d74d..9c910f180b9f 100644
--- a/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h
+++ b/llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.h
@@ -6,6 +6,9 @@
 //
 //===----------------------------------------------------------------------===//
 
+#ifndef LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_LIVEDEBUGVALUES_H
+#define LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_LIVEDEBUGVALUES_H
+
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 
@@ -30,3 +33,5 @@ public:
 extern LDVImpl *makeVarLocBasedLiveDebugValues();
 extern LDVImpl *makeInstrRefBasedLiveDebugValues();
 } // namespace llvm
+
+#endif // LLVM_LIB_CODEGEN_LIVEDEBUGVALUES_LIVEDEBUGVALUES_H
diff --git a/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
index e2daa46fe6b9..1e6d65c18953 100644
--- a/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
+++ b/llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp
@@ -76,20 +76,23 @@
 /// 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.
+/// VarLoc object that identifies the source variable, the set of
+/// machine-locations that currently describe it (a single location for
+/// DBG_VALUE or multiple for DBG_VALUE_LIST), and the DBG_VALUE inst that
+/// specifies the location. Each VarLoc is indexed in the (function-scope) \p
+/// VarLocMap, giving each VarLoc a set of unique indexes, each of which
+/// corresponds to one of the VarLoc's machine-locations and can be used to
+/// lookup the VarLoc in the VarLocMap. Rather than operate directly on machine
+/// locations, the dataflow analysis in this pass identifies locations by their
+/// indices 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
+/// function of each block. "flushPendingLocs" installs debug value instructions
+/// 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
@@ -175,17 +178,6 @@ static cl::opt<unsigned> InputDbgValueLimit(
         "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.
@@ -210,6 +202,13 @@ namespace {
 // this prevents fallback to std::set::count() operations.
 using DefinedRegsSet = SmallSet<Register, 32>;
 
+// The IDs in this set correspond to MachineLocs in VarLocs, as well as VarLocs
+// that represent Entry Values; every VarLoc in the set will also appear
+// exactly once at Location=0.
+// As a result, each VarLoc may appear more than once in this "set", but each
+// range corresponding to a Reg, SpillLoc, or EntryValue type will still be a
+// "true" set (i.e. each VarLoc may appear only once), and the range Location=0
+// is the set of all VarLocs.
 using VarLocSet = CoalescingBitVector<uint64_t>;
 
 /// A type-checked pair of {Register Location (or 0), Index}, used to index
@@ -229,11 +228,19 @@ struct LocIndex {
                            // 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.
+  /// The location that has an entry for every VarLoc in the map.
+  static constexpr u32_location_t kUniversalLocation = 0;
+
+  /// The first location that is reserved for VarLocs with locations of kind
+  /// RegisterKind.
+  static constexpr u32_location_t kFirstRegLocation = 1;
+
+  /// The first location greater than 0 that is not reserved for VarLocs with
+  /// locations of kind RegisterKind.
   static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30;
 
-  /// A special location reserved for VarLocs of kind SpillLocKind.
+  /// A special location reserved for VarLocs with locations of kind
+  /// SpillLocKind.
   static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation;
 
   /// A special location reserved for VarLocs of kind EntryValueBackupKind and
@@ -258,7 +265,7 @@ struct LocIndex {
 
   /// 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) {
+  static uint64_t rawIndexForReg(Register Reg) {
     return LocIndex(Reg, 0).getAsRawInteger();
   }
 
@@ -272,6 +279,13 @@ struct LocIndex {
   }
 };
 
+// Simple Set for storing all the VarLoc Indices at a Location bucket.
+using VarLocsInRange = SmallSet<LocIndex::u32_index_t, 32>;
+// Vector of all `LocIndex`s for a given VarLoc; the same Location should not
+// appear in any two of these, as each VarLoc appears at most once in any
+// Location bucket.
+using LocIndices = SmallVector<LocIndex, 2>;
+
 class VarLocBasedLDV : public LDVImpl {
 private:
   const TargetRegisterInfo *TRI;
@@ -312,51 +326,130 @@ private:
     /// is moved.
     const MachineInstr &MI;
 
-    enum VarLocKind {
+    enum class MachineLocKind {
       InvalidKind = 0,
       RegisterKind,
       SpillLocKind,
-      ImmediateKind,
+      ImmediateKind
+    };
+
+    enum class EntryValueLocKind {
+      NonEntryValueKind = 0,
       EntryValueKind,
       EntryValueBackupKind,
       EntryValueCopyBackupKind
-    } Kind = InvalidKind;
+    } EVKind;
 
     /// The value location. Stored separately to avoid repeatedly
     /// extracting it from MI.
-    union LocUnion {
+    union MachineLocValue {
       uint64_t RegNo;
       SpillLoc SpillLocation;
       uint64_t Hash;
       int64_t Immediate;
       const ConstantFP *FPImm;
       const ConstantInt *CImm;
-      LocUnion() : Hash(0) {}
-    } Loc;
+      MachineLocValue() : Hash(0) {}
+    };
+
+    /// A single machine location; its Kind is either a register, spill
+    /// location, or immediate value.
+    /// If the VarLoc is not a NonEntryValueKind, then it will use only a
+    /// single MachineLoc of RegisterKind.
+    struct MachineLoc {
+      MachineLocKind Kind;
+      MachineLocValue Value;
+      bool operator==(const MachineLoc &Other) const {
+        if (Kind != Other.Kind)
+          return false;
+        switch (Kind) {
+        case MachineLocKind::SpillLocKind:
+          return Value.SpillLocation == Other.Value.SpillLocation;
+        case MachineLocKind::RegisterKind:
+        case MachineLocKind::ImmediateKind:
+          return Value.Hash == Other.Value.Hash;
+        default:
+          llvm_unreachable("Invalid kind");
+        }
+      }
+      bool operator<(const MachineLoc &Other) const {
+        switch (Kind) {
+        case MachineLocKind::SpillLocKind:
+          return std::make_tuple(
+                     Kind, Value.SpillLocation.SpillBase,
+                     Value.SpillLocation.SpillOffset.getFixed(),
+                     Value.SpillLocation.SpillOffset.getScalable()) <
+                 std::make_tuple(
+                     Other.Kind, Other.Value.SpillLocation.SpillBase,
+                     Other.Value.SpillLocation.SpillOffset.getFixed(),
+                     Other.Value.SpillLocation.SpillOffset.getScalable());
+        case MachineLocKind::RegisterKind:
+        case MachineLocKind::ImmediateKind:
+          return std::tie(Kind, Value.Hash) <
+                 std::tie(Other.Kind, Other.Value.Hash);
+        default:
+          llvm_unreachable("Invalid kind");
+        }
+      }
+    };
+
+    /// The set of machine locations used to determine the variable's value, in
+    /// conjunction with Expr. Initially populated with MI's debug operands,
+    /// but may be transformed independently afterwards.
+    SmallVector<MachineLoc, 8> Locs;
+    /// Used to map the index of each location in Locs back to the index of its
+    /// original debug operand in MI. Used when multiple location operands are
+    /// coalesced and the original MI's operands need to be accessed while
+    /// emitting a debug value.
+    SmallVector<unsigned, 8> OrigLocMap;
 
     VarLoc(const MachineInstr &MI, LexicalScopes &LS)
         : Var(MI.getDebugVariable(), MI.getDebugExpression(),
               MI.getDebugLoc()->getInlinedAt()),
-          Expr(MI.getDebugExpression()), MI(MI) {
+          Expr(MI.getDebugExpression()), MI(MI),
+          EVKind(EntryValueLocKind::NonEntryValueKind) {
       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();
+      assert((MI.isDebugValueList() || MI.getNumOperands() == 4) &&
+             "malformed DBG_VALUE");
+      for (const MachineOperand &Op : MI.debug_operands()) {
+        MachineLoc ML = GetLocForOp(Op);
+        auto It = find(Locs, ML);
+        if (It == Locs.end()) {
+          Locs.push_back(ML);
+          OrigLocMap.push_back(MI.getDebugOperandIndex(&Op));
+        } else {
+          // ML duplicates an element in Locs; replace references to Op
+          // with references to the duplicating element.
+          unsigned OpIdx = Locs.size();
+          unsigned DuplicatingIdx = std::distance(Locs.begin(), It);
+          Expr = DIExpression::replaceArg(Expr, OpIdx, DuplicatingIdx);
+        }
       }
 
-      // We create the debug entry values from the factory functions rather than
-      // from this ctor.
-      assert(Kind != EntryValueKind && !isEntryBackupLoc());
+      // We create the debug entry values from the factory functions rather
+      // than from this ctor.
+      assert(EVKind != EntryValueLocKind::EntryValueKind &&
+             !isEntryBackupLoc());
+    }
+
+    static MachineLoc GetLocForOp(const MachineOperand &Op) {
+      MachineLocKind Kind;
+      MachineLocValue Loc;
+      if (Op.isReg()) {
+        Kind = MachineLocKind::RegisterKind;
+        Loc.RegNo = Op.getReg();
+      } else if (Op.isImm()) {
+        Kind = MachineLocKind::ImmediateKind;
+        Loc.Immediate = Op.getImm();
+      } else if (Op.isFPImm()) {
+        Kind = MachineLocKind::ImmediateKind;
+        Loc.FPImm = Op.getFPImm();
+      } else if (Op.isCImm()) {
+        Kind = MachineLocKind::ImmediateKind;
+        Loc.CImm = Op.getCImm();
+      } else
+        llvm_unreachable("Invalid Op kind for MachineLoc.");
+      return {Kind, Loc};
     }
 
     /// Take the variable and machine-location in DBG_VALUE MI, and build an
@@ -364,10 +457,11 @@ private:
     static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS,
                                  const DIExpression *EntryExpr, Register Reg) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueKind;
+      assert(VL.Locs.size() == 1 &&
+             VL.Locs[0].Kind == MachineLocKind::RegisterKind);
+      VL.EVKind = EntryValueLocKind::EntryValueKind;
       VL.Expr = EntryExpr;
-      VL.Loc.RegNo = Reg;
+      VL.Locs[0].Value.RegNo = Reg;
       return VL;
     }
 
@@ -379,8 +473,9 @@ private:
                                        LexicalScopes &LS,
                                        const DIExpression *EntryExpr) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueBackupKind;
+      assert(VL.Locs.size() == 1 &&
+             VL.Locs[0].Kind == MachineLocKind::RegisterKind);
+      VL.EVKind = EntryValueLocKind::EntryValueBackupKind;
       VL.Expr = EntryExpr;
       return VL;
     }
@@ -393,32 +488,40 @@ private:
                                            const DIExpression *EntryExpr,
                                            Register NewReg) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueCopyBackupKind;
+      assert(VL.Locs.size() == 1 &&
+             VL.Locs[0].Kind == MachineLocKind::RegisterKind);
+      VL.EVKind = EntryValueLocKind::EntryValueCopyBackupKind;
       VL.Expr = EntryExpr;
-      VL.Loc.RegNo = NewReg;
+      VL.Locs[0].Value.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,
+    static VarLoc CreateCopyLoc(const VarLoc &OldVL, const MachineLoc &OldML,
                                 Register NewReg) {
-      VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Loc.RegNo = NewReg;
-      return VL;
+      VarLoc VL = OldVL;
+      for (size_t I = 0, E = VL.Locs.size(); I < E; ++I)
+        if (VL.Locs[I] == OldML) {
+          VL.Locs[I].Kind = MachineLocKind::RegisterKind;
+          VL.Locs[I].Value.RegNo = NewReg;
+          return VL;
+        }
+      llvm_unreachable("Should have found OldML in new VarLoc.");
     }
 
-    /// Take the variable described by DBG_VALUE MI, and create a VarLoc
+    /// 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;
+    static VarLoc CreateSpillLoc(const VarLoc &OldVL, const MachineLoc &OldML,
+                                 unsigned SpillBase, StackOffset SpillOffset) {
+      VarLoc VL = OldVL;
+      for (int I = 0, E = VL.Locs.size(); I < E; ++I)
+        if (VL.Locs[I] == OldML) {
+          VL.Locs[I].Kind = MachineLocKind::SpillLocKind;
+          VL.Locs[I].Value.SpillLocation = {SpillBase, SpillOffset};
+          return VL;
+        }
+      llvm_unreachable("Should have found OldML in new VarLoc.");
     }
 
     /// Create a DBG_VALUE representing this VarLoc in the given function.
@@ -426,79 +529,143 @@ private:
     /// inlining information from the original DBG_VALUE instruction, which may
     /// have been several transfers ago.
     MachineInstr *BuildDbgValue(MachineFunction &MF) const {
+      assert(!isEntryBackupLoc() &&
+             "Tried to produce DBG_VALUE for backup VarLoc");
       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");
+      const DIExpression *DIExpr = Expr;
+      SmallVector<MachineOperand, 8> MOs;
+      for (unsigned I = 0, E = Locs.size(); I < E; ++I) {
+        MachineLocKind LocKind = Locs[I].Kind;
+        MachineLocValue Loc = Locs[I].Value;
+        const MachineOperand &Orig = MI.getDebugOperand(OrigLocMap[I]);
+        switch (LocKind) {
+        case MachineLocKind::RegisterKind:
+          // 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.
+          // Non-entry value register locations are like the source
+          // DBG_VALUE, but with the register number from this VarLoc.
+          MOs.push_back(MachineOperand::CreateReg(
+              EVKind == EntryValueLocKind::EntryValueKind ? Orig.getReg()
+                                                          : Register(Loc.RegNo),
+              false));
+          MOs.back().setIsDebug();
+          break;
+        case MachineLocKind::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.
+          unsigned Base = Loc.SpillLocation.SpillBase;
+          auto *TRI = MF.getSubtarget().getRegisterInfo();
+          if (MI.isNonListDebugValue()) {
+            DIExpr =
+                TRI->prependOffsetExpression(DIExpr, DIExpression::ApplyOffset,
+                                             Loc.SpillLocation.SpillOffset);
+            Indirect = true;
+          } else {
+            SmallVector<uint64_t, 4> Ops;
+            TRI->getOffsetOpcodes(Loc.SpillLocation.SpillOffset, Ops);
+            Ops.push_back(dwarf::DW_OP_deref);
+            DIExpr = DIExpression::appendOpsToArg(DIExpr, Ops, I);
+          }
+          MOs.push_back(MachineOperand::CreateReg(Base, false));
+          MOs.back().setIsDebug();
+          break;
+        }
+        case MachineLocKind::ImmediateKind: {
+          MOs.push_back(Orig);
+          break;
+        }
+        case MachineLocKind::InvalidKind:
+          llvm_unreachable("Tried to produce DBG_VALUE for invalid VarLoc");
+        }
       }
-      llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum");
+      return BuildMI(MF, DbgLoc, IID, Indirect, MOs, Var, DIExpr);
     }
 
     /// Is the Loc field a constant or constant object?
-    bool isConstant() const { return Kind == ImmediateKind; }
+    bool isConstant(MachineLocKind Kind) const {
+      return Kind == MachineLocKind::ImmediateKind;
+    }
 
     /// Check if the Loc field is an entry backup location.
     bool isEntryBackupLoc() const {
-      return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind;
+      return EVKind == EntryValueLocKind::EntryValueBackupKind ||
+             EVKind == EntryValueLocKind::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 register \p Reg holding the entry
+    /// value, return true.
+    bool isEntryValueBackupReg(Register Reg) const {
+      return EVKind == EntryValueLocKind::EntryValueBackupKind && usesReg(Reg);
     }
 
-    /// 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 register \p Reg holding a copy of the
+    /// entry value, return true.
+    bool isEntryValueCopyBackupReg(Register Reg) const {
+      return EVKind == EntryValueLocKind::EntryValueCopyBackupKind &&
+             usesReg(Reg);
     }
 
-    /// If this variable is described by a register, return it,
-    /// otherwise return 0.
-    unsigned isDescribedByReg() const {
-      if (Kind == RegisterKind)
-        return Loc.RegNo;
-      return 0;
+    /// If this variable is described in whole or part by \p Reg, return true.
+    bool usesReg(Register Reg) const {
+      MachineLoc RegML;
+      RegML.Kind = MachineLocKind::RegisterKind;
+      RegML.Value.RegNo = Reg;
+      return is_contained(Locs, RegML);
+    }
+
+    /// If this variable is described in whole or part by \p Reg, return true.
+    unsigned getRegIdx(Register Reg) const {
+      for (unsigned Idx = 0; Idx < Locs.size(); ++Idx)
+        if (Locs[Idx].Kind == MachineLocKind::RegisterKind &&
+            Locs[Idx].Value.RegNo == Reg)
+          return Idx;
+      llvm_unreachable("Could not find given Reg in Locs");
+    }
+
+    /// If this variable is described in whole or part by 1 or more registers,
+    /// add each of them to \p Regs and return true.
+    bool getDescribingRegs(SmallVectorImpl<uint32_t> &Regs) const {
+      bool AnyRegs = false;
+      for (auto Loc : Locs)
+        if (Loc.Kind == MachineLocKind::RegisterKind) {
+          Regs.push_back(Loc.Value.RegNo);
+          AnyRegs = true;
+        }
+      return AnyRegs;
+    }
+
+    bool containsSpillLocs() const {
+      return any_of(Locs, [](VarLoc::MachineLoc ML) {
+        return ML.Kind == VarLoc::MachineLocKind::SpillLocKind;
+      });
+    }
+
+    /// If this variable is described in whole or part by \p SpillLocation,
+    /// return true.
+    bool usesSpillLoc(SpillLoc SpillLocation) const {
+      MachineLoc SpillML;
+      SpillML.Kind = MachineLocKind::SpillLocKind;
+      SpillML.Value.SpillLocation = SpillLocation;
+      return is_contained(Locs, SpillML);
+    }
+
+    /// If this variable is described in whole or part by \p SpillLocation,
+    /// return the index .
+    unsigned getSpillLocIdx(SpillLoc SpillLocation) const {
+      for (unsigned Idx = 0; Idx < Locs.size(); ++Idx)
+        if (Locs[Idx].Kind == MachineLocKind::SpillLocKind &&
+            Locs[Idx].Value.SpillLocation == SpillLocation)
+          return Idx;
+      llvm_unreachable("Could not find given SpillLoc in Locs");
     }
 
     /// Determine whether the lexical scope of this value's debug location
@@ -511,24 +678,26 @@ private:
     // 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");
+      for (const MachineLoc &MLoc : Locs) {
+        if (Locs.begin() != &MLoc)
+          Out << ", ";
+        switch (MLoc.Kind) {
+        case MachineLocKind::RegisterKind:
+          Out << printReg(MLoc.Value.RegNo, TRI);
+          break;
+        case MachineLocKind::SpillLocKind:
+          Out << printReg(MLoc.Value.SpillLocation.SpillBase, TRI);
+          Out << "[" << MLoc.Value.SpillLocation.SpillOffset.getFixed() << " + "
+              << MLoc.Value.SpillLocation.SpillOffset.getScalable()
+              << "x vscale"
+              << "]";
+          break;
+        case MachineLocKind::ImmediateKind:
+          Out << MLoc.Value.Immediate;
+          break;
+        case MachineLocKind::InvalidKind:
+          llvm_unreachable("Invalid VarLoc in dump method");
+        }
       }
 
       Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
@@ -545,90 +714,76 @@ private:
 #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");
-      }
+      return std::tie(EVKind, Var, Expr, Locs) ==
+             std::tie(Other.EVKind, Other.Var, Other.Expr, Other.Locs);
     }
 
     /// 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");
-      }
+      return std::tie(Var, EVKind, Locs, Expr) <
+             std::tie(Other.Var, Other.EVKind, Other.Locs, Other.Expr);
     }
   };
 
+#ifndef NDEBUG
+  using VarVec = SmallVector<VarLoc, 32>;
+#endif
+
   /// VarLocMap is used for two things:
-  /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to
+  /// 1) Assigning LocIndices to a VarLoc. The LocIndices 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;
+    std::map<VarLoc, LocIndices> Var2Indices;
 
     /// 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) &&
+  public:
+    /// Retrieve LocIndices for \p VL.
+    LocIndices insert(const VarLoc &VL) {
+      LocIndices &Indices = Var2Indices[VL];
+      // If Indices is not empty, VL is already in the map.
+      if (!Indices.empty())
+        return Indices;
+      SmallVector<LocIndex::u32_location_t, 4> Locations;
+      // LocIndices are determined by EVKind and MLs; each Register has a
+      // unique location, while all SpillLocs use a single bucket, and any EV
+      // VarLocs use only the Backup bucket or none at all (except the
+      // compulsory entry at the universal location index). LocIndices will
+      // always have an index at the universal location index as the last index.
+      if (VL.EVKind == VarLoc::EntryValueLocKind::NonEntryValueKind) {
+        VL.getDescribingRegs(Locations);
+        assert(all_of(Locations,
+                      [](auto RegNo) {
+                        return 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;
+        if (VL.containsSpillLocs()) {
+          LocIndex::u32_location_t Loc = LocIndex::kSpillLocation;
+          Locations.push_back(Loc);
+        }
+      } else if (VL.EVKind != VarLoc::EntryValueLocKind::EntryValueKind) {
+        LocIndex::u32_location_t Loc = LocIndex::kEntryValueBackupLocation;
+        Locations.push_back(Loc);
       }
-    }
-
-  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) {
+      Locations.push_back(LocIndex::kUniversalLocation);
+      for (LocIndex::u32_location_t Location : Locations) {
         auto &Vars = Loc2Vars[Location];
+        Indices.push_back(
+            {Location, static_cast<LocIndex::u32_index_t>(Vars.size())});
         Vars.push_back(VL);
-        Index = Vars.size();
       }
-      return {Location, Index - 1};
+      return Indices;
+    }
+
+    LocIndices getAllIndices(const VarLoc &VL) const {
+      auto IndIt = Var2Indices.find(VL);
+      assert(IndIt != Var2Indices.end() && "VarLoc not tracked");
+      return IndIt->second;
     }
 
     /// Retrieve the unique VarLoc associated with \p ID.
@@ -660,6 +815,17 @@ private:
   using VarToFragments =
       DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
 
+  /// Collects all VarLocs from \p CollectFrom. Each unique VarLoc is added
+  /// to \p Collected once, in order of insertion into \p VarLocIDs.
+  static void collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
+                                const VarLocSet &CollectFrom,
+                                const VarLocMap &VarLocIDs);
+
+  /// Get the registers which are used by VarLocs of kind RegisterKind tracked
+  /// by \p CollectFrom.
+  void getUsedRegs(const VarLocSet &CollectFrom,
+                   SmallVectorImpl<Register> &UsedRegs) const;
+
   /// 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
@@ -670,39 +836,45 @@ private:
   /// we will erase/insert from the EntryValuesBackupVars map, otherwise
   /// we perform the operation on the Vars.
   class OpenRangesSet {
+    VarLocSet::Allocator &Alloc;
     VarLocSet VarLocs;
     // Map the DebugVariable to recent primary location ID.
-    SmallDenseMap<DebugVariable, LocIndex, 8> Vars;
+    SmallDenseMap<DebugVariable, LocIndices, 8> Vars;
     // Map the DebugVariable to recent backup location ID.
-    SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars;
+    SmallDenseMap<DebugVariable, LocIndices, 8> EntryValuesBackupVars;
     OverlapMap &OverlappingFragments;
 
   public:
     OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap)
-        : VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
+        : Alloc(Alloc), VarLocs(Alloc), OverlappingFragments(_OLapMap) {}
 
     const VarLocSet &getVarLocs() const { return VarLocs; }
 
+    // Fetches all VarLocs in \p VarLocIDs and inserts them into \p Collected.
+    // This method is needed to get every VarLoc once, as each VarLoc may have
+    // multiple indices in a VarLocMap (corresponding to each applicable
+    // location), but all VarLocs appear exactly once at the universal location
+    // index.
+    void getUniqueVarLocs(SmallVectorImpl<VarLoc> &Collected,
+                          const VarLocMap &VarLocIDs) const {
+      collectAllVarLocs(Collected, VarLocs, VarLocIDs);
+    }
+
     /// 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);
+    /// Terminate all open ranges listed as indices in \c KillSet with
+    /// \c Location by removing them from the set.
+    void erase(const VarLocsInRange &KillSet, const VarLocMap &VarLocIDs,
+               LocIndex::u32_location_t Location);
 
     /// Insert a new range into the set.
-    void insert(LocIndex VarLocID, const VarLoc &VL);
+    void insert(LocIndices VarLocIDs, 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);
-      }
-    }
+    void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map);
 
-    llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var);
+    llvm::Optional<LocIndices> getEntryValueBackup(DebugVariable Var);
 
     /// Empty the set.
     void clear() {
@@ -725,18 +897,18 @@ private:
                                                        getVarLocs().end());
     }
 
-    /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg.
+    /// Get all set IDs for VarLocs with MLs 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.
+    /// Get all set IDs for VarLocs with MLs of kind SpillLocKind.
     auto getSpillVarLocs() const {
       return LocIndex::indexRangeForLocation(getVarLocs(),
                                              LocIndex::kSpillLocation);
     }
 
-    /// Get all set IDs for VarLocs of kind EntryValueBackupKind or
+    /// Get all set IDs for VarLocs of EVKind EntryValueBackupKind or
     /// EntryValueCopyBackupKind.
     auto getEntryValueBackupVarLocs() const {
       return LocIndex::indexRangeForLocation(
@@ -744,16 +916,14 @@ private:
     }
   };
 
-  /// 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;
+  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs with MLs of kind
+  /// RegisterKind which are located in any reg in \p Regs. The IDs for each
+  /// VarLoc correspond to entries in the universal location bucket, which every
+  /// VarLoc has exactly 1 entry for. Insert collected IDs into \p Collected.
+  static void collectIDsForRegs(VarLocsInRange &Collected,
+                                const DefinedRegsSet &Regs,
+                                const VarLocSet &CollectFrom,
+                                const VarLocMap &VarLocIDs);
 
   VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) {
     std::unique_ptr<VarLocSet> &VLS = Locs[MBB];
@@ -800,6 +970,7 @@ private:
   void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                TransferMap &Transfers, VarLocMap &VarLocIDs,
                                LocIndex OldVarID, TransferKind Kind,
+                               const VarLoc::MachineLoc &OldLoc,
                                Register NewReg = Register());
 
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
@@ -810,7 +981,7 @@ private:
                         VarLocMap &VarLocIDs, const VarLoc &EntryVL);
   void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
                        VarLocMap &VarLocIDs, TransferMap &Transfers,
-                       VarLocSet &KillSet);
+                       VarLocsInRange &KillSet);
   void recordEntryValue(const MachineInstr &MI,
                         const DefinedRegsSet &DefinedRegs,
                         OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
@@ -871,8 +1042,9 @@ void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
     auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     auto It = EraseFrom->find(VarToErase);
     if (It != EraseFrom->end()) {
-      LocIndex ID = It->second;
-      VarLocs.reset(ID.getAsRawInteger());
+      LocIndices IDs = It->second;
+      for (LocIndex ID : IDs)
+        VarLocs.reset(ID.getAsRawInteger());
       EraseFrom->erase(It);
     }
   };
@@ -899,26 +1071,46 @@ void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
   }
 }
 
-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::erase(const VarLocsInRange &KillSet,
+                                          const VarLocMap &VarLocIDs,
+                                          LocIndex::u32_location_t Location) {
+  VarLocSet RemoveSet(Alloc);
+  for (LocIndex::u32_index_t ID : KillSet) {
+    const VarLoc &VL = VarLocIDs[LocIndex(Location, ID)];
+    auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
+    EraseFrom->erase(VL.Var);
+    LocIndices VLI = VarLocIDs.getAllIndices(VL);
+    for (LocIndex ID : VLI)
+      RemoveSet.set(ID.getAsRawInteger());
+  }
+  VarLocs.intersectWithComplement(RemoveSet);
+}
+
+void VarLocBasedLDV::OpenRangesSet::insertFromLocSet(const VarLocSet &ToLoad,
+                                                     const VarLocMap &Map) {
+  VarLocsInRange UniqueVarLocIDs;
+  DefinedRegsSet Regs;
+  Regs.insert(LocIndex::kUniversalLocation);
+  collectIDsForRegs(UniqueVarLocIDs, Regs, ToLoad, Map);
+  for (uint64_t ID : UniqueVarLocIDs) {
+    LocIndex Idx = LocIndex::fromRawInteger(ID);
+    const VarLoc &VarL = Map[Idx];
+    const LocIndices Indices = Map.getAllIndices(VarL);
+    insert(Indices, VarL);
   }
 }
 
-void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID,
-                                            const VarLoc &VL) {
+void VarLocBasedLDV::OpenRangesSet::insert(LocIndices VarLocIDs,
+                                           const VarLoc &VL) {
   auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-  VarLocs.set(VarLocID.getAsRawInteger());
-  InsertInto->insert({VL.Var, VarLocID});
+  for (LocIndex ID : VarLocIDs)
+    VarLocs.set(ID.getAsRawInteger());
+  InsertInto->insert({VL.Var, VarLocIDs});
 }
 
 /// Return the Loc ID of an entry value backup location, if it exists for the
 /// variable.
-llvm::Optional<LocIndex>
+llvm::Optional<LocIndices>
 VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
   auto It = EntryValuesBackupVars.find(Var);
   if (It != EntryValuesBackupVars.end())
@@ -927,26 +1119,35 @@ VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) {
   return llvm::None;
 }
 
-void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
-                                        const DefinedRegsSet &Regs,
-                                        const VarLocSet &CollectFrom) const {
+void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected,
+                                       const DefinedRegsSet &Regs,
+                                       const VarLocSet &CollectFrom,
+                                       const VarLocMap &VarLocIDs) {
   assert(!Regs.empty() && "Nothing to collect");
-  SmallVector<uint32_t, 32> SortedRegs;
-  for (Register Reg : Regs)
-    SortedRegs.push_back(Reg);
+  SmallVector<Register, 32> SortedRegs;
+  append_range(SortedRegs, Regs);
   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.
+  for (Register Reg : SortedRegs) {
+    // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains
+    // all possible VarLoc IDs for VarLocs with MLs 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);
+    for (; It != End && *It < FirstInvalidIndex; ++It) {
+      LocIndex ItIdx = LocIndex::fromRawInteger(*It);
+      const VarLoc &VL = VarLocIDs[ItIdx];
+      LocIndices LI = VarLocIDs.getAllIndices(VL);
+      // For now, the back index is always the universal location index.
+      assert(LI.back().Location == LocIndex::kUniversalLocation &&
+             "Unexpected order of LocIndices for VarLoc; was it inserted into "
+             "the VarLocMap correctly?");
+      Collected.insert(LI.back().Index);
+    }
 
     if (It == End)
       return;
@@ -954,10 +1155,11 @@ void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
 }
 
 void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom,
-                                  SmallVectorImpl<uint32_t> &UsedRegs) const {
+                                 SmallVectorImpl<Register> &UsedRegs) const {
   // All register-based VarLocs are assigned indices greater than or equal to
   // FirstRegIndex.
-  uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1);
+  uint64_t FirstRegIndex =
+      LocIndex::rawIndexForReg(LocIndex::kFirstRegLocation);
   uint64_t FirstInvalidIndex =
       LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation);
   for (auto It = CollectFrom.find(FirstRegIndex),
@@ -995,9 +1197,10 @@ void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
     const VarLocSet &L = getVarLocsInMBB(&BB, V);
     if (L.empty())
       continue;
+    SmallVector<VarLoc, 32> VarLocs;
+    collectAllVarLocs(VarLocs, L, VarLocIDs);
     Out << "MBB: " << BB.getNumber() << ":\n";
-    for (uint64_t VLL : L) {
-      const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)];
+    for (const VarLoc &VL : VarLocs) {
       Out << " Var: " << VL.Var.getVariable()->getName();
       Out << " MI: ";
       VL.dump(TRI, Out);
@@ -1044,11 +1247,11 @@ bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
   // 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.)
@@ -1060,13 +1263,11 @@ bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
     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 &&
+      if (VL.isEntryValueCopyBackupReg(Reg) &&
+          // Entry Values should not be variadic.
           VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
         return false;
     }
@@ -1095,7 +1296,7 @@ void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
   // 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];
+    const VarLoc &EntryVL = VarLocIDs[EntryValBackupID->back()];
     if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) {
       LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: ";
                  MI.print(dbgs(), /*IsStandalone*/ false,
@@ -1105,59 +1306,79 @@ void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI,
     }
   }
 
-  if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() ||
-      MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) {
+  if (all_of(MI.debug_operands(), [](const MachineOperand &MO) {
+        return (MO.isReg() && MO.getReg()) || MO.isImm() || MO.isFPImm() ||
+               MO.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);
+    LocIndices IDs = VarLocIDs.insert(VL);
     // Add the VarLoc to OpenRanges from this DBG_VALUE.
-    OpenRanges.insert(ID, VL);
-  } else if (MI.hasOneMemOperand()) {
+    OpenRanges.insert(IDs, VL);
+  } else if (MI.memoperands().size() > 0) {
     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 &&
+    assert(MI.isUndefDebugValue() &&
            "Unexpected non-undef DBG_VALUE encountered");
     VarLoc VL(MI, LS);
     OpenRanges.erase(VL);
   }
 }
 
+// This should be removed later, doesn't fit the new design.
+void VarLocBasedLDV::collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected,
+                                       const VarLocSet &CollectFrom,
+                                       const VarLocMap &VarLocIDs) {
+  // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all
+  // possible VarLoc IDs for VarLocs with MLs of kind RegisterKind which live
+  // in Reg.
+  uint64_t FirstIndex = LocIndex::rawIndexForReg(LocIndex::kUniversalLocation);
+  uint64_t FirstInvalidIndex =
+      LocIndex::rawIndexForReg(LocIndex::kUniversalLocation + 1);
+  // Iterate through that half-open interval and collect all the set IDs.
+  for (auto It = CollectFrom.find(FirstIndex), End = CollectFrom.end();
+       It != End && *It < FirstInvalidIndex; ++It) {
+    LocIndex RegIdx = LocIndex::fromRawInteger(*It);
+    Collected.push_back(VarLocIDs[RegIdx]);
+  }
+}
+
 /// Turn the entry value backup locations into primary locations.
 void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
-                                      OpenRangesSet &OpenRanges,
-                                      VarLocMap &VarLocIDs,
-                                      TransferMap &Transfers,
-                                      VarLocSet &KillSet) {
+                                     OpenRangesSet &OpenRanges,
+                                     VarLocMap &VarLocIDs,
+                                     TransferMap &Transfers,
+                                     VarLocsInRange &KillSet) {
   // Do not insert entry value locations after a terminator.
   if (MI.isTerminator())
     return;
 
-  for (uint64_t ID : KillSet) {
-    LocIndex Idx = LocIndex::fromRawInteger(ID);
+  for (uint32_t ID : KillSet) {
+    // The KillSet IDs are indices for the universal location bucket.
+    LocIndex Idx = LocIndex(LocIndex::kUniversalLocation, ID);
     const VarLoc &VL = VarLocIDs[Idx];
     if (!VL.Var.getVariable()->isParameter())
       continue;
 
     auto DebugVar = VL.Var;
-    Optional<LocIndex> EntryValBackupID =
+    Optional<LocIndices> EntryValBackupIDs =
         OpenRanges.getEntryValueBackup(DebugVar);
 
     // If the parameter has the entry value backup, it means we should
     // be able to use its entry value.
-    if (!EntryValBackupID)
+    if (!EntryValBackupIDs)
       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);
+    const VarLoc &EntryVL = VarLocIDs[EntryValBackupIDs->back()];
+    VarLoc EntryLoc = VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr,
+                                             EntryVL.Locs[0].Value.RegNo);
+    LocIndices EntryValueIDs = VarLocIDs.insert(EntryLoc);
+    Transfers.push_back({&MI, EntryValueIDs.back()});
+    OpenRanges.insert(EntryValueIDs, EntryLoc);
   }
 }
 
@@ -1169,20 +1390,20 @@ void VarLocBasedLDV::emitEntryValues(MachineInstr &MI,
 void VarLocBasedLDV::insertTransferDebugPair(
     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
     VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
-    Register NewReg) {
-  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
+    const VarLoc::MachineLoc &OldLoc, Register NewReg) {
+  const VarLoc &OldVarLoc = VarLocIDs[OldVarID];
 
   auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) {
-    LocIndex LocId = VarLocIDs.insert(VL);
+    LocIndices LocIds = 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);
+    OpenRanges.insert(LocIds, VL);
     assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator");
-    TransferDebugPair MIP = {&MI, LocId};
+    TransferDebugPair MIP = {&MI, LocIds.back()};
     Transfers.push_back(MIP);
   };
 
@@ -1194,7 +1415,7 @@ void VarLocBasedLDV::insertTransferDebugPair(
            "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);
+    VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for register copy:";
@@ -1206,8 +1427,8 @@ void VarLocBasedLDV::insertTransferDebugPair(
     // 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);
+    VarLoc VL = VarLoc::CreateSpillLoc(
+        OldVarLoc, OldLoc, SpillLocation.SpillBase, SpillLocation.SpillOffset);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for spill:";
@@ -1220,7 +1441,7 @@ void VarLocBasedLDV::insertTransferDebugPair(
            "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);
+    VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for restore:";
@@ -1267,9 +1488,9 @@ void VarLocBasedLDV::transferRegisterDef(
   // 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;
+    SmallVector<Register, 32> UsedRegs;
     getUsedRegs(OpenRanges.getVarLocs(), UsedRegs);
-    for (uint32_t Reg : UsedRegs) {
+    for (Register 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.
@@ -1290,9 +1511,9 @@ void VarLocBasedLDV::transferRegisterDef(
   if (DeadRegs.empty())
     return;
 
-  VarLocSet KillSet(Alloc);
-  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
-  OpenRanges.erase(KillSet, VarLocIDs);
+  VarLocsInRange KillSet;
+  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs(), VarLocIDs);
+  OpenRanges.erase(KillSet, VarLocIDs, LocIndex::kUniversalLocation);
 
   if (TPC) {
     auto &TM = TPC->getTM<TargetMachine>();
@@ -1390,14 +1611,14 @@ void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
   // 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);
+  VarLocsInRange KillSet;
   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) {
+      assert(VL.containsSpillLocs() && "Broken VarLocSet?");
+      if (VL.usesSpillLoc(*Loc)) {
         // This location is overwritten by the current instruction -- terminate
         // the open range, and insert an explicit DBG_VALUE $noreg.
         //
@@ -1408,13 +1629,15 @@ void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
         //
         // 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});
+        KillSet.insert(ID);
+        unsigned SpillLocIdx = VL.getSpillLocIdx(*Loc);
+        VarLoc::MachineLoc OldLoc = VL.Locs[SpillLocIdx];
+        VarLoc UndefVL = VarLoc::CreateCopyLoc(VL, OldLoc, 0);
+        LocIndices UndefLocIDs = VarLocIDs.insert(UndefVL);
+        Transfers.push_back({&MI, UndefLocIDs.back()});
       }
     }
-    OpenRanges.erase(KillSet, VarLocIDs);
+    OpenRanges.erase(KillSet, VarLocIDs, LocIndex::kSpillLocation);
   }
 
   // Try to recognise spill and restore instructions that may create a new
@@ -1441,21 +1664,25 @@ void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
   for (uint64_t ID : TransferCandidates) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
     const VarLoc &VL = VarLocIDs[Idx];
+    unsigned LocIdx;
     if (TKind == TransferKind::TransferSpill) {
-      assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?");
+      assert(VL.usesReg(Reg) && "Broken VarLocSet?");
       LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '('
                         << VL.Var.getVariable()->getName() << ")\n");
+      LocIdx = VL.getRegIdx(Reg);
     } else {
-      assert(TKind == TransferKind::TransferRestore &&
-             VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?");
-      if (VL.Loc.SpillLocation != *Loc)
+      assert(TKind == TransferKind::TransferRestore && VL.containsSpillLocs() &&
+             "Broken VarLocSet?");
+      if (!VL.usesSpillLoc(*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");
+      LocIdx = VL.getSpillLocIdx(*Loc);
     }
+    VarLoc::MachineLoc MLoc = VL.Locs[LocIdx];
     insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind,
-                            Reg);
+                            MLoc, Reg);
     // FIXME: A comment should explain why it's correct to return early here,
     // if that is in fact correct.
     return;
@@ -1504,17 +1731,16 @@ void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
     for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       const VarLoc &VL = VarLocIDs[Idx];
-      if (VL.getEntryValueBackupReg() == SrcReg) {
+      if (VL.isEntryValueBackupReg(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);
+        LocIndices EntryValCopyLocIDs = VarLocIDs.insert(EntryValLocCopyBackup);
+        OpenRanges.insert(EntryValCopyLocIDs, EntryValLocCopyBackup);
         break;
       }
     }
@@ -1525,9 +1751,12 @@ void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
 
   for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
-    assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?");
+    assert(VarLocIDs[Idx].usesReg(SrcReg) && "Broken VarLocSet?");
+    VarLoc::MachineLocValue Loc;
+    Loc.RegNo = SrcReg;
+    VarLoc::MachineLoc MLoc{VarLoc::MachineLocKind::RegisterKind, Loc};
     insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx,
-                            TransferKind::TransferCopy, DestReg);
+                            TransferKind::TransferCopy, MLoc, DestReg);
     // FIXME: A comment should explain why it's correct to return early here,
     // if that is in fact correct.
     return;
@@ -1540,12 +1769,14 @@ bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
                                          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);
+  LLVM_DEBUG({
+    VarVec VarLocs;
+    OpenRanges.getUniqueVarLocs(VarLocs, VarLocIDs);
+    for (VarLoc &VL : VarLocs) {
+      // Copy OpenRanges to OutLocs, if not already present.
+      dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ":  ";
+      VL.dump(TRI);
+    }
   });
   VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
   Changed = VLS != OpenRanges.getVarLocs();
@@ -1668,12 +1899,11 @@ bool VarLocBasedLDV::join(
 
     LLVM_DEBUG({
       if (!InLocsT.empty()) {
-        for (uint64_t ID : InLocsT)
+        VarVec VarLocs;
+        collectAllVarLocs(VarLocs, InLocsT, VarLocIDs);
+        for (const VarLoc &VL : VarLocs)
           dbgs() << "  gathered candidate incoming var: "
-                 << VarLocIDs[LocIndex::fromRawInteger(ID)]
-                        .Var.getVariable()
-                        ->getName()
-                 << "\n";
+                 << VL.Var.getVariable()->getName() << "\n";
       }
     });
 
@@ -1722,10 +1952,12 @@ void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
     auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
     VarLocSet &Pending = *Iter.second.get();
 
-    for (uint64_t ID : Pending) {
+    SmallVector<VarLoc, 32> VarLocs;
+    collectAllVarLocs(VarLocs, Pending, VarLocIDs);
+
+    for (VarLoc DiffIt : VarLocs) {
       // 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());
@@ -1810,8 +2042,8 @@ void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
   DIExpression *NewExpr =
       DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
   VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
-  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
-  OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
+  LocIndices EntryValLocIDs = VarLocIDs.insert(EntryValLocAsBackup);
+  OpenRanges.insert(EntryValLocIDs, EntryValLocAsBackup);
 }
 
 /// Calculate the liveness information for the given machine function and
@@ -1896,9 +2128,9 @@ bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
 
   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;
+  for (MachineBasicBlock *MBB : RPOT) {
+    OrderToBB[RPONumber] = MBB;
+    BBToOrder[MBB] = RPONumber;
     Worklist.push(RPONumber);
     ++RPONumber;
   }