[DebugInfo][InstrRef] Use PHI placement utilities for variable-value calculations

[jmorse]

Summary

This patch is very similar to D110173, but for variable values rather than machine values. This is for the second instr-ref problem, calculating the correct variable value on entry to each block. As in D110173, rather than using Jeremys incorrect lattice solution, we use the existing LLVM tooling to place PHI values at control flow merges, and then use value propagation to eliminate un-necessary ones. The only real difference with the machine-value implementation is that we must pick a location for variable PHI values, i.e. when the variable has two different values in predecessors to the block, try to find a register where those same values merge together. That's implemented in pickVPHILoc. Again, I've written a bunch of unit tests to demonstrate and stimulate what different parts of this implementation should be doing.

Into the specifics: I've moved the VLocTracker class into the InstrRefBasedImpl header, so that we can test with it. I's just a collection containing the variable-value transfer function for each block. The DbgValue class, storing the "current value "of a variable while solving, grows a "VPHI" kind to represent variable-value PHIs that haven't been eliminated (yet).

Quite a lot of vlocJoin gets deleted: we no longer try to pick the right variable value and whether there should be a PHI in this function. Instead, PHIs are pre-placed with the LLVM IDF calculator, and vlocJoin just tries to eliminate them. Picking a location for a PHI is handled immediately afterwards by calling pickVPHILoc. The transfer function evaluation doesn't change at all.

In the unit-tests, I've re-factored creation of the block layouts into their own function so that they can be shared, and re-numbered the MachineBasicBlock pointer variables to be zero based, to avoid future confusion. As with the machine-location testing, I can't guarantee the unit tests achieve wonderful coverage, but they're a lot better than nothing and should demonstrate what's supposed to be happening in various scenarios.

The regression test added used to cause an infinite loop in the old lattice arrangement, because it would whip back and forth between trying to have a PHI in $rdx then $rcx, and back again. As I'd already figured out this was basically trying to do SSA construction, it probably could have been fixed... but better to refresh everything in terms that can actually be understood.

[Orlando]

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

509

Over in D110173 I said:

I think that the tests, especially this one, would be easier to read if there was a comment mapping the block numbers to the block names used in the CFG comment at the start of each test. Or, slightly more radically, replace the integer literals with a name. E.g.

const uint64_t Entry = 0, Loop1 = ...;
LiveInRsp(Entry, 0, RspLoc);

I think this is even more desirable now with the block-layout-function refactor.

[StephenTozer]

First pass look through looks fine to me, some minor nits inline but the overall function seems correct.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

2055

2220

Unused variable?

[jmorse]

Update for review comments, labelled all the block numbers with names, adjusted comments, and deleted some now unused variables.

I've also switched the "BlockNo" field of class DbgValue to being an int rather than unsigned: MachineBasicBlock::getNumber returns a signed int, so it makes sense to store something as close to that as possible.

[StephenTozer]

LGTM

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h

 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/TargetFrameLowering.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 
 #include "LiveDebugValues.h"
 
