[DebugInfo][InstrRef][NFC] Handle transfers of variadic debug values in InstrRefLDV

[StephenTozer]

Summary

This patch adds the last of the changes required to enable DBG_VALUE_LIST handling in InstrRefLDV, handling variadic debug values during the transfer tracking step. Most of the changes are fairly straightforward, and based around tracking multiple locations per variable in TransferTracker::VLocTracker. There has also been a significant change in tracking use-before-defs, since we now have to 1) only emit a UseBeforeDef value when all of its values are defined, meaning that we can't just look up whether there is a dependent UseBeforeDef for each instruction as we go along, and 2) when it is time to emit a UseBeforeDef, we have to check that all the values it wants to use are still available - it is possible that one of the required values is killed before all of the values have been defined.

[jmorse]

Various comments inline, but this looks like the right direction and correct. A serious awkwardness is that we're adding an extra level of indirection to absolutely everything, which is painful, but it's fundamental to what variadic variable locations are. One thing that helps this is the loc_indices filter iterator you've added -- however that's not actually used in the patch? Please do use it, it'd eliminated numerous if conditionals!

loadInLocs is getting pretty big now -- if there's an obvious portion that can be split into a method, or a helper lambda that can be defined with less indentation, that'd help.

Adding iteration over all locations in checkInstForNewValues is awkward for performance: it doesn't happen for every MachineInstr, but there can be a _lot_ of locations when it does. And the reason it has to happen is hard to program for: tracking a value that's needed for a variable, but a half-formed variable that mustn't be given a full location yet. IIRC you were going to run this all over CTMark, were there any notable performance regressions there?

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

200–1

Insert the range perhaps? Also, isn't this a meaningful change from the prior implementation -- variables that were active at the destination used to be erased (in the overwrite), now they'll remain active. I can't remember whether this presents an issue, but is it necessary to change the behaviour?

200–1

std::replace?

201–202

Nit: const refs to Var / Properties

201–203

Could we use a SmallDenseMap to avoid the initial DenseMap heap allocation? I don't think this makes much of a difference seeing how it's out of the fast-path, and use-before-defs aren't too common.

202

Splitting hairs, IMO IsValueValid reads closer to a full sentence, is easier to read.

203

Nit: is this somewhere we can use emplace_back / std::move? Makes a difference in the rare case that the operand vector in UBD allocates, I think.

203

Similar concerns as above, do we need this to be ordered during the search, do we not need to erase all operands of the DebugVariable from ActiveMLocs?

206

Good use of auto to avoid misery; definitely wants a docucomment to explain what's being produced here though -- a range over all the LocIdx's that are made use of?

While we're at it, perhaps this class needs renaming now that it refers to more than one location? ValueWithProperties?

212

A dense map here is expensive IMO -- can we append to a vector of pair<LocIdx, DebugVariable> and erase later, or is the ordering in the loop important? Also, I get the feeling we need to erase all operands of the untracked variable from ActiveMLocs, not just the ones that have been clobbered, so could we just keep a collection of DebugVariables?

213–220

This is difficult to unpick -- could we make the two 'if' conditions early-continues instead? IMO a longer but shallower for loop is beneficial to readability.

I tried to think about how we could get rid of this, but we need to:

• Collect DILocalVariables, and
• Scan their operands to see if they're now untracked,

Which necessitates two fors. I suppose this is the cost we pay for a lazy update to the tracking list.

Also: shouldn't Op.Loc != NewLoc be the opposite, we select this variable to be erased if one of its operands was at a location that's now clobbered?

236–237

LastUseBeforeDef = std::max(LastUseBeforeDef, Num.getInst());?

240–242

I'd suggest pushing this check into recoverAsEntryValue -- then we get free checking to ensure things like clobberMloc don't try to recover things as entry values.

[StephenTozer]

In D128211#3685401, @jmorse wrote:

Various comments inline, but this looks like the right direction and correct. A serious awkwardness is that we're adding an extra level of indirection to absolutely everything, which is painful, but it's fundamental to what variadic variable locations are. One thing that helps this is the loc_indices filter iterator you've added -- however that's not actually used in the patch? Please do use it, it'd eliminated numerous if conditionals!

Of course, I wrote a nice function for it and forgot to use it - consider it used!

loadInLocs is getting pretty big now -- if there's an obvious portion that can be split into a method, or a helper lambda that can be defined with less indentation, that'd help.

Probably a good idea, I'll look to find a way to split it up a bit more.

Adding iteration over all locations in checkInstForNewValues is awkward for performance: it doesn't happen for every MachineInstr, but there can be a _lot_ of locations when it does. And the reason it has to happen is hard to program for: tracking a value that's needed for a variable, but a half-formed variable that mustn't be given a full location yet. IIRC you were going to run this all over CTMark, were there any notable performance regressions there?

w.r.t. checkInstForNewValues, it is a somewhat naive implementation - a messier but typically-faster approach would be to keep track of every instruction in the block that defines values needed by the DbgValue, not just the last one to appear. Then in checkInstForNewValues, we can just look up the locations directly to see if they still contain the values we need; most of the time I'd imagine they will, and if they don't then we can either search every location or (if it's too harsh performance-wise) simply give up. Last I checked I think there was a surprisingly low performance impact, but I'll check again to make sure it's not an error in measurement.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

200–1

I'll double check this one. To summarize: we assume the destination to have been pre-clobbered. The reason we do this instead of clobbering it here is that when there is an "identity" copy, we may 1) clobber the location Dst, 2) select a backup location for those values in Src, and 3) subsequently declare those variables to be live in Dst. This change to the logic happened in D128101; I'm not sure if this is an unnecessary change on top of that one, but I'm moderately sure I came across some case where it was an issue; I'll double check and get a test case out this time.

203

Can also be made into a vector; see comment above.

212

This could quite reasonably be a vector - the reason for using a map structure was so that we can erase all the variables for each MLoc in one go, but since we still need to make one call per LocIdx:Variable pair it's probably not worth the overhead of having the map. It could be made into a SmallDenseMap declared outside of the loop (there probably won't be any entries here most of the time) and cleared after each iteration, but the Vector is probably simpler given the lack of an "erase many" function.

