[DebugInfo][InstrRef] Fix error in copy handling in InstrRefLDV

[StephenTozer]

Summary

Currently, an error exists when InstrRefBasedLDV observes transfers of variables across copies, which causes it to lose track of variables under certain circumstances, resulting in shorter lifetimes for those variables as LDV gives up searching for live locations for them.

The issue can be summarised as, when the TransferTracker observes a copy, under certain circumstances it may start tracking variables, that previously were in the source location, in the destination location instead. This is obviously valid, but it then tries to clobber the destination location due to it being overwritten, including clobbering the variables that were just moved to use this location. This does not immediately kill the variable, but causes it to stop being tracked, potentially ending its lifetime early.

This patch fixes this issue by first tracking the specific set of variables and values that already live in the destination, then after updating our underlying store of values (in the MLocTracker) we try to find new locations for all those variables that have been clobbered. Only after that do we potentially move other variables into the destination location, ensuring that no variables are erroneously clobbered and all the existing variables in the destination are given proper homes.

[Orlando]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1777

Is it significant that the "The copy might have clobbered variables based on the destination register" loop has moved above up above this part?

llvm/test/DebugInfo/X86/instr-ref-track-clobbers.mir

17–18

Is the unordered-ness of CHECK-DAG limited to anything between the previous and next CHECK lines or not limited at all, do you know?

Personally I think it would be better to simplify the test to check for the behaviour that occurs now with a comment explaining other permissible behaviour, rather than trying to encode all correct behaviours. wdyt?

[StephenTozer]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1777

Yes - the order in which we want these operations performed is:

1. Keep track of the variables in the Dest and what value(s) they referred to.
2. Update our location->value tracker to reflect the copy.
3. Find a new location for (or undef) the variables that were in Dest.
4. Now that "Dest" is empty, transfer the variables that were in Source to Dest.

Step 3 should come before step 4 because we want to empty out the bucket for Dest before moving other variables into it, otherwise TTracker may be confused about which variables were previously there and which ones have just been moved there.

[StephenTozer]

llvm/test/DebugInfo/X86/instr-ref-track-clobbers.mir

17–18

I believe the CHECK-DAG lines will still be checked between the previous and next non-DAG directive. I'm personally ambivalent about the "check current behaviour with a comment" vs "check any permissible behaviour" approaches, happy to switch to the former!

[Orlando]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1777

That makes sense, thanks. One last thing then - is it necessary for 2 (performCopy) to come between 1 and 3, or could we fold 3 into 1 (i.e. do the clobberMloc call in the first loop rather than separately)?

llvm/test/DebugInfo/X86/instr-ref-track-clobbers.mir

17–18

I would prefer that - it'd be easier to read and there will be less room for things to slip through unnoticed.

[StephenTozer]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1777

3 should come after 2, because the behaviour of step 3 is somewhat dependent on step 2; step 2 updates the MLocTracker (which maps locations -> values), and step 3 then uses that updated location->value mapping. This is necessary to make sure that we don't assume that the current location is automatically a valid location (since it would still appear to contain the right value at that point), while at the same time being able to choose the current location if we have an identity copy (silly, but it can actually happen).

Technically we could try and account for this in step 3 and fold it into 1, but I think that actually muddles the logic, since it would mean the TransferTracker has to start assuming that maybe the MLocTracker has wrong info and trying to account for that, while taking this approach means that the TTracker doesn't have to worry about that.

[Orlando]

LGTM (once the test is updated), thanks.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1777

Ok great - thanks for the explanation! With that, I'm happy to approve.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

