summaryrefslogtreecommitdiff
path: root/src/support
Commit message (Collapse)AuthorAgeFilesLines
* Fix errors when building in C++20 mode (#4528)Jakub Szewczyk2022-03-182-9/+11
| | | | | | | * use [[noreturn]] available since C++11 instead of compiler-specific attributes * replace deprecated std::is_pod with is_trivial&&is_standard_layout (also available since C++11/14) * explicitly capture this in [=] lambdas * extra const functions in FeatureSet, fix implicit cast warning by using the features field directly * Use CMAKE_CXX_STANDARD to ensure the C++ standard parameter is set on all targets, remove manual compiler flag workaround.
* Generate heap type names when printing types (#4503)Thomas Lively2022-02-071-0/+29
| | | | | | | | | | | | | | | | | | | | | | The previous printing system in the Types API would print the full recursive structure of a Type or HeapType with special markers using de Bruijn indices to avoid infinite recursion and a separate special marker for when the size exceeded an arbitrary upper limit. In practice, the types printed by that system were not human readable, so all that complexity was not useful. Replace that system with a new system that always emits a HeapType name rather than recursing into the structure of inner HeapTypes. Add methods for printing Types and HeapTypes with custom HeapType name generators. Also add a new wasm-type-printing.h header with off-the-shelf type name generators that implement simple naming schemes sufficient for tests and the type fuzzer. Note that these new printing methods and the old printing methods they augment are not used for emitting text modules. Printing types as part of expressions and modules is handled by separate code in Print.cpp and the printing API modified in this PR is mostly used for debugging. However, the new printing methods are general enough that Print.cpp should be able to use them as well, so update the format used to print types in the modified printing system to match the text format in anticipation of making that change in a follow-up PR.
* CRTP topological sort utility (#4499)Thomas Lively2022-02-031-0/+118
| | | | | | | | Refactor the `TopologicalSortStack` into a `TopologicalSort` CRTP utility that manipulates the DFS stack internally instead of exposing it to the user. The only method users have to implement to use the utility is `pushPredecessors`, which should call the provided `push` method on all the predecessors of a given item. The public interface to `TopologicalSort` is an input iterator, so it can easily be used in range-based for loops.
* Topological sorting of types in isorecursive output (#4492)Thomas Lively2022-02-021-0/+2
| | | | | | | | | | | | | | | | | | | Generally we try to order types by decreasing use count so that frequently used types get smaller indices. For the equirecursive and nominal systems, there are no contraints on the ordering of types, so we just have to sort them according to their use counts. For the isorecursive type system, however, there are a number of ordering constraints that have to be met for the type section to be valid. First, types in the same recursion group must be adjacent so they can be grouped together. Second, groups must be ordered topologically so that they only refer to types in themselves or prior groups. Update type ordering to produce a valid isorecursive output by performing a topological sort on the recursion groups. While performing the sort, prefer to visit and finish processing the most used groups first as a heuristic to improve the final ordering. Do not reorder types within groups, since doing so would change type identity and could affect the external interface of the module. Leave that reordering to an optimization pass (not yet implemented) that users can explicitly opt in to.
* Create `ParentIndexIterator` to reduce iterator boilerplate (#4469)Thomas Lively2022-01-211-0/+96
| | | | | | | Add a utility class for defining all the common operations like pre- and post- increment and decrement, addition and subtraction, and assigning addition and subtraction for iterators that are comprised of a parent object and an index into that parent object. Use the new utility to reduce the boilerplate in wasm-type.h. Add a new test of the iterator behavior.
* LiteralList => Literals (#4451)Alon Zakai2022-01-131-0/+8
| | | | | | | LiteralList overlaps with Literals, but is less efficient as it is not a SmallVector. Add reserve/capacity methods to SmallVector which are now necessary to compile.
* Add categories to --help text (#4421)Alon Zakai2022-01-052-12/+47
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The general shape of the --help output is now: ======================== wasm-foo Does the foo operation ======================== wasm-foo opts: -------------- --foo-bar .. Tool opts: ---------- .. The options are now in categories, with the more specific ones - most likely to be wanted by the user - first. I think this makes the list a lot less confusing. In particular, in wasm-opt all the opt passes are now in their own category. Also add a script to make it easy to update the help tests.
* Modernize code to C++17 (#3104)Max Graey2021-11-227-33/+14
|
* Add fixup function for nested pops in catch (#4348)Heejin Ahn2021-11-222-3/+13
| | | | | | | | | | | | | | | | | | | | | | | | | This adds `EHUtils::handleBlockNestedPops`, which can be called at the end of passes that has a possibility to put `pop`s inside `block`s. This method assumes there exists a `pop` in a first-descendant line, even though it can be nested within a block. This allows a `pop` to be nested within a `block` or a `try`, but not a `loop`, since that means the `pop` can run multile times. In case of `if`, `pop` can exist only in its condition; if a `pop` is in its true or false body, that's not in the first-descendant line. This can be useful when optimization passes create blocks to do transformations. Wrapping expressions wiith a block does not change semantics most of the time, but if pops happen to be inside a block generated by those passes, they can result in invalid binaries. To test this, this adds `passes/test_passes.cpp`, which is intended to contain multiple test passes that test a single (or more) utility functions separately. Without this kind of pass, it is hard to test various cases in which nested `pop`s can be generated in existing passes. This PR also adds `PassRegistry::registerTestPass`, which registers a pass that's intended only for internal testing and does not show up in `wasm-opt --help`. Fixes #4237.
* DeadArgumentElimination argument subtyping: Add fixups if the param is used ↵Alon Zakai2021-11-111-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (#4319) Before, if we saw a param is written, that prevented us from subtyping it: function foo(x : oldType) { .. x = someValue; .. } Even if all calls to foo send some specific struct type that we'd like to subtype to, seeing that write stopped us. To handle such a write we need to do some extra handling for the case in which it is written a less-specific type (that is, if someValue is of type oldType, something like this: function foo(x : newType) { var x_old : oldType; x_old = x; // copy the param to x_old, and use x_old everywhere .. x_old = someValue; .. } That is, still refine the param type, but inside the function use a new local that has the old type, and is guaranteed to validate. This PR implements that logic so that we can optimize more cases. To allow that, this PR avoids trying to both refine a type and remove a param as being unused - that has annoying corner cases. If it is unused, we can simply remove it anyhow.
* Add a SmallSet and use it in LocalGraph. NFC (#4188)Alon Zakai2021-09-291-0/+276
| | | | | | | | | | | | | | | | | A SmallSet starts with fixed storage that it uses in the simplest possible way (linear scan, no sorting). If it exceeds a size then it starts using a normal std::set. So for small amounts of data it avoids allocation and any other overhead. This adds a unit test and also uses it in LocalGraph which provides a large amount of additional coverage. I also changed an unrelated data structure from std::map to std::unordered_map which I noticed while doing profiling in LocalGraph. (And a tiny bit of additional refactoring there.) This makes LocalGraph-using passes like ssa-nomerge and precompute-propagate 10-15% faster on a bunch of real-world codebases I tested.
* Use UniqueDeferringQueue in Precompute (#4179)Alon Zakai2021-09-221-0/+1
|
* Read from stdin when the input file is `-` (#4106)Thomas Lively2021-08-272-2/+18
| | | | We already supported `-` as meaning stdout for output and this is useful in similar situations. Fixes #4105.
* Add space between options in --help text (#3940)Thomas Lively2021-06-171-0/+1
| | | | | Improve the legibility of the option documentation by adding vertical space between options. This is particularly helpful to delimit the text of options with longer explanations.
* [wasm-split] Add an option to emit only the module names (#3901)Thomas Lively2021-05-251-8/+21
| | | | | | 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.
* Remove Type ordering (#3793)Thomas Lively2021-05-181-16/+40
| | | | | | | | | 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.
* Add namespace and include guard to insert_ordered.h (#3891)Thomas Lively2021-05-171-0/+9
|
* [NFC] Move InsertOrdered{Set,Map} into a new header (#3888)Thomas Lively2021-05-171-0/+136
| | | | | | 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`.
* Support --symbolmap and --symbolmap=FOO in wasm-opt (#3885)Alon Zakai2021-05-142-7/+6
| | | | | | | | | | 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.
* Add pass argument sugar to commandline (#3882)Alon Zakai2021-05-132-7/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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).
* UniqueDeferredQueue improvements (#3847)Alon Zakai2021-04-291-0/+26
| | | | | | | | Add clear(). Add UniqueNonrepeatingDeferredQueue which also has the property that it never repeats values in the output. Also add unit tests.
* Support comparing, subtyping, and naming recursive types (#3610)Thomas Lively2021-02-251-0/+13
| | | | | | | | | | | | | | | | | | | | | When the type section is emitted, types with an equal amount of references are ordered by an arbitrary measure of simplicity, which previously would infinitely recurse on structurally equivalent recursive types. Similarly, calculating whether an recursive type was a subtype of another recursive type could have infinitely recursed. This PR avoids infinite recursions in both cases by switching the algorithms from using normal inductive recursion to using coinductive recursion. The difference is that while the inductive algorithms assume the relations do not hold for a pair of HeapTypes until they have been exhaustively shown to hold, the coinductive algorithms assume the relations hold unless a counterexample can be found. In addition to those two algorithms, this PR also implement name generation for recursive types, using de Bruijn indices to stand in for inner uses of the recursive types. There are additional algorithms that will need to be switched from inductive to coinductive recursion, such as least upper bound generation, but these presented a good starting point and are sufficient to get some interesting programs working end-to-end.
* Remove assertions that prevent non-assertion builds (#3576)Alon Zakai2021-02-171-6/+0
| | | And fix errors from such a build.
* cleanup to allow binaryen to be built in more strict environments (#3566)walkingeyerobot2021-02-164-2/+6
|
* Debug info handling for new EH try-catch (#3496)Alon Zakai2021-01-251-0/+24
| | | | | | | | We now have multiple catches in each try, and a possible catch-all. This changes our "extra delimiter" storage to store either an "else" (unchanged from before) or an arbitrary list of things - we use that for catches.
* [GC] Fix parsing/printing of ref types using i31 (#3469)Alon Zakai2021-01-071-0/+4
| | | | | | | | | | | | This lets us parse (ref null i31) and (ref i31) and not just i31ref. It also fixes the parsing of i31ref, making it nullable for now, which we need to do until we support non-nullability. Fix some internal handling of i31 where we had just i31ref (which meant we just handled the non-nullable type). After fixing a bug in printing (where we didn't print out (ref null i31) properly), I found some a simplification, to remove TypeName.
* [GC] Add Array operations (#3436)Alon Zakai2020-12-101-0/+1
| | | | | | | | | | | | | | array.new/get/set/len - pretty straightforward after structs and all the infrastructure for them. Also fixes validation of the unnecessary heapType param in the text and binary formats in structs as well as arrays. Fixes printing of packed types in type names, which emitted i32 for them. That broke when we emitted the same name for an array of i8 and i32 as in the new testing here. Also fix a bug in Field::operator< which was wrong for packed types; again, this was easy to notice with the new testing.
* [GC] Add struct.new and start to test interesting execution (#3433)Alon Zakai2020-12-091-0/+7
| | | | | | | | | | | | | | With struct.new read/write support, we can start to do interesting things! This adds a test of creating a struct and seeing that references behave like references, that is, if we write to the value X refers to, and if Y refers to the same thing, when reading from Y's value we see the change as well. The test is run through all of -O1, which uncovered a minor issue in Precompute: We can't try to precompute a reference type, as we can't replace a reference with a value. Note btw that the test shows the optimizer properly running CoalesceLocals on reference types, merging two locals.
* [wasm-split] Read and use profiles (#3400)Thomas Lively2020-11-241-1/+1
| | | | | | Read the profiles produced by wasm-split's instrumentation to guide splitting. In this initial implementation, all functions that the profile shows to have been called are kept in the initial module. In the future, users may be able to tune this so that functions that are run later will still be split out.
* Fix pow2 util and avoid pow2 for left shifting in ZeroRemover (#3293)Max Graey2020-10-281-1/+1
| | | | | | | | Fixes a fuzz bug that was triggered by https://github.com/WebAssembly/binaryen/pull/3015#issuecomment-718001620 but was actually a pre-existing bug in pow2, that that PR just happened to uncover.
* Avoid UB in pow2 func (#3243)Max Graey2020-10-231-1/+1
|
* Optimize comparisons with 0/1 in boolean context (#3240)Max Graey2020-10-182-5/+13
| | | | | | | | | | i32(bool(x)) != 0 ==> i32(bool(x)) i64(bool(x)) & 1 ==> i64(bool(x)) Also: * clean up related matching rules in optimizeWithConstantOnRight * add more explanations about isPowerOf2Float & rename to isPowerOfTwoInvertibleFloat
* Fuzz fix for MemoryPacking on trampled data (#3222)Alon Zakai2020-10-151-0/+84
| | | | | | | | | | | | | I believe originally wasm did not allow overlapping segments, that is, where one memory segment tramples the data from a previous one. But then the spec changed its mind and we allowed it. Binaryen seems to have assumed the original case, and not checked for trampling. If there is a chance of trampling, we cannot optimize out zeros - the zero may have an effect if it tramples data from a previous segment. This does not occur in practice in LLVM output, which is why this wasn't a problem so far, I think. An existing testcase hit this issue, so I split it up.
* Optimize power of two float divisions (#3018)Max Graey2020-10-132-0/+27
|
* Simplify some numeric code (#3186)Max Graey2020-10-012-16/+4
|
* Clean up support/bits.h (#3177)Thomas Lively2020-09-303-64/+67
| | | | | 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.
* Implement more cases for getMaxBits (#2879)Max Graey2020-09-172-0/+14
| | | | | | | | | | | | | | | - 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
* Add 64-bit hash_combine (#3041)Daniel Wirtz2020-08-161-1/+9
| | | Currently only the low 32-bits of a hash are guaranteed to be shuffled before combining with the other hash, so this PR also adds a 64-bit variant of hash_combine, including a comment on where the constants are coming from.
* Refactor hashing (#3023)Daniel Wirtz2020-08-121-19/+14
| | | | | | | | | * 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.
* Fix CountLeadingZeroes on MSVC (#3028)Alon Zakai2020-08-061-2/+5
| | | | | | | We just had the logic there wrong - MSVC's intrinsic returns the bit index, not the number of leading zeros. That's identical when scanning forward but not in reverse... Fixes #2942
* Fix build for win32 (#3001)Max Graey2020-07-291-2/+2
| | | | | Check for x64 before using a non-32bit operation. See #2955 for context.
* Fix i32.trunc_f64_u of values that round down to UINT32_MAX (#2976)Alon Zakai2020-07-221-2/+2
|
* Fix i32.trunc_f64_s of values that round up to INT32_MIN (#2975)Alon Zakai2020-07-221-2/+2
| | | See WebAssembly/spec#1224
* Fix i32.trunc_f64_s of values near the limit of f64 representation (#2968)Alon Zakai2020-07-211-2/+2
| | | See WebAssembly/spec#1223
* Avoid __popcnt and __popcnt64 intrinsics for MSVC (#2944)Max Graey2020-07-061-8/+6
| | | | 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 efficient isInteger util (#2945)Max Graey2020-07-061-1/+1
|
* Optimize bit count polyfills (#2914)Max Graey2020-06-172-26/+75
|
* Add a non-const iterator to SmallVector (#2685)Thomas Lively2020-03-101-15/+22
| | | Using CRTP, yay!
* Initial multivalue support (#2675)Thomas Lively2020-03-051-0/+5
| | | | | | | | | 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
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-14 14:10:12 +0000