Also, I get the feeling we need to erase all operands of the untracked variable from ActiveMLocs, not just the ones that have been clobbered, so could we just keep a collection of DebugVariables?

That's what this loop is doing (see comment below).

213–220

Also: shouldn't Op.Loc != NewLoc be the opposite, we select this variable to be erased if one of its operands was at a location that's now clobbered?

This is meant to erase the ActiveMLocs mappings for all of the variable's other operands after the variable is killed by the NewLoc clobber. For all the operands Op.Loc == NewLoc, we don't need the map - it's trivially solved by the line ActiveMLocs[NewLoc.asU64()].clear(). This check is to stop us manually erasing every variable one at a time from ActiveMLocs[NewLoc] when we're just going to clear the whole set anyway.

[StephenTozer]

Addressed all review comments except for the query around erasing existing locations in transferMlocs.

[StephenTozer]

Further comment: this patch doesn't have tests currently as there are no existing unit tests for transfer tracking, and there are no changes that would be visible to an MIR test. I could create a suite of transfer tracking unit tests as part of this patch, though if possible I'd prefer that not to block this patch, since it would probably involve writing tests for more behaviour than is featured in this patch alone.

[Orlando]

loadInLocs is getting pretty big now -- if there's an obvious portion that can be split into a method, or a helper lambda that can be defined with less indentation, that'd help.

Have you addressed this?

Further comment: this patch doesn't have tests currently as there are no existing unit tests for transfer tracking, and there are no changes that would be visible to an MIR test. I could create a suite of transfer tracking unit tests as part of this patch, though if possible I'd prefer that not to block this patch, since it would probably involve writing tests for more behaviour than is featured in this patch alone.

It would be reassuring to demonstrate that the feature as a whole is working with this patch in. A few llvm-lit tests for this purpose may be beneficial, or if such tests exist in other patches, mentioning them in the patch summary and in the commit message would be useful IMO.

LGTM once these comments have been addressed and on the understanding that lit tests for the not-yet-testable variadic use-before-defs are added when variadic DBG_INSTR_REF support is added.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

200–1

Did you check this?

201

Can DbgOps be a const &?

202

Incomplete comment here

[StephenTozer]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

200–1

Checked, the reason we need this change is because as of the prior changes described above, if we copy from $r10 to $r11 when both already contain the same value, when we "clobber" $r11 it is possible the variables that were live there will continue to be live there. Then, if we choose to transfer the variables that were live in $r10 to be live in $r11, we do not want to terminate the perfectly valid variables that are live in $r11.

llvm/include/llvm/ADT/STLExtras.h

OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P) {
   return std::copy_if(adl_begin(Range), adl_end(Range), Out, P);
 }
 
 template <typename R, typename OutputIt>
 OutputIt copy(R &&Range, OutputIt Out) {
   return std::copy(adl_begin(Range), adl_end(Range), Out);
 }
 
+/// Provide wrappers to std::replace_copy_if which take ranges instead of having
+/// to pass begin/end explicitly.
+template <typename R, typename OutputIt, typename UnaryPredicate, typename T>
+OutputIt replace_copy_if(R &&Range, OutputIt Out, UnaryPredicate P,
+                         const T &NewValue) {
+  return std::replace_copy_if(adl_begin(Range), adl_end(Range), Out, P,
+                              NewValue);
+}
+
+/// Provide wrappers to std::replace_copy which take ranges instead of having to
+/// pass begin/end explicitly.
+template <typename R, typename OutputIt, typename T>
+OutputIt replace_copy(R &&Range, OutputIt Out, const T &OldValue,
+                      const T &NewValue) {
+  return std::replace_copy(adl_begin(Range), adl_end(Range), Out, OldValue,
+                           NewValue);
+}
+
 /// Provide wrappers to std::move which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename OutputIt>
 OutputIt move(R &&Range, OutputIt Out) {
   return std::move(adl_begin(Range), adl_end(Range), Out);
 }
 
 /// Wrapper function around std::find to detect if an element exists

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

 public:
   /// Default construct and initialize the pass.
   InstrRefBasedLDV();
 
   LLVM_DUMP_METHOD
   void dump_mloc_transfer(const MLocTransferMap &mloc_transfer) const;
 
   bool isCalleeSaved(LocIdx L) const;