public:
   void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
                    bool MakeUndef = true) {
     auto ActiveMLocIt = ActiveMLocs.find(MLoc);
     if (ActiveMLocIt == ActiveMLocs.end())
       return;
 
     // What was the old variable value?
     ValueIDNum OldValue = VarLocs[MLoc.asU64()];
+    clobberMloc(MLoc, OldValue, Pos, MakeUndef);
+  }
+  /// Overload that takes an explicit value \p OldValue for when the value in
+  /// \p MLoc has changed and the TransferTracker's locations have not been
+  /// updated yet.
+  void clobberMloc(LocIdx MLoc, ValueIDNum OldValue,
+                   MachineBasicBlock::iterator Pos, bool MakeUndef = true) {
+    auto ActiveMLocIt = ActiveMLocs.find(MLoc);
+    if (ActiveMLocIt == ActiveMLocs.end())
+      return;
+
     VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;
 
     // Examine the remaining variable locations: if we can find the same value
     // again, we can recover the location.
     Optional<LocIdx> NewLoc = None;
     for (auto Loc : MTracker->locations())
       if (Loc.Value == OldValue)
         NewLoc = Loc.Idx;
bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
   // ignore this condition.
   if (EmulateOldLDV && !isCalleeSavedReg(DestReg))
     return false;
 
   // InstrRefBasedImpl only followed killing copies.
   if (EmulateOldLDV && !SrcRegOp->isKill())
     return false;
 
+  // Before we update MTracker, remember which values were present in each of
+  // the locations about to be overwritten, so that we can recover any
+  // potentially clobbered variables.
+  DenseMap<LocIdx, ValueIDNum> ClobberedLocs;
+  if (TTracker) {
+    for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
+      LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
+      auto MLocIt = TTracker->ActiveMLocs.find(ClobberedLoc);
+      // If ActiveMLocs isn't tracking this location or there are no variables
+      // using it, don't bother remembering.
+      if (MLocIt == TTracker->ActiveMLocs.end() || MLocIt->second.empty())
+        continue;
+      ValueIDNum Value = MTracker->readReg(*RAI);
+      ClobberedLocs[ClobberedLoc] = Value;
+    }
+  }
+
   // Copy MTracker info, including subregs if available.
   InstrRefBasedLDV::performCopy(SrcReg, DestReg);
 
+  // The copy might have clobbered variables based on the destination register.
+  // Tell TTracker about it, passing the old ValueIDNum to search for
+  // alternative locations (or else terminating those variables).
+  if (TTracker) {
+    for (auto LocVal : ClobberedLocs) {
+      TTracker->clobberMloc(LocVal.first, LocVal.second, MI.getIterator(), false);
+    }
+  }
+
   // Only produce a transfer of DBG_VALUE within a block where old LDV
   // would have. We might make use of the additional value tracking in some
   // other way, later.
   if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
     TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
                             MTracker->getRegMLoc(DestReg), MI.getIterator());
 
   // VarLocBasedImpl would quit tracking the old location after copying.
   if (EmulateOldLDV && SrcReg != DestReg)
     MTracker->defReg(SrcReg, CurBB, CurInst);
 
-  // Finally, the copy might have clobbered variables based on the destination
-  // register. Tell TTracker about it, in case a backup location exists.
-  if (TTracker) {
-    for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {
-      LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
-      TTracker->clobberMloc(ClobberedLoc, MI.getIterator(), false);
-    }
-  }
-
   return true;
 }
 
 /// Accumulate a mapping between each DILocalVariable fragment and other
 /// fragments of that DILocalVariable which overlap. This reduces work during
 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
 /// known-to-overlap fragments are present".
 /// \param MI A previously unprocessed debug instruction to analyze for

llvm/test/DebugInfo/X86/instr-ref-track-clobbers.mir

