[DebugInfo] Process DBG_VALUE_LIST in LiveDebugValues

[StephenTozer]

Summary

Continuing the work discussed in the RFC[0], this patch implements DBG_VALUE_LIST handling in the LiveDebugValues pass.

This is without question the largest change to a single pass in terms of both line count and complexity, largely due to the complexity of the pass and the extent to which it is currently coupled with single machine location variables. Although the line count for this change is high, the logical changes to the patch derive largely from a few basic changes.

First and foremost, the VarLocSet+VarLocMap model has changed:

Previously, VarLocMap acted as a simple bidirectional map between machine locations and VarLocs. Each VarLoc would be assigned a single unique LocIndex by VarLocMap, which could be used to look up that VarLoc in the map. This coupled with VarLocSet, which was a set of LocIndexes optimized for range lookups (using the CoalescingBitVector class). Due to how LocIndex was structured, this allowed VarLocSet to be used to look up every LocIndex associated with a given machine location - either a specific register, or one of several shared buckets for spill locations, entry values, entry value backups, or constants (undef or immediate). VarLocSet also supports all other basic set operations, and was used to track all live VarLocs at a given point.

In order to support DBG_VALUE_LIST, a few changes have been made to this model. VarLocMap no longer provides a single unique LocIndex for a VarLoc, but a set of them corresponding to each machine location used; a single VarLoc will still never have multiple indices in a single bucket, and every LocIndex of a VarLoc must be inserted into any associated VarLocSet. Any one of these indices can be used by itself to look up the VarLoc they are assigned to. Within this index set, every VarLoc has an index in the "constant" bucket; the purpose of this is to provide a means of looking up every current VarLoc in VarLocSet.
VarLocSet is no longer strictly a "set of VarLocs", but a set of LocIndexes (this probably warrants a name change), as each VarLoc may have multiple LocIndexes inserted into the VarLocSet. Functionally, this means that VarLocSet is used slightly differently; the methods for looking up every VarLoc that uses a given bucket (a specific register, spill location, entry value, or entry value backup) is unchanged. When looking up every active VarLoc, instead of fetching the entire set we simply fetch every LocIndex with Location=0 (the "constant" bucket), as every VarLoc appears exactly once in there. While these changes make up a significant bulk of the line count, there are few resulting changes outside of the functions that directly operate on VarLocSets - the signatures of these functions are mostly unchanged.

The other major change is the VarLoc class itself. This mostly consists of cleaning up its interface to work with multiple machine locations, as well as separating the old "Kind" enum into MachineLocKind (for machine locations) and EntryValueKind (describing the VarLoc as a whole). The majority of these changes are simply using more specific functions to do things that didn't need them before, such as replacing if (VarLoc.getSpillLoc()) with if (VarLoc.containsSpillLocs()), or if (VarLoc.getReg() == RegNo) with if (VarLoc.usesReg(RegNo).

[0] http://lists.llvm.org/pipermail/llvm-dev/2020-February/139376.html

[djtodoro]

Thanks for doing this!

Can you please update the top-level comment of the file, so we have the whole picture of the change?

llvm/lib/CodeGen/LiveDebugValues.cpp

263 ↗

