summaryrefslogtreecommitdiff
path: root/src/ir
Commit message (Collapse)AuthorAgeFilesLines
* Refactor naming convention for functions handling tuples (#3196)Max Graey2020-10-092-4/+4
| | | When there are two versions of a function, one handling tuples and the other handling non-tuple values, the previous naming convention was to have "Single" in the name of the non-tuple handling function. This PR simplifies the convention and shortens function names by making the names plural for the tuple-handling version and singular for the non-tuple-handling version.
* Add optimization rules for some shift operations (#3099)Max Graey2020-10-071-0/+7
| | | Specifically, truncates constant shift values that are greater than the number of bits available and optimizes out explicit masking of the shift value that is redundant with the implicit masking performed by shift operations.
* Optimize "clear bit mask" combination to cyclic rotation over preinverted ↵Max Graey2020-10-011-0/+10
| | | | mask (#3184)
* Clean up support/bits.h (#3177)Thomas Lively2020-09-301-5/+5
| | | | | Use overloads instead of templates where applicable and change function names from PascalCase to camelCase. Also puts the functions in the Bits namespace to avoid naming conflicts.
* GC: Add stubs for the remaining instructions (#3174)Daniel Wirtz2020-09-295-0/+139
| | | NFC, except adding most of the boilerplate for the remaining GC instructions. Each implementation site is marked with a respective `TODO (gc): theInstruction` in between the typical boilerplate code.
* GC: Fuzzing support for i31 (#3169)Daniel Wirtz2020-09-292-9/+15
| | | Integrates `i31ref` types and instructions into the fuzzer, by assuming that `(i31.new (i32.const N))` is constant and hence suitable to be used in global initializers.
* Add new unary and binary matchers (#3168)Thomas Lively2020-09-241-34/+82
| | | | | Adds new matchers that allow for matching any unary or binary operation and optionally extracting it. The previous matchers only allowed matching specific unary and binary operations. This should help simplify #3132.
* GC: Add i31 instructions (#3154)Daniel Wirtz2020-09-245-0/+16
| | | Adds the `i31.new` and `i31.get_s/u` instructions for creating and working with `i31ref` typed values. Does not include fuzzer integration just yet because the fuzzer expects that trivial values it creates are suitable in global initializers, which is not the case for trivial `i31ref` expressions.
* ir/bits.h cleanups after #2879 (#3156)Alon Zakai2020-09-221-19/+11
| | | | Improve some comments, and remove fast paths that are just optimizations for compile time (code clarity matters more here).
* Fix i64 type checking in getMaxBitsForLocal of DummyLocalInfoProvider (#3150)Max Graey2020-09-211-2/+1
| | | | | The problem existed for a very long time, but since the DummyLocalInfoProvider is almost never used, this did not create problems.
* GC: Add ref.eq instruction (#3145)Daniel Wirtz2020-09-216-4/+13
| | | With `eqref` now integrated, the `ref.eq` instruction can be implemented. The only valid LHS and RHS value is `(ref.null eq)` for now, but implementation and fuzzer integration is otherwise complete.
* GC: Integrate eqref and i31ref types (#3141)Daniel Wirtz2020-09-191-0/+4
| | | Adds the `eqref` and `i31ref` types to their respective code locations. Implements what can be implemented trivially and otherwise traps with a TODO for now. Integration of `eqref` is mostly complete due to it being nullable, just like `anyref`, but `i31ref` needs to remain disabled in the fuzzer because we are lacking the functionality to create trivial `i31ref` values, i.e. `(i31.new (i32.const 0))`, which is left for follow-ups to implement.
* Expression matching API (#3134)Thomas Lively2020-09-182-6/+802
| | | | | | | | | | | Provides an easily extensible layered API for matching expression patterns and extracting their components. The low-level API provides modular building blocks for creating matchers for any data type and the high-level API provides a succinct and flexible interface for matching expressions and extracting useful information from them. Matchers are currently provided for Const, Unary, Binary, and Select instructions. Adding a matcher for a new type of expression is straightforward enough that I expect to add them as they become useful as part of other changes.
* Initial implementation of "Memory64" proposal (#3130)Wouter van Oortmerssen2020-09-181-3/+1
| | | Also includes a lot of new spec tests that eventually need to go into the spec repo
* Implement more cases for getMaxBits (#2879)Max Graey2020-09-171-15/+172
| | | | | | | | | | | | | | | - Complete 64-bit cases in range `AddInt64` ... `ShrSInt64` - `ExtendSInt32` and `ExtendUInt32` for unary cases - For binary cases - `AddInt32` / `AddInt64` - `MulInt32` / `MulInt64` - `RemUInt32` / `RemUInt64` - `RemSInt32` / `RemSInt64` - `DivUInt32` / `DivUInt64` - `DivSInt32` / `DivSInt64` - and more Also more fast paths for some getMaxBits calculations
* Refactor Host expression to MemorySize and MemoryGrow (#3137)Daniel Wirtz2020-09-176-21/+31
| | | Aligns the internal representations of `memory.size` and `memory.grow` with other more recent memory instructions by removing the legacy `Host` expression class and adding separate expression classes for `MemorySize` and `MemoryGrow`. Simplifies related APIs, but is also a breaking API change.
* Add float operations for isSymmetric util (#3127)Max Graey2020-09-141-0/+5
| | | Add floating point Eq and Ne operators to Properties::isSymmetric. Also treat additional float ops as symmetric specifically in OptimizeInstructions when their operands are known to be non-NaN.
* Fix RefNull issues (#3123)Daniel Wirtz2020-09-131-1/+1
| | | | | | | | | * ExpressionAnalyzer: Fix `ref.null ht` equality check to include `ht`. * Precompute: Fix `ref.null ht` expression reuse to also update `ht`. * Fuzzing: Fix `ref.null func` becoming canonicalized to `ref.func $funcref` when evaluating execution results, by adding a check for `isNull`. * Fuzzing: Print actual and expected execution results when aborting. * Tests: Update `if-arms-subtype` test in `optimize-instructions` to check that identical `if` arms become folded while not identical arms are kept.
* Add anyref feature and type (#3109)Daniel Wirtz2020-09-101-0/+2
| | | Adds `anyref` type, which is enabled by a new feature `--enable-anyref`. This type is primarily used for testing that passes correctly handle subtype relationships so that the codebase will continue to be prepared for future subtyping. Since `--enable-anyref` is meaningless without also using `--enable-reference-types`, this PR also makes it a validation error to pass only the former (and similarly makes it a validation error to enable exception handling without enabling reference types).
* Simplify BinaryenIRWriter (#3110)Thomas Lively2020-09-103-27/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | BinaryenIRWriter was previously inconsistent about whether or not it emitted an instruction if that instruction was not reachable. Instructions that produced values were not emitted if they were unreachable, but instructions that did not produce values were always emitted. Additionally, blocks continued to emit their children even after emitting an unreachable child. Since it was not possible to tell whether an unreachable instruction's parent would be emitted, BinaryenIRWriter had to be very defensive and emit many extra `unreachable` instructions around unreachable code to avoid type errors. This PR unifies the logic for emitting all non-control flow instructions and changes the behavior of BinaryenIRWriter so that it never emits instructions that cannot be reached due to having unreachable children. This means that extra `unreachable` instructions now only need to be emitted after unreachable control flow constructs. BinaryenIRWriter now also stops emitting instructions inside blocks after the first unreachable instruction as an extra optimization. This change will also simplify Poppy IR stackification (see #3059) by guaranteeing that instructions with unreachable children will not be emitted into the stackifier. This makes satisfying the Poppy IR rule against unreachable Pops trivial, whereas previously satisfying this rule would have required about about 700 additional lines of code to recompute the types of all unreachable children for any instruction.
* Poppy IR wast parsing and validation (#3105)Thomas Lively2020-09-092-2/+35
| | | | | Adds an IR profile to each function so the validator can determine which validation rules to apply and adds a flag to have the wast parser set the profile to Poppy for testing purposes.
* Update reference types (#3084)Daniel Wirtz2020-09-094-9/+10
| | | | | | | Align with the current state of the reference types proposal: * Remove `nullref` * Remove `externref` and `funcref` subtyping * A `Literal` of a nullable reference type can now represent `null` (previously was type `nullref`) * Update the tests and temporarily comment out those tests relying on subtyping
* Stack utils (#3083)Thomas Lively2020-09-073-0/+489
| | | | | | Implement and test utilities for manipulating and analyzing a new stacky form of Binaryen IR that is able to express arbitrary stack machine code. This new Poppy IR will eventually replace Stack IR, and new optimization passes will be built with these utilities. See #3059.
* Optimize MergeBlocks by caching branch results (#3102)Alon Zakai2020-09-031-8/+94
| | | | | | | | | | | BranchSeekerCache caches the set of branches in a node + its children, and helps compute new results by looking in the cache and using data for the children. This avoids quadratic time in the common case of a post-walk on a tower of nested blocks which is common in a switch. Fixes #3090 . On the testcase there this pass goes from over a minute to less than a second.
* MinifyImportsAndExports: Minify the memory and table as well. (#3089)Alon Zakai2020-09-021-0/+8
| | | | | | | | | | | | We were careful not to minify those, as well as the stack pointer, which makes sense in dynamic linking. But we don't run this pass in dynamic linking anyhow - we need the proper names of symbols in that case. So this was not helping us, and was just a leftover from an early state. This both a useful optimization and also important for #3043, as the wasm backend exports the table as __indirect_function_table - a much longer name than emscripten's table. So just changing to that would regress code size on small projects. Once we land this, the name won't matter as it will be minified anyhow.
* Add new compound Signature, Struct and Array types (#3012)Daniel Wirtz2020-08-241-1/+1
| | | | | Extends the `Type` hash-consing infrastructure to handle type-parameterized and constructed types introduced in the typed function references and GC proposals. This should be a non-functional change since the new types are not used anywhere yet. Recursive type construction and canonicalization is also left as future work. Co-authored-by: Thomas Lively <tlively@google.com>
* Prepare for compound types that are single but not basic (#3046)Daniel Wirtz2020-08-173-5/+5
| | | | | | | | | | | | | | As a follow-up to https://github.com/WebAssembly/binaryen/pull/3012#pullrequestreview-459686171 this PR prepares for the new compound Signature, Struct and Array types that are single but not basic. This includes: * Renames `Type::getSingle` to `Type::getBasic` (NFC). Previously, its name was not representing its implementation (`isSingle` excluded `none` and `unreachable` while `getSingle` didn't, i.e. `getSingle` really was `getBasic`). Note that a hypothetical `Type::getSingle` cannot return `ValueType` anyway (new compound types are single but don't map to `ValueType`), so I figured it's best to skip implementing it until we actually need it. * Marks locations where we are (still) assuming that all single types are basic types, as suggested in https://github.com/WebAssembly/binaryen/pull/3012#discussion_r465356708, but using a macro, so we get useful errors once we start implementing the new types and can quickly traverse the affected locations. The macro is added where * there used to be a `switch (type.getSingle())` or similar that handled any basic type (NFC), but in the future will also have to handle single types that are not basic types. * we are not dealing with `Unary`, `Binary`, `Load`, `Store` or `AtomicXY` instructions, since these don't deal with compound types anyway.
* Refactor hashing (#3023)Daniel Wirtz2020-08-124-31/+26
| | | | | | | | | * Unifies internal hashing helpers to naturally integrate with std::hash * Removes the previous custom implementation * Computed hashes are now always size_t * Introduces a hash_combine helper * Fixes an overwritten partial hash in Relooper.cpp
* Added headers to CMake files (#3037)Wouter van Oortmerssen2020-08-101-0/+2
| | | This is needed for headers to show up in IDE projects, and has no other effect on the build.
* Asyncify verbose option (#3022)Alon Zakai2020-08-061-3/+8
| | | | | | | | | | | | | | | | This logs out the decisions made about instrumenting functions, which can help figure out why a function is instrumented, or to get a list of what might need to be. As the test shows, it can print things like this: [asyncify] import is an import that can change the state [asyncify] calls-import can change the state due to import [asyncify] calls-calls-import can change the state due to calls-import [asyncify] calls-calls-calls-import can change the state due to calls-calls-import (the test has calls-calls-calls-import => calls-calls-import => calls-import -> import).
* Refactor getMaxBits() out of OptimizeInstructions and add beginnings of unit ↵Alon Zakai2020-08-041-69/+232
| | | | | | | | | testing for it (#3019) getMaxBits just moves around, no logic is changed. Aside from adding getMaxBits, the change in bits.h is 99% whitespace. helps #2879
* Fix the side effects of data.drop (#2996)Alon Zakai2020-07-281-2/+4
| | | | | | | | | | | | | We marked it as readsMemory so that it could be reordered with various things, except for memory.init. However, the fuzzer found that's not quite right, as it has a global side effect - memory.inits that run later can notice that. So it can't be reordered with anything that might affect global side effects from happening, as in the testcase added here (an instruction that may trap cannot be reordered with a data.drop, as it may prevent the data.drop from happening and changing global state). There may be a way to optimize this more carefully that would allow more optimizations, but as this is a rare instruction I'm not sure it's worth more work.
* Optimize select with const arms (#2869)Max Graey2020-07-221-2/+15
| | | | | x ? 1 : 0 => !!x and so forth.
* Add a builder.makeConst helper template (#2971)Alon Zakai2020-07-213-5/+4
|
* Avoid __popcnt and __popcnt64 intrinsics for MSVC (#2944)Max Graey2020-07-061-3/+3
| | | | We may need to check the CPU ID or something else before using those special things on MSVC. To be safe, avoid them for now.
* More optimizations for pow of two and pos/neg one const on the right (#2870)Max Graey2020-06-221-0/+40
|
* Rename anyref to externref to match proposal change (#2900)Jay Phelps2020-06-101-2/+2
| | | | | | | anyref future semantics were changed to only represent opaque host values, and thus renamed to externref. [Chromium](https://bugs.chromium.org/p/v8/issues/detail?id=7748#c360) was just updated to today (not yet released). I couldn't find a Mozilla bugzilla ticket mentioning externref so I don't immediately know if they've updated yet. https://github.com/WebAssembly/reference-types/pull/87
* Add prototype SIMD rounding instructions (#2895)Thomas Lively2020-06-051-0/+8
| | | As specified in https://github.com/WebAssembly/simd/pull/232.
* DeNaN improvements (#2888)Alon Zakai2020-06-031-1/+22
| | | | | | | | | Instead of instrumenting every local.get, instrument parameters on arrival at a function once on entry. After that, every local will always contain a de-naned value (since we would denan on a local.set). This is more efficient and also less confusing I think. Also avoid doing anything to values that fall through as they have already been fixed up.
* Prevent pops from sinking in SimplifyLocals (#2885)Heejin Ahn2020-06-031-4/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This prevents `exnref.pop`s from being sinked and separated from `catch`. For example, ```wast (try (do) (catch (local.set $0 (exnref.pop)) (call $foo (i32.const 3) (local.get $0) ) ) ) ``` Here, if we sink `exnref.pop` to remove `local.set $0` and `local.get $0`, it becomes this: ```wast (try (do) (catch (nop) (call $foo (i32.const 3) (exnref.pop) ) ) ) ``` This move was possible because `i32.const 3` does not have any side effects. But this is incorrect because now `exnref.pop` does not follow right after `catch`. To prevent this, this patch checks this case in `canSink` in SimplifyLocals. When we encountered a similar case in CodeFolding, we prevented every expression that contains `Pop` anywhere in it from being moved, which was too conservative. This adds `danglingPop` property in `EffectAnalyzer`, so that only pops that are not enclosed within a `catch` count as 'dangling pops` and we only prevent those pops from being moved or sinked.
* Fix SideEffect::Branches to only represent branches (#2886)Heejin Ahn2020-06-021-1/+1
| | | | | | After #2783 `SideEffects::Branches` includes possibly throwing expressions, which can be calls (when EH is enabled). This changes `SideEffects::Branches` back to only include branches, returns, and infinite loops as it was before #2783.
* Refactor Effects (#2873)Alon Zakai2020-05-291-32/+49
| | | | | | | Avoid special work in analyze(). This lets breakTargets always reflect the breaks that we've seen and that might be external, and we check it in hasSideEffects etc. Also do some internal refactoring and renamings for clarity.
* Flat IR: local.set's value should not be a control flow (#2589)Alon Zakai2020-05-271-4/+10
|
* Remove `Push` (#2867)Thomas Lively2020-05-225-8/+0
| | | | | | Push and Pop have been superseded by tuples for their original intended purpose of supporting multivalue. Pop is still used to represent block arguments for exception handling, but there are no plans to use Push for anything now or in the future.
* Add EH support for SimplifyLocals (#2858)Heejin Ahn2020-05-191-1/+9
| | | | | | | - `br_on_exn`'s target block cannot be optimized to have a separate return value. This handles that in `SimplifyLocals`. - `br_on_exn` and `rethrow` can trap (when the arg is null). This handles that in `EffectAnalyzer`. - Fix a few nits
* Implement i64x2.mul (#2860)Thomas Lively2020-05-191-0/+3
| | | | This is the only instruction in the current spec proposal that had not yet been implemnented in the tools.
* Fix br_on_exn handling in ReFinalize (#2854)Heejin Ahn2020-05-151-1/+2
| | | | | | | | | | | | In `ReFinalize`'s branch handling, `updateBreakValueType` is supposed to be executed only when the branch itself is not replaced with its argument (because it is guaranteed not to be taken). Also this moves `visitBrOnExn` from `RuntimeExpressionRunner` to its base class `ExpressionRunner`, because it does not depend on anything on the runtime instance to work. This is effectively NFC for now because `visitTry` is still only implemented only in `RuntimeExpressionRunner` because it relies on multivalue handling of it, and without it we cannot create a valid exception `Literal`.
* Implement pseudo-min/max SIMD instructions (#2847)Thomas Lively2020-05-121-0/+12
| | | As specified in https://github.com/WebAssembly/simd/pull/122.
* Remove --fuzz-binary and simplify round trip (#2799)Thomas Lively2020-04-241-11/+2
| | | Since the --roundtrip pass is more general than --fuzz-binary anyways. Also reimplements `ModuleUtils::clearModule` to use the module destructor and placement new to ensure that no members are missed.
* Remove function index printing (#2742)Thomas Lively2020-04-091-52/+0
| | | | | | | | `BinaryIndexes` was only used in two places (Print.cpp and wasm-binary.h), so it didn't seem to be a great fit for module-utils.h. This change moves it to wasm-binary.h and removes its usage in Print.cpp. This means that function indexes are no longer printed, but those were of limited utility and were the source of annoying noise when updating tests, anyway.