-class VLocTracker;
 class TransferTracker;
 
 // Forward dec of unit test class, so that we can peer into the LDV object.
 class InstrRefLDVTest;
 
 namespace LiveDebugValues {
 
 class MLocTracker;

 
 /// Class recording the (high level) _value_ of a variable. Identifies either
 /// the value of the variable as a ValueIDNum, or a constant MachineOperand.
 /// This class also stores meta-information about how the value is qualified.
 /// Used to reason about variable values when performing the second
 /// (DebugVariable specific) dataflow analysis.
 class DbgValue {
 public:
-  union {
-    /// If Kind is Def, the value number that this value is based on.
-    ValueIDNum ID;
-    /// If Kind is Const, the MachineOperand defining this value.
-    MachineOperand MO;
-    /// For a NoVal DbgValue, which block it was generated in.
-    unsigned BlockNo;
-  };
+  /// If Kind is Def, the value number that this value is based on. VPHIs set
+  /// this field to EmptyValue if there is no machine-value for this VPHI, or
+  /// the corresponding machine-value if there is one.
+  Optional<MachineOperand> MO;
+  /// For a NoVal or VPHI DbgValue, which block it was generated in.
+  int BlockNo;
+
   /// Qualifiers for the ValueIDNum above.
   DbgValueProperties Properties;
 
   typedef enum {
-    Undef,    // Represents a DBG_VALUE $noreg in the transfer function only.
-    Def,      // This value is defined by an inst, or is a PHI value.
-    Const,    // A constant value contained in the MachineOperand field.
-    Proposed, // This is a tentative PHI value, which may be confirmed or
-              // invalidated later.
-    NoVal     // Empty DbgValue, generated during dataflow. BlockNo stores
-              // which block this was generated in.
+    Undef, // Represents a DBG_VALUE $noreg in the transfer function only.
+    Def,   // This value is defined by an inst, or is a PHI value.
+    Const, // A constant value contained in the MachineOperand field.
+    VPHI,  // Incoming values to BlockNo differ, those values must be joined by
+           // a PHI in this block.
+    NoVal, // Empty DbgValue indicating an unknown value. Used as initializer,
+           // before dominating blocks values are propagated in.
   } KindT;
   /// Discriminator for whether this is a constant or an in-program value.
   KindT Kind;
 
   DbgValue(const ValueIDNum &Val, const DbgValueProperties &Prop, KindT Kind)
-      : ID(Val), Properties(Prop), Kind(Kind) {
-    assert(Kind == Def || Kind == Proposed);
+      : ID(Val), MO(None), BlockNo(0), Properties(Prop), Kind(Kind) {
+    assert(Kind == Def);
   }
 
   DbgValue(unsigned BlockNo, const DbgValueProperties &Prop, KindT Kind)
-      : BlockNo(BlockNo), Properties(Prop), Kind(Kind) {
-    assert(Kind == NoVal);
+      : ID(ValueIDNum::EmptyValue), MO(None), BlockNo(BlockNo),
+        Properties(Prop), Kind(Kind) {
+    assert(Kind == NoVal || Kind == VPHI);
   }
 
   DbgValue(const MachineOperand &MO, const DbgValueProperties &Prop, KindT Kind)
-      : MO(MO), Properties(Prop), Kind(Kind) {
+      : ID(ValueIDNum::EmptyValue), MO(MO), BlockNo(0), Properties(Prop),
+        Kind(Kind) {
     assert(Kind == Const);
   }
 
   DbgValue(const DbgValueProperties &Prop, KindT Kind)
-      : Properties(Prop), Kind(Kind) {
+    : ID(ValueIDNum::EmptyValue), MO(None), BlockNo(0), Properties(Prop),
+      Kind(Kind) {
     assert(Kind == Undef &&
            "Empty DbgValue constructor must pass in Undef kind");
   }
 
 #ifndef NDEBUG
   void dump(const MLocTracker *MTrack) const;
 #endif
 
   bool operator==(const DbgValue &Other) const {
     if (std::tie(Kind, Properties) != std::tie(Other.Kind, Other.Properties))
       return false;
-    else if (Kind == Proposed && ID != Other.ID)
-      return false;
     else if (Kind == Def && ID != Other.ID)
       return false;
     else if (Kind == NoVal && BlockNo != Other.BlockNo)
       return false;
     else if (Kind == Const)
-      return MO.isIdenticalTo(Other.MO);
+      return MO->isIdenticalTo(*Other.MO);
+    else if (Kind == VPHI && BlockNo != Other.BlockNo)
+      return false;
+    else if (Kind == VPHI && ID != Other.ID)
+      return false;
 
     return true;
   }
 
   bool operator!=(const DbgValue &Other) const { return !(*this == Other); }
 };
 
 class LocIdxToIndexFunctor {
#endif
 
   /// Create a DBG_VALUE based on  machine location \p MLoc. Qualify it with the
   /// information in \pProperties, for variable Var. Don't insert it anywhere,
   /// just return the builder for it.
   MachineInstrBuilder emitLoc(Optional<LocIdx> MLoc, const DebugVariable &Var,
                               const DbgValueProperties &Properties);
 };
 
+/// Collection of DBG_VALUEs observed when traversing a block. Records each
+/// variable and the value the DBG_VALUE refers to. Requires the machine value
+/// location dataflow algorithm to have run already, so that values can be
+/// identified.
+class VLocTracker {
+public:
+  /// Map DebugVariable to the latest Value it's defined to have.
+  /// Needs to be a MapVector because we determine order-in-the-input-MIR from
+  /// the order in this container.
+  /// We only retain the last DbgValue in each block for each variable, to
+  /// determine the blocks live-out variable value. The Vars container forms the
+  /// transfer function for this block, as part of the dataflow analysis. The
+  /// movement of values between locations inside of a block is handled at a
+  /// much later stage, in the TransferTracker class.
+  MapVector<DebugVariable, DbgValue> Vars;
+  DenseMap<DebugVariable, const DILocation *> Scopes;
+  MachineBasicBlock *MBB;
+
+public:
+  VLocTracker() {}
+
+  void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
+              Optional<ValueIDNum> ID) {
+    assert(MI.isDebugValue() || MI.isDebugRef());
+    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
+                      MI.getDebugLoc()->getInlinedAt());
+    DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
+                        : DbgValue(Properties, DbgValue::Undef);
+
+    // Attempt insertion; overwrite if it's already mapped.
+    auto Result = Vars.insert(std::make_pair(Var, Rec));
+    if (!Result.second)
+      Result.first->second = Rec;
+    Scopes[Var] = MI.getDebugLoc().get();
+  }
+
+  void defVar(const MachineInstr &MI, const MachineOperand &MO) {
+    // Only DBG_VALUEs can define constant-valued variables.
+    assert(MI.isDebugValue());
+    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
+                      MI.getDebugLoc()->getInlinedAt());
+    DbgValueProperties Properties(MI);
+    DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);
+
+    // Attempt insertion; overwrite if it's already mapped.
+    auto Result = Vars.insert(std::make_pair(Var, Rec));
+    if (!Result.second)
+      Result.first->second = Rec;
+    Scopes[Var] = MI.getDebugLoc().get();
+  }
+};
+
 /// Types for recording sets of variable fragments that overlap. For a given
 /// local variable, we record all other fragments of that variable that could
 /// overlap it, to reduce search time.
 using FragmentOfVar =
     std::pair<const DILocalVariable *, DIExpression::FragmentInfo>;
 using OverlapMap =
     DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>;
 
 // XXX XXX docs
 class InstrRefBasedLDV : public LDVImpl {
-private:
+public:
   friend class ::InstrRefLDVTest;
 
   using FragmentInfo = DIExpression::FragmentInfo;
   using OptFragmentInfo = Optional<DIExpression::FragmentInfo>;
 
   // Helper while building OverlapMap, a map of all fragments seen for a given
   // DILocalVariable.
   using VarToFragments =
public:
 
   /// Type for a live-in value: the predecessor block, and its value.
   using InValueT = std::pair<MachineBasicBlock *, DbgValue *>;
 
   /// 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>;
 
+private:
   MachineDominatorTree *DomTree;
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   const MachineFrameInfo *MFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
   TargetPassConfig *TPC;
 
+  // An empty DIExpression. Used default / placeholder DbgValueProperties
+  // objects, as we can't have null expressions.
+  const DIExpression *EmptyExpr;
+
   /// 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;
 
   /// Number of the current block LiveDebugValues is stepping through.
   unsigned CurBB;
 
   /// Number of the current instruction LiveDebugValues is evaluating.
private:
   TransferTracker *TTracker;
 
   /// Blocks which are artificial, i.e. blocks which exclusively contain
   /// instructions without DebugLocs, or with line 0 locations.
   SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
 
   // Mapping of blocks to and from their RPOT order.
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
-  DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
+  DenseMap<const MachineBasicBlock *, unsigned int> BBToOrder;
   DenseMap<unsigned, unsigned> BBNumToRPO;
 
   /// 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;
private:
   /// \p InLocs. \returns two bools -- the first indicates whether a change
   /// was made, the second whether a lattice downgrade occurred. If the latter
   /// is true, revisiting this block is necessary.
   bool mlocJoin(MachineBasicBlock &MBB,
                 SmallPtrSet<const MachineBasicBlock *, 16> &Visited,
                 ValueIDNum **OutLocs, ValueIDNum *InLocs);
 
   /// Solve the variable value dataflow problem, for a single lexical scope.
-  /// Uses the algorithm from the file comment to resolve control flow joins,
-  /// although there are extra hacks, see vlocJoin. Reads the
-  /// locations of values from the \p MInLocs and \p MOutLocs arrays (see
-  /// buildMLocValueMap) and reads the variable values transfer function from
-  /// \p AllTheVlocs. Live-in and Live-out variable values are stored locally,
-  /// with the live-ins permanently stored to \p Output once the fixedpoint is
-  /// reached.
+  /// Uses the algorithm from the file comment to resolve control flow joins
+  /// using PHI placement and value propagation. Reads the locations of machine
+  /// values from the \p MInLocs and \p MOutLocs arrays (see buildMLocValueMap)
+  /// and reads the variable values transfer function from \p AllTheVlocs.
+  /// Live-in and Live-out variable values are stored locally, with the live-ins
+  /// permanently stored to \p Output once a fixedpoint is reached.
   /// \p VarsWeCareAbout contains a collection of the variables in \p Scope
   /// that we should be tracking.
-  /// \p AssignBlocks contains the set of blocks that aren't in \p Scope, but
-  /// which do contain DBG_VALUEs, which VarLocBasedImpl tracks locations
-  /// through.
-  void vlocDataflow(const LexicalScope *Scope, const DILocation *DILoc,
+  /// \p AssignBlocks contains the set of blocks that aren't in \p DILoc's
+  /// scope, but which do contain DBG_VALUEs, which VarLocBasedImpl tracks
+  /// locations through.
+  void buildVLocValueMap(const DILocation *DILoc,
                     const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
                     SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,
                     LiveInsT &Output, ValueIDNum **MOutLocs,
                     ValueIDNum **MInLocs,
                     SmallVectorImpl<VLocTracker> &AllTheVLocs);
 
-  /// Compute the live-ins to a block, considering control flow merges according
-  /// to the method in the file comment. Live out and live in variable values
-  /// are stored in \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB
-  /// are computed and stored into \p VLOCInLocs. \returns true if the live-ins
-  /// are modified.
-  /// \p InLocsT Output argument, storage for calculated live-ins.
-  /// \returns two bools -- the first indicates whether a change
-  /// was made, the second whether a lattice downgrade occurred. If the latter
-  /// is true, revisiting this block is necessary.
-  std::tuple<bool, bool>
-  vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
-           SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited,
-           unsigned BBNum, const SmallSet<DebugVariable, 4> &AllVars,
-           ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
+  /// Attempt to eliminate un-necessary PHIs on entry to a block. Examines the
+  /// live-in values coming from predecessors live-outs, and replaces any PHIs
+  /// already present in this blocks live-ins with a live-through value if the
+  /// PHI isn't needed. Live out and live in variable values are stored in
+  /// \p VLOCOutLocs and \p VLOCInLocs. The live-ins for \p MBB are computed and
+  /// stored into \p VLOCInLocs.
+  /// \p InLocsT Output argument, where calculated live-in values are also
+  ///          stored.
+  /// \returns true if any live-ins change value, either from value propagation
+  ///          or PHI elimination.
+  bool vlocJoin(MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,
+                LiveIdxT &VLOCInLocs,
+                const SmallSet<DebugVariable, 4> &AllVars,
                 SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
                 SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
                 DenseMap<DebugVariable, DbgValue> &InLocsT);
 
-  /// Continue exploration of the variable-value lattice, as explained in the
-  /// file-level comment. \p OldLiveInLocation contains the current
-  /// exploration position, from which we need to descend further. \p Values
-  /// contains the set of live-in values, \p CurBlockRPONum the RPO number of
-  /// the current block, and \p CandidateLocations a set of locations that
-  /// should be considered as PHI locations, if we reach the bottom of the
-  /// lattice. \returns true if we should downgrade; the value is the agreeing
-  /// value number in a non-backedge predecessor.
-  bool vlocDowngradeLattice(const MachineBasicBlock &MBB,
-                            const DbgValue &OldLiveInLocation,
-                            const SmallVectorImpl<InValueT> &Values,
-                            unsigned CurBlockRPONum);
-
   /// For the given block and live-outs feeding into it, try to find a
-  /// machine location where they all join. If a solution for all predecessors
-  /// can't be found, a location where all non-backedge-predecessors join
-  /// will be returned instead. While this method finds a join location, this
-  /// says nothing as to whether it should be used.
-  /// \returns Pair of value ID if found, and true when the correct value
-  /// is available on all predecessor edges, or false if it's only available
-  /// for non-backedge predecessors.
-  std::tuple<Optional<ValueIDNum>, bool>
-  pickVPHILoc(MachineBasicBlock &MBB, const DebugVariable &Var,
+  /// machine location where all the variable values join together.
+  /// \returns Value ID of a machine PHI if an appropriate one is available.
+  Optional<ValueIDNum>
+  pickVPHILoc(const MachineBasicBlock &MBB, const DebugVariable &Var,
               const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
-              ValueIDNum **MInLocs,
-              const SmallVectorImpl<MachineBasicBlock *> &BlockOrders);
+              const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders);
 
   /// 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.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

 /// spill location numbers.
 class SpillLocationNo {
 public:
   explicit SpillLocationNo(unsigned SpillNo) : SpillNo(SpillNo) {}
   unsigned SpillNo;
   unsigned id() const { return SpillNo; }
 };
 
-/// Collection of DBG_VALUEs observed when traversing a block. Records each
-/// variable and the value the DBG_VALUE refers to. Requires the machine value
-/// location dataflow algorithm to have run already, so that values can be
-/// identified.
-class VLocTracker {
-public:
-  /// Map DebugVariable to the latest Value it's defined to have.
-  /// Needs to be a MapVector because we determine order-in-the-input-MIR from
-  /// the order in this container.
-  /// We only retain the last DbgValue in each block for each variable, to
-  /// determine the blocks live-out variable value. The Vars container forms the
-  /// transfer function for this block, as part of the dataflow analysis. The
-  /// movement of values between locations inside of a block is handled at a
-  /// much later stage, in the TransferTracker class.
-  MapVector<DebugVariable, DbgValue> Vars;
-  DenseMap<DebugVariable, const DILocation *> Scopes;
-  MachineBasicBlock *MBB;
-
-public:
-  VLocTracker() {}
-
-  void defVar(const MachineInstr &MI, const DbgValueProperties &Properties,
-              Optional<ValueIDNum> ID) {
-    assert(MI.isDebugValue() || MI.isDebugRef());
-    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
-                      MI.getDebugLoc()->getInlinedAt());
-    DbgValue Rec = (ID) ? DbgValue(*ID, Properties, DbgValue::Def)
-                        : DbgValue(Properties, DbgValue::Undef);
-
-    // Attempt insertion; overwrite if it's already mapped.
-    auto Result = Vars.insert(std::make_pair(Var, Rec));
-    if (!Result.second)
-      Result.first->second = Rec;
-    Scopes[Var] = MI.getDebugLoc().get();
-  }
-
-  void defVar(const MachineInstr &MI, const MachineOperand &MO) {
-    // Only DBG_VALUEs can define constant-valued variables.
-    assert(MI.isDebugValue());
-    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
-                      MI.getDebugLoc()->getInlinedAt());
-    DbgValueProperties Properties(MI);
-    DbgValue Rec = DbgValue(MO, Properties, DbgValue::Const);
-
-    // Attempt insertion; overwrite if it's already mapped.
-    auto Result = Vars.insert(std::make_pair(Var, Rec));
-    if (!Result.second)
-      Result.first->second = Rec;
-    Scopes[Var] = MI.getDebugLoc().get();
-  }
-};
-
 /// Tracker for converting machine value locations and variable values into
 /// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs
 /// specifying block live-in locations and transfers within blocks.
 ///
 /// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
 /// and must be initialized with the set of variable values that are live-in to
 /// the block. The caller then repeatedly calls process(). TransferTracker picks
 /// out variable locations for the live-in variable values (if there _is_ a
for (auto Location : MTracker->locations()) {
           PrefLocRes.first->second = Idx;
       }
     }
 
     // Now map variables to their picked LocIdxes.
     for (auto Var : VLocs) {
       if (Var.second.Kind == DbgValue::Const) {
         PendingDbgValues.push_back(
-            emitMOLoc(Var.second.MO, Var.first, Var.second.Properties));
+            emitMOLoc(*Var.second.MO, Var.first, Var.second.Properties));
         continue;
       }
 
       // If the value has no location, we can't make a variable location.
       const ValueIDNum &Num = Var.second.ID;
       auto ValuesPreferredLoc = ValueToLoc.find(Num);
       if (ValuesPreferredLoc == ValueToLoc.end()) {
         // If it's a def that occurs in this block, register it as a

 //            Implementation
 //===----------------------------------------------------------------------===//
 
 ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};
 
 #ifndef NDEBUG
 void DbgValue::dump(const MLocTracker *MTrack) const {
   if (Kind == Const) {
-    MO.dump();
+    MO->dump();
   } else if (Kind == NoVal) {
     dbgs() << "NoVal(" << BlockNo << ")";
-  } else if (Kind == Proposed) {
-    dbgs() << "VPHI(" << MTrack->IDAsString(ID) << ")";
+  } else if (Kind == VPHI) {
+    dbgs() << "VPHI(" << BlockNo << "," << MTrack->IDAsString(ID) << ")";
   } else {
     assert(Kind == Def);
     dbgs() << MTrack->IDAsString(ID);
   }
   if (Properties.Indirect)
     dbgs() << " indir";
   if (Properties.DIExpr)
     dbgs() << " " << *Properties.DIExpr;
void InstrRefBasedLDV::BlockPHIPlacement(
   IDFCalculatorDetail::ChildrenGetterTy<MachineDomTreeBase, false> foo;
   IDFCalculatorBase<MachineDomTreeBase, false> IDF(DomTree->getBase(), foo);
 
   IDF.setLiveInBlocks(AllBlocks);
   IDF.setDefiningBlocks(DefBlocks);
   IDF.calculate(PHIBlocks);
 }
 
-bool InstrRefBasedLDV::vlocDowngradeLattice(
-    const MachineBasicBlock &MBB, const DbgValue &OldLiveInLocation,
-    const SmallVectorImpl<InValueT> &Values, unsigned CurBlockRPONum) {
-  // Ranking value preference: see file level comment, the highest rank is
-  // a plain def, followed by PHI values in reverse post-order. Numerically,
-  // we assign all defs the rank '0', all PHIs their blocks RPO number plus
-  // one, and consider the lowest value the highest ranked.
-  int OldLiveInRank = BBNumToRPO[OldLiveInLocation.ID.getBlock()] + 1;
-  if (!OldLiveInLocation.ID.isPHI())
-    OldLiveInRank = 0;
-
-  // Allow any unresolvable conflict to be over-ridden.
-  if (OldLiveInLocation.Kind == DbgValue::NoVal) {
-    // Although if it was an unresolvable conflict from _this_ block, then
-    // all other seeking of downgrades and PHIs must have failed before hand.
-    if (OldLiveInLocation.BlockNo == (unsigned)MBB.getNumber())
-      return false;
-    OldLiveInRank = INT_MIN;
-  }
-
-  auto &InValue = *Values[0].second;
-
-  if (InValue.Kind == DbgValue::Const || InValue.Kind == DbgValue::NoVal)
-    return false;
-
-  unsigned ThisRPO = BBNumToRPO[InValue.ID.getBlock()];
-  int ThisRank = ThisRPO + 1;
-  if (!InValue.ID.isPHI())
-    ThisRank = 0;
-
-  // Too far down the lattice?
-  if (ThisRPO >= CurBlockRPONum)
-    return false;
-
-  // Higher in the lattice than what we've already explored?
-  if (ThisRank <= OldLiveInRank)
-    return false;
-
-  return true;
-}
-
-std::tuple<Optional<ValueIDNum>, bool> InstrRefBasedLDV::pickVPHILoc(
-    MachineBasicBlock &MBB, const DebugVariable &Var, const LiveIdxT &LiveOuts,
-    ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
-    const SmallVectorImpl<MachineBasicBlock *> &BlockOrders) {
+Optional<ValueIDNum> InstrRefBasedLDV::pickVPHILoc(
+    const MachineBasicBlock &MBB, const DebugVariable &Var,
+    const LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
+    const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
   // Collect a set of locations from predecessor where its live-out value can
   // be found.
   SmallVector<SmallVector<LocIdx, 4>, 8> Locs;
+  SmallVector<const DbgValueProperties *, 4> Properties;
   unsigned NumLocs = MTracker->getNumLocs();
-  unsigned BackEdgesStart = 0;
 
-  for (auto p : BlockOrders) {
-    // Pick out where backedges start in the list of predecessors. Relies on
-    // BlockOrders being sorted by RPO.
-    if (BBToOrder[p] < BBToOrder[&MBB])
-      ++BackEdgesStart;
+  // No predecessors means no PHIs.
+  if (BlockOrders.empty())
+    return None;
 
-    // For each predecessor, create a new set of locations.
-    Locs.resize(Locs.size() + 1);
+  for (auto p : BlockOrders) {
     unsigned ThisBBNum = p->getNumber();
     auto LiveOutMap = LiveOuts.find(p);
     if (LiveOutMap == LiveOuts.end())
       // This predecessor isn't in scope, it must have no live-in/live-out
       // locations.
-      continue;
+      return None;
 
     auto It = LiveOutMap->second->find(Var);
     if (It == LiveOutMap->second->end())
       // There's no value recorded for this variable in this predecessor,
       // leave an empty set of locations.
-      continue;
+      return None;
 
     const DbgValue &OutVal = It->second;
 
     if (OutVal.Kind == DbgValue::Const || OutVal.Kind == DbgValue::NoVal)
       // Consts and no-values cannot have locations we can join on.
-      continue;
+      return None;
 
-    assert(OutVal.Kind == DbgValue::Proposed || OutVal.Kind == DbgValue::Def);
-    ValueIDNum ValToLookFor = OutVal.ID;
+    Properties.push_back(&OutVal.Properties);
 
+    // Create new empty vector of locations.
+    Locs.resize(Locs.size() + 1);
+
+    // If the live-in value is a def, find the locations where that value is
+    // present. Do the same for VPHIs where we know the VPHI value.
+    if (OutVal.Kind == DbgValue::Def ||
+        (OutVal.Kind == DbgValue::VPHI && OutVal.BlockNo != MBB.getNumber() &&
+         OutVal.ID != ValueIDNum::EmptyValue)) {
+      ValueIDNum ValToLookFor = OutVal.ID;
       // Search the live-outs of the predecessor for the specified value.
       for (unsigned int I = 0; I < NumLocs; ++I) {
         if (MOutLocs[ThisBBNum][I] == ValToLookFor)
           Locs.back().push_back(LocIdx(I));
       }
+    } else {
+      assert(OutVal.Kind == DbgValue::VPHI);
+      // For VPHIs where we don't know the location, we definitely can't find
+      // a join loc.
+      if (OutVal.BlockNo != MBB.getNumber())
+        return None;
+
+      // Otherwise: this is a VPHI on a backedge feeding back into itself, i.e.
+      // a value that's live-through the whole loop. (It has to be a backedge,
+      // because a block can't dominate itself). We can accept as a PHI location
+      // any location where the other predecessors agree, _and_ the machine
+      // locations feed back into themselves. Therefore, add all self-looping
+      // machine-value PHI locations.
+      for (unsigned int I = 0; I < NumLocs; ++I) {
+        ValueIDNum MPHI(MBB.getNumber(), 0, LocIdx(I));
+        if (MOutLocs[ThisBBNum][I] == MPHI)
+          Locs.back().push_back(LocIdx(I));
+      }
+    }
   }
 
-  // If there were no locations at all, return an empty result.
-  if (Locs.empty())
-    return std::tuple<Optional<ValueIDNum>, bool>(None, false);
-
-  // Lambda for seeking a common location within a range of location-sets.
-  using LocsIt = SmallVector<SmallVector<LocIdx, 4>, 8>::iterator;
-  auto SeekLocation =
-      [&Locs](llvm::iterator_range<LocsIt> SearchRange) -> Optional<LocIdx> {
-    // Starting with the first set of locations, take the intersection with
-    // subsequent sets.
-    SmallVector<LocIdx, 4> base = Locs[0];
-    for (auto &S : SearchRange) {
-      SmallVector<LocIdx, 4> new_base;
-      std::set_intersection(base.begin(), base.end(), S.begin(), S.end(),
-                            std::inserter(new_base, new_base.begin()));
-      base = new_base;
-    }
-    if (base.empty())
-      return None;
+  // We should have found locations for all predecessors, or returned.
+  assert(Locs.size() == BlockOrders.size());
+
+  // Check that all properties are the same. We can't pick a location if they're
+  // not.
+  const DbgValueProperties *Properties0 = Properties[0];
+  for (auto *Prop : Properties)
+    if (*Prop != *Properties0)
+      return None;
+
+  SmallVector<LocIdx, 4> CandidateLocs = Locs[0];
+  for (unsigned int I = 1; I < Locs.size(); ++I) {
+    auto &LocVec = Locs[I];
+    SmallVector<LocIdx, 4> NewCandidates;
+    std::set_intersection(CandidateLocs.begin(), CandidateLocs.end(),
+                          LocVec.begin(), LocVec.end(), std::inserter(NewCandidates, NewCandidates.begin()));
+    CandidateLocs = NewCandidates;
+  if (CandidateLocs.empty())
 
-    // We now have a set of LocIdxes that contain the right output value in
-    // each of the predecessors. Pick the lowest; if there's a register loc,
-    // that'll be it.
-    return *base.begin();
-  };
-
-  // Search for a common location for all predecessors. If we can't, then fall
-  // back to only finding a common location between non-backedge predecessors.
-  bool ValidForAllLocs = true;
-  auto TheLoc = SeekLocation(Locs);
-  if (!TheLoc) {
-    ValidForAllLocs = false;
-    TheLoc =
-        SeekLocation(make_range(Locs.begin(), Locs.begin() + BackEdgesStart));
-  }
-
-  if (!TheLoc)
-    return std::tuple<Optional<ValueIDNum>, bool>(None, false);
+  LocIdx L = *CandidateLocs.begin();
 
   // Return a PHI-value-number for the found location.
-  LocIdx L = *TheLoc;
   ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};
-  return std::tuple<Optional<ValueIDNum>, bool>(PHIVal, ValidForAllLocs);
+  return PHIVal;
 }
 
-std::tuple<bool, bool> InstrRefBasedLDV::vlocJoin(
+bool InstrRefBasedLDV::vlocJoin(
     MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs, LiveIdxT &VLOCInLocs,
-    SmallPtrSet<const MachineBasicBlock *, 16> *VLOCVisited, unsigned BBNum,
-    const SmallSet<DebugVariable, 4> &AllVars, ValueIDNum **MOutLocs,
-    ValueIDNum **MInLocs,
+    const SmallSet<DebugVariable, 4> &AllVars,
     SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
     SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
     DenseMap<DebugVariable, DbgValue> &InLocsT) {
-  bool DowngradeOccurred = false;
-
   // To emulate VarLocBasedImpl, process this block if it's not in scope but
   // _does_ assign a variable value. No live-ins for this scope are transferred
   // in though, so we can return immediately.
-  if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB)) {
-    if (VLOCVisited)
-      return std::tuple<bool, bool>(true, false);
-    return std::tuple<bool, bool>(false, false);
-  }
+  if (InScopeBlocks.count(&MBB) == 0 && !ArtificialBlocks.count(&MBB))
+    return false;
 
   LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");
   bool Changed = false;
 
-  // Find any live-ins computed in a prior iteration.
+  // Pick out the live-ins from prior iterations.
   auto ILSIt = VLOCInLocs.find(&MBB);
   assert(ILSIt != VLOCInLocs.end());
   auto &ILS = *ILSIt->second;
 
   // Order predecessors by RPOT order, for exploring them in that order.
   SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());
 
   auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {
     return BBToOrder[A] < BBToOrder[B];
   };
 
   llvm::sort(BlockOrders, Cmp);
 
   unsigned CurBlockRPONum = BBToOrder[&MBB];
 
-  // Force a re-visit to loop heads in the first dataflow iteration.
-  // FIXME: if we could "propose" Const values this wouldn't be needed,
-  // because they'd need to be confirmed before being emitted.
-  if (!BlockOrders.empty() &&
-      BBToOrder[BlockOrders[BlockOrders.size() - 1]] >= CurBlockRPONum &&
-      VLOCVisited)
-    DowngradeOccurred = true;
-
+  // We re-construct the live-in map each time we join. For each variable, call
+  // one of these "confirm" utilities, according to which flavour of variable
+  // value it is.
   auto ConfirmValue = [&InLocsT](const DebugVariable &DV, DbgValue VR) {
     auto Result = InLocsT.insert(std::make_pair(DV, VR));
     (void)Result;
     assert(Result.second);
   };
 
-  auto ConfirmNoVal = [&ConfirmValue, &MBB](const DebugVariable &Var, const DbgValueProperties &Properties) {
-    DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::NoVal);
-
+  auto ConfirmVPHI = [&ConfirmValue,
+                      &MBB](const DebugVariable &Var,
+                            const DbgValueProperties &Properties) {
+    DbgValue NoLocPHIVal(MBB.getNumber(), Properties, DbgValue::VPHI);
     ConfirmValue(Var, NoLocPHIVal);
   };
 
   // Attempt to join the values for each variable.
   for (auto &Var : AllVars) {
-    // Collect all the DbgValues for this variable.
+    // Collect all the incoming DbgValues for this variable, from predecessor
+    // live-out values.
     SmallVector<InValueT, 8> Values;
     bool Bail = false;
     unsigned BackEdgesStart = 0;
     for (auto p : BlockOrders) {
       // If the predecessor isn't in scope / to be explored, we'll never be
       // able to join any locations.
       if (!BlocksToExplore.contains(p)) {
         Bail = true;
         break;
       }
 
-      // Don't attempt to handle unvisited predecessors: they're implicitly
-      // "unknown"s in the lattice.
-      if (VLOCVisited && !VLOCVisited->count(p))
-        continue;
-
       // If the predecessors OutLocs is absent, there's not much we can do.
       auto OL = VLOCOutLocs.find(p);
       if (OL == VLOCOutLocs.end()) {
         Bail = true;
         break;
       }
 
       // No live-out value for this predecessor also means we can't produce
       // a joined value.
       auto VIt = OL->second->find(Var);
       if (VIt == OL->second->end()) {
         Bail = true;
         break;
       }
 
       // Keep track of where back-edges begin in the Values vector. Relies on
       // BlockOrders being sorted by RPO.
       unsigned ThisBBRPONum = BBToOrder[p];
       if (ThisBBRPONum < CurBlockRPONum)
         ++BackEdgesStart;
 
       Values.push_back(std::make_pair(p, &VIt->second));
     }
 
+    // Pick out the live-in value from last time we vlocJoin'd this block.
+    auto LiveInIt = ILS.find(Var);
+    assert(LiveInIt != ILS.end() && "Uninitialized live-in vloc?");
+    const DbgValue &OldLiveInDbgValue = LiveInIt->second;
+
     // If there were no values, or one of the predecessors couldn't have a
     // value, then give up immediately. It's not safe to produce a live-in
-    // value.
-    if (Bail || Values.size() == 0)
+    // value. Leave as whatever it was before.
+    if (Bail || Values.size() == 0) {
+      ConfirmValue(Var, OldLiveInDbgValue);
       continue;
-
-    // Enumeration identifying the current state of the predecessors values.
-    enum {
-      Unset = 0,
-      Agreed,       // All preds agree on the variable value.
-      PropDisagree, // All preds agree, but the value kind is Proposed in some.
-      BEDisagree,   // Only back-edges disagree on variable value.
-      PHINeeded,    // Non-back-edge predecessors have conflicing values.
-      NoSolution    // Conflicting Value metadata makes solution impossible.
-    } OurState = Unset;
+    }
 
     // All (non-entry) blocks have at least one non-backedge predecessor.
     // Pick the variable value from the first of these, to compare against
     // all others.
     const DbgValue &FirstVal = *Values[0].second;
-    const ValueIDNum &FirstID = FirstVal.ID;
 
-    // Scan for variable values that can't be resolved: if they have different
-    // DIExpressions, different indirectness, or are mixed constants /
+    // If the old live-in value is not a PHI then either a) no PHI is needed
+    // here, or b) we eliminated the PHI that was here. If so, we can just
+    // propagate in the first parents incoming value.
+    if (OldLiveInDbgValue.Kind != DbgValue::VPHI ||
+        OldLiveInDbgValue.BlockNo != MBB.getNumber()) {
+      ConfirmValue(Var, FirstVal);
+      continue;
+    }
+
+    // Scan for variable values that can never be resolved: if they have
+    // different DIExpressions, different indirectness, or are mixed constants /
     // non-constants.
+    bool AlwaysIncompatible = false;
     for (auto &V : Values) {
       if (V.second->Properties != FirstVal.Properties)
-        OurState = NoSolution;
+        AlwaysIncompatible = true;
+      if (V.second->Kind == DbgValue::NoVal)
+        AlwaysIncompatible = true;
       if (V.second->Kind == DbgValue::Const && FirstVal.Kind != DbgValue::Const)
-        OurState = NoSolution;
+        AlwaysIncompatible = true;
+    }
+
+    if (AlwaysIncompatible) {
+      // Leave this as a VPHI.
+      ConfirmVPHI(Var, OldLiveInDbgValue.Properties);
+      continue;
     }
 
-    // Flags diagnosing _how_ the values disagree.
-    bool NonBackEdgeDisagree = false;
-    bool DisagreeOnPHINess = false;
-    bool IDDisagree = false;
+    // Try to eliminate this PHI. Do the incoming values all agree?
     bool Disagree = false;
-    if (OurState == Unset) {
-      for (auto &V : Values) {
-        if (*V.second == FirstVal)
-          continue; // No disagreement.
 
-        Disagree = true;
-
-        // Flag whether the value number actually diagrees.
-        if (V.second->ID != FirstID)
-          IDDisagree = true;
-
-        // Distinguish whether disagreement happens in backedges or not.
-        // Relies on Values (and BlockOrders) being sorted by RPO.
-        unsigned ThisBBRPONum = BBToOrder[V.first];
-        if (ThisBBRPONum < CurBlockRPONum)
-          NonBackEdgeDisagree = true;
+      // Eliminate if a backedge feeds a VPHI back into itself.
+      if (V.second->Kind == DbgValue::VPHI &&
+          V.second->BlockNo == MBB.getNumber() &&
+          // Is this a backedge?
+          std::distance(Values.begin(), &V) >= BackEdgesStart)
+        continue;
 
-        // Is there a difference in whether the value is definite or only
-        // proposed?
-        if (V.second->Kind != FirstVal.Kind &&
-            (V.second->Kind == DbgValue::Proposed ||
-             V.second->Kind == DbgValue::Def) &&
-            (FirstVal.Kind == DbgValue::Proposed ||
-             FirstVal.Kind == DbgValue::Def))
-          DisagreeOnPHINess = true;
-      }
-
-      // Collect those flags together and determine an overall state for
-      // what extend the predecessors agree on a live-in value.
-      if (!Disagree)
-        OurState = Agreed;
-      else if (!IDDisagree && DisagreeOnPHINess)
-        OurState = PropDisagree;
-      else if (!NonBackEdgeDisagree)
-        OurState = BEDisagree;
-      else
-        OurState = PHINeeded;
+      Disagree = true;
     }
 
-    // An extra indicator: if we only disagree on whether the value is a
-    // Def, or proposed, then also flag whether that disagreement happens
-    // in backedges only.
-    bool PropOnlyInBEs = Disagree && !IDDisagree && DisagreeOnPHINess &&
-                         !NonBackEdgeDisagree && FirstVal.Kind == DbgValue::Def;
-
-    const auto &Properties = FirstVal.Properties;
-
-    auto OldLiveInIt = ILS.find(Var);
-    const DbgValue *OldLiveInLocation =
-        (OldLiveInIt != ILS.end()) ? &OldLiveInIt->second : nullptr;
-
-    bool OverRide = false;
-    if (OurState == BEDisagree && OldLiveInLocation) {
-      // Only backedges disagree: we can consider downgrading. If there was a
-      // previous live-in value, use it to work out whether the current
-      // incoming value represents a lattice downgrade or not.
-      OverRide =
-          vlocDowngradeLattice(MBB, *OldLiveInLocation, Values, CurBlockRPONum);
-    }
-
-    // Use the current state of predecessor agreement and other flags to work
-    // out what to do next. Possibilities include:
-    //  * Accept a value all predecessors agree on, or accept one that
-    //    represents a step down the exploration lattice,
-    //  * Use a PHI value number, if one can be found,
-    //  * Propose a PHI value number, and see if it gets confirmed later,
-    //  * Emit a 'NoVal' value, indicating we couldn't resolve anything.
-    if (OurState == Agreed) {
-      // Easiest solution: all predecessors agree on the variable value.
-      ConfirmValue(Var, FirstVal);
-    } else if (OurState == BEDisagree && OverRide) {
-      // Only backedges disagree, and the other predecessors have produced
-      // a new live-in value further down the exploration lattice.
-      DowngradeOccurred = true;
+    // No disagreement -> live-through value.
+    if (!Disagree) {
       ConfirmValue(Var, FirstVal);
-    } else if (OurState == PropDisagree) {
-      // Predecessors agree on value, but some say it's only a proposed value.
-      // Propagate it as proposed: unless it was proposed in this block, in
-      // which case we're able to confirm the value.
-      if (FirstID.getBlock() == (uint64_t)MBB.getNumber() && FirstID.isPHI()) {
-        ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
-      } else if (PropOnlyInBEs) {
-        // If only backedges disagree, a higher (in RPO) block confirmed this
-        // location, and we need to propagate it into this loop.
-        ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Def));
-      } else {
-        // Otherwise; a Def meeting a Proposed is still a Proposed.
-        ConfirmValue(Var, DbgValue(FirstID, Properties, DbgValue::Proposed));
-      }
-    } else if ((OurState == PHINeeded || OurState == BEDisagree)) {
-      // Predecessors disagree and can't be downgraded: this can only be
-      // solved with a PHI. Use pickVPHILoc to go look for one.
-      Optional<ValueIDNum> VPHI;
-      bool AllEdgesVPHI = false;
-      std::tie(VPHI, AllEdgesVPHI) =
-          pickVPHILoc(MBB, Var, VLOCOutLocs, MOutLocs, MInLocs, BlockOrders);
-
-      if (VPHI && AllEdgesVPHI) {
-        // There's a PHI value that's valid for all predecessors -- we can use
-        // it. If any of the non-backedge predecessors have proposed values
-        // though, this PHI is also only proposed, until the predecessors are
-        // confirmed.
-        DbgValue::KindT K = DbgValue::Def;
-        for (unsigned int I = 0; I < BackEdgesStart; ++I)
-          if (Values[I].second->Kind == DbgValue::Proposed)
-            K = DbgValue::Proposed;
-
-        ConfirmValue(Var, DbgValue(*VPHI, Properties, K));
-      } else if (VPHI) {
-        // There's a PHI value, but it's only legal for backedges. Leave this
-        // as a proposed PHI value: it might come back on the backedges,
-        // and allow us to confirm it in the future.
-        DbgValue NoBEValue = DbgValue(*VPHI, Properties, DbgValue::Proposed);
-        ConfirmValue(Var, NoBEValue);
-      } else {
-        ConfirmNoVal(Var, Properties);
-      }
-    } else {
-      // Otherwise: we don't know. Emit a "phi but no real loc" phi.
-      ConfirmNoVal(Var, Properties);
+      // Otherwise use a VPHI.
+      ConfirmVPHI(Var, FirstVal.Properties);
     }
   }
 
   // Store newly calculated in-locs into VLOCInLocs, if they've changed.
   Changed = ILS != InLocsT;
   if (Changed)
     ILS = InLocsT;
 
-  return std::tuple<bool, bool>(Changed, DowngradeOccurred);
+  return Changed;
 }
 