(On Diff #278233)

In stands for Indices here? I'd change that in order not to mix up terms with the In/Out...

267 ↗

(On Diff #278233)

This should have more intuitive name, I guess...

308 ↗

(On Diff #278233)

I don't understand why we need new Kind for the EntryValue here.

322 ↗

(On Diff #278233)

why typedef here?

331 ↗

(On Diff #278233)

Please add a comment here by describing the purpose of the structure.

1579 ↗

(On Diff #278233)

This should be deleted?

1719 ↗

(On Diff #278233)

We have declared this multiple times, therefore, can we declare it just once out of the methods?

llvm/test/DebugInfo/MIR/X86/dvl-livedebugvalues-clobber.mir

74

We don't need all the MF attributes. Most of them could be deleted (applies to all the tests).

[StephenTozer]

llvm/lib/CodeGen/LiveDebugValues.cpp

263 ↗

(On Diff #278233)

In this case, "In" just means "In", as in the VarLocs that are in a given range. I think there could be a better name for this as well as some of the other classes here; it might even be better to make them into full classes rather than just named sets/vectors. I'm not sure whether doing so would make it easier to understand what's going on, or just make it harder to compare to the previous behaviour.

308 ↗

(On Diff #278233)

After completing the overall work I found the separation isn't strictly necessary, as entry values currently only ever consist of a single register. The logical distinction is that a complete VarLoc is or is not an EntryValue; a machine location doesn't have EntryValue-ness. Still: at the moment we lose no information by combining them, although if at any point we expand what is permissible for an entry value they should be separated.

322 ↗

(On Diff #278233)

This union type is useful to have at the scope of VarLoc, since several VarLoc methods use variables with these values. The best alternative I think would be to move it into MachineLoc; regardless, having it as a typedef instead of an anonymous union is convenient in the functions below where it is used.

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues.cpp

263 ↗

(On Diff #278233)

OK. I thinks In/Out are well known already here, so I think we don't have to worry about that. We might want to update the comment above to remove any ambiguity.

308 ↗

(On Diff #278233)

That makes sense then. There are targets where the entry value would be in multiple regs, but I am not sure we can face it with the current support. I am OK with the separation.

[StephenTozer]

Remove unused data from tests, add/modify comments, move VarVec declaration up, fix error in duplicated-op-removal.

[djtodoro]

@StephenTozer Thanks for addressing the comments! Can you please share with us if you have any measurements with the respect to build time increase (e.g. on clang build itself) with this patch? I think that this patch is the only one from the stack that could give us potential performance issues.

[StephenTozer]

• Fixed a few minor errors, including a linux compile error
• Rebased onto latest master, moving changes into VarLocBasedImpl.cpp.

[StephenTozer]

Rebased onto recent master, no changes.

[StephenTozer]

In D83890#2177846, @djtodoro wrote:

@StephenTozer Thanks for addressing the comments! Can you please share with us if you have any measurements with the respect to build time increase (e.g. on clang build itself) with this patch? I think that this patch is the only one from the stack that could give us potential performance issues.

I mentioned this in a comment on another review, but just to make sure the answer is available here: there doesn't appear to be a large compile time increase as a result of this change. I haven't yet measured LiveDebugValues specifically, but for the samples in the CTMark projects in the LLVM test suite the average compile time increase currently appears to be 0.5% at -O2 -g. At this point it's hard to say how much of this is down to LiveDebugValues, but it is probably the most significant pass in that regard.

[StephenTozer]

Rebased onto recent master.

[StephenTozer]

Ping.

[jmorse]

Paging @vsk -- it was a while ago, but do you still have the bitcode from D7406 handy, and would you have spare cycles to test it against this (combined patch in D94631)?

Taking a high level view: because variadic variable locations can be part of more than one machine location, here @StephenTozer is adding a VarLoc to each machine location the variable location uses, and keeping an index of all VarLocs in LocIndex=0, so that a "cannonical" VarLoc can be looked up.

I'm not concerned about the average performance, as the cost of extra VarLocs will be proportionate to the number of variadic variable locations, which will be small (at least initially). However, keeping everything in a single index risks defeating the CoalescingBitVector improvements by fragmenting the collection of set bits more than it was before, increasing pointer chasing. Hence it'd be good to test against the original motivating example, if possible.

[vsk]

In D83890#2515600, @jmorse wrote:

Paging @vsk -- it was a while ago, but do you still have the bitcode from D7406 handy, and would you have spare cycles to test it against this (combined patch in D94631)?

Taking a high level view: because variadic variable locations can be part of more than one machine location, here @StephenTozer is adding a VarLoc to each machine location the variable location uses, and keeping an index of all VarLocs in LocIndex=0, so that a "cannonical" VarLoc can be looked up.

I'm not concerned about the average performance, as the cost of extra VarLocs will be proportionate to the number of variadic variable locations, which will be small (at least initially). However, keeping everything in a single index risks defeating the CoalescingBitVector improvements by fragmenting the collection of set bits more than it was before, increasing pointer chasing. Hence it'd be good to test against the original motivating example, if possible.

I do still have the bitcode handy, but wasn't able to apply D94631 cleanly to my checkout. Happy to report results back, just let me know which hash of llvm-project to apply D94631 onto.

Edit: FTR here's what I see with top-of-tree llc --

 % ./bin/llc -O3 glyphbench-metarenamed.bc -o /dev/null -filetype=obj -time-passes
===-------------------------------------------------------------------------===
                      ... Pass execution timing report ...
===-------------------------------------------------------------------------===
  Total Execution Time: 412.5068 seconds (484.1841 wall clock)

   ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
  202.0015 ( 49.3%)   0.2855 ( 10.7%)  202.2870 ( 49.0%)  203.3913 ( 42.0%)  Machine Common Subexpression Elimination
  46.3881 ( 11.3%)   0.3938 ( 14.7%)  46.7819 ( 11.3%)  87.3571 ( 18.0%)  X86 DAG->DAG Instruction Selection
  46.3634 ( 11.3%)   0.1293 (  4.8%)  46.4927 ( 11.3%)  75.9819 ( 15.7%)  Merge disjoint stack slots
  72.4355 ( 17.7%)   0.3826 ( 14.3%)  72.8180 ( 17.7%)  73.1227 ( 15.1%)  Greedy Register Allocator
  25.1784 (  6.1%)   0.0254 (  1.0%)  25.2038 (  6.1%)  25.3227 (  5.2%)  Machine Instruction Scheduler
   6.6854 (  1.6%)   1.2851 ( 48.0%)   7.9705 (  1.9%)   8.0105 (  1.7%)  X86 Assembly Printer
   5.2662 (  1.3%)   0.0256 (  1.0%)   5.2918 (  1.3%)   5.3122 (  1.1%)  Debug Variable Analysis
   1.1159 (  0.3%)   0.0010 (  0.0%)   1.1169 (  0.3%)   1.1253 (  0.2%)  X86 Execution Dependency Fix
   0.7744 (  0.2%)   0.0106 (  0.4%)   0.7849 (  0.2%)   0.7908 (  0.2%)  Live DEBUG_VALUE analysis
   0.3617 (  0.1%)   0.0016 (  0.1%)   0.3633 (  0.1%)   0.3672 (  0.1%)  Virtual Register Rewriter
   0.2488 (  0.1%)   0.0050 (  0.2%)   0.2538 (  0.1%)   0.2539 (  0.1%)  Module Verifier #2
   0.2426 (  0.1%)   0.0083 (  0.3%)   0.2508 (  0.1%)   0.2508 (  0.1%)  Module Verifier
   0.2184 (  0.1%)   0.0081 (  0.3%)   0.2265 (  0.1%)   0.2265 (  0.0%)  Live Variable Analysis
[snip]

[StephenTozer]

In D83890#2525566, @vsk wrote:

I do still have the bitcode handy, but wasn't able to apply D94631 cleanly to my checkout. Happy to report results back, just let me know which hash of llvm-project to apply D94631 onto.

The current version of the patch can be applied to 993c488ed, although I'll be updating it tomorrow onto the latest master, plus some bug fixes (also, D95463 is necessary for some source files to prevent an immense excess of debug values). I'd be very interested to see the results with just what we have now, however.

Finally, assuming that the bitcode you have is already optimized, we won't see the full impact of this change with it: the major feature being added is the support for DBG_VALUEs that reference more than one machine location (DBG_VALUE_LISTs), which makes the LiveDebugValues analysis more complicated. These DBG_VALUE_LISTs can currently only be produced when salvaging debug values in opt passes; with pre-optimized bitcode, the resulting MIR won't have any DBG_VALUE_LISTs and so won't give an indication of how well we handle the new instruction. However, it would still be very valuable just to know what impact this change has on simple DBG_VALUEs - preventing a regression here is vital.

[StephenTozer]

@vsk Just pushed an update onto aforementioned patch bringing it up to 30b8f553 and fixing some small bugs; it does not conflict with the latest master (5d3dca24 as of this comment), but I've not finished building and testing yet, so the former revision should be fine.

[jmorse]

I'm going to tentatively "LGTM" this -- I've read through it a couple of times and think it works, it'd be great if someone else could chip in. There are various things that aren't ideal, but that stems from having to track things across multiple entries. It's encouraging that @vsk's benchmark didn't show a regression. I've added some minor comments inline.

I'd highly recommend giving the "location zero" index a fixed number, like kEntryValueBackupLocation, to identify all the parts of LiveDebugValues that rely on it.

There's a small amount of code to cope with scenarios where a DBG_VALUE_LIST has duplicate operands; if we're going to support this, there'll need to be a test that this is properly handled.

Could I also ask for a test featuring a DBG_VALUE_LIST with a $noreg operand, just to check that doesn't propagate any further.

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

233–1

Comment indicating these are only meaningful for NonEntryValueKind VarLocs?

233–1

std::tie for consistency?

233–1

This and nearby reformatting looks to be a no-op refactor, yes? IMO best to remove it, or add it as a follow-up, to avoid further review / audit burden.

233–1

Explanation of the magic zero would help, "Iterate over all VarLocs -- they will all have an entry at location zero"?

234

I worry that this will hit "unused type / name" warnings in later compilers, can we guard it with NDEBUG, like its uses?

234

Is now "later"? If this needs to stay it, better to document it and what its limitation is (reduces bus factor)

236

IMHO having a default location-bucket here is undesirable: the KillSet is meaningless without it, and it raises the possibility of accidentally clearing VarLocs from location-bucket zero, when a different location-bucket should have been used.

237

assertion for that? Strikes me as fragile otherwise.

239

I'm not sure what "true set" means here

241

Register rather than uint32_t?

277

nit: I would say transformed, as VarLocs themselves should be constant.

279–281

As I understand it, this is to cope with duplicate locations from a MachineInstr, yes? If so, that should go in the comment.

[StephenTozer]

Rebased onto latest master, address review comments.

[nikic]

It looks like this is a significant compile-time regression for optimized builds with debug info: https://llvm-compile-time-tracker.com/compare.php?from=b4825a6d9c18bdb3e241d709f2f76573aba9f91b&to=e2196ddcdbf13aa1051e0150036e103d23a03f13&stat=instructions SPASS.link is up 3.6%.

[StephenTozer]

In D83890#2615025, @nikic wrote:

It looks like this is a significant compile-time regression for optimized builds with debug info: https://llvm-compile-time-tracker.com/compare.php?from=b4825a6d9c18bdb3e241d709f2f76573aba9f91b&to=e2196ddcdbf13aa1051e0150036e103d23a03f13&stat=instructions SPASS.link is up 3.6%.

Some compile-time regression was expected to take place as a result of this; the LiveDebugValues implementation was heavily optimized, and this change necessarily breaks part of that optimization. With that said, performance tests of this patch prior to merging did not give results that were this dramatic; total compile times for SPASS were closer to 1% than 3%. This is still a significant increase in compile time, but proportional to the expected increase in variable coverage (in aggregate). It is possible to optimize the LiveDebugValues implementation further however - this implementation represents a first pass attempt to allow LiveDebugValues to handle variables with more complex location expressions, but further optimizations can be made in subsequent patches.

llvm/lib/CodeGen/LiveDebugValues/VarLocBasedImpl.cpp

 /// is at least "True", and then propagate "False" from the entry block and any
 /// clobbers until there are no more changes to make. This gives us an accurate
 /// solution because all incorrect locations will have a "False" propagated into
 /// them. It also gives us a solution that copes well with loops by assuming
 /// that variable locations are live-through every loop, and then removing those
 /// that are not through dataflow.
 ///
 /// Within LiveDebugValues: each variable location is represented by a
-/// VarLoc object that identifies the source variable, its current
-/// machine-location, and the DBG_VALUE inst that specifies the location. Each
-/// VarLoc is indexed in the (function-scope) \p VarLocMap, giving each VarLoc a
-/// unique index. Rather than operate directly on machine locations, the
-/// dataflow analysis in this pass identifies locations by their index in the
-/// VarLocMap, meaning all the variable locations in a block can be described
-/// by a sparse vector of VarLocMap indicies.
+/// 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
 /// implementation. Instead, unvisited blocks implicitly have all lattice
 /// values set as "Unknown". After being visited, there will be path back to
 /// the entry block where the lattice value is "False", and as the transfer
 /// function cannot make new "Unknown" locations, there are no scenarios where
 /// a block can have an "Unknown" location after being visited. Similarly, we
static cl::opt<unsigned> InputBBLimit(
     cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"),
     cl::init(10000), cl::Hidden);
 static cl::opt<unsigned> InputDbgValueLimit(
     "livedebugvalues-input-dbg-value-limit",
     cl::desc(
         "Maximum input DBG_VALUE insts supported by debug range extension"),
     cl::init(50000), cl::Hidden);
 
-// If @MI is a DBG_VALUE with debug value described by a defined
-// register, returns the number of this register. In the other case, returns 0.
-static Register isDbgValueDescribedByReg(const MachineInstr &MI) {
-  assert(MI.isDebugValue() && "expected a DBG_VALUE");
-  assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE");
-  // If location of variable is described using a register (directly
-  // or indirectly), this register is always a first operand.
-  return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg()
-                                       : Register();
-}
-
 /// If \p Op is a stack or frame register return true, otherwise return false.
 /// This is used to avoid basing the debug entry values on the registers, since
 /// we do not support it at the moment.
 static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
                                   const MachineInstr &MI,
                                   const TargetRegisterInfo *TRI) {
   if (!Op.isReg())
     return false;
 
   const MachineFunction *MF = MI.getParent()->getParent();
   const TargetLowering *TLI = MF->getSubtarget().getTargetLowering();
   Register SP = TLI->getStackPointerRegisterToSaveRestore();
   Register FP = TRI->getFrameRegister(*MF);
   Register Reg = Op.getReg();
 
   return Reg && Reg != SP && Reg != FP;
 }
 
 namespace {
 
 // Max out the number of statically allocated elements in DefinedRegsSet, as
 // this prevents fallback to std::set::count() operations.
 using DefinedRegsSet = SmallSet<Register, 32>;
 
+// 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
 /// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int
 /// for insertion into a \ref VarLocSet, and efficiently converted back. The
 /// type-checker helps ensure that the conversions aren't lossy.
 ///
 /// Why encode a location /into/ the VarLocMap index? This makes it possible
 /// to find the open VarLocs killed by a register def very quickly. This is a
 /// performance-critical operation for LiveDebugValues.
 struct LocIndex {
   using u32_location_t = uint32_t;
   using u32_index_t = uint32_t;
 
   u32_location_t Location; // Physical registers live in the range [1;2^30) (see
                            // \ref MCRegister), so we have plenty of range left
                            // here to encode non-register locations.
   u32_index_t Index;
 
-  /// The first location greater than 0 that is not reserved for VarLocs of
-  /// kind RegisterKind.
+  /// 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
   /// EntryValueCopyBackupKind.
   static constexpr u32_location_t kEntryValueBackupLocation =
       kFirstInvalidRegLocation + 1;
 
   LocIndex(u32_location_t Location, u32_index_t Index)
       : Location(Location), Index(Index) {}
 
   uint64_t getAsRawInteger() const {
     return (static_cast<uint64_t>(Location) << 32) | Index;
   }
 
   template<typename IntT> static LocIndex fromRawInteger(IntT ID) {
     static_assert(std::is_unsigned<IntT>::value &&
                       sizeof(ID) == sizeof(uint64_t),
                   "Cannot convert raw integer to LocIndex");
     return {static_cast<u32_location_t>(ID >> 32),
             static_cast<u32_index_t>(ID)};
   }
 
   /// Get the start of the interval reserved for VarLocs of kind RegisterKind
   /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1.
-  static uint64_t rawIndexForReg(uint32_t Reg) {
+  static uint64_t rawIndexForReg(Register Reg) {
     return LocIndex(Reg, 0).getAsRawInteger();
   }
 
   /// Return a range covering all set indices in the interval reserved for
   /// \p Location in \p Set.
   static auto indexRangeForLocation(const VarLocSet &Set,
                                     u32_location_t Location) {
     uint64_t Start = LocIndex(Location, 0).getAsRawInteger();
     uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger();
     return Set.half_open_range(Start, End);
   }
 };
 
+// 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;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   TargetPassConfig *TPC;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
struct VarLoc {
 
     /// The expression applied to this location.
     const DIExpression *Expr;
 
     /// DBG_VALUE to clone var/expr information from if this location
     /// is moved.
     const MachineInstr &MI;
 
-    enum VarLocKind {
+    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();
-      }
-
-      // We create the debug entry values from the factory functions rather than
-      // from this ctor.
-      assert(Kind != EntryValueKind && !isEntryBackupLoc());
+      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(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
     /// entry location using the given expression.
     static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS,
                                  const DIExpression *EntryExpr, Register Reg) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueKind;
+      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;
     }
 
     /// Take the variable and machine-location from the DBG_VALUE (from the
     /// function entry), and build an entry value backup location. The backup
     /// location will turn into the normal location if the backup is valid at
     /// the time of the primary location clobbering.
     static VarLoc CreateEntryBackupLoc(const MachineInstr &MI,
                                        LexicalScopes &LS,
                                        const DIExpression *EntryExpr) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueBackupKind;
+      assert(VL.Locs.size() == 1 &&
+             VL.Locs[0].Kind == MachineLocKind::RegisterKind);
+      VL.EVKind = EntryValueLocKind::EntryValueBackupKind;
       VL.Expr = EntryExpr;
       return VL;
     }
 
     /// Take the variable and machine-location from the DBG_VALUE (from the
     /// function entry), and build a copy of an entry value backup location by
     /// setting the register location to NewReg.
     static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI,
                                            LexicalScopes &LS,
                                            const DIExpression *EntryExpr,
                                            Register NewReg) {
       VarLoc VL(MI, LS);
-      assert(VL.Kind == RegisterKind);
-      VL.Kind = EntryValueCopyBackupKind;
+      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;
+      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};
+    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.
     /// Copies variable-specific information such as DILocalVariable and
     /// inlining information from the original DBG_VALUE instruction, which may
     /// have been several transfers ago.
     MachineInstr *BuildDbgValue(MachineFunction &MF) const {
+      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:
+      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.
-        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: {
+          // 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.
-        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);
+          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 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");
+        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 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 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 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 by a register holding the entry value,
-    /// return it, otherwise return 0.
-    unsigned getEntryValueBackupReg() const {
-      if (Kind == EntryValueBackupKind)
-        return Loc.RegNo;
-      return 0;
-    }
-
-    /// If this variable is described by a register holding the copy of the
-    /// entry value, return it, otherwise return 0.
-    unsigned getEntryValueCopyBackupReg() const {
-      if (Kind == EntryValueCopyBackupKind)
-        return Loc.RegNo;
-      return 0;
-    }
-
-    /// If this variable is described by a register, return it,
-    /// otherwise return 0.
-    unsigned isDescribedByReg() const {
-      if (Kind == RegisterKind)
-        return Loc.RegNo;
-      return 0;
+    /// 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
     /// dominates MBB.
     bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const {
       return LS.dominates(MI.getDebugLoc().get(), &MBB);
     }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     // TRI can be null.
     void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const {
       Out << "VarLoc(";
-      switch (Kind) {
-      case RegisterKind:
-      case EntryValueKind:
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-        Out << printReg(Loc.RegNo, TRI);
+      for (const MachineLoc &MLoc : Locs) {
+        if (Locs.begin() != &MLoc)
+          Out << ", ";
+        switch (MLoc.Kind) {
+        case MachineLocKind::RegisterKind:
+          Out << printReg(MLoc.Value.RegNo, TRI);
           break;
-      case SpillLocKind:
-        Out << printReg(Loc.SpillLocation.SpillBase, TRI);
-        Out << "[" << Loc.SpillLocation.SpillOffset.getFixed() << " + "
-            << Loc.SpillLocation.SpillOffset.getScalable() << "x vscale"
+        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 ImmediateKind:
-        Out << Loc.Immediate;
+        case MachineLocKind::ImmediateKind:
+          Out << MLoc.Value.Immediate;
           break;
-      case InvalidKind:
+        case MachineLocKind::InvalidKind:
           llvm_unreachable("Invalid VarLoc in dump method");
         }
+      }
 
       Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", ";
       if (Var.getInlinedAt())
         Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n";
       else
         Out << "(null))";
 
       if (isEntryBackupLoc())
         Out << " (backup loc)\n";
       else
         Out << "\n";
     }
 #endif
 
     bool operator==(const VarLoc &Other) const {
-      if (Kind != Other.Kind || !(Var == Other.Var) || Expr != Other.Expr)
-        return false;
-
-      switch (Kind) {
-      case SpillLocKind:
-        return Loc.SpillLocation == Other.Loc.SpillLocation;
-      case RegisterKind:
-      case ImmediateKind:
-      case EntryValueKind:
-      case EntryValueBackupKind:
-      case EntryValueCopyBackupKind:
-        return Loc.Hash == Other.Loc.Hash;
-      default:
-        llvm_unreachable("Invalid kind");
-      }
+      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.
     const VarLoc &operator[](LocIndex ID) const {
       auto LocIt = Loc2Vars.find(ID.Location);
       assert(LocIt != Loc2Vars.end() && "Location not tracked");
       return LocIt->second[ID.Index];
     }
#endif
   using OverlapMap =
       DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
 
   // Helper while building OverlapMap, a map of all fragments seen for a given
   // DILocalVariable.
   using VarToFragments =
       DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>;
 
+  /// 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
   /// previous open ranges for the same variable. In addition, we keep
   /// two different maps (Vars/EntryValuesBackupVars), so erase/insert
   /// methods act differently depending on whether a VarLoc is primary
   /// location or backup one. In the case the VarLoc is backup location
   /// we will erase/insert from the EntryValuesBackupVars map, otherwise
   /// we perform the operation on the Vars.
   class OpenRangesSet {
+    VarLocSet::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() {
       VarLocs.clear();
       Vars.clear();
       EntryValuesBackupVars.clear();
     }
 
     /// Return whether the set is empty or not.
     bool empty() const {
       assert(Vars.empty() == EntryValuesBackupVars.empty() &&
              Vars.empty() == VarLocs.empty() &&
              "open ranges are inconsistent");
       return VarLocs.empty();
     }
 
     /// Get an empty range of VarLoc IDs.
     auto getEmptyVarLocRange() const {
       return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(),
                                                        getVarLocs().end());
     }
 
-    /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg.
+    /// 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(
           getVarLocs(), LocIndex::kEntryValueBackupLocation);
     }
   };
 
-  /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind
-  /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs
-  /// into \p Collected.
-  void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs,
-                         const VarLocSet &CollectFrom) const;
-
-  /// Get the registers which are used by VarLocs of kind RegisterKind tracked
-  /// by \p CollectFrom.
-  void getUsedRegs(const VarLocSet &CollectFrom,
-                   SmallVectorImpl<uint32_t> &UsedRegs) const;
+  /// 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];
     if (!VLS)
       VLS = std::make_unique<VarLocSet>(Alloc);
     return *VLS.get();
   }
 
Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
                                                   MachineFunction *MF,
                                                   Register &Reg);
   /// Given a spill instruction, extract the register and offset used to
   /// address the spill location in a target independent way.
   VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
   void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                TransferMap &Transfers, VarLocMap &VarLocIDs,
                                LocIndex OldVarID, TransferKind Kind,
+                               const VarLoc::MachineLoc &OldLoc,
                                Register NewReg = Register());
 
   void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                           VarLocMap &VarLocIDs);
   void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges,
                                   VarLocMap &VarLocIDs, TransferMap &Transfers);
   bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges,
                         VarLocMap &VarLocIDs, const VarLoc &EntryVL);
   void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges,
                        VarLocMap &VarLocIDs, TransferMap &Transfers,
-                       VarLocSet &KillSet);
+                       VarLocsInRange &KillSet);
   void recordEntryValue(const MachineInstr &MI,
                         const DefinedRegsSet &DefinedRegs,
                         OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs);
   void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges,
                             VarLocMap &VarLocIDs, TransferMap &Transfers);
   void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges,
                            VarLocMap &VarLocIDs, TransferMap &Transfers);
   bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges,

 /// tracking its backup entry location. Otherwise, if the VarLoc is primary
 /// location, erase the variable from the Vars set.
 void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) {
   // Erasure helper.
   auto DoErase = [VL, this](DebugVariable VarToErase) {
     auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
     auto It = EraseFrom->find(VarToErase);
     if (It != EraseFrom->end()) {
-      LocIndex ID = It->second;
+      LocIndices IDs = It->second;
+      for (LocIndex ID : IDs)
         VarLocs.reset(ID.getAsRawInteger());
       EraseFrom->erase(It);
     }
   };
 
   DebugVariable Var = VL.Var;
 
   // Erase the variable/fragment that ends here.
   DoErase(Var);
for (auto Fragment : MapIt->second) {
       VarLocBasedLDV::OptFragmentInfo FragmentHolder;
       if (!DebugVariable::isDefaultFragment(Fragment))
         FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment);
       DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()});
     }
   }
 }
 