+  bool isCalleeSavedReg(Register R) const;
 
   bool hasFoldedStackStore(const MachineInstr &MI) {
     // Instruction must have a memory operand that's a stack slot, and isn't
     // aliased, meaning it's a spill from regalloc instead of a variable.
     // If it's aliased, we can't guarantee its value.
     if (!MI.hasOneMemOperand())
       return false;
     auto *MemOperand = *MI.memoperands_begin();

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
   /// we allow inserting either before or after the point: MBB != nullptr
   /// indicates it's before, otherwise after.
   struct Transfer {
     MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes
     MachineBasicBlock *MBB; /// non-null if we should insert after.
     SmallVector<MachineInstr *, 4> Insts; /// Vector of DBG_VALUEs to insert.
   };
 
-  struct LocAndProperties {
-    LocIdx Loc;
+  /// Stores the resolved operands (machine locations and constants) and
+  /// qualifying meta-information needed to construct a concrete DBG_VALUE-like
+  /// instruction.
+  struct ResolvedDbgValue {
+    SmallVector<ResolvedDbgOp> Ops;
     DbgValueProperties Properties;
+
+    ResolvedDbgValue(SmallVectorImpl<ResolvedDbgOp> &Ops,
+                     DbgValueProperties Properties)
+        : Ops(Ops.begin(), Ops.end()), Properties(Properties) {}
+
+    /// Returns all the LocIdx values used in this struct, in the order in which
+    /// they appear as operands in the debug value; may contain duplicates.
+    auto loc_indices() const {
+      return map_range(
+          make_filter_range(
+              Ops, [](const ResolvedDbgOp &Op) { return !Op.IsConst; }),
+          [](const ResolvedDbgOp &Op) { return Op.Loc; });
+    }
   };
 
   /// Collection of transfers (DBG_VALUEs) to be inserted.
   SmallVector<Transfer, 32> Transfers;
 
   /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
   /// between TransferTrackers view of variable locations and MLocTrackers. For
   /// example, MLocTracker observes all clobbers, but TransferTracker lazily
   /// does not.
   SmallVector<ValueIDNum, 32> VarLocs;
 
   /// Map from LocIdxes to which DebugVariables are based that location.
   /// Mantained while stepping through the block. Not accurate if
   /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
   DenseMap<LocIdx, SmallSet<DebugVariable, 4>> ActiveMLocs;
 
   /// Map from DebugVariable to it's current location and qualifying meta
   /// information. To be used in conjunction with ActiveMLocs to construct
   /// enough information for the DBG_VALUEs for a particular LocIdx.
-  DenseMap<DebugVariable, LocAndProperties> ActiveVLocs;
+  DenseMap<DebugVariable, ResolvedDbgValue> ActiveVLocs;
 
   /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.
   SmallVector<MachineInstr *, 4> PendingDbgValues;
 
   /// Record of a use-before-def: created when a value that's live-in to the
   /// current block isn't available in any machine location, but it will be
   /// defined in this block.
   struct UseBeforeDef {
     /// Value of this variable, def'd in block.
-    ValueIDNum ID;
+    SmallVector<DbgOp> Values;
     /// Identity of this variable.
     DebugVariable Var;
     /// Additional variable properties.
     DbgValueProperties Properties;
+    UseBeforeDef(ArrayRef<DbgOp> Values, const DebugVariable &Var,
+                 const DbgValueProperties &Properties)
+        : Values(Values.begin(), Values.end()), Var(Var),
+          Properties(Properties) {}
   };
 
   /// Map from instruction index (within the block) to the set of UseBeforeDefs
   /// that become defined at that instruction.
   DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;
 
   /// The set of variables that are in UseBeforeDefs and can become a location
   /// once the relevant value is defined. An element being erased from this
   /// collection prevents the use-before-def materializing.
   DenseSet<DebugVariable> UseBeforeDefVariables;
 
   const TargetRegisterInfo &TRI;
   const BitVector &CalleeSavedRegs;
 
   TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,
                   MachineFunction &MF, const TargetRegisterInfo &TRI,
                   const BitVector &CalleeSavedRegs, const TargetPassConfig &TPC)
       : TII(TII), MTracker(MTracker), MF(MF), TRI(TRI),
         CalleeSavedRegs(CalleeSavedRegs) {
     TLI = MF.getSubtarget().getTargetLowering();
     auto &TM = TPC.getTM<TargetMachine>();
     ShouldEmitDebugEntryValues = TM.Options.ShouldEmitDebugEntryValues();
   }
 
+  bool isCalleeSaved(LocIdx L) {
+    unsigned Reg = MTracker->LocIdxToLocID[L];
+    if (Reg >= MTracker->NumRegs)
+      return false;
+    for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
+      if (CalleeSavedRegs.test(*RAI))
+        return true;
+    return false;
+  };
+
+  /// For a variable \p Var with the live-in value \p Value, attempts to resolve
+  /// the DbgValue to a concrete DBG_VALUE, emitting that value and loading the
+  /// tracking information to track Var throughout the block.
+  /// \p ValueToLoc is a map containing the best known location for every
+  ///    ValueIDNum that Value may use.
+  /// \p MBB is the basic block that we are loading the live-in value for.
+  /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to
+  ///    determine the values used by Value.
+  void loadVarInloc(MachineBasicBlock &MBB, DbgOpIDMap &DbgOpStore,
+                    const DenseMap<ValueIDNum, LocIdx> &ValueToLoc,
+                    DebugVariable Var, DbgValue Value) {
+    SmallVector<DbgOp> DbgOps;
+    SmallVector<ResolvedDbgOp> ResolvedDbgOps;
+    bool IsValueValid = true;
+    unsigned LastUseBeforeDef = 0;
+
+    // If every value used by the incoming DbgValue is available at block
+    // entry, ResolvedDbgOps will contain the machine locations/constants for
+    // those values and will be used to emit a debug location.
+    // If one or more values are not yet available, but will all be defined in
+    // this block, then LastUseBeforeDef will track the instruction index in
+    // this BB at which the last of those values is defined, DbgOps will
+    // contain the values that we will emit when we reach that instruction.
+    // If one or more values are undef or not available throughout this block,
+    // and we can't recover as an entry value, we set IsValueValid=false and
+    // skip this variable.
+    for (DbgOpID ID : Value.getDbgOpIDs()) {
+      DbgOp Op = DbgOpStore.find(ID);
+      DbgOps.push_back(Op);
+      if (ID.isUndef()) {
+        IsValueValid = false;
+        break;
+      }
+      if (ID.isConst()) {
+        ResolvedDbgOps.push_back(Op.MO);
+        continue;
+      }
+
+      // If the value has no location, we can't make a variable location.
+      const ValueIDNum &Num = Op.ID;
+      auto ValuesPreferredLoc = ValueToLoc.find(Num);
+      if (ValuesPreferredLoc->second.isIllegal()) {
+        // If it's a def that occurs in this block, register it as a
+        // use-before-def to be resolved as we step through the block.
+        // Continue processing values so that we add any other UseBeforeDef
+        // entries needed for later.
+        if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) {
+          LastUseBeforeDef = std::max(LastUseBeforeDef,
+                                      static_cast<unsigned>(Num.getInst()));
+          continue;
+        }
+        recoverAsEntryValue(Var, Value.Properties, Num);
+        IsValueValid = false;
+        break;
+      }
+
+      // Defer modifying ActiveVLocs until after we've confirmed we have a
+      // live range.
+      LocIdx M = ValuesPreferredLoc->second;
+      ResolvedDbgOps.push_back(M);
+    }
+
+    // If we cannot produce a valid value for the LiveIn value within this
+    // block, skip this variable.
+    if (!IsValueValid)
+      return;
+
+    // Add UseBeforeDef entry for the last value to be defined in this block.
+    if (LastUseBeforeDef) {
+      addUseBeforeDef(Var, Value.Properties, DbgOps,
+                      LastUseBeforeDef);
+      return;
+    }
+
+    // The LiveIn value is available at block entry, begin tracking and record
+    // the transfer.
+    for (const ResolvedDbgOp &Op : ResolvedDbgOps)
+      if (!Op.IsConst)
+        ActiveMLocs[Op.Loc].insert(Var);
+    auto NewValue = ResolvedDbgValue{ResolvedDbgOps, Value.Properties};
+    auto Result = ActiveVLocs.insert(std::make_pair(Var, NewValue));
+    if (!Result.second)
+      Result.first->second = NewValue;
+    PendingDbgValues.push_back(
+        MTracker->emitLoc(ResolvedDbgOps, Var, Value.Properties));
+  }
+
   /// Load object with live-in variable values. \p mlocs contains the live-in
   /// values in each machine location, while \p vlocs the live-in variable
   /// values. This method picks variable locations for the live-in variables,
   /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other
   /// object fields to track variable locations as we step through the block.
   /// FIXME: could just examine mloctracker instead of passing in \p mlocs?
   void
   loadInlocs(MachineBasicBlock &MBB, ValueTable &MLocs, DbgOpIDMap &DbgOpStore,
              const SmallVectorImpl<std::pair<DebugVariable, DbgValue>> &VLocs,
              unsigned NumLocs) {
     ActiveMLocs.clear();
     ActiveVLocs.clear();
     VarLocs.clear();
     VarLocs.reserve(NumLocs);
     UseBeforeDefs.clear();
     UseBeforeDefVariables.clear();
 
-    auto isCalleeSaved = [&](LocIdx L) {
-      unsigned Reg = MTracker->LocIdxToLocID[L];
-      if (Reg >= MTracker->NumRegs)
-        return false;
-      for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)
-        if (CalleeSavedRegs.test(*RAI))
-          return true;
-      return false;
-    };
-
     // Map of the preferred location for each value.
     DenseMap<ValueIDNum, LocIdx> ValueToLoc;
 
     // Initialized the preferred-location map with illegal locations, to be
     // filled in later.
