Skip to content

egraphs: fix handling of effectful-but-idempotent ops and GVN.#5800

Merged
cfallin merged 3 commits intobytecodealliance:mainfrom
cfallin:fix-egraph-effectful-gvn
Mar 2, 2023
Merged

egraphs: fix handling of effectful-but-idempotent ops and GVN.#5800
cfallin merged 3 commits intobytecodealliance:mainfrom
cfallin:fix-egraph-effectful-gvn

Conversation

@cfallin
Copy link
Copy Markdown
Member

@cfallin cfallin commented Feb 16, 2023

This PR addresses #5796: currently, ops that are effectful, i.e., remain in the side-effecting skeleton (which we keep in the Layout while the egraph exists), but are idempotent and thus mergeable by a GVN pass, are not handled properly.

GVN is still possible on effectful but idempotent ops precisely because our GVN does not create partial redundancies: it removes an instruction only when it is dominated by an identical instruction. An isntruction will not be "hoisted" to a point where it could execute in the optimized code but not in the original.

However, there are really two parts to the egraph implementation that produce this effect: the deduplication on insertion into the egraph, and the elaboration with a scoped hashmap. The deduplication lets us give a single name (value ID) to all copies of an identical instruction, and then elaboration will re-create duplicates if GVN should not hoist or merge some of them.

Because deduplication need not worry about dominance or scopes, we use a simple (non-scoped) hashmap to dedup/intern ops as "egraph nodes".

When we added support for GVN'ing effectful but idempotent ops (#5594), we kept the use of this simple dedup'ing hashmap, but these ops do not get elaborated; instead they stay in the side-effecting skeleton. Thus, we inadvertently created potential for weird code-motion effects.

The proposal in #5796 would solve this in a clean way by treating these ops as pure again, and keeping them out of the skeleton, instead putting "force" pseudo-ops in the skeleton. However, this is a little more complex than I would like, and I've realized that @jameysharp's earlier suggestion is much simpler: we can keep an actual scoped hashmap separately just for the effectful-but-idempotent ops, and use it to GVN while we build the egraph. In effect, we're fusing a separate GVN pass with the egraph pass (but letting it interact corecursively with egraph rewrites). This is in principle similar to how we keep a separate map for loads and fuse this pass with the egraph rewrite pass as well.

Note that we can use a ScopedHashMap here without the "context" (as needed by CtxHashMap) because, as noted by @jameysharp, in practice the ops we want to GVN have all their args inline. Equality on the InstructionData itself is conservative: two insts whose struct contents compare shallowly equal are definitely identical, but identical insts in a deep-equality sense may not compare shallowly equal, due to list indirection. This is fine for GVN, because it is still sound to skip any given GVN opportunity (and keep the original instructions).

Fixes #5796.

@cfallin cfallin requested a review from jameysharp February 16, 2023 06:12
@cfallin
Copy link
Copy Markdown
Member Author

cfallin commented Feb 16, 2023

IMHO it'd be good to discuss backporting this to 6.0 as well. The release is quite soon, so there is some risk (not much fuzzing time); on the other hand, while it's a somewhat subtle effect (in case of trap, the trap side-effect might reorder with other side-effects), it is in fact a miscompile. Interested in others' thoughts on this!

