[DebugInstrRef][1/3] Track PHI values through register allocation

[jmorse]

Summary

(Context: the patch series' at D83046 and D85741). This series tracks PHI instructions through register allocation -- which in the original RFC, I wrote:

"My understanding is that the register allocation phase of LLVM starts there [phielim] and ends after virtregrewriter, and it'd be legitimate to say "we do special things for these passes"."

This patch introduces the "special things": in PHI Elimination we record the position of any PHI instruction that is eliminated, its register and debug instruction number. The register is updated through register allocation; and afterwards, we emit a 'DBG_PHI' instruction identifying the physreg / stack slot where the PHI occurs.

An example of the DBG_PHI instruction working would be:

bb1:
   DBG_PHI $rax, 1
   [... more insts ... ]
bb2:
   DBG_INSTR_REF 1, 0

The DBG_PHI identifies the position at which the PHI occurs ($rax here) for debug instruction 1, which can then be picked up by instruction-referencing LiveDebugValues, and tracked until a DBG_INSTR_REF instruction uses that debug instruction number.

This may look a bit like a DBG_VALUE, but it isn't: by using two instructions, we've separated two really important parts of variable value tracking:

• Where the machine value comes from (specified by DBG_PHI),
• Where the machine value becomes the variables value.

For PHI instructions, we absolutely need a program point to identify the machine value: that's the nature of PHIs. Thus, to track PHI values, we need to put a new instruction to identify where the PHI occurs.

In this particular patch, I've added boilerplate for the DBG_PHI instruction, some data structures in MachineFunction to track PHIs during regalloc, and code in LiveDebugVariables to update locations when virtual registers are split plus emit DBG_PHIs afterwards. In the other two patches:

• Register coalescing
• Handling this all in LiveDebugValues

[aprantl]

llvm/include/llvm/CodeGen/MachineFunction.h

459

nit /// comes before the field, ///< after.

llvm/lib/CodeGen/LiveDebugVariables.cpp

413

do we need the sorted-ness of the map for determinism, or could we use a DenseMap?

llvm/lib/CodeGen/PHIElimination.cpp

324

insert({ID, p});

[jmorse]

Address comments; add a test for creating DBG_PHIs for PHIs that happen in spill slots.

(I also suggested a test was needed for sub-register inputs; however on further examination, you can't PHI unequal register classes, so subregisters don't enter the picture at that stage).

[dstenb]

Just some drive-by nits while familiarizing myself with this patch series.

llvm/include/llvm/CodeGen/MachineFunction.h

455

maintenance.

llvm/lib/CodeGen/LiveDebugVariables.cpp

410

///

llvm/lib/CodeGen/PrologEpilogInserter.cpp

1243

Nit: Capital letter and period.

[jmorse]

Revise some dodgy comments, cheers!

[jmorse]

ping; (also remove from summary the reference to additional tests needed, as these are now in the patch).

[jmorse]

'Tis the season to ping!

Note that I'm very comfortable with Stephens patches having a higher priority than these; they're less of a conceptual difference and appear to be yielding a good improvement :)

[djtodoro]

LGTM, some nits inline. Thanks.

llvm/include/llvm/CodeGen/MachineFunction.h

468

Do we need the std::map sortness? Can we use llvm::DenseMap instead?

llvm/lib/CodeGen/LiveDebugVariables.cpp

1226

should be capital letter

1587–1589

I guess we do not need the else here.

llvm/lib/CodeGen/PHIElimination.cpp

323–324

these should be capital letters, I guess

llvm/lib/CodeGen/PrologEpilogInserter.cpp

1243

the comment should go above the line

llvm/test/DebugInfo/MIR/InstrRef/phi-regallocd-to-stack.mir

22–28

unused, could be deleted

llvm/test/DebugInfo/MIR/InstrRef/phi-through-regalloc.mir

51–52

unused, could be deleted

[jmorse]

Ping and update for @djtodoro 's comments -- some minor editing and deleting of un-necessary parts of tests.

Now that I'm confident that the overall approach is sound (see D102158), I'd like to put this patch series back into peoples minds again.

Promoting from inline:

Do we need the std::map sortness? Can we use llvm::DenseMap instead?

No, and I've removed it in this revision. I've been pursuing a "don't prematurely optimise" approach during development, but it makes sense to optimise when actually committing things.

[jmorse]

NB: I'll probably drop this in sometimes soon, on the back of @djtodoro 's LGTM earlier

[djtodoro]

