MachineSink debug invariance

[markus]

Summary

https://github.com/llvm/llvm-project/issues/55914

When counting instructions to compare with threshold debug instructions need to be ignored in order to be invariant wrt to debuginfo

[markus]

Should add a .mir test

llvm/lib/CodeGen/MachineSink.cpp

271

Don't we already have some utility function for this?

[Orlando]

Should add a .mir test

+1

This change looks ok to me but FTR I haven't touched the MachineSink pass before.

llvm/lib/CodeGen/MachineSink.cpp

271

It looks like we have .instructionsWithoutDebug() and .sizeWithoutDebug() for BasicBlock but I'm not sure if there's an equivalent for MachineBasicBlock. Maybe it'd be worth adding to MachineBasicBlock?

274

Should this be .isMetaInstr() (rather than .isDebugInstr()) to cover other non-debug that do not correspond to executable instructions?

[markus]

Add MachineBasicBlock::sizeWithoutDebug() to make more similar to IR.

[markus]

llvm/lib/CodeGen/MachineSink.cpp

274

Not sure but the way we do it now should be equivalent to how it works in BasicBlock::sizeWithoutDebug() which I guess is the way it should be.

[Orlando]

The code changes look good to me, so just waiting for the test before approving now.

[jmorse]

Also LGTM with a regression test, thanks for finding this.

[fhahn]

llvm/lib/CodeGen/MachineBasicBlock.cpp

1622

One issue with this helper is that it needs to iterate over all instructions in the block to count them and the limit is used to decide whether the block is too big to process.

Not sure there's a good alternative, but maybe have something like sizeWIthoutDebugLargerThan(x) so we can at least bail out once the limit is reached.

[jmorse]

llvm/lib/CodeGen/MachineBasicBlock.cpp

1622

IIUC, basic block size is ilist size, which is already linear time anyway, so this wouldn't be a regression. That being said, putting a bound on this would be a neat extension.

[markus]

Added lit-test.

[markus]

llvm/lib/CodeGen/MachineBasicBlock.cpp

1622

Agree that it would be better to limit the number of instructions scanned but I worry that introducing such a function in MachineBasicBlock would make it slightly unsymmetric wrt its IR equivalent. Maybe it is worth it though, I can't really tell.

[Orlando]

The test LGTM - I'll leave it to @jmorse or @fhahn to accept when a consensus is reached on whether a bounded version of sizeWithoutDebug should be added or not.

[markus]

Fixed typo in lit-test.

[markus]

MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit)

[markus]

ping

[jmorse]

LGTM, adding a size-with-limit method looks good too.

llvm/include/llvm/CodeGen/MachineBasicBlock.h

public:
 
   using iterator = MachineInstrBundleIterator<MachineInstr>;
   using const_iterator = MachineInstrBundleIterator<const MachineInstr>;
   using reverse_iterator = MachineInstrBundleIterator<MachineInstr, true>;
   using const_reverse_iterator =
       MachineInstrBundleIterator<const MachineInstr, true>;
 
   unsigned size() const { return (unsigned)Insts.size(); }
+  bool sizeWithoutDebugLargerThan(unsigned Limit) const;
   bool empty() const { return Insts.empty(); }
 
   MachineInstr       &instr_front()       { return Insts.front(); }
   MachineInstr       &instr_back()        { return Insts.back();  }
   const MachineInstr &instr_front() const { return Insts.front(); }
   const MachineInstr &instr_back()  const { return Insts.back();  }
 
   MachineInstr       &front()             { return Insts.front(); }

llvm/lib/CodeGen/MachineBasicBlock.cpp

if (MF.getFunction().hasPersonalityFn()) {
     auto PersonalityFn = MF.getFunction().getPersonalityFn();
     ExceptionPointer = TLI.getExceptionPointerRegister(PersonalityFn);
     ExceptionSelector = TLI.getExceptionSelectorRegister(PersonalityFn);
   }
 
   return liveout_iterator(*this, ExceptionPointer, ExceptionSelector, false);
 }
 
+bool MachineBasicBlock::sizeWithoutDebugLargerThan(unsigned Limit) const {
+  unsigned Cntr = 0;
+  auto R = instructionsWithoutDebug(begin(), end());
+  for (auto I = R.begin(), E = R.end(); I != E; ++I) {
+    if (++Cntr > Limit)
+      return true;
+  }
+  return false;
+}
+
 const MBBSectionID MBBSectionID::ColdSectionID(MBBSectionID::SectionType::Cold);
 const MBBSectionID
     MBBSectionID::ExceptionSectionID(MBBSectionID::SectionType::Exception);

llvm/lib/CodeGen/MachineSink.cpp

