1;; rewrites for integer and floating-point arithmetic
2;; eg: `iadd`, `isub`, `ineg`, `imul`, `fadd`, `fsub`, `fmul`
3
4;; For commutative instructions, we depend on cprop.isle pushing immediates to
5;; the right, and thus only simplify patterns like `x+0`, not `0+x`.
6
7;; x+0 == x.
8(rule (simplify (iadd ty
9                      x
10                      (iconst_u ty 0)))
11      (subsume x))
12;; x-0 == x.
13(rule (simplify (isub ty
14                      x
15                      (iconst_u ty 0)))
16      (subsume x))
17;; 0-x == (ineg x).
18(rule (simplify (isub ty
19                      (iconst_u ty 0)
20                      x))
21      (ineg ty x))
22
23;; x + -y == -y + x == -(y - x) == x - y
24(rule (simplify (iadd ty x (ineg ty y)))
25      (isub ty x y))
26(rule (simplify (iadd ty (ineg ty y) x))
27      (isub ty x y))
28(rule (simplify (ineg ty (isub ty y x)))
29      (isub ty x y))
30;; x - -y == x + y
31(rule (simplify (isub ty x (ineg ty y)))
32      (iadd ty x y))
33
34;; ineg(ineg(x)) == x.
35(rule (simplify (ineg ty (ineg ty x))) (subsume x))
36
37;; ineg(x) * ineg(y) == x*y.
38(rule (simplify (imul ty (ineg ty x) (ineg ty y)))
39      (subsume (imul ty x y)))
40
41;; iabs(ineg(x)) == iabs(x).
42(rule (simplify (iabs ty (ineg ty x)))
43      (iabs ty x))
44
45;; iabs(iabs(x)) == iabs(x).
46(rule (simplify (iabs ty inner @ (iabs ty x)))
47      (subsume inner))
48
49;; x-x == 0.
50(rule (simplify (isub (ty_int ty) x x)) (subsume (iconst_u ty 0)))
51
52;; x*1 == x.
53(rule (simplify (imul ty
54                      x
55                      (iconst_u ty 1)))
56      (subsume x))
57
58;; x*0 == 0.
59(rule (simplify (imul ty
60                      _
61                      zero @ (iconst_u ty 0)))
62      (subsume zero))
63
64;; x*-1 == ineg(x).
65(rule (simplify (imul ty x (iconst_s ty -1)))
66      (ineg ty x))
67
68;; (!x) + 1 == ineg(x)
69(rule (simplify (iadd ty (bnot ty x) (iconst_u ty 1)))
70      (ineg ty x))
71
72;; !(x - 1) == !(x + (-1)) == ineg(x)
73(rule (simplify (bnot ty (isub ty x (iconst_s ty 1))))
74      (ineg ty x))
75(rule (simplify (bnot ty (iadd ty x (iconst_s ty -1))))
76      (ineg ty x))
77
78;; x / 1 == x.
79(rule (simplify_skeleton (sdiv x (iconst_s ty 1))) x)
80(rule (simplify_skeleton (udiv x (iconst_u ty 1))) x)
81
82;; Unsigned `x / d == x >> ilog2(d)` when d is a power of two.
83(rule (simplify_skeleton (udiv x (iconst_u ty (u64_extract_power_of_two d))))
84      (ushr ty x (iconst_u ty (u64_ilog2 d))))
85
86;; Signed `x / d` when d is a power of two is a bit more involved...
87(rule (simplify_skeleton (sdiv x (iconst_u ty (u64_extract_power_of_two d))))
88      (if-let true (u64_gt d 1))
89      (let ((k u32 (u64_trailing_zeros d))
90            (t1 Value (sshr ty x (iconst_u ty (u32_sub k 1))))
91            (t2 Value (ushr ty t1 (iconst_u ty (u32_sub (ty_bits ty) k))))
92            (t3 Value (iadd ty x t2))
93            (t4 Value (sshr ty t3 (iconst_s ty k))))
94        t4))
95
96;; And signed `x / d` when d is a negative power of two is the same, but with a
97;; negation.
98(rule (simplify_skeleton (sdiv x (iconst_s ty d)))
99      (if-let true (i64_is_negative_power_of_two d))
100      (if-let true (i64_ne d -1))
101      (let ((k u32 (i64_trailing_zeros d))
102            (t1 Value (sshr ty x (iconst_u ty (u32_sub k 1))))
103            (t2 Value (ushr ty t1 (iconst_u ty (u32_sub (ty_bits ty) k))))
104            (t3 Value (iadd ty x t2))
105            (t4 Value (sshr ty t3 (iconst_s ty k)))
106            (t5 Value (ineg ty t4)))
107        t5))
108
109;; General cases for `udiv` with constant divisors.
110(rule (simplify_skeleton (udiv x (iconst_u $I32 (u64_extract_non_zero (u32_from_u64 d)))))
111      (if-let false (u32_is_power_of_two d))
112      (apply_div_const_magic_u32 (Opcode.Udiv) x d))
113(rule (simplify_skeleton (udiv x (iconst_u $I64 (u64_extract_non_zero d))))
114      (if-let false (u64_is_power_of_two d))
115      (apply_div_const_magic_u64 (Opcode.Udiv) x d))
116
117;; General cases for `sdiv` with constant divisors.
118(rule (simplify_skeleton (sdiv x (iconst_s $I32 (i64_extract_non_zero (i32_from_i64 d)))))
119      (if-let false (i64_is_any_sign_power_of_two d))
120      (apply_div_const_magic_s32 (Opcode.Sdiv) x d))
121(rule (simplify_skeleton (sdiv x (iconst_s $I64 (i64_extract_non_zero d))))
122      (if-let false (i64_is_any_sign_power_of_two d))
123      (apply_div_const_magic_s64 (Opcode.Sdiv) x d))
124
125;; x % 1 == 0
126(rule (simplify_skeleton (urem x (iconst_u ty 1))) (iconst_u ty 0))
127(rule (simplify_skeleton (srem x (iconst_u ty 1))) (iconst_u ty 0))
128(rule (simplify_skeleton (srem x (iconst_s ty -1))) (iconst_u ty 0))
129
130;; Unsigned `x % d == x & ((1 << ilog2(d)) - 1)` when `d` is a power of two.
131(rule (simplify_skeleton (urem x (iconst_u ty (u64_extract_power_of_two d))))
132      (if-let true (u64_gt d 1))
133      (let ((mask Value (iconst_u ty (u64_sub (u64_shl 1 (u64_ilog2 d)) 1))))
134        (band ty x mask)))
135
136;; Signed `x % d` when `d` is a (possibly negative) power of two is a little
137;; more complicated.
138(rule (simplify_skeleton (srem x d_val @ (iconst_s ty d)))
139      ;; Interestingly, this same sequence works for both positive and negative
140      ;; powers of two.
141      (if-let true (i64_is_any_sign_power_of_two d))
142      (if-let true (i64_ne d 1))
143      (if-let true (i64_ne d -1))
144      (let ((k u32 (i64_trailing_zeros d))
145            (t1 Value (sshr ty x (iconst_u ty (u32_sub k 1))))
146            (t2 Value (ushr ty t1 (iconst_u ty (u32_sub (ty_bits ty) k))))
147            (t3 Value (iadd ty x t2))
148            (t4 Value (band ty t3 (iconst_s ty (i64_wrapping_neg (i64_shl 1 k)))))
149            (t5 Value (isub ty x t4)))
150        t5))
151
152;; General cases for `urem` with constant divisors.
153(rule (simplify_skeleton (urem x (iconst_u $I32 (u64_extract_non_zero (u32_from_u64 d)))))
154      (if-let false (u32_is_power_of_two d))
155      (apply_div_const_magic_u32 (Opcode.Urem) x d))
156(rule (simplify_skeleton (urem x (iconst_u $I64 (u64_extract_non_zero d))))
157      (if-let false (u64_is_power_of_two d))
158      (apply_div_const_magic_u64 (Opcode.Urem) x d))
159
160;; General cases for `srem` with constant divisors.
161(rule (simplify_skeleton (srem x (iconst_s $I32 (i64_extract_non_zero (i32_from_i64 d)))))
162      (if-let false (i64_is_any_sign_power_of_two d))
163      (apply_div_const_magic_s32 (Opcode.Srem) x d))
164(rule (simplify_skeleton (srem x (iconst_s $I64 (i64_extract_non_zero d))))
165      (if-let false (i64_is_any_sign_power_of_two d))
166      (apply_div_const_magic_s64 (Opcode.Srem) x d))
167
168;; x*2 == x+x.
169(rule (simplify (imul ty x (iconst_u _ 2)))
170      (iadd ty x x))
171
172;; x*c == x<<log2(c) when c is a power of two.
173;;
174;; Note that the type of `iconst` must be the same as the type of `imul`,
175;; so these rules can only fire in situations where it's safe to construct an
176;; `iconst` of that type.
177(rule (simplify (imul ty x (iconst _ (imm64_power_of_two c))))
178      (ishl ty x (iconst ty (imm64 c))))
179(rule (simplify (imul ty (iconst _ (imm64_power_of_two c)) x))
180      (ishl ty x (iconst ty (imm64 c))))
181
182;; fneg(fneg(x)) == x.
183(rule (simplify (fneg ty (fneg ty x))) (subsume x))
184
185;; If both of the multiplied arguments to an `fma` are negated then remove
186;; both of them since they cancel out.
187(rule (simplify (fma ty (fneg ty x) (fneg ty y) z))
188      (fma ty x y z))
189
190;; If both of the multiplied arguments to an `fmul` are negated then remove
191;; both of them since they cancel out.
192(rule (simplify (fmul ty (fneg ty x) (fneg ty y)))
193      (fmul ty x y))
194
195;; (a op (b op (c op d))) ==> ((a op b) op (c op d))
196;;
197;; and
198;;
199;; (((a op b) op c) op d) ==> ((a op b) op (c op d))
200;;
201;; where `op` is an associative operation: `iadd`, `imul`, `band`, or `bxor`.
202;;
203;; This increases instruction-level parallelism and shrinks live ranges. It also
204;; canonicalizes into the shallow-and-wide form for reassociating constants
205;; together for cprop.
206;;
207;; NB: We subsume to avoid exponential e-node blow up due to reassociating very
208;; large chains of operations.
209;;
210;; TODO: We should add `bor` rules for this as well. Unfortunately, they
211;; conflict with our `bswap` recognizing rules when we `subsume`.
212
213(rule (simplify (iadd ty a (iadd ty b (iadd ty c d))))
214      (subsume (iadd ty (iadd ty a b) (iadd ty c d))))
215(rule (simplify (iadd ty (iadd ty (iadd ty a b) c) d))
216      (subsume (iadd ty (iadd ty a b) (iadd ty c d))))
217
218(rule (simplify (imul ty a (imul ty b (imul ty c d))))
219      (subsume (imul ty (imul ty a b) (imul ty c d))))
220(rule (simplify (imul ty (imul ty (imul ty a b) c) d))
221      (subsume (imul ty (imul ty a b) (imul ty c d))))
222
223(rule (simplify (band ty a (band ty b (band ty c d))))
224      (subsume (band ty (band ty a b) (band ty c d))))
225(rule (simplify (band ty (band ty (band ty a b) c) d))
226      (subsume (band ty (band ty a b) (band ty c d))))
227
228(rule (simplify (bxor ty a (bxor ty b (bxor ty c d))))
229      (subsume (bxor ty (bxor ty a b) (bxor ty c d))))
230(rule (simplify (bxor ty (bxor ty (bxor ty a b) c) d))
231      (subsume (bxor ty (bxor ty a b) (bxor ty c d))))
232
233
234;; Similar rules but for associating combinations of + and -
235
236;; a -(b-(c-d)) = (a-b) + (c-d)
237(rule (simplify (isub ty a (isub ty b (isub ty c d))))
238      (subsume (iadd ty (isub ty a b) (isub ty c d))))
239
240;; a -(b-(c+d)) = (a-b) + (c+d)
241(rule (simplify (isub ty a (isub ty b (iadd ty c d))))
242      (subsume (iadd ty (isub ty a b) (iadd ty c d))))
243
244;; a -(b+(c-d)) = (a-b) - (c-d)
245(rule (simplify (isub ty a (iadd ty b (isub ty c d))))
246      (subsume (isub ty (isub ty a b) (isub ty c d))))
247
248;; a -(b+(c+d)) = (a-b) - (c+d)
249(rule (simplify (isub ty a (iadd ty b (iadd ty c d))))
250      (subsume (isub ty (isub ty a b) (iadd ty c d))))
251
252;; a +(b-(c-d)) = (a+b) - (c-d)
253(rule (simplify (iadd ty a (isub ty b (isub ty c d))))
254      (subsume (isub ty (iadd ty a b) (isub ty c d))))
255
256;; a +(b-(c+d)) = (a+b) - (c+d)
257(rule (simplify (iadd ty a (isub ty b (iadd ty c d))))
258      (subsume (isub ty (iadd ty a b) (iadd ty c d))))
259
260;; a +(b+(c-d)) = (a+b) + (c-d)
261(rule (simplify (iadd ty a (iadd ty b (isub ty c d))))
262      (subsume (iadd ty (iadd ty a b) (isub ty c d))))
263
264;; and nested the other way
265
266;; ((a-b)-c)-d = (a-b) - (c+d)
267(rule (simplify (isub ty (isub ty (isub ty a b) c) d))
268      (subsume (isub ty (isub ty a b) (iadd ty c d))))
269
270;; ((a-b)-c)+d = (a-b) - (c-d)
271(rule (simplify (iadd ty (isub ty (isub ty a b) c) d))
272      (subsume (isub ty (isub ty a b) (isub ty c d))))
273
274;; ((a-b)+c)-d = (a-b) + (c-d)
275(rule (simplify (isub ty (iadd ty (isub ty a b) c) d))
276      (subsume (iadd ty (isub ty a b) (isub ty c d))))
277
278;; ((a-b)+c)+d = (a-b) + (c+d)
279(rule (simplify (iadd ty (iadd ty (isub ty a b) c) d))
280      (subsume (iadd ty (isub ty a b) (iadd ty c d))))
281
282;; ((a+b)-c)-d = (a+b) - (c+d)
283(rule (simplify (isub ty (isub ty (iadd ty a b) c) d))
284      (subsume (isub ty (iadd ty a b) (iadd ty c d))))
285
286;; ((a+b)-c)+d = (a+b) - (c-d)
287(rule (simplify (iadd ty (isub ty (iadd ty a b) c) d))
288      (subsume (isub ty (iadd ty a b) (isub ty c d))))
289
290;; ((a+b)+c)-d = (a+b) + (c-d)
291(rule (simplify (isub ty (iadd ty (iadd ty a b) c) d))
292      (subsume (iadd ty (iadd ty a b) (isub ty c d))))
293
294;; Detect people open-coding `mulhi`: (x as big * y as big) >> bits
295;; LLVM doesn't have an intrinsic for it, so you'll see it in code like
296;; <https://github.com/rust-lang/rust/blob/767453eb7ca188e991ac5568c17b984dd4893e77/library/core/src/num/mod.rs#L174-L180>
297(rule (simplify (sshr ty (imul ty (sextend _ x@(value_type half_ty))
298                                  (sextend _ y@(value_type half_ty)))
299                         (iconst_u _ k)))
300      (if-let true (ty_equal half_ty (ty_half_width ty)))
301      (if-let true (u64_eq k (ty_bits_u64 half_ty)))
302      (sextend ty (smulhi half_ty x y)))
303(rule (simplify (ushr ty (imul ty (uextend _ x@(value_type half_ty))
304                                  (uextend _ y@(value_type half_ty)))
305                         (iconst_u _ k)))
306      (if-let true (ty_equal half_ty (ty_half_width ty)))
307      (if-let true (u64_eq k (ty_bits_u64 half_ty)))
308      (uextend ty (umulhi half_ty x y)))
309
310;; Cranelift's `fcvt_from_{u,s}int` instructions are polymorphic over the input
311;; type so remove any unnecessary `uextend` or `sextend` to give backends
312;; the chance to convert from the smallest integral type to the float. This
313;; can help lowerings on x64 for example which has a less efficient u64-to-float
314;; conversion than other bit widths.
315(rule (simplify (fcvt_from_uint ty (uextend _ val)))
316      (fcvt_from_uint ty val))
317(rule (simplify (fcvt_from_sint ty (sextend _ val)))
318      (fcvt_from_sint ty val))
319
320
321;; or(x, C) + (-C)  -->  and(x, ~C)
322(rule
323  (simplify (iadd ty
324              (bor ty x (iconst_s ty n))
325              (iconst_s ty m)))
326  (if-let m (i64_checked_neg n))
327  (band ty x (iconst ty (imm64_masked ty (i64_cast_unsigned (i64_not n))))))
328
329;; (x + y) - (x | y) --> x & y
330(rule (simplify (isub ty (iadd ty x y) (bor ty x y))) (band ty x y))
331
332;; x * (1 << y) == x << y
333(rule (simplify (imul ty x (ishl ty (iconst_s ty 1) y))) (ishl ty x y))
334
335;; (x - y) + x --> x
336(rule (simplify (iadd ty (isub ty x y) y)) x)
337(rule (simplify (iadd ty y (isub ty x y))) x)
338
339;; (x + y) - y --> x
340(rule (simplify (isub ty (iadd ty x y) x)) y)
341(rule (simplify (isub ty (iadd ty x y) y)) x)
342
343
344