[MachineSink] Check block prologue interference

[critson]

Summary

Sinking must check for interference between the block prologue
and the instruction being sunk.
Specifically check for clobbering of uses by the prologue, and
overwrites to prologue defined registers by the sunk instruction.

[MatzeB]

What do you mean by "block prologue"? Can you tell me which of the 2 COPYs in your test is falsely moved with your test and which instruction clobbers the register?

(Intuitively I would expect a live-in value to be available after all PHI instructions so I don't see why there can be a clobber when something is inserted at the beginning of the basic block...)

[critson]

• Rebase on top of pre-committed test

[critson]

In D121277#3370730, @MatzeB wrote:

What do you mean by "block prologue"? Can you tell me which of the 2 COPYs in your test is falsely moved with your test and which instruction clobbers the register?

(Intuitively I would expect a live-in value to be available after all PHI instructions so I don't see why there can be a clobber when something is inserted at the beginning of the basic block...)

I have pre-committed the test, so the offending sink should now be obvious.

This occurs because SkipPHIsAndLabels skips block prologue instructions as determined by the target, something which is not obvious from the function name.
On AMDGPU the S_AND_SAVEEXEC_B64 is considered part of the block prologue because it is setting up the correct execution mask for the instructions in the block; however RA has assigned the register $sgpr4 to the destination of this instruction, effectively clobbering the source of the COPY being sunk.

[rampitec]

LGTM.

[critson]

In D121277#3373171, @rampitec wrote:

LGTM.

@rampitec was that also meant to be an accept?

[rampitec]

In D121277#3381121, @critson wrote:

In D121277#3373171, @rampitec wrote:

LGTM.

@rampitec was that also meant to be an accept?

That meant to be just LGTM, but I guess after some time passed accepted.

[ruiling]

I agree this issue should be fixed here. Machine sinking should check for register dependency between the sunk instruction and the prologue instruction in the successor block.
But I think there are two kinds of register dependency need to be checked:

a.) the definition of a register which would be used in successor prologue instruction.
b.) the instruction which has a source physical register being overwritten by successor prologue instruction.

I think you are fixing the second kind of dependency currently. Maybe check the first kind of dependency in the same change?
The first kind of def-use dependency should also apply to the pre-RA sinking.

I am not sure whether other uses of SkipPHIsXXX() in the backend would also need such kind of register dependency check, but I think that needs to be investigated separately.

Aside from this, whether we should treat a S_AND_XXX exec as prologue might change in the future. IMO, it is only S_OR_XXX exec like instructions which would activating more threads should really be treated as prologue instruction.

[arsenm]

llvm/lib/CodeGen/MachineSink.cpp

1855–1870

Is there not a helper for this somewhere?

[critson]

In D121277#3381838, @ruiling wrote:

I agree this issue should be fixed here. Machine sinking should check for register dependency between the sunk instruction and the prologue instruction in the successor block.
But I think there are two kinds of register dependency need to be checked:

a.) the definition of a register which would be used in successor prologue instruction.
b.) the instruction which has a source physical register being overwritten by successor prologue instruction.

I think you are fixing the second kind of dependency currently. Maybe check the first kind of dependency in the same change?
The first kind of def-use dependency should also apply to the pre-RA sinking.

Presumably (a) only applies to pre-RA sinking? As post-RA everything should be physical registers?
At the moment I think we are getting away without checking because most virtual registers are still unique from SSA form.
However, I agree the risk exists.

I am not sure whether other uses of SkipPHIsXXX() in the backend would also need such kind of register dependency check, but I think that needs to be investigated separately.

Agreed.

Aside from this, whether we should treat a S_AND_XXX exec as prologue might change in the future. IMO, it is only S_OR_XXX exec like instructions which would activating more threads should really be treated as prologue instruction.

Yes, it would be preferable to narrow the definition of prologue instructions in the long run.

[ruiling]

Try this. I don't know what would be the most likely pattern in real cases, this is just to show that sinking $sgpr0_sgpr1 definition instruction into successor block would break the register dependency of type (a).

