| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
|
|
|
| |
This is a partial revert of #3669, which removed the old implementation of
Type::getLeastUpperBound that did not correctly handle recursive types. The new
implementation in this PR uses a TypeBuilder to construct LUBs and for recursive
types, it returns a temporary HeapType that has not yet been fully constructed
to break what would otherwise be infinite recursions.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Several old passes like DeadArgumentElimination and DuplicateFunctionElimination
need to look at all ref.funcs, and they scanned functions for that, but that is not
enough as such an instruction might appear in a global initializer. To fix this, add a
walkModuleCode method.
walkModuleCode is useful when doing the pattern of creating a function-parallel
pass to scan functions quickly, but we also want to do the same scanning of code
at the module level. This allows doing so in a single line.
(It is also possible to just do walk() on the entire module, which will find all code,
but that is not function-parallel. Perhaps we should have a walkParallel() option
to simplify this further in a followup, and that would call walkModuleCode afterwards
etc.)
Also add some missing validation and comments in the validator about issues that
I noticed in relation to the new testcases here.
|
| |
|
|
|
|
|
|
| |
We must write them to a tuple with nullable types, then fix that up when
reading. This is similar to what we do in handleNonNullableLocals, except
that it operates on the entire tuple type, so it can't share that code.
This fixes a regression from #3710 that was harder to notice by the fuzzer
until now.
|
| |
|
|
|
|
|
| |
This looks like a pre-existing issue to #3731, but
the testcase only fails on that PR for a reason I did not investigate in
depth, so it should land first.
Also fix the check for nondefaultability in the fuzzer.
|
| | |
|
| |
|
|
|
|
|
|
|
|
| |
Makes TypeBuilders growable, adds a `getTempHeapType` method, allows the
`getTemp*Type` methods to take arbitrary temporary or canonical HeapTypes rather
than just an index, and allows BasicHeapTypes to be assigned to TypeBuilder
slots. All of these changes are necessary for the upcoming re-implementation of
equirecursive LUB calculation.
Also adds a new utility to TypeBuilder for using `operator[]` as an intuitive
and readable wrapper around the `getTempHeapType` and `setHeapType` methods.
|
| |
|
|
|
| |
This variable is only used when asserts are enabled, so it was causing
compilation errors on optimized builds with -Wunused-variable -Werror. This PR
fixes the build errors by hiding the variable and its uses behind ifdefs.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
used (#3727)
For example, on this invalid wat:
(module
(type $vec (struct (field i64)))
(func $test
(drop
(struct.new_with_rtt $vec (i32.const 1) (rtt.canon $vec))
)
)
)
We used to print:
[wasm-validator error in function test] struct.new operand must have proper type, on
(struct.new_with_rtt ${i64}
(i32.const 1)
(rtt.canon ${i64})
)
We will now print:
[wasm-validator error in function test] struct.new operand must have proper type, on
(struct.new_with_rtt $vec
(i32.const 1)
(rtt.canon $vec)
)
Note that $vec is used. In real-world examples the autogenerated structural name
can be huge, which this avoids.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
#3719 optimized the case where the kind is what we want, like br_on_func of
a function. This handles the opposite case, where we know the kind is wrong, and
so the break is not taken.
This seems equally useful for "polymorphic" code that does a bunch of checks
and routes to different code for each case, as after inlining or other optimizations
we may see which paths are taken and which are not.
Also refactor the checking code to a shared location as RefIs/As will also want to
use it.
|
| | |
|
| |
|
|
|
|
| |
This PR adds support for `ref.null t` as a valid element segment
item. The abbreviated format of `(elem ... func $f $g...)` is kept in
both printing and binary emitting if all items are `ref.func`s. Public
APIs aren't updated in this PR.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* Equirecursive type canonicalization
Use Hopcroft's DFA minimization algorithm to properly canonicalize and
deduplicate recursive types. Type canonicalization has two stages:
1. Shape canonicalization
- The top-level structure of HeapTypes is used to split the declared HeapTypes
into their initial partitions.
- Hopcroft's algorithm refines the partitions such that all pairs of
distinguishable types end up in different partitions.
- A fresh HeapTypeInfo is created for each final partition. Each new
HeapTypeInfo is linked to other new HeapTypeInfos to create a minimal type
definition graph that defines the same types as the original graph.
2. Global canonicalization
- Each new minimal HeapTypeInfo that does not have the same finite
shape as an existing globally canonical HeapTypeInfo is moved to the
global heap type store to become the new canonical HeapTypeInfo.
- Each temporary Type referenced by the newly canonical HeapTypeInfos is
replaced in-place with the equivalent canonical Type to avoid leaking
temporary Types into the global stores.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
After this PR we still do not support non-nullable locals. But we no longer
turn all types into nullable upon load. In particular, we support non-nullable
types on function parameters and struct fields, etc. This should be enough to
experiment with optimizations in both binaryen and in VMs regarding non-
nullability (since we expect that optimizing VMs can do well inside functions
anyhow; it's non-nullability across calls and from data that the VM can't be
expected to think about).
Let is handled as before, by lowering it into gets and sets. In addition, we
turn non-nullable locals into nullable ones, and add a ref.as_non_null on
all their gets (to keep the type identical there). This is used not just for
loading code with a let but also is needed after inlining.
Most of the code changes here are removing FIXMEs for allowing
non-nullable types. But there is also code to handle the issues mentioned
above.
Most of the test updates are removing extra nulls that we added before
when we turned all types nullable. A few tests had actual issues, though,
and also some new tests are added to cover the code changes here.
|
| |
|
|
|
|
| |
When we can skip function bodies, we still need to parse the start function
for the pthreads case, see details in the comments. This still gives us 99%
of the speedup as the start function is just 1 function and it's not that big,
so with this we return to full speed after the reversion in #3705
|
| | |
|
| |
|
|
|
| |
It is a little "fun" to fake their uses because of the overloaded type.
cppreference says that this is the way to do it, and I've found no
other way than a C cast like this (std::function fails).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
output (#3698)
When not writing output we don't need debug info, as it is not relevant for
our metadata. This saves loading and interning all the names, which takes
several seconds on massive inputs.
This is possible in principle in other tools, but this does not change anything
in them for now. (We do use names internally in some nontrivial ways without
opting in to it, so that would require further refactoring. Also the other tools
almost always do write an output.)
This is not 100% unobservable. If validation fails then the validation error would
just contain the function index instead of the name from the Names section if
there is one. However finalize does not validate atm so that would only matter
if we change that later.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
A recent change in LLVM causes it to sometimes end up with a thing
with no parent. That is, a debug_line or a debug_loc that has no CU that
refers to it. This is perhaps LLVM DCEing CUs, or something else that
changed - not sure. But it seems like valid DWARF we should handle.
This PR handles that in our code. Two things broke here. First, locs must
be simply ignored when there is no CU. Second, lines are trickier as we
used to compute their position by scanning them, and that list contained
only ones with a CU. So we missed some and ended up with wrong offsets.
To make things simpler and more robust, just track the position of each
line table on itself.
Fixes #3697
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
After sbc100 's work on EM_ASM and EM_JS they are now parsed from
the wasm using exports etc. and so we no longer need to parse function bodies.
As a result if we are not emitting a wasm from wasm-emscripten-finalize then all we are
doing is scanning global structures like imports and exports and emitting metadata
about them. And indeed we do not need to emit a wasm in some cases, specifically
when not optimizing and when using WASM_BIGINT (to avoid needing to
legalize).
We had considering skipping wasm-emscripten-finalize entirely in that situation,
and instead to parse the metadata from the wasm in python on the emscripten
side. However sbc100 had the brilliant idea today to just skip function bodies.
That is very simple to do - no need to write another parser for wasm, and also
look at how simple this PR is - and also it will be faster to run
wasm-emscripten-finalize in this mode than to run python. (With the only
downside that the bytes of the wasm are loaded even if they aren't parsed; but
almost certainly they are in the disk cache anyhow.)
This PR implements that idea: when wasm-emscripten-finalize knows it will
not write a wasm output, it notes "skip function bodies". The binary reader then
skips the bodies and places unreachables there instead (so that the wasm still
validates).
There are no new tests here because this can't be tested - by design it is an
unobservable optimization. (If we could notice the bodies have been skipped,
we would not have skipped them.) This is also why no changes are needed on
the emscripten side to benefit from this speedup. Basically when binaryen sees
it will not need X, it skips parsing of X automatically.
Benchmarking speed, it is as fast as you'd expect: the wasm-emscripten-finalize
step is 15x faster on SQLite (1MB of wasm) and almost 50x faster on the biggest
wasm I have on my drive (40MB of LLVM). (These numbers are on release
builds, without debug info - debug into makes things slower, so the speedup is
lower there, and will need further work.)
Tested manually and also on wasm0 wasm2 other on emscripten.
|
| |
|
|
|
|
| |
`isTemp` is used in new assertions that guard against leaking temporary types
and heap types into the global stores and `isSelfReferential` replaces and
external set of self-referential types. Both fields will additionally be used in
upcoming PRs improving type canonicalization.
|
| |
|
|
| |
Also add more spec tests, including one that verifies we validate
rtt.sub and on a global location as fixed by #3694
|
| |
|
|
|
|
| |
This validation is almost never needed, but it starts to get interesting with
GC, where a global initializer can be an rtt.sub which must be valid.
No tests here as testing requires a further GC fix in a later PR.
|
| | |
|
| |
|
|
|
| |
Works around #3682 With this, I can roundtrip
a large real-world testcase.
|
| |
|
|
|
|
|
| |
(#3680)
When storing to an i8, we can ignore any higher bits, etc.
Adds a getByteSize utility to Field to make this convenient.
|
| |
|
|
|
|
|
|
| |
Since correct LUB calculation for recursive types is complicated, stop depending
on LUBs throughout the code base. This also fixes a validation bug in which the
validator required blocks to be typed with the LUB of all the branch types, when
in fact any upper bound should have been valid. In addition to fixing that bug,
this PR simplifies the code for break handling by not storing redundant
information about the arity of types.
|
| |
|
|
|
|
|
| |
Since in principle an unreachable expression can be used in any position. An
exception to this rule is in OptimizeInstructions, which avoids replacing
concrete expressions with unreachable expressions so that it doesn't need to
refinalize any expressions. Notably, Type::getLeastUpperBound was already
treating unreachable as the bottom type.
|
| |
|
|
|
|
| |
This was missing from #3663
Fixes #3656
|
| |
|
|
|
|
|
|
|
| |
We handled them as S63 instead of U32. That should be fine, as all U32 values fit
in S63. But it is not strictly correct. The signed encoding may use an additional byte
which is unnecessary, and there is an actual correctness issue where a U32 may
be interpreted as a large negative S63 (because it sign extends a final bit that
happens to be 1).
May help #3656 but that testcase still does not pass even with this.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
| |
Passive element segments do not belong to any table, so the link between
Table and elem needs to be weaker; i.e. an elem may have a table in case
of active segments, or simply be a collection of function references in
case of passive/declarative segments.
This PR takes Table::Segment out and turns it into a first class module
element just like tables and functions. It also implements early support
for parsing, printing, encoding and decoding passive/declarative elem
segments.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When writing a binary, we take the local indexes in the IR and turn
them into the format in the binary, which clumps them by type. When
writing the names section we should be aware of that ordering, but
we never were, as noticed in #3499
This fixes that by saving the mapping of locals when we are emitting
the name section, then using it when emitting the local names.
This also fixes the order of the types themselves as part of the
refactoring. We used to depend on the ordering of types to decide
which to emit first, but that isn't good for at least two reasons. First,
it hits #3648 - that order is not fully
defined for recursive types. Also, it's not good for code size - we've
ordered the locals in a way we think is best already (ReorderLocals pass).
This PR makes us pick an order of types based on that, as much as
possible, that is, when we see a type for the first time we append it to
a list whose order we use.
Test changes: Some are just because we use a different order than
before, as in atomics64. But some are actual fixes, e.g. in heap-types
where we now have (local $tv (ref null $vector)) which is indeed
right - v there is for vector, and likewise m for matrix etc. - we
just had wrong names before. Another example, we now have
(local $local_externref externref) whereas before the name was
funcref, and which was wrong... seems like the incorrectness was
more common on reference types and GC types, which is why this was
not noticed before.
Fixes #3499
Makes part of #3648 moot.
|
| |
|
|
|
|
|
| |
This adds support for reading (elem declare func $foo .. in the text and
binary formats. We can simply ignore it: we don't need to represent it in
IR, rather we find what needs to be declared when writing. That part takes
a little more work, for which this adds a shared helper function.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
The comparison implemented by TypeComparator was not previously antisymmetric
because it held that both A < B and B < A when A and B were structurally
identical but nominally distinct recursive types. This meant that it did not
satisfy the conditions of C++'s "Compare" requirement, which meant that std::set
did not operate correctly, as discovered in #3648. The PR fixes the problem by
having making A < B be false (and vice versa), making type comparisons properly
antisymmetric.
As a drive by, also switches to using std::stable_sort in collectHeapTypes to
make the order of the type section completely deterministic accross platforms.
Fixes #3648.
|
| |
|
|
|
|
|
| |
together (#3647)
Names of structurally identical types end up "collapsed" together after the
types are canonicalized, but with this PR we can properly read content that
has structurally identical types with different names.
|
| |
|
| |
This updates them to be correct in the current spec and prototype v3.
|
| |
|
|
|
|
|
|
|
| |
Note that Binaryen "canonicalizes" the type, so in the test output here
we end up with $grandchild twice. This is a consequence of us not
storing the heap type as an extra field. I can't think of a downside to
this canonicalization, aside from losing perfect roundtripping, but I think
that's a worthwhile tradeoff for efficiency as we've been thinking so far.
Fixes #3636
|
| | |
|
| |
|
|
|
|
|
|
|
|
| |
Adds support for GC struct fields in the binary format, implementing
WebAssembly/gc#193
No extra tests needed, see the .fromBinary output which shows this working.
This also has a minor fix in the s-parser, we should not always add a name
to the map of index=>name - only if it exists. Without that fix, the binary
emitter would write out null strings.
|
| |
|
|
|
|
| |
This adds ValidationBuilder which can allow sharing of builder code that also
validates, between the text and binary parsers. In general we share that code in
the validator, but the validator can only run once IR exists, and in some cases we
can't even emit valid IR structure at all.
|
| |
|
|
| |
Most of it goes in a new parsing.cpp. One method was only used in
the s-expression's parser, and has been moved there.
|
| |
|
|
|
|
|
|
|
| |
The old code here just referred to Block and Loop. Refactor it to use the
generic helper code that also handles Try.
Also add validation of Try names in the validator.
The testcase here would have $label appear twice before this fix. After
the fix there is $label0 for one of them.
|
| |
|
|
|
|
|
|
| |
Previously we assumed catch body's size should be at least 3: `catch`
keyword, event name, and body. But catch's body can be empty when the
event's type is none. This PR fixes the bug and allows empty catch
bodies to be parsed correctly.
Fixes #3629.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
This PR makes the TypeBuilder move self-referential HeapTypes to global HeapType
store so that they are considered canonical. This means that when a HeapType is
constructed with an identical definition, it will be equivalent to the original
HeapType constructed by the TypeBuilder, but it does _not_ mean that
self-referential HeapTypes are deduplicated.
This fixes a bug in which two versions of each self-referential function
signature were emitted. Before this PR, the global HeapType store was not aware
of the original self-referential HeapTypes. When the function signatures were
used to construct HeapTypes during type collection, new HeapTypes were allocated
and emitted in addition to the original HeapTypes. Now the global HeapType store
returns the original HeapTypes, so the extra HeapType is never allocated.
|
| |
|
|
|
| |
As a readability improvement, use an enum with `Polymorphic` and `Fixed`
variants to represent the polymorphic behavior of StackSignatures rather than a
`bool uneachable`.
|
| |
|
|
|
| |
Also fixes a few locations in Print.cpp where types were being printed directly
rather than going through the s-expression type printer and removes vestigial
wrapper types that were no longer used.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Previously we computed the fixed point of the parent-child relation to identify
self-referential HeapTypes in the TypeBuilder canonicalizer. That algorithm was
O(|V|^3) in the worst case and took over five seconds to find the
self-referential HeapTypes in an example program with just 1134 HeapTypes,
probably due to high allocation traffic from the std::unordered_map and
std::unordered_sets used to implement the parent-child graph's adjacency list.
This PR replaces that algorithm with Tarjan's strongly connected component
algorithm, which runs in O(|V|+|E|) and finds the self-referential HeapTypes in
the mentioned example program in under 30 ms. All strongly connected components
of more than one element in the HeapType parent-child graph correspond to sets
of mutually recursive HeapTypes that are therefore self-referential. The only
other self-referential HeapTypes are those that are not mutually recursive with
any other HeapTypes, but these are trivial to find because they must be their
own direct children.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When the type section is emitted, types with an equal amount of references are
ordered by an arbitrary measure of simplicity, which previously would infinitely
recurse on structurally equivalent recursive types. Similarly, calculating
whether an recursive type was a subtype of another recursive type could have
infinitely recursed. This PR avoids infinite recursions in both cases by
switching the algorithms from using normal inductive recursion to using
coinductive recursion. The difference is that while the inductive algorithms
assume the relations do not hold for a pair of HeapTypes until they have been
exhaustively shown to hold, the coinductive algorithms assume the relations hold
unless a counterexample can be found.
In addition to those two algorithms, this PR also implement name generation for
recursive types, using de Bruijn indices to stand in for inner uses of the
recursive types.
There are additional algorithms that will need to be switched from inductive to
coinductive recursion, such as least upper bound generation, but these presented
a good starting point and are sufficient to get some interesting programs
working end-to-end.
|
| |
|
| |
Also add a missing source file for a GC test, let.wasm.
|
