;; x86-64 instruction selection and CLIF-to-MachInst lowering.

;; The main lowering constructor term: takes a clif `Inst` and returns the

;; register(s) within which the lowered instruction's result values live.

(spec (lower arg)

(provide (= result arg)))

(decl partial lower (Inst) InstOutput)

;; A variant of the main lowering constructor term, used for branches.

;; The only difference is that it gets an extra argument holding a vector

;; of branch targets to be used.

(decl partial lower_branch (Inst MachLabelSlice) Unit)

;;;; Rules for `iconst` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

(rule (lower (has_type (fits_in_64 ty)

(iconst (u64_from_imm64 x))))

(imm ty x))

;; `i128`

(rule 1 (lower (has_type $I128

(iconst (u64_from_imm64 x))))

(value_regs (imm $I64 x)

(imm $I64 0)))

;;;; Rules for `f16const` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (f16const (u16_from_ieee16 x)))

(imm $F16 x))

;;;; Rules for `f32const` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (f32const (u32_from_ieee32 x)))

(imm $F32 x))

;;;; Rules for `f64const` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (f64const (u64_from_ieee64 x)))

(imm $F64 x))

;;;; Rules for `f128const` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (f128const const))

;; TODO use Inst::gen_constant() instead.

(x64_xmm_load_const $F128 (const_to_vconst const)))

(rule 1 (lower (f128const (u128_from_constant 0)))

(xmm_zero $F128))

;;;; Rules for `iadd` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

;; Base case for 8 and 16-bit types

(rule -6 (lower (has_type (fits_in_16 ty)

(iadd x y)))

(x64_add ty x y))

;; Base case for 32 and 64-bit types which might end up using the `lea`

;; instruction to fold multiple operations into one.

;;

;; Note that at this time this always generates a `lea` pseudo-instruction,

;; but the actual instruction emitted might be an `add` if it's equivalent.

;; For more details on this see the `emit.rs` logic to emit

;; `LoadEffectiveAddress`.

(rule iadd_base_case_32_or_64_lea -5 (lower (has_type (ty_32_or_64 ty) (iadd x y)))

(x64_lea ty (to_amode_add (mem_flags_trusted) x y (zero_offset))))

;; Higher-priority cases than the previous two where a load can be sunk into

;; the add instruction itself. Note that both operands are tested for

;; sink-ability since addition is commutative

(rule -4 (lower (has_type (fits_in_64 ty)

(iadd x (sinkable_load y))))

(x64_add ty x y))

(rule -3 (lower (has_type (fits_in_64 ty)

(iadd (sinkable_load x) y)))

(x64_add ty y x))

;; SSE.

(rule (lower (has_type (multi_lane 8 16)

(iadd x y)))

(x64_paddb x y))

(rule (lower (has_type (multi_lane 16 8)

(iadd x y)))

(x64_paddw x y))

(rule (lower (has_type (multi_lane 32 4)

(iadd x y)))

(x64_paddd x y))

(rule (lower (has_type (multi_lane 64 2)

(iadd x y)))

(x64_paddq x y))

;; `i128`

(rule 1 (lower (has_type $I128 (iadd x y)))

;; Get the high/low registers for `x`.

(let ((x_regs ValueRegs x)

(y_regs ValueRegs y))

(iadd128

(value_regs_get_gpr x_regs 0)

(value_regs_get_gpr x_regs 1)

(value_regs_get_gpr y_regs 0)

(value_regs_get_gpr y_regs 1))))

(rule 2 (lower (has_type $I128 (iadd x (iconcat y_lo y_hi))))

(let ((x_regs ValueRegs x))

(iadd128 (value_regs_get_gpr x 0) (value_regs_get_gpr x 1) y_lo y_hi)))

(rule 3 (lower (has_type $I128 (iadd x (uextend y @ (value_type $I64)))))

(let ((x_regs ValueRegs x))

(iadd128 (value_regs_get_gpr x 0) (value_regs_get_gpr x 1)

y (RegMemImm.Imm 0))))

;; Specialized lowering rule for `iadd` of two 64-bit unsigned integers, meaning

;; that we can skip the `adc` and instead use `setb`. This is in some sense a

;; way of modeling `uadd_overflow`.

(rule 4 (lower (has_type $I128 (iadd (uextend x) (uextend y @ (value_type $I64)))))

(let (

(x Gpr (extend_to_gpr x $I64 (ExtendKind.Zero)))

(ret ValueRegs (with_flags (x64_add_with_flags_paired $I64 x y)

(x64_setcc_paired (CC.B))))

)

;; FIXME: this `movzx` ideally would happen before the `add` itself to

;; zero out the destination register with `xor %dst,%dst` and then

;; the `setb` would just write to the lower bytes. That would probably

;; require modeling this as a pseudo-inst which isn't quite worth it

;; at this time.

(value_regs (value_regs_get ret 0)

(x64_movzx (ExtMode.BQ) (value_regs_get ret 1)))))

;; Helper for lowering 128-bit addition with the 64-bit halves of the lhs/rhs

;; already split. The first two arguments are lo/hi for the lhs and the second

;; two are lo/hi for the rhs.

(decl iadd128 (Gpr Gpr GprMemImm GprMemImm) ValueRegs)

(rule (iadd128 x_lo x_hi y_lo y_hi)

(with_flags (x64_add_with_flags_paired $I64 x_lo y_lo)

(x64_adc_paired $I64 x_hi y_hi)))

