[DebugInstrRef][3/3] Follow DBG_PHI instructions through LiveDebugValues.

[jmorse]

Summary

This patch reads machine value numbers from DBG_PHI instructions (marking where SSA PHIs used to be), and matches them up with DBG_INSTR_REF instructions that refer to them. Essentially they are two separate parts of a DBG_VALUE: the place to read the value (register and program position), and where the variable is assigned that value.

...Unfortunately, it's not quite that simple though.

A PHI instruction is computed by control flow -- and after we've left SSA form and run the register allocator, we are back in a scenario where values are identified by their location, like before we were in SSA form. This allows optimisations that change control flow to create and destroy PHI nodes without having to account for them. Specifically, imagine the control flow below being fed to the tail duplicator pass with a PHI node in 'C':

A     B
 \   /
  \ /
   C
  / \
 /   \
P     Q

And it folding C into the two predecessors, making:

A     B
|\   /|
| \ / | 
|  X  |
| / \ |
|/   \|
P     Q

(The X in the middle isn't a block, it's just edges). This has effectively destroyed the one PHI that happened at block C, and replaced it with two PHIs, one on entry to each of P and Q. LLVM doesn't represent this fact in any way.

This would be fatal to our attempt to track PHIs, however because we placed DBG_PHIs at the positions where the PHIs occurred, we can rely on DBG_PHIs appearing in blocks A and B, copied from C. That then gives us definition points -- and we can treat this like any other SSA problem, one made up of Defs and Uses. In this patch I've used the "Standard" LLVM utility for updating SSA form to do the same with machine value numbers.

Before the technical details, the obvious question is "Isn't that really crazy^W expensive?" I believe this is going to be necessary if we ever hope to get rid of debug instructions from being in the IR/MIR. However, I don't think the cost will be high: for a full stage2 build of clang, the number of blocks examined by the SSA updater was thus (frequency, then number of blocks):

73109 2
18636 3
 1611 4
 1059 5
  472 6
   89 7
   74 8
   38 9
   74 12
   56 14
   30 15

While the number of PHI points identified was:

63744 0
29876 1
  970 2
  632 3
   18 4
    8 5

My observation being: having to examine a large number of blocks and do a lot of accounting for solving this SSA problem is very infrequent. Thus I don't believe there will be a serious performance cost. This artifact is likely because the kind of folding that causes this situation happens very late in LLVM, and so there's a much reduced scope for crazy control flow changes.

I don't think this approach is _completely_ crazy. I'm not aware of another way to address the example above (where a PHI is transformed to be two PHIs) without a solution similar to this.

Technical details:

This patch adds another 350 lines of C++ to InstrRefBasedImpl.cpp, which is annoying. However, about 80% of it is boilerplate wrappers to feed block and value information into the SSAUpdater utility, there's very little actual logic. Clearly this file should be split up in the future, but I'd prefer to do that as part of a larger refactor (IMO, YMMV).

Everything interesting happens in the resolveDbgPHIs function. Outside of that, there's an additional instruction handler that records where DBG_PHIs are, and a small amount of code to update their values after the machine value problem is solved. DBG_INSTR_REFs that refer to values defined by DBG_PHI(s) call resolveDbgPHIs to get their machine value number. There's no other changed to the rest of InstrRevBasedLDV -- the dataflow problems don't change, only identifying inputs.

Within resolveDbgPHIs, we present the SSAUpdaterImpl utility with an "Updater" object, a collection of locations where DBG_PHIs read machine value numbers, and a collection in which to stuff new PHIs inferred. SSAUpdaterImpl then makes queries into the SSAUpdaterTraits class, using the Updater object to store state. How it actually goes about building SSA form is beyond the scope of this review; it just returns the value number to use in the block where a DBG_INSTR_REF lives.

After doing so, we have to perfom some validation. SSAUpdater isn't aware that it's working in a non-SSA environment, and so there might be register clobbers along the way that erase the determined value. We examine each PHI to see whether its desired input is actually what the block outputs. If any are wrong, then a necessary PHI is wrong, and we return None.

[jmorse]

Address the loop matter I mention at the end of the review summary -- I've convinced myself that we only need to validate very simple loops in this context, because LLVMs tail-duplicator doesn't substantially rewrite functions, it only duplicates bits of it.

I've added an extra test for finding the value of DBG_PHIs even if there's a loop in between the DBG_PHIs and their uses.

[jmorse]

(Update for a conflict with current master)

[jmorse]

Ping and refresh of this patch; I've replaced a multimap with a sorted vector, used a class to store information about seen DBG_PHIs, and twiddled some documentation.

See the main review comment, while there's tons of C++ in this patch, it's boilerplate to deploy LLVMs existing SSA Updater.

[jmorse]

Pingaty ping; note that I've uploaded some patches at D104520 that gets instruction-referencing working for aarch64, hopefully that makes these changes more accessible / useful for everyone.

[TWeaver]

Looks good to this 'not such an expert in this area' (me).

Code quality looks good minus a couple of nits. I'm unable to make a genuine assessment of the approach to solving this problem due to a lack of experience in this specific area, but it smells like compiler theory to me (thinks hard back to his comp science degree).

As this has been up for so long, and it doesn't seem to be getting much traction, I'd be happy to officially LGTM this, so long as nobody speaks up ASAP.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

3488

the uint64_t here seems to denote the number of a value in a preceding LDVSSABlock.

is there anyway we can typedef this away into something more contextual so this pairing reads better? (so long as my assumption about the intent is correct).

3490

same here again, can we do away with the uint64_6 and add a more contextual using/typedefed name instead for readability?

3745

perhaps this assumption can be asserted?

[jmorse]

Replaced the uint64_t for block incoming values with a BlockValueNum typedef -- sadly we can't use something more robust as SSAUpdater expects it to be an integer. It'll be useful to distinguish between the other competing value numbers in this file though, including the instruction number that comes in to resolveDbgPHIs.

IMO the assumption about resolved PHIs only occurring in the "original" register location of the PHI shouldn't be asserted. If LLVM does create code that violates this assumption, the safe thing to do is drop the variable location, rather than crash. It's possible we'll end up scanning for un-necessarily dropped locations in the future and decide to develop it further.

~

(Insert suspicious eyes here) On the landing front, given the review; that this is all hidden behind the -fexperimental-debug-variable-locations flag; and all the source in the file was originally written by me anyway;, I'll press ahead with landing shortly. This patch was fairly niche anyway, and none of it is going to be exposed to "real" users without some very thorough testing first.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

 ///   Entry values
 ///   Add back DEBUG statements for debugging this
 ///   Collect statistics
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/UniqueVector.h"
 #include "llvm/CodeGen/LexicalScopes.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"

 #include "llvm/InitializePasses.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TypeSize.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <functional>
 #include <queue>
 #include <tuple>
 #include <utility>
 #include <vector>
 #include <limits.h>
 #include <limits>
 
 #include "LiveDebugValues.h"
 
 using namespace llvm;
 
+// SSAUpdaterImple sets DEBUG_TYPE, change it.
+#undef DEBUG_TYPE
 #define DEBUG_TYPE "livedebugvalues"
 
 // Act more like the VarLoc implementation, by propagating some locations too
 // far and ignoring some transfers.
 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
                                    cl::desc("Act like old LiveDebugValues did"),
                                    cl::init(false));
 
private:
 
   /// Vector (per block) of a collection (inner smallvector) of live-ins.
   /// Used as the result type for the variable value dataflow problem.
   using LiveInsT = SmallVector<SmallVector<VarAndLoc, 8>, 8>;
 
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
+  const MachineFrameInfo *MFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
   TargetPassConfig *TPC;
 
   /// Object to track machine locations as we step through a block. Could
   /// probably be a field rather than a pointer, as it's always used.
   MLocTracker *MTracker;
 
