| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
| |
The type may prove the value is not null, and may also show it to be
of the type we are casting to. In that case, we can simplify things.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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.
|
| |
|
|
|
| |
We have the if's type, and when replacing it with a select, can use that
type. This could be more efficient. It also avoids a current crash
after the removal of LUBs, but it's worth doing regardless of that.
|
| |
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
I'm not entirely sure how LUB removal made this noticeable, as it seems
to be a pre-existing bug. However, somehow before #3669 it was not
noticable - perhaps the finalize code worked around it.
The bug is that RemoveUnusedBrs was moving code around and
finalizing the parent before the child. The correct pattern is always to
work from the children outwards, as otherwise the parent is trying to
finalize itself based on non-finalized children.
The fix is to just not finalize in the stealSlice method. The caller can
do it after finishing any other work it has. As part of this refactoring,
move stealSlice into the single pass that uses it; aside from that being
more orderly, this method is really not a general-purpose tool, it is
quite specific to what RemoveUnusedBrs does, and it might easily
be used incorrectly elsewhere.
|
| | |
|
| |
|
|
|
| |
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).
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
That PR assumed that wasm-emscripten-finalize does not need to scan
function bodies for metadata. But there is a case where it does, which is
that EM_ASMs with pthreads do still require scanning of the code. So that
approach is not valid.
We could maybe disable the optimization just on pthreads, but I think
major use cases need that. Also there is no simple way to disable it atm,
we'd need changes on both emscripten and binaryen. Also that PR can
no longer be reverted cleanly due to other changes. For all those reasons,
this just disables the optimization so that users of tot are no longer
broken, while we figure out how a valid way to optimize this use case.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
| |
The pass was only aware of Break and Switch. Refactor it to use the
generic code, so that we can first handle Break, and then if anything
remains, note a problem was found. The same path can handle a Switch
which we handled before and also a BrOn etc.
git diff is not that useful after the refactoring sadly, but basically this just
moves the Break code and the Drop code, then adds the BranchUtils::operateOn
stuff after them (and we switch to a unified visitor so that we get called
for all expressions).
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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
|
| |
|
| |
Fixes #3664
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
| |
We were missing type names and the features section.
|
| |
|
|
| |
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.
|
| |
|
| |
Same as we already do for struct.set.
|
| | |
|
| |
|
| |
Rather than use delegates.h, we have helpers for scope names.
|
| | |
|
| |
|
|
|
| |
Now that they have names they can collide. All the fuzzer wants is
to ensure there is a segment to add to, so if there is one, do not
add another.
|
| |
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Instead of a single big optimize() method we now use separate functions
per instruction. This gives us smaller functions and less nesting in some cases,
and avoids manually casting and checking etc.
The reason this was not done originally is that this pass does repeated
applications. That is, if optimize() changed something, it would run again
on the result, perhaps further optimizing it. It did not need to run on the
children, but just on the result itself, so it didn't just do another full walk,
and so the simplest way was to just do a loop on optimize(). To replace that,
this PR modifies replaceCurrent() which the methods now call to report
that the current node can be replaced. There is some code in there now that
keeps doing more processing while changes happen. It's not trivial code as
it avoids recursion, but that slight complexity seems worthwhile in order to
simplify the bulk of the (very large) pass.
|
| | |
|
| |
|
|
|
|
|
|
| |
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.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
reduction (#3668)
The old code tried to call visitExpression from outside of a walk on the
wasm, which works except that replaceCurrent does nothing as there is
no current node. Perhaps it should assert if called outside of a walk? Might
be an expensive check, but once we have no-assert builds maybe that's
worthwhile.
Replace that with a working check during the walk. Also limit the
frequency of it (do it 1000x more often than a normal reduction, but not
all the time like we used to).
Also optimize the starting factor for text reduction. Text files are much
larger for the same amount of IR, so the initial factor was far too high and
inefficient.
|
| |
|
|
|
|
|
|
|
|
|
| |
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.
|
| |
|
|
|
|
|
|
|
|
|
| |
Just as reads and writes to memory can interfere with each other, reads and
writes of GC objects can interfere with each other. This PR adds new `readsHeap`
and `writesHeap` fields to EffectAnalyzer to account for this interference. Note
that memory accesses can never alias with GC heap accesses, so they are
considered separately. Similarly, it would be possible to prove that different
GC heap accesses never interfere with each other based on the accessed types,
but that's left to future work.
Fixes #3655.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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.
|
| | |
|
| | |
|
