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;;
135;; Recursion: may recurse at most once to reduce reduce 128-bit to 64-bit.
136(decl rec iconst_s (Type i64) Value)
137(extractor (iconst_s ty c) (inst_data_value_tupled (iconst_sextend_etor ty c)))
138(rule 0 (iconst_s ty c)
139    (if-let c_masked (u64_and (i64_cast_unsigned c)
140                              (ty_umax ty)))
141    (if-let c_reextended (i64_sextend_u64 ty c_masked))
142    (if-let true (i64_eq c c_reextended))
143    (iconst ty (imm64 c_masked)))
144(rule 1 (iconst_s $I128 c) (sextend $I128 (iconst_s $I64 c)))
145
146;; Construct an `iconst` from a `u64` or Extract a `u64` from an `iconst`
147;; by treating the constant as unsigned.
148;; When extracting, smaller types get their value zero-extended to 64-bits,
149;; so that `iconst.i8 255` will give you a `255_u64`.
150;; When constructing, the rule will fail if the value cannot be represented in
151;; the target type.
152;;
153;; Recursion: may recurse at most once to reduce reduce 128-bit to 64-bit.
154(decl rec iconst_u (Type u64) Value)
155(extractor (iconst_u ty c) (iconst ty (u64_from_imm64 c)))
156(rule 0 (iconst_u ty c)
157    (if-let true (u64_lt_eq c (ty_umax ty)))
158    (iconst ty (imm64 c)))
159(rule 1 (iconst_u $I128 c) (uextend $I128 (iconst_u $I64 c)))
160
161;; These take `Value`, rather than going through `inst_data_value_tupled`,
162;; because most of the time they want to return the original `Value`, and it
163;; would be a waste to need to re-GVN the instruction data in those cases.
164(decl multi sextend_maybe_etor (Type Value) Value)
165(extern extractor infallible sextend_maybe_etor sextend_maybe_etor)
166(decl multi uextend_maybe_etor (Type Value) Value)
167(extern extractor infallible uextend_maybe_etor uextend_maybe_etor)
168
169;; Match or Construct a possibly-`uextend`ed value.
170;; Gives the extended-to type and inner value when matching something that was
171;; extended, or the input value and its type when the value isn't an extension.
172;; Useful to write a single pattern that can match things that may or may not
173;; have undergone C's "usual arithmetic conversions".
174;; When generating values, extending to the same type is invalid CLIF,
175;; so this avoids doing that where there's no extension actually needed.
176(decl uextend_maybe (Type Value) Value)
177(extractor (uextend_maybe ty val) (uextend_maybe_etor ty val))
178(rule 0 (uextend_maybe ty val) (uextend ty val))
179(rule 1 (uextend_maybe ty val@(value_type ty)) val)
180
181;; Same as `uextend_maybe` above, just for `sextend`.
182(decl sextend_maybe (Type Value) Value)
183(extractor (sextend_maybe ty val) (sextend_maybe_etor ty val))
184(rule 0 (sextend_maybe ty val) (sextend ty val))
185(rule 1 (sextend_maybe ty val@(value_type ty)) val)
186
187;;;;;; Helper CLIF Extractors ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
188
189(decl eq (Type Value Value) Value)
190(extractor (eq ty x y) (icmp ty (IntCC.Equal) x y))
191
192(decl ne (Type Value Value) Value)
193(extractor (ne ty x y) (icmp ty (IntCC.NotEqual) x y))
194
195(decl ult (Type Value Value) Value)
196(extractor (ult ty x y) (icmp ty (IntCC.UnsignedLessThan) x y))
197
198(decl ule (Type Value Value) Value)
199(extractor (ule ty x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
200
201(decl ugt (Type Value Value) Value)
202(extractor (ugt ty x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
203
204(decl uge (Type Value Value) Value)
205(extractor (uge ty x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
206
207(decl slt (Type Value Value) Value)
208(extractor (slt ty x y) (icmp ty (IntCC.SignedLessThan) x y))
209
210(decl sle (Type Value Value) Value)
211(extractor (sle ty x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
212
213(decl sgt (Type Value Value) Value)
214(extractor (sgt ty x y) (icmp ty (IntCC.SignedGreaterThan) x y))
215
216(decl sge (Type Value Value) Value)
217(extractor (sge ty x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
218
219;;;;;; Division-By-Constant Helpers ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
220
221(decl pure i64_is_negative_power_of_two (i64) bool)
222(rule (i64_is_negative_power_of_two x)
223      (u64_is_power_of_two (i64_cast_unsigned (i64_wrapping_neg x))))
224
225(decl pure i64_is_any_sign_power_of_two (i64) bool)
226(rule 2 (i64_is_any_sign_power_of_two x)
227      (if-let true (u64_is_power_of_two (i64_cast_unsigned x)))
228      true)
229(rule 1 (i64_is_any_sign_power_of_two x)
230      (if-let true (i64_is_negative_power_of_two x))
231      true)
232(rule 0 (i64_is_any_sign_power_of_two _) false)
233
234(type DivConstMagicU32 (enum (U32 (mul_by u32)
235                                  (do_add bool)
236                                  (shift_by u32))))
237(type DivConstMagicU64 (enum (U64 (mul_by u64)
238                                  (do_add bool)
239                                  (shift_by u32))))
240(type DivConstMagicS32 (enum (S32 (mul_by i32)
241                                  (shift_by u32))))
242(type DivConstMagicS64 (enum (S64 (mul_by i64)
243                                  (shift_by u32))))
244
245;; Extern magic-const constructors and accessors.
246
247(decl div_const_magic_u32 (u32) DivConstMagicU32)
248(extern constructor div_const_magic_u32 div_const_magic_u32)
249
250(decl div_const_magic_u64 (u64) DivConstMagicU64)
251(extern constructor div_const_magic_u64 div_const_magic_u64)
252
253(decl div_const_magic_s32 (i32) DivConstMagicS32)
254(extern constructor div_const_magic_s32 div_const_magic_s32)
255
256(decl div_const_magic_s64 (i64) DivConstMagicS64)
257(extern constructor div_const_magic_s64 div_const_magic_s64)
258
259;; Applying div-const magic for u32.
260(decl apply_div_const_magic_u32 (Opcode Value u32) Value)
261(rule (apply_div_const_magic_u32 opcode numerator divisor)
262      (apply_div_const_magic_u32_inner opcode numerator divisor (div_const_magic_u32 divisor)))
263
264;; q0 = umuli numerator, mul_by
265(decl apply_div_const_magic_u32_inner (Opcode Value u32 DivConstMagicU32) Value)
266(rule (apply_div_const_magic_u32_inner opcode
267                                       numerator
268                                       divisor
269                                       magic @ (DivConstMagicU32.U32 mul_by _do_add _shift_by))
270      (let ((q0 Value (umulhi $I32 numerator (iconst_u $I32 mul_by))))
271        (apply_div_const_magic_u32_maybe_add opcode numerator divisor magic q0)))
272
273;; qf = if do_add {
274;;     q1 = isub numerator, q0
275;;     q2 = ushr q1, 1
276;;     q3 = iadd q0, q2
277;;     maybe_shift(q3)
278;; } else {
279;;     ushr q0, shift_by
280;; };
281(decl apply_div_const_magic_u32_maybe_add (Opcode Value u32 DivConstMagicU32 Value) Value)
282(rule (apply_div_const_magic_u32_maybe_add opcode
283                                           numerator
284                                           divisor
285                                           magic @ (DivConstMagicU32.U32 _mul_by true _shift_by)
286                                           q0)
287      (let ((q1 Value (isub $I32 numerator q0))
288            (q2 Value (ushr $I32 q1 (iconst_u $I32 1)))
289            (q3 Value (iadd $I32 q0 q2)))
290        (apply_div_const_magic_u32_maybe_shift opcode numerator divisor magic q3)))
291(rule (apply_div_const_magic_u32_maybe_add opcode
292                                           numerator
293                                           divisor
294                                           magic @ (DivConstMagicU32.U32 _mul_by false shift_by)
295                                           q0)
296      (let ((q3 Value (ushr $I32 q0 (iconst_u $I32 shift_by))))
297        (apply_div_const_magic_u32_finish opcode numerator divisor q3)))
298
299;; qf = if shift_by == 0 {
300;;     q3
301;; } else {
302;;     ushr q3, shift_by - 1
303;; };
304(decl apply_div_const_magic_u32_maybe_shift (Opcode Value u32 DivConstMagicU32 Value) Value)
305(rule 2 (apply_div_const_magic_u32_maybe_shift opcode
306                                                          numerator
307                                                          divisor
308                                                          (DivConstMagicU32.U32 _mul_by _do_add 0)
309                                                          q3)
310      (apply_div_const_magic_u32_finish opcode numerator divisor q3))
311(rule 1 (apply_div_const_magic_u32_maybe_shift opcode
312                                               numerator
313                                               divisor
314                                               (DivConstMagicU32.U32 _mul_by
315                                                                     _do_add
316                                                                     (u32_extract_non_zero shift_by))
317                                               q3)
318      (let ((qf Value (ushr $I32 q3 (iconst_u $I32 (u32_sub shift_by 1)))))
319        (apply_div_const_magic_u32_finish opcode numerator divisor qf)))
320
321;; Now `qf` holds the final quotient. If necessary calculate the remainder
322;; instead.
323;;
324;; if Opcode == Urem {
325;;     tt = imul qf, divisor
326;;     isub numerator, tt
327;; } else {
328;;     qf
329;; }
330(decl apply_div_const_magic_u32_finish (Opcode Value u32 Value) Value)
331(rule (apply_div_const_magic_u32_finish (Opcode.Udiv) _ _ qf) qf)
332(rule (apply_div_const_magic_u32_finish (Opcode.Urem) numerator divisor qf)
333      (let ((tt Value (imul $I32 qf (iconst_u $I32 divisor))))
334        (isub $I32 numerator tt)))
335
336;; Applying div-const magic for u64.
337(decl apply_div_const_magic_u64 (Opcode Value u64) Value)
338(rule (apply_div_const_magic_u64 opcode numerator divisor)
339      (apply_div_const_magic_u64_inner opcode numerator divisor (div_const_magic_u64 divisor)))
340
341;; q0 = umuli numerator, mul_by
342(decl apply_div_const_magic_u64_inner (Opcode Value u64 DivConstMagicU64) Value)
343(rule (apply_div_const_magic_u64_inner opcode
344                                       numerator
345                                       divisor
346                                       magic @ (DivConstMagicU64.U64 mul_by _do_add _shift_by))
347      (let ((q0 Value (umulhi $I64 numerator (iconst_u $I64 mul_by))))
348        (apply_div_const_magic_u64_maybe_add opcode numerator divisor magic q0)))
349
350;; qf = if do_add {
351;;     q1 = isub numerator, q0
352;;     q2 = ushr q1, 1
353;;     q3 = iadd q0, q2
354;;     maybe_shift(q3)
355;; } else {
356;;     ushr q0, shift_by
357;; };
358(decl apply_div_const_magic_u64_maybe_add (Opcode Value u64 DivConstMagicU64 Value) Value)
359(rule (apply_div_const_magic_u64_maybe_add opcode
360                                           numerator
361                                           divisor
362                                           magic @ (DivConstMagicU64.U64 _mul_by true _shift_by)
363                                           q0)
364      (let ((q1 Value (isub $I64 numerator q0))
365            (q2 Value (ushr $I64 q1 (iconst_u $I64 1)))
366            (q3 Value (iadd $I64 q0 q2)))
367        (apply_div_const_magic_u64_maybe_shift opcode numerator divisor magic q3)))
368(rule (apply_div_const_magic_u64_maybe_add opcode
369                                           numerator
370                                           divisor
371                                           magic @ (DivConstMagicU64.U64 _mul_by false shift_by)
372                                           q0)
373      (let ((q3 Value (ushr $I64 q0 (iconst_u $I64 shift_by))))
374        (apply_div_const_magic_u64_finish opcode numerator divisor q3)))
375
376;; qf = if shift_by == 0 {
377;;     q3
378;; } else {
379;;     ushr q3, shift_by - 1
380;; };
381(decl apply_div_const_magic_u64_maybe_shift (Opcode Value u64 DivConstMagicU64 Value) Value)
382(rule 2 (apply_div_const_magic_u64_maybe_shift opcode
383                                                          numerator
384                                                          divisor
385                                                          (DivConstMagicU64.U64 _mul_by _do_add 0)
386                                                          q3)
387      (apply_div_const_magic_u64_finish opcode numerator divisor q3))
388(rule 1 (apply_div_const_magic_u64_maybe_shift opcode
389                                               numerator
390                                               divisor
391                                               (DivConstMagicU64.U64 _mul_by
392                                                                     _do_add
393                                                                     (u32_extract_non_zero shift_by))
394                                               q3)
395      (let ((qf Value (ushr $I64 q3 (iconst_u $I64 (u64_sub shift_by 1)))))
396        (apply_div_const_magic_u64_finish opcode numerator divisor qf)))
397
398;; Now `qf` holds the final quotient. If necessary calculate the remainder
399;; instead.
400;;
401;; if Opcode == Urem {
402;;     tt = imul qf, divisor
403;;     isub numerator, tt
404;; } else {
405;;     qf
406;; }
407(decl apply_div_const_magic_u64_finish (Opcode Value u64 Value) Value)
408(rule (apply_div_const_magic_u64_finish (Opcode.Udiv) _ _ qf) qf)
409(rule (apply_div_const_magic_u64_finish (Opcode.Urem) numerator divisor qf)
410      (let ((tt Value (imul $I64 qf (iconst_u $I64 divisor))))
411        (isub $I64 numerator tt)))
412
413;; Applying div-const magic for s32.
414
415(decl apply_div_const_magic_s32 (Opcode Value i32) Value)
416(rule (apply_div_const_magic_s32 opcode numerator divisor)
417      (apply_div_const_magic_s32_inner opcode numerator divisor (div_const_magic_s32 divisor)))
418
419;; q0 = iconst.i32 mul_by
420;; q1 = smulhi numerator, q0
421(decl apply_div_const_magic_s32_inner (Opcode Value i32 DivConstMagicS32) Value)
422(rule (apply_div_const_magic_s32_inner opcode
423                                       numerator
424                                       divisor
425                                       magic @ (DivConstMagicS32.S32 mul_by _shift_by))
426      (let ((q0 Value (iconst_s $I32 mul_by))
427            (q1 Value (smulhi $I32 numerator q0)))
428        (apply_div_const_magic_s32_add_sub opcode numerator divisor magic q1)))
429
430;; q2 = if divisor > 0 && mul_by < 0 {
431;;     iadd q1, numerator
432;; } else if divisor < 0 && mul_by > 0 {
433;;     isub q1, numerator
434;; } else {
435;;     q1
436;; };
437(decl apply_div_const_magic_s32_add_sub (Opcode Value i32 DivConstMagicS32 Value) Value)
438(rule 2 (apply_div_const_magic_s32_add_sub opcode
439                                           numerator
440                                           divisor
441                                           magic @ (DivConstMagicS32.S32 mul_by _shift_by)
442                                           q1)
443      (if-let true (i32_gt divisor 0))
444      (if-let true (i32_lt mul_by 0))
445      (let ((q2 Value (iadd $I32 q1 numerator)))
446        (apply_div_const_magic_s32_shift opcode numerator divisor magic q2)))
447(rule 1 (apply_div_const_magic_s32_add_sub opcode
448                                           numerator
449                                           divisor
450                                           magic @ (DivConstMagicS32.S32 mul_by _shift_by)
451                                           q1)
452      (if-let true (i32_lt divisor 0))
453      (if-let true (i32_gt mul_by 0))
454      (let ((q2 Value (isub $I32 q1 numerator)))
455        (apply_div_const_magic_s32_shift opcode numerator divisor magic q2)))
456(rule 0 (apply_div_const_magic_s32_add_sub opcode
457                                           numerator
458                                           divisor
459                                           magic
460                                           q1)
461      (apply_div_const_magic_s32_shift opcode numerator divisor magic q1))
462
463;; q3 = sshr q2, shift_by
464;; t1 = ushr q3, 31
465;; qf = iadd q3, t1
466(decl apply_div_const_magic_s32_shift (Opcode Value i32 DivConstMagicS32 Value) Value)
467(rule (apply_div_const_magic_s32_shift opcode
468                                       numerator
469                                       divisor
470                                       magic @ (DivConstMagicS32.S32 _mul_by shift_by)
471                                       q2)
472      ;; Note: let other rules clean up `q2` when `shift_by == 0`.
473      (let ((q3 Value (sshr $I32 q2 (iconst_s $I32 shift_by)))
474            (t1 Value (ushr $I32 q3 (iconst_s $I32 31)))
475            (qf Value (iadd $I32 q3 t1)))
476        (apply_div_const_magic_s32_finish opcode numerator divisor qf)))
477
478;; Now `qf` holds the final quotient. If necessary, produce the remainder
479;; instead.
480;;
481;; if Opcode == Srem {
482;;     tt = imul qf, divisor
483;;     isub numerator, tt
484;; } else {
485;;     qf
486;; }
487(decl apply_div_const_magic_s32_finish (Opcode Value i32 Value) Value)
488(rule (apply_div_const_magic_s32_finish (Opcode.Srem) numerator divisor qf)
489      (let ((tt Value (imul $I32 qf (iconst_s $I32 divisor))))
490        (isub $I32 numerator tt)))
491(rule (apply_div_const_magic_s32_finish (Opcode.Sdiv) _numerator _divisor qf)
492      qf)
493
494;; Applying div-const magic for s64.
495
496(decl apply_div_const_magic_s64 (Opcode Value i64) Value)
497(rule (apply_div_const_magic_s64 opcode numerator divisor)
498      (apply_div_const_magic_s64_inner opcode numerator divisor (div_const_magic_s64 divisor)))
499
500;; q0 = iconst.i64 mul_by
501;; q1 = smulhi numerator, q0
502(decl apply_div_const_magic_s64_inner (Opcode Value i64 DivConstMagicS64) Value)
503(rule (apply_div_const_magic_s64_inner opcode
504                                       numerator
505                                       divisor
506                                       magic @ (DivConstMagicS64.S64 mul_by _shift_by))
507      (let ((q0 Value (iconst_s $I64 mul_by))
508            (q1 Value (smulhi $I64 numerator q0)))
509        (apply_div_const_magic_s64_add_sub opcode numerator divisor magic q1)))
510
511;; q2 = if divisor > 0 && mul_by < 0 {
512;;     iadd q1, numerator
513;; } else if divisor < 0 && mul_by > 0 {
514;;     isub q1, numerator
515;; } else {
516;;     q1
517;; };
518(decl apply_div_const_magic_s64_add_sub (Opcode Value i64 DivConstMagicS64 Value) Value)
519(rule 2 (apply_div_const_magic_s64_add_sub opcode
520                                           numerator
521                                           divisor
522                                           magic @ (DivConstMagicS64.S64 mul_by _shift_by)
523                                           q1)
524      (if-let true (i64_gt divisor 0))
525      (if-let true (i64_lt mul_by 0))
526      (let ((q2 Value (iadd $I64 q1 numerator)))
527        (apply_div_const_magic_s64_shift opcode numerator divisor magic q2)))
528(rule 1 (apply_div_const_magic_s64_add_sub opcode
529                                           numerator
530                                           divisor
531                                           magic @ (DivConstMagicS64.S64 mul_by _shift_by)
532                                           q1)
533      (if-let true (i64_lt divisor 0))
534      (if-let true (i64_gt mul_by 0))
535      (let ((q2 Value (isub $I64 q1 numerator)))
536        (apply_div_const_magic_s64_shift opcode numerator divisor magic q2)))
537(rule 0 (apply_div_const_magic_s64_add_sub opcode
538                                           numerator
539                                           divisor
540                                           magic
541                                           q1)
542      (apply_div_const_magic_s64_shift opcode numerator divisor magic q1))
543
544;; q3 = sshr q2, shift_by
545;; t1 = ushr q3, 63
546;; qf = iadd q3, t1
547(decl apply_div_const_magic_s64_shift (Opcode Value i64 DivConstMagicS64 Value) Value)
548(rule (apply_div_const_magic_s64_shift opcode
549                                       numerator
550                                       divisor
551                                       magic @ (DivConstMagicS64.S64 _mul_by shift_by)
552                                       q2)
553      ;; Note: let other rules clean up `q2` when `shift_by == 0`.
554      (let ((q3 Value (sshr $I64 q2 (iconst_s $I64 shift_by)))
555            (t1 Value (ushr $I64 q3 (iconst_s $I64 63)))
556            (qf Value (iadd $I64 q3 t1)))
557        (apply_div_const_magic_s64_finish opcode numerator divisor qf)))
558
559;; Now `qf` holds the final quotient. If necessary, produce the remainder
560;; instead.
561;;
562;; if Opcode == Srem {
563;;     tt = imul qf, divisor
564;;     isub numerator, tt
565;; } else {
566;;     qf
567;; }
568(decl apply_div_const_magic_s64_finish (Opcode Value i64 Value) Value)
569(rule (apply_div_const_magic_s64_finish (Opcode.Srem) numerator divisor qf)
570      (let ((tt Value (imul $I64 qf (iconst_s $I64 divisor))))
571        (isub $I64 numerator tt)))
572(rule (apply_div_const_magic_s64_finish (Opcode.Sdiv) _numerator _divisor qf)
573      qf)
574