---
name:            _amdgpu_ps_main
alignment:       1
tracksRegLiveness: true
registers:       []
liveins:
  - { reg: '$sgpr4', virtual-reg: '' }
body:             |
  bb.0:
    successors: %bb.1(0x80000000)
    liveins: $sgpr4, $sgpr5

    renamable $sgpr9 = COPY $sgpr4
    renamable $vgpr5 = IMPLICIT_DEF
    renamable $sgpr0_sgpr1 = COPY $sgpr4_sgpr5
    S_BRANCH %bb.1

  bb.1:
    successors: %bb.2(0x40000000), %bb.8(0x40000000)
    liveins: $sgpr6, $sgpr9, $sgpr0_sgpr1

    $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
    renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
    S_CBRANCH_EXECZ %bb.8, implicit $exec
    S_BRANCH %bb.2

  bb.2:
    successors: %bb.8(0x40000000)
    liveins: $sgpr6

    $m0 = COPY killed renamable $sgpr6
    S_BRANCH %bb.8

  bb.8:

    S_ENDPGM 0

...

[critson]

• Generalize to any target defined block prologue instruction interfering with a sink candidate
• Extend to pre-RA machine sink

[critson]

In D121277#3384816, @ruiling wrote:

Try this. I don't know what would be the most likely pattern in real cases, this is just to show that sinking $sgpr0_sgpr1 definition instruction into successor block would break the register dependency of type (a).

snipped

Thanks for this example. I used this as a basis for a test case, but used separate sources for the two COPY instructions.

llvm/lib/CodeGen/MachineSink.cpp

1855–1870

I could not see immediately find one.
Also the newer code is now special cased to only operate on target defined block prologue instructions, which is more efficient.

[ruiling]

Thanks for the change, mostly looks good to me. with only a few minor comments.

llvm/lib/CodeGen/MachineSink.cpp

1307

maybe start from BB->getFirstNonPHI()? so you don't need to pass PHI to isBasicBlockPrologue().

1324

Could you also return true if PI->modifiesRegister()? This is mainly for case like the sunk instruction define whole piece of the register, but there is some prologue instruction overwrite the sub-register. With this check, we would be much like what hasRegisterDependency() has done.

1851

May be better to move this log after the interference check?

[critson]

• Address case of sunk instruction clobbering register partially defined in block prologue

[ruiling]

To the best of my knowledge, this should work. But please wait one or two days in case others have more comment. Please also update commit message before push.

llvm/lib/CodeGen/MachineSink.cpp

1332

auto *DefOp = PI->findRegisterDefOperand(...);
if (DefOp && !DefOp->isDead())
  return true;

[critson]

• Incorporate reviewer feedback.

[critson]

Thanks!
I won't submit this for at least 72 hours.

llvm/lib/CodeGen/MachineSink.cpp

1324

Yes, I guess this edge case exists.
We need to be careful not to consider dead defs, as AMDGPU block prologue instructions often define $scc as a side-effect.

1851

I don't think that makes sense, then the debug output will not indicate what was rejected due to interference. The pre-RA sink outputs this information before performing its checks.

llvm/lib/CodeGen/MachineSink.cpp

bool MachineSinking::SinkIntoLoop(MachineLoop *L, MachineInstr &I) {
 
   // The instruction is moved from its basic block, so do not retain the
   // debug information.
   assert(!I.isDebugInstr() && "Should not sink debug inst");
   I.setDebugLoc(DebugLoc());
   return true;
 }
 
