[DebugInstrRef][6/9] Pass DBG_INSTR_REFs safely through register allocation

[jmorse]

Summary

Both FastRegAlloc and LiveDebugVariables/greedy need to cope with DBG_INSTR_REFs. None of them actually need to take any action, other than passing DBG_INSTR_REFs through: variable location information doesn't refer to any registers at this stage.

LiveDebugVariables stashes the instruction information in a tuple, then re-creates it later. This is only necessary as the register allocator doesn't expect to see any debug instructions while it's working. No equivalence classes or interval splitting is required at all!

No changes are needed for the fast register allocator, as it just ignores debug instructions. The test added checks that both of them preserve DBG_INSTR_REFs.

I also expand ScheduleDAGInstrs.cpp to treat DBG_INSTR_REFs as DBG_VALUEs when rescheduling instructions around -- done in this patch as machine-scheduler is part of the register allocation phase, as I understand it. The current movement of DBG_VALUEs around is less than ideal, but it's not a regression to make DBG_INSTR_REFs subject to the same movement.

[jmorse]

NB: I said in the test:

The fast register allocator puts some spills in -- these are no-ops as far
as the slot indexes are concerned. It doesn't matter which side of spills
the DBG_INSTR_REF lands on.

And in the mean time, fast-isel has changed where it puts those spills. I updated the relevant CHECK lines to be CHECK-DAGs.

llvm/lib/CodeGen/LiveDebugVariables.cpp

 /// Implementation of the LiveDebugVariables pass.
 class LDVImpl {
   LiveDebugVariables &pass;
   LocMap::Allocator allocator;
   MachineFunction *MF = nullptr;
   LiveIntervals *LIS;
   const TargetRegisterInfo *TRI;
 
+  using StashedInstrRef =
+      std::tuple<unsigned, unsigned, const DILocalVariable *,
+                 const DIExpression *, DebugLoc>;
+  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;
 
   /// All allocated UserValue instances.
   SmallVector<std::unique_ptr<UserValue>, 8> userValues;
class LDVImpl {
   /// Add DBG_VALUE instruction to our maps.
   ///
   /// \param MI DBG_VALUE instruction
   /// \param Idx Last valid SLotIndex before instruction.
   ///
   /// \returns True if the DBG_VALUE instruction should be deleted.
   bool handleDebugValue(MachineInstr &MI, SlotIndex Idx);
 
+  /// Track a DBG_INSTR_REF. This needs to be removed from the MachineFunction
+  /// during regalloc -- but there's no need to maintain live ranges, as we
+  /// refer to a value rather than a location.
+  ///
+  /// \param MI DBG_INSTR_REF instruction
+  /// \param Idx Last valid SlotIndex before instruction
+  ///
+  /// \returns True if the DBG_VALUE instruction should be deleted.
+  bool handleDebugInstrRef(MachineInstr &MI, SlotIndex Idx);
+
   /// Add DBG_LABEL instruction to UserLabel.
   ///
   /// \param MI DBG_LABEL instruction
   /// \param Idx Last valid SlotIndex before instruction.
   ///
   /// \returns True if the DBG_LABEL instruction should be deleted.
   bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx);
 

 public:
   LDVImpl(LiveDebugVariables *ps) : pass(*ps) {}
 
   bool runOnMachineFunction(MachineFunction &mf);
 
   /// Release all memory.
   void clear() {
     MF = nullptr;
+    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;
bool LDVImpl::handleDebugValue(MachineInstr &MI, SlotIndex Idx) {
   else {
     MachineOperand MO = MachineOperand::CreateReg(0U, false);
     MO.setIsDebug();
     UV->addDef(Idx, MO, false, *Expr);
   }
   return true;
 }
 
+bool LDVImpl::handleDebugInstrRef(MachineInstr &MI, SlotIndex Idx) {
+  assert(MI.isDebugRef());
+  unsigned InstrNum = MI.getOperand(0).getImm();
+  unsigned OperandNum = MI.getOperand(1).getImm();
+  auto *Var = MI.getDebugVariable();
+  auto *Expr = MI.getDebugExpression();
+  auto &DL = MI.getDebugLoc();
+  StashedInstrRef Stashed =
+      std::make_tuple(InstrNum, OperandNum, Var, Expr, DL);
+  StashedInstrReferences[Idx].push_back(Stashed);
+  return true;
+}
+
 bool LDVImpl::handleDebugLabel(MachineInstr &MI, SlotIndex Idx) {
   // DBG_LABEL label
   if (MI.getNumOperands() != 1 || !MI.getOperand(0).isMetadata()) {
     LLVM_DEBUG(dbgs() << "Can't handle " << MI);
     return false;
   }
 
   // Get or create the UserLabel for label here.
for (MachineBasicBlock::iterator MBBI = MBB->begin(), MBBE = MBB->end();
           MBBI == MBB->begin()
               ? LIS->getMBBStartIdx(MBB)
               : LIS->getInstructionIndex(*std::prev(MBBI)).getRegSlot();
       // Handle consecutive debug instructions with the same slot index.
       do {
         // Only handle DBG_VALUE in handleDebugValue(). Skip all other
         // kinds of debug instructions.
         if ((MBBI->isDebugValue() && handleDebugValue(*MBBI, Idx)) ||
+            (MBBI->isDebugRef() && handleDebugInstrRef(*MBBI, Idx)) ||
             (MBBI->isDebugLabel() && handleDebugLabel(*MBBI, Idx))) {
           MBBI = MBB->erase(MBBI);
           Changed = true;
         } else
           ++MBBI;
       } while (MBBI != MBBE && MBBI->isDebugInstr());
     }
   }
for (auto &userValue : userValues) {
     userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets);
     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 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));
