[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

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

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

1182

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

[aprantl]

lib/CodeGen/MachineSink.cpp

960

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

1129

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

[rnk]

lib/CodeGen/MachineSink.cpp

960

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

nit: unnecessary newline at L1116

1130

Can you get away with using MI->isDebugInstr ?

1140

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

1145

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

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

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

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

[aprantl]

one more documentation request inline.

lib/CodeGen/MachineSink.cpp

737

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

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.
 static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo,
-                        MachineBasicBlock::iterator InsertPos) {
-  // Collect matching debug values.
+                        MachineBasicBlock::iterator InsertPos,
+                        SmallVectorImpl<MachineInstr *> *DbgVals = nullptr) {
+  // If debug values provided, use those, otherwise collect
   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
+  std::multimap<unsigned, 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 potentially have to sink this DBG_VALUE if its operand is sunk, and
+    // it may not be anywhere near the register def
+    if (MI->isDebugValue()) {
+      auto &MO = MI->getOperand(0);
+      if (MO.isReg() && TRI->isPhysicalRegister(MO.getReg())) {
+        // Bail if sink would be rejected, rather than accumulate lots of
+        // DBG_VALUEs
+        if (hasRegisterDependency(MI, UsedOpsInCopy, DefedRegsInCopy,
+                                  ModifiedRegUnits, UsedRegUnits))
+          continue;
+
+        // Record debug use of this register
+        SeenDbgInstrs.insert(std::make_pair(MO.getReg(), 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();
+      auto Range = SeenDbgInstrs.equal_range(reg);
+      for (auto It = Range.first; It != Range.second; It++)
+        DbgValsToSink.push_back(It->second);
+    }
+
     // 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;
 }
 

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: the DBG_VALUE on ebx below is not sunk with the def of ebx in PR38952,
+  ; check that ebx sinks and the DBG_VALUE follows it.
+
+    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
+
+...