<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/xhtml; charset=utf-8">
</head>
<body>
<div style="font-family:sans-serif"><div style="white-space:normal">
<p dir="auto">n 2 Jun 2021, at 2:02, Sameer Sahasrabuddhe wrote:</p>
</div>
<div style="white-space:normal"><blockquote style="border-left:2px solid #3983C4; color:#3983C4; margin:0 0 5px; padding-left:5px"><p dir="auto">Sameer Sahasrabuddhe via llvm-dev writes:<br>
</p>
<blockquote style="border-left:2px solid #3983C4; color:#7CBF0C; margin:0 0 5px; padding-left:5px; border-left-color:#7CBF0C"><p dir="auto">TL;DR<br>
=====<br>
<br>
We propose the following changes to LLVM IR in order to better support<br>
operations that are sensitive to the set of threads that execute them<br>
together:<br>
<br>
- Redefine "convergent" in terms of thread divergence in a<br>
multi-threaded execution.<br>
- Fix all optimizations that examine the "convergent" attribute to also<br>
depend on divergence analysis. This avoids any impact on CPU<br>
compilation since control flow is always uniform on CPUs.<br>
- Make all function calls "convergent" by default (D69498). Introduce a<br>
new "noconvergent" attribute, and make "convergent" a nop.<br>
- Update the "convergence tokens" proposal to take into account this new<br>
default property (D85603).</p>
</blockquote></blockquote></div>
<div style="white-space:normal">
<p dir="auto">I would suggest a slightly different way of thinking of this.</p>
<p dir="auto">It’s not really that functions are defaulting to convergence,<br>
it’s that they’re defaulting to not participating in the convergence<br>
analysis. A function that does participate in the analysis should have<br>
a way to mark itself as being convergent. A function that participates<br>
and isn’t marked convergent should probably default to being<br>
non-convergent, because that’s the conservative assumption (I believe).<br>
But if a function doesn’t participate in the analysis at all, well,<br>
it just doesn’t apply.</p>
<p dir="auto">At an IR level, there are a couple of different ways to model this.<br>
One option is to have two different attributes, e.g.<br>
<code>hasconvergence convergent</code>. But the second attribute would be<br>
meaningless without the first, and clients would have to look up<br>
both, which is needlessly inefficient. The other option is to<br>
have one attribute with an argument, e.g. <code>convergent(true)</code>.<br>
Looking up the attribute would give you both pieces of information.</p>
<p dir="auto">GPU targets would presumably require functions (maybe just<br>
definitions?) to participate in the convergence analysis. Or maybe<br>
they could have different default rules for functions that don’t<br>
participate than CPU targets do. Either seems a reasonable choice<br>
to me.</p>
<p dir="auto">If the inliner wants to inline non-participating code into participating<br>
code, or vice-versa, it either needs to refuse or to mark the resulting<br>
function as non-participating.</p>
<p dir="auto">I know this is a little bit more complex than what you’re describing,<br>
but I think it’s useful complexity, and I think it’s important to set<br>
a good example for how to handle this kind of thing. Non-convergence<br>
is a strange property in many ways because of its dependence on the<br>
exact code structure rather than simply the code’s ordinary semantics.<br>
But if you consider it more abstractly in terms of the shape of the<br>
problem, it’s actually a very standard example of an “effect”, and<br>
convergence analysis is just another example of an “effect analysis”,<br>
which is a large class of analyses with the same basic structure:</p>
<ul>
<li>There’s some sort of abstract effect.</li>
<li>There are some primitive operations that have the effect.</li>
<li>The effect normally propagates through abstractions: if code calls
other code that has the effect, the calling code also has the effect.</li>
<li>The propagation is disjunctive: a code sequence has the effect
if any part of the sequence has the effect.</li>
<li>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.</li>
<li>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).</li>
<li>Clients are usually trying to prove that code <em>doesn’t</em> have the
effect, because that gives them more flexibility.</li>
<li>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.</li>
</ul>
<p dir="auto">The thing is, people are constantly inventing new effect analyses.<br>
LLVM has some built-in analyses that are basically effect analyses,<br>
like “does this touch global memory” or “does this have any<br>
side-effects”. Maybe soon we’ll want to do a new general analysis<br>
in LLVM to check whether a function synchronizes with other threads<br>
(in the more standard atomics/locks sense, not GPU thread<br>
communication). Maybe somebody will add a language-specific analysis<br>
to track if a function ever runs “unsafe” code. Maybe somebody will<br>
want to do an environment-specific analysis that checks whether a<br>
function ever makes an I/O call. Who knows? But they come up a lot,<br>
and LLVM doesn’t deal with them very well when it can’t make nice<br>
assumptions like “all the code came from the same frontend and<br>
is correctly participating in the analysis”.</p>
<p dir="auto">Convergence is important enough for GPUs that maybe it’s worthwhile<br>
for all GPU frontends — and so all functions in a module — to<br>
participate in it. A lot of these other analyses, well, probably<br>
not. And we shouldn’t be totally blocked from doing interprocedural<br>
optimization in LLVM just because we’re combining things from<br>
different frontends.</p>
<p dir="auto">So my interest here is that I’d like the IR for convergence to set<br>
a good example for how to model this kind of effect analysis.<br>
I think that starts with acknowledging that maybe not all<br>
functions are participating in the analysis and that that’s okay.<br>
And I think that lets us more neatly talk about what we want for<br>
convergence: either you want to require that all functions in the<br>
module participate in the analysis, or you want to recognize<br>
non-participating code and treat it more conservatively.</p>
<p dir="auto">Other than that, I don’t much care about the rest of the details;<br>
this isn’t my domain, and you all know what you’re trying to<br>
do better than I do.</p>
<p dir="auto">John.</p>
</div>
</div>
</body>
</html>