Stream: git-wasmtime

Topic: wasmtime / issue #8004 Cranelift: egraph rule subsumption...

Wasmtime GitHub notifications bot (Feb 28 2024 at 01:21):

jameysharp added the bug label to Issue #8004.

Wasmtime GitHub notifications bot (Feb 28 2024 at 01:21):

jameysharp added the cranelift label to Issue #8004.

Wasmtime GitHub notifications bot (Feb 28 2024 at 01:21):

jameysharp opened issue #8004:

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

Last updated: Nov 22 2024 at 16:03 UTC