summaryrefslogtreecommitdiff
path: root/src/ir/possible-contents.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Fix GUFA on calls to function refs in open world (#7135)Alon Zakai2024-12-041-13/+30
| | | | In open world we must assume that a funcref that escapes to the outside might be called.
* [NFC + bugfix] Remove BreakTargetLocation from GUFA (#6956)Alon Zakai2024-09-181-29/+34
| | | | | | | | | | | | | | | | | | | | | | Before, a br would send its value to a BreakTargetLocation. That would then be linked to the target: { br's value } => BreakTargetLocation(target name) => { location of target } This PR skips the middle: { br's value } => { location of target } It just connects breaks directly to the targets. We can do that if we keep a map of the targets as we go. This is 2% faster as well as simplifies the code, as an NFC refactoring. But it also fixes a bug: we have handling on ExpressionLocation that filters values as they come in (they must accord with the expression's type). We were not doing that on BreakTargetLocation, leading to an assert. Removing BreakTargetLocation entirely is easier and better than adding filtering logic for it. Fixes #6955
* [NFC] Refactor LocalGraph's core getSets API (#6877)Alon Zakai2024-08-281-2/+7
| | | | | | | | | | | | | | Before we just had a map that people would access with localGraph.getSetses[get], while now it is a call localGraph.getSets(get), which more nicely hides the internal implementation details. Also rename getSetses => getSetsMap. This will allow a later PR to optimize the internals of this API. This is performance-neutral as far as I can measure. (We do replace a direct read from a data structure with a call, but the call is in a header and should always get inlined.)
* [Exceptions] Finish interpreter + optimizer support for try_table. (#6814)Sébastien Doeraene2024-08-201-2/+32
| | | | | | * Add interpreter support for exnref values. * Fix optimization passes to support try_table. * Enable the interpreter (but not in V8, see code) on exceptions.
* Implement table.init (#6827)Alon Zakai2024-08-161-0/+1
| | | | | Also use TableInit in the interpreter to initialize module's table state, which will now handle traps properly, fixing #6431
* Rename external conversion instructions (#6716)Jérôme Vouillon2024-07-081-1/+1
| | | | | | | | | Rename instructions `extern.internalize` into `any.convert_extern` and `extern.externalize` into `extern.convert_any` to follow more closely the spec. This was changed in https://github.com/WebAssembly/gc/issues/432. The legacy name is still accepted in text inputs and in the C and JS APIs.
* [Strings] Remove stringview types and instructions (#6579)Thomas Lively2024-05-151-20/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | The stringview types from the stringref proposal have three irregularities that break common invariants and require pervasive special casing to handle properly: they are supertypes of `none` but not subtypes of `any`, they cannot be the targets of casts, and they cannot be used to construct nullable references. At the same time, the stringref proposal has been superseded by the imported strings proposal, which does not have these irregularities. The cost of maintaing and improving our support for stringview types is no longer worth the benefit of supporting them. Simplify the code base by entirely removing the stringview types and related instructions that do not have analogues in the imported strings proposal and do not make sense in the absense of stringviews. Three remaining instructions, `stringview_wtf16.get_codeunit`, `stringview_wtf16.slice`, and `stringview_wtf16.length` take stringview operands in the stringref proposal but cannot be removed because they lower to operations from the imported strings proposal. These instructions are changed to take stringref operands in Binaryen IR, and to allow a graceful upgrade path for users of these instructions, the text and binary parsers still accept but ignore `string.as_wtf16`, which is the instruction used to convert stringrefs to stringviews. The binary writer emits code sequences that use scratch locals and `string.as_wtf16` to keep the output valid. Future PRs will further align binaryen with the imported strings proposal instead of the stringref proposal, for example by making `string` a subtype of `extern` instead of a subtype of `any` and by removing additional instructions that do not have analogues in the imported strings proposal.
* GUFA: Handle bottom types in filterDataContents() (#6545)Alon Zakai2024-04-251-1/+7
| | | | | | Normally a bottom type cannot reach there, as we ignore unreachable GC operations early on. However, we can infer a bottom type later during the flow, so we need to handle that (just not error on it, and for clarity during debugging we also clear the contents).
* GUFA: Fix signed reads of packed GC data (#6494)Alon Zakai2024-04-111-1/+68
| | | | | | | GUFA already truncated packed fields on write, which is enough for unsigned gets, but for signed gets we also need to sign them on reads. Similar to #6493 but for GUFA. Also found by #6486
* GUFA: Fix nondeterminism in roots (#6456)Alon Zakai2024-03-291-1/+4
| | | | | Found by the fuzzer. We already processed the work queue in a deterministic order, but the roots were unordered. The work queue's initial state is filled by the roots, so we must process the roots deterministically as well.
* Typed continuations: suspend instructions (#6393)Frank Emrich2024-03-191-0/+4
| | | | | | | | | | | | | | | | | | | | | 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/+4
| | | | | | | | | | | | | | | | | | | | | | | | 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.
* Typed continuations: cont.new instructions (#6308)Frank Emrich2024-02-221-0/+4
| | | | | | | | | | | | | | | | | 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.
* GUFA: Propagate string literals (#6262)Alon Zakai2024-02-011-1/+2
| | | We only noted the type but not the literal value.
* Typed continuations: resume instructions (#6083)Frank Emrich2024-01-111-0/+5
| | | | | This PR is part of a series that adds basic support for the [typed continuations proposal](https://github.com/wasmfx/specfx). This particular PR adds support for the `resume` instruction. The most notable missing feature is validation, which is not implemented, yet.
* [EH] Add instructions for new proposal (#6181)Heejin Ahn2023-12-191-0/+5
| | | | | | | | | | | | | | | | | | | | | | | | 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.
* [NFC] Add LocalLocation for future use (#6105)Alon Zakai2023-11-131-0/+10
| | | | | | This is not needed in GUFA as it tracks local values precisely (each set is connected to the gets that actually read from it), but in a future PR it will be useful to track local values per index (each set is connected to all gets for that index, i.e., each local index is a single "location").
* Implement table.copy (#6078)Alon Zakai2023-11-061-0/+1
| | | Helps #5951
* [NFC] Rename getSuperType to getDeclaredSuperType (#6015)Alon Zakai2023-10-171-1/+1
| | | | A later PR will add getSuperType which will mean "get the general super type - either declared, or not".
* 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.
* [NFC] Remove some unneeded cruft from PossibleContents::intersect() (#5854)Alon Zakai2023-08-021-25/+4
| | | | | | | | In order of appearance in this diff: * Use heapType rather than otherHeapType when either will do, for brevity. * We checked isNull after checking for isLiteral (line 173), but every null is a literal. * Calling setNoneOrNull simplifies some repetitive code. * We checked isLiteral yet again lower down.
* GUFA: Infer using TrapsNeverHappen (#5850)Alon Zakai2023-08-021-11/+550
| | | | | | | | | | | | | | | | | | | | | | | | This adds a TrapsNeverHappen oracle that is used inside the main PossibleContents oracle of GUFA. The idea is that when traps never happen we can reason "backwards" from information to things that must be true before it: temp = x.field; x.cast_to<Y>(); // Y is a subtype of x's type X Here we cast x to a subtype. If we assume traps never happen then the cast must succeed, and that means we can assume we had a Y on the previous line, where perhaps that information lets us infer the value of x.field. This PR focuses on calls, which are the more interesting situation to optimize because other passes do some work already inside functions. Specifically, we look for things that will trap in the called function or the caller, such as if the called function always casts a param to some type, we can assume the caller passes such a type in. And if we have a call_ref then any target that would trap cannot be called (at least in a closed world). This has some benefits, in particular when combined with --gufa-cast-all since that casts more things, which lets us apply the inferences made here. I see 3.3% fewer call_ref instructions on a Kotlin testcase, for example. This helps more on -Os when we inline less.
* PossibleContents: Support more intersection types (#5847)Alon Zakai2023-07-311-26/+66
|
* End the current basic block on a Call (#5823)Alon Zakai2023-07-261-1/+1
| | | | | | | | | | | | | Before this PR, if a call had no paths to a catch in the same function then we skipped creating a new basic block right after it. As a result, we could have a call in the middle of a basic block. If EH is enabled that means we might transfer control flow out of the function from the middle of a block. But it is better to have the property that any transfer of control flow - to another basic block, or outside of the function - can only happen at the end of a basic block. This causes some overhead, but a subsequent PR (#5838) will remove that as a followup, and this PR adds a little code to pass the module and check if EH is enabled, and avoid the overhead if not, which at least avoids regressing the non-EH case until that followup lands.
* [NFC] Refactor each of ArrayNewSeg and ArrayInit into subclasses for ↵Alon Zakai2023-05-041-15/+15
| | | | | | | | | | | Data/Elem (#5692) ArrayNewSeg => ArrayNewSegData, ArrayNewSegElem ArrayInit => ArrayInitData, ArrayInitElem Basically we remove the opcode and use the class type to differentiate them. This adds some code but it makes the representation simpler and more compact in memory, and it will help with #5690
* [Wasm GC] Fix GUFA on array.init of a bottom type (#5675)Alon Zakai2023-04-191-2/+6
|
* [GUFA] Fix packed field filtering (#5652)Alon Zakai2023-04-101-6/+41
| | | | | | | | | | | | | | | | | | | | | | Technically we need to filter both before and after combining, that is, if a location's contents will be filtered by F() then if the new contents are x and old contents y then we need to end up with F(F(x) U F(y)). That is, filtering before is necessary to ensure the union of content does not end up unnecessarily large, and the filtering after is necessary to ensure the final result is properly filtered to fit. (If our representation were perfect then this would not be needed, but it is not, as the union of two exact types can end up as a very large cone, for example.) For efficiency we have been filtering afterwards. But that is not enough for packed fields, it turns out, where we must filter before. If we don't, then if inputs 0 and 0x100 arrive to an i8 field then combining them we get "unknown integer" (which is then filtered by 0xff, but it's too late). By filtering before, the actual values are both 0 and we end up with that as the only possible value. It turns out that filtering before is enough for such fields, so do only that.
* [Wasm GC] Handle packed fields in GUFA and CFP (#5640)Alon Zakai2023-04-071-0/+31
| | | | | The same bug was present in both: We ignored packing, so writing a larger value than fits in the field would lead to us propagating that original value.
* [GUFA] Refine global types during flow (#5639)Alon Zakai2023-04-071-7/+19
| | | | | | | | | | | | Previously (ref.as_non_null (global.get ..)) would return the global with no changes, and if the global was nullable then the type didn't match the output, which hit an assertion (where GUFA checks that the contents match the declared type in the wasm). To fix this, refine global types, that is, the type we track on GlobalInfo may be more refined than the global itself. In the above example, if the global is nullable then the GlobalInfo would point to that global but have a non-nullable type. In fact the code was already prepared for this, and few changes were needed.
* [Wasm GC] Fix GUFA on ArrayInit (#5638)Alon Zakai2023-04-071-3/+14
|
* Implement array.fill, array.init_data, and array.init_elem (#5637)Thomas Lively2023-04-061-1/+16
| | | | | These complement array.copy, which we already supported, as an initial complete set of bulk array operations. Replace the WIP spec tests with the upstream spec tests, lightly edited for compatibility with Binaryen.
* Use Names instead of indices to identify segments (#5618)Thomas Lively2023-04-041-1/+1
| | | | | | | | | | All top-level Module elements are identified and referred to by Name, but for historical reasons element and data segments were referred to by index instead. Fix this inconsistency by using Names to refer to segments from expressions that use them. Also parse and print segment names like we do for other elements. The C API is partially converted to use names instead of indices, but there are still many functions that refer to data segments by index. Finishing the conversion can be done in the future once it becomes necessary.
* [NFC] Internally rename `ArrayInit` to `ArrayNewFixed` (#5526)Thomas Lively2023-02-281-1/+1
| | | | | | | | To match the standard instruction name, rename the expression class without changing any parsing or printing behavior. A follow-on PR will take care of the functional side of this change while keeping support for parsing the old name. This change will allow `ArrayInit` to be used as the expression class for the upcoming `array.init_data` and `array.init_elem` instructions.
* Replace `RefIs` with `RefIsNull` (#5401)Thomas Lively2023-01-091-1/+1
| | | | | | | | | | | | | | | * Replace `RefIs` with `RefIsNull` The other `ref.is*` instructions are deprecated and expressible in terms of `ref.test`. Update binary and text parsing to parse those instructions as `RefTest` expressions. Also update the printing and emitting of `RefTest` expressions to emit the legacy instructions for now to minimize test changes and make this a mostly non-functional change. Since `ref.is_null` is the only `RefIs` instruction left, remove the `RefIsOp` field and rename the expression class to `RefIsNull`. The few test changes are due to the fact that `ref.is*` instructions are now subject to `ref.test` validation, and in particular it is no longer valid to perform a `ref.is_func` on a value outside of the `func` type hierarchy.
* Use C++17's [[maybe_unused]]. NFC (#5309)Sam Clegg2022-12-021-6/+3
|
* Remove equirecursive typing (#5240)Thomas Lively2022-11-231-11/+2
| | | | Equirecursive is no longer standards track and its implementation is extremely complex. Remove it.
* [Wasm GC] Fix a GUFA bug on null call_ref targets (#5262)Alon Zakai2022-11-161-0/+6
| | | | If the target is a bottom type then it is a heap type but it is not a signature type, and we should treat it as unreachable (and not crash).
* [GUFA] [NFC] Remove RefCast special-casing (#5244)Alon Zakai2022-11-141-33/+4
| | | | All that code did was filter contents by the type of the RefCast. We do that for all expressions now, so it was redundant.
* [Wasm GC] Fix nondeterminism in GUFA due to ordering (#5243)Alon Zakai2022-11-111-10/+13
| | | | | | | | | | We don't actually have the distributive property since our PossibleContents representation is an approximation, and the fuzzer found a case where that is noticeable. See more details in the new comment + testcase. I measured speed and memory usage and this actually causes almost no noticeable change.
* Fix possible-contents.h for `array.new_{data,elem}` (#5232)Thomas Lively2022-11-081-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Update MemoryPacking for array.new_data The MemoryPacking pass looks at all instructions that reference memory segments to determine how they can be optimized. #5214 introduced a new instruction that references memory segments, array.new_data, but did not update MemoryPacking accordingly. This omission meant that MemoryPacking could produce invalid or misoptimized modules in the presence of array.new_data. Fix the problem by making MemoryPacking aware of array.new_data. Consider array.new_data when determining whether a segment is used and update array.new_data to reflect the new, optimized segment numberings afterward. To keep things simple, do not try to split any segment that is referred to by a array.new_data instruction. * fix * Add test explanations * Fix possible-contents.h for `array.new_{data,elem}` This code was not properly updated in #5214, so GUFA would incorrectly optimize out `array.new_data` and `array.new_elem` instructions. Fix the problem by making these instructions data flow roots. * fix * move tests
* Implement `array.new_data` and `array.new_elem` (#5214)Thomas Lively2022-11-071-0/+20
| | | | | | | | | In order to test them, fix the binary and text parsers to accept passive data segments even if a module has no memory. In addition to parsing and emitting the new instructions, also implement their validation and interpretation. Test the interpretation directly with wasm-shell tests adapted from the upstream spec tests. Running the upstream spec tests directly would require fixing too many bugs in the legacy text parser, so it will have to wait for the new text parser to be ready.
* [Wasm GC] Fix GUFA on externalize/internalize (#5220)Alon Zakai2022-11-041-3/+22
| | | | | | | These operations emit a completely different type than their input, so they must be marked as roots, and not as things that flow values through them (because then we filter everything out as the types are not compatible). Fixes #5219
* [NFC] Rewrite PossibleContents::combine to be static (#5192)Alon Zakai2022-10-281-50/+43
| | | | | This makes the logic symmetric and easier to read. Measuring speed, this seems identical to before, so that concern seems fine.
* [Wasm GC] Use Cones in GUFA data reads and writes (#5157)Alon Zakai2022-10-191-73/+76
| | | | | | | | | | | When we read from a struct/array using a cone type, read from the types in the cone and nothing else. Previously we used the declared type in the wasm, which might be larger (both in the base type and the depth). Likewise, in a write. To do this, this extends ConeReadLocation with a depth (previously the depth there was assumed to be infinite, and now it is to a potentially limited depth). After this we are fully utilizing cone types in GUFA, as the test changes show (or at least I can't think of any other uses of cones).
* [Wasm GC] [NFC] Remove .type checks from GUFA that are not needed with ↵Alon Zakai2022-10-181-10/+4
| | | | | modern nulls (#5154) Modern nulls never compare equal unless they have the same type too.
* [Wasm GC] Filter GUFA expression locations by their type (#5149)Alon Zakai2022-10-181-17/+132
| | | | | | | | | | | | | | | | | Now that we have a cone type, we are able to represent in PossibleContents the natural content of a wasm location: a type or any of its subtypes. This allows us to enforce the wasm typing rules, that is, to filter the data arriving at a location by the wasm type of the location. Technically this could be unnecessary if we had full implementations of flowFoo and so forth, that is, tailored code for each wasm expression that makes sure we only contain and flow content that fits in the wasm type. Atm we don't have that, and until the wasm spec stabilizes it's probably not worth the effort. Instead, simply filter based on the type, which gives the same result (though it does take a little more work; I measured it at 3% or so of runtime). While doing so normalize cones to their actual maximum depth, which simplifies things and will help more later as well.
* [Wasm GC][GUFA] Avoid Many in roots (#5142)Alon Zakai2022-10-131-8/+16
| | | Instead of Many, use a proper Cone Type for the data, as appropriate.
* [Wasm GC] Fix the intersection of a bottom type null (#5128)Alon Zakai2022-10-121-2/+8
| | | | | When the heap types are not subtypes of each other, but a null is possible, the intersection exists and is a null. That null must be the shared bottom type.
* [Wasm GC] [GUFA] Add initial ConeType support (#5116)Alon Zakai2022-10-111-69/+234
| | | | | | | | | | | A cone type is a PossibleContents that has a base type and a depth, and it contains all subtypes up to that depth. So depth 0 is an exact type from before, etc. This only adds cone type computations when combining types, that is, when we combine two exact types we might get a cone, etc. This does not yet use the cone info in all places (like struct gets and sets), and it does not yet define roots of cone types, all of which is left for later. IOW this is the MVP of cone types that is just enough to add them + pass tests + test the new functionality.
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-07 17:51:49 +0000