| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
| |
1. Ignore the fake delegate target in the unique name mapper. The mapper
is run after inlining, so this fixes inlining into a function that has a delegate
to the caller.
2. Do not inline a function with a delegate. We should support this eventually,
but for now I think this is good enough.
After this Inlining should be safe to run on exceptions code.
|
| |
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
| |
The assertion is not really needed. Wasm64 will need changes to support
more than 2^32 names, in theory, but (1) wasm64 is just memory64 atm,
and (2) we'd need to add a general option for Index to be larger than 32
bits in general, so there is nothing specific to the hashing code here.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
| |
Uses BinaryenIndex instead of int to mirror parameter types in table construction, and adds setters for name, initial and max.
|
| | |
|
| | |
|
| |
|
|
|
|
| |
We can just iterate on children using the standard order as in
delegates.h, as used by the binary format as well. The only
exceptions are control flow instructions which need some
special handling.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
| |
This as a consequence of https://reviews.llvm.org/D95651
|
| | |
|
| | |
|
| |
|
| |
The first occurrence of segment refers to memory.
|
| |
|
|
|
|
| |
The comment refers to a nonexisting comment in Table.
This comment was added in 95d00d6 and refers to a field (`bool
exists`) that was removed in the meantime, along with the comment in
Table.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Updates TypeBuilder to support recursive types. Recursive types are particularly
problematic because under the current scheme it is necessary to canonicalize the
uses of a type's immediate children before canonicalizing the type itself to
avoid leaking non-canonical, temporary types out of the TypeBuilder and into the
global type stores. In the case of recursive types, it is not possible to do
this because of their cyclic nature. In principle this could be overcome by
hashing recursive types based on their structure rather than their contents, but
that would be complicated. Instead, this PR takes the shortcut of not
canonicalizing self-referential HeapTypes at all, but rather moving them out of the
TypeBuilder and into the global type store without changing their addresses or
needing to update any of their use sites. This breaks all cycles and makes it
possible to canonicalize the other types correctly.
Note that this PR only adds support for building recursive types. Doing almost
anything with the types, such as printing, comparing, or emitting them will
certainly lead to infinite recursions. A follow up PR will update all these
operations to work correctly with recursive types.
|
| |
|
|
| |
(not 100% NFC since it also fixes a bug by moving a line out of
a loop)
|
| |
|
|
|
|
|
|
| |
#3591 adds type and field names to the Module object, and used that
for the type but not the fields. This uses it for the fields as well, and removes
the "name" field from the Field objects itself, completing the refactoring.
After this, binary format support can be added as a proper replacement for
#3589
|
| |
|
|
|
|
|
|
|
|
| |
Before this we would assert on hashing e.g. (br $x) by itself, without the
context so we recognized the name $x. Somehow that was not an issue
until delegate, we just happened to not hash such things. I believe I remember
that @aheejin noticed this issue before, but given we didn't have a testcase,
we deferred fixing it - now is the time, I guess, as with delegate it is easy to
get e.g. CodeFolding to hash a Try with a delegate.
Issue found by emscripten-core/emscripten#13485
|
| | |
|
| |
|
|
|
|
| |
We were missing a pop of catchIndexStack at a Delegate. It ends the scope,
so it should do that, like TryEnd does.
Found by emscripten-core/emscripten#13485 on -O2.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This adds a TypeNames entry to modules, which can store names for types. So
far this PR uses that to store type names from text format. Future PRs will add
support for field names and for the binary format.
(Field names are added to wasm.h here to see if we agree on this direction.)
Most of the work here is threading a module through the various functions in
Print.cpp. This keeps the module optional, so that we can still print an
expression independently of a module, which has always been the case, and
which I think we should keep (but, if a module was mandatory perhaps this
would be a little simpler, and could be refactored into a form that depends on
that).
99% of this diff are test updates, since almost all our tests use the text
format, and many of them specify a type name but we used to ignore it.
This is a step towards a proper solution for #3589
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
(#3594)
This was an unfortunate case of the order of execution of call
arguments. link(self->currBasicBlock, self->startBasicBlock()) would
run the call first, which sets currBasicBlock, so we'd end up with
the same value for both parameters.
Without this fix, the testcase would drop the result of the call,
as it thought it had no uses.
Also improve debug logging here a tiny bit.
Found by emscripten-core/emscripten#13485
|
| |
|
|
|
| |
On Windows/VS the maps in this code caused a double-delete of a Literal.
Given that order of destruction is unspecified, I decided to make them locals, which fixed it.
Not sure if there is still a latent ordering bug, but not having these as globals seems an improvement regardless.
|
| |
|
|
|
|
| |
Update parsing of binary type sections to use TypeBuilder to support uses before
definitions. Now that both the binary and text parsers support out-of-order type
uses, this PR also relaxes the logic for emitting types to allow uses to be
emitted before definitions.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
singleton (#3581)
The fix here is to remove the code with
// maybe we don't need a block here?
That would remove a try's block if we thought it wasn't needed. However,
it just checked for exception branches, but not normal branches, which are
also possible.
At that location, we don't have a good way to find out if the block has other
branches to it aside from scanning its contents. So this PR just gives up on
doing so, which means we add an unnecessary block if the optimizer is not
run. If this matters we could make the binary parser more complicated by
remembering whether a block had branches in the past, but I'm not sure if
it's worth it.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Traverses the module to find type definitions and uses a TypeBuilder to
construct the corresponding HeapTypes rather than constructing them directly.
This allows types to be used in the definitions of other types before they
themselves are defined, which is an important step toward supporting recursive
types. After this PR, no further text parsing changes will be necessary to
support recursive types.
Beyond allowing types to be used before their definitions, this PR also makes a
couple incidental changes to the parser's behavior. First, compound heaptypes
can now only be declared in `(type ...)` elements and cannot be declared inline
at their site of use. This reduces the flexibility of the parser, but is in line
with what the text format spec will probably look like eventually (see
https://github.com/WebAssembly/function-references/issues/42).
The second change is that `(type ...)` elements are now all parsed before `(func
...)` elements rather than in text order with them, so the type indices will be
different and wasts using numeric type indices will be broken. Note however,
that we were already not completely spec compliant in this regard because we
parsed types defined by `(type...)` and `(func...)` elements before types
defined by the type uses of `call_indirect` instructions.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
When types or heap types were used multiple times in a TypeBuilder instance, it
was possible for the canonicalization algorithm to canonicalize a parent type
before canonicalizing all of its component child types, leaking the temporary
types into globally interned types. This bug led to incorrect canonicalization
results and use-after free bugs.
The cause of the bug was that types were canonicalized in the reverse of the
order that they were visited in, but children were visited after the first
occurrence of their parents, not necessarily after the last occurrence of their
parents. One fix could have been to remove the logic that prevented types from
being visited multiple times so that children would always be visited after
their parents. That simple fix, however, would not scale gracefully to handle
recursive types because it would require some way to detect recursions without
accidentally reintroducing these bugs.
This PR implements a more robust solution: topologically sorting the traversed
types to ensure that children are canonicalized before their parents. This
solution will be trivial to adapt for recursive types because recursive types
are trivial to detect from the reachability graph used to perform the
topological sort.
|
| | |
|
