;; Algebraic optimizations.
;; Rules here are allowed to rewrite pure expressions arbitrarily,
;; using the same inputs as the original, or fewer. In other words, we
;; cannot pull a new eclass id out of thin air and refer to it, other
;; than a piece of the input or a new node that we construct; but we
;; can freely rewrite e.g. `x+y-y` to `x`.
;; x+0 == 0+x == x.
(rule (simplify (iadd ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (iadd ty
(iconst ty (u64_from_imm64 0))
x))
(subsume x))
;; x-0 == x.
(rule (simplify (isub ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
;; 0-x == (ineg x).
(rule (simplify (isub ty
(iconst ty (u64_from_imm64 0))
x))
(ineg ty x))
;; x*1 == 1*x == x.
(rule (simplify (imul ty
x
(iconst ty (u64_from_imm64 1))))
(subsume x))
(rule (simplify (imul ty
(iconst ty (u64_from_imm64 1))
x))
(subsume x))
;; x*0 == 0*x == x.
(rule (simplify (imul ty
x
(iconst ty (u64_from_imm64 0))))
(iconst ty (imm64 0)))
(rule (simplify (imul ty
(iconst ty (u64_from_imm64 0))
x))
(iconst ty (imm64 0)))
;; x/1 == x.
(rule (simplify (sdiv ty
x
(iconst ty (u64_from_imm64 1))))
(subsume x))
(rule (simplify (udiv ty
x
(iconst ty (u64_from_imm64 1))))
(subsume x))
;; x>>0 == x<<0 == x rotr 0 == x rotl 0 == x.
(rule (simplify (ishl ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (ushr ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (sshr ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (rotr ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (rotl ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
;; x | 0 == 0 | x == x | x == x.
(rule (simplify (bor ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (bor ty
(iconst ty (u64_from_imm64 0))
x))
(subsume x))
(rule (simplify (bor ty x x))
(subsume x))
;; x ^ 0 == 0 ^ x == x.
(rule (simplify (bxor ty
x
(iconst ty (u64_from_imm64 0))))
(subsume x))
(rule (simplify (bxor ty
(iconst ty (u64_from_imm64 0))
x))
(subsume x))
;; x ^ x == 0.
(rule (simplify (bxor (fits_in_64 (ty_int ty)) x x))
(subsume (iconst ty (imm64 0))))
;; x ^ not(x) == not(x) ^ x == -1.
(rule (simplify (bxor $I32 x (bnot $I32 x))) (subsume (iconst $I32 (imm64 0xffff_ffff))))
(rule (simplify (bxor $I32 (bnot $I32 x) x)) (subsume (iconst $I32 (imm64 0xffff_ffff))))
(rule (simplify (bxor $I64 x (bnot $I64 x))) (subsume (iconst $I64 (imm64 0xffff_ffff_ffff_ffff))))
(rule (simplify (bxor $I64 (bnot $I64 x) x)) (subsume (iconst $I64 (imm64 0xffff_ffff_ffff_ffff))))
;; x & -1 == -1 & x == x & x == x.
(rule (simplify (band ty x x)) x)
(rule (simplify (band $I32 x (iconst $I32 (u64_from_imm64 0xffff_ffff)))) (subsume x))
(rule (simplify (band $I32 (iconst $I32 (u64_from_imm64 0xffff_ffff)) x)) (subsume x))
(rule (simplify (band $I64 x (iconst $I64 (u64_from_imm64 0xffff_ffff_ffff_ffff)))) (subsume x))
(rule (simplify (band $I64 (iconst $I64 (u64_from_imm64 0xffff_ffff_ffff_ffff)) x)) (subsume x))
;; x & 0 == 0 & x == 0.
(rule (simplify (band ty x (iconst ty (u64_from_imm64 0)))) (iconst ty (imm64 0)))
(rule (simplify (band ty (iconst ty (u64_from_imm64 0)) x)) (iconst ty (imm64 0)))
;; not(not(x)) == x.
(rule (simplify (bnot ty (bnot ty x))) (subsume x))
;; DeMorgan's rule (two versions):
;; bnot(bor(x, y)) == band(bnot(x), bnot(y))
(rule (simplify (bnot ty (bor ty x y)))
(band ty (bnot ty x) (bnot ty y)))
;; bnot(band(x, y)) == bor(bnot(x), bnot(y))
(rule (simplify (bnot ty (band t x y)))
(bor ty (bnot ty x) (bnot ty y)))
;; `or(and(x, y), not(y)) == or(x, not(y))`
(rule (simplify (bor ty
(band ty x y)
z @ (bnot ty y)))
(bor ty x z))
;; Duplicate the rule but swap the `bor` operands because `bor` is
;; commutative. We could, of course, add a `simplify` rule to do the commutative
;; swap for all `bor`s but this will bloat the e-graph with many e-nodes. It is
;; cheaper to have additional rules, rather than additional e-nodes, because we
;; amortize their cost via ISLE's smart codegen.
(rule (simplify (bor ty
z @ (bnot ty y)
(band ty x y)))
(bor ty x z))
;; `or(and(x, y), not(y)) == or(x, not(y))` specialized for constants, since
;; otherwise we may not know that `z == not(y)` since we don't generally expand
;; constants in the e-graph.
;;
;; (No need to duplicate for commutative `bor` for this constant version because
;; we move constants to the right.)
(rule (simplify (bor ty
(band ty x (iconst ty (u64_from_imm64 y)))
z @ (iconst ty (u64_from_imm64 zk))))
(if-let $true (u64_eq (u64_and (ty_mask ty) zk)
(u64_and (ty_mask ty) (u64_not y))))
(bor ty x z))
;; x*2 == 2*x == x+x.
(rule (simplify (imul ty x (iconst _ (simm32 2))))
(iadd ty x x))
(rule (simplify (imul ty (iconst _ (simm32 2)) x))
(iadd ty x x))
;; x*c == x<<log2(c) when c is a power of two.
;; Note that the type of `iconst` must be the same as the type of `imul`,
;; so these rules can only fire in situations where it's safe to construct an
;; `iconst` of that type.
(rule (simplify (imul ty x (iconst _ (imm64_power_of_two c))))
(ishl ty x (iconst ty (imm64 c))))
(rule (simplify (imul ty (iconst _ (imm64_power_of_two c)) x))
(ishl ty x (iconst ty (imm64 c))))
;; x<<32>>32: uextend/sextend 32->64.
(rule (simplify (ushr $I64 (ishl $I64 (uextend $I64 x @ (value_type $I32)) (iconst _ (simm32 32))) (iconst _ (simm32 32))))
(uextend $I64 x))
(rule (simplify (sshr $I64 (ishl $I64 (uextend $I64 x @ (value_type $I32)) (iconst _ (simm32 32))) (iconst _ (simm32 32))))
(sextend $I64 x))
;; TODO: strength reduction: div to shifts
;; TODO: div/rem by constants -> magic multiplications
;; `(x >> k) << k` is the same as masking off the bottom `k` bits (regardless if
;; this is a signed or unsigned shift right).
(rule (simplify (ishl (fits_in_64 ty)
(ushr ty x (iconst _ k))
(iconst _ k)))
(let ((mask Imm64 (imm64_shl ty (imm64 0xFFFF_FFFF_FFFF_FFFF) k)))
(band ty x (iconst ty mask))))
(rule (simplify (ishl (fits_in_64 ty)
(sshr ty x (iconst _ k))
(iconst _ k)))
(let ((mask Imm64 (imm64_shl ty (imm64 0xFFFF_FFFF_FFFF_FFFF) k)))
(band ty x (iconst ty mask))))
;; Rematerialize ALU-op-with-imm and iconsts in each block where they're
;; used. This is neutral (add-with-imm) or positive (iconst) for
;; register pressure, and these ops are very cheap.
(rule (simplify x @ (iadd _ (iconst _ _) _))
(remat x))
(rule (simplify x @ (iadd _ _ (iconst _ _)))
(remat x))
(rule (simplify x @ (isub _ (iconst _ _) _))
(remat x))
(rule (simplify x @ (isub _ _ (iconst _ _)))
(remat x))
(rule (simplify x @ (band _ (iconst _ _) _))
(remat x))
(rule (simplify x @ (band _ _ (iconst _ _)))
(remat x))
(rule (simplify x @ (bor _ (iconst _ _) _))
(remat x))
(rule (simplify x @ (bor _ _ (iconst _ _)))
(remat x))
(rule (simplify x @ (bxor _ (iconst _ _) _))
(remat x))
(rule (simplify x @ (bxor _ _ (iconst _ _)))
(remat x))
(rule (simplify x @ (bnot _ _))
(remat x))
(rule (simplify x @ (iconst _ _))
(remat x))
(rule (simplify x @ (f32const _ _))
(remat x))
(rule (simplify x @ (f64const _ _))
(remat x))
;; Optimize icmp-of-icmp.
(rule (simplify (icmp ty
(IntCC.NotEqual)
(uextend _ inner @ (icmp ty _ _ _))
(iconst _ (u64_from_imm64 0))))
(subsume inner))
(rule (simplify (icmp ty
(IntCC.Equal)
(uextend _ (icmp ty cc x y))
(iconst _ (u64_from_imm64 0))))
(subsume (icmp ty (intcc_inverse cc) x y)))
;; 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))
(rule (simplify
(select ty (uextend _ c @ (icmp _ _ _ _)) x y))
(select ty c x y))
;; `x == x` is always true for integers; `x != x` is false. Strict
;; inequalities are false, and loose inequalities are true.
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.Equal) x x))
(iconst ty (imm64 1)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.NotEqual) x x))
(iconst ty (imm64 0)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.UnsignedGreaterThan) x x))
(iconst ty (imm64 0)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.UnsignedGreaterThanOrEqual) x x))
(iconst ty (imm64 1)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.SignedGreaterThan) x x))
(iconst ty (imm64 0)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.SignedGreaterThanOrEqual) x x))
(iconst ty (imm64 1)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.UnsignedLessThan) x x))
(iconst ty (imm64 0)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.UnsignedLessThanOrEqual) x x))
(iconst ty (imm64 1)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.SignedLessThan) x x))
(iconst ty (imm64 0)))
(rule (simplify
(icmp (fits_in_64 (ty_int ty)) (IntCC.SignedLessThanOrEqual) x x))
(iconst ty (imm64 1)))