-void InstrRefBasedLDV::vlocDataflow(
-    const LexicalScope *Scope, const DILocation *DILoc,
+void InstrRefBasedLDV::buildVLocValueMap(const DILocation *DILoc,
     const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
     SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,
     ValueIDNum **MOutLocs, ValueIDNum **MInLocs,
     SmallVectorImpl<VLocTracker> &AllTheVLocs) {
-  // This method is much like mlocDataflow: but focuses on a single
+  // This method is much like buildMLocValueMap: but focuses on a single
   // LexicalScope at a time. Pick out a set of blocks and variables that are
   // to have their value assignments solved, then run our dataflow algorithm
   // until a fixedpoint is reached.
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist, Pending;
   SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;
 
void InstrRefBasedLDV::buildVLocValueMap(const DILocation *DILoc,
   llvm::sort(BlockOrders, Cmp);
   unsigned NumBlocks = BlockOrders.size();
 
   // Allocate some vectors for storing the live ins and live outs. Large.
   SmallVector<DenseMap<DebugVariable, DbgValue>, 32> LiveIns, LiveOuts;
   LiveIns.resize(NumBlocks);
   LiveOuts.resize(NumBlocks);
 
+  // Initialize all values to start as NoVals. This signifies "it's live
+  // through, but we don't know what it is".
+  DbgValueProperties EmptyProperties(EmptyExpr, false);
+  unsigned int BlockIdx = 0;
+  for (auto &VarMap : LiveIns) {
+    for (const DebugVariable &Var : VarsWeCareAbout)
+      VarMap.insert(
+          {Var, DbgValue(BlockIdx, EmptyProperties, DbgValue::NoVal)});
+
+    ++BlockIdx;
+  }
+
   // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
   // vlocJoin.
   LiveIdxT LiveOutIdx, LiveInIdx;
   LiveOutIdx.reserve(NumBlocks);
   LiveInIdx.reserve(NumBlocks);
   for (unsigned I = 0; I < NumBlocks; ++I) {
     LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];
     LiveInIdx[BlockOrders[I]] = &LiveIns[I];
   }
 
+  // Convert a const set to a non-const set. LexicalScopes
+  // getMachineBasicBlocks returns const MBB pointers, IDF wants mutable ones.
+  // (Neither of them mutate anything).
+  SmallPtrSet<MachineBasicBlock *, 8> MutBlocksToExplore;
+  for (const auto *MBB : BlocksToExplore)
+    MutBlocksToExplore.insert(const_cast<MachineBasicBlock*>(MBB));
+
+  // Place PHIs for variable values, using the LLVM IDF calculator.
+  for (const DebugVariable &Var : VarsWeCareAbout) {
+    // Collect the set of blocks where variables are def'd.
+    SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;
+    for (const MachineBasicBlock *ExpMBB : BlocksToExplore) {
+      auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
+      if (TransferFunc.find(Var) != TransferFunc.end())
+        DefBlocks.insert(const_cast<MachineBasicBlock *>(ExpMBB));
+    }
+
+    SmallVector<MachineBasicBlock *, 32> PHIBlocks;
+
+    // Request the set of PHIs we should insert for this variable.
+    BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks);
+
+    // Insert PHIs into the per-block live-in tables for this variable.
+    for (MachineBasicBlock *PHIMBB : PHIBlocks) {
+      unsigned BlockNo = PHIMBB->getNumber();
+      auto *BlockLiveIns = LiveInIdx[PHIMBB];
+      auto It = BlockLiveIns->find(Var);
+      assert(It != BlockLiveIns->end() && "Uninitialized live-in?");
+      It->second = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI);
+    }
+  }
+
   for (auto *MBB : BlockOrders) {
     Worklist.push(BBToOrder[MBB]);
     OnWorklist.insert(MBB);
   }
 
-  // Iterate over all the blocks we selected, propagating variable values.
+  // Iterate over all the blocks we selected, propagating variable values. This
+  // loop does two things:
+  //  * Eliminates un-necessary VPHIs in vlocJoin,
+  //  * Evaluates the blocks transfer function (i.e. variable assignments) and
+  //    stores the result to the blocks live-outs.
+  // Always evaluate the transfer function on the first iteration, and when the
+  // live-ins change thereafter.
   bool FirstTrip = true;
