[DebugInfo][MachineSink] Don't stop copy-propagating DBG_VALUEs that will have a sunk copy created

[jmorse]

Summary

When sinking instructions, and sinking DBG_VALUEs at the same time, we leave one DBG_VALUE at the source location to either mark an undef location, or copy-propagate it if it can be recovered. However, this remaining DBG_VALUE wasn't receiving any further copy propagation (there can be multiple copies in a row), potentially leading to a debug use-before-def. Fix this by trying to copy-propagate all DBG_VALUEs, including those that used to refer to a sunk instruction,

While we're at it, "PerformTrivialForwardCoalescing" occasionally eliminates COPYs, leading to dropped variable locations in one of the added tests. Fix this by updating our list of debug-users-of-vregs whenever we coalesce a register this way.

There are zero changes to the location statistics for a clang-3.4 build with this patch (alas), it's purely a correctness thing.

You may notice that MachineSink.cpp seems to be accumulating a lot of debug related stuff... this is partially because it's had my attention through its use of collectDebugValues, but I would also describe shuffling DBG_VALUEs around as "fiddly". I'll see at some point whether this can be generalised in some way.

[aprantl]

llvm/lib/CodeGen/MachineSink.cpp

1084

if (!AlreadySinking) ?

1091

generally, the control flow here isn't quite obvious. It almost looks like a mistake that the instructions inserted into the set on the line above aren't counted here, but I think it's intentional. Is there a way to make it more obvious? Perhaps by renaming the AlreadySinking variable?

[uabelho]

I think you're on the right track. My mir-reproducer passes with this patch, so now I get the wanted

%6:an32_rn_pairs = COPY %5.hiAcc
%8:an32_0_7 = COPY %6
DBG_VALUE %8, [...]

instead of the previous

%6:an32_rn_pairs = COPY %5.hiAcc
%8:an32_0_7 = COPY %6
DBG_VALUE %8.hiAcc:an32_0_7, [...]

llvm/lib/CodeGen/MachineSink.cpp

class MachineSinking : public MachineFunctionPass {
     };
 
     /// Map sunk vreg to the final destination of the vreg def, and the
     /// DBG_VALUEs that were attached to it. We need only create one new
     /// DBG_VALUE even if the defining instruction sinks through multiple
     /// blocks.
     DenseMap<unsigned, SunkDebugDef> SunkDebugDefs;
 
+    /// A set of DBG_VALUEs that are going to have a sunk copy created later.
+    /// These DBG_VALUEs might need to be copy-propagated further, but
+    /// they should not be sunk out of the same block twice.
+    SmallPtrSet<MachineInstr *, 8> DbgInstsAlreadySinking;
+
   public:
     static char ID; // Pass identification
 
     MachineSinking() : MachineFunctionPass(ID) {
       initializeMachineSinkingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
   MachineInstr *DefMI = MRI->getVRegDef(SrcReg);
   if (DefMI->isCopyLike())
     return false;
   LLVM_DEBUG(dbgs() << "Coalescing: " << *DefMI);
   LLVM_DEBUG(dbgs() << "*** to: " << MI);
   MRI->replaceRegWith(DstReg, SrcReg);
   MI.eraseFromParent();
 
+  // Debug users pointing at the destination of the copy, should now be
+  // recorded against its source.
+  if (SeenDbgUsers.count(DstReg)) {
+    auto &DbgSrcSeen = SeenDbgUsers[SrcReg];
+    auto &DbgDstSeen = SeenDbgUsers[DstReg];
+    DbgSrcSeen.insert(DbgSrcSeen.end(), DbgDstSeen.begin(), DbgDstSeen.end());
+  }
+
+  // We should never sink something, and _then_ coalesce it. Assert that there
+  // are no sinking DBG_VALUEs hanging off this copy.
+  assert(SunkDebugDefs.count(DstReg) == 0);
+
   // Conservatively, clear any kill flags, since it's possible that they are no
   // longer correct.
   MRI->clearKillFlags(SrcReg);
 
   ++NumCoalesces;
   return true;
 }
 
if (SinkInstruction(MI, SawStore, AllSuccessors)) {
       MadeChange = true;
     }
 
     // If we just processed the first instruction in the block, we're done.
   } while (!ProcessedBegin);
 
   SeenDbgUsers.clear();
   SeenDbgVars.clear();