-    for (const auto &VLoc : VLocs) {
-      if (VLoc.second.Kind == DbgValue::Def &&
-          !VLoc.second.getDbgOpID(0).isConst()) {
-        ValueToLoc.insert({DbgOpStore.find(VLoc.second.getDbgOpID(0)).ID,
-                           LocIdx::MakeIllegalLoc()});
-      }
-    }
+    for (const auto &VLoc : VLocs)
+      if (VLoc.second.Kind == DbgValue::Def)
+        for (DbgOpID OpID : VLoc.second.getDbgOpIDs())
+          if (!OpID.ID.IsConst)
+            ValueToLoc.insert(
+                {DbgOpStore.find(OpID).ID, LocIdx::MakeIllegalLoc()});
 
     ActiveMLocs.reserve(VLocs.size());
     ActiveVLocs.reserve(VLocs.size());
 
     // Produce a map of value numbers to the current machine locs they live
     // in. When emulating VarLocBasedImpl, there should only be one
     // location; when not, we get to pick.
     for (auto Location : MTracker->locations()) {
for (auto Location : MTracker->locations()) {
           (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
         // Insert, or overwrite if insertion failed.
         VIt->second = Idx;
       }
     }
 
     // Now map variables to their picked LocIdxes.
     for (const auto &Var : VLocs) {
-      DbgOpID OpID = Var.second.getDbgOpID(0);
-      DbgOp Op = DbgOpStore.find(OpID);
-      if (Var.second.Kind == DbgValue::Def && OpID.isConst()) {
-        PendingDbgValues.push_back(
-            emitMOLoc(Op.MO, Var.first, Var.second.Properties));
-        continue;
-      }
-
-      // If the value has no location, we can't make a variable location.
-      const ValueIDNum &Num = Op.ID;
-      auto ValuesPreferredLoc = ValueToLoc.find(Num);
-      if (ValuesPreferredLoc->second.isIllegal()) {
-        // If it's a def that occurs in this block, register it as a
-        // use-before-def to be resolved as we step through the block.
-        if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI())
-          addUseBeforeDef(Var.first, Var.second.Properties, Num);
-        else
-          recoverAsEntryValue(Var.first, Var.second.Properties, Num);
-        continue;
-      }
-
-      LocIdx M = ValuesPreferredLoc->second;
-      auto NewValue = LocAndProperties{M, Var.second.Properties};
-      auto Result = ActiveVLocs.insert(std::make_pair(Var.first, NewValue));
-      if (!Result.second)
-        Result.first->second = NewValue;
-      ActiveMLocs[M].insert(Var.first);
-      SmallVector<ResolvedDbgOp> ResolvedOps;
-      ResolvedOps.push_back(M);
-      PendingDbgValues.push_back(
-          MTracker->emitLoc(ResolvedOps, Var.first, Var.second.Properties));
+      loadVarInloc(MBB, DbgOpStore, ValueToLoc, Var.first, Var.second);
     }
     flushDbgValues(MBB.begin(), &MBB);
   }
 
   /// Record that \p Var has value \p ID, a value that becomes available
   /// later in the function.
   void addUseBeforeDef(const DebugVariable &Var,
-                       const DbgValueProperties &Properties, ValueIDNum ID) {
-    UseBeforeDef UBD = {ID, Var, Properties};
-    UseBeforeDefs[ID.getInst()].push_back(UBD);
+                       const DbgValueProperties &Properties,
+                       const SmallVectorImpl<DbgOp> &DbgOps, unsigned Inst) {
+    UseBeforeDefs[Inst].emplace_back(DbgOps, Var, Properties);
     UseBeforeDefVariables.insert(Var);
   }
 
   /// After the instruction at index \p Inst and position \p pos has been
   /// processed, check whether it defines a variable value in a use-before-def.
   /// If so, and the variable value hasn't changed since the start of the
   /// block, create a DBG_VALUE.
   void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {
     auto MIt = UseBeforeDefs.find(Inst);
     if (MIt == UseBeforeDefs.end())
       return;
 
+    // Map of values to the locations that store them for every value used by
+    // the variables that may have become available.
+    SmallDenseMap<ValueIDNum, LocIdx> ValueToLoc;
+
+    // Populate ValueToLoc with illegal default mappings for every value used by
+    // any UseBeforeDef variables for this instruction.
     for (auto &Use : MIt->second) {
-      LocIdx L = Use.ID.getLoc();
+      if (!UseBeforeDefVariables.count(Use.Var))
+        continue;
+
+      for (DbgOp &Op : Use.Values) {
+        assert(!Op.isUndef() && "UseBeforeDef erroneously created for a "
+                                "DbgValue with undef values.");
+        if (Op.IsConst)
+          continue;
+
+        ValueToLoc.insert(std::make_pair(Op.ID, LocIdx::MakeIllegalLoc()));
+      }
+    }
+
+    // Exit early if we have no DbgValues to produce.
+    if (ValueToLoc.empty())
+      return;
+
+    // Determine the best location for each desired value.
+    for (auto Location : MTracker->locations()) {
+      LocIdx Idx = Location.Idx;
+      ValueIDNum &LocValueID = Location.Value;
 
-      // If something goes very wrong, we might end up labelling a COPY
-      // instruction or similar with an instruction number, where it doesn't
-      // actually define a new value, instead it moves a value. In case this
-      // happens, discard.
-      if (MTracker->readMLoc(L) != Use.ID)
+      // Is there a variable that wants a location for this value? If not, skip.
+      auto VIt = ValueToLoc.find(LocValueID);
+      if (VIt == ValueToLoc.end())
         continue;
 
-      // If a different debug instruction defined the variable value / location
-      // since the start of the block, don't materialize this use-before-def.
+      LocIdx CurLoc = VIt->second;
+      // In order of preference, pick:
+      //  * Callee saved registers,
+      //  * Other registers,
+      //  * Spill slots.
+      if (CurLoc.isIllegal() || MTracker->isSpill(CurLoc) ||
+          (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.asU64()))) {
+        // Insert, or overwrite if insertion failed.
+        VIt->second = Idx;
+      }
+    }
+
+    // Using the map of values to locations, produce a final set of values for
+    // this variable.
+    for (auto &Use : MIt->second) {
       if (!UseBeforeDefVariables.count(Use.Var))
         continue;
 
-      SmallVector<ResolvedDbgOp> ResolvedOps;
-      ResolvedOps.push_back(L);
+      SmallVector<ResolvedDbgOp> DbgOps;
+
+      for (DbgOp &Op : Use.Values) {
+        if (Op.IsConst) {
+          DbgOps.push_back(Op.MO);
+          continue;
+        }
+        LocIdx NewLoc = ValueToLoc.find(Op.ID)->second;
+        if (NewLoc.isIllegal())
+          break;
+        DbgOps.push_back(NewLoc);
+      }
+
+      // If at least one value used by this debug value is no longer available,
+      // i.e. one of the values was killed before we finished defining all of
+      // the values used by this variable, discard.
+      if (DbgOps.size() != Use.Values.size())
+        continue;
+
+      // Otherwise, we're good to go.
       PendingDbgValues.push_back(
-          MTracker->emitLoc(ResolvedOps, Use.Var, Use.Properties));
+          MTracker->emitLoc(DbgOps, Use.Var, Use.Properties));
     }
     flushDbgValues(pos, nullptr);
   }
 
   /// Helper to move created DBG_VALUEs into Transfers collection.
   void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
     if (PendingDbgValues.size() == 0)
       return;