+/// Return true if a target defined block prologue instruction interferes
+/// with a sink candidate.
+static bool blockPrologueInterferes(MachineBasicBlock *BB,
+                                    MachineBasicBlock::iterator End,
+                                    MachineInstr &MI,
+                                    const TargetRegisterInfo *TRI,
+                                    const TargetInstrInfo *TII,
+                                    const MachineRegisterInfo *MRI) {
+  if (BB->begin() == End)
+    return false; // no prologue
+  for (MachineBasicBlock::iterator PI = BB->getFirstNonPHI(); PI != End; ++PI) {
+    // Only check target defined prologue instructions
+    if (!TII->isBasicBlockPrologue(*PI))
+      continue;
+    for (auto &MO : MI.operands()) {
+      if (!MO.isReg())
+        continue;
+      Register Reg = MO.getReg();
+      if (!Reg)
+        continue;
+      if (MO.isUse()) {
+        if (Register::isPhysicalRegister(Reg) &&
+            (TII->isIgnorableUse(MO) || (MRI && MRI->isConstantPhysReg(Reg))))
+          continue;
+        if (PI->modifiesRegister(Reg, TRI))
+          return true;
+      } else {
+        if (PI->readsRegister(Reg, TRI))
+          return true;
+        // Check for interference with non-dead defs
+        auto *DefOp = PI->findRegisterDefOperand(Reg, false, true, TRI);
+        if (DefOp && !DefOp->isDead())
+          return true;
+      }
+    }
+  }
+  return false;
+}
+
 /// SinkInstruction - Determine whether it is safe to sink the specified machine
 /// instruction out of its current block into a successor.
 bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,
                                      AllSuccsCache &AllSuccessors) {
   // Don't sink instructions that the target prefers not to sink.
   if (!TII->shouldSink(MI))
     return false;
 
if (!Status)
                            "break critical edge\n");
     // The instruction will not be sunk this time.
     return false;
   }
 
   // Determine where to insert into. Skip phi nodes.
   MachineBasicBlock::iterator InsertPos =
       SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());
+  if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) {
+    LLVM_DEBUG(dbgs() << " *** Not sinking: prologue interference\n");
+    return false;
+  }
 
   // Collect debug users of any vreg that this inst defines.
   SmallVector<MIRegs, 4> DbgUsersToSink;
   for (auto &MO : MI.operands()) {
     if (!MO.isReg() || !MO.isDef() || !MO.getReg().isVirtual())
       continue;
     if (!SeenDbgUsers.count(MO.getReg()))
       continue;
for (auto &MO : MI.operands()) {
           auto &Regs = DbgValsToSinkMap[MIRegs.first];
           for (unsigned Reg : MIRegs.second)
             Regs.push_back(Reg);
         }
       }
     }
     auto DbgValsToSink = DbgValsToSinkMap.takeVector();
 
+    LLVM_DEBUG(dbgs() << "Sink instr " << MI << "\tinto block " << *SuccBB);
+
+    MachineBasicBlock::iterator InsertPos =
+        SuccBB->SkipPHIsAndLabels(SuccBB->begin());
+    if (blockPrologueInterferes(SuccBB, InsertPos, MI, TRI, TII, nullptr)) {
+      LLVM_DEBUG(
+          dbgs() << " *** Not sinking: prologue interference\n");
+      continue;
+    }
+
     // 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->SkipPHIsAndLabels(SuccBB->begin());
     performSink(MI, *SuccBB, InsertPos, DbgValsToSink);
     updateLiveIn(&MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy);
 
     Changed = true;
     ++NumPostRACopySink;
   }
   return Changed;
 }
 
 bool PostRAMachineSinking::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
 
   bool Changed = false;
   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();

llvm/test/CodeGen/AMDGPU/sink-after-control-flow-postra.mir

 # NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
 # RUN: llc -march=amdgcn -mcpu=gfx1010 -verify-machineinstrs -run-pass=postra-machine-sink -mattr=-wavefrontsize32,+wavefrontsize64 -o - %s | FileCheck -check-prefixes=GFX10 %s
 
 # Ensure that PostRA Machine Sink does not sink instructions
 # past block prologues which would overwrite their uses.
 
 ---
