Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization #10988
Conversation
Note: the test expectation change in `filetests/egraph/misc.clif` is simply because we happen to change the order in which we created the legalized `stack_addr` instructions that get GVN'd together, and therefore also changed their relative value numbering. We dedupe to the value that occurs first in the function, which is the one inserted into the DFG *after* the other now because of the backwards traversal, and it therefore has a different value number from before. The resulting program is identical, modulo value numbering.
…onditional traps during legalization Given this instruction: ```clif brif v0, block1, block2 ``` If we know that `block1` does nothing but immediately trap then we can rewrite that `brif` into the following: ```clif trapz v0, <trapcode> jump block2 ``` (And we can do the equivalent with `trapz` if `block2` immediately traps). This transformation allows for the conditional trap instructions to be GVN'd and for our egraphs mid-end to generally better optimize the program. We additionally have better codegen in our backends for `trapz` than branches to unconditional traps. Fixes bytecodealliance#10941
|
Could you detail more why this is part of legalization and not a separate function/pass? It seems a bit odd to me to have this be intertwined with legalization as it's basically not realized to legalization at all and is more of an optimization pass. Was it a compile-speed-related concern? Also, do you know why so many tests are changing? Is it also due to the nature of the first commit where it's switching to a backwards walk from a forwards walk which renumbers legalization-produced things which GVN might pick differently between now?
FWIW with |
Yes, I did not want to introduce another IR traversal, and would consider that a non-starter for solving this issue. We have in general been trying to remove passes (eg we've talked a lot about how to fuse phi-removal into the egraph pass) rather than add them. You can think of legalization as a type of canonicalization, and this PR is canonicalizing conditional-branch-to-unconditional-trap into conditional-trap, if that helps.
Yes, GVN is a forwards pass will choose the first value it sees as the canonical version. This used to be the legalized value with the lowest number because legalization was also a forwards pass so values at the start of the function would be legalized before those at the end. After the change to legalize in reverse, the legalized values at the end of the function are lower and at the start of the function are higher. So even if the IR is the "same" except for value numbers, the value numbers do change in the golden output.
We don't mark any Wasm blocks |
Given this instruction:
If we know that
block1does nothing but immediately trap then we can rewritethat
brifinto the following:(And we can do the equivalent with
trapzifblock2immediately traps).This transformation allows for the conditional trap instructions to be GVN'd and
for our egraphs mid-end to generally better optimize the program. We
additionally have better codegen in our backends for
trapzthan branches tounconditional traps.
Fixes #10941