summaryrefslogtreecommitdiff
path: root/src/passes/DeadCodeElimination.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [EH] Fix pop enclosed within a block in DCE (#6922)Heejin Ahn2024-09-101-12/+13
| | | | | | | | | | | #6400 fixed this case but that handled only when a `pop` is an immediate child of the current expression, but a `pop` can be nested deeper down. We conservatively run the EH fixup whenever we have a `pop` and create `block`s in the optimization. We considered using `FindAll<Pop>` to make it precise, but we decided the quadratic time plexity was not worth it. Fixes #6918.
* [NFC] Standardize Super:: over super:: (#6920)Alon Zakai2024-09-101-1/+1
| | | | As the name of a class, uppercase seems better here.
* [Exceptions] Finish interpreter + optimizer support for try_table. (#6814)Sébastien Doeraene2024-08-201-0/+6
| | | | | | * Add interpreter support for exnref values. * Fix optimization passes to support try_table. * Enable the interpreter (but not in V8, see code) on exceptions.
* DCE: Fix old EH on a pop that gets moved in a catch body (#6400)Alon Zakai2024-03-141-7/+25
|
* Refactor interaction between Pass and PassRunner (#5093)Thomas Lively2022-09-301-1/+3
| | | | | | | | | | | | | | Previously only WalkerPasses had access to the `getPassRunner` and `getPassOptions` methods. Move those methods to `Pass` so all passes can use them. As a result, the `PassRunner` passed to `Pass::run` and `Pass::runOnFunction` is no longer necessary, so remove it. Also update `Pass::create` to return a unique_ptr, which is more efficient than having it return a raw pointer only to have the `PassRunner` wrap that raw pointer in a `unique_ptr`. Delete the unused template `PassRunner::getLast()`, which looks like it was intended to enable retrieving previous analyses and has been in the code base since 2015 but is not implemented anywhere.
* [Wasm GC] Support non-nullable locals in the "1a" form (#4959)Alon Zakai2022-08-311-0/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | An overview of this is in the README in the diff here (conveniently, it is near the top of the diff). Basically, we fix up nn locals after each pass, by default. This keeps things easy to reason about - what validates is what is valid wasm - but there are some minor nuances as mentioned there, in particular, we ignore nameless blocks (which are commonly added by various passes; ignoring them means we can keep more locals non-nullable). The key addition here is LocalStructuralDominance which checks which local indexes have the "structural dominance" property of 1a, that is, that each get has a set in its block or an outer block that precedes it. I optimized that function quite a lot to reduce the overhead of running that logic after each pass. The overhead is something like 2% on J2Wasm and 0% on Dart (0%, because in this mode we shrink code size, so there is less work actually, and it balances out). Since we run fixups after each pass, this PR removes logic to manually call the fixup code from various places we used to call it (like eh-utils and various passes). Various passes are now marked as requiresNonNullableLocalFixups => false. That lets us skip running the fixups after them, which we normally do automatically. This helps avoid overhead. Most passes still need the fixups, though - any pass that adds a local, or a named block, or moves code around, likely does. This removes a hack in SimplifyLocals that is no longer needed. Before we worked to avoid moving a set into a try, as it might not validate. Now, we just do it and let fixups happen automatically if they need to: in the common code they probably don't, so the extra complexity seems not worth it. Also removes a hack from StackIR. That hack tried to avoid roundtrip adding a nondefaultable local. But we have the logic to fix that up now, and opts will likely keep it non-nullable as well. Various tests end up updated here because now a local can be non-nullable - previous fixups are no longer needed. Note that this doesn't remove the gc-nn-locals feature. That has been useful for testing, and may still be useful in the future - it basically just allows nn locals in all positions (that can't read the null default value at the entry). We can consider removing it separately. Fixes #4824
* Basic EH instrucion support for the new spec (#3487)Heejin Ahn2021-01-151-2/+5
| | | | | | | | | | | | | | | | | | | | This updates `try`-`catch`-`catch_all` and `rethrow` instructions to match the new spec. `delegate` is not included. Now `Try` contains not a single `catchBody` expression but a vector of catch bodies and events. This updates most existing routines, optimizations, and tests modulo the interpreter and the CFG traversal. Because the interpreter has not been updated yet, the EH spec test is temporarily disabled in check.py. Also, because the CFG traversal for EH is not yet updated, several EH tests in `rse_all-features.wast`, which uses CFG traversal, are temporarily commented out. Also added a few more tests in existing EH test functions in test/passes. In the previous spec, `catch` was catching all exceptions so it was assumed that anything `try` body throws is caught by its `catch`, but now we can assume the same only if there is a `catch_all`. Newly added tests test cases when there is a `catch_all` and cases there are only `catch`es separately.
* Rewrite DCE pass (#3274)Alon Zakai2020-10-261-493/+95
| | | | | | | | | | | | | | | | | | | | | | | | | The DCE pass is one of the oldest in binaryen, and had quite a lot of cruft from the changes in unreachability and other stuff in wasm and binaryen's history. This PR rewrites it from scratch, making it about 1/3 the size. I noticed this when looking for places to use code autogeneration. The old version had annoying boilerplate, while the new one avoids any need for it. There may be noticeable differences, as the old pass did more than it needed to. It overlapped with remove-unused-names for some reason I don't remember. The new pass leaves that to the other pass to do. I added another run of remove-unused-names to avoid noticeable differences in optimized builds, but you can see differences in the testcases that only run DCE by itself. (The test differences in this PR are mostly whitespace.) (The overlap is that if a block ended up not needed, that is, all branches to it were removed, the old DCE would remove the block.) This pass is about 15% faster than the old version. However, when adding another run of remove-unused-names the difference basically vanishes, so this isn't a speedup.
* Implement v128.{load,store}{8,16,32,64}_lane instructions (#3278)Thomas Lively2020-10-221-0/+2
| | | | | | | These instructions are proposed in https://github.com/WebAssembly/simd/pull/350. This PR implements them throughout Binaryen except in the C/JS APIs and in the fuzzer, where it leaves TODOs instead. Right now these instructions are just being implemented for prototyping so adding them to the APIs isn't critical and they aren't generally available to be fuzzed in Wasm engines.
* GC: Add stubs for the remaining instructions (#3174)Daniel Wirtz2020-09-291-0/+24
| | | 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: Add i31 instructions (#3154)Daniel Wirtz2020-09-241-0/+4
| | | 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.
* GC: Add ref.eq instruction (#3145)Daniel Wirtz2020-09-211-0/+10
| | | 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.
* Refactor Host expression to MemorySize and MemoryGrow (#3137)Daniel Wirtz2020-09-171-3/+9
| | | 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.
* Remove `Push` (#2867)Thomas Lively2020-05-221-2/+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.
* Handle throw and rethrow in DCE (#2844)Heejin Ahn2020-05-111-8/+12
| | | | This adds missing handlings for `throw` and `rethrow` in DCE. They should set `reachable` variable to `false`, like other branches.
* Initial multivalue support (#2675)Thomas Lively2020-03-051-0/+4
| | | | | | | | | Implements parsing and emitting of tuple creation and extraction and tuple-typed control flow for both the text and binary formats. TODO: - Extend Precompute/interpreter to handle tuple values - C and JS API support/testing - Figure out how to lower in stack IR - Fuzzing
* [NFC] Enforce use of `Type::` on type names (#2434)Thomas Lively2020-01-071-4/+8
|
* Add support for reference types proposal (#2451)Heejin Ahn2019-12-301-0/+6
| | | | | | | | | | | | This adds support for the reference type proposal. This includes support for all reference types (`anyref`, `funcref`(=`anyfunc`), and `nullref`) and four new instructions: `ref.null`, `ref.is_null`, `ref.func`, and new typed `select`. This also adds subtype relationship support between reference types. This does not include table instructions yet. This also does not include wasm2js support. Fixes #2444 and fixes #2447.
* Add string parameter to WASM_UNREACHABLE (#2499)Sam Clegg2019-12-051-2/+2
| | | | | This works more like llvm's unreachable handler in that is preserves information even in release builds.
* Remove 'none' type as a branch target in ReFinalize (#2492)Alon Zakai2019-12-041-1/+1
| | | | | | | | | | | | | | | | | That was needed for super-old wasm type system, where we allowed (block $x (br_if $x (unreachable) (nop) ) ) That is, we differentiated "taken" branches from "named" ones (just referred to by name, but not actually taken as it's in unreachable code). We don't need to differentiate those any more. Remove the ReFinalize code that considered it, and also remove the named/taken distinction in other places.
* Add EH support for DCE pass (#2415)Heejin Ahn2019-11-011-1/+30
| | | | Like an `If`, `Try` construct is reachable when either its try body or catch body is reachable. This adds support for that.
* vNxM.load_splat instructions (#2350)Thomas Lively2019-09-231-0/+2
| | | | | | | Introduces a new instruction class, `SIMDLoad`. Implements encoding, decoding, parsing, printing, and interpretation of the load and splat instructions, including in the C and JS APIs. `v128.load` remains in the `Load` instruction class for now because the interpreter code expects a `Load` to be able to load any memory value type.
* QFMA/QFMS instructions (#2328)Thomas Lively2019-09-031-2/+2
| | | | | | | | | Renames the SIMDBitselect class to SIMDTernary and adds the new {f32x4,f64x2}.qfm{a,s} ternary instructions. Because the SIMDBitselect class is no more, this is a backwards-incompatible change to the C interface. The new instructions are not yet used in the fuzzer because they are not yet implemented in V8. The corresponding LLVM commit is https://reviews.llvm.org/rL370556.
* Add atomic.fence instruction (#2307)Heejin Ahn2019-08-271-0/+2
| | | | | | | This adds `atomic.fence` instruction: https://github.com/WebAssembly/threads/blob/master/proposals/threads/Overview.md#fence-operator This also fix bugs in `atomic.wait` and `atomic.notify` instructions in binaryen.js and adds tests for them.
* Add basic exception handling support (#2282)Heejin Ahn2019-08-131-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This adds basic support for exception handling instructions, according to the spec: https://github.com/WebAssembly/exception-handling/blob/master/proposals/Exceptions.md This PR includes support for: - Binary reading/writing - Wast reading/writing - Stack IR - Validation - binaryen.js + C API - Few IR routines: branch-utils, type-updating, etc - Few passes: just enough to make `wasm-opt -O` pass - Tests This PR does not include support for many optimization passes, fuzzer, or interpreter. They will be follow-up PRs. Try-catch construct is modeled in Binaryen IR in a similar manner to that of if-else: each of try body and catch body will contain a block, which can be omitted if there is only a single instruction. This block will not be emitted in wast or binary, as in if-else. As in if-else, `class Try` contains two expressions each for try body and catch body, and `catch` is not modeled as an instruction. `exnref` value pushed by `catch` is get by `pop` instruction. `br_on_exn` is special: it returns different types of values when taken and not taken. We make `exnref`, the type `br_on_exn` pushes if not taken, as `br_on_exn`'s type.
* Finalize tail call support (#2246)Thomas Lively2019-07-231-1/+9
| | | | Adds tail call support to fuzzer and makes small changes to handle return calls in multiple utilities and passes. Makes larger changes to DAE and inlining passes to properly handle tail calls.
* Minimal Push/Pop support (#2207)Alon Zakai2019-07-031-0/+4
| | | | | | | This is the first stage of adding support for stacky/multivaluey things. It adds new push/pop instructions, and so far just shows that they can be read and written, and that the optimizer doesn't do anything immediately wrong on them. No fuzzer support, since there isn't a "correct" way to use these yet. The current test shows some "incorrect" usages of them, which is nice to see that we can parse/emit them, but we should replace them with proper usages of push/pop once we actually have those (see comments in the tests). This should be enough to unblock exceptions (which needs a pop in try-catches). It is also a step towards multivalue (I added some docs about that), but most of multivalue is left to be done.
* Reflect instruction renaming in code (#2128)Heejin Ahn2019-05-211-10/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | - Reflected new renamed instruction names in code and tests: - `get_local` -> `local.get` - `set_local` -> `local.set` - `tee_local` -> `local.tee` - `get_global` -> `global.get` - `set_global` -> `global.set` - `current_memory` -> `memory.size` - `grow_memory` -> `memory.grow` - Removed APIs related to old instruction names in Binaryen.js and added APIs with new names if they are missing. - Renamed `typedef SortedVector LocalSet` to `SetsOfLocals` to prevent name clashes. - Resolved several TODO renaming items in wasm-binary.h: - `TableSwitch` -> `BrTable` - `I32ConvertI64` -> `I32WrapI64` - `I64STruncI32` -> `I64SExtendI32` - `I64UTruncI32` -> `I64UExtendI32` - `F32ConvertF64` -> `F32DemoteI64` - `F64ConvertF32` -> `F64PromoteF32` - Renamed `BinaryenGetFeatures` and `BinaryenSetFeatures` to `BinaryenModuleGetFeatures` and `BinaryenModuleSetFeatures` for consistency.
* clang-tidy braces changes (#2075)Alon Zakai2019-05-011-3/+6
| | | Applies the changes in #2065, and temprarily disables the hook since it's too slow to run on a change this large. We should re-enable it in a later commit.
* Apply format changes from #2048 (#2059)Alon Zakai2019-04-261-95/+133
| | | Mass change to apply clang-format to everything. We are applying this in a PR by me so the (git) blame is all mine ;) but @aheejin did all the work to get clang-format set up and all the manual work to tidy up some things to make the output nicer in #2048
* Rename atomic wait/notify instructions (#1972)Heejin Ahn2019-03-301-1/+1
| | | | | | | | This renames the following: - `i32.wait` -> `i32.atomic.wait` - `i64.wait` -> `i64.atomic.wait` - `wake` -> `atomic.notify` to match the spec.
* Bulk memory operations (#1892)Thomas Lively2019-02-051-0/+4
| | | | | | Bulk memory operations The only parts missing are the interpreter implementation and spec tests.
* SIMD (#1820)Thomas Lively2018-12-131-0/+5
| | | | | | | | | Implement and test the following functionality for SIMD. - Parsing and printing - Assembling and disassembling - Interpretation - C API - JS API
* Remove default cases (#1757)Thomas Lively2018-11-271-2/+2
| | | | | | Where reasonable from a readability perspective, remove default cases in switches over types and instructions. This makes future feature additions easier by making the compiler complain about each location where new types and instructions are not yet handled.
* Unify imported and non-imported things (#1678)Alon Zakai2018-09-191-5/+0
| | | | | | | | | | | | | | Fixes #1649 This moves us to a single object for functions, which can be imported or nor, and likewise for globals (as a result, GetGlobals do not need to check if the global is imported or not, etc.). All imported things now inherit from Importable, which has the module and base of the import, and if they are set then it is an import. For convenient iteration, there are a few helpers like ModuleUtils::iterDefinedGlobals(wasm, [&](Global* global) { .. use global .. }); as often iteration only cares about imported or defined (non-imported) things.
* Souper integration + DataFlow optimizations (#1638)Alon Zakai2018-08-271-1/+1
| | | | | | | | | Background: google/souper#323 This adds a --souperify pass, which emits Souper IR in text format. That can then be read by Souper which can emit superoptimization rules. We hope that eventually we can integrate those rules into Binaryen. How this works is we emit an internal "DataFlow IR", which is an SSA-based IR, and then write that out into Souper text. This also adds a --dfo pass, which stands for data-flow optimizations. A DataFlow IR is generated, like in souperify, and then performs some trivial optimizations using it. There are very few things that can do that our other optimizations can't already, but this is also good testing for the DataFlow IR, plus it is good preparation for using Souper's superoptimization output (which would also construct DataFlow IR, like here, but then do some matching on the Souper rules).
* Rename WasmType => Type (#1398)Alon Zakai2018-02-021-1/+1
| | | | * rename WasmType to Type. it's in the wasm:: namespace anyhow, and without Wasm- it fits in better alongside Index, Address, Expression, Module, etc.
* notation change: AST => IR (#1245)Alon Zakai2017-10-241-3/+3
| | | 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).
* Atomics support in interpreter + optimizer + fuzz fixes for that (#1227)Alon Zakai2017-10-201-0/+4
|
* fix a dce fuzz bug where if changed to unreachable but didn't propagate that ↵Alon Zakai2017-10-101-1/+5
| | | | effect up. also add set_global support in dce (#1218)
* Add a superclass typedef to WalkerPass to simplify overrides (#1211)jgravelle-google2017-10-041-2/+2
|
* fix dce bug with not updating the parent when turning a node unreachable (#1198)Alon Zakai2017-09-251-20/+23
|
* Optimizer support for atomic instructions (#1094)Derek Schuff2017-07-211-60/+38
| | | | | | * Teach EffectAnalyzer not to reorder atomics wrt other memory operations. * Teach EffectAnalyzer not to reorder host operations with memory operations * Teach various passes about the operands of AtomicRMW and AtomicCmpxchg * Factor out some functions in DeadCodeElimination and MergeBlocks
* add the option to seek named breaks, not just taken breaks; refactor headers ↵Alon Zakai (kripken)2017-07-111-2/+2
| | | | to make this practical
* Support new result syntax for if/loop/block (#1047)Sam Clegg2017-06-121-1/+1
| | | | | | Support both syntax formats in input since the old spec tests still need to be parsable.
* optimize dceing of blocks and known-to-exist children (#1015)Alon Zakai2017-05-181-57/+34
|
* Validate finalization (#1014)Alon Zakai2017-05-181-8/+34
| | | | | | | * validate that types are properly finalized, when in pass-debug mode (BINARYEN_PASS_DEBUG env var): check after each pass is run that the type of each node is equal to the proper type (when finalizing it, i.e., fully recomputing the type). * fix many fuzz bugs found by that. * in particular, fix dce bugs with type changes not being fully updated during code removal. add a new TypeUpdater helper class that lets a pass update types efficiently, by the helper tracking deps between blocks and branches etc., and updating/propagating type changes only as necessary.
* when creating blocks during dce, make sure they have the same type as before ↵Alon Zakai (kripken)2017-05-021-9/+14
| | | | the transformation, as the outside might care about that
* improve dce to handle more cases of nested unreachable code (#989)Alon Zakai2017-05-021-7/+41
| | | | | | | | | | * improve dce to handle more cases of nested unreachable code, in particular, when the child is unreachable in type but not an actual Unreachable node, e.g. if it's a br. in that case, we just need to verify that the br is not to us where we are a block or loop * handle unreachable switch conditions in dce * handle dce of br condition which is unreachable, and host arguments * handle dce of block i32 etc. which is actually unreachable
* Default Walker subclasses to using Visitor<SubType> (#921)jgravelle-google2017-02-231-2/+2
| | | | Most module walkers use PostWalker<T, Visitor<T>>, let that pattern be expressed as simply PostWalker<T>
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-07 10:09:09 +0000