1;; Simplifications for C++20's `<=>` "spaceship" operator, aka Rust's `Ord::cmp`.
2;;
3;; There's no cranelift instruction for this, nor usually a machine instruction.
4;; Inspired by <https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign>
5;; we canonicalize the various implementations of `x <=> y` to `(x > y) - (x < y)`.
6
7;; Unfortunately, there's at least 3!×2 reasonable ways to write this as nested
8;; selects, and no broad agreement which is the best -- notably Rust 1.74 and
9;; Clang 17 use different sequences -- so we just match all of them.
10
11;; x < y ? -1 : x == y ? 0 : +1
12;; x < y ? -1 : x != y ? +1 : 0
13(rule (simplify (select ty (ult rty x y)
14                           (iconst_s ty -1)
15                           (uextend_maybe ty (ne rty x y))))
16      (sextend_maybe ty (spaceship_u rty x y)))
17;; x < y ? -1 : x <= y ? 0 : +1
18;; x < y ? -1 : x > y ? +1 : 0
19(rule (simplify (select ty (ult rty x y)
20                           (iconst_s ty -1)
21                           (uextend_maybe ty (ugt rty x y))))
22      (sextend_maybe ty (spaceship_u rty x y)))
23
24;; x == y ? 0 : x < y ? -1 : +1
25(rule (simplify (select ty (eq rty x y)
26                           (iconst_s ty 0)
27                           (select ty (ult rty x y)
28                                      (iconst_s ty -1)
29                                      (iconst_s ty 1))))
30      (sextend_maybe ty (spaceship_u rty x y)))
31;; x == y ? 0 : x <= y ? -1 : +1
32(rule (simplify (select ty (eq rty x y)
33                           (iconst_s ty 0)
34                           (select ty (ule rty x y)
35                                      (iconst_s ty -1)
36                                      (iconst_s ty 1))))
37      (sextend_maybe ty (spaceship_u rty x y)))
38;; x == y ? 0 : x > y ? +1 : -1
39(rule (simplify (select ty (eq rty x y)
40                           (iconst_s ty 0)
41                           (select ty (ugt rty x y)
42                                      (iconst_s ty 1)
43                                      (iconst_s ty -1))))
44      (sextend_maybe ty (spaceship_u rty x y)))
45;; x == y ? 0 : x >= y ? +1 : -1
46(rule (simplify (select ty (eq rty x y)
47                           (iconst_s ty 0)
48                           (select ty (uge rty x y)
49                                      (iconst_s ty 1)
50                                      (iconst_s ty -1))))
51      (sextend_maybe ty (spaceship_u rty x y)))
52
53;; x > y ? 1 : x < y ? -1 : 0
54;; x > y ? 1 : x >= y ? 0 : -1
55(rule (simplify (select ty (ugt rty x y)
56                           (iconst_s ty 1)
57                           (ineg rty (ult rty x y))))
58      (sextend_maybe ty (spaceship_u rty x y)))
59(rule (simplify (select ty (ugt rty x y)
60                           (iconst_s ty 1)
61                           (bmask ty (ult rty x y))))
62      (sextend_maybe ty (spaceship_u rty x y)))
63;; x > y ? 1 : x != y ? -1 : 0
64;; x > y ? 1 : x == y ? 0 : -1
65(rule (simplify (select ty (ugt rty x y)
66                           (iconst_s ty 1)
67                           (ineg rty (ne rty x y))))
68      (sextend_maybe ty (spaceship_u rty x y)))
69(rule (simplify (select ty (ugt rty x y)
70                           (iconst_s ty 1)
71                           (bmask ty (ne rty x y))))
72      (sextend_maybe ty (spaceship_u rty x y)))
73
74;; Same, but for signed comparisons this time
75
76;; x < y ? -1 : x == y ? 0 : +1
77;; x < y ? -1 : x != y ? +1 : 0
78(rule (simplify (select ty (slt rty x y)
79                           (iconst_s ty -1)
80                           (uextend_maybe ty (ne rty x y))))
81      (sextend_maybe ty (spaceship_s rty x y)))
82;; x < y ? -1 : x <= y ? 0 : +1
83;; x < y ? -1 : x > y ? +1 : 0
84(rule (simplify (select ty (slt rty x y)
85                           (iconst_s ty -1)
86                           (uextend_maybe ty (sgt rty x y))))
87      (sextend_maybe ty (spaceship_s rty x y)))
88
89;; x == y ? 0 : x < y ? -1 : +1
90(rule (simplify (select ty (eq rty x y)
91                           (iconst_s ty 0)
92                           (select ty (slt rty x y)
93                                      (iconst_s ty -1)
94                                      (iconst_s ty 1))))
95      (sextend_maybe ty (spaceship_s rty x y)))
96;; x == y ? 0 : x <= y ? -1 : +1
97(rule (simplify (select ty (eq rty x y)
98                           (iconst_s ty 0)
99                           (select ty (sle rty x y)
100                                      (iconst_s ty -1)
101                                      (iconst_s ty 1))))
102      (sextend_maybe ty (spaceship_s rty x y)))
103;; x == y ? 0 : x > y ? +1 : -1
104(rule (simplify (select ty (eq rty x y)
105                           (iconst_s ty 0)
106                           (select ty (sgt rty x y)
107                                      (iconst_s ty 1)
108                                      (iconst_s ty -1))))
109      (sextend_maybe ty (spaceship_s rty x y)))
110;; x == y ? 0 : x >= y ? +1 : -1
111(rule (simplify (select ty (eq rty x y)
112                           (iconst_s ty 0)
113                           (select ty (sge rty x y)
114                                      (iconst_s ty 1)
115                                      (iconst_s ty -1))))
116      (sextend_maybe ty (spaceship_s rty x y)))
117
118;; x > y ? 1 : x < y ? -1 : 0
119;; x > y ? 1 : x >= y ? 0 : -1
120(rule (simplify (select ty (sgt rty x y)
121                           (iconst_s ty 1)
122                           (ineg rty (slt rty x y))))
123      (sextend_maybe ty (spaceship_s rty x y)))
124(rule (simplify (select ty (sgt rty x y)
125                           (iconst_s ty 1)
126                           (bmask ty (slt rty x y))))
127      (sextend_maybe ty (spaceship_s rty x y)))
128;; x > y ? 1 : x != y ? -1 : 0
129;; x > y ? 1 : x == y ? 0 : -1
130(rule (simplify (select ty (sgt rty x y)
131                           (iconst_s ty 1)
132                           (ineg rty (ne rty x y))))
133      (sextend_maybe ty (spaceship_s rty x y)))
134(rule (simplify (select ty (sgt rty x y)
135                           (iconst_s ty 1)
136                           (bmask ty (ne rty x y))))
137      (sextend_maybe ty (spaceship_s rty x y)))
138
139;; Then once we have it normalized, we can apply some basic simplifications.
140;; For example, a derived `PartialOrd::lt` on a newtype in Rust will essentially
141;; emit `(a <=> b) < 0`, and replacing that with `a < b` can really help.
142;; `icmp.isle` prefers comparing against zero so we don't need to worry about
143;; also matching things like `(a <=> b) < 1` or `(a <=> b) <= -1`.
144
145;; (a <=> b) == 0 --> a == b
146(rule (simplify (eq _ (spaceship_s ty x y) (iconst_s _ 0)))
147      (eq ty x y))
148(rule (simplify (eq _ (spaceship_u ty x y) (iconst_s _ 0)))
149      (eq ty x y))
150;; (a <=> b) != 0 --> a != b
151(rule (simplify (ne _ (spaceship_s ty x y) (iconst_s _ 0)))
152      (ne ty x y))
153(rule (simplify (ne _ (spaceship_u ty x y) (iconst_s _ 0)))
154      (ne ty x y))
155
156;; (a <=> b) < 0 --> a < b
157(rule (simplify (slt _ (spaceship_s ty x y) (iconst_s _ 0)))
158      (slt ty x y))
159(rule (simplify (slt _ (spaceship_u ty x y) (iconst_s _ 0)))
160      (ult ty x y))
161;; (a <=> b) <= 0 --> a <= b
162(rule (simplify (sle _ (spaceship_s ty x y) (iconst_s _ 0)))
163      (sle ty x y))
164(rule (simplify (sle _ (spaceship_u ty x y) (iconst_s _ 0)))
165      (ule ty x y))
166;; (a <=> b) > 0 --> a > b
167(rule (simplify (sgt _ (spaceship_s ty x y) (iconst_s _ 0)))
168      (sgt ty x y))
169(rule (simplify (sgt _ (spaceship_u ty x y) (iconst_s _ 0)))
170      (ugt ty x y))
171;; (a <=> b) >= 0 --> a >= b
172(rule (simplify (sge _ (spaceship_s ty x y) (iconst_s _ 0)))
173      (sge ty x y))
174(rule (simplify (sge _ (spaceship_u ty x y) (iconst_s _ 0)))
175      (uge ty x y))
176
177;; Rust's `sort_by` uses `compare(a, b) == Less`, which the general icmp rules
178;; can't simplify to a comparison against zero, so catch things like that too.
179(rule (simplify (eq _ (spaceship_s ty x y) (iconst_s _ -1)))
180      (slt ty x y))
181(rule (simplify (eq _ (spaceship_u ty x y) (iconst_s _ -1)))
182      (ult ty x y))
183(rule (simplify (ne _ (spaceship_s ty x y) (iconst_s _ -1)))
184      (sge ty x y))
185(rule (simplify (ne _ (spaceship_u ty x y) (iconst_s _ -1)))
186      (uge ty x y))
187(rule (simplify (eq _ (spaceship_s ty x y) (iconst_s _ 1)))
188      (sgt ty x y))
189(rule (simplify (eq _ (spaceship_u ty x y) (iconst_s _ 1)))
190      (ugt ty x y))
191(rule (simplify (ne _ (spaceship_s ty x y) (iconst_s _ 1)))
192      (sle ty x y))
193(rule (simplify (ne _ (spaceship_u ty x y) (iconst_s _ 1)))
194      (ule ty x y))
195