+# Make sure COPY to $sgpr9 is not sunk after S_AND_SAVEEXEC_B64.
 name:            _amdgpu_ps_main
 alignment:       1
 tracksRegLiveness: true
 registers:       []
 liveins:
   - { reg: '$sgpr4', virtual-reg: '' }
 body:             |
   ; GFX10-LABEL: name: _amdgpu_ps_main
   ; GFX10: bb.0:
   ; GFX10-NEXT:   successors: %bb.1(0x80000000)
   ; GFX10-NEXT:   liveins: $sgpr4
   ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   renamable $sgpr9 = COPY $sgpr4
   ; GFX10-NEXT:   renamable $vgpr5 = IMPLICIT_DEF
   ; GFX10-NEXT:   renamable $sgpr0_sgpr1 = nofpexcept V_CMP_NGT_F32_e64 0, 0, 0, $vgpr5, 0, implicit $mode, implicit $exec
   ; GFX10-NEXT:   S_BRANCH %bb.1
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT: bb.1:
   ; GFX10-NEXT:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
-  ; GFX10-NEXT:   liveins: $sgpr4:0x0000000000000003, $sgpr6, $sgpr0_sgpr1
+  ; GFX10-NEXT:   liveins: $sgpr6, $sgpr9, $sgpr0_sgpr1
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT:   $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
-  ; GFX10-NEXT:   renamable $sgpr9 = COPY $sgpr4
   ; GFX10-NEXT:   renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
   ; GFX10-NEXT:   S_CBRANCH_EXECZ %bb.3, implicit $exec
   ; GFX10-NEXT:   S_BRANCH %bb.2
   ; GFX10-NEXT: {{  $}}
   ; GFX10-NEXT: bb.2:
   ; GFX10-NEXT:   successors: %bb.3(0x80000000)
   ; GFX10-NEXT:   liveins: $sgpr6
   ; GFX10-NEXT: {{  $}}
bb.2:
     $m0 = COPY killed renamable $sgpr6
     S_BRANCH %bb.8
 
   bb.8:
 
     S_ENDPGM 0
 
 ...
