[RegAllocFast] Salvage debug values when killing operands

[vsk]

Summary

Teach the fast register allocator to update DBG_VALUE instructions when
it reloads a vreg.

Specifically, when a machine operand can be killed, point the DBG_VALUE
uses of that operand to a replacement vreg and update LiveDbgValuesMap.

[vsk]

Here's what the end-to-end test looks like before and after this patch (along with https://reviews.llvm.org/D43386 applied).

Target 0: (e2e.Os.before) stopped.
(lldb) fr v
(S) s = (x = -16843010, y = "ab", z = 3.1415926540000001)
(int) x = <no location, value may have been optimized out>
(char) y1 = <no location, value may have been optimized out>
(double) z = <no location, value may have been optimized out>

Target 0: (e2e.Os.after) stopped.
(lldb) fr v
(double) z = 3.1415926540000001
(char) y1 = 'b'
(int) x = -16843010
(S) s = (x = -16843010, y = "ab", z = 3.1415926540000001)

[aprantl]

The debug info part of this looks fine to me, it would be great if the same function could also be applied to the other register allocators.

[vsk]

@aprantl thanks for the feedback, I'll take a look at whether MachineRegisterInfo is the right place for generic register allocator helpers to live.

A side note: I won't get back to this patch for a few days, as I need to take a look at Swift bugs.

lib/CodeGen/MachineRegisterInfo.cpp

582

Note: This probably shouldn't be called unless we've actually updated any uses.

lib/CodeGen/RegAllocFast.cpp

705

I think this should be:

auto &DbgUses = ...;
LiveDbgValueMap[DstVReg].append(DbgUses.begin(), DbgUses.end());
DbgUses.clear();

I still need to figure out how to get test coverage for this.

[aprantl]

I still need to figure out how to get test coverage for this.

A debugify MIR pass :-)

Joke aside, that would probably by overkill. In practice -stop-before=regalloc and manually inserting DBG_VALUEs should be fine.

[vsk]

• Only update LiveDbgValsMap when a dbg_value has been salvaged. Test coverage for this is provided by the fission-ranges.ll test added in r325438. Prior to this update, the test would fail because extra locations were generated for the wrong spills.

[MatzeB]

• I'd rather keep MachineRegisterInfo to things directly related to information about virtual registers (register class etc.); I don't think it's role should be to provide transformations for involving virtual registers. So I'd rather move the functionality somewhere else.
• I'm skeptical this works as intended in the presence of control flow (= multiple uses and defs of a vreg anywhere in the control flow graph).
• I'm not sure I completely understand what is going on here, is it looking for COPYs killing a value so it can replace the debug values with the copied value? The commit message should mention that then.

[vsk]

Now that we've reverted r325438, we'll need some replacement before this patch is relevant.

• I'd rather keep MachineRegisterInfo to things directly related to information about virtual registers (register class etc.); I don't think it's role should be to provide transformations for involving virtual registers. So I'd rather move the functionality somewhere else.

I'll look into this.

• I'm skeptical this works as intended in the presence of control flow (= multiple uses and defs of a vreg anywhere in the control flow graph).

It sounds like this at least needs better testing. I'm not sure whether we do the right thing if there are dbg_value uses of the dying vreg before the copy.

• I'm not sure I completely understand what is going on here, is it looking for COPYs killing a value so it can replace the debug values with the copied value? The commit message should mention that then.

Yes, I'll fix the commit message.

include/llvm/CodeGen/MachineRegisterInfo.h

private:
   }
 
   /// Get the next element in the use-def chain.
   static MachineOperand *getNextOperandForReg(const MachineOperand *MO) {
     assert(MO && MO->isReg() && "This is not a register operand!");
     return MO->Contents.Reg.Next;
   }
 
+  /// Apply \p Updater on every DBG_VALUE instruction which uses \p Reg.
+  /// Returns true if any such instructions were found.
+  bool
+  updateDebugValueUses(unsigned Reg,
+                       function_ref<void(MachineInstr *DbgMI)> Updater) const;
+
   /// UsedPhysRegMask - Additional used physregs including aliases.
   /// This bit vector represents all the registers clobbered by function calls.
   BitVector UsedPhysRegMask;
 
   /// ReservedRegs - This is a bit vector of reserved registers.  The target
   /// may change its mind about which registers should be reserved.  This
   /// vector is the frozen set of reserved registers when register allocation
   /// started.