+# RUN: llc --run-pass=livedebugvalues %s -o - -experimental-debug-variable-locations | FileCheck %s --check-prefixes=CHECK
+
+# Test that we accurately track variables through transfers and clobbers.
+
+# In this test case, the value of "b" is found in $rax. From there it is moved
+# to $r15, $rax is killed, the value is moved back from $r15 into $rax again,
+# and then $r15 is killed. Throughout this, we should track "b" and end up with
+# DBG_VALUEs pointing to $rax, then $r15, then $rax again.
+
+# CHECK-LABEL: bb.0.entry:
+# CHECK: DBG_VALUE $rax,
+# CHECK: $r15 = MOV64rr
+
+## Technically it's correct to insert the DBG_VALUE for $r15 either immediately
+## after the move to $r15 or immediately after $rax is clobbered, but no later.
+# CHECK: DBG_VALUE $r15,
+# CHECK: $rax = LEA64r
+# CHECK: $rax = MOV64rr
+
+## Again, the DBG_VALUE can come either after the copy to $rax or the kill of
+## $r15, but no later.
+# CHECK: $r15 = LEA64r
+# CHECK: DBG_VALUE $rax,
+# CHECK: RET64
+
+--- |
+  ; ModuleID = 'test.cpp'
+  source_filename = "test.cpp"
+  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"
+  
+  ; Function Attrs: mustprogress nofree norecurse nosync nounwind readnone willreturn uwtable
+  define dso_local noundef i64 @_Z3fooxx(i64 noundef %a, i64 noundef %b) local_unnamed_addr !dbg !7 {
+  entry:
+    call void @llvm.dbg.value(metadata i64 %a, metadata !12, metadata !DIExpression()), !dbg !16
+    call void @llvm.dbg.value(metadata i64 %b, metadata !13, metadata !DIExpression()), !dbg !16
+    %add = add nsw i64 %b, %a, !dbg !17
+    call void @llvm.dbg.value(metadata i64 %add, metadata !14, metadata !DIExpression()), !dbg !16
+    %mul17 = sub i64 %a, %b, !dbg !18
+    %sub = mul i64 %add, %mul17, !dbg !18
+    call void @llvm.dbg.value(metadata i64 %sub, metadata !15, metadata !DIExpression()), !dbg !16
+    %add2 = add nsw i64 %sub, %add, !dbg !19
+    ret i64 %add2, !dbg !20
+  }
+  
+  ; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata)
+  
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!2, !3, !4, !5}
+  !llvm.ident = !{!6}
+  
+  !0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus_14, file: !1, producer: "clang version 15.0.0 (https://github.com/llvm/llvm-project.git 44673278e029d7a6f56c8a3177247026b831720f)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "test.cpp", directory: "/home/stozer/dev/llvm-project-build", checksumkind: CSK_MD5, checksum: "1e1c19354b0e967af705e204e8740d56")
+  !2 = !{i32 7, !"Dwarf Version", i32 5}
+  !3 = !{i32 2, !"Debug Info Version", i32 3}
+  !4 = !{i32 1, !"wchar_size", i32 4}
+  !5 = !{i32 7, !"uwtable", i32 2}
+  !6 = !{!"clang version 15.0.0 (https://github.com/llvm/llvm-project.git 44673278e029d7a6f56c8a3177247026b831720f)"}
+  !7 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooxx", scope: !1, file: !1, line: 1, type: !8, scopeLine: 1, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11)
+  !8 = !DISubroutineType(types: !9)
+  !9 = !{!10, !10, !10}
+  !10 = !DIBasicType(name: "long long", size: 64, encoding: DW_ATE_signed)
+  !11 = !{!12, !13, !14, !15}
+  !12 = !DILocalVariable(name: "a", arg: 1, scope: !7, file: !1, line: 1, type: !10)
+  !13 = !DILocalVariable(name: "b", arg: 2, scope: !7, file: !1, line: 1, type: !10)
+  !14 = !DILocalVariable(name: "c", scope: !7, file: !1, line: 2, type: !10)
+  !15 = !DILocalVariable(name: "d", scope: !7, file: !1, line: 3, type: !10)
+  !16 = !DILocation(line: 0, scope: !7)
+  !17 = !DILocation(line: 2, column: 19, scope: !7)
+  !18 = !DILocation(line: 3, column: 23, scope: !7)
+  !19 = !DILocation(line: 4, column: 12, scope: !7)
+  !20 = !DILocation(line: 4, column: 3, scope: !7)
+
+...
+---
+name:            _Z3fooxx
+alignment:       16
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+callsEHReturn:   false
+callsUnwindInit: false
+hasEHCatchret:   false
+hasEHScopes:     false
+hasEHFunclets:   false
+failsVerification: false
+tracksDebugUserValues: true
+registers:       []
+liveins:
+  - { reg: '$rdi', virtual-reg: '' }
+  - { reg: '$rsi', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    1
+  adjustsStack:    false
+  hasCalls:        false
+  stackProtector:  ''
+  functionContext: ''
+  maxCallFrameSize: 0
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  hasTailCall:     false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:
+- { id: 0, type: spill-slot, offset: -16, size: 8, alignment: 16, stack-id: default, 
+    callee-saved-register: '$r15', callee-saved-restored: true, debug-info-variable: '', 
+    debug-info-expression: '', debug-info-location: '' }
+stack:           []
+callSites:       []
+debugValueSubstitutions:
+  - { srcinst: 1, srcop: 0, dstinst: 3, dstop: 0, subreg: 0 }
+constants:       []
+machineFunctionInfo: {}
+body:             |
+  bb.0.entry:
+    liveins: $rdi, $rsi
+  
+    renamable $rax = LEA64r renamable $rsi, 1, renamable $rdi, 0, $noreg, debug-instr-number 3, debug-location !17
+    DBG_VALUE $rax, $noreg, !13, !DIExpression(), debug-location !17
+    $r15 = MOV64rr killed $rax, debug-location !16
+    renamable $rax = LEA64r renamable $rdi, 1, $noreg, 12, $noreg, debug-location !16
+    $rax = MOV64rr killed $r15, debug-location !16
+    renamable $r15 = LEA64r renamable $rdi, 1, $noreg, 12, $noreg, debug-location !16
+    RET64 $r15, debug-location !20
+
+...