This is an archive of the discontinued LLVM Phabricator instance.

[IR] Mark `llvm.trap` as `memory(inaccessiblemem: write)`
ClosedPublic

Authored by jdoerfert on Jul 27 2023, 12:15 PM.

Details

Summary

Traps will not read/write the program state but they need an effect for
preservation, similar to llvm.assume. We really want a new memory kind
for that (see TODO), but for now inaccessiblemem: write is better than
any possible effect.

Diff Detail

Event Timeline

jdoerfert created this revision.Jul 27 2023, 12:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2023, 12:15 PM
jdoerfert requested review of this revision.Jul 27 2023, 12:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 27 2023, 12:15 PM

I just want to get feedback before I fix tests and such.

llvm/include/llvm/IR/Intrinsics.td
1676

Making it inaccessible mem only is certainly correct -- but I'm wondering: Does it even need to have a memory effect at all? After all, it already has a divergence effect by dint of not being willreturn, so it's not legal to drop llvm.trap anyway.

Making it inaccessible mem only is certainly correct -- but I'm wondering: Does it even need to have a memory effect at all? After all, it already has a divergence effect by dint of not being willreturn, so it's not legal to drop llvm.trap anyway.

So with inaccessiblemem and with read none we can loose updates on state prior to the trap, but I think those are outside of our abstract machine.
The only problem I see is a must progress function containing a trap. We could eliminate the call, couldn't we?

I think because we also have assume, the best way forward is memory(artificial: write) for both, or, if we want to have an easier time dropping transitive assumes:
memory(terminate: write) for trap, and memory(assume: write) for llvm.assume. Then you can drop calls to assume only functions if you would not inline them, etc.

Making it inaccessible mem only is certainly correct -- but I'm wondering: Does it even need to have a memory effect at all? After all, it already has a divergence effect by dint of not being willreturn, so it's not legal to drop llvm.trap anyway.

So with inaccessiblemem and with read none we can loose updates on state prior to the trap, but I think those are outside of our abstract machine.
The only problem I see is a must progress function containing a trap. We could eliminate the call, couldn't we?

Yeah, good point. mustprogress + readonly = willreturn, so we need to force a write memory effect to avoid that. In that case memory(inaccessiblemem: write) does seem like the best we can do.

I think because we also have assume, the best way forward is memory(artificial: write) for both, or, if we want to have an easier time dropping transitive assumes:
memory(terminate: write) for trap, and memory(assume: write) for llvm.assume. Then you can drop calls to assume only functions if you would not inline them, etc.

FWIW, I don't think I've ever encountered an optimization failure that was caused by the inaccessiblemem effect on assume (well, apart from the fact that it has any at all -- code that only checks mayWriteToMemory without going though AA does cause problems sometimes). Not opposed to making it more precise, but I'm not sure whether the added precision will really bring much practical value.

In that case memory(inaccessiblemem: write) does seem like the best we can do.

I'll prepare the test changes.

FWIW, I don't think I've ever encountered an optimization failure that was caused by the inaccessiblemem effect on assume (well, apart from the fact that it has any at all -- code that only checks mayWriteToMemory without going though AA does cause problems sometimes). Not opposed to making it more precise, but I'm not sure whether the added precision will really bring much practical value.

I am really more thinking towards the deletion of stray llvm.assumes that came up the other day. I don't have a use case either right now.
This patch is needed though as we get unfortunate initial deductions for the GPU runtime (pre linking). We also need D153311 but that is a different story.

jdoerfert updated this revision to Diff 544935.Jul 27 2023, 2:34 PM

update tests

Making it inaccessible mem only is certainly correct -- but I'm wondering: Does it even need to have a memory effect at all? After all, it already has a divergence effect by dint of not being willreturn, so it's not legal to drop llvm.trap anyway.

So with inaccessiblemem and with read none we can loose updates on state prior to the trap, but I think those are outside of our abstract machine.

That's ok.
If we have

store %foo, @glb
call llvm.trap()

It's perfectly legal to remove the store as it's not observable. Trap doesn't read memory.

Yeah, good point. mustprogress + readonly = willreturn, so we need to force a write memory effect to avoid that. In that case memory(inaccessiblemem: write) does seem like the best we can do.

I don't know why that equality must hold. A function that doesn't return doesn't have to write to memory. We can think of the state has having a halt bit, to where trap, exit(), etc, write to. (exit() reads memory because it executes global destructors though, while trap doesn't).

That said, this change shouldn't even be needed because since trap doesn't return, whatever it writes to is not observable by the rest of the program. I think that noreturn can safely imply write: none.

nikic added a comment.EditedJul 28 2023, 2:08 AM

Yeah, good point. mustprogress + readonly = willreturn, so we need to force a write memory effect to avoid that. In that case memory(inaccessiblemem: write) does seem like the best we can do.

I don't know why that equality must hold.

Here is what LangRef says about mustprogress:

This attribute indicates that the function is required to return, unwind, or interact with the environment in an observable way e.g. via a volatile memory access, I/O, or other synchronization.

We assume that the "interact with the environment" part of this requires at least (something modeled as) a memory write. This means that for a readonly function, the only way to satisfy mustprogress is to return (where return can also be an unwind).

Edit: To clarify, this is supposed to be an implication, not an equality. We certainly can't deduce mustprogress and readonly from willreturn.

A function that doesn't return doesn't have to write to memory. We can think of the state has having a halt bit, to where trap, exit(), etc, write to. (exit() reads memory because it executes global destructors though, while trap doesn't).

That halt bit is effectively what inaccessiblemem: write models.

nlopes accepted this revision.Jul 28 2023, 3:41 AM

Yeah, good point. mustprogress + readonly = willreturn, so we need to force a write memory effect to avoid that. In that case memory(inaccessiblemem: write) does seem like the best we can do.

I don't know why that equality must hold.

Here is what LangRef says about mustprogress:

This attribute indicates that the function is required to return, unwind, or interact with the environment in an observable way e.g. via a volatile memory access, I/O, or other synchronization.

We assume that the "interact with the environment" part of this requires at least (something modeled as) a memory write. This means that for a readonly function, the only way to satisfy mustprogress is to return (where return can also be an unwind).

Edit: To clarify, this is supposed to be an implication, not an equality. We certainly can't deduce mustprogress and readonly from willreturn.

A function that doesn't return doesn't have to write to memory. We can think of the state has having a halt bit, to where trap, exit(), etc, write to. (exit() reads memory because it executes global destructors though, while trap doesn't).

That halt bit is effectively what inaccessiblemem: write models.

I was thinking that this bit is part of the state machine, not of the memory. But it's fair enough to exclude bits that are observable by the program. We have to be careful with functions with float operations and so on, since those can't be nowrite with this definition (as they may read/write rounding mode, etc).

But fair enough, I'm good with that definition. Thanks!

This revision is now accepted and ready to land.Jul 28 2023, 3:41 AM
This revision was landed with ongoing or failed builds.Jul 31 2023, 1:45 PM
This revision was automatically updated to reflect the committed changes.