-void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet,
-                                           const VarLocMap &VarLocIDs) {
-  VarLocs.intersectWithComplement(KillSet);
-  for (uint64_t ID : KillSet) {
-    const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)];
-    auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars;
-    EraseFrom->erase(VL->Var);
+void VarLocBasedLDV::OpenRangesSet::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,
   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())
     return It->second;
 
   return llvm::None;
 }
 
-void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected,
-                                        const DefinedRegsSet &Regs,
-                                        const VarLocSet &CollectFrom) const {
+void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected,
+                                       const VarLocSet &CollectFrom,
+                                       const VarLocMap &VarLocIDs) {
   assert(!Regs.empty() && "Nothing to collect");
-  SmallVector<uint32_t, 32> SortedRegs;
+  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;
   }
 }
 
 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),
             End = CollectFrom.find(FirstInvalidIndex);
        It != End;) {
     // We found a VarLoc ID for a VarLoc that lives in a register. Figure out
     // which register and add it to UsedRegs.
     uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location;
void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF,
                                        raw_ostream &Out) const {
   Out << '\n' << msg << '\n';
   for (const MachineBasicBlock &BB : MF) {
     if (!V.count(&BB))
       continue;
     const VarLocSet &L = getVarLocsInMBB(&BB, V);
     if (L.empty())
       continue;
+    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);
     }
   }
   Out << "\n";
 }
 #endif
bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI,
   // indicating that we should stop tracking its entry value as well.
   if (!MI.getDebugOperand(0).isReg() ||
       MI.getDebugExpression()->getNumElements() != 0)
     return true;
 
   // If the DBG_VALUE comes from a copy instruction that copies the entry value,
   // it means the parameter's value has not changed and we should be able to use
   // its entry value.
-  bool TrySalvageEntryValue = false;
   Register Reg = MI.getDebugOperand(0).getReg();
   auto I = std::next(MI.getReverseIterator());
   const MachineOperand *SrcRegOp, *DestRegOp;
   if (I != MI.getParent()->rend()) {
+
     // TODO: Try to keep tracking of an entry value if we encounter a propagated
     // DBG_VALUE describing the copy of the entry value. (Propagated entry value
     // does not indicate the parameter modification.)
     auto DestSrc = TII->isCopyInstr(*I);
     if (!DestSrc)
       return true;
 
     SrcRegOp = DestSrc->Source;
     DestRegOp = DestSrc->Destination;
     if (Reg != DestRegOp->getReg())
       return true;
-    TrySalvageEntryValue = true;
-  }
 
-  if (TrySalvageEntryValue) {
     for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
       const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)];
-      if (VL.getEntryValueCopyBackupReg() == Reg &&
+      if (VL.isEntryValueCopyBackupReg(Reg) &&
+          // Entry Values should not be variadic.
           VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg())
         return false;
     }
   }
 
   return true;
 }
 
assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
          "Expected inlined-at fields to agree");
 
   DebugVariable V(Var, Expr, InlinedAt);
 
   // Check if this DBG_VALUE indicates a parameter's value changing.
   // If that is the case, we should stop tracking its entry value.
   auto EntryValBackupID = OpenRanges.getEntryValueBackup(V);
   if (Var->isParameter() && EntryValBackupID) {
-    const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID];
+    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,
                           /*SkipOpers*/ false, /*SkipDebugLoc*/ false,
                           /*AddNewLine*/ true, TII));
       OpenRanges.erase(EntryVL);
     }
   }
 
-  if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() ||
-      MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) {
+  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) {
+                                     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);
   }
 }
 
 /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc
 /// with \p OldVarID should be deleted form \p OpenRanges and replaced with
 /// new VarLoc. If \p NewReg is different than default zero value then the
 /// new location will be register location created by the copy like instruction,
 /// otherwise it is variable's location on the stack.
 void VarLocBasedLDV::insertTransferDebugPair(
     MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers,
     VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind,
-    Register NewReg) {
-  const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI;
+    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);
   };
 
   // End all previous ranges of VL.Var.
   OpenRanges.erase(VarLocIDs[OldVarID]);
   switch (Kind) {
   case TransferKind::TransferCopy: {
     assert(NewReg &&
            "No register supplied when handling a copy of a debug value");
     // Create a DBG_VALUE instruction to describe the Var in its new
     // register location.
-    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
+    VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for register copy:";
       VL.dump(TRI);
     });
     return;
   }
   case TransferKind::TransferSpill: {
     // Create a DBG_VALUE instruction to describe the Var in its spilled
     // location.
     VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI);
