summaryrefslogtreecommitdiff
path: root/test/lit/passes/coalesce-locals-learning.wast
Commit message (Collapse)AuthorAgeFilesLines
* Update lit tests to parse with the new parser (#6290)Thomas Lively2024-02-081-1/+4
| | | | | | | | | Get as many of the lit tests as possible to parse with the new parser, mostly by moving declared module items to be after imports. Also fix a bug in the new parser's pop validation to allow supertypes of the expected type. The two big issues that still prevent some lit tests from working correctly under the new parser are missing support for symbolic field names and missing support for source map annotations.
* Fix incorrect wat in tests (#6207)Thomas Lively2024-01-081-2/+1
| | | | | | | | | The new wat parser is much more strict than the legacy wat parser; the latter accepts all sorts of things that the spec does not allow. To ease an eventual transition to using the new wat parser by default, update the tests to use the standard text format in many places where they previously did not. We do not yet have a way to prevent new errors from being introduced into the test suite, but at least there will now be many fewer errors when it comes time to make the switch.
* Require `then` and `else` with `if` (#6201)Thomas Lively2024-01-041-606/+782
| | | | | | | | | | | | We previously supported (and primarily used) a non-standard text format for conditionals in which the condition, if-true expression, and if-false expression were all simply s-expression children of the `if` expression. The standard text format, however, requires the use of `then` and `else` forms to introduce the if-true and if-false arms of the conditional. Update the legacy text parser to require the standard format and update all tests to match. Update the printer to print the standard format as well. The .wast and .wat test inputs were mechanically updated with this script: https://gist.github.com/tlively/85ae7f01f92f772241ec994c840ccbb1
* Fix name of port_passes_tests_to_lit.py script. NFC (#4902)Sam Clegg2022-08-121-1/+1
| | | I was reading these tests and failing to find the names script.
* CoalesceLocals: Use ValueNumbering (#4355)Alon Zakai2021-11-241-10/+10
| | | | | | | | | | | | This removes the old hardcoded value numbering in that pass and makes it use the new code that was split into helper code. The immediate benefit of this is to make the code aware of identical constants: if two locals have the same constant then they do not interfere. Future improvements to numbering will also automatically help here. This changes some constants in existing tests so that they keep testing what they were testing before, and adds new tests for the new benefit here. This implements a proposed TODO from #4314
* CoalesceLocals: Rewrite the algorithm to be linear and to ignore copies (#4314)Alon Zakai2021-11-101-19/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The old algorithm can be summarized as: In each basic block, start at the beginning. Each pair of live locals there might interfere with each other, as they might arrive from different entry blocks with different values. Afterwards, go through the block and find overlapping live ranges, and mark interferences there as well. This is non-linear because at the start of the block we do a double-loop over all pairs of live locals, which in general can be O(N^2) (N - number of locals). It also has the downside of ignoring copies: if two locals have overlapping live ranges but they must have identical values on those ranges, they do not actually interfere, for example x = 10; y = x; .. // live ranges overlap here foo(x, y); // live ranges end here. We can ignore this overlap since the copy shows they are identical there, but the pass did not take this into account. To some extent other passes can remove such copies (SimplifyLocals, MergeLocals, RedundantSetElimination), but in general this was a weak spot for the optimizer. I realized there is a solution to both these problems: In Wasm, given that we have a default value for all locals, if a local is live at the start of a block then it must be live at the end of all the blocks reaching it. That is so because the liveness will extend backwards all the way to some set of the local, possibly all the way to the zero-initialization at the start of the function, and it extends that way through all predecessor blocks. A consequence of this is that there are no interferences between locals that only occur during a merge: The live ranges include the predecessor blocks, and theirs, and so forth, until we reach a block where one of the locals is assigned a value different than the other. That is a necessary and sufficient condition for intererence, and therefore when processing a block we only need to look at its contents, and can ignore the merging of control flow, which allows us to be linear. More details on this and on the new algorithm in comments in the source, but the basic idea is that it simply goes through each block in a linear way, finding which values are assigned to each local (using a numbering of unique values), and noting which are live at each time. If two locals are live and one is assigned a value that is not the same as the value in the other, mark them as interfering. This is of substantial benefit to j2wasm output, I believe because it is common there to find local subexpression elimination opportunities after inlining, and each time we find one we add a local. If we inline different functions into the same target, we may end up with copied locals for each of them. (This was not noticed in the past because it is very rare on LLVM output, which has already had inlining and GVN etc. done.) There is a small benefit to LLVM output as well, though just a few percent at best. However, it is enough to be noticeable on some of the code size tests. This is also faster than the previous pass. It's normally not noticeable as this pass is not one of the slowest anyhow, but I found some real-world codebases where the pass becomes 50% faster. I have not found any case where it is slower than the old algorithm. Fuzzed over several days to be sure this is correct, and also verified on the emscripten test suite.
* Port test/passes/c* to lit (#3988)Thomas Lively2021-07-151-0/+1766