[llvm-dev] [RFC] Refinement of convergent semantics

[Jingyue Wu via llvm-dev]

Hi Owen,

This is very interesting.

How different is "convergent" from "uniform"? An instruction is uniform if
threads in the same SIMT unit (e.g. warp) do not diverge when executing
this instruction.

I ask this because Bjarke recently came up with a mathematical definition
of uniformity. I wonder if that is a foundation "convergent" needs as well.
AFAICT, Bjarke's definition of "uniformity" is less restrictive than
"convergent". For example, it allows loop unswitching the following code if
"c" is uniform, which seems a case you ideally want to allow.

DISALLOWED:
for (…) {
  if (c) { … }
  convergent();
}

Jingyue

On Fri, Sep 4, 2015 at 1:25 PM, Owen Anderson via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Hi all,
>
> In light of recent discussions regarding updating passes to respect
> convergent semantics, and whether or not it is sufficient for barriers, I
> would like to propose a change in convergent semantics that should resolve
> a lot of the identified problems regarding loop unrolling, loop
> unswitching, etc.  Credit to John McCall for talking this over with me and
> seeding the core ideas.
>
> Today, convergent operations may only be moved into control-equivalent
> locations, or, in layman’s terms, a convergent operation may neither be
> sunk into nor hoisted out of, a condition.  This causes problems for full
> loop unrolling, as the control dependence on the loop counter is
> eliminated, but our intuition indicates that this dependence was somehow
> trivial.  More concretely, all know uses of convergent are OK with full
> unrolling, making this semantic undesirable.  Related problems arise in
> loop unswitching as well.
>
> The proposed change is to split the semantics of convergent into two
> annotations:
>         convergent - this operation may not be made control dependent on
> any additional values (aka may not be sunk into a condition)
>         nospeculate - this operation may not be added to any program trace
> on which it was not previously executed (same as notrap?)
>
> Most of today’s convergent operations (barriers, arithmetic gradients)
> would continue to be marked only as convergent.  The new semantics would
> allow full loop unrolling, and provide clarity on which loop unswitching
> operations are allowed, examples below.
>
> The one case where nospeculate would also be needed is in the case of
> texture fetches that compute implicit gradients.  Because the computed
> gradient forms part of the addressing mode, gibberish gradients here can
> cause invalid memory dereferences.
>
> —Owen
>
> ——————————————————
>
> Loop Unswitching Examples
>
> ALLOWED:
> for (…) {
>   if (c) { convergent(); }
> }
>
> DISALLOWED:
> for (…) {
>   if (c) { … }
>   convergent();
> }
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150922/cc9cb45b/attachment.html>