[DebugInfo] Make postra sinking of DBG_VALUEs safe in the presence of subregisters

[jmorse]

Summary

Currently the machine instruction sinker identifies DBG_VALUE insts that also need to sink by comparing register numbers. Unfortunately this isn't safe, because (after register allocation) a DBG_VALUE may read a register that aliases what's being sunk. To fix this, identify the DBG_VALUEs that need to sink by recording & examining their register units. Register units gives us the following guarantee:

"Two registers overlap if and only if they have a common register unit" [MCRegisterInfo.h]

Thus we can always identify aliasing DBG_VALUEs if the set of register units read by the DBG_VALUE, and the register units of the instruction being sunk, intersect. (MachineSink already uses classes like "LiveRegUnits" for determining sinking validity anyway).

The test added checks for super and subregister DBG_VALUE reads of a sunk copy being sunk as well.

[aprantl]

lib/CodeGen/MachineSink.cpp

1208 ↗

(On Diff #186683)

I think you may need to sort here to avoid nondeterministic output when iterating over a Set?

[jmorse]

Sort dbg-values to be sunk to ensure determinism, sprinkle -NEXT on some CHECKS to strengthen test.

[jmorse]

lib/CodeGen/MachineSink.cpp

1208 ↗

(On Diff #186683)

Good catch, I've added a sort to avoid relying on the sets order.

[jmorse]

Archaeology-ping: this patch avoids super/sub-register sinking leading to DBG_VALUEs referring to the wrong location, would be good for LLVM-9.

(Update is to add a triple to the command line, I've already tripped up the buildbots enough).

[vsk]

This test looks reasonable. Is D58238 the only MachineSink change you have queued up?

[jmorse]

In D58191#1579194, @vsk wrote:

This test looks reasonable. Is D58238 the only MachineSink change you have queued up?

There's also D58386, and it looks like I missed that Adrian put comments on there -- I'll freshen that up shortly.

(Many thanks for giving these patches a look!)

[jmorse]

Facepalm: it looks like I mucked up the diff before uploading, the patch originally came with this change to MachineSink, not just the test. Oooff.

[vsk]

lib/CodeGen/MachineSink.cpp

1208 ↗

(On Diff #186683)

Naive question, but: is llvm::sort sorting by address-of-the-MI here, or something else? (Just checking -- if it's the former that's not quite deterministic, and maybe a SetVector is called for)

[jmorse]

/Really/ avoid nondeterminism this time.

[jmorse]

lib/CodeGen/MachineSink.cpp

1208 ↗

(On Diff #186683)

*blinks* *double-takes* Clearly I had a serious caffeine deficiency when writing that code. Updated to use a SetVector as recommended. Single sunk instructions tend to only have a few DBG_VALUEs attached, so I'm not worried about the performance implications.

I'll continue on and land this as I think this qualifies as a trivial update to the patch.

llvm/lib/CodeGen/MachineSink.cpp

 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/IR/BasicBlock.h"
-#include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/BranchProbability.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::NoVRegs);
   }
 
 private:
   /// Track which register units have been modified and used.
   LiveRegUnits ModifiedRegUnits, UsedRegUnits;
 
-  /// Track DBG_VALUEs of (unmodified) register units.
-  DenseMap<unsigned, TinyPtrVector<MachineInstr*>> SeenDbgInstrs;
+  /// Track DBG_VALUEs of (unmodified) register units. Each DBG_VALUE has an
+  /// entry in this map for each unit it touches.
+  DenseMap<unsigned, TinyPtrVector<MachineInstr *>> SeenDbgInstrs;
 
   /// Sink Copy instructions unused in the same block close to their uses in
   /// successors.
   bool tryToSinkCopy(MachineBasicBlock &BB, MachineFunction &MF,
                      const TargetRegisterInfo *TRI, const TargetInstrInfo *TII);
 };
 } // namespace
 
if (MO.isDef()) {
         break;
       }
       UsedOpsInCopy.push_back(i);
     }
   }
   return HasRegDependency;
 }
 