INITIALIZE_PASS_BEGIN(MachineSinking, DEBUG_TYPE,
                       "Machine code sinking", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(MachineSinking, DEBUG_TYPE,
                     "Machine code sinking", false, false)
 
 bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr &MI,
                                                      MachineBasicBlock *MBB) {
   if (!MI.isCopy())
     return false;
 
   Register SrcReg = MI.getOperand(1).getReg();
   Register DstReg = MI.getOperand(0).getReg();
   if (!Register::isVirtualRegister(SrcReg) ||
       !Register::isVirtualRegister(DstReg) || !MRI->hasOneNonDBGUse(SrcReg))
     return false;
 
   const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg);
for (MachineBasicBlock *BB : depth_first(From)) {
     HandledBlocks.insert(BB);
     // To post dominates BB, it must be a path from block From.
     if (PDT->dominates(To, BB)) {
       if (!HandledDomBlocks.count(BB))
         HandledDomBlocks.insert(BB);
 
       // If this BB is too big or the block number in straight line between From
       // and To is too big, stop searching to save compiling time.
-      if (BB->size() > SinkLoadInstsPerBlockThreshold ||
+      if (BB->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold) ||
           HandledDomBlocks.size() > SinkLoadBlocksThreshold) {
         for (auto *DomBB : HandledDomBlocks) {
           if (DomBB != BB && DT->dominates(DomBB, BB))
             HasStoreCache[std::make_pair(DomBB, To)] = true;
           else if(DomBB != BB && DT->dominates(BB, DomBB))
             HasStoreCache[std::make_pair(From, DomBB)] = true;
         }
         HasStoreCache[BlockPair] = true;
if (!SinkBlock) {
     LLVM_DEBUG(dbgs() << "CycleSink: Not sinking, can't find sink block.\n");
     return false;
   }
   if (SinkBlock == Preheader) {
     LLVM_DEBUG(
         dbgs() << "CycleSink: Not sinking, sink block is the preheader\n");
     return false;
   }
-  if (SinkBlock->size() > SinkLoadInstsPerBlockThreshold) {
+  if (SinkBlock->sizeWithoutDebugLargerThan(SinkLoadInstsPerBlockThreshold)) {
     LLVM_DEBUG(
         dbgs() << "CycleSink: Not Sinking, block too large to analyse.\n");
     return false;
   }
 
   LLVM_DEBUG(dbgs() << "CycleSink: Sinking instruction!\n");
   SinkBlock->splice(SinkBlock->SkipPHIsAndLabels(SinkBlock->begin()), Preheader,
                     I);

llvm/test/CodeGen/X86/machinesink-debug-inv-0.mir

+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64 -machine-sink-load-instrs-threshold=2 -run-pass=machine-sink %s -o - | FileCheck %s
+# RUN: llc -mtriple=x86_64 -machine-sink-load-instrs-threshold=2 -run-pass=mir-debugify,machine-sink,mir-strip-debug %s -o - | FileCheck %s
+
+# Verify that machine-sink pass is debug invariant wrt to given input. Since
+# the pass examines MemOperands the IR is required for the original bug to
+# trigger.
+
+--- |
+  @e = global i32 0, align 1
+  @d = global i32 0, align 1
+  @f = global i32 0, align 1
+  @g = global i32 0, align 1
+
+  define i32 @l() {
+  entry:
+    br label %for.body
+
+  for.body:                                         ; preds = %h.exit, %entry
+    %cmp = phi i1 [ true, %entry ], [ false, %h.exit ]
+    %0 = load i32, ptr @d, align 1
+    %tobool61.not.i = icmp eq i32 %0, 0
+    %e.promoted44.i = load i32, ptr @e, align 1
+    br i1 %tobool61.not.i, label %h.exit, label %for.cond13.preheader.preheader.i
+
+  for.cond13.preheader.preheader.i:                 ; preds = %for.body
+    %1 = load i32, ptr @f, align 1
+    store i32 %1, ptr @g, align 1
+    br label %h.exit
+
+  h.exit:                                           ; preds = %for.cond13.preheader.preheader.i, %for.body
+    %.us-phi50.i = or i32 %e.promoted44.i, 4
+    store i32 %.us-phi50.i, ptr @e, align 1
+    br i1 %cmp, label %for.body, label %for.end
+
+  for.end:                                          ; preds = %h.exit
+    ret i32 undef
+  }
+...
+---
+name:            l
+alignment:       16
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr8 }
+  - { id: 1, class: gr32 }
+  - { id: 2, class: gr8 }
+  - { id: 3, class: gr64 }
+  - { id: 4, class: gr64 }
+  - { id: 5, class: gr64 }
+  - { id: 6, class: gr32 }
+  - { id: 7, class: gr64 }
+  - { id: 8, class: gr8 }
+  - { id: 9, class: gr32 }
+  - { id: 10, class: gr64 }
+  - { id: 11, class: gr32 }
+  - { id: 12, class: gr32 }
+frameInfo:
+  maxAlignment:    1
+machineFunctionInfo: {}
+body:             |
+  ; CHECK-LABEL: name: l
+  ; CHECK: bb.0.entry:
+  ; CHECK-NEXT:   successors: %bb.1(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV8ri:%[0-9]+]]:gr8 = MOV8ri 1
+  ; CHECK-NEXT:   [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @d, $noreg :: (load (s64) from got)
+  ; CHECK-NEXT:   [[MOV64rm1:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @e, $noreg :: (load (s64) from got)
+  ; CHECK-NEXT:   [[MOV64rm2:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @f, $noreg :: (load (s64) from got)
+  ; CHECK-NEXT:   [[MOV64rm3:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @g, $noreg :: (load (s64) from got)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1.for.body:
+  ; CHECK-NEXT:   successors: %bb.3(0x30000000), %bb.2(0x50000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[PHI:%[0-9]+]]:gr8 = PHI [[MOV8ri]], %bb.0, %8, %bb.3
+  ; CHECK-NEXT:   CMP32mi8 [[MOV64rm]], 1, $noreg, 0, $noreg, 0, implicit-def $eflags :: (dereferenceable load (s32) from @d, align 1)
+  ; CHECK-NEXT:   JCC_1 %bb.3, 4, implicit $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2.for.cond13.preheader.preheader.i:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32rm:%[0-9]+]]:gr32 = MOV32rm [[MOV64rm2]], 1, $noreg, 0, $noreg :: (dereferenceable load (s32) from @f, align 1)
+  ; CHECK-NEXT:   MOV32mr [[MOV64rm3]], 1, $noreg, 0, $noreg, killed [[MOV32rm]] :: (store (s32) into @g, align 1)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3.h.exit:
+  ; CHECK-NEXT:   successors: %bb.1(0x7c000000), %bb.4(0x04000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32rm1:%[0-9]+]]:gr32 = MOV32rm [[MOV64rm1]], 1, $noreg, 0, $noreg :: (dereferenceable load (s32) from @e, align 1)
+  ; CHECK-NEXT:   [[OR32ri8_:%[0-9]+]]:gr32 = OR32ri8 [[MOV32rm1]], 4, implicit-def dead $eflags
+  ; CHECK-NEXT:   MOV32mr [[MOV64rm1]], 1, $noreg, 0, $noreg, killed [[OR32ri8_]] :: (store (s32) into @e, align 1)
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr8 = COPY [[MOV32r0_]].sub_8bit
+  ; CHECK-NEXT:   TEST8ri [[PHI]], 1, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.1, 5, implicit $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4.for.end:
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:gr32 = IMPLICIT_DEF
+  ; CHECK-NEXT:   $eax = COPY [[DEF]]
+  ; CHECK-NEXT:   RET 0, $eax
+  bb.0.entry:
+    %2:gr8 = MOV8ri 1
+    %3:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @d, $noreg :: (load (s64) from got)
+    %4:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @e, $noreg :: (load (s64) from got)
+    %5:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @f, $noreg :: (load (s64) from got)
+    %7:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @g, $noreg :: (load (s64) from got)
+
+  bb.1.for.body:
+    successors: %bb.3(0x30000000), %bb.2(0x50000000)
+
+    %0:gr8 = PHI %2, %bb.0, %8, %bb.3
+    CMP32mi8 %3, 1, $noreg, 0, $noreg, 0, implicit-def $eflags :: (dereferenceable load (s32) from @d, align 1)
+    %1:gr32 = MOV32rm %4, 1, $noreg, 0, $noreg :: (dereferenceable load (s32) from @e, align 1)
+    JCC_1 %bb.3, 4, implicit $eflags
+    JMP_1 %bb.2
+
+  bb.2.for.cond13.preheader.preheader.i:
+    %6:gr32 = MOV32rm %5, 1, $noreg, 0, $noreg :: (dereferenceable load (s32) from @f, align 1)
+    MOV32mr %7, 1, $noreg, 0, $noreg, killed %6 :: (store (s32) into @g, align 1)
+
+  bb.3.h.exit:
+    successors: %bb.1(0x7c000000), %bb.4(0x04000000)
+
+    %9:gr32 = OR32ri8 %1, 4, implicit-def dead $eflags
+    MOV32mr %4, 1, $noreg, 0, $noreg, killed %9 :: (store (s32) into @e, align 1)
+    %11:gr32 = MOV32r0 implicit-def dead $eflags
+    %8:gr8 = COPY %11.sub_8bit
+    TEST8ri %0, 1, implicit-def $eflags
+    JCC_1 %bb.1, 5, implicit $eflags
+    JMP_1 %bb.4
+
+  bb.4.for.end:
+    %12:gr32 = IMPLICIT_DEF
+    $eax = COPY %12
+    RET 0, $eax
+...