Bongjun Jang (Nov 23 2025 at 10:33): Bongjun Jang (Nov 23 2025 at 10:33):Hi, reading mid-end optimizations in ISLE, I noticed that these rules increase cost which defined in https://github.com/bytecodealliance/wasmtime/blob/68a6afd4f925724fd359c13a27fac5a6163d12f4/cranelift/codegen/src/egraph/cost.rs#L111-L132.
Is there a rationale why such rules exist? I think this is opposed to the first rule writing mid-end opts in ISLE stated at https://github.com/bytecodealliance/wasmtime/blob/68a6afd4f925724fd359c13a27fac5a6163d12f4/cranelift/codegen/src/opts/README.md
Chris Fallin (Nov 23 2025 at 19:42):The first rule there is a guideline, but not a hard rule (the system doesn't depend on always-reducing cost as an invariant). In the specific case you linked, it is a kind of normalization: the idea is that we want to simplify possibly deeply nested bit-op expressions and the way we do that is by "pushing NOTs down the tree" to the leaves
Bongjun Jang (Nov 24 2025 at 06:30):thanks for the reply. normalization (constant operand to right, etc) can help improve the execution performance in general, but how does "pushing NOTs down the tree" improve performance? Is there any possibility or evidence that it can lead to better codegen/optimization opportunity for this case?
Jacob Lifshay (Nov 24 2025 at 09:11):afaik the general idea of e-graphs (what ISLE is mostly used for) is that it generates a bunch of different equivalent expressions for your code and then picks the least expensive one, so some of the expression transformations may make it more expensive only for later optimizations to make it even less expensive.
e.g. if you're optimizing ((a == b) & !c) & !d, just doing the de-morgan rule once would give you !(!((a == b) & !c) | !!d) which is a bit more expensive, but that can be further optimized to !((a != b) | c) | d which has one less instruction than the original expression.
Chris Fallin (Nov 24 2025 at 23:56):Yes, and in general, pushing boolean expressions toward a normal form allows expressions to GVN together more. I don't have ready examples or data for that, but it's a general compilers-transformation principle. I would consider these rules part of the same family as the push-constants-to-the-right-and-reassociate rules that let cprop work better.
Chris Fallin (Nov 24 2025 at 23:57):(Note to researchers: getting data on how individual rules, and combinations of rules together, bring optimization benefit -- i.e., somehow finding a way to attribute "credit" to rules -- would be really neat and a way to talk about all this more objectively)
Bongjun Jang (Nov 25 2025 at 07:50):Hi, I uploaded performance evaluation data of removing the rules in wasmtime Github: https://github.com/bytecodealliance/wasmtime/issues/12086
Last updated: Dec 06 2025 at 07:03 UTC