Add an @llvm.sideeffect intrinsic
AcceptedPublic

Authored by sunfish on Wed, Sep 27, 3:09 PM.

Details

Reviewers
hfinkel
Summary

This patch implements Chandler's idea for supporting languages that require support for infinite loops with side effects, such as Rust, providing a solution to bug 965.

Specifically, it adds an llvm.sideeffect() intrinsic, which has no actual effect, but which appears to optimization passes to have obscure side effects, such that they don't optimize away loops containing it. It also teaches several optimization passes to ignore this intrinsic, so that it doesn't significantly impact optimization in most cases.

Diff Detail

Repository
rL LLVM
sunfish created this revision.Wed, Sep 27, 3:09 PM
efriedma added inline comments.
docs/LangRef.rst
14208

A language that needs these is going to be inserting a lot of them; assuming a language doesn't have goto, I think the frontend needs to insert one at the beginning of every function and every loop. Is there some rule for coalescing and/or eliminating llvm.sideeffect calls which aren't necessary?

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5667

Why is it safe to drop the llvm.sideeffect call in SelectionDAG?

sunfish added inline comments.Wed, Sep 27, 4:32 PM
docs/LangRef.rst
14208

Eliminating requires seeing a volatile access, or similar, nearby, because LLVM doesn't know when calls are guaranteed to perform side effects. Coalescing two @llvm.sideeffect calls would be straightforward. I haven't implemented these yet because if there's already a volatile access or an @llvm.sideeffect call nearby, deleting another @llvm.sideeffect call doesn't usually make much difference (to eg. functionattrs).

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5667

Just that SelectionDAG and CodeGen after it don't currently have any optimizations that rely on forward-progress guarantees, and probably won't add them. Those kinds of optimizations are the optimizer's job.

If there's any situation where there's an actual loop in the user code that is at all possible to eliminate, it's always better to find a way to have the optimizer do it, because that's an enabling optimization that will make other parts of the optimizer more powerful.