Still LGTM.

llvm/include/llvm/CodeGen/MachineFunction.h

public:
   using DebugInstrOperandPair = std::pair<unsigned, unsigned>;
 
   /// Substitution map: from one <inst,operand> pair to another. Used to
   /// record changes in where a value is defined, so that debug variable
   /// locations can find it later.
   std::map<DebugInstrOperandPair, DebugInstrOperandPair>
       DebugValueSubstitutions;
 
+  /// Location of a PHI instruction that is also a debug-info variable value,
+  /// for the duration of register allocation. Loaded by the PHI-elimination
+  /// pass, and emitted as DBG_PHI instructions during VirtRegRewriter, with
+  /// maintenence applied by intermediate passes that edit registers (such as
+  /// coalescing and the allocator passes).
+  class DebugPHIRegallocPos {
+  public:
+    MachineBasicBlock *MBB; ///< Block where this PHI was originally located.
+    Register Reg;           ///< VReg where the control-flow-merge happens.
+    unsigned SubReg;        ///< Optional subreg qualifier within Reg.
+    DebugPHIRegallocPos(MachineBasicBlock *MBB, Register Reg, unsigned SubReg)
+        : MBB(MBB), Reg(Reg), SubReg(SubReg) {}
+  };
+
+  /// Map of debug instruction numbers to the position of their PHI instructions
+  /// during register allocation. See DebugPHIRegallocPos.
+  std::map<unsigned, DebugPHIRegallocPos> DebugPHIPositions;
+
   /// Create a substitution between one <instr,operand> value to a different,
   /// new value.
   void makeDebugValueSubstitution(DebugInstrOperandPair, DebugInstrOperandPair);
 
   /// Create substitutions for any tracked values in \p Old, to point at
   /// \p New. Needed when we re-create an instruction during optimization,
   /// which has the same signature (i.e., def operands in the same place) but
   /// a modified instruction type, flags, or otherwise. An example: X86 moves

llvm/include/llvm/CodeGen/MachineInstr.h

public:
   }
 
   // True if the instruction represents a position in the function.
   bool isPosition() const { return isLabel() || isCFIInstruction(); }
 
   bool isDebugValue() const { return getOpcode() == TargetOpcode::DBG_VALUE; }
   bool isDebugLabel() const { return getOpcode() == TargetOpcode::DBG_LABEL; }
   bool isDebugRef() const { return getOpcode() == TargetOpcode::DBG_INSTR_REF; }
+  bool isDebugPHI() const { return getOpcode() == TargetOpcode::DBG_PHI; }
   bool isDebugInstr() const {
-    return isDebugValue() || isDebugLabel() || isDebugRef();
+    return isDebugValue() || isDebugLabel() || isDebugRef() || isDebugPHI();
   }
 
   bool isDebugOffsetImm() const { return getDebugOffset().isImm(); }
 
   /// A DBG_VALUE is indirect iff the location operand is a register and
   /// the offset operand is an immediate.
   bool isIndirectDebugValue() const {
     return isDebugValue() && getDebugOperand(0).isReg() && isDebugOffsetImm();
default:
       return false;
     case TargetOpcode::IMPLICIT_DEF:
     case TargetOpcode::KILL:
     case TargetOpcode::CFI_INSTRUCTION:
     case TargetOpcode::EH_LABEL:
     case TargetOpcode::GC_LABEL:
     case TargetOpcode::DBG_VALUE:
     case TargetOpcode::DBG_INSTR_REF:
+    case TargetOpcode::DBG_PHI:
     case TargetOpcode::DBG_LABEL:
     case TargetOpcode::LIFETIME_START:
     case TargetOpcode::LIFETIME_END:
       return true;
     }
   }
 
   /// Return true if this is a transient instruction that is either very likely

llvm/include/llvm/Support/TargetOpcodes.def

 
 /// DBG_VALUE - a mapping of the llvm.dbg.value intrinsic
 HANDLE_TARGET_OPCODE(DBG_VALUE)
 
 /// DBG_INSTR_REF - A mapping of llvm.dbg.value referring to the instruction
 /// that defines the value, rather than a virtual register.
 HANDLE_TARGET_OPCODE(DBG_INSTR_REF)
 