public:
   }
 
   /// Change a variable value after encountering a DBG_VALUE inside a block.
   void redefVar(const MachineInstr &MI) {
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
     DbgValueProperties Properties(MI);
 
-    const MachineOperand &MO = MI.getDebugOperand(0);
-
     // Ignore non-register locations, we don't transfer those.
-    if (!MO.isReg() || MO.getReg() == 0) {
+    if (MI.isUndefDebugValue() ||
+        all_of(MI.debug_operands(),
+               [](const MachineOperand &MO) { return !MO.isReg(); })) {
       auto It = ActiveVLocs.find(Var);
       if (It != ActiveVLocs.end()) {
-        ActiveMLocs[It->second.Loc].erase(Var);
+        for (LocIdx Loc : It->second.loc_indices())
+          ActiveMLocs[Loc].erase(Var);
         ActiveVLocs.erase(It);
       }
       // Any use-before-defs no longer apply.
       UseBeforeDefVariables.erase(Var);
       return;
     }
 
+    SmallVector<ResolvedDbgOp> NewLocs;
+    for (const MachineOperand &MO : MI.debug_operands()) {
+      if (MO.isReg()) {
+        // Any undef regs have already been filtered out above.
         Register Reg = MO.getReg();
         LocIdx NewLoc = MTracker->getRegMLoc(Reg);
-    redefVar(MI, Properties, NewLoc);
+        NewLocs.push_back(NewLoc);
+      } else {
+        NewLocs.push_back(MO);
+      }
+    }
+
+    redefVar(MI, Properties, NewLocs);
   }
 
   /// Handle a change in variable location within a block. Terminate the
   /// variables current location, and record the value it now refers to, so
   /// that we can detect location transfers later on.
   void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
-                Optional<LocIdx> OptNewLoc) {
+                SmallVectorImpl<ResolvedDbgOp> &NewLocs) {
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
     // Any use-before-defs no longer apply.
     UseBeforeDefVariables.erase(Var);
 
-    // Erase any previous location,
+    // Erase any previous location.
     auto It = ActiveVLocs.find(Var);
-    if (It != ActiveVLocs.end())
-      ActiveMLocs[It->second.Loc].erase(Var);
+    if (It != ActiveVLocs.end()) {
+      for (LocIdx Loc : It->second.loc_indices())
+        ActiveMLocs[Loc].erase(Var);
+    }
 
     // If there _is_ no new location, all we had to do was erase.
-    if (!OptNewLoc)
+    if (NewLocs.empty()) {
+      if (It != ActiveVLocs.end())
+        ActiveVLocs.erase(It);
       return;
-    LocIdx NewLoc = *OptNewLoc;
+    }
+
+    SmallVector<std::pair<LocIdx, DebugVariable>> LostMLocs;
+    for (ResolvedDbgOp &Op : NewLocs) {
+      if (Op.IsConst)
+        continue;
 
-    // Check whether our local copy of values-by-location in #VarLocs is out of
-    // date. Wipe old tracking data for the location if it's been clobbered in
-    // the meantime.
+      LocIdx NewLoc = Op.Loc;
+
+      // Check whether our local copy of values-by-location in #VarLocs is out
+      // of date. Wipe old tracking data for the location if it's been clobbered
+      // in the meantime.
       if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) {
         for (const auto &P : ActiveMLocs[NewLoc]) {
+          auto LostVLocIt = ActiveVLocs.find(P);
+          if (LostVLocIt != ActiveVLocs.end()) {
+            for (LocIdx Loc : LostVLocIt->second.loc_indices()) {
+              // Every active variable mapping for NewLoc will be cleared, no
+              // need to track individual variables.
+              if (Loc == NewLoc)
+                continue;
+              LostMLocs.emplace_back(Loc, P);
+            }
+          }
           ActiveVLocs.erase(P);
         }
+        for (const auto &LostMLoc : LostMLocs)
+          ActiveMLocs[LostMLoc.first].erase(LostMLoc.second);
+        LostMLocs.clear();
+        It = ActiveVLocs.find(Var);
         ActiveMLocs[NewLoc.asU64()].clear();
         VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc);
       }
 
       ActiveMLocs[NewLoc].insert(Var);
