Improvements to call site register worklist

[dstenb]

Summary

This fixes PR44118. For cases where we have a chain like this:

R8 = R1 (entry value)
R0 = R8
call @foo R0

the code that emits call site entries using entry values would not
follow that chain, instead emitting a call site entry with R8 as
location rather than R0. Such a case was discovered when originally
adding dbgcall-site-orr-moves.mir. This patch fixes that issue. This is
done by changing the ForwardedRegWorklist set to a map in which the
worklist registers always map to the parameter registers that they
describe.

Another thing this patch fixes is that worklist registers now can
describe more than one parameter register at a time. Such a case
occurred in dbgcall-site-interpretation.mir, resulting in a call site
entry not being emitted for one of the parameters.

[djtodoro]

Nice! Thanks!

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

638

Can we describe the usage of it with a comment?

665

The register worklist ?

669

auto Reg

693

Good NFC, thanks.

llvm/test/DebugInfo/MIR/X86/dbgcall-site-reg-shuffle.mir

50

I believe you don't need all the attributes.

[dstenb]

Sorry, I now realized that the RegsToKeep handling is not sufficient, since it will not correctly handle cases where we have a mix of parameter registers that should be discarded, and those that were added in this iteration, which we should keep.

This patch will for example not correctly handle the following example on a made-up architecture:

$r1 = mv-imm 123
$r0, $r1 = mv_registers $r1, <register that can't be described>
call @foo, $r0, $r1

For such code, this patch will produce call site entries for both $r0 and $r1 described by 123, but we should only emit a call site entry for $r0.

That is quite a silly code example, but it seems good to get such a thing right from the start. I'll upload an updated patch.

[dstenb]

Fix the RegsToKeep flaw I mentioned in a previous comment. I added a new test, dbgcall-site-partial-describe.mir, as a reproducer for that.

Address comments.

[dstenb]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

665

"The worklist register" is perhaps a bit poorly phrased, or awkward to read. I meant "The register in the worklist". Perhaps it should just say "ParamFwdReg"?

[vsk]

This is looking really nice. Thanks!

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

574

I think this needs to be a MapVector. Otherwise, the iteration order in getForwardingRegsDefinedByMI will be non-deterministic. I.e. the insertion order into the Defs SmallSetVector will not be deterministic.

623

Consider adding assert(find(I.first->second, ParamReg) == nullptr && "Same parameter described twice by forwarding reg") before pushing ParamReg?

llvm/test/DebugInfo/MIR/X86/dbgcall-site-partial-describe.mir

76 ↗

(On Diff #239899)

I think the first CHECK-NOT for DW_TAG_GNU_call_site_parameter can safely be deleted. Or you could pass -implicit-check-not=DW_TAG_GNU_call_site_parameter to FileCheck and get rid of both CHECK-NOT's.

llvm/test/DebugInfo/MIR/X86/dbgcall-site-reg-shuffle.mir

91

Nice!

[djtodoro]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

597

Cool :)

[dstenb]

Address review comments. Reword a test description slightly.

[dstenb]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

574

Good catch! As I've understood it the iteration order for a non-pointer type holding DenseMap is deterministic for a single binary? However, I guess it's not free from implementation-defined behavior (e.g. the hash function is dependent on the width of unsigned), so I guess there's no guarantee that the iteration order is deterministic between binaries built with different compilers. I made it a MapVector.

llvm/test/DebugInfo/MIR/X86/dbgcall-site-partial-describe.mir

76 ↗

