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

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
>

On 25.10.2016 01:11, Nicolai Hähnle wrote:
> 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.
One big question is whether there are transformations in LLVM today that 
replace a value %a with a value %b, where %b "has additional 
dependencies in its computation". I can't think of anything obvious 
where that would be the case, but I'm not sure.

Nicolai


>
> 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
>>

> On Oct 24, 2016, at 4:15 PM, Nicolai Hähnle <nhaehnle at gmail.com>
wrote:
> 
> On 25.10.2016 01:11, Nicolai Hähnle wrote:
>> 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.
> 
> One big question is whether there are transformations in LLVM today that
replace a value %a with a value %b, where %b "has additional dependencies
in its computation". I can't think of anything obvious where that would
be the case, but I'm not sure.
What do you mean by “additional dependencies in its computation" here? 

— 
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
>>>