stage2: Wasm - Integrate lifeness analysis for locals reusal #13193
Conversation
This file contains 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
This hooks reusal of locals into liveness analysis. Meaning that when an operand dies, and is a local, it will automatically be freed so it can be re-used when a new local is required. The result of this, is a lower allocation required for locals. Having less locals means smaller binary size, as well as faster compilation speed when loaded by the runtime.
By reference counting the locals, we can ensure that when we free a local, no local will be reused while it still has references pointing to it. This prevents misscompilations. The compiler will also panic if we free a local more than we reference it, introducing extra safety to ensure they match up.
When reusing an operand it increases the reference count, then when an operand dies it will only decrease the reference count. When this reaches 0, the local will be virtually freed, meaning it can be re-used for a new local.
Upon a branch, we only allow locals to be freed which were allocated within the same branch as where they die. This ensures that when two or more branches target the same operand we do not try to free it more than once. This does however not implement freeing the local upon branch merging yet.
When determining the type of a local (read: register), we would previously subtract the stack locals also. However, this locals are also within the same `locals` list, meaning the type of the local we were retrieving was off by 2. This could create a validation error when we re-use a local of a different type.
Rather than accepting a canonical branch and a target branch we allow to directly merge a branch into the parent branch. This is possible as there's no overlapping and we have infinite registers to our availability. This makes merging a lot simpler.
When we return an operand directly as a result, we must call `reuseOperand`. This commit ensures it's done for all currently- implemented AIR instructions.
'Self' isn't a very good name to describe what it does. This commit changes the type name into `CodeGen` and the parameter to `func` as we're generating code for a function. With this change, the backend's coding style is in line with the self-hosted Wasm-linker.
|
That is some serious progress on the self-hosted Wasm backend - very exciting! |
|
One massive diff in exactly one file. 👨🍳 😗 👌 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
This uses a combination of lifeness analysis and reference counting to 'free' locals virtually so they can be reused for new temporaries and variables. Although Wasm has an infinite amount of locals available to itself, by reducing the number of locals we generate we decrease the binary size as well as the load time when loading the Wasm binary into the runtime. Currently, we only decrease a reference if an operand dies within the same branch it was created. Operands dying inside of a branch is an exercise for later, which won't require any major refactoring as all of the ground has already been done now.
The binary size for the behavior test suite (1074 passing tests), resulted in a decrease of 8259 bytes (1.4%). While not a substantial change, there are a lot of operands dying within other branches, so this could be shaved off more in the future. I still think this was a worthwhile change, regardless of the increased complexity.
Other changes I did also:
valtypewas off by 2 and therefore stored locals into free-lists that had a different type. Causing the Wasm-validator to not pass.selfto a self-explanatory name.