-  SmallPtrSet<const MachineBasicBlock *, 16> VLOCVisited;
   while (!Worklist.empty() || !Pending.empty()) {
     while (!Worklist.empty()) {
       auto *MBB = OrderToBB[Worklist.top()];
       CurBB = MBB->getNumber();
       Worklist.pop();
 
       DenseMap<DebugVariable, DbgValue> JoinedInLocs;
 
       // Join values from predecessors. Updates LiveInIdx, and writes output
       // into JoinedInLocs.
-      bool InLocsChanged, DowngradeOccurred;
-      std::tie(InLocsChanged, DowngradeOccurred) = vlocJoin(
-          *MBB, LiveOutIdx, LiveInIdx, (FirstTrip) ? &VLOCVisited : nullptr,
-          CurBB, VarsWeCareAbout, MOutLocs, MInLocs, InScopeBlocks,
-          BlocksToExplore, JoinedInLocs);
-
-      bool FirstVisit = VLOCVisited.insert(MBB).second;
-
-      // Always explore transfer function if inlocs changed, or if we've not
-      // visited this block before.
-      InLocsChanged |= FirstVisit;
-
-      // If a downgrade occurred, book us in for re-examination on the next
-      // iteration.
-      if (DowngradeOccurred && OnPending.insert(MBB).second)
-        Pending.push(BBToOrder[MBB]);
+      bool InLocsChanged;
+      InLocsChanged = vlocJoin(*MBB, LiveOutIdx, LiveInIdx,
+                               VarsWeCareAbout, InScopeBlocks, BlocksToExplore,
+                               JoinedInLocs);
+
+      SmallVector<const MachineBasicBlock *, 8> Preds;
+      for (const auto *Pred : MBB->predecessors())
+        Preds.push_back(Pred);
+
+      // Opportunistically pick a machine-value for any VPHIs starting in this
+      // block. This makes their machine-value available and propagated through
+      // all blocks by the time value propagation finishes. We can't do this any
+      // earlier as it needs to read the block live-outs.
+      for (auto &Var : VarsWeCareAbout) {
+        DbgValue &Val = JoinedInLocs.find(Var)->second;
+        if (Val.Kind != DbgValue::VPHI || Val.BlockNo != (int)CurBB)
+          continue;
+
+        // There's a small possibility that on a preceeding path, a VPHI is
+        // eliminated and transitions from VPHI-with-location to
+        // live-through-value. As a result, the selected location of any VPHI
+        // might change, so we need to re-compute it on each iteration.
+        Optional<ValueIDNum> ValueNum = pickVPHILoc(
+                  *MBB, Var, LiveOutIdx, MOutLocs, Preds);
+
+        if (ValueNum) {
+          InLocsChanged |= Val.ID != *ValueNum;
+          Val.ID = *ValueNum;
+          // FIXME: it's stupid to have two different live-in maps at this
+          // stage, one for evaluating the transfer func in, one for storage.
+          // Fix this in the future.
+          LiveInIdx[MBB]->find(Var)->second.ID = *ValueNum;
+        }
+      }
 
-      if (!InLocsChanged)
+      if (!InLocsChanged && !FirstTrip)
         continue;
 
       // Do transfer function.
       auto &VTracker = AllTheVLocs[MBB->getNumber()];
       for (auto &Transfer : VTracker.Vars) {
         // Is this var we're mangling in this scope?
         if (VarsWeCareAbout.count(Transfer.first)) {
           // Erase on empty transfer (DBG_VALUE $noreg).
           if (Transfer.second.Kind == DbgValue::Undef) {
-            JoinedInLocs.erase(Transfer.first);
+            auto InLocIt = JoinedInLocs.find(Transfer.first);
+            assert(InLocIt != JoinedInLocs.end());
+            InLocIt->second.Kind = DbgValue::NoVal;
           } else {
             // Insert new variable value; or overwrite.
             auto NewValuePair = std::make_pair(Transfer.first, Transfer.second);
             auto Result = JoinedInLocs.insert(NewValuePair);
             if (!Result.second)
               Result.first->second = Transfer.second;
           }
         }
while (!Worklist.empty() || !Pending.empty()) {
     }
     Worklist.swap(Pending);
     std::swap(OnWorklist, OnPending);
     OnPending.clear();
     assert(Pending.empty());
     FirstTrip = false;
   }
 
-  // Dataflow done. Now what? Save live-ins. Ignore any that are still marked
-  // as being variable-PHIs, because those did not have their machine-PHI
-  // value confirmed. Such variable values are places that could have been
-  // PHIs, but are not.
+  // Save live-ins to output vector. Ignore any that are still marked as being
+  // VPHIs with no location -- those are variables that we know the value of,
+  // but are not actually available in the register file.
   for (auto *MBB : BlockOrders) {
     auto &VarMap = *LiveInIdx[MBB];
     for (auto &P : VarMap) {
-      if (P.second.Kind == DbgValue::Proposed ||
-          P.second.Kind == DbgValue::NoVal)
+      if (P.second.Kind == DbgValue::NoVal)
         continue;
+      if (P.second.Kind == DbgValue::VPHI && P.second.ID == ValueIDNum::EmptyValue)
+        continue;
+      if (P.second.Kind == DbgValue::VPHI)
+        P.second.Kind = DbgValue::Def;
       Output[MBB->getNumber()].push_back(P);
     }
   }
 
   BlockOrders.clear();
   BlocksToExplore.clear();
 }
 
if (P.MBB) {
         MBB.insertAfterBundle(P.Pos, MI);
       }
     }
   }
 }
 
 void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {
   // Build some useful data structures.
+
+  LLVMContext &Context = MF.getFunction().getContext();
+  EmptyExpr = DIExpression::get(Context, {});
+
   auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
     if (const DebugLoc &DL = MI.getDebugLoc())
       return DL.getLine() != 0;
     return false;
   };
   // Collect a set of all the artificial blocks.
   for (auto &MBB : MF)
     if (none_of(MBB.instrs(), hasNonArtificialLocation))
LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()
                       << VarAssignCount
                       << " variable assignments, exceeding limits.\n");
   } else {
     // Compute the extended ranges, iterating over scopes. There might be
     // something to be said for ordering them by size/locality, but that's for
     // the future. For each scope, solve the variable value problem, producing
     // a map of variables to values in SavedLiveIns.
     for (auto &P : ScopeToVars) {
-      vlocDataflow(P.first, ScopeToDILocation[P.first], P.second,
+      buildVLocValueMap(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, MOutLocs, MInLocs, AllVarsNumbering, *TPC);

llvm/test/DebugInfo/MIR/InstrRef/pick-vphi-in-shifting-loop.mir

+# RUN: llc %s -o - -run-pass=livedebugvalues \
+# RUN:     -experimental-debug-variable-locations \
+# RUN: | FileCheck %s
+#
+# This test used to cause an infinite loop in InstrRefBasedLDV. Observe block
+# five: on the first entry the desired variable value is in $rdx and $rcx, on
+# both paths to the block. However, the block rotates values between those
+# registers, and feeds a zero-value in too. Ultimately, there is no correct
+# location for the variable in that block.
+# This caused an infinite loop in a previous implementation of LiveDebugValues.
+# Keep this around as a regression test, and check that no location is picked
+# in block 5.
+#
+# CHECK-LABEL: bb.3:
+# CHECK:       DBG_INSTR_REF 7, 0
+# CHECK-NEXT:  DBG_VALUE $rdx
+# CHECK-NEXT:  $rcx = MOV64rr $rdx
+# CHECK-LABEL: bb.4:
+# CHECK:       DBG_VALUE $rcx
+# CHECK-NEXT:  $rdx = MOV64rr killed $rcx
+# CHECK-LABEL: bb.5:
+# CHEKC-NOT:   DBG_VALUE
+--- |
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  ; Function Attrs: nofree norecurse nosync nounwind readonly uwtable
+  define dso_local void @bees() local_unnamed_addr !dbg !13 {
+  entry:
+    ret void, !dbg !22
+  }
+  
+  ; Function Attrs: nofree nosync nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!2}
+  !llvm.module.flags = !{!8, !9, !10, !11}
+  !llvm.ident = !{!12}
+  
+  !0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+  !1 = distinct !DIGlobalVariable(name: "xmlNormalizeURIPath_path", scope: !2, file: !3, line: 1, type: !6, isLocal: false, isDefinition: true)
+  !2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 10.0 ([e-mail]:llvm/llvm-project 9d8de79d09c9560c094d90b010e8315fe2712ec2)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, splitDebugInlining: false, nameTableKind: None)
+  !3 = !DIFile(filename: "test4.c", directory: "/tmp")
+  !4 = !{}
+  !5 = !{!0}
+  !6 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !7, size: 64)
+  !7 = !DIBasicType(name: "char", size: 8, encoding: DW_ATE_signed_char)
+  !8 = !{i32 7, !"Dwarf Version", i32 4}
+  !9 = !{i32 2, !"Debug Info Version", i32 3}
+  !10 = !{i32 1, !"wchar_size", i32 4}
+  !11 = !{i32 7, !"uwtable", i32 1}
+  !12 = !{!"clang version 10.0 ([e-mail]:llvm/llvm-project 9d8de79d09c9560c094d90b010e8315fe2712ec2)"}
+  !13 = distinct !DISubprogram(name: "xmlNormalizeURIPath", scope: !3, file: !3, line: 2, type: !14, scopeLine: 2, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !16)
+  !14 = !DISubroutineType(types: !15)
+  !15 = !{null}
+  !16 = !{!17, !18}
+  !17 = !DILocalVariable(name: "cur", scope: !13, file: !3, line: 3, type: !6)
+  !18 = !DILocalVariable(name: "segp", scope: !19, file: !3, line: 5, type: !6)
+  !19 = distinct !DILexicalBlock(scope: !13, file: !3, line: 4, column: 13)
+  !20 = !DILocation(line: 4, column: 3, scope: !13)
+  !21 = !DILocation(line: 0, scope: !13)
+  !22 = !DILocation(line: 0, scope: !19)
+  !23 = !DILocation(line: 6, column: 5, scope: !19)
+  !24 = !DILocation(line: 6, column: 12, scope: !19)
+  !25 = !{!26, !26, i64 0}
+  !26 = !{!"omnipotent char", !27, i64 0}
+  !27 = !{!"Simple C/C++ TBAA"}
+  !28 = !DILocation(line: 6, column: 27, scope: !19)
+  !29 = !DILocation(line: 7, column: 7, scope: !19)
+  !30 = distinct !{!30, !23, !31, !32, !33}
+  !31 = !DILocation(line: 7, column: 9, scope: !19)
+  !32 = !{!"llvm.loop.mustprogress"}
+  !33 = !{!"llvm.loop.unroll.disable"}
+
+...
+---
+name:            bees
+alignment:       16
+tracksRegLiveness: true
+frameInfo:
+  maxAlignment:    1
+  maxCallFrameSize: 0
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    $rdx = MOV64ri 0, implicit-def $eflags
+    $esi = MOV32ri 0, implicit-def $eflags
+  
+  bb.1:
+    successors: %bb.2(0x03e0f83e), %bb.1(0x7c1f07c2)
+    liveins: $rcx, $rdi, $rdx, $eflags
+  
+    DBG_PHI $rcx, 2
+    DBG_INSTR_REF 2, 0, !18, !DIExpression(), debug-location !22
+    JCC_1 %bb.1, 4, implicit $eflags, debug-location !22
+  
+  bb.2:
+    successors: %bb.4(0x30000000), %bb.3(0x50000000)
+    liveins: $rcx, $rdi, $eflags
+  
+    JCC_1 %bb.4, 4, implicit $eflags, debug-location !22
+  
+  bb.3:
+    successors: %bb.5(0x04000000)
+    liveins: $rcx, $rdi, $eflags
+  
+    $rdx = MOV64ri 0, debug-instr-number 7, debug-location !22
+    DBG_INSTR_REF 7, 0, !18, !DIExpression(), debug-location !22
+    $rcx = MOV64rr $rdx
+    JMP_1 %bb.5, debug-location !22
+  
+  bb.4:
+    liveins: $rcx, $rdi, $eflags
+  
+    $rdx = MOV64rr killed $rcx, debug-location !22
+  
+  bb.5:
+    successors: %bb.5(0x7c000000), %bb.6(0x04000000)
+    liveins: $rdi, $rdx, $eflags
+  
+    $rcx = MOV64rr $rdx, debug-location !22
+    $rdx = MOV64ri 0 ; jmorse -- disabling this makes variable live-through
+    JCC_1 %bb.5, 6, implicit $eflags, debug-location !22
+  
+  bb.6:
+    RETQ debug-location !22
+
+...

llvm/unittests/CodeGen/InstrRefLDVTest.cpp

public:
   std::unique_ptr<MachineFunction> MF;
   std::unique_ptr<MachineDominatorTree> DomTree;
   DICompileUnit *OurCU;
   DIFile *OurFile;
   DISubprogram *OurFunc;
   DILexicalBlock *OurBlock, *AnotherBlock;
   DISubprogram *ToInlineFunc;
   DILexicalBlock *ToInlineBlock;
+  DILocalVariable *FuncVariable;
+  DIBasicType *LongInt;
+  DIExpression *EmptyExpr;
 
   DebugLoc OutermostLoc, InBlockLoc, NotNestedBlockLoc, InlinedLoc;
 
-  MachineBasicBlock *MBB1, *MBB2, *MBB3, *MBB4, *MBB5;
+  MachineBasicBlock *MBB0, *MBB1, *MBB2, *MBB3, *MBB4;
 
   std::unique_ptr<InstrRefBasedLDV> LDV;
   std::unique_ptr<MLocTracker> MTracker;
