1;; Rewrites for `band`, `bnot`, `bor`, `bxor`
2
3;; x | 0 == x | x == x.
4(rule (simplify (bor ty
5                     x
6                     (iconst ty (u64_from_imm64 0))))
7      (subsume x))
8(rule (simplify (bor ty x x))
9      (subsume x))
10
11;; x ^ 0 == x.
12(rule (simplify (bxor ty
13                     x
14                     (iconst ty (u64_from_imm64 0))))
15      (subsume x))
16
17;; x ^ x == 0.
18(rule (simplify (bxor (fits_in_64 (ty_int ty)) x x))
19      (subsume (iconst ty (imm64 0))))
20
21;; x ^ not(x) == not(x) ^ x == x | not(x) == not(x) | x == -1.
22;; This identity also holds for non-integer types, vectors, and wider types.
23;; But `iconst` is only valid for integers up to 64 bits wide.
24(rule (simplify (bxor (fits_in_64 (ty_int ty)) x (bnot ty x))) (subsume (iconst ty (imm64 (ty_mask ty)))))
25(rule (simplify (bxor (fits_in_64 (ty_int ty)) (bnot ty x) x)) (subsume (iconst ty (imm64 (ty_mask ty)))))
26(rule (simplify (bor (fits_in_64 (ty_int ty)) x (bnot ty x))) (subsume (iconst ty (imm64 (ty_mask ty)))))
27(rule (simplify (bor (fits_in_64 (ty_int ty)) (bnot ty x) x)) (subsume (iconst ty (imm64 (ty_mask ty)))))
28
29;; x & x == x & -1 == x.
30(rule (simplify (band ty x x)) (subsume x))
31(rule (simplify (band ty x (iconst ty k)))
32      (if-let -1 (i64_sextend_imm64 ty k))
33      (subsume x))
34
35;; x & 0 == x & not(x) == not(x) & x == 0.
36(rule (simplify (band ty _ zero @ (iconst ty (u64_from_imm64 0)))) (subsume zero))
37(rule (simplify (band (fits_in_64 (ty_int ty)) x (bnot ty x))) (subsume (iconst ty (imm64 0))))
38(rule (simplify (band (fits_in_64 (ty_int ty)) (bnot ty x) x)) (subsume (iconst ty (imm64 0))))
39
40;; not(not(x)) == x.
41(rule (simplify (bnot ty (bnot ty x))) (subsume x))
42
43;; DeMorgan's rule (two versions):
44;; bnot(bor(x, y)) == band(bnot(x), bnot(y))
45(rule (simplify (bnot ty (bor ty x y)))
46      (band ty (bnot ty x) (bnot ty y)))
47;; bnot(band(x, y)) == bor(bnot(x), bnot(y))
48(rule (simplify (bnot ty (band t x y)))
49      (bor ty (bnot ty x) (bnot ty y)))
50
51;; `or(and(x, y), not(y)) == or(x, not(y))`
52(rule (simplify (bor ty
53                     (band ty x y)
54                     z @ (bnot ty y)))
55      (bor ty x z))
56;; Duplicate the rule but swap the `bor` operands because `bor` is
57;; commutative. We could, of course, add a `simplify` rule to do the commutative
58;; swap for all `bor`s but this will bloat the e-graph with many e-nodes. It is
59;; cheaper to have additional rules, rather than additional e-nodes, because we
60;; amortize their cost via ISLE's smart codegen.
61(rule (simplify (bor ty
62                     z @ (bnot ty y)
63                     (band ty x y)))
64      (bor ty x z))
65
66;; `or(and(x, y), not(y)) == or(x, not(y))` specialized for constants, since
67;; otherwise we may not know that `z == not(y)` since we don't generally expand
68;; constants in the e-graph.
69;;
70;; (No need to duplicate for commutative `bor` for this constant version because
71;; we move constants to the right.)
72(rule (simplify (bor ty
73                     (band ty x (iconst ty (u64_from_imm64 y)))
74                     z @ (iconst ty (u64_from_imm64 zk))))
75      (if-let $true (u64_eq (u64_and (ty_mask ty) zk)
76                            (u64_and (ty_mask ty) (u64_not y))))
77      (bor ty x z))
78
79;; (x ^ -1) can be replaced with the `bnot` instruction
80(rule (simplify (bxor ty x (iconst ty k)))
81  (if-let -1 (i64_sextend_imm64 ty k))
82  (bnot ty x))
83
84;; sshr((x | -x), N) == bmask(x) where N = ty_bits(ty) - 1.
85;;
86;; (x | -x) sets the sign bit to 1 if x is nonzero, and 0 if x is zero. sshr propagates
87;; the sign bit to the rest of the value.
88(rule (simplify (sshr ty (bor ty x (ineg ty x)) (iconst ty (u64_from_imm64 shift_amt))))
89      (if-let $true (u64_eq shift_amt (ty_shift_mask ty)))
90      (bmask ty x))
91
92(rule (simplify (sshr ty (bor ty (ineg ty x) x) (iconst ty (u64_from_imm64 shift_amt))))
93      (if-let $true (u64_eq shift_amt (ty_shift_mask ty)))
94      (bmask ty x))
95
96;; Matches any expressions that preserve "truthiness".
97;; i.e. If the input is zero it remains zero, and if it is nonzero it can have
98;; a different value as long as it is still nonzero.
99(decl pure multi truthy (Value) Value)
100(rule (truthy (sextend _ x)) x)
101(rule (truthy (uextend _ x)) x)
102(rule (truthy (bmask _ x)) x)
103(rule (truthy (ineg _ x)) x)
104(rule (truthy (bswap _ x)) x)
105(rule (truthy (bitrev _ x)) x)
106(rule (truthy (popcnt _ x)) x)
107(rule (truthy (rotl _ x _)) x)
108(rule (truthy (rotr _ x _)) x)
109(rule (truthy (select _ x (iconst _ (u64_from_imm64 (u64_nonzero _))) (iconst _ (u64_from_imm64 0)))) x)
110;; (ne ty (iconst 0) v) is also canonicalized into this form via another rule
111(rule (truthy (ne _ x (iconst _ (u64_from_imm64 0)))) x)
112
113;; All of these expressions don't care about their input as long as it is truthy.
114;; so we can remove expressions that preserve that property from the input.
115(rule (simplify (bmask ty v)) (if-let x (truthy v)) (bmask ty x))
116(rule (simplify (select ty v t f)) (if-let c (truthy v)) (select ty c t f))
117;; (ne ty (iconst 0) v) is also canonicalized into this form via another rule
118(rule (simplify (ne cty v (iconst _ (u64_from_imm64 0))))
119      (if-let c (truthy v))
120      (if-let (value_type (ty_int_ref_scalar_64 ty)) c)
121      (ne cty c (iconst ty (imm64 0))))
122
123
124
125;; (sextend (bmask x)) can be replaced with (bmask x) since bmask
126;; supports any size of output type, regardless of input.
127;; Same with `ireduce`
128(rule (simplify (sextend ty (bmask _ x))) (bmask ty x))
129(rule (simplify (ireduce ty (bmask _ x))) (bmask ty x))
130
131;; (bswap (bswap x)) == x
132(rule (simplify (bswap ty (bswap ty x))) (subsume x))
133
134;; (bitrev (bitrev x)) == x
135(rule (simplify (bitrev ty (bitrev ty x))) (subsume x))
136
137;; WebAssembly doesn't have a native byte-swapping instruction at this time so
138;; languages which have a byte-swapping operation will compile it down to bit
139;; shifting and twiddling. This attempts to pattern match what LLVM currently
140;; generates today for the Rust code `a.swap_bytes()`. This might be a bit
141;; brittle over time and/or with other possible LLVM backend optimizations, but
142;; it's at least one way to generate a byte swap.
143;;
144;; Technically this could be permuted quite a few ways and currently there's no
145;; easy way to match all of them, so only one is matched here.
146(rule (simplify (bor ty @ $I32
147    (bor ty
148      (ishl ty x (iconst ty (u64_from_imm64 24)))
149      (ishl ty
150        (band ty x (iconst ty (u64_from_imm64 0xff00)))
151        (iconst ty (u64_from_imm64 8))))
152    (bor ty
153      (band ty
154        (ushr ty x (iconst ty (u64_from_imm64 8)))
155        (iconst ty (u64_from_imm64 0xff00)))
156      (ushr ty x (iconst ty (u64_from_imm64 24))))))
157  (bswap ty x))
158
159(rule (simplify (bor ty @ $I64
160    (bor ty
161      (bor ty
162        (ishl ty x (iconst ty (u64_from_imm64 56)))
163        (ishl ty
164          (band ty x (iconst ty (u64_from_imm64 0xff00)))
165          (iconst ty (u64_from_imm64 40))))
166      (bor ty
167        (ishl ty
168          (band ty x (iconst ty (u64_from_imm64 0xff_0000)))
169          (iconst ty (u64_from_imm64 24)))
170        (ishl ty
171          (band ty x (iconst ty (u64_from_imm64 0xff00_0000)))
172          (iconst ty (u64_from_imm64 8)))))
173    (bor ty
174      (bor ty
175        (band ty
176          (ushr ty x (iconst ty (u64_from_imm64 8)))
177          (iconst ty (u64_from_imm64 0xff00_0000)))
178        (band ty
179          (ushr ty x (iconst ty (u64_from_imm64 24)))
180          (iconst ty (u64_from_imm64 0xff_0000))))
181      (bor ty
182        (band ty
183          (ushr ty x (iconst ty (u64_from_imm64 40)))
184          (iconst ty (u64_from_imm64 0xff00)))
185        (ushr ty x (iconst ty (u64_from_imm64 56)))))))
186  (bswap ty x))
187