summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
...
* [NFC] Rename topological_orders.h to topological_sort.h (#6915)Thomas Lively2024-09-076-8/+8
| | | | | Now that the header includes topological sort utilities in addition to the utility that iterates over all topological orders, it makes more sense for it to be named topological_sort.h
* [NFC] Rename the old topological sort utility (#6914)Thomas Lively2024-09-065-15/+15
| | | | This will allow both the old and new topological sort utilities to be included into the same .cpp file while we phase out the old utility.
* [FP16] Fix replace lane for F16x8. (#6906)Brendan Dahl2024-09-062-1/+11
| | | | | | | | | | | | | | | Before this change, replace lane was converting all the F16 lanes to F32 and then replacing one lane with the F16 (I32 representation) value, but it did not then convert all the other lanes back to F16 (I32). To fix this we can just leave the lanes as I32 and replace the one lane. Note: Previous replace lane tests didn't catch this since they started with vectors with all zeros so the F32->I32 didn't matter. Also, other operations don't run into this issue since they iterate over all lanes and convert the F32's back to F16 (I32). --------- Co-authored-by: Alon Zakai <alonzakai@gmail.com>
* Adds a J2CL specific pass that moves itable entries to vtables (#6888)Roberto Lublinerman2024-09-068-0/+592
| | | | | | | | This allows to remove a reference field from all Java objects reducing the per object memory and initialization overhead. The pass is designed to run direclty on the J2CL output before other optimizations since it relies on invariants that might get lost in optimization. If the invariants don't hold the pass aborts.
* Avoid conflicts with public rec groups in MinimizeRecGroups (#6911)Thomas Lively2024-09-062-7/+153
| | | | | | | | | | | | | | | | | | | As with all type optimizations, MinimizeRecGroups only changes private types, which are the only types that are safe to modify. However, it is important for correctness that MinimimizeRecGroups maintain separate type identities for all types, whether public or private, to ensure that casts that should differentiate two types cannot change behavior. Previously the pass worked exclusively on private types, so there was nothing preventing it from constructing a minimial rec group that happened to have the same shape, and therefore type identity, as a public rec group. #6886 exhibits a fuzzer test case where this happens and changes the behavior of the program. Fix the bug by recording all public rec group shapes and resolve conflicts with these shapes by updating the shape of the conflicting non-public type. Fixes #6886.
* [NFC] Avoid wasted LocalGraph work in MergeLocals (#6908)Alon Zakai2024-09-052-1/+31
| | | | | | We computed both get and set influences, but getGetInfluences() was never called, so that work was entirely pointless. This makes the pass 20% faster.
* Version 119 (#6910)Alon Zakai2024-09-052-1/+7
|
* Fix supertype counts when collecting heap types (#6905)Thomas Lively2024-09-0510-95/+75
| | | | | | | We previous incremented the use count for a declared supertype only if it was also a type we had never seen before. Fix the count by treating the supertype the same as any other type used in a type definition. Update tests accordingly, including by manually moving input types around to better match the output.
* [NFC] Add a more powerful API for collecting heap types (#6904)Thomas Lively2024-09-052-116/+177
| | | | | | | | | | | | | | | | | | | | | | | | | Many passes need to know both the set of all used types and also the sets of private or public types. Previously there was no API to get both at once, so getting both required two API calls that internally collected all the types twice. Furthermore, there are many reasons to collect heap types, and they have different requirements about precisely which types need to be collected. For example, in some edge cases the IR can reference heap types that do not need to be emitted into a binary; passes that replace all types would need to collect these types, but the binary writer would not. The existing APIs for collecting types did not distinguish between these use cases, so the code conservatively collected extra types that were not always needed. Refactor the type collecting code to expose a new API that takes a description of which types need to be collected and returns the appropriate types, their use counts, and optionally whether they are each public or private. Keep this change non-functional by commenting on places where the code could be cleaned up or improved rather than actually making the changes. Follow-up PRs will implement the improvements, which will necessarily come with test changes.
* [NFC] Add a lazy mode to LocalGraph (#6895)Alon Zakai2024-09-054-59/+293
| | | | | | | | | | LocalGraph by default will compute all the local.sets that can be read from all local.gets. However, many passes only query a small amount of those. To avoid wasted work, add a lazy mode that only computes sets when asked about a get. This is then used in a single place, LoopInvariantCodeMotion, which becomes 18% faster.
* Only generate string.consts custom section if it is needed (#6893)Goktug Gokdogan2024-09-052-7/+32
|
* [NFC] Use Index instead of size_t in topological sort util (#6903)Thomas Lively2024-09-054-90/+94
| | | | | | This saves memory and could in principle improve performance, although a quick experiment with 30 samples on ReorderGlobals did not yield a statistically significant improvement. At any rate, using Index is more consistent with other parts of the code base.
* Use TopologicalSort::minSort to order rec groups (#6892)Thomas Lively2024-09-0431-538/+525
| | | | | | | | | | | | | | | | Rec groups need to be topologically sorted for the output module to be valid, but the specific order of rec groups also affects the module size because types at lower indices requires fewer bytes to reference. We previously optimized for code size when gathering types by sorting the list of groups before doing the topological sort. This was brittle, though, and depended on implementation details of the topological sort to be correct. Replace the old topological sort with use of the new `TopologicalSort::minSort` utility, which is a more principled method of achieving a minimal topological sort with respect to some comparator. Also draw inspiration from ReorderGlobals and apply an exponential factor to take the users of a rec group into account when determining its weight.
* [NFC] Compute only one dependence graph in ReorderGlobals (#6891)Thomas Lively2024-09-041-28/+18
| | | | | | We previously computed both forward and reverse dependence graphs, but one of them was only used for a single topological sort that could just as well be computed by reversing the topological sort on the other graph.
* [EH] Rename Catch(All)_P3 to Catch(All)_Legacy (NFC) (#6901)Heejin Ahn2024-09-043-10/+11
| | | | | | | This renames `Catch(All)_P3` enum to denote the old Phase 3 `catch(_all)` instructions to `Catch(All)_Legacy`, which sounds clearer. This is also to be consistent with https://github.com/llvm/llvm-project/pull/107187.
* [NFC] Take custom comparator in TopologicalSort::minSort (#6890)Thomas Lively2024-09-045-271/+223
| | | | | | | | | | | | | | | | Rather than finding the minimum sort with respect to the original order of vertices, find the minimum sort with respect to an arbitrary user-provided comparator. Users of the minSort utility previously had to sort their input graphs according to their desired ordering, but now they can simply provide their comparator instead. Take advantage of the new functionality in ReorderGlobals and also standardize on a single data type for representing dependence graphs to avoid unnecessary conversions. Together, these changes slightly speed up ReorderGlobals. Move the topological sort code previously in a .cpp file into the header so the comparator can be provided as a lambda template parameter instead of as a `std::function`. This makes ReorderGlobals about 5% faster.
* [NFC] Convert LocalGraph influences accesses to function calls (#6899)Alon Zakai2024-09-048-32/+40
| | | | | This replaces direct access of the data structure graph.*influences[foo] with a call graph.get*influences(foo). This will allow a later PR to make those calls optionally lazy.
* [CI] Fix GitHub error due to deprecated artifact uploading v1 (#6900)Alon Zakai2024-09-041-1/+1
|
* [EH] Rename BrTarget to Trampoline (NFC) (#6898)Heejin Ahn2024-09-041-30/+34
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This renames "delegate_br_target" to "delegate_trampoline". So how we translate `try`-`delegate` is: - Before: ```wast (try $delegate_target ... (try (do ... ) (delegate $delegate_target) ) ... ) ``` - After: ```wast (try_table $delegate_target (throw_ref (block $delegate_br_target ... (try_table (catch_all $delegate_br_target) ... ) ... ) ) ) ``` So `delegate_br_target` is the destination we branch (via `try_table`) to, in order to rethrow the exnref using `throw_ref`. But given that the translated code does not actually have a `br`, I think this name can be confusing. This renames `br_target` to `trampoline`, given that the block is upon which we bounce the exnref off to reach the real delegate target. This is to be consistent with the variable names in the LLVM implementation (which has not been submitted yet).
* [NFC] Convert HeapStoreOptimization to use a CFG (#6896)Alon Zakai2024-09-031-5/+49
| | | | | | | | | This does not use the CFG yet, so there is no benefit (and likely some small slowdown). The next PR will actually use it to fix a correctness bug. This PR only sets up the CFG and converts the pass to operate on it, without changing any behavior or tests. Followup to #6882
* [NFC] Move optimizeSubsequentStructSet() to a new pass, ↵Alon Zakai2024-09-0311-195/+313
| | | | | | | | | | | | | | | | | | | HeapStoreOptimization (#6882) This just moves code out of OptimizeInstructions to the new pass. The existing test is renamed and now runs the new pass instead. The new pass is run right after each --optimize-instructions invocation, so it should not cause any noticeable effects whatsoever, making this NFC. The motivation here is that there is a bug in the pass, see the new testcase added at the end, which shows the bug. It is not practical to fix that bug in OptimizeInstructions since we need more than peephole optimizations to do so. This PR moves the code to a new pass so we can fix it there properly, later. The new pass is named HeapStoreOptimization since the same infrastructure we will need to fix the bug will also help dead store elimination and related things.
* [NFC] Refactor LocalGraph to split up flow() for future laziness work (#6880)Alon Zakai2024-09-033-93/+165
|
* [NFC] Avoid repeated work in DeadArgumentElimination scanning (#6869)Alon Zakai2024-09-033-61/+141
| | | | | | | | | | | | | | | | | | | This pass may do multiple iterations, and before this PR it scanned the entire module each time. That is simpler than tracking stale data, but it can be quite slow. This PR adds staleness tracking, which makes it over 3x faster (and this can be one of our slowest passes in some cases, so this is significant). To achieve this: * Add a staleness marker on function info. * Rewrite how we track unseen calls. Previously we used atomics in a clever way, * now we just accumulate the data in a simple way (easier for staleness tracking). * Add staleness invalidation in the proper places. * Add a param to localizeCallsTo to allow us to learn when a function is changed. This kind of staleness analysis is usually not worthwhile, but given the 3x plus speedup it seems justified. I fuzzed it directly, and also any staleness bug can lead to validation errors, so normal fuzzing also gives us good coverage here.
* [FP16] Fix max opcode typo. (#6894)Brendan Dahl2024-09-031-1/+1
|
* [FP16] Implement madd and nmadd. (#6878)Brendan Dahl2024-09-0313-41/+207
| | | | | | | | | | | | | | Specified at https://github.com/WebAssembly/half-precision/blob/main/proposals/half-precision/Overview.md A few notes: - The F32x4 and F64x2 versions of madd and nmadd are missing spect tests. - For madd, the implementation was incorrectly doing `(b*c)+a` where it should be `(a*b)+c`. - For nmadd, the implementation was incorrectly doing `(-b*c)+a` where it should be `-(a*b)+c`. - There doesn't appear to be a great way to actually implement a fused nmadd, but the spec allows the double rounded version I added.
* [NFC] Change topological sort utilities to functions (#6889)Thomas Lively2024-09-034-84/+83
| | | | | | | Previously they were structs and their results were accessed with `operator*()`, but that was unnecessarily complicated and could lead to problems with temporary lifetimes being too short. Simplify the utilities by making them functions. This also allows the wrapper templates to infer the proper element types automatically.
* Simplify ReorderGlobals using new topological sort utils (#6885)Thomas Lively2024-08-291-141/+62
| | | | | | | | | | | | | | Use the new TopologicalSort and MinTopologicalSortOf utilities instead of the old CRTP topological sort utility and a bespoke heap-based topological sort in ReorderGlobals. Since there is no longer a heap to pop from, the direction of the custom comparator is now much more intuitive. Further simplify the code by switching from tracking the new order of globals using a sequence of new indices to tracking the order using a sequence of old indices. This change also makes the pass about 20% faster on a large real-world module.
* Add a utility for finding minimal topological sorts (#6884)Thomas Lively2024-08-293-9/+170
| | | | | | | | Reuse the code implementing Kahn's topological sort algorithm with a new configuration that uses a min-heap to always choose the best available element. Also add wrapper utilities that can find topological sorts of graphs with arbitrary element types, not just indices.
* Move lit test temporary files to out/test/ (#6887)Thomas Lively2024-08-291-1/+1
| | | | Previously for in-tree builds, they were put directly into test/, which unnecessarily pollutes the tree.
* Ignore fp16 in the fuzzer (#6881)Alon Zakai2024-08-292-1/+3
| | | | Add the feature flag in V8 invocations, but also disable the feature as it isn't quite ready yet.
* [NFC] Refactor LocalGraph's core getSets API (#6877)Alon Zakai2024-08-2814-68/+84
| | | | | | | | | | | | | | 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.)
* Rename relaxed SIMD fma instructions to match spec. (#6876)Brendan Dahl2024-08-2718-160/+166
| | | | | | | The instructions relaxed_fma and relaxed_fnma have been renamed to relaxed_madd and relaxed_nmadd. https://github.com/WebAssembly/relaxed-simd/blob/main/proposals/relaxed-simd/Overview.md#binary-format
* Check for required actions when parsing wast (#6874)Thomas Lively2024-08-272-3/+19
| | | | | | | | | The parser function for `action` returned a `MaybeResult`, but we were treating it as returning a normal `Result` and not checking that it had contents in several places. Replace the current `action()` with `maybeAction()` and add a new `action()` that requires the action to be present. Fixes #6872.
* [FP16] Implement unary operations. (#6867)Brendan Dahl2024-08-2717-70/+493
| | | | Specified at https://github.com/WebAssembly/half-precision/blob/main/proposals/half-precision/Overview.md
* [NFC] Optimize ParamUtils::getUsedParams() (#6866)Alon Zakai2024-08-265-18/+74
| | | | | | | | | | | | | This constructed a LocalGraph, which computes the sets that reach each get. But all we need to know is which params are live, so instead we can do a liveness computation (which is just a boolean, not the list of sets). Also, it is simple to get the liveness computation to only work on the parameters and not all the locals, as a further optimization. Existing tests cover this, though I did find that the case of unreachability needed a new test. On a large testcase I am looking at, this makes --dae 17% faster.
* Fix null dereference in FunctionValidator (#6849)mtb2024-08-262-2/+25
| | | | | | | | | | visitBlock() and validateCallParamsAndResult() both assumed they were running inside a function, but might be called on global code too. Calls and blocks are invalid in global positions, so we should error there, but must do so properly without a null deref. Fixes #6847 Fixes #6848
* Fix the fp16 header include. (#6871)Brendan Dahl2024-08-261-5/+1
|
* Support more reference constants in wast scripts (#6865)Thomas Lively2024-08-265-25/+52
| | | | | | | | | | | | | | Spec tests use constants like `ref.array` and `ref.eq` to assert that exported function return references of the correct types. Support more such constants in the wast parser. Also fix a bug where the interpretation of `array.new_data` for arrays of packed fields was not properly truncating the packed data. Move the function for reading fields from memory from literal.cpp to wasm-interpreter.h, where the function for truncating packed data lives. Other bugs prevent us from enabling any more spec tests as a result of this change, but we can get farther through several of them before failing. Update the comments about the failures accordingly.
* [FP16] Add a feature flag for FP16. (#6864)Brendan Dahl2024-08-2222-134/+226
| | | Ensure the "fp16" feature is enabled for FP16 instructions.
* [NFC] Avoid quadratic time when precomputing blocks (#6862)Alon Zakai2024-08-211-0/+67
| | | | | | | | | When precomputing fails on a child block of a parent block, there is no point to precompute the parent, as that will fail as well. This makes --precompute on Emscripten's test_biggerswitch go from 1.44 seconds to 0.02 seconds (not a typo, that is 72x faster). The absolute number is not that big, but we do run this pass more than once, so it saves a noticeable chunk of time.
* [NFC] Avoid quadratic time in StackIROptimizer::removeUnneededBlocks() (#6859)Alon Zakai2024-08-211-5/+15
| | | | | | | | | | | | | | | This is in quite ancient code, so it's a long-standing issue, but it got worse when we enabled StackIR in more situations (#6568), which made it more noticeable, I think. For example, testing on test_biggerswitch in Emscripten, the LLVM part is pretty slow too so the Binaryen slowdown didn't stand out hugely, but just doing wasm-opt --optimize-level=2 input.wasm -o output.wasm (that is, do no work, but set the optimize level to 2 so that StackIR opts are run) used to take 28 seconds (!). With this PR that goes down to less than 1.
* Add a string lowering mode disallowing non-UTF-8 strings (#6861)Thomas Lively2024-08-217-2/+46
| | | | | | | | | | | The best way to lower strings is via the "magic imports" API that uses the names of imported string globals as their values. This approach only works for valid UTF-8 strings, though. The existing string-lowering-magic-imports pass falls back to putting non-UTF-8 strings in a JSON custom section, but this requires the runtime to support that custom section for correctness. To help catch errors early when runtimes do not support the strings custom section, add a new pass that uses magic imports and raises an error if there are any invalid strings.
* [FP16] Implement arithmetic operations. (#6855)Brendan Dahl2024-08-2116-11/+549
| | | | Specified at https://github.com/WebAssembly/half-precision/blob/main/proposals/half-precision/Overview.md
* [NFC] hash constant string as void* (#6863)Thomas Lively2024-08-211-1/+1
| | | | | | | | possible-contents.h hashes the location for caught exnrefs by hashing an arbitrary string, "caught-exnref-location". It previously used `std::hash<const char*>` for this, but some standard library implementations report an error when this template instantiation is used because hashing the location of a string is almost never correct. In this case it is fine, so switch to using `std::hash<const void*>`.
* Support `ref.extern n` in spec tests (#6858)Thomas Lively2024-08-2111-2234/+29
| | | | | | | | | | | | | | | | | Spec tests pass the value `ref.extern n`, where `n` is some integer, into exported functions that expect to receive externrefs and receive such values back out as return values. The payload serves to distinguish externrefs so the test can assert that the correct one was returned. Parse these values in wast scripts and represent them as externalized i31refs carrying the payload. We will need a different representation eventually, since some tests explicitly expect these externrefs to not be i31refs, but this suffices to get several new tests passing. To get the memory64 version of table_grow.wast passing, additionally fix the interpreter to handle growing 64-bit tables correctly. Delete the local versions of the upstream tests that can now be run successfully.
* [NFC] Triage spec test problems (#6857)Thomas Lively2024-08-211-81/+80
| | | | Add comments to the spec test skip list briefly explaining why each skipped spec test must be skipped.
* Fix encoding of heap type definitions (#6856)Thomas Lively2024-08-204-988/+24
| | | | | | | | The leading bytes that indicate what kind of heap type is being defined are bytes, but we were previously treating them as SLEB128-encoded values. Since we emit the smallest LEB encodings possible, we were writing the correct bytes in output files, but we were also improperly accepting binaries that used more than one byte to encode these values. This was caught by an upstream spec test.
* Add the upstream spec testsuite as a submodule (#6853)Thomas Lively2024-08-2064-32159/+140
| | | | | | Run the upstream tests by default, except for a large list of them that do not successfully run. Remove the local version of those that do successfully run where the local version is entirely subsumed by the upstream version.
* [Exceptions] Finish interpreter + optimizer support for try_table. (#6814)Sébastien Doeraene2024-08-2041-420/+2764
| | | | | | * Add interpreter support for exnref values. * Fix optimization passes to support try_table. * Enable the interpreter (but not in V8, see code) on exceptions.
* Validate array.init_elem segment in IRBuilder (#6852)Thomas Lively2024-08-192-1/+21
| | | | | | | | | IRBuilder is responsible for validation involving type annotations on GC instructions because those type annotations may not be preserved in the built IR to be used by the main validator. For `array.init_elem`, we were not using the type annotation to validate the element segment, which allowed us to parse invalid modules when the reference operand was a nullref. Add the missing validation in IRBuilder and fix a relevant spec test.