[DebugInfo] Track multiple registers in DbgEntityHistoryCalculator

[dstenb]

Summary

When calculating the debug value history, DbgEntityHistoryCalculator
would only keep track of register clobbering for the latest debug value
per inlined entity. This meant that preceding register-described debug
value fragments would live on until the next overlapping debug value,
ignoring any potential clobbering. This patch amends
DbgEntityHistoryCalculator so that it keeps track of all registers that
a inlined entity's currently live debug values are described by.

The DebugInfo/COFF/pieces.ll test case has had to be changed since
previously a register-described fragment would incorrectly outlive its
basic block.

The parent patch is expected to increase the coverage slightly, as it
makes sure that location list entries are inserted after clobbered
fragments, and this patch is expected to decrease it, as it stops
preceding register-described from living longer than they should. All
in all, this patch and the preceding patch has a negligible effect
on the output from `llvm-dwarfdump -statistics' for a clang-3.4 binary
built using the RelWithDebInfo build profile. "Scope bytes covered"
increases by 0.5%, and "variables with location" increases from 2212083
to 2212088, but it should improve the accuracy quite a bit.

This fixes PR40283.

[aprantl]

I think this looks reasonable. Is there any performance hit?

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

131 ↗

(On Diff #192648)

///
\p Var

161 ↗

(On Diff #192648)

Should this be a SmallDenseMap?

[dstenb]

In D59942#1447919, @aprantl wrote:

Is there any performance hit?

See https://reviews.llvm.org/D59941#1451056 for some measurements. The decrease in performance appears to be small.

[dstenb]

Address comments.

[dstenb]

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

161 ↗

(On Diff #192648)

Sorry, yes, this was totally overkill. For example, in a RelWithDebInfo+asan build the maximum size of the map was 11, and in 99.98% of the cases the size of the map was less than or equal 2.

[dstenb]

Rebase after update of D59941.

[aprantl]

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

183 ↗

(On Diff #193289)

if (!TrackedRegs.count(NewReg))

186 ↗

(On Diff #193289)

for symmetry, perhaps write this as TrackedRegs.insert({NewReg, true});

190 ↗

(On Diff #193289)

Is it safe to iterate over the map here, or can this introduce nondeterminism?

[dstenb]

Address review comments.

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

186 ↗

(On Diff #193289)

If it is okay, I'd prefer to keep it as it is, to be consistent with the compound-assignment a few lines above:

if (unsigned Reg = isDescribedByReg(DV))
  TrackedRegs[Reg] |= !Overlaps;

190 ↗

(On Diff #193289)

Yes, the iteration order does not matter here. The only effects (in non-crash cases) that each call to dropRegDescribedVar(RegVars, I.first, Var) has is:

1. Look up VarSet = RegVars[I.first] in the RegVars map.
2. Remove Var from the VarSet set.
3. Remove I.first from RegVars if VarSet is empty.

[aprantl]

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

161 ↗

(On Diff #192648)

So should it be size 2 then? ;-)

[dstenb]

Thanks for the review! Just so that I don't misunderstand something; is the LGTM specifically for the changes in this patch, or does that imply the entire patch series?

lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

161 ↗

(On Diff #192648)

Right! I'll change that.

[aprantl]

If there are remaining patches that I haven't accepted yet, please ping them.

[dstenb]

In D59942#1456415, @aprantl wrote:

If there are remaining patches that I haven't accepted yet, please ping them.

In addition to D59941, this patch is dependent on four preceding refactoring commits (which are listed in the revision stack). I pinged / added reviewers to them now!

llvm/trunk/include/llvm/CodeGen/DbgEntityHistoryCalculator.h

 private:
   EntriesMap VarEntries;
 
 public:
   bool startDbgValue(InlinedEntity Var, const MachineInstr &MI,
                      EntryIndex &NewIndex);
   EntryIndex startClobber(InlinedEntity Var, const MachineInstr &MI);
 
-  // Returns register currently describing @Var. If @Var is currently
-  // unaccessible or is not described by a register, returns 0.
-  unsigned getRegisterForVar(InlinedEntity Var) const;
-
   Entry &getEntry(InlinedEntity Var, EntryIndex Index) {
     auto &Entries = VarEntries[Var];
     return Entries[Index];
   }
 
   bool empty() const { return VarEntries.empty(); }
   void clear() { VarEntries.clear(); }
   EntriesMap::const_iterator begin() const { return VarEntries.begin(); }

llvm/trunk/lib/CodeGen/AsmPrinter/DbgEntityHistoryCalculator.cpp

bool DbgValueHistoryMap::startDbgValue(InlinedEntity Var,
   Entries.emplace_back(&MI, Entry::DbgValue);
   NewIndex = Entries.size() - 1;
   return true;
 }
 
 EntryIndex DbgValueHistoryMap::startClobber(InlinedEntity Var,
                                             const MachineInstr &MI) {
   auto &Entries = VarEntries[Var];
+  // If an instruction clobbers multiple registers that the variable is
+  // described by, then we may have already created a clobbering instruction.
+  if (Entries.back().isClobber() && Entries.back().getInstr() == &MI)
+    return Entries.size() - 1;
   Entries.emplace_back(&MI, Entry::Clobber);
   return Entries.size() - 1;
 }
 
 void DbgValueHistoryMap::Entry::endEntry(EntryIndex Index) {
   // For now, instruction ranges are not allowed to cross basic block
   // boundaries.
   assert(isDbgValue() && "Setting end index for non-debug value");
   assert(!isClosed() && "End index has already been set");
   EndIndex = Index;
 }
 
-unsigned DbgValueHistoryMap::getRegisterForVar(InlinedEntity Var) const {
-  const auto &I = VarEntries.find(Var);
-  if (I == VarEntries.end())
-    return 0;
-  const auto &Entries = I->second;
-  if (Entries.empty() || Entries.back().isClosed())
-    return 0;
-  if (Entries.back().isClobber())
-    return 0;
-  return isDescribedByReg(*Entries.back().getInstr());
-}
-
 void DbgLabelInstrMap::addInstr(InlinedEntity Label, const MachineInstr &MI) {
   assert(MI.isDebugLabel() && "not a DBG_LABEL");
   LabelInstr[Label] = &MI;
 }
 
 namespace {
 
 // Maps physreg numbers to the variables they describe.

 static void addRegDescribedVar(RegDescribedVarsMap &RegVars, unsigned RegNo,
                                InlinedEntity Var) {
   assert(RegNo != 0U);
   auto &VarSet = RegVars[RegNo];
   assert(!is_contained(VarSet, Var));
   VarSet.push_back(Var);
 }
 
+/// Create a clobbering entry and end all open debug value entries
+/// for \p Var that are described by \p RegNo using that entry.
 static void clobberRegEntries(InlinedEntity Var, unsigned RegNo,
                               const MachineInstr &ClobberingInstr,
                               DbgValueEntriesMap &LiveEntries,
                               DbgValueHistoryMap &HistMap) {
   EntryIndex ClobberIndex = HistMap.startClobber(Var, ClobberingInstr);
 
-  // TODO: Close all preceding live entries that are clobbered by this
-  // instruction.
-  EntryIndex ValueIndex = ClobberIndex - 1;
-  auto &ValueEntry = HistMap.getEntry(Var, ValueIndex);
-  ValueEntry.endEntry(ClobberIndex);
-  LiveEntries[Var].erase(ValueIndex);
+  // Close all entries whose values are described by the register.
+  SmallVector<EntryIndex, 4> IndicesToErase;
+  for (auto Index : LiveEntries[Var]) {
+    auto &Entry = HistMap.getEntry(Var, Index);
+    assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
+    if (isDescribedByReg(*Entry.getInstr()) == RegNo) {
+      IndicesToErase.push_back(Index);
+      Entry.endEntry(ClobberIndex);
+    }
+  }
+
+  // Drop all entries that have ended.
+  for (auto Index : IndicesToErase)
+    LiveEntries[Var].erase(Index);
 }
 
 /// Add a new debug value for \p Var. Closes all overlapping debug values.
 static void handleNewDebugValue(InlinedEntity Var, const MachineInstr &DV,
                                 RegDescribedVarsMap &RegVars,
                                 DbgValueEntriesMap &LiveEntries,
                                 DbgValueHistoryMap &HistMap) {
-  // TODO: We should track all registers which this variable is currently
-  // described by.
-
-  if (unsigned PrevReg = HistMap.getRegisterForVar(Var))
-    dropRegDescribedVar(RegVars, PrevReg, Var);
-
   EntryIndex NewIndex;
   if (HistMap.startDbgValue(Var, DV, NewIndex)) {
+    SmallDenseMap<unsigned, bool, 4> TrackedRegs;
+
     // If we have created a new debug value entry, close all preceding
     // live entries that overlap.
     SmallVector<EntryIndex, 4> IndicesToErase;
     const DIExpression *DIExpr = DV.getDebugExpression();
     for (auto Index : LiveEntries[Var]) {
       auto &Entry = HistMap.getEntry(Var, Index);
       assert(Entry.isDbgValue() && "Not a DBG_VALUE in LiveEntries");
       const MachineInstr &DV = *Entry.getInstr();
-      if (DIExpr->fragmentsOverlap(DV.getDebugExpression())) {
+      bool Overlaps = DIExpr->fragmentsOverlap(DV.getDebugExpression());
+      if (Overlaps) {
         IndicesToErase.push_back(Index);
         Entry.endEntry(NewIndex);
       }
+      if (unsigned Reg = isDescribedByReg(DV))
+        TrackedRegs[Reg] |= !Overlaps;
+    }
+
+    // If the new debug value is described by a register, add tracking of
+    // that register if it is not already tracked.
+    if (unsigned NewReg = isDescribedByReg(DV)) {
+      if (!TrackedRegs.count(NewReg))
+        addRegDescribedVar(RegVars, NewReg, Var);
+      LiveEntries[Var].insert(NewIndex);
+      TrackedRegs[NewReg] = true;
     }
+
+    // Drop tracking of registers that are no longer used.
+    for (auto I : TrackedRegs)
+      if (!I.second)
+        dropRegDescribedVar(RegVars, I.first, Var);
+
     // Drop all entries that have ended, and mark the new entry as live.
     for (auto Index : IndicesToErase)
       LiveEntries[Var].erase(Index);
     LiveEntries[Var].insert(NewIndex);
   }
-
-  if (unsigned NewReg = isDescribedByReg(DV))
-    addRegDescribedVar(RegVars, NewReg, Var);
 }
 
 // Terminate the location range for variables described by register at
 // @I by inserting @ClobberingInstr to their history.
 static void clobberRegisterUses(RegDescribedVarsMap &RegVars,
                                 RegDescribedVarsMap::iterator I,
                                 DbgValueHistoryMap &HistMap,
                                 DbgValueEntriesMap &LiveEntries,

llvm/trunk/test/DebugInfo/COFF/pieces.ll

 
 
 ; ASM-LABEL:  .short  4423                    # Record kind: S_GPROC32_ID
 ; ASM:        .asciz  "loop_csr"              # Function name
 ; ASM:        .short  4414                    # Record kind: S_LOCAL
 ; ASM:        .asciz  "o"
 ; ASM:        .cv_def_range    [[oy_ox_start]] [[ox_start]], "C\021\030\000\000\000\000\000\000\000"
 ; ASM:        .cv_def_range    [[oy_ox_start]] [[oy_start]], "C\021\027\000\000\000\004\000\000\000"
-; ASM:        .cv_def_range    [[ox_start]] .Lfunc_end0, "C\021\030\000\000\000\000\000\000\000"
+; ASM:        .cv_def_range    [[ox_start]] [[oy_end]], "C\021\030\000\000\000\000\000\000\000"
 ; ASM:        .cv_def_range    [[oy_start]] [[oy_end]], "C\021\027\000\000\000\004\000\000\000"
 
 
 ; OBJ-LABEL: GlobalProcIdSym {
 ; OBJ:         Kind: S_GPROC32_ID (0x1147)
 ; OBJ:         DisplayName: loop_csr
 ; OBJ:       }
 ; OBJ:       LocalSym {

llvm/trunk/test/DebugInfo/MIR/X86/clobbered-fragments.mir

 # RUN: llc -O1 -start-after=livedebugvalues -o - %s | FileCheck %s
 
 # Reproducer based on the following C file:
 #
 # int global1, global2, global3;
 #
 # extern void ext1(int);
 # extern void ext2(int, int);
 # extern void ext3(int, int, int);
 #
 # int test1() {
 #   int local[3] = {global1, 123, 456};
 #   ext2(local[0], local[1]);
 #   return local[1];
 # }
 #
+# int test2() {
+#   int local[3] = {global1, global2, global3};
+#   ext3(local[0], local[1], local[2]);
+#   return local[0];
+# }
+#
 # Compiled using -O1 -g.
 
 --- |
   target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"
 
   @global1 = common global i32 0, align 4
   @global2 = common global i32 0, align 4
   @global3 = common global i32 0, align 4
 
   ; Function Attrs: nounwind uwtable
   define i32 @test1() #0 !dbg !8 {
   entry:
     %0 = load i32, i32* @global1, align 4, !dbg !16
     call void @llvm.dbg.value(metadata i32 %0, metadata !12, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)), !dbg !16
     call void @llvm.dbg.value(metadata i32 123, metadata !12, metadata !DIExpression(DW_OP_LLVM_fragment, 32, 32)), !dbg !16
     call void @llvm.dbg.value(metadata i32 456, metadata !12, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 32)), !dbg !16
     tail call void @ext2(i32 %0, i32 123), !dbg !16
     ret i32 123, !dbg !17
   }
 
   declare void @ext2(i32, i32)
 
+  ; Function Attrs: nounwind uwtable
+  define i32 @test2() #0 !dbg !18 {
+  entry:
+    %0 = load i32, i32* @global1, align 4, !dbg !20
+    call void @llvm.dbg.value(metadata i32 %0, metadata !19, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 32)), !dbg !20
+    %1 = load i32, i32* @global2, align 4, !dbg !20
+    call void @llvm.dbg.value(metadata i32 %1, metadata !19, metadata !DIExpression(DW_OP_LLVM_fragment, 32, 32)), !dbg !20
+    %2 = load i32, i32* @global3, align 4, !dbg !20
+    call void @llvm.dbg.value(metadata i32 %2, metadata !19, metadata !DIExpression(DW_OP_LLVM_fragment, 64, 32)), !dbg !20
+    tail call void @ext3(i32 %0, i32 %1, i32 %2) #3, !dbg !20
+    ret i32 %0, !dbg !21
+  }
+
+  declare void @ext3(i32, i32, i32)
+
   ; Function Attrs: nounwind readnone speculatable
   declare void @llvm.dbg.value(metadata, metadata, metadata) #1
 
   attributes #0 = { nounwind uwtable }
   attributes #1 = { nounwind readnone speculatable }
 
   !llvm.dbg.cu = !{!1}
   !llvm.module.flags = !{!5, !6}
--- |
   !10 = !{!4}
   !11 = !{!12}
   !12 = !DILocalVariable(name: "local", scope: !8, file: !2, line: 8, type: !13)
   !13 = !DICompositeType(tag: DW_TAG_array_type, baseType: !4, size: 96, elements: !14)
   !14 = !{!15}
   !15 = !DISubrange(count: 3)
   !16 = !DILocation(line: 8, scope: !8)
   !17 = !DILocation(line: 9, scope: !8)
+  !18 = distinct !DISubprogram(name: "test2", scope: !2, file: !2, line: 7, type: !9, scopeLine: 7, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !1, retainedNodes: !11)
+  !19 = !DILocalVariable(name: "local", scope: !18, file: !2, line: 8, type: !13)
+  !20 = !DILocation(line: 15, scope: !18)
+  !21 = !DILocation(line: 16, scope: !18)
 
 ...
 ---
 name:            test1
 tracksRegLiveness: true
 body:             |
   bb.0.entry:
     frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp

 
 # CHECK: .Ltmp1
 # CHECK-NEXT: #DEBUG_VALUE: test1:local <- [DW_OP_LLVM_fragment 64 32] 456
 # CHECK-NEXT: #DEBUG_VALUE: test1:local <- [DW_OP_LLVM_fragment 32 32] 123
 # CHECK-NEXT: #DEBUG_VALUE: test1:local <- [DW_OP_LLVM_fragment 0 32] $edi
 # CHECK:         callq   ext2
 # CHECK-NEXT: .Ltmp2:
 
+...
+---
+name:            test2
+tracksRegLiveness: true
+body:             |
+  bb.0.entry:
+    liveins: $rbx
+
+    frame-setup PUSH64r killed $rbx, implicit-def $rsp, implicit $rsp, debug-location !20
+    renamable $ebx = MOV32rm $rip, 1, $noreg, @global1, $noreg, debug-location !20 :: (dereferenceable load 4 from @global1)
+    DBG_VALUE $ebx, $noreg, !19, !DIExpression(DW_OP_LLVM_fragment, 0, 32), debug-location !20
+    renamable $esi = MOV32rm $rip, 1, $noreg, @global2, $noreg, debug-location !20 :: (dereferenceable load 4 from @global2)
+    DBG_VALUE $esi, $noreg, !19, !DIExpression(DW_OP_LLVM_fragment, 32, 32), debug-location !20
+    renamable $edx = MOV32rm $rip, 1, $noreg, @global3, $noreg, debug-location !20 :: (dereferenceable load 4 from @global3)
+    DBG_VALUE $edx, $noreg, !19, !DIExpression(DW_OP_LLVM_fragment, 64, 32), debug-location !20
+    $edi = MOV32rr $ebx, debug-location !20
+    CALL64pcrel32 @ext3, csr_64, implicit $rsp, implicit $ssp, implicit killed $edi, implicit $esi, implicit $edx, implicit-def $rsp, implicit-def $ssp, debug-location !20
+    $eax = MOV32rr killed $ebx, debug-location !20
+    $rbx = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !20
+    RETQ killed $eax, debug-location !21
+
+...
+
+# CHECK: .Ltmp4:
+# CHECK-NEXT: #DEBUG_VALUE: test2:local <- [DW_OP_LLVM_fragment 0 32] $ebx
+# CHECK: .Ltmp5:
+# CHECK-NEXT: #DEBUG_VALUE: test2:local <- [DW_OP_LLVM_fragment 32 32] $esi
+# CHECK: .Ltmp6:
+# CHECK-NEXT: #DEBUG_VALUE: test2:local <- [DW_OP_LLVM_fragment 64 32] $edx
+# CHECK:         callq   ext3
+# CHECK-NEXT: .Ltmp7:
+# CHECK:         popq    %rbx
+# CHECK-NEXT: .Ltmp8:
+
 #### Location list for test1:local.
 
 # Verify that a location list entry, which does not contain the fragment that
 # is described by the clobbered $edi, is emitted directly after the call to
 # ext2().
 
 # CHECK: .Ldebug_loc0:
 # CHECK-NEXT: .quad   .Ltmp1-.Lfunc_begin0

 # CHECK-NEXT: .byte   200    # 456
 # CHECK-NEXT: .byte   3      #
 # CHECK-NEXT: .byte   159    # DW_OP_stack_value
 # CHECK-NEXT: .byte   147    # DW_OP_piece
 # CHECK-NEXT: .byte   4      # 4
 # CHECK-NEXT: .quad   0
 # CHECK-NEXT: .quad   0
 
+#### Location list for test2:local.
+
+# Verify that the debug values that are described by $edi and $edx are
+# considered clobbered by the call to ext3(), leaving a location list entry
+# after the call where the first 32 bits are still described by $ebx.
+# That location list entry is valid until the restore of the register.
+
+# CHECK: .Ldebug_loc1:
+# CHECK-NEXT: .quad   .Ltmp4-.Lfunc_begin0
+# CHECK-NEXT: .quad   .Ltmp5-.Lfunc_begin0
+# CHECK-NEXT: .short  3                       # Loc expr size
+# CHECK-NEXT: .byte   83                      # super-register DW_OP_reg3
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .quad   .Ltmp5-.Lfunc_begin0
+# CHECK-NEXT: .quad   .Ltmp6-.Lfunc_begin0
+# CHECK-NEXT: .short  6                       # Loc expr size
+# CHECK-NEXT: .byte   83                      # super-register DW_OP_reg3
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .byte   84                      # super-register DW_OP_reg4
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .quad   .Ltmp6-.Lfunc_begin0
+# CHECK-NEXT: .quad   .Ltmp7-.Lfunc_begin0
+# CHECK-NEXT: .short  9                       # Loc expr size
+# CHECK-NEXT: .byte   83                      # super-register DW_OP_reg3
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .byte   84                      # super-register DW_OP_reg4
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .byte   81                      # super-register DW_OP_reg1
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .quad   .Ltmp7-.Lfunc_begin0
+# CHECK-NEXT: .quad   .Ltmp8-.Lfunc_begin0
+# CHECK-NEXT: .short  3                       # Loc expr size
+# CHECK-NEXT: .byte   83                      # super-register DW_OP_reg3
+# CHECK-NEXT: .byte   147                     # DW_OP_piece
+# CHECK-NEXT: .byte   4                       # 4
+# CHECK-NEXT: .quad   0
+# CHECK-NEXT: .quad   0