-    VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase,
-                                       SpillLocation.SpillOffset, LS);
+    VarLoc VL = VarLoc::CreateSpillLoc(
+        OldVarLoc, OldLoc, SpillLocation.SpillBase, SpillLocation.SpillOffset);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for spill:";
       VL.dump(TRI);
     });
     return;
   }
   case TransferKind::TransferRestore: {
     assert(NewReg &&
            "No register supplied when handling a restore of a debug value");
     // DebugInstr refers to the pre-spill location, therefore we can reuse
     // its expression.
-    VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg);
+    VarLoc VL = VarLoc::CreateCopyLoc(OldVarLoc, OldLoc, NewReg);
     ProcessVarLoc(VL);
     LLVM_DEBUG({
       dbgs() << "Creating VarLoc for restore:";
       VL.dump(TRI);
     });
     return;
   }
   }
if (MO.isReg() && MO.isDef() && MO.getReg() &&
       RegMasks.push_back(MO.getRegMask());
     }
   }
 
   // Erase VarLocs which reside in one of the dead registers. For performance
   // reasons, it's critical to not iterate over the full set of open VarLocs.
   // Iterate over the set of dying/used regs instead.
   if (!RegMasks.empty()) {
-    SmallVector<uint32_t, 32> UsedRegs;
+    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.
       // While the debug info may be off for an instruction or two around
       // callee-cleanup calls, transferring the DEBUG_VALUE across the call is
       // still a better user experience.
       if (Reg == SP)
         continue;
       bool AnyRegMaskKillsReg =
           any_of(RegMasks, [Reg](const uint32_t *RegMask) {
             return MachineOperand::clobbersPhysReg(RegMask, Reg);
           });
       if (AnyRegMaskKillsReg)
         DeadRegs.insert(Reg);
     }
   }
 
   if (DeadRegs.empty())
     return;
 
-  VarLocSet KillSet(Alloc);
-  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs());
-  OpenRanges.erase(KillSet, VarLocIDs);
+  VarLocsInRange KillSet;
+  collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs(), VarLocIDs);
+  OpenRanges.erase(KillSet, VarLocIDs, LocIndex::kUniversalLocation);
 
   if (TPC) {
     auto &TM = TPC->getTM<TargetMachine>();
     if (TM.Options.ShouldEmitDebugEntryValues())
       emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet);
   }
 }
 
void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
   Register Reg;
   Optional<VarLoc::SpillLoc> Loc;
 
   LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););
 
   // First, if there are any DBG_VALUEs pointing at a spill slot that is
   // written to, then close the variable location. The value in memory
   // will have changed.
-  VarLocSet KillSet(Alloc);
+  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.
         //
         // Doing this at a later stage would require re-interpreting all
         // DBG_VALUes and DIExpressions to identify whether they point at
         // memory, and then analysing all memory writes to see if they
         // overwrite that memory, which is expensive.
         //
         // At this stage, we already know which DBG_VALUEs are for spills and
         // where they are located; it's best to fix handle overwrites now.
-        KillSet.set(ID);
-        VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0);
-        LocIndex UndefLocID = VarLocIDs.insert(UndefVL);
-        Transfers.push_back({&MI, UndefLocID});
+        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
   // variable location.
   if (isLocationSpill(MI, MF, Reg)) {
     TKind = TransferKind::TransferSpill;
     LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump(););
     LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI)
void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI,
   auto TransferCandidates = OpenRanges.getEmptyVarLocRange();
   if (TKind == TransferKind::TransferSpill)
     TransferCandidates = OpenRanges.getRegisterVarLocs(Reg);
   else if (TKind == TransferKind::TransferRestore)
     TransferCandidates = OpenRanges.getSpillVarLocs();
   for (uint64_t ID : TransferCandidates) {
     LocIndex Idx = LocIndex::fromRawInteger(ID);
     const VarLoc &VL = VarLocIDs[Idx];
+    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;
   }
 }
 
 /// If \p MI is a register copy instruction, that copies a previously tracked
 /// value from one register to another register that is callee saved, we
void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI,
 
   // Remember an entry value movement. If we encounter a new debug value of
   // a parameter describing only a moving of the value around, rather then
   // modifying it, we are still able to use the entry value if needed.
   if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) {
     for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) {
       LocIndex Idx = LocIndex::fromRawInteger(ID);
       const VarLoc &VL = VarLocIDs[Idx];
-      if (VL.getEntryValueBackupReg() == SrcReg) {
+      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;
       }
     }
   }
 
   if (!SrcRegOp->isKill())
     return;
 
   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;
   }
 }
 
 /// Terminate all open ranges at the end of the current basic block.
 bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB,
                                          OpenRangesSet &OpenRanges,
                                          VarLocInMBB &OutLocs,
                                          const VarLocMap &VarLocIDs) {
   bool Changed = false;
-
-  LLVM_DEBUG(for (uint64_t ID
-                  : OpenRanges.getVarLocs()) {
+  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() << ":  ";
-    VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI);
+      VL.dump(TRI);
+    }
   });
   VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs);
   Changed = VLS != OpenRanges.getVarLocs();
   // New OutLocs set may be different due to spill, restore or register
   // copy instruction processing.
   if (Changed)
     VLS = OpenRanges.getVarLocs();
   OpenRanges.clear();
