Limit alias regions in Wasm-to-CLIF translation to 256 - #14253
Open
fitzgen wants to merge 2 commits into
Open
Conversation
There were two ways in which alias analysis's `LastStores` state was not a proper lattice, which made the order we processed the worklist and called `LastStores::meet` observable: 1. We didn't have a single, canonical bottom value for the last store to a region. We were taking the first instruction in a block as an identifier for control-flow join points so that we would get different `MemoryLoc`s for different control-flow joins, which is necessary to avoid illegally forwarding a value loaded inside one control-flow join to a load in another, different control-flow join. However, this meant that we effectively had multiple bottom elements, which made the path we descended through the "lattice" observable. The solution here was to create a separate `LastStore` dataflow value that has a single, canonical bottom element, and a distinct `MemoryVersion` value that is the same as `LastStore` but replaces its bottom value with a variant that identifies the associated control-flow join point. We use `LastStore` in our `LastStores` lattice, when we need a bottom element, and we use `MemoryVersion` in our `MemoryLoc` keys, to distinguish between different regions where we don't know anything about the contents of memory. 2. We computed the observed-stores set while we computed the fixpoint of the initial `LastStores` inputs to each block. This was incorrect, however, because a `LastStores` could transiently contain a `LastStore::Inst` that disappears in later iterations of the fixpoint, and which instructions do or don't transiently appear in `LastStores` in that way depends on the order in which we call `LastStores::meet`. Therefore, observing stores while computing the fixpoint might or might not observe an instruction depending on the worklist processing order. The solution in this case was to only compute the observed-stores set after we've computed the `LastStores` fixpoint, at which point there are no transient `LastStore::Inst`s anymore.
Instead of bitpacking the `AliasRegionKey` into a `u32`, hash it and then `xor`-fold the hash down to one byte. Fixes bytecodealliance#14221
github-actions
Bot
added
the
cranelift
Contributor
|
This fixes the problem I reported in #14210. I used the generator script from that issue and ran
Time roughly doubles when N doubles, out to N=8000. The blowup is gone and my FYI, the RPO worklist from #14211 is still 3-5x faster on top of this PR One request: if this misses the 49.0.0 branch on the 5th, could it be |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Instead of bitpacking the
AliasRegionKeyinto au32, hash it and thenxor-fold the hash down to one byte.Fixes #14221
Depends on #14230