(On Diff #239899)

Oh, right!

I switched to implicit-check-not in both tests.

[dstenb]

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

574

By the way, the DWARF5 standard appears to mandate that the call site parameter entries occur in the same order as they do in the source, which is currently not the case for LLVM. I created a Bugzilla ticket for that: https://bugs.llvm.org/show_bug.cgi?id=44653.

[vsk]

Lgtm!

llvm/lib/CodeGen/AsmPrinter/DwarfDebug.cpp

static void collectCallSiteParameters(const MachineInstr *CallMI,
   auto *MBB = CallMI->getParent();
   const auto &TRI = MF->getSubtarget().getRegisterInfo();
   const auto &TII = MF->getSubtarget().getInstrInfo();
   const auto &TLI = MF->getSubtarget().getTargetLowering();
 
   // Skip the call instruction.
   auto I = std::next(CallMI->getReverseIterator());
 
-  DenseSet<unsigned> ForwardedRegWorklist;
+  // Worklist that maps the current registers to the parameter registers that
+  // they describe.
+  DenseMap<unsigned, SmallVector<unsigned, 2>> ForwardedRegWorklist;
+
   // Add all the forwarding registers into the ForwardedRegWorklist.
   for (auto ArgReg : CallFwdRegsInfo->second) {
-    bool InsertedReg = ForwardedRegWorklist.insert(ArgReg.Reg).second;
+    bool InsertedReg =
+        ForwardedRegWorklist.insert({ArgReg.Reg, {ArgReg.Reg}}).second;
     assert(InsertedReg && "Single register used to forward two arguments?");
     (void)InsertedReg;
   }
 
   // We erase, from the ForwardedRegWorklist, those forwarding registers for
   // which we successfully describe a loaded value (by using
   // the describeLoadedValue()). For those remaining arguments in the working
   // list, for which we do not describe a loaded value by
   // the describeLoadedValue(), we try to generate an entry value expression
   // for their call site value description, if the call is within the entry MBB.
-  // The RegsForEntryValues maps a forwarding register into the register holding
-  // the entry value.
   // TODO: Handle situations when call site parameter value can be described
   // as the entry value within basic blocks other than the first one.
   bool ShouldTryEmitEntryVals = MBB->getIterator() == MF->begin();
-  DenseMap<unsigned, unsigned> RegsForEntryValues;
 
   // If the MI is an instruction defining one or more parameters' forwarding
   // registers, add those defines.
   auto getForwardingRegsDefinedByMI = [&](const MachineInstr &MI,
                                           SmallSetVector<unsigned, 4> &Defs) {
     if (MI.isDebugInstr())
       return;
 
     for (const MachineOperand &MO : MI.operands()) {
       if (MO.isReg() && MO.isDef() &&
           Register::isPhysicalRegister(MO.getReg())) {
         for (auto FwdReg : ForwardedRegWorklist)
-          if (TRI->regsOverlap(FwdReg, MO.getReg()))
-            Defs.insert(FwdReg);
+          if (TRI->regsOverlap(FwdReg.first, MO.getReg()))
+            Defs.insert(FwdReg.first);
       }
     }
   };
 
-  auto finishCallSiteParam = [&](DbgValueLoc DbgLocVal, unsigned Reg) {
-    unsigned FwdReg = Reg;
-    if (ShouldTryEmitEntryVals) {
-      auto EntryValReg = RegsForEntryValues.find(Reg);
-      if (EntryValReg != RegsForEntryValues.end())
-        FwdReg = EntryValReg->second;
-    }
-
+  auto finishCallSiteParams = [&](DbgValueLoc DbgLocVal,
+                                  ArrayRef<unsigned> ParamRegs) {
+    for (unsigned FwdReg : ParamRegs) {
       DbgCallSiteParam CSParm(FwdReg, DbgLocVal);
       Params.push_back(CSParm);
       ++NumCSParams;
+    }
   };
 
   // Search for a loading value in forwarding registers.
   for (; I != MBB->rend(); ++I) {
     // Skip bundle headers.
     if (I->isBundle())
       continue;
 
     // If the next instruction is a call we can not interpret parameter's
     // forwarding registers or we finished the interpretation of all parameters.
     if (I->isCall())
       return;
 
     if (ForwardedRegWorklist.empty())
       return;
 
     SmallSetVector<unsigned, 4> FwdRegDefs;
     getForwardingRegsDefinedByMI(*I, FwdRegDefs);
     if (FwdRegDefs.empty())
       continue;
 
-    // If the MI clobbers more then one forwarding register we must remove
-    // all of them from the working list.
-    for (auto Reg : FwdRegDefs)
-      ForwardedRegWorklist.erase(Reg);
-
+    SmallSet<unsigned, 2> RegsToKeep;
     for (auto ParamFwdReg : FwdRegDefs) {
       if (auto ParamValue = TII->describeLoadedValue(*I, ParamFwdReg)) {
         if (ParamValue->first.isImm()) {
           int64_t Val = ParamValue->first.getImm();
           DbgValueLoc DbgLocVal(ParamValue->second, Val);
-          finishCallSiteParam(DbgLocVal, ParamFwdReg);
+          finishCallSiteParams(DbgLocVal, ForwardedRegWorklist[ParamFwdReg]);
         } else if (ParamValue->first.isReg()) {
           Register RegLoc = ParamValue->first.getReg();
           // TODO: For now, there is no use of describing the value loaded into the
           //       register that is also the source registers (e.g. $r0 = add $r0, x).
           if (ParamFwdReg == RegLoc)
             continue;
 
           unsigned SP = TLI->getStackPointerRegisterToSaveRestore();
           Register FP = TRI->getFrameRegister(*MF);
           bool IsSPorFP = (RegLoc == SP) || (RegLoc == FP);
           if (TRI->isCalleeSavedPhysReg(RegLoc, *MF) || IsSPorFP) {
             DbgValueLoc DbgLocVal(ParamValue->second,
                                   MachineLocation(RegLoc,
                                                   /*IsIndirect=*/IsSPorFP));
-            finishCallSiteParam(DbgLocVal, ParamFwdReg);
+            finishCallSiteParams(DbgLocVal, ForwardedRegWorklist[ParamFwdReg]);
           // TODO: Add support for entry value plus an expression.
           } else if (ShouldTryEmitEntryVals &&
                      ParamValue->second->getNumElements() == 0) {
-            ForwardedRegWorklist.insert(RegLoc);
-            RegsForEntryValues[RegLoc] = ParamFwdReg;
+            assert(RegLoc != ParamFwdReg &&
+                   "Can't handle a register that is described by itself");
+            // The worklist register was described by a non-callee saved
+            // register. Add the new register to the worklist if not already
+            // present, and move over all parameter registers to that.
+            auto I = ForwardedRegWorklist.insert({RegLoc, {}});
+            for (auto R : ForwardedRegWorklist[ParamFwdReg])
+              I.first->second.push_back(R);
+
+            // Do not remove the new register from the worklist.
+            RegsToKeep.insert(RegLoc);
           }
         }
       }
     }
+
+    // Remove all registers that we were not able to describe, or that have
+    // been replaced by other registers in the worklist.
+    for (auto ParamFwdReg : FwdRegDefs)
+      if (!RegsToKeep.count(ParamFwdReg))
+        ForwardedRegWorklist.erase(ParamFwdReg);
   }
 
   // Emit the call site parameter's value as an entry value.
   if (ShouldTryEmitEntryVals) {
     // Create an expression where the register's entry value is used.
     DIExpression *EntryExpr = DIExpression::get(
         MF->getFunction().getContext(), {dwarf::DW_OP_LLVM_entry_value, 1});
     for (auto RegEntry : ForwardedRegWorklist) {
-      unsigned FwdReg = RegEntry;
-      auto EntryValReg = RegsForEntryValues.find(RegEntry);
-        if (EntryValReg != RegsForEntryValues.end())
-          FwdReg = EntryValReg->second;
-
-      DbgValueLoc DbgLocVal(EntryExpr, MachineLocation(RegEntry));
-      DbgCallSiteParam CSParm(FwdReg, DbgLocVal);
-      Params.push_back(CSParm);
-      ++NumCSParams;
+      DbgValueLoc DbgLocVal(EntryExpr, MachineLocation(RegEntry.first));
+      finishCallSiteParams(DbgLocVal, RegEntry.second);
     }
   }
 }
 
 void DwarfDebug::constructCallSiteEntryDIEs(const DISubprogram &SP,
                                             DwarfCompileUnit &CU, DIE &ScopeDIE,
                                             const MachineFunction &MF) {
   // Add a call site-related attribute (DWARF5, Sec. 3.3.1.3). Do this only if

llvm/test/DebugInfo/MIR/AArch64/dbgcall-site-orr-moves.mir

bb.0.entry:
     RET undef $lr, implicit killed $w0, debug-location !44
 
 ...
 
 # CHECK: DW_TAG_GNU_call_site
 # CHECK-NEXT: DW_AT_abstract_origin ({{.*}} "call_int_int")
 #
 # CHECK: DW_TAG_GNU_call_site_parameter
-# FIXME: The DW_AT_location attribute should actually refer to W0! See PR44118.
-# CHECK-NEXT: DW_AT_location      (DW_OP_reg8 W8)
+# CHECK-NEXT: DW_AT_location      (DW_OP_reg0 W0)
 # CHECK-NEXT: DW_AT_GNU_call_site_value   (DW_OP_GNU_entry_value(DW_OP_reg1 W1))

llvm/test/DebugInfo/MIR/X86/dbgcall-site-interpretation.mir

 # RUN: llc -debug-entry-values -start-after=machineverifier -filetype=obj %s -o -| llvm-dwarfdump -| FileCheck %s
 #
 # CHECK:        DW_TAG_GNU_call_site
 # CHECK-NEXT:     DW_AT_abstract_origin {{.*}} "foo"
 # CHECK-NEXT:     DW_AT_low_pc
 # CHECK-EMPTY:
 # CHECK-NEXT:     DW_TAG_GNU_call_site_parameter
 # CHECK-NEXT:       DW_AT_location      (DW_OP_reg2 RCX)
 # CHECK-NEXT:       DW_AT_GNU_call_site_value   (DW_OP_breg14 R14+0)
 # CHECK-EMPTY: 
 # CHECK-NEXT:     DW_TAG_GNU_call_site_parameter
 # CHECK-NEXT:       DW_AT_location      (DW_OP_reg1 RDX)
 # CHECK-NEXT:       DW_AT_GNU_call_site_value   (DW_OP_fbreg +8)
 # CHECK-EMPTY: 
 # CHECK-NEXT:     DW_TAG_GNU_call_site_parameter
+# CHECK-NEXT:       DW_AT_location      (DW_OP_reg4 RSI)
+# CHECK-NEXT:       DW_AT_GNU_call_site_value   (DW_OP_GNU_entry_value(DW_OP_reg4 RSI))
+# CHECK-EMPTY: 
+# CHECK-NEXT:     DW_TAG_GNU_call_site_parameter
 # CHECK-NEXT:       DW_AT_location      (DW_OP_reg5 RDI)
 # CHECK-NEXT:       DW_AT_GNU_call_site_value   (DW_OP_GNU_entry_value(DW_OP_reg4 RSI))
 # CHECK-EMPTY:
 # CHECK:        DW_TAG_GNU_call_site
 # CHECK-NEXT:     DW_AT_abstract_origin {{.*}}"foo"
 # CHECK-NEXT:     DW_AT_low_pc
 # CHECK-EMPTY:
 # CHECK-NEXT:     DW_TAG_GNU_call_site_parameter

llvm/test/DebugInfo/MIR/X86/dbgcall-site-reg-shuffle.mir

+# RUN: llc -debug-entry-values -start-before=livedebugvalues -filetype=obj -o - %s | llvm-dwarfdump - | FileCheck %s
+
+--- |
+  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: nounwind uwtable
+  define void @move_around_args(i32 %a) #0 !dbg !12 {
+  entry:
+    call void @call2(i32 123, i32 %a), !dbg !18
+    ret void, !dbg !19
+  }
+
+  declare !dbg !4 dso_local void @call2(i32, i32)
+
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+  attributes #0 = { nounwind uwtable }
+  attributes #1 = { nounwind readnone speculatable willreturn }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!8, !9, !10}
+  !llvm.ident = !{!11}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 11.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !3, splitDebugInlining: false, nameTableKind: None)
+  !1 = !DIFile(filename: "worklist.c", directory: "/")
+  !2 = !{}
+  !3 = !{!4}
+  !4 = !DISubprogram(name: "call2", scope: !1, file: !1, line: 1, type: !5, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+  !5 = !DISubroutineType(types: !6)
+  !6 = !{null, !7, !7}
+  !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !8 = !{i32 7, !"Dwarf Version", i32 4}
+  !9 = !{i32 2, !"Debug Info Version", i32 3}
+  !10 = !{i32 1, !"wchar_size", i32 4}
+  !11 = !{!"clang version 11.0.0"}
+  !12 = distinct !DISubprogram(name: "move_around_args", scope: !1, file: !1, line: 3, type: !13, scopeLine: 3, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !15)
+  !13 = !DISubroutineType(types: !14)
+  !14 = !{null, !7}
+  !15 = !{!16}
+  !16 = !DILocalVariable(name: "a", arg: 1, scope: !12, file: !1, line: 3, type: !7)
+  !17 = !DILocation(line: 0, scope: !12)
+  !18 = !DILocation(line: 4, scope: !12)
+  !19 = !DILocation(line: 5, scope: !12)
+
+...
+---
+name:            move_around_args
+tracksRegLiveness: true
+liveins:
+  - { reg: '$edi' }
+frameInfo:
+  stackSize:       8
+  offsetAdjustment: -8
+  maxAlignment:    1
+  adjustsStack:    true
+  hasCalls:        true
+  maxCallFrameSize: 0
+callSites:
+  - { bb: 0, offset: 12, fwdArgRegs:
+      - { arg: 0, reg: '$edi' }
+      - { arg: 1, reg: '$esi' } }
+body:             |
+  bb.0.entry:
+    liveins: $edi
+
+    frame-setup PUSH64r undef $rax, implicit-def $rsp, implicit $rsp
+    CFI_INSTRUCTION def_cfa_offset 16
+    $esi = MOV32ri 123
+
+    ; Move the values around between different registers.
+
+    $edx = MOV32rr $edi
+
+    $edi = MOV32rr $esi
+    $esi = MOV32rr $edx
+
+    $edx = MOV32rr $edi
+    $eax = MOV32rr $esi
+
+    $esi = MOV32rr $edx
+    $edx = MOV32rr $eax
+
+    $edi = MOV32rr $esi
+    $esi = MOV32rr $edx
+
+    CALL64pcrel32 @call2, csr_64, implicit $rsp, implicit $ssp, implicit $edi, implicit $esi, implicit-def $rsp, implicit-def $ssp, debug-location !18
+    $rax = frame-destroy POP64r implicit-def $rsp, implicit $rsp, debug-location !19
+    CFI_INSTRUCTION def_cfa_offset 8, debug-location !19
+    RETQ debug-location !19
+
+...
+
+# Verify that we emit correct call site parameter entries even after moving
+# around the call site values between different registers.
+
+# CHECK-NOT: DW_TAG_GNU_call_site_parameter
+# CHECK: DW_TAG_GNU_call_site_parameter
+# CHECK-NEXT: DW_AT_location  (DW_OP_reg5 RDI)
+# CHECK-NEXT: DW_AT_GNU_call_site_value (DW_OP_constu 0x7b)
+# CHECK-EMPTY:
+# CHECK-NEXT: DW_TAG_GNU_call_site_parameter
+# CHECK-NEXT: DW_AT_location  (DW_OP_reg4 RSI)
+# CHECK-NEXT: DW_AT_GNU_call_site_value (DW_OP_GNU_entry_value(DW_OP_reg5 RDI))
+# CHECK-NOT: DW_TAG_GNU_call_site_parameter