private:
 
   /// Pair of MachineInstr, and its 1-based offset into the containing block.
   using InstAndNum = std::pair<const MachineInstr *, unsigned>;
   /// Map from debug instruction number to the MachineInstr labelled with that
   /// number, and its location within the function. Used to transform
   /// instruction numbers in DBG_INSTR_REFs into machine value numbers.
   std::map<uint64_t, InstAndNum> DebugInstrNumToInstr;
 
+  /// Record of where we observed a DBG_PHI instruction.
+  class DebugPHIRecord {
+  public:
+    uint64_t InstrNum;      ///< Instruction number of this DBG_PHI.
+    MachineBasicBlock *MBB; ///< Block where DBG_PHI occurred.
+    ValueIDNum ValueRead;   ///< The value number read by the DBG_PHI.
+    LocIdx ReadLoc;         ///< Register/Stack location the DBG_PHI reads.
+
+    operator unsigned() const { return InstrNum; }
+  };
+
+  /// Map from instruction numbers defined by DBG_PHIs to a record of what that
+  /// DBG_PHI read and where. Populated and edited during the machine value
+  /// location problem -- we use LLVMs SSA Updater to fix changes by
+  /// optimizations that destroy PHI instructions.
+  SmallVector<DebugPHIRecord, 32> DebugPHINumToValue;
+
   // Map of overlapping variable fragments.
   OverlapMap OverlapFragments;
   VarToFragments SeenFragments;
 
   /// Tests whether this instruction is a spill to a stack slot.
   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
 
   /// Decide if @MI is a spill instruction and return true if it is. We use 2
private:
   Optional<SpillLoc> isRestoreInstruction(const MachineInstr &MI,
                                           MachineFunction *MF, unsigned &Reg);
 
   /// Given a spill instruction, extract the register and offset used to
   /// address the spill slot in a target independent way.
   SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI);
 
   /// Observe a single instruction while stepping through a block.
-  void process(MachineInstr &MI);
+  void process(MachineInstr &MI, ValueIDNum **MLiveOuts = nullptr,
+               ValueIDNum **MLiveIns = nullptr);
 
   /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
   /// \returns true if MI was recognized and processed.
   bool transferDebugValue(const MachineInstr &MI);
 
   /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
   /// \returns true if MI was recognized and processed.
-  bool transferDebugInstrRef(MachineInstr &MI);
+  bool transferDebugInstrRef(MachineInstr &MI, ValueIDNum **MLiveOuts,
+                             ValueIDNum **MLiveIns);
+
+  /// Stores value-information about where this PHI occurred, and what
+  /// instruction number is associated with it.
+  /// \returns true if MI was recognized and processed.
+  bool transferDebugPHI(MachineInstr &MI);
 
   /// Examines whether \p MI is copy instruction, and notifies trackers.
   /// \returns true if MI was recognized and processed.
   bool transferRegisterCopy(MachineInstr &MI);
 
   /// Examines whether \p MI is stack spill or restore  instruction, and
   /// notifies trackers. \returns true if MI was recognized and processed.
   bool transferSpillOrRestoreInst(MachineInstr &MI);
 
   /// Examines \p MI for any registers that it defines, and notifies trackers.
   void transferRegisterDef(MachineInstr &MI);
 
   /// Copy one location to the other, accounting for movement of subregisters
   /// too.
   void performCopy(Register Src, Register Dst);
 
   void accumulateFragmentMap(MachineInstr &MI);
 
+  /// Determine the machine value number referred to by (potentially several)
+  /// DBG_PHI instructions. Block duplication and tail folding can duplicate
+  /// DBG_PHIs, shifting the position where values in registers merge, and
+  /// forming another mini-ssa problem to solve.
+  /// \p Here the position of a DBG_INSTR_REF seeking a machine value number
+  /// \p InstrNum Debug instruction number defined by DBG_PHI instructions.
+  /// \returns The machine value number at position Here, or None.
+  Optional<ValueIDNum> resolveDbgPHIs(MachineFunction &MF,
+                                      ValueIDNum **MLiveOuts,
+                                      ValueIDNum **MLiveIns, MachineInstr &Here,
+                                      uint64_t InstrNum);
+
   /// Step through the function, recording register definitions and movements
   /// in an MLocTracker. Convert the observations into a per-block transfer
   /// function in \p MLocTransfer, suitable for using with the machine value
   /// location dataflow problem.
   void
   produceMLocTransferFunction(MachineFunction &MF,
                               SmallVectorImpl<MLocTransferMap> &MLocTransfer,
                               unsigned MaxNumBlocks);
private:
   /// Given the solutions to the two dataflow problems, machine value locations
   /// in \p MInLocs and live-in variable values in \p SavedLiveIns, runs the
   /// TransferTracker class over the function to produce live-in and transfer
   /// DBG_VALUEs, then inserts them. Groups of DBG_VALUEs are inserted in the
   /// order given by AllVarsNumbering -- this could be any stable order, but
   /// right now "order of appearence in function, when explored in RPO", so
   /// that we can compare explictly against VarLocBasedImpl.
   void emitLocations(MachineFunction &MF, LiveInsT SavedLiveIns,
-                     ValueIDNum **MInLocs,
+                     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
                      DenseMap<DebugVariable, unsigned> &AllVarsNumbering);
 
   /// Boilerplate computation of some initial sets, artifical blocks and
   /// RPOT block ordering.
   void initialSetup(MachineFunction &MF);
 
   bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override;
 
bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
 
   // If performing final tracking of transfers, report this variable definition
   // to the TransferTracker too.
   if (TTracker)
     TTracker->redefVar(MI);
   return true;
 }
 
-bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
+bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
+                                             ValueIDNum **MLiveOuts,
+                                             ValueIDNum **MLiveIns) {
   if (!MI.isDebugRef())
     return false;
 
   // Only handle this instruction when we are building the variable value
   // transfer function.
   if (!VTracker)
     return false;
 
while (Sub != MF.DebugValueSubstitutions.end()) {
     Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
   }
 
   // Default machine value number is <None> -- if no instruction defines
   // the corresponding value, it must have been optimized out.
   Optional<ValueIDNum> NewID = None;
 
   // Try to lookup the instruction number, and find the machine value number
-  // that it defines.
+  // that it defines. It could be an instruction, or a PHI.
   auto InstrIt = DebugInstrNumToInstr.find(InstNo);
+  auto PHIIt = std::lower_bound(DebugPHINumToValue.begin(),
+                                DebugPHINumToValue.end(), InstNo);
   if (InstrIt != DebugInstrNumToInstr.end()) {
     const MachineInstr &TargetInstr = *InstrIt->second.first;
     uint64_t BlockNo = TargetInstr.getParent()->getNumber();
 
     // Pick out the designated operand.
     assert(OpNo < TargetInstr.getNumOperands());
     const MachineOperand &MO = TargetInstr.getOperand(OpNo);
 
     // Today, this can only be a register.
     assert(MO.isReg() && MO.isDef());
 
     unsigned LocID = MTracker->getLocID(MO.getReg(), false);
     LocIdx L = MTracker->LocIDToLocIdx[LocID];
     NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
+  } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
+    // It's actually a PHI value. Which value it is might not be obvious, use
+    // the resolver helper to find out.
+    NewID = resolveDbgPHIs(*MI.getParent()->getParent(), MLiveOuts, MLiveIns,
+                           MI, InstNo);
   }
 
   // We, we have a value number or None. Tell the variable value tracker about
   // it. The rest of this LiveDebugValues implementation acts exactly the same
   // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
   // aren't immediately available).
   DbgValueProperties Properties(Expr, false);
   VTracker->defVar(MI, Properties, NewID);
bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
 
   // 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).
   MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
   TTracker->PendingDbgValues.push_back(DbgMI);
   TTracker->flushDbgValues(MI.getIterator(), nullptr);
+  return true;
+}
+
+bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {
+  if (!MI.isDebugPHI())
+    return false;
+
+  // Analyse these only when solving the machine value location problem.
+  if (VTracker || TTracker)
+    return true;
+
+  // First operand is the value location, either a stack slot or register.
+  // Second is the debug instruction number of the original PHI.
+  const MachineOperand &MO = MI.getOperand(0);
+  unsigned InstrNum = MI.getOperand(1).getImm();
+
+  if (MO.isReg()) {
+    // The value is whatever's currently in the register. Read and record it,
+    // to be analysed later.
+    Register Reg = MO.getReg();
+    ValueIDNum Num = MTracker->readReg(Reg);
+    auto PHIRec = DebugPHIRecord(
+        {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
+    DebugPHINumToValue.push_back(PHIRec);
+  } else {
+    // The value is whatever's in this stack slot.
+    assert(MO.isFI());
+    unsigned FI = MO.getIndex();
+
+    // If the stack slot is dead, then this was optimized away.
+    // FIXME: stack slot colouring should account for slots that get merged.
+    if (MFI->isDeadObjectIndex(FI))
+      return true;
+
+    // Identify this spill slot.
+    Register Base;
+    StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
+    SpillLoc SL = {Base, Offs};
+    Optional<ValueIDNum> Num = MTracker->readSpill(SL);
+
+    if (!Num)
+      // Nothing ever writes to this slot. Curious, but nothing we can do.
+      return true;
+
+    // Record this DBG_PHI for later analysis.
+    auto DbgPHI = DebugPHIRecord(
+        {InstrNum, MI.getParent(), *Num, *MTracker->getSpillMLoc(SL)});
+    DebugPHINumToValue.push_back(DbgPHI);
+  }
 
   return true;
 }
 
 void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
   // Meta Instructions do not affect the debug liveness of any register they
   // define.
   if (MI.isImplicitDef()) {
if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
              "Previously seen var fragment has no vector of overlaps");
       ASeenFragmentsOverlaps->second.push_back(ThisFragment);
     }
   }
 
   AllSeenFragments.insert(ThisFragment);
 }
 
-void InstrRefBasedLDV::process(MachineInstr &MI) {
+void InstrRefBasedLDV::process(MachineInstr &MI, ValueIDNum **MLiveOuts,
+                               ValueIDNum **MLiveIns) {
   // Try to interpret an MI as a debug or transfer instruction. Only if it's
   // none of these should we interpret it's register defs as new value
   // definitions.
   if (transferDebugValue(MI))
     return;
-  if (transferDebugInstrRef(MI))
+  if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))
+    return;
+  if (transferDebugPHI(MI))
     return;
   if (transferRegisterCopy(MI))
     return;
   if (transferSpillOrRestoreInst(MI))
     return;
   transferRegisterDef(MI);
 }
 
for (auto &P : mloc_transfer) {
     std::string foo = MTracker->LocIdxToName(P.first);
     std::string bar = MTracker->IDAsString(P.second);
     dbgs() << "Loc " << foo << " --> " << bar << "\n";
   }
 }
 #endif
 
 void InstrRefBasedLDV::emitLocations(
-    MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MInLocs,
-    DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
+    MachineFunction &MF, LiveInsT SavedLiveIns, ValueIDNum **MOutLocs,
+    ValueIDNum **MInLocs, DenseMap<DebugVariable, unsigned> &AllVarsNumbering) {
   TTracker = new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs);
   unsigned NumLocs = MTracker->getNumLocs();
 
   // For each block, load in the machine value locations and variable value
   // live-ins, then step through each instruction in the block. New DBG_VALUEs
   // to be inserted will be created along the way.
   for (MachineBasicBlock &MBB : MF) {
     unsigned bbnum = MBB.getNumber();
     MTracker->reset();
     MTracker->loadFromArray(MInLocs[bbnum], bbnum);
     TTracker->loadInlocs(MBB, MInLocs[bbnum], SavedLiveIns[MBB.getNumber()],
                          NumLocs);
 
     CurBB = bbnum;
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       TTracker->checkInstForNewValues(CurInst, MI.getIterator());
       ++CurInst;
     }
   }
 
   // We have to insert DBG_VALUEs in a consistent order, otherwise they appeaer
   // in DWARF in different orders. Use the order that they appear when walking
   // through each block / each instruction, stored in AllVarsNumbering.
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
 
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
   this->TPC = TPC;
 
   TRI = MF.getSubtarget().getRegisterInfo();
   TII = MF.getSubtarget().getInstrInfo();
   TFI = MF.getSubtarget().getFrameLowering();
   TFI->getCalleeSaves(MF, CalleeSavedRegs);
+  MFI = &MF.getFrameInfo();
   LS.initialize(MF);
 
   MTracker =
       new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());
   VTracker = nullptr;
   TTracker = nullptr;
 
   SmallVector<MLocTransferMap, 32> MLocTransfer;
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   }
 
   // Solve the machine value dataflow problem using the MLocTransfer function,
   // storing the computed live-ins / live-outs into the array-of-arrays. We use
   // both live-ins and live-outs for decision making in the variable value
   // dataflow problem.
   mlocDataflow(MInLocs, MOutLocs, MLocTransfer);
 
+  // Patch up debug phi numbers, turning unknown block-live-in values into
+  // either live-through machine values, or PHIs.
+  for (auto &DBG_PHI : DebugPHINumToValue) {
+    // Identify unresolved block-live-ins.
+    ValueIDNum &Num = DBG_PHI.ValueRead;
+    if (!Num.isPHI())
+      continue;
+
+    unsigned BlockNo = Num.getBlock();
+    LocIdx LocNo = Num.getLoc();
+    Num = MInLocs[BlockNo][LocNo.asU64()];
+  }
+  // Later, we'll be looking up ranges of instruction numbers.
+  llvm::sort(DebugPHINumToValue);
+
   // Walk back through each block / instruction, collecting DBG_VALUE
   // instructions and recording what machine value their operands refer to.
   for (auto &OrderPair : OrderToBB) {
     MachineBasicBlock &MBB = *OrderPair.second;
     CurBB = MBB.getNumber();
     VTracker = &vlocs[CurBB];
     VTracker->MBB = &MBB;
     MTracker->loadFromArray(MInLocs[CurBB], CurBB);
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       ++CurInst;
     }
     MTracker->reset();
   }
 
   // Number all variables in the order that they appear, to be used as a stable
   // insertion order later.
   DenseMap<DebugVariable, unsigned> AllVarsNumbering;
for (auto &P : ScopeToVars) {
     vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
                  ScopeToBlocks[P.first], SavedLiveIns, MOutLocs, MInLocs,
                  vlocs);
   }
 
   // Using the computed value locations and variable values for each block,
   // create the DBG_VALUE instructions representing the extended variable
   // locations.
