| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| ... | |
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
This adds a new IR, "Stack IR". This represents wasm at a very low level, as a simple stream of instructions, basically the same as wasm's binary format. This is unlike Binaryen IR which is structured and in a tree format.
This gives some small wins on binary sizes, less than 1% in most cases, usually 0.25-0.50% or so. That's not much by itself, but looking forward this prepares us for multi-value, which we really need an IR like this to be able to optimize well. Also, it's possible there is more we can do already - currently there are just a few stack IR optimizations implemented,
DCE
local2stack - check if a set_local/get_local pair can be removed, which keeps the set's value on the stack, which if the stars align it can be popped instead of the get.
Block removal - remove any blocks with no branches, as they are valid in wasm binary format.
Implementation-wise, the IR is defined in wasm-stack.h. A new StackInst is defined, representing a single instruction. Most are simple reflections of Binaryen IR (an add, a load, etc.), and just pointers to them. Control flow constructs are expanded into multiple instructions, like a block turns into a block begin and end, and we may also emit extra unreachables to handle the fact Binaryen IR has unreachable blocks/ifs/loops but wasm does not. Overall, all the Binaryen IR differences with wasm vanish on the way to stack IR.
Where this IR lives: Each Function now has a unique_ptr to stack IR, that is, a function may have stack IR alongside the main IR. If the stack IR is present, we write it out during binary writing; if not, we do the same binaryen IR => wasm binary process as before (this PR should not affect speed there). This design lets us use normal Passes on stack IR, in particular this PR defines 3 passes:
Generate stack IR
Optimize stack IR (might be worth splitting out into separate passes eventually)
Print stack IR for debugging purposes
Having these as normal passes is convenient as then they can run in parallel across functions and all the other conveniences of our current Pass system. However, a downside of keeping the second IR as an option on Functions, and using normal Passes to operate on it, means that we may get out of sync: if you generate stack IR, then modify binaryen IR, then the stack IR may no longer be valid (for example, maybe you removed locals or modified instructions in place etc.). To avoid that, Passes now define if they modify Binaryen IR or not; if they do, we throw away the stack IR.
Miscellaneous notes:
Just writing Stack IR, then writing to binary - no optimizations - is 20% slower than going directly to binary, which is one reason why we still support direct writing. This does lead to some "fun" C++ template code to make that convenient: there is a single StackWriter class, templated over the "mode", which is either Binaryen2Binary (direct writing), Binaryen2Stack, or Stack2Binary. This avoids a lot of boilerplate as the 3 modes share a lot of code in overlapping ways.
Stack IR does not support source maps / debug info. We just don't use that IR if debug info is present.
A tiny text format comment (if emitting non-minified text) indicates stack IR is present, if it is ((; has Stack IR ;)). This may help with debugging, just in case people forget. There is also a pass to print out the stack IR for debug purposes, as mentioned above.
The sieve binaryen.js test was actually not validating all along - these new opts broke it in a more noticeable manner. Fixed.
Added extra checks in pass-debug mode, to verify that if stack IR should have been thrown out, it was. This should help avoid any confusion with the IR being invalid.
Added a comment about the possible future of stack IR as the main IR, depending on optimization results, following some discussion earlier today.
|
| | |
|
| |
|
|
|
|
|
| |
This separates out the WasmBinaryWriter parts that do stack writing into a separate class, StackWriter. Previously the WasmBinaryWriter did both the general writing and the stack stuff, and the stack stuff has global state, which it manually cleaned up etc. - seems nicer to have it as a separate class, a class focused on just that one thing.
Should be no functional changes in this PR.
Also add a timeout to the wasm-reduce test, which happened to fail on one of the commits here. It was running slower on that commit for some reason, could have been random - I verified that general wasm writing speed is unaffected by this PR. (But I added the timeout to prevent future random timeouts.)
|
| |
|
|
|
|
| |
* code cleanups in wasm-binary: remove an & param, and standardize whitespace
* add some docs for how the relooper handles blocks with no outgoing branches [ci skip]
|
| | |
|
| | |
|
| |
|
|
|
| |
Report the offset with the error.
Also fix a compiler warning about comparing signed/unsigned types in the LEB code.
|
| |
|
| |
Improve error handling, validation, and assertions for having a non-concrete type in an inappropriate place. Fixes a fuzz testcase.
|
| |
|
|
|
| |
The optimization in #1495 had a bug which was found by the fuzzer: our binary format parsing will not emit unreachable code (it may be stacky, so we ignore it). However, while parsing it we note breaks that are taken there, and then we removed that code, leading to a state where a break was not taken in the code, but we thought it was.
This PR clarifies the difference between unreachable code in the wasm sense (anything from the start of a block til an unreachable is "reachable") and the literal sense (even that code at the start may not be literally reachable if the block is not reachable), and then we use literal unreachability to know what code will be ignored and therefore we should ignore breaks in.
|
| |
|
|
| |
break to it - use that to avoid rescanning blocks for unreachability purposes (#1495)
|
| |
|
|
| |
found by valgrind (#1478)
|
| |
|
|
|
|
|
|
|
|
|
| |
This adds a pass that implements "function pointer cast emulation" - allows indirect calls to go through even if the number of arguments or their types is incorrect. That is undefined behavior in C/C++ but in practice somehow works in native archs. It is even relied upon in e.g. Python.
Emscripten already has such emulation for asm.js, which also worked for asm2wasm. This implements something like it in binaryen which also allows the wasm backend to use it. As a result, Python should now be portable using the wasm backend.
The mechanism used for the emulation is to make all indirect calls use a fixed number of arguments, all of type i64, and a return type of also i64. Thunks are then placed in the table which translate the arguments properly for the target, basically by reinterpreting to i64 and back. As a result, receiving an i64 when an i32 is sent will have the upper bits all zero, and the reverse would truncate the upper bits, etc. (Note that this is different than emscripten's existing emulation, which converts (as signed) to a double. That makes sense for JS where double's can contain all numeric values, but in wasm we have i64s. Also, bitwise conversion may be more like what native archs do anyhow. It is enough for Python.)
Also adds validation for a function's type matching the function's actual params and result (surprised we didn't have that before, but we didn't, and there was even a place in the test suite where that was wrong).
Also simplifies the build script by moving two cpp files into the wasm/ subdir, so they can be built once and shared between the various tools.
|
| |
|
|
| |
collisions between say a global import and a function with a name from the name section that happens to match it (#1424)
|
| |
|
|
|
|
|
|
| |
* Dedupe function names when reading a binary
* More robust name deduplication, use .s instead of _s
* Add name-duplicated wasm binaries
|
| |
|
|
| |
* rename WasmType to Type. it's in the wasm:: namespace anyhow, and without Wasm- it fits in better alongside Index, Address, Expression, Module, etc.
|
| | |
|
| |
|
|
|
|
|
|
| |
* fix wait and wake binary format support, they have alignments and offsets
* don't emit unreachable parts of atomic operations, for simplicity and to avoid special handling
* don't emit atomic waits by default in the fuzzer, they hang in native vm support
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* Skeleton of a beginning of o2wasm, WIP and probably not going to be used
* Get building post-cherry-pick
* ast->ir, remove commented out code, include a debug module print because linking
* Read linking section, print emscripten metadata json
* WasmBinaryWriter emits user sections on Module
* Remove debugging prints, everything that isn't needed to build metadata
* Rename o2wasm to lld-metadata
* lld-metadata support for outputting to file
* Use tables index instead of function index for initializer functions
* Add lld-emscripten tool to add emscripten-runtime functions to wasm modules (built with lld)
* Handle EM_ASM in lld-emscripten
* Add a list of functions to forcibly export (for initializer functions)
* Disable incorrect initializer function reading
* Add error printing when parsing .o files in lld-metadata
* Remove ';; METADATA: ' prefix from lld-metadata, output is now standalone json
* Support em_asm consts that aren't at the start of a segment
* Initial test framework for lld-metadata tool
* Add em_asm test
* Add support for WASM_INIT_FUNCS in the linking section
* Remove reloc section parsing because it's unused
* lld-emscripten can read and write text
* Add test harness for lld-emscripten
* Export all functions for now
* Add missing lld test output
* Add support for reading object files differently
Only difference so far is in importing mutable globals being an object
file representation for symbols, but invalid wasm.
* Update help strings
* Update linking tests for stackAlloc fix
* Rename lld-emscripten,lld-metadata to wasm-emscripten-finalize,wasm-link-metadata
* Add help text to header comments
* auto& instead of auto &
* Extract LinkType to abi/wasm-object.h
* Remove special handling for wasm object file reading, allow mutable globals
* Add braces around default switch case
* Fix flake8 errors
* Handle generating dyncall thunks for imports as well
* Use explicit bool for stackPointerGlobal
* Use glob patterns for lld file iteration
* Use __wasm_call_ctors for all initializer functions
|
| |
|
| |
Emits binary size and opcode counts for each function, which helps investigating what's taking up space in a wasm binary.
|
| |
|
|
|
| |
Instead merge constant-offset segments if we must in order to stay under the limit.
If we can't - too many non-constant-offset segments - then issue a warning.
|
| |
|
|
|
|
| |
* Check if there is a currFunction before using it (we need it for some stacky code; a valid wasm wouldn't need a function in that location anyhow, as what can be put in a memory/table offset is very limited).
* Huge alignment led us to do a power of 2 shift that is undefined behavior.
Also adds a test facility to check we don't crash on testcases.
|
| |
|
|
|
|
| |
* remove unneeded code to handle a br to the return from the function. Now that we use getBlockOrSingleton there, it does that for us anyhow
* fix a fuzz bug of popping from outside a block
|
| |
|
|
| |
* remove unneeded code to handle a br to the return from the function. Now that we use getBlockOrSingleton there, it does that for us anyhow
|
| | |
|
| | |
|
| |
|
| |
The IR is indeed a tree, but not an "abstract syntax tree" since there is no language for which it is the syntax (except in the most trivial and meaningless sense).
|
| | |
|
| |
|
|
| |
complaining about out-of-range values (#1233)
|
| | |
|
| | |
|
| |
|
| |
* optimize wasm reading: use a set of the breaks we've seen, don't rescan blocks to see if they have breaks to them
|
| |
|
|
|
|
| |
* don't emit a toplevel block if we don't need to, as in wasm it is a list context
* don't create unnecessary blocks in wasm reading
|
| |
|
| |
These are not atomic operations, but are added with the atomic operations to keep from having to define atomic versions of all the sign-extending loads (an atomic zero-extending load + signext operation can be used instead).
|
| |
|
|
| |
validation that was from when we differentiated reachable from unreachable breaks (#1166)
|
| |
|
| |
According to spec at https://github.com/WebAssembly/threads/blob/master/proposals/threads/Overview.md#wait-and-wake-operators
|
| |
|
| |
Ignoring unreachable code in wasm binaries lets us avoid corner cases with unstructured code in wasm binaries that is a poor fit for Binaryen's structured IR.
|
| |
|
|
| |
* emit optimal-size LEBs in section/subsection/function body sizes, instead of preallocating 5 bytes
|
| |
|
|
| |
unreachable
|
| | |
|
| | |
|
| |\ |
|
| | |
| |
| |
| |
| |
| |
| | |
Emit valid wasm binaries even for corner cases of unreachable code.
* emit an unreachable after a node that pushes a value that has unreachable type (where wasm type checking would have pushed a concrete type)
* conversely, as a hack, emulate the wasm polymorphic stack mode by not emptying the stack when it has one element and that element is unreachable. this lets further pops work (all returning an unreachable element)
|
| | | |
|
| |/
|
|
| |
unreachable stacky code which may introduce concrete elements in non-final block positoins
|
| |
|
|
| |
to make this practical
|
| | |
|
| |
|
|
|
| |
threads proposal (#1082)
Also leave a stub (but valid) visitAtomicRMW in the visitor template so that not all visitors need to implement this function yet.
|
| |
|
|
| |
* show a clear error on nulls in inline strings (which we don't support, and in general are not seen in practice, but are technically valid wasm) in binary format reading
|
| |
|
|
|
| |
Add IR, wast and binary support for atomic loads and stores.
Currently all IR generated by means other than parsing wast and binary files always generates non-atomic accesses, and optimizations have not yet been made aware of atomics, so they are certainly not ready to be used yet.
|
| |
|
|
|
| |
Begin to implement wasm threading proposal in https://github.com/WebAssembly/threads/blob/master/proposals/threads/Overview.md
This PR just has shared memory attribute with wast and binary support.
|