+    }
+
     if (It == ActiveVLocs.end()) {
       ActiveVLocs.insert(
-          std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
+          std::make_pair(Var, ResolvedDbgValue(NewLocs, Properties)));
     } else {
-      It->second.Loc = NewLoc;
+      It->second.Ops.assign(NewLocs);
       It->second.Properties = Properties;
     }
   }
 
   /// Account for a location \p mloc being clobbered. Examine the variable
   /// locations that will be terminated: and try to recover them by using
   /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to
   /// explicitly terminate a location if it can't be recovered.
if (!NewLoc && !MakeUndef) {
         recoverAsEntryValue(Var, Prop, OldValue);
       }
       flushDbgValues(Pos, nullptr);
       return;
     }
 
     // Examine all the variables based on this location.
     DenseSet<DebugVariable> NewMLocs;
+    // If no new location has been found, every variable that depends on this
+    // MLoc is dead, so end their existing MLoc->Var mappings as well.
+    SmallVector<std::pair<LocIdx, DebugVariable>> LostMLocs;
     for (const auto &Var : ActiveMLocIt->second) {
       auto ActiveVLocIt = ActiveVLocs.find(Var);
       // Re-state the variable location: if there's no replacement then NewLoc
       // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
       // identifying the alternative location will be emitted.
       const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;
-      SmallVector<ResolvedDbgOp> ResolvedOps;
-      if (NewLoc)
-        ResolvedOps.push_back(*NewLoc);
-      PendingDbgValues.push_back(
-          MTracker->emitLoc(ResolvedOps, Var, Properties));
+
+      // Produce the new list of debug ops - an empty list if no new location
+      // was found, or the existing list with the substitution MLoc -> NewLoc
+      // otherwise.
+      SmallVector<ResolvedDbgOp> DbgOps;
+      if (NewLoc) {
+        ResolvedDbgOp OldOp(MLoc);
+        ResolvedDbgOp NewOp(*NewLoc);
+        // Insert illegal ops to overwrite afterwards.
+        DbgOps.insert(DbgOps.begin(), ActiveVLocIt->second.Ops.size(),
+                      ResolvedDbgOp(LocIdx::MakeIllegalLoc()));
+        replace_copy(ActiveVLocIt->second.Ops, DbgOps.begin(), OldOp, NewOp);
+      }
+
+      PendingDbgValues.push_back(MTracker->emitLoc(DbgOps, Var, Properties));
 
       // Update machine locations <=> variable locations maps. Defer updating
-      // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
+      // ActiveMLocs to avoid invalidating the ActiveMLocIt iterator.
       if (!NewLoc) {
+        for (LocIdx Loc : ActiveVLocIt->second.loc_indices()) {
+          if (Loc != MLoc)
+            LostMLocs.emplace_back(Loc, Var);
+        }
         ActiveVLocs.erase(ActiveVLocIt);
       } else {
-        ActiveVLocIt->second.Loc = *NewLoc;
+        ActiveVLocIt->second.Ops = DbgOps;
         NewMLocs.insert(Var);
       }
     }
 