+  std::unique_ptr<VLocTracker> VTracker;
 
   InstrRefLDVTest() : Ctx(), Mod("beehives", Ctx) {
   }
 
   void SetUp() {
     // Boilerplate that creates a MachineFunction and associated blocks.
 
     Mod.setDataLayout("e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-f64:32:64-f80:32-n8:16:32-S128");
void SetUp() {
     // Make some nested scopes.
     OutermostLoc = DILocation::get(Ctx, 3, 1, OurFunc);
     InBlockLoc = DILocation::get(Ctx, 4, 1, OurBlock);
     InlinedLoc = DILocation::get(Ctx, 10, 1, ToInlineFunc, InBlockLoc.get());
 
     // Make a scope that isn't nested within the others.
     NotNestedBlockLoc = DILocation::get(Ctx, 4, 1, AnotherBlock);
 
+    LongInt = DIB.createBasicType("long", 64, llvm::dwarf::DW_ATE_unsigned);
+    FuncVariable = DIB.createAutoVariable(OurFunc, "lala", OurFile, 1, LongInt);
+    EmptyExpr = DIExpression::get(Ctx, {});
+
     DIB.finalize();
   }
 
   Register getRegByName(const char *WantedName) {
     auto *TRI = MF->getRegInfo().getTargetRegisterInfo();
     // Slow, but works.
     for (unsigned int I = 1; I < TRI->getNumRegs(); ++I) {
       const char *Name = TRI->getName(I);
InstrRefBasedLDV *setupLDVObj() {
     DomTree = std::make_unique<MachineDominatorTree>(*MF);
     LDV->DomTree = &*DomTree;
 
     // Future work: unit tests for mtracker / vtracker / ttracker.
 
     // Setup things like the artifical block map, and BlockNo <=> RPO Order
     // mappings.
     LDV->initialSetup(*MF);
+    LDV->LS.initialize(*MF);
     addMTracker();
+    addVTracker();
     return &*LDV;
   }
 
   void addMTracker() {
     ASSERT_TRUE(LDV);
     // Add a machine-location-tracking object to LDV. Don't initialize any
     // register locations within it though.
     const TargetSubtargetInfo &STI = MF->getSubtarget();
     MTracker = std::make_unique<MLocTracker>(
           *MF, *LDV->TII, *LDV->TRI, *STI.getTargetLowering());
     LDV->MTracker = &*MTracker;
   }
 
+  void addVTracker() {
+    ASSERT_TRUE(LDV);
+    VTracker = std::make_unique<VLocTracker>();
+    LDV->VTracker = &*VTracker;
+  }
+
   // Some routines for bouncing into LDV,
   void buildMLocValueMap(ValueIDNum **MInLocs, ValueIDNum **MOutLocs,
                          SmallVectorImpl<MLocTransferMap> &MLocTransfer) {
     LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer);
   }
 
+  Optional<ValueIDNum>
+  pickVPHILoc(const MachineBasicBlock &MBB, const DebugVariable &Var,
+              const InstrRefBasedLDV::LiveIdxT &LiveOuts, ValueIDNum **MOutLocs,
+              const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {
+    return LDV->pickVPHILoc(MBB, Var, LiveOuts, MOutLocs, BlockOrders);
+  }
+
+  bool vlocJoin(MachineBasicBlock &MBB, InstrRefBasedLDV::LiveIdxT &VLOCOutLocs,
+                InstrRefBasedLDV::LiveIdxT &VLOCInLocs,
+                const SmallSet<DebugVariable, 4> &AllVars,
+                SmallPtrSet<const MachineBasicBlock *, 8> &InScopeBlocks,
+                SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,
+                DenseMap<DebugVariable, DbgValue> &InLocsT) {
+    return LDV->vlocJoin(MBB, VLOCOutLocs, VLOCInLocs, AllVars,
+                         InScopeBlocks, BlocksToExplore, InLocsT);
+  }
+
+  void buildVLocValueMap(const DILocation *DILoc,
+                    const SmallSet<DebugVariable, 4> &VarsWeCareAbout,
+                    SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks,
+                    InstrRefBasedLDV::LiveInsT &Output, ValueIDNum **MOutLocs,
+                    ValueIDNum **MInLocs,
+                    SmallVectorImpl<VLocTracker> &AllTheVLocs) {
+    LDV->buildVLocValueMap(DILoc, VarsWeCareAbout, AssignBlocks, Output,
+                           MOutLocs, MInLocs, AllTheVLocs);
+  }
+
   void initValueArray(ValueIDNum **Nums, unsigned Blks, unsigned Locs) {
     for (unsigned int I = 0; I < Blks; ++I)
       for (unsigned int J = 0; J < Locs; ++J)
         Nums[I][J] = ValueIDNum::EmptyValue;
   }
-};
-
-TEST_F(InstrRefLDVTest, MLocSingleBlock) {
-  // Test some very simple properties about interpreting the transfer function.
 
+  void setupSingleBlock() {
     // Add an entry block with nothing but 'ret void' in it.
     Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
-  IRBuilder<> IRB(BB1);
+    auto *BB0 = BasicBlock::Create(Ctx, "entry", &F);
+    IRBuilder<> IRB(BB0);
     IRB.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
+    MF->RenumberBlocks();
+
+    setupLDVObj();
+  }
+
+  void setupDiamondBlocks() {
+    //        entry
+    //        /  \
+    //      br1  br2
+    //        \  /
+    //         ret
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto *BB0 = BasicBlock::Create(Ctx, "a", &F);
+    auto *BB1 = BasicBlock::Create(Ctx, "b", &F);
+    auto *BB2 = BasicBlock::Create(Ctx, "c", &F);
+    auto *BB3 = BasicBlock::Create(Ctx, "d", &F);
+    IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3);
+    IRB0.CreateBr(BB1);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateBr(BB3);
+    IRB3.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
+    MBB1 = MF->CreateMachineBasicBlock(BB1);
+    MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB3 = MF->CreateMachineBasicBlock(BB3);
+    MF->insert(MF->end(), MBB3);
+    MBB0->addSuccessor(MBB1);
+    MBB0->addSuccessor(MBB2);
+    MBB1->addSuccessor(MBB3);
+    MBB2->addSuccessor(MBB3);
+    MF->RenumberBlocks();
+
+    setupLDVObj();
+  }
+
+  void setupSimpleLoop() {
+    //    entry
+    //     |
+    //     |/-----\
+    //    loopblk |
+    //     |\-----/
+    //     |
+    //     ret
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto *BB0 = BasicBlock::Create(Ctx, "entry", &F);
+    auto *BB1 = BasicBlock::Create(Ctx, "loop", &F);
+    auto *BB2 = BasicBlock::Create(Ctx, "ret", &F);
+    IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2);
+    IRB0.CreateBr(BB1);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
     MBB1 = MF->CreateMachineBasicBlock(BB1);
     MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB0->addSuccessor(MBB1);
+    MBB1->addSuccessor(MBB2);
+    MBB1->addSuccessor(MBB1);
     MF->RenumberBlocks();
 
     setupLDVObj();
+  }
+
+  void setupNestedLoops() {
+    //    entry
+    //     |
+    //    loop1
+    //     ^\
+    //     | \    /-\
+    //     |  loop2  |
+    //     |  /   \-/
+    //     ^ /
+    //     join
+    //     |
+    //     ret
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto *BB0 = BasicBlock::Create(Ctx, "entry", &F);
+    auto *BB1 = BasicBlock::Create(Ctx, "loop1", &F);
+    auto *BB2 = BasicBlock::Create(Ctx, "loop2", &F);
+    auto *BB3 = BasicBlock::Create(Ctx, "join", &F);
+    auto *BB4 = BasicBlock::Create(Ctx, "ret", &F);
+    IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
+    IRB0.CreateBr(BB1);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateBr(BB3);
+    IRB3.CreateBr(BB4);
+    IRB4.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
+    MBB1 = MF->CreateMachineBasicBlock(BB1);
+    MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB3 = MF->CreateMachineBasicBlock(BB3);
+    MF->insert(MF->end(), MBB3);
+    MBB4 = MF->CreateMachineBasicBlock(BB4);
+    MF->insert(MF->end(), MBB4);
+    MBB0->addSuccessor(MBB1);
+    MBB1->addSuccessor(MBB2);
+    MBB2->addSuccessor(MBB2);
+    MBB2->addSuccessor(MBB3);
+    MBB3->addSuccessor(MBB1);
+    MBB3->addSuccessor(MBB4);
+    MF->RenumberBlocks();
+
+    setupLDVObj();
+  }
+
+  void setupNoDominatingLoop() {
+    //           entry
+    //            / \
+    //           /   \
+    //          /     \
+    //        head1   head2
+    //        ^  \   /   ^
+    //        ^   \ /    ^
+    //        \-joinblk -/
+    //             |
+    //            ret
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto *BB0 = BasicBlock::Create(Ctx, "entry", &F);
+    auto *BB1 = BasicBlock::Create(Ctx, "head1", &F);
+    auto *BB2 = BasicBlock::Create(Ctx, "head2", &F);
+    auto *BB3 = BasicBlock::Create(Ctx, "joinblk", &F);
+    auto *BB4 = BasicBlock::Create(Ctx, "ret", &F);
+    IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
+    IRB0.CreateBr(BB1);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateBr(BB3);
+    IRB3.CreateBr(BB4);
+    IRB4.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
+    MBB1 = MF->CreateMachineBasicBlock(BB1);
+    MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB3 = MF->CreateMachineBasicBlock(BB3);
+    MF->insert(MF->end(), MBB3);
+    MBB4 = MF->CreateMachineBasicBlock(BB4);
+    MF->insert(MF->end(), MBB4);
+    MBB0->addSuccessor(MBB1);
+    MBB0->addSuccessor(MBB2);
+    MBB1->addSuccessor(MBB3);
+    MBB2->addSuccessor(MBB3);
+    MBB3->addSuccessor(MBB1);
+    MBB3->addSuccessor(MBB2);
+    MBB3->addSuccessor(MBB4);
+    MF->RenumberBlocks();
+
+    setupLDVObj();
+  }
+
+  void setupBadlyNestedLoops() {
+    //           entry
+    //             |
+    //           loop1 -o
+    //             | ^
+    //             | ^
+    //           loop2 -o
+    //             | ^
+    //             | ^
+    //           loop3 -o
+    //             |
+    //            ret
+    //
+    // NB: the loop blocks self-loop, which is a bit too fiddly to draw on
+    // accurately.
+    llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
+    auto *BB0 = BasicBlock::Create(Ctx, "entry", &F);
+    auto *BB1 = BasicBlock::Create(Ctx, "loop1", &F);
+    auto *BB2 = BasicBlock::Create(Ctx, "loop2", &F);
+    auto *BB3 = BasicBlock::Create(Ctx, "loop3", &F);
+    auto *BB4 = BasicBlock::Create(Ctx, "ret", &F);
+    IRBuilder<> IRB0(BB0), IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
+    IRB0.CreateBr(BB1);
+    IRB1.CreateBr(BB2);
+    IRB2.CreateBr(BB3);
+    IRB3.CreateBr(BB4);
+    IRB4.CreateRetVoid();
+    MBB0 = MF->CreateMachineBasicBlock(BB0);
+    MF->insert(MF->end(), MBB0);
+    MBB1 = MF->CreateMachineBasicBlock(BB1);
+    MF->insert(MF->end(), MBB1);
+    MBB2 = MF->CreateMachineBasicBlock(BB2);
+    MF->insert(MF->end(), MBB2);
+    MBB3 = MF->CreateMachineBasicBlock(BB3);
+    MF->insert(MF->end(), MBB3);
+    MBB4 = MF->CreateMachineBasicBlock(BB4);
+    MF->insert(MF->end(), MBB4);
+    MBB0->addSuccessor(MBB1);
+    MBB1->addSuccessor(MBB1);
+    MBB1->addSuccessor(MBB2);
+    MBB2->addSuccessor(MBB1);
+    MBB2->addSuccessor(MBB2);
+    MBB2->addSuccessor(MBB3);
+    MBB3->addSuccessor(MBB2);
+    MBB3->addSuccessor(MBB3);
+    MBB3->addSuccessor(MBB4);
+    MF->RenumberBlocks();
+
+    setupLDVObj();
+  }
+};
+
+TEST_F(InstrRefLDVTest, MLocSingleBlock) {
+  // Test some very simple properties about interpreting the transfer function.
+  setupSingleBlock();
+
   // We should start with a single location, the stack pointer.
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
 
   // Set up live-in and live-out tables for this function: two locations (we
   // add one later) in a single block.
   ValueIDNum InLocs[2], OutLocs[2];
   ValueIDNum *InLocsPtr[1] = {&InLocs[0]};
TEST_F(InstrRefLDVTest, MLocSingleBlock) {
   EXPECT_EQ(InLocs[1], ValueIDNum(0, 0, RaxLoc));
   EXPECT_EQ(OutLocs[0], ValueIDNum(0, 1, RspLoc));
   EXPECT_EQ(OutLocs[1], ValueIDNum(0, 0, RspLoc)); // Rax contains RspLoc.
   TransferFunc[0].clear();
 }
 
 TEST_F(InstrRefLDVTest, MLocDiamondBlocks) {
   // Test that information flows from the entry block to two successors.
-
   //        entry
   //        /  \
   //      br1  br2
   //        \  /
   //         ret
-  llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "a", &F);
-  auto *BB2 = BasicBlock::Create(Ctx, "b", &F);
-  auto *BB3 = BasicBlock::Create(Ctx, "c", &F);
-  auto *BB4 = BasicBlock::Create(Ctx, "d", &F);
-  IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4);
-  IRB1.CreateBr(BB2);
-  IRB2.CreateBr(BB3);
-  IRB3.CreateBr(BB4);
-  IRB4.CreateRetVoid();
-  MBB1 = MF->CreateMachineBasicBlock(BB1);
-  MF->insert(MF->end(), MBB1);
-  MBB2 = MF->CreateMachineBasicBlock(BB2);
-  MF->insert(MF->end(), MBB2);
-  MBB3 = MF->CreateMachineBasicBlock(BB3);
-  MF->insert(MF->end(), MBB3);
-  MBB4 = MF->CreateMachineBasicBlock(BB4);
-  MF->insert(MF->end(), MBB4);
-  MBB1->addSuccessor(MBB2);
-  MBB1->addSuccessor(MBB3);
-  MBB2->addSuccessor(MBB4);
-  MBB3->addSuccessor(MBB4);
-  MF->RenumberBlocks();
-
-  setupLDVObj();
+  setupDiamondBlocks();
 
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
   Register RAX = getRegByName("RAX");
   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
 
   ValueIDNum InLocs[4][2], OutLocs[4][2];
   ValueIDNum *InLocsPtr[4] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3]};
   ValueIDNum *OutLocsPtr[4] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3]};
 
   // Transfer function: start with nothing.
   SmallVector<MLocTransferMap, 1> TransferFunc;
   TransferFunc.resize(4);
 
   // Name some values.
-  ValueIDNum LiveInRsp(0, 0, RspLoc);
-  ValueIDNum RspDefInBlk0(0, 1, RspLoc);
-  ValueIDNum RspDefInBlk1(1, 1, RspLoc);
-  ValueIDNum RspDefInBlk2(2, 1, RspLoc);
-  ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
-  ValueIDNum RaxLiveInBlk1(1, 0, RaxLoc);
-  ValueIDNum RaxLiveInBlk2(2, 0, RaxLoc);
+  unsigned EntryBlk = 0, BrBlk1 = 1, BrBlk2 = 2, RetBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum RspDefInBlk0(EntryBlk, 1, RspLoc);
+  ValueIDNum RspDefInBlk1(BrBlk1, 1, RspLoc);
+  ValueIDNum RspDefInBlk2(BrBlk2, 1, RspLoc);
+  ValueIDNum RspPHIInBlk3(RetBlk, 0, RspLoc);
+  ValueIDNum RaxLiveInBlk1(BrBlk1, 0, RaxLoc);
+  ValueIDNum RaxLiveInBlk2(BrBlk2, 0, RaxLoc);
 
   // With no transfer function, the live-in values to the entry block should
   // propagate to all live-outs and the live-ins to the two successor blocks.
   // IN ADDITION: this checks that the exit block doesn't get a PHI put in it.
   initValueArray(InLocsPtr, 4, 2);
   initValueArray(OutLocsPtr, 4, 2);
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
   EXPECT_EQ(InLocs[0][0], LiveInRsp);

 TEST_F(InstrRefLDVTest, MLocSimpleLoop) {
   //    entry
   //     |
   //     |/-----\
   //    loopblk |
   //     |\-----/
   //     |
   //     ret
-  llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
-  auto *BB2 = BasicBlock::Create(Ctx, "loop", &F);
-  auto *BB3 = BasicBlock::Create(Ctx, "ret", &F);
-  IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3);
-  IRB1.CreateBr(BB2);
-  IRB2.CreateBr(BB3);
-  IRB3.CreateRetVoid();
-  MBB1 = MF->CreateMachineBasicBlock(BB1);
-  MF->insert(MF->end(), MBB1);
-  MBB2 = MF->CreateMachineBasicBlock(BB2);
-  MF->insert(MF->end(), MBB2);
-  MBB3 = MF->CreateMachineBasicBlock(BB3);
-  MF->insert(MF->end(), MBB3);
-  MBB1->addSuccessor(MBB2);
-  MBB2->addSuccessor(MBB3);
-  MBB2->addSuccessor(MBB2);
-  MF->RenumberBlocks();
-
-  setupLDVObj();
+  setupSimpleLoop();
 
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
   Register RAX = getRegByName("RAX");
   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
 
   ValueIDNum InLocs[3][2], OutLocs[3][2];
   ValueIDNum *InLocsPtr[3] = {InLocs[0], InLocs[1], InLocs[2]};
   ValueIDNum *OutLocsPtr[3] = {OutLocs[0], OutLocs[1], OutLocs[2]};
 
   SmallVector<MLocTransferMap, 1> TransferFunc;
   TransferFunc.resize(3);
 
   // Name some values.