-  emitLocations(MF, SavedLiveIns, MInLocs, AllVarsNumbering);
+  emitLocations(MF, SavedLiveIns, MOutLocs, MInLocs, AllVarsNumbering);
 
   for (int Idx = 0; Idx < MaxNumBlocks; ++Idx) {
     delete[] MOutLocs[Idx];
     delete[] MInLocs[Idx];
   }
   delete[] MOutLocs;
   delete[] MInLocs;
 
   // Did we actually make any changes? If we created any DBG_VALUEs, then yes.
   bool Changed = TTracker->Transfers.size() != 0;
 
   delete MTracker;
   delete TTracker;
   MTracker = nullptr;
   VTracker = nullptr;
   TTracker = nullptr;
 
   ArtificialBlocks.clear();
   OrderToBB.clear();
   BBToOrder.clear();
   BBNumToRPO.clear();
   DebugInstrNumToInstr.clear();
+  DebugPHINumToValue.clear();
 
   return Changed;
 }
 
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }
+
+namespace {
+class LDVSSABlock;
+class LDVSSAUpdater;
+
+// Pick a type to identify incoming block values as we construct SSA. We
+// can't use anything more robust than an integer unfortunately, as SSAUpdater
+// expects to zero-initialize the type.
+typedef uint64_t BlockValueNum;
+
+/// Represents an SSA PHI node for the SSA updater class. Contains the block
+/// this PHI is in, the value number it would have, and the expected incoming
+/// values from parent blocks.
+class LDVSSAPhi {
+public:
+  SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;
+  LDVSSABlock *ParentBlock;
+  BlockValueNum PHIValNum;
+  LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
+      : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
+
+  LDVSSABlock *getParent() { return ParentBlock; }
+};
+
+/// Thin wrapper around a block predecessor iterator. Only difference from a
+/// normal block iterator is that it dereferences to an LDVSSABlock.
+class LDVSSABlockIterator {
+public:
+  MachineBasicBlock::pred_iterator PredIt;
+  LDVSSAUpdater &Updater;
+
+  LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,
+                      LDVSSAUpdater &Updater)
+      : PredIt(PredIt), Updater(Updater) {}
+
+  bool operator!=(const LDVSSABlockIterator &OtherIt) const {
+    return OtherIt.PredIt != PredIt;
+  }
+
+  LDVSSABlockIterator &operator++() {
+    ++PredIt;
+    return *this;
+  }
+
+  LDVSSABlock *operator*();
+};
+
+/// Thin wrapper around a block for SSA Updater interface. Necessary because
+/// we need to track the PHI value(s) that we may have observed as necessary
+/// in this block.
+class LDVSSABlock {
+public:
+  MachineBasicBlock &BB;
+  LDVSSAUpdater &Updater;
+  using PHIListT = SmallVector<LDVSSAPhi, 1>;
+  /// List of PHIs in this block. There should only ever be one.
+  PHIListT PHIList;
+
+  LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)
+      : BB(BB), Updater(Updater) {}
+
+  LDVSSABlockIterator succ_begin() {
+    return LDVSSABlockIterator(BB.succ_begin(), Updater);
+  }
+
+  LDVSSABlockIterator succ_end() {
+    return LDVSSABlockIterator(BB.succ_end(), Updater);
+  }
+
+  /// SSAUpdater has requested a PHI: create that within this block record.
+  LDVSSAPhi *newPHI(BlockValueNum Value) {
+    PHIList.emplace_back(Value, this);
+    return &PHIList.back();
+  }
+
+  /// SSAUpdater wishes to know what PHIs already exist in this block.
+  PHIListT &phis() { return PHIList; }
+};
+
+/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values
+/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to
+// SSAUpdaterTraits<LDVSSAUpdater>.
+class LDVSSAUpdater {
+public:
+  /// Map of value numbers to PHI records.
+  DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;
+  /// Map of which blocks generate Undef values -- blocks that are not
+  /// dominated by any Def.
+  DenseMap<MachineBasicBlock *, BlockValueNum> UndefMap;
+  /// Map of machine blocks to our own records of them.
+  DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;
+  /// Machine location where any PHI must occur.
+  LocIdx Loc;
+  /// Table of live-in machine value numbers for blocks / locations.
+  ValueIDNum **MLiveIns;
+
+  LDVSSAUpdater(LocIdx L, ValueIDNum **MLiveIns) : Loc(L), MLiveIns(MLiveIns) {}
+
+  void reset() {
+    PHIs.clear();
+    UndefMap.clear();
+    BlockMap.clear();
+  }
+
+  ~LDVSSAUpdater() { reset(); }
+
+  /// For a given MBB, create a wrapper block for it. Stores it in the
+  /// LDVSSAUpdater block map.
+  LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {
+    auto it = BlockMap.find(BB);
+    if (it == BlockMap.end()) {
+      BlockMap[BB] = new LDVSSABlock(*BB, *this);
+      it = BlockMap.find(BB);
+    }
+    return it->second;
+  }
+
+  /// Find the live-in value number for the given block. Looks up the value at
+  /// the PHI location on entry.
+  BlockValueNum getValue(LDVSSABlock *LDVBB) {
+    return MLiveIns[LDVBB->BB.getNumber()][Loc.asU64()].asU64();
+  }
+};
+
+LDVSSABlock *LDVSSABlockIterator::operator*() {
+  return Updater.getSSALDVBlock(*PredIt);
+}
+
+} // namespace
+
+namespace llvm {
+
+raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {
+  out << "SSALDVPHI " << PHI.PHIValNum;
+  return out;
+}
+
+/// Template specialization to give SSAUpdater access to CFG and value
+/// information. SSAUpdater calls methods in these traits, passing in the
+/// LDVSSAUpdater object, to learn about blocks and the values they define.
+/// It also provides methods to create PHI nodes and track them.
+template <> class SSAUpdaterTraits<LDVSSAUpdater> {
+public:
+  using BlkT = LDVSSABlock;
+  using ValT = BlockValueNum;
+  using PhiT = LDVSSAPhi;
+  using BlkSucc_iterator = LDVSSABlockIterator;
+
+  // Methods to access block successors -- dereferencing to our wrapper class.
+  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
+  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
+
+  /// Iterator for PHI operands.
+  class PHI_iterator {
+  private:
+    LDVSSAPhi *PHI;
+    unsigned Idx;
+
+  public:
+    explicit PHI_iterator(LDVSSAPhi *P) // begin iterator
+        : PHI(P), Idx(0) {}
+    PHI_iterator(LDVSSAPhi *P, bool) // end iterator
+        : PHI(P), Idx(PHI->IncomingValues.size()) {}
+
+    PHI_iterator &operator++() {
+      Idx++;
+      return *this;
+    }
+    bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }
+    bool operator!=(const PHI_iterator &X) const { return !operator==(X); }
+
+    BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
+
+    LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
+  };
+
+  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }
+
+  static inline PHI_iterator PHI_end(PhiT *PHI) {
+    return PHI_iterator(PHI, true);
+  }
+
+  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
+  /// vector.
+  static void FindPredecessorBlocks(LDVSSABlock *BB,
+                                    SmallVectorImpl<LDVSSABlock *> *Preds) {
+    for (MachineBasicBlock::pred_iterator PI = BB->BB.pred_begin(),
+                                          E = BB->BB.pred_end();
+         PI != E; ++PI)
+      Preds->push_back(BB->Updater.getSSALDVBlock(*PI));
+  }
+
+  /// GetUndefVal - Normally creates an IMPLICIT_DEF instruction with a new
+  /// register. For LiveDebugValues, represents a block identified as not having
+  /// any DBG_PHI predecessors.
+  static BlockValueNum GetUndefVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {
+    // Create a value number for this block -- it needs to be unique and in the
+    // "undef" collection, so that we know it's not real. Use a number
+    // representing a PHI into this block.
+    BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
+    Updater->UndefMap[&BB->BB] = Num;
+    return Num;
+  }
+
+  /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
+  /// SSAUpdater will populate it with information about incoming values. The
+  /// value number of this PHI is whatever the  machine value number problem
+  /// solution determined it to be. This includes non-phi values if SSAUpdater
+  /// tries to create a PHI where the incoming values are identical.
+  static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
+                                   LDVSSAUpdater *Updater) {
+    BlockValueNum PHIValNum = Updater->getValue(BB);
+    LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
+    Updater->PHIs[PHIValNum] = PHI;
+    return PHIValNum;
+  }
+
+  /// AddPHIOperand - Add the specified value as an operand of the PHI for
+  /// the specified predecessor block.
+  static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
+    PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
+  }
+
+  /// ValueIsPHI - Check if the instruction that defines the specified value
+  /// is a PHI instruction.
+  static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
+    auto PHIIt = Updater->PHIs.find(Val);
+    if (PHIIt == Updater->PHIs.end())
+      return nullptr;
+    return PHIIt->second;
+  }
+
+  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
+  /// operands, i.e., it was just added.
+  static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
+    LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
+    if (PHI && PHI->IncomingValues.size() == 0)
+      return PHI;
+    return nullptr;
+  }
+
+  /// GetPHIValue - For the specified PHI instruction, return the value
+  /// that it defines.
+  static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
+};
+
+} // end namespace llvm
+
+Optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(MachineFunction &MF,
+                                                      ValueIDNum **MLiveOuts,
+                                                      ValueIDNum **MLiveIns,
+                                                      MachineInstr &Here,
+                                                      uint64_t InstrNum) {
+  // Pick out records of DBG_PHI instructions that have been observed. If there
+  // are none, then we cannot compute a value number.
+  auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
+                                    DebugPHINumToValue.end(), InstrNum);
+  auto LowerIt = RangePair.first;
+  auto UpperIt = RangePair.second;
+
+  // No DBG_PHI means there can be no location.
+  if (LowerIt == UpperIt)
+    return None;
+
+  // If there's only one DBG_PHI, then that is our value number.
+  if (std::distance(LowerIt, UpperIt) == 1)
+    return LowerIt->ValueRead;
+
+  auto DBGPHIRange = make_range(LowerIt, UpperIt);
+
+  // Pick out the location (physreg, slot) where any PHIs must occur. It's
+  // technically possible for us to merge values in different registers in each
+  // block, but highly unlikely that LLVM will generate such code after register
+  // allocation.
+  LocIdx Loc = LowerIt->ReadLoc;
+
+  // We have several DBG_PHIs, and a use position (the Here inst). All each
+  // DBG_PHI does is identify a value at a program position. We can treat each
+  // DBG_PHI like it's a Def of a value, and the use position is a Use of a
+  // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
+  // determine which Def is used at the Use, and any PHIs that happen along
+  // the way.
+  // Adapted LLVM SSA Updater:
+  LDVSSAUpdater Updater(Loc, MLiveIns);
+  // Map of which Def or PHI is the current value in each block.
+  DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;
+  // Set of PHIs that we have created along the way.
+  SmallVector<LDVSSAPhi *, 8> CreatedPHIs;
+
+  // Each existing DBG_PHI is a Def'd value under this model. Record these Defs
+  // for the SSAUpdater.
+  for (const auto &DBG_PHI : DBGPHIRange) {
+    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
+    const ValueIDNum &Num = DBG_PHI.ValueRead;
+    AvailableValues.insert(std::make_pair(Block, Num.asU64()));
+  }
+
+  LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());
+  const auto &AvailIt = AvailableValues.find(HereBlock);
+  if (AvailIt != AvailableValues.end()) {
+    // Actually, we already know what the value is -- the Use is in the same
+    // block as the Def.
+    return ValueIDNum::fromU64(AvailIt->second);
+  }
+
+  // Otherwise, we must use the SSA Updater. It will identify the value number
+  // that we are to use, and the PHIs that must happen along the way.
+  SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);
+  BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));
+  ValueIDNum Result = ValueIDNum::fromU64(ResultInt);
+
+  // We have the number for a PHI, or possibly live-through value, to be used
+  // at this Use. There are a number of things we have to check about it though:
+  //  * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this
+  //    Use was not completely dominated by DBG_PHIs and we should abort.
+  //  * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that
+  //    we've left SSA form. Validate that the inputs to each PHI are the
+  //    expected values.
+  //  * Is a PHI we've created actually a merging of values, or are all the
+  //    predecessor values the same, leading to a non-PHI machine value number?
+  //    (SSAUpdater doesn't know that either). Remap validated PHIs into the
+  //    the ValidatedValues collection below to sort this out.
+  DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;
+
+  // Define all the input DBG_PHI values in ValidatedValues.
+  for (const auto &DBG_PHI : DBGPHIRange) {
+    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
+    const ValueIDNum &Num = DBG_PHI.ValueRead;
+    ValidatedValues.insert(std::make_pair(Block, Num));
+  }
+
+  // Sort PHIs to validate into RPO-order.
+  SmallVector<LDVSSAPhi *, 8> SortedPHIs;
+  for (auto &PHI : CreatedPHIs)
+    SortedPHIs.push_back(PHI);
+
+  std::sort(
+      SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *B) {
+        return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
+      });
+
+  for (auto &PHI : SortedPHIs) {
+    ValueIDNum ThisBlockValueNum =
+        MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.asU64()];
+
+    // Are all these things actually defined?
+    for (auto &PHIIt : PHI->IncomingValues) {
+      // Any undef input means DBG_PHIs didn't dominate the use point.
+      if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
+        return None;
+
+      ValueIDNum ValueToCheck;
+      ValueIDNum *BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
+
+      auto VVal = ValidatedValues.find(PHIIt.first);
+      if (VVal == ValidatedValues.end()) {
+        // We cross a loop, and this is a backedge. LLVMs tail duplication
+        // happens so late that DBG_PHI instructions should not be able to
+        // migrate into loops -- meaning we can only be live-through this
+        // loop.
+        ValueToCheck = ThisBlockValueNum;
+      } else {
+        // Does the block have as a live-out, in the location we're examining,
+        // the value that we expect? If not, it's been moved or clobbered.
+        ValueToCheck = VVal->second;
+      }
+
+      if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)
+        return None;
+    }
+
+    // Record this value as validated.
+    ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});
+  }
+
+  // All the PHIs are valid: we can return what the SSAUpdater said our value
+  // number was.
+  return Result;
+}

llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-in-ldv.mir

+# RUN: llc %s -o - -mtriple=x86_64-unknown-unknown \
+# RUN:    -experimental-debug-variable-locations -run-pass=livedebugvalues\
+# RUN:    | FileCheck %s
+#
+# Test that a DBG_INSTR_REF that refers to a DBG_PHI, will be translated into a
+# DBG_VALUE of the value read at that DBG_PHI. Same original code as
+# phi-coalescing.mir.
+# 
+--- |
+  ; ModuleID = 'phi-coalescing.mir'
+  source_filename = "test.c"
+  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"
+  
+  define dso_local i32 @foo(i64 %bar, i64 %baz) !dbg !7 {
+  entry:
+    call void @llvm.dbg.value(metadata i64 %bar, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @llvm.dbg.value(metadata i64 %baz, metadata !14, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %bar), !dbg !15
+    %add = add nsw i64 %bar, 12, !dbg !16
+    call void @llvm.dbg.value(metadata i64 %add, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add), !dbg !17
+    %call = call i64 @getlong(), !dbg !18
+    %tobool = icmp ne i64 %call, 0, !dbg !18
+    br i1 %tobool, label %if.then, label %if.end, !dbg !20
+  
+  if.then:                                          ; preds = %entry
+    %add1 = add nsw i64 %add, 1, !dbg !21
+    call void @llvm.dbg.value(metadata i64 %add1, metadata !12, metadata !DIExpression()), !dbg !13
+    br label %if.end, !dbg !22
+  
+  if.end:                                           ; preds = %if.then, %entry
+    %bar.addr.0 = phi i64 [ %add1, %if.then ], [ %add, %entry ], !dbg !13
+    call void @llvm.dbg.value(metadata i64 %bar.addr.0, metadata !12, metadata !DIExpression()), !dbg !13
+    %add2 = add nsw i64 %bar.addr.0, %baz, !dbg !23
+    call void @llvm.dbg.value(metadata i64 %add2, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add2), !dbg !24
+    %conv = trunc i64 %add2 to i32, !dbg !25
+    ret i32 %conv, !dbg !26
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.declare(metadata, metadata, metadata)
+  
+  declare dso_local void @ext(i64)
+  
+  declare dso_local i64 @getlong()
+  
+  ; 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_C99, file: !1, isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", directory: "/tmp/out.c")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!""}
+  !7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !11, !11}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+  !12 = !DILocalVariable(name: "bar", arg: 1, scope: !7, file: !1, line: 3, type: !11)
+  !13 = !DILocation(line: 0, scope: !7)
+  !14 = !DILocalVariable(name: "baz", arg: 2, scope: !7, file: !1, line: 3, type: !11)
+  !15 = !DILocation(line: 4, column: 3, scope: !7)
+  !16 = !DILocation(line: 5, column: 7, scope: !7)
+  !17 = !DILocation(line: 6, column: 3, scope: !7)
+  !18 = !DILocation(line: 8, column: 7, scope: !19)
+  !19 = distinct !DILexicalBlock(scope: !7, file: !1, line: 8, column: 7)
+  !20 = !DILocation(line: 8, column: 7, scope: !7)
+  !21 = !DILocation(line: 9, column: 9, scope: !19)
+  !22 = !DILocation(line: 9, column: 5, scope: !19)
+  !23 = !DILocation(line: 11, column: 7, scope: !7)
+  !24 = !DILocation(line: 12, column: 3, scope: !7)
+  !25 = !DILocation(line: 13, column: 10, scope: !7)
+  !26 = !DILocation(line: 13, column: 3, scope: !7)
+
+...
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi' }
+  - { reg: '$rsi' }
+frameInfo:
+  stackSize:       24
+  offsetAdjustment: -24
+  maxAlignment:    1
+  adjustsStack:    true
+  hasCalls:        true
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 16
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -24, size: 8, alignment: 8, callee-saved-register: '$rbx' }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16, callee-saved-register: '$r14' }
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi, $r14, $rbx
+  
+    frame-setup PUSH64r killed $r14, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup PUSH64r killed $rbx, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 24
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 32
+    CFI_INSTRUCTION offset $rbx, -24
+    CFI_INSTRUCTION offset $r14, -16
+    $r14 = MOV64rr $rsi
+    $rbx = MOV64rr $rdi
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !15
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 12, implicit-def $eflags, debug-location !16
+    $rdi = MOV64rr $rbx, debug-location !17
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !17
+    CALL64pcrel32 @getlong, csr_64, implicit $rsp, implicit $ssp, implicit-def $rax, debug-location !18
+    CMP64ri8 killed renamable $rax, 0, implicit-def $eflags, debug-location !18
+    JCC_1 %bb.2, 4, implicit $eflags, debug-location !20
+  
+  bb.1.if.then:
+    liveins: $rbx, $r14
+  
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 1, implicit-def $eflags, debug-location !21
+  
+  bb.2.if.end:
+    liveins: $rbx, $r14
+  
+    DBG_PHI $rbx, 1
+    $rax = COPY $rbx
+    $rbx = MOV64ri 0
+    DBG_INSTR_REF 1, 0, !12, !DIExpression(), debug-location !13
+
+    ; This sequence should mark the contents of rbx on block entry as being the
+    ; value for the variable at this DBG_INSTR_REF. We've force it to be in
+    ; $rax now, so we should see a DBG_VALUE for rax:
+    ; CHECK:      DBG_PHI $rbx, 1
+    ; CHECK-NEXT: $rax = COPY $rbx
+    ; CHECK-NEXT: $rbx = MOV64ri 0
+    ; CHECK-NEXT: DBG_INSTR_REF 1, 0
+    ; CHECK-NEXT: DBG_VALUE $rax, $noreg
+
+    $rbx = COPY $rax
+    renamable $rbx = ADD64rr killed renamable $rbx, killed renamable $r14, implicit-def $eflags, debug-location !23
+    DBG_VALUE $rbx, $noreg, !12, !DIExpression(), debug-location !13
+    $rdi = MOV64rr $rbx, debug-location !24
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !24
+    $eax = MOV32rr $ebx, implicit killed $rbx, debug-location !26
+    $rsp = frame-destroy ADD64ri8 $rsp, 8, implicit-def dead $eflags, debug-location !26
+    CFI_INSTRUCTION def_cfa_offset 24, debug-location !26
+    $rbx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !26
+    CFI_INSTRUCTION def_cfa_offset 16, debug-location !26
+    $r14 = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !26
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !26
+    RETQ implicit $eax, debug-location !26
+
+...

llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-merging-in-ldv.mir

+# RUN: llc %s -o - -mtriple=x86_64-unknown-unknown \
+# RUN:    -experimental-debug-variable-locations -run-pass=livedebugvalues \
+# RUN:    | FileCheck %s --check-prefix=CHECK
+#
+# Test that, in a scenario where tail duplication has duplicated DBG_PHI
+# instructions, we can reconstruct the value to refer to. This includes cases
+# where the DBG_PHIs refer to the same value, to values that later merge, and
+# value that become unavailable.
+--- |
+  ; ModuleID = 'before.mir'
+  source_filename = "test.c"
+  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"
+  
+  define dso_local i32 @foo(i64 %bar, i64 %baz) !dbg !7 {
+  entry:
+    call void @llvm.dbg.value(metadata i64 %bar, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @llvm.dbg.value(metadata i64 %baz, metadata !14, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %bar), !dbg !15
+    %add = add nsw i64 %bar, 12, !dbg !16
+    call void @llvm.dbg.value(metadata i64 %add, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add), !dbg !17
+    %add1 = add nsw i64 %baz, 1, !dbg !18
+    call void @llvm.dbg.value(metadata i64 %add1, metadata !14, metadata !DIExpression()), !dbg !13
+    %call = call i64 @getlong(), !dbg !19
+    %tobool = icmp ne i64 %call, 0, !dbg !19
+    br i1 %tobool, label %if.then, label %if.else, !dbg !21
+  
+  if.then:                                          ; preds = %entry
+    %add2 = add nsw i64 %add, 1, !dbg !22
+    call void @llvm.dbg.value(metadata i64 %add2, metadata !12, metadata !DIExpression()), !dbg !13
+    br label %if.end, !dbg !24
+  
+  if.else:                                          ; preds = %entry
+    %add3 = add nsw i64 %add, 2, !dbg !25
+    call void @llvm.dbg.value(metadata i64 %add3, metadata !12, metadata !DIExpression()), !dbg !13
+    br label %if.end
+  
+  if.end:                                           ; preds = %if.else, %if.then
+    %bar.addr.0 = phi i64 [ %add2, %if.then ], [ %add3, %if.else ], !dbg !27
+    call void @llvm.dbg.value(metadata i64 %bar.addr.0, metadata !12, metadata !DIExpression()), !dbg !13
+    %add4 = add nsw i64 %bar.addr.0, %add1, !dbg !28
+    call void @llvm.dbg.value(metadata i64 %add4, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add4), !dbg !29
+    %conv = trunc i64 %add4 to i32, !dbg !30
+    ret i32 %conv, !dbg !31
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.declare(metadata, metadata, metadata)
+  
+  declare dso_local void @ext(i64)
+  
+  declare dso_local i64 @getlong()
+  
+  ; 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_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", 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"}
+  !7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !11, !11}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+  !12 = !DILocalVariable(name: "bar", arg: 1, scope: !7, file: !1, line: 3, type: !11)
+  !13 = !DILocation(line: 0, scope: !7)
+  !14 = !DILocalVariable(name: "baz", arg: 2, scope: !7, file: !1, line: 3, type: !11)
+  !15 = !DILocation(line: 4, column: 3, scope: !7)
+  !16 = !DILocation(line: 5, column: 7, scope: !7)
+  !17 = !DILocation(line: 6, column: 3, scope: !7)
+  !18 = !DILocation(line: 7, column: 7, scope: !7)
+  !19 = !DILocation(line: 9, column: 7, scope: !20)
+  !20 = distinct !DILexicalBlock(scope: !7, file: !1, line: 9, column: 7)
+  !21 = !DILocation(line: 9, column: 7, scope: !7)
+  !22 = !DILocation(line: 10, column: 9, scope: !23)
+  !23 = distinct !DILexicalBlock(scope: !20, file: !1, line: 9, column: 18)
+  !24 = !DILocation(line: 11, column: 3, scope: !23)
+  !25 = !DILocation(line: 12, column: 9, scope: !26)
+  !26 = distinct !DILexicalBlock(scope: !20, file: !1, line: 11, column: 10)
+  !27 = !DILocation(line: 0, scope: !20)
+  !28 = !DILocation(line: 15, column: 7, scope: !7)
+  !29 = !DILocation(line: 16, column: 3, scope: !7)
+  !30 = !DILocation(line: 17, column: 10, scope: !7)
+  !31 = !DILocation(line: 17, column: 3, scope: !7)
+
+...
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi' }
+  - { reg: '$rsi' }
+frameInfo:
+  stackSize:       24
+  offsetAdjustment: -24
+  maxAlignment:    1
+  adjustsStack:    true
+  hasCalls:        true
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 16
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -24, size: 8, alignment: 8, callee-saved-register: '$rbx' }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16, callee-saved-register: '$r14' }
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.2, %bb.1
+    liveins: $rdi, $rsi, $r14, $rbx
+  
+    frame-setup PUSH64r killed $r14, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup PUSH64r killed $rbx, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 24
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 32
+    CFI_INSTRUCTION offset $rbx, -24
+    CFI_INSTRUCTION offset $r14, -16
+    $r14 = MOV64rr $rsi
+    $rbx = MOV64rr $rdi
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !15
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 12, implicit-def $eflags, debug-location !16
+    $rdi = MOV64rr $rbx, debug-location !17
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !17
+    renamable $r14 = ADD64ri32 killed renamable $r14, 1, implicit-def $eflags, debug-location !18
+    CALL64pcrel32 @getlong, csr_64, implicit $rsp, implicit $ssp, implicit-def $rax, debug-location !19
+    CMP64ri8 killed renamable $rax, 0, implicit-def $eflags, debug-location !19
+    JCC_1 %bb.1, 5, implicit $eflags, debug-location !21
+  
+  bb.2.if.else:
+    liveins: $rbx, $r14, $rax
+  
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 2, implicit-def $eflags, debug-location !25
+    DBG_PHI $r14, 1
+    DBG_PHI $rbx, 2
+    DBG_PHI $rax, 3
+    $rax = MOV64ri 0
+    JMP_1 %bb.3
+  
+  bb.1.if.then:
+    liveins: $rbx, $r14, $rax
+  
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 1, implicit-def $eflags, debug-location !22
+    DBG_PHI $r14, 1
+    DBG_PHI $rbx, 2
+    DBG_PHI $rax, 3
+
+  bb.3.if.end:
+    liveins: $rbx, $r14
+  
+    DBG_INSTR_REF 1, 0, !14, !DIExpression(), debug-location !13
+    DBG_INSTR_REF 2, 0, !12, !DIExpression(), debug-location !13
+    DBG_INSTR_REF 3, 0, !12, !DIExpression(), debug-location !13
+
+    ; Value number 1 is live-through the above control flow from the two
+    ; DBG_PHIs:
+    ; CHECK:       DBG_INSTR_REF 1, 0
+    ; CHECK-NEXT:  DBG_VALUE $r14
+    ;
+    ; While value number 2 has different defs that merge on entry to bb.3.
+    ; These are both in $rbx though, and we should find its location:
+    ; CHECK:       DBG_INSTR_REF 2, 0
+    ; CHECK-NEXT:  DBG_VALUE $rbx
+    ;
+    ; Value number 3 cannot be resolved because $rax is clobbered in bb.2,
+    ; meaning the merged value in bb.3 is incorrect. It should produce a
+    ; DBG_VALUE $noreg.
+    ; CHECK:       DBG_INSTR_REF 3, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg
+
+    renamable $rbx = ADD64rr killed renamable $rbx, killed renamable $r14, implicit-def $eflags, debug-location !28
+    DBG_INSTR_REF 2, 0, !12, !DIExpression(), debug-location !13
+
+    ; After clobbering rbx, the variable location should not be available.
+    ; CHECK:       DBG_INSTR_REF 2, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg
+
+    $rdi = MOV64rr $rbx, debug-location !29
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !29
+    $eax = MOV32rr $ebx, implicit killed $rbx, debug-location !31
+    $rsp = frame-destroy ADD64ri8 $rsp, 8, implicit-def dead $eflags, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 24, debug-location !31
+    $rbx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 16, debug-location !31
+    $r14 = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !31
+    RETQ implicit $eax, debug-location !31
+
+...

llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-with-loops.mir

+# RUN: llc %s -o - -mtriple=x86_64-unknown-unknown \
+# RUN:    -experimental-debug-variable-locations -run-pass=livedebugvalues \
+# RUN:    | FileCheck %s --check-prefix=CHECK
+#
+# Copy of dbg-phis-merging-in-ldv.mir, where I've added a loop in between the
+# DBG_PHI "definitions" of values, and the DBG_INSTR_REFs where they're used.
+# We should be able to traverse this obstacle.
+--- |
+  ; ModuleID = 'before.mir'
+  source_filename = "test.c"
+  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"
+  
+  define dso_local i32 @foo(i64 %bar, i64 %baz) !dbg !7 {
+  entry:
+    call void @llvm.dbg.value(metadata i64 %bar, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @llvm.dbg.value(metadata i64 %baz, metadata !14, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %bar), !dbg !15
+    %add = add nsw i64 %bar, 12, !dbg !16
+    call void @llvm.dbg.value(metadata i64 %add, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add), !dbg !17
+    %add1 = add nsw i64 %baz, 1, !dbg !18
+    call void @llvm.dbg.value(metadata i64 %add1, metadata !14, metadata !DIExpression()), !dbg !13
+    %call = call i64 @getlong(), !dbg !19
+    %tobool = icmp ne i64 %call, 0, !dbg !19
+    br i1 %tobool, label %if.then, label %if.else, !dbg !21
+  
+  if.then:                                          ; preds = %entry
+    %add2 = add nsw i64 %add, 1, !dbg !22
+    call void @llvm.dbg.value(metadata i64 %add2, metadata !12, metadata !DIExpression()), !dbg !13
+    br label %if.end, !dbg !24
+  
+  if.else:                                          ; preds = %entry
+    %add3 = add nsw i64 %add, 2, !dbg !25
+    call void @llvm.dbg.value(metadata i64 %add3, metadata !12, metadata !DIExpression()), !dbg !13
+    br label %if.end
+  
+  if.end:                                           ; preds = %if.else, %if.then
+    %bar.addr.0 = phi i64 [ %add2, %if.then ], [ %add3, %if.else ], !dbg !27
+    call void @llvm.dbg.value(metadata i64 %bar.addr.0, metadata !12, metadata !DIExpression()), !dbg !13
+    %add4 = add nsw i64 %bar.addr.0, %add1, !dbg !28
+    call void @llvm.dbg.value(metadata i64 %add4, metadata !12, metadata !DIExpression()), !dbg !13
+    call void @ext(i64 %add4), !dbg !29
+    %conv = trunc i64 %add4 to i32, !dbg !30
+    ret i32 %conv, !dbg !31
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.declare(metadata, metadata, metadata) #0
+  
+  declare dso_local void @ext(i64)
+  
+  declare dso_local i64 @getlong()
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+  
+  attributes #0 = { nounwind readnone speculatable willreturn }
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", 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"}
+  !7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 3, type: !8, scopeLine: 3, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !11, !11}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !DIBasicType(name: "long int", size: 64, encoding: DW_ATE_signed)
+  !12 = !DILocalVariable(name: "bar", arg: 1, scope: !7, file: !1, line: 3, type: !11)
+  !13 = !DILocation(line: 0, scope: !7)
+  !14 = !DILocalVariable(name: "baz", arg: 2, scope: !7, file: !1, line: 3, type: !11)
+  !15 = !DILocation(line: 4, column: 3, scope: !7)
+  !16 = !DILocation(line: 5, column: 7, scope: !7)
+  !17 = !DILocation(line: 6, column: 3, scope: !7)
+  !18 = !DILocation(line: 7, column: 7, scope: !7)
+  !19 = !DILocation(line: 9, column: 7, scope: !20)
+  !20 = distinct !DILexicalBlock(scope: !7, file: !1, line: 9, column: 7)
+  !21 = !DILocation(line: 9, column: 7, scope: !7)
+  !22 = !DILocation(line: 10, column: 9, scope: !23)
+  !23 = distinct !DILexicalBlock(scope: !20, file: !1, line: 9, column: 18)
+  !24 = !DILocation(line: 11, column: 3, scope: !23)
+  !25 = !DILocation(line: 12, column: 9, scope: !26)
+  !26 = distinct !DILexicalBlock(scope: !20, file: !1, line: 11, column: 10)
+  !27 = !DILocation(line: 0, scope: !20)
+  !28 = !DILocation(line: 15, column: 7, scope: !7)
+  !29 = !DILocation(line: 16, column: 3, scope: !7)
+  !30 = !DILocation(line: 17, column: 10, scope: !7)
+  !31 = !DILocation(line: 17, column: 3, scope: !7)
+
+...
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi' }
+  - { reg: '$rsi' }
+frameInfo:
+  stackSize:       24
+  offsetAdjustment: -24
+  maxAlignment:    1
+  adjustsStack:    true
+  hasCalls:        true
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 16
+fixedStack:
+  - { id: 0, type: spill-slot, offset: -24, size: 8, alignment: 8, callee-saved-register: '$rbx' }
+  - { id: 1, type: spill-slot, offset: -16, size: 8, alignment: 16, callee-saved-register: '$r14' }
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.2, %bb.1
+    liveins: $rdi, $rsi, $r14, $rbx
+  
+    frame-setup PUSH64r killed $r14, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup PUSH64r killed $rbx, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 24
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 32
+    CFI_INSTRUCTION offset $rbx, -24
+    CFI_INSTRUCTION offset $r14, -16
+    $r14 = MOV64rr $rsi
+    $rbx = MOV64rr $rdi
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !15
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 12, implicit-def $eflags, debug-location !16
+    $rdi = MOV64rr $rbx, debug-location !17
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !17
+    renamable $r14 = ADD64ri32 killed renamable $r14, 1, implicit-def $eflags, debug-location !18
+    CALL64pcrel32 @getlong, csr_64, implicit $rsp, implicit $ssp, implicit-def $rax, debug-location !19
+    CMP64ri8 killed renamable $rax, 0, implicit-def $eflags, debug-location !19
+    JCC_1 %bb.1, 5, implicit $eflags, debug-location !21
+  
+  bb.2.if.else:
+    liveins: $rbx, $r14, $rax
+  
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 2, implicit-def $eflags, debug-location !25
+    DBG_PHI $r14, 1
+    DBG_PHI $rbx, 2
+    DBG_PHI $rax, 3
+    $rax = MOV64ri 0
+    JMP_1 %bb.3
+  
+  bb.1.if.then:
+    liveins: $rbx, $r14, $rax
+  
+    renamable $rbx = ADD64ri32 killed renamable $rbx, 1, implicit-def $eflags, debug-location !22
+    DBG_PHI $r14, 1
+    DBG_PHI $rbx, 2
+    DBG_PHI $rax, 3
+
+  bb.3:
+    $r15 = MOV64ri 0
+    CMP64ri8 $r15, 0, implicit-def $eflags, debug-location !19
+    JCC_1 %bb.3, 5, implicit $eflags, debug-location !21
+
+  bb.4:
+    liveins: $rbx, $r14
+  
+    DBG_INSTR_REF 1, 0, !14, !DIExpression(), debug-location !13
+    DBG_INSTR_REF 2, 0, !12, !DIExpression(), debug-location !13
+    DBG_INSTR_REF 3, 0, !12, !DIExpression(), debug-location !13
+
+    ; Value number 1 is live-through the above control flow from the two
+    ; DBG_PHIs:
+    ; CHECK:       DBG_INSTR_REF 1, 0
+    ; CHECK-NEXT:  DBG_VALUE $r14
+    ;
+    ; While value number 2 has different defs that merge on entry to bb.3.
+    ; These are both in $rbx though, and we should find its location:
+    ; CHECK:       DBG_INSTR_REF 2, 0
+    ; CHECK-NEXT:  DBG_VALUE $rbx
+    ;
+    ; Value number 3 cannot be resolved because $rax is clobbered in bb.2,
+    ; meaning the merged value in bb.3 is incorrect. It should produce a
+    ; DBG_VALUE $noreg.
+    ; CHECK:       DBG_INSTR_REF 3, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg
+
+    renamable $rbx = ADD64rr killed renamable $rbx, killed renamable $r14, implicit-def $eflags, debug-location !28
+    DBG_INSTR_REF 2, 0, !12, !DIExpression(), debug-location !13
+
+    ; After clobbering rbx, the variable location should not be available.
+    ; CHECK:       DBG_INSTR_REF 2, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg
+
+    $rdi = MOV64rr $rbx, debug-location !29
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, debug-location !29
+    $eax = MOV32rr $ebx, implicit killed $rbx, debug-location !31
+    $rsp = frame-destroy ADD64ri8 $rsp, 8, implicit-def dead $eflags, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 24, debug-location !31
+    $rbx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 16, debug-location !31
+    $r14 = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !31
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !31
+    RETQ implicit $eax, debug-location !31
+
+...