-    // Commit any deferred ActiveMLoc changes.
-    if (!NewMLocs.empty())
-      for (auto &Var : NewMLocs)
-        ActiveMLocs[*NewLoc].insert(Var);
+    // Remove variables from ActiveMLocs if they no longer use any other MLocs
+    // due to being killed by this clobber.
+    for (auto &LocVarIt : LostMLocs) {
+      auto LostMLocIt = ActiveMLocs.find(LocVarIt.first);
+      assert(LostMLocIt != ActiveMLocs.end() &&
+             "Variable was using this MLoc, but ActiveMLocs[MLoc] has no "
+             "entries?");
+      assert(LostMLocIt->second.contains(LocVarIt.second) &&
+             "Variable was using this MLoc, but does not appear in "
+             "ActiveMLocs?");
+      LostMLocIt->second.erase(LocVarIt.second);
+    }
 
     // We lazily track what locations have which values; if we've found a new
     // location for the clobbered value, remember it.
     if (NewLoc)
       VarLocs[NewLoc->asU64()] = OldValue;
 
     flushDbgValues(Pos, nullptr);
 
-    // Re-find ActiveMLocIt, iterator could have been invalidated.
-    ActiveMLocIt = ActiveMLocs.find(MLoc);
+    // Commit ActiveMLoc changes.
     ActiveMLocIt->second.clear();
+    if (!NewMLocs.empty())
+      for (auto &Var : NewMLocs)
+        ActiveMLocs[*NewLoc].insert(Var);
   }
 
   /// Transfer variables based on \p Src to be based on \p Dst. This handles
   /// both register copies as well as spills and restores. Creates DBG_VALUEs
   /// describing the movement.
   void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {
     // Does Src still contain the value num we expect? If not, it's been
     // clobbered in the meantime, and our variable locations are stale.
     if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))
       return;
 
     // assert(ActiveMLocs[Dst].size() == 0);
     //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
 
     // Move set of active variables from one location to another.
     auto MovingVars = ActiveMLocs[Src];
-    ActiveMLocs[Dst] = MovingVars;
+    ActiveMLocs[Dst].insert(MovingVars.begin(), MovingVars.end());
     VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
 
     // For each variable based on Src; create a location at Dst.
+    ResolvedDbgOp SrcOp(Src);
+    ResolvedDbgOp DstOp(Dst);
     for (const auto &Var : MovingVars) {
       auto ActiveVLocIt = ActiveVLocs.find(Var);
       assert(ActiveVLocIt != ActiveVLocs.end());
-      ActiveVLocIt->second.Loc = Dst;
 
-      SmallVector<ResolvedDbgOp> ResolvedOps;
-      ResolvedOps.push_back(Dst);
-      MachineInstr *MI =
-          MTracker->emitLoc(ResolvedOps, Var, ActiveVLocIt->second.Properties);
+      // Update all instances of Src in the variable's tracked values to Dst.
+      std::replace(ActiveVLocIt->second.Ops.begin(),
+                   ActiveVLocIt->second.Ops.end(), SrcOp, DstOp);
+
+      MachineInstr *MI = MTracker->emitLoc(ActiveVLocIt->second.Ops, Var,
+                                           ActiveVLocIt->second.Properties);
       PendingDbgValues.push_back(MI);
     }
     ActiveMLocs[Src].clear();
     flushDbgValues(Pos, nullptr);
 
     // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data
     // about the old location.
     if (EmulateOldLDV)
