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

Jingyue Wu via llvm-dev
2015-09-22T17:33:19Z

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>