;;;; Helpers for `*_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(decl construct_overflow_op (CC ProducesFlags) InstOutput)

(rule (construct_overflow_op cc inst)

(let ((results ValueRegs (with_flags inst

(x64_setcc_paired cc))))

(output_pair (value_regs_get results 0)

(value_regs_get results 1))))

(decl construct_overflow_op_alu (Type CC AluRmiROpcode Gpr GprMemImm) InstOutput)

(rule (construct_overflow_op_alu ty cc alu_op src1 src2)

(construct_overflow_op cc (x64_alurmi_with_flags_paired alu_op ty src1 src2)))

;; This essentially creates

;; alu_<op1> x_lo, y_lo

;; alu_<op2> x_hi, y_hi

;; set<cc> r8

(decl construct_overflow_op_alu_128 (CC AluRmiROpcode AluRmiROpcode Value Value) InstOutput)

(rule (construct_overflow_op_alu_128 cc op1 op2 x y)

;; Get the high/low registers for `x`.

(let ((x_regs ValueRegs x)

(x_lo Gpr (value_regs_get_gpr x_regs 0))

(x_hi Gpr (value_regs_get_gpr x_regs 1)))

;; Get the high/low registers for `y`.

(let ((y_regs ValueRegs y)

(y_lo Gpr (value_regs_get_gpr y_regs 0))

(y_hi Gpr (value_regs_get_gpr y_regs 1)))

(let ((lo_inst ProducesFlags (x64_alurmi_with_flags_paired op1 $I64 x_lo y_lo))

(hi_inst ConsumesAndProducesFlags (x64_alurmi_with_flags_chained op2 $I64 x_hi y_hi))

(of_inst ConsumesFlags (x64_setcc_paired cc))

(result MultiReg (with_flags_chained lo_inst hi_inst of_inst)))

(multi_reg_to_pair_and_single result)))))

;;;; Rules for `uadd_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 1 (lower (uadd_overflow x y @ (value_type (fits_in_64 ty))))

(construct_overflow_op_alu ty (CC.B) (AluRmiROpcode.Add) x y))

;; i128 gets lowered into adc and add

(rule 0 (lower (uadd_overflow x y @ (value_type $I128)))

(construct_overflow_op_alu_128 (CC.B) (AluRmiROpcode.Add) (AluRmiROpcode.Adc) x y))

;;;; Rules for `sadd_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 1 (lower (sadd_overflow x y @ (value_type (fits_in_64 ty))))

(construct_overflow_op_alu ty (CC.O) (AluRmiROpcode.Add) x y))

(rule 0 (lower (sadd_overflow x y @ (value_type $I128)))

(construct_overflow_op_alu_128 (CC.O) (AluRmiROpcode.Add) (AluRmiROpcode.Adc) x y))

;;;; Rules for `usub_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 1 (lower (usub_overflow x y @ (value_type (fits_in_64 ty))))

(construct_overflow_op_alu ty (CC.B) (AluRmiROpcode.Sub) x y))

(rule 0 (lower (usub_overflow x y @ (value_type $I128)))

(construct_overflow_op_alu_128 (CC.B) (AluRmiROpcode.Sub) (AluRmiROpcode.Sbb) x y))

;;;; Rules for `ssub_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 1 (lower (ssub_overflow x y @ (value_type (fits_in_64 ty))))

(construct_overflow_op_alu ty (CC.O) (AluRmiROpcode.Sub) x y))

(rule 0 (lower (ssub_overflow x y @ (value_type $I128)))

(construct_overflow_op_alu_128 (CC.O) (AluRmiROpcode.Sub) (AluRmiROpcode.Sbb) x y))

;;;; Rules for `umul_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 2 (lower (umul_overflow x y @ (value_type $I8)))

(construct_overflow_op (CC.O) (x64_mul8_with_flags_paired false x y)))

(rule 3 (lower (umul_overflow x y @ (value_type (ty_int_ref_16_to_64 ty))))

(construct_overflow_op (CC.O) (x64_mul_lo_with_flags_paired ty false x y)))

;;;; Rules for `smul_overflow` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule 2 (lower (smul_overflow x y @ (value_type $I8)))

(construct_overflow_op (CC.O) (x64_mul8_with_flags_paired true x y)))

(rule 3 (lower (smul_overflow x y @ (value_type (ty_int_ref_16_to_64 ty))))

(construct_overflow_op (CC.O) (x64_mul_lo_with_flags_paired ty true x y)))

;;;; Rules for `sadd_sat` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (has_type (multi_lane 8 16)

(sadd_sat x y)))

(x64_paddsb x y))

(rule (lower (has_type (multi_lane 16 8)

(sadd_sat x y)))

(x64_paddsw x y))

;;;; Rules for `uadd_sat` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (has_type (multi_lane 8 16)

(uadd_sat x y)))

(x64_paddusb x y))

(rule (lower (has_type (multi_lane 16 8)

(uadd_sat x y)))

(x64_paddusw x y))

;;;; Rules for `isub` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

;; Sub two registers.

(rule -3 (lower (has_type (fits_in_64 ty)

(isub x y)))

(x64_sub ty x y))

;; SSE.

(rule (lower (has_type (multi_lane 8 16)

(isub x y)))

(x64_psubb x y))

(rule (lower (has_type (multi_lane 16 8)

(isub x y)))

(x64_psubw x y))

(rule (lower (has_type (multi_lane 32 4)

(isub x y)))

(x64_psubd x y))