+  DbgInstsAlreadySinking.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");
for (auto &MO : MI.operands()) {
     SunkDef.MI = &MI;
 
     // Record that these DBG_VALUEs refer to this sinking vreg, so that they
     // can be re-specified after sinking completes. Try copy-propagating
     // the original location too.
     auto &Users = SeenDbgUsers[MO.getReg()];
     for (auto &User : Users) {
       MachineInstr *DbgMI = User.getPointer();
-      DebugVariable Var(DbgMI->getDebugVariable(), DbgMI->getDebugExpression(),
-                        DbgMI->getDebugLoc()->getInlinedAt());
-      // If we can't copy-propagate the original DBG_VALUE, mark it undef, as
+
+      bool AlreadySinking = DbgInstsAlreadySinking.count(DbgMI) != 0;
+
+      // If we can't copy-propagate this DBG_VALUE, mark it undef, as
       // its operand will not be available.
-      if (!attemptDebugCopyProp(MI, *DbgMI))
+      if (!attemptDebugCopyProp(MI, *DbgMI)) {
         DbgMI->getOperand(0).setReg(0);
+      } else {
+        ProcessDbgInst(*DbgMI);
+        DbgInstsAlreadySinking.insert(DbgMI);
+      }
+
+      // If we've already created a "sinking" record for this DBG_VALUE, and
+      // we get here, then it's being repeatedly copy propagated. Don't create
+      // any more sinking records.
+      if (AlreadySinking)
+        continue;
+
+      DebugVariable Var(DbgMI->getDebugVariable(), DbgMI->getDebugExpression(),
+                        DbgMI->getDebugLoc()->getInlinedAt());
 
       // Debug users that don't pass any other DBG_VALUEs for this variable
       // can be sunk.
       if (!User.getInt())
         SunkDef.InstsToSink.insert({Var, DbgMI});
     }
   }
 

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

 # RUN: llc -mtriple=x86_64-unknown-unknown -run-pass=machine-sink -o - %s | FileCheck %s
 # 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.
 #
 # Test four: if we sink a DBG_VALUE via an intermediate block, no spurious
 # DBG_VALUE $noreg's should appear along the way.
+#
+# Test five and six: we should continue to copy-propagate remaining DBG_VALUEs
+# once we know they need a sunk DBG_VALUE creating.
 --- |
   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 {
--- |
   combined:
     br label %branch1
   branch1:
     br label %exit
   exit:
     ret void
   }
 
-  ; Function Attrs: nounwind readnone
+  define void @test5(i32* nocapture readonly %p) local_unnamed_addr !dbg !401 {
+  ; Stripped
+  entry:
+    br label %nou
+  nou:
+    br label %exit
+  exit:
+    ret void
+  }
+
+  define void @test6(i32* nocapture readonly %p) local_unnamed_addr !dbg !501 {
+  ; Stripped
+  entry:
+    br label %nou
+  nou:
+    br label %exit
+  exit:
+    ret void
+  }
+  
   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())
   !1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !3, globals: !4)
--- |
   !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)
   !301 = 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: !302)
   !302 = !{!303}
   !303 = !DILocalVariable(name: "s", arg: 1, scope: !301, file: !2, line: 2, type: !12)
   !304 = !DILocation(line: 1, column: 1, scope: !301)
