[llvm-dev] [RFC] Introducing convergence control bundles and intrinsics

[Nicolai Hähnle via llvm-dev]

Hi Owen,

On 29.10.20 02:59, Owen Anderson wrote:
>> On Oct 28, 2020, at 3:13 PM, Nicolai Hähnle via llvm-dev 
>> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>>
>> The presentation from the dev meeting three weeks ago is here:
>> https://www.youtube.com/watch?v=_Z5DuiVCFAw
> 
> I have not studied the new proposal yet, but I wanted to ask a question 
> about the JumpThreading example in your dev meeting talk: does allowing 
> this transformation break programs?
> 
> I’m asking because my reading of the semantic correctness of the 
> jump-threading transformation is that it *is* allowed by the current 
> convergent annotation: the execution of the barrier() intrinsic depends 
> on the value of `condition` in both the before and after cases.  In the 
> former, it is a transitive dependency via `flag`, but still a 
> dependency.  This seems to differ from your interpretation of the 
> example, so I’m wondering to what degree clarifying the definition to 
> include transitive dependencies would eliminate some or all spooky 
> action, and whether doing so would result in broken programs.

Perhaps part of the problem is the notion of "control dependence" that 
the current definition of `convergent` relies on. I don't actually know 
if there's a universally accepted definition in the literature. The one 
I kept finding and that made sense to me as being usable in practice in 
a compiler is only in terms of divergent terminators and post-dominance. 
The data dependencies of `flag` in the original program aren't relevant.

With that definition of control dependence, the barrier() is initially 
not dependent on the branch on `condition`, because that branch is 
post-dominated by the intermediate basic block and therefore hidden.

In more practical terms, the transform really could result in a broken 
program depending on how the underlying implementation does divergence 
and reconvergence. This particular example shouldn't change anything wrt 
the current implementation in AMDGPU, for example, but it would break an 
implementation based on reconverging at post-dominators (which is 
documented in the literature as well).

Cheers,
Nicolai



> 
> Thanks,
> 
> —Owen
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-- 
Lerne, wie die Welt wirklich ist,
Aber vergiss niemals, wie sie sein sollte.