Index: llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
===================================================================
--- llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
+++ llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp
@@ -148,6 +148,7 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -184,6 +185,7 @@
 #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>
@@ -199,6 +201,8 @@
 
 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
@@ -1329,6 +1333,7 @@
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
+  const MachineFrameInfo *MFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
   TargetPassConfig *TPC;
@@ -1369,6 +1374,23 @@
   /// 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;
@@ -1395,7 +1417,8 @@
   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.
@@ -1403,7 +1426,13 @@
 
   /// 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.
@@ -1422,6 +1451,18 @@
 
   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
@@ -1524,7 +1565,7 @@
   /// 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
@@ -1637,7 +1678,9 @@
   return true;
 }
 
-bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
+bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,
+                                             ValueIDNum **MLiveOuts,
+                                             ValueIDNum **MLiveIns) {
   if (!MI.isDebugRef())
     return false;
 
@@ -1679,8 +1722,10 @@
   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();
@@ -1695,6 +1740,11 @@
     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
@@ -1749,6 +1799,55 @@
   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;
 }
@@ -2121,13 +2220,16 @@
   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;
@@ -3123,8 +3225,8 @@
 #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();
 
@@ -3141,7 +3243,7 @@
     CurBB = bbnum;
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       TTracker->checkInstForNewValues(CurInst, MI.getIterator());
       ++CurInst;
     }
@@ -3219,6 +3321,7 @@
   TII = MF.getSubtarget().getInstrInfo();
   TFI = MF.getSubtarget().getFrameLowering();
   TFI->getCalleeSaves(MF, CalleeSavedRegs);
+  MFI = &MF.getFrameInfo();
   LS.initialize(MF);
 
   MTracker =
@@ -3261,6 +3364,21 @@
   // 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) {
@@ -3271,7 +3389,7 @@
     MTracker->loadFromArray(MInLocs[CurBB], CurBB);
     CurInst = 1;
     for (auto &MI : MBB) {
-      process(MI);
+      process(MI, MOutLocs, MInLocs);
       ++CurInst;
     }
     MTracker->reset();
@@ -3326,7 +3444,7 @@
   // 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];
@@ -3349,6 +3467,7 @@
   BBToOrder.clear();
   BBNumToRPO.clear();
   DebugInstrNumToInstr.clear();
+  DebugPHINumToValue.clear();
 
   return Changed;
 }
@@ -3356,3 +3475,377 @@
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }
+
+namespace {
+class LDVSSABlock;
+class LDVSSAUpdater;
+
+/// 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 *, uint64_t>, 4> IncomingValues;
+  LDVSSABlock *ParentBlock;
+  uint64_t PHIValNum;
+  LDVSSAPhi(uint64_t 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(uint64_t 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<uint64_t, LDVSSAPhi *> PHIs;
+  /// Map of which blocks generate Undef values -- blocks that are not
+  /// dominated by any Def.
+  DenseMap<MachineBasicBlock *, uint64_t> 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.
+  uint64_t 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 = uint64_t;
+  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); }
+
+    uint64_t 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 uint64_t 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.
+    uint64_t 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 uint64_t CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,
+                                 LDVSSAUpdater *Updater) {
+    uint64_t 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, uint64_t 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(uint64_t 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(uint64_t 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 uint64_t 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 *, uint64_t> 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);
+  uint64_t 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 ThisBlockValue =
+        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 = ThisBlockValue;
+      } 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, ThisBlockValue});
+  }
+
+  // All the PHIs are valid: we can return what the SSAUpdater said our value
+  // number was.
+  return Result;
+}
Index: llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-in-ldv.mir
===================================================================
--- /dev/null
+++ llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-in-ldv.mir
@@ -0,0 +1,162 @@
+# 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
+
+...
Index: llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-merging-in-ldv.mir
===================================================================
--- /dev/null
+++ llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-merging-in-ldv.mir
@@ -0,0 +1,199 @@
+# 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
+
+...
Index: llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-with-loops.mir
===================================================================
--- /dev/null
+++ llvm/test/DebugInfo/MIR/InstrRef/dbg-phis-with-loops.mir
@@ -0,0 +1,205 @@
+# 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
+
+...