+  !401 = distinct !DISubprogram(name: "test5", scope: !2, file: !2, line: 2, type: !10, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !1, retainedNodes: !402)
+  !402 = !{!403}
+  !403 = !DILocalVariable(name: "t", arg: 1, scope: !401, file: !2, line: 2, type: !12)
+  !404 = !DILocation(line: 1, column: 1, scope: !401)
+  !501 = distinct !DISubprogram(name: "test5", scope: !2, file: !2, line: 2, type: !10, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !1, retainedNodes: !502)
+  !502 = !{!503}
+  !503 = !DILocalVariable(name: "u", arg: 1, scope: !501, file: !2, line: 2, type: !12)
+  !504 = !DILocation(line: 1, column: 1, scope: !501)
 
   ; CHECK: [[VARNUM:![0-9]+]] = !DILocalVariable(name: "p",
   ; CHECK: [[VAR2NUM:![0-9]+]] = !DILocalVariable(name: "q",
   ; CHECK: [[VAR3NUM:![0-9]+]] = !DILocalVariable(name: "r",
   ; CHECK: [[VAR4NUM:![0-9]+]] = !DILocalVariable(name: "s",
+  ; CHECK: [[VAR5NUM:![0-9]+]] = !DILocalVariable(name: "t",
+  ; CHECK: [[VAR6NUM:![0-9]+]] = !DILocalVariable(name: "u",
 
 ...
 ---
 name:            Process
 tracksRegLiveness: true
 liveins:
   - { reg: '$rdi', virtual-reg: '%2' }
   - { reg: '$rsi', virtual-reg: '%2' }
body:             |
   bb.5.exit:
     ; CHECK-LABEL: bb.5.exit
     ; CHECK-NOT:   DBG_VALUE
     ; CHECK:       RET 0
 
     $rax = MOV64rr %2
     RET 0
 ...
+---
+name:            test5
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$rsi', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.nou, %bb.2.exit
+    liveins: $rdi, $esi
+
+    ; This block has a chain of COPYs that should be sunk out, except the first,
+    ; which has a use in this block. We know that the DBG_VALUE will sink,
+    ; but should continue to copy propagate it.
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK:       [[T5ARG0:%[0-9]+]]:gr64 = COPY $rdi
+    ; CHECK-NEXT:  [[T5COPY1:%[0-9]+]]:gr64 = COPY [[T5ARG0]]
+    ; CHECK-NEXT:  CMP64ri8 [[T5COPY1]], 0
+    ; CHECK-NEXT:  DBG_VALUE [[T5COPY1]], $noreg, [[VAR5NUM]]
+    ; CHECK-NEXT:  JCC_1 %bb.1, 4
+    ; CHECK-NEXT:  JMP_1
+
+    %2:gr64 = COPY $rdi
+    %5:gr64 = COPY %2
+    %7:gr64 = COPY %5
+    %8:gr64 = COPY %7
+    CMP64ri8 %5, 0, implicit-def $eflags
+    DBG_VALUE %8, $noreg, !403, !17, debug-location !404
+    JCC_1 %bb.1.nou, 4, implicit $eflags
+    JMP_1 %bb.2.exit
+
+  bb.1.nou:
+    successors: %bb.2.exit
+
+    ; This block should receive the sunk copies and DBG_VALUE
+    ; CHECK-LABEL: bb.1.nou:
+    ; CHECK:       [[T5COPY2:%[0-9]+]]:gr64 = COPY [[T5COPY1]]
+    ; CHECK-NEXT:  [[T5COPY3:%[0-9]+]]:gr64 = COPY [[T5COPY2]]
+    ; CHECK-NEXT:  DBG_VALUE [[T5COPY3]], $noreg, [[VAR5NUM]]
+    ; CHECK-NEXT:  ADD64ri8
+    ; CHECK-NEXT:  JMP_1
+    %1:gr64 = ADD64ri8 %8, 4, implicit-def dead $eflags
+    JMP_1 %bb.2.exit
+
+  bb.2.exit:
+    $rax = MOV64rr %2
+    RET 0
+...
+---
+name:            test6
+tracksRegLiveness: true
+liveins:
+  - { reg: '$rdi', virtual-reg: '%2' }
+  - { reg: '$rsi', virtual-reg: '%2' }
+body:             |
+  bb.0.entry:
+    successors: %bb.1.nou, %bb.2.exit
+    liveins: $rdi, $esi
+
+    ; This block has a chain of insts that should be completely sunk out;
+    ; the DBG_VALUE should copy-propagate through each and end up $noreg.
+    ; CHECK-LABEL: bb.0.entry:
+    ; CHECK:       CMP32ri $esi, 0
+    ; CHECK-NEXT:  DBG_VALUE $noreg, $noreg, [[VAR6NUM]]
+    ; CHECK-NEXT:  JCC_1 %bb.1, 4
+    ; CHECK-NEXT:  JMP_1
+
+    %2:gr64 = MOV64ri 0
+    %5:gr64 = COPY %2
+    %7:gr64 = COPY %5
+    %8:gr64 = COPY %7
+    CMP32ri $esi, 0, implicit-def $eflags
+    DBG_VALUE %8, $noreg, !503, !17, debug-location !504
+    JCC_1 %bb.1.nou, 4, implicit $eflags
+    JMP_1 %bb.2.exit
+
+  bb.1.nou:
+    successors: %bb.2.exit
+
+    ; This block should receive the sunk copies and DBG_VALUE
+    ; CHECK-LABEL: bb.1.nou:
+    ; CHECK:       [[T6COPY1:%[0-9]+]]:gr64 = MOV64ri 0
+    ; CHECK-NEXT:  [[T6COPY2:%[0-9]+]]:gr64 = COPY [[T6COPY1]]
+    ; CHECK-NEXT:  [[T6COPY3:%[0-9]+]]:gr64 = COPY [[T6COPY2]]
+    ; CHECK-NEXT:  DBG_VALUE [[T6COPY3]], $noreg, [[VAR6NUM]]
+    ; CHECK-NEXT:  ADD64ri8
+    ; CHECK-NEXT:  JMP_1
+    %1:gr64 = ADD64ri8 %8, 4, implicit-def dead $eflags
+    JMP_1 %bb.2.exit
+
+  bb.2.exit:
+    $rax = MOV64ri 1
+    RET 0
+...