llvm dev - Oct 2016 - RFC: (Co-)Convergent functions and uniform function parameters

Hi all,

Some brain-storming on an issue with SPMD/SIMT backend support where I 
think some additional IR attributes would be useful. Sorry for the 
somewhat long mail; the short version of my current thinking is that I 
would like to have the following:

1) convergent: a call to a function with this attribute cannot be moved 
to have additional control dependencies; i.e., moving it from A to B is 
only possible if B dominates or post-dominates A.

2) co-convergent (divergent? for lack of a better name...): a call to a 
function with this attribute cannot be moved to have _fewer_ control 
dependencies; i.e., moving it from A to B is only possible if A 
dominates or post-dominates B.

3) uniform (for function arguments): transformations are not allowed to 
introduce additional non-uniformity in this argument.

I'd appreciate input on this proposal, e.g. if this can be solved in an 
easier way or if there are obvious problems with this approach.

Thanks,
Nicolai

..........
In a nutshell, the problem that this intends to solve is that:

   %v1 = texelFetch(%sampler, %coord0)
   %v2 = texelFetch(%sampler, %coord1)
   %v = select i1 %cond, vType %v1, %v2

is logically equivalent to and could benefit from being transformed to,

   %coord = select i1 %cond, cType %coord0, %coord1
   %v = texelFetch(%sampler, %coord)

but on the other hand

   %v1 = texelFetch(%sampler0, %coord)
   %v2 = texelFetch(%sampler1, %coord)
   %v = select i1 %cond, vType %v1, %v2

_must_not_ be transformed to

   %s = select i1 %cond, sType %sampler0, %sampler1
   %v = texelFetch(%s, %coord)

because of uniformity restrictions on the first argument of texelFetch.

We currently have a shader that is mis-compiled in the wild because 
something much like the latter transform is done by SimplifyCFG.[1] 
There, the equivalent thing happens with phi nodes:

if:
   %v.if = texelFetch(%sampler0, %coord)
   br label %end

else:
   %v.else = texelFetch(%sampler1, %coord)
   br label %end

end:
   %v = phi [ %v.if, %if ], [ %v.else, %else ]

becomes

   ...
end:
   %s = phi [ %sampler0, %if ], [ %sampler1, %else ]
   %v = texelFetch(%s, %coord)

I have collected some more examples at [2]

The distinctions between all three attribute types mentioned above makes 
sense, because there are OpenGL shader intrinsics that naturally carry 
almost all of the possible combinations of those attributes.

That said, a pass that is not SPMD/SIMT-aware must treat every function 
call that has a uniform argument as if it were co-convergent, because 
the input to the uniform argument could have non-uniformity whose 
structure correlates with control dependencies; see [2] for an example. 
Furthermore, I have not yet found an operation that needs the 
co-convergent attribute without also having uniform arguments. So for 
the purposes of LLVM, it may be sufficient to add the 'uniform' 
attribute for function arguments.


[1] https://bugs.freedesktop.org/show_bug.cgi?id=97988
[2] 
http://nhaehnle.blogspot.de/2016/10/compiling-shaders-dynamically-uniform.html

> On Oct 24, 2016, at 12:38 PM, Nicolai Hähnle via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi all,
> 
> Some brain-storming on an issue with SPMD/SIMT backend support where I
think some additional IR attributes would be useful. Sorry for the somewhat long
mail; the short version of my current thinking is that I would like to have the
following:
> 
> 1) convergent: a call to a function with this attribute cannot be moved to
have additional control dependencies; i.e., moving it from A to B is only
possible if B dominates or post-dominates A.
> 
> 2) co-convergent (divergent? for lack of a better name...): a call to a
function with this attribute cannot be moved to have _fewer_ control
dependencies; i.e., moving it from A to B is only possible if A dominates or
post-dominates B.
> 
> 3) uniform (for function arguments): transformations are not allowed to
introduce additional non-uniformity in this argument.
Can you describe it in terms that are non-SPMD/SIMT? 
I.e. I’m not sure that “uniformity” refers to an existing LLVM IR concept.

Thanks,