+      MIB.addImm(std::get<1>(Stashed));
+      MIB.addMetadata(std::get<2>(Stashed));
+      MIB.addMetadata(std::get<3>(Stashed));
+      MachineInstr *New = MIB;
+      MBB->insert(insertPos, New);
+    }
+  }
+
   EmitDone = true;
 }
 
 void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->emitDebugValues(VRM);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void LiveDebugVariables::dump() const {
   if (pImpl)
     static_cast<LDVImpl*>(pImpl)->print(dbgs());
 }
 #endif

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

void ScheduleDAGInstrs::buildSchedGraph(AAResults *AA,
   for (MachineBasicBlock::iterator MII = RegionEnd, MIE = RegionBegin;
        MII != MIE; --MII) {
     MachineInstr &MI = *std::prev(MII);
     if (DbgMI) {
       DbgValues.push_back(std::make_pair(DbgMI, &MI));
       DbgMI = nullptr;
     }
 
-    if (MI.isDebugValue()) {
+    if (MI.isDebugValue() || MI.isDebugRef()) {
       DbgMI = &MI;
       continue;
     }
     if (MI.isDebugLabel())
       continue;
 
     SUnit *SU = MISUnitMap[&MI];
     assert(SU && "No SUnit mapped to this MI");

llvm/test/DebugInfo/MIR/InstrRef/survives-livedebugvars.mir

+# RUN: llc -start-after=phi-node-elimination -stop-after=virtregrewriter %s -mtriple=x86_64-unknown-unknown -o - -experimental-debug-variable-locations | FileCheck %s
+# RUN: llc -O0 -start-after=phi-node-elimination -stop-after=regallocfast %s -mtriple=x86_64-unknown-unknown -o - -experimental-debug-variable-locations | FileCheck %s --check-prefix=FASTREG
+#
+# Test that DBG_INSTR_REFs can pass through livedebugvariables to the end of
+# regalloc without problem. Program body copied from
+# livedebugvars-crossbb-interval.mir.
+#
+# CHECK-LABEL: bb.0:
+# CHECK:       DBG_INSTR_REF 1, 0
+# CHECK-NEXT:  JMP_1
+# CHECK-LABEL: bb.1:
+# CHECK:       DBG_INSTR_REF 2, 0
+# CHECK-NEXT:  JMP_1
+# CHECK-LABEL: bb.2:
+# CHECK:       DBG_INSTR_REF 3, 0
+# CHECK-NEXT:  CALL64pcrel32
+# CHECK-LABEL: bb.3:
+# CHECK:       DBG_INSTR_REF 4, 0
+# CHECK-NEXT:  JMP_1
+#
+#
+# The fast register allocator puts some spills in -- these are no-ops as far
+# as the slot indexes are concerned. It doesn't matter which side of spills
+# the DBG_INSTR_REF lands on.
+#
+# FASTREG-LABEL: bb.0:
+# FASTREG-DAG:   DBG_INSTR_REF 1, 0
+# FASTREG-DAG:   MOV64mr
+# FASTREG-DAG:   MOV32mr
+# FASTREG-NEXT:  JMP_1
+# FASTREG-LABEL: bb.1:
+# FASTREG:       DBG_INSTR_REF 2, 0
+# FASTREG-NEXT:  JMP_1
+# FASTREG-LABEL: bb.2:
+# FASTREG:       DBG_INSTR_REF 3, 0
+# FASTREG-NEXT:  CALL64pcrel32
+# FASTREG-LABEL: bb.3:
+# FASTREG-DAG:   MOV32rm
+# FASTREG-DAG:   DBG_INSTR_REF 4, 0
+# FASTREG-DAG:   MOV32mr
+# FASTREG-NEXT:  JMP_1
+# FASTREG-LABEL: bb.4:
+# FASTREG:       DBG_INSTR_REF 5, 0
+# FASTREG-NEXT:  RETQ
+
+--- |
+  ; ModuleID = 'tmp.ll'
+  source_filename = "tmp.ll"
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+  %struct.a = type { i32 }
+
+  ; Function Attrs: nounwind ssp
+  define i32 @bar() !dbg !4 {
+    ret i32 0, !dbg !18
+  }
+
+  declare i32 @foo();
+
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!3}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "asdf", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !2)
+  !1 = !DIFile(filename: "bar.c", directory: "asdf")
+  !2 = !{}
+  !3 = !{i32 1, !"Debug Info Version", i32 3}
+  !4 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 5, type: !5, virtualIndex: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !8)
+  !5 = !DISubroutineType(types: !6)
+  !6 = !{!7}
+  !7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+  !8 = !{!9, !14}
+  !9 = !DILocalVariable(name: "b", arg: 1, scope: !4, file: !1, line: 5, type: !10)
+  !10 = !DIDerivedType(tag: DW_TAG_pointer_type, scope: !0, baseType: !11, size: 64, align: 64)
+  !11 = !DICompositeType(tag: DW_TAG_structure_type, name: "a", scope: !0, file: !1, line: 1, size: 32, align: 32, elements: !12)
+  !12 = !{!13}
+  !13 = !DIDerivedType(tag: DW_TAG_member, name: "c", scope: !1, file: !1, line: 2, baseType: !7, size: 32, align: 32)
+  !14 = !DILocalVariable(name: "x", scope: !15, file: !1, line: 6, type: !7)
+  !15 = distinct !DILexicalBlock(scope: !4, file: !1, line: 5, column: 22)
+  !16 = !DILocation(line: 5, column: 19, scope: !4)
+  !17 = !DILocation(line: 6, column: 14, scope: !15)
+  !18 = !DILocation(line: 8, column: 2, scope: !15)
+  !19 = !DILocation(line: 7, column: 2, scope: !15)
+
+...
+---
+name:            bar
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr64 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr64 }
+  - { id: 3, class: gr64 }
+  - { id: 4, class: gr32 }
+  - { id: 5, class: gr32 }
+  - { id: 6, class: gr32 }
+  - { id: 7, class: gr32 }
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$esi', virtual-reg: '%4' }
+frameInfo:
+  hasCalls:        true
+machineFunctionInfo: {}
+body:             |
+  bb.0:
+    liveins: $rdi, $esi
+
+    %4:gr32 = COPY $esi
+    %2:gr64 = COPY $rdi
+    %3:gr64 = COPY killed %2
+    %5:gr32 = COPY killed %4
+    DBG_INSTR_REF 1, 0, !9, !DIExpression(), debug-location !16
+    JMP_1 %bb.3
+
+  bb.1:
+    DBG_INSTR_REF 2, 0, !9, !DIExpression(), debug-location !16
+    JMP_1 %bb.4
+
+  bb.2:
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def $rsp, implicit-def $eflags, implicit-def $ssp, implicit $rsp, implicit $ssp, debug-location !19
+    $edi = COPY %6, debug-location !19
+    $al = MOV8ri 0, debug-location !19
+    DBG_INSTR_REF 3, 0, !9, !DIExpression(), debug-location !16
+    CALL64pcrel32 @foo, csr_64, implicit $rsp, implicit $ssp, implicit $al, implicit $edi, implicit-def $eax, debug-location !19
+    ADJCALLSTACKUP64 0, 0, implicit-def $rsp, implicit-def $eflags, implicit-def $ssp, implicit $rsp, implicit $ssp, debug-location !19
+    %7:gr32 = COPY $eax, debug-location !19
+    JMP_1 %bb.1
+
+  bb.3:
+    %6:gr32 = MOV32rm %3, 1, $noreg, 0, $noreg, debug-location !17
+    DBG_INSTR_REF 4, 0, !9, !DIExpression(), debug-location !16
+    JMP_1 %bb.2
+
+  bb.4:
+    $eax = COPY %5, debug-location !18
+    DBG_INSTR_REF 5, 0, !9, !DIExpression(), debug-location !16
+    RETQ implicit $eax, debug-location !18
+
+...