# Rules for Writing Optimization Rules

For both correctness and compile speed, we must be careful with our rules. A lot
of it boils down to the fact that, unlike traditional e-graphs, our rules are
*directional*.

1. Rules should not rewrite to worse code: the right-hand side should be at
   least as good as the left-hand side or better.

   For example, the rule

       x => (add x 0)

   is disallowed, but swapping its left- and right-hand sides produces a rule
   that is allowed.

   Any kind of canonicalizing rule that intends to help subsequent rules match
   and unlock further optimizations (e.g. floating constants to the right side
   for our constant-propagation rules to match) must produce canonicalized
   output that is no worse than its noncanonical input.

   We assume this invariant as a heuristic to break ties between two
   otherwise-equal-cost expressions in various places, making up for some
   limitations of our explicit cost function.

2. Any rule that removes value-uses in its right-hand side that previously
   existed in its left-hand side MUST use `subsume`.

   For example, the rule

       (select 1 x y) => x

   MUST use `subsume`.

   This is required for correctness because, once a value-use is removed, some
   e-nodes in the e-class are more equal than others. There might be uses of `x`
   in a scope where `y` is not available, and so emitting `(select 1 x y)` in
   place of `x` in such cases would introduce uses of `y` where it is not
   defined.

   An exception to this rule is discarding constants, as they can be
   rematerialized anywhere without introducing correctness issues. For example,
   the (admittedly silly) rule `(select 1 x (iconst_u _)) => x` would be a good
   candidate for not using `subsume`, as it does not discard any non-constant
   values introduced in its LHS.

3. Avoid overly general rewrites like commutativity and associativity. Instead,
   prefer targeted instances of the rewrite (for example, canonicalizing adds
   where one operand is a constant such that the constant is always the add's
   second operand, rather than general commutativity for adds) or even writing
   the "same" optimization rule multiple times.

   For example, the commutativity in the first rule in the following snippet is
   bad because it will match even when the first operand is not an add:

       ;; Commute to allow `(foo (add ...) x)`, when we see it, to match.
       (foo x y) => (foo y x)

       ;; Optimize.
       (foo x (add ...)) => (bar x)

   Better is to commute only when we know that canonicalizing in this way will
   all definitely allow the subsequent optimization rule to match:

       ;; Canonicalize all adds to `foo`'s second operand.
       (foo (add ...) x) => (foo x (add ...))

       ;; Optimize.
       (foo x (add ...)) => (bar x)

   But even better in this case is to write the "same" optimization multiple
   times:

       (foo (add ...) x) => (bar x)
       (foo x (add ...)) => (bar x)

   The cost of rule-matching is amortized by the ISLE compiler, where as the
   intermediate result of each rewrite allocates new e-nodes and requires
   storage in the dataflow graph. Therefore, additional rules are cheaper than
   additional e-nodes.

   Commutativity and associativity in particular can cause huge amounts of
   e-graph bloat.

   One day we intend to extend ISLE with built-in support for commutativity, so
   we don't need to author the redundant commutations ourselves:
   https://github.com/bytecodealliance/wasmtime/issues/6128

4. Be careful with (ideally avoid) multiple matches on the same `Value`, as
   they can result in surprising multi-matching behavior. Be skeptical of
   helpers that can inadvertently create this behavior.

   In our mid-end ISLE environment, a `Value` corresponds to an eclass, with
   multiple possible representations. A rule that matches on a `Value` will
   traverse all enodes in the eclass, looking for a match. This is usually
   exactly what we want: it is what allows a pattern like `(iadd (iconst k) x)`
   to find the `iconst` amongst multiple possibilities for the argument.

   However, this can also result in surprising behavior. If one has a helper
   and a simplify rule like

       (decl suitable_for_rewrite (Value) Value)
       (rule (suitable_for_rewrite x @ (iadd ...)) x)
       (rule (suitable_for_rewrite x @ (isub ...)) x)

       (rule (simplify (ireduce _ x))
         (if-let _ (suitable_for_rewrite x))
         x)

    Then this can result in the extremely surprising behavior that `(ireduce
    (other_op ...))` matches, if `(other_op ...)` is in the same eclass as an
    `iadd` or `isub`. This happens because the left-hand side binds `x`, which
    describes the entire eclass; and `suitable_for_rewrite` matches if *any*
    representation of `x` matches.

    This resulted in a real bug in #7999. The best guidance is to keep rules
    simple and direct: rather than attempting to abstract out helpers and
    perform multiple, separate, matches on a `Value`, write patterns directly.
    This has the additional benefit that the rewrites are more clearly visible
    to the casual reader. For example:

        (rule (simplify (ireduce _ (iadd ...)))
              (iadd ...))
        (rule (simplify (ireduce _ (isub ...)))
              (isub ...))