Page MenuHomePhabricator

Update langref to indicate that calls may be convergent.

Authored by jlebar on Feb 16 2016, 4:52 PM.



As previously written, only functions could be convergent. But calls
need to have a notion of convergence as well.

To see why this is important, consider an indirect call. We may or may
not want to disable optimizations around it and behave as though we're
calling a convergent function -- it depends on the semantics of the
language we're compiling. Thus the need for this attr on the call.

Diff Detail


Event Timeline

jlebar updated this revision to Diff 48128.Feb 16 2016, 4:52 PM
jlebar retitled this revision from to Update langref to indicate that calls may be convergent..
jlebar updated this object.
jlebar added reviewers: resistor, jingyue, mehdi_amini.
jlebar added subscribers: hfinkel, chandlerc, arsenm and 3 others.
jingyue accepted this revision.Feb 16 2016, 10:03 PM
jingyue edited edge metadata.
This revision is now accepted and ready to land.Feb 16 2016, 10:03 PM
mehdi_amini requested changes to this revision.Feb 16 2016, 10:07 PM
mehdi_amini edited edge metadata.

What happens on inline?

This revision now requires changes to proceed.Feb 16 2016, 10:07 PM
In D17314#354379, @joker.eph wrote:

What happens on inline?

We can clarify this if you want (there are no restrictions on inlining a call to a convergent function), but inasmuch as it's unclear, I think it may speak to a larger problem with the way we're describing this, and I'm afraid that calling out inlining specifically may just paper over the issue. For example, what about outlining? Someone more familiar with LLVM than I can probably come up with other edge cases.

The most concrete way I have to explain this is something like:

There are certain instructions, e.g. llvm.cuda.syncthreads(), that must never be made control-flow dependent on additional values. This applies transitively through function calls (so long as they are marked convergent). That is, if a call is convergent, then we must behave as though the call will trigger a convergent instruction (unless we can prove otherwise), and therefore we can't make the call control-flow dependent on additional values, because that would make our putative convergent instruction control-flow dependent on additional values.

I think this makes it relatively clear that inlining/outlining is OK -- the issue is just that you can't put additional control-dependencies in the way of an eventual call to syncthreads. This is also how I'd explain this notion of convergence to someone IRL.

As I see it, the problem as currently written is that we make no distinction between different "types" of convergent functions. But we can remove "convergent" from any function which doesn't invoke any convergent is it turtles all the way down? Like, if you can see the full program source, can you just drop "convergent" everywhere? Clearly not, because there are leaves: these special instructions such as syncthreads. If it weren't for these leaves, we really *could* drop convergent everywhere, in the presence of full source.

In the spec we treat these special instructions the same as functions that you can't see the source of, and I grant that they behave the same, from the perspective of the compiler. But to at least one human, they're not at all the same. If we could agree on clarifying that, I think we might make this whole thing a lot better.

But if we can't, I'll just add a note about inlining. :)

mehdi_amini accepted this revision.Feb 16 2016, 11:30 PM
mehdi_amini edited edge metadata.

I think the last paragraph may be enough to me. Please see the two nits.

1252 ↗(On Diff #48128)

"When the appears" does not seem right to me. "When it appears"?

1260 ↗(On Diff #48128)

"does not run" sounds odd, what about "can call" instead?

This revision is now accepted and ready to land.Feb 16 2016, 11:30 PM
jlebar marked 2 inline comments as done.Feb 17 2016, 9:42 AM

Thank you for the review. :)

This revision was automatically updated to reflect the committed changes.