+static SmallSet<unsigned, 4> getRegUnits(unsigned Reg,
+                                         const TargetRegisterInfo *TRI) {
+  SmallSet<unsigned, 4> RegUnits;
+  for (auto RI = MCRegUnitIterator(Reg, TRI); RI.isValid(); ++RI)
+    RegUnits.insert(*RI);
+  return RegUnits;
+}
+
 bool PostRAMachineSinking::tryToSinkCopy(MachineBasicBlock &CurBB,
                                          MachineFunction &MF,
                                          const TargetRegisterInfo *TRI,
                                          const TargetInstrInfo *TII) {
   SmallPtrSet<MachineBasicBlock *, 2> SinkableBBs;
   // FIXME: For now, we sink only to a successor which has a single predecessor
   // so that we can directly sink COPY instructions to the successor without
   // adding any new block or branch instruction.
if (MI->isDebugValue()) {
       auto &MO = MI->getOperand(0);
       if (MO.isReg() && Register::isPhysicalRegister(MO.getReg())) {
         // Bail if we can already tell the sink would be rejected, rather
         // than needlessly accumulating lots of DBG_VALUEs.
         if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
                                   ModifiedRegUnits, UsedRegUnits))
           continue;
 
-        // Record debug use of this register.
-        SeenDbgInstrs[MO.getReg()].push_back(MI);
+        // Record debug use of each reg unit.
+        SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
+        for (unsigned Reg : Units)
+          SeenDbgInstrs[Reg].push_back(MI);
       }
       continue;
     }
 
     if (MI->isDebugInstr())
       continue;
 
     // Do not move any instruction across function call.
for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
     if (!SuccBB) {
       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
                                         TRI);
       continue;
     }
     assert((SuccBB->pred_size() == 1 && *SuccBB->pred_begin() == &CurBB) &&
            "Unexpected predecessor");
 
-    // Collect DBG_VALUEs that must sink with this copy.
+    // Collect DBG_VALUEs that must sink with this copy. We've previously
+    // recorded which reg units that DBG_VALUEs read, if this instruction
+    // writes any of those units then the corresponding DBG_VALUEs must sink.
+    SetVector<MachineInstr *> DbgValsToSinkSet;
     SmallVector<MachineInstr *, 4> DbgValsToSink;
     for (auto &MO : MI->operands()) {
       if (!MO.isReg() || !MO.isDef())
         continue;
-      Register reg = MO.getReg();
-      for (auto *MI : SeenDbgInstrs.lookup(reg))
-        DbgValsToSink.push_back(MI);
+
+      SmallSet<unsigned, 4> Units = getRegUnits(MO.getReg(), TRI);
+      for (unsigned Reg : Units)
+        for (auto *MI : SeenDbgInstrs.lookup(Reg))
+          DbgValsToSinkSet.insert(MI);
     }
+    DbgValsToSink.insert(DbgValsToSink.begin(), DbgValsToSinkSet.begin(),
+                         DbgValsToSinkSet.end());
 
     // Clear the kill flag if SrcReg is killed between MI and the end of the
     // block.
     clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI);
     MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI();
     performSink(*MI, *SuccBB, InsertPos, &DbgValsToSink);
     updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
 

llvm/test/DebugInfo/MIR/X86/postra-subreg-sink.mir

