[AMDGPU] Fix merging m0 inits

[piotr]

Summary

Fix incorrect merges of m0 inits in loops.

It was assumed that if a clobbering instruction appears in
the same block as an init and the clobbering instruction
does not dominate the init then it does not interfere with
init.

This does not work in the presence of loops, where in this
scenario, the clobbering instruction does interfere with
the init in another iteration.

To fix this, do not check for block equality and defer the
decision to the predecessor check.

[rampitec]

Doesn't loop block self dominate?

[arsenm]

About a year ago I was working on eliminating this code completely but I guess I won't be getting back to this any time soon

[piotr]

In D87882#2282278, @rampitec wrote:

Doesn't loop block self dominate?

You mean, why the condition "MDT.dominates(From, To)" returns false if From and To are in the same BB? Inside that function there is a bb dominance check if the instructions are in different blocks, but if the instructions are in the same block the code checks whether From comes before To.

The bug I am trying to fix is simplified in the test m0-in-loop-0 where before my patch SI_INIT from line 333 was incorrectly removed. Although "m0 = COPY" comes after SI_INIT in that bb, this is a loop and in the second iteration DS_WRITE would see a clobbered m0, so SI_INIT has to be preserved.

[rampitec]

In D87882#2282818, @piotr wrote:

In D87882#2282278, @rampitec wrote:

Doesn't loop block self dominate?

You mean, why the condition "MDT.dominates(From, To)" returns false if From and To are in the same BB? Inside that function there is a bb dominance check if the instructions are in different blocks, but if the instructions are in the same block the code checks whether From comes before To.

The bug I am trying to fix is simplified in the test m0-in-loop-0 where before my patch SI_INIT from line 333 was incorrectly removed. Although "m0 = COPY" comes after SI_INIT in that bb, this is a loop and in the second iteration DS_WRITE would see a clobbered m0, so SI_INIT has to be preserved.

That sounds like a bug in the dominate() to me.

[piotr]

In D87882#2282886, @rampitec wrote:

In D87882#2282818, @piotr wrote:

In D87882#2282278, @rampitec wrote:

Doesn't loop block self dominate?

You mean, why the condition "MDT.dominates(From, To)" returns false if From and To are in the same BB? Inside that function there is a bb dominance check if the instructions are in different blocks, but if the instructions are in the same block the code checks whether From comes before To.

The bug I am trying to fix is simplified in the test m0-in-loop-0 where before my patch SI_INIT from line 333 was incorrectly removed. Although "m0 = COPY" comes after SI_INIT in that bb, this is a loop and in the second iteration DS_WRITE would see a clobbered m0, so SI_INIT has to be preserved.

That sounds like a bug in the dominate() to me.

MDT.dominates() gives correct answer. In the failing case "From" (m0 copy, line 335 in the test) is inside the same block as "To" (SI_INIT, line 333). "From" comes after "To", and "From" does not dominate "To" (so MDT.dominates() return false as expected), but "To" is reachable from "From" from previous iteration, so "To" cannot be removed.

[rampitec]

In D87882#2284543, @piotr wrote:

In D87882#2282886, @rampitec wrote:

In D87882#2282818, @piotr wrote:

In D87882#2282278, @rampitec wrote:

Doesn't loop block self dominate?

You mean, why the condition "MDT.dominates(From, To)" returns false if From and To are in the same BB? Inside that function there is a bb dominance check if the instructions are in different blocks, but if the instructions are in the same block the code checks whether From comes before To.

The bug I am trying to fix is simplified in the test m0-in-loop-0 where before my patch SI_INIT from line 333 was incorrectly removed. Although "m0 = COPY" comes after SI_INIT in that bb, this is a loop and in the second iteration DS_WRITE would see a clobbered m0, so SI_INIT has to be preserved.

That sounds like a bug in the dominate() to me.