&getRegAllocationHints(unsigned VReg) const {
     return RegAllocHints[VReg];
   }
 
   /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
   /// specified register as undefined which causes the DBG_VALUE to be
   /// deleted during LiveDebugVariables analysis.
   void markUsesInDebugValueAsUndef(unsigned Reg) const;
 
+  /// Assuming the operand \p DyingOp will be killed once \p ReplacementMI is
+  /// assigned physical registers, attempt to salvage DBG_VALUE uses of the
+  /// dying operand by pointing them to a new virtual register. \p VRegCallback
+  /// is called if the salvage operation succeeds.
+  void
+  salvageDebugInfo(MachineOperand &DyingOp, MachineInstr &ReplacementMI,
+                   function_ref<void(unsigned Src, unsigned Dst)> VRegCallback);
+
   /// Return true if the specified register is modified in this function.
   /// This checks that no defining machine operands exist for the register or
   /// any of its aliases. Definitions found on functions marked noreturn are
   /// ignored, to consider them pass 'true' for optional parameter
   /// SkipNoReturnDef. The register is also considered modified when it is set
   /// in the UsedPhysRegMask.
   bool isPhysRegModified(unsigned PhysReg, bool SkipNoReturnDef = false) const;
 

lib/CodeGen/MachineRegisterInfo.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
 
 using namespace llvm;
 
