Partial support for no_std in cranelift_codegen (#12222)

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now

Partial support for no_std in cranelift_codegen (#12222)

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* some instances shouldn't have been renamed, fixes cargo test

* add cranelift-assembler-x64 (no_std) to CI

* fix codegen_meta, missed one spot with std::slice

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* remove unused import

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* some instances shouldn't have been renamed, fixes cargo test

* add cranelift-assembler-x64 (no_std) to CI

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* remove unused import

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* add cranelift-assembler-x64 (no_std) to CI

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* revert Cargo.toml formating

* remove prelude and fix cargo.toml

* cargo fmt

* remove empty lines

* bad renames

* macro_use only on no_std

* revert OnceLock change

* only use stable libm features

* update regalloc2

* update comment

* use continue instead

* Update vets

---------

Co-authored-by: Alex Crichton <[email protected]>

show more ...

refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)

* refactor(cranelift): merge DominatorTreePreorder into DominatorTree

Integrate preorder functionality directly into Dom

refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)

* refactor(cranelift): merge DominatorTreePreorder into DominatorTree

Integrate preorder functionality directly into DominatorTree to
eliminate duplicate computation and improve performance.

This eliminates the need for a separate DominatorTreePreorder data
structure, reducing memory usage and providing O(1) block dominance
checks by default. Block dominance checks throughout the compiler now
benefit from constant-time performance instead of O(depth) tree
traversal.

* refactor(cranelift): implement the new unified DominatorTree

Remove separate DominatorTreePreorder computation and use unified API:

- Context: Remove domtree_preorder field, simplify compute_domtree()
- AliasAnalysis: Switch from DominatorTreePreorder to DominatorTree
- Update dominance checks to use general dominates() method

All dominance checks in alias analysis now automatically benefit from
O(1) block dominance performance when instructions are in different
blocks.

* refactor(cranelift): update optimization passes for DominatorTree

* refactor(cranelift): update verifier and tests for new DominatorTree

SSA dominance validation in the verifier now benefits from O(1)
block-to-block dominance checks, improving compilation performance
during debug builds with verification enabled.

show more ...

