[DebugInfo] Avoid creating entry values for clobbered registers

[dstenb]

Summary

Entry values are considered for parameters that have register-described
DBG_VALUEs in the entry block (along with other conditions).

If a parameter's value has been propagated from the caller to the
callee, then the parameter's DBG_VALUE in the entry block may be
described using a register defined by some instruction, and entry values
should not be emitted for the parameter, which can currently occur.
One such case was seen in the attached test case, in which the second
parameter, which is described by a redefinition of the first parameter's
register, would incorrectly get an entry value using the first
parameter's register. This commit intends to solve such cases by keeping
track of register defines, and ignoring DBG_VALUEs in the entry block
that are described by such registers.

In a RelWithDebInfo build of clang-8, the average size of the set was
27, and in a RelWithDebInfo+ASan build it was 30.

[djtodoro]

@dstenb Thanks!

llvm/lib/CodeGen/LiveDebugValues.cpp

1326

Can we put this in a helper?

1331

Maybe all of this can go in a helper as well. I think that should simplify the code here.

[dstenb]

Address review comments.

[dstenb]

llvm/lib/CodeGen/LiveDebugValues.cpp

1331

Yes, good idea! I put that refactoring in a parent patch.

[aprantl]

llvm/lib/CodeGen/LiveDebugValues.cpp

1253

I assume you checked that such a helper doesn't already exist?

1353

I'm assuming this is IsEntryValueCandidate()? There's no context..
So we're saying any DBG_VALUE using a register that has been defined in the entry block is not an entry value candidate?

[dstenb]

Rebase (IsEntryValueCandidate function moved to a separate function), and include full diff context.

[djtodoro]

llvm/lib/CodeGen/LiveDebugValues.cpp

1281

const DefinedRegsSet&?

1370

Perhaps we can add a comment here describing what is the purpose of adding this.

[dstenb]

llvm/lib/CodeGen/LiveDebugValues.cpp

1253

Yes, I have not been able to find any functions that collects the defs in this way.

1353

I'm assuming this is IsEntryValueCandidate()? There's no context..

Sorry about not including the context! I have updated the diff.

So we're saying any DBG_VALUE using a register that has been defined in the entry block is not an entry value candidate?

Yes, it will check any DBG_VALUE in the entry block. I think that "have we seen a preceding DBG_VALUE for this parameter which wasn't a viable candidate?" is a condition that is missing here (before this patch also), and in such cases we should not emit entry values for the parameter, Otherwise, I guess that we might emit incorrect entry values in cases like this:

void func(int foo, int bar);

entry:
DBG_VALUE $rdi, $noreg, "foo"
DBG_VALUE [some value other than a live-in register], "bar"
[instructions that do not clobber $rdi]
DBG_VALUE $rdi, $noreg, "bar"

I don't think such cases can happen now due to the isNotModified() guard, but as we're moving away from that, it's something to consider.

As a side note, I think it would be neat if there was some side-table mapping parameters to their corresponding registers, in the same as is done for the call sites with the callSites metadata, so that we would not have to find entry values by inspecting the entry block's debug values.

[vsk]

Thanks @dstenb. I have a mix of comments on this one: some minor nits & some more architectural questions which I'd appreciate your input on. That said I don't want to distract from landing this asap and fixing the correctness issue.

llvm/lib/CodeGen/LiveDebugValues.cpp

1304

Does this intentionally allow non-register uses (like, DBG_VALUE <constant>, ...)?

1353

Would the side-table mapping parameters to their corresponding registers have to keep track of movements (say, if parameter 1 was moved from %rdi to %r15)?

1378–1383

Perhaps this is out of scope for the current patch, but: Is it possible to find no candidate entry values in the entry block, but to miss candidates in subsequent blocks? Example:

define void @callee(i32 %param1) {
entry:
  ; No use of %param1 in entry block: does this imply no entry value?
  br label %succ
succ:
  ; Last use of %param1. We can assume it is dead after the call.
  call void @use(i32 %param1) 
  br label %succ2
succ2:
  ; No entry value location emitted for %param1?
  ret void
}

llvm/test/DebugInfo/MIR/ARM/dbgcall-site-propagated-value.mir

147

Nothing to do with this patch, but: Is it expected that "p1" moves from r0 to r4? I guess I'd expect regalloc to keep "p1" in r0, then materialize "p2" in the ABI-specified register for the second argument (r1?). Might be worth a separate bug.

150

It might aid readability to add a comment here explaining that the movi + orrri pair materializes 0xabcd in the callee (& that the adjacent DBG_VALUE for !34 defines "p2").

[vsk]

