| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
| |
fixes part of #3906
|
| |
|
|
|
|
|
| |
Given a list of profiles for the same module, --merge-profiles produces a single
combined profile the contains the minimum timestamp among the original profiles
for each function. When verbose output is enabled, also emit a message for each
profile that could individually be removed without affecting the set of
functions in the combined profile, as suggested in #3912.
|
| |
|
|
|
|
| |
They are basically the flip versions. The only interesting part in the impl is that their
returned typed and sent types are different.
Spec: https://docs.google.com/document/d/1DklC3qVuOdLHSXB5UXghM_syCh-4cMinQ50ICiXnK3Q/edit
|
| |
|
|
|
|
| |
In anticipation of adding a third wasm-split mode, merge-profiles, in addition
to the existing split and instrument modes, refactor wasm-split's option
validation to let the valid modes be declared for each option. This approach is
more scalable and robust than the ad-hoc validation we had previously.
|
| |
|
|
|
|
|
|
|
| |
wasm-split would previously use internal function names to create the external
names of the functions that are newly exported from the primary module to be
imported into the secondary module. When the input module contains full function
names (as is commonly the case when emitting symbol maps), this caused the
function names to be preserved as the export names, even when names are
otherwise being stripped. To save on code size and properly anonymize functions,
generate minimal export names when debuginfo is disabled instead.
|
| |
|
|
| |
Simplifies the public API to not unnecessarily take an index and simplifies the
implementation to use a single integer as state rather than a vector of indices.
|
| |
|
|
|
|
|
|
| |
Spec for it is here:
https://docs.google.com/document/d/1DklC3qVuOdLHSXB5UXghM_syCh-4cMinQ50ICiXnK3Q/edit#
Also reorder some things in wasm.h that were not in the canonical order (that has
no effect, but it is confusing to read).
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
Without adding logic there, it simply ignored the branch, which could
lead to bad optimizations (thinking code is unreachable when it was).
There isn't a trivial way to add a static error to force us to add new
classes to CFGWalker. But this PR generalizes the code there to
handle all branches and all unreachable instructions in a generic
way. The only thing we'll need to remember to do in the future is to
add control flow structures. (And normally the fuzzer should quickly
find such bugs, but we don't have full fuzzing enabled for GC yet.)
Fixes #3907
|
| |
|
|
|
|
| |
Even when other names are stripped, it can be useful for wasm-split to preserve
the module name so that the split modules can be differentiated in stack traces.
Adding this option to wasm-split requires adding similar options to ModuleWriter
and WasmBinaryWriter.
|
| | |
|
| |
|
|
|
|
|
|
|
|
| |
`Walker::TaskFunc` has changed from a function pointer to
`std::function` in #3494, mainly to make the EH support for `CFGWalker`
easier. We didn't notice much performance difference then, but it was
recently reported that it creased binaryen.js code size and performance.
This changes `Walker::TaskFunc` back to a function pointer and does a
little more work to manage catch index in `CFGWalker` side.
Hopefully fixes #3857.
|
| |
|
|
|
|
|
|
| |
Imported functions come first when modules are emitted, so to ensure the
function indices are correct, they need to come first in the symbol maps. We
never noticed this bug before because imported functions are always the first
functions when a module is parsed, so the bug never mattered in practice.
However, wasm-split adds new imported functions after parsing and these were
causing the symbol map indices to be incorrect.
|
| |
|
|
| |
We must do that before assuming the type is a heap type in getStructIndex,
or we'd hit an assert there.
|
| |
|
| |
Fixes #3895
|
| |
|
|
|
| |
The new option emits a symbol map file for each of the split modules. The file
names are created by appending ".symbols" to each of the Wasm output file
names.
|
| |
|
|
|
|
|
|
|
|
|
| |
Valmari and Lehtinen's algorithm is broadly similar to Hopcroft's algorithm, but
it more precisely keeps track of which input transitions might be able to split
a partition of states so it ends up doing much less work. Unlike our
implementation of Hopcroft's algorithm, which naively used sets of HeapTypes,
this new algorithm also uses optimized data structures that can split partitions
in constant time and never reallocate.
This change improves the shape canonicalization time for a real-world
unoptimized type section from 40 minutes to 1.5 seconds.
|
| |
|
|
|
|
| |
When things go well, the reducer shrinks the factor by 50% or more, but
when things are slow it kept the factor unchanged. That is annoying in
some cases where you really have no benefit from reduction until the
factor gets small. So this at least reduces it by 10% in each iteration.
|
| |
|
|
|
|
|
|
|
| |
As found in #3682, the current implementation of type ordering is not correct,
and although the immediate issue would be easy to fix, I don't think the current
intended comparison algorithm is correct in the first place. Rather than try to
switch to using a correct algorithm (which I am not sure I know how to
implement, although I have an idea) this PR removes Type ordering entirely. In
places that used Type ordering with std::set or std::map because they require
deterministic iteration order, this PR uses InsertOrdered{Set,Map} instead.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Previously we would try to stop using the allocation as much as possible,
for example not writing it to locals any more, and leaving it to other passes
to actually remove it (and remove gets of those locals etc.). This seemed
simpler and more modular, but does not actually work in some cases as
the fuzzer has found. Specifically, if we stop writing our allocation to
locals, then if we do a (ref.as_non_null (local.get ..)) of that, then we
will trap on the null present in the local.
Instead, this changes our rewriting to do slightly more work, but it is
simpler in the end. We replace the allocation with a null, and replace
all the places that use it accordingly, for example, updating types to be
nullable, and removing RefAsNonNulls, etc. This literally gets rid of the
allocation and all the places it flows to (leaving less for other passes to
do later).
|
| |
|
|
| |
Similar to struct operations, if the reference is unreachable then we do
not know the heap type, and cannot print the full expression.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
| |
If we run a pass that removes DWARF followed by one that could destroy it, then
there is no possible problem - there is nothing left to destroy. We can run the later
pass with no issues (and no warnings).
Also add an assertion on running a pass runner only once. That has always been
the assumption, and now that we track whether the added passes remove debug
info, we need to check it.
Fixes emscripten-core/emscripten#14161
|
| |
|
|
|
|
| |
Move the InsertOrderedSet and InsertOrderedMap implementations out of
Relooper.h and into a new insert_ordered.h so they can be used more widely. Only
changes the implementation code to use unordered_maps and
`WASM_UNREACHABLE` instead of `abort`.
|
| |
|
|
| |
Affects `printMajor` and `printMedium`. There is no usage of this optional
argument in the source code.
|
| |
|
| |
Via the C API.
|
| |
|
|
|
|
|
|
|
|
| |
wasm-as supports --symbolmap=FOO as an argument. We got a request to
support the same in wasm-opt. wasm-opt does have --print-function-map which
does the same, but as a pass. To unify them, use the new pass arg sugar from
#3882 which allows us to add a --symbolmap pass whose argument can be
set as --symbolmap=FOO. That perfectly matches the wasm-as notation.
For now, keep the old --print-function-map notation as well, to not break
emscripten. After we remove it there we can remove it here.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We have --pass-arg that allows sending an argument to a pass, like this:
wasm-opt --do-stuff --pass-arg=do-stuff@FUNCTION_NAME
With this PR that is equivalent to this:
wasm-opt --do-stuff=FUNCTION_NAME
That is,one can just give an argument to a pass on the commandline.
This fixes the Optional mode in command-line.h/cpp. That was not
actually used anywhere before this PR.
Also rename --extract-function's pass argument to match it. That is, the usage
used to be
wasm-opt --extract-function --pass-arg=extract@FUNCTION_NAME
Note how the pass name differed from the pass-arg name. This changes it to
match. This is a breaking change, but I doubt this is used enough to justify
any deprecation / backwards compatibility effort, and any usage is almost
certainly manual, and with PR writing it manually becomes easier as one
can do
wasm-opt --extract-function=FUNCTION_NAME
The existing test for that is kept (&renamed), and a new test added to test the
new notation.
This is a step towards unifying the symbol map functionality between
wasm-as and wasm-opt (later PRs will turn the symbol mapping pass into
a pass that receives an argument).
|
| |
|
|
|
| |
Without this fix we can segfault, as it has no body.
Fixes #3879
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
If we branch to a block, and there are no other branches or a final
value on the block either, then there is no mixing, and we may be able
to optimize the allocation. Before this PR, all branches stopped us.
To do this, add some helpers in BranchUtils.
The main flow logic in Heap2Local used to stop when we reached a
child for the second time. With branches, however, a child can flow both to
its immediate parent, and to branch targets, and so the proper thing to look
at is when we reach a parent for the second time (which would definitely
indicate mixing).
Tests are added for the new functionality. Note that some existing tests
already covered some things we should not optimize, and so no tests
were needed for them. The existing ones are: $get-through-block,
$branch-to-block.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
If we allocate some GC data, and do not let the reference escape, then we can
replace the allocation with locals, one local for each field in the allocation
basically. This avoids the allocation, and also allows us to optimize the locals
further.
On the Dart DeltaBlue benchmark, this is a 24% speedup (making it faster than
the JS version, incidentially), and also a 6% reduction in code size.
The tests are not the best way to show what this does, as the pass assumes
other passes will clean up after. Here is an example to clarify. First, in pseudocode:
ref = new Int(42)
do {
ref.set(ref.get() + 1)
} while (import(ref.get())
That is, we allocate an int on the heap and use it as a counter. Unnecessarily,
as it could be a normal int on the stack.
Wat:
(module
;; A boxed integer: an entire struct just to hold an int.
(type $boxed-int (struct (field (mut i32))))
(import "env" "import" (func $import (param i32) (result i32)))
(func "example"
(local $ref (ref null $boxed-int))
;; Allocate a boxed integer of 42 and save the reference to it.
(local.set $ref
(struct.new_with_rtt $boxed-int
(i32.const 42)
(rtt.canon $boxed-int)
)
)
;; Increment the integer in a loop, looking for some condition.
(loop $loop
(struct.set $boxed-int 0
(local.get $ref)
(i32.add
(struct.get $boxed-int 0
(local.get $ref)
)
(i32.const 1)
)
)
(br_if $loop
(call $import
(struct.get $boxed-int 0
(local.get $ref)
)
)
)
)
)
)
Before this pass, the optimizer could do essentially nothing with this.
Even with this pass, running -O1 has no effect, as the pass is only
used in -O2+. However, running --heap2local -O1 leads to this:
(func $0
(local $0 i32)
(local.set $0
(i32.const 42)
)
(loop $loop
(br_if $loop
(call $import
(local.tee $0
(i32.add
(local.get $0)
(i32.const 1)
)
)
)
)
)
)
All the GC heap operations have been removed, and we just
have a plain int now, allowing a bunch of other opts to run. That
output is basically the optimal code, I think.
|
| |
|
|
|
|
| |
If we can't emit something, and instead emit a replacement for it (as is
the case for a StructSet with an unreachable RTT, so we have no known
heap type for it), add a comment that mentions it is a replacement. This
might avoid confusion while debugging.
|
| |
|
|
|
|
|
|
|
| |
Instead, run RemoveUnusedModuleElements, which does that sort of thing. That
is, this pass just "extracts" the function by turning all others into imports, and then
they should almost all be removable via RemoveUnusedModuleElements, depending
on whether they are used in the table or not, whether the extracted function calls
them, etc.
Without this, we would error if a function was in the table, and so this fixes #3876
|
| |
|
|
|
|
| |
Also fix printing of unreachable StructSets, which must handle the case
of an unreachable reference, which means we do not know the RTT,
and so we must print a replacement for the StructSet somehow. Emit a
block with drops, fixing the old behavior which was missing the drops.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Precompute not only computes values, but looks at the fallthrough,
(local.set 0
(block
..stuff we can ignore..
;; the fallthrough we care about - if a value is set to local 0, it is this
(i32.const 10)
)
)
Normally that is fine, but the fuzzer found a case where it is not: RefCast may
return a different type than the fallthrough, even an incompatible type if we
try to do something bad like cast a function to a struct. As we may then
propagate the value to a place that expects the proper type, this can cause an
error.
To fix this, check if the precomputed value is a proper subtype. If it is not,
then do not look through into the fallthrough, but compute the entire thing.
(In the case of a bad RefCast of a func to a struct, it would then indicate a
trap happens, and we would not precompute the value.)
|
| |
|
|
|
|
| |
The method had TODOs which it halted on. But we should not halt the
entire program, as this is a best-effort attempt to replace a node with
something simpler of the same type (we call it when we know the value
is not actually used).
|
| |
|
|
|
|
|
|
|
|
| |
The logic there would construct the cast value separately for functions and data
(as we must), and then in an attempt to share code, would then check if the
cast succeed or not (and if not, do nothing with the cast value).
But this was wrong, as in some weird casts (like a struct to a function) we
cannot construct a valid cast value, and we error there. Instead, check if the
cast works first, once we know enough to do so, and only then construct the
cast value if so.
|
| |
|
|
|
|
| |
We truncated and extended packed values in get and set, but
not during initialization.
Found by the fuzzer.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Binaryen allows optimizing functions in function-parallel passes while the
module is still being built, that is, while not all the other functions have
even been added to the module yet. Since the removal of asm2wasm that
has not been heavily tested, but the fuzzer found a closely related bug:
in passes like inlining-optimizing, that inline and then optimize the
functions we inlined into, the mechanism for optimizing only the relevant
functions is to create a module with only some of them. (We only want to
optimize the relevant ones, that we inlined into, because this happens
after the main optimization pipeline - we don't want to re-optimize all the
functions if we just inlined into one of them.)
The specific bug here is that ref.cast of a funcref looked up the target
function on the module (in order to get its signature, to see if the cast
has the right RTT for it). The fix is to return a nonconstant flow in that
case, as it is something we cannot precompute. (This does mean we
may miss some optimization opportunities, but as in the case of where
we optimize functions before the module is fully built up, we do still
get 99% of function-local optimizations that way, and a subsequent
round of full optimizations can be done later if necessary.)
|
| |
|
| |
Becomes BinaryenElementSegmentIsPassive
|
| |
|
|
|
|
|
|
|
|
| |
Add operateOnScopeNameUsesAndSentValues which is like the
existing utilities, but provides the child expression that is sent as a
value on the branch.
Also provide a BranchTargets utility that maps target names to the
control flow structure for them.
Both will be used and tested in escape analysis.
|
| |
|
|
|
|
| |
A new getImmediateFallthrough is called in the loop.
Aside from this being more efficient than recursion, the new method will
be used in escape analysis.
|
| |
|
|
|
|
|
| |
Some passes need setInfluences but not getInfluences, but were
computing them nonetheless.
This makes e.g. MergeLocals 12% faster. It will also help use LocalGraph
in new passes with less worries about speed.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Fix two potential sources of data races identified with the help of thread
sanitizer.
First, keep a lock on the global HeapType store as long as it can reach
temporary types to ensure that no other threads observe the temporary types, for
example if another thread concurrently constructs a new HeapType with the same
shape as one being canonicalized here. This cannot happen with Types because
they are hashed in the global store by pointer identity, which has not yet
escaped the builder, rather than shape.
Second, in the shape canonicalizer, do not replace children of the new, minimal
HeapTypeInfos if they are already canonical. Even though these writes are always
no-ops, they still race because they are visible to other threads via canonical
Types.
|
| |
|
|
|
|
|
|
|
|
|
| |
Add new public `getHeapTypeChildren` methods to Type and HeapType, implemented
in using the standard machinery from #3844, and use them to simplify
`ModuleUtils::collectHeapTypes`.
Now that the type traversal code in wasm-type.cpp is not just used in
canonicalization, move it to a more appropriate place in the file. Also, since
the only users of `HeapTypePathWalker` were using it to visit top-level children
only, replace that with a more specialized `HeapTypeChildWalker` to reduce code
duplication.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This compares two local.gets and checks whether we are sure they are
equivalent, that is, they contain the same value.
This does not solve the general problem, but uses the existing info to get
a positive answer for the common case where two gets only receive values
by a single set, like
(local.set $x ..)
(a use.. (local.get $x))
(another use.. (local.get $x))
If they only receive values from the same single set, then we know it must
dominate them. The only risk is that the set is "in between" the gets, that is,
that the set occurs after one get and before the other. That can happen in
a loop in theory,
(loop $loop
(use (local.get $x))
(local.set $x ..some new value each iteration..)
(use (local.get $x))
(br_if $loop ..)
)
Both of those gets receive a value from the set, and they may be different
values, from different loop iterations. But as mentioned in the source code,
this is not a problem since wasm always has a zero-initialization value, and
so the first local.get in that loop would have another set from which it can
receive a value, the function entry. (The only way to avoid that is for this
entire code to be unreachable, in which case nothing matters.)
This will be useful in dead store elimination, which has to use this to reason
about references and pointers in order to be able to do anything useful with
GC and memory.
|
| |
|
|
|
|
| |
This is similar to the limit in TypeNamePrinter in Print.cpp. This limit
affects the printed type when debugging with std::cout << type etc.,
which just prints the structure and not the name.
|
| |
|
|
|
|
|
|
| |
Add clear().
Add UniqueNonrepeatingDeferredQueue which also has the property
that it never repeats values in the output.
Also add unit tests.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Fixes #3843.
The issue was that during LUB type building, Hopcroft's algorithm was only
running on the temporary HeapTypes in the TypeBuilder and not considering the
globally canonical HeapTypes that were reachable from the temporary HeapTypes.
That meant that temporary HeapTypes that referred to and were equirecursively
equivalent to the globally canonical types were not properly minimized and could
not be matched to the corresponding globally canonical HeapTypes.
The fix is to run Hopcroft's algorithm on the complete HeapType graph, not just
the root HeapTypes. Since there were already multiple implementations of type
graph traversal, this PR consolidates them into a generic type traversal
utility. Although this creates more boilerplate, it also reduces code
duplication and will be easier to maintain and reuse.
Now that Hopcroft's algorithm partitions can contain globally canonical
HeapTypes, this PR also updates the `translateToTypes` step of shape
canonicalization to reuse the globally canonical types unchanged, since they
must already be minimal. Without this change, `translateToTypes` could end up
incorrectly inserting temporary HeapTypes into the globally canonical type
graph. Unfortunately, this change complicates the interface presented by
`ShapeCanonicalizer` because it no longer owns the HeapTypeInfos backing all of
the minimized types. Fixing this is left as future work.
|
| | |
|
| | |
|