for (auto p : MBB.predecessors()) {
     VarLocSet &OutLocVLS = *OL->second.get();
     if (!NumVisited)
       InLocsT = OutLocVLS;
     else
       InLocsT &= OutLocVLS;
 
     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";
       }
     });
 
     NumVisited++;
   }
 
   // Filter out DBG_VALUES that are out of scope.
   VarLocSet KillSet(Alloc);
void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
   for (auto &Iter : PendingInLocs) {
     // Map is keyed on a constant pointer, unwrap it so we can insert insts.
     auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first);
     VarLocSet &Pending = *Iter.second.get();
 
-    for (uint64_t ID : Pending) {
+    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());
       MBB.insert(MBB.instr_begin(), MI);
 
       (void)MI;
       LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     }
void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI,
 
   LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump(););
 
   // Create the entry value and use it as a backup location until it is
   // valid. It is valid until a parameter is not changed.
   DIExpression *NewExpr =
       DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue);
   VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr);
-  LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup);
-  OpenRanges.insert(EntryValLocID, EntryValLocAsBackup);
+  LocIndices EntryValLocIDs = VarLocIDs.insert(EntryValLocAsBackup);
+  OpenRanges.insert(EntryValLocIDs, EntryValLocAsBackup);
 }
 
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) {
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 
   if (!MF.getFunction().getSubprogram())

llvm/test/DebugInfo/MIR/X86/dvl-livedebugvalues-clobber.mir

+# RUN: llc -mtriple=x86_64-- -run-pass livedebugvalues -o - %s | FileCheck %s --implicit-check-not=DBG_VALUE_LIST
+#
+# Test that even after a move, clobbering a register terminates a DBG_VALUE_LIST.
+# Check the same for DBG_VALUE $noreg.
+#
+# CHECK: ![[VAR:[0-9]+]] = !DILocalVariable(name: "c"
+# 
+# CHECK-LABEL: bb.0.entry:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi
+# CHECK:       $rbx = COPY killed $rdi
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# CHECK-LABEL: bb.1:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# CHECK:       $rsi = MOV64ri 0
+# CHECK-LABEL: bb.2:
+# no live-in!
+# CHECK:       $rsi = MOV64ri 0
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# CHECK-LABEL: bb.3:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# live-in to bb.3, then explicitly undef'd, should be no further locations
+# propagated.
+# CHECK-LABEL: bb.4:
+--- |
+  ; ModuleID = 'test.cpp'
+  source_filename = "test.cpp"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  ; Function Attrs: norecurse nounwind readnone uwtable
+  define dso_local i32 @_Z3fooii(i32 %a, i32 %b) local_unnamed_addr !dbg !7 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.cpp", directory: "/")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"clang version 11.0.0"}
+  !7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !{!12, !13, !14}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !13 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 0, scope: !7)
+  !16 = !DILocation(line: 4, column: 12, scope: !7)
+  !17 = !DILocation(line: 4, column: 3, scope: !7)
+
+...
+---
+name:            _Z3fooii
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -32, size: 8, alignment: 16, stack-id: default,
+      callee-saved-register: '$rbx', callee-saved-restored: true }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16, stack-id: default,
+      callee-saved-register: '$rbp', callee-saved-restored: true }
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi
+  
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    $rbx = COPY killed $rdi
+    $rdi = MOV64ri 0
+    JMP_1 %bb.1
+
+  bb.1:
+    liveins: $rbx, $rsi
+    $rsi = MOV64ri 0
+    JMP_1 %bb.2
+
+  bb.2:
+    liveins: $rbx, $rsi
+
+    $rsi = MOV64ri 0
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi, debug-location !15
+    JMP_1 %bb.3
+
+  bb.3:
+    liveins: $rbx, $rsi
+    DBG_VALUE $noreg, $noreg, !14, !DIExpression(), debug-location !15
+    JMP_1 %bb.4
+
+  bb.4:
+    liveins: $rbx, $rsi
+    RETQ $rbx, debug-location !17
+
+...
+

llvm/test/DebugInfo/MIR/X86/dvl-livedebugvalues-join.mir

+# RUN: llc -mtriple=x86_64-- -run-pass livedebugvalues -o - %s | FileCheck %s --implicit-check-not=DBG_VALUE_LIST
+#
+# Test a series of joins, where:
+#  * The locations agree, although registers have changed,
+#  * A register down one of the predecessors has been def'd,
+#  * The register operands to DBG_VALUE_LIST have been swapped,
+#  * A spurious additional operand has been added to one path,
+#  * The expressions are not the same (plus -> minus).
+#
+# Each join block below checks for one DBG_VALUE_LIST: either we re-state the var
+# location in a block for the next test, or it's created as a live-in and we
+# use that for the next test. Two DBG_VALUE_LISTs in a block would represent
+# a live-in that we didn't expect, and a test failure.
+#
+# Each conditional block should have at least one, possibly two.
+#
+# CHECK: ![[VAR:[0-9]+]] = !DILocalVariable(name: "c"
+# 
+# CHECK-LABEL: bb.0.entry:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-LABEL: bb.1:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-LABEL: bb.2:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi
+# CHECK-LABEL: bb.3:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-LABEL: bb.4:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:        $rdi, $rsi
+# CHECK-LABEL: bb.5:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:        $rsi, $rdi
+# CHECK-LABEL: bb.6:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-LABEL: bb.7:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:        $rdi, $rsi, $rax
+# CHECK-LABEL: bb.8:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-LABEL: bb.9:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:        DW_OP_minus
+# CHECK-LABEL: bb.10:
+--- |
+  ; ModuleID = 'test.cpp'
+  source_filename = "test.cpp"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  ; Function Attrs: norecurse nounwind readnone uwtable
+  define dso_local i32 @_Z3fooii(i32 %a, i32 %b) local_unnamed_addr !dbg !7 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.cpp", directory: "/")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"clang version 11.0.0"}
+  !7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !{!12, !13, !14}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !13 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 0, scope: !7)
+  !16 = !DILocation(line: 4, column: 12, scope: !7)
+  !17 = !DILocation(line: 4, column: 3, scope: !7)
+
+...
+---
+name:            _Z3fooii
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi
+  
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    CMP64ri8 $rdi, 0, implicit-def $eflags
+    JCC_1 %bb.2, 4, implicit $eflags
+
+  bb.1:
+    liveins: $rdi, $rsi
+    $rdi = MOV64ri 0
+    $rsi = MOV64ri 0
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+
+  bb.2:
+    liveins: $rdi, $rsi
+    ; Should be a live-in loc here,
+    CMP64ri8 $rdi, 0, implicit-def $eflags
+    JCC_1 %bb.4, 4, implicit $eflags
+    
+  bb.3:
+    liveins: $rdi, $rsi
+    $rsi = MOV64ri 0
+
+  bb.4:
+    liveins: $rdi, $rsi
+    ; Should _not_ be a live-in loc here.
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    CMP64ri8 $rdi, 0, implicit-def $eflags
+    JCC_1 %bb.6, 4, implicit $eflags
+
+  bb.5:
+    liveins: $rdi, $rsi
+    ; Flip some args,
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rsi, $rdi, debug-location !15
+
+  bb.6:
+    liveins: $rdi, $rsi
+    ; Should _not_ be a live-in loc here.
+    $rax = MOV64ri 0
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    CMP64ri8 $rdi, 0, implicit-def $eflags
+    JCC_1 %bb.8, 4, implicit $eflags
+
+  bb.7:
+    liveins: $rdi, $rsi
+    ; Add an extra, spurious, unused argument
+    $rax = MOV64ri 1
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, $rax, debug-location !15
+
+  bb.8:
+    liveins: $rdi, $rsi
+    ; Should _not_ be a live-in loc here.
+    $rax = MOV64ri 0
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    CMP64ri8 $rdi, 0, implicit-def $eflags
+    JCC_1 %bb.10, 4, implicit $eflags
+
+  bb.9:
+    liveins: $rdi, $rsi
+    ; Replace add with sub in the expr
+    $rax = MOV64ri 1
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_minus), $rdi, $rsi, debug-location !15
+
+  bb.10:
+    liveins: $rdi, $rsi
+    ; Should _not_ be a live-in loc here.
+    RETQ
+
+...
+