+---
+# Make sure COPY to $sgpr0_sgpr1 is not sunk after S_AND_SAVEEXEC_B64.
+name:            _amdgpu_ps_main2
+alignment:       1
+tracksRegLiveness: true
+registers:       []
+liveins:
+  - { reg: '$sgpr4', virtual-reg: '' }
+  - { reg: '$sgpr6_sgpr7', virtual-reg: '' }
+body:             |
+  ; GFX10-LABEL: name: _amdgpu_ps_main2
+  ; GFX10: bb.0:
+  ; GFX10-NEXT:   successors: %bb.1(0x80000000)
+  ; GFX10-NEXT:   liveins: $sgpr4, $sgpr6_sgpr7
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   renamable $sgpr9 = COPY $sgpr4
+  ; GFX10-NEXT:   renamable $vgpr5 = IMPLICIT_DEF
+  ; GFX10-NEXT:   renamable $sgpr0_sgpr1 = COPY $sgpr6_sgpr7
+  ; GFX10-NEXT:   S_BRANCH %bb.1
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.1:
+  ; GFX10-NEXT:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GFX10-NEXT:   liveins: $sgpr6, $sgpr9, $sgpr0_sgpr1
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
+  ; GFX10-NEXT:   renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
+  ; GFX10-NEXT:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GFX10-NEXT:   S_BRANCH %bb.2
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.2:
+  ; GFX10-NEXT:   successors: %bb.3(0x80000000)
+  ; GFX10-NEXT:   liveins: $sgpr6
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   $m0 = COPY killed renamable $sgpr6
+  ; GFX10-NEXT:   S_BRANCH %bb.3
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.3:
+  ; GFX10-NEXT:   S_ENDPGM 0
+  bb.0:
+    successors: %bb.1(0x80000000)
+    liveins: $sgpr4, $sgpr6_sgpr7
+
+    renamable $sgpr9 = COPY $sgpr4
+    renamable $vgpr5 = IMPLICIT_DEF
+    renamable $sgpr0_sgpr1 = COPY $sgpr6_sgpr7
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2(0x40000000), %bb.8(0x40000000)
+    liveins: $sgpr6, $sgpr9, $sgpr0_sgpr1
+
+    $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
+    renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
+    S_CBRANCH_EXECZ %bb.8, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.8(0x40000000)
+    liveins: $sgpr6
+
+    $m0 = COPY killed renamable $sgpr6
+    S_BRANCH %bb.8
+
+  bb.8:
+
+    S_ENDPGM 0
+
+...
+---
+# Make sure COPY to $sgpr2_sgpr3 is not sunk after S_AND_SAVEEXEC_B32.
+name:            _amdgpu_ps_main3
+alignment:       1
+tracksRegLiveness: true
+registers:       []
+liveins:
+  - { reg: '$sgpr6_sgpr7', virtual-reg: '' }
+  - { reg: '$sgpr8', virtual-reg: '' }
+body:             |
+  ; GFX10-LABEL: name: _amdgpu_ps_main3
+  ; GFX10: bb.0:
+  ; GFX10-NEXT:   successors: %bb.1(0x80000000)
+  ; GFX10-NEXT:   liveins: $sgpr6_sgpr7, $sgpr8
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   renamable $vgpr5 = IMPLICIT_DEF
+  ; GFX10-NEXT:   renamable $sgpr0_sgpr1 = IMPLICIT_DEF
+  ; GFX10-NEXT:   renamable $sgpr2_sgpr3 = COPY $sgpr6_sgpr7
+  ; GFX10-NEXT:   S_BRANCH %bb.1
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.1:
+  ; GFX10-NEXT:   successors: %bb.2(0x40000000), %bb.3(0x40000000)
+  ; GFX10-NEXT:   liveins: $sgpr6, $sgpr8, $sgpr0_sgpr1, $sgpr2_sgpr3
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   $sgpr2 = S_AND_SAVEEXEC_B32 $sgpr8, implicit-def $exec, implicit-def $scc, implicit $exec
+  ; GFX10-NEXT:   $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
+  ; GFX10-NEXT:   renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
+  ; GFX10-NEXT:   S_NOP 0, implicit $sgpr2_sgpr3
+  ; GFX10-NEXT:   S_CBRANCH_EXECZ %bb.3, implicit $exec
+  ; GFX10-NEXT:   S_BRANCH %bb.2
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.2:
+  ; GFX10-NEXT:   successors: %bb.3(0x80000000)
+  ; GFX10-NEXT:   liveins: $sgpr6
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT:   $m0 = COPY killed renamable $sgpr6
+  ; GFX10-NEXT:   S_BRANCH %bb.3
+  ; GFX10-NEXT: {{  $}}
+  ; GFX10-NEXT: bb.3:
+  ; GFX10-NEXT:   S_ENDPGM 0
+  bb.0:
+    successors: %bb.1(0x80000000)
+    liveins: $sgpr6_sgpr7, $sgpr8
+
+    renamable $vgpr5 = IMPLICIT_DEF
+    renamable $sgpr0_sgpr1 = IMPLICIT_DEF
+    renamable $sgpr2_sgpr3 = COPY $sgpr6_sgpr7
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2(0x40000000), %bb.8(0x40000000)
+    liveins: $sgpr6, $sgpr8, $sgpr0_sgpr1, $sgpr2_sgpr3
+
+    $sgpr2 = S_AND_SAVEEXEC_B32 $sgpr8, implicit-def $exec, implicit-def $scc, implicit $exec
+    $sgpr4_sgpr5 = S_AND_SAVEEXEC_B64 $sgpr0_sgpr1, implicit-def $exec, implicit-def $scc, implicit $exec
+    renamable $sgpr14_sgpr15 = S_XOR_B64 $exec, killed renamable $sgpr4_sgpr5, implicit-def dead $scc
+    S_NOP 0, implicit $sgpr2_sgpr3
+    S_CBRANCH_EXECZ %bb.8, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.8(0x40000000)
+    liveins: $sgpr6
+
+    $m0 = COPY killed renamable $sgpr6
+    S_BRANCH %bb.8
+
+  bb.8:
+
+    S_ENDPGM 0
+
+...