Skip to content

A lightweight WebAssembly runtime that is fast, secure, and standards-compliant

28.6 KB
Raw Blame
;; `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))