Is literally the only purpose to handle infinite loops?
If so, please tighten up the description a bit.
(Right now "indicate that the loop shouldn't be optimized away even if it's an infinite
loop with no other side effects." would cover unreachable loops, etc).

Do you expect it to keep provably finite loops that have it alive.
IE a loop where we can prove the backedge is not taken?

Maybe we should do this in follow-up, but I'd also like to see some general text added to the LangRef about the semantics of loops (that makes reference to this intrinsic). Maybe we can say something like:

Loops that contains no calls that access inaccessible memory, perform no atomic or volatile memory access, nor otherwise synchronizes with other threads, are assumed to eventually terminate. If the source-level language has well-defined infinite loops, the LLVM IR representation of such loops should contain at least one call to `@llvm.sideeffect`.

We'll then need to update Clang to insert this intrinsic into loops (in C) that have a constant controlling condition (per C11 6.8.5p6).

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5667

I'm not sure the situation is that straightforward. We can also use this information to assume things about the behavior of expressions that determine loop strip counts, and we might want to do that later in the pipeline too.

We don't have anything that does that now, however, so we'll just need to preserve this somehow if need be.

Is literally the only purpose to handle infinite loops?
If so, please tighten up the description a bit.
(Right now "indicate that the loop shouldn't be optimized away even if it's an infinite
loop with no other side effects." would cover unreachable loops, etc).

Another potential use was mentioned here.

Do you expect it to keep provably finite loops that have it alive.
IE a loop where we can prove the backedge is not taken?

No; a backedge can still be folded away in the normal ways. The llvm.sideeffect call would remain, no longer needed, but not invalid. If it were important, we could add code to remove it in that case, but the patch here doesn't have that.

Is literally the only purpose to handle infinite loops?
If so, please tighten up the description a bit.
(Right now "indicate that the loop shouldn't be optimized away even if it's an infinite
loop with no other side effects." would cover unreachable loops, etc).

Another potential use was mentioned here.

One reason i ask is because ADCE/etc wouldn't even see it. they won't process the block in such a case.
Hence, if the intrinsic relies on always being looked at and then deciding to keep everything containing it, i'd be opposed (since that adds O(N) walks to everything :P).
Right now, it doesn't sound like that's the case.

(If it was, i'd request we either build an analysis like assume analysis, or circularly link these into a separate instruction list in basic blocks so you can tell in O(1) whether they are there)

Do you expect it to keep provably finite loops that have it alive.
IE a loop where we can prove the backedge is not taken?

No; a backedge can still be folded away in the normal ways. The llvm.sideeffect call would remain, no longer needed, but not invalid. If it were important, we could add code to remove it in that case, but the patch here doesn't have that.

SGTM

One reason i ask is because ADCE/etc wouldn't even see it. they won't process the block in such a case.
Hence, if the intrinsic relies on always being looked at and then deciding to keep everything containing it, i'd be opposed (since that adds O(N) walks to everything :P).
Right now, it doesn't sound like that's the case.

If it supports C++, ADCE needs to preserve calls to a library I/O functions, volatile operations, thread synchronizations, and atomic operations, and calls to functions which may perform any of these. Whatever it does to handle those should handle llvm.sideeffect as well.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
5667

It wouldn't be complicated to add an ISD::SIDEEFFECT and TargetOpcode::SIDEEFFECT and carry them all the way through codegen, and to fix the various places that they pessimize, if it turns out to be important.

One reason i ask is because ADCE/etc wouldn't even see it. they won't process the block in such a case.
Hence, if the intrinsic relies on always being looked at and then deciding to keep everything containing it, i'd be opposed (since that adds O(N) walks to everything :P).
Right now, it doesn't sound like that's the case.

If it supports C++, ADCE needs to preserve calls to a library I/O functions, volatile operations, thread synchronizations, and atomic operations, and calls to functions which may perform any of these. Whatever it does to handle those should handle llvm.sideeffect as well.

This seems pretty incongruous to me with your answers to my earlier questions, so i feel like i'm missing something.
Those mechanisms keep loops that are useful alive. They are definition of what makes a loop useful in the first place.
You said that llvm.sideeffect, by itself, should not be a reason to keep it alive if say, you can prove it finite or unreachable. It's only there to keep otherwise infinite empty loops alive.
But if you use the same mechanisms, it will always keep the loop alive, no matter what. Even if it's finite, etc.
In particular, those mechanisms are used to mark things that are still not able to be eliminated, for example, despite the loop being provably finite and otherwise empty.

So if llvm.sideeffect is not like those things, and does not mean the loop should stay alive if it's provably finite and otherwise empty (For example), i fail to see how the existence of those mechanisms helps.

sunfish updated this revision to Diff 117135.Fri, Sep 29, 8:15 AM

This update revises the documentation to clarify that the intrinsic doesn't inherently prevent loops from being optimized away.

If it supports C++, ADCE needs to preserve calls to a library I/O functions, volatile operations, thread synchronizations, and atomic operations, and calls to functions which may perform any of these. Whatever it does to handle those should handle llvm.sideeffect as well.

This seems pretty incongruous to me with your answers to my earlier questions, so i feel like i'm missing something.

The basic idea of llvm.sideeffect is to just be a thing that gets treated like it has side effects. It's just like a volatile store through a non-escaped memory address.

I may have been unclear when you asked

Do you expect it to keep provably finite loops that have it alive.
IE a loop where we can prove the backedge is not taken?

and I said

No; a backedge can still be folded away in the normal ways. The llvm.sideeffect call would remain, no longer needed, but not invalid. If it were important, we could add code to remove it in that case, but the patch here doesn't have that.

I interpreted your question to be just about loops where we can prove the backedge is not taken. llvm.sideeffect does keep finite loops alive under the same conditions that other operations with side effects would.

In the future, we may want to optimize away redundant llvm.sideeffect calls, and an advanced form of this could allow optimizing away provably-finite loops containing llvm.sideeffect, however, the current patch doesn't depend on this.

This update revises the documentation to clarify that the intrinsic doesn't inherently prevent loops from being optimized away.

If it supports C++, ADCE needs to preserve calls to a library I/O functions, volatile operations, thread synchronizations, and atomic operations, and calls to functions which may perform any of these. Whatever it does to handle those should handle llvm.sideeffect as well.

This seems pretty incongruous to me with your answers to my earlier questions, so i feel like i'm missing something.

The basic idea of llvm.sideeffect is to just be a thing that gets treated like it has side effects. It's just like a volatile store through a non-escaped memory address.

I may have been unclear when you asked

Do you expect it to keep provably finite loops that have it alive.
IE a loop where we can prove the backedge is not taken?

and I said

No; a backedge can still be folded away in the normal ways. The llvm.sideeffect call would remain, no longer needed, but not invalid. If it were important, we could add code to remove it in that case, but the patch here doesn't have that.

I interpreted your question to be just about loops where we can prove the backedge is not taken. llvm.sideeffect does keep finite loops alive under the same conditions that other operations with side effects would.

In the future, we may want to optimize away redundant llvm.sideeffect calls, and an advanced form of this could allow optimizing away provably-finite loops containing llvm.sideeffect, however, the current patch doesn't depend on this.

Okay, that helps, thanks.

hfinkel accepted this revision.Tue, Oct 3, 7:45 PM

LGTM

This revision is now accepted and ready to land.Tue, Oct 3, 7:45 PM