[LiveDebugValues][InstrRef][1/2] Try harder to recover clobbered variable locations

[jmorse]

Summary

Hi,

Here's a patch that improves variable location PC-range coverage when using the instruction-referencing LiveDebugValues implementation. I've mostly been focusing on ensuring there are no regressions in variable availability (i.e., the number of variables that have at least one location), and wasn't really looking at the 'PC Ranges covered' output of llvm-locstats. This patch rectifies some of that to give a modest improvement in covered PC ranges -- however the real benefits come with entry values (see next patch, an additional 5% PC ranges).

In various circumstances, when we clobber a register there may be alternative locations that the value is live in. The classic example would be a value loaded from the stack, and then clobbered: the value is still available on the stack. InstrRefBasedLDV was coping with this at block starts where it's forced to pick a location; however it wasn't searching for alternative locations when values were clobbered. This patch notifies the "TransferTracker" object when clobbers occur, and it's able to find alternatives and issue DBG_VALUEs for the that location. See: the added test.

More generally, it's pretty clear that this should be done by something like DbgEntityHistoryCalculator instead, which would also be able to avoid redundant location transfers. But that's an improvement for another day.

Here's the output of llvm-locstats when buildling clang-3.4 before and after this patch, when forcing the use of InstrRefBasedLV, for which I've added an -mllvm switch.

Before:

=================================================
    cov%           samples         percentage(~)
-------------------------------------------------
  0%               872495               26%
  (0%,10%)          47486                1%
  [10%,20%)         50330                1%
  [20%,30%)         57127                1%
  [30%,40%)         48881                1%
  [40%,50%)         46630                1%
  [50%,60%)         59643                1%
  [60%,70%)         57581                1%
  [70%,80%)         67858                2%
  [80%,90%)         77362                2%
  [90%,100%)       100012                2%
  100%            1866414               55%
=================================================
-the number of debug variables processed: 3351819
-PC ranges covered: 56%
-------------------------------------------------
-total availability: 60%
=================================================

After:

=================================================
    cov%           samples         percentage(~)
-------------------------------------------------
  0%               872508               26%
  (0%,10%)          44994                1%
  [10%,20%)         49960                1%
  [20%,30%)         56512                1%
  [30%,40%)         48070                1%
  [40%,50%)         46135                1%
  [50%,60%)         58738                1%
  [60%,70%)         55552                1%
  [70%,80%)         65360                1%
  [80%,90%)         74530                2%
  [90%,100%)        97362                2%
  100%            1882113               56%
=================================================
-the number of debug variables processed: 3351834
-PC ranges covered: 56%
-------------------------------------------------
-total availability: 60%
=================================================

So that's roughly 16,000 more variable locations in the 100% bucket, and other variable locations have shifted up a few buckets too.

This patch isn't based on any of the other instruction referencing work, only the LiveDebugValues implementation in tree. After a few months of prodding it, it could definitely do with a refactor, but I'd like to do that from a position where it's working well. Given that it's "officially" in an experimental state, it's not clear if it needs "full" review, I'll probably take my lead from the child patch that I'll upload in a moment.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1225

this seems to be always called with false? Does that mean the second half is untested?

[jmorse]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1225

There's a call to clobberMloc with the default argument (true) on lines (pre) 1735 / (post) 1798 of this patch. The background to this is D66941, spill slots can be merged, and DbgEntityHistoryCalculator doesn't terminate any variable locations when the stack is written to, so LiveDebugValues has to explicitly terminate (with DBG_VALUE $noreg) any variable locations clobbered by stack writes. (Eww).

The test for D66941 should stimulate the code path through line 1798, as it needs an explicit DBG_VALUE $noreg to be generated by LiveDebugValues.

(This is another thing that would fixed by refactoring this responsibility into / with DbgEntityHistoryCalculator; I'm deep in the tar pit here, horray).

[jmorse]

Rebase onto existing patches to make this applicable through arc; one line marked "future work" in livedebugvalues_instrref_tolocs.mir now has a variable location, as this is the future work that implements it.

[djtodoro]

Super nit inline.

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1924

, ==> .

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

1225

Nit: make_undef ==> MakeUndef

llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp

if (It == ActiveVLocs.end()) {
       ActiveVLocs.insert(
           std::make_pair(Var, LocAndProperties{NewLoc, Properties}));
     } else {
       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) {
-    assert(MTracker->isSpill(MLoc));
+  /// Account for a location \p mloc being clobbered. Examine the variable
+  /// locations that will be terminated: and try to recover them by using
+  /// another location. Optionally, given \p make_undef, emit a DBG_VALUE to
+  /// explicitly terminate a location if it can't be recovered.
+  void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,
+                   bool make_undef = true) {
     auto ActiveMLocIt = ActiveMLocs.find(MLoc);
     if (ActiveMLocIt == ActiveMLocs.end())
       return;
 
+    // What was the old variable value?
+    ValueIDNum OldValue = VarLocs[MLoc.asU64()];
     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;
+
+    // If there is no location, and we weren't asked to make the variable
+    // explicitly undef, then stop here.
+    if (!NewLoc && !make_undef)
+      return;
+
+    // Examine all the variables based on this location.
+    DenseSet<DebugVariable> NewMLocs;
     for (auto &Var : ActiveMLocIt->second) {
       auto ActiveVLocIt = ActiveVLocs.find(Var);
-      // Create an undef. We can't feed in a nullptr DIExpression alas,
-      // so use the variables last expression. Pass None as the location.
+      // Re-state the variable location: if there's no replacement then NewLoc
+      // is None and a $noreg DBG_VALUE will be created. Otherwise, a DBG_VALUE
+      // identifying the alternative location will be emitted.
       const DIExpression *Expr = ActiveVLocIt->second.Properties.DIExpr;
       DbgValueProperties Properties(Expr, false);
-      PendingDbgValues.push_back(MTracker->emitLoc(None, Var, Properties));
+      PendingDbgValues.push_back(MTracker->emitLoc(NewLoc, Var, Properties));
+
+      // Update machine locations <=> variable locations maps. Defer updating
+      // ActiveMLocs to avoid invalidaing the ActiveMLocIt iterator.
+      if (!NewLoc) {
         ActiveVLocs.erase(ActiveVLocIt);
+      } else {
+        ActiveVLocIt->second.Loc = *NewLoc;
+        NewMLocs.insert(Var);
+      }
     }
+
+    // Commit any deferred ActiveMLoc changes.
+    if (!NewMLocs.empty())
+      for (auto &Var : NewMLocs)
+        ActiveMLocs[*NewLoc].insert(Var);
+
+    // We lazily track what locations have which values; if we've found a new
+    // location for the clobbered value, remember it.
+    if (NewLoc)
+      VarLocs[NewLoc->asU64()] = OldValue;
+
     flushDbgValues(Pos, nullptr);
 
     ActiveMLocIt->second.clear();
   }
 
   /// Transfer variables based on \p Src to be based on \p Dst. This handles
   /// both register copies as well as spills and restores. Creates DBG_VALUEs
   /// describing the movement.
void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {
   }
 
   // Tell MLocTracker about all definitions, of regmasks and otherwise.
   for (uint32_t DeadReg : DeadRegs)
     MTracker->defReg(DeadReg, CurBB, CurInst);
 
   for (auto *MO : RegMaskPtrs)
     MTracker->writeRegMask(MO, CurBB, CurInst);
+
+  if (!TTracker)
+    return;
+
+  // When committing variable values to locations: tell transfer tracker that
+  // we've clobbered things. It may be able to recover the variable from a
+  // different location.
+
+  // Inform TTracker about any direct clobbers,
+  for (uint32_t DeadReg : DeadRegs) {
+    LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
+    TTracker->clobberMloc(Loc, MI.getIterator(), false);
+  }
+
+  // Look for any clobbers performed by a register mask. Only test locations
+  // that are actually being tracked.
+  for (auto L : MTracker->locations()) {
+    // Stack locations can't be clobbered by regmasks.
+    if (MTracker->isSpill(L.Idx))
+      continue;
+
+    Register Reg = MTracker->LocIdxToLocID[L.Idx];
+    for (auto *MO : RegMaskPtrs)
+      if (MO->clobbersPhysReg(Reg))
+        TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
+  }
 }
 
 void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {
   ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
 
   MTracker->setReg(DstRegNum, SrcValue);
 
   // In all circumstances, re-def the super registers. It's definitely a new
bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {
   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_VALUE instruction to analyze for

llvm/lib/CodeGen/LiveDebugValues/LiveDebugValues.cpp

 //===- LiveDebugValues.cpp - Tracking Debug Value MIs ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "LiveDebugValues.h"
 
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Target/TargetMachine.h"
 
 /// \file LiveDebugValues.cpp
 ///
 /// The LiveDebugValues pass extends the range of variable locations
 /// (specified by DBG_VALUE instructions) from single blocks to successors
 /// and any other code locations where the variable location is valid.
 /// There are currently two implementations: the "VarLoc" implementation
 /// explicitly tracks the location of a variable, while the "InstrRef"
 /// implementation tracks the values defined by instructions through locations.
 ///
 /// This file implements neither; it merely registers the pass, allows the
 /// user to pick which implementation will be used to propagate variable
 /// locations.
 
 #define DEBUG_TYPE "livedebugvalues"
 
 using namespace llvm;
 
+static cl::opt<bool>
+    ForceInstrRefLDV("force-instr-ref-livedebugvalues", cl::Hidden,
+                     cl::desc("Use instruction-ref based LiveDebugValues with "
+                              "normal DBG_VALUE inputs"),
+                     cl::init(false));
+
 /// Generic LiveDebugValues pass. Calls through to VarLocBasedLDV or
 /// InstrRefBasedLDV to perform location propagation, via the LDVImpl
 /// base class.
 class LiveDebugValues : public MachineFunctionPass {
 public:
   static char ID;
 
   LiveDebugValues();
if (!TheImpl) {
     TPC = getAnalysisIfAvailable<TargetPassConfig>();
 
     bool InstrRefBased = false;
     if (TPC) {
       auto &TM = TPC->getTM<TargetMachine>();
       InstrRefBased = TM.Options.ValueTrackingVariableLocations;
     }
 
+    // Allow the user to force selection of InstrRef LDV.
+    InstrRefBased |= ForceInstrRefLDV;
+
     if (InstrRefBased)
       TheImpl = llvm::makeInstrRefBasedLiveDebugValues();
     else
       TheImpl = llvm::makeVarLocBasedLiveDebugValues();
   }
 
   return TheImpl->ExtendRanges(MF, TPC);
 }

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

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.
+    ; CHECK: DBG_VALUE $rbx, $noreg
 
     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

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

+--- |
+  ; RUN: llc %s -march=x86-64 -run-pass=livedebugvalues -o - -force-instr-ref-livedebugvalues=1 -emulate-old-livedebugvalues=0 | FileCheck %s -implicit-check-not=DBG_VALUE
+
+  ;; When using instruction referencing LiveDebugValues, when a register gets
+  ;; clobbered, we should transfer variable locations to backup locations, if
+  ;; one is available.
+  ;; I've written this test in terms of DBG_VALUEs rather than DBG_INSTR_REFs
+  ;; as this is purely a LiveDebugValues feature, and should work without the
+  ;; need to use any other instructoin referencing work.
+
+  declare i32 @use() local_unnamed_addr;
+
+  define i32 @_Z8bb_to_bb() local_unnamed_addr !dbg !12 {
+  entry:
+    br label %bb1, !dbg !17
+  bb1:
+    br label %bb2, !dbg !17
+  bb2:
+    br label %bb3, !dbg !17
+  bb3:
+    br label %bb3, !dbg !17
+  bb4:
+    br label %bb3, !dbg !17
+  bb5:
+    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
+stack:
+  - { id: 0, type: spill-slot, offset: -12, size: 4, alignment: 4 }
+body:  |
+  bb.0.entry:
+    $eax = MOV32ri 0, debug-location !17
+    $eax = COPY $ebx
+    DBG_VALUE $eax, $noreg, !16, !DIExpression(), debug-location !17
+    ;; Over-write eax, we should recover its location as being in ebx.
+    $eax = MOV32ri 0, debug-location !17
+
+    ; CHECK:      DBG_VALUE $eax
+    ; CHECK-NEXT: $eax = MOV32ri 0
+    ; CHECK-NEXT: DBG_VALUE $ebx
+
+    ;; The same should occur for spills.
+    $ebx = MOV32ri 2, debug-location !17
+    MOV32mr $rsp, 1, _, -12, _, killed $ebx :: (store 4 into %stack.0)
+    DBG_VALUE $ebx, $noreg, !16, !DIExpression(), debug-location !17
+    $ebx = MOV32ri 0, debug-location !17
+
+    ; CHECK-NEXT: $ebx = MOV32ri 2
+    ; CHECK-NEXT: MOV32mr $rsp
+    ; CHECK-NEXT: DBG_VALUE $ebx
+    ; CHECK-NEXT: $ebx = MOV32ri
+    ; CHECK-NEXT: DBG_VALUE $rsp
+
+    ;; Now test copies and register masks.
+    $eax = COPY $ebx
+    DBG_VALUE $ebx, $noreg, !16, !DIExpression(), debug-location !17
+    ;; Overwrite ebx with a copy.
+    $ecx = MOV32ri 1, debug-location !17
+    $ebx = COPY $ecx
+
+    ; CHECK:      DBG_VALUE $ebx
+    ; CHECK-NEXT: $ecx = MOV32ri
+    ; CHECK-NEXT: $ebx = COPY
+    ; CHECK-NEXT: DBG_VALUE $eax
+
+    ;; Similarly, with a register mask
+    $ebx = COPY $eax
+    CALL64pcrel32 @use, csr_64, implicit $rsp, implicit $edi, implicit-def $rsp, debug-location !17
+
+    ; CHECK-NEXT: $ebx = COPY $eax
+    ; CHECK-NEXT: CALL64pcrel32
+    ; CHECK-NEXT: DBG_VALUE $ebx
+
+    RETQ $eax, debug-location !17
+...