[RFC] Introduce convergence control intrinsics

[sameerds]

Summary

This is a continuation of the original attempt in:
https://reviews.llvm.org/D85603

This change also obsoletes an earlier attempt at restarting the work on
convergence tokens:
https://reviews.llvm.org/D104504

Based on concepts originally outlined by
Nicolai Haehnle <[e-mail]>

Changes relative to D85603:

1. Clean up the definition of a "convergent operation", a convergent call and convergent function.
2. Clean up the relationship between dynamic instances, sets of threads and convergence tokens.
3. Redistribute the formal rules into the definitions of the convergence intrinsics.
4. Expand on the semantics of entering a function from outside LLVM, and the environment-defined outcome of the entry intrinsic.
5. Replace the term "cycle" with "closed path". The static rules are defined in terms of closed paths, and then a relation is established with cycles.
6. Specify that if a function contains a controlled convergent operation, then all convergent operations in that function must be controlled.
7. Describe an optional procedure to infer tokens for uncontrolled convergent operations.
8. Introduce controlled maximal convergence-before and controlled m-converged property as an update to the original properties in UniformityAnalysis

[jsilvanus]

llvm/docs/ConvergentOperations.rst

574

Maybe mention that n is an integer, so

There is an integer *n* such that [..]

725–727

Maybe "does not satisfy" -> "violates"?
In the current form, there is a ambiguity in whether all properties are violated, or just a single one.
I assume a single one is intended?

829–830

I think this property should be communicated more prominently.

Per my understanding, loops in reducible control flow have unique headers, which give rise to a "natural" convergence (implicit maximal convergence?) by counting executions of the header, and considering those converged if the counter agrees.
For irreducible control flow, there are no unique headers, instead there is an ambiguity caused by the dependency on a choice of a cycle hierarchy (and their headers).

Explicit convergence control intrinsincs eliminate this ambiguity by allowing to explicitly define loop hearts. But for reducible control flow, if loop hearts are not placed at loop headers, then the notion of convergence may be different. I believe this is what these lines refer to. For example, in the example in llvm/docs/convergence-heart.png, removing the edge from D to R makes the CFG reducible, but iteration counts at R might be different from iteration counts at H, due to the shortcut from H to L.

Is that intentional, a "neutral" side-effect of the model, or a side-effect of the model that we would want to eliminate but cannot easily?
In any case, I think we should discuss this more explicitly. Also, an example somewhere suggests to construct explicit control intrinsics by putting hearts into loop headers, maybe we can mention there that this ensures that the two notions of convergence agree, because the imaginary counters do.

[nhaehnle]

llvm/docs/ConvergentOperations.rst

829–830

I'd say it's somewhere between intentional and a neutral side-effect. It certainly allows for some interesting experiments.

By the way, the whole loop intrinsic business isn't only about eliminating ambiguity for irreducible loops. Consider:

do {
  do {
    a();
  } while (conda);
  b();
} while (condb);

// vs.
do {
  a();
  if (conda)
    continue;
  b();
} while (condb);

Assuming that conda implies condb, these two loops are semantically identical from a single-threaded perspective and could easily result in identical CFGs. But the "intuitively expected" convergence behavior is very different.

Convergence control allows us to explicitly encode in the IR which of the two intuitive behaviors are expected. (And for the first version of the loop, this would result in two nested loops in the CFG that cannot be collapsed into a single one because the loop intrinsics are "in the way".)

[jsilvanus]

llvm/docs/ConvergentOperations.rst

829–830

Thanks for the background and the example, that definitely helps.

I still feel this should be stated more explicitly, possibly quite at the beginning when introducing these new concepts?

We motivate the use of convergent operations in great detail, but motivate only very briefly why we need to control it explicitly.
An example where naive loop-header-based convergence is not intended would be helpful for that.
Also, generalizing this example, the fact that explicit control intrinsics allow to change the structure of nested loops while preserving convergence semantics.

[jsilvanus]

llvm/docs/ConvergentOperations.rst

829–830

To expand on the above, it probably suffices to add a loop-based example (the one above?) to the list of examples motivating intrinsics, and mention early on that deviating from natural loop-header based convergence is possible and intended, referencing the above new example.

[nhaehnle]

llvm/docs/ConvergentOperations.rst

829–830

Ironically, there's now been some discussion that we may be able to simplify this by only allowing loop hearts in natural loop headers.

They're still required (the example above with the two loops vs. single loop with continue still stands). But yeah, perhaps that could be added to the document.