llvm/test/DebugInfo/MIR/X86/dvl-livedebugvalues-movements.mir

+# RUN: llc -mtriple=x86_64-- -run-pass livedebugvalues -o - %s | FileCheck %s --implicit-check-not=DBG_VALUE_LIST
+#
+# The MIR below moves values from argument registers to callee saved registers,
+# moves that are followed by DBG_VALUEs and which should also result in
+# DBG_VALUE_LISTs moving their operands.
+#
+# CHECK: ![[VAR:[0-9]+]] = !DILocalVariable(name: "c"
+# 
+# CHECK-LABEL: bb.0.entry:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi
+# CHECK:       $rbx = COPY killed $rdi
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# CHECK-LABEL: bb.1:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rsi
+# CHECK:       $rbp = COPY killed $rsi
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rbp
+# CHECK-LABEL: bb.2:
+# CHECK:       DBG_VALUE_LIST ![[VAR]], !DIExpression(DW_OP_LLVM_arg, 0,
+# CHECK-SAME:                        DW_OP_LLVM_arg, 1, DW_OP_plus), $rbx, $rbp
+--- |
+  ; ModuleID = 'test.cpp'
+  source_filename = "test.cpp"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  ; Function Attrs: norecurse nounwind readnone uwtable
+  define dso_local i32 @_Z3fooii(i32 %a, i32 %b) local_unnamed_addr !dbg !7 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.cpp", directory: "/")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"clang version 11.0.0"}
+  !7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !{!12, !13, !14}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !13 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 0, scope: !7)
+  !16 = !DILocation(line: 4, column: 12, scope: !7)
+  !17 = !DILocation(line: 4, column: 3, scope: !7)
+
+...
+---
+name:            _Z3fooii
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -32, size: 8, alignment: 16, stack-id: default,
+      callee-saved-register: '$rbx', callee-saved-restored: true }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16, stack-id: default,
+      callee-saved-register: '$rbp', callee-saved-restored: true }
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi
+
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    $rbx = COPY killed $rdi
+    $rdi = MOV64ri 0
+    JMP_1 %bb.1
+
+  bb.1:
+    liveins: $rbx, $rsi
+    $rbp = COPY killed $rsi
+    $rsi = MOV64ri 0
+    JMP_1 %bb.2
+
+  bb.2:
+    liveins: $rbx, $rbp
+    RETQ $rbp, debug-location !17
+
+...
+

llvm/test/DebugInfo/MIR/X86/dvl-livedebugvalues-spillrestore.mir

+# RUN: llc -mtriple=x86_64-- -run-pass livedebugvalues -o - %s | FileCheck %s --implicit-check-not=DBG_VALUE_LIST
+#
+# A DBG_VALUE_LIST that has a component spilt and restored should had its
+# expression and operands updated to refer to the stack for that period, and
+# then return to normal once the value is restored.
+#
+# CHECK: ![[VAR:[0-9]+]] = !DILocalVariable(name: "c"
+# 
+# CHECK-LABEL: bb.0.entry:
+# CHECK:       DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:  !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus),
+# CHECK-SAME:  $rdi, $rsi,
+# CHECK:       MOV64mr $rsp, 1, $noreg, -16, $noreg, $rdi
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:  !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_constu, 8, DW_OP_minus, DW_OP_deref, DW_OP_LLVM_arg, 1, DW_OP_plus),
+# CHECK-SAME:                $rsp, $rsi,
+# CHECK:       $rdi = MOV64rm $rsp, 1, $noreg, -16,
+# CHECK-NEXT:  DBG_VALUE_LIST ![[VAR]],
+# CHECK-SAME:  !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus),
+# CHECK-SAME:  $rdi, $rsi,
+
+--- |
+  ; ModuleID = 'test.cpp'
+  source_filename = "test.cpp"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  ; Function Attrs: norecurse nounwind readnone uwtable
+  define dso_local i32 @_Z3fooii(i32 %a, i32 %b) local_unnamed_addr !dbg !7 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.cpp", directory: "/")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"clang version 11.0.0"}
+  !7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooii", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !{!12, !13, !14}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !13 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 0, scope: !7)
+  !16 = !DILocation(line: 4, column: 12, scope: !7)
+  !17 = !DILocation(line: 4, column: 3, scope: !7)
+
+...
+---
+name:            _Z3fooii
+stack:
+  - { id: 0, offset: -16, size: 8, alignment: 8, type: spill-slot }
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi
+  
+    $rsp = frame-setup SUB64ri8 $rsp, 24, implicit-def dead $eflags
+    DBG_VALUE_LIST !14, !DIExpression(DW_OP_LLVM_arg, 0, DW_OP_LLVM_arg, 1, DW_OP_plus), $rdi, $rsi, debug-location !15
+    MOV64mr $rsp, 1, _, -16, _, $rdi, debug-location !15 :: (store 8 into %stack.0)
+    $rax = COPY killed $rdi
+    $rdi = MOV64ri 0
+    $rdi = MOV64rm $rsp, 1, $noreg, -16, $noreg, debug-location !15 :: (load 8 from %stack.0)
+    RETQ
+...
+