+/// DBG_PHI - remainder of a PHI, identifies a program point where values
+/// merge under control flow.
+HANDLE_TARGET_OPCODE(DBG_PHI)
+
 /// DBG_LABEL - a mapping of the llvm.dbg.label intrinsic
 HANDLE_TARGET_OPCODE(DBG_LABEL)
 
 /// REG_SEQUENCE - This variadic instruction is used to form a register that
 /// represents a consecutive sequence of sub-registers. It's used as a
 /// register coalescing / allocation aid and must be eliminated before code
 /// emission.
 // In SDNode form, the first operand encodes the register class created by

llvm/include/llvm/Target/Target.td

def DBG_VALUE : StandardPseudoInstruction {
   let hasSideEffects = 0;
 }
 def DBG_INSTR_REF : StandardPseudoInstruction {
   let OutOperandList = (outs);
   let InOperandList = (ins variable_ops);
   let AsmString = "DBG_INSTR_REF";
   let hasSideEffects = 0;
 }
+def DBG_PHI : StandardPseudoInstruction {
+  let OutOperandList = (outs);
+  let InOperandList = (ins variable_ops);
+  let AsmString = "DBG_PHI";
+  let hasSideEffects = 0;
+}
 def DBG_LABEL : StandardPseudoInstruction {
   let OutOperandList = (outs);
   let InOperandList = (ins unknown:$label);
   let AsmString = "DBG_LABEL";
   let hasSideEffects = 0;
 }
 def REG_SEQUENCE : StandardPseudoInstruction {
   let OutOperandList = (outs unknown:$dst);

llvm/lib/CodeGen/AsmPrinter/AsmPrinter.cpp

for (auto &MI : MBB) {
             emitInstruction(&MI);
         }
         break;
       case TargetOpcode::DBG_INSTR_REF:
         // This instruction reference will have been resolved to a machine
         // location, and a nearby DBG_VALUE created. We can safely ignore
         // the instruction reference.
         break;
+      case TargetOpcode::DBG_PHI:
+        // This instruction is only used to label a program point, it's purely
+        // meta information.
+        break;
       case TargetOpcode::DBG_LABEL:
         if (isVerbose()) {
           if (!emitDebugLabelComment(&MI, *this))
             emitInstruction(&MI);
         }
         break;
       case TargetOpcode::IMPLICIT_DEF:
         if (isVerbose()) emitImplicitDef(&MI);

llvm/lib/CodeGen/LiveDebugVariables.cpp

class LDVImpl {
   LocMap::Allocator allocator;
   MachineFunction *MF = nullptr;
   LiveIntervals *LIS;
   const TargetRegisterInfo *TRI;
 
   using StashedInstrRef =
       std::tuple<unsigned, unsigned, const DILocalVariable *,
                  const DIExpression *, DebugLoc>;
+
+  /// Position and VReg of a PHI instruction during register allocation.
+  struct PHIValPos {
+    SlotIndex SI;    /// Slot where this PHI occurs.
+    Register Reg;    /// VReg this PHI occurs in.
+    unsigned SubReg; /// Qualifiying subregister for Reg.
+  };
+
+  /// Map from debug instruction number to PHI position during allocation.
+  std::map<unsigned, PHIValPos> PHIValToPos;
+  // Index of, for each VReg, which debug instruction numbers and corresponding
+  /// PHIs are sensitive to splitting. Each VReg may have multiple PHI defs,
+  /// at different positions.
+  DenseMap<Register, std::vector<unsigned>> RegToPHIIdx;
+
   std::map<SlotIndex, std::vector<StashedInstrRef>> StashedInstrReferences;
 
   /// Whether emitDebugValues is called.
   bool EmitDone = false;
 
   /// Whether the machine function is modified during the pass.
   bool ModifiedMF = false;
 

 public:
   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 
   bool runOnMachineFunction(MachineFunction &mf);
 
   /// Release all memory.
   void clear() {
     MF = nullptr;
+    PHIValToPos.clear();
+    RegToPHIIdx.clear();
     StashedInstrReferences.clear();
     userValues.clear();
     userLabels.clear();
     virtRegToEqClass.clear();
     userVarMap.clear();
     // Make sure we call emitDebugValues if the machine function was modified.
     assert((!ModifiedMF || EmitDone) &&
            "Dbg values are not emitted in LDV");
     EmitDone = false;
     ModifiedMF = false;
   }
 
   /// Map virtual register to an equivalence class.
   void mapVirtReg(Register VirtReg, UserValue *EC);
 
+  /// Replace any PHI referring to OldReg with its corresponding NewReg, if
+  /// present.
+  void splitPHIRegister(Register OldReg, ArrayRef<Register> NewRegs);
+
   /// Replace all references to OldReg with NewRegs.
   void splitRegister(Register OldReg, ArrayRef<Register> NewRegs);
 
   /// Recreate DBG_VALUE instruction from data structures.
   void emitDebugValues(VirtRegMap *VRM);
 
   void print(raw_ostream&);
 };
bool LDVImpl::runOnMachineFunction(MachineFunction &mf) {
   LIS = &pass.getAnalysis<LiveIntervals>();
   TRI = mf.getSubtarget().getRegisterInfo();
   LLVM_DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: "
                     << mf.getName() << " **********\n");
 
   bool Changed = collectDebugValues(mf);
   computeIntervals();
   LLVM_DEBUG(print(dbgs()));
+
+  // Collect the set of VReg / SlotIndexs where PHIs occur; index the sensitive
+  // VRegs too, for when we're notified of a range split.
+  SlotIndexes *Slots = LIS->getSlotIndexes();
+  for (const auto &PHIIt : MF->DebugPHIPositions) {
+    const MachineFunction::DebugPHIRegallocPos &Position = PHIIt.second;
+    MachineBasicBlock *MBB = Position.MBB;
+    Register Reg = Position.Reg;
+    unsigned SubReg = Position.SubReg;
+    SlotIndex SI = Slots->getMBBStartIdx(MBB);
+    PHIValPos VP = {SI, Reg, SubReg};
+    PHIValToPos.insert(std::make_pair(PHIIt.first, VP));
+    RegToPHIIdx[Reg].push_back(PHIIt.first);
+  }
+
   ModifiedMF = Changed;
   return Changed;
 }
 
 static void removeDebugValues(MachineFunction &mf) {
   for (MachineBasicBlock &MBB : mf) {
     for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) {
       if (!MBBI->isDebugValue()) {
for (unsigned i = locations.size(); i ; --i) {
     const MachineOperand *Loc = &locations[LocNo];
     if (!Loc->isReg() || Loc->getReg() != OldReg)
       continue;
     DidChange |= splitLocation(LocNo, NewRegs, LIS);
   }
   return DidChange;
 }
 
+void LDVImpl::splitPHIRegister(Register OldReg, ArrayRef<Register> NewRegs) {
+  auto RegIt = RegToPHIIdx.find(OldReg);
+  if (RegIt == RegToPHIIdx.end())
+    return;
+
+  std::vector<std::pair<Register, unsigned>> NewRegIdxes;
+  // Iterate over all the debug instruction numbers affected by this split.
+  for (unsigned InstrID : RegIt->second) {
+    auto PHIIt = PHIValToPos.find(InstrID);
+    assert(PHIIt != PHIValToPos.end());
+    const SlotIndex &Slot = PHIIt->second.SI;
+#ifndef NDEBUG
+    Register r = PHIIt->second.Reg;
+    assert(r == OldReg);
+#endif
+
+    // Find the new register that covers this position.
+    for (auto NewReg : NewRegs) {
+      const LiveInterval &LI = LIS->getInterval(NewReg);
+      auto LII = LI.find(Slot);
+      if (LII != LI.end() && LII->start <= Slot) {
+        // This new register covers this PHI position, record this for indexing.
+        NewRegIdxes.push_back(std::make_pair(NewReg, InstrID));
+        // Record that this value lives in a different VReg now.
+        PHIIt->second.Reg = NewReg;
+        break;
+      }
+    }
+
+    // If we do not find a new register covering this PHI, then register
+    // allocation has dropped its location, for example because it's not live.
+    // The old VReg will not be mapped to a physreg, and the instruction
+    // number will have been optimized out.
+  }
+
+  // Re-create register index using the new register numbers.
+  RegToPHIIdx.erase(RegIt);
+  for (auto &RegAndInstr : NewRegIdxes)
+    RegToPHIIdx[RegAndInstr.first].push_back(RegAndInstr.second);
+}
+
 void LDVImpl::splitRegister(Register OldReg, ArrayRef<Register> NewRegs) {
+  // Consider whether this split range affects any PHI locations.
+  splitPHIRegister(OldReg, NewRegs);
+
+  // Check whether any intervals mapped by a DBG_VALUE were split and need
+  // updating.
   bool DidChange = false;
   for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
     DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
 
   if (!DidChange)
     return;
 
   // Map all of the new virtual registers.
for (auto &userValue : userValues) {
     userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets);
   }
   LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n");
   for (auto &userLabel : userLabels) {
     LLVM_DEBUG(userLabel->print(dbgs(), TRI));
     userLabel->emitDebugLabel(*LIS, *TII);
   }
 
+  LLVM_DEBUG(dbgs() << "********** EMITTING DEBUG PHIS **********\n");
+
+  auto Slots = LIS->getSlotIndexes();
+  for (auto &It : PHIValToPos) {
+    // For each ex-PHI, identify its physreg location or stack slot, and emit
+    // a DBG_PHI for it.
+    unsigned InstNum = It.first;
+    auto Slot = It.second.SI;
+    Register Reg = It.second.Reg;
+    unsigned SubReg = It.second.SubReg;
+
+    MachineBasicBlock *OrigMBB = Slots->getMBBFromIndex(Slot);
+    if (VRM->isAssignedReg(Reg) &&
+        Register::isPhysicalRegister(VRM->getPhys(Reg))) {
+      unsigned PhysReg = VRM->getPhys(Reg);
+      if (SubReg != 0)
+        PhysReg = TRI->getSubReg(PhysReg, SubReg);
+
+      auto Builder = BuildMI(*OrigMBB, OrigMBB->begin(), DebugLoc(),
+                             TII->get(TargetOpcode::DBG_PHI));
+      Builder.addReg(PhysReg);
+      Builder.addImm(InstNum);
+    } else if (VRM->getStackSlot(Reg) != VirtRegMap::NO_STACK_SLOT) {
+      const MachineRegisterInfo &MRI = MF->getRegInfo();
+      const TargetRegisterClass *TRC = MRI.getRegClass(Reg);
+      unsigned SpillSize, SpillOffset;
+
+      // Test whether this location is legal with the given subreg.
+      bool Success =
+          TII->getStackSlotRange(TRC, SubReg, SpillSize, SpillOffset, *MF);
+
+      if (Success) {
+        auto Builder = BuildMI(*OrigMBB, OrigMBB->begin(), DebugLoc(),
+                               TII->get(TargetOpcode::DBG_PHI));
+        Builder.addFrameIndex(VRM->getStackSlot(Reg));
+        Builder.addImm(InstNum);
+      }
+    } else {
+      // There is no mapping for this value ID, it's gone. Create no DBG_PHI.
+    }
+  }
+  MF->DebugPHIPositions.clear();
+
   LLVM_DEBUG(dbgs() << "********** EMITTING INSTR REFERENCES **********\n");
 
   // Re-insert any DBG_INSTR_REFs back in the position they were. Ordering
   // is preserved by vector.
-  auto Slots = LIS->getSlotIndexes();
   const MCInstrDesc &RefII = TII->get(TargetOpcode::DBG_INSTR_REF);
   for (auto &P : StashedInstrReferences) {
     const SlotIndex &Idx = P.first;
     auto *MBB = Slots->getMBBFromIndex(Idx);
     MachineBasicBlock::iterator insertPos = findInsertLocation(MBB, Idx, *LIS);
     for (auto &Stashed : P.second) {
       auto MIB = BuildMI(*MF, std::get<4>(Stashed), RefII);
       MIB.addImm(std::get<0>(Stashed));

llvm/lib/CodeGen/PHIElimination.cpp

if (entry) {
       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);
       entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC);
     }
     // Give the target possiblity to handle special cases fallthrough otherwise
     PHICopy = TII->createPHIDestinationCopy(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
                                   IncomingReg, DestReg);
   }
 
+  if (MPhi->peekDebugInstrNum()) {
+    // If referred to by debug-info, store where this PHI was.
+    MachineFunction *MF = MBB.getParent();
+    unsigned ID = MPhi->peekDebugInstrNum();
+    auto p = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);
+    auto res = MF->DebugPHIPositions.insert({ID, p});
+    assert(res.second);
+    (void)res;
+  }
+
   // Update live variable information if there is any.
   if (LV) {
     if (IncomingReg) {
       LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
 
       // Increment use count of the newly created virtual register.
       LV->setPHIJoin(IncomingReg);
 

llvm/lib/CodeGen/PrologEpilogInserter.cpp

for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
           bool WithStackValue = true;
           DIExpr = DIExpression::prependOpcodes(DIExpr, Ops, WithStackValue);
           // Make the DBG_VALUE direct.
           MI.getDebugOffset().ChangeToRegister(0, false);
         }
         DIExpr = DIExpression::prepend(DIExpr, PrependFlags, Offset);
         MI.getDebugExpressionOp().setMetadata(DIExpr);
         continue;
+      } else if (MI.isDebugPHI()) {
+        continue; // allow stack ref to continue onwards
       }
 
       // TODO: This code should be commoned with the code for
       // PATCHPOINT. There's no good reason for the difference in
       // implementation other than historical accident.  The only
       // remaining difference is the unconditional use of the stack
       // pointer as the base register.
       if (MI.getOpcode() == TargetOpcode::STATEPOINT) {

llvm/test/DebugInfo/MIR/InstrRef/phi-regallocd-to-stack.mir

+# RUN: llc %s -o - -mtriple=x86_64-unknown-unknown \
+# RUN:    -experimental-debug-variable-locations \
+# RUN:    -run-pass=phi-node-elimination,livedebugvars,greedy,virtregrewriter \
+# RUN:    | FileCheck %s
+#
+# Like phi-through-regalloc.mir, pass a PHI node into register allocation, and
+# test that it correctly comes out, in a stack slot. Fifteen spurious PHIs have
+# been added to force the register allocator to spill one.
+
+--- |
+  ; ModuleID = 'promoted.ll'
+  source_filename = "test.c"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  define dso_local i32 @foo(i32 %bar, i32 %baz) !dbg !7 {
+  entry:
+    ret i32 0, !dbg !19
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.declare(metadata, metadata, metadata) #0
+  
+  declare dso_local i32 @ext(i32)
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+  
+  attributes #0 = { nounwind readnone speculatable willreturn }
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", directory: ".")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"."}
+  !7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !DILocalVariable(name: "bar", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !12 = !DILocation(line: 0, scope: !7)
+  !13 = !DILocalVariable(name: "baz", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "either", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 4, column: 7, scope: !16)
+  !16 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 7)
+  !17 = !DILocation(line: 4, column: 7, scope: !7)
+  !18 = !DILocation(line: 0, scope: !16)
+  !19 = !DILocation(line: 9, column: 3, scope: !7)
+
+...
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr32 }
+  - { id: 4, class: gr32 }
+liveins:
+  - { reg: '$edi', virtual-reg: '%1' }
+  - { reg: '$esi', virtual-reg: '%2' }
+frameInfo:
+  maxAlignment:    1
+  hasCalls:        true
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: bb.0:
+  ; CHECK:       renamable $ebp = COPY $edi
+  ; CHECK:       MOV32mr %stack.1, 1, $noreg, 0, $noreg, killed renamable $ebp
+  bb.0:
+    successors: %bb.2(0x50000000), %bb.1(0x30000000)
+    liveins: $edi, $esi
+  
+    DBG_VALUE $edi, $noreg, !11, !DIExpression(), debug-location !12
+    DBG_VALUE $esi, $noreg, !13, !DIExpression(), debug-location !12
+    %2:gr32 = COPY killed $esi
+    DBG_VALUE %2, $noreg, !13, !DIExpression(), debug-location !12
+    %1:gr32 = COPY killed $edi
+    DBG_VALUE %1, $noreg, !11, !DIExpression(), debug-location !12
+    DBG_VALUE 0, $noreg, !14, !DIExpression(), debug-location !12
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp, debug-location !15
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    $edi = COPY killed %3, debug-location !15
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax, debug-location !15
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp, debug-location !15
+    %4:gr32 = COPY killed $eax, debug-location !15
+    %10:gr32 = MOV32ri 0
+    %11:gr32 = MOV32ri 1
+    %12:gr32 = MOV32ri 2
+    %13:gr32 = MOV32ri 3
+    %14:gr32 = MOV32ri 4
+    %15:gr32 = MOV32ri 5
+    %16:gr32 = MOV32ri 6
+    %17:gr32 = MOV32ri 7
+    %18:gr32 = MOV32ri 8
+    %19:gr32 = MOV32ri 9
+    %20:gr32 = MOV32ri 10
+    %21:gr32 = MOV32ri 11
+    %22:gr32 = MOV32ri 12
+    %23:gr32 = MOV32ri 13
+    %24:gr32 = MOV32ri 14
+    TEST32rr killed %4, %4, implicit-def $eflags, debug-location !15
+    JCC_1 %bb.2, 5, implicit killed $eflags, debug-location !17
+    JMP_1 %bb.1, debug-location !17
+  
+  bb.1:
+    DBG_VALUE %2, $noreg, !14, !DIExpression(), debug-location !12
+    %30:gr32 = MOV32ri 0
+    %31:gr32 = MOV32ri 1
+    %32:gr32 = MOV32ri 2
+    %33:gr32 = MOV32ri 3
+    %34:gr32 = MOV32ri 4
+    %35:gr32 = MOV32ri 5
+    %36:gr32 = MOV32ri 6
+    %37:gr32 = MOV32ri 7
+    %38:gr32 = MOV32ri 8
+    %39:gr32 = MOV32ri 9
+    %40:gr32 = MOV32ri 10
+    %41:gr32 = MOV32ri 11
+    %42:gr32 = MOV32ri 12
+    %43:gr32 = MOV32ri 13
+    %44:gr32 = MOV32ri 14
+
+    ; CHECK-LABEL: bb.2:
+  bb.2:
+    %0:gr32 = PHI %1, %bb.0, %2, %bb.1, debug-instr-number 1, debug-location !18
+    %50:gr32 = PHI %10, %bb.0, %30, %bb.1, debug-location !18
+    %51:gr32 = PHI %11, %bb.0, %31, %bb.1, debug-location !18
+    %52:gr32 = PHI %12, %bb.0, %32, %bb.1, debug-location !18
+    %53:gr32 = PHI %13, %bb.0, %33, %bb.1, debug-location !18
+    %54:gr32 = PHI %14, %bb.0, %34, %bb.1, debug-location !18
+    %55:gr32 = PHI %15, %bb.0, %35, %bb.1, debug-location !18
+    %56:gr32 = PHI %16, %bb.0, %36, %bb.1, debug-location !18
+    %57:gr32 = PHI %17, %bb.0, %37, %bb.1, debug-location !18
+    %58:gr32 = PHI %18, %bb.0, %38, %bb.1, debug-location !18
+    %59:gr32 = PHI %19, %bb.0, %39, %bb.1, debug-location !18
+    %60:gr32 = PHI %20, %bb.0, %40, %bb.1, debug-location !18
+    %61:gr32 = PHI %21, %bb.0, %41, %bb.1, debug-location !18
+    %62:gr32 = PHI %22, %bb.0, %42, %bb.1, debug-location !18
+    %63:gr32 = PHI %23, %bb.0, %43, %bb.1, debug-location !18
+    %64:gr32 = PHI %24, %bb.0, %44, %bb.1, debug-location !18
+
+    DBG_INSTR_REF 1, 0, !14, !DIExpression(), debug-location !12
+    ; CHECK:      DBG_PHI %stack.1, 1
+    ; CHECK:      renamable $eax = MOV32rm %stack.1,
+    ; CHECK:      DBG_INSTR_REF 1, 0
+    $eax = COPY killed %0, debug-location !19
+    RET 0, killed $eax, debug-location !19
+
+...

llvm/test/DebugInfo/MIR/InstrRef/phi-through-regalloc.mir

+# RUN: llc %s -o - -mtriple=x86_64-unknown-unknown \
+# RUN:    -experimental-debug-variable-locations \
+# RUN:    -run-pass=phi-node-elimination,livedebugvars,greedy,virtregrewriter \
+# RUN:    | FileCheck %s
+#
+# This test checks that for a very simple PHI, we produce a corresponding
+# DBG_PHI instruction, that a DBG_INSTR_REF refers to. Tests the path through
+# phi-node-elimination, live debug variables, and then placement after register
+# allocation.
+#
+# Original code, compiled with only -mem2reg, then fed to llc -stop-before...
+#    
+#    int ext(int);
+#    int foo(int bar, int baz) {
+#      int either = 0;
+#      if (ext(0))
+#        either = bar;
+#      else
+#        either = baz;
+#    
+#      return either;
+#    }
+#    
+
+--- |
+  ; ModuleID = 'promoted.ll'
+  source_filename = "test.c"
+  target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+  
+  define dso_local i32 @foo(i32 %bar, i32 %baz) !dbg !7 {
+  entry:
+    call void @llvm.dbg.value(metadata i32 %bar, metadata !11, metadata !DIExpression()), !dbg !12
+    call void @llvm.dbg.value(metadata i32 %baz, metadata !13, metadata !DIExpression()), !dbg !12
+    call void @llvm.dbg.value(metadata i32 0, metadata !14, metadata !DIExpression()), !dbg !12
+    %call = call i32 @ext(i32 0), !dbg !15
+    %tobool = icmp ne i32 %call, 0, !dbg !15
+    br i1 %tobool, label %if.end, label %if.else, !dbg !17
+  
+  if.else:                                          ; preds = %entry
+    call void @llvm.dbg.value(metadata i32 %baz, metadata !14, metadata !DIExpression()), !dbg !12
+    br label %if.end
+  
+  if.end:                                           ; preds = %entry, %if.else
+    %either.0 = phi i32 [ %baz, %if.else ], [ %bar, %entry ], !dbg !18
+    call void @llvm.dbg.value(metadata i32 %either.0, metadata !14, metadata !DIExpression()), !dbg !12
+    ret i32 %either.0, !dbg !19
+  }
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.declare(metadata, metadata, metadata) #0
+  
+  declare dso_local i32 @ext(i32)
+  
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+  
+  attributes #0 = { nounwind readnone speculatable willreturn }
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.c", directory: ".")
+  !2 = !{}
+  !3 = !{i32 7, !"Dwarf Version", i32 4}
+  !4 = !{i32 2, !"Debug Info Version", i32 3}
+  !5 = !{i32 1, !"wchar_size", i32 4}
+  !6 = !{!"."}
+  !7 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 2, type: !8, scopeLine: 2, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !0, retainedNodes: !2)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !11 = !DILocalVariable(name: "bar", arg: 1, scope: !7, file: !1, line: 2, type: !10)
+  !12 = !DILocation(line: 0, scope: !7)
+  !13 = !DILocalVariable(name: "baz", arg: 2, scope: !7, file: !1, line: 2, type: !10)
+  !14 = !DILocalVariable(name: "either", scope: !7, file: !1, line: 3, type: !10)
+  !15 = !DILocation(line: 4, column: 7, scope: !16)
+  !16 = distinct !DILexicalBlock(scope: !7, file: !1, line: 4, column: 7)
+  !17 = !DILocation(line: 4, column: 7, scope: !7)
+  !18 = !DILocation(line: 0, scope: !16)
+  !19 = !DILocation(line: 9, column: 3, scope: !7)
+
+...
+---
+name:            foo
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr32 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr32 }
+  - { id: 3, class: gr32 }
+  - { id: 4, class: gr32 }
+liveins:
+  - { reg: '$edi', virtual-reg: '%1' }
+  - { reg: '$esi', virtual-reg: '%2' }
+frameInfo:
+  maxAlignment:    1
+  hasCalls:        true
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    successors: %bb.2(0x50000000), %bb.1(0x30000000)
+    liveins: $edi, $esi
+  
+    DBG_VALUE $edi, $noreg, !11, !DIExpression(), debug-location !12
+    DBG_VALUE $esi, $noreg, !13, !DIExpression(), debug-location !12
+    %2:gr32 = COPY killed $esi
+    DBG_VALUE %2, $noreg, !13, !DIExpression(), debug-location !12
+    %1:gr32 = COPY killed $edi
+    DBG_VALUE %1, $noreg, !11, !DIExpression(), debug-location !12
+    DBG_VALUE 0, $noreg, !14, !DIExpression(), debug-location !12
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp, debug-location !15
+    %3:gr32 = MOV32r0 implicit-def dead $eflags
+    $edi = COPY killed %3, debug-location !15
+    CALL64pcrel32 @ext, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit-def $rsp, implicit-def $ssp, implicit-def $eax, debug-location !15
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp, debug-location !15
+    %4:gr32 = COPY killed $eax, debug-location !15
+    TEST32rr killed %4, %4, implicit-def $eflags, debug-location !15
+    JCC_1 %bb.2, 5, implicit killed $eflags, debug-location !17
+    JMP_1 %bb.1, debug-location !17
+  
+  bb.1.if.else:
+    DBG_VALUE %2, $noreg, !14, !DIExpression(), debug-location !12
+  
+
+    ; CHECK-LABEL: bb.2.if.end:
+  bb.2.if.end:
+    %0:gr32 = PHI %1, %bb.0, %2, %bb.1, debug-instr-number 1, debug-location !18
+    DBG_INSTR_REF 1, 0, !14, !DIExpression(), debug-location !12
+    ; CHECK:      DBG_PHI $ebp, 1
+    ; CHECK:      DBG_INSTR_REF 1, 0
+    $eax = COPY killed %0, debug-location !19
+    ; Confirm that %0 is allocated in $ebp,
+    ; CHECK:      $eax = COPY killed renamable $ebp
+    RET 0, killed $eax, debug-location !19
+
+...