[DebugInstrRef][8/9] Convert DBG_INSTR_REFs into variable locations

[jmorse]

Summary

Handle DBG_INSTR_REF instructions in LiveDebugValues, to determine and propagate variable locations. The logic is fairly straight forwards:

• Collect a map of debug-instruction-number to the machine value numbers generated in the first walk through the function,
• When building the variable value transfer function and we see a DBG_INSTR_REF, look up the instruction it refers to, and pick the machine value number it generates,
• That's it; the rest of LiveDebugValues continues as normal.

Reviewing this change may be sticky, as it depends on what route we take with reviewing D83047.

Awkwardly, there are two kinds of instruction numbering happening here: the offset into the block (which is how machine value numbers are determined), and the numbers that we label instructions with when generating DBG_INSTR_REFs. Suggestions on naming them most welcome, I haven't come up with anything good yet.

Practically, the map above isn't to a set of value numbers, it's to a MachineInstr and its offset into its block. One can determine the machine value number it generates at a particular operand using that information.

I've also restructured the TransferTracker redefVar code a little, to separate some DBG_VALUE specific operations into its own method. The changes around redefVar should be largely NFC, while allowing DBG_INSTR_REFs to specify a value number rather than just a location.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

919

???

1092–1097

We don't use curly braces for single statements.

[jmorse]

Remove some needless comments and some needless curly braces.

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

919

The overlapping fragments comment was a reminder to myself that I hadn't implemented support for it yet; I guess it isn't helpful being left in the code.

(It won't be forgotten in the future as there's a test for overlapping fragments in-tree already).

[aprantl]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1632

if (!Tracker)

return true;

[jmorse]

Early-exit to avoid un-necessary indentation.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
   /// 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, Optional<ValueIDNum> ID) {
-    // XXX skipping overlapping fragments for now.
-    assert(MI.isDebugValue());
+  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());
-    DbgValueProperties Properties(MI);
     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) {
-    // XXX skipping overlapping fragments for now.
+    // 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));
public:
   /// Helper to move created DBG_VALUEs into Transfers collection.
   void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {
     if (PendingDbgValues.size() > 0) {
       Transfers.push_back({Pos, MBB, PendingDbgValues});
       PendingDbgValues.clear();
     }
   }
 
-  /// Handle a DBG_VALUE within a block. Terminate the variables current
-  /// location, and record the value its DBG_VALUE refers to, so that we can
-  /// detect location transfers later on.
+  /// Change a variable value after encountering a DBG_VALUE inside a block.
   void redefVar(const MachineInstr &MI) {
     DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
                       MI.getDebugLoc()->getInlinedAt());
+    DbgValueProperties Properties(MI);
+
     const MachineOperand &MO = MI.getOperand(0);
 
-    // Erase any previous location,
+    // Ignore non-register locations, we don't transfer those.
+    if (!MO.isReg() || MO.getReg() == 0) {
       auto It = ActiveVLocs.find(Var);
       if (It != ActiveVLocs.end()) {
         ActiveMLocs[It->second.Loc].erase(Var);
-    }
-
-    // Insert a new variable location. Ignore non-register locations, we don't
-    // transfer those, and can't currently describe spill locs independently of
-    // regs.
-    // (This is because a spill location is a DBG_VALUE of the stack pointer).
-    if (!MO.isReg() || MO.getReg() == 0) {
-      if (It != ActiveVLocs.end())
         ActiveVLocs.erase(It);
+     }
       return;
     }
 
     Register Reg = MO.getReg();
-    LocIdx MLoc = MTracker->getRegMLoc(Reg);
-    DbgValueProperties Properties(MI);
+    LocIdx NewLoc = MTracker->getRegMLoc(Reg);
+    redefVar(MI, Properties, NewLoc);
+  }
+
+  /// Handle a change in variable location within a block. Terminate the
+  /// variables current location, and record the value it now refers to, so
+  /// that we can detect location transfers later on.
+  void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,
+                Optional<LocIdx> OptNewLoc) {
+    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
+                      MI.getDebugLoc()->getInlinedAt());
+
+    // Erase any previous location,
+    auto It = ActiveVLocs.find(Var);
+    if (It != ActiveVLocs.end())
+      ActiveMLocs[It->second.Loc].erase(Var);
+
+    // If there _is_ no new location, all we had to do was erase.
+    if (!OptNewLoc)
+      return;
+    LocIdx NewLoc = *OptNewLoc;
 
     // Check whether our local copy of values-by-location in #VarLocs is out of
     // date. Wipe old tracking data for the location if it's been clobbered in
     // the meantime.
