A lightweight WebAssembly runtime that is fast, secure, and standards-compliant
;; `icmp`-related rewrites
;; `x == x` is always true for integers; `x != x` is false. Strict
;; inequalities are false, and loose inequalities are true.
(rule (simplify (has_type ty (eq _ x x))) (subsume (cmp_true ty)))
(rule (simplify (has_type ty (ne _ x x))) (subsume (all_zero ty)))
(rule (simplify (has_type ty (ugt _ x x))) (subsume (all_zero ty)))
(rule (simplify (has_type ty (uge _ x x))) (subsume (cmp_true ty)))
(rule (simplify (has_type ty (sgt _ x x))) (subsume (all_zero ty)))
(rule (simplify (has_type ty (sge _ x x))) (subsume (cmp_true ty)))
(rule (simplify (has_type ty (ult _ x x))) (subsume (all_zero ty)))
(rule (simplify (has_type ty (ule _ x x))) (subsume (cmp_true ty)))
(rule (simplify (has_type ty (slt _ x x))) (subsume (all_zero ty)))
(rule (simplify (has_type ty (sle _ x x))) (subsume (cmp_true ty)))
;; For integers, adding the same thing on both sides of an equality check
;; (or an inequality check) doesn't change the result.
;; This applies for arbitrary expressions, not just constants, so we need to
;; check all possible orderings since nothing normalizes it.
(rule (simplify (eq ty (iadd _ a k) (iadd _ b k)))
(subsume (eq ty a b)))
(rule (simplify (eq ty (iadd _ a k) (iadd _ k b)))
(subsume (eq ty a b)))
(rule (simplify (eq ty (iadd _ k a) (iadd _ b k)))
(subsume (eq ty a b)))
(rule (simplify (eq ty (iadd _ k a) (iadd _ k b)))
(subsume (eq ty a b)))
(rule (simplify (ne ty (iadd _ a k) (iadd _ b k)))
(subsume (ne ty a b)))
(rule (simplify (ne ty (iadd _ a k) (iadd _ k b)))
(subsume (ne ty a b)))
(rule (simplify (ne ty (iadd _ k a) (iadd _ b k)))
(subsume (ne ty a b)))
(rule (simplify (ne ty (iadd _ k a) (iadd _ k b)))
(subsume (ne ty a b)))
;; To avoid repeating all the above rules again, normalize isub to iadd
;; (a - b) == (c - d) ⟹ (a + d) == (c + b)
(rule (simplify (eq ty1 (isub ty2 a b) (isub ty3 c d)))
(eq ty1 (iadd ty2 a d) (iadd ty3 c b)))
(rule (simplify (ne ty1 (isub ty2 a b) (isub ty3 c d)))
(ne ty1 (iadd ty2 a d) (iadd ty3 c b)))
;; Optimize icmp-of-icmp.
;; ne(icmp(ty, cc, x, y), 0) == icmp(ty, cc, x, y)
;; e.g. neq(ugt(x, y), 0) == ugt(x, y)
(rule (simplify (ne _
(uextend_maybe _ inner @ (icmp _ _ _ _))
(all_zero _)))
(subsume inner))
;; Likewise for icmp-of-fcmp.
;; ne(fcmp(ty, cc, x, y), 0) == fcmp(ty, cc, x, y)
(rule (simplify (ne _
(uextend_maybe _ inner @ (fcmp _ _ _ _))
(all_zero _)))
(subsume inner))
;; eq(icmp(ty, cc, x, y), 0) == icmp(ty, cc_complement, x, y)
;; e.g. eq(ugt(x, y), 0) == ule(x, y)
(rule (simplify (eq _
(uextend_maybe _ (icmp ty cc x y))
(all_zero _)))
(subsume (icmp ty (intcc_complement cc) x y)))
;; ne(icmp(ty, cc, x, y), 1) == icmp(ty, cc_complement, x, y)
;; e.g. ne(ugt(x, y), 1) == ule(x, y)
(rule (simplify (ne _
(uextend_maybe _ (icmp ty cc x y))
(iconst_u _ 1)))
(subsume (icmp ty (intcc_complement cc) x y)))
;; eq(icmp(ty, cc, x, y), 1) == icmp(ty, cc, x, y)
;; e.g. eq(ugt(x, y), 1) == ugt(x, y)
(rule (simplify (eq ty
(uextend_maybe _ inner @ (icmp _ _ _ _))
(iconst_u _ 1)))
(subsume inner))
;; Optimize select-of-uextend-of-icmp to select-of-icmp, because
;; select can take an I8 condition too.
(rule (simplify
(select ty (uextend _ c @ (icmp _ _ _ _)) x y))
(select ty c x y))
;; Masking the result of a comparison with 1 always results in the comparison
;; itself. Note that comparisons in wasm may sometimes be hidden behind
;; extensions.
(rule (simplify
(band (ty_int _)
cmp @ (icmp _ _ _ _)
(iconst_u _ 1)))
cmp)
(rule (simplify
(band (ty_int _)
extend @ (uextend _ (icmp _ _ _ _))
(iconst_u _ 1)))
extend)
;; Comparisons against largest/smallest signed/unsigned values:
;; ult(x, 0) == false.
(rule (simplify (has_type bty (ult _ x zero @ (all_zero _))))
(subsume (all_zero bty)))
;; ule(x, 0) == eq(x, 0)
(rule (simplify (ule (fits_in_64 (ty_int cty)) x zero @ (all_zero _)))
(eq cty x zero))
;; ugt(x, 0) == ne(x, 0).
(rule (simplify (ugt (fits_in_64 (ty_int cty)) x zero @ (all_zero _)))
(ne cty x zero))
;; uge(x, 0) == true.
(rule (simplify (has_type bty (uge _ x zero @ (all_zero _))))
(subsume (cmp_true bty)))
;; ult(x, UMAX) == ne(x, UMAX).
(rule (simplify (ult (fits_in_64 (ty_int cty)) x umax @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_umax cty)))
(ne cty x umax))
;; ule(x, UMAX) == true.
(rule (simplify (has_type bty (ule (fits_in_64 (ty_int cty)) x umax @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_umax cty)))
(subsume (iconst_u bty 1)))
;; ugt(x, UMAX) == false.
(rule (simplify (has_type bty (ugt (fits_in_64 (ty_int cty)) x umax @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_umax cty)))
(subsume (all_zero bty)))
;; uge(x, UMAX) == eq(x, UMAX).
(rule (simplify (uge (fits_in_64 (ty_int cty)) x umax @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_umax cty)))
(eq cty x umax))
;; slt(x, SMIN) == false.
(rule (simplify (has_type bty (slt (fits_in_64 (ty_int cty)) x smin @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_smin cty)))
(subsume (all_zero bty)))
;; sle(x, SMIN) == eq(x, SMIN).
(rule (simplify (sle (fits_in_64 (ty_int cty)) x smin @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_smin cty)))
(eq cty x smin))
;; sgt(x, SMIN) == ne(x, SMIN).
(rule (simplify (sgt (fits_in_64 (ty_int cty)) x smin @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_smin cty)))
(ne cty x smin))
;; sge(x, SMIN) == true.
(rule (simplify (has_type bty (sge (fits_in_64 (ty_int cty)) x smin @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_smin cty)))
(subsume (iconst_u bty 1)))
;; slt(x, SMAX) == ne(x, SMAX).
(rule (simplify (slt (fits_in_64 (ty_int cty)) x smax @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_smax cty)))
(ne cty x smax))
;; sle(x, SMAX) == true.
(rule (simplify (has_type bty (sle (fits_in_64 (ty_int cty)) x smax @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_smax cty)))
(subsume (iconst_u bty 1)))
;; sgt(x, SMAX) == false.
(rule (simplify (has_type bty (sgt (fits_in_64 (ty_int cty)) x smax @ (iconst_u cty y))))
(if-let true (u64_eq y (ty_smax cty)))
(subsume (all_zero bty)))
;; sge(x, SMAX) == eq(x, SMAX).
(rule (simplify (sge (fits_in_64 (ty_int cty)) x smax @ (iconst_u cty y)))
(if-let true (u64_eq y (ty_smax cty)))
(eq cty x smax))
;; `band`/`bor` of 2 comparisons:
(rule (simplify (band (fits_in_64 bty) (icmp ty cc1 x y) (icmp ty cc2 x y)))
(if-let signed (intcc_comparable cc1 cc2))
(compose_icmp bty ty (u64_and (decompose_intcc cc1) (decompose_intcc cc2)) signed x y))
(rule (simplify (bor (fits_in_64 bty) (icmp ty cc1 x y) (icmp ty cc2 x y)))
(if-let signed (intcc_comparable cc1 cc2))
(compose_icmp bty ty (u64_or (decompose_intcc cc1) (decompose_intcc cc2)) signed x y))
;; Prefer comparing against zero
;; uge(x, 1) == ne(x, 0)
(rule (simplify (uge ty x (iconst_u cty 1)))
(ne ty x (all_zero cty)))
;; ult(x, 1) == eq(x, 0)
(rule (simplify (ult ty x (iconst_u cty 1)))
(eq ty x (all_zero cty)))
;; sge(x, 1) == sgt(x, 0)
(rule (simplify (sge ty x (iconst_s cty 1)))
(sgt ty x (all_zero cty)))
;; slt(x, 1) == sle(x, 0)
(rule (simplify (slt ty x (iconst_s cty 1)))
(sle ty x (all_zero cty)))
;; sgt(x, -1) == sge(x, 0)
(rule (simplify (sgt ty x (iconst_s cty -1)))
(sge ty x (all_zero cty)))
;; sle(x, -1) == slt(x, 0)
(rule (simplify (sle ty x (iconst_s cty -1)))
(slt ty x (all_zero cty)))
(decl pure partial intcc_comparable (IntCC IntCC) bool)
(rule (intcc_comparable x y)
(if-let (u64_extract_non_zero class) (u64_and (intcc_class x) (intcc_class y)))
(u64_eq 2 class))
(decl pure decompose_intcc (IntCC) u64)
(rule (decompose_intcc (IntCC.Equal)) 1)
(rule (decompose_intcc (IntCC.UnsignedLessThan)) 2)
(rule (decompose_intcc (IntCC.SignedLessThan)) 2)
(rule (decompose_intcc (IntCC.UnsignedLessThanOrEqual)) 3)
(rule (decompose_intcc (IntCC.SignedLessThanOrEqual)) 3)
(rule (decompose_intcc (IntCC.UnsignedGreaterThan)) 4)
(rule (decompose_intcc (IntCC.SignedGreaterThan)) 4)
(rule (decompose_intcc (IntCC.UnsignedGreaterThanOrEqual)) 5)
(rule (decompose_intcc (IntCC.SignedGreaterThanOrEqual)) 5)
(rule (decompose_intcc (IntCC.NotEqual)) 6)
;; Compose a comparison from its decomposed condition code. The first type
;; is the comparison's result type, the second its operand (controlling) type.
(decl compose_icmp (Type Type u64 bool Value Value) Value)
(rule (compose_icmp bty _ 0 _ _ _) (subsume (all_zero bty)))
(rule (compose_icmp _ ty 1 _ x y) (icmp ty (IntCC.Equal) x y))
(rule (compose_icmp _ ty 2 false x y) (icmp ty (IntCC.UnsignedLessThan) x y))
(rule (compose_icmp _ ty 2 true x y) (icmp ty (IntCC.SignedLessThan) x y))
(rule (compose_icmp _ ty 3 false x y) (icmp ty (IntCC.UnsignedLessThanOrEqual) x y))
(rule (compose_icmp _ ty 3 true x y) (icmp ty (IntCC.SignedLessThanOrEqual) x y))
(rule (compose_icmp _ ty 4 false x y) (icmp ty (IntCC.UnsignedGreaterThan) x y))
(rule (compose_icmp _ ty 4 true x y) (icmp ty (IntCC.SignedGreaterThan) x y))
(rule (compose_icmp _ ty 5 false x y) (icmp ty (IntCC.UnsignedGreaterThanOrEqual) x y))
(rule (compose_icmp _ ty 5 true x y) (icmp ty (IntCC.SignedGreaterThanOrEqual) x y))
(rule (compose_icmp _ ty 6 _ x y) (icmp ty (IntCC.NotEqual) x y))
(rule (compose_icmp bty _ 7 _ _ _) (subsume (iconst_u bty 1)))
(decl pure intcc_class (IntCC) u64)
(rule (intcc_class (IntCC.UnsignedLessThan)) 1)
(rule (intcc_class (IntCC.UnsignedLessThanOrEqual)) 1)
(rule (intcc_class (IntCC.UnsignedGreaterThan)) 1)
(rule (intcc_class (IntCC.UnsignedGreaterThanOrEqual)) 1)
(rule (intcc_class (IntCC.SignedLessThan)) 2)
(rule (intcc_class (IntCC.SignedLessThanOrEqual)) 2)
(rule (intcc_class (IntCC.SignedGreaterThan)) 2)
(rule (intcc_class (IntCC.SignedGreaterThanOrEqual)) 2)
(rule (intcc_class (IntCC.Equal)) 3)
(rule (intcc_class (IntCC.NotEqual)) 3)
;; Pattern-match what LLVM emits today for 128-bit comparisons into actual
;; 128-bit comparisons. Platforms like x64 and aarch64 have more optimal
;; lowerings for 128-bit arithmetic than the default structure.
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(uge _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(uge _ a_hi b_hi)))
(uge $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(uge _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(sge _ a_hi b_hi)))
(sge $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ugt _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(ugt _ a_hi b_hi)))
(ugt $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ugt _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(sgt _ a_hi b_hi)))
(sgt $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ule _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(ule _ a_hi b_hi)))
(ule $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ule _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(sle _ a_hi b_hi)))
(sle $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ult _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(ult _ a_hi b_hi)))
(ult $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (select _ (eq _ a_hi @ (value_type $I64) b_hi @ (value_type $I64))
(ult _ a_lo @ (value_type $I64) b_lo @ (value_type $I64))
(slt _ a_hi b_hi)))
(slt $I128 (iconcat $I64 a_lo a_hi) (iconcat $I64 b_lo b_hi)))
(rule (simplify (eq cty x (bxor (ty_int bty) x y))) (subsume (eq cty y (all_zero bty))))
(rule (simplify (ne cty x (bxor (ty_int bty) x y))) (subsume (ne cty y (all_zero bty))))
; (x - y) > x == y > x
(rule (simplify (ugt cty (isub ty x y) x)) (ugt cty y x))
(rule (simplify (ule cty (isub ty x y) x)) (ule cty y x))
;; (x < y) ? x : y != x == x > y, for both signed and unsigned.
(rule (simplify (ne ty (select ty (slt ty x y) x y) x)) (sgt ty x y))
(rule (simplify (ne ty (select ty (ult ty x y) x y) x)) (ugt ty x y))
(rule (simplify (ult cty (bnot ty x) (bnot ty y))) (ugt cty x y))
(rule (simplify (slt cty (bnot ty x) (bnot ty y))) (sgt cty x y))
;; a < b ^^ a > b => (a ≠ b)
(rule (simplify (bxor _ (sgt ty x y) (sgt ty y x))) (ne ty x y))
(rule (simplify (bxor _ (sgt ty x y) (slt ty x y))) (ne ty x y))
(rule (simplify (bxor _ (slt ty x y) (sgt ty x y))) (ne ty x y))
(rule (simplify (bxor _ (slt ty x y) (slt ty y x))) (ne ty x y))
(rule (simplify (bxor _ (ugt ty x y) (ugt ty y x))) (ne ty x y))
(rule (simplify (bxor _ (ugt ty x y) (ult ty x y))) (ne ty x y))
(rule (simplify (bxor _ (ult ty x y) (ugt ty x y))) (ne ty x y))
(rule (simplify (bxor _ (ult ty x y) (ult ty y x))) (ne ty x y))
;; a < b && a > b = false
(rule (simplify (band (ty_int_vec128 bty) (sgt ty x y) (slt ty x y))) (all_zero bty))
(rule (simplify (band (ty_int_vec128 bty) (slt ty x y) (sgt ty x y))) (all_zero bty))
(rule (simplify (band (ty_int_vec128 bty) (ugt ty x y) (ult ty x y))) (all_zero bty))
(rule (simplify (band (ty_int_vec128 bty) (ult ty x y) (ugt ty x y))) (all_zero bty))
(rule
(simplify (band bty (sgt _ x (iconst_s _ y)) (ult _ x (iconst_s _ y))))
(if-let true (i64_gt_eq y 0))
(all_zero bty))
(rule
(simplify (band bty (sgt _ (iconst_s _ x) y) (ult _ (iconst_s _ x) y)))
(if-let true (i64_lt x 0))
(all_zero bty))
(rule
(simplify (band bty (slt _ x (iconst_s _ y)) (ugt _ x (iconst_s _ y))))
(if-let true (i64_lt y 0))
(all_zero bty))
(rule
(simplify (band bty (slt _ (iconst_s _ x) y) (ugt _ (iconst_s _ x) y)))
(if-let true (i64_gt_eq x 0))
(all_zero bty))
(rule
(simplify (band bty (ugt _ x (iconst_s _ y)) (slt _ x (iconst_s _ y))))
(if-let true (i64_lt y 0))
(all_zero bty))
(rule
(simplify (band bty (ugt _ (iconst_s _ x) y) (slt _ (iconst_s _ x) y)))
(if-let true (i64_gt_eq x 0))
(all_zero bty))
(rule
(simplify (band bty (ult _ x (iconst_s _ y)) (sgt _ x (iconst_s _ y))))
(if-let true (i64_gt_eq y 0))
(all_zero bty))
(rule
(simplify (band bty (ult _ (iconst_s _ x) y) (sgt _ (iconst_s _ x) y)))
(if-let true (i64_lt x 0))
(all_zero bty))
;; (x < y) & (x ≠ -1) = (x < y)
(rule
(simplify (band _ (ne ty x (iconst_s _ -1)) (ugt ty y x)))
(ult ty x y))
(rule
(simplify (band _ (ne ty x (iconst_s _ -1)) (ult ty x z)))
(ult ty x z))
(rule
(simplify (band _ (ne ty (iconst_s _ -1) x) (ugt ty y x)))
(ult ty x y))
(rule
(simplify (band _ (ne ty (iconst_s _ -1) x) (ult ty x z)))
(ult ty x z))
(rule
(simplify (band _ (ugt ty x y) (ne ty y (iconst_s _ -1))))
(ult ty y x))
(rule
(simplify (band _ (ugt ty x y) (ne ty (iconst_s _ -1) y)))
(ult ty y x))
(rule
(simplify (band _ (ult ty x y) (ne ty x (iconst_s _ -1))))
(ult ty x y))
(rule
(simplify (band _ (ult ty x y) (ne ty (iconst_s _ -1) x)))
(ult ty x y))
;; icmp on select with two constant inputs compared with one of the two
;; constants can directly use the inner select condition.
;; See: https://github.com/bytecodealliance/wasmtime/issues/11578
(rule (simplify (eq _
(select _ inner_cond @ (value_type inner_ty)
(iconst_u _ k1)
(iconst_u _ k2))
(iconst_u _ k1)))
(if-let false (u64_eq k1 k2))
(ne inner_ty inner_cond (all_zero inner_ty)))
(rule (simplify (eq _
(select _ inner_cond @ (value_type inner_ty)
(iconst_u _ k1)
(iconst_u _ k2))
(iconst_u _ k2)))
(if-let false (u64_eq k1 k2))
(eq inner_ty inner_cond (all_zero inner_ty)))
(rule (simplify (ne _
(select _ inner_cond @ (value_type inner_ty)
(iconst_u _ k1)
(iconst_u _ k2))
(iconst_u _ k1)))
(if-let false (u64_eq k1 k2))
(eq inner_ty inner_cond (all_zero inner_ty)))
(rule (simplify (ne _
(select _ inner_cond @ (value_type inner_ty)
(iconst_u _ k1)
(iconst_u _ k2))
(iconst_u _ k2)))
(if-let false (u64_eq k1 k2))
(ne inner_ty inner_cond (all_zero inner_ty)))
;;;;; Boolean-context simplifications for `ctz` and `clz` ;;;;;;;;;;;;;;;;;;;;;;
;;
;; When a count-trailing/leading-zeros instruction's result is fed into a
;; comparison against zero (the consumer cares whether the count is zero,
;; not its numeric value), rewrite to test the corresponding bit of X
;; directly:
;;
;; ctz(X) == 0 iff LSB of X is set iff (X & 1) != 0
;; clz(X) == 0 iff MSB of X is set iff X is signed-negative
;;
;; LZCNT/TZCNT/BSF/BSR each cost ~3 cycles on Intel and write a GPR (creating
;; a false dependency); the rewritten forms emit a single-cycle `test` whose
;; result lives only in flags. JIT-less interpreters benefit even more — their
;; bit-counting paths are typically loops.
;;
;; The matching wasm-side fold is in WebAssembly/binaryen#8562 (LSB→ctz under
;; `-Os`). With these mid-end rules in place, that fold becomes cycle-neutral
;; on cranelift JITs even when produced unconditionally.
;; ctz(X) == 0 iff the LSB of X is 1, i.e. (X & 1) != 0.
(rule (simplify (eq result_ty (ctz x_ty X) (all_zero _)))
(ne result_ty (band x_ty X (iconst_u x_ty 1)) (all_zero x_ty)))
;; ctz(X) != 0 iff the LSB of X is 0, i.e. (X & 1) == 0.
(rule (simplify (ne result_ty (ctz x_ty X) (all_zero _)))
(eq result_ty (band x_ty X (iconst_u x_ty 1)) (all_zero x_ty)))
;; clz(X) == 0 iff the MSB of X is 1, i.e. X is signed-negative.
;; Lowers to `test X, X; js` on x86_64 — single-instruction sign-bit test.
(rule (simplify (eq result_ty (clz x_ty X) (all_zero _)))
(slt result_ty X (all_zero x_ty)))
;; clz(X) != 0 iff the MSB of X is 0, i.e. X is signed-non-negative.
(rule (simplify (ne result_ty (clz x_ty X) (all_zero _)))
(sge result_ty X (all_zero x_ty)))
;;;;; Same simplifications applied directly when the count-leading /
;;;;; trailing-zeros value is consumed as a `brif` condition (the 2-op
;;;;; wasm pattern `i32.ctz; br_if`, with no `i32.eqz` interposed for the
;;;;; rules above to hinge on). We rewrite only the condition operand in
;;;;; place; the brif's successors are unchanged so the CFG is preserved.
;; `brif (ctz X) bt be` branches when `ctz(X) != 0`, i.e. LSB(X) == 0.
(rule (simplify_skeleton (brif (ctz x_ty X) _ _))
(replace_branch_cond
(eq x_ty (band x_ty X (iconst_u x_ty 1)) (all_zero x_ty))))
;; `brif (clz X) bt be` branches when `clz(X) != 0`, i.e. MSB(X) == 0.
(rule (simplify_skeleton (brif (clz x_ty X) _ _))
(replace_branch_cond (sge x_ty X (all_zero x_ty))))
;; Same when an `ireduce` (truncation) sits between the count and the
;; brif. The count is in [0, bitwidth] so the truncation is lossless.
(rule (simplify_skeleton (brif (ireduce _ (ctz x_ty x)) _ _))
(replace_branch_cond
(eq x_ty (band x_ty x (iconst_u x_ty 1)) (all_zero x_ty))))
(rule (simplify_skeleton (brif (ireduce _ (clz x_ty x)) _ _))
(replace_branch_cond (sge x_ty x (all_zero x_ty))))
;; ~x == x --> 0
(rule (simplify (has_type ty (eq _ (bnot cty x) x))) (subsume (all_zero ty)))
;; ~x != x --> 1
(rule (simplify (has_type ty (ne _ (bnot cty x) x))) (subsume (cmp_true ty)))
;; x >=u (x - y) --> x >=u y
(rule (simplify (uge rty x (isub ty x y))) (uge rty x y))
(rule (simplify (ult rty x (isub ty x y))) (ult rty x y))
;; x >=u (x >>u y) --> true
(rule (simplify (has_type rty (uge _ x (ushr ty x y)))) (cmp_true rty))
(rule (simplify (has_type rty (ule _ (ushr ty x y) x))) (cmp_true rty))
(rule (simplify (has_type rty (ugt _ (ushr ty x y) x))) (subsume (all_zero rty)))
(rule (simplify (has_type rty (ult _ x (ushr ty x y)))) (subsume (all_zero rty)))
;; smin(x, y) > smax(x, y) --> false
(rule (simplify (has_type ty (sgt _ (smin cty x y) (smax cty x y)))) (all_zero ty))
;; umin(x, y) > umax(x, y) --> false
(rule (simplify (has_type ty (ugt _ (umin cty x y) (umax cty x y)))) (all_zero ty))
;; smin(x, y) <= smax(x, y) --> true
(rule (simplify (has_type ty (sle _ (smin cty x y) (smax cty x y)))) (cmp_true ty))
(rule (simplify (has_type ty (sle _ (smin cty x y) (smax cty y x)))) (cmp_true ty))
;; umin(x, y) <= umax(x, y) --> true
(rule (simplify (has_type ty (ule _ (umin cty x y) (umax cty x y)))) (cmp_true ty))
(rule (simplify (has_type ty (ule _ (umin cty x y) (umax cty y x)))) (cmp_true ty))
;; smin(x, y) == smax(x, y) --> x == y
(rule (simplify (eq ty (smin cty x y) (smax cty x y))) (eq ty x y))
(rule (simplify (eq ty (smin cty x y) (smax cty y x))) (eq ty x y))
;; smin(x, y) != smax(x, y) --> x != y
(rule (simplify (ne ty (smin cty x y) (smax cty x y))) (ne ty x y))
(rule (simplify (ne ty (smin cty x y) (smax cty y x))) (ne ty x y))
;; (x - y) == 0 --> x == y
(rule (simplify (eq ty (isub cty x y) (all_zero cty))) (eq ty x y))
;; (x - y) != 0 --> x != y
(rule (simplify (ne ty (isub cty x y) (all_zero cty))) (ne ty x y))
;; (x ^ y) == 0 --> x == y
(rule (simplify (eq ty (bxor cty x y) (all_zero cty))) (eq ty x y))
;; (x ^ y) != 0 --> x != y
(rule (simplify (ne ty (bxor cty x y) (all_zero cty))) (ne ty x y))
;; (x ^ y) == x --> y == 0
(rule (simplify (eq ty (bxor cty x y) x)) (eq ty y (all_zero cty)))
;; (x + y) != x --> y != 0
(rule (simplify (ne ty (iadd cty x y) x)) (ne ty y (all_zero cty)))
;; -x != -y --> x != y
(rule (simplify (ne ty (ineg cty x) (ineg cty y))) (ne ty x y))
;; (x >>s y) >s -1 --> x >=s 0
(rule (simplify (sgt ty (sshr cty x y) (iconst_s cty -1)))
(subsume (sge ty x (all_zero cty))))
;; (x >>s y) >=s 0 --> x >=s 0
(rule (simplify (sge ty (sshr cty x y) (all_zero cty)))
(subsume (sge ty x (all_zero cty))))
;; rotl(x, k) == rotl(y, k) --> x == y
(rule (simplify (eq ty (rotl cty x k) (rotl cty y k)))
(subsume (eq ty x y)))
;; (x >=s 0) & (x <s N) --> x <u N, 0 < N < 2^(B - 1)
(rule (simplify (band _
(sge ty x (all_zero ty))
(slt ty x n @ (iconst_s (ty_int ty) limit))))
(if-let true (i64_gt limit 0))
(ult ty x n))
(rule (simplify (band _
(slt ty x n @ (iconst_s (ty_int ty) limit))
(sge ty x (all_zero ty))))
(if-let true (i64_gt limit 0))
(ult ty x n))
;; x == ((x + (y >>u (B - k))) & -2^k) --> (x & (2^k - 1)) == 0
(rule (simplify (eq rty x
(band (ty_int ty)
(iadd ty x (ushr ty y (iconst_u _ shift)))
(iconst_s ty mask))))
(if-let true (i64_is_negative_power_of_two mask))
(if-let bits (i64_trailing_zeros mask))
(if-let true (u32_lt bits (ty_bits ty)))
(if-let true (u64_eq (u64_and shift (ty_shift_mask ty))
(u64_sub (ty_bits_u64 ty) bits)))
(subsume (eq rty (band ty x (iconst_s ty (i64_wrapping_sub (i64_wrapping_neg mask) 1)))
(all_zero ty))))
(rule (simplify (eq rty x
(band (ty_int ty)
(iadd ty (ushr ty y (iconst_u _ shift)) x)
(iconst_s ty mask))))
(if-let true (i64_is_negative_power_of_two mask))
(if-let bits (i64_trailing_zeros mask))
(if-let true (u32_lt bits (ty_bits ty)))
(if-let true (u64_eq (u64_and shift (ty_shift_mask ty))
(u64_sub (ty_bits_u64 ty) bits)))
(subsume (eq rty (band ty x (iconst_s ty (i64_wrapping_sub (i64_wrapping_neg mask) 1)))
(all_zero ty))))
(rule (simplify (eq rty
(band (ty_int ty)
(iadd ty x (ushr ty y (iconst_u _ shift)))
(iconst_s ty mask))
x))
(if-let true (i64_is_negative_power_of_two mask))
(if-let bits (i64_trailing_zeros mask))
(if-let true (u32_lt bits (ty_bits ty)))
(if-let true (u64_eq (u64_and shift (ty_shift_mask ty))
(u64_sub (ty_bits_u64 ty) bits)))
(subsume (eq rty (band ty x (iconst_s ty (i64_wrapping_sub (i64_wrapping_neg mask) 1)))
(all_zero ty))))
(rule (simplify (eq rty
(band (ty_int ty)
(iadd ty (ushr ty y (iconst_u _ shift)) x)
(iconst_s ty mask))
x))
(if-let true (i64_is_negative_power_of_two mask))
(if-let bits (i64_trailing_zeros mask))
(if-let true (u32_lt bits (ty_bits ty)))
(if-let true (u64_eq (u64_and shift (ty_shift_mask ty))
(u64_sub (ty_bits_u64 ty) bits)))
(subsume (eq rty (band ty x (iconst_s ty (i64_wrapping_sub (i64_wrapping_neg mask) 1)))
(all_zero ty))))
;; (x == y) ^ 1 --> x != y
(rule (simplify (bxor bty
(eq cty x y)
(iconst_u bty 1)))
(ne cty x y))
;; x >u (x - 1) --> x != 0
(rule (simplify (ugt ty x (isub cty x (iconst_u cty 1))))
(ne ty x (iconst_u cty 0)))
(rule (simplify (ult ty (isub cty x (iconst_u cty 1)) x))
(ne ty x (iconst_u cty 0)))
;; rotr(x, k) == rotr(y, k) --> x == y
(rule (simplify (eq ty (rotr cty x k) (rotr cty y k)))
(subsume (eq ty x y)))
;; (x != 0) | (y != 0) --> (x | y) != 0
(rule (simplify (bor _ (ne cty x (iconst_u cty 0)) (ne cty y (iconst_u cty 0)))) (ne cty (bor cty x y) (all_zero cty)))
;; (x == 0) & (y == 0) --> (x | y) == 0
(rule (simplify (band _ (eq cty x (iconst_u cty 0)) (eq cty y (iconst_u cty 0)))) (eq cty (bor cty x y) (all_zero cty)))
;; (x << 1) == x --> x == 0
(rule (simplify (eq ty (ishl cty x (iconst_u _ 1)) x)) (eq ty x (all_zero cty)))
(rule (simplify (eq ty x (ishl cty x (iconst_u _ 1)))) (eq ty x (all_zero cty)))
;; (x >>u 1) == x --> x == 0
(rule (simplify (eq ty (ushr cty x (iconst_u _ 1)) x)) (eq ty x (all_zero cty)))
(rule (simplify (eq ty x (ushr cty x (iconst_u _ 1)))) (eq ty x (all_zero cty)))
;; (~x & y) == y --> (y & x) == 0
(rule (simplify (eq ty (band cty (bnot cty x) y) y)) (eq ty (band cty y x) (all_zero cty)))
(rule (simplify (eq ty (band cty x (bnot cty y)) x)) (eq ty (band cty x y) (all_zero cty)))
(rule (simplify (eq ty x (band cty (bnot cty y) x))) (eq ty (band cty x y) (all_zero cty)))
(rule (simplify (eq ty x (band cty x (bnot cty y)))) (eq ty (band cty x y) (all_zero cty)))
;; umax(x, y) OP 0 --> (x | y) OP 0 (OP = {==, !=})
(rule (simplify (eq ty (umax cty x y) (all_zero cty))) (eq ty (bor cty x y) (all_zero cty)))
(rule (simplify (ne ty (umax cty x y) (all_zero cty))) (ne ty (bor cty x y) (all_zero cty)))
;; umax(x, y) OP umin(x, y) --> x OP y (OP = {==, !=})
(rule (simplify (eq ty (umax cty x y) (umin cty x y))) (eq ty x y))
(rule (simplify (eq ty (umax cty x y) (umin cty y x))) (eq ty x y))
(rule (simplify (eq ty (umin cty x y) (umax cty x y))) (eq ty x y))
(rule (simplify (eq ty (umin cty x y) (umax cty y x))) (eq ty x y))
(rule (simplify (ne ty (umax cty x y) (umin cty x y))) (ne ty x y))
(rule (simplify (ne ty (umax cty x y) (umin cty y x))) (ne ty x y))
(rule (simplify (ne ty (umin cty x y) (umax cty x y))) (ne ty x y))
(rule (simplify (ne ty (umin cty x y) (umax cty y x))) (ne ty x y))
;; ~x == (~x | y) --> (y & x) == 0
(rule (simplify (eq ty (bnot cty x) (bor cty (bnot cty x) y))) (eq ty (band cty y x) (all_zero cty)))
(rule (simplify (eq ty (bnot cty x) (bor cty y (bnot cty x)))) (eq ty (band cty y x) (all_zero cty)))
(rule (simplify (eq ty (bor cty (bnot cty x) y) (bnot cty x))) (eq ty (band cty y x) (all_zero cty)))
(rule (simplify (eq ty (bor cty x (bnot cty y)) (bnot cty y))) (eq ty (band cty x y) (all_zero cty)))
;; (c ? x : y) == (c ? y : x) --> x == y
(rule (simplify (eq ty (select cty x y z) (select cty x z y))) (eq ty y z))
;; (x >=s y) & (y >=s x) --> x == y
(rule (simplify (band _ (sge cty x y) (sge cty y x))) (eq cty x y))
(rule (simplify (band _ (sge cty x y) (sle cty x y))) (eq cty x y))
(rule (simplify (band _ (sle cty x y) (sge cty x y))) (eq cty x y))
(rule (simplify (band _ (sle cty x y) (sle cty y x))) (eq cty x y))
;; (x >=u y) & (y >=u x) --> x == y
(rule (simplify (band _ (uge cty x y) (uge cty y x))) (eq cty x y))
(rule (simplify (band _ (uge cty x y) (ule cty x y))) (eq cty x y))
(rule (simplify (band _ (ule cty x y) (uge cty x y))) (eq cty x y))
(rule (simplify (band _ (ule cty x y) (ule cty y x))) (eq cty x y))