[llvm-dev] RFC: make calls "convergent" by default

[John McCall via llvm-dev]

n 2 Jun 2021, at 2:02, Sameer Sahasrabuddhe wrote:
> Sameer Sahasrabuddhe via llvm-dev writes:
>
>> TL;DR
>> =====
>>
>> We propose the following changes to LLVM IR in order to better support
>> operations that are sensitive to the set of threads that execute them
>> together:
>>
>> - Redefine "convergent" in terms of thread divergence in a
>>   multi-threaded execution.
>> - Fix all optimizations that examine the "convergent" attribute to also
>>   depend on divergence analysis. This avoids any impact on CPU
>>   compilation since control flow is always uniform on CPUs.
>> - Make all function calls "convergent" by default (D69498). Introduce a
>>   new "noconvergent" attribute, and make "convergent" a nop.
>> - Update the "convergence tokens" proposal to take into account this new
>>   default property (D85603).

I would suggest a slightly different way of thinking of this.

It’s not really that functions are defaulting to convergence,
it’s that they’re defaulting to not participating in the convergence
analysis.  A function that does participate in the analysis should have
a way to mark itself as being convergent.  A function that participates
and isn’t marked convergent should probably default to being
non-convergent, because that’s the conservative assumption (I believe).
But if a function doesn’t participate in the analysis at all, well,
it just doesn’t apply.

At an IR level, there are a couple of different ways to model this.
One option is to have two different attributes, e.g.
`hasconvergence convergent`.  But the second attribute would be
meaningless without the first, and clients would have to look up
both, which is needlessly inefficient.  The other option is to
have one attribute with an argument, e.g. `convergent(true)`.
Looking up the attribute would give you both pieces of information.

GPU targets would presumably require functions (maybe just
definitions?) to participate in the convergence analysis.  Or maybe
they could have different default rules for functions that don’t
participate than CPU targets do.  Either seems a reasonable choice
to me.

If the inliner wants to inline non-participating code into participating
code, or vice-versa, it either needs to refuse or to mark the resulting
function as non-participating.

I know this is a little bit more complex than what you’re describing,
but I think it’s useful complexity, and I think it’s important to set
a good example for how to handle this kind of thing.  Non-convergence
is a strange property in many ways because of its dependence on the
exact code structure rather than simply the code’s ordinary semantics.
But if you consider it more abstractly in terms of the shape of the
problem, it’s actually a very standard example of an “effect”, and
convergence analysis is just another example of an “effect analysis”,
which is a large class of analyses with the same basic structure:

- There’s some sort of abstract effect.
- There are some primitive operations that have the effect.
- The effect normally propagates through abstractions: if code calls
  other code that has the effect, the calling code also has the effect.
- The propagation is disjunctive: a code sequence has the effect
  if any part of the sequence has the effect.
- Often it is rare to see the primitive operations explicitly in code,
  and the analysis is largely about propagation.  Sometimes the
  primitive operations aren’t even modeled in IR at all, and the
  only source of the effect in the model is that calls to unknown
  functions have to be treated conservatively.
- Sometimes there are ways of preventing propagation; this is
  usually called “handling” the effect.  But a lot of effects don’t
  have this, and the analysis purely about whether one of the
  primitive operations is ever performed (directly or indirectly).
- Clients are usually trying to prove that code *doesn’t* have the
  effect, because that gives them more flexibility.
- Code has to be assumed to have the effect by default, but if you
  can prove that a function doesn’t have the effect, you can often
  propagate that information.

The thing is, people are constantly inventing new effect analyses.
LLVM has some built-in analyses that are basically effect analyses,
like “does this touch global memory” or “does this have any
side-effects”.  Maybe soon we’ll want to do a new general analysis
in LLVM to check whether a function synchronizes with other threads
(in the more standard atomics/locks sense, not GPU thread
communication).  Maybe somebody will add a language-specific analysis
to track if a function ever runs “unsafe” code.  Maybe somebody will
want to do an environment-specific analysis that checks whether a
function ever makes an I/O call.  Who knows?  But they come up a lot,
and LLVM doesn’t deal with them very well when it can’t make nice
assumptions like “all the code came from the same frontend and
is correctly participating in the analysis”.

Convergence is important enough for GPUs that maybe it’s worthwhile
for all GPU frontends — and so all functions in a module — to
participate in it.  A lot of these other analyses, well, probably
not.  And we shouldn’t be totally blocked from doing interprocedural
optimization in LLVM just because we’re combining things from
different frontends.

So my interest here is that I’d like the IR for convergence to set
a good example for how to model this kind of effect analysis.
I think that starts with acknowledging that maybe not all
functions are participating in the analysis and that that’s okay.
And I think that lets us more neatly talk about what we want for
convergence: either you want to require that all functions in the
module participate in the analysis, or you want to recognize
non-participating code and treat it more conservatively.

Other than that, I don’t much care about the rest of the details;
this isn’t my domain, and you all know what you’re trying to
do better than I do.

John.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20210602/f48b1c46/attachment.html>