[Cranelift] add select simplification rules (#12742)

* [Cranelift] select rules add

* Update cranelift/codegen/src/opts/selects.isle

Co-authored-by: Nick Fitzgerald <[email protected]>

* [Craneli

[Cranelift] add select simplification rules (#12742)

* [Cranelift] select rules add

* Update cranelift/codegen/src/opts/selects.isle

Co-authored-by: Nick Fitzgerald <[email protected]>

* [Cranelift] generalize select simplification

---------

Co-authored-by: Nick Fitzgerald <[email protected]>

show more ...

Fix ISLE optimization for vector inputs (#12179)

Add some more `fits_in_64` constraints to types to handle the fact that
`iconst_u` can't construct a 128-bit output.

Closes #12170

[Cranelift] `min x y < y => false` (#11998)

* [Cranelift] `min x y < y => false`

* fix tet

* add comm/flipped

* remove redundancies after renaming

[Cranelift] folds selects (#11648)

* [Cranelift] add opts and tests

* [Cranelift] update tests

* [Cranelift] generalize cases

* [Cranelift] update tests

* [Cranelift] rename test

Use a wrapping add in egraph optimizations (#11588)

* Use a wrapping add in egraph optimizations

This commit fixes an accidental bug from #11526 found via fuzzing where
the `u64_add` helper in ISLE

Use a wrapping add in egraph optimizations (#11588)

* Use a wrapping add in egraph optimizations

This commit fixes an accidental bug from #11526 found via fuzzing where
the `u64_add` helper in ISLE is a panicking add but the desired
semantics here were a wrapping add. A test is added here and the
additions are updated to `u64_wrapping_add` instead.

* Add output assertion

show more ...

Fix a verifier error generated during optimizations (#11562)

This commit fixes an accidental regression from #11526 detected on
OSS-Fuzz. The `imm64` constants created needed to be masked off to the

Fix a verifier error generated during optimizations (#11562)

This commit fixes an accidental regression from #11526 detected on
OSS-Fuzz. The `imm64` constants created needed to be masked off to the
type width to avoid having the upper bits set.

show more ...

[Cranelift] `(C ? X : Y) + Z --> (C ? X + Z : Y + Z)` (#11526)

* [ISLE] add an opt and its test

* [ISLE] add runtests for new opt

Cranelift: Generate integer numeric ops and conversions for ISLE in the meta crate (#11065)

* Cranelift: Generate integer numeric ops and conversions for ISLE in the meta crate

This automatically g

Cranelift: Generate integer numeric ops and conversions for ISLE in the meta crate (#11065)

* Cranelift: Generate integer numeric ops and conversions for ISLE in the meta crate

This automatically generates operations and conversions for integer types for
use in ISLE.

Supported types are: `{i,u}{8,16,32,64,128}`

We generate

* Comparisons (eq, ne, lt, lt_eq, gt, gt_eq)
* Arithmetic operations (add, sub, mul, div, neg)
* These each have checked, wrapping, and unwrapping variants
* Bitwise operations (and, or, xor, shifts, counting leading/trailing zeros/ones)
* A variety of predicates (is_zero, is_power_of_two, is_odd, etc...)
* These generate both partial constructors and a handful of extractors
* Conversions
* These come in a variety of flavors: fallible, infallible, truncating,
unwrapping, sign-reinterpretation
* Fallible conversions are also available as an extractor

* Fix copy paste

* Rename `x_reinterpret_as_y` to `x_cast_[un]signed`

* Collapse some fallible conversions in pulley lowering

* Clean up pulley iconst lowering, make sure narrowest `xconst*` instruction is always used

* Avoid an unnecessary truncation in riscv64 lowering

* Use extractor instead of partial constructor in x64 `imm` rule

* Clean up `op mem, imm` x64 lowering rules

* Use `(i64_eq a b)` instead of `(u64_eq (i64_cast_unsigned a) (i64_cast_unsigned b))`

* Rename `<ty>_unwrapping_<op>` to `<ty>_<op>`

show more ...

Cranelift: `((x > 0) ? x : -x)` => `(iabs x)` (#10850)

* add rules

* add tests

* fix rules

Cranelift: egraphs: fix a few sources of exponential rewrite blowup. (#10579)

This arrived as a fuzzbug [1] with some very interesting optimization
behavior. The test case has sequences of `(select

Cranelift: egraphs: fix a few sources of exponential rewrite blowup. (#10579)

This arrived as a fuzzbug [1] with some very interesting optimization
behavior. The test case has sequences of `(select _ x x)` operators --
that is, conditional selects with both inputs the same -- that are
chained together sequentially. A few aspects of the egraph framework and
our optimization rules conspired to create exponential blowup:

- We have a rewrite rule for `(select _ x x) -> x`, but we do not
subsume; this means that we create an eclass for both. This in itself
is not a problem; however...

- We have some *other* rules that look through the inputs to the select
to detect other cases (e.g.: select between constants 1 and 0, or 0
and 0, or ...), so we traverse both inputs;

- And we also do nested rewrites, so when the rewrite rule for `(select
_ x x) -> x` fires, and the `x` is itself another select in a long
chain of selects, we traverse all possible paths (through first
or second args) to the roots. In effect we get an eclass that has the
ultimate root and then 2^n combinations of `select` nodes on top of
that.

This got worse with the recent change to canonicalize less (for
simpler/cheaper compilation), hence the fuzzbug timeouts.

This PR includes a few fixes, all complementary to each other:

- The `(select _ x x) -> x` rule now subsumes; this is another case
where we have a strictly better rewrite and so we should short-circuit
the eclass blowup.

- The rewrite runner sorts and dedups returned value numbers; in
debugging the above I noticed we were getting two rules producing the
same rewritten value and we were adding the same value twice with two
union nodes.

- The rewriter keeps a total eclass size per root and limits the total
eclass size to a fixed limit (currently 5). We thus now have limits in
three different axes: depth of eager rewrites (5); number of returned
matches (also 5); and total size of eclass (5). The first two don't
necessarily imply the third because we otherwise can keep unioning on
top of an eclass and (as seen above) see exponential blowup.

[1]: https://oss-fuzz.com/testcase-detail/4806924172591104

show more ...

Add ISLE rules to generate 128-bit comparisons (#9176)

This commits adds pattern-matches to detect 128-bit comparisons encoded
in 64-bit comparisons and promote them to 128-bit to enable backends to

Add ISLE rules to generate 128-bit comparisons (#9176)

This commits adds pattern-matches to detect 128-bit comparisons encoded
in 64-bit comparisons and promote them to 128-bit to enable backends to
apply architecture-specific optimizations to these operations.

show more ...

Add `sextend_maybe` and `uextend_maybe` to opt ISLE (#7710)

* Add a test demonstrating a missed optimization

* Add `[su]extend_maybe` to opt ISLE

More spaceship patterns (#7702)

Cranelift: Add iconst shorthand to simplify ISLE opts (#7670)

* Demote `simm32` and `uimm8` to lowering ISLE only

There seems to be nothing in opt ISLE that actually wanted them, just something tha

Cranelift: Add iconst shorthand to simplify ISLE opts (#7670)

* Demote `simm32` and `uimm8` to lowering ISLE only

There seems to be nothing in opt ISLE that actually wanted them, just something that's more consistently done with using a 64-bit type to read from an Imm64.

And `simm32` feels like it's probably wrong to me -- `simm32` can't actually match `-1_i32` -- but I'm not confident enough in my analysis to actually change it.

* Cranelift: Add iconst shorthand to simplify ISLE opts

* Do a manually un-currying to avoid duplicating loading the `InstructionData`

* rustfmt is my nemesis

show more ...

Cranelift: additional `icmp` & `select` ISLE opts (#7615)

* Cranelift: additional `icmp` & `select` ISLE opts

* Don't include an invalid i8-to-i8 extend in the egraph

Tests covering both widths he

Cranelift: additional `icmp` & `select` ISLE opts (#7615)

* Cranelift: additional `icmp` & `select` ISLE opts

* Don't include an invalid i8-to-i8 extend in the egraph

Tests covering both widths here (added in previous commit) still pass.

show more ...

egraphs: Recognize `bitselect` from bitwise operations (#6879)

* egraphs: Transform bitops into a `bitselect`

* cranelift: Add bitwise bitselect tests

cranelift: Remove `f{min,max}_pseudo` instructions (#6874)

This commit removes these two instructions and replaces them instead
with their equivalents using `fcmp` plus `select` or `bitselect`
depen

cranelift: Remove `f{min,max}_pseudo` instructions (#6874)

This commit removes these two instructions and replaces them instead
with their equivalents using `fcmp` plus `select` or `bitselect`
depending on the type (`bitselect` for vectors, `select` for scalars).
The motivation for this commit is that incorrect optimizations for these
instructions were removed in #6859 and likely stemmed from the
surprising definitions of these instructions. These originally were
intended to correspond to operations in the SIMD proposal for
WebAssembly but nowadays the functionality of these instructions is
replaced with:

* Lowering from wasm to clif uses the `fcmp` plus `select` combo instruction.
* Backends that support optimizing this pattern use ISLE patterns to
match the instruction and emit the specialization for the pseudo
semantics.

This means that while the instructions are removed here it should be the
case that no functionality is lost and the output of Wasmtime/Cranelift
should still be the same as it was before. Existing tests using the
pseudo instructions were preserved except the riscv64 ones (where the
lowering was deleted) and the dynamic AArch64 ones. Both s390x and x64
continue to have specialized patterns for this compare-plus-select.

show more ...

egraphs: Delete `select+fcmp` to `f{min,max}_pseudo` transform (#6859)

This transform is wrong for the inputs in the attached testcase.

It was introduced in #5546 and has been sort of unnoticed unt

egraphs: Delete `select+fcmp` to `f{min,max}_pseudo` transform (#6859)

This transform is wrong for the inputs in the attached testcase.

It was introduced in #5546 and has been sort of unnoticed until #6843 caused
some wasmtime testcode to fire this optimization rule and produce this
counterexample.

show more ...

Add `multi_lane` precondition to `bitselect` => `{u,s}{min,max}` rewrite (#6201)

ISLE: simplify select/bitselect when both choices are the same (#6141)

ISLE: split algebraic.isle into several files (#6140)

* ISLE: split algebraic.isle into several files

* delete `algebraic.clif`

* Add `README.md`

* Remove old `algebraic.clif` tests

---------

C

ISLE: split algebraic.isle into several files (#6140)

* ISLE: split algebraic.isle into several files

* delete `algebraic.clif`

* Add `README.md`

* Remove old `algebraic.clif` tests

---------

Co-authored-by: Jamey Sharp <[email protected]>

show more ...