(rule (lower (has_type (multi_lane 64 2)

(isub x y)))

(x64_psubq x y))

;; `i128`

(rule 1 (lower (has_type $I128 (isub x y)))

;; Get the high/low registers for `x`.

(let ((x_regs ValueRegs x)

(y_regs ValueRegs y))

(isub128

(value_regs_get_gpr x_regs 0)

(value_regs_get_gpr x_regs 1)

(value_regs_get_gpr y_regs 0)

(value_regs_get_gpr y_regs 1))))

(rule 2 (lower (has_type $I128 (isub x (iconcat y_lo y_hi))))

(let ((x_regs ValueRegs x))

(isub128 (value_regs_get_gpr x 0) (value_regs_get_gpr x 1) y_lo y_hi)))

(rule 3 (lower (has_type $I128 (isub x (uextend y @ (value_type $I64)))))

(let ((x_regs ValueRegs x))

(isub128 (value_regs_get_gpr x 0) (value_regs_get_gpr x 1)

y (RegMemImm.Imm 0))))

;; Helper for lowering 128-bit subtraction with the 64-bit halves of the lhs/rhs

;; already split. The first two arguments are lo/hi for the lhs and the second

;; two are lo/hi for the rhs.

(decl isub128 (Gpr Gpr GprMemImm GprMemImm) ValueRegs)

(rule (isub128 x_lo x_hi y_lo y_hi)

(with_flags (x64_sub_with_flags_paired $I64 x_lo y_lo)

(x64_sbb_paired $I64 x_hi y_hi)))

;;;; Rules for `ssub_sat` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (has_type (multi_lane 8 16)

(ssub_sat x y)))

(x64_psubsb x y))

(rule (lower (has_type (multi_lane 16 8)

(ssub_sat x y)))

(x64_psubsw x y))

;;;; Rules for `usub_sat` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(rule (lower (has_type (multi_lane 8 16)

(usub_sat x y)))

(x64_psubusb x y))

(rule (lower (has_type (multi_lane 16 8)

(usub_sat x y)))

(x64_psubusw x y))

;;;; Rules for `band` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `{i,b}64` and smaller.

;; And two registers.

(rule 0 (lower (has_type ty (band x y)))

(if (ty_int_ref_scalar_64 ty))

(x64_and ty x y))

;; The above case automatically handles when the rhs is an immediate or a

;; sinkable load, but additionally handle the lhs here.