#endif
   return BuildMI(MF, DL, Desc, Indirect, MOs, Var.getVariable(), Expr);
 }
 
 /// Default construct and initialize the pass.
 InstrRefBasedLDV::InstrRefBasedLDV() = default;
 
 bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const {
   unsigned Reg = MTracker->LocIdxToLocID[L];
-  for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
+  return isCalleeSavedReg(Reg);
+}
+bool InstrRefBasedLDV::isCalleeSavedReg(Register R) const {
+  for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI)
     if (CalleeSavedRegs.test(*RAI))
       return true;
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 //            Debug Range Extension Implementation
 //===----------------------------------------------------------------------===//
bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
   if (Scope == nullptr)
     return true; // handled it; by doing nothing
 
   // For now, ignore DBG_VALUE_LISTs when extending ranges. Allow it to
   // contribute to locations in this block, but don't propagate further.
   // Interpret it like a DBG_VALUE $noreg.
   if (MI.isDebugValueList()) {
     SmallVector<DbgOpID> EmptyDebugOps;
+    SmallVector<ResolvedDbgOp> EmptyResolvedDebugOps;
     if (VTracker)
       VTracker->defVar(MI, Properties, EmptyDebugOps);
     if (TTracker)
-      TTracker->redefVar(MI, Properties, None);
+      TTracker->redefVar(MI, Properties, EmptyResolvedDebugOps);
     return true;
   }
 
-  const MachineOperand &MO = MI.getDebugOperand(0);
-
   // MLocTracker needs to know that this register is read, even if it's only
   // read by a debug inst.
+  for (const MachineOperand &MO : MI.debug_operands())
     if (MO.isReg() && MO.getReg() != 0)
       (void)MTracker->readReg(MO.getReg());
 
   // If we're preparing for the second analysis (variables), the machine value
   // locations are already solved, and we report this DBG_VALUE and the value
   // it refers to to VLocTracker.
   if (VTracker) {
     SmallVector<DbgOpID> DebugOps;
     // Feed defVar the new variable location, or if this is a DBG_VALUE $noreg,
     // feed defVar None.
     if (!MI.isUndefDebugValue()) {
+      for (const MachineOperand &MO : MI.debug_operands()) {
         // There should be no undef registers here, as we've screened for undef
         // debug values.
         if (MO.isReg()) {
           DebugOps.push_back(DbgOpStore.insert(MTracker->readReg(MO.getReg())));
         } else if (MO.isImm() || MO.isFPImm() || MO.isCImm()) {
           DebugOps.push_back(DbgOpStore.insert(MO));
         } else {
           llvm_unreachable("Unexpected debug operand type.");
         }
       }
+    }
     VTracker->defVar(MI, Properties, DebugOps);
   }
 
   // If performing final tracking of transfers, report this variable definition
   // to the TransferTracker too.
   if (TTracker)
     TTracker->redefVar(MI);
   return true;
if (NewID && ID == NewID) {
       else if (!MTracker->isSpill(*FoundLoc) &&
                !MTracker->isSpill(CurL) &&
                !isCalleeSaved(*FoundLoc) &&
                isCalleeSaved(CurL))
         FoundLoc = CurL; // Callee saved regs are longer term than normal.
     }
   }
 
+  SmallVector<ResolvedDbgOp> NewLocs;
+  if (FoundLoc)
+    NewLocs.push_back(*FoundLoc);
   // Tell transfer tracker that the variable value has changed.
-  TTracker->redefVar(MI, Properties, FoundLoc);
+  TTracker->redefVar(MI, Properties, NewLocs);
 
   // If there was a value with no location; but the value is defined in a
   // later instruction in this block, this is a block-local use-before-def.
   if (!FoundLoc && NewID && NewID->getBlock() == CurBB &&
-      NewID->getInst() > CurInst)
+      NewID->getInst() > CurInst) {
+    SmallVector<DbgOp> UseBeforeDefLocs;
+    UseBeforeDefLocs.push_back(*NewID);
     TTracker->addUseBeforeDef(V, {MI.getDebugExpression(), false, false},
-                              *NewID);
+                              UseBeforeDefLocs, NewID->getInst());
+  }
 
   // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
   // This DBG_VALUE is potentially a $noreg / undefined location, if
   // FoundLoc is None.
   // (XXX -- could morph the DBG_INSTR_REF in the future).
-  SmallVector<ResolvedDbgOp> ResolvedOps;
-  if (FoundLoc)
-    ResolvedOps.push_back(*FoundLoc);
-  MachineInstr *DbgMI = MTracker->emitLoc(ResolvedOps, V, Properties);
+  MachineInstr *DbgMI = MTracker->emitLoc(NewLocs, V, Properties);
 
   TTracker->PendingDbgValues.push_back(DbgMI);
   TTracker->flushDbgValues(MI.getIterator(), nullptr);
   return true;
 }
 
 bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
   if (!MI.isDebugPHI())

 bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
   auto DestSrc = TII->isCopyInstr(MI);
   if (!DestSrc)
     return false;
 
   const MachineOperand *DestRegOp = DestSrc->Destination;
   const MachineOperand *SrcRegOp = DestSrc->Source;
 
-  auto isCalleeSavedReg = [&](unsigned Reg) {
-    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)
-      if (CalleeSavedRegs.test(*RAI))
-        return true;
-    return false;
-  };
-
   Register SrcReg = SrcRegOp->getReg();
   Register DestReg = DestRegOp->getReg();
 
   // Ignore identity copies. Yep, these make it as far as LiveDebugValues.
   if (SrcReg == DestReg)
     return true;
 
   // For emulating VarLocBasedImpl: