[DebugInfo] Don't sink DBG_VALUEs past other DBG_VALUEs of the same variable location

[jmorse]

Summary

This patch is part of a fix for PR43855 [0], resolving problems in D58386 / rGf5e1b718a6 (which ended up being backed out).

It turns out DBG_VALUEs would be sunk even if the variables location was re-specified in the block, so for example in:

 %0 = someinst
DBG_VALUE %0, !123, !DIExpression()
 %1 = anotherinst
DBG_VALUE %1, !123, !DIExpression()

if %0 were to sink, the corresponding DBG_VALUE would sink too, past the next DBG_VALUE, effectively re-ordering assignments.

To fix these things: I've added a SeenDbgVars set recording what variable locations have been seen in a block already (working bottom up), and now flag DBG_VALUEs that would pass a later DBG_VALUE for the same variable.

If such a DBG_VALUE has its operand sunk, then it will now be set to undef, if it can't be copy propagated. I've split out the copy-prop code into a helper function to ease this. This patch is based on a tree with f5e1b718a6 reapplied to make it easier to read.

NB, this only works for repeated DBG_VALUEs in the same basic block, the general case involving control flow is much harder, which I've written up in [1].

[0] https://bugs.llvm.org/show_bug.cgi?id=43855
[1] https://bugs.llvm.org/show_bug.cgi?id=44117

[aprantl]

Could you please add the motivating example from the description into one of the comments?

Otherwise I think this looks reasonable!

llvm/lib/CodeGen/MachineSink.cpp

117

I have a suspicion that on average, this DenseMap will have very few entries since it contains registers that hold variable values. Would it make sense to use a SmallDenseMap here? Or does it not because the DenseMap is being reused?

[jmorse]

Insert an example into a field comment, to explain the kind of code / DBG_VALUE sequences we want to avoid re-ordering.

[jmorse]

llvm/lib/CodeGen/MachineSink.cpp

117

I'd suggest the latter; assuming the concern is memory size, there's only one instance of this field per Pass, so it shouldn't consume too much memory.

(NB, I couldn't immediately find any documentation on SmallDenseMap, so I assume its purpose is memory conservation rather than a performance improvement).

[aprantl]

llvm/lib/CodeGen/MachineSink.cpp

117

The reuse argument makes sense to me.

llvm/lib/CodeGen/MachineSink.cpp

 // they aren't executed on paths where their results aren't needed.
 //
 // This pass is not intended to be a replacement or a complete alternative
 // for an LLVM-IR-level sinking pass. It is only designed to sink simple
 // constructs that are not exposed before lowering and instruction selection.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
class MachineSinking : public MachineFunctionPass {
     // will be split.
     SetVector<std::pair<MachineBasicBlock *, MachineBasicBlock *>> ToSplit;
 
     SparseBitVector<> RegsToClearKillFlags;
 
     using AllSuccsCache =
         std::map<MachineBasicBlock *, SmallVector<MachineBasicBlock *, 4>>;
 
-    // Remember debug uses of vregs seen, so we know what to sink out of blocks.
-    DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgUsers;
+    /// DBG_VALUE pointer and flag. The flag is true if this DBG_VALUE is
+    /// post-dominated by another DBG_VALUE of the same variable location.
+    /// This is necessary to detect sequences such as:
+    ///     %0 = someinst
+    ///     DBG_VALUE %0, !123, !DIExpression()
+    ///     %1 = anotherinst
+    ///     DBG_VALUE %1, !123, !DIExpression()
+    /// Where if %0 were to sink, the DBG_VAUE should not sink with it, as that
+    /// would re-order assignments.
+    using SeenDbgUser = PointerIntPair<MachineInstr *, 1>;
+
+    /// Record of DBG_VALUE uses of vregs in a block, so that we can identify
+    /// debug instructions to sink.
+    SmallDenseMap<unsigned, TinyPtrVector<SeenDbgUser>> SeenDbgUsers;
+
+    /// Record of debug variables that have had their locations set in the
+    /// current block.
+    DenseSet<DebugVariable> SeenDbgVars;
 
   public:
     static char ID; // Pass identification
 
     MachineSinking() : MachineFunctionPass(ID) {
       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     }
 
if (SinkInstruction(MI, SawStore, AllSuccessors)) {
       ++NumSunk;
       MadeChange = true;
     }
 
     // If we just processed the first instruction in the block, we're done.
   } while (!ProcessedBegin);
 
   SeenDbgUsers.clear();
+  SeenDbgVars.clear();
 
   return MadeChange;
 }
 
 void MachineSinking::ProcessDbgInst(MachineInstr &MI) {
   // When we see DBG_VALUEs for registers, record any vreg it reads, so that
   // we know what to sink if the vreg def sinks.
   assert(MI.isDebugValue() && "Expected DBG_VALUE for processing");
 
+  DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),
+                    MI.getDebugLoc()->getInlinedAt());
+  bool SeenBefore = SeenDbgVars.count(Var) != 0;
+
   MachineOperand &MO = MI.getOperand(0);
-  if (!MO.isReg() || !MO.getReg().isVirtual())
-    return;
+  if (MO.isReg() && MO.getReg().isVirtual())
+    SeenDbgUsers[MO.getReg()].push_back(SeenDbgUser(&MI, SeenBefore));
 
-  SeenDbgUsers[MO.getReg()].push_back(&MI);
+  // Record the variable for any DBG_VALUE, to avoid re-ordering any of them.
+  SeenDbgVars.insert(Var);
 }
 
 bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
                                                  MachineBasicBlock *From,
                                                  MachineBasicBlock *To) {
   // FIXME: Need much better heuristics.
 
   // If the pass has already considered breaking this edge (during this pass
if (TII->analyzeBranchPredicate(*PredMBB, MBP, false))
     return false;
 
   return MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
          (MBP.Predicate == MachineBranchPredicate::PRED_NE ||
           MBP.Predicate == MachineBranchPredicate::PRED_EQ) &&
          MBP.LHS.getReg() == BaseOp->getReg();
 }
 
-/// Sink an instruction and its associated debug instructions.
-static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
-                        MachineBasicBlock::iterator InsertPos,
-                        SmallVectorImpl<MachineInstr *> &DbgValuesToSink) {
-  const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo();
-  const TargetInstrInfo &TII = *MI.getMF()->getSubtarget().getInstrInfo();
-
-  // If we cannot find a location to use (merge with), then we erase the debug
-  // location to prevent debug-info driven tools from potentially reporting
-  // wrong location information.
-  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
-    MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
-                                                 InsertPos->getDebugLoc()));
-  else
-    MI.setDebugLoc(DebugLoc());
-
-  // Move the instruction.
-  MachineBasicBlock *ParentBlock = MI.getParent();
-  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
-                      ++MachineBasicBlock::iterator(MI));
-
-  // Sink a copy of debug users to the insert position. Mark the original
-  // DBG_VALUE location as 'undef', indicating that any earlier variable
-  // location should be terminated as we've optimised away the value at this
-  // point.
-  // If the sunk instruction is a copy, try to forward the copy instead of
-  // leaving an 'undef' DBG_VALUE in the original location. Don't do this if
-  // there's any subregister weirdness involved.
-  for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
-                                                 DBE = DbgValuesToSink.end();
-       DBI != DBE; ++DBI) {
-    MachineInstr *DbgMI = *DBI;
-    MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI);
-    SuccToSinkTo.insert(InsertPos, NewDbgMI);
+/// If the sunk instruction is a copy, try to forward the copy instead of
+/// leaving an 'undef' DBG_VALUE in the original location. Don't do this if
+/// there's any subregister weirdness involved. Returns true if copy
+/// propagation occurred.
+static bool attemptDebugCopyProp(MachineInstr &SinkInst, MachineInstr &DbgMI) {
+  const MachineRegisterInfo &MRI = SinkInst.getMF()->getRegInfo();
+  const TargetInstrInfo &TII = *SinkInst.getMF()->getSubtarget().getInstrInfo();
 
-    // Copy DBG_VALUE operand and set the original to undef. We then check to
-    // see whether this is something that can be copy-forwarded. If it isn't,
-    // continue around the loop.
-    MachineOperand DbgMO = DbgMI->getOperand(0);
-    DbgMI->getOperand(0).setReg(0);
+  MachineOperand DbgMO = DbgMI.getOperand(0);
 
-    const MachineOperand *SrcMO = nullptr, *DstMO = nullptr;
-    auto CopyOperands = TII.isCopyInstr(MI);
-    if (!CopyOperands)
-      continue;
-    SrcMO = CopyOperands->Source;
-    DstMO = CopyOperands->Destination;
+  auto CopyOperands = TII.isCopyInstr(SinkInst);
+    return false;
 
-    // Check validity of forwarding this copy.
-    bool PostRA = MRI.getNumVirtRegs() == 0;
 
-    // Trying to forward between physical and virtual registers is too hard.
-    if (DbgMO.getReg().isVirtual() != SrcMO->getReg().isVirtual())
-      continue;
+    return false;
 
-    // Only try virtual register copy-forwarding before regalloc, and physical
-    // register copy-forwarding after regalloc.
-    bool arePhysRegs = !DbgMO.getReg().isVirtual();
-    if (arePhysRegs != PostRA)
-      continue;
+    return false;
 
-    // Pre-regalloc, only forward if all subregisters agree (or there are no
-    // subregs at all). More analysis might recover some forwardable copies.
-    if (!PostRA && (DbgMO.getSubReg() != SrcMO->getSubReg() ||
-                    DbgMO.getSubReg() != DstMO->getSubReg()))
-      continue;
+    return false;
 
-    // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register
-    // of this copy. Only forward the copy if the DBG_VALUE operand exactly
-    // matches the copy destination.
-    if (PostRA && DbgMO.getReg() != DstMO->getReg())
-      continue;
+    return false;
+
+  DbgMI.getOperand(0).setReg(SrcMO->getReg());
+  DbgMI.getOperand(0).setSubReg(SrcMO->getSubReg());
+  return true;
+}
+
+/// Sink an instruction and its associated debug instructions.
+static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
+                        MachineBasicBlock::iterator InsertPos,
+                        SmallVectorImpl<MachineInstr *> &DbgValuesToSink) {
+
+  // If we cannot find a location to use (merge with), then we erase the debug
+  // location to prevent debug-info driven tools from potentially reporting
+  // wrong location information.
+  if (!SuccToSinkTo.empty() && InsertPos != SuccToSinkTo.end())
+    MI.setDebugLoc(DILocation::getMergedLocation(MI.getDebugLoc(),
+                                                 InsertPos->getDebugLoc()));
+  else
+    MI.setDebugLoc(DebugLoc());
+
+  // Move the instruction.
+  MachineBasicBlock *ParentBlock = MI.getParent();
+  SuccToSinkTo.splice(InsertPos, ParentBlock, MI,
+                      ++MachineBasicBlock::iterator(MI));
+
+  // Sink a copy of debug users to the insert position. Mark the original
+  // DBG_VALUE location as 'undef', indicating that any earlier variable
+  // location should be terminated as we've optimised away the value at this
+  // point.
+  for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(),
+                                                 DBE = DbgValuesToSink.end();
+       DBI != DBE; ++DBI) {
+    MachineInstr *DbgMI = *DBI;
+    MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI);
+    SuccToSinkTo.insert(InsertPos, NewDbgMI);
 
-    DbgMI->getOperand(0).setReg(SrcMO->getReg());
-    DbgMI->getOperand(0).setSubReg(SrcMO->getSubReg());
+    if (!attemptDebugCopyProp(MI, *DbgMI))
+      DbgMI->getOperand(0).setReg(0);
   }
 }
 
 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 /// instruction out of its current block into a successor.
 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
                                      AllSuccsCache &AllSuccessors) {
   // Don't sink instructions that the target prefers not to sink.
bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
   // Collect debug users of any vreg that this inst defines.
   SmallVector<MachineInstr *, 4> DbgUsersToSink;
   for (auto &MO : MI.operands()) {
     if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
       continue;
     if (!SeenDbgUsers.count(MO.getReg()))
       continue;
 
+    // Sink any users that don't pass any other DBG_VALUEs for this variable.
     auto &Users = SeenDbgUsers[MO.getReg()];
-    DbgUsersToSink.insert(DbgUsersToSink.end(), Users.begin(), Users.end());
+    for (auto &User : Users) {
+      MachineInstr *DbgMI = User.getPointer();
+      if (User.getInt()) {
+        // This DBG_VALUE would re-order assignments. If we can't copy-propagate
+        // it, it can't be recovered. Set it undef.
+        if (!attemptDebugCopyProp(MI, *DbgMI))
+          DbgMI->getOperand(0).setReg(0);
+      } else {
+        DbgUsersToSink.push_back(DbgMI);
+      }
+    }
   }
 
   // After sinking, some debug users may not be dominated any more. If possible,
   // copy-propagate their operands. As it's expensive, don't do this if there's
   // no debuginfo in the program.
   if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy())
     SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo);
 

llvm/test/DebugInfo/MIR/X86/machinesink.mir

 # RUN: llc -mtriple=x86_64-unknown-unknown -run-pass=machine-sink -o - %s | FileCheck %s
-# Check various things when we sink machine instructions:
+# In the first test, check various things when we sink machine instructions:
 #   a) DBG_VALUEs should sink with defs
 #   b) Undefs should be left behind
 #   c) DBG_VALUEs not immediately following the defining inst should sink too
 #   d) If we generate debug-use-before-defs through sinking, and can copy
 #      propagate to a different value, we should do that.
+#
+# Test two checks DBG_VALUEs do not sink past a DBG_VALUE in the same block
+# that redefines the variable location, while three checks that copy-propagation
+# happens in the same scenario.
 --- |
   target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"
 
   @x = common local_unnamed_addr global i32 0, align 4, !dbg !0
 
   ; Function Attrs: noreturn nounwind uwtable
   define void @Process(i32* nocapture readonly %p) local_unnamed_addr !dbg !9 {
   ; Stripped
   entry:
     br label %nou
   nou:
     br label %exit
   exit:
     ret void
   }
 
+  define void @test2(i32* nocapture readonly %p) local_unnamed_addr !dbg !101 {
+  ; Stripped
+  entry:
+    br label %block1
+  block1:
+    br label %exit
+  exit:
+    ret void
+  }
+
+  define void @test3(i32* nocapture readonly %p) local_unnamed_addr !dbg !201 {
+  ; Stripped
+  entry:
+    br label %block1
+  block1:
+    br label %exit
+  exit:
+    ret void
+  }
+
   ; Function Attrs: nounwind readnone
   declare void @llvm.dbg.value(metadata, i64, metadata, metadata)
 
   !llvm.dbg.cu = !{!1}
   !llvm.module.flags = !{!6, !7}
   !llvm.ident = !{!8}
 
   !0 = !DIGlobalVariableExpression(var: !DIGlobalVariable(name: "x", scope: !1, file: !2, line: 1, type: !5, isLocal: false, isDefinition: true), expr: !DIExpression())
--- |
   !12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !13, size: 64)
   !13 = !DIDerivedType(tag: DW_TAG_const_type, baseType: !14)
   !14 = !DIBasicType(name: "unsigned int", size: 32, encoding: DW_ATE_unsigned)
   !15 = !{!16}
   !16 = !DILocalVariable(name: "p", arg: 1, scope: !9, file: !2, line: 2, type: !12)
   !17 = !DIExpression()
   !18 = !DILocation(line: 2, column: 34, scope: !9)
   !28 = !DILexicalBlockFile(scope: !9, file: !2, discriminator: 1)
+  !101 = distinct !DISubprogram(name: "test2", scope: !2, file: !2, line: 2, type: !10, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !1, retainedNodes: !102)
+  !102 = !{!103}
+  !103 = !DILocalVariable(name: "q", arg: 1, scope: !101, file: !2, line: 2, type: !12)
+  !104 = !DILocation(line: 1, column: 1, scope: !101)
+  !201 = distinct !DISubprogram(name: "test2", scope: !2, file: !2, line: 2, type: !10, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !1, retainedNodes: !202)
+  !202 = !{!203}
+  !203 = !DILocalVariable(name: "r", arg: 1, scope: !201, file: !2, line: 2, type: !12)
+  !204 = !DILocation(line: 1, column: 1, scope: !201)
 
   ; CHECK: [[VARNUM:![0-9]+]] = !DILocalVariable(name: "p",
+  ; CHECK: [[VAR2NUM:![0-9]+]] = !DILocalVariable(name: "q",
+  ; CHECK: [[VAR3NUM:![0-9]+]] = !DILocalVariable(name: "r",
 
 ...
 ---
 name:            Process
 tracksRegLiveness: true
 liveins:
   - { reg: '$rdi', virtual-reg: '%2' }
   - { reg: '$rsi', virtual-reg: '%2' }
bb.2.exit:
     ; CHECK-LABEL: bb.2.exit:
     ; CHECK:       DBG_VALUE [[ARG0VREG]], $noreg, [[VARNUM]]
     ; CHECK-NEXT:  $rax = MOV64rr [[ARG0VREG]]
     ; CHECK-NEXT:  RET 0
     DBG_VALUE %5, _, !16, !17, debug-location !18
     $rax = MOV64rr %2
     RET 0
 ...
+---
+name:            test2
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$rsi', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.block1, %bb.2.exit
+    liveins: $rdi, $esi
+
+    ; This block should _not_ have the first DBG_VALUE sunk out from it, as it
+    ; would pass a later DBG_VALUE of the same variable location. An undef
+    ; DBG_VALUE should be left behind though.
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK:       [[TEST2VREG:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT:  CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg, $noreg, [[VAR2NUM]]
+    ; CHECK-NEXT:  CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE 0, $noreg, [[VAR2NUM]]
+    ; CHECK-NEXT:  JCC_1 %bb.1, 4
+    ; CHECK-NEXT:  JMP_1
+
+    %2:gr64 = COPY $rdi
+    %5:gr64 = ADD64ri8 %2, 1, implicit-def dead $eflags
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE %5, $noreg, !103, !17, debug-location !104
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE 0, $noreg, !103, !17, debug-location !104
+    JCC_1 %bb.1.block1, 4, implicit $eflags
+    JMP_1 %bb.2.exit
+
+  bb.1.block1:
+    successors: %bb.2.exit
+
+    ; This block should receive no DBG_VALUE.
+    ; CHECK-LABEL: bb.1.block1:
+    ; CHECK-NOT:   DBG_VALUE
+    ; CHECK:       [[SUNKVREG2:%[0-9]+]]:gr64 = ADD64ri8 [[TEST2VREG]]
+    ; CHECK-NOT:   DBG_VALUE
+    ; CHECK-NEXT:  ADD64ri8
+    ; CHECK: JMP_1 %bb.2
+    %1:gr64 = ADD64ri8 %5, 4, implicit-def dead $eflags
+    JMP_1 %bb.2.exit
+
+  bb.2.exit:
+    $rax = MOV64rr %2
+    RET 0
+...
+---
+name:            test3
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$rsi', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.block1, %bb.2.exit
+    liveins: $rdi, $esi
+
+    ; The copy from %2 to %5 will sink into a later block, and the first
+    ; DBG_VALUE cannot pass the second. But, we should be able to recover
+    ; the variable location through copy propagation.
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK:       [[TEST3VREG:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT:  CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE [[TEST3VREG]], $noreg, [[VAR3NUM]]
+    ; CHECK-NEXT:  CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE 0, $noreg, [[VAR3NUM]]
+    ; CHECK-NEXT:  JCC_1 %bb.1, 4
+    ; CHECK-NEXT:  JMP_1
+
+    %2:gr64 = COPY $rdi
+    %5:gr64 = COPY %2
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE %5, $noreg, !203, !17, debug-location !204
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE 0, $noreg, !203, !17, debug-location !204
+    JCC_1 %bb.1.block1, 4, implicit $eflags
+    JMP_1 %bb.2.exit
+
+  bb.1.block1:
+    successors: %bb.2.exit
+
+    ; This block should receive no DBG_VALUE.
+    ; CHECK-LABEL: bb.1.block1:
+    ; CHECK-NOT:   DBG_VALUE
+    ; CHECK:       COPY [[TEST3VREG]]
+    ; CHECK-NOT:   DBG_VALUE
+    ; CHECK-NEXT:  ADD64ri8
+    ; CHECK: JMP_1 %bb.2
+    %1:gr64 = ADD64ri8 %5, 4, implicit-def dead $eflags
+    JMP_1 %bb.2.exit
+
+  bb.2.exit:
+    $rax = MOV64rr %2
+    RET 0
+...