llvm/lib/CodeGen/LiveDebugValues.cpp

1304

I totally misread the condition, please ignore.

[dstenb]

Address review comments.

[dstenb]

llvm/lib/CodeGen/LiveDebugValues.cpp

1281

Yes, thanks!

1353

This is just an idea that I threw out without giving it a lot of thought, but I imagined that the side table would only specify in which register(s) each parameter reside in at function entry, and we'd then leave it up to LiveDebugValues to track the register movements.

1378–1383

Testing this throughout the day, I was not able to get such a case when compiling Csmith programs at least. SelectionDAGBuilder puts some effort into placing the parameters' first DBG_VALUEs at the start of the entry block [0], so perhaps we're safe from that (or perhaps it's at least unlikely)? Other passes, e.g. PrologEpilogInserter also try to keep parameter DBG_VALUEs at the start of the entry block [1].

[0] https://github.com/llvm/llvm-project/blob/2028ae975c6aa65df3d89c10c95bf9b7baa5e0ab/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp#L5279
[1]https://github.com/llvm/llvm-project/blob/2028ae975c6aa65df3d89c10c95bf9b7baa5e0ab/llvm/lib/CodeGen/PrologEpilogInserter.cpp#L177

llvm/test/DebugInfo/MIR/ARM/dbgcall-site-propagated-value.mir

147

I think it is as expected, since the second parameter's value is passed in r0 in the call to interesting() below here.

[vsk]

Looks good to me.

llvm/lib/CodeGen/LiveDebugValues.cpp

1378–1383

Oh, interesting. Perhaps, as a follow-up, we could try asserting that we get that behavior from ISel & onwards ('if an MI outside of First_MBB is an entry value candidate, & its DIVar is not in the entry vals map, panic').

[dstenb]

Any more comments on this, @djtodoro?

[djtodoro]

LGTM as well. Thanks @dstenb!

llvm/lib/CodeGen/LiveDebugValues.cpp

static bool isRegOtherThanSPAndFP(const MachineOperand &Op,
   Register FP = TRI->getFrameRegister(*MF);
   Register Reg = Op.getReg();
 
   return Reg && Reg != SP && Reg != FP;
 }
 
 namespace {
 
+using DefinedRegsSet = SmallSet<Register, 32>;
+
 class LiveDebugValues : public MachineFunctionPass {
 private:
   const TargetRegisterInfo *TRI;
   const TargetInstrInfo *TII;
   const TargetFrameLowering *TFI;
   BitVector CalleeSavedRegs;
   LexicalScopes LS;
 
#endif
   bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF,
                        unsigned &Reg);
 
   /// Returns true if the given machine instruction is a debug value which we
   /// can emit entry values for.
   ///
   /// Currently, we generate debug entry values only for parameters that are
   /// unmodified throughout the function and located in a register.
-  bool isEntryValueCandidate(const MachineInstr &MI) const;
+  bool isEntryValueCandidate(const MachineInstr &MI,
+                             const DefinedRegsSet &Regs) const;
 
   /// If a given instruction is identified as a spill, return the spill location
   /// and set \p Reg to the spilled register.
   Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI,
                                                   MachineFunction *MF,
                                                   unsigned &Reg);
   /// Given a spill instruction, extract the register and offset used to
   /// address the spill location in a target independent way.
bool LiveDebugValues::join(
   // new in-locations, and delete those.
   VarLocSet Removed = ILS;
   Removed.intersectWithComplement(InLocsT);
   for (auto ID : Removed) {
     Pending.reset(ID);
     ILS.reset(ID);
     ++NumRemoved;
     Changed = true;
   }
 
   return Changed;
 }
 
 void LiveDebugValues::flushPendingLocs(VarLocInMBB &PendingInLocs,
                                        VarLocMap &VarLocIDs) {
   // PendingInLocs records all locations propagated into blocks, which have
   // not had DBG_VALUE insts created. Go through and create those insts now.
for (unsigned ID : Pending) {
       MBB.insert(MBB.instr_begin(), MI);
 
       (void)MI;
       LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump(););
     }
   }
 }
 