feat(cranelift): Use DominatorTreePreorder in more places (#11098)

Enable the `useless_conversion` Clippy lint (#10838)

* Enable the `useless_conversion` Clippy lint

We've got lots of types in Wasmtime and convert between them quite a
lot, but often over time conv

Enable the `useless_conversion` Clippy lint (#10838)

* Enable the `useless_conversion` Clippy lint

We've got lots of types in Wasmtime and convert between them quite a
lot, but often over time conversions become unnecessary through
refactorings or similar. This will hopefully enable us to clean up some
conversions as they come up to try to have as few as possible ideally.

* Review comments

show more ...

Update Wasmtime to the 2024 Rust Edition (#10806)

* Update Wasmtime to the 2024 Rust Edition

Now that our MSRV supports the 2024 edition it's possible to make this
switch. This commit moves Wasmtim

Update Wasmtime to the 2024 Rust Edition (#10806)

* Update Wasmtime to the 2024 Rust Edition

Now that our MSRV supports the 2024 edition it's possible to make this
switch. This commit moves Wasmtime to the 2024 Edition to keep
up-to-date with Rust idioms and access many of the edition features
exclusive to the 2024 edition.

prtest:full

* Reformat with the 2024 edition

show more ...

Enforce `clippy::clone_on_copy` for the workspace (#9025)

* Derive `Copy` for `Val`

* Fix `clippy::clone_on_copy` for the whole repo

* Enforce `clippy::clone_on_copy` for the workspace

* fix some

Enforce `clippy::clone_on_copy` for the workspace (#9025)

* Derive `Copy` for `Val`

* Fix `clippy::clone_on_copy` for the whole repo

* Enforce `clippy::clone_on_copy` for the workspace

* fix some more clippy::clone_on_copy that got missed

show more ...

Fxhash to rustchash (#8498)

* move fx hash to workspace level dep

* change internal fxhash to use fxhash crate

* remove unneeded HashSet import

* change fxhash crate to rustc hash

* undo migrat

Fxhash to rustchash (#8498)

* move fx hash to workspace level dep

* change internal fxhash to use fxhash crate

* remove unneeded HashSet import

* change fxhash crate to rustc hash

* undo migration to rustc hash

* manually implement hash function from fxhash

* change to rustc hash

show more ...

cranelift: Minimize ways to manipulate instruction results (#8293)

* cranelift: Minimize ways to manipulate instruction results

In particular, remove support for detaching/attaching/appending
instr

cranelift: Minimize ways to manipulate instruction results (#8293)

* cranelift: Minimize ways to manipulate instruction results

In particular, remove support for detaching/attaching/appending
instruction results.

The AliasAnalysis pass used detach_results, but leaked the detached
ValueList; using clear_results instead is better.

The verifier's `test_printing_contextual_errors` needed to get the
verifier to produce an error containing a pretty-printed instruction,
and did so by appending too many results. Instead, failing to append any
results gets a similar error out of the verifier, without requiring that
we expose the easy-to-misuse append_result method. However, `iconst` is
not a suitable instruction for this version of the test because its
result type is its controlling type, so failing to create any results
caused assertion failures rather than the desired verifier error. I
switched to `f64const` which has a non-polymorphic type.

The DFG's `aliases` test cleared both results of an instruction and then
reattached one of them. Since we have access to DFG internals in these
tests, it's easier to directly manipulate the relevant ValueList than to
use these unsafe methods.

The only other use of attach/append was in `make_inst_results_reusing`
which decided which to use based on whether a particular result was
supposed to reuse an existing value. Inlining both methods there
revealed that they were nearly identical and could have most of their
code factored out.

While I was looking at uses of `DataFlowGraph::results`, I also
simplified replace_with_aliases a little bit.

* Review comments

show more ...

Refactor the `MemFlags` internal representation (#8162)

* Refactor the `MemFlags` internal representation

This commit refactors the internal `MemFlags` bits to be not just flags.
Instead some bits

Refactor the `MemFlags` internal representation (#8162)

* Refactor the `MemFlags` internal representation

This commit refactors the internal `MemFlags` bits to be not just flags.
Instead some bits are now grouped together and interpreted as a unit.
This enables two primary API changes:

* First the `heap`/`table`/`vmctx` split is now represented as an "alias
region" which is set as an enum. This means that all `MemFlags` carry
an `Option<AliasRegion>` internally.

* Second trapping state is now represented as an `Option<TrapCode>`.
This means that `notrap` is no longer a flag and `tabletrap` is no
longer a flag. This does enable storing arbitrary trap codes though so
long as they aren't `TrapCode::User(_)`.

The main purpose of this commit is to enable using more trap codes with
`MemFlags` for when a segfault is detected. For example with #5291 we
want a segfault to indicate a call-to-null, which is not currently
covered by `MemFlags`.

* Remove individual alias region setters/getters from `MemFlags`

Instead use the `AliasRegion` enum instead to help emphasize that only
one region is possible on a `MemFlags`, not multiple.

* Update cranelift/codegen/src/ir/memflags.rs

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

---------

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

show more ...

Make DataFlowGraph::insts public, but restricted (#5450)

We have some operations defined on DataFlowGraph purely to work around borrow-checker issues with InstructionData and other data on DataFlowG

Make DataFlowGraph::insts public, but restricted (#5450)

We have some operations defined on DataFlowGraph purely to work around borrow-checker issues with InstructionData and other data on DataFlowGraph. Part of the problem is that indexing the DFG directly hides the fact that we're only indexing the insts field of the DFG.

This PR makes the insts field of the DFG public, but wraps it in a newtype that only allows indexing. This means that the borrow checker is better able to tell when operations on memory held by the DFG won't conflict, which comes up frequently when mutating ValueLists held by InstructionData.

show more ...

Alias analysis: refactor for use by other driver loops. (#5380)

* Alias analysis: refactor for use by other driver loops.

This PR pulls the core of the alias analysis infrastructure into a
`proc

Alias analysis: refactor for use by other driver loops. (#5380)

* Alias analysis: refactor for use by other driver loops.

This PR pulls the core of the alias analysis infrastructure into a
`process_inst()` method that operates on a single instruction, and
allows another compiler pass to apply store-to-load forwarding and
redundant-load elimination interleaved with other work. The existing
behavior remains unchanged; the pass's toplevel loop calls this
extracted method.

This refactor is a prerequisite for using the alias analysis as part of
a refactored egraph-based optimization framework.

* Review feedback: remove unneeded mut.

show more ...

Initial forward-edge CFI implementation (#3693)

* Initial forward-edge CFI implementation

Give the user the option to start all basic blocks that are targets
of indirect branches with the BTI in

Initial forward-edge CFI implementation (#3693)

* Initial forward-edge CFI implementation

Give the user the option to start all basic blocks that are targets
of indirect branches with the BTI instruction introduced by the
Branch Target Identification extension to the Arm instruction set
architecture.

Copyright (c) 2022, Arm Limited.

* Refactor `from_artifacts` to avoid second `make_executable` (#1)

This involves "parsing" twice but this is parsing just the header of an
ELF file so it's not a very intensive operation and should be ok to do
twice.

* Address the code review feedback

Copyright (c) 2022, Arm Limited.

Co-authored-by: Alex Crichton <[email protected]>

show more ...

cranelift: Introduce a feature to enable `trace` logs (#4484)

* Don't use `log::trace` directly but a feature-enabled `trace` macro
* Don't emit disassembly based on the log level

Add a basic alias analysis with redundant-load elim and store-to-load fowarding opts. (#4163)

This PR adds a basic *alias analysis*, and optimizations that use it.
This is a "mid-end optimization":

Add a basic alias analysis with redundant-load elim and store-to-load fowarding opts. (#4163)

This PR adds a basic *alias analysis*, and optimizations that use it.
This is a "mid-end optimization": it operates on CLIF, the
machine-independent IR, before lowering occurs.

The alias analysis (or maybe more properly, a sort of memory-value
analysis) determines when it can prove a particular memory
location is equal to a given SSA value, and when it can, it replaces any
loads of that location.

This subsumes two common optimizations:

* Redundant load elimination: when the same memory address is loaded two
times, and it can be proven that no intervening operations will write
to that memory, then the second load is *redundant* and its result
must be the same as the first. We can use the first load's result and
remove the second load.

* Store-to-load forwarding: when a load can be proven to access exactly
the memory written by a preceding store, we can replace the load's
result with the store's data operand, and remove the load.

Both of these optimizations rely on a "last store" analysis that is a
sort of coloring mechanism, split across disjoint categories of abstract
state. The basic idea is that every memory-accessing operation is put
into one of N disjoint categories; it is disallowed for memory to ever
be accessed by an op in one category and later accessed by an op in
another category. (The frontend must ensure this.)

Then, given this, we scan the code and determine, for each
memory-accessing op, when a single prior instruction is a store to the
same category. This "colors" the instruction: it is, in a sense, a
static name for that version of memory.

This analysis provides an important invariant: if two operations access
memory with the same last-store, then *no other store can alias* in the
time between that last store and these operations. This must-not-alias
property, together with a check that the accessed address is *exactly
the same* (same SSA value and offset), and other attributes of the
access (type, extension mode) are the same, let us prove that the
results are the same.

Given last-store info, we scan the instructions and build a table from
"memory location" key (last store, address, offset, type, extension) to
known SSA value stored in that location. A store inserts a new mapping.
A load may also insert a new mapping, if we didn't already have one.
Then when a load occurs and an entry already exists for its "location",
we can reuse the value. This will be either RLE or St-to-Ld depending on
where the value came from.

Note that this *does* work across basic blocks: the last-store analysis
is a full iterative dataflow pass, and we are careful to check dominance
of a previously-defined value before aliasing to it at a potentially
redundant load. So we will do the right thing if we only have a
"partially redundant" load (loaded already but only in one predecessor
block), but we will also correctly reuse a value if there is a store or
load above a loop and a redundant load of that value within the loop, as
long as no potentially-aliasing stores happen within the loop.

show more ...