1# Rules for Writing Optimization Rules
2
3For both correctness and compile speed, we must be careful with our rules. A lot
4of it boils down to the fact that, unlike traditional e-graphs, our rules are
5*directional*.
6
71. Rules should not rewrite to worse code: the right-hand side should be at
8   least as good as the left-hand side or better.
9
10   For example, the rule
11
12       x => (add x 0)
13
14   is disallowed, but swapping its left- and right-hand sides produces a rule
15   that is allowed.
16
17   Any kind of canonicalizing rule that intends to help subsequent rules match
18   and unlock further optimizations (e.g. floating constants to the right side
19   for our constant-propagation rules to match) must produce canonicalized
20   output that is no worse than its noncanonical input.
21
22   We assume this invariant as a heuristic to break ties between two
23   otherwise-equal-cost expressions in various places, making up for some
24   limitations of our explicit cost function.
25
262. Any rule that removes value-uses in its right-hand side that previously
27   existed in its left-hand side MUST use `subsume`.
28
29   For example, the rule
30
31       (select 1 x y) => x
32
33   MUST use `subsume`.
34
35   This is required for correctness because, once a value-use is removed, some
36   e-nodes in the e-class are more equal than others. There might be uses of `x`
37   in a scope where `y` is not available, and so emitting `(select 1 x y)` in
38   place of `x` in such cases would introduce uses of `y` where it is not
39   defined.
40
41   An exception to this rule is discarding constants, as they can be
42   rematerialized anywhere without introducing correctness issues. For example,
43   the (admittedly silly) rule `(select 1 x (iconst_u _)) => x` would be a good
44   candidate for not using `subsume`, as it does not discard any non-constant
45   values introduced in its LHS.
46
473. Avoid overly general rewrites like commutativity and associativity. Instead,
48   prefer targeted instances of the rewrite (for example, canonicalizing adds
49   where one operand is a constant such that the constant is always the add's
50   second operand, rather than general commutativity for adds) or even writing
51   the "same" optimization rule multiple times.
52
53   For example, the commutativity in the first rule in the following snippet is
54   bad because it will match even when the first operand is not an add:
55
56       ;; Commute to allow `(foo (add ...) x)`, when we see it, to match.
57       (foo x y) => (foo y x)
58
59       ;; Optimize.
60       (foo x (add ...)) => (bar x)
61
62   Better is to commute only when we know that canonicalizing in this way will
63   all definitely allow the subsequent optimization rule to match:
64
65       ;; Canonicalize all adds to `foo`'s second operand.
66       (foo (add ...) x) => (foo x (add ...))
67
68       ;; Optimize.
69       (foo x (add ...)) => (bar x)
70
71   But even better in this case is to write the "same" optimization multiple
72   times:
73
74       (foo (add ...) x) => (bar x)
75       (foo x (add ...)) => (bar x)
76
77   The cost of rule-matching is amortized by the ISLE compiler, where as the
78   intermediate result of each rewrite allocates new e-nodes and requires
79   storage in the dataflow graph. Therefore, additional rules are cheaper than
80   additional e-nodes.
81
82   Commutativity and associativity in particular can cause huge amounts of
83   e-graph bloat.
84
85   One day we intend to extend ISLE with built-in support for commutativity, so
86   we don't need to author the redundant commutations ourselves:
87   https://github.com/bytecodealliance/wasmtime/issues/6128
88
894. Be careful with (ideally avoid) multiple matches on the same `Value`, as
90   they can result in surprising multi-matching behavior. Be skeptical of
91   helpers that can inadvertently create this behavior.
92
93   In our mid-end ISLE environment, a `Value` corresponds to an eclass, with
94   multiple possible representations. A rule that matches on a `Value` will
95   traverse all enodes in the eclass, looking for a match. This is usually
96   exactly what we want: it is what allows a pattern like `(iadd (iconst k) x)`
97   to find the `iconst` amongst multiple possibilities for the argument.
98
99   However, this can also result in surprising behavior. If one has a helper
100   and a simplify rule like
101
102       (decl suitable_for_rewrite (Value) Value)
103       (rule (suitable_for_rewrite x @ (iadd ...)) x)
104       (rule (suitable_for_rewrite x @ (isub ...)) x)
105
106       (rule (simplify (ireduce _ x))
107         (if-let _ (suitable_for_rewrite x))
108         x)
109
110    Then this can result in the extremely surprising behavior that `(ireduce
111    (other_op ...))` matches, if `(other_op ...)` is in the same eclass as an
112    `iadd` or `isub`. This happens because the left-hand side binds `x`, which
113    describes the entire eclass; and `suitable_for_rewrite` matches if *any*
114    representation of `x` matches.
115
116    This resulted in a real bug in #7999. The best guidance is to keep rules
117    simple and direct: rather than attempting to abstract out helpers and
118    perform multiple, separate, matches on a `Value`, write patterns directly.
119    This has the additional benefit that the rewrites are more clearly visible
120    to the casual reader. For example:
121
122        (rule (simplify (ireduce _ (iadd ...)))
123              (iadd ...))
124        (rule (simplify (ireduce _ (isub ...)))
125              (isub ...))
126