1;; Prelude definitions specific to the mid-end.
2
3;; Any `extern` definitions here are generally implemented in `src/opts.rs`.
4
5;;;;; eclass and enode access ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
6
7;; Extract any node(s) for the given eclass ID.
8(decl multi inst_data_value (Type InstructionData) Value)
9(extern extractor inst_data_value inst_data_value_etor)
10
11;; An extractor from an `Inst` to its `InstructionData`.
12(decl inst_data (InstructionData) Inst)
13(extern extractor inst_data inst_data_etor)
14
15;; Identical to `inst_data_value`, just with a different ISLE type.  This is
16;; basically a manual version of `curry`/`uncurry` in Haskell: to compose
17;; extractors the outer one needs to be single-parameter, so this combines the
18;; two parameters of `inst_data_value` into one.
19(type TypeAndInstructionData (primitive TypeAndInstructionData))
20(decl multi inst_data_value_tupled (TypeAndInstructionData) Value)
21(extern extractor inst_data_value_tupled inst_data_value_tupled_etor)
22
23;; Construct a pure node, returning a new (or deduplicated
24;; already-existing) eclass ID.
25(decl make_inst (Type InstructionData) Value)
26(extern constructor make_inst make_inst_ctor)
27
28;; Make a new side-effectful instruction, do not insert it into the layout, and
29;; return its `Inst`.
30(decl make_skeleton_inst (InstructionData) Inst)
31(extern constructor make_skeleton_inst make_skeleton_inst_ctor)
32
33;; Constructors for value arrays.
34(decl value_array_2_ctor (Value Value) ValueArray2)
35(extern constructor value_array_2_ctor value_array_2_ctor)
36(decl value_array_3_ctor (Value Value Value) ValueArray3)
37(extern constructor value_array_3_ctor value_array_3_ctor)
38
39(rule (eq ty x y) (icmp ty (IntCC.Equal) x y))
40(rule (ne ty x y) (icmp ty (IntCC.NotEqual) x y))
41(rule (ult ty x y) (icmp ty (IntCC.UnsignedLessThan) x y))
42(rule (ule ty x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
43(rule (ugt ty x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
44(rule (uge ty x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
45(rule (slt ty x y) (icmp ty (IntCC.SignedLessThan) x y))
46(rule (sle ty x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
47(rule (sgt ty x y) (icmp ty (IntCC.SignedGreaterThan) x y))
48(rule (sge ty x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
49
50;; 3-way comparison, returning -1/0/+1 in I8
51(decl spaceship_s (Type Value Value) Value)
52(rule (spaceship_s ty x y) (isub $I8 (sgt ty x y) (slt ty x y)))
53(extractor (spaceship_s ty x y) (isub $I8 (sgt ty x y) (slt ty x y)))
54(decl spaceship_u (Type Value Value) Value)
55(rule (spaceship_u ty x y) (isub $I8 (ugt ty x y) (ult ty x y)))
56(extractor (spaceship_u ty x y) (isub $I8 (ugt ty x y) (ult ty x y)))
57
58;;;;; optimization toplevel ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
59
60;; The main matcher rule invoked by the toplevel driver.
61(decl multi simplify (Value) Value)
62
63;; The kind of simplification to perform on a skeleton instruction.
64(type SkeletonInstSimplification
65      (enum
66        ;; Remove the instruction being simplified from the skeleton, it is
67        ;; unnecessary.
68        ;;
69        ;; The instruction must not define any results.
70        (Remove)
71
72        ;; Remove the instruction being simplified from the skeleton, and
73        ;; replace its result value with the given `val`.
74        (RemoveWithVal (val Value))
75
76        ;; Replace the instruction being simplified with the given instruction.
77        ;;
78        ;; The given instruction must not already be in a block and must define
79        ;; the same number and types of results as the old instruction that it
80        ;; is replacing.
81        (Replace (inst Inst))
82
83        ;; Like `Replace` but replace the old instruction's result value with
84        ;; the given `val`.
85        ;;
86        ;; The old instruction must define a single result value and `val` must
87        ;; match its type. The new instruction need not define the same number
88        ;; or types of results as the old instruction.
89        (ReplaceWithVal (inst Inst) (val Value))))
90
91(decl pure inst_to_skeleton_inst_simplification (Inst) SkeletonInstSimplification)
92(rule (inst_to_skeleton_inst_simplification inst)
93      (SkeletonInstSimplification.Replace inst))
94
95(decl pure value_to_skeleton_inst_simplification (Value) SkeletonInstSimplification)
96(rule (value_to_skeleton_inst_simplification val)
97      (SkeletonInstSimplification.RemoveWithVal val))
98
99(decl pure remove_inst () SkeletonInstSimplification)
100(rule (remove_inst) (SkeletonInstSimplification.Remove))
101
102(decl pure replace_with_val (Inst Value) SkeletonInstSimplification)
103(rule (replace_with_val inst val) (SkeletonInstSimplification.ReplaceWithVal inst val))
104
105(convert Inst SkeletonInstSimplification inst_to_skeleton_inst_simplification)
106(convert Value SkeletonInstSimplification value_to_skeleton_inst_simplification)
107
108;; The main term for simplifying side-effectful instructions, invoked by the
109;; egraph driver.
110(decl multi simplify_skeleton (Inst) SkeletonInstSimplification)
111
112;; Mark a node as requiring remat when used in a different block.
113(decl remat (Value) Value)
114(extern constructor remat remat)
115
116;; Mark a node as subsuming whatever else it's rewritten from -- this
117;; is definitely preferable, not just a possible option. Useful for,
118;; e.g., constant propagation where we arrive at a definite "final
119;; answer".
120(decl subsume (Value) Value)
121(extern constructor subsume subsume)
122
123;;;;; constructors ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
124
125(decl iconst_sextend_etor (Type i64) TypeAndInstructionData)
126(extern extractor iconst_sextend_etor iconst_sextend_etor)
127
128;; Construct an `iconst` from an `i64` or Extract an `i64` from an `iconst`
129;; by treating the constant as signed.
130;; When extracting, smaller types get their value sign-extended to 64-bits,
131;; so that `iconst.i8 255` will give you a `-1_i64`.
132;; When constructing, the rule will fail if the value cannot be represented in
133;; the target type.  If it fits, it'll be masked accordingly in the constant.
134(decl iconst_s (Type i64) Value)
135(extractor (iconst_s ty c) (inst_data_value_tupled (iconst_sextend_etor ty c)))
136(rule 0 (iconst_s ty c)
137    (if-let c_masked (u64_and (i64_cast_unsigned c)
138                              (ty_umax ty)))
139    (if-let c_reextended (i64_sextend_u64 ty c_masked))
140    (if-let true (i64_eq c c_reextended))
141    (iconst ty (imm64 c_masked)))
142(rule 1 (iconst_s $I128 c) (sextend $I128 (iconst_s $I64 c)))
143
144;; Construct an `iconst` from a `u64` or Extract a `u64` from an `iconst`
145;; by treating the constant as unsigned.
146;; When extracting, smaller types get their value zero-extended to 64-bits,
147;; so that `iconst.i8 255` will give you a `255_u64`.
148;; When constructing, the rule will fail if the value cannot be represented in
149;; the target type.
150(decl iconst_u (Type u64) Value)
151(extractor (iconst_u ty c) (iconst ty (u64_from_imm64 c)))
152(rule 0 (iconst_u ty c)
153    (if-let true (u64_lt_eq c (ty_umax ty)))
154    (iconst ty (imm64 c)))
155(rule 1 (iconst_u $I128 c) (uextend $I128 (iconst_u $I64 c)))
156
157;; These take `Value`, rather than going through `inst_data_value_tupled`,
158;; because most of the time they want to return the original `Value`, and it
159;; would be a waste to need to re-GVN the instruction data in those cases.
160(decl multi sextend_maybe_etor (Type Value) Value)
161(extern extractor infallible sextend_maybe_etor sextend_maybe_etor)
162(decl multi uextend_maybe_etor (Type Value) Value)
163(extern extractor infallible uextend_maybe_etor uextend_maybe_etor)
164
165;; Match or Construct a possibly-`uextend`ed value.
166;; Gives the extended-to type and inner value when matching something that was
167;; extended, or the input value and its type when the value isn't an extension.
168;; Useful to write a single pattern that can match things that may or may not
169;; have undergone C's "usual arithmetic conversions".
170;; When generating values, extending to the same type is invalid CLIF,
171;; so this avoids doing that where there's no extension actually needed.
172(decl uextend_maybe (Type Value) Value)
173(extractor (uextend_maybe ty val) (uextend_maybe_etor ty val))
174(rule 0 (uextend_maybe ty val) (uextend ty val))
175(rule 1 (uextend_maybe ty val@(value_type ty)) val)
176
177;; Same as `uextend_maybe` above, just for `sextend`.
178(decl sextend_maybe (Type Value) Value)
179(extractor (sextend_maybe ty val) (sextend_maybe_etor ty val))
180(rule 0 (sextend_maybe ty val) (sextend ty val))
181(rule 1 (sextend_maybe ty val@(value_type ty)) val)
182
183;;;;;; Helper CLIF Extractors ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
184
185(decl eq (Type Value Value) Value)
186(extractor (eq ty x y) (icmp ty (IntCC.Equal) x y))
187
188(decl ne (Type Value Value) Value)
189(extractor (ne ty x y) (icmp ty (IntCC.NotEqual) x y))
190
191(decl ult (Type Value Value) Value)
192(extractor (ult ty x y) (icmp ty (IntCC.UnsignedLessThan) x y))
193
194(decl ule (Type Value Value) Value)
195(extractor (ule ty x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
196
197(decl ugt (Type Value Value) Value)
198(extractor (ugt ty x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
199
200(decl uge (Type Value Value) Value)
201(extractor (uge ty x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
202
203(decl slt (Type Value Value) Value)
204(extractor (slt ty x y) (icmp ty (IntCC.SignedLessThan) x y))
205
206(decl sle (Type Value Value) Value)
207(extractor (sle ty x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
208
209(decl sgt (Type Value Value) Value)
210(extractor (sgt ty x y) (icmp ty (IntCC.SignedGreaterThan) x y))
211
212(decl sge (Type Value Value) Value)
213(extractor (sge ty x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
214
215;;;;;; Divison-By-Constant Helpers ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
216
217(decl pure i64_is_negative_power_of_two (i64) bool)
218(rule (i64_is_negative_power_of_two x)
219      (u64_is_power_of_two (i64_cast_unsigned (i64_wrapping_neg x))))
220
221(decl pure i64_is_any_sign_power_of_two (i64) bool)
222(rule 2 (i64_is_any_sign_power_of_two x)
223      (if-let true (u64_is_power_of_two (i64_cast_unsigned x)))
224      true)
225(rule 1 (i64_is_any_sign_power_of_two x)
226      (if-let true (i64_is_negative_power_of_two x))
227      true)
228(rule 0 (i64_is_any_sign_power_of_two _) false)
229
230(type DivConstMagicU32 (enum (U32 (mul_by u32)
231                                  (do_add bool)
232                                  (shift_by u32))))
233(type DivConstMagicU64 (enum (U64 (mul_by u64)
234                                  (do_add bool)
235                                  (shift_by u32))))
236(type DivConstMagicS32 (enum (S32 (mul_by i32)
237                                  (shift_by u32))))
238(type DivConstMagicS64 (enum (S64 (mul_by i64)
239                                  (shift_by u32))))
240
241;; Extern magic-const constructors and accessors.
242
243(decl div_const_magic_u32 (u32) DivConstMagicU32)
244(extern constructor div_const_magic_u32 div_const_magic_u32)
245
246(decl div_const_magic_u64 (u64) DivConstMagicU64)
247(extern constructor div_const_magic_u64 div_const_magic_u64)
248
249(decl div_const_magic_s32 (i32) DivConstMagicS32)
250(extern constructor div_const_magic_s32 div_const_magic_s32)
251
252(decl div_const_magic_s64 (i64) DivConstMagicS64)
253(extern constructor div_const_magic_s64 div_const_magic_s64)
254
255;; Applying div-const magic for u32.
256(decl apply_div_const_magic_u32 (Opcode Value u32) Value)
257(rule (apply_div_const_magic_u32 opcode numerator divisor)
258      (apply_div_const_magic_u32_inner opcode numerator divisor (div_const_magic_u32 divisor)))
259
260;; q0 = umuli numerator, mul_by
261(decl apply_div_const_magic_u32_inner (Opcode Value u32 DivConstMagicU32) Value)
262(rule (apply_div_const_magic_u32_inner opcode
263                                       numerator
264                                       divisor
265                                       magic @ (DivConstMagicU32.U32 mul_by _do_add _shift_by))
266      (let ((q0 Value (umulhi $I32 numerator (iconst_u $I32 mul_by))))
267        (apply_div_const_magic_u32_maybe_add opcode numerator divisor magic q0)))
268
269;; qf = if do_add {
270;;     q1 = isub numerator, q0
271;;     q2 = ushr q1, 1
272;;     q3 = iadd q0, q2
273;;     maybe_shift(q3)
274;; } else {
275;;     ushr q0, shift_by
276;; };
277(decl apply_div_const_magic_u32_maybe_add (Opcode Value u32 DivConstMagicU32 Value) Value)
278(rule (apply_div_const_magic_u32_maybe_add opcode
279                                           numerator
280                                           divisor
281                                           magic @ (DivConstMagicU32.U32 _mul_by true _shift_by)
282                                           q0)
283      (let ((q1 Value (isub $I32 numerator q0))
284            (q2 Value (ushr $I32 q1 (iconst_u $I32 1)))
285            (q3 Value (iadd $I32 q0 q2)))
286        (apply_div_const_magic_u32_maybe_shift opcode numerator divisor magic q3)))
287(rule (apply_div_const_magic_u32_maybe_add opcode
288                                           numerator
289                                           divisor
290                                           magic @ (DivConstMagicU32.U32 _mul_by false shift_by)
291                                           q0)
292      (let ((q3 Value (ushr $I32 q0 (iconst_u $I32 shift_by))))
293        (apply_div_const_magic_u32_finish opcode numerator divisor q3)))
294
295;; qf = if shift_by == 0 {
296;;     q3
297;; } else {
298;;     ushr q3, shift_by - 1
299;; };
300(decl apply_div_const_magic_u32_maybe_shift (Opcode Value u32 DivConstMagicU32 Value) Value)
301(rule 2 (apply_div_const_magic_u32_maybe_shift opcode
302                                                          numerator
303                                                          divisor
304                                                          (DivConstMagicU32.U32 _mul_by _do_add 0)
305                                                          q3)
306      (apply_div_const_magic_u32_finish opcode numerator divisor q3))
307(rule 1 (apply_div_const_magic_u32_maybe_shift opcode
308                                               numerator
309                                               divisor
310                                               (DivConstMagicU32.U32 _mul_by
311                                                                     _do_add
312                                                                     (u32_extract_non_zero shift_by))
313                                               q3)
314      (let ((qf Value (ushr $I32 q3 (iconst_u $I32 (u32_sub shift_by 1)))))
315        (apply_div_const_magic_u32_finish opcode numerator divisor qf)))
316
317;; Now `qf` holds the final quotient. If necessary calculate the remainder
318;; instead.
319;;
320;; if Opcode == Urem {
321;;     tt = imul qf, divisor
322;;     isub numerator, tt
323;; } else {
324;;     qf
325;; }
326(decl apply_div_const_magic_u32_finish (Opcode Value u32 Value) Value)
327(rule (apply_div_const_magic_u32_finish (Opcode.Udiv) _ _ qf) qf)
328(rule (apply_div_const_magic_u32_finish (Opcode.Urem) numerator divisor qf)
329      (let ((tt Value (imul $I32 qf (iconst_u $I32 divisor))))
330        (isub $I32 numerator tt)))
331
332;; Applying div-const magic for u64.
333(decl apply_div_const_magic_u64 (Opcode Value u64) Value)
334(rule (apply_div_const_magic_u64 opcode numerator divisor)
335      (apply_div_const_magic_u64_inner opcode numerator divisor (div_const_magic_u64 divisor)))
336
337;; q0 = umuli numerator, mul_by
338(decl apply_div_const_magic_u64_inner (Opcode Value u64 DivConstMagicU64) Value)
339(rule (apply_div_const_magic_u64_inner opcode
340                                       numerator
341                                       divisor
342                                       magic @ (DivConstMagicU64.U64 mul_by _do_add _shift_by))
343      (let ((q0 Value (umulhi $I64 numerator (iconst_u $I64 mul_by))))
344        (apply_div_const_magic_u64_maybe_add opcode numerator divisor magic q0)))
345
346;; qf = if do_add {
347;;     q1 = isub numerator, q0
348;;     q2 = ushr q1, 1
349;;     q3 = iadd q0, q2
350;;     maybe_shift(q3)
351;; } else {
352;;     ushr q0, shift_by
353;; };
354(decl apply_div_const_magic_u64_maybe_add (Opcode Value u64 DivConstMagicU64 Value) Value)
355(rule (apply_div_const_magic_u64_maybe_add opcode
356                                           numerator
357                                           divisor
358                                           magic @ (DivConstMagicU64.U64 _mul_by true _shift_by)
359                                           q0)
360      (let ((q1 Value (isub $I64 numerator q0))
361            (q2 Value (ushr $I64 q1 (iconst_u $I64 1)))
362            (q3 Value (iadd $I64 q0 q2)))
363        (apply_div_const_magic_u64_maybe_shift opcode numerator divisor magic q3)))
364(rule (apply_div_const_magic_u64_maybe_add opcode
365                                           numerator
366                                           divisor
367                                           magic @ (DivConstMagicU64.U64 _mul_by false shift_by)
368                                           q0)
369      (let ((q3 Value (ushr $I64 q0 (iconst_u $I64 shift_by))))
370        (apply_div_const_magic_u64_finish opcode numerator divisor q3)))
371
372;; qf = if shift_by == 0 {
373;;     q3
374;; } else {
375;;     ushr q3, shift_by - 1
376;; };
377(decl apply_div_const_magic_u64_maybe_shift (Opcode Value u64 DivConstMagicU64 Value) Value)
378(rule 2 (apply_div_const_magic_u64_maybe_shift opcode
379                                                          numerator
380                                                          divisor
381                                                          (DivConstMagicU64.U64 _mul_by _do_add 0)
382                                                          q3)
383      (apply_div_const_magic_u64_finish opcode numerator divisor q3))
384(rule 1 (apply_div_const_magic_u64_maybe_shift opcode
385                                               numerator
386                                               divisor
387                                               (DivConstMagicU64.U64 _mul_by
388                                                                     _do_add
389                                                                     (u32_extract_non_zero shift_by))
390                                               q3)
391      (let ((qf Value (ushr $I64 q3 (iconst_u $I64 (u64_sub shift_by 1)))))
392        (apply_div_const_magic_u64_finish opcode numerator divisor qf)))
393
394;; Now `qf` holds the final quotient. If necessary calculate the remainder
395;; instead.
396;;
397;; if Opcode == Urem {
398;;     tt = imul qf, divisor
399;;     isub numerator, tt
400;; } else {
401;;     qf
402;; }
403(decl apply_div_const_magic_u64_finish (Opcode Value u64 Value) Value)
404(rule (apply_div_const_magic_u64_finish (Opcode.Udiv) _ _ qf) qf)
405(rule (apply_div_const_magic_u64_finish (Opcode.Urem) numerator divisor qf)
406      (let ((tt Value (imul $I64 qf (iconst_u $I64 divisor))))
407        (isub $I64 numerator tt)))
408
409;; Applying div-const magic for s32.
410
411(decl apply_div_const_magic_s32 (Opcode Value i32) Value)
412(rule (apply_div_const_magic_s32 opcode numerator divisor)
413      (apply_div_const_magic_s32_inner opcode numerator divisor (div_const_magic_s32 divisor)))
414
415;; q0 = iconst.i32 mul_by
416;; q1 = smulhi numerator, q0
417(decl apply_div_const_magic_s32_inner (Opcode Value i32 DivConstMagicS32) Value)
418(rule (apply_div_const_magic_s32_inner opcode
419                                       numerator
420                                       divisor
421                                       magic @ (DivConstMagicS32.S32 mul_by _shift_by))
422      (let ((q0 Value (iconst_s $I32 mul_by))
423            (q1 Value (smulhi $I32 numerator q0)))
424        (apply_div_const_magic_s32_add_sub opcode numerator divisor magic q1)))
425
426;; q2 = if divisor > 0 && mul_by < 0 {
427;;     iadd q1, numerator
428;; } else if divisor < 0 && mul_by > 0 {
429;;     isub q1, numerator
430;; } else {
431;;     q1
432;; };
433(decl apply_div_const_magic_s32_add_sub (Opcode Value i32 DivConstMagicS32 Value) Value)
434(rule 2 (apply_div_const_magic_s32_add_sub opcode
435                                           numerator
436                                           divisor
437                                           magic @ (DivConstMagicS32.S32 mul_by _shift_by)
438                                           q1)
439      (if-let true (i32_gt divisor 0))
440      (if-let true (i32_lt mul_by 0))
441      (let ((q2 Value (iadd $I32 q1 numerator)))
442        (apply_div_const_magic_s32_shift opcode numerator divisor magic q2)))
443(rule 1 (apply_div_const_magic_s32_add_sub opcode
444                                           numerator
445                                           divisor
446                                           magic @ (DivConstMagicS32.S32 mul_by _shift_by)
447                                           q1)
448      (if-let true (i32_lt divisor 0))
449      (if-let true (i32_gt mul_by 0))
450      (let ((q2 Value (isub $I32 q1 numerator)))
451        (apply_div_const_magic_s32_shift opcode numerator divisor magic q2)))
452(rule 0 (apply_div_const_magic_s32_add_sub opcode
453                                           numerator
454                                           divisor
455                                           magic
456                                           q1)
457      (apply_div_const_magic_s32_shift opcode numerator divisor magic q1))
458
459;; q3 = sshr q2, shift_by
460;; t1 = ushr q3, 31
461;; qf = iadd q3, t1
462(decl apply_div_const_magic_s32_shift (Opcode Value i32 DivConstMagicS32 Value) Value)
463(rule (apply_div_const_magic_s32_shift opcode
464                                       numerator
465                                       divisor
466                                       magic @ (DivConstMagicS32.S32 _mul_by shift_by)
467                                       q2)
468      ;; Note: let other rules clean up `q2` when `shift_by == 0`.
469      (let ((q3 Value (sshr $I32 q2 (iconst_s $I32 shift_by)))
470            (t1 Value (ushr $I32 q3 (iconst_s $I32 31)))
471            (qf Value (iadd $I32 q3 t1)))
472        (apply_div_const_magic_s32_finish opcode numerator divisor qf)))
473
474;; Now `qf` holds the final quotient. If necessary, produce the remainder
475;; instead.
476;;
477;; if Opcode == Srem {
478;;     tt = imul qf, divisor
479;;     isub numerator, tt
480;; } else {
481;;     qf
482;; }
483(decl apply_div_const_magic_s32_finish (Opcode Value i32 Value) Value)
484(rule (apply_div_const_magic_s32_finish (Opcode.Srem) numerator divisor qf)
485      (let ((tt Value (imul $I32 qf (iconst_s $I32 divisor))))
486        (isub $I32 numerator tt)))
487(rule (apply_div_const_magic_s32_finish (Opcode.Sdiv) _numerator _divisor qf)
488      qf)
489
490;; Applying div-const magic for s64.
491
492(decl apply_div_const_magic_s64 (Opcode Value i64) Value)
493(rule (apply_div_const_magic_s64 opcode numerator divisor)
494      (apply_div_const_magic_s64_inner opcode numerator divisor (div_const_magic_s64 divisor)))
495
496;; q0 = iconst.i64 mul_by
497;; q1 = smulhi numerator, q0
498(decl apply_div_const_magic_s64_inner (Opcode Value i64 DivConstMagicS64) Value)
499(rule (apply_div_const_magic_s64_inner opcode
500                                       numerator
501                                       divisor
502                                       magic @ (DivConstMagicS64.S64 mul_by _shift_by))
503      (let ((q0 Value (iconst_s $I64 mul_by))
504            (q1 Value (smulhi $I64 numerator q0)))
505        (apply_div_const_magic_s64_add_sub opcode numerator divisor magic q1)))
506
507;; q2 = if divisor > 0 && mul_by < 0 {
508;;     iadd q1, numerator
509;; } else if divisor < 0 && mul_by > 0 {
510;;     isub q1, numerator
511;; } else {
512;;     q1
513;; };
514(decl apply_div_const_magic_s64_add_sub (Opcode Value i64 DivConstMagicS64 Value) Value)
515(rule 2 (apply_div_const_magic_s64_add_sub opcode
516                                           numerator
517                                           divisor
518                                           magic @ (DivConstMagicS64.S64 mul_by _shift_by)
519                                           q1)
520      (if-let true (i64_gt divisor 0))
521      (if-let true (i64_lt mul_by 0))
522      (let ((q2 Value (iadd $I64 q1 numerator)))
523        (apply_div_const_magic_s64_shift opcode numerator divisor magic q2)))
524(rule 1 (apply_div_const_magic_s64_add_sub opcode
525                                           numerator
526                                           divisor
527                                           magic @ (DivConstMagicS64.S64 mul_by _shift_by)
528                                           q1)
529      (if-let true (i64_lt divisor 0))
530      (if-let true (i64_gt mul_by 0))
531      (let ((q2 Value (isub $I64 q1 numerator)))
532        (apply_div_const_magic_s64_shift opcode numerator divisor magic q2)))
533(rule 0 (apply_div_const_magic_s64_add_sub opcode
534                                           numerator
535                                           divisor
536                                           magic
537                                           q1)
538      (apply_div_const_magic_s64_shift opcode numerator divisor magic q1))
539
540;; q3 = sshr q2, shift_by
541;; t1 = ushr q3, 63
542;; qf = iadd q3, t1
543(decl apply_div_const_magic_s64_shift (Opcode Value i64 DivConstMagicS64 Value) Value)
544(rule (apply_div_const_magic_s64_shift opcode
545                                       numerator
546                                       divisor
547                                       magic @ (DivConstMagicS64.S64 _mul_by shift_by)
548                                       q2)
549      ;; Note: let other rules clean up `q2` when `shift_by == 0`.
550      (let ((q3 Value (sshr $I64 q2 (iconst_s $I64 shift_by)))
551            (t1 Value (ushr $I64 q3 (iconst_s $I64 63)))
552            (qf Value (iadd $I64 q3 t1)))
553        (apply_div_const_magic_s64_finish opcode numerator divisor qf)))
554
555;; Now `qf` holds the final quotient. If necessary, produce the remainder
556;; instead.
557;;
558;; if Opcode == Srem {
559;;     tt = imul qf, divisor
560;;     isub numerator, tt
561;; } else {
562;;     qf
563;; }
564(decl apply_div_const_magic_s64_finish (Opcode Value i64 Value) Value)
565(rule (apply_div_const_magic_s64_finish (Opcode.Srem) numerator divisor qf)
566      (let ((tt Value (imul $I64 qf (iconst_s $I64 divisor))))
567        (isub $I64 numerator tt)))
568(rule (apply_div_const_magic_s64_finish (Opcode.Sdiv) _numerator _divisor qf)
569      qf)
570