[DebugInfo] Correctly sink DBG_VALUEs in postra-machine-sink

[jmorse]

Summary

As reported in PR38952 [0] the postRA machine-code sinking of copies relies on relevant DBG_VALUEs always immediately following the instruction that's being sunk. The PR has a counterexample to this, and DBG_VALUE location does not seem guaranteed after the register allocator runs.

Because postra-machine-sink walks backwards through each BB looking for copies to sink, it will walk past any DBG_VALUE that refers to a copy it subsequently sinks. This means we don't need to scan the whole block looking for DBG_VALUEs, only record which ones have already been seen.

This patch collects seen DBG_VALUEs into a PhysRegister : DBG_VALUE multimap, and hands a vector of relevant DBG_VALUEs down to performSink if a copy gets sunk. Multimap is expensive, but there are no guarantees AFAIK about what order we'll encounter DBG_VALUEs in or what registers they may refer to, so I can't see what else to use.

Highly relevant to this patch is the discussion in [1] regarding the validity of sinking DBG_VALUEs past other DBG_VALUEs of the same variable, re-ordering the appearance of values for the user. My summary would be "yes that's a problem, but it's currently an acceptable tradeoff" (YMMV).

Building debug clang+llvm using another clang+llvm with and without this patch, completes in the same amount of time (give or take a second).

[0] https://bugs.llvm.org/show_bug.cgi?id=38952
[1] https://reviews.llvm.org/D45637

[jmorse]

Because it's not completely clear in the summary: the reliance on DBG_VALUEs following the insn being sunk is caused by performSink's use of MachineInstr::collectDebugValues

[probinson]

Presumably this addresses the bad debugging experience for the sample from the PR; does it have any other good/bad effect on the Dexter corpus?

test/CodeGen/X86/pr38952.mir

72 ↗

