| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
|
| |
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
|
| |
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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>
|
| |
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
We computed both get and set influences, but getGetInfluences() was
never called, so that work was entirely pointless.
This makes the pass 20% faster.
|
| | |
|
| |
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
Previously for in-tree builds, they were put directly into test/, which
unnecessarily pollutes the tree.
|
| |
|
|
| |
Add the feature flag in V8 invocations, but also disable the feature as it
isn't quite ready yet.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.)
|
| |
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
Specified at
https://github.com/WebAssembly/half-precision/blob/main/proposals/half-precision/Overview.md
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
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
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
| |
Ensure the "fp16" feature is enabled for FP16 instructions.
|
| |
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
Specified at
https://github.com/WebAssembly/half-precision/blob/main/proposals/half-precision/Overview.md
|
| |
|
|
|
|
|
|
| |
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*>`.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
| |
Add comments to the spec test skip list briefly explaining why each
skipped spec test must be skipped.
|
| |
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
* Add interpreter support for exnref values.
* Fix optimization passes to support try_table.
* Enable the interpreter (but not in V8, see code) on exceptions.
|
| |
|
|
|
|
|
|
|
| |
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.
|