-  ValueIDNum LiveInRsp(0, 0, RspLoc);
-  ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
-  ValueIDNum RspDefInBlk1(1, 1, RspLoc);
-  ValueIDNum LiveInRax(0, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
+  unsigned EntryBlk = 0, LoopBlk = 1, RetBlk = 2;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk1(LoopBlk, 0, RspLoc);
+  ValueIDNum RspDefInBlk1(LoopBlk, 1, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk1(LoopBlk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk2(RetBlk, 0, RaxLoc);
 
   // Begin test with all locations being live-through.
   initValueArray(InLocsPtr, 3, 2);
   initValueArray(OutLocsPtr, 3, 2);
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
   EXPECT_EQ(InLocs[0][0], LiveInRsp);
   EXPECT_EQ(InLocs[1][0], LiveInRsp);
   EXPECT_EQ(InLocs[2][0], LiveInRsp);
TEST_F(InstrRefLDVTest, MLocNestedLoop) {
   //     ^\
   //     | \    /-\
   //     |  loop2  |
   //     |  /   \-/
   //     ^ /
   //     join
   //     |
   //     ret
-  llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
-  auto *BB2 = BasicBlock::Create(Ctx, "loop1", &F);
-  auto *BB3 = BasicBlock::Create(Ctx, "loop2", &F);
-  auto *BB4 = BasicBlock::Create(Ctx, "join", &F);
-  auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
-  IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
-  IRB1.CreateBr(BB2);
-  IRB2.CreateBr(BB3);
-  IRB3.CreateBr(BB4);
-  IRB4.CreateBr(BB5);
-  IRB5.CreateRetVoid();
-  MBB1 = MF->CreateMachineBasicBlock(BB1);
-  MF->insert(MF->end(), MBB1);
-  MBB2 = MF->CreateMachineBasicBlock(BB2);
-  MF->insert(MF->end(), MBB2);
-  MBB3 = MF->CreateMachineBasicBlock(BB3);
-  MF->insert(MF->end(), MBB3);
-  MBB4 = MF->CreateMachineBasicBlock(BB4);
-  MF->insert(MF->end(), MBB4);
-  MBB5 = MF->CreateMachineBasicBlock(BB5);
-  MF->insert(MF->end(), MBB5);
-  MBB1->addSuccessor(MBB2);
-  MBB2->addSuccessor(MBB3);
-  MBB3->addSuccessor(MBB3);
-  MBB3->addSuccessor(MBB4);
-  MBB4->addSuccessor(MBB2);
-  MBB4->addSuccessor(MBB5);
-  MF->RenumberBlocks();
-
-  setupLDVObj();
+  setupNestedLoops();
 
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
   Register RAX = getRegByName("RAX");
   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
 
   ValueIDNum InLocs[5][2], OutLocs[5][2];
   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
                               InLocs[4]};
   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
                                OutLocs[4]};
 
   SmallVector<MLocTransferMap, 1> TransferFunc;
   TransferFunc.resize(5);
 
-  ValueIDNum LiveInRsp(0, 0, RspLoc);
-  ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
-  ValueIDNum RspDefInBlk1(1, 1, RspLoc);
-  ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
-  ValueIDNum RspDefInBlk2(2, 1, RspLoc);
-  ValueIDNum RspDefInBlk3(3, 1, RspLoc);
-  ValueIDNum LiveInRax(0, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
+  unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2, JoinBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk1(Loop1Blk, 1, RspLoc);
+  ValueIDNum RspPHIInBlk2(Loop2Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk2(Loop2Blk, 1, RspLoc);
+  ValueIDNum RspDefInBlk3(JoinBlk, 1, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk1(Loop1Blk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk2(Loop2Blk, 0, RaxLoc);
 
   // Like the other tests: first ensure that if there's nothing in the transfer
   // function, then everything is live-through (check $rsp).
   initValueArray(InLocsPtr, 5, 2);
   initValueArray(OutLocsPtr, 5, 2);
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
   EXPECT_EQ(InLocs[0][0], LiveInRsp);
   EXPECT_EQ(InLocs[1][0], LiveInRsp);
TEST_F(InstrRefLDVTest, MLocNoDominatingLoop) {
   //           /   \
   //          /     \
   //        head1   head2
   //        ^  \   /   ^
   //        ^   \ /    ^
   //        \-joinblk -/
   //             |
   //            ret
-  llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
-  auto *BB2 = BasicBlock::Create(Ctx, "head1", &F);
-  auto *BB3 = BasicBlock::Create(Ctx, "head2", &F);
-  auto *BB4 = BasicBlock::Create(Ctx, "joinblk", &F);
-  auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
-  IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
-  IRB1.CreateBr(BB2);
-  IRB2.CreateBr(BB3);
-  IRB3.CreateBr(BB4);
-  IRB4.CreateBr(BB5);
-  IRB5.CreateRetVoid();
-  MBB1 = MF->CreateMachineBasicBlock(BB1);
-  MF->insert(MF->end(), MBB1);
-  MBB2 = MF->CreateMachineBasicBlock(BB2);
-  MF->insert(MF->end(), MBB2);
-  MBB3 = MF->CreateMachineBasicBlock(BB3);
-  MF->insert(MF->end(), MBB3);
-  MBB4 = MF->CreateMachineBasicBlock(BB4);
-  MF->insert(MF->end(), MBB4);
-  MBB5 = MF->CreateMachineBasicBlock(BB5);
-  MF->insert(MF->end(), MBB5);
-  MBB1->addSuccessor(MBB2);
-  MBB1->addSuccessor(MBB3);
-  MBB2->addSuccessor(MBB4);
-  MBB3->addSuccessor(MBB4);
-  MBB4->addSuccessor(MBB2);
-  MBB4->addSuccessor(MBB3);
-  MBB4->addSuccessor(MBB5);
-  MF->RenumberBlocks();
-
-  setupLDVObj();
+  setupNoDominatingLoop();
 
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
   Register RAX = getRegByName("RAX");
   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
 
   ValueIDNum InLocs[5][2], OutLocs[5][2];
   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
                               InLocs[4]};
   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
                                OutLocs[4]};
 
   SmallVector<MLocTransferMap, 1> TransferFunc;
   TransferFunc.resize(5);
 
-  ValueIDNum LiveInRsp(0, 0, RspLoc);
-  ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
-  ValueIDNum RspDefInBlk1(1, 1, RspLoc);
-  ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
-  ValueIDNum RspDefInBlk2(2, 1, RspLoc);
-  ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
-  ValueIDNum RspDefInBlk3(3, 1, RspLoc);
-  ValueIDNum RaxPHIInBlk1(1, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk2(2, 0, RaxLoc);
+  unsigned EntryBlk = 0, Head1Blk = 1, Head2Blk = 2, JoinBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk1(Head1Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk1(Head1Blk, 1, RspLoc);
+  ValueIDNum RspPHIInBlk2(Head2Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk2(Head2Blk, 1, RspLoc);
+  ValueIDNum RspPHIInBlk3(JoinBlk, 0, RspLoc);
+  ValueIDNum RspDefInBlk3(JoinBlk, 1, RspLoc);
+  ValueIDNum RaxPHIInBlk1(Head1Blk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk2(Head2Blk, 0, RaxLoc);
 
   // As ever, test that everything is live-through if there are no defs.
   initValueArray(InLocsPtr, 5, 2);
   initValueArray(OutLocsPtr, 5, 2);
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
   EXPECT_EQ(InLocs[0][0], LiveInRsp);
   EXPECT_EQ(InLocs[1][0], LiveInRsp);
   EXPECT_EQ(InLocs[2][0], LiveInRsp);
TEST_F(InstrRefLDVTest, MLocBadlyNestedLoops) {
   //             | ^
   //             | ^
   //           loop2 -o
   //             | ^
   //             | ^
   //           loop3 -o
   //             |
   //            ret
-  //
-  // NB: the loop blocks self-loop, which is a bit too fiddly to draw on
-  // accurately.
-  llvm::Function &F = const_cast<llvm::Function &>(MF->getFunction());
-  auto *BB1 = BasicBlock::Create(Ctx, "entry", &F);
-  auto *BB2 = BasicBlock::Create(Ctx, "loop1", &F);
-  auto *BB3 = BasicBlock::Create(Ctx, "loop2", &F);
-  auto *BB4 = BasicBlock::Create(Ctx, "loop3", &F);
-  auto *BB5 = BasicBlock::Create(Ctx, "ret", &F);
-  IRBuilder<> IRB1(BB1), IRB2(BB2), IRB3(BB3), IRB4(BB4), IRB5(BB5);
-  IRB1.CreateBr(BB2);
-  IRB2.CreateBr(BB3);
-  IRB3.CreateBr(BB4);
-  IRB4.CreateBr(BB5);
-  IRB5.CreateRetVoid();
-  MBB1 = MF->CreateMachineBasicBlock(BB1);
-  MF->insert(MF->end(), MBB1);
-  MBB2 = MF->CreateMachineBasicBlock(BB2);
-  MF->insert(MF->end(), MBB2);
-  MBB3 = MF->CreateMachineBasicBlock(BB3);
-  MF->insert(MF->end(), MBB3);
-  MBB4 = MF->CreateMachineBasicBlock(BB4);
-  MF->insert(MF->end(), MBB4);
-  MBB5 = MF->CreateMachineBasicBlock(BB5);
-  MF->insert(MF->end(), MBB5);
-  MBB1->addSuccessor(MBB2);
-  MBB2->addSuccessor(MBB2);
-  MBB2->addSuccessor(MBB3);
-  MBB3->addSuccessor(MBB2);
-  MBB3->addSuccessor(MBB3);
-  MBB3->addSuccessor(MBB4);
-  MBB4->addSuccessor(MBB3);
-  MBB4->addSuccessor(MBB4);
-  MBB4->addSuccessor(MBB5);
-  MF->RenumberBlocks();
-
-  setupLDVObj();
+  setupBadlyNestedLoops();
 
   ASSERT_TRUE(MTracker->getNumLocs() == 1);
   LocIdx RspLoc(0);
   Register RAX = getRegByName("RAX");
   LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
 
   ValueIDNum InLocs[5][2], OutLocs[5][2];
   ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3],
                               InLocs[4]};
   ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3],
                                OutLocs[4]};
 
   SmallVector<MLocTransferMap, 1> TransferFunc;
   TransferFunc.resize(5);
 
-  ValueIDNum LiveInRsp(0, 0, RspLoc);
-  ValueIDNum RspPHIInBlk1(1, 0, RspLoc);
-  ValueIDNum RspDefInBlk1(1, 1, RspLoc);
-  ValueIDNum RspPHIInBlk2(2, 0, RspLoc);
-  ValueIDNum RspPHIInBlk3(3, 0, RspLoc);
-  ValueIDNum RspDefInBlk3(3, 1, RspLoc);
-  ValueIDNum LiveInRax(0, 0, RaxLoc);
-  ValueIDNum RaxPHIInBlk3(3, 0, RaxLoc);
+  unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2, Loop3Blk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk1(Loop1Blk, 1, RspLoc);
+  ValueIDNum RspPHIInBlk2(Loop2Blk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk3(Loop3Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk3(Loop3Blk, 1, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RaxPHIInBlk3(Loop3Blk, 0, RaxLoc);
 
   // As ever, test that everything is live-through if there are no defs.
   initValueArray(InLocsPtr, 5, 2);
   initValueArray(OutLocsPtr, 5, 2);
   buildMLocValueMap(InLocsPtr, OutLocsPtr, TransferFunc);
   EXPECT_EQ(InLocs[0][0], LiveInRsp);
   EXPECT_EQ(InLocs[1][0], LiveInRsp);
   EXPECT_EQ(InLocs[2][0], LiveInRsp);
TEST_F(InstrRefLDVTest, MLocBadlyNestedLoops) {
   EXPECT_EQ(InLocs[3][1], LiveInRsp);
   EXPECT_EQ(InLocs[4][1], LiveInRsp);
   EXPECT_EQ(OutLocs[0][1], LiveInRsp);
   EXPECT_EQ(OutLocs[1][1], LiveInRsp);
   EXPECT_EQ(OutLocs[2][1], LiveInRsp);
   EXPECT_EQ(OutLocs[3][1], LiveInRsp);
   EXPECT_EQ(OutLocs[4][1], LiveInRsp);
 }
+
+TEST_F(InstrRefLDVTest, pickVPHILocDiamond) {
+  //        entry
+  //        /  \
+  //      br1  br2
+  //        \  /
+  //         ret
+  setupDiamondBlocks();
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  ValueIDNum OutLocs[4][2];
+  ValueIDNum *OutLocsPtr[4] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3]};
+
+  initValueArray(OutLocsPtr, 4, 2);
+
+  unsigned EntryBlk = 0, Br2Blk = 2, RetBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk2(Br2Blk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk3(RetBlk, 0, RspLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts;
+  VLiveOuts.resize(4);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+  VLiveOutIdx[MBB3] = &VLiveOuts[3];
+
+  SmallVector<const MachineBasicBlock *, 2> Preds;
+  for (const auto *Pred : MBB3->predecessors())
+    Preds.push_back(Pred);
+
+  // Specify the live-outs around the joining block.
+  OutLocs[1][0] = LiveInRsp;
+  OutLocs[2][0] = LiveInRax;
+
+  Optional<ValueIDNum> Result;
+
+  // Simple case: join two distinct values on entry to the block.
+  VLiveOuts[1].insert({Var,  DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var,  DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  // Should have picked a PHI in $rsp in block 3.
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk3);
+
+  // If the incoming values are swapped between blocks, we should not
+  // successfully join. The CFG merge would select the right values, but in
+  // the wrong conditions.
+  std::swap(VLiveOuts[1], VLiveOuts[2]);
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Swap back,
+  std::swap(VLiveOuts[1], VLiveOuts[2]);
+  // Setting one of these to being a constant should prohibit merging.
+  VLiveOuts[1].find(Var)->second.Kind = DbgValue::Const;
+  VLiveOuts[1].find(Var)->second.MO = MachineOperand::CreateImm(0);
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Seeing both to being a constant -> still prohibit, it shouldn't become
+  // a value in the register file anywhere.
+  VLiveOuts[2].find(Var)->second = VLiveOuts[1].find(Var)->second;
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // NoVals shouldn't join with anything else.
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var,  DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var,  DbgValue(2, EmptyProps, DbgValue::NoVal)});
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // We might merge in another VPHI in such a join. Present pickVPHILoc with
+  // such a scenario: first, where one incoming edge has a VPHI with no known
+  // value. This represents an edge where there was a PHI value that can't be
+  // found in the register file -- we can't subsequently find a PHI here.
+  VLiveOuts[2].clear();
+  VLiveOuts[2].insert({Var,  DbgValue(2, EmptyProps, DbgValue::VPHI)});
+  EXPECT_EQ(VLiveOuts[2].find(Var)->second.ID, ValueIDNum::EmptyValue);
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // However, if we know the value of the incoming VPHI, we can search for its
+  // location. Use a PHI machine-value for doing this, as VPHIs should always
+  // have PHI values, or they should have been eliminated.
+  OutLocs[2][0] = RspPHIInBlk2;
+  VLiveOuts[2].find(Var)->second.ID = RspPHIInBlk2;
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk3);
+
+  // If that value isn't available from that block, don't join.
+  OutLocs[2][0] = LiveInRsp;
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Check that we don't pick values when the properties disagree, for example
+  // different indirectness or DIExpression.
+  DIExpression *NewExpr = DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4);
+  DbgValueProperties PropsWithExpr(NewExpr, false);
+  VLiveOuts[2].clear();
+  VLiveOuts[2].insert({Var,  DbgValue(LiveInRsp, PropsWithExpr, DbgValue::Def)});
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  DbgValueProperties PropsWithIndirect(EmptyExpr, true);
+  VLiveOuts[2].clear();
+  VLiveOuts[2].insert({Var,  DbgValue(LiveInRsp, PropsWithIndirect, DbgValue::Def)});
+  Result = pickVPHILoc(*MBB3, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+}
+
+TEST_F(InstrRefLDVTest, pickVPHILocLoops) {
+  setupSimpleLoop();
+  //    entry
+  //     |
+  //     |/-----\
+  //    loopblk |
+  //     |\-----/
+  //     |
+  //     ret
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  ValueIDNum OutLocs[3][2];
+  ValueIDNum *OutLocsPtr[4] = {OutLocs[0], OutLocs[1], OutLocs[2]};
+
+  initValueArray(OutLocsPtr, 3, 2);
+
+  unsigned EntryBlk = 0, LoopBlk = 1;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk1(LoopBlk, 0, RspLoc);
+  ValueIDNum RaxPHIInBlk1(LoopBlk, 0, RaxLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts;
+  VLiveOuts.resize(3);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+
+  SmallVector<const MachineBasicBlock *, 2> Preds;
+  for (const auto *Pred : MBB1->predecessors())
+    Preds.push_back(Pred);
+
+  // Specify the live-outs around the joining block.
+  OutLocs[0][0] = LiveInRsp;
+  OutLocs[1][0] = LiveInRax;
+
+  Optional<ValueIDNum> Result;
+
+  // See that we can merge as normal on a backedge.
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  // Should have picked a PHI in $rsp in block 1.
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk1);
+
+  // And that, if the desired values aren't available, we don't merge.
+  OutLocs[1][0] = LiveInRsp;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Test the backedge behaviour: PHIs that feed back into themselves can
+  // carry this variables value. Feed in LiveInRsp in both $rsp and $rax
+  // from the entry block, but only put an appropriate backedge PHI in $rax.
+  // Only the $rax location can form the correct PHI.
+  OutLocs[0][0] = LiveInRsp;
+  OutLocs[0][1] = LiveInRsp;
+  OutLocs[1][0] = RaxPHIInBlk1;
+  OutLocs[1][1] = RaxPHIInBlk1;
+  VLiveOuts[0].clear();
+  VLiveOuts[1].clear();
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  // Crucially, a VPHI originating in this block:
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RaxPHIInBlk1);
+
+  // Merging should not be permitted if there's a usable PHI on the backedge,
+  // but it's in the wrong place. (Overwrite $rax).
+  OutLocs[1][1] = LiveInRax;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Additionally, if the VPHI coming back on the loop backedge isn't from
+  // this block (block 1), we can't merge it.
+  OutLocs[1][1] = RaxPHIInBlk1;
+  VLiveOuts[1].clear();
+  VLiveOuts[1].insert({Var, DbgValue(0, EmptyProps, DbgValue::VPHI)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+}
+
+TEST_F(InstrRefLDVTest, pickVPHILocBadlyNestedLoops) {
+  // Run some tests similar to pickVPHILocLoops, with more than one backedge,
+  // and check that we merge correctly over many candidate locations.
+  setupBadlyNestedLoops();
+  //           entry
+  //             |
+  //           loop1 -o
+  //             | ^
+  //             | ^
+  //           loop2 -o
+  //             | ^
+  //             | ^
+  //           loop3 -o
+  //             |
+  //            ret
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+  Register RBX = getRegByName("RBX");
+  LocIdx RbxLoc = MTracker->lookupOrTrackRegister(RBX);
+
+  ValueIDNum OutLocs[5][3];
+  ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3], OutLocs[4]};
+
+  initValueArray(OutLocsPtr, 5, 3);
+
+  unsigned EntryBlk = 0, Loop1Blk = 1;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum LiveInRbx(EntryBlk, 0, RbxLoc);
+  ValueIDNum RspPHIInBlk1(Loop1Blk, 0, RspLoc);
+  ValueIDNum RaxPHIInBlk1(Loop1Blk, 0, RaxLoc);
+  ValueIDNum RbxPHIInBlk1(Loop1Blk, 0, RbxLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts;
+  VLiveOuts.resize(5);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+  VLiveOutIdx[MBB3] = &VLiveOuts[3];
+  VLiveOutIdx[MBB4] = &VLiveOuts[4];
+
+  // We're going to focus on block 1.
+  SmallVector<const MachineBasicBlock *, 2> Preds;
+  for (const auto *Pred : MBB1->predecessors())
+    Preds.push_back(Pred);
+
+  // Specify the live-outs around the joining block. Incoming edges from the
+  // entry block, self, and loop2.
+  OutLocs[0][0] = LiveInRsp;
+  OutLocs[1][0] = LiveInRax;
+  OutLocs[2][0] = LiveInRbx;
+
+  Optional<ValueIDNum> Result;
+
+  // See that we can merge as normal on a backedge.
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRbx, EmptyProps, DbgValue::Def)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  // Should have picked a PHI in $rsp in block 1.
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk1);
+
+  // Check too that permuting the live-out locations prevents merging
+  OutLocs[0][0] = LiveInRax;
+  OutLocs[1][0] = LiveInRbx;
+  OutLocs[2][0] = LiveInRsp;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  OutLocs[0][0] = LiveInRsp;
+  OutLocs[1][0] = LiveInRax;
+  OutLocs[2][0] = LiveInRbx;
+
+  // Feeding a PHI back on one backedge shouldn't merge (block 1 self backedge
+  // wants LiveInRax).
+  OutLocs[1][0] = RspPHIInBlk1;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // If the variables value on that edge is a VPHI feeding into itself, that's
+  // fine.
+  VLiveOuts[1].clear();
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk1);
+
+  // Likewise: the other backedge being a VPHI from block 1 should be accepted.
+  OutLocs[2][0] = RspPHIInBlk1;
+  VLiveOuts[2].clear();
+  VLiveOuts[2].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RspPHIInBlk1);
+
+  // Here's where it becomes tricky: we should not merge if there are two
+  // _distinct_ backedge PHIs. We can't have a PHI that happens in both rsp
+  // and rax for example. We can only pick one location as the live-in.
+  OutLocs[2][0] = RaxPHIInBlk1;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // The above test sources correct machine-PHI-value from two places. Now
+  // try with one machine-PHI-value, but placed in two different locations
+  // on the backedge. Again, we can't merge a location here, there's no
+  // location that works on all paths.
+  OutLocs[0][0] = LiveInRsp;
+  OutLocs[1][0] = RspPHIInBlk1;
+  OutLocs[2][0] = LiveInRsp;
+  OutLocs[2][1] = RspPHIInBlk1;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_FALSE(Result);
+
+  // Scatter various PHI values across the available locations. Only rbx (loc 2)
+  // has the right value in both backedges -- that's the loc that should be
+  // picked.
+  OutLocs[0][2] = LiveInRsp;
+  OutLocs[1][0] = RspPHIInBlk1;
+  OutLocs[1][1] = RaxPHIInBlk1;
+  OutLocs[1][2] = RbxPHIInBlk1;
+  OutLocs[2][0] = LiveInRsp;
+  OutLocs[2][1] = RspPHIInBlk1;
+  OutLocs[2][2] = RbxPHIInBlk1;
+  Result = pickVPHILoc(*MBB1, Var, VLiveOutIdx, OutLocsPtr, Preds);
+  EXPECT_TRUE(Result);
+  if (Result)
+    EXPECT_EQ(*Result, RbxPHIInBlk1);
+}
+
+TEST_F(InstrRefLDVTest, vlocJoinDiamond) {
+  //        entry
+  //        /  \
+  //      br1  br2
+  //        \  /
+  //         ret
+  setupDiamondBlocks();
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  unsigned EntryBlk = 0, Br2Blk = 2, RetBlk = 3;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlkBr2Blk(Br2Blk, 0, RspLoc);
+  ValueIDNum RspPHIInBlkRetBlk(RetBlk, 0, RspLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts, VLiveIns;
+  VLiveOuts.resize(4);
+  VLiveIns.resize(4);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx, VLiveInIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+  VLiveOutIdx[MBB3] = &VLiveOuts[3];
+  VLiveInIdx[MBB0] = &VLiveIns[0];
+  VLiveInIdx[MBB1] = &VLiveIns[1];
+  VLiveInIdx[MBB2] = &VLiveIns[2];
+  VLiveInIdx[MBB3] = &VLiveIns[3];
+
+  SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks;
+  AllBlocks.insert(MBB0);
+  AllBlocks.insert(MBB1);
+  AllBlocks.insert(MBB2);
+  AllBlocks.insert(MBB3);
+
+  SmallVector<const MachineBasicBlock *, 2> Preds;
+  for (const auto *Pred : MBB3->predecessors())
+    Preds.push_back(Pred);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  DenseMap<DebugVariable, DbgValue> JoinedLocs;
+
+  // vlocJoin is here to propagate incoming values, and eliminate PHIs. Start
+  // off by propagating a value into the merging block, number 3.
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::NoVal)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  bool Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                         AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result); // Output locs should have changed.
+  auto It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  JoinedLocs.clear();
+
+  // And if we did it a second time, leaving the live-ins as it was, then
+  // we should report no change.
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // If the live-in variable values are different, but there's no PHI placed
+  // in this block, then just pick a location. It should be the first (in RPO)
+  // predecessor to avoid being a backedge.
+  VLiveOuts[2].clear();
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::NoVal)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  // RPO is blocks 0 2 1 3, so LiveInRax is picked as the first predecessor
+  // of this join.
+  EXPECT_EQ(It->second.ID, LiveInRax);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // No tests for whether vlocJoin will pass-through a variable with differing
+  // expressions / properties. Those can only come about due to assignments; and
+  // for any assignment at all, a PHI should have been placed at the dominance
+  // frontier. We rely on the IDF calculator being accurate (which is OK,
+  // because so does the rest of LLVM).
+
+  // Try placing a PHI. With differing input values (LiveInRsp, LiveInRax),
+  // this PHI should not be eliminated.
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  // Expect no change.
+  EXPECT_FALSE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  // This should not have been assigned a fixed value.
+  EXPECT_EQ(It->second.ID, ValueIDNum::EmptyValue);
+  EXPECT_EQ(It->second.BlockNo, 3);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // Try a simple PHI elimination. Put a PHI in block 3, but LiveInRsp on both
+  // incoming edges. Re-load in and out-locs with unrelated values; they're
+  // irrelevant.
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // If the "current" live-in is a VPHI, but not a VPHI generated in the current
+  // block, then it's the remains of an earlier value propagation. We should
+  // value propagate through this merge. Even if the current incoming values
+  // disagree, because we've previously determined any VPHI here is redundant.
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(2, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRax); // from block 2
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // The above test, but test that we will install one value-propagated VPHI
+  // over another.
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(0, EmptyProps, DbgValue::VPHI)});
+  VLiveIns[3].insert({Var, DbgValue(2, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 0);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // We shouldn't eliminate PHIs when properties disagree.
+  DbgValueProperties PropsWithIndirect(EmptyExpr, true);
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRsp, PropsWithIndirect, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 3);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // Even if properties disagree, we should still value-propagate if there's no
+  // PHI to be eliminated. The disagreeing values should work themselves out,
+  // seeing how we've determined no PHI is necessary.
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRsp, PropsWithIndirect, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(2, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  // Also check properties come from block 2, the first RPO predecessor to block
+  // three.
+  EXPECT_EQ(It->second.Properties, PropsWithIndirect);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+
+  // Again, disagreeing properties, this time the expr, should cause a PHI to
+  // not be eliminated.
+  DIExpression *NewExpr = DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4);
+  DbgValueProperties PropsWithExpr(NewExpr, false);
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRsp, PropsWithExpr, DbgValue::Def)});
+  VLiveIns[3].insert({Var, DbgValue(3, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB3, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[3].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 3);
+  EXPECT_EQ(It->second.Properties, EmptyProps);
+  JoinedLocs.clear();
+  VLiveIns[3].clear();
+}
+
+TEST_F(InstrRefLDVTest, vlocJoinLoops) {
+  setupSimpleLoop();
+  //    entry
+  //     |
+  //     |/-----\
+  //    loopblk |
+  //     |\-----/
+  //     |
+  //     ret
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  unsigned EntryBlk = 0, LoopBlk = 1;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk1(LoopBlk, 0, RspLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts, VLiveIns;
+  VLiveOuts.resize(3);
+  VLiveIns.resize(3);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx, VLiveInIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+  VLiveInIdx[MBB0] = &VLiveIns[0];
+  VLiveInIdx[MBB1] = &VLiveIns[1];
+  VLiveInIdx[MBB2] = &VLiveIns[2];
+
+  SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks;
+  AllBlocks.insert(MBB0);
+  AllBlocks.insert(MBB1);
+  AllBlocks.insert(MBB2);
+
+  SmallVector<const MachineBasicBlock *, 2> Preds;
+  for (const auto *Pred : MBB1->predecessors())
+    Preds.push_back(Pred);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  DenseMap<DebugVariable, DbgValue> JoinedLocs;
+
+  // Test some back-edge-specific behaviours of vloc join. Mostly: the fact that
+  // VPHIs that arrive on backedges can be eliminated, despite having different
+  // values to the predecessor.
+
+  // First: when there's no VPHI placed already, propagate the live-in value of
+  // the first RPO predecessor.
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveIns[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  bool Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  auto It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // If there is a VPHI: don't elimiante it if there are disagreeing values.
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // If we feed this VPHI back into itself though, we can eliminate it.
+  VLiveOuts[0].clear();
+  VLiveOuts[1].clear();
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // Don't eliminate backedge VPHIs if the predecessors have different
+  // properties.
+  DIExpression *NewExpr = DIExpression::prepend(EmptyExpr, DIExpression::ApplyOffset, 4);
+  DbgValueProperties PropsWithExpr(NewExpr, false);
+  VLiveOuts[1].clear();
+  VLiveOuts[1].insert({Var, DbgValue(1, PropsWithExpr, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // Backedges with VPHIs, but from the wrong block, shouldn't be eliminated.
+  VLiveOuts[1].clear();
+  VLiveOuts[1].insert({Var, DbgValue(0, EmptyProps, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+}
+
+TEST_F(InstrRefLDVTest, vlocJoinBadlyNestedLoops) {
+  // Test PHI elimination in the presence of multiple backedges.
+  setupBadlyNestedLoops();
+  //           entry
+  //             |
+  //           loop1 -o
+  //             | ^
+  //             | ^
+  //           loop2 -o
+  //             | ^
+  //             | ^
+  //           loop3 -o
+  //             |
+  //            ret
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+  Register RBX = getRegByName("RBX");
+  LocIdx RbxLoc = MTracker->lookupOrTrackRegister(RBX);
+
+  unsigned EntryBlk = 0;
+
+  ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax(EntryBlk, 0, RaxLoc);
+  ValueIDNum LiveInRbx(EntryBlk, 0, RbxLoc);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+  SmallVector<DenseMap<DebugVariable, DbgValue>, 32> VLiveOuts, VLiveIns;
+  VLiveOuts.resize(5);
+  VLiveIns.resize(5);
+  InstrRefBasedLDV::LiveIdxT VLiveOutIdx, VLiveInIdx;
+  VLiveOutIdx[MBB0] = &VLiveOuts[0];
+  VLiveOutIdx[MBB1] = &VLiveOuts[1];
+  VLiveOutIdx[MBB2] = &VLiveOuts[2];
+  VLiveOutIdx[MBB3] = &VLiveOuts[3];
+  VLiveOutIdx[MBB4] = &VLiveOuts[4];
+  VLiveInIdx[MBB0] = &VLiveIns[0];
+  VLiveInIdx[MBB1] = &VLiveIns[1];
+  VLiveInIdx[MBB2] = &VLiveIns[2];
+  VLiveInIdx[MBB3] = &VLiveIns[3];
+  VLiveInIdx[MBB4] = &VLiveIns[4];
+
+  SmallPtrSet<const MachineBasicBlock *, 8> AllBlocks;
+  AllBlocks.insert(MBB0);
+  AllBlocks.insert(MBB1);
+  AllBlocks.insert(MBB2);
+  AllBlocks.insert(MBB3);
+  AllBlocks.insert(MBB4);
+
+  // We're going to focus on block 1.
+  SmallVector<const MachineBasicBlock *, 3> Preds;
+  for (const auto *Pred : MBB1->predecessors())
+    Preds.push_back(Pred);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  DenseMap<DebugVariable, DbgValue> JoinedLocs;
+
+  // Test a normal VPHI isn't eliminated.
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  VLiveOuts[2].insert({Var, DbgValue(LiveInRbx, EmptyProps, DbgValue::Def)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  bool Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  auto It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // Common VPHIs on backedges should merge.
+  VLiveOuts[0].clear();
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  VLiveOuts[2].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_TRUE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::Def);
+  EXPECT_EQ(It->second.ID, LiveInRsp);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // They shouldn't merge if one of their properties is different.
+  DbgValueProperties PropsWithIndirect(EmptyExpr, true);
+  VLiveOuts[0].clear();
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  VLiveOuts[2].insert({Var, DbgValue(1, PropsWithIndirect, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+
+  // VPHIs from different blocks should not merge.
+  VLiveOuts[0].clear();
+  VLiveOuts[1].clear();
+  VLiveOuts[2].clear();
+  VLiveOuts[0].insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLiveOuts[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  VLiveOuts[2].insert({Var, DbgValue(2, EmptyProps, DbgValue::VPHI)});
+  VLiveIns[1].insert({Var, DbgValue(1, EmptyProps, DbgValue::VPHI)});
+  Result = vlocJoin(*MBB1, VLiveOutIdx, VLiveInIdx, AllVars,
+                    AllBlocks, AllBlocks, JoinedLocs);
+  EXPECT_FALSE(Result);
+  It = VLiveIns[1].find(Var);
+  EXPECT_EQ(It->second.Kind, DbgValue::VPHI);
+  EXPECT_EQ(It->second.BlockNo, 1);
+  JoinedLocs.clear();
+  VLiveIns[1].clear();
+}
+
+// Above are tests for picking VPHI locations, and eliminating VPHIs. No
+// unit-tests are written for evaluating the transfer function as that's
+// pretty straight forwards, or applying VPHI-location-picking to live-ins.
+// Instead, pre-set some machine locations and apply buildVLocValueMap to the
+// existing CFG patterns.
+TEST_F(InstrRefLDVTest, VLocSingleBlock) {
+  setupSingleBlock();
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+
+  ValueIDNum InLocs[2], OutLocs[2];
+  ValueIDNum *InLocsPtr[1] = {&InLocs[0]};
+  ValueIDNum *OutLocsPtr[1] = {&OutLocs[0]};
+
+  ValueIDNum LiveInRsp = ValueIDNum(0, 0, RspLoc);
+  InLocs[0] = OutLocs[0] = LiveInRsp;
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  // Mild hack: rather than constructing machine instructions in each block
+  // and creating lexical scopes across them, instead just tell
+  // buildVLocValueMap that there's an assignment in every block. That makes
+  // every block in scope.
+  SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
+  AssignBlocks.insert(MBB0);
+
+  SmallVector<VLocTracker, 1> VLocs;
+  VLocs.resize(1);
+
+  InstrRefBasedLDV::LiveInsT Output;
+
+  // Test that, with no assignments at all, no mappings are created for the
+  // variable in this function.
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output.size(), 0ul);
+
+  // If we put an assignment in the transfer function, that should... well,
+  // do nothing, because we don't store the live-outs.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output.size(), 0ul);
+
+  // There is pretty much nothing else of interest to test with a single block.
+  // It's not relevant to the SSA-construction parts of variable values.
+}
+
+TEST_F(InstrRefLDVTest, VLocDiamondBlocks) {
+  setupDiamondBlocks();
+  //        entry
+  //        /  \
+  //      br1  br2
+  //        \  /
+  //         ret
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  unsigned EntryBlk = 0, RetBlk = 3;
+
+  ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk3 = ValueIDNum(RetBlk, 0, RspLoc);
+
+  ValueIDNum InLocs[4][2], OutLocs[4][2];
+  ValueIDNum *InLocsPtr[4] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3]};
+  ValueIDNum *OutLocsPtr[4] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3]};
+
+  initValueArray(InLocsPtr, 4, 2);
+  initValueArray(OutLocsPtr, 4, 2);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  // Mild hack: rather than constructing machine instructions in each block
+  // and creating lexical scopes across them, instead just tell
+  // buildVLocValueMap that there's an assignment in every block. That makes
+  // every block in scope.
+  SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
+  AssignBlocks.insert(MBB0);
+  AssignBlocks.insert(MBB1);
+  AssignBlocks.insert(MBB2);
+  AssignBlocks.insert(MBB3);
+
+  SmallVector<VLocTracker, 1> VLocs;
+  VLocs.resize(4);
+
+  InstrRefBasedLDV::LiveInsT Output;
+
+  // Start off with LiveInRsp in every location.
+  for (unsigned int I = 0; I < 4; ++I) {
+    InLocs[I][0] = InLocs[I][1] = LiveInRsp;
+    OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
+  }
+
+  auto ClearOutputs = [&]() {
+    for (auto &Elem : Output)
+      Elem.clear();
+  };
+  Output.resize(4);
+
+  // No assignments -> no values.
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+
+  // An assignment in the end block should also not affect other blocks; or
+  // produce any live-ins.
+  VLocs[3].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  ClearOutputs();
+
+  // Assignments in either of the side-of-diamond blocks should also not be
+  // propagated anywhere.
+  VLocs[3].Vars.clear();
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  VLocs[2].Vars.clear();
+  ClearOutputs();
+
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  VLocs[1].Vars.clear();
+  ClearOutputs();
+
+  // However: putting an assignment in the first block should propagate variable
+  // values through to all other blocks, as it dominates.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+
+  // Additionally, even if that value isn't available in the register file, it
+  // should still be propagated, as buildVLocValueMap shouldn't care about
+  // what's in the registers (except for PHIs).
+  // values through to all other blocks, as it dominates.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+
+  // We should get a live-in to the merging block, if there are two assigns of
+  // the same value in either side of the diamond.
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[1].Vars.clear();
+  VLocs[2].Vars.clear();
+
+  // If we assign a value in the entry block, then 'undef' on a branch, we
+  // shouldn't have a live-in in the merge block.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(EmptyProps, DbgValue::Undef)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Having different values joining into the merge block should mean we have
+  // no live-in in that block. Block ones LiveInRax value doesn't appear as a
+  // live-in anywhere, it's block internal.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // But on the other hand, if there's a location in the register file where
+  // those two values can be joined, do so.
+  OutLocs[1][0] = LiveInRax;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, RspPHIInBlk3);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+}
+
+TEST_F(InstrRefLDVTest, VLocSimpleLoop) {
+  setupSimpleLoop();
+  //    entry
+  //     |
+  //     |/-----\
+  //    loopblk |
+  //     |\-----/
+  //     |
+  //     ret
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  unsigned EntryBlk = 0, LoopBlk = 1;
+
+  ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk1 = ValueIDNum(LoopBlk, 0, RspLoc);
+  ValueIDNum RspDefInBlk1 = ValueIDNum(LoopBlk, 1, RspLoc);
+  ValueIDNum RaxPHIInBlk1 = ValueIDNum(LoopBlk, 0, RaxLoc);
+
+  ValueIDNum InLocs[3][2], OutLocs[3][2];
+  ValueIDNum *InLocsPtr[3] = {InLocs[0], InLocs[1], InLocs[2]};
+  ValueIDNum *OutLocsPtr[3] = {OutLocs[0], OutLocs[1], OutLocs[2]};
+
+  initValueArray(InLocsPtr, 3, 2);
+  initValueArray(OutLocsPtr, 3, 2);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  SmallPtrSet<MachineBasicBlock *, 4> AssignBlocks;
+  AssignBlocks.insert(MBB0);
+  AssignBlocks.insert(MBB1);
+  AssignBlocks.insert(MBB2);
+
+  SmallVector<VLocTracker, 3> VLocs;
+  VLocs.resize(3);
+
+  InstrRefBasedLDV::LiveInsT Output;
+
+  // Start off with LiveInRsp in every location.
+  for (unsigned int I = 0; I < 3; ++I) {
+    InLocs[I][0] = InLocs[I][1] = LiveInRsp;
+    OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
+  }
+
+  auto ClearOutputs = [&]() {
+    for (auto &Elem : Output)
+      Elem.clear();
+  };
+  Output.resize(3);
+
+  // Easy starter: a dominating assign should propagate to all blocks.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Put an undef assignment in the loop. Should get no live-in value.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(EmptyProps, DbgValue::Undef)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Assignment of the same value should naturally join.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Assignment of different values shouldn't join with no machine PHI vals.
+  // Will be live-in to exit block as it's dominated.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Install a completely unrelated PHI value, that we should not join on. Try
+  // with unrelated assign in loop block again.
+  InLocs[1][0] = RspPHIInBlk1;
+  OutLocs[1][0] = RspDefInBlk1;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Now, if we assign RspDefInBlk1 in the loop block, we should be able to
+  // find the appropriate PHI.
+  InLocs[1][0] = RspPHIInBlk1;
+  OutLocs[1][0] = RspDefInBlk1;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(RspDefInBlk1, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, RspPHIInBlk1);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, RspDefInBlk1);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // If the PHI happens in a different location, the live-in should happen
+  // there.
+  InLocs[1][0] = LiveInRsp;
+  OutLocs[1][0] = LiveInRsp;
+  InLocs[1][1] = RaxPHIInBlk1;
+  OutLocs[1][1] = RspDefInBlk1;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(RspDefInBlk1, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, RaxPHIInBlk1);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, RspDefInBlk1);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // The PHI happening in both places should be handled too. Exactly where
+  // isn't important, but if the location picked changes, this test will let
+  // you know.
+  InLocs[1][0] = RaxPHIInBlk1;
+  OutLocs[1][0] = RspDefInBlk1;
+  InLocs[1][1] = RaxPHIInBlk1;
+  OutLocs[1][1] = RspDefInBlk1;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(RspDefInBlk1, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  // Today, the first register is picked.
+  EXPECT_EQ(Output[1][0].second.ID, RspPHIInBlk1);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, RspDefInBlk1);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // If the loop block looked a bit like this:
+  //    %0 = PHI %1, %2
+  //    [...]
+  //    DBG_VALUE %0
+  // Then with instr-ref it becomes:
+  //    DBG_PHI %0
+  //    [...]
+  //    DBG_INSTR_REF
+  // And we would be feeding a machine PHI-value back around the loop. However:
+  // this does not mean we can eliminate the variable value PHI and use the
+  // variable value from the entry block: they are distinct values that must be
+  // joined at some location by the control flow.
+  // [This test input would never occur naturally, the machine-PHI would be
+  //  eliminated]
+  InLocs[1][0] = RspPHIInBlk1;
+  OutLocs[1][0] = RspPHIInBlk1;
+  InLocs[1][1] = LiveInRax;
+  OutLocs[1][1] = LiveInRax;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(RspPHIInBlk1, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, RspPHIInBlk1);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, RspPHIInBlk1);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // Test that we can eliminate PHIs. A PHI will be placed at the loop head
+  // because there's a def in in.
+  InLocs[1][0] = LiveInRsp;
+  OutLocs[1][0] = LiveInRsp;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+}
+
+// test phi elimination with the nested situation
+TEST_F(InstrRefLDVTest, VLocNestedLoop) {
+  //    entry
+  //     |
+  //    loop1
+  //     ^\
+  //     | \    /-\
+  //     |  loop2  |
+  //     |  /   \-/
+  //     ^ /
+  //     join
+  //     |
+  //     ret
+  setupNestedLoops();
+
+  ASSERT_TRUE(MTracker->getNumLocs() == 1);
+  LocIdx RspLoc(0);
+  Register RAX = getRegByName("RAX");
+  LocIdx RaxLoc = MTracker->lookupOrTrackRegister(RAX);
+
+  unsigned EntryBlk = 0, Loop1Blk = 1, Loop2Blk = 2;
+
+  ValueIDNum LiveInRsp = ValueIDNum(EntryBlk, 0, RspLoc);
+  ValueIDNum LiveInRax = ValueIDNum(EntryBlk, 0, RaxLoc);
+  ValueIDNum RspPHIInBlk1 = ValueIDNum(Loop1Blk, 0, RspLoc);
+  ValueIDNum RspPHIInBlk2 = ValueIDNum(Loop2Blk, 0, RspLoc);
+  ValueIDNum RspDefInBlk2 = ValueIDNum(Loop2Blk, 1, RspLoc);
+
+  ValueIDNum InLocs[5][2], OutLocs[5][2];
+  ValueIDNum *InLocsPtr[5] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3], InLocs[4]};
+  ValueIDNum *OutLocsPtr[5] = {OutLocs[0], OutLocs[1], OutLocs[2], OutLocs[3], OutLocs[4]};
+
+  initValueArray(InLocsPtr, 5, 2);
+  initValueArray(OutLocsPtr, 5, 2);
+
+  DebugVariable Var(FuncVariable, None, nullptr);
+  DbgValueProperties EmptyProps(EmptyExpr, false);
+
+  SmallSet<DebugVariable, 4> AllVars;
+  AllVars.insert(Var);
+
+  SmallPtrSet<MachineBasicBlock *, 5> AssignBlocks;
+  AssignBlocks.insert(MBB0);
+  AssignBlocks.insert(MBB1);
+  AssignBlocks.insert(MBB2);
+  AssignBlocks.insert(MBB3);
+  AssignBlocks.insert(MBB4);
+
+  SmallVector<VLocTracker, 5> VLocs;
+  VLocs.resize(5);
+
+  InstrRefBasedLDV::LiveInsT Output;
+
+  // Start off with LiveInRsp in every location.
+  for (unsigned int I = 0; I < 5; ++I) {
+    InLocs[I][0] = InLocs[I][1] = LiveInRsp;
+    OutLocs[I][0] = OutLocs[I][1] = LiveInRsp;
+  }
+
+  auto ClearOutputs = [&]() {
+    for (auto &Elem : Output)
+      Elem.clear();
+  };
+  Output.resize(5);
+
+  // A dominating assign should propagate to all blocks.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+
+  // Test that an assign in the inner loop causes unresolved PHIs at the heads
+  // of both loops, and no output location. Dominated blocks do get values.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[2].Vars.clear();
+
+  // Same test, but with no assignment in block 0. We should still get values
+  // in dominated blocks.
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[2].Vars.clear();
+
+  // Similarly, assignments in the outer loop gives location to dominated
+  // blocks, but no PHI locations are found at the outer loop head.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[3].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  EXPECT_EQ(Output[3].size(), 0ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[3].Vars.clear();
+
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[1].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[1].Vars.clear();
+
+  // With an assignment of the same value in the inner loop, we should work out
+  // that all PHIs can be eliminated and the same value is live-through the
+  // whole function.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 1ul);
+  EXPECT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRsp);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRsp);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[2].Vars.clear();
+
+  // If we have an assignment in the inner loop, and a PHI for it at the inner
+  // loop head, we could find a live-in location for the inner loop. But because
+  // the outer loop has no PHI, we can't find a variable value for outer loop
+  // head, so can't have a live-in value for the inner loop head.
+  InLocs[2][0] = RspPHIInBlk2;
+  OutLocs[2][0] = LiveInRax;
+  // NB: all other machine locations are LiveInRsp, disallowing a PHI in block
+  // one. Even though RspPHIInBlk2 isn't available later in the function, we
+  // should still produce a live-in value. The fact it's unavailable is a
+  // different concern.
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[2].Vars.insert({Var, DbgValue(LiveInRax, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  EXPECT_EQ(Output[1].size(), 0ul);
+  EXPECT_EQ(Output[2].size(), 0ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, LiveInRax);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, LiveInRax);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[2].Vars.clear();
+
+  // Have an assignment in inner loop that can have a PHI resolved; and add a
+  // machine value PHI to the outer loop head, so that we can find a location
+  // all the way through the function.
+  InLocs[1][0] = RspPHIInBlk1;
+  OutLocs[1][0] = RspPHIInBlk1;
+  InLocs[2][0] = RspPHIInBlk2;
+  OutLocs[2][0] = RspDefInBlk2;
+  InLocs[3][0] = RspDefInBlk2;
+  OutLocs[3][0] = RspDefInBlk2;
+  VLocs[0].Vars.insert({Var, DbgValue(LiveInRsp, EmptyProps, DbgValue::Def)});
+  VLocs[2].Vars.insert({Var, DbgValue(RspDefInBlk2, EmptyProps, DbgValue::Def)});
+  buildVLocValueMap(OutermostLoc, AllVars, AssignBlocks, Output,
+                    OutLocsPtr, InLocsPtr, VLocs);
+  EXPECT_EQ(Output[0].size(), 0ul);
+  ASSERT_EQ(Output[1].size(), 1ul);
+  ASSERT_EQ(Output[2].size(), 1ul);
+  ASSERT_EQ(Output[3].size(), 1ul);
+  ASSERT_EQ(Output[4].size(), 1ul);
+  EXPECT_EQ(Output[1][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[1][0].second.ID, RspPHIInBlk1);
+  EXPECT_EQ(Output[2][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[2][0].second.ID, RspPHIInBlk2);
+  EXPECT_EQ(Output[3][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[3][0].second.ID, RspDefInBlk2);
+  EXPECT_EQ(Output[4][0].second.Kind, DbgValue::Def);
+  EXPECT_EQ(Output[4][0].second.ID, RspDefInBlk2);
+  ClearOutputs();
+  VLocs[0].Vars.clear();
+  VLocs[2].Vars.clear();
+}
+