AMDGPU: Fix copying i1 value out of loop with non-uniform exit

[nhaehnle]

Summary

When an i1-value is defined inside of a loop and used outside of it, we
cannot simply use the SGPR bitmask from the loop's last iteration.

There are also useful and correct cases of an i1-value being copied between
basic blocks, e.g. when a condition is computed outside of a loop and used
inside it. The concept of dominators is not sufficient to capture what is
going on, so I propose the notion of "lane-dominators".

Fixes a bug encountered in Nier: Automata.

Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=103743
Change-Id: If37b969ddc71d823ab3004aeafb9ea050e45bd9a

[t-tye]

lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

70 ↗

(On Diff #124543)

Would this return true for the CFG:

B

v
A

v
end

Since no successors of A reaches A to cause false to be returned. But no check seems to be made to ensure that A traditionally-dominates B.

[arsenm]

lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

13–15 ↗

(On Diff #124543)

Are you really trying to find control flow equivalent regions? Or is this a active lanes are a subset?

[alex-t]

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.
In this case different threads would have different values.
Traditional Divergence Analysis cannot handle this. Since definition inside the loop body is uniform the use is uniform as well.
Since the value has no explicit data dependency of the loop index, the PHI-node in the loop header (that is divergent if loop-exit is) does not affect it's divergence formally.
The value in fact does have loop-carried dependency. For example:

%tid = call i32 @llvm.amdgcn.workitem.id.x()

for.body:

%val = add i32 %val, 1                                               <== definition of %val is uniform
%cmp = icmp gt i64 %tid, %arg1
br i1 %cmp, label %for.end, label %for.body             <== loop exit condition is divergent

for.end:

store i32 %val, i32 addrspace(1)* %out     <== each thread will have different %val here

Fortunately, you interested in the concrete def and concrete use: AMDGPU::laneDominates(DefInst->getParent(), &MBB))

Could you please look here: https://reviews.llvm.org/D40556

Could you use same approach?

You have 2 blocks: defBlock and useBlock and you want to know:

1. is useBlock is control dependent of defBlock ?
2. if 1 is true is defBlock's termination branch uniform?

The set of control dependencies for defBlock is it's post-dominance frontier set
The set of control dependencies for useBlock is it's post-dominance frontier set
We need to check the branches that are NOT common in 2 sets above.

[nhaehnle]

lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

13–15 ↗

(On Diff #124543)

They don't have to be equivalent. In the case of:

   A
  / \
 /   \
B     C

A lane-dominates both B and C, but they're not equivalent.

70 ↗

(On Diff #124543)

I'm afraid I'm not sure what the CFG you have in mind looks like. The function assumes that A traditionally-dominates B, the caller must ensure that (as per the comment).

[nhaehnle]

In D40547#938894, @alex-t wrote:

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.

More or less. However, whether the value is uniform or not doesn't really make a difference: I can change the test case so that %cc is non-uniform, and the same issue occurs. So this isn't really about DivergenceAnalysis.

Could you please look here: https://reviews.llvm.org/D40556

Could you use same approach?

You have 2 blocks: defBlock and useBlock and you want to know:

1. is useBlock is control dependent of defBlock ?
2. if 1 is true is defBlock's termination branch uniform?

The set of control dependencies for defBlock is it's post-dominance frontier set
The set of control dependencies for useBlock is it's post-dominance frontier set
We need to check the branches that are NOT common in 2 sets above.

I don't think this works, but perhaps I'm misunderstanding you. In the test case which I've added, the defBlock is %for.body, and the useBlock is %for.end.

%for.end post-dominates the entire loop, so its post-dominance frontier is empty.

%for.body post-dominates %entry and %end.loop, so its PDF is only %mid.loop.

None of that information seems to help?

[alex-t]

In D40547#989137, @nhaehnle wrote:

In D40547#938894, @alex-t wrote:

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.

More or less. However, whether the value is uniform or not doesn't really make a difference: I can change the test case so that %cc is non-uniform, and the same issue occurs. So this isn't really about DivergenceAnalysis.

Could you please look here: https://reviews.llvm.org/D40556

Could you use same approach?

You have 2 blocks: defBlock and useBlock and you want to know:

1. is useBlock is control dependent of defBlock ?
2. if 1 is true is defBlock's termination branch uniform?

The set of control dependencies for defBlock is it's post-dominance frontier set
The set of control dependencies for useBlock is it's post-dominance frontier set
We need to check the branches that are NOT common in 2 sets above.

I don't think this works, but perhaps I'm misunderstanding you. In the test case which I've added, the defBlock is %for.body, and the useBlock is %for.end.

%for.end post-dominates the entire loop, so its post-dominance frontier is empty.

%for.body post-dominates %entry and %end.loop, so its PDF is only %mid.loop.

None of that information seems to help?

for.body:

%i = phi i32 [0, %entry], [%i.inc, %end.loop]

• %cc = icmp ult i32 %i, 4** <-- definition br i1 %cc, label %mid.loop, label %for.end

mid.loop:

%v = call float @llvm.amdgcn.buffer.load.f32(<4 x i32> %rsrc, i32 %tid, i32 %i, i1 false, i1 false)
%cc2 = fcmp oge float %v, 0.0

• br i1 %cc2, label %end.loop, label %for.end ** <-- divergent branch condition

end.loop:

%i.inc = add i32 %i, 1
br label %for.body

for.end:

**br i1 %cc, label %if, label %end**     <-- use

Since the use block's PDF is empty and def block PDF contains the only one block "mid.loop" we only should check the "mid.loop"'s termination branch divergence.
Here it's immediately clear that the "cc2" is divergent and the branch in "mid.loop" is divergent as well.
So, the use in "for.end" is divergent by the control dependency of the "mid.block" divergent branch.

[nhaehnle]

In D40547#990379, @alex-t wrote:

In D40547#989137, @nhaehnle wrote:

In D40547#938894, @alex-t wrote:

If I understand everything correct...
The problem you're trying to solve is well known.
You have divergent loop-exit and a value that is uniformly defined inside the loop but used outside the loop.

More or less. However, whether the value is uniform or not doesn't really make a difference: I can change the test case so that %cc is non-uniform, and the same issue occurs. So this isn't really about DivergenceAnalysis.

Could you please look here: https://reviews.llvm.org/D40556

Could you use same approach?

You have 2 blocks: defBlock and useBlock and you want to know:

1. is useBlock is control dependent of defBlock ?
2. if 1 is true is defBlock's termination branch uniform?

The set of control dependencies for defBlock is it's post-dominance frontier set
The set of control dependencies for useBlock is it's post-dominance frontier set
We need to check the branches that are NOT common in 2 sets above.

I don't think this works, but perhaps I'm misunderstanding you. In the test case which I've added, the defBlock is %for.body, and the useBlock is %for.end.

%for.end post-dominates the entire loop, so its post-dominance frontier is empty.

%for.body post-dominates %entry and %end.loop, so its PDF is only %mid.loop.

None of that information seems to help?

for.body:

%i = phi i32 [0, %entry], [%i.inc, %end.loop]

• %cc = icmp ult i32 %i, 4** <-- definition br i1 %cc, label %mid.loop, label %for.end

mid.loop:

%v = call float @llvm.amdgcn.buffer.load.f32(<4 x i32> %rsrc, i32 %tid, i32 %i, i1 false, i1 false)
%cc2 = fcmp oge float %v, 0.0

• br i1 %cc2, label %end.loop, label %for.end ** <-- divergent branch condition

end.loop:

%i.inc = add i32 %i, 1
br label %for.body

for.end:

**br i1 %cc, label %if, label %end**     <-- use

Since the use block's PDF is empty and def block PDF contains the only one block "mid.loop" we only should check the "mid.loop"'s termination branch divergence.
Here it's immediately clear that the "cc2" is divergent and the branch in "mid.loop" is divergent as well.
So, the use in "for.end" is divergent by the control dependency of the "mid.block" divergent branch.

Right, but what if the uniformness were reversed? We could have something like:

for.body:
  %i = phi i32 [0, %entry], [%i.inc, %end.loop]
  %cc = icmp ult i32 %i, 4**                               <-- uniform definition
  %v = call float @llvm.amdgcn.buffer.load.f32(<4 x i32> %rsrc, i32 %tid, i32 %i, i1 false, i1 false)
  %cc2 = fcmp oge float %v, 0.0
  br i1 %cc2, label %mid.loop, label %for.end <-- divergent branch

mid.loop:
  ...
  br i1 %cc3, label %end.loop, label %for.end   <-- uniform branch condition defined somewhere else

The same problem would still exist, but the proposed way of looking at PDFs would not detect the situation.

[nhaehnle]

Ping?

[nhaehnle]

Ping!

[arsenm]

lib/Target/AMDGPU/SILowerI1Copies.cpp

146 ↗

(On Diff #124543)

I think the info from the commit message needs to be added here

lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

52 ↗

(On Diff #124543)

We keep repeating essentially the same control flow depth first search in various places, but I don't have a better idea until we really fix the control flow situation

test/CodeGen/AMDGPU/i1-copy-from-loop.ll

1–2 ↗

(On Diff #124543)

s/SI/GCN

llvm/trunk/lib/Target/AMDGPU/SILowerI1Copies.cpp

 ///
 //===----------------------------------------------------------------------===//
 //
 
 #define DEBUG_TYPE "si-i1-copies"
 #include "AMDGPU.h"
 #include "AMDGPUSubtarget.h"
 #include "SIInstrInfo.h"
+#include "Utils/AMDGPULaneDominator.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetMachine.h"
for (I = MBB.begin(); I != MBB.end(); I = Next) {
             DefInst->getOperand(1).isImm() && DefInst->getOperand(2).isImm() &&
             DefInst->getOperand(1).getImm() == 0 &&
             DefInst->getOperand(2).getImm() != 0 &&
             DefInst->getOperand(3).isReg() &&
             TargetRegisterInfo::isVirtualRegister(
               DefInst->getOperand(3).getReg()) &&
             TRI->getCommonSubClass(
               MRI.getRegClass(DefInst->getOperand(3).getReg()),
-              &AMDGPU::SGPR_64RegClass)) {
+              &AMDGPU::SGPR_64RegClass) &&
+            AMDGPU::laneDominates(DefInst->getParent(), &MBB)) {
           BuildMI(MBB, &MI, DL, TII->get(AMDGPU::S_AND_B64))
               .add(Dst)
               .addReg(AMDGPU::EXEC)
               .add(DefInst->getOperand(3));
         } else {
           BuildMI(MBB, &MI, DL, TII->get(AMDGPU::V_CMP_NE_U32_e64))
               .add(Dst)
               .add(Src)

llvm/trunk/lib/Target/AMDGPU/Utils/AMDGPULaneDominator.h

+//===- AMDGPULaneDominator.h ------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_AMDGPU_UTILS_AMDGPULANEDOMINATOR_H
+#define LLVM_LIB_TARGET_AMDGPU_UTILS_AMDGPULANEDOMINATOR_H
+
+namespace llvm {
+
+class MachineBasicBlock;
+
+namespace AMDGPU {
+
+bool laneDominates(MachineBasicBlock *MBBA, MachineBasicBlock *MBBB);
+
+} // end namespace AMDGPU
+} // end namespace llvm
+
+#endif // LLVM_LIB_TARGET_AMDGPU_UTILS_AMDGPULANEDOMINATOR_H

llvm/trunk/lib/Target/AMDGPU/Utils/AMDGPULaneDominator.cpp

+//===-- AMDGPULaneDominator.cpp - Determine Lane Dominators ---------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// MBB A lane-dominates MBB B if
+// 1. A dominates B in the usual sense, i.e. every path from the entry to B
+//    goes through A, and
+// 2. whenever B executes, every active lane during that execution of B was
+//    also active during the most recent execution of A.
+//
+// The simplest example where A dominates B but does not lane-dominate it is
+// where A is a loop:
+//
+//     |
+//     +--+
+//     A  |
+//     +--+
+//     |
+//     B
+//
+// Unfortunately, the second condition is not fully captured by the control
+// flow graph when it is unstructured (as may happen when branch conditions are
+// uniform).
+//
+// The following replacement of the second condition is a conservative
+// approximation. It is an equivalent condition when the CFG is fully
+// structured:
+//
+// 2'. every cycle in the CFG that contains A also contains B.
+//
+//===----------------------------------------------------------------------===//
+
+#include "AMDGPULaneDominator.h"
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+
+namespace llvm {
+
+namespace AMDGPU {
+
+// Given machine basic blocks A and B where A dominates B, check whether
+// A lane-dominates B.
+//
+// The check is conservative, i.e. there can be false-negatives.
+bool laneDominates(MachineBasicBlock *A, MachineBasicBlock *B) {
+  // Check whether A is reachable from itself without going through B.
+  DenseSet<MachineBasicBlock *> Reachable;
+  SmallVector<MachineBasicBlock *, 8> Stack;
+
+  Stack.push_back(A);
+  do {
+    MachineBasicBlock *MBB = Stack.back();
+    Stack.pop_back();
+
+    for (MachineBasicBlock *Succ : MBB->successors()) {
+      if (Succ == A)
+        return false;
+      if (Succ != B && Reachable.insert(Succ).second)
+        Stack.push_back(Succ);
+    }
+  } while (!Stack.empty());
+
+  return true;
+}
+
+} // namespace AMDGPU
+
+} // namespace llvm

llvm/trunk/lib/Target/AMDGPU/Utils/CMakeLists.txt

 add_llvm_library(LLVMAMDGPUUtils
   AMDGPUBaseInfo.cpp
   AMDKernelCodeTUtils.cpp
   AMDGPUAsmUtils.cpp
+  AMDGPULaneDominator.cpp
   )

llvm/trunk/test/CodeGen/AMDGPU/i1-copy-from-loop.ll

+; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=SI %s
+; RUN: llc -march=amdgcn -mcpu=tonga -verify-machineinstrs < %s | FileCheck -check-prefix=SI %s
+
+; SI-LABEL: {{^}}i1_copy_from_loop:
+;
+; Cannot use an SGPR mask to copy %cc out of the loop, since the mask would
+; only contain the lanes that were active during the last loop iteration.
+;
+; SI: ; %for.body
+; SI: v_cmp_gt_u32_e64 [[SREG:s\[[0-9]+:[0-9]+\]]], 4,
+; SI: v_cndmask_b32_e64 [[VREG:v[0-9]+]], 0, -1, [[SREG]]
+; SI-NOT: [[VREG]]
+; SI: ; %for.end
+; SI: v_cmp_ne_u32_e32 vcc, 0, [[VREG]]
+define amdgpu_ps void @i1_copy_from_loop(<4 x i32> inreg %rsrc, i32 %tid) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [0, %entry], [%i.inc, %end.loop]
+  %cc = icmp ult i32 %i, 4
+  br i1 %cc, label %mid.loop, label %for.end
+
+mid.loop:
+  %v = call float @llvm.amdgcn.buffer.load.f32(<4 x i32> %rsrc, i32 %tid, i32 %i, i1 false, i1 false)
+  %cc2 = fcmp oge float %v, 0.0
+  br i1 %cc2, label %end.loop, label %for.end
+
+end.loop:
+  %i.inc = add i32 %i, 1
+  br label %for.body
+
+for.end:
+  br i1 %cc, label %if, label %end
+
+if:
+  call void @llvm.amdgcn.exp.f32(i32 0, i32 15, float undef, float undef, float undef, float undef, i1 true, i1 true)
+  br label %end
+
+end:
+  ret void
+}
+
+declare float @llvm.amdgcn.buffer.load.f32(<4 x i32>, i32, i32, i1, i1) #0
+declare void @llvm.amdgcn.exp.f32(i32, i32, float, float, float, float, i1, i1) #1
+
+attributes #0 = { nounwind readonly }
+attributes #1 = { nounwind inaccessiblememonly }