+# RUN: llc  -mtriple=x86_64-unknown-unknown %s -run-pass=postra-machine-sink -o - | FileCheck %s
+# Test that when we run the postra machine sinker (which sinks COPYs), that
+# DBG_VALUEs of both sub and super-registers that depend on such COPYs are
+# sunk with them.
+--- |
+  ; Module stripped of everything, MIR below is what's interesting
+  ; ModuleID = '<stdin>'
+  source_filename = "justacall.cpp"
+  target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+  target triple = "x86_64-unknown-linux-gnu"
+
+  ; Function Attrs: noinline norecurse nounwind uwtable
+  define dso_local i32 @main(i32 %argc, i8** nocapture readnone %argv) !dbg !14 {
+  entry:
+    br label %return
+  return:
+    ret i32 0
+  }
+
+  !llvm.dbg.cu = !{!2}
+  !llvm.module.flags = !{!1, !1000}
+
+  !0 = !{!"dummy metadata"}
+  !1 = !{i32 2, !"Dwarf Version", i32 4}
+  !1000 = !{i32 2, !"Debug Info Version", i32 3}
+  !2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, nameTableKind: None)
+  !3 = !DIFile(filename: "justacall.cpp", directory: "/tmp")
+  !4 = !{}
+  !7 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !8 = !DIBasicType(name: "int", size: 8, encoding: DW_ATE_signed)
+  !9 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed)
+  !14 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 7, type: !15, isLocal: false, isDefinition: true, scopeLine: 8, flags: DIFlagPrototyped, isOptimized: true, unit: !2, retainedNodes: !20)
+  !15 = !DISubroutineType(types: !16)
+  !16 = !{!7, !7}
+  !20 = !{!21, !22, !23, !24}
+  !21 = !DILocalVariable(name: "argc", arg: 1, scope: !14, file: !3, line: 7, type: !7)
+  !22 = !DILocalVariable(name: "foo", scope: !14, file: !3, line: 7, type: !8)
+  !23 = !DILocalVariable(name: "bar", scope: !14, file: !3, line: 7, type: !7)
+  !24 = !DILocalVariable(name: "baz", scope: !14, file: !3, line: 7, type: !9)
+  !100 = !DILocation(line: 1, scope: !14)
+
+...
+---
+name:            main
+tracksRegLiveness: true
+registers:
+liveins:
+  - { reg: '$edi', virtual-reg: '' }
+frameInfo:
+  hasCalls:        true
+fixedStack:
+stack:
+constants:
+body:             |
+
+  ; CHECK: ![[ARGVAR:[0-9]+]] = !DILocalVariable(name: "argc",
+  ; CHECK: ![[FOOVAR:[0-9]+]] = !DILocalVariable(name: "foo",
+  ; CHECK: ![[BARVAR:[0-9]+]] = !DILocalVariable(name: "bar",
+  ; CHECK: ![[BAZVAR:[0-9]+]] = !DILocalVariable(name: "baz",
+
+  ; In the following code, the:
+  ;   DBG_VALUE of $edi should not sink: it's an argument
+  ;   DBG_VALUE of $ebx should sink: it's a standard copy
+  ;   DBG_VALUE of $bx should sink: a write of its superregister sinks
+  ;   DBG_VALUE of $ecx should sink: a write of one of its subregisters sinks
+
+  ; CHECK-LABEL: name: main
+  ; CHECK: bb.0.entry:
+  ; CHECK:   successors: %bb.1(0x80000000)
+  ; CHECK:   liveins: $edi
+  ; CHECK:   DBG_VALUE $edi, $noreg, ![[BARVAR]]
+  ; CHECK-NEXT:   renamable $cl = MOV8ri 1
+  ; CHECK-NEXT:   JMP_1 %bb.1
+  ; CHECK: bb.1.return:
+  ; CHECK:   liveins: $cl, $edi
+  ; CHECK:   renamable $ebx = COPY $edi
+  ; CHECK-NEXT:   DBG_VALUE $bx, $noreg, ![[BAZVAR]]
+  ; CHECK-NEXT:   DBG_VALUE $ebx, $noreg, ![[ARGVAR]]
+  ; CHECK-NEXT:   renamable $ch = COPY renamable $cl
+  ; CHECK-NEXT:   DBG_VALUE $ecx, $noreg, ![[FOOVAR]]
+  ; CHECK-NEXT:   $rdi = MOV32ri64 0
+  ; CHECK-NEXT:   $eax = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT:   RET 0, $eax
+  bb.0.entry:
+    successors: %bb.1(0x40000000)
+    liveins: $edi
+
+    DBG_VALUE $edi, $noreg, !23, !DIExpression(), debug-location !100
+    renamable $ebx = COPY $edi
+    DBG_VALUE $ebx, $noreg, !21, !DIExpression(), debug-location !100
+    DBG_VALUE $bx,  $noreg, !24, !DIExpression(), debug-location !100
+    renamable $cl = MOV8ri 1, debug-location !100
+    renamable $ch = COPY renamable $cl
+    DBG_VALUE $ecx, $noreg, !22, !DIExpression(), debug-location !100
+    JMP_1 %bb.1
+
+  bb.1.return:
+    liveins: $ebx, $ch
+
+    $rdi = MOV32ri64 0
+    $eax = MOV32r0 implicit-def dead $eflags
+    RET 0, $eax
+
+...