— 
Mehdi
> 
> I'd appreciate input on this proposal, e.g. if this can be solved in an
easier way or if there are obvious problems with this approach.
> 
> Thanks,
> Nicolai
> 
> ..........
> In a nutshell, the problem that this intends to solve is that:
> 
>  %v1 = texelFetch(%sampler, %coord0)
>  %v2 = texelFetch(%sampler, %coord1)
>  %v = select i1 %cond, vType %v1, %v2
> 
> is logically equivalent to and could benefit from being transformed to,
> 
>  %coord = select i1 %cond, cType %coord0, %coord1
>  %v = texelFetch(%sampler, %coord)
> 
> but on the other hand
> 
>  %v1 = texelFetch(%sampler0, %coord)
>  %v2 = texelFetch(%sampler1, %coord)
>  %v = select i1 %cond, vType %v1, %v2
> 
> _must_not_ be transformed to
> 
>  %s = select i1 %cond, sType %sampler0, %sampler1
>  %v = texelFetch(%s, %coord)
> 
> because of uniformity restrictions on the first argument of texelFetch.
> 
> We currently have a shader that is mis-compiled in the wild because
something much like the latter transform is done by SimplifyCFG.[1] There, the
equivalent thing happens with phi nodes:
> 
> if:
>  %v.if = texelFetch(%sampler0, %coord)
>  br label %end
> 
> else:
>  %v.else = texelFetch(%sampler1, %coord)
>  br label %end
> 
> end:
>  %v = phi [ %v.if, %if ], [ %v.else, %else ]
> 
> becomes
> 
>  ...
> end:
>  %s = phi [ %sampler0, %if ], [ %sampler1, %else ]
>  %v = texelFetch(%s, %coord)
> 
> I have collected some more examples at [2]
> 
> The distinctions between all three attribute types mentioned above makes
sense, because there are OpenGL shader intrinsics that naturally carry almost
all of the possible combinations of those attributes.
> 
> That said, a pass that is not SPMD/SIMT-aware must treat every function
call that has a uniform argument as if it were co-convergent, because the input
to the uniform argument could have non-uniformity whose structure correlates
with control dependencies; see [2] for an example. Furthermore, I have not yet
found an operation that needs the co-convergent attribute without also having
uniform arguments. So for the purposes of LLVM, it may be sufficient to add the
'uniform' attribute for function arguments.
> 
> 
> [1] https://bugs.freedesktop.org/show_bug.cgi?id=97988
> [2]
http://nhaehnle.blogspot.de/2016/10/compiling-shaders-dynamically-uniform.html
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 24.10.2016 21:54, Mehdi Amini wrote:
>> On Oct 24, 2016, at 12:38 PM, Nicolai Hähnle via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
>> Some brain-storming on an issue with SPMD/SIMT backend support where I
think some additional IR attributes would be useful. Sorry for the somewhat long
mail; the short version of my current thinking is that I would like to have the
following:
>>
>> 1) convergent: a call to a function with this attribute cannot be moved
to have additional control dependencies; i.e., moving it from A to B is only
possible if B dominates or post-dominates A.
>>
>> 2) co-convergent (divergent? for lack of a better name...): a call to a
function with this attribute cannot be moved to have _fewer_ control
dependencies; i.e., moving it from A to B is only possible if A dominates or
post-dominates B.
>>
>> 3) uniform (for function arguments): transformations are not allowed to
introduce additional non-uniformity in this argument.
>
> Can you describe it in terms that are non-SPMD/SIMT?
> I.e. I’m not sure that “uniformity” refers to an existing LLVM IR concept.
Yeah, that's actually the key problem I've been struggling with.

The first example I sent shows the gist of it. It also shows that the 
concept can't be expressed in terms of the CFG, which makes this tricky.

In a way it's the data-flow analog of the convergent attribute: the 
argument cannot be changed to have additional dependencies in its 
computation. That captures the basic intention, but I'm not completely 
sure that it works.

Thanks,
Nicolai
>
> Thanks,
>
> —
> Mehdi
>
>>
>> I'd appreciate input on this proposal, e.g. if this can be solved
in an easier way or if there are obvious problems with this approach.
>>
>> Thanks,
>> Nicolai
>>
>> ..........
>> In a nutshell, the problem that this intends to solve is that:
>>
>>  %v1 = texelFetch(%sampler, %coord0)
>>  %v2 = texelFetch(%sampler, %coord1)
>>  %v = select i1 %cond, vType %v1, %v2
>>
>> is logically equivalent to and could benefit from being transformed to,
>>
>>  %coord = select i1 %cond, cType %coord0, %coord1
>>  %v = texelFetch(%sampler, %coord)
>>
>> but on the other hand
>>
>>  %v1 = texelFetch(%sampler0, %coord)
>>  %v2 = texelFetch(%sampler1, %coord)
>>  %v = select i1 %cond, vType %v1, %v2
>>
>> _must_not_ be transformed to
>>
>>  %s = select i1 %cond, sType %sampler0, %sampler1
>>  %v = texelFetch(%s, %coord)
>>
>> because of uniformity restrictions on the first argument of texelFetch.
>>
>> We currently have a shader that is mis-compiled in the wild because
something much like the latter transform is done by SimplifyCFG.[1] There, the
equivalent thing happens with phi nodes:
>>
>> if:
>>  %v.if = texelFetch(%sampler0, %coord)
>>  br label %end
>>
>> else:
>>  %v.else = texelFetch(%sampler1, %coord)
>>  br label %end
>>
>> end:
>>  %v = phi [ %v.if, %if ], [ %v.else, %else ]
>>
>> becomes
>>
>>  ...
>> end:
>>  %s = phi [ %sampler0, %if ], [ %sampler1, %else ]
>>  %v = texelFetch(%s, %coord)
>>
>> I have collected some more examples at [2]
>>
>> The distinctions between all three attribute types mentioned above
makes sense, because there are OpenGL shader intrinsics that naturally carry
almost all of the possible combinations of those attributes.
>>
>> That said, a pass that is not SPMD/SIMT-aware must treat every function
call that has a uniform argument as if it were co-convergent, because the input
to the uniform argument could have non-uniformity whose structure correlates
with control dependencies; see [2] for an example. Furthermore, I have not yet
found an operation that needs the co-convergent attribute without also having
uniform arguments. So for the purposes of LLVM, it may be sufficient to add the
'uniform' attribute for function arguments.
>>
>>
>> [1] https://bugs.freedesktop.org/show_bug.cgi?id=97988
>> [2]
http://nhaehnle.blogspot.de/2016/10/compiling-shaders-dynamically-uniform.html
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>