| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
| |
We already ignore OOMs in the interpreter. This adds the syntax for V8, which
I saw an error on now (on an array.new of a massive size).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We used to have a wasm-merge tool but removed it for a lack of use cases. Recently
use cases have been showing up in the wasm GC space and elsewhere, as people are
using more diverse toolchains together, for example a project might build some C++
code alongside some wasm GC code. Merging those wasm files together can allow
for nice optimizations like inlining and better DCE etc., so it makes sense to have a
tool for merging.
Background:
* Removal: #1969
* Requests:
* wasm-merge - why it has been deleted #2174
* Compiling and linking wat files #2276
* wasm-link? #2767
This PR is a compete rewrite of wasm-merge, not a restoration of the original
codebase. The original code was quite messy (my fault), and also, since then
we've added multi-memory and multi-table which makes things a lot simpler.
The linking semantics are as described in the "wasm-link" issue #2767 : all we do
is merge normal wasm files together and connect imports and export. That is, we
have a graph of modules and their names, and each import to a module name can
be resolved to that module. Basically, like a JS bundler would do for JS, or, in other
words, we do the same operations as JS code would do to glue wasm modules
together at runtime, but at compile time. See the README update in this PR for a
concrete example.
There are no plans to do more than that simple bundling, so this should not
really overlap with wasm-ld's use cases.
This should be fairly fast as it works in linear time on the total input code. However,
it won't be as fast as wasm-ld, of course, as it does build Binaryen IR for each
module. An advantage to working on Binaryen IR is that we can easily do some
global DCE after merging, and further optimizations are possible later.
|
| |
|
|
|
|
|
|
|
| |
This removes the trapping export and all others after it. This avoids a potential
infinite loop that can happen when fuzzing TNH, as if TNH is set and a trap
happens then the optimizer can cause an iloop, and while that is valid, it would hang the
fuzzer. We could check for a timeout, but it is faster and more robust to just
remove the code we can't compare anyhow.
This uses wasm-metadce to remove the exports from the failing one.
|
| |
|
|
|
|
|
|
|
|
|
| |
DCE at the end avoids issues with non-nullable local operations in unreachable
code, which is still being discussed. This PR avoids fuzzer errors for now, but we
should revert it when we have a proper fix.
See
* #5599
* #5665
* https://github.com/WebAssembly/function-references/issues/98
|
| |
|
|
|
| |
After this change, the only type system usable from the tools will be the
standard isorecursive type system. The nominal type system is still usable via
the API, but it will be removed entirely in a follow-on PR.
|
| |
|
|
|
|
|
|
|
|
| |
I ran CheckDeterminism at full throttle overnight (set to 1, and disabled
all other things) and it found a bug, so we should focus on that more.
Also ctor-eval as there is ongoing work there.
I reduced a few other priorities of things that haven't seen bugs in a
very long time and are not high priority.
|
| |
|
| |
This is the default, and also used by J2Wasm.
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
| |
TypeMerging previously tried to merge types with their supertypes and siblings
in a single step, but this could cause a misoptimization in which a type was
merged with its parent's sibling without being merged with its parent, breaking
subtyping.
Fix the bug by merging with supertypes and siblings separately. Since we now
have multiple merging steps, also take the opportunity to run the sibling
merging step multiple times to exploit more merging opportunities.
Fixes #5556.
|
| |
|
|
|
|
|
| |
For example, we might hit an allocation limit in the wasm, but the
optimized wasm might optimize that allocation out. So we need to
ignore comparisons in such cases, as we cannot expect the output
to be identical. We already do similar things for FuzzExec and
#5560 adds it for TrapsNeverHappen; this adds it to CompareVMs.
|
| |
|
|
|
|
|
|
|
|
| |
If the program tries to allocate an infinite number of objects, but is
prevented from doing that by a null pointer trap, then after we run
with trapsNeverHappen the trap may fail to occur, and we'll hit the
host limitation on allocations. As a result, we'd be comparing one
run with a trap and one run that is meant to be ignored (as we ignore
runs with host limitations), and before this PR we'd error as we would
expect to find the normal output and not the "ignore this host
limitation" marker.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
With this we generate random GC types that may be used in creating
instructions later.
We don't create many instructions yet, which will be the next step after
this.
Also add some trivial assertions in some places, that have helped
debugging in the past.
Stop fuzzing TypeMerging for now due to #5556 , which this PR
uncovers.
|
| | |
|
| |
|
|
|
| |
If this number ever gets high then we would need to look into
why we ignore so much. Right now we seem to end up ignoring
much less than 1% which seems ok.
|
| |
|
|
|
|
| |
After the recent improvements and fixes this is now simple and the fuzzer found
no more issues overnight for me.
Also adjust some existing frequencies.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
If a type hierarchy has abstract classes in the middle, that is, types that
are never instantiated, then we can optimize casts and other operations
to them. Say in Java that we have `AbstractList`, and it only has one
subclass `IntList` that is ever created, then any place we have an `AbstractList`
we must actually have an `IntList`, or a null. (Or, if no subtype is instantiated,
then the value must definitely be a null.)
The actual implementation does a type mapping, that is, it finds all places
using an abstract type and makes them refer to the single instantiated
subtype (or null). After that change, no references to the abstract type
remain in the program, so this both refines types and also cleans up the
type section.
|
| |
|
|
|
| |
Do not fuzz some new testcases that have imported memories. The fuzzer doesn't seem
to have support for that (it errors when it tries to do operations on them, since the
import hasn't been created).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
Since #5347 public types are never updated by type optimizations, but the
optimization passes have not yet been updated to take that into account, so they
are all buggy under an open world assumption. In #5359 we worked around many
closed world validation errors in the fuzzer by treating --closed-world like a
feature flag and checking whether it was necessary for fuzzer input, but that
did not prevent the type optimization passes from running under an open world,
so it did not work around all the potential issues.
Work around the problem more thoroughly by not running any type optimization
passes in the fuzzer without --closed-world. Also add logic to those passes to
error out if they are run without --closed-world and update the tests
accordingly.
|
| |
|
|
|
| |
An initial content testcase may only work in open world, so check for that
using the existing mechanism of checking if such testcases work with out
feature flags.
|
| |
|
|
|
|
|
|
| |
This finds types that can be merged into their super: types that add no
fields, and are not used in casts, etc. - so we might as well use the super.
This complements TypeSSA, in that it can merge back the new types that
TypeSSA created, if we never found a use for them. Without this, TypeSSA
can bloat binary size quite a lot (I see 10-20%).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This creates new nominal types for each (interesting) struct.new. That then allows
type-based optimizations to be more precise, as those optimizations will track
separate info for each struct.new, in effect. That is kind of like SSA, however, we
do not handle merges. For example:
x = struct.new $A (5);
print(x.value);
y = struct.new $A (11);
print(y.value);
// => //
x = struct.new $A.x (5);
print(x.value);
y = struct.new $A.y (11);
print(y.value);
After the pass runs each of those struct.new creates a unique type, and type-based
analysis can see that 5 or 11 are the only values written in that type (if nothing else
writes there).
This bloats the type section with the new subtypes, so it is best used with a pass
to merge unneeded duplicate types, which a later PR will add. That later PR will
exactly merge back in the types created here, which are nominally different but
indistinguishable otherwise.
This pass is not enabled by default. It's not clear yet where is the best place to do it,
as it must be balanced by type merging, but it might be better to do multiple
rounds of optimization between the two. Needs more investigation.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
With this change we default to an open world, that is, we do the safe thing
by default: we no longer assume a closed world. Users that want a closed
world must pass --closed-world.
Atm we just do not run passes that assume a closed world. (We might later
refine them to find which types don't escape and only optimize those.) The
RemoveUnusedModuleElements is an exception in that the closed-world
flag influences one part of its operation, but not the rest.
Fixes #5292
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(some.operation
(ref.cast .. (local.get $ref))
(local.get $ref)
)
=>
(some.operation
(local.tee $temp
(ref.cast .. (local.get $ref))
)
(local.get $temp)
)
This can help cases where we cast for some reason but happen to not use the
cast value in all places. This occurs in j2wasm in itable calls sometimes: The
this pointer is is refined, but the itable may be done with an unrefined pointer,
which is less optimizable.
So far this is just inside basic blocks, but that is enough for the cast of itable
calls and other common patterns I see.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Monomorphization finds cases where we send more refined types to a function
than it declares. In such cases we can copy the function and refine the parameters:
// B is a subtype of A
foo(new B());
function foo(x : A) { ..}
=>
foo_B(new B()); // call redirected to refined copy
function foo(x : A) { ..} // unchanged
function foo_B(x : B) { ..} // refined copy
This increases code size so it may not be worth it in all cases. This initial PR is
hopefully enough to start experimenting with this on performance, and so it does
not enable the pass by default.
This adds two variations of monomorphization, one that always does it, and the
default which is "careful": it sees whether monomorphizing lets the refined function
actually be better than the original (say, by removing a cast). If there is no
improvement then we do not make any changes. This saves a significant amount
of code size - on j2wasm the careful version increases by 13% instead of 20% -
but it does run more slowly obviously.
|
| |
|
|
|
|
|
| |
That PR renamed test/lit/optimize-instructions.wast to
test/lit/optimize-instructions-mvp.wast. However, the fuzzer was explicitly
adding the testto the list of important initial contents under the old name, so
it was failing an assertion that the initial contents existed. Update the fuzzer
to use the new test name.
|
| |
|
|
|
|
|
| |
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
|
| | |
|
| |
|
|
|
| |
The fuzzer started to fail on the recent externalize/internalize test
that was added in #5175 as we lack interpreter support. Move that to a separate
file and ignore it in the fuzzer for now.
|
| |
|
| |
Also fix some formatting issue in the file.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This adds a map of function name => the effects of that function to the
PassOptions structure. That lets us compute those effects once and then
use them in multiple passes afterwards. For example, that lets us optimize
away a call to a function that has no effects:
(drop (call $nothing))
[..]
(func $nothing
;; .. lots of stuff but no effects, only a returned value ..
)
Vacuum will remove that dropped call if we tell it that the called function has
no effects. Note that a nice result of adding this to the PassOptions struct
is that all passes will use the extra info automatically.
This is not enabled by default as the benefits seem rather minor, though it
does help in a small but noticeable way on J2Wasm code, where we use
call.without.effects and have situations like this:
(func $foo
(call $bar)
)
(func $bar
(call.without.effects ..)
)
The call to bar looks like it has effects, normally, but with global effect info
we know it actually doesn't.
To use this, one would do
--generate-global-effects [.. some passes that use the effects ..] --discard-global-effects
Discarding is not necessary, but if there is a pass later that adds effects, then not
discarding could lead to bugs, since we'd think there are fewer effects than there are.
(However, normal optimization passes never add effects, only remove them.)
It's also possible to call this multiple times:
--generate-global-effects -O3 --generate-global-effects -O3
That computes affects after the first -O3, and may find fewer effects than earlier.
This doesn't compute the full transitive closure of the effects across functions. That is,
when computing a function's effects, we don't look into its own calls. The simple case
so far is enough to handle the call.without.effects example from before (though it
may take multiple optimization cycles).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In practice typed function references will not ship before GC and is not
independently useful, so it's not necessary to have a separate feature for it.
Roll the functionality previously enabled by --enable-typed-function-references
into --enable-gc instead.
This also avoids a problem with the ongoing implementation of the new GC bottom
heap types. That change will make all ref.null instructions in Binaryen IR refer
to one of the bottom heap types. But since those bottom types are introduced in
GC, it's not valid to emit them in binaries unless unless GC is enabled. The fix
if only reference types is enabled is to emit (ref.null func) instead
of (ref.null nofunc), but that doesn't always work if typed function references
are enabled because a function type more specific than func may be required.
Getting rid of typed function references as a separate feature makes this a
nonissue.
|
| |
|
|
| |
These new GC instructions infallibly convert between `extern` and `any`
references now that those types are not in the same hierarchy.
|
| |
|
|
| |
Also fix a small logic error - call lines can be prefixes of each other, so use
the full line (including newline) to differentiate.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This mode is tricky to fuzz because the mode is basically "assume traps never
happen; if a trap does happen, that is undefined behavior". So if any trap occurs
in the random fuzz testcase, we can't optimize with -tnh and assume the results
stay to same. To avoid that, we ignore all functions from the first one that traps,
that is, we only compare the code that ran without trapping. That often is a small
subset of the total functions, sadly, but I do see that this ends up with some useful
coverage despite the drawback.
This also requires some fixes to comparing of references, specifically, funcrefs
are printed with the function name/index, but that can change during opts, so
ignore that. This wasn't noticed before because this new fuzzer mode does
comparisons of --fuzz-exec-before output, instead of doing --fuzz-exec which
runs it before and after and compares it internally in wasm-opt. Here we are
comparing the output externally, which we didn't do before.
|
| |
|
|
|
|
|
| |
This PR removes the single memory restriction in IR, adding support for a single module to reference multiple memories. To support this change, a new memory name field was added to 13 memory instructions in order to identify the memory for the instruction.
It is a goal of this PR to maintain backwards compatibility with existing text and binary wasm modules, so memory indexes remain optional for memory instructions. Similarly, the JS API makes assumptions about which memory is intended when only one memory is present in the module. Another goal of this PR is that existing tests behavior be unaffected. That said, tests must now explicitly define a memory before invoking memory instructions or exporting a memory, and memory names are now printed for each memory instruction in the text format.
There remain quite a few places where a hardcoded reference to the first memory persist (memory flattening, for example, will return early if more than one memory is present in the module). Many of these call-sites, particularly within passes, will require us to rethink how the optimization works in a multi-memories world. Other call-sites may necessitate more invasive code restructuring to fully convert away from relying on a globally available, single memory pointer.
|
| | |
|
| |
|
|
|
|
|
| |
* better
* fix
* undo
|
| | |
|
| |
|
|
|
|
|
| |
RTTs were removed from the GC spec and if they are added back in in the future,
they will be heap types rather than value types as in our implementation.
Updating our implementation to have RTTs be heap types would have been more work
than deleting them for questionable benefit since we don't know how long it will
be before they are specced again.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
This tracks the possible contents in the entire program all at once using a single IR.
That is in contrast to say DeadArgumentElimination of LocalRefining etc., all of whom
look at one particular aspect of the program (function params and returns in DAE,
locals in LocalRefining). The cost is to build up an entire new IR, which takes a lot
of new code (mostly in the already-landed PossibleContents). Another cost
is this new IR is very big and requires a lot of time and memory to process.
The benefit is that this can find opportunities that are only obvious when looking
at the entire program, and also it can track information that is more specialized
than the normal type system in the IR - in particular, this can track an ExactType,
which is the case where we know the value is of a particular type exactly and not
a subtype.
|
| |
|
|
|
|
| |
#4758 regressed the determinism fuzzer. First, FEATURE_OPTS is not a
list but a string. Second, as a hack another location would add --strip-dwarf
to that list, but that only works in wasm-opt. To fix that, remove the hack
and instead just ignore DWARF-containing files.
|
| |
|
|
|
|
|
|
| |
This starts to implement the Wasm Strings proposal
https://github.com/WebAssembly/stringref/blob/main/proposals/stringref/Overview.md
This just adds the types.
|
| |
|
|
|
|
|
|
|
|
|
| |
Nominal types don't make much sense without GC, and in particular trying to emit
them with typed function references but not GC enabled can result in invalid
binaries because nominal types do not respect the type ordering constraints
required by the typed function references proposal. Making this change was
mostly straightforward, but required fixing the fuzzer to use --nominal only
when GC is enabled and required exiting early from nominal-only optimizations
when GC was not enabled.
Fixes #4756.
|
| | |
|
| |
|
| |
Relates to #4741
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This optimizes constants in the megamorphic case of two: when we
know two function references are possible, we could in theory emit this:
(select
(ref.func A)
(ref.func B)
(ref.eq
(..ref value..) ;; globally, only 2 things are possible here, and one has
;; ref.func A as its value, and the other ref.func B
(ref.func A))
That is, compare to one of the values, and emit the two possible values there.
Other optimizations can then turn a call_ref on this select into an if over
two direct calls, leading to devirtualization.
We cannot compare a ref.func directly (since function references are not
comparable), and so instead we look at immutable global structs. If we
find a struct type that has only two possible values in some field, and
the structs are in immutable globals (which happens in the vtable case
in j2wasm for example), then we can compare the references of the struct
to decide between the two values in the field.
|
| |
|
|
| |
If we use it as initial contents, we will try to execute it, and hit the TODOs
in the interpreter for unimplemented parts.
|
| |
|
|
|
|
| |
Without this the error from a bad given wasm file - either by the user, or during
a reduction where smaller wasms are given - could be very confusing. A bad
given wasm file during reduction, in particular, indicates a bug in the reducer
most likely.
|
| |
|
|
|
| |
Without this the reduction will fail on not being able to
parse the input file, if the input file depends on
nominal typing.
|