MDT.dominates() gives correct answer. In the failing case "From" (m0 copy, line 335 in the test) is inside the same block as "To" (SI_INIT, line 333). "From" comes after "To", and "From" does not dominate "To" (so MDT.dominates() return false as expected), but "To" is reachable from "From" from previous iteration, so "To" cannot be removed.

I believe it gives incorrect answer:

(gdb) p MDT.dominates(From, To)
$1 = false
(gdb) p MDT.dominates(From->getParent(), To->getParent())
$2 = true

It correctly tells that block dominates itself, but then it says instructions in that block do not dominate other instructions in that block.
I believe the correct change would be to replace this:

bool dominates(const MachineInstr *A, const MachineInstr *B) const {
  applySplitCriticalEdges();
  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
  if (BBA != BBB) return DT->dominates(BBA, BBB);

with this:

bool dominates(const MachineInstr *A, const MachineInstr *B) const {
  applySplitCriticalEdges();
  const MachineBasicBlock *BBA = A->getParent(), *BBB = B->getParent();
  if (DT->dominates(BBA, BBB))
    return true;
  if (BBA != BBB)
    return false;

[piotr]

bb.1:
  ..
  TO_inst   (inits m0)
  ...       (uses m0)
  FROM_inst (clobbers m0)
  ...
  S_CBRANCH_VCCZ %bb.1, undef
  S_BRANCH %bb.2

I guess I am missing something here, the dominance usually refers to blocks so it can be confusing if applied for instructions.

In this case I expect MDT.dominates(FROM_inst, TO_inst) to return false, because it is possible for a program invocation to execute TO_inst, without executing FROM_inst first (e.g. single loop iteration).

Anyway, the spirit of the code I am editing was that before my patch it was assumed that if FROM_inst comes after TO_inst in a basic block (as in the case described above) then there was no path from FROM_inst to TO_inst, so TO_inst could be removed. This is not true for loops, where FROM_inst will clober m0 used in the next iteration.

[rampitec]

In D87882#2287724, @piotr wrote:

bb.1:
  ..
  TO_inst   (inits m0)
  ...       (uses m0)
  FROM_inst (clobbers m0)
  ...
  S_CBRANCH_VCCZ %bb.1, undef
  S_BRANCH %bb.2

I guess I am missing something here, the dominance usually refers to blocks so it can be confusing if applied for instructions.

In this case I expect MDT.dominates(FROM_inst, TO_inst) to return false, because it is possible for a program invocation to execute TO_inst, without executing FROM_inst first (e.g. single loop iteration).

Anyway, the spirit of the code I am editing was that before my patch it was assumed that if FROM_inst comes after TO_inst in a basic block (as in the case described above) then there was no path from FROM_inst to TO_inst, so TO_inst could be removed. This is not true for loops, where FROM_inst will clober m0 used in the next iteration.

If block A dominates block B then all instructions in A dominate all instructions in B, isn't it? That is not changed if A == B. Imagine you have split that block in between of "From" and "To" and there is simple fall-through at that split. Nothing has changed in the program logic, right? But now MDT::dominates() suddenly start to return true instead of false. This just cannot be right.

[alex-t]

In D87882#2282278, @rampitec wrote:

Doesn't loop block self dominate?

By definition: in CFG block X dominates block Y iif every path from entry to Y goes through X. Every block dominates itself.
Also by definition: block X strictly dominates block Y iif X dominates Y and X != Y.
To check if MBB A strictly dominates MBB B you need to call MDT.properlyDominates(A, B)

All the above is about that there are 2 orthogonal problems - dominance and reachability.
All instructions in a loop (irrelative of the number of blocks in a loop) are reachable from each other, i.e form SCC in a graph.
This is not about dominance at all. Moreover, the notion of dominance applied to instructions is just an interface sugar because dominance assumes graph but we don't have a graph of instructions but only basic blocks.
So, my opinion that check for a loop (i.e.predecessor search) is correct here.

[rampitec]

OK, thanks Alex.

llvm/lib/Target/AMDGPU/SIFixSGPRCopies.cpp

 
 // Checks if there is potential path From instruction To instruction.
 // If CutOff is specified and it sits in between of that path we ignore
 // a higher portion of the path and report it is not reachable.
 static bool isReachable(const MachineInstr *From,
                         const MachineInstr *To,
                         const MachineBasicBlock *CutOff,
                         MachineDominatorTree &MDT) {
-  // If either From block dominates To block or instructions are in the same
-  // block and From is higher.
   if (MDT.dominates(From, To))
     return true;
 
   const MachineBasicBlock *MBBFrom = From->getParent();
   const MachineBasicBlock *MBBTo = To->getParent();
-  if (MBBFrom == MBBTo)
-    return false;
 
-  // Instructions are in different blocks, do predecessor search.
+  // Do predecessor search.
   // We should almost never get here since we do not usually produce M0 stores
   // other than -1.
   return searchPredecessors(MBBTo, CutOff, [MBBFrom]
            (const MachineBasicBlock *MBB) { return MBB == MBBFrom; });
 }
 
 // Return the first non-prologue instruction in the block.
 static MachineBasicBlock::iterator

llvm/test/CodeGen/AMDGPU/merge-m0.mir

 body:             |
   bb.0:
     %0 = IMPLICIT_DEF
     %1 = IMPLICIT_DEF
     S_SETREG_IMM32_B32 0, 1, implicit-def $mode, implicit $mode
     SI_INIT_M0 -1, implicit-def $m0
     DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
 ...
+
+
+# GCN-LABEL: name: m0-in-loop-0
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: $m0 = COPY %2
+
+---
+name: m0-in-loop-0
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-1
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN-NOT:      SI_INIT_M0 -1
+# GCN: DS_WRITE_B32
+
+---
+name: m0-in-loop-1
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-2
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+# GCN-NEXT:      SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+
+---
+name: m0-in-loop-2
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-3
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+# GCN-NEXT:      SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: DS_WRITE_B32
+
+---
+name: m0-in-loop-3
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-4
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN:  SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+
+---
+name: m0-in-loop-4
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-5
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN:  SI_INIT_M0 65536
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT:  SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+
+---
+name: m0-in-loop-5
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    SI_INIT_M0 65536, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.2
+
+  bb.2:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-6
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN:  SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+
+---
+name: m0-in-loop-6
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2
+
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.3, %bb.1
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.3
+
+
+  bb.3:
+    S_ENDPGM 0
+...
+
+# GCN-LABEL: name: m0-in-loop-7
+# GCN:    bb.0.entry:
+# GCN:      SI_INIT_M0 -1
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: IMPLICIT_DEF
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.1:
+# GCN:  SI_INIT_M0 -1
+# GCN-NEXT: DS_WRITE_B32
+# GCN-NEXT: DS_WRITE_B32
+
+# GCN:    bb.2:
+# GCN: $m0 = COPY %2
+# GCN-NEXT:      SENDMSG
+
+---
+name: m0-in-loop-7
+registers:
+  - { id: 0, class: vgpr_32 }
+  - { id: 1, class: vgpr_32 }
+  - { id: 2, class: sgpr_32 }
+body:             |
+  bb.0.entry:
+    successors: %bb.1
+
+    %0 = IMPLICIT_DEF
+    %1 = IMPLICIT_DEF
+    %2 = IMPLICIT_DEF
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.1
+
+  bb.1:
+    successors: %bb.2
+
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    SI_INIT_M0 -1, implicit-def $m0
+    DS_WRITE_B32 %0, %1, 0, 0, implicit $m0, implicit $exec
+    S_BRANCH %bb.2
+
+  bb.2:
+    successors: %bb.3, %bb.1
+    $m0 = COPY %2:sgpr_32
+    S_SENDMSG 34, implicit $exec, implicit $m0
+    S_CBRANCH_VCCZ %bb.1, implicit undef $vcc
+    S_BRANCH %bb.3
+
+  bb.3:
+    S_ENDPGM 0
+...