1 use crate::cdsl::ast::{var, ExprBuilder, Literal};
2 use crate::cdsl::instructions::{Bindable, Instruction, InstructionGroup};
3 use crate::cdsl::xform::{TransformGroupBuilder, TransformGroups};
4
5 use crate::shared::immediates::Immediates;
6 use crate::shared::types::Float::{F32, F64};
7 use crate::shared::types::Int::{I128, I16, I32, I64, I8};
8 use cranelift_codegen_shared::condcodes::{CondCode, IntCC};
9
10 #[allow(clippy::many_single_char_names, clippy::cognitive_complexity)]
define(insts: &InstructionGroup, imm: &Immediates) -> TransformGroups11 pub(crate) fn define(insts: &InstructionGroup, imm: &Immediates) -> TransformGroups {
12 let mut narrow = TransformGroupBuilder::new(
13 "narrow",
14 r#"
15 Legalize instructions by narrowing.
16
17 The transformations in the 'narrow' group work by expressing
18 instructions in terms of smaller types. Operations on vector types are
19 expressed in terms of vector types with fewer lanes, and integer
20 operations are expressed in terms of smaller integer types.
21 "#,
22 );
23
24 let mut widen = TransformGroupBuilder::new(
25 "widen",
26 r#"
27 Legalize instructions by widening.
28
29 The transformations in the 'widen' group work by expressing
30 instructions in terms of larger types.
31 "#,
32 );
33
34 let mut expand = TransformGroupBuilder::new(
35 "expand",
36 r#"
37 Legalize instructions by expansion.
38
39 Rewrite instructions in terms of other instructions, generally
40 operating on the same types as the original instructions.
41 "#,
42 );
43
44 // List of instructions.
45 let band = insts.by_name("band");
46 let band_imm = insts.by_name("band_imm");
47 let band_not = insts.by_name("band_not");
48 let bint = insts.by_name("bint");
49 let bitrev = insts.by_name("bitrev");
50 let bnot = insts.by_name("bnot");
51 let bor = insts.by_name("bor");
52 let bor_imm = insts.by_name("bor_imm");
53 let bor_not = insts.by_name("bor_not");
54 let brnz = insts.by_name("brnz");
55 let brz = insts.by_name("brz");
56 let br_icmp = insts.by_name("br_icmp");
57 let br_table = insts.by_name("br_table");
58 let bxor = insts.by_name("bxor");
59 let bxor_imm = insts.by_name("bxor_imm");
60 let bxor_not = insts.by_name("bxor_not");
61 let cls = insts.by_name("cls");
62 let clz = insts.by_name("clz");
63 let ctz = insts.by_name("ctz");
64 let copy = insts.by_name("copy");
65 let fabs = insts.by_name("fabs");
66 let f32const = insts.by_name("f32const");
67 let f64const = insts.by_name("f64const");
68 let fcopysign = insts.by_name("fcopysign");
69 let fcvt_from_sint = insts.by_name("fcvt_from_sint");
70 let fneg = insts.by_name("fneg");
71 let iadd = insts.by_name("iadd");
72 let iadd_cin = insts.by_name("iadd_cin");
73 let iadd_cout = insts.by_name("iadd_cout");
74 let iadd_carry = insts.by_name("iadd_carry");
75 let iadd_ifcin = insts.by_name("iadd_ifcin");
76 let iadd_ifcout = insts.by_name("iadd_ifcout");
77 let iadd_imm = insts.by_name("iadd_imm");
78 let icmp = insts.by_name("icmp");
79 let icmp_imm = insts.by_name("icmp_imm");
80 let iconcat = insts.by_name("iconcat");
81 let iconst = insts.by_name("iconst");
82 let ifcmp = insts.by_name("ifcmp");
83 let ifcmp_imm = insts.by_name("ifcmp_imm");
84 let imul = insts.by_name("imul");
85 let imul_imm = insts.by_name("imul_imm");
86 let ireduce = insts.by_name("ireduce");
87 let irsub_imm = insts.by_name("irsub_imm");
88 let ishl = insts.by_name("ishl");
89 let ishl_imm = insts.by_name("ishl_imm");
90 let isplit = insts.by_name("isplit");
91 let istore8 = insts.by_name("istore8");
92 let istore16 = insts.by_name("istore16");
93 let isub = insts.by_name("isub");
94 let isub_bin = insts.by_name("isub_bin");
95 let isub_bout = insts.by_name("isub_bout");
96 let isub_borrow = insts.by_name("isub_borrow");
97 let isub_ifbin = insts.by_name("isub_ifbin");
98 let isub_ifbout = insts.by_name("isub_ifbout");
99 let jump = insts.by_name("jump");
100 let load = insts.by_name("load");
101 let popcnt = insts.by_name("popcnt");
102 let resumable_trapnz = insts.by_name("resumable_trapnz");
103 let rotl = insts.by_name("rotl");
104 let rotl_imm = insts.by_name("rotl_imm");
105 let rotr = insts.by_name("rotr");
106 let rotr_imm = insts.by_name("rotr_imm");
107 let sdiv = insts.by_name("sdiv");
108 let sdiv_imm = insts.by_name("sdiv_imm");
109 let select = insts.by_name("select");
110 let sextend = insts.by_name("sextend");
111 let sshr = insts.by_name("sshr");
112 let sshr_imm = insts.by_name("sshr_imm");
113 let srem = insts.by_name("srem");
114 let srem_imm = insts.by_name("srem_imm");
115 let store = insts.by_name("store");
116 let udiv = insts.by_name("udiv");
117 let udiv_imm = insts.by_name("udiv_imm");
118 let uextend = insts.by_name("uextend");
119 let uload8 = insts.by_name("uload8");
120 let uload16 = insts.by_name("uload16");
121 let umulhi = insts.by_name("umulhi");
122 let ushr = insts.by_name("ushr");
123 let ushr_imm = insts.by_name("ushr_imm");
124 let urem = insts.by_name("urem");
125 let urem_imm = insts.by_name("urem_imm");
126 let trapif = insts.by_name("trapif");
127 let trapnz = insts.by_name("trapnz");
128 let trapz = insts.by_name("trapz");
129
130 // Custom expansions for memory objects.
131 expand.custom_legalize(insts.by_name("global_value"), "expand_global_value");
132 expand.custom_legalize(insts.by_name("heap_addr"), "expand_heap_addr");
133 expand.custom_legalize(insts.by_name("table_addr"), "expand_table_addr");
134
135 // Custom expansions for calls.
136 expand.custom_legalize(insts.by_name("call"), "expand_call");
137
138 // Custom expansions that need to change the CFG.
139 // TODO: Add sufficient XForm syntax that we don't need to hand-code these.
140 expand.custom_legalize(trapz, "expand_cond_trap");
141 expand.custom_legalize(trapnz, "expand_cond_trap");
142 expand.custom_legalize(resumable_trapnz, "expand_cond_trap");
143 expand.custom_legalize(br_table, "expand_br_table");
144 expand.custom_legalize(select, "expand_select");
145 widen.custom_legalize(select, "expand_select"); // small ints
146
147 // Custom expansions for floating point constants.
148 // These expansions require bit-casting or creating constant pool entries.
149 expand.custom_legalize(f32const, "expand_fconst");
150 expand.custom_legalize(f64const, "expand_fconst");
151
152 // Custom expansions for stack memory accesses.
153 expand.custom_legalize(insts.by_name("stack_load"), "expand_stack_load");
154 expand.custom_legalize(insts.by_name("stack_store"), "expand_stack_store");
155
156 // Custom expansions for small stack memory acccess.
157 widen.custom_legalize(insts.by_name("stack_load"), "expand_stack_load");
158 widen.custom_legalize(insts.by_name("stack_store"), "expand_stack_store");
159
160 // List of variables to reuse in patterns.
161 let x = var("x");
162 let y = var("y");
163 let z = var("z");
164 let a = var("a");
165 let a1 = var("a1");
166 let a2 = var("a2");
167 let a3 = var("a3");
168 let a4 = var("a4");
169 let b = var("b");
170 let b1 = var("b1");
171 let b2 = var("b2");
172 let b3 = var("b3");
173 let b4 = var("b4");
174 let b_in = var("b_in");
175 let b_int = var("b_int");
176 let c = var("c");
177 let c1 = var("c1");
178 let c2 = var("c2");
179 let c3 = var("c3");
180 let c4 = var("c4");
181 let c_in = var("c_in");
182 let c_int = var("c_int");
183 let d = var("d");
184 let d1 = var("d1");
185 let d2 = var("d2");
186 let d3 = var("d3");
187 let d4 = var("d4");
188 let e = var("e");
189 let e1 = var("e1");
190 let e2 = var("e2");
191 let e3 = var("e3");
192 let e4 = var("e4");
193 let f = var("f");
194 let f1 = var("f1");
195 let f2 = var("f2");
196 let xl = var("xl");
197 let xh = var("xh");
198 let yl = var("yl");
199 let yh = var("yh");
200 let al = var("al");
201 let ah = var("ah");
202 let cc = var("cc");
203 let block = var("block");
204 let ptr = var("ptr");
205 let flags = var("flags");
206 let offset = var("off");
207 let vararg = var("vararg");
208
209 narrow.custom_legalize(load, "narrow_load");
210 narrow.custom_legalize(store, "narrow_store");
211
212 // iconst.i64 can't be legalized in the meta langage (because integer literals can't be
213 // embedded as part of arguments), so use a custom legalization for now.
214 narrow.custom_legalize(iconst, "narrow_iconst");
215
216 for &(ty, ty_half) in &[(I128, I64), (I64, I32)] {
217 let inst = uextend.bind(ty).bind(ty_half);
218 narrow.legalize(
219 def!(a = inst(x)),
220 vec![
221 def!(ah = iconst(Literal::constant(&imm.imm64, 0))),
222 def!(a = iconcat(x, ah)),
223 ],
224 );
225 }
226
227 for &(ty, ty_half, shift) in &[(I128, I64, 63), (I64, I32, 31)] {
228 let inst = sextend.bind(ty).bind(ty_half);
229 narrow.legalize(
230 def!(a = inst(x)),
231 vec![
232 def!(ah = sshr_imm(x, Literal::constant(&imm.imm64, shift))), // splat sign bit to whole number
233 def!(a = iconcat(x, ah)),
234 ],
235 );
236 }
237
238 for &bin_op in &[band, bor, bxor, band_not, bor_not, bxor_not] {
239 narrow.legalize(
240 def!(a = bin_op(x, y)),
241 vec![
242 def!((xl, xh) = isplit(x)),
243 def!((yl, yh) = isplit(y)),
244 def!(al = bin_op(xl, yl)),
245 def!(ah = bin_op(xh, yh)),
246 def!(a = iconcat(al, ah)),
247 ],
248 );
249 }
250
251 narrow.legalize(
252 def!(a = bnot(x)),
253 vec![
254 def!((xl, xh) = isplit(x)),
255 def!(al = bnot(xl)),
256 def!(ah = bnot(xh)),
257 def!(a = iconcat(al, ah)),
258 ],
259 );
260
261 narrow.legalize(
262 def!(a = select(c, x, y)),
263 vec![
264 def!((xl, xh) = isplit(x)),
265 def!((yl, yh) = isplit(y)),
266 def!(al = select(c, xl, yl)),
267 def!(ah = select(c, xh, yh)),
268 def!(a = iconcat(al, ah)),
269 ],
270 );
271
272 for &ty in &[I128, I64] {
273 let block = var("block");
274 let block1 = var("block1");
275 let block2 = var("block2");
276
277 narrow.legalize(
278 def!(brz.ty(x, block, vararg)),
279 vec![
280 def!((xl, xh) = isplit(x)),
281 def!(
282 a = icmp_imm(
283 Literal::enumerator_for(&imm.intcc, "eq"),
284 xl,
285 Literal::constant(&imm.imm64, 0)
286 )
287 ),
288 def!(
289 b = icmp_imm(
290 Literal::enumerator_for(&imm.intcc, "eq"),
291 xh,
292 Literal::constant(&imm.imm64, 0)
293 )
294 ),
295 def!(c = band(a, b)),
296 def!(brnz(c, block, vararg)),
297 ],
298 );
299
300 narrow.legalize(
301 def!(brnz.ty(x, block1, vararg)),
302 vec![
303 def!((xl, xh) = isplit(x)),
304 def!(brnz(xl, block1, vararg)),
305 def!(jump(block2, Literal::empty_vararg())),
306 block!(block2),
307 def!(brnz(xh, block1, vararg)),
308 ],
309 );
310 }
311
312 narrow.legalize(
313 def!(a = popcnt.I128(x)),
314 vec![
315 def!((xl, xh) = isplit(x)),
316 def!(e1 = popcnt(xl)),
317 def!(e2 = popcnt(xh)),
318 def!(e3 = iadd(e1, e2)),
319 def!(a = uextend(e3)),
320 ],
321 );
322
323 // TODO(ryzokuken): benchmark this and decide if branching is a faster
324 // approach than evaluating boolean expressions.
325
326 narrow.custom_legalize(icmp_imm, "narrow_icmp_imm");
327
328 let intcc_eq = Literal::enumerator_for(&imm.intcc, "eq");
329 let intcc_ne = Literal::enumerator_for(&imm.intcc, "ne");
330 for &(int_ty, int_ty_half) in &[(I64, I32), (I128, I64)] {
331 narrow.legalize(
332 def!(b = icmp.int_ty(intcc_eq, x, y)),
333 vec![
334 def!((xl, xh) = isplit(x)),
335 def!((yl, yh) = isplit(y)),
336 def!(b1 = icmp.int_ty_half(intcc_eq, xl, yl)),
337 def!(b2 = icmp.int_ty_half(intcc_eq, xh, yh)),
338 def!(b = band(b1, b2)),
339 ],
340 );
341
342 narrow.legalize(
343 def!(b = icmp.int_ty(intcc_ne, x, y)),
344 vec![
345 def!((xl, xh) = isplit(x)),
346 def!((yl, yh) = isplit(y)),
347 def!(b1 = icmp.int_ty_half(intcc_ne, xl, yl)),
348 def!(b2 = icmp.int_ty_half(intcc_ne, xh, yh)),
349 def!(b = bor(b1, b2)),
350 ],
351 );
352
353 use IntCC::*;
354 for cc in &[
355 SignedGreaterThan,
356 SignedGreaterThanOrEqual,
357 SignedLessThan,
358 SignedLessThanOrEqual,
359 UnsignedGreaterThan,
360 UnsignedGreaterThanOrEqual,
361 UnsignedLessThan,
362 UnsignedLessThanOrEqual,
363 ] {
364 let intcc_cc = Literal::enumerator_for(&imm.intcc, cc.to_static_str());
365 let cc1 = Literal::enumerator_for(&imm.intcc, cc.without_equal().to_static_str());
366 let cc2 =
367 Literal::enumerator_for(&imm.intcc, cc.inverse().without_equal().to_static_str());
368 let cc3 = Literal::enumerator_for(&imm.intcc, cc.unsigned().to_static_str());
369 narrow.legalize(
370 def!(b = icmp.int_ty(intcc_cc, x, y)),
371 vec![
372 def!((xl, xh) = isplit(x)),
373 def!((yl, yh) = isplit(y)),
374 // X = cc1 || (!cc2 && cc3)
375 def!(b1 = icmp.int_ty_half(cc1, xh, yh)),
376 def!(b2 = icmp.int_ty_half(cc2, xh, yh)),
377 def!(b3 = icmp.int_ty_half(cc3, xl, yl)),
378 def!(c1 = bnot(b2)),
379 def!(c2 = band(c1, b3)),
380 def!(b = bor(b1, c2)),
381 ],
382 );
383 }
384 }
385
386 // TODO(ryzokuken): explore the perf diff w/ x86_umulx and consider have a
387 // separate legalization for x86.
388 for &ty in &[I64, I128] {
389 narrow.legalize(
390 def!(a = imul.ty(x, y)),
391 vec![
392 def!((xl, xh) = isplit(x)),
393 def!((yl, yh) = isplit(y)),
394 def!(a1 = imul(xh, yl)),
395 def!(a2 = imul(xl, yh)),
396 def!(a3 = iadd(a1, a2)),
397 def!(a4 = umulhi(xl, yl)),
398 def!(ah = iadd(a3, a4)),
399 def!(al = imul(xl, yl)),
400 def!(a = iconcat(al, ah)),
401 ],
402 );
403 }
404
405 let zero = Literal::constant(&imm.imm64, 0);
406 narrow.legalize(
407 def!(a = iadd_imm.I128(x, c)),
408 vec![
409 def!(yh = iconst.I64(zero)),
410 def!(yl = iconst.I64(c)),
411 def!(y = iconcat.I64(yh, yl)),
412 def!(a = iadd(x, y)),
413 ],
414 );
415
416 // Widen instructions with one input operand.
417 for &op in &[bnot, popcnt] {
418 for &int_ty in &[I8, I16] {
419 widen.legalize(
420 def!(a = op.int_ty(b)),
421 vec![
422 def!(x = uextend.I32(b)),
423 def!(z = op.I32(x)),
424 def!(a = ireduce.int_ty(z)),
425 ],
426 );
427 }
428 }
429
430 // Widen instructions with two input operands.
431 let mut widen_two_arg = |signed: bool, op: &Instruction| {
432 for &int_ty in &[I8, I16] {
433 let sign_ext_op = if signed { sextend } else { uextend };
434 widen.legalize(
435 def!(a = op.int_ty(b, c)),
436 vec![
437 def!(x = sign_ext_op.I32(b)),
438 def!(y = sign_ext_op.I32(c)),
439 def!(z = op.I32(x, y)),
440 def!(a = ireduce.int_ty(z)),
441 ],
442 );
443 }
444 };
445
446 for bin_op in &[
447 iadd, isub, imul, udiv, urem, band, bor, bxor, band_not, bor_not, bxor_not,
448 ] {
449 widen_two_arg(false, bin_op);
450 }
451 for bin_op in &[sdiv, srem] {
452 widen_two_arg(true, bin_op);
453 }
454
455 // Widen instructions using immediate operands.
456 let mut widen_imm = |signed: bool, op: &Instruction| {
457 for &int_ty in &[I8, I16] {
458 let sign_ext_op = if signed { sextend } else { uextend };
459 widen.legalize(
460 def!(a = op.int_ty(b, c)),
461 vec![
462 def!(x = sign_ext_op.I32(b)),
463 def!(z = op.I32(x, c)),
464 def!(a = ireduce.int_ty(z)),
465 ],
466 );
467 }
468 };
469
470 for bin_op in &[
471 iadd_imm, imul_imm, udiv_imm, urem_imm, band_imm, bor_imm, bxor_imm, irsub_imm,
472 ] {
473 widen_imm(false, bin_op);
474 }
475 for bin_op in &[sdiv_imm, srem_imm] {
476 widen_imm(true, bin_op);
477 }
478
479 for &(int_ty, num) in &[(I8, 24), (I16, 16)] {
480 let imm = Literal::constant(&imm.imm64, -num);
481
482 widen.legalize(
483 def!(a = clz.int_ty(b)),
484 vec![
485 def!(c = uextend.I32(b)),
486 def!(d = clz.I32(c)),
487 def!(e = iadd_imm(d, imm)),
488 def!(a = ireduce.int_ty(e)),
489 ],
490 );
491
492 widen.legalize(
493 def!(a = cls.int_ty(b)),
494 vec![
495 def!(c = sextend.I32(b)),
496 def!(d = cls.I32(c)),
497 def!(e = iadd_imm(d, imm)),
498 def!(a = ireduce.int_ty(e)),
499 ],
500 );
501 }
502
503 for &(int_ty, num) in &[(I8, 1 << 8), (I16, 1 << 16)] {
504 let num = Literal::constant(&imm.imm64, num);
505 widen.legalize(
506 def!(a = ctz.int_ty(b)),
507 vec![
508 def!(c = uextend.I32(b)),
509 // When `b` is zero, returns the size of x in bits.
510 def!(d = bor_imm(c, num)),
511 def!(e = ctz.I32(d)),
512 def!(a = ireduce.int_ty(e)),
513 ],
514 );
515 }
516
517 // iconst
518 for &int_ty in &[I8, I16] {
519 widen.legalize(
520 def!(a = iconst.int_ty(b)),
521 vec![def!(c = iconst.I32(b)), def!(a = ireduce.int_ty(c))],
522 );
523 }
524
525 for &extend_op in &[uextend, sextend] {
526 // The sign extension operators have two typevars: the result has one and controls the
527 // instruction, then the input has one.
528 let bound = extend_op.bind(I16).bind(I8);
529 widen.legalize(
530 def!(a = bound(b)),
531 vec![def!(c = extend_op.I32(b)), def!(a = ireduce(c))],
532 );
533 }
534
535 widen.legalize(
536 def!(store.I8(flags, a, ptr, offset)),
537 vec![
538 def!(b = uextend.I32(a)),
539 def!(istore8(flags, b, ptr, offset)),
540 ],
541 );
542
543 widen.legalize(
544 def!(store.I16(flags, a, ptr, offset)),
545 vec![
546 def!(b = uextend.I32(a)),
547 def!(istore16(flags, b, ptr, offset)),
548 ],
549 );
550
551 widen.legalize(
552 def!(a = load.I8(flags, ptr, offset)),
553 vec![
554 def!(b = uload8.I32(flags, ptr, offset)),
555 def!(a = ireduce(b)),
556 ],
557 );
558
559 widen.legalize(
560 def!(a = load.I16(flags, ptr, offset)),
561 vec![
562 def!(b = uload16.I32(flags, ptr, offset)),
563 def!(a = ireduce(b)),
564 ],
565 );
566
567 for &int_ty in &[I8, I16] {
568 widen.legalize(
569 def!(br_table.int_ty(x, y, z)),
570 vec![def!(b = uextend.I32(x)), def!(br_table(b, y, z))],
571 );
572 }
573
574 for &int_ty in &[I8, I16] {
575 widen.legalize(
576 def!(a = bint.int_ty(b)),
577 vec![def!(x = bint.I32(b)), def!(a = ireduce.int_ty(x))],
578 );
579 }
580
581 for &int_ty in &[I8, I16] {
582 for &op in &[ishl, ishl_imm, ushr, ushr_imm] {
583 widen.legalize(
584 def!(a = op.int_ty(b, c)),
585 vec![
586 def!(x = uextend.I32(b)),
587 def!(z = op.I32(x, c)),
588 def!(a = ireduce.int_ty(z)),
589 ],
590 );
591 }
592
593 for &op in &[sshr, sshr_imm] {
594 widen.legalize(
595 def!(a = op.int_ty(b, c)),
596 vec![
597 def!(x = sextend.I32(b)),
598 def!(z = op.I32(x, c)),
599 def!(a = ireduce.int_ty(z)),
600 ],
601 );
602 }
603
604 for cc in &["eq", "ne", "ugt", "ult", "uge", "ule"] {
605 let w_cc = Literal::enumerator_for(&imm.intcc, cc);
606 widen.legalize(
607 def!(a = icmp_imm.int_ty(w_cc, b, c)),
608 vec![def!(x = uextend.I32(b)), def!(a = icmp_imm(w_cc, x, c))],
609 );
610 widen.legalize(
611 def!(a = icmp.int_ty(w_cc, b, c)),
612 vec![
613 def!(x = uextend.I32(b)),
614 def!(y = uextend.I32(c)),
615 def!(a = icmp.I32(w_cc, x, y)),
616 ],
617 );
618 }
619
620 for cc in &["sgt", "slt", "sge", "sle"] {
621 let w_cc = Literal::enumerator_for(&imm.intcc, cc);
622 widen.legalize(
623 def!(a = icmp_imm.int_ty(w_cc, b, c)),
624 vec![def!(x = sextend.I32(b)), def!(a = icmp_imm(w_cc, x, c))],
625 );
626
627 widen.legalize(
628 def!(a = icmp.int_ty(w_cc, b, c)),
629 vec![
630 def!(x = sextend.I32(b)),
631 def!(y = sextend.I32(c)),
632 def!(a = icmp(w_cc, x, y)),
633 ],
634 );
635 }
636 }
637
638 for &ty in &[I8, I16] {
639 widen.legalize(
640 def!(brz.ty(x, block, vararg)),
641 vec![def!(a = uextend.I32(x)), def!(brz(a, block, vararg))],
642 );
643
644 widen.legalize(
645 def!(brnz.ty(x, block, vararg)),
646 vec![def!(a = uextend.I32(x)), def!(brnz(a, block, vararg))],
647 );
648 }
649
650 for &(ty_half, ty) in &[(I64, I128), (I32, I64)] {
651 let inst = ireduce.bind(ty_half).bind(ty);
652 expand.legalize(
653 def!(a = inst(x)),
654 vec![def!((b, c) = isplit(x)), def!(a = copy(b))],
655 );
656 }
657
658 // Expand integer operations with carry for RISC architectures that don't have
659 // the flags.
660 let intcc_ult = Literal::enumerator_for(&imm.intcc, "ult");
661 expand.legalize(
662 def!((a, c) = iadd_cout(x, y)),
663 vec![def!(a = iadd(x, y)), def!(c = icmp(intcc_ult, a, x))],
664 );
665
666 let intcc_ugt = Literal::enumerator_for(&imm.intcc, "ugt");
667 expand.legalize(
668 def!((a, b) = isub_bout(x, y)),
669 vec![def!(a = isub(x, y)), def!(b = icmp(intcc_ugt, a, x))],
670 );
671
672 expand.legalize(
673 def!(a = iadd_cin(x, y, c)),
674 vec![
675 def!(a1 = iadd(x, y)),
676 def!(c_int = bint(c)),
677 def!(a = iadd(a1, c_int)),
678 ],
679 );
680
681 expand.legalize(
682 def!(a = isub_bin(x, y, b)),
683 vec![
684 def!(a1 = isub(x, y)),
685 def!(b_int = bint(b)),
686 def!(a = isub(a1, b_int)),
687 ],
688 );
689
690 expand.legalize(
691 def!((a, c) = iadd_carry(x, y, c_in)),
692 vec![
693 def!((a1, c1) = iadd_cout(x, y)),
694 def!(c_int = bint(c_in)),
695 def!((a, c2) = iadd_cout(a1, c_int)),
696 def!(c = bor(c1, c2)),
697 ],
698 );
699
700 expand.legalize(
701 def!((a, b) = isub_borrow(x, y, b_in)),
702 vec![
703 def!((a1, b1) = isub_bout(x, y)),
704 def!(b_int = bint(b_in)),
705 def!((a, b2) = isub_bout(a1, b_int)),
706 def!(b = bor(b1, b2)),
707 ],
708 );
709
710 // Expansion for fcvt_from_sint for smaller integer types.
711 // This uses expand and not widen because the controlling type variable for
712 // this instruction is f32/f64, which is legalized as part of the expand
713 // group.
714 for &dest_ty in &[F32, F64] {
715 for &src_ty in &[I8, I16] {
716 let bound_inst = fcvt_from_sint.bind(dest_ty).bind(src_ty);
717 expand.legalize(
718 def!(a = bound_inst(b)),
719 vec![
720 def!(x = sextend.I32(b)),
721 def!(a = fcvt_from_sint.dest_ty(x)),
722 ],
723 );
724 }
725 }
726
727 // Expansions for immediate operands that are out of range.
728 for &(inst_imm, inst) in &[
729 (iadd_imm, iadd),
730 (imul_imm, imul),
731 (sdiv_imm, sdiv),
732 (udiv_imm, udiv),
733 (srem_imm, srem),
734 (urem_imm, urem),
735 (band_imm, band),
736 (bor_imm, bor),
737 (bxor_imm, bxor),
738 (ifcmp_imm, ifcmp),
739 ] {
740 expand.legalize(
741 def!(a = inst_imm(x, y)),
742 vec![def!(a1 = iconst(y)), def!(a = inst(x, a1))],
743 );
744 }
745
746 expand.legalize(
747 def!(a = irsub_imm(y, x)),
748 vec![def!(a1 = iconst(x)), def!(a = isub(a1, y))],
749 );
750
751 // Rotates and shifts.
752 for &(inst_imm, inst) in &[
753 (rotl_imm, rotl),
754 (rotr_imm, rotr),
755 (ishl_imm, ishl),
756 (sshr_imm, sshr),
757 (ushr_imm, ushr),
758 ] {
759 expand.legalize(
760 def!(a = inst_imm(x, y)),
761 vec![def!(a1 = iconst.I32(y)), def!(a = inst(x, a1))],
762 );
763 }
764
765 expand.legalize(
766 def!(a = icmp_imm(cc, x, y)),
767 vec![def!(a1 = iconst(y)), def!(a = icmp(cc, x, a1))],
768 );
769
770 //# Expansions for *_not variants of bitwise ops.
771 for &(inst_not, inst) in &[(band_not, band), (bor_not, bor), (bxor_not, bxor)] {
772 expand.legalize(
773 def!(a = inst_not(x, y)),
774 vec![def!(a1 = bnot(y)), def!(a = inst(x, a1))],
775 );
776 }
777
778 //# Expand bnot using xor.
779 let minus_one = Literal::constant(&imm.imm64, -1);
780 expand.legalize(
781 def!(a = bnot(x)),
782 vec![def!(y = iconst(minus_one)), def!(a = bxor(x, y))],
783 );
784
785 //# Expand bitrev
786 //# Adapted from Stack Overflow.
787 //# https://stackoverflow.com/questions/746171/most-efficient-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c
788 let imm64_1 = Literal::constant(&imm.imm64, 1);
789 let imm64_2 = Literal::constant(&imm.imm64, 2);
790 let imm64_4 = Literal::constant(&imm.imm64, 4);
791
792 widen.legalize(
793 def!(a = bitrev.I8(x)),
794 vec![
795 def!(a1 = band_imm(x, Literal::constant(&imm.imm64, 0xaa))),
796 def!(a2 = ushr_imm(a1, imm64_1)),
797 def!(a3 = band_imm(x, Literal::constant(&imm.imm64, 0x55))),
798 def!(a4 = ishl_imm(a3, imm64_1)),
799 def!(b = bor(a2, a4)),
800 def!(b1 = band_imm(b, Literal::constant(&imm.imm64, 0xcc))),
801 def!(b2 = ushr_imm(b1, imm64_2)),
802 def!(b3 = band_imm(b, Literal::constant(&imm.imm64, 0x33))),
803 def!(b4 = ishl_imm(b3, imm64_2)),
804 def!(c = bor(b2, b4)),
805 def!(c1 = band_imm(c, Literal::constant(&imm.imm64, 0xf0))),
806 def!(c2 = ushr_imm(c1, imm64_4)),
807 def!(c3 = band_imm(c, Literal::constant(&imm.imm64, 0x0f))),
808 def!(c4 = ishl_imm(c3, imm64_4)),
809 def!(a = bor(c2, c4)),
810 ],
811 );
812
813 let imm64_8 = Literal::constant(&imm.imm64, 8);
814
815 widen.legalize(
816 def!(a = bitrev.I16(x)),
817 vec![
818 def!(a1 = band_imm(x, Literal::constant(&imm.imm64, 0xaaaa))),
819 def!(a2 = ushr_imm(a1, imm64_1)),
820 def!(a3 = band_imm(x, Literal::constant(&imm.imm64, 0x5555))),
821 def!(a4 = ishl_imm(a3, imm64_1)),
822 def!(b = bor(a2, a4)),
823 def!(b1 = band_imm(b, Literal::constant(&imm.imm64, 0xcccc))),
824 def!(b2 = ushr_imm(b1, imm64_2)),
825 def!(b3 = band_imm(b, Literal::constant(&imm.imm64, 0x3333))),
826 def!(b4 = ishl_imm(b3, imm64_2)),
827 def!(c = bor(b2, b4)),
828 def!(c1 = band_imm(c, Literal::constant(&imm.imm64, 0xf0f0))),
829 def!(c2 = ushr_imm(c1, imm64_4)),
830 def!(c3 = band_imm(c, Literal::constant(&imm.imm64, 0x0f0f))),
831 def!(c4 = ishl_imm(c3, imm64_4)),
832 def!(d = bor(c2, c4)),
833 def!(d1 = band_imm(d, Literal::constant(&imm.imm64, 0xff00))),
834 def!(d2 = ushr_imm(d1, imm64_8)),
835 def!(d3 = band_imm(d, Literal::constant(&imm.imm64, 0x00ff))),
836 def!(d4 = ishl_imm(d3, imm64_8)),
837 def!(a = bor(d2, d4)),
838 ],
839 );
840
841 let imm64_16 = Literal::constant(&imm.imm64, 16);
842
843 expand.legalize(
844 def!(a = bitrev.I32(x)),
845 vec![
846 def!(a1 = band_imm(x, Literal::constant(&imm.imm64, 0xaaaa_aaaa))),
847 def!(a2 = ushr_imm(a1, imm64_1)),
848 def!(a3 = band_imm(x, Literal::constant(&imm.imm64, 0x5555_5555))),
849 def!(a4 = ishl_imm(a3, imm64_1)),
850 def!(b = bor(a2, a4)),
851 def!(b1 = band_imm(b, Literal::constant(&imm.imm64, 0xcccc_cccc))),
852 def!(b2 = ushr_imm(b1, imm64_2)),
853 def!(b3 = band_imm(b, Literal::constant(&imm.imm64, 0x3333_3333))),
854 def!(b4 = ishl_imm(b3, imm64_2)),
855 def!(c = bor(b2, b4)),
856 def!(c1 = band_imm(c, Literal::constant(&imm.imm64, 0xf0f0_f0f0))),
857 def!(c2 = ushr_imm(c1, imm64_4)),
858 def!(c3 = band_imm(c, Literal::constant(&imm.imm64, 0x0f0f_0f0f))),
859 def!(c4 = ishl_imm(c3, imm64_4)),
860 def!(d = bor(c2, c4)),
861 def!(d1 = band_imm(d, Literal::constant(&imm.imm64, 0xff00_ff00))),
862 def!(d2 = ushr_imm(d1, imm64_8)),
863 def!(d3 = band_imm(d, Literal::constant(&imm.imm64, 0x00ff_00ff))),
864 def!(d4 = ishl_imm(d3, imm64_8)),
865 def!(e = bor(d2, d4)),
866 def!(e1 = ushr_imm(e, imm64_16)),
867 def!(e2 = ishl_imm(e, imm64_16)),
868 def!(a = bor(e1, e2)),
869 ],
870 );
871
872 #[allow(overflowing_literals)]
873 let imm64_0xaaaaaaaaaaaaaaaa = Literal::constant(&imm.imm64, 0xaaaa_aaaa_aaaa_aaaa);
874 let imm64_0x5555555555555555 = Literal::constant(&imm.imm64, 0x5555_5555_5555_5555);
875 #[allow(overflowing_literals)]
876 let imm64_0xcccccccccccccccc = Literal::constant(&imm.imm64, 0xcccc_cccc_cccc_cccc);
877 let imm64_0x3333333333333333 = Literal::constant(&imm.imm64, 0x3333_3333_3333_3333);
878 #[allow(overflowing_literals)]
879 let imm64_0xf0f0f0f0f0f0f0f0 = Literal::constant(&imm.imm64, 0xf0f0_f0f0_f0f0_f0f0);
880 let imm64_0x0f0f0f0f0f0f0f0f = Literal::constant(&imm.imm64, 0x0f0f_0f0f_0f0f_0f0f);
881 #[allow(overflowing_literals)]
882 let imm64_0xff00ff00ff00ff00 = Literal::constant(&imm.imm64, 0xff00_ff00_ff00_ff00);
883 let imm64_0x00ff00ff00ff00ff = Literal::constant(&imm.imm64, 0x00ff_00ff_00ff_00ff);
884 #[allow(overflowing_literals)]
885 let imm64_0xffff0000ffff0000 = Literal::constant(&imm.imm64, 0xffff_0000_ffff_0000);
886 let imm64_0x0000ffff0000ffff = Literal::constant(&imm.imm64, 0x0000_ffff_0000_ffff);
887 let imm64_32 = Literal::constant(&imm.imm64, 32);
888
889 expand.legalize(
890 def!(a = bitrev.I64(x)),
891 vec![
892 def!(a1 = band_imm(x, imm64_0xaaaaaaaaaaaaaaaa)),
893 def!(a2 = ushr_imm(a1, imm64_1)),
894 def!(a3 = band_imm(x, imm64_0x5555555555555555)),
895 def!(a4 = ishl_imm(a3, imm64_1)),
896 def!(b = bor(a2, a4)),
897 def!(b1 = band_imm(b, imm64_0xcccccccccccccccc)),
898 def!(b2 = ushr_imm(b1, imm64_2)),
899 def!(b3 = band_imm(b, imm64_0x3333333333333333)),
900 def!(b4 = ishl_imm(b3, imm64_2)),
901 def!(c = bor(b2, b4)),
902 def!(c1 = band_imm(c, imm64_0xf0f0f0f0f0f0f0f0)),
903 def!(c2 = ushr_imm(c1, imm64_4)),
904 def!(c3 = band_imm(c, imm64_0x0f0f0f0f0f0f0f0f)),
905 def!(c4 = ishl_imm(c3, imm64_4)),
906 def!(d = bor(c2, c4)),
907 def!(d1 = band_imm(d, imm64_0xff00ff00ff00ff00)),
908 def!(d2 = ushr_imm(d1, imm64_8)),
909 def!(d3 = band_imm(d, imm64_0x00ff00ff00ff00ff)),
910 def!(d4 = ishl_imm(d3, imm64_8)),
911 def!(e = bor(d2, d4)),
912 def!(e1 = band_imm(e, imm64_0xffff0000ffff0000)),
913 def!(e2 = ushr_imm(e1, imm64_16)),
914 def!(e3 = band_imm(e, imm64_0x0000ffff0000ffff)),
915 def!(e4 = ishl_imm(e3, imm64_16)),
916 def!(f = bor(e2, e4)),
917 def!(f1 = ushr_imm(f, imm64_32)),
918 def!(f2 = ishl_imm(f, imm64_32)),
919 def!(a = bor(f1, f2)),
920 ],
921 );
922
923 narrow.legalize(
924 def!(a = bitrev.I128(x)),
925 vec![
926 def!((xl, xh) = isplit(x)),
927 def!(yh = bitrev(xl)),
928 def!(yl = bitrev(xh)),
929 def!(a = iconcat(yl, yh)),
930 ],
931 );
932
933 // Floating-point sign manipulations.
934 for &(ty, const_inst, minus_zero) in &[
935 (F32, f32const, &Literal::bits(&imm.ieee32, 0x8000_0000)),
936 (
937 F64,
938 f64const,
939 &Literal::bits(&imm.ieee64, 0x8000_0000_0000_0000),
940 ),
941 ] {
942 expand.legalize(
943 def!(a = fabs.ty(x)),
944 vec![def!(b = const_inst(minus_zero)), def!(a = band_not(x, b))],
945 );
946
947 expand.legalize(
948 def!(a = fneg.ty(x)),
949 vec![def!(b = const_inst(minus_zero)), def!(a = bxor(x, b))],
950 );
951
952 expand.legalize(
953 def!(a = fcopysign.ty(x, y)),
954 vec![
955 def!(b = const_inst(minus_zero)),
956 def!(a1 = band_not(x, b)),
957 def!(a2 = band(y, b)),
958 def!(a = bor(a1, a2)),
959 ],
960 );
961 }
962
963 expand.custom_legalize(br_icmp, "expand_br_icmp");
964
965 let mut groups = TransformGroups::new();
966
967 let narrow_id = narrow.build_and_add_to(&mut groups);
968 let expand_id = expand.build_and_add_to(&mut groups);
969
970 // Expansions using CPU flags.
971 let mut expand_flags = TransformGroupBuilder::new(
972 "expand_flags",
973 r#"
974 Instruction expansions for architectures with flags.
975
976 Expand some instructions using CPU flags, then fall back to the normal
977 expansions. Not all architectures support CPU flags, so these patterns
978 are kept separate.
979 "#,
980 )
981 .chain_with(expand_id);
982
983 let imm64_0 = Literal::constant(&imm.imm64, 0);
984 let intcc_ne = Literal::enumerator_for(&imm.intcc, "ne");
985 let intcc_eq = Literal::enumerator_for(&imm.intcc, "eq");
986
987 expand_flags.legalize(
988 def!(trapnz(x, c)),
989 vec![
990 def!(a = ifcmp_imm(x, imm64_0)),
991 def!(trapif(intcc_ne, a, c)),
992 ],
993 );
994
995 expand_flags.legalize(
996 def!(trapz(x, c)),
997 vec![
998 def!(a = ifcmp_imm(x, imm64_0)),
999 def!(trapif(intcc_eq, a, c)),
1000 ],
1001 );
1002
1003 expand_flags.build_and_add_to(&mut groups);
1004
1005 // Narrow legalizations using CPU flags.
1006 let mut narrow_flags = TransformGroupBuilder::new(
1007 "narrow_flags",
1008 r#"
1009 Narrow instructions for architectures with flags.
1010
1011 Narrow some instructions using CPU flags, then fall back to the normal
1012 legalizations. Not all architectures support CPU flags, so these
1013 patterns are kept separate.
1014 "#,
1015 )
1016 .chain_with(narrow_id);
1017
1018 narrow_flags.legalize(
1019 def!(a = iadd(x, y)),
1020 vec![
1021 def!((xl, xh) = isplit(x)),
1022 def!((yl, yh) = isplit(y)),
1023 def!((al, c) = iadd_ifcout(xl, yl)),
1024 def!(ah = iadd_ifcin(xh, yh, c)),
1025 def!(a = iconcat(al, ah)),
1026 ],
1027 );
1028
1029 narrow_flags.legalize(
1030 def!(a = isub(x, y)),
1031 vec![
1032 def!((xl, xh) = isplit(x)),
1033 def!((yl, yh) = isplit(y)),
1034 def!((al, b) = isub_ifbout(xl, yl)),
1035 def!(ah = isub_ifbin(xh, yh, b)),
1036 def!(a = iconcat(al, ah)),
1037 ],
1038 );
1039
1040 narrow_flags.build_and_add_to(&mut groups);
1041
1042 // TODO(ryzokuken): figure out a way to legalize iadd_c* to iadd_ifc* (and
1043 // similarly isub_b* to isub_ifb*) on expand_flags so that this isn't required.
1044 // Narrow legalizations for ISAs that don't have CPU flags.
1045 let mut narrow_no_flags = TransformGroupBuilder::new(
1046 "narrow_no_flags",
1047 r#"
1048 Narrow instructions for architectures without flags.
1049
1050 Narrow some instructions avoiding the use of CPU flags, then fall back
1051 to the normal legalizations. Not all architectures support CPU flags,
1052 so these patterns are kept separate.
1053 "#,
1054 )
1055 .chain_with(narrow_id);
1056
1057 narrow_no_flags.legalize(
1058 def!(a = iadd(x, y)),
1059 vec![
1060 def!((xl, xh) = isplit(x)),
1061 def!((yl, yh) = isplit(y)),
1062 def!((al, c) = iadd_cout(xl, yl)),
1063 def!(ah = iadd_cin(xh, yh, c)),
1064 def!(a = iconcat(al, ah)),
1065 ],
1066 );
1067
1068 narrow_no_flags.legalize(
1069 def!(a = isub(x, y)),
1070 vec![
1071 def!((xl, xh) = isplit(x)),
1072 def!((yl, yh) = isplit(y)),
1073 def!((al, b) = isub_bout(xl, yl)),
1074 def!(ah = isub_bin(xh, yh, b)),
1075 def!(a = iconcat(al, ah)),
1076 ],
1077 );
1078
1079 narrow_no_flags.build_and_add_to(&mut groups);
1080
1081 // TODO The order of declarations unfortunately matters to be compatible with the Python code.
1082 // When it's all migrated, we can put this next to the narrow/expand build_and_add_to calls
1083 // above.
1084 widen.build_and_add_to(&mut groups);
1085
1086 groups
1087 }
1088