(rule 1 (lower (has_type ty (band (sinkable_load x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_and ty y x))

(rule 2 (lower (has_type ty (band (simm32_from_value x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_and ty y x))

;; f32 and f64

(rule 5 (lower (has_type (ty_scalar_float ty) (band x y)))

(sse_and ty x y))

;; SSE.

(decl sse_and (Type Xmm XmmMem) Xmm)

(rule (sse_and $F32X4 x y) (x64_andps x y))

(rule (sse_and $F64X2 x y) (x64_andpd x y))

(rule (sse_and $F32 x y) (x64_andps x y))

(rule (sse_and $F64 x y) (x64_andpd x y))

(rule -1 (sse_and (multi_lane _bits _lanes) x y) (x64_pand x y))

(rule 6 (lower (has_type ty @ (multi_lane _bits _lanes)

(band x y)))

(sse_and ty x y))

;; `i128`.

(decl and_i128 (ValueRegs ValueRegs) ValueRegs)

(rule (and_i128 x y)

(let ((x_regs ValueRegs x)

(x_lo Gpr (value_regs_get_gpr x_regs 0))

(x_hi Gpr (value_regs_get_gpr x_regs 1))

(y_regs ValueRegs y)

(y_lo Gpr (value_regs_get_gpr y_regs 0))

(y_hi Gpr (value_regs_get_gpr y_regs 1)))

(value_gprs (x64_and $I64 x_lo y_lo)

(x64_and $I64 x_hi y_hi))))

(rule 7 (lower (has_type $I128 (band x y)))

(and_i128 x y))

;; Specialized lowerings for `(band x (bnot y))` which is additionally produced

;; by Cranelift's `band_not` instruction that is legalized into the simpler

;; forms early on.

(decl sse_and_not (Type Xmm XmmMem) Xmm)

(rule (sse_and_not $F32X4 x y) (x64_andnps x y))

(rule (sse_and_not $F64X2 x y) (x64_andnpd x y))

(rule -1 (sse_and_not (multi_lane _bits _lanes) x y) (x64_pandn x y))

;; Note the flipping of operands below as we're match

;;

;; (band x (bnot y))

;;

;; while x86 does

;;

;; pandn(x, y) = and(not(x), y)

(rule 8 (lower (has_type ty @ (multi_lane _bits _lane) (band x (bnot y))))

(sse_and_not ty y x))

(rule 9 (lower (has_type ty @ (multi_lane _bits _lane) (band (bnot y) x)))

(sse_and_not ty y x))

(rule 10 (lower (has_type ty (band x (bnot y))))

(if (ty_int_ref_scalar_64 ty))

(if-let true (use_bmi1))

;; the first argument is the one that gets inverted with andn

(x64_andn ty y x))

(rule 11 (lower (has_type ty (band (bnot y) x)))

(if (ty_int_ref_scalar_64 ty))

(if-let true (use_bmi1))

(x64_andn ty y x))

;; Specialization of `blsr` for BMI1

(decl pure partial val_minus_one (Value) Value)

(rule 0 (val_minus_one (isub x (u64_from_iconst 1))) x)

(rule 0 (val_minus_one (iadd x (i64_from_iconst -1))) x)

(rule 1 (val_minus_one (iadd (i64_from_iconst -1) x)) x)

(rule 12 (lower (has_type (ty_32_or_64 ty) (band x y)))

(if-let true (use_bmi1))

(if-let x (val_minus_one y))

(x64_blsr ty x))

(rule 13 (lower (has_type (ty_32_or_64 ty) (band y x)))

(if-let true (use_bmi1))

(if-let x (val_minus_one y))

(x64_blsr ty x))

;; Specialization of `blsi` for BMI1

(rule 14 (lower (has_type (ty_32_or_64 ty) (band (ineg x) x)))

(if-let true (use_bmi1))

(x64_blsi ty x))

(rule 15 (lower (has_type (ty_32_or_64 ty) (band x (ineg x))))

(if-let true (use_bmi1))

(x64_blsi ty x))

;; Specialization of `bzhi` for BMI2

;;

;; The `bzhi` instruction clears all bits indexed by the second operand of the

;; first operand. This is pattern-matched here with a `band` against a mask

;; which is generated to be N bits large. Note that if the index is larger than

;; the bit-width of the type then `bzhi` doesn't have the same semantics as

;; `ishl`, so an `and` instruction is required to mask the index to match the

;; semantics of Cranelift's `ishl`.

(rule 16 (lower (has_type (ty_32_or_64 ty) (band x y)))

(if-let true (use_bmi2))

(if-let (ishl (u64_from_iconst 1) index) (val_minus_one y))

(x64_bzhi ty x (x64_and ty index (RegMemImm.Imm (u32_sub (ty_bits ty) 1)))))

;;;; Rules for `bor` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `{i,b}64` and smaller.

;; Or two registers.

(rule 0 (lower (has_type ty (bor x y)))

(if (ty_int_ref_scalar_64 ty))

(x64_or ty x y))

;; Handle immediates/sinkable loads on the lhs in addition to the automatic

;; handling of the rhs above

(rule 1 (lower (has_type ty (bor (sinkable_load x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_or ty y x))

(rule 2 (lower (has_type ty (bor (simm32_from_value x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_or ty y x))

;; f32 and f64

(rule 5 (lower (has_type (ty_scalar_float ty) (bor x y)))

(sse_or ty x y))

;; SSE.

(decl sse_or (Type Xmm XmmMem) Xmm)

(rule (sse_or $F32X4 x y) (x64_orps x y))

(rule (sse_or $F64X2 x y) (x64_orpd x y))

(rule (sse_or $F32 x y) (x64_orps x y))

(rule (sse_or $F64 x y) (x64_orpd x y))

(rule -1 (sse_or (multi_lane _bits _lanes) x y) (x64_por x y))

(rule 6 (lower (has_type ty @ (multi_lane _bits _lanes)

(bor x y)))

(sse_or ty x y))

;; `{i,b}128`.

(decl or_i128 (ValueRegs ValueRegs) ValueRegs)

(rule (or_i128 x y)

(let ((x_lo Gpr (value_regs_get_gpr x 0))

(x_hi Gpr (value_regs_get_gpr x 1))

(y_lo Gpr (value_regs_get_gpr y 0))

(y_hi Gpr (value_regs_get_gpr y 1)))

(value_gprs (x64_or $I64 x_lo y_lo)

(x64_or $I64 x_hi y_hi))))

(rule 7 (lower (has_type $I128 (bor x y)))

(or_i128 x y))

;; Specialized lowerings to generate the `shld` instruction.

;;

;; The `shld` instruction will shift a value left and shift-in bits from a

;; different register. Pattern-match doing this with bit-ops and shifts to

;; generate a `shld` instruction.

(rule 8 (lower (has_type (ty_int_ref_16_to_64 ty)

(bor (ishl x (u8_from_iconst xs)) (ushr y (u8_from_iconst ys)))))

(if-let true (u64_eq (ty_bits ty) (u64_add xs ys)))

(x64_shld ty x y xs))

(rule 8 (lower (has_type (ty_int_ref_16_to_64 ty)

(bor (ushr y (u8_from_iconst ys)) (ishl x (u8_from_iconst xs)))))

(if-let true (u64_eq (ty_bits ty) (u64_add xs ys)))

(x64_shld ty x y xs))

;;;; Rules for `bxor` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `{i,b}64` and smaller.

;; Xor two registers.

(rule 0 (lower (has_type ty (bxor x y)))

(if (ty_int_ref_scalar_64 ty))

(x64_xor ty x y))

;; Handle xor with lhs immediates/sinkable loads in addition to the automatic

;; handling of the rhs above.

(rule 1 (lower (has_type ty (bxor (sinkable_load x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_xor ty y x))

(rule 4 (lower (has_type ty (bxor (simm32_from_value x) y)))

(if (ty_int_ref_scalar_64 ty))

(x64_xor ty y x))

;; f32 and f64

(rule 5 (lower (has_type (ty_scalar_float ty) (bxor x y)))

(x64_xor_vector ty x y))

;; SSE.

(rule 6 (lower (has_type ty @ (multi_lane _bits _lanes) (bxor x y)))

(x64_xor_vector ty x y))

;; `{i,b}128`.

(rule 7 (lower (has_type $I128 (bxor x y)))

(let ((x_regs ValueRegs x)

(x_lo Gpr (value_regs_get_gpr x_regs 0))

(x_hi Gpr (value_regs_get_gpr x_regs 1))

(y_regs ValueRegs y)

(y_lo Gpr (value_regs_get_gpr y_regs 0))

(y_hi Gpr (value_regs_get_gpr y_regs 1)))

(value_gprs (x64_xor $I64 x_lo y_lo)

(x64_xor $I64 x_hi y_hi))))

;; Specialization of `blsmsk` for BMI1

(rule 8 (lower (has_type (ty_32_or_64 ty) (bxor x y)))

(if-let true (use_bmi1))

(if-let x (val_minus_one y))

(x64_blsmsk ty x))

(rule 9 (lower (has_type (ty_32_or_64 ty) (bxor y x)))

(if-let true (use_bmi1))

(if-let x (val_minus_one y))

(x64_blsmsk ty x))

;;;; Rules for `ishl` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

(rule -1 (lower (has_type (fits_in_64 ty) (ishl src amt)))

(x64_shl ty src (put_masked_in_imm8_gpr amt ty)))

;; `i128`.

(decl shl_i128 (ValueRegs Gpr) ValueRegs)

(rule (shl_i128 src amt)

;; Unpack the registers that make up the 128-bit value being shifted.

(let ((src_lo Gpr (value_regs_get_gpr src 0))

(src_hi Gpr (value_regs_get_gpr src 1))

;; Do two 64-bit shifts.

(lo_shifted Gpr (x64_shl $I64 src_lo amt))

(hi_shifted Gpr (x64_shl $I64 src_hi amt))

;; `src_lo >> (64 - amt)` are the bits to carry over from the lo

;; into the hi.

(carry Gpr (x64_shr $I64

src_lo

(x64_sub $I64

(imm $I64 64)

amt)))

(zero Gpr (imm $I64 0))

;; Nullify the carry if we are shifting in by a multiple of 128.

(carry_ Gpr (with_flags_reg (x64_test (OperandSize.Size64)

amt

(RegMemImm.Imm 127))

(cmove $I64

(CC.Z)

zero

carry)))

;; Add the carry into the high half.

(hi_shifted_ Gpr (x64_or $I64 carry_ hi_shifted)))

;; Combine the two shifted halves. However, if we are shifting by >= 64

;; (modulo 128), then the low bits are zero and the high bits are our

;; low bits.

(with_flags (x64_test (OperandSize.Size64) amt (RegMemImm.Imm 64))

(consumes_flags_concat

(cmove $I64 (CC.Z) lo_shifted zero)

(cmove $I64 (CC.Z) hi_shifted_ lo_shifted)))))

(rule (lower (has_type $I128 (ishl src amt)))

;; NB: Only the low bits of `amt` matter since we logically mask the shift

;; amount to the value's bit width.

(let ((amt_ Gpr (lo_gpr amt)))

(shl_i128 src amt_)))

;; SSE.

;; Since the x86 instruction set does not have any 8x16 shift instructions (even

;; in higher feature sets like AVX), we lower the `ishl.i8x16` to a sequence of

;; instructions. The basic idea, whether the amount to shift by is an immediate

;; or not, is to use a 16x8 shift and then mask off the incorrect bits to 0s.

(rule (lower (has_type ty @ $I8X16 (ishl src amt)))

(let (

;; Mask the amount to ensure wrapping behaviour

(masked_amt RegMemImm (mask_xmm_shift ty amt))

;; Shift `src` using 16x8. Unfortunately, a 16x8 shift will only be

;; correct for half of the lanes; the others must be fixed up with

;; the mask below.

(unmasked Xmm (x64_psllw src (mov_rmi_to_xmm masked_amt)))

(mask_addr SyntheticAmode (ishl_i8x16_mask masked_amt))

(mask Reg (x64_load $I8X16 mask_addr (ExtKind.None))))

(sse_and $I8X16 unmasked (RegMem.Reg mask))))

;; Get the address of the mask to use when fixing up the lanes that weren't

;; correctly generated by the 16x8 shift.

(decl ishl_i8x16_mask (RegMemImm) SyntheticAmode)

;; When the shift amount is known, we can statically (i.e. at compile time)

;; determine the mask to use and only emit that.

(decl ishl_i8x16_mask_for_const (u32) SyntheticAmode)

(extern constructor ishl_i8x16_mask_for_const ishl_i8x16_mask_for_const)

(rule (ishl_i8x16_mask (RegMemImm.Imm amt))

(ishl_i8x16_mask_for_const amt))

;; Otherwise, we must emit the entire mask table and dynamically (i.e. at run

;; time) find the correct mask offset in the table. We use `lea` to find the

;; base address of the mask table and then complex addressing to offset to the

;; right mask: `base_address + amt << 4`

(decl ishl_i8x16_mask_table () SyntheticAmode)

(extern constructor ishl_i8x16_mask_table ishl_i8x16_mask_table)

(rule (ishl_i8x16_mask (RegMemImm.Reg amt))

(let ((mask_table SyntheticAmode (ishl_i8x16_mask_table))

(base_mask_addr Gpr (x64_lea $I64 mask_table))

(mask_offset Gpr (x64_shl $I64 amt

(imm8_to_imm8_gpr 4))))

(Amode.ImmRegRegShift 0

base_mask_addr

mask_offset

0

(mem_flags_trusted))))

(rule (ishl_i8x16_mask (RegMemImm.Mem amt))

(ishl_i8x16_mask (RegMemImm.Reg (x64_load $I64 amt (ExtKind.None)))))

;; 16x8, 32x4, and 64x2 shifts can each use a single instruction, once the shift amount is masked.

(rule (lower (has_type ty @ $I16X8 (ishl src amt)))

(x64_psllw src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(rule (lower (has_type ty @ $I32X4 (ishl src amt)))

(x64_pslld src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(rule (lower (has_type ty @ $I64X2 (ishl src amt)))

(x64_psllq src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

;;;; Rules for `ushr` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

(rule -1 (lower (has_type (fits_in_64 ty) (ushr src amt)))

(let ((src_ Gpr (extend_to_gpr src ty (ExtendKind.Zero))))

(x64_shr ty src_ (put_masked_in_imm8_gpr amt ty))))

;; `i128`.

(decl shr_i128 (ValueRegs Gpr) ValueRegs)

(rule (shr_i128 src amt)

;; Unpack the lo/hi halves of `src`.

(let ((src_lo Gpr (value_regs_get_gpr src 0))

(src_hi Gpr (value_regs_get_gpr src 1))

;; Do a shift on each half.

(lo_shifted Gpr (x64_shr $I64 src_lo amt))

(hi_shifted Gpr (x64_shr $I64 src_hi amt))

;; `src_hi << (64 - amt)` are the bits to carry over from the hi

;; into the lo.

(carry Gpr (x64_shl $I64

src_hi

(x64_sub $I64

(imm $I64 64)

amt)))

;; Share the zero value to reduce register pressure

(zero Gpr (imm $I64 0))

;; Nullify the carry if we are shifting by a multiple of 128.

(carry_ Gpr (with_flags_reg (x64_test (OperandSize.Size64) amt (RegMemImm.Imm 127))

(cmove $I64 (CC.Z) zero carry)))

;; Add the carry bits into the lo.

(lo_shifted_ Gpr (x64_or $I64 carry_ lo_shifted)))

;; Combine the two shifted halves. However, if we are shifting by >= 64

;; (modulo 128), then the hi bits are zero and the lo bits are what

;; would otherwise be our hi bits.

(with_flags (x64_test (OperandSize.Size64) amt (RegMemImm.Imm 64))

(consumes_flags_concat

(cmove $I64 (CC.Z) lo_shifted_ hi_shifted)

(cmove $I64 (CC.Z) hi_shifted zero)))))

(rule (lower (has_type $I128 (ushr src amt)))

;; NB: Only the low bits of `amt` matter since we logically mask the shift

;; amount to the value's bit width.

(let ((amt_ Gpr (lo_gpr amt)))

(shr_i128 src amt_)))

;; SSE.

;; There are no 8x16 shifts in x64. Do the same 16x8-shift-and-mask thing we do

;; with 8x16 `ishl`.

(rule (lower (has_type ty @ $I8X16 (ushr src amt)))

(let (

;; Mask the amount to ensure wrapping behaviour

(masked_amt RegMemImm (mask_xmm_shift ty amt))

;; Shift `src` using 16x8. Unfortunately, a 16x8 shift will only be

;; correct for half of the lanes; the others must be fixed up with

;; the mask below.

(unmasked Xmm (x64_psrlw src (mov_rmi_to_xmm masked_amt))))

(sse_and $I8X16

unmasked

(ushr_i8x16_mask masked_amt))))

;; Get the address of the mask to use when fixing up the lanes that weren't

;; correctly generated by the 16x8 shift.

(decl ushr_i8x16_mask (RegMemImm) SyntheticAmode)

;; When the shift amount is known, we can statically (i.e. at compile time)

;; determine the mask to use and only emit that.

(decl ushr_i8x16_mask_for_const (u32) SyntheticAmode)

(extern constructor ushr_i8x16_mask_for_const ushr_i8x16_mask_for_const)

(rule (ushr_i8x16_mask (RegMemImm.Imm amt))

(ushr_i8x16_mask_for_const amt))

;; Otherwise, we must emit the entire mask table and dynamically (i.e. at run

;; time) find the correct mask offset in the table. We use `lea` to find the

;; base address of the mask table and then complex addressing to offset to the

;; right mask: `base_address + amt << 4`

(decl ushr_i8x16_mask_table () SyntheticAmode)

(extern constructor ushr_i8x16_mask_table ushr_i8x16_mask_table)

(rule (ushr_i8x16_mask (RegMemImm.Reg amt))

(let ((mask_table SyntheticAmode (ushr_i8x16_mask_table))

(base_mask_addr Gpr (x64_lea $I64 mask_table))

(mask_offset Gpr (x64_shl $I64

amt

(imm8_to_imm8_gpr 4))))

(Amode.ImmRegRegShift 0

base_mask_addr

mask_offset

0

(mem_flags_trusted))))

(rule (ushr_i8x16_mask (RegMemImm.Mem amt))

(ushr_i8x16_mask (RegMemImm.Reg (x64_load $I64 amt (ExtKind.None)))))

;; 16x8, 32x4, and 64x2 shifts can each use a single instruction, once the shift amount is masked.

(rule (lower (has_type ty @ $I16X8 (ushr src amt)))

(x64_psrlw src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(rule (lower (has_type ty @ $I32X4 (ushr src amt)))

(x64_psrld src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(rule (lower (has_type ty @ $I64X2 (ushr src amt)))

(x64_psrlq src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(decl mask_xmm_shift (Type Value) RegMemImm)

(rule (mask_xmm_shift ty amt)

(gpr_to_reg (x64_and $I64 amt (RegMemImm.Imm (shift_mask ty)))))

(rule 1 (mask_xmm_shift ty (iconst n))

(RegMemImm.Imm (shift_amount_masked ty n)))

;;;; Rules for `sshr` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

(rule -1 (lower (has_type (fits_in_64 ty) (sshr src amt)))

(let ((src_ Gpr (extend_to_gpr src ty (ExtendKind.Sign))))

(x64_sar ty src_ (put_masked_in_imm8_gpr amt ty))))

;; `i128`.

(decl sar_i128 (ValueRegs Gpr) ValueRegs)

(rule (sar_i128 src amt)

;; Unpack the low/high halves of `src`.

(let ((src_lo Gpr (value_regs_get_gpr src 0))

(src_hi Gpr (value_regs_get_gpr src 1))

;; Do a shift of each half. NB: the low half uses an unsigned shift

;; because its MSB is not a sign bit.

(lo_shifted Gpr (x64_shr $I64 src_lo amt))

(hi_shifted Gpr (x64_sar $I64 src_hi amt))

;; `src_hi << (64 - amt)` are the bits to carry over from the low

;; half to the high half.

(carry Gpr (x64_shl $I64

src_hi

(x64_sub $I64

(imm $I64 64)

amt)))

;; Nullify the carry if we are shifting by a multiple of 128.

(carry_ Gpr (with_flags_reg (x64_test (OperandSize.Size64) amt (RegMemImm.Imm 127))

(cmove $I64 (CC.Z) (imm $I64 0) carry)))

;; Add the carry into the low half.

(lo_shifted_ Gpr (x64_or $I64 lo_shifted carry_))

;; Get all sign bits.

(sign_bits Gpr (x64_sar $I64 src_hi (imm8_to_imm8_gpr 63))))

;; Combine the two shifted halves. However, if we are shifting by >= 64

;; (modulo 128), then the hi bits are all sign bits and the lo bits are

;; what would otherwise be our hi bits.

(with_flags (x64_test (OperandSize.Size64) amt (RegMemImm.Imm 64))

(consumes_flags_concat

(cmove $I64 (CC.Z) lo_shifted_ hi_shifted)

(cmove $I64 (CC.Z) hi_shifted sign_bits)))))

(rule (lower (has_type $I128 (sshr src amt)))

;; NB: Only the low bits of `amt` matter since we logically mask the shift

;; amount to the value's bit width.

(let ((amt_ Gpr (lo_gpr amt)))

(sar_i128 src amt_)))

;; SSE.

;; Since the x86 instruction set does not have an 8x16 shift instruction and the

;; approach used for `ishl` and `ushr` cannot be easily used (the masks do not

;; preserve the sign), we use a different approach here: separate the low and

;; high lanes, shift them separately, and merge them into the final result.

;;

;; Visually, this looks like the following, where `src.i8x16 = [s0, s1, ...,

;; s15]:

;;

;; lo.i16x8 = [(s0, s0), (s1, s1), ..., (s7, s7)]

;; shifted_lo.i16x8 = shift each lane of `low`

;; hi.i16x8 = [(s8, s8), (s9, s9), ..., (s15, s15)]

;; shifted_hi.i16x8 = shift each lane of `high`

;; result = [s0'', s1'', ..., s15'']

(rule (lower (has_type ty @ $I8X16 (sshr src amt @ (value_type amt_ty))))

(let ((src_ Xmm (put_in_xmm src))

;; Mask the amount to ensure wrapping behaviour

(masked_amt RegMemImm (mask_xmm_shift ty amt))

;; In order for `packsswb` later to only use the high byte of each

;; 16x8 lane, we shift right an extra 8 bits, relying on `psraw` to

;; fill in the upper bits appropriately.

(lo Xmm (x64_punpcklbw src_ src_))

(hi Xmm (x64_punpckhbw src_ src_))

(amt_ XmmMemImm (sshr_i8x16_bigger_shift amt_ty masked_amt))

(shifted_lo Xmm (x64_psraw lo amt_))

(shifted_hi Xmm (x64_psraw hi amt_)))

(x64_packsswb shifted_lo shifted_hi)))

(decl sshr_i8x16_bigger_shift (Type RegMemImm) XmmMemImm)

(rule (sshr_i8x16_bigger_shift _ty (RegMemImm.Imm i))

(xmm_mem_imm_new (RegMemImm.Imm (u32_add i 8))))

(rule (sshr_i8x16_bigger_shift ty (RegMemImm.Reg r))

(mov_rmi_to_xmm (RegMemImm.Reg (x64_add ty

r

(RegMemImm.Imm 8)))))

(rule (sshr_i8x16_bigger_shift ty rmi @ (RegMemImm.Mem _m))

(mov_rmi_to_xmm (RegMemImm.Reg (x64_add ty

(imm ty 8)

rmi))))

;; `sshr.{i16x8,i32x4}` can be a simple `psra{w,d}`, we just have to make sure

;; that if the shift amount is in a register, it is in an XMM register.

(rule (lower (has_type ty @ $I16X8 (sshr src amt)))

(x64_psraw src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

(rule (lower (has_type ty @ $I32X4 (sshr src amt)))

(x64_psrad src (mov_rmi_to_xmm (mask_xmm_shift ty amt))))

;; The `sshr.i64x2` CLIF instruction has no single x86 instruction in the older

;; feature sets. To remedy this, a small dance is done with an unsigned right

;; shift plus some extra ops.

(rule 3 (lower (has_type ty @ $I64X2 (sshr src (iconst n))))

(if-let true (use_avx512vl))

(if-let true (use_avx512f))

(x64_vpsraq_imm src (shift_amount_masked ty n)))

(rule 2 (lower (has_type ty @ $I64X2 (sshr src amt)))

(if-let true (use_avx512vl))

(if-let true (use_avx512f))

(let ((masked Gpr (x64_and $I64 amt (RegMemImm.Imm (shift_mask ty)))))

(x64_vpsraq src (x64_movd_to_xmm masked))))

(rule 1 (lower (has_type $I64X2 (sshr src (iconst (u64_from_imm64 (u64_as_u32 amt))))))

(lower_i64x2_sshr_imm src (u32_and amt 63)))

(rule (lower (has_type $I64X2 (sshr src amt)))

(lower_i64x2_sshr_gpr src (x64_and $I64 amt (RegMemImm.Imm 63))))

(decl lower_i64x2_sshr_imm (Xmm u32) Xmm)

;; If the shift amount is less than 32 then do an sshr with 32-bit lanes to

;; produce the upper halves of each result, followed by a ushr of 64-bit lanes

;; to produce the lower halves of each result. Interleave results at the end.

(rule 2 (lower_i64x2_sshr_imm vec imm)

(if-let true (u64_lt imm 32))

(let (

(high32 Xmm (x64_psrad vec (xmi_imm imm)))

(high32 Xmm (x64_pshufd high32 0b11_10_11_01))

(low32 Xmm (x64_psrlq vec (xmi_imm imm)))

(low32 Xmm (x64_pshufd low32 0b11_10_10_00))

)

(x64_punpckldq low32 high32)))

;; If the shift amount is 32 then the `psrlq` from the above rule can be avoided

(rule 1 (lower_i64x2_sshr_imm vec 32)

(let (

(low32 Xmm (x64_pshufd vec 0b11_10_11_01))

(high32 Xmm (x64_psrad vec (xmi_imm 31)))

(high32 Xmm (x64_pshufd high32 0b11_10_11_01))

)

(x64_punpckldq low32 high32)))

;; Shifts >= 32 use one `psrad` to generate the upper bits and second `psrad` to

;; generate the lower bits. Everything is then woven back together with

;; shuffles.

(rule (lower_i64x2_sshr_imm vec imm)

(if-let true (u64_lt 32 imm))

(let (

(high32 Xmm (x64_psrad vec (xmi_imm 31)))

(high32 Xmm (x64_pshufd high32 0b11_10_11_01))

(low32 Xmm (x64_psrad vec (xmi_imm (u32_sub imm 32))))

(low32 Xmm (x64_pshufd low32 0b11_10_11_01))

)

(x64_punpckldq low32 high32)))

;; A variable shift amount is slightly more complicated than the immediate

;; shift amounts from above. The `Gpr` argument is guaranteed to be <= 63 by

;; earlier masking. A `ushr` operation is used with some xor/sub math to

;; generate the sign bits.

(decl lower_i64x2_sshr_gpr (Xmm Gpr) Xmm)

(rule (lower_i64x2_sshr_gpr vec val)

(let (

(val Xmm (x64_movq_to_xmm val))

(mask Xmm (flip_high_bit_mask $I64X2))

(sign_bit_loc Xmm (x64_psrlq mask val))

(ushr Xmm (x64_psrlq vec val))

(ushr_sign_bit_flip Xmm (x64_pxor sign_bit_loc ushr))

)

(x64_psubq ushr_sign_bit_flip sign_bit_loc)))

;;;; Rules for `rotl` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller: we can rely on x86's rotate-amount masking since

;; we operate on the whole register. For const's we mask the constant.

(rule -1 (lower (has_type (fits_in_64 ty) (rotl src amt)))

(x64_rotl ty src (put_masked_in_imm8_gpr amt ty)))

;; `i128`.

(rule (lower (has_type $I128 (rotl src amt)))

(let ((src_ ValueRegs src)

;; NB: Only the low bits of `amt` matter since we logically mask the

;; rotation amount to the value's bit width.

(amt_ Gpr (lo_gpr amt)))

(or_i128 (shl_i128 src_ amt_)

(shr_i128 src_ (x64_sub $I64

(imm $I64 128)

amt_)))))

;;;; Rules for `rotr` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller: we can rely on x86's rotate-amount masking since

;; we operate on the whole register. For const's we mask the constant.

(rule -1 (lower (has_type (fits_in_64 ty) (rotr src amt)))

(x64_rotr ty src (put_masked_in_imm8_gpr amt ty)))

;; `i128`.

(rule (lower (has_type $I128 (rotr src amt)))

(let ((src_ ValueRegs src)

;; NB: Only the low bits of `amt` matter since we logically mask the

;; rotation amount to the value's bit width.

(amt_ Gpr (lo_gpr amt)))

(or_i128 (shr_i128 src_ amt_)

(shl_i128 src_ (x64_sub $I64

(imm $I64 128)

amt_)))))

;;;; Rules for `ineg` ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; `i64` and smaller.

(rule -1 (lower (has_type (fits_in_64 ty) (ineg x)))

(x64_neg ty x))

(rule -2 (lower (has_type $I128 (ineg x)))

;; Get the high/low registers for `x`.