@github-actions github-actions bot added cranelift Issues related to the Cranelift code generator cranelift:meta Everything related to the meta-language. labels Feb 16, 2023
cfallin added a commit to cfallin/wasmtime that referenced this pull request Feb 16, 2023
This is a short-term fix to the same bug that bytecodealliance#5800 is addressing
(bytecodealliance#5796), but with less risk: it simply turns off GVN'ing of effectful
but idempotent ops. Because we have an upcoming release, and this is a
miscompile (albeit to do with trapping behavior), we would like to make
the simplest possible fix that avoids the bug, and backport it. I will
then rebase bytecodealliance#5800 on top of a revert of this followed by the more
complete fix.
cfallin added a commit to cfallin/wasmtime that referenced this pull request Feb 16, 2023
This is a short-term fix to the same bug that bytecodealliance#5800 is addressing
(bytecodealliance#5796), but with less risk: it simply turns off GVN'ing of effectful
but idempotent ops. Because we have an upcoming release, and this is a
miscompile (albeit to do with trapping behavior), we would like to make
the simplest possible fix that avoids the bug, and backport it. I will
then rebase bytecodealliance#5800 on top of a revert of this followed by the more
complete fix.
cfallin added a commit that referenced this pull request Feb 16, 2023
This is a short-term fix to the same bug that #5800 is addressing
(#5796), but with less risk: it simply turns off GVN'ing of effectful
but idempotent ops. Because we have an upcoming release, and this is a
miscompile (albeit to do with trapping behavior), we would like to make
the simplest possible fix that avoids the bug, and backport it. I will
then rebase #5800 on top of a revert of this followed by the more
complete fix.
cfallin added a commit that referenced this pull request Feb 16, 2023
This is a short-term fix to the same bug that #5800 is addressing
(#5796), but with less risk: it simply turns off GVN'ing of effectful
but idempotent ops. Because we have an upcoming release, and this is a
miscompile (albeit to do with trapping behavior), we would like to make
the simplest possible fix that avoids the bug, and backport it. I will
then rebase #5800 on top of a revert of this followed by the more
complete fix.
This PR addresses bytecodealliance#5796: currently, ops that are effectful, i.e., remain
in the side-effecting skeleton (which we keep in the `Layout` while the
egraph exists), but are idempotent and thus mergeable by a GVN pass, are
not handled properly.

GVN is still possible on effectful but idempotent ops precisely because
our GVN does not create partial redundancies: it removes an instruction
only when it is dominated by an identical instruction. An isntruction
will not be "hoisted" to a point where it could execute in the optimized
code but not in the original.

However, there are really two parts to the egraph implementation that
produce this effect: the deduplication on insertion into the egraph, and
the elaboration with a scoped hashmap. The deduplication lets us give a
single name (value ID) to all copies of an identical instruction, and
then elaboration will re-create duplicates if GVN should not hoist or
merge some of them.

Because deduplication need not worry about dominance or scopes, we use a
simple (non-scoped) hashmap to dedup/intern ops as "egraph nodes".

When we added support for GVN'ing effectful but idempotent ops (bytecodealliance#5594),
we kept the use of this simple dedup'ing hashmap, but these ops do not
get elaborated; instead they stay in the side-effecting skeleton. Thus,
we inadvertently created potential for weird code-motion effects.

The proposal in bytecodealliance#5796 would solve this in a clean way by treating these
ops as pure again, and keeping them out of the skeleton, instead putting
"force" pseudo-ops in the skeleton. However, this is a little more
complex than I would like, and I've realized that @jameysharp's earlier
suggestion is much simpler: we can keep an actual scoped hashmap
separately just for the effectful-but-idempotent ops, and use it to GVN
while we build the egraph. In effect, we're fusing a separate GVN pass
with the egraph pass (but letting it interact corecursively with
egraph rewrites. This is in principle similar to how we keep a separate
map for loads and fuse this pass with the egraph rewrite pass as well.

Note that we can use a `ScopedHashMap` here without the "context" (as
needed by `CtxHashMap`) because, as noted by @jameysharp, in practice
the ops we want to GVN have all their args inline. Equality on the
`InstructinoData` itself is conservative: two insts whose struct
contents compare shallowly equal are definitely identical, but identical
insts in a deep-equality sense may not compare shallowly equal, due to
list indirection. This is fine for GVN, because it is still sound to
skip any given GVN opportunity (and keep the original instructions).

Fixes bytecodealliance#5796.
@cfallin cfallin force-pushed the fix-egraph-effectful-gvn branch from 7d2f84c to ab7c2a5 Compare February 16, 2023 23:04
@cfallin
Copy link
Copy Markdown
Member Author

cfallin commented Feb 16, 2023

Rebased on top of latest main, which includes a temporary lower-risk fix (#5808); this PR now includes a revert of that more temporary fix, and then the more complete fix originally proposed here.

Copy link
Copy Markdown
Contributor

@jameysharp jameysharp left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I believe this is correct, addressing the original desire to GVN more without breaking codegen. Thanks for your patience while it took me a while to review this!

I've already talked with Chris about this, but in case anyone else is looking at this PR: I don't think this is the final form this optimization should take, because it doesn't let us apply any optimizations beyond this limited GVN to these side-effecting instructions. I've written up more on that in #5908. However, this is a good incremental step.

@cfallin cfallin enabled auto-merge March 2, 2023 01:52
@cfallin cfallin added this pull request to the merge queue Mar 2, 2023
Merged via the queue into bytecodealliance:main with commit 7b8854f Mar 2, 2023
@cfallin cfallin deleted the fix-egraph-effectful-gvn branch March 2, 2023 02:46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

cranelift:meta Everything related to the meta-language. cranelift Issues related to the Cranelift code generator

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Cranelift: idempotent instructions have weird interactions with GVN

2 participants