-bool LiveDebugValues::isEntryValueCandidate(const MachineInstr &MI) const {
+bool LiveDebugValues::isEntryValueCandidate(
+    const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const {
   if (!MI.isDebugValue())
     return false;
 
   // TODO: Add support for local variables that are expressed in terms of
   // parameters entry values.
   // TODO: Add support for modified arguments that can be expressed
   // by using its entry value.
   auto *DIVar = MI.getDebugVariable();
   if (!DIVar->isParameter() || !DIVar->isNotModified())
     return false;
 
   // Do not consider parameters that belong to an inlined function.
   if (MI.getDebugLoc()->getInlinedAt())
     return false;
 
   // Do not consider indirect debug values (TODO: explain why).
   if (MI.isIndirectDebugValue())
     return false;
 
   // Only consider parameters that are described using registers. Parameters
   // that are passed on the stack are not yet supported, so ignore debug
   // values that are described by the frame or stack pointer.
   if (!isRegOtherThanSPAndFP(MI.getOperand(0), MI, TRI))
     return false;
 
+  // If a parameter's value has been propagated from the caller, then the
+  // parameter's DBG_VALUE may be described using a register defined by some
+  // instruction in the entry block, in which case we shouldn't create an
+  // entry value.
+  if (DefinedRegs.count(MI.getOperand(0).getReg()))
+    return false;
+
   // TODO: Add support for parameters that are described as fragments.
   if (MI.getDebugExpression()->isFragment())
     return false;
 
   return true;
 }
 
+/// Collect all register defines (including aliases) for the given instruction.
+static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs,
+                           const TargetRegisterInfo *TRI) {
+  for (const MachineOperand &MO : MI.operands())
+    if (MO.isReg() && MO.isDef() && MO.getReg())
+      for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI)
+        Regs.insert(*AI);
+}
+
 /// Calculate the liveness information for the given machine function and
 /// extend ranges across basic blocks.
 bool LiveDebugValues::ExtendRanges(MachineFunction &MF) {
   LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");
 
   bool Changed = false;
   bool OLChanged = false;
   bool MBBJoined = false;
 
   VarLocMap VarLocIDs;         // Map VarLoc<>unique ID for use in bitvectors.
   OverlapMap OverlapFragments; // Map of overlapping variable fragments.
   OpenRangesSet OpenRanges(OverlapFragments);
                               // Ranges that are open until end of bb.
   VarLocInMBB OutLocs;        // Ranges that exist beyond bb.
   VarLocInMBB InLocs;         // Ranges that are incoming after joining.
   TransferMap Transfers;      // DBG_VALUEs associated with transfers (such as
                               // spills, copies and restores).
   VarLocInMBB PendingInLocs;  // Ranges that are incoming after joining, but
                               // that we have deferred creating DBG_VALUE insts
                               // for immediately.
 
   VarToFragments SeenFragments;
 
   // Blocks which are artificial, i.e. blocks which exclusively contain
   // instructions without locations, or with line 0 locations.
   SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks;
 
   DenseMap<unsigned int, MachineBasicBlock *> OrderToBB;
   DenseMap<MachineBasicBlock *, unsigned int> BBToOrder;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Worklist;
   std::priority_queue<unsigned int, std::vector<unsigned int>,
                       std::greater<unsigned int>>
       Pending;
 
   // Working set of currently collected debug variables mapped to DBG_VALUEs
   // representing candidates for production of debug entry values.
   DebugParamMap DebugEntryVals;
 
+  // Set of register defines that are seen when traversing the entry block
+  // looking for debug entry value candidates.
+  DefinedRegsSet DefinedRegs;
+
   // Only in the case of entry MBB collect DBG_VALUEs representing
   // function parameters in order to generate debug entry values for them.
+
   MachineBasicBlock &First_MBB = *(MF.begin());
-  for (auto &MI : First_MBB)
-    if (isEntryValueCandidate(MI) &&
+  for (auto &MI : First_MBB) {
+    collectRegDefs(MI, DefinedRegs, TRI);
+    if (isEntryValueCandidate(MI, DefinedRegs) &&
         !DebugEntryVals.count(MI.getDebugVariable()))
       DebugEntryVals[MI.getDebugVariable()] = &MI;
+  }
 
   // Initialize per-block structures and scan for fragment overlaps.
   for (auto &MBB : MF) {
     PendingInLocs[&MBB] = VarLocSet();
 
     for (auto &MI : MBB) {
       if (MI.isDebugValue())
         accumulateFragmentMap(MI, SeenFragments, OverlapFragments);

llvm/test/DebugInfo/MIR/ARM/dbgcall-site-propagated-value.mir

+# RUN: llc -debug-entry-values -run-pass=livedebugvalues -o - %s | FileCheck %s
+
+# Based on the following C reproducer:
+#
+# extern void ext(int *);
+# extern int interesting(int *);
+# extern int *value(void);
+#
+# static void callee(int *p1, int *p2) {
+#   if (interesting(p2))
+#     for (;;)
+#       ext(p1);
+#   ext(p2);
+# }
+#
+# void caller() {
+#   int *local = value();
+#   callee(local, (int *)0xabcd);
+# }
+#
+# Generated using:
+#
+# clang -Os -fno-inline -Xclang -femit-debug-entry-values -g --target=armeb.
+
+--- |
+  target datalayout = "E-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
+  target triple = "armebv4t-unknown-unknown"
+
+  ; Function Attrs: noinline nounwind optsize
+  define arm_aapcs_vfpcc void @caller() #0 !dbg !20 {
+  entry:
+    unreachable
+  }
+
+  ; Function Attrs: noinline nounwind optsize
+  define internal arm_aapcs_vfpcc void @callee(i32* %p1) unnamed_addr #0 !dbg !29 {
+  entry:
+    unreachable
+  }
+
+  declare !dbg !4 arm_aapcs_vfpcc i32* @value()
+  declare !dbg !9 arm_aapcs_vfpcc i32 @interesting(i32*)
+  declare !dbg !12 arm_aapcs_vfpcc void @ext(i32*)
+
+  ; Function Attrs: nounwind readnone speculatable willreturn
+  declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+  attributes #0 = { noinline nounwind optsize "frame-pointer"="all" }
+  attributes #1 = { nounwind readnone speculatable willreturn }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!15, !16, !17, !18}
+  !llvm.ident = !{!19}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !3, nameTableKind: None)
+  !1 = !DIFile(filename: "armeb.c", directory: "/")
+  !2 = !{}
+  !3 = !{!4, !7, !9, !12}
+  !4 = !DISubprogram(name: "value", scope: !1, file: !1, line: 3, type: !5, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+  !5 = !DISubroutineType(types: !6)
+  !6 = !{!7}
+  !7 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !8, size: 32)
+  !8 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !9 = !DISubprogram(name: "interesting", scope: !1, file: !1, line: 2, type: !10, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+  !10 = !DISubroutineType(types: !11)
+  !11 = !{!8, !7}
+  !12 = !DISubprogram(name: "ext", scope: !1, file: !1, line: 1, type: !13, flags: DIFlagPrototyped, spFlags: DISPFlagOptimized, retainedNodes: !2)
+  !13 = !DISubroutineType(types: !14)
+  !14 = !{null, !7}
+  !15 = !{i32 2, !"Dwarf Version", i32 4}
+  !16 = !{i32 2, !"Debug Info Version", i32 3}
+  !17 = !{i32 1, !"wchar_size", i32 4}
+  !18 = !{i32 1, !"min_enum_size", i32 4}
+  !19 = !{!"clang version 10.0.0"}
+  !20 = distinct !DISubprogram(name: "caller", scope: !1, file: !1, line: 12, type: !21, scopeLine: 12, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !23)
+  !21 = !DISubroutineType(types: !22)
+  !22 = !{null}
+  !23 = !{!24}
+  !24 = !DILocalVariable(name: "local", scope: !20, file: !1, line: 13, type: !7)
+  !25 = !DILocation(line: 13, scope: !20)
+  !26 = !DILocation(line: 0, scope: !20)
+  !27 = !DILocation(line: 14, scope: !20)
+  !28 = !DILocation(line: 15, scope: !20)
+  !29 = distinct !DISubprogram(name: "callee", scope: !1, file: !1, line: 5, type: !30, scopeLine: 5, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !32)
+  !30 = !DISubroutineType(types: !31)
+  !31 = !{null, !7, !7}
+  !32 = !{!33, !34}
+  !33 = !DILocalVariable(name: "p1", arg: 1, scope: !29, file: !1, line: 5, type: !7, flags: DIFlagArgumentNotModified)
+  !34 = !DILocalVariable(name: "p2", arg: 2, scope: !29, file: !1, line: 5, type: !7, flags: DIFlagArgumentNotModified)
+  !35 = !DILocation(line: 0, scope: !29)
+  !36 = !DILocation(line: 6, scope: !37)
+  !37 = distinct !DILexicalBlock(scope: !29, file: !1, line: 6)
+  !38 = !DILocation(line: 6, scope: !29)
+  !39 = !DILocation(line: 7, scope: !40)
+  !40 = distinct !DILexicalBlock(scope: !37, file: !1, line: 7)
+  !41 = !DILocation(line: 8, scope: !42)
+  !42 = distinct !DILexicalBlock(scope: !40, file: !1, line: 7)
+  !43 = !DILocation(line: 7, scope: !42)
+  !44 = distinct !{!44, !39, !45}
+  !45 = !DILocation(line: 8, scope: !40)
+  !46 = !DILocation(line: 9, scope: !29)
+  !47 = !DILocation(line: 10, scope: !29)
+
+...
+---
+name:            caller
+alignment:       4
+tracksRegLiveness: true
+callSites:
+  - { bb: 0, offset: 6 }
+  - { bb: 0, offset: 9, fwdArgRegs:
+      - { arg: 0, reg: '$r0' } }
+body:             |
+  bb.0:
+    liveins: $lr
+
+    $sp = frame-setup STMDB_UPD $sp, 14, $noreg, $r11, killed $lr
+    frame-setup CFI_INSTRUCTION def_cfa_offset 8
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r11, -8
+    $r11 = frame-setup MOVr $sp, 14, $noreg, $noreg
+    frame-setup CFI_INSTRUCTION def_cfa_register $r11
+    BL @value, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit-def $sp, implicit-def $r0, debug-location !25
+    DBG_VALUE $r0, $noreg, !24, !DIExpression(), debug-location !26
+    $sp = LDMIA_UPD $sp, 14, $noreg, def $r11, def $lr, debug-location !27
+    TAILJMPd @callee, implicit $sp, implicit $sp, implicit killed $r0, debug-location !27
+
+...
+---
+name:            callee
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    successors: %bb.2(0x30000000), %bb.1(0x50000000)
+    liveins: $r0, $r4, $r10, $lr
+
+    DBG_VALUE $r0, $noreg, !33, !DIExpression(), debug-location !35
+    $sp = frame-setup STMDB_UPD $sp, 14, $noreg, killed $r4, killed $r10, $r11, killed $lr
+    frame-setup CFI_INSTRUCTION def_cfa_offset 16
+    frame-setup CFI_INSTRUCTION offset $lr, -4
+    frame-setup CFI_INSTRUCTION offset $r11, -8
+    frame-setup CFI_INSTRUCTION offset $r10, -12
+    frame-setup CFI_INSTRUCTION offset $r4, -16
+    $r11 = frame-setup ADDri $sp, 8, 14, $noreg, $noreg
+    frame-setup CFI_INSTRUCTION def_cfa $r11, 8
+    $r4 = MOVr killed $r0, 14, $noreg, $noreg
+    DBG_VALUE $r4, $noreg, !33, !DIExpression(), debug-location !35
+    $r0 = MOVi 205, 14, $noreg, $noreg
+    $r0 = ORRri killed $r0, 43776, 14, $noreg, $noreg
+    ; The MOVI and ORRri produce the second parameter's (!34) value which has
+    ; been propagated from caller().
+    DBG_VALUE $r0, $noreg, !34, !DIExpression(), debug-location !35
+    BL @interesting, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit killed $r0, implicit-def $sp, implicit-def $r0, debug-location !36
+    CMPri killed renamable $r0, 0, 14, $noreg, implicit-def $cpsr, debug-location !38
+    Bcc %bb.2, 0, killed $cpsr, debug-location !38
+
+  bb.1:
+    liveins: $r4
+
+    $r0 = MOVr $r4, 14, $noreg, $noreg, debug-location !41
+    BL @ext, csr_aapcs, implicit-def dead $lr, implicit $sp, implicit killed $r0, implicit-def $sp, debug-location !41
+    B %bb.1, debug-location !43
+
+  bb.2:
+    $r0 = MOVi 205, 14, $noreg, $noreg
+    $r0 = ORRri killed $r0, 43776, 14, $noreg, $noreg
+    $sp = LDMIA_UPD $sp, 14, $noreg, def $r4, def $r10, def $r11, def $lr, debug-location !46
+    TAILJMPd @ext, implicit $sp, implicit $sp, implicit killed $r0, debug-location !46
+
+...
+
+# In this test case the second parameter's value has been propagated from the
+# caller to the callee, so we should not emit any entry value DBG_VALUEs for
+# that parameter. The second parameter reuses the first parameter's register
+# ($r0), and previously we would incorrectly emit an entry value for the
+# parameter using that register.
+
+# CHECK-DAG: ![[P1:[0-9]+]] = !DILocalVariable(name: "p1", arg: 1
+# CHECK-DAG: ![[P2:[0-9]+]] = !DILocalVariable(name: "p2", arg: 2
+
+# CHECK-NOT: DBG_VALUE $r0, $noreg, ![[P2]], !DIExpression(DW_OP_LLVM_entry_value
+
+# CHECK: DBG_VALUE $r0, $noreg, ![[P1]], !DIExpression(DW_OP_LLVM_entry_value
+
+# CHECK-NOT: DBG_VALUE $r0, $noreg, ![[P2]], !DIExpression(DW_OP_LLVM_entry_value