1;; rewrites for shifts and rotates: `ishl, `ushr`, `sshr`, `rotl, `rotr`
2
3;; x>>0 == x<<0 == x rotr 0 == x rotl 0 == x.
4(rule (simplify (ishl ty
5                      x
6                      (iconst_u ty 0)))
7      (subsume x))
8(rule (simplify (ushr ty
9                      x
10                      (iconst_u ty 0)))
11      (subsume x))
12(rule (simplify (sshr ty
13                      x
14                      (iconst_u ty 0)))
15      (subsume x))
16(rule (simplify (rotr ty
17                      x
18                      (iconst_u ty 0)))
19      (subsume x))
20(rule (simplify (rotl ty
21                      x
22                      (iconst_u ty 0)))
23      (subsume x))
24
25;; `(x >> k) << k` is the same as masking off the bottom `k` bits (regardless if
26;; this is a signed or unsigned shift right).
27(rule (simplify (ishl (fits_in_64 ty)
28                      (ushr ty x (iconst _ k))
29                      (iconst _ k)))
30      (let ((mask Imm64 (imm64_shl ty (imm64 0xFFFF_FFFF_FFFF_FFFF) k)))
31        (band ty x (iconst ty mask))))
32(rule (simplify (ishl (fits_in_64 ty)
33                      (sshr ty x (iconst _ k))
34                      (iconst _ k)))
35      (let ((mask Imm64 (imm64_shl ty (imm64 0xFFFF_FFFF_FFFF_FFFF) k)))
36        (band ty x (iconst ty mask))))
37
38;; For unsigned shifts, `(x << k) >> k` is the same as masking out the top
39;; `k` bits. A similar rule is valid for vectors but this `iconst` mask only
40;; works for scalar integers.
41(rule (simplify (ushr (fits_in_64 (ty_int ty))
42                      (ishl ty x (iconst _ k))
43                      (iconst _ k)))
44      (band ty x (iconst ty (imm64_ushr ty (imm64 (ty_mask ty)) k))))
45
46;; For signed shifts, `(x << k) >> k` does sign-extension from `n` bits to
47;; `n+k` bits. In the special case where `x` is the result of either `sextend`
48;; or `uextend` from `n` bits to `n+k` bits, we can implement this using
49;; `sextend`.
50(rule (simplify (sshr wide
51                 (ishl wide
52                  (uextend wide x @ (value_type narrow))
53                  (iconst_u _ shift_u64))
54                 (iconst_u _ shift_u64)))
55      (if-let true (u64_eq shift_u64 (u64_wrapping_sub (ty_bits_u64 wide) (ty_bits_u64 narrow))))
56      (sextend wide x))
57
58;; If `k` is smaller than the difference in bit widths of the two types, then
59;; the intermediate sign bit comes from the extend op, so the final result is
60;; the same as the original extend op.
61(rule (simplify (sshr wide
62                 (ishl wide
63                  x @ (uextend wide (value_type narrow))
64                  (iconst_u _ shift_u64))
65                 (iconst_u _ shift_u64)))
66      (if-let true (u64_lt shift_u64 (u64_wrapping_sub (ty_bits_u64 wide) (ty_bits_u64 narrow))))
67      x)
68
69;; If the original extend op was `sextend`, then both of the above cases say
70;; the result should also be `sextend`.
71(rule (simplify (sshr wide
72                 (ishl wide
73                  x @ (sextend wide (value_type narrow))
74                  (iconst_u _ shift_u64))
75                 (iconst_u _ shift_u64)))
76      (if-let true (u64_lt_eq shift_u64 (u64_wrapping_sub (ty_bits_u64 wide) (ty_bits_u64 narrow))))
77      x)
78
79;; (x << N) >> N == x as T_SMALL as T_LARGE
80;; if N == bytesizeof(T_LARGE) - bytesizeof(T_SMALL)
81;;
82;; Note that the shift is required to be >0 to ensure this doesn't accidentally
83;; try to `ireduce` a type to itself, which isn't a valid use of `ireduce`.
84(rule (simplify (sshr (ty_int ty) (ishl ty x (iconst _ shift)) (iconst _ shift)))
85      (if-let (u64_from_imm64 (u64_extract_non_zero shift_u64)) shift)
86      (if-let ty_small (shift_amt_to_type (u64_wrapping_sub (ty_bits ty) shift_u64)))
87      (sextend ty (ireduce ty_small x)))
88(rule (simplify (ushr (ty_int ty) (ishl ty x (iconst _ shift)) (iconst _ shift)))
89      (if-let (u64_from_imm64 (u64_extract_non_zero shift_u64)) shift)
90      (if-let ty_small (shift_amt_to_type (u64_wrapping_sub (ty_bits ty) shift_u64)))
91      (uextend ty (ireduce ty_small x)))
92
93(decl pure partial shift_amt_to_type (u64) Type)
94(rule (shift_amt_to_type 8) $I8)
95(rule (shift_amt_to_type 16) $I16)
96(rule (shift_amt_to_type 32) $I32)
97
98;; ineg(ushr(x, k)) == sshr(x, k) when k == ty_bits - 1.
99(rule (simplify (ineg ty (ushr ty x sconst @ (iconst_u ty shift_amt))))
100      (if-let true (u64_eq shift_amt (ty_shift_mask ty)))
101      (sshr ty x sconst))
102
103;; Shifts and rotates allow a different type for the shift amount, so we
104;; can remove any extend/reduce operations on the shift amount.
105;;
106;; (op x (ireduce y)) == (op x y)
107;; (op x (uextend y)) == (op x y)
108;; (op x (sextend y)) == (op x y)
109;;
110;; where `op` is one of ishl, ushr, sshr, rotl, rotr
111;;
112;; TODO: This rule is restricted to <=64 bits for ireduce since the x86
113;; backend doesn't support SIMD shifts with 128-bit shift amounts.
114
115(rule (simplify (ishl ty x (ireduce _ y @ (value_type (fits_in_64 _))))) (ishl ty x y))
116(rule (simplify (ishl ty x (uextend _ y))) (ishl ty x y))
117(rule (simplify (ishl ty x (sextend _ y))) (ishl ty x y))
118(rule (simplify (ushr ty x (ireduce _ y @ (value_type (fits_in_64 _))))) (ushr ty x y))
119(rule (simplify (ushr ty x (uextend _ y))) (ushr ty x y))
120(rule (simplify (ushr ty x (sextend _ y))) (ushr ty x y))
121(rule (simplify (sshr ty x (ireduce _ y @ (value_type (fits_in_64 _))))) (sshr ty x y))
122(rule (simplify (sshr ty x (uextend _ y))) (sshr ty x y))
123(rule (simplify (sshr ty x (sextend _ y))) (sshr ty x y))
124(rule (simplify (rotr ty x (ireduce _ y @ (value_type (fits_in_64 _))))) (rotr ty x y))
125(rule (simplify (rotr ty x (uextend _ y))) (rotr ty x y))
126(rule (simplify (rotr ty x (sextend _ y))) (rotr ty x y))
127(rule (simplify (rotl ty x (ireduce _ y @ (value_type (fits_in_64 _))))) (rotl ty x y))
128(rule (simplify (rotl ty x (uextend _ y))) (rotl ty x y))
129(rule (simplify (rotl ty x (sextend _ y))) (rotl ty x y))
130
131;; Remove iconcat from the shift amount input. This is correct even if the
132;; the iconcat is i8 type, since it can represent the largest shift amount
133;; for i128 types.
134;;
135;; (op x (iconcat y1 y2)) == (op x y1)
136;;
137;; where `op` is one of ishl, ushr, sshr, rotl, rotr
138
139(rule (simplify (ishl ty x (iconcat _ y _))) (ishl ty x y))
140(rule (simplify (ushr ty x (iconcat _ y _))) (ushr ty x y))
141(rule (simplify (sshr ty x (iconcat _ y _))) (sshr ty x y))
142(rule (simplify (rotr ty x (iconcat _ y _))) (rotr ty x y))
143(rule (simplify (rotl ty x (iconcat _ y _))) (rotl ty x y))
144
145;; Try to combine the shift amount from multiple consecutive shifts
146;; This only works if the shift amount remains smaller than the bit
147;; width of the type.
148;;
149;; (ishl (ishl x k1) k2) == (ishl x (add k1 k2)) if shift_mask(k1) + shift_mask(k2) < ty_bits
150;; (ushr (ushr x k1) k2) == (ushr x (add k1 k2)) if shift_mask(k1) + shift_mask(k2) < ty_bits
151;; (sshr (sshr x k1) k2) == (sshr x (add k1 k2)) if shift_mask(k1) + shift_mask(k2) < ty_bits
152(rule (simplify (ishl ty
153                      (ishl ty x (iconst_u kty k1))
154                      (iconst_u _ k2)))
155      (if-let shift_amt (u64_wrapping_add
156                              (u64_and k1 (ty_shift_mask ty))
157                              (u64_and k2 (ty_shift_mask ty))))
158      (if-let true (u64_lt shift_amt (ty_bits_u64 (lane_type ty))))
159      (ishl ty x (iconst_u kty shift_amt)))
160
161(rule (simplify (ushr ty
162                      (ushr ty x (iconst_u kty k1))
163                      (iconst_u _ k2)))
164      (if-let shift_amt (u64_wrapping_add
165                              (u64_and k1 (ty_shift_mask ty))
166                              (u64_and k2 (ty_shift_mask ty))))
167      (if-let true (u64_lt shift_amt (ty_bits_u64 (lane_type ty))))
168      (ushr ty x (iconst_u kty shift_amt)))
169
170(rule (simplify (sshr ty
171                      (sshr ty x (iconst_u kty k1))
172                      (iconst_u _ k2)))
173      (if-let shift_amt (u64_wrapping_add
174                              (u64_and k1 (ty_shift_mask ty))
175                              (u64_and k2 (ty_shift_mask ty))))
176      (if-let true (u64_lt shift_amt (ty_bits_u64 (lane_type ty))))
177      (sshr ty x (iconst_u kty shift_amt)))
178
179;; Similarly, if the shift amount overflows the type, then we can turn
180;; it into a 0
181;;
182;; (ishl (ishl x k1) k2) == 0 if shift_mask(k1) + shift_mask(k2) >= ty_bits
183;; (ushr (ushr x k1) k2) == 0 if shift_mask(k1) + shift_mask(k2) >= ty_bits
184(rule (simplify (ishl ty
185                      (ishl ty x (iconst_u _ k1))
186                      (iconst_u _ k2)))
187      (if-let shift_amt (u64_wrapping_add
188                              (u64_and k1 (ty_shift_mask ty))
189                              (u64_and k2 (ty_shift_mask ty))))
190      (if-let true (u64_lt_eq (ty_bits_u64 ty) shift_amt))
191      (subsume (iconst_u ty 0)))
192
193(rule (simplify (ushr ty
194                      (ushr ty x (iconst_u _ k1))
195                      (iconst_u _ k2)))
196      (if-let shift_amt (u64_wrapping_add
197                              (u64_and k1 (ty_shift_mask ty))
198                              (u64_and k2 (ty_shift_mask ty))))
199      (if-let true (u64_lt_eq (ty_bits_u64 ty) shift_amt))
200      (subsume (iconst_u ty 0)))
201
202;; (rotl (rotr x y) y) == x
203;; (rotr (rotl x y) y) == x
204(rule (simplify (rotl ty (rotr ty x y) y)) (subsume x))
205(rule (simplify (rotr ty (rotl ty x y) y)) (subsume x))
206
207;; Emits an iadd for two values. If they have different types
208;; then the smaller type is zero extended to the larger type.
209(decl iadd_uextend (Value Value) Value)
210(rule 1 (iadd_uextend x @ (value_type ty) y @ (value_type ty))
211      (iadd ty x y))
212(rule 2 (iadd_uextend x @ (value_type x_ty) y @ (value_type y_ty))
213      (if-let true (u64_lt (ty_bits_u64 x_ty) (ty_bits_u64 y_ty)))
214      (iadd y_ty (uextend y_ty x) y))
215(rule 3 (iadd_uextend x @ (value_type x_ty) y @ (value_type y_ty))
216      (if-let true (u64_lt (ty_bits_u64 y_ty) (ty_bits_u64 x_ty)))
217      (iadd x_ty x (uextend x_ty y)))
218
219;; Emits an isub for two values. If they have different types
220;; then the smaller type is zero extended to the larger type.
221(decl isub_uextend (Value Value) Value)
222(rule 1 (isub_uextend x @ (value_type ty) y @ (value_type ty))
223      (isub ty x y))
224(rule 2 (isub_uextend x @ (value_type x_ty) y @ (value_type y_ty))
225      (if-let true (u64_lt (ty_bits_u64 x_ty) (ty_bits_u64 y_ty)))
226      (isub y_ty (uextend y_ty x) y))
227(rule 3 (isub_uextend x @ (value_type x_ty) y @ (value_type y_ty))
228      (if-let true (u64_lt (ty_bits_u64 y_ty) (ty_bits_u64 x_ty)))
229      (isub x_ty x (uextend x_ty y)))
230
231;; Try to group constants together so that other cprop rules can optimize them.
232;;
233;; (rotr (rotr x y) z) == (rotr x (iadd y z))
234;; (rotl (rotl x y) z) == (rotl x (iadd y z))
235;; (rotr (rotl x y) z) == (rotr x (isub y z))
236;; (rotl (rotr x y) z) == (rotl x (isub y z))
237;;
238;; if x or z are constants
239(rule (simplify (rotl ty (rotl ty x y @ (iconst _ _)) z)) (rotl ty x (iadd_uextend y z)))
240(rule (simplify (rotl ty (rotl ty x y) z @ (iconst _ _))) (rotl ty x (iadd_uextend y z)))
241(rule (simplify (rotr ty (rotr ty x y @ (iconst _ _)) z)) (rotr ty x (iadd_uextend y z)))
242(rule (simplify (rotr ty (rotr ty x y) z @ (iconst _ _))) (rotr ty x (iadd_uextend y z)))
243
244(rule (simplify (rotr ty (rotl ty x y @ (iconst _ _)) z)) (rotl ty x (isub_uextend y z)))
245(rule (simplify (rotr ty (rotl ty x y) z @ (iconst _ _))) (rotl ty x (isub_uextend y z)))
246(rule (simplify (rotl ty (rotr ty x y @ (iconst _ _)) z)) (rotr ty x (isub_uextend y z)))
247(rule (simplify (rotl ty (rotr ty x y) z @ (iconst _ _))) (rotr ty x (isub_uextend y z)))
248
249;; Similarly to the rules above, if y and z have the same type, we should emit
250;; an iadd or isub instead. In some backends this is cheaper than a rotate.
251;;
252;; If they have different types we end up in a situation where we have to insert
253;; and additional extend and that transformation is not universally beneficial.
254;;
255;; (rotr (rotr x y) z) == (rotr x (iadd y z))
256;; (rotl (rotl x y) z) == (rotl x (iadd y z))
257;; (rotr (rotl x y) z) == (rotl x (isub y z))
258;; (rotl (rotr x y) z) == (rotr x (isub y z))
259(rule (simplify (rotr ty (rotr ty x y @ (value_type kty)) z @ (value_type kty)))
260      (rotr ty x (iadd_uextend y z)))
261(rule (simplify (rotl ty (rotl ty x y @ (value_type kty)) z @ (value_type kty)))
262      (rotl ty x (iadd_uextend y z)))
263
264(rule (simplify (rotr ty (rotl ty x y @ (value_type kty)) z @ (value_type kty)))
265      (rotl ty x (isub_uextend y z)))
266(rule (simplify (rotl ty (rotr ty x y @ (value_type kty)) z @ (value_type kty)))
267      (rotr ty x (isub_uextend y z)))
268
269(rule
270    (simplify (rotr ty (iconst ty p) (select ty x (iconst ty y) (iconst ty z))))
271    (select ty x (iconst ty (imm64_rotr ty p y)) (iconst ty (imm64_rotr ty p z))))
272
273;; Convert shifts into rotates. We always normalize into a rotate left.
274;;
275;; (bor (ishl x k1) (ushr x k2)) == (rotl x k1) if k2 == ty_bits - k1
276;; (bor (ushr x k2) (ishl x k1)) == (rotl x k1) if k2 == ty_bits - k1
277;;
278;; TODO: This rule is restricted to scalars since no backend currently
279;; supports SIMD rotates.
280(rule (simplify (bor (ty_int ty)
281                      (ishl ty x k @ (iconst _ (u64_from_imm64 k1)))
282                      (ushr ty x (iconst _ (u64_from_imm64 k2)))))
283      (if-let true (u64_eq k2 (u64_wrapping_sub (ty_bits_u64 (lane_type ty)) k1)))
284      (rotl ty x k))
285(rule (simplify (bor (ty_int ty)
286                      (ushr ty x (iconst _ (u64_from_imm64 k2)))
287                      (ishl ty x k @ (iconst _ (u64_from_imm64 k1)))))
288      (if-let true (u64_eq k2 (u64_wrapping_sub (ty_bits_u64 (lane_type ty)) k1)))
289      (rotl ty x k))
290
291;; Normalize the shift amount. Some rules can't fire unless the shift amount
292;; is normalized. This also helps us materialize fewer and smaller constants.
293;;
294;; (op x k) == (op x (and k (ty_shift_mask ty)))
295;;
296;; where `op` is one of ishl, ushr, sshr, rotl, rotr
297(rule (simplify (ishl ty x (iconst_u kty k)))
298      (if-let false (u64_eq k (u64_and k (ty_shift_mask ty))))
299      (ishl ty x (iconst_u kty (u64_and k (ty_shift_mask ty)))))
300(rule (simplify (ushr ty x (iconst_u kty k)))
301      (if-let false (u64_eq k (u64_and k (ty_shift_mask ty))))
302      (ushr ty x (iconst_u kty (u64_and k (ty_shift_mask ty)))))
303(rule (simplify (sshr ty x (iconst_u kty k)))
304      (if-let false (u64_eq k (u64_and k (ty_shift_mask ty))))
305      (sshr ty x (iconst_u kty (u64_and k (ty_shift_mask ty)))))
306(rule (simplify (rotr ty x (iconst_u kty k)))
307      (if-let false (u64_eq k (u64_and k (ty_shift_mask ty))))
308      (rotr ty x (iconst_u kty (u64_and k (ty_shift_mask ty)))))
309(rule (simplify (rotl ty x (iconst_u kty k)))
310      (if-let false (u64_eq k (u64_and k (ty_shift_mask ty))))
311      (rotl ty x (iconst_u kty (u64_and k (ty_shift_mask ty)))))
312
313(rule (simplify (band ty (ishl ty x z) (ishl ty y z))) (ishl ty (band ty x y) z))
314(rule (simplify (isub ty (ishl ty x z) (ishl ty y z))) (ishl ty (isub ty x y) z))
315(rule (simplify (iadd ty (ishl ty x z) (ishl ty y z))) (ishl ty (iadd ty x y) z))
316
317(rule (simplify (ushr ty (band ty (ishl ty x y) z) y)) (band ty x (ushr ty z y)))
318