bytecodealliance / bytecodealliance/wasmtime
Cranelift: egraph rule subsumption is too aggressive
- Dominant language
- Rust
- Stars
- 18.6k
- Forks
- 1.8k
- Avg merge
- 1d 18h
- Merged PRs (30d)
- 126
Description
In `cranelift/codegen/src/egraph.rs`, `OptimizeCtx::subsume_values` is shared among all the recursive invocations of `optimize_pure_enode` and the `simplify` constructor. That means using `subsume` in one rule can cause a rule applied to a different instruction to behave as if it used `subsume` as well, if the latter happens to return the same value as the former.
This is not a correctness bug: it does not cause rules to apply when they shouldn't. It just means we're pruning the e-graph more aggressively than I think we intended to, which means we may be missing optimizations.
I noticed this while investigating #7999 but that is an overly complicated reproducer for this issue.
A too-simple test case is `imul v0, (iconst 1)`.
- This should get rewritten to `ishl v0, (iconst 0)` because 1 is a power of two (though that's another thing we might want to change).
- When that new `ishl` is recursively optimized, it should be subsumed to `v0` because a shift by 0 is a no-op.
- Then we return to optimizing the `imul` and see that the result of the `ishl` rule has been returned as `v0`, which is already subsumed because of this bug, and we ignore any other `imul` optimization rules as a result.
That isn't a great test case because frankly that's a desirable outcome in that case. But I think we should discuss this more generally because I don't think this is how `subsume` was intended to work.
cc: @elliottt @cfallin @lpereira
Contributor guide
Assessment
This issue has not been assessed yet.