PCC: remove proof-carrying code (for now?). (#12800)

In late 2023, we built out an experimental feature called
Proof-Carrying Code (PCC), where we attached "facts" to values in the
CLIF IR and built

PCC: remove proof-carrying code (for now?). (#12800)

In late 2023, we built out an experimental feature called
Proof-Carrying Code (PCC), where we attached "facts" to values in the
CLIF IR and built verification of these facts after lowering to
machine instructions. We also added "memory types" describing layout
of memory and a "checked" flag on memory operations such that we could
verify that any checked memory operation accessed valid memory (as
defined by memory types attached to pointer values via
facts). Wasmtime's Cranelift backend then put appropriate memory types
and facts in its IR such that all accesses to memory (aspirationally)
could be checked, taking the whole mid-end and lowering backend of
Cranelift out of the trusted core that enforces SFI.

This basically worked, at the time, for static memories; but never for
dynamic memories, and then work on the feature lost
prioritization (aka I had to work on other things) and I wasn't able
to complete it and put it in fuzzing/enable it as a production option.

Unfortunately since then it has bit-rotted significantly -- as we add
new backend optimizations and instruction lowerings we haven't kept
the PCC framework up to date.

Inspired by the discussion in #12497 I think it's time to delete
it (hopefully just "for now"?) unless/until we can build it again. And
when we do that, we should probably get it to the point of validating
robust operation on all combinations of memory configurations before
merging. (That implies a big experiment branch rather than a bunch of
eager PRs in-tree, but so it goes.) I still believe it is possible to
build this (and I have ideas on how to do it!) but not right now.

show more ...

Cranelift: preserve_all: disallow return values. (#12447)

In #12399 a fuzzbug uncovered an issue whereby a function with
`preserve_all` and with many return values cannot be called, because
`emit_re

Cranelift: preserve_all: disallow return values. (#12447)

In #12399 a fuzzbug uncovered an issue whereby a function with
`preserve_all` and with many return values cannot be called, because
`emit_retval_loads` cannot codegen memory-to-memory moves (from on-stack
return value slots directly to spillslots) without a
temporary/clobberable register, and `preserve_all` implies no such
registers exist.

I thought about trying to support this by shuffling registers -- such a
case implies many return values, and at least some of them will be in
registers, so we might be able to temporarily spill one of those and use
it as a scratch to move other values memory-to-memory. But the
complexity doesn't seem worthwhile, and this path is not actually needed
at the moment.

Thinking more broadly, anyone using `preserve_all` for hooks meant to
minimally perturb register state will likely not want to use many return
values anyway (that defeats the point). We could allow *one* return
value, with the knowledge that this always fits in a register in our
existing ABIs, but that also feels somewhat arbitrary, and I could make
the argument that "preserve all" should really mean preserve *all*.
Someone wanting to return a value anyway from such a hook could use
indirect means (pass in a pointer to a stackslot, for example). I'm
happy to tweak this limit if others have more thoughts, however.

Fixes #12399.

show more ...

cranelift-codegen: rename most uses of std to core and alloc (#12237)

* rename most std uses to core and alloc

* cargo fmt

Cranelift: make all non-tail, non-indirect calls patchable, and rename patchable ABI to `preserve_all`. (#12160)

* Cranelift: make all non-tail, non-indirect calls patchable, and rename patchable AB

Cranelift: make all non-tail, non-indirect calls patchable, and rename patchable ABI to `preserve_all`. (#12160)

* Cranelift: make all non-tail, non-indirect calls patchable, and rename patchable ABI to `preserve_all`.

As discussed in this week's Cranelift meeting, we've discovered a need
to generalize the `patchable_call` mechanism and corresponding
`patchable` ABI slightly. In particular, we will need patchable
`try_call` callsites as well in order to allow breakpoint handlers to
throw exceptions (desirable functionality eventually) and have this work
in the presence of inlining. Also, it's just a nice generalization to
say that patchability is an orthogonal dimension to the call ABI and the
other restrictions we initially imposed, and works as long as the basic
requirement (no return values) is met.

This also renames the `patchable` ABI to `preserve_all`, to make it
clear that its purpose is actually orthogonal, and it can be used
independently of patchable callsites. It also deletes the `cold` ABI,
which never actually did anything and is misleading in the presence of
an actual cold-ish (subzero temperature, actually) ABI like
`preserve_all`.

* Review feedback.

show more ...

Cranelift: add patchable call instructions. (#12101)

* Cranelift: add patchable call instructions.

The new `patchable_call` CLIF instruction pairs with the `patchable`
ABI, and emits a callsite wit

Cranelift: add patchable call instructions. (#12101)

* Cranelift: add patchable call instructions.

The new `patchable_call` CLIF instruction pairs with the `patchable`
ABI, and emits a callsite with one new key property: the MachBuffer
carries metadata that describes exactly which byte range to "NOP out"
(overwrite with NOP instructions) to disable that callsite. Doing so is
semantically valid and explicitly supported.

This enables patching of code at runtime to dynamically turn on and off
features such as instrumentation or debugging hooks. We plan to use this
to implement breakpoints in Wasmtime's guest debugging support.

As part of this change, I added a notion of "unit of NOP bytes" to the
MachBuffer so that the consumer (e.g., Wasmtime's Cranelift-based code
compilation pipeline and metadata-producing logic) can handle patchable
callsites without any other special knowledge of the ISA.

For the "real metal" ISAs there are perfectly well-defined NOPs to use,
but for Pulley, where all opcodes are assigned at compile time by macro
magic, I explicitly defined NOP as opcode byte 0 by moving `Nop`'s
definition to the top of the list and adding a unit test asserting its
encoding.

A design note: in principle it would be possible, as an alternative, to
treat "patchability" as an orthogonal dimension of all callsites, and
emit the metadata describing the instruction-offset range for any
callsite with the flag set. The only truly necessary semantic
restriction is that there are no return values (because if we turn the
callsite off, nothing writes to them); we could support patchability for
other ABIs and for the other kinds of call instructions. The `patchable`
ABI would then be better described as something like the "no clobbers
ABI". I opted not to generalize in this way because it creates some
less-tested corners and the generalized form, at least at the MachInst
level, is not really much simpler in the end.

A testing note: I opted not to implement actual code patching in the
`cranelift-tools` filetest runner and test patching callsites in/out via
some actuation (e.g. a magic hostcall, like we do for throws) because
(i) that's a lot of new plumbing and (ii) we are going to test this very
shortly in Wasmtime anyway and (iii) the correctness (or not) of the
location-and-length metadata is easy enough to verify in the
disassemblies in the compile-tests.

* Review feedback: remove dependence on (and test for) NOP being the literal byte 0.

show more ...

Cranelift: add a "patchable call" ABI. (#12061)

This ABI is intended for use in scenarios where we want a very
lightweight callsite that can be turned on and off by patching in one
instruction. (The

Cranelift: add a "patchable call" ABI. (#12061)

This ABI is intended for use in scenarios where we want a very
lightweight callsite that can be turned on and off by patching in one
instruction. (The actual patchable call instruction is not in this PR;
that will be a separate PR.)

The idea is that we define a call to clobber *no* registers -- not
even the arguments! And we restrict signatures such that on all of our
supported architectures, all arguments go into registers only. Those
two requirements together mean that all callsites for this ABI should
have only a raw call instruction, with no loads/stores to stackslots;
and have the minimum possible impact on regalloc, by only imposing
constraints on args to ensure they are in certain registers but not
altering those registers.

Given this, we could implement, e.g., breakpoints with patchable
callsites (off by default) at every sequence point in compiled
code. In a typical use-case with Wasmtime-compiled Wasm, that would
put a bunch of uses of vmctx constrained to the first argument
register in every code path, but vmctx likely already sits there most
of the time anyway (for any call to other Wasm functions or for
libcalls). Thus, the impact is just the one instruction and nothing
else.

This PR adds the calling convention itself and tests that show
that *two* consecutive callsites can be compiled with no register
setup re-occurring from one call to the next (thus demonstrating no
clobbers).

show more ...

Cranelift: add debug tag infrastructure. (#11768)

* Cranelift: add debug tag infrastructure.

This PR adds *debug tags*, a kind of metadata that can attach to CLIF
instructions and be lowered to VCo

Cranelift: add debug tag infrastructure. (#11768)

* Cranelift: add debug tag infrastructure.

This PR adds *debug tags*, a kind of metadata that can attach to CLIF
instructions and be lowered to VCode instructions and as metadata on
the produced compiled code. It also adds opaque descriptor blobs
carried with stackslots. Together, these two features allow decorating
IR with first-class debug instrumentation that is properly preserved
by the compiler, including across optimizations and
inlining. (Wasmtime's use of these features will come in followup
PRs.)

The key idea of a "debug tag" is to allow the Cranelift embedder to
express whatever information it needs to, in a format that is opaque
to Cranelift itself, except for the parts that need translation during
lowering. In particular, the `DebugTag::StackSlot` variant gets
translated to a physical offset into the stackframe in the compiled
metadata output. So, for example, the embedder can emit a tag
referring to a stackslot, and another describing an offset in that
stackslot.

The debug tags exist as a *sequence* on any given instruction; the
meaning of the sequence is known only to the embedder, *except* that
during inlining, the tags for the inlining call instruction are
prepended to the tags of inlined instructions. In this way, a
canonical use-case of tags as describing original source-language
frames can preserve the source-language view even when multiple
functions are inlined into one.

The descriptor on a stackslot may look a little odd at first, but its
purpose is to allow serializing some description of
stackslot-contained runtime user-program data, in a way that is firmly
attached to the stackslot. In particular, in the face of inlining,
this descriptor is copied into the inlining (parent) function from the
inlined function when the stackslot entity is copied; no other
metadata outside Cranelift needs to track the identity of stackslots
and know about that motion. This fits nicely with the ability of tags
to refer to stackslots; together, the embedder can annotate
instructions as having certain state in stackslots, and describe the
format of that state per stackslot.

This infrastructure is tested with some compile-tests now;
testing of the interpretation of the metadata output will come with
end-to-end debug instrumentation tests in a followup PR.

* Review feedback: add back sequence points and enforce tags only on sequence points or calls.

* Use Vecs for debug metadata in MachBuffer to avoid SmallVec size penalty in not-used case.

* Review feedback: switch from inlined stackslot descriptor blobs to u64 keys.

show more ...

Cranelift: add get_exception_handler_address. (#11629)

* Cranelift: add get_exception_handler_address.

This is designed to enable applications such as #11592 that use
alternative unwinding mechanis

Cranelift: add get_exception_handler_address. (#11629)

* Cranelift: add get_exception_handler_address.

This is designed to enable applications such as #11592 that use
alternative unwinding mechanisms that may not necessarily want to walk a
stack and look up exception tables. The idea is that whenever it would
be valid to resume to an exception handler that is active on the stack,
we can provide the same PC as a first-class runtime value that would be
found in the exception table for the given handler edge. A "custom"
resume step can then use this PC as a resume-point as long as it follows
the relevant exception ABI (i.e.: restore SP, FP, any other saved
registers that the exception ABI specifies, and provide appropriate
payload value(s)).

Handlers are associated with edges out of `try_call`s (or
`try_call_indirect`s); and edges specifically, not blocks, because there
could be multiple out-edges to one block. The instruction thus takes the
block that contains the try-call and an immediate that indexes its
exceptional edges.

This CLIF instruction required a bit of infrastructure to (i) allow
naming raw blocks, not just block calls, as instruction arguments, and
(ii) allow getting the MachLabel for any other lowered block during
lowering. But given that, the lowerings themselves are straightforward
uses of MachBuffer labels to fix-up PC-relative address-loading
instructions (e.g., `LEA` or `ADR` or `AUIPC`+`ADDI`).

* Review feedback.

* Review feedback: more tests.

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

Cranelift: support dynamic contexts in exception-handler lists. (#11321)

In #11285, we realized that Wasm semantics require us to match on
dynamic instances of exception tags, rather than static tag

Cranelift: support dynamic contexts in exception-handler lists. (#11321)

In #11285, we realized that Wasm semantics require us to match on
dynamic instances of exception tags, rather than static tag types. This
fundamentally requires the unwinder to be able to resolve the current
Wasm instance for each Wasm frame on the stack that has any handlers,
and our frame format does not provide this today.

We discussed many options, some of which solve the more general problem
(Wasm vmctx for any frame), but ultimately landed on a notion of
"dynamic context for evaluating tags", specific to Cranelift's
exception-catch metadata; and storing that context and carrying it
through to a place that is named in the unwind metadata. The reasoning
is fairly straightforward: we cannot afford a more general approach that
stores vmctx in every frame (I measured this at 20% overhead for a
recursive-Fibonacci benchmark that is call-intensive); and inlining
means that we may have *multiple* contexts at any given program point,
each associated with a different slice of the handler tags; so we need a
mechanism that, *just for a try-call*, intersperses contexts with tags
(or puts a context on each tag) and stores these somewhere that the
exception-unwind ABI doesn't clobber (e.g., on the stack).

This PR implements "option 4" from that issue, namely, *dynamic
exception contexts*. The idea is that this is the dual to exception
payload: while payload lets the unwinder communicate state *to* the
catching code, context lets the unwinder take state *from* the catching
code that lets it decide whether the tag is a match. Because of
inlining, we need to either associate (optional) context with every tag,
or intersperse context-updates with handler tags. I've opted for the
latter for efficiency at the CLIF level (in most cases there will be
multiple tags per context), though they are isomorphic.

The new tag-matching semantics are: when walking up the stack, upon
reaching a `try_call`, evaluate catch-clauses in listed order. A
`context` clause sets the current context. A `tagN: block(...)` clause
attempts to match the throwing exception against `tagN`, *evaluated in
the current context*, and branches to the named block if it matches. A
`default: block(...)` always branches to the named block.

Note that this lets us assume less about tags than before, and this
particularly manifests in the changes to the inliner. Whereas before,
`tagN` is `tagN` and an inner handler for that tag shadows an outer
handler (that is, tags always alias if identical indices); and whereas
before, `tagN` is not `tagM` and so we can order the tags arbitrarily
(that is, tags never alias if non-identical indices); now any two static
tag indices may or may not alias depending on the dynamic context of
each. Or, even in the same context, two may alias, because we leave the
match-predicate as an unspecified (user-chosen) algorithm during
unwinding. (This mirrors the reality that, for example, a Wasm instance
may import two tags, and dynamically these tags may be equal or
different at runtime, even instantiation-to-instantiation.) Cranelift's
only job is to faithfully carry the list of contexts and tags through to
the compiled-code metadata; and to ensure that they remain in the order
they were specified in the CLIF.

This PR introduces the Cranelift-level feature, and it will be used in
a subsequent PR that introduces Wasm exception handling. Because of
that, I've opted not to update the clif-utils runtest "runtime" to read
out contexts and do something with them -- we will have plenty of test
coverage via a bunch of Wasm tests for corner cases such as the above.
This PR does include filetests that show that contexts are carried
through to spillslots and those appear in the metadata.

Fixes #11285.

show more ...

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

Enable the `from_over_into` Clippy lint (#10837)

This requires implementing `From<T> for U` instead of `Into<U> for T`.
While both trait impls are valid the `From` one is more useful because
it imp

Enable the `from_over_into` Clippy lint (#10837)

This requires implementing `From<T> for U` instead of `Into<U> for T`.
While both trait impls are valid the `From` one is more useful because
it implies `Into` and additionally gives you `From`. This additionally
then migrates the existing codebase to using the new style of impls.

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

Some fixes for try_call (#10593)

* Fix cranelift-frontend handling of try_call

* Implement eliminate_unreachable_code for exception tables

* Ensure try_call is considered a memory fence

* Don't e

Some fixes for try_call (#10593)

* Fix cranelift-frontend handling of try_call

* Implement eliminate_unreachable_code for exception tables

* Ensure try_call is considered a memory fence

* Don't error on try_call in the verifier if no TargetIsa is passed

* Don't clobber all registers for try_call unless the tail call conv is used

This way other consumers of Cranelift don't have to pay the cost of the
way Wasmtime will implement unwinding on exceptions.

* Allow SystemV call conv with try_call

show more ...

Cranelift: initial try_call / try_call_indirect (exception) support. (#10510)

* Cranelift: initial try_call / try_call_indirect (exception) support.

This PR adds `try_call` and `try_call_indirect`

Cranelift: initial try_call / try_call_indirect (exception) support. (#10510)

* Cranelift: initial try_call / try_call_indirect (exception) support.

This PR adds `try_call` and `try_call_indirect` instructions, and
lowerings on four of five ISAs (x86-64, aarch64, riscv64, pulley; s390x
has its own non-shared ABI code that will need separate work).

It extends CLIF to support these instructions as new kinds of branches,
and extends block-calls to accept `retN` and `exnN` block-call args that
carry the normal return values or exception payloads (respectively) into
the appropriate successor blocks.

It wires up the "normal return path" so that it continues to work.
It updates the ABI so that unwinding is possible without an initial
register state at throw: specifically, as per our RFC, all registers are
clobbered. It also includes metadata in the `MachBuffer` that describes
exception-catch destinations. However, no unwinder exists to interpret
these catch-destinations yet, so they are untested.

* Add try_call_indirect lowering as well.

show more ...

Add some more context to the CLIF verifier (#10410)

Helps when debugging verifier failures.

Introduce verification of integer address type widths. (#10209)

* cranelift/codegen/verifier: Add verification of pointer width (#10118)

This adds a check to load that confirms the pointer width is

Introduce verification of integer address type widths. (#10209)

* cranelift/codegen/verifier: Add verification of pointer width (#10118)

This adds a check to load that confirms the pointer width is as expected
according to the target.

* cranelift/verifier: Add load pointer width verification.

Also clarify width of integer address type and unit tests that check
the new verifier rule.

* cranelift/filetests: Split out 64 and 32 bit loads.

Makes unit test pass with the verifier checking the load address
size.

* cranelift/verifier: Add address verification to more instructions.

Also adds unit tests to ensure problematic cases are detected.

* cranelift/verifier: Change wording, restructure arms.

show more ...

Compute dominator tree using semi-NCA algorithm (#9603)

* Add dominator tree computed using semi-NCA algorithm.

* Add dominator tree fuzz target

* Move previous version of dominator tree to a sepa

Compute dominator tree using semi-NCA algorithm (#9603)

* Add dominator tree computed using semi-NCA algorithm.

* Add dominator tree fuzz target

* Move previous version of dominator tree to a separate file

* Improve comments.

* Use the new dominator tree in verifier.

* Remove unused `iterators` module.

show more ...

Enforce `uninlined_format_args` for the workspace (#9065)

* Enforce `uninlined_format_args` for the workspace

* fix: failing `Monolith Checks` job

* fix: formatting

Refactor `Ieee{16,32,64,128}` (#8982)

cranelift: Add `f16const` and `f128const` instructions (#8893)

* cranelift: Add `f16const` and `f128const` instructions

* cranelift: Add constant propagation for `f16` and `f128`

Cranelift: Split out dominator tree's depth-first traversal into a reusable iterator (#8640)

We intend to use this when computing liveness of GC references in
`cranelift-frontend` to manually constr

Cranelift: Split out dominator tree's depth-first traversal into a reusable iterator (#8640)

We intend to use this when computing liveness of GC references in
`cranelift-frontend` to manually construct safepoints and ultimately remove
`r{32,64}` reference types from CLIF, `cranelift-codegen`, and `regalloc2`.

Co-authored-by: Trevor Elliott <[email protected]>

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

cranelift: Remove support for WebAssembly tables (#8124)

Wasmtime no longer needs any of this infrastructure and neither should
anybody else.

This diff is nearly identical to @bjorn3's version of t

cranelift: Remove support for WebAssembly tables (#8124)

Wasmtime no longer needs any of this infrastructure and neither should
anybody else.

This diff is nearly identical to @bjorn3's version of the same change,
except I didn't remove Uimm64, which has started being used in other
places. I forgot bjorn3 had already tackled this part until after I was
already done, but it's reassuring that we both made the same changes.

https://github.com/bjorn3/wasmtime/commit/fb82ccb3948e949641a6d9581aa84472f68f97b8

Fixes #5532

show more ...

Remove type parameter from `VerifierStepResult` (#7861)