(On Diff #172198)

The way this comment is written looks like an alternate CHECK line, except it isn't. You can just say "Test that the DBG_VALUE ..." and avoid the potential confusion.

[probinson]

Please review all comments to ensure proper punctuation. There are a lot of missing full-stops.

lib/CodeGen/MachineSink.cpp

741 ↗

(On Diff #172198)

Comment needs to finish the thought; or is it just missing a full-stop?

1182 ↗

(On Diff #172198)

Did clang-format-diff let you do this? Normally 'continue' would be on the next line.

[aprantl]

lib/CodeGen/MachineSink.cpp

960 ↗

(On Diff #172198)

Would a (Small)DenseMap<SmallVector> be more efficient?

1129 ↗

(On Diff #172198)

Nitpick: Please always use full sentences in comments with a trailing .

[rnk]

lib/CodeGen/MachineSink.cpp

960 ↗

(On Diff #172198)

Peanut gallery: DenseMap of Small* things are usually not efficient. There is TinyPtrVector, though, which is optimized for this use case, so DenseMap<unsigned, TinyPtrVector<MachineInstr*>> is probably a good choice.

[mattd]

lib/CodeGen/MachineSink.cpp

1116 ↗

(On Diff #172198)

nit: unnecessary newline at L1116

1130 ↗

(On Diff #172198)

Can you get away with using MI->isDebugInstr ?

1140 ↗

(On Diff #172198)

As an alternative to insert, you can call emplace().
SeenDbgInstrs.emplace(MO.getReg(), MI);

1145 ↗

(On Diff #172198)

This condition might not be necessary since you will always continue in the previous conditional at L1130... if you update the conditional at L1130 to be isDebugInstr.

[jmorse]

Rewrite comments, use DenseMap<u, TinyPtrVector> instead of multimap

[jmorse]

Hi,

In D53992#1284437, @probinson wrote:

Presumably this addresses the bad debugging experience for the sample from the PR; does it have any other good/bad effect on the Dexter corpus?

Alas there's no other effect on the rest of the tests, only the original [0], although we also get the correct lifetime for the function argument now. (Previously it was "optimized out" everywhere after the start of the function).

[0] https://github.com/jmorse/dexter/blob/dextests/tests/nostdlib/llvm_passes/Vectorize/MissingArgVal/missingargval.cpp

lib/CodeGen/MachineSink.cpp

960 ↗

(On Diff #172198)

Now using the suggested container; running a Debug clang/llvm build again gave one faster time, one slower time, both within the margin of error. It looks like this container form will match the common case very well, and in the worst case be no worse than multimap.

1130 ↗

(On Diff #172198)

I don't believe so -- that matches DebugLabels as well which don't get sunk, so there'd need to be another condition filtering them out.

(NB, at this time I don't really know what DebugLabels are used for, so this opinion isn't based on any knowledge).

1140 ↗

(On Diff #172198)

(Container changed to one that doesn't have emplace).

[aprantl]

one more documentation request inline.

lib/CodeGen/MachineSink.cpp

737 ↗

(On Diff #172362)

Please document what the optional DbgVals parameter is for. The next time someone reads this function they will be very confused about it :-)

llvm/trunk/lib/CodeGen/MachineSink.cpp

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() == BaseReg;
 }
 
-/// Sink an instruction and its associated debug instructions.
+/// Sink an instruction and its associated debug instructions. If the debug
+/// instructions to be sunk are already known, they can be provided in DbgVals.
 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
-                        MachineBasicBlock::iterator InsertPos) {
-  // Collect matching debug values.
+                        MachineBasicBlock::iterator InsertPos,
+                        SmallVectorImpl<MachineInstr *> *DbgVals = nullptr) {
+  // If debug values are provided use those, otherwise call collectDebugValues.
   SmallVector<MachineInstr *, 2> DbgValuesToSink;
+  if (DbgVals)
+    DbgValuesToSink.insert(DbgValuesToSink.begin(),
+                           DbgVals->begin(), DbgVals->end());
+  else
     MI.collectDebugValues(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
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;
+
   /// 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
 
 char PostRAMachineSinking::ID = 0;
if (SinkableBBs.empty())
     return false;
 
   bool Changed = false;
 
   // Track which registers have been modified and used between the end of the
   // block and the current instruction.
   ModifiedRegUnits.clear();
   UsedRegUnits.clear();
+  SeenDbgInstrs.clear();
 
   for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) {
     MachineInstr *MI = &*I;
     ++I;
 
+    // Track the operand index for use in Copy.
+    SmallVector<unsigned, 2> UsedOpsInCopy;
+    // Track the register number defed in Copy.
+    SmallVector<unsigned, 2> DefedRegsInCopy;
+
+    // We must sink this DBG_VALUE if its operand is sunk. To avoid searching
+    // for DBG_VALUEs later, record them when they're encountered.
+    if (MI->isDebugValue()) {
+      auto &MO = MI->getOperand(0);
+      if (MO.isReg() && TRI->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);
+      }
+      continue;
+    }
+
     if (MI->isDebugInstr())
       continue;
 
     // Do not move any instruction across function call.
     if (MI->isCall())
       return false;
 
     if (!MI->isCopy() || !MI->getOperand(0).isRenamable()) {
       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
                                         TRI);
       continue;
     }
 
-    // Track the operand index for use in Copy.
-    SmallVector<unsigned, 2> UsedOpsInCopy;
-    // Track the register number defed in Copy.
-    SmallVector<unsigned, 2> DefedRegsInCopy;
-
     // Don't sink the COPY if it would violate a register dependency.
     if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
                               ModifiedRegUnits, UsedRegUnits)) {
       LiveRegUnits::accumulateUsedDefed(*MI, ModifiedRegUnits, UsedRegUnits,
                                         TRI);
       continue;
     }
     assert((!UsedOpsInCopy.empty() && !DefedRegsInCopy.empty()) &&
            "Unexpect SrcReg or DefReg");
     MachineBasicBlock *SuccBB =
         getSingleLiveInSuccBB(CurBB, SinkableBBs, DefedRegsInCopy, TRI);
     // Don't sink if we cannot find a single sinkable successor in which Reg
     // is live-in.
     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.
+    SmallVector<MachineInstr *, 4> DbgValsToSink;
+    for (auto &MO : MI->operands()) {
+      if (!MO.isReg() || !MO.isDef())
+        continue;
+      unsigned reg = MO.getReg();
+      for (auto *MI : SeenDbgInstrs.lookup(reg))
+        DbgValsToSink.push_back(MI);
+    }
+
     // 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);
+    performSink(*MI, *SuccBB, InsertPos, &DbgValsToSink);
     updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
 
     Changed = true;
     ++NumPostRACopySink;
   }
   return Changed;
 }
 

llvm/trunk/test/CodeGen/X86/pr38952.mir

+# RUN: llc %s -run-pass=postra-machine-sink -o - | FileCheck %s
+--- |
+  ; 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) local_unnamed_addr #0 {
+  entry:
+    br label %if.end
+  if.end:
+    br label %return
+  return:
+    ret i32 0
+  }
+
+  !0 = !{!"dummy metadata"}
+  !2 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !3, producer: "clang", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: None)
+  !3 = !DIFile(filename: "justacall.cpp", directory: "/tmp")
+  !4 = !{}
+  !5 = !{!0}
+  !7 = !DIBasicType(name: "int", size: 32, 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}
+  !21 = !DILocalVariable(name: "argc", arg: 1, scope: !14, file: !3, line: 7, type: !7)
+
+...
+---
+name:            main
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+failedISel:      false
+tracksRegLiveness: true
+hasWinCFI:       false
+registers:
+liveins:
+  - { reg: '$edi', virtual-reg: '' }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        true
+  stackProtector:  ''
+  maxCallFrameSize: 4294967295
+  cvBytesOfCalleeSavedRegisters: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+  localFrameSize:  0
+  savePoint:       ''
+  restorePoint:    ''
+fixedStack:
+stack:
+constants:
+body:             |
+  bb.0.entry:
+    successors: %bb.2(0x40000000), %bb.1(0x40000000)
+    liveins: $edi
+  
+  ; Test that the DBG_VALUE on ebx below is sunk with the def of ebx, despite
+  ; not being adjacent to the def, see PR38952
+
+    DBG_VALUE $edi, $noreg, !21, !DIExpression()
+    renamable $ebx = COPY $edi
+    renamable $eax = MOV32r0 implicit-def dead $eflags
+    DBG_VALUE $ebx, $noreg, !21, !DIExpression()
+    CMP32ri $edi, 255, implicit-def $eflags
+    JG_1 %bb.2, implicit killed $eflags
+    JMP_1 %bb.1
+  
+  bb.1.if.end:
+  ; CHECK-LABEL: bb.1.if.end
+    successors: %bb.2(0x80000000)
+    liveins: $ebx
+  
+  ; CHECK: $ebx = COPY $edi
+  ; CHECK-NEXT: DBG_VALUE $ebx
+    renamable $rdx = MOVSX64rr32 renamable $ebx
+    renamable $rdx = nsw SHL64ri killed renamable $rdx, 2, implicit-def dead $eflags
+    ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+    $rdi = MOV32ri64 0
+    $esi = MOV32r0 implicit-def dead $eflags
+    CALL64pcrel32 &memset, csr_64, implicit $rsp, implicit $ssp, implicit $rdi, implicit killed $esi, implicit $rdx, implicit-def $rsp, implicit-def $ssp, implicit-def dead $rax
+    ADJCALLSTACKUP64 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp
+  
+  bb.2.return:
+    liveins: $eax
+  
+    RET 0, $eax
+
+...