-    if (MTracker->getNumAtPos(MLoc) != VarLocs[MLoc.asU64()]) {
-      for (auto &P : ActiveMLocs[MLoc.asU64()]) {
+    if (MTracker->getNumAtPos(NewLoc) != VarLocs[NewLoc.asU64()]) {
+      for (auto &P : ActiveMLocs[NewLoc]) {
         ActiveVLocs.erase(P);
       }
-      ActiveMLocs[MLoc].clear();
-      VarLocs[MLoc.asU64()] = MTracker->getNumAtPos(MLoc);
+      ActiveMLocs[NewLoc.asU64()].clear();
+      VarLocs[NewLoc.asU64()] = MTracker->getNumAtPos(NewLoc);
     }
 
-    ActiveMLocs[MLoc].insert(Var);
+    ActiveMLocs[NewLoc].insert(Var);
     if (It == ActiveVLocs.end()) {
-      ActiveVLocs.insert(std::make_pair(Var, LocAndProperties{MLoc, Properties}));
+      ActiveVLocs.insert(
+          std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
     } else {
-      It->second.Loc = MLoc;
+      It->second.Loc = NewLoc;
       It->second.Properties = Properties;
     }
   }
 
   /// Explicitly terminate variable locations based on \p mloc. Creates undef
   /// DBG_VALUEs for any variables that were located there, and clears
   /// #ActiveMLoc / #ActiveVLoc tracking information for that location.
   void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos) {
private:
   /// 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<unsigned, unsigned> BBNumToRPO;
 
+  /// Pair of MachineInstr, and its 1-based offset into the containing block.
+  typedef std::pair<const MachineInstr *, unsigned> InstAndNum;
+  /// 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;
+
   // Map of overlapping variable fragments.
   OverlapMap OverlapFragments;
   VarToFragments SeenFragments;
 
   /// Tests whether this instruction is a spill to a stack slot.
   bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF);
 
   /// Decide if @MI is a spill instruction and return true if it is. We use 2
private:
 
   /// Observe a single instruction while stepping through a block.
   void process(MachineInstr &MI);
 
   /// Examines whether \p MI is a DBG_VALUE and notifies trackers.
   /// \returns true if MI was recognized and processed.
   bool transferDebugValue(const MachineInstr &MI);
 
+  /// Examines whether \p MI is a DBG_INSTR_REF and notifies trackers.
+  /// \returns true if MI was recognized and processed.
+  bool transferDebugInstrRef(MachineInstr &MI);
+
   /// Examines whether \p MI is copy instruction, and notifies trackers.
   /// \returns true if MI was recognized and processed.
   bool transferRegisterCopy(MachineInstr &MI);
 
   /// Examines whether \p MI is stack spill or restore  instruction, and
   /// notifies trackers. \returns true if MI was recognized and processed.
   bool transferSpillOrRestoreInst(MachineInstr &MI);
 
bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {
   const DILocalVariable *Var = MI.getDebugVariable();
   const DIExpression *Expr = MI.getDebugExpression();
   const DILocation *DebugLoc = MI.getDebugLoc();
   const DILocation *InlinedAt = DebugLoc->getInlinedAt();
   assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
          "Expected inlined-at fields to agree");
 
   DebugVariable V(Var, Expr, InlinedAt);
+  DbgValueProperties Properties(MI);
 
   // If there are no instructions in this lexical scope, do no location tracking
   // at all, this variable shouldn't get a legitimate location range.
   auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
   if (Scope == nullptr)
     return true; // handled it; by doing nothing
 
   const MachineOperand &MO = MI.getOperand(0);
 
   // MLocTracker needs to know that this register is read, even if it's only
   // read by a debug inst.
   if (MO.isReg() && MO.getReg() != 0)
     (void)MTracker->readReg(MO.getReg());
 
   // If we're preparing for the second analysis (variables), the machine value
   // locations are already solved, and we report this DBG_VALUE and the value
   // it refers to to VLocTracker.
   if (VTracker) {
     if (MO.isReg()) {
       // Feed defVar the new variable location, or if this is a
       // DBG_VALUE $noreg, feed defVar None.
       if (MO.getReg())
-        VTracker->defVar(MI, MTracker->readReg(MO.getReg()));
+        VTracker->defVar(MI, Properties, MTracker->readReg(MO.getReg()));
       else
-        VTracker->defVar(MI, None);
+        VTracker->defVar(MI, Properties, None);
     } else if (MI.getOperand(0).isImm() || MI.getOperand(0).isFPImm() ||
                MI.getOperand(0).isCImm()) {
       VTracker->defVar(MI, MI.getOperand(0));
     }
   }
 
   // If performing final tracking of transfers, report this variable definition
   // to the TransferTracker too.
   if (TTracker)
     TTracker->redefVar(MI);
   return true;
 }
 
+bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI) {
+  if (!MI.isDebugRef())
+    return false;
+
+  // Only handle this instruction when we are building the variable value
+  // transfer function.
+  if (!VTracker)
+    return false;
+
+  unsigned InstNo = MI.getOperand(0).getImm();
+  unsigned OpNo = MI.getOperand(1).getImm();
+
+  const DILocalVariable *Var = MI.getDebugVariable();
+  const DIExpression *Expr = MI.getDebugExpression();
+  const DILocation *DebugLoc = MI.getDebugLoc();
+  const DILocation *InlinedAt = DebugLoc->getInlinedAt();
+  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
+         "Expected inlined-at fields to agree");
+
+  DebugVariable V(Var, Expr, InlinedAt);
+
+  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());
+  if (Scope == nullptr)
+    return true; // Handled by doing nothing. This variable is never in scope.
+
+  const MachineFunction &MF = *MI.getParent()->getParent();
+
+  // Various optimizations may have happened to the value during codegen,
+  // recorded in the value substitution table. Apply any substitutions to
+  // the instruction / operand number in this DBG_INSTR_REF.
+  auto Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
+  while (Sub != MF.DebugValueSubstitutions.end()) {
+    InstNo = Sub->second.first;
+    OpNo = Sub->second.second;
+    Sub = MF.DebugValueSubstitutions.find(std::make_pair(InstNo, OpNo));
+  }
+
+  // Default machine value number is <None> -- if no instruction defines
+  // the corresponding value, it must have been optimized out.
+  Optional<ValueIDNum> NewID = None;
+
+  // Try to lookup the instruction number, and find the machine value number
+  // that it defines.
+  auto InstrIt = DebugInstrNumToInstr.find(InstNo);
+  if (InstrIt != DebugInstrNumToInstr.end()) {
+    const MachineInstr &TargetInstr = *InstrIt->second.first;
+    uint64_t BlockNo = TargetInstr.getParent()->getNumber();
+
+    // Pick out the designated operand.
+    assert(OpNo < TargetInstr.getNumOperands());
+    const MachineOperand &MO = TargetInstr.getOperand(OpNo);
+
+    // Today, this can only be a register.
+    assert(MO.isReg() && MO.isDef());
+
+    unsigned LocID = MTracker->getLocID(MO.getReg(), false);
+    LocIdx L = MTracker->LocIDToLocIdx[LocID];
+    NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
+  }
+
+  // We, we have a value number or None. Tell the variable value tracker about
+  // it. The rest of this LiveDebugValues implementation acts exactly the same
+  // for DBG_INSTR_REFs as DBG_VALUEs (just, the former can refer to values that
+  // aren't immediately available).
+  DbgValueProperties Properties(Expr, false);
+  VTracker->defVar(MI, Properties, NewID);
+
+  // If we're on the final pass through the function, decompose this INSTR_REF
+  // into a plain DBG_VALUE.
+  if (!TTracker)
+    return true;
+
+  // Pick a location for the machine value number, if such a location exists.
+  // (This information could be stored in TransferTracker to make it faster).
+  Optional<LocIdx> FoundLoc = None;
+  for (auto Location : MTracker->locations()) {
+    LocIdx CurL = Location.Idx;
+    ValueIDNum ID = MTracker->LocIdxToIDNum[CurL];
+    if (NewID && ID == NewID) {
+      // If this is the first location with that value, pick it. Otherwise,
+      // consider whether it's a "longer term" location.
+      if (!FoundLoc) {
+        FoundLoc = CurL;
+        continue;
+      }
+
+      if (MTracker->isSpill(CurL))
+        FoundLoc = CurL; // Spills are a longer term location.
+      else if (!MTracker->isSpill(*FoundLoc) &&
+               !MTracker->isSpill(CurL) &&
+               !isCalleeSaved(*FoundLoc) &&
+               isCalleeSaved(CurL))
+        FoundLoc = CurL; // Callee saved regs are longer term than normal.
+    }
+  }
+
+  // Tell transfer tracker that the variable value has changed.
+  TTracker->redefVar(MI, Properties, FoundLoc);
+
+  // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.
+  // This DBG_VALUE is potentially a $noreg / undefined location, if
+  // FoundLoc is None.
+  // (XXX -- could morph the DBG_INSTR_REF in the future).
+  MachineInstr *DbgMI = MTracker->emitLoc(FoundLoc, V, Properties);
+  TTracker->PendingDbgValues.push_back(DbgMI);
+  TTracker->flushDbgValues(MI.getIterator(), nullptr);
+
+  return true;
+}
+
 void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
   // Meta Instructions do not affect the debug liveness of any register they
   // define.
   if (MI.isImplicitDef()) {
     // Except when there's an implicit def, and the location it's defining has
     // no value number. The whole point of an implicit def is to announce that
     // the register is live, without be specific about it's value. So define
     // a value if there isn't one already.

 }
 
 void InstrRefBasedLDV::process(MachineInstr &MI) {
   // Try to interpret an MI as a debug or transfer instruction. Only if it's
   // none of these should we interpret it's register defs as new value
   // definitions.
   if (transferDebugValue(MI))
     return;
+  if (transferDebugInstrRef(MI))
+    return;
   if (transferRegisterCopy(MI))
     return;
   if (transferSpillOrRestoreInst(MI))
     return;
   transferRegisterDef(MI);
 }
 
 void InstrRefBasedLDV::produceMLocTransferFunction(
for (auto &MBB : MF) {
     MTracker->setMPhis(CurBB);
 
     // Step through each instruction in this block.
     for (auto &MI : MBB) {
       process(MI);
       // Also accumulate fragment map.
       if (MI.isDebugValue())
         accumulateFragmentMap(MI);
+
+      // Create a map from the instruction number (if present) to the
+      // MachineInstr and its position.
+      if (MI.peekDebugInstrNum()) {
+        uint64_t InstrNo = MI.peekDebugInstrNum();
+        auto InstrAndPos = std::make_pair(&MI, CurInst);
+        auto InsertResult =
+            DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
+
+        // There should never be duplicate instruction numbers.
+        assert(InsertResult.second);
+        (void)InsertResult;
+      }
+
       ++CurInst;
     }
 
     // Produce the transfer function, a map of machine location to new value. If
     // any machine location has the live-in phi value from the start of the
     // block, it's live-through and doesn't need recording in the transfer
     // function.
     for (auto Location : MTracker->locations()) {
bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,
   MTracker = nullptr;
   VTracker = nullptr;
   TTracker = nullptr;
 
   ArtificialBlocks.clear();
   OrderToBB.clear();
   BBToOrder.clear();
   BBNumToRPO.clear();
+  DebugInstrNumToInstr.clear();
 
   return Changed;
 }
 
 LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {
   return new InstrRefBasedLDV();
 }

llvm/test/DebugInfo/MIR/InstrRef/livedebugvalues_instrref_tolocs.mir

+--- |
+  ; RUN: llc %s -march=x86-64 -run-pass=livedebugvalues -o - -experimental-debug-variable-locations | FileCheck %s -implicit-check-not=DBG_VALUE
+
+  define i32 @_Z8bb_to_bb() local_unnamed_addr !dbg !12 {
+  entry:
+    ret i32 0, !dbg !17
+  }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!7, !8, !9, !10}
+  !llvm.ident = !{!11}
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 10.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !3, debugInfoForProfiling: true, nameTableKind: None)
+  !1 = !DIFile(filename: "main.cpp", directory: "F:\")
+  !2 = !{}
+  !3 = !{!4}
+  !4 = !DIGlobalVariableExpression(var: !5, expr: !DIExpression())
+  !5 = distinct !DIGlobalVariable(name: "start", scope: !0, file: !1, line: 4, type: !6, isLocal: false, isDefinition: true)
+  !6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !7 = !{i32 2, !"Dwarf Version", i32 4}
+  !8 = !{i32 2, !"Debug Info Version", i32 3}
+  !9 = !{i32 1, !"wchar_size", i32 2}
+  !10 = !{i32 7, !"PIC Level", i32 2}
+  !11 = !{!"clang version 10.0.0"}
+  !12 = distinct !DISubprogram(name: "bb_to_bb", linkageName: "bb_to_bb", scope: !1, file: !1, line: 6, type: !13, scopeLine: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !15)
+  !13 = !DISubroutineType(types: !14)
+  !14 = !{!6, !6}
+  !15 = !{!16}
+  !16 = !DILocalVariable(name: "myVar", scope: !12, file: !1, line: 7, type: !6)
+  !17 = !DILocation(line: 10, scope: !12)
+
+...
+---
+name: _Z8bb_to_bb
+debugValueSubstitutions:
+  - { srcinst: 4, srcop: 0, dstinst: 3, dstop: 0 }
+body:  |
+  bb.0.entry:
+    $rax = MOV64ri 1, debug-instr-number 1, debug-location !17
+    ; This debug instruction should identify the value as being in $rax.
+    DBG_INSTR_REF 1, 0, !16, !DIExpression(), debug-location !17
+    ; CHECK: DBG_VALUE $rax, $noreg
+
+    $rbx = COPY killed $rax, debug-location !17
+    $rax = MOV64ri 1, debug-location !17
+    ; Presently, this COPY isn't followed. Dealing with that is future work.
+
+    DBG_INSTR_REF 2, 0, !16, !DIExpression(), debug-location !17
+    ; No instruction is labelled with the number "2". This should produce an
+    ; empty variable location.
+    ; CHECK: DBG_VALUE $noreg, $noreg
+
+    $rbx = MOV64ri 1, debug-instr-number 3, debug-location !17
+    JMP_1 %bb.1
+
+
+    ; CHECK-LABEL: bb.1:
+  bb.1:
+
+    DBG_INSTR_REF 3, 0, !16, !DIExpression(), debug-location !17
+    ; This refers to a value def'd in a parent block -- but it should be
+    ; tracked into this block.
+    ; CHECK: DBG_VALUE $rbx, $noreg
+    JMP_1 %bb.2
+
+    ; CHECK-LABEL: bb.2:
+  bb.2:
+    ; Just like any other variable location, live-ins should be created for
+    ; any successor blocks.
+    ; CHECK: DBG_VALUE $rbx, $noreg
+
+    RETQ $eax, debug-location !17
+...