Cranelift: Split out computation of where to move a cursor from actually updating its position (#11464)

This allows users to query what the next/prev position in their traversal would
be without act

Cranelift: Split out computation of where to move a cursor from actually updating its position (#11464)

This allows users to query what the next/prev position in their traversal would
be without actually changing the cursor's current location. Otherwise, they
would have to do something like

```rust
cursor.next_block();
let next_pos = cursor.current_position();
cursor.prev_block();
```

These new methods aren't used anywhere yet, other than the implementation of the
cursor-position-updating methods they were split out from, but it seems useful
to expose. I almost needed it for some inlining stuff, but ultimately took a
slightly different approach.

show more ...

Cranelift: simplify some side-effectful instructions in ISLE (#10524)

* Cranelift: simplify some side-effectful instructions in ISLE

This commit adds a new top-level ISLE entrypoint specifically fo

Cranelift: simplify some side-effectful instructions in ISLE (#10524)

* Cranelift: simplify some side-effectful instructions in ISLE

This commit adds a new top-level ISLE entrypoint specifically for instructions
in the side-effectful skeleton: `simplify_skeleton`. While these rewrites are
processed during the egraph pass, values from skeleton instructions still do not
get inserted into the egraph. Indeed, `simplify_skeleton` operates
on *instructions* rather than *values* because we do not represent side effects
as values; values do not have side effects in CLIF, instructions do. Therefore,
rather than doing a whole dynamic-programming style extraction of the best
candidate simplification like we do with the egraph, we take an eager and greedy
approach.

Furthermore, `simplify_skeleton` is limited only to skeleton instructions that
do not involve control-flow or terminators right now. This is because changing
the control-flow graph can change whether a use is dominated by a def or not,
and we do not currently have the machinery to track and fix up invalidated
uses. Addressing this is left for future commits.

* fix `MIN / -1` cprop and add negative tests for things simplify_skeleton cannot handle yet

show more ...

Wasmtime: Add support for Wasm tail calls (#6774)

* Wasmtime: Add support for Wasm tail calls

This adds the `Config::wasm_tail_call` method and `--wasm-features tail-call`
CLI flag to enable the Wa

Wasmtime: Add support for Wasm tail calls (#6774)

* Wasmtime: Add support for Wasm tail calls

This adds the `Config::wasm_tail_call` method and `--wasm-features tail-call`
CLI flag to enable the Wasm tail calls proposal in Wasmtime.

This PR is mostly just plumbing and enabling tests, since all the prerequisite
work (Wasmtime trampoline overhauls and Cranelift tail calls) was completed in
earlier pull requests.

When Wasm tail calls are enabled, Wasm code uses the `tail` calling
convention. The `tail` calling convention is known to cause a 1-7% slow down for
regular code that isn't using tail calls, which is why it isn't used
unconditionally. This involved shepherding `Tunables` through to Wasm signature
construction methods. The eventual plan is for the `tail` calling convention to
be used unconditionally, but not until the performance regression is
addressed. This work is tracked in
https://github.com/bytecodealliance/wasmtime/issues/6759

Additionally while our x86-64, aarch64, and riscv64 backends support tail calls,
the s390x backend does not support them yet. Attempts to use tail calls on s390x
will return errors. Support for s390x is tracked in
https://github.com/bytecodealliance/wasmtime/issues/6530

* Store `Tunables` inside the `Compiler`

Instead of passing as an argument to every `Compiler` method.

* Cranelift: Support "direct" return calls on riscv64

They still use `jalr` instead of `jal` but this allows us to use the `RiscvCall`
reloc, which Wasmtime handles. Before we were using `LoadExternalName` which
produces an `Abs8` reloc, which Wasmtime intentionally does not handle since
that involves patching code at runtime, which makes loading code slower.

* Fix tests that assume tail call support on s390x

show more ...

Removes debug assertion that was related to issue 796 (#6175)

* fix typo: behaviour -> behavior

* remove debug assertion since 796 has been merged

* Update data_value.rs

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

Implement an incremental compilation cache for Cranelift (#4551)

This is the implementation of https://github.com/bytecodealliance/wasmtime/issues/4155, using the "inverted API" approach suggested b

Implement an incremental compilation cache for Cranelift (#4551)

This is the implementation of https://github.com/bytecodealliance/wasmtime/issues/4155, using the "inverted API" approach suggested by @cfallin (thanks!) in Cranelift, and trait object to provide a backend for an all-included experience in Wasmtime.

After the suggestion of Chris, `Function` has been split into mostly two parts:

- on the one hand, `FunctionStencil` contains all the fields required during compilation, and that act as a compilation cache key: if two function stencils are the same, then the result of their compilation (`CompiledCodeBase<Stencil>`) will be the same. This makes caching trivial, as the only thing to cache is the `FunctionStencil`.
- on the other hand, `FunctionParameters` contain the... function parameters that are required to finalize the result of compilation into a `CompiledCode` (aka `CompiledCodeBase<Final>`) with proper final relocations etc., by applying fixups and so on.

Most changes are here to accomodate those requirements, in particular that `FunctionStencil` should be `Hash`able to be used as a key in the cache:

- most source locations are now relative to a base source location in the function, and as such they're encoded as `RelSourceLoc` in the `FunctionStencil`. This required changes so that there's no need to explicitly mark a `SourceLoc` as the base source location, it's automatically detected instead the first time a non-default `SourceLoc` is set.
- user-defined external names in the `FunctionStencil` (aka before this patch `ExternalName::User { namespace, index }`) are now references into an external table of `UserExternalNameRef -> UserExternalName`, present in the `FunctionParameters`, and must be explicitly declared using `Function::declare_imported_user_function`.
- some refactorings have been made for function names:
- `ExternalName` was used as the type for a `Function`'s name; while it thus allowed `ExternalName::Libcall` in this place, this would have been quite confusing to use it there. Instead, a new enum `UserFuncName` is introduced for this name, that's either a user-defined function name (the above `UserExternalName`) or a test case name.
- The future of `ExternalName` is likely to become a full reference into the `FunctionParameters`'s mapping, instead of being "either a handle for user-defined external names, or the thing itself for other variants". I'm running out of time to do this, and this is not trivial as it implies touching ISLE which I'm less familiar with.

The cache computes a sha256 hash of the `FunctionStencil`, and uses this as the cache key. No equality check (using `PartialEq`) is performed in addition to the hash being the same, as we hope that this is sufficient data to avoid collisions.

A basic fuzz target has been introduced that tries to do the bare minimum:

- check that a function successfully compiled and cached will be also successfully reloaded from the cache, and returns the exact same function.
- check that a trivial modification in the external mapping of `UserExternalNameRef -> UserExternalName` hits the cache, and that other modifications don't hit the cache.
- This last check is less efficient and less likely to happen, so probably should be rethought a bit.

Thanks to both @alexcrichton and @cfallin for your very useful feedback on Zulip.

Some numbers show that for a large wasm module we're using internally, this is a 20% compile-time speedup, because so many `FunctionStencil`s are the same, even within a single module. For a group of modules that have a lot of code in common, we get hit rates up to 70% when they're used together. When a single function changes in a wasm module, every other function is reloaded; that's still slower than I expect (between 10% and 50% of the overall compile time), so there's likely room for improvement.

Fixes #4155.

show more ...

Cranelift: remove unused EncCursor

Remove more old backend ISA concepts (#3402)

This also paves the way for unifying TargetIsa and MachBackend, since now they map one to one. In theory the two traits could be merged, which would be n

Remove more old backend ISA concepts (#3402)

This also paves the way for unifying TargetIsa and MachBackend, since now they map one to one. In theory the two traits could be merged, which would be nice to limit the number of total concepts. Also they have quite different responsibilities, so it might be fine to keep them separate.

Interestingly, this PR started as removing RegInfo from the TargetIsa trait since the adapter returned a dummy value there. From the fallout, noticed that all Display implementations didn't needed an ISA anymore (since these were only used to render ISA specific registers). Also the whole family of RegInfo / ValueLoc / RegUnit was exclusively used for the old backend, and these could be removed. Notably, some IR instructions needed to be removed, because they were using RegUnit too: this was the oddball of regfill / regmove / regspill / copy_special, which were IR instructions inserted by the old regalloc. Fare thee well!

show more ...

Remove ancient register allocation (#3401)

Avoid touching encodings in `EncCursor` if using a MachInst backend.

`EncCursor` is a variant of `Cursor` that allows updating CLIF while
keeping its encodings up to date, given a particular ISA. Ho

Avoid touching encodings in `EncCursor` if using a MachInst backend.

`EncCursor` is a variant of `Cursor` that allows updating CLIF while
keeping its encodings up to date, given a particular ISA. However, new
(MachInst) backends don't use the encodings, and the `TargetIsaAdapter`
shim will panic if any encoding-related method is called. This PR avoids
those panics.

Fixes #1809.

show more ...

Rename 'an block' to 'a block'

Missed this in the automatic rename of 'Ebb' to 'Block'.

Mass rename Ebb and relatives to Block (#1365)

* Manually rename BasicBlock to BlockPredecessor

BasicBlock is a pair of (Ebb, Inst) that is used to represent the
basic block subcomponent of an E

Mass rename Ebb and relatives to Block (#1365)

* Manually rename BasicBlock to BlockPredecessor

BasicBlock is a pair of (Ebb, Inst) that is used to represent the
basic block subcomponent of an Ebb that is a predecessor to an Ebb.

Eventually we will be able to remove this struct, but for now it
makes sense to give it a non-conflicting name so that we can start
to transition Ebb to represent a basic block.

I have not updated any comments that refer to BasicBlock, as
eventually we will remove BlockPredecessor and replace with Block,
which is a basic block, so the comments will become correct.

* Manually rename SSABuilder block types to avoid conflict

SSABuilder has its own Block and BlockData types. These along with
associated identifier will cause conflicts in a later commit, so
they are renamed to be more verbose here.

* Automatically rename 'Ebb' to 'Block' in *.rs

* Automatically rename 'EBB' to 'block' in *.rs

* Automatically rename 'ebb' to 'block' in *.rs

* Automatically rename 'extended basic block' to 'basic block' in *.rs

* Automatically rename 'an basic block' to 'a basic block' in *.rs

* Manually update comment for `Block`

`Block`'s wikipedia article required an update.

* Automatically rename 'an `Block`' to 'a `Block`' in *.rs

* Automatically rename 'extended_basic_block' to 'basic_block' in *.rs

* Automatically rename 'ebb' to 'block' in *.clif

* Manually rename clif constant that contains 'ebb' as substring to avoid conflict

* Automatically rename filecheck uses of 'EBB' to 'BB'

'regex: EBB' -> 'regex: BB'
'$EBB' -> '$BB'

* Automatically rename 'EBB' 'Ebb' to 'block' in *.clif

* Automatically rename 'an block' to 'a block' in *.clif

* Fix broken testcase when function name length increases

Test function names are limited to 16 characters. This causes
the new longer name to be truncated and fail a filecheck test. An
outdated comment was also fixed.

show more ...

Drop 'basic-blocks' feature (#1363)

* All: Drop 'basic-blocks' feature

This makes it so that 'basic-blocks' cannot be disabled and we can
start assuming it everywhere.

* Tests: Replace non-bb

Drop 'basic-blocks' feature (#1363)

* All: Drop 'basic-blocks' feature

This makes it so that 'basic-blocks' cannot be disabled and we can
start assuming it everywhere.

* Tests: Replace non-bb filetests with bb version

* Tests: Adapt solver-fixedconflict filetests to use basic blocks

show more ...

Fix clippy warnings.

This commit fixes the current set of (stable) clippy warnings in the repo.

Assert if newly added instructions break the Basic Block invariant.

Add the dyn keyword before trait objects;

moved crates in lib/ to src/, renamed crates, modified some files' text (#660)

moved crates in lib/ to src/, renamed crates, modified some files' text (#660)