ISLE: Add proper bool type (#9593)

* ISLE: add proper booleans (expressions)

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: add proper booleans (pattern

ISLE: Add proper bool type (#9593)

* ISLE: add proper booleans (expressions)

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: add proper booleans (patterns)

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: add proper booleans (spec expressions)

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: replace opaque boolean constants

Copyright (c) 2024, Arm Limited.

Replace all occurences of `$true` and `$false` with `true` and `false`.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: remove `on_lhs` argument

Instead of threading `on_lhs` through all the calls to `translate_expr`,
we can just set `is_partial` and `is_pure` on `root_flags` to true.

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* ISLE: add proper booleans (language reference)

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

---------

Signed-off-by: Karl Meakin <[email protected]>

show more ...

Implement a few minor optimizations around 128-bit integers (#9136)

* Implement a few minor optimizations around 128-bit integers

This commit implements a few minor changes for `i128` in both the e

Implement a few minor optimizations around 128-bit integers (#9136)

* Implement a few minor optimizations around 128-bit integers

This commit implements a few minor changes for `i128` in both the egraph
optimizations and lowerings for x64. The optimization pass will now
transform `iconcat` into a `uextend` or `sextend` where appropriate.
The x64 backend then pattern-matches this to produce slightly more
optimal machine code. Additionally the x64 backend now handles
memory/immediate operands a bit better when the argument to a 128-bit
operation is an `iconcat`.

* Update test expectations

* Match iadd lowering rules for isub

show more ...

cranelift: Fix ireduce rules (#8005)

We had two optimization rules which started off like this:

(rule (simplify (ireduce smallty val@(binary_op _ op x y)))
(if-let _ (reducible_modular_op val

cranelift: Fix ireduce rules (#8005)

We had two optimization rules which started off like this:

(rule (simplify (ireduce smallty val@(binary_op _ op x y)))
(if-let _ (reducible_modular_op val))
...)

This was intended to check that `x` and `y` came from an instruction
which not only was a binary op but also matched `reducible_modular_op`.

Unfortunately, both `binary_op` and `reducible_modular_op` were
multi-terms.
- So `binary_op` would search the eclass rooted at `val` to find each
instruction that uses a binary operator.
- Then `reducible_modular_op` would search the entire eclass again to
find an instruction which matched its criteria.

Nothing ensured that both searches would find the same instruction.

The reason these rules were written this way was because they had
additional guards (`will_simplify_with_ireduce`) which made them fairly
complex, and it seemed desirable to not have to copy those guards for
every operator where we wanted to apply this optimization.

However, we've decided that checking whether the rule is actually an
improvement is not desirable. In general, that should be the job of the
cost function. Blindly adding equivalent expressions gives us more
opportunities for other rules to fire, and we have global recursion and
growth limits to keep the process from going too wild.

As a result, we can just delete those guards. That allows us to write
the rules in a more straightforward way.

Fixes #7999.

Co-authored-by: Trevor Elliott <[email protected]>
Co-authored-by: L Pereira <[email protected]>
Co-authored-by: Chris Fallin <[email protected]>

show more ...

Guard recursion in `will_simplify_with_ireduce` (#7882)

Add a test to expose issues with unbounded recursion through `iadd`
during egraph rewrites, and bound the recursion of
`will_simplify_with_ire

Guard recursion in `will_simplify_with_ireduce` (#7882)

Add a test to expose issues with unbounded recursion through `iadd`
during egraph rewrites, and bound the recursion of
`will_simplify_with_ireduce`.

Fixes #7874

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

show more ...

Add missing subsume uses in egraph rules (#7879)

* Fix a few egraph rules that needed `subsume`

There were a few rules that dropped value references from the LHS
without using subsume. I think they

Add missing subsume uses in egraph rules (#7879)

* Fix a few egraph rules that needed `subsume`

There were a few rules that dropped value references from the LHS
without using subsume. I think they were probably benign as they
produced constant results, but this change is in the spirit of our
revised guidelines for egraph rules.

* Augment egraph rule guideline 2 to talk about constants

show more ...

Optimize more reduction-of-an-extend cases (#7711)

* Optimize more reduction-of-an-extend cases

* Rebase atop 7719

Simplify ireduce of modular operators, when it lowers the total instructions (#7719)

Cranelift: use more `iconst_[su]` in opts, notably enabling some i128 patterns (#7693)

* Cranelift: use more `iconst_[su]` in opts, notably re-enabling some i128 cases

`iconst_u` and `iconst_s` sup

Cranelift: use more `iconst_[su]` in opts, notably enabling some i128 patterns (#7693)

* Cranelift: use more `iconst_[su]` in opts, notably re-enabling some i128 cases

`iconst_u` and `iconst_s` support `$I128`, so we can now enable these even though they had to be excluded before to avoid generating `iconst.i128` that doesn't exist.

* Update for PR feedback

show more ...

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 ...

Additional `extend` opt patterns (#7644)

Add opt patterns for 3-way comparison (`Ord::cmp` or `<=>`) (#7636)

* Add opt patterns for 3-way comparison (`Ord::cmp` or `<=>`)

Compare clang: <https://cpp.godbolt.org/z/bTbe1556W>

* Add `spaces

Add opt patterns for 3-way comparison (`Ord::cmp` or `<=>`) (#7636)

* Add opt patterns for 3-way comparison (`Ord::cmp` or `<=>`)

Compare clang: <https://cpp.godbolt.org/z/bTbe1556W>

* Add `spaceship_[su]` extractors and constructors

show more ...

egraphs: Disable bitwise `splat` transform for floats (#6916)

* egraphs: Move `{s,u}widen+splat` rules to vector.isle

* egraphs: Disable some `splat` rules for floats

egraphs: Transform `{u,s}widen_{low,high}+splat` into `splat+{u,s}extend` (#6533)

Optimize sign extension via shifts (#6220)

* Optimize sign extension via shifts

This commit adds egraph optimization patterns for left-shifting a value
and then right-shifting it as a form of sign

Optimize sign extension via shifts (#6220)

* Optimize sign extension via shifts

This commit adds egraph optimization patterns for left-shifting a value
and then right-shifting it as a form of sign extending its lower bits.
This matches the behavior of the WebAssembly `i32.extend8_s`
instruction, for example. Note that the lowering of that WebAssembly
instruction does not use shifts, but historical versions of LLVM that
didn't support the instruction, or versions with the instruction
disabled, will use shifts instead.

A second rule for reduction-of-extend being the same as the original
value was added to keep an existing shift-related test passing as well.

* Add reference assemblies for new opts

show more ...

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 ...