RFD: Do not CSE convergent calls in different basic blocks

[foad]

Summary

"convergent" is documented as meaning that the call cannot be made
control-dependent on more values, but in practice we also require that
it cannot be made control-dependent on fewer values, e.g. it cannot be
hoisted out of the body of an "if" statement.

In code like this, if we allow CSE to combine the two calls:

x = convergent_call();
if (cond) {
  y = convergent_call();
  use y;
}

then we get this:

x = convergent_call();
if (cond) {
  use x;
}

This is conceptually equivalent to moving the second call out of the
body of the "if", up to the location of the first call, so it should be
disallowed.

[foad]

llvm/test/CodeGen/AMDGPU/cse-convergent.ll

37

This is the effect of the fix: we repeat the DPP subgroup operation over a reduced set of lanes, instead of reusing the result of the first DPP subgroup operation over all lanes.

llvm/test/Transforms/SimplifyCFG/convergent.ll

85 ↗

(On Diff #517552)

This is a completely accidental hoisting improvement due to https://reviews.llvm.org/D129370#inline-1442432. Convergent calls in the "then" and "else" branches are now treated as not identical, which weirdly allows *more* hoisting than when they were considered identical.

[nikic]

llvm/lib/IR/Instruction.cpp

529 ↗

(On Diff #517552)

This check should not be part of hasSameSpecialState(). It's not the job of this function to model any dependencies, be they memory dependencies or convergence.

[b-sumner]

How confident are we in our ability to strip the convergent attribute off of functions that don't need it? Seems like this could cause performance regressions.

[foad]

Move logic from Instruction::hasSameSpecialState to
Instruction::isIdenticalToWhenDefined. @nikic is that more acceptable?

[foad]

Move logic from Instruction::hasSameSpecialState to
Instruction::isIdenticalToWhenDefined. @nikic is that more acceptable?

Failing that I can move it up into SimpleValue's isEqualImpl in EarlyCSE.

[foad]

How confident are we in our ability to strip the convergent attribute off of functions that don't need it? Seems like this could cause performance regressions.

I don't know. I guess that is an Attributor question? @arsenm @jdoerfert

[nikic]

In D149348#4302188, @foad wrote:

Move logic from Instruction::hasSameSpecialState to
Instruction::isIdenticalToWhenDefined. @nikic is that more acceptable?

Not really. All of those functions are about purely structural comparison of instructions, they don't reason about effects. Moving the check to EarlyCSE would be fine.

[arsenm]

In D149348#4302261, @foad wrote:

How confident are we in our ability to strip the convergent attribute off of functions that don't need it? Seems like this could cause performance regressions.

I don't know. I guess that is an Attributor question? @arsenm @jdoerfert

Removing convergent is easy. It

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

I’m questioning whether it’s worth or correct to allow CSE of convergent operations in the same block

[foad]

Restrict the changes to EarlyCSE itself.

[foad]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

Surely it's correct? You could even CSE them in different blocks if there is no divergent control flow between them. When we have convergence tokens perhaps this will become trivial: you can CSE them iff they use the convergence token.

[nikic]

(My concern has been addressed and I can't comment on the change itself.)

[ruiling]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

I’m questioning whether it’s worth or correct to allow CSE of convergent operations in the same block

Very good question. CSE convergent operations in the same block may still be helpful if there are several subgroup operations(like mbcnt(ballot)) in one block.

Regarding to whether it is correct to CSE convergent operation. I think into two cases:

1. WWM operations with normal operations. As the inputs to the WWM operation are already set.inactiveed, so we will not do wrong CSE between WWM operation and normal operation.
2. convergent operations before and after amdgcn.kill. A ballot before an amdgcn.kill obviously cannot be CSEed with another one after the kill.

So I think we should not try to CSE ANY convergent operation up till now.
Last time I think into kill, my idea is we need to add a new type of basic block terminator for it. But I have not go into the details of how to make it work with other parts of our compiler.

[foad]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

So I think we should not try to CSE ANY convergent operation up till now.

I would like to push the current patch because I think it is justified by the target-independent meaning of "convergent".

The problem with amdgcn.kill is very AMDGPU-specific, so I think ideally we should find an AMDGPU-specific way to fix it, instead of pessimizing target-independent code.

[sameerds]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

I kinda agree with that sentiment. Is it correct to assume that the kill intrinsic is itself experimental, and its semantics needs to be worked out for convergent operations? Shouldn't that happen before using the intrinsic in production?

[nhaehnle]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

I'd say the change should go ahead as-is. kill is AMDGPU-specific, and in any case, it looks like this change doesn't make the situation regarding kill worse than it is today.

Further, I agree with @ruiling that kill should conceptually be a terminator. We should consider just using it with callbr.

[sameerds]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

Convergence tokens are not sufficient by themselves for CSE. The set of threads at the use of a token can be a subset of the threads at the definition, if there is divergent control flow along the way. Then two uses of the same token can be reached by different sets of the original set, which is no different from the current situation. The same can happen across a kill intrinsic call.

[arsenm]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

Yes, I’ve thought about only allowing callbr kills. It would fix this ugly edge case

[foad]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

in any case, it looks like this change doesn't make the situation regarding kill worse than it is today.

Right, this patch is a step in the direction of @ruiling's suggestion of disallowing all CSE of convergent calls.

[ruiling]

llvm/lib/IR/Instruction.cpp

578 ↗

(On Diff #517570)

Yes, I agree on submit the change, I was just going too much specific to AMDGPU specific stuff when thinking about possible issues. Generally speaking, this change is correct.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

static unsigned getHashValueImpl(SimpleValue Val) {
 
   // gc.relocate is 'special' call: its second and third operands are
   // not real values, but indices into statepoint's argument list.
   // Get values they point to.
   if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))
     return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
                         GCR->getBasePtr(), GCR->getDerivedPtr());
 
+  // Don't CSE convergent calls in different basic blocks, because they
+  // implicitly depend on the set of threads that is currently executing.
+  if (CallInst *CI = dyn_cast<CallInst>(Inst); CI && CI->isConvergent()) {
+    return hash_combine(
+        Inst->getOpcode(), Inst->getParent(),
+        hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
+  }
+
   // Mix in the opcode.
   return hash_combine(
       Inst->getOpcode(),
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 }
 
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
 #ifndef NDEBUG

 static bool isEqualImpl(SimpleValue LHS, SimpleValue RHS) {
   Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
 
   if (LHS.isSentinel() || RHS.isSentinel())
     return LHSI == RHSI;
 
   if (LHSI->getOpcode() != RHSI->getOpcode())
     return false;
-  if (LHSI->isIdenticalToWhenDefined(RHSI))
+  if (LHSI->isIdenticalToWhenDefined(RHSI)) {
+    // Convergent calls implicitly depend on the set of threads that is
+    // currently executing, so conservatively return false if they are in
+    // different basic blocks.
+    if (CallInst *CI = dyn_cast<CallInst>(LHSI);
+        CI && CI->isConvergent() && LHSI->getParent() != RHSI->getParent())
+      return false;
+
     return true;
+  }
 
   // If we're not strictly identical, we still might be a commutable instruction
   if (BinaryOperator *LHSBinOp = dyn_cast<BinaryOperator>(LHSI)) {
     if (!LHSBinOp->isCommutative())
       return false;
 
     assert(isa<BinaryOperator>(RHSI) &&
            "same opcode, but different instruction type?");

llvm/test/CodeGen/AMDGPU/cse-convergent.ll

 ; GCN-NEXT:    s_mov_b32 exec_lo, s4
 ; GCN-NEXT:    v_mov_b32_e32 v3, v0
 ; GCN-NEXT:    s_not_b32 exec_lo, exec_lo
 ; GCN-NEXT:    v_mov_b32_e32 v3, 0
 ; GCN-NEXT:    s_not_b32 exec_lo, exec_lo
 ; GCN-NEXT:    s_or_saveexec_b32 s4, -1
 ; GCN-NEXT:    v_mov_b32_dpp v2, v3 row_xmask:1 row_mask:0xf bank_mask:0xf
 ; GCN-NEXT:    s_mov_b32 exec_lo, s4
-; GCN-NEXT:    v_mov_b32_e32 v4, 0
-; GCN-NEXT:    v_mov_b32_e32 v0, v2
+; GCN-NEXT:    v_mov_b32_e32 v5, 0
+; GCN-NEXT:    v_mov_b32_e32 v4, v2
 ; GCN-NEXT:    v_cmp_eq_u32_e32 vcc_lo, 0, v1
 ; GCN-NEXT:    s_and_saveexec_b32 s4, vcc_lo
 ; GCN-NEXT:  ; %bb.1: ; %if
-; GCN-NEXT:    v_mov_b32_e32 v4, v0
+; GCN-NEXT:    s_or_saveexec_b32 s5, -1
+; GCN-NEXT:    v_mov_b32_e32 v2, 0
+; GCN-NEXT:    s_mov_b32 exec_lo, s5
+; GCN-NEXT:    v_mov_b32_e32 v3, v0
+; GCN-NEXT:    s_not_b32 exec_lo, exec_lo
+; GCN-NEXT:    v_mov_b32_e32 v3, 0
+; GCN-NEXT:    s_not_b32 exec_lo, exec_lo
+; GCN-NEXT:    s_or_saveexec_b32 s5, -1
+; GCN-NEXT:    v_mov_b32_dpp v2, v3 row_xmask:1 row_mask:0xf bank_mask:0xf
+; GCN-NEXT:    s_mov_b32 exec_lo, s5
+; GCN-NEXT:    v_mov_b32_e32 v5, v2
 ; GCN-NEXT:  ; %bb.2: ; %end
 ; GCN-NEXT:    s_or_b32 exec_lo, exec_lo, s4
-; GCN-NEXT:    v_add_nc_u32_e32 v0, v0, v4
+; GCN-NEXT:    v_add_nc_u32_e32 v0, v4, v5
 ; GCN-NEXT:    s_xor_saveexec_b32 s4, -1
 ; GCN-NEXT:    s_clause 0x1
 ; GCN-NEXT:    buffer_load_dword v2, off, s[0:3], s32
 ; GCN-NEXT:    buffer_load_dword v3, off, s[0:3], s32 offset:4
 ; GCN-NEXT:    s_waitcnt_depctr 0xffe3
 ; GCN-NEXT:    s_mov_b32 exec_lo, s4
 ; GCN-NEXT:    s_waitcnt vmcnt(0)
 ; GCN-NEXT:    s_waitcnt_vscnt null, 0x0