+#define DEBUG_TYPE "regalloc"
+
 static cl::opt<bool> EnableSubRegLiveness("enable-subreg-liveness", cl::Hidden,
   cl::init(true), cl::desc("Enable subregister liveness tracking."));
 
 // Pin the vtable to this file.
 void MachineRegisterInfo::Delegate::anchor() {}
 
 MachineRegisterInfo::MachineRegisterInfo(MachineFunction *MF)
     : MF(MF), TracksSubRegLiveness(MF->getSubtarget().enableSubRegLiveness() &&

 
 bool
 MachineRegisterInfo::isCallerPreservedOrConstPhysReg(unsigned PhysReg) const {
   const TargetRegisterInfo *TRI = getTargetRegisterInfo();
   return isConstantPhysReg(PhysReg) ||
       TRI->isCallerPreservedPhysReg(PhysReg, *MF);
 }
 
+bool MachineRegisterInfo::updateDebugValueUses(
+    unsigned Reg, function_ref<void(MachineInstr *DbgMI)> Updater) const {
+  bool FoundDebugUse = false;
+  MachineRegisterInfo::use_instr_iterator nextI;
+  for (use_instr_iterator I = use_instr_begin(Reg), E = use_instr_end(); I != E;
+       I = nextI) {
+    nextI = std::next(I); // I may be invalidated by the use updater.
+    MachineInstr *UseMI = &*I;
+    if (UseMI->isDebugValue()) {
+      FoundDebugUse = true;
+      Updater(UseMI);
+    }
+  }
+  return FoundDebugUse;
+}
+
 /// markUsesInDebugValueAsUndef - Mark every DBG_VALUE referencing the
 /// specified register as undefined which causes the DBG_VALUE to be
 /// deleted during LiveDebugVariables analysis.
 void MachineRegisterInfo::markUsesInDebugValueAsUndef(unsigned Reg) const {
   // Mark any DBG_VALUE that uses Reg as undef (but don't delete it.)
-  MachineRegisterInfo::use_instr_iterator nextI;
-  for (use_instr_iterator I = use_instr_begin(Reg), E = use_instr_end();
-       I != E; I = nextI) {
-    nextI = std::next(I);  // I is invalidated by the setReg
-    MachineInstr *UseMI = &*I;
-    if (UseMI->isDebugValue())
-      UseMI->getOperand(0).setReg(0U);
+  updateDebugValueUses(
+      Reg, [](MachineInstr *DbgMI) { DbgMI->getOperand(0).setReg(0U); });
+}
+
+void MachineRegisterInfo::salvageDebugInfo(
+    MachineOperand &DyingOp, MachineInstr &ReplacementMI,
+    function_ref<void(unsigned Src, unsigned Dst)> VRegCallback) {
+  if (ReplacementMI.isCopy()) {
+    // The source of the replacement copy must be the dying op.
+    unsigned SrcVReg = DyingOp.getReg();
+    if (ReplacementMI.getOperand(1).getReg() != SrcVReg)
+      return;
+
+    unsigned DstVReg = ReplacementMI.getOperand(0).getReg();
+
+    bool Salvaged =
+        updateDebugValueUses(SrcVReg, [DstVReg](MachineInstr *DbgMI) {
+          DbgMI->getOperand(0).setReg(DstVReg);
+          DEBUG(dbgs() << "SALVAGE:  " << *DbgMI << "\n");
+        });
+    if (Salvaged)
+      VRegCallback(SrcVReg, DstVReg);
   }
+  // TODO: Try to salvage debug values through moves, spills, etc.
 }
 
 static const Function *getCalledFunction(const MachineInstr &MI) {
   for (const MachineOperand &MO : MI.operands()) {
     if (!MO.isGlobal())
       continue;
     const Function *Func = dyn_cast<Function>(MO.getGlobal());
     if (Func != nullptr)

lib/CodeGen/RegAllocFast.cpp

private:
     };
 
     using LiveRegMap = SparseSet<LiveReg>;
 
     /// This map contains entries for each virtual register that is currently
     /// available in a physical register.
     LiveRegMap LiveVirtRegs;
 
+    /// This maps virtual registers to the debug values in those registers.
     DenseMap<unsigned, SmallVector<MachineInstr *, 4>> LiveDbgValueMap;
 
     /// Track the state of a physical register.
     enum RegState {
       /// A disabled register is not available for allocation, but an alias may
       /// be in use. A register can only be moved out of the disabled state if
       /// all aliases are disabled.
       regDisabled,
private:
 
     LiveRegMap::iterator assignVirtToPhysReg(unsigned VReg, MCPhysReg PhysReg);
     LiveRegMap::iterator allocVirtReg(MachineInstr &MI, LiveRegMap::iterator,
                                       unsigned Hint);
     LiveRegMap::iterator defineVirtReg(MachineInstr &MI, unsigned OpNum,
                                        unsigned VirtReg, unsigned Hint);
     LiveRegMap::iterator reloadVirtReg(MachineInstr &MI, unsigned OpNum,
                                        unsigned VirtReg, unsigned Hint);
+    void handleLiveDbgValRemap(unsigned SrcVReg, unsigned DstVReg);
     void spillAll(MachineBasicBlock::iterator MI);
     bool setPhysReg(MachineInstr &MI, unsigned OpNum, MCPhysReg PhysReg);
 
     void dumpState();
   };
 
 } // end anonymous namespace
 
if (New) {
     int FrameIndex = getStackSpaceFor(VirtReg, RC);
     DEBUG(dbgs() << "Reloading " << printReg(VirtReg, TRI) << " into "
                  << printReg(LRI->PhysReg, TRI) << "\n");
     TII->loadRegFromStackSlot(*MBB, MI, LRI->PhysReg, FrameIndex, &RC, TRI);
     ++NumLoads;
   } else if (LRI->Dirty) {
     if (isLastUseOfLocalReg(MO)) {
       DEBUG(dbgs() << "Killing last use: " << MO << "\n");
-      if (MO.isUse())
+      if (MO.isUse()) {
+        MRI->salvageDebugInfo(MO, MI,
+                              [this](unsigned SrcVReg, unsigned DstVReg) {
+                                handleLiveDbgValRemap(SrcVReg, DstVReg);
+                              });
         MO.setIsKill();
-      else
+      } else
         MO.setIsDead();
     } else if (MO.isKill()) {
       DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n");
       MO.setIsKill(false);
     } else if (MO.isDead()) {
       DEBUG(dbgs() << "Clearing dubious dead: " << MO << "\n");
       MO.setIsDead(false);
     }
RegAllocFast::LiveRegMap::iterator RegAllocFast::reloadVirtReg(MachineInstr &MI,
   }
   assert(LRI->PhysReg && "Register not assigned");
   LRI->LastUse = &MI;
   LRI->LastOpNum = OpNum;
   markRegUsedInInstr(LRI->PhysReg);
   return LRI;
 }
 
+/// Update LiveDbgValueMap when DBG_VALUE instructions using \p SrcVReg are
+/// updated to point to \p DstVReg.
+void RegAllocFast::handleLiveDbgValRemap(unsigned SrcVReg, unsigned DstVReg) {
+  assert(TargetRegisterInfo::isVirtualRegister(SrcVReg) &&
+         TargetRegisterInfo::isVirtualRegister(DstVReg) &&
+         "Source and destination are not both virtual registers");
+  auto DbgUsesIt = LiveDbgValueMap.find(SrcVReg);
+  if (DbgUsesIt != LiveDbgValueMap.end()) {
+    auto &DbgUses = DbgUsesIt->second;
+    LiveDbgValueMap[DstVReg].append(DbgUses.begin(), DbgUses.end());
+    DbgUses.clear();
+  }
+}
+
 /// Changes operand OpNum in MI the refer the PhysReg, considering subregs. This
 /// may invalidate any operand pointers.  Return true if the operand kills its
 /// register.
 bool RegAllocFast::setPhysReg(MachineInstr &MI, unsigned OpNum,
                               MCPhysReg PhysReg) {
   MachineOperand &MO = MI.getOperand(OpNum);
   bool Dead = MO.isDead();
   if (!MO.getSubReg()) {

test/CodeGen/X86/salvage-dbg-val-regallocfast.ll

+; RUN: llc -O0 < %s | FileCheck %s
+
+; // Source (compiled at -Os -g):
+; struct S { int x = 0xfefefefe; };
+; static void escape(void *p) { asm volatile("" : : "g"(p) : "memory"); }
+; int main() {
+;   S s;
+;   int x = s.x;
+;   escape(&s);
+;   return 0;
+; }
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.13.0"
+
+%struct.S = type { i32 }
+
+define i32 @main() !dbg !8 {
+entry:
+  %s = alloca %struct.S, align 4
+  %0 = bitcast %struct.S* %s to i8*, !dbg !18
+
+; CHECK: DEBUG_VALUE: main:s <- $rax
+  call void @llvm.dbg.value(metadata %struct.S* %s, metadata !13, metadata !DIExpression()), !dbg !19
+
+; CHECK: DEBUG_VALUE: S:this <- $rax
+  call void @llvm.dbg.value(metadata %struct.S* %s, metadata !20, metadata !DIExpression()), !dbg !28
+
+; CHECK: DEBUG_VALUE: S:this <- $rax
+  call void @llvm.dbg.value(metadata %struct.S* %s, metadata !30, metadata !DIExpression()), !dbg !33
+  %x.i.i = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0, !dbg !35
+  store i32 -16843010, i32* %x.i.i, align 4, !dbg !35, !tbaa !36
+
+; CHECK: DEBUG_VALUE: main:x <- [DW_OP_deref, DW_OP_stack_value] $rax
+  call void @llvm.dbg.value(metadata %struct.S* %s, metadata !17, metadata !DIExpression(DW_OP_deref, DW_OP_stack_value)), !dbg !41
+
+; CHECK: DEBUG_VALUE: escape:p <- $rax
+  call void @llvm.dbg.value(metadata i8* %0, metadata !42, metadata !DIExpression()) #3, !dbg !48
+  call void asm sideeffect "", "imr,~{memory},~{dirflag},~{fpsr},~{flags}"(i8* nonnull %0) #3, !dbg !50, !srcloc !51
+  ret i32 0, !dbg !53
+}
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5, !6}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 7.0.0 (trunk 325319) (llvm/trunk 325317)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "extractvalue-e2e.cc", directory: "/Users/vsk/Desktop/extractvalue")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{i32 7, !"PIC Level", i32 2}
+!7 = !{!"clang version 7.0.0 (trunk 325319) (llvm/trunk 325317)"}
+!8 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 9, type: !9, isLocal: false, isDefinition: true, scopeLine: 9, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !12)
+!9 = !DISubroutineType(types: !10)
+!10 = !{!11}
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !{!13, !17}
+!13 = !DILocalVariable(name: "s", scope: !8, file: !1, line: 10, type: !14)
+!14 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "S", file: !1, line: 1, size: 32, flags: DIFlagTypePassByValue, elements: !15, identifier: "_ZTS1S")
+!15 = !{!16}
+!16 = !DIDerivedType(tag: DW_TAG_member, name: "x", scope: !14, file: !1, line: 2, baseType: !11, size: 32)
+!17 = !DILocalVariable(name: "x", scope: !8, file: !1, line: 11, type: !11)
+!18 = !DILocation(line: 10, column: 3, scope: !8)
+!19 = !DILocation(line: 10, column: 5, scope: !8)
+!20 = !DILocalVariable(name: "this", arg: 1, scope: !21, type: !27, flags: DIFlagArtificial | DIFlagObjectPointer)
+!21 = distinct !DISubprogram(name: "S", linkageName: "_ZN1SC1Ev", scope: !14, file: !1, line: 1, type: !22, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagArtificial | DIFlagPrototyped, isOptimized: true, unit: !0, declaration: !25, variables: !26)
+!22 = !DISubroutineType(types: !23)
+!23 = !{null, !24}
+!24 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !14, size: 64, flags: DIFlagArtificial | DIFlagObjectPointer)
+!25 = !DISubprogram(name: "S", scope: !14, type: !22, isLocal: false, isDefinition: false, flags: DIFlagArtificial | DIFlagPrototyped, isOptimized: true)
+!26 = !{!20}
+!27 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !14, size: 64)
+!28 = !DILocation(line: 0, scope: !21, inlinedAt: !29)
+!29 = distinct !DILocation(line: 10, column: 5, scope: !8)
+!30 = !DILocalVariable(name: "this", arg: 1, scope: !31, type: !27, flags: DIFlagArtificial | DIFlagObjectPointer)
+!31 = distinct !DISubprogram(name: "S", linkageName: "_ZN1SC2Ev", scope: !14, file: !1, line: 1, type: !22, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagArtificial | DIFlagPrototyped, isOptimized: true, unit: !0, declaration: !25, variables: !32)
+!32 = !{!30}
+!33 = !DILocation(line: 0, scope: !31, inlinedAt: !34)
+!34 = distinct !DILocation(line: 1, column: 8, scope: !21, inlinedAt: !29)
+!35 = !DILocation(line: 2, column: 7, scope: !31, inlinedAt: !34)
+!36 = !{!37, !38, i64 0}
+!37 = !{!"_ZTS1S", !38, i64 0}
+!38 = !{!"int", !39, i64 0}
+!39 = !{!"omnipotent char", !40, i64 0}
+!40 = !{!"Simple C++ TBAA"}
+!41 = !DILocation(line: 11, column: 7, scope: !8)
+!42 = !DILocalVariable(name: "p", arg: 1, scope: !43, file: !1, line: 7, type: !46)
+!43 = distinct !DISubprogram(name: "escape", linkageName: "_ZL6escapePv", scope: !1, file: !1, line: 7, type: !44, isLocal: true, isDefinition: true, scopeLine: 7, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !47)
+!44 = !DISubroutineType(types: !45)
+!45 = !{null, !46}
+!46 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: null, size: 64)
+!47 = !{!42}
+!48 = !DILocation(line: 7, column: 26, scope: !43, inlinedAt: !49)
+!49 = distinct !DILocation(line: 14, column: 3, scope: !8)
+!50 = !DILocation(line: 7, column: 31, scope: !43, inlinedAt: !49)
+!51 = !{i32 141}
+!52 = !DILocation(line: 16, column: 1, scope: !8)
+!53 = !DILocation(line: 15, column: 3, scope: !8)