summaryrefslogtreecommitdiff
path: root/src/wasm-ir-builder.h
Commit message (Collapse)AuthorAgeFilesLines
* [Parser] Preserve try labels (#6505)Thomas Lively2024-04-171-6/+17
| | | | | | | | | | | | | | | | | | In the standard text format, try scopes can be targeted by both normal branches and delegates, but in Binaryen IR we only allow them to be targeted by delegates, so we have to translate branches to try scopes into branches to wrapper blocks instead. These wrapper blocks must have different names than the try expressions they wrap, so we actually need to track two label names for try expressions: one for delegates and another for normal branches. We previously tried to avoid this complexity by tracking only the branch label and computing the delegate label from the branch label as necessary, but that produced unnecessary wrapper blocks and ugly label names that did not appear in the source. To produce better IR and minimize the diff when switching to the new text parser, bite the bullet and track the delegate and branch label names separately. This eliminates unnecessary wrapper blocks and keeps try names the same as in the wat source where possible.
* [Parser] Match legacy parser block naming (#6504)Thomas Lively2024-04-161-3/+7
| | | | To reduce the size of the test output diff when switching to the new text parser, update it to generate the same block names as the legacy parser.
* [Parser] Pop past unreachables where possible (#6489)Thomas Lively2024-04-161-46/+17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We previously would eagerly drop all concretely typed expressions on the stack when pushing an unreachable instruction. This was semantically correct and closely modeled the semantics of unreachable instructions, which implicitly drop the entire stack and start a new polymorphic stack. However, it also meant that the structure of the parsed IR did not match the structure of the folded input, which meant that tests involving unreachable children would not parse as intended, preventing the test from testing the intended behavior. For example, this wat: ```wasm (i32.add (i32.const 0) (unreachable) ) ``` Would previously parse into this IR: ```wasm (drop (i32.const 0) ) (i32.add (unreachable) (unreachable) ) ``` To fix this problem, we need to stop eagerly dropping stack values when encountering an unreachable instruction so we can still pop expressions pushed before the unreachable as direct children of later instructions. In the example above, we need to keep the `i32.const 0` on the stack so it is available to be popped and become a child of the `i32.add`. However, the naive solution of simply popping past unreachables would produce invalid IR in some cases. For example, consider this wat: ```wasm f32.const 0 unreachable i32.add ``` The naive solution would parse this wat into this IR: ```wasm (i32.add (f32.const 0) (unreachable) ) ``` But we do not want to parse an `i32.add` with an `f32`-typed child. Neither do we want to reject this input, since it is a perfectly valid Wasm fragment. In this case, we actually want the old behavior of dropping the `f32.const` and replacing it with another `unreachable` as the first child of the `i32.add`. To both match the input structure where possible and also gracefully fall back to the old behavior of dropping expressions prior to the unreachable, collect constraints on the types of each child for each kind of expression and compare them to the types of available expressions on the stack when an unreachable instruction will be popped. When the constraints are satisfied, pop expressions normally, even after popping the unreachable instruction. Otherwise, drop the instructions that precede the unreachable instruction to ensure we parse valid IR. To collect the constraints, add a new `ChildTyper` utility that calls a different callback for each kind of possible type constraint for each child. In the future, this utility can be used to simplify the validator as well.
* Typed continuations: suspend instructions (#6393)Frank Emrich2024-03-191-0/+2
| | | | | | | | | | | | | | | | | | | | | This PR is part of a series that adds basic support for the [typed continuations/wasmfx proposal](https://github.com/wasmfx/specfx). This particular PR adds support for the `suspend` instruction for suspending with a given tag, documented [here](https://github.com/wasmfx/specfx/blob/main/proposals/continuations/Overview.md#instructions). These instructions are of the form `(suspend $tag)`. Assuming that `$tag` is defined with _n_ `param` types `t_1` to `t_n`, the instruction consumes _n_ arguments of types `t_1` to `t_n`. Its result type is the same as the `result` type of the tag. Thus, the folded textual representation looks like `(suspend $tag arg1 ... argn)`. Support for the instruction is implemented in both the old and the new wat parser. Note that this PR does not implement validation of the new instruction. This PR also fixes finalization of `cont.new`, `cont.bind` and `resume` nodes in those cases where any of their children are unreachable.
* Typed continuations: cont.bind instructions (#6365)Frank Emrich2024-03-041-0/+3
| | | | | | | | | | | | | | | | | | | | | | | | This PR is part of a series that adds basic support for the [typed continuations/wasmfx proposal](https://github.com/wasmfx/specfx). This particular PR adds support for the `cont.bind` instruction for partially applying continuations, documented [here](https://github.com/wasmfx/specfx/blob/main/proposals/continuations/Overview.md#instructions). In short, these instructions are of the form `(cont.bind $ct_before $ct_after)` where `$ct_before` and `$ct_after` are related continuation types. They must only differ in the number of arguments, where `$ct_before` has _n_ additional parameters as compared to `$ct_after`, for some _n_ ≥ 0. The idea is that `(cont.bind $ct_before $ct_after)` then takes a reference to a continuation of type `$ct_before` as well as _n_ operands and returns a (reference to a) continuation of type `$ct_after`. Thus, the folded textual representation looks like `(cont.bind $ct_before $ct_after arg1 ... argn c)`. Support for the instruction is implemented in both the old and the new wat parser. Note that this PR does not implement validation of the new instruction.
* [Outlining] Fixes break reconstruction (#6352)Ashley Nelson2024-02-271-2/+18
| | | Adds new visitBreakWithType and visitSwitchWithType functions to the IRBuilder API. These functions work around an assumption in IRBuilder that the module is being traversed in the fully nested format, i.e., that the destination scope of a break or switch has been visited before visiting the break or switch. Instead, the type of the destination scope is passed to IRBuilder.
* [Parser] Parse annotations, including source map comments (#6345)Thomas Lively2024-02-261-0/+7
| | | | | | | | | | Parse annotations using the standards-track `(@annotation ...)` format as well as the `;;@ source-map:0:1` format. Have the lexer implicitly collect annotations while it skips whitespace and add lexer APIs to access the annotations since the last token was parsed. Collect annotations before parsing each instruction and pass the annotations explicitly to the parser and parser context functions for instructions. Add an API to `IRBuilder` to set a debug location to be attached to the next visited or created instruction and use it from the parser.
* Typed continuations: cont.new instructions (#6308)Frank Emrich2024-02-221-0/+1
| | | | | | | | | | | | | | | | | This PR is part of a series that adds basic support for the [typed continuations/wasmfx proposal](https://github.com/wasmfx/specfx). This particular PR adds support for the `cont.new` instruction for creating continuations, documented [here(https://github.com/wasmfx/specfx/blob/main/proposals/continuations/Overview.md#instructions). In short, these instructions are of the form `(cont.new $ct)` where `$ct` must be a continuation type. The instruction takes a single (nullable) function reference as its argument, which means that the folded representation of the instruction is of the form `(cont.new $ct (foo ...))`. Support for the instruction is implemented in both the old and the new wat parser. Note that this PR does not implement validation of the new instruction.
* [Parser] Parse `resume` (#6295)Thomas Lively2024-02-091-2/+6
|
* [Parser] Parse pops (by doing nothing) (#6252)Thomas Lively2024-01-301-1/+2
| | | | | | | | | | | | | Parse pop expressions and check that they have the expected types, but do not actually create new Pop expressions or push anything onto the stack because we already create Pop expressions as necessary when visiting the beginning of catch blocks. Unlike the legacy text parser, the new text parser is not capable of parsing pops in invalid locations in the IR. This means that the new text parser will never be able to parse test/lit/catch-pop-fixup-eh-old.wast, which deliberately parses invalid IR to check that the pops can be fixed up and moved to the correct locations. It should be acceptable to delete that test when we turn on the new parser by default, though, so that won't be a problem.
* [Parser] Parse local.set and global.set of tuple values correctly (#6250)Thomas Lively2024-01-291-0/+2
| | | | These instructions always pop a single value, except when tuples are involved, in which case they need special handling to know how many values to pop.
* [Parser] Parse throw_ref (#6238)Thomas Lively2024-01-251-1/+1
|
* [Parser] Parse try_table (#6237)Thomas Lively2024-01-251-2/+28
|
* [Parser] Parse br_if correctly (#6202)Thomas Lively2024-01-041-1/+1
| | | | The new text parser and IRBuilder were previously not differentiating between `br` and `br_if`. Handle `br_if` correctly by popping and assigning a condition.
* [Parser] Parse br_on_cast{_fail} input annotations (#6198)Thomas Lively2024-01-031-1/+1
| | | | And validate in IRBuilder both that the input annotation is valid and that the input matches it.
* [EH] Add instructions for new proposal (#6181)Heejin Ahn2023-12-191-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | This adds basic support for the new instructions in the new EH proposal passed at the Oct CG hybrid CG meeting: https://github.com/WebAssembly/meetings/blob/main/main/2023/CG-10.md https://github.com/WebAssembly/exception-handling/blob/main/proposals/exception-handling/Exceptions.md This mainly adds two instructions: `try_table` and `throw_ref`. This is the bare minimum required to read and write text and binary format, and does not include analyses or optimizations. (It includes some analysis required for validation of existing instructions.) Validation for the new instructions is not yet included. `try_table` faces the same problem with the `resume` instruction in #6083 that without the module-level tag info, we are unable to know the 'sent types' of `try_table`. This solves it with a similar approach taken in #6083: this adds `Module*` parameter to `finalize` methods, which defaults to `nullptr` when not given. The `Module*` parameter is given when called from the binary and text parser, and we cache those tag types in `sentTypes` array within `TryTable` class. In later optimization passes, as long as they don't touch tags, it is fine to call `finalize` without the `Module*`. Refer to https://github.com/WebAssembly/binaryen/pull/6083#issuecomment-1854634679 and #6096 for related discussions when `resume` was added.
* [Parser] Parse tuple operations (#6174)Thomas Lively2023-12-131-2/+7
| | | | | Parse `tuple.make`, `tuple.extract`, and `tuple.drop`. Also slightly improve the way we break up tuples into individual elements in IRBuilder by using a `local.tee` instead of a block containing a `local.set` and `local.get`.
* Preserve multivalue drops in IRBuilder (#6150)Thomas Lively2023-12-131-3/+9
| | | | | | | | | In Binaryen IR, we allow single `Drop` expressions to drop multiple values packaged up as a tuple. When using IRBuilder to rebuild IR containing such a drop, it previously treated the drop as a normal WebAssembly drop that dropped only a single value, producing invalid IR that had extra, undropped values. Fix the problem by preserving the arity of `Drop` inputs in IRBuilder. To avoid bloating the IR, thread the size of the desired value through IRBuilder's pop implementation so that tuple values do not need to be split up and recombined.
* [Parser] Parse the remaining array operations (#6158)Thomas Lively2023-12-121-15/+17
| | | | | | | Parse `array.new_elem`, `array.init_data`, and `array.init_elem`. Accidentally also includes: * [Parser] Parse string types and operations (#6161)
* [Parser] Parse rethrow (#6155)Thomas Lively2023-12-121-1/+2
| | | | Like `delegate`, rethrow takes a `Try` label. Refactor the delegate handling so that `Try` can share its logic.
* [Parser] Parse table operations (#6154)Thomas Lively2023-12-121-6/+6
| | | | Including table.get, table.set, table.size, table.grow, table.fill, and table.copy.
* [Parser] Parse call_indirect and return_call_indirect (#6148)Thomas Lively2023-12-061-1/+2
|
* [Parser] Parse try/catch/catch_all/delegate (#6128)Thomas Lively2023-11-291-4/+76
| | | | | | | | | | | | | | Parse the legacy v3 syntax for try/catch/catch_all/delegate in both its folded and unfolded forms. The first sources of significant complexity is the optional IDs after `catch` and `catch_all` in the unfolded form, which can be confused for tag indices and require backtracking to parse correctly. The second source of complexity is the handling of delegate labels, which are relative to the try's parent scope despite being parsed after the try's scope has already started. Handling this correctly requires punching a whole big enough to drive a truck through through both the parser and IRBuilder abstractions.
* [Parser] Parse tags and throw (#6126)Thomas Lively2023-11-201-1/+2
| | | | Also fix the parser to correctly error if an imported item appears after a non-imported item and make the corresponding fix to the test.
* Fix a bug with unreachable control flow in IRBuilder (#6130)Thomas Lively2023-11-201-0/+1
| | | | | | | | | | | | When branches target control flow structures other than blocks or loops, the IRBuilder wraps those control flow structures with an extra block for the branches to target in Binaryen IR. Usually that block has the same type as the control flow structure it wraps, but when the control flow structure is unreachable because all its bodies are unreachable, the wrapper block may still need to have a non-unreachable type if it is targeted by branches. Previously the wrapper block would also be unreachable in that case. Fix the bug by tracking whether the wrapper block will be targeted by any branches and use the control flow structure's original, non-unreachable type if so.
* [IRBuilder] Add visitCallIndirect and makeCallIndirect (#6127)Ashley Nelson2023-11-211-0/+1
| | | Adds support for call_indirect to wasm-ir-builder. Tests this works by outlining a sequence including call_indirect.
* Update IRBuilder to visit control flow correctly (#6124)Thomas Lively2023-11-161-3/+8
| | | | | | | | | | | Besides If, no control flow structure consumes values from the stack. Fix a bug in IRBuilder that was causing it to pop control flow children. Also fix a follow on bug in outlining where it did not make the If condition available on the stack when starting to visit an If. This required making push() part of the public API of IRBuilder. As a drive-by, also add helpful debug logging to IRBuilder. Co-authored-by: Ashley Nelson <nashley@google.com>
* [Parser] Parse call_ref (#6103)Thomas Lively2023-11-151-1/+2
| | | | Also mark array.new_elem as unimplemented as a drive-by; it previously had an incorrect implementation.
* [Parser] Parse array.new_fixed (#6102)Thomas Lively2023-11-151-1/+2
|
* [Parser] Parse RefAs expressions (#6101)Thomas Lively2023-11-151-1/+1
|
* [Parser] Parse BrOn expressions (#6100)Thomas Lively2023-11-151-1/+2
|
* [Parser] Parse ref.test and ref.cast (#6099)Thomas Lively2023-11-151-2/+2
|
* [Parser] Parse br_table (#6098)Thomas Lively2023-11-151-1/+7
|
* [Parser] Parse ref.func (#6097)Thomas Lively2023-11-151-1/+4
|
* [Parser] Parse `call` and `return_call` (#6086)Thomas Lively2023-11-071-1/+3
| | | | To support parsing calls, add support for parsing function indices and building calls with IRBuilder.
* Implement table.copy (#6078)Alon Zakai2023-11-061-0/+1
| | | Helps #5951
* [Parser] Parse labels and br (#5970)Thomas Lively2023-10-021-13/+64
| | | | | | The parser previously parsed labels and could attach them to control flow structures, but did not maintain the context necessary to correctly parse branches. Support parsing labels as both names and indices in IRBuilder, handling shadowing correctly, and use that support to implement parsing of br.
* Support function contexts in IRBuilder (#5967)Thomas Lively2023-09-221-4/+18
| | | | | | Add a `visitFunctionStart` function to IRBuilder and make it responsible for setting the function's body when the context is closed. This will simplify outlining, will be necessary to support branches to function scope properly, and removes an extra block around function bodies in the new wat parser.
* [Parser] Support loops (#5966)Thomas Lively2023-09-211-2/+20
| | | Parse loops in the new wat parser and add support for them to the IRBuilder.
* [Parser] Parse if-else in the new wat parser and IRBuilder (#5963)Thomas Lively2023-09-211-6/+87
| | | | | | Parse both the straight-line and folded versions of if, including the abbreviations that allow omitting the else clause. In the IRBuilder, generalize the scope stack to be able to track scopes other than blocks and add methods for visiting the beginnings of ifs and elses.
* Fix visitBlock and add visitBlockStart in IRBuilder (#5959)Thomas Lively2023-09-191-7/+12
| | | | | | | | | | Visiting a block should push it onto the stack just like visiting any other expression, but we previously had a `visitBlock` that introduced a new scope instead. Fix `visitBlock` to behave as expected and introduce a new `visitBlockStart` method to introduce a new scope. Unfortunately this cannot be fully tested yet because the wat parser uses the `makeXYZ` API intead of the `visit` API, but at least I updated `makeBlock` to call `visitBlockStart`, so that is tested.
* Implement table.fill (#5949)Thomas Lively2023-09-181-0/+1
| | | | | | | | This instruction was standardized as part of the bulk memory proposal, but we never implemented it until now. Leave similar instructions like table.copy as future work. Fixes #5939.
* Replace I31New with RefI31 everywhere (#5930)Thomas Lively2023-09-131-1/+1
| | | | | | | | Globally replace the source string "I31New" with "RefI31" in preparation for renaming the instruction from "i31.new" to "ref.i31", as implemented in the spec in https://github.com/WebAssembly/gc/pull/422. This would be NFC, except that it also changes the string in the external-facing C APIs. A follow-up PR will make the corresponding behavioral change.
* Refactor IRBuilder to build blocks internally (#5901)Thomas Lively2023-08-281-18/+33
| | | | | | | | | | | | | The initial PR introducing IRBuilder kept the interface the same as the previous internal interface in the new wat parser. This PR updates that interface to avoid exposing implementation details of the IRBuilder and to provide an API that matches the binary format. For example, after calling `makeBlock` or `visitBlock` at the beginning of a block, users now call `visitEnd()` at the end of the block without having to manually install the block's contents. Providing this improved interface requires refactoring some of the IRBuilder internals. While we are refactoring things anyway, put in extra effort to avoid unnecessarily splitting up and recombining tuples that could simply be returned from a multivalue block.
* Factor IRBuilder utility out of the new wat parser (#5880)Thomas Lively2023-08-221-0/+208
Add an IRBuilder utility in a new wasm-ir-builder.h header. IRBuilder is extremely similar to Builder, except that it manages building full trees of Binaryen IR from a linear sequence of instructions, whereas Builder only builds a single IR node at a time. To build full IR trees, IRBuilder maintains an internal stack of expressions, popping children off the stack and pushing the new node onto the stack whenever it builds a new node. In addition to providing makeXYZ function to allocate, initialize, and finalize new IR nodes, IRBuilder also provides a visit() method that can be used when the user has already allocated the IR nodes and only needs to reconstruct the connections between them. This will be useful in outlining both for constructing outlined functions and for reconstructing functions around arbitrary outlined holes. Besides the new wat parser and outlining, this new utility can also eventually be used in the binary parser and to convert from Poppy IR back to Binaryen IR if that ever becomes necessary. To simplify this initial change, IRBuilder exposes the same interface as the code it replaces in the wat parser. A future change requiring more extensive changes to the wat parser will simplify this interface. Also, since the new code is tested only via the new wat parser, it only supports building instructions that were already supported by the new wat parser to avoid trying to support any instructions without corresponding testing. Implementing support for the remaining instructions is left as future work.
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-15 12:56:29 +0000