Repository: bytecodealliance/wasmtime
Pull request #8481 (2024-04-25 23:22:44)

wasmtime(gc): Add support for array types
This commit adds support for defining array types from Wasm or the host, and managing them inside the engine's types registry. It does not introduce support for allocating or manipulating array values. That functionality will come in future pull requests.

<!--
Please make sure you include the following information:

- If this work has been discussed elsewhere, please include a link to that
  conversation. If it was discussed in an issue, just mention "issue #...".

- Explain why this change is needed. If the details are in an issue already,
  this can be brief.

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->


github-actions[bot]: #### Subscribe to Label Action

cc @fitzgen

<details>
This issue or pull request has been labeled: "fuzzing", "wasmtime:api", "wasmtime:c-api"

Thus the following users have been cc'd because of the following labels:

* fitzgen: fuzzing

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

[Learn more.](https://github.com/bytecodealliance/subscribe-to-label-action)
</details>

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 639755bbc..da9be3bda 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3414,6 +3414,7 @@ dependencies = [
  "serde",
  "serde_derive",
  "serde_json",
+ "smallvec",
  "target-lexicon",
  "tempfile",
  "wasi-common",
diff --git a/cranelift/codegen/src/isa/aarch64/inst/mod.rs b/cranelift/codegen/src/isa/aarch64/inst/mod.rs
index 4237982bc..98b7abdee 100644
--- a/cranelift/codegen/src/isa/aarch64/inst/mod.rs
+++ b/cranelift/codegen/src/isa/aarch64/inst/mod.rs
@@ -396,155 +396,157 @@ impl Inst {
 //=============================================================================
 // Instructions: get_regs
 
-fn memarg_operands<F: Fn(VReg) -> VReg>(memarg: &AMode, collector: &mut OperandCollector<'_, F>) {
+fn memarg_operands<F: Fn(VReg) -> VReg>(
+    memarg: &mut AMode,
+    collector: &mut OperandCollector<'_, F>,
+) {
     // This should match `AMode::with_allocs()`.
     match memarg {
-        &AMode::Unscaled { rn, .. } | &AMode::UnsignedOffset { rn, .. } => {
+        AMode::Unscaled { rn, .. } | AMode::UnsignedOffset { rn, .. } => {
             collector.reg_use(rn);
         }
-        &AMode::RegReg { rn, rm, .. }
-        | &AMode::RegScaled { rn, rm, .. }
-        | &AMode::RegScaledExtended { rn, rm, .. }
-        | &AMode::RegExtended { rn, rm, .. } => {
+        AMode::RegReg { rn, rm, .. }
+        | AMode::RegScaled { rn, rm, .. }
+        | AMode::RegScaledExtended { rn, rm, .. }
+        | AMode::RegExtended { rn, rm, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &AMode::Label { .. } => {}
-        &AMode::SPPreIndexed { .. } | &AMode::SPPostIndexed { .. } => {}
-        &AMode::FPOffset { .. } | &AMode::IncomingArg { .. } => {}
-        &AMode::SPOffset { .. } | &AMode::NominalSPOffset { .. } => {}
-        &AMode::RegOffset { rn, .. } => {
+        AMode::Label { .. } => {}
+        AMode::SPPreIndexed { .. } | AMode::SPPostIndexed { .. } => {}
+        AMode::FPOffset { .. } | AMode::IncomingArg { .. } => {}
+        AMode::SPOffset { .. } | AMode::NominalSPOffset { .. } => {}
+        AMode::RegOffset { rn, .. } => {
             collector.reg_use(rn);
         }
-        &AMode::Const { .. } => {}
+        AMode::Const { .. } => {}
     }
 }
 
 fn pairmemarg_operands<F: Fn(VReg) -> VReg>(
-    pairmemarg: &PairAMode,
+    pairmemarg: &mut PairAMode,
     collector: &mut OperandCollector<'_, F>,
 ) {
     // This should match `PairAMode::with_allocs()`.
     match pairmemarg {
-        &PairAMode::SignedOffset { reg, .. } => {
+        PairAMode::SignedOffset { reg, .. } => {
             collector.reg_use(reg);
         }
-        &PairAMode::SPPreIndexed { .. } | &PairAMode::SPPostIndexed { .. } => {}
+        PairAMode::SPPreIndexed { .. } | PairAMode::SPPostIndexed { .. } => {}
     }
 }
 
-fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCollector<'_, F>) {
+fn aarch64_get_operands<F: Fn(VReg) -> VReg>(
+    inst: &mut Inst,
+    collector: &mut OperandCollector<'_, F>,
+) {
     match inst {
-        &Inst::AluRRR { rd, rn, rm, .. } => {
+        Inst::AluRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::AluRRRR { rd, rn, rm, ra, .. } => {
+        Inst::AluRRRR { rd, rn, rm, ra, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_use(ra);
         }
-        &Inst::AluRRImm12 { rd, rn, .. } => {
+        Inst::AluRRImm12 { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::AluRRImmLogic { rd, rn, .. } => {
+        Inst::AluRRImmLogic { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::AluRRImmShift { rd, rn, .. } => {
+        Inst::AluRRImmShift { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::AluRRRShift { rd, rn, rm, .. } => {
+        Inst::AluRRRShift { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::AluRRRExtend { rd, rn, rm, .. } => {
+        Inst::AluRRRExtend { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::BitRR { rd, rn, .. } => {
+        Inst::BitRR { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::ULoad8 { rd, ref mem, .. }
-        | &Inst::SLoad8 { rd, ref mem, .. }
-        | &Inst::ULoad16 { rd, ref mem, .. }
-        | &Inst::SLoad16 { rd, ref mem, .. }
-        | &Inst::ULoad32 { rd, ref mem, .. }
-        | &Inst::SLoad32 { rd, ref mem, .. }
-        | &Inst::ULoad64 { rd, ref mem, .. } => {
+        Inst::ULoad8 { rd, mem, .. }
+        | Inst::SLoad8 { rd, mem, .. }
+        | Inst::ULoad16 { rd, mem, .. }
+        | Inst::SLoad16 { rd, mem, .. }
+        | Inst::ULoad32 { rd, mem, .. }
+        | Inst::SLoad32 { rd, mem, .. }
+        | Inst::ULoad64 { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::Store8 { rd, ref mem, .. }
-        | &Inst::Store16 { rd, ref mem, .. }
-        | &Inst::Store32 { rd, ref mem, .. }
-        | &Inst::Store64 { rd, ref mem, .. } => {
+        Inst::Store8 { rd, mem, .. }
+        | Inst::Store16 { rd, mem, .. }
+        | Inst::Store32 { rd, mem, .. }
+        | Inst::Store64 { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::StoreP64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::StoreP64 { rt, rt2, mem, .. } => {
             collector.reg_use(rt);
             collector.reg_use(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::LoadP64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::LoadP64 { rt, rt2, mem, .. } => {
             collector.reg_def(rt);
             collector.reg_def(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::Mov { rd, rm, .. } => {
+        Inst::Mov { rd, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rm);
         }
-        &Inst::MovFromPReg { rd, rm } => {
+        Inst::MovFromPReg { rd, rm } => {
             debug_assert!(rd.to_reg().is_virtual());
             collector.reg_def(rd);
-            collector.reg_fixed_nonallocatable(rm);
+            collector.reg_fixed_nonallocatable(*rm);
         }
-        &Inst::MovToPReg { rd, rm } => {
+        Inst::MovToPReg { rd, rm } => {
             debug_assert!(rm.is_virtual());
-            collector.reg_fixed_nonallocatable(rd);
+            collector.reg_fixed_nonallocatable(*rd);
             collector.reg_use(rm);
         }
-        &Inst::MovK { rd, rn, .. } => {
+        Inst::MovK { rd, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_reuse_def(rd, 0); // `rn` == `rd`.
         }
-        &Inst::MovWide { rd, .. } => {
+        Inst::MovWide { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::CSel { rd, rn, rm, .. } => {
+        Inst::CSel { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::CSNeg { rd, rn, rm, .. } => {
+        Inst::CSNeg { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::CSet { rd, .. } | &Inst::CSetm { rd, .. } => {
+        Inst::CSet { rd, .. } | Inst::CSetm { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::CCmp { rn, rm, .. } => {
+        Inst::CCmp { rn, rm, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::CCmpImm { rn, .. } => {
+        Inst::CCmpImm { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::AtomicRMWLoop {
+        Inst::AtomicRMWLoop {
             op,
             addr,
             operand,
@@ -557,22 +559,22 @@ fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_fixed_use(operand, xreg(26));
             collector.reg_fixed_def(oldval, xreg(27));
             collector.reg_fixed_def(scratch1, xreg(24));
-            if op != AtomicRMWLoopOp::Xchg {
+            if *op != AtomicRMWLoopOp::Xchg {
                 collector.reg_fixed_def(scratch2, xreg(28));
             }
         }
-        &Inst::AtomicRMW { rs, rt, rn, .. } => {
+        Inst::AtomicRMW { rs, rt, rn, .. } => {
             collector.reg_use(rs);
             collector.reg_def(rt);
             collector.reg_use(rn);
         }
-        &Inst::AtomicCAS { rd, rs, rt, rn, .. } => {
+        Inst::AtomicCAS { rd, rs, rt, rn, .. } => {
             collector.reg_reuse_def(rd, 1); // reuse `rs`.
             collector.reg_use(rs);
             collector.reg_use(rt);
             collector.reg_use(rn);
         }
-        &Inst::AtomicCASLoop {
+        Inst::AtomicCASLoop {
             addr,
             expected,
             replacement,
@@ -586,95 +588,95 @@ fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_fixed_def(oldval, xreg(27));
             collector.reg_fixed_def(scratch, xreg(24));
         }
-        &Inst::LoadAcquire { rt, rn, .. } => {
+        Inst::LoadAcquire { rt, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_def(rt);
         }
-        &Inst::StoreRelease { rt, rn, .. } => {
+        Inst::StoreRelease { rt, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rt);
         }
-        &Inst::Fence {} | &Inst::Csdb {} => {}
-        &Inst::FpuMove32 { rd, rn } => {
+        Inst::Fence {} | Inst::Csdb {} => {}
+        Inst::FpuMove32 { rd, rn } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuMove64 { rd, rn } => {
+        Inst::FpuMove64 { rd, rn } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuMove128 { rd, rn } => {
+        Inst::FpuMove128 { rd, rn } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuMoveFromVec { rd, rn, .. } => {
+        Inst::FpuMoveFromVec { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuExtend { rd, rn, .. } => {
+        Inst::FpuExtend { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuRR { rd, rn, .. } => {
+        Inst::FpuRR { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuRRR { rd, rn, rm, .. } => {
+        Inst::FpuRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::FpuRRI { rd, rn, .. } => {
+        Inst::FpuRRI { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuRRIMod { rd, ri, rn, .. } => {
+        Inst::FpuRRIMod { rd, ri, rn, .. } => {
             collector.reg_reuse_def(rd, 1); // reuse `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
         }
-        &Inst::FpuRRRR { rd, rn, rm, ra, .. } => {
+        Inst::FpuRRRR { rd, rn, rm, ra, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_use(ra);
         }
-        &Inst::VecMisc { rd, rn, .. } => {
+        Inst::VecMisc { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
 
-        &Inst::VecLanes { rd, rn, .. } => {
+        Inst::VecLanes { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecShiftImm { rd, rn, .. } => {
+        Inst::VecShiftImm { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecShiftImmMod { rd, ri, rn, .. } => {
+        Inst::VecShiftImmMod { rd, ri, rn, .. } => {
             collector.reg_reuse_def(rd, 1); // `rd` == `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
         }
-        &Inst::VecExtract { rd, rn, rm, .. } => {
+        Inst::VecExtract { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecTbl { rd, rn, rm } => {
+        Inst::VecTbl { rd, rn, rm } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_def(rd);
         }
-        &Inst::VecTblExt { rd, ri, rn, rm } => {
+        Inst::VecTblExt { rd, ri, rn, rm } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_reuse_def(rd, 3); // `rd` == `ri`.
             collector.reg_use(ri);
         }
 
-        &Inst::VecTbl2 { rd, rn, rn2, rm } => {
+        Inst::VecTbl2 { rd, rn, rn2, rm } => {
             // Constrain to v30 / v31 so that we satisfy the "adjacent
             // registers" constraint without use of pinned vregs in
             // lowering.
@@ -683,7 +685,7 @@ fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_use(rm);
             collector.reg_def(rd);
         }
-        &Inst::VecTbl2Ext {
+        Inst::VecTbl2Ext {
             rd,
             ri,
             rn,
@@ -699,276 +701,263 @@ fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_reuse_def(rd, 4); // `rd` == `ri`.
             collector.reg_use(ri);
         }
-        &Inst::VecLoadReplicate { rd, rn, .. } => {
+        Inst::VecLoadReplicate { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecCSel { rd, rn, rm, .. } => {
+        Inst::VecCSel { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::FpuCmp { rn, rm, .. } => {
+        Inst::FpuCmp { rn, rm, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::FpuLoad32 { rd, ref mem, .. } => {
+        Inst::FpuLoad32 { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuLoad64 { rd, ref mem, .. } => {
+        Inst::FpuLoad64 { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuLoad128 { rd, ref mem, .. } => {
+        Inst::FpuLoad128 { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuStore32 { rd, ref mem, .. } => {
+        Inst::FpuStore32 { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuStore64 { rd, ref mem, .. } => {
+        Inst::FpuStore64 { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuStore128 { rd, ref mem, .. } => {
+        Inst::FpuStore128 { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::FpuLoadP64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::FpuLoadP64 { rt, rt2, mem, .. } => {
             collector.reg_def(rt);
             collector.reg_def(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::FpuStoreP64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::FpuStoreP64 { rt, rt2, mem, .. } => {
             collector.reg_use(rt);
             collector.reg_use(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::FpuLoadP128 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::FpuLoadP128 { rt, rt2, mem, .. } => {
             collector.reg_def(rt);
             collector.reg_def(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::FpuStoreP128 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::FpuStoreP128 { rt, rt2, mem, .. } => {
             collector.reg_use(rt);
             collector.reg_use(rt2);
             pairmemarg_operands(mem, collector);
         }
-        &Inst::FpuToInt { rd, rn, .. } => {
+        Inst::FpuToInt { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::IntToFpu { rd, rn, .. } => {
+        Inst::IntToFpu { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuCSel32 { rd, rn, rm, .. } | &Inst::FpuCSel64 { rd, rn, rm, .. } => {
+        Inst::FpuCSel32 { rd, rn, rm, .. } | Inst::FpuCSel64 { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::FpuRound { rd, rn, .. } => {
+        Inst::FpuRound { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::MovToFpu { rd, rn, .. } => {
+        Inst::MovToFpu { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuMoveFPImm { rd, .. } => {
+        Inst::FpuMoveFPImm { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::MovToVec { rd, ri, rn, .. } => {
+        Inst::MovToVec { rd, ri, rn, .. } => {
             collector.reg_reuse_def(rd, 1); // `rd` == `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
         }
-        &Inst::MovFromVec { rd, rn, .. } | &Inst::MovFromVecSigned { rd, rn, .. } => {
+        Inst::MovFromVec { rd, rn, .. } | Inst::MovFromVecSigned { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecDup { rd, rn, .. } => {
+        Inst::VecDup { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecDupFromFpu { rd, rn, .. } => {
+        Inst::VecDupFromFpu { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecDupFPImm { rd, .. } => {
+        Inst::VecDupFPImm { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecDupImm { rd, .. } => {
+        Inst::VecDupImm { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecExtend { rd, rn, .. } => {
+        Inst::VecExtend { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecMovElement { rd, ri, rn, .. } => {
+        Inst::VecMovElement { rd, ri, rn, .. } => {
             collector.reg_reuse_def(rd, 1); // `rd` == `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
         }
-        &Inst::VecRRLong { rd, rn, .. } => {
+        Inst::VecRRLong { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecRRNarrowLow { rd, rn, .. } => {
+        Inst::VecRRNarrowLow { rd, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_def(rd);
         }
-        &Inst::VecRRNarrowHigh { rd, ri, rn, .. } => {
+        Inst::VecRRNarrowHigh { rd, ri, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_reuse_def(rd, 2); // `rd` == `ri`.
             collector.reg_use(ri);
         }
-        &Inst::VecRRPair { rd, rn, .. } => {
+        Inst::VecRRPair { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecRRRLong { rd, rn, rm, .. } => {
+        Inst::VecRRRLong { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecRRRLongMod { rd, ri, rn, rm, .. } => {
+        Inst::VecRRRLongMod { rd, ri, rn, rm, .. } => {
             collector.reg_reuse_def(rd, 1); // `rd` == `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecRRPairLong { rd, rn, .. } => {
+        Inst::VecRRPairLong { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecRRR { rd, rn, rm, .. } => {
+        Inst::VecRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecRRRMod { rd, ri, rn, rm, .. } | &Inst::VecFmlaElem { rd, ri, rn, rm, .. } => {
+        Inst::VecRRRMod { rd, ri, rn, rm, .. } | Inst::VecFmlaElem { rd, ri, rn, rm, .. } => {
             collector.reg_reuse_def(rd, 1); // `rd` == `ri`.
             collector.reg_use(ri);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::MovToNZCV { rn } => {
+        Inst::MovToNZCV { rn } => {
             collector.reg_use(rn);
         }
-        &Inst::MovFromNZCV { rd } => {
+        Inst::MovFromNZCV { rd } => {
             collector.reg_def(rd);
         }
-        &Inst::Extend { rd, rn, .. } => {
+        Inst::Extend { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::Args { ref args } => {
-            for arg in args {
-                collector.reg_fixed_def(arg.vreg, arg.preg);
+        Inst::Args { args } => {
+            for ArgPair { vreg, preg } in args {
+                collector.reg_fixed_def(vreg, *preg);
             }
         }
-        &Inst::Rets { ref rets } => {
-            for ret in rets {
-                collector.reg_fixed_use(ret.vreg, ret.preg);
+        Inst::Rets { rets } => {
+            for RetPair { vreg, preg } in rets {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::Ret { .. } | &Inst::AuthenticatedRet { .. } => {}
-        &Inst::Jump { .. } => {}
-        &Inst::Call { ref info, .. } => {
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::Ret { .. } | Inst::AuthenticatedRet { .. } => {}
+        Inst::Jump { .. } => {}
+        Inst::Call { info, .. } => {
+            let CallInfo { uses, defs, .. } = &mut **info;
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             collector.reg_clobbers(info.clobbers);
         }
-        &Inst::CallInd { ref info, .. } => {
-            collector.reg_use(info.rn);
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::CallInd { info, .. } => {
+            let CallIndInfo { rn, uses, defs, .. } = &mut **info;
+            collector.reg_use(rn);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             collector.reg_clobbers(info.clobbers);
         }
-        &Inst::ReturnCall {
-            ref info,
-            callee: _,
-        } => {
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::ReturnCall { info, callee: _ } => {
+            for CallArgPair { vreg, preg } in &mut info.uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::ReturnCallInd { ref info, callee } => {
+        Inst::ReturnCallInd { info, callee } => {
             // TODO(https://github.com/bytecodealliance/regalloc2/issues/145):
             // This shouldn't be a fixed register constraint, but it's not clear how to pick a
             // register that won't be clobbered by the callee-save restore code emitted with a
             // return_call_indirect.
             collector.reg_fixed_use(callee, xreg(1));
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            for CallArgPair { vreg, preg } in &mut info.uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::CondBr { ref kind, .. } => match kind {
-            CondBrKind::Zero(rt) | CondBrKind::NotZero(rt) => {
-                collector.reg_use(*rt);
-            }
+        Inst::CondBr { kind, .. } => match kind {
+            CondBrKind::Zero(rt) | CondBrKind::NotZero(rt) => collector.reg_use(rt),
             CondBrKind::Cond(_) => {}
         },
-        &Inst::TestBitAndBranch { rn, .. } => {
+        Inst::TestBitAndBranch { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::IndirectBr { rn, .. } => {
+        Inst::IndirectBr { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::Nop0 | Inst::Nop4 => {}
-        &Inst::Brk => {}
-        &Inst::Udf { .. } => {}
-        &Inst::TrapIf { ref kind, .. } => match kind {
-            CondBrKind::Zero(rt) | CondBrKind::NotZero(rt) => {
-                collector.reg_use(*rt);
-            }
+        Inst::Nop0 | Inst::Nop4 => {}
+        Inst::Brk => {}
+        Inst::Udf { .. } => {}
+        Inst::TrapIf { kind, .. } => match kind {
+            CondBrKind::Zero(rt) | CondBrKind::NotZero(rt) => collector.reg_use(rt),
             CondBrKind::Cond(_) => {}
         },
-        &Inst::Adr { rd, .. } | &Inst::Adrp { rd, .. } => {
+        Inst::Adr { rd, .. } | Inst::Adrp { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::Word4 { .. } | &Inst::Word8 { .. } => {}
-        &Inst::JTSequence {
+        Inst::Word4 { .. } | Inst::Word8 { .. } => {}
+        Inst::JTSequence {
             ridx, rtmp1, rtmp2, ..
         } => {
             collector.reg_use(ridx);
             collector.reg_early_def(rtmp1);
             collector.reg_early_def(rtmp2);
         }
-        &Inst::LoadExtName { rd, .. } => {
+        Inst::LoadExtName { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::LoadAddr { rd, ref mem } => {
+        Inst::LoadAddr { rd, mem } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::Paci { .. } | &Inst::Xpaclri => {
+        Inst::Paci { .. } | Inst::Xpaclri => {
             // Neither LR nor SP is an allocatable register, so there is no need
             // to do anything.
         }
-        &Inst::Bti { .. } => {}
-        &Inst::VirtualSPOffsetAdj { .. } => {}
+        Inst::Bti { .. } => {}
+        Inst::VirtualSPOffsetAdj { .. } => {}
 
-        &Inst::ElfTlsGetAddr { rd, tmp, .. } => {
+        Inst::ElfTlsGetAddr { rd, tmp, .. } => {
             // TLSDESC has a very neat calling convention. It is required to preserve
             // all registers except x0 and x30. X30 is non allocatable in cranelift since
             // its the link register.
@@ -978,19 +967,19 @@ fn aarch64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_fixed_def(rd, regs::xreg(0));
             collector.reg_early_def(tmp);
         }
-        &Inst::MachOTlsGetAddr { rd, .. } => {
+        Inst::MachOTlsGetAddr { rd, .. } => {
             collector.reg_fixed_def(rd, regs::xreg(0));
             let mut clobbers =
                 AArch64MachineDeps::get_regs_clobbered_by_call(CallConv::AppleAarch64);
             clobbers.remove(regs::xreg_preg(0));
             collector.reg_clobbers(clobbers);
         }
-        &Inst::Unwind { .. } => {}
-        &Inst::EmitIsland { .. } => {}
-        &Inst::DummyUse { reg } => {
+        Inst::Unwind { .. } => {}
+        Inst::EmitIsland { .. } => {}
+        Inst::DummyUse { reg } => {
             collector.reg_use(reg);
         }
-        &Inst::StackProbeLoop { start, end, .. } => {
+        Inst::StackProbeLoop { start, end, .. } => {
             collector.reg_early_def(start);
             collector.reg_use(end);
         }
@@ -1008,7 +997,7 @@ impl MachInst for Inst {
     // debugging.
     const TRAP_OPCODE: &'static [u8] = &0xc11f_u32.to_le_bytes();
 
-    fn get_operands<F: Fn(VReg) -> VReg>(&self, collector: &mut OperandCollector<'_, F>) {
+    fn get_operands<F: Fn(VReg) -> VReg>(&mut self, collector: &mut OperandCollector<'_, F>) {
         aarch64_get_operands(self, collector);
     }
 
diff --git a/cranelift/codegen/src/isa/riscv64/inst/args.rs b/cranelift/codegen/src/isa/riscv64/inst/args.rs
index 12fa965b7..42326222b 100644
--- a/cranelift/codegen/src/isa/riscv64/inst/args.rs
+++ b/cranelift/codegen/src/isa/riscv64/inst/args.rs
@@ -128,11 +128,11 @@ impl AMode {
     /// Add the registers referenced by this AMode to `collector`.
     /// Keep this in sync with `with_allocs`.
     pub(crate) fn get_operands<F: Fn(regalloc2::VReg) -> regalloc2::VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
-            &AMode::RegOffset(reg, ..) => collector.reg_use(reg),
+            AMode::RegOffset(reg, ..) => collector.reg_use(reg),
             // Registers used in these modes aren't allocatable.
             AMode::SPOffset(..)
             | AMode::FPOffset(..)
diff --git a/cranelift/codegen/src/isa/riscv64/inst/mod.rs b/cranelift/codegen/src/isa/riscv64/inst/mod.rs
index fbd3020a3..fe148b43c 100644
--- a/cranelift/codegen/src/isa/riscv64/inst/mod.rs
+++ b/cranelift/codegen/src/isa/riscv64/inst/mod.rs
@@ -318,164 +318,168 @@ impl Inst {
 //=============================================================================
 
 fn vec_mask_operands<F: Fn(VReg) -> VReg>(
-    mask: &VecOpMasking,
+    mask: &mut VecOpMasking,
     collector: &mut OperandCollector<'_, F>,
 ) {
     match mask {
         VecOpMasking::Enabled { reg } => {
-            collector.reg_fixed_use(*reg, pv_reg(0).into());
+            collector.reg_fixed_use(reg, pv_reg(0).into());
         }
         VecOpMasking::Disabled => {}
     }
 }
 fn vec_mask_late_operands<F: Fn(VReg) -> VReg>(
-    mask: &VecOpMasking,
+    mask: &mut VecOpMasking,
     collector: &mut OperandCollector<'_, F>,
 ) {
     match mask {
         VecOpMasking::Enabled { reg } => {
-            collector.reg_fixed_late_use(*reg, pv_reg(0).into());
+            collector.reg_fixed_late_use(reg, pv_reg(0).into());
         }
         VecOpMasking::Disabled => {}
     }
 }
 
-fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCollector<'_, F>) {
+fn riscv64_get_operands<F: Fn(VReg) -> VReg>(
+    inst: &mut Inst,
+    collector: &mut OperandCollector<'_, F>,
+) {
     match inst {
-        &Inst::Nop0 => {}
-        &Inst::Nop4 => {}
-        &Inst::BrTable {
+        Inst::Nop0 | Inst::Nop4 => {}
+        Inst::BrTable {
             index, tmp1, tmp2, ..
         } => {
             collector.reg_use(index);
             collector.reg_early_def(tmp1);
             collector.reg_early_def(tmp2);
         }
-        &Inst::Auipc { rd, .. } => collector.reg_def(rd),
-        &Inst::Lui { rd, .. } => collector.reg_def(rd),
-        &Inst::LoadInlineConst { rd, .. } => collector.reg_def(rd),
-        &Inst::AluRRR { rd, rs1, rs2, .. } => {
+        Inst::Auipc { rd, .. } => collector.reg_def(rd),
+        Inst::Lui { rd, .. } => collector.reg_def(rd),
+        Inst::LoadInlineConst { rd, .. } => collector.reg_def(rd),
+        Inst::AluRRR { rd, rs1, rs2, .. } => {
             collector.reg_use(rs1);
             collector.reg_use(rs2);
             collector.reg_def(rd);
         }
-        &Inst::FpuRRR { rd, rs1, rs2, .. } => {
+        Inst::FpuRRR { rd, rs1, rs2, .. } => {
             collector.reg_use(rs1);
             collector.reg_use(rs2);
             collector.reg_def(rd);
         }
-        &Inst::AluRRImm12 { rd, rs, .. } => {
+        Inst::AluRRImm12 { rd, rs, .. } => {
             collector.reg_use(rs);
             collector.reg_def(rd);
         }
-        &Inst::CsrReg { rd, rs, .. } => {
+        Inst::CsrReg { rd, rs, .. } => {
             collector.reg_use(rs);
             collector.reg_def(rd);
         }
-        &Inst::CsrImm { rd, .. } => {
+        Inst::CsrImm { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::Load { rd, from, .. } => {
+        Inst::Load { rd, from, .. } => {
             from.get_operands(collector);
             collector.reg_def(rd);
         }
-        &Inst::Store { to, src, .. } => {
+        Inst::Store { to, src, .. } => {
             to.get_operands(collector);
             collector.reg_use(src);
         }
 
-        &Inst::Args { ref args } => {
-            for arg in args {
-                collector.reg_fixed_def(arg.vreg, arg.preg);
+        Inst::Args { args } => {
+            for ArgPair { vreg, preg } in args {
+                collector.reg_fixed_def(vreg, *preg);
             }
         }
-        &Inst::Rets { ref rets } => {
-            for ret in rets {
-                collector.reg_fixed_use(ret.vreg, ret.preg);
+        Inst::Rets { rets } => {
+            for RetPair { vreg, preg } in rets {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::Ret { .. } => {}
+        Inst::Ret { .. } => {}
 
-        &Inst::Extend { rd, rn, .. } => {
+        Inst::Extend { rd, rn, .. } => {
             collector.reg_use(rn);
             collector.reg_def(rd);
         }
-        &Inst::Call { ref info } => {
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::Call { info } => {
+            let CallInfo { uses, defs, .. } = &mut **info;
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             collector.reg_clobbers(info.clobbers);
         }
-        &Inst::CallInd { ref info } => {
-            collector.reg_use(info.rn);
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::CallInd { info } => {
+            let CallIndInfo { rn, uses, defs, .. } = &mut **info;
+            collector.reg_use(rn);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             collector.reg_clobbers(info.clobbers);
         }
-        &Inst::ReturnCall {
-            callee: _,
-            ref info,
-        } => {
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::ReturnCall { info, .. } => {
+            for CallArgPair { vreg, preg } in &mut info.uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::ReturnCallInd { ref info, callee } => {
+        Inst::ReturnCallInd { info, callee } => {
             // TODO(https://github.com/bytecodealliance/regalloc2/issues/145):
             // This shouldn't be a fixed register constraint.
             collector.reg_fixed_use(callee, x_reg(5));
 
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            for CallArgPair { vreg, preg } in &mut info.uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::Jal { .. } => {
+        Inst::Jal { .. } => {
             // JAL technically has a rd register, but we currently always
             // hardcode it to x0.
         }
-        &Inst::CondBr { kind, .. } => {
-            collector.reg_use(kind.rs1);
-            collector.reg_use(kind.rs2);
+        Inst::CondBr {
+            kind: IntegerCompare { rs1, rs2, .. },
+            ..
+        } => {
+            collector.reg_use(rs1);
+            collector.reg_use(rs2);
         }
-        &Inst::LoadExtName { rd, .. } => {
+        Inst::LoadExtName { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::ElfTlsGetAddr { rd, .. } => {
+        Inst::ElfTlsGetAddr { rd, .. } => {
             // x10 is a0 which is both the first argument and the first return value.
             collector.reg_fixed_def(rd, a0());
             let mut clobbers = Riscv64MachineDeps::get_regs_clobbered_by_call(CallConv::SystemV);
             clobbers.remove(px_reg(10));
             collector.reg_clobbers(clobbers);
         }
-        &Inst::LoadAddr { rd, mem } => {
+        Inst::LoadAddr { rd, mem } => {
             mem.get_operands(collector);
             collector.reg_early_def(rd);
         }
 
-        &Inst::VirtualSPOffsetAdj { .. } => {}
-        &Inst::Mov { rd, rm, .. } => {
+        Inst::VirtualSPOffsetAdj { .. } => {}
+        Inst::Mov { rd, rm, .. } => {
             collector.reg_use(rm);
             collector.reg_def(rd);
         }
-        &Inst::MovFromPReg { rd, rm } => {
-            debug_assert!([px_reg(2), px_reg(8)].contains(&rm));
+        Inst::MovFromPReg { rd, rm } => {
+            debug_assert!([px_reg(2), px_reg(8)].contains(rm));
             collector.reg_def(rd);
         }
-        &Inst::Fence { .. } => {}
-        &Inst::EBreak => {}
-        &Inst::Udf { .. } => {}
-        &Inst::FpuRR { rd, rs, .. } => {
+        Inst::Fence { .. } => {}
+        Inst::EBreak => {}
+        Inst::Udf { .. } => {}
+        Inst::FpuRR { rd, rs, .. } => {
             collector.reg_use(rs);
             collector.reg_def(rd);
         }
-        &Inst::FpuRRRR {
+        Inst::FpuRRRR {
             rd, rs1, rs2, rs3, ..
         } => {
             collector.reg_use(rs1);
@@ -484,28 +488,28 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_def(rd);
         }
 
-        &Inst::Jalr { rd, base, .. } => {
+        Inst::Jalr { rd, base, .. } => {
             collector.reg_use(base);
             collector.reg_def(rd);
         }
-        &Inst::Atomic { rd, addr, src, .. } => {
+        Inst::Atomic { rd, addr, src, .. } => {
             collector.reg_use(addr);
             collector.reg_use(src);
             collector.reg_def(rd);
         }
-        &Inst::Select {
-            ref dst,
-            condition,
+        Inst::Select {
+            dst,
+            condition: IntegerCompare { rs1, rs2, .. },
             x,
             y,
             ..
         } => {
-            collector.reg_use(condition.rs1);
-            collector.reg_use(condition.rs2);
-            for &reg in x.regs() {
+            collector.reg_use(rs1);
+            collector.reg_use(rs2);
+            for reg in x.regs_mut() {
                 collector.reg_use(reg);
             }
-            for &reg in y.regs() {
+            for reg in y.regs_mut() {
                 collector.reg_use(reg);
             }
             // If there's more than one destination register then use
@@ -517,16 +521,16 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             // When there's only one destination register though don't use an
             // early def because once the register is written no other inputs
             // are read so it's ok for the destination to overlap the sources.
-            match dst.regs() {
-                [reg] => collector.reg_def(*reg),
+            match dst.regs_mut() {
+                [reg] => collector.reg_def(reg),
                 regs => {
                     for d in regs {
-                        collector.reg_early_def(*d);
+                        collector.reg_early_def(d);
                     }
                 }
             }
         }
-        &Inst::AtomicCas {
+        Inst::AtomicCas {
             offset,
             t0,
             dst,
@@ -543,16 +547,16 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(dst);
         }
 
-        &Inst::RawData { .. } => {}
-        &Inst::AtomicStore { src, p, .. } => {
+        Inst::RawData { .. } => {}
+        Inst::AtomicStore { src, p, .. } => {
             collector.reg_use(src);
             collector.reg_use(p);
         }
-        &Inst::AtomicLoad { rd, p, .. } => {
+        Inst::AtomicLoad { rd, p, .. } => {
             collector.reg_use(p);
             collector.reg_def(rd);
         }
-        &Inst::AtomicRmwLoop {
+        Inst::AtomicRmwLoop {
             offset,
             dst,
             p,
@@ -566,15 +570,15 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(t0);
             collector.reg_early_def(dst);
         }
-        &Inst::TrapIf { rs1, rs2, .. } => {
+        Inst::TrapIf { rs1, rs2, .. } => {
             collector.reg_use(rs1);
             collector.reg_use(rs2);
         }
-        &Inst::Unwind { .. } => {}
-        &Inst::DummyUse { reg } => {
+        Inst::Unwind { .. } => {}
+        Inst::DummyUse { reg } => {
             collector.reg_use(reg);
         }
-        &Inst::FloatRound {
+        Inst::FloatRound {
             rd,
             int_tmp,
             f_tmp,
@@ -586,7 +590,7 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(f_tmp);
             collector.reg_early_def(rd);
         }
-        &Inst::Popcnt {
+        Inst::Popcnt {
             sum, step, rs, tmp, ..
         } => {
             collector.reg_use(rs);
@@ -594,7 +598,7 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(step);
             collector.reg_early_def(sum);
         }
-        &Inst::Cltz {
+        Inst::Cltz {
             sum, step, tmp, rs, ..
         } => {
             collector.reg_use(rs);
@@ -602,7 +606,7 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(step);
             collector.reg_early_def(sum);
         }
-        &Inst::Brev8 {
+        Inst::Brev8 {
             rs,
             rd,
             step,
@@ -616,19 +620,19 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_early_def(tmp2);
             collector.reg_early_def(rd);
         }
-        &Inst::StackProbeLoop { .. } => {
+        Inst::StackProbeLoop { .. } => {
             // StackProbeLoop has a tmp register and StackProbeLoop used at gen_prologue.
             // t3 will do the job. (t3 is caller-save register and not used directly by compiler like writable_spilltmp_reg)
             // gen_prologue is called at emit stage.
             // no need let reg alloc know.
         }
-        &Inst::VecAluRRRR {
+        Inst::VecAluRRRR {
             op,
             vd,
             vd_src,
             vs1,
             vs2,
-            ref mask,
+            mask,
             ..
         } => {
             debug_assert_eq!(vd_src.class(), RegClass::Vector);
@@ -642,12 +646,12 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
             collector.reg_reuse_def(vd, 2); // `vd` == `vd_src`.
             vec_mask_late_operands(mask, collector);
         }
-        &Inst::VecAluRRRImm5 {
+        Inst::VecAluRRRImm5 {
             op,
             vd,
             vd_src,
             vs2,
-            ref mask,
+            mask,
             ..
         } => {
             debug_assert_eq!(vd_src.class(), RegClass::Vector);
@@ -668,12 +672,12 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
                 vec_mask_operands(mask, collector);
             }
         }
-        &Inst::VecAluRRR {
+        Inst::VecAluRRR {
             op,
             vd,
             vs1,
             vs2,
-            ref mask,
+            mask,
             ..
         } => {
             debug_assert_eq!(vd.to_reg().class(), RegClass::Vector);
@@ -694,12 +698,8 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
 
             vec_mask_operands(mask, collector);
         }
-        &Inst::VecAluRRImm5 {
-            op,
-            vd,
-            vs2,
-            ref mask,
-            ..
+        Inst::VecAluRRImm5 {
+            op, vd, vs2, mask, ..
         } => {
             debug_assert_eq!(vd.to_reg().class(), RegClass::Vector);
             debug_assert_eq!(vs2.class(), RegClass::Vector);
@@ -717,12 +717,8 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
 
             vec_mask_operands(mask, collector);
         }
-        &Inst::VecAluRR {
-            op,
-            vd,
-            vs,
-            ref mask,
-            ..
+        Inst::VecAluRR {
+            op, vd, vs, mask, ..
         } => {
             debug_assert_eq!(vd.to_reg().class(), op.dst_regclass());
             debug_assert_eq!(vs.class(), op.src_regclass());
@@ -740,34 +736,22 @@ fn riscv64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut Operan
 
             vec_mask_operands(mask, collector);
         }
-        &Inst::VecAluRImm5 {
-            op, vd, ref mask, ..
-        } => {
+        Inst::VecAluRImm5 { op, vd, mask, .. } => {
             debug_assert_eq!(vd.to_reg().class(), RegClass::Vector);
             debug_assert!(!op.forbids_overlaps(mask));
 
             collector.reg_def(vd);
             vec_mask_operands(mask, collector);
         }
-        &Inst::VecSetState { rd, .. } => {
+        Inst::VecSetState { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecLoad {
-            to,
-            ref from,
-            ref mask,
-            ..
-        } => {
+        Inst::VecLoad { to, from, mask, .. } => {
             from.get_operands(collector);
             collector.reg_def(to);
             vec_mask_operands(mask, collector);
         }
-        &Inst::VecStore {
-            ref to,
-            from,
-            ref mask,
-            ..
-        } => {
+        Inst::VecStore { to, from, mask, .. } => {
             to.get_operands(collector);
             collector.reg_use(from);
             vec_mask_operands(mask, collector);
@@ -805,7 +789,7 @@ impl MachInst for Inst {
         }
     }
 
-    fn get_operands<F: Fn(VReg) -> VReg>(&self, collector: &mut OperandCollector<'_, F>) {
+    fn get_operands<F: Fn(VReg) -> VReg>(&mut self, collector: &mut OperandCollector<'_, F>) {
         riscv64_get_operands(self, collector);
     }
 
diff --git a/cranelift/codegen/src/isa/riscv64/inst/vector.rs b/cranelift/codegen/src/isa/riscv64/inst/vector.rs
index aea65523e..dc04ba9ca 100644
--- a/cranelift/codegen/src/isa/riscv64/inst/vector.rs
+++ b/cranelift/codegen/src/isa/riscv64/inst/vector.rs
@@ -1071,7 +1071,7 @@ impl VecAMode {
     }
 
     pub fn get_operands<F: Fn(regalloc2::VReg) -> regalloc2::VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
diff --git a/cranelift/codegen/src/isa/s390x/inst/mod.rs b/cranelift/codegen/src/isa/s390x/inst/mod.rs
index 6f74de82f..a59c06a93 100644
--- a/cranelift/codegen/src/isa/s390x/inst/mod.rs
+++ b/cranelift/codegen/src/isa/s390x/inst/mod.rs
@@ -389,215 +389,205 @@ impl Inst {
 //=============================================================================
 // Instructions: get_regs
 
-fn memarg_operands<F: Fn(VReg) -> VReg>(memarg: &MemArg, collector: &mut OperandCollector<'_, F>) {
+fn memarg_operands<F: Fn(VReg) -> VReg>(
+    memarg: &mut MemArg,
+    collector: &mut OperandCollector<'_, F>,
+) {
     match memarg {
-        &MemArg::BXD12 { base, index, .. } | &MemArg::BXD20 { base, index, .. } => {
+        MemArg::BXD12 { base, index, .. } | MemArg::BXD20 { base, index, .. } => {
             collector.reg_use(base);
             collector.reg_use(index);
         }
-        &MemArg::Label { .. } | &MemArg::Symbol { .. } => {}
-        &MemArg::RegOffset { reg, .. } => {
+        MemArg::Label { .. } | MemArg::Symbol { .. } => {}
+        MemArg::RegOffset { reg, .. } => {
             collector.reg_use(reg);
         }
-        &MemArg::InitialSPOffset { .. } | &MemArg::NominalSPOffset { .. } => {}
+        MemArg::InitialSPOffset { .. } | MemArg::NominalSPOffset { .. } => {}
     }
     // mem_finalize might require %r1 to hold (part of) the address.
     // Conservatively assume this will always be necessary here.
     collector.reg_fixed_nonallocatable(gpr_preg(1));
 }
 
-fn s390x_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCollector<'_, F>) {
+fn s390x_get_operands<F: Fn(VReg) -> VReg>(
+    inst: &mut Inst,
+    collector: &mut OperandCollector<'_, F>,
+) {
     match inst {
-        &Inst::AluRRR { rd, rn, rm, .. } => {
+        Inst::AluRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::AluRRSImm16 { rd, rn, .. } => {
+        Inst::AluRRSImm16 { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::AluRR { rd, ri, rm, .. } => {
+        Inst::AluRR { rd, ri, rm, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rm);
         }
-        &Inst::AluRX {
-            rd, ri, ref mem, ..
-        } => {
+        Inst::AluRX { rd, ri, mem, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             memarg_operands(mem, collector);
         }
-        &Inst::AluRSImm16 { rd, ri, .. } => {
+        Inst::AluRSImm16 { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::AluRSImm32 { rd, ri, .. } => {
+        Inst::AluRSImm32 { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::AluRUImm32 { rd, ri, .. } => {
+        Inst::AluRUImm32 { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::AluRUImm16Shifted { rd, ri, .. } => {
+        Inst::AluRUImm16Shifted { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::AluRUImm32Shifted { rd, ri, .. } => {
+        Inst::AluRUImm32Shifted { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::SMulWide { rd, rn, rm } => {
+        Inst::SMulWide { rd, rn, rm } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
             // FIXME: The pair is hard-coded as %r2/%r3 because regalloc cannot handle pairs. If
             // that changes, all the hard-coded uses of %r2/%r3 can be changed.
-            collector.reg_fixed_def(rd.hi, gpr(2));
-            collector.reg_fixed_def(rd.lo, gpr(3));
+            collector.reg_fixed_def(&mut rd.hi, gpr(2));
+            collector.reg_fixed_def(&mut rd.lo, gpr(3));
         }
-        &Inst::UMulWide { rd, ri, rn } => {
+        Inst::UMulWide { rd, ri, rn } => {
             collector.reg_use(rn);
-            collector.reg_fixed_def(rd.hi, gpr(2));
-            collector.reg_fixed_def(rd.lo, gpr(3));
+            collector.reg_fixed_def(&mut rd.hi, gpr(2));
+            collector.reg_fixed_def(&mut rd.lo, gpr(3));
             collector.reg_fixed_use(ri, gpr(3));
         }
-        &Inst::SDivMod32 { rd, ri, rn } | &Inst::SDivMod64 { rd, ri, rn } => {
+        Inst::SDivMod32 { rd, ri, rn } | Inst::SDivMod64 { rd, ri, rn } => {
             collector.reg_use(rn);
-            collector.reg_fixed_def(rd.hi, gpr(2));
-            collector.reg_fixed_def(rd.lo, gpr(3));
+            collector.reg_fixed_def(&mut rd.hi, gpr(2));
+            collector.reg_fixed_def(&mut rd.lo, gpr(3));
             collector.reg_fixed_use(ri, gpr(3));
         }
-        &Inst::UDivMod32 { rd, ri, rn } | &Inst::UDivMod64 { rd, ri, rn } => {
+        Inst::UDivMod32 { rd, ri, rn } | Inst::UDivMod64 { rd, ri, rn } => {
             collector.reg_use(rn);
-            collector.reg_fixed_def(rd.hi, gpr(2));
-            collector.reg_fixed_def(rd.lo, gpr(3));
-            collector.reg_fixed_use(ri.hi, gpr(2));
-            collector.reg_fixed_use(ri.lo, gpr(3));
+            collector.reg_fixed_def(&mut rd.hi, gpr(2));
+            collector.reg_fixed_def(&mut rd.lo, gpr(3));
+            collector.reg_fixed_use(&mut ri.hi, gpr(2));
+            collector.reg_fixed_use(&mut ri.lo, gpr(3));
         }
-        &Inst::Flogr { rd, rn } => {
+        Inst::Flogr { rd, rn } => {
             collector.reg_use(rn);
-            collector.reg_fixed_def(rd.hi, gpr(2));
-            collector.reg_fixed_def(rd.lo, gpr(3));
+            collector.reg_fixed_def(&mut rd.hi, gpr(2));
+            collector.reg_fixed_def(&mut rd.lo, gpr(3));
         }
-        &Inst::ShiftRR {
+        Inst::ShiftRR {
             rd, rn, shift_reg, ..
         } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(shift_reg);
         }
-        &Inst::RxSBG { rd, ri, rn, .. } => {
+        Inst::RxSBG { rd, ri, rn, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rn);
         }
-        &Inst::RxSBGTest { rd, rn, .. } => {
+        Inst::RxSBGTest { rd, rn, .. } => {
             collector.reg_use(rd);
             collector.reg_use(rn);
         }
-        &Inst::UnaryRR { rd, rn, .. } => {
+        Inst::UnaryRR { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::CmpRR { rn, rm, .. } => {
+        Inst::CmpRR { rn, rm, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::CmpRX { rn, ref mem, .. } => {
+        Inst::CmpRX { rn, mem, .. } => {
             collector.reg_use(rn);
             memarg_operands(mem, collector);
         }
-        &Inst::CmpRSImm16 { rn, .. } => {
+        Inst::CmpRSImm16 { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::CmpRSImm32 { rn, .. } => {
+        Inst::CmpRSImm32 { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::CmpRUImm32 { rn, .. } => {
+        Inst::CmpRUImm32 { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::CmpTrapRR { rn, rm, .. } => {
+        Inst::CmpTrapRR { rn, rm, .. } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::CmpTrapRSImm16 { rn, .. } => {
+        Inst::CmpTrapRSImm16 { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::CmpTrapRUImm16 { rn, .. } => {
+        Inst::CmpTrapRUImm16 { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::AtomicRmw {
-            rd, rn, ref mem, ..
-        } => {
+        Inst::AtomicRmw { rd, rn, mem, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             memarg_operands(mem, collector);
         }
-        &Inst::AtomicCas32 {
-            rd,
-            ri,
-            rn,
-            ref mem,
-            ..
+        Inst::AtomicCas32 {
+            rd, ri, rn, mem, ..
         }
-        | &Inst::AtomicCas64 {
-            rd,
-            ri,
-            rn,
-            ref mem,
-            ..
+        | Inst::AtomicCas64 {
+            rd, ri, rn, mem, ..
         } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rn);
             memarg_operands(mem, collector);
         }
-        &Inst::Fence => {}
-        &Inst::Load32 { rd, ref mem, .. }
-        | &Inst::Load32ZExt8 { rd, ref mem, .. }
-        | &Inst::Load32SExt8 { rd, ref mem, .. }
-        | &Inst::Load32ZExt16 { rd, ref mem, .. }
-        | &Inst::Load32SExt16 { rd, ref mem, .. }
-        | &Inst::Load64 { rd, ref mem, .. }
-        | &Inst::Load64ZExt8 { rd, ref mem, .. }
-        | &Inst::Load64SExt8 { rd, ref mem, .. }
-        | &Inst::Load64ZExt16 { rd, ref mem, .. }
-        | &Inst::Load64SExt16 { rd, ref mem, .. }
-        | &Inst::Load64ZExt32 { rd, ref mem, .. }
-        | &Inst::Load64SExt32 { rd, ref mem, .. }
-        | &Inst::LoadRev16 { rd, ref mem, .. }
-        | &Inst::LoadRev32 { rd, ref mem, .. }
-        | &Inst::LoadRev64 { rd, ref mem, .. } => {
+        Inst::Fence => {}
+        Inst::Load32 { rd, mem, .. }
+        | Inst::Load32ZExt8 { rd, mem, .. }
+        | Inst::Load32SExt8 { rd, mem, .. }
+        | Inst::Load32ZExt16 { rd, mem, .. }
+        | Inst::Load32SExt16 { rd, mem, .. }
+        | Inst::Load64 { rd, mem, .. }
+        | Inst::Load64ZExt8 { rd, mem, .. }
+        | Inst::Load64SExt8 { rd, mem, .. }
+        | Inst::Load64ZExt16 { rd, mem, .. }
+        | Inst::Load64SExt16 { rd, mem, .. }
+        | Inst::Load64ZExt32 { rd, mem, .. }
+        | Inst::Load64SExt32 { rd, mem, .. }
+        | Inst::LoadRev16 { rd, mem, .. }
+        | Inst::LoadRev32 { rd, mem, .. }
+        | Inst::LoadRev64 { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::Store8 { rd, ref mem, .. }
-        | &Inst::Store16 { rd, ref mem, .. }
-        | &Inst::Store32 { rd, ref mem, .. }
-        | &Inst::Store64 { rd, ref mem, .. }
-        | &Inst::StoreRev16 { rd, ref mem, .. }
-        | &Inst::StoreRev32 { rd, ref mem, .. }
-        | &Inst::StoreRev64 { rd, ref mem, .. } => {
+        Inst::Store8 { rd, mem, .. }
+        | Inst::Store16 { rd, mem, .. }
+        | Inst::Store32 { rd, mem, .. }
+        | Inst::Store64 { rd, mem, .. }
+        | Inst::StoreRev16 { rd, mem, .. }
+        | Inst::StoreRev32 { rd, mem, .. }
+        | Inst::StoreRev64 { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::StoreImm8 { ref mem, .. }
-        | &Inst::StoreImm16 { ref mem, .. }
-        | &Inst::StoreImm32SExt16 { ref mem, .. }
-        | &Inst::StoreImm64SExt16 { ref mem, .. } => {
+        Inst::StoreImm8 { mem, .. }
+        | Inst::StoreImm16 { mem, .. }
+        | Inst::StoreImm32SExt16 { mem, .. }
+        | Inst::StoreImm64SExt16 { mem, .. } => {
             memarg_operands(mem, collector);
         }
-        &Inst::Mvc {
-            ref dst, ref src, ..
-        } => {
-            collector.reg_use(dst.base);
-            collector.reg_use(src.base);
+        Inst::Mvc { dst, src, .. } => {
+            collector.reg_use(&mut dst.base);
+            collector.reg_use(&mut src.base);
         }
-        &Inst::LoadMultiple64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::LoadMultiple64 { rt, rt2, mem, .. } => {
             memarg_operands(mem, collector);
             let first_regnum = rt.to_reg().to_real_reg().unwrap().hw_enc();
             let last_regnum = rt2.to_reg().to_real_reg().unwrap().hw_enc();
@@ -605,9 +595,7 @@ fn s390x_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandC
                 collector.reg_fixed_nonallocatable(gpr_preg(regnum));
             }
         }
-        &Inst::StoreMultiple64 {
-            rt, rt2, ref mem, ..
-        } => {
+        Inst::StoreMultiple64 { rt, rt2, mem, .. } => {
             memarg_operands(mem, collector);
             let first_regnum = rt.to_real_reg().unwrap().hw_enc();
             let last_regnum = rt2.to_real_reg().unwrap().hw_enc();
@@ -615,262 +603,257 @@ fn s390x_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandC
                 collector.reg_fixed_nonallocatable(gpr_preg(regnum));
             }
         }
-        &Inst::Mov64 { rd, rm } => {
+        Inst::Mov64 { rd, rm } => {
             collector.reg_def(rd);
             collector.reg_use(rm);
         }
-        &Inst::MovPReg { rd, ref rm } => {
+        Inst::MovPReg { rd, rm } => {
             debug_assert!([gpr_preg(0), gpr_preg(14), gpr_preg(15)].contains(rm));
             debug_assert!(rd.to_reg().is_virtual());
             collector.reg_def(rd);
         }
-        &Inst::Mov32 { rd, rm } => {
+        Inst::Mov32 { rd, rm } => {
             collector.reg_def(rd);
             collector.reg_use(rm);
         }
-        &Inst::Mov32Imm { rd, .. }
-        | &Inst::Mov32SImm16 { rd, .. }
-        | &Inst::Mov64SImm16 { rd, .. }
-        | &Inst::Mov64SImm32 { rd, .. }
-        | &Inst::Mov64UImm16Shifted { rd, .. }
-        | &Inst::Mov64UImm32Shifted { rd, .. } => {
+        Inst::Mov32Imm { rd, .. }
+        | Inst::Mov32SImm16 { rd, .. }
+        | Inst::Mov64SImm16 { rd, .. }
+        | Inst::Mov64SImm32 { rd, .. }
+        | Inst::Mov64UImm16Shifted { rd, .. }
+        | Inst::Mov64UImm32Shifted { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::CMov32 { rd, ri, rm, .. } | &Inst::CMov64 { rd, ri, rm, .. } => {
+        Inst::CMov32 { rd, ri, rm, .. } | Inst::CMov64 { rd, ri, rm, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rm);
         }
-        &Inst::CMov32SImm16 { rd, ri, .. } | &Inst::CMov64SImm16 { rd, ri, .. } => {
+        Inst::CMov32SImm16 { rd, ri, .. } | Inst::CMov64SImm16 { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::Insert64UImm16Shifted { rd, ri, .. }
-        | &Inst::Insert64UImm32Shifted { rd, ri, .. } => {
+        Inst::Insert64UImm16Shifted { rd, ri, .. } | Inst::Insert64UImm32Shifted { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::LoadAR { rd, .. } => {
+        Inst::LoadAR { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::InsertAR { rd, ri, .. } => {
+        Inst::InsertAR { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::FpuMove32 { rd, rn } | &Inst::FpuMove64 { rd, rn } => {
+        Inst::FpuMove32 { rd, rn } | Inst::FpuMove64 { rd, rn } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuCMov32 { rd, ri, rm, .. } | &Inst::FpuCMov64 { rd, ri, rm, .. } => {
+        Inst::FpuCMov32 { rd, ri, rm, .. } | Inst::FpuCMov64 { rd, ri, rm, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rm);
         }
-        &Inst::FpuRR { rd, rn, .. } => {
+        Inst::FpuRR { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::FpuRRR { rd, rn, rm, .. } => {
+        Inst::FpuRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::FpuRRRR { rd, rn, rm, ra, .. } => {
+        Inst::FpuRRRR { rd, rn, rm, ra, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_use(ra);
         }
-        &Inst::FpuCmp32 { rn, rm } | &Inst::FpuCmp64 { rn, rm } => {
+        Inst::FpuCmp32 { rn, rm } | Inst::FpuCmp64 { rn, rm } => {
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::LoadFpuConst32 { rd, .. } | &Inst::LoadFpuConst64 { rd, .. } => {
+        Inst::LoadFpuConst32 { rd, .. } | Inst::LoadFpuConst64 { rd, .. } => {
             collector.reg_def(rd);
             collector.reg_fixed_nonallocatable(gpr_preg(1));
         }
-        &Inst::FpuRound { rd, rn, .. } => {
+        Inst::FpuRound { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecRRR { rd, rn, rm, .. } => {
+        Inst::VecRRR { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecRR { rd, rn, .. } => {
+        Inst::VecRR { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecShiftRR {
+        Inst::VecShiftRR {
             rd, rn, shift_reg, ..
         } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(shift_reg);
         }
-        &Inst::VecSelect { rd, rn, rm, ra, .. } => {
+        Inst::VecSelect { rd, rn, rm, ra, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_use(ra);
         }
-        &Inst::VecPermute { rd, rn, rm, ra, .. } => {
+        Inst::VecPermute { rd, rn, rm, ra, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
             collector.reg_use(ra);
         }
-        &Inst::VecPermuteDWImm { rd, rn, rm, .. } => {
+        Inst::VecPermuteDWImm { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecIntCmp { rd, rn, rm, .. } | &Inst::VecIntCmpS { rd, rn, rm, .. } => {
+        Inst::VecIntCmp { rd, rn, rm, .. } | Inst::VecIntCmpS { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecFloatCmp { rd, rn, rm, .. } | &Inst::VecFloatCmpS { rd, rn, rm, .. } => {
+        Inst::VecFloatCmp { rd, rn, rm, .. } | Inst::VecFloatCmpS { rd, rn, rm, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecInt128SCmpHi { tmp, rn, rm, .. } | &Inst::VecInt128UCmpHi { tmp, rn, rm, .. } => {
+        Inst::VecInt128SCmpHi { tmp, rn, rm, .. } | Inst::VecInt128UCmpHi { tmp, rn, rm, .. } => {
             collector.reg_def(tmp);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecLoad { rd, ref mem, .. } => {
+        Inst::VecLoad { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadRev { rd, ref mem, .. } => {
+        Inst::VecLoadRev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadByte16Rev { rd, ref mem, .. } => {
+        Inst::VecLoadByte16Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadByte32Rev { rd, ref mem, .. } => {
+        Inst::VecLoadByte32Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadByte64Rev { rd, ref mem, .. } => {
+        Inst::VecLoadByte64Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadElt16Rev { rd, ref mem, .. } => {
+        Inst::VecLoadElt16Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadElt32Rev { rd, ref mem, .. } => {
+        Inst::VecLoadElt32Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadElt64Rev { rd, ref mem, .. } => {
+        Inst::VecLoadElt64Rev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStore { rd, ref mem, .. } => {
+        Inst::VecStore { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreRev { rd, ref mem, .. } => {
+        Inst::VecStoreRev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreByte16Rev { rd, ref mem, .. } => {
+        Inst::VecStoreByte16Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreByte32Rev { rd, ref mem, .. } => {
+        Inst::VecStoreByte32Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreByte64Rev { rd, ref mem, .. } => {
+        Inst::VecStoreByte64Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreElt16Rev { rd, ref mem, .. } => {
+        Inst::VecStoreElt16Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreElt32Rev { rd, ref mem, .. } => {
+        Inst::VecStoreElt32Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreElt64Rev { rd, ref mem, .. } => {
+        Inst::VecStoreElt64Rev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadReplicate { rd, ref mem, .. } => {
+        Inst::VecLoadReplicate { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadReplicateRev { rd, ref mem, .. } => {
+        Inst::VecLoadReplicateRev { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecMov { rd, rn } => {
+        Inst::VecMov { rd, rn } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::VecCMov { rd, ri, rm, .. } => {
+        Inst::VecCMov { rd, ri, rm, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             collector.reg_use(rm);
         }
-        &Inst::MovToVec128 { rd, rn, rm } => {
+        Inst::MovToVec128 { rd, rn, rm } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(rm);
         }
-        &Inst::VecLoadConst { rd, .. } | &Inst::VecLoadConstReplicate { rd, .. } => {
+        Inst::VecLoadConst { rd, .. } | Inst::VecLoadConstReplicate { rd, .. } => {
             collector.reg_def(rd);
             collector.reg_fixed_nonallocatable(gpr_preg(1));
         }
-        &Inst::VecImmByteMask { rd, .. } => {
+        Inst::VecImmByteMask { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecImmBitMask { rd, .. } => {
+        Inst::VecImmBitMask { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecImmReplicate { rd, .. } => {
+        Inst::VecImmReplicate { rd, .. } => {
             collector.reg_def(rd);
         }
-        &Inst::VecLoadLane {
-            rd, ri, ref mem, ..
-        } => {
+        Inst::VecLoadLane { rd, ri, mem, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadLaneUndef { rd, ref mem, .. } => {
+        Inst::VecLoadLaneUndef { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreLaneRev { rd, ref mem, .. } => {
+        Inst::VecStoreLaneRev { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadLaneRevUndef { rd, ref mem, .. } => {
+        Inst::VecLoadLaneRevUndef { rd, mem, .. } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecStoreLane { rd, ref mem, .. } => {
+        Inst::VecStoreLane { rd, mem, .. } => {
             collector.reg_use(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::VecLoadLaneRev {
-            rd, ri, ref mem, ..
-        } => {
+        Inst::VecLoadLaneRev { rd, ri, mem, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
             memarg_operands(mem, collector);
         }
-        &Inst::VecInsertLane {
+        Inst::VecInsertLane {
             rd,
             ri,
             rn,
@@ -882,92 +865,94 @@ fn s390x_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandC
             collector.reg_use(rn);
             collector.reg_use(lane_reg);
         }
-        &Inst::VecInsertLaneUndef {
+        Inst::VecInsertLaneUndef {
             rd, rn, lane_reg, ..
         } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(lane_reg);
         }
-        &Inst::VecExtractLane {
+        Inst::VecExtractLane {
             rd, rn, lane_reg, ..
         } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
             collector.reg_use(lane_reg);
         }
-        &Inst::VecInsertLaneImm { rd, ri, .. } => {
+        Inst::VecInsertLaneImm { rd, ri, .. } => {
             collector.reg_reuse_def(rd, 1);
             collector.reg_use(ri);
         }
-        &Inst::VecReplicateLane { rd, rn, .. } => {
+        Inst::VecReplicateLane { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::Extend { rd, rn, .. } => {
+        Inst::Extend { rd, rn, .. } => {
             collector.reg_def(rd);
             collector.reg_use(rn);
         }
-        &Inst::Call { link, ref info } => {
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::Call { link, info } => {
+            let CallInfo { uses, defs, .. } = &mut **info;
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             let mut clobbers = info.clobbers.clone();
             clobbers.add(link.to_reg().to_real_reg().unwrap().into());
             collector.reg_clobbers(clobbers);
         }
-        &Inst::CallInd { link, ref info } => {
-            collector.reg_use(info.rn);
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+        Inst::CallInd { link, info } => {
+            let CallIndInfo { rn, uses, defs, .. } = &mut **info;
+            collector.reg_use(rn);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
             let mut clobbers = info.clobbers.clone();
             clobbers.add(link.to_reg().to_real_reg().unwrap().into());
             collector.reg_clobbers(clobbers);
         }
-        &Inst::Args { ref args } => {
-            for arg in args {
-                collector.reg_fixed_def(arg.vreg, arg.preg);
+        Inst::Args { args } => {
+            for ArgPair { vreg, preg } in args {
+                collector.reg_fixed_def(vreg, *preg);
             }
         }
-        &Inst::Rets { ref rets } => {
-            for ret in rets {
-                collector.reg_fixed_use(ret.vreg, ret.preg);
+        Inst::Rets { rets } => {
+            for RetPair { vreg, preg } in rets {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
-        &Inst::Ret { .. } => {
+        Inst::Ret { .. } => {
             // NOTE: we explicitly don't mark the link register as used here, as the use is only in
             // the epilog where callee-save registers are restored.
         }
-        &Inst::Jump { .. } => {}
-        &Inst::IndirectBr { rn, .. } => {
+        Inst::Jump { .. } => {}
+        Inst::IndirectBr { rn, .. } => {
             collector.reg_use(rn);
         }
-        &Inst::CondBr { .. } | &Inst::OneWayCondBr { .. } => {}
-        &Inst::Nop0 | Inst::Nop2 => {}
-        &Inst::Debugtrap => {}
-        &Inst::Trap { .. } => {}
-        &Inst::TrapIf { .. } => {}
-        &Inst::JTSequence { ridx, .. } => {
+        Inst::CondBr { .. } | Inst::OneWayCondBr { .. } => {}
+        Inst::Nop0 | Inst::Nop2 => {}
+        Inst::Debugtrap => {}
+        Inst::Trap { .. } => {}
+        Inst::TrapIf { .. } => {}
+        Inst::JTSequence { ridx, .. } => {
             collector.reg_use(ridx);
             collector.reg_fixed_nonallocatable(gpr_preg(1));
         }
-        &Inst::LoadSymbolReloc { rd, .. } => {
+        Inst::LoadSymbolReloc { rd, .. } => {
             collector.reg_def(rd);
             collector.reg_fixed_nonallocatable(gpr_preg(1));
         }
-        &Inst::LoadAddr { rd, ref mem } => {
+        Inst::LoadAddr { rd, mem } => {
             collector.reg_def(rd);
             memarg_operands(mem, collector);
         }
-        &Inst::Loop { ref body, .. } => {
-            for inst in body.iter() {
+        Inst::Loop { body, .. } => {
+            for inst in body {
                 s390x_get_operands(inst, collector);
             }
 
@@ -977,10 +962,10 @@ fn s390x_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandC
             // instructions that would have emitted `reuse_def` constraints are fine.
             debug_assert!(collector.no_reuse_def());
         }
-        &Inst::CondBreak { .. } => {}
-        &Inst::VirtualSPOffsetAdj { .. } => {}
-        &Inst::Unwind { .. } => {}
-        &Inst::DummyUse { reg } => {
+        Inst::CondBreak { .. } => {}
+        Inst::VirtualSPOffsetAdj { .. } => {}
+        Inst::Unwind { .. } => {}
+        Inst::DummyUse { reg } => {
             collector.reg_use(reg);
         }
     }
@@ -994,7 +979,7 @@ impl MachInst for Inst {
     type LabelUse = LabelUse;
     const TRAP_OPCODE: &'static [u8] = &[0, 0];
 
-    fn get_operands<F: Fn(VReg) -> VReg>(&self, collector: &mut OperandCollector<'_, F>) {
+    fn get_operands<F: Fn(VReg) -> VReg>(&mut self, collector: &mut OperandCollector<'_, F>) {
         s390x_get_operands(self, collector);
     }
 
diff --git a/cranelift/codegen/src/isa/x64/inst/args.rs b/cranelift/codegen/src/isa/x64/inst/args.rs
index aa7f19ce5..82206958f 100644
--- a/cranelift/codegen/src/isa/x64/inst/args.rs
+++ b/cranelift/codegen/src/isa/x64/inst/args.rs
@@ -55,12 +55,6 @@ macro_rules! newtype_of_reg {
             }
         }
 
-        impl From<&$newtype_reg> for Reg {
-            fn from(r: &$newtype_reg) -> Self {
-                r.0
-            }
-        }
-
         impl $newtype_reg {
             /// Create this newtype from the given register, or return `None` if the register
             /// is not a valid instance of this newtype.
@@ -92,6 +86,15 @@ macro_rules! newtype_of_reg {
             }
         }
 
+        /// If you know what you're doing, you can explicitly mutably borrow the
+        /// underlying `Reg`. Don't make it point to the wrong type of register
+        /// please.
+        impl AsMut<Reg> for $newtype_reg {
+            fn as_mut(&mut self) -> &mut Reg {
+                &mut self.0
+            }
+        }
+
         /// Writable Gpr.
         pub type $newtype_writable_reg = Writable<$newtype_reg>;
 
@@ -164,7 +167,7 @@ macro_rules! newtype_of_reg {
 
                 #[allow(dead_code)] // Used by some newtypes and not others.
                 pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-                    &self,
+                    &mut self,
                     collector: &mut OperandCollector<'_, F>,
                 ) {
                     self.0.get_operands(collector);
@@ -232,7 +235,7 @@ macro_rules! newtype_of_reg {
 
                 #[allow(dead_code)] // Used by some newtypes and not others.
                 pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-                    &self,
+                    &mut self,
                     collector: &mut OperandCollector<'_, F>,
                 ) {
                     self.0.get_operands(collector);
@@ -274,6 +277,12 @@ macro_rules! newtype_of_reg {
             pub fn as_imm8_reg(&self) -> &Imm8Reg {
                 &self.0
             }
+
+            /// Borrow this newtype as its underlying `Imm8Reg`.
+            #[allow(dead_code)] // Used by some newtypes and not others.
+            pub fn as_imm8_reg_mut(&mut self) -> &mut Imm8Reg {
+                &mut self.0
+            }
         }
     };
 }
@@ -362,16 +371,16 @@ impl Amode {
 
     /// Add the registers mentioned by `self` to `collector`.
     pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
             Amode::ImmReg { base, .. } => {
                 if *base != regs::rbp() && *base != regs::rsp() {
-                    collector.reg_use(*base);
+                    collector.reg_use(base);
                 }
             }
-            &Amode::ImmRegRegShift { base, index, .. } => {
+            Amode::ImmRegRegShift { base, index, .. } => {
                 debug_assert_ne!(base.to_reg(), regs::rbp());
                 debug_assert_ne!(base.to_reg(), regs::rsp());
                 collector.reg_use(base);
@@ -387,14 +396,14 @@ impl Amode {
 
     /// Same as `get_operands`, but add the registers in the "late" phase.
     pub(crate) fn get_operands_late<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
             Amode::ImmReg { base, .. } => {
-                collector.reg_late_use(*base);
+                collector.reg_late_use(base);
             }
-            &Amode::ImmRegRegShift { base, index, .. } => {
+            Amode::ImmRegRegShift { base, index, .. } => {
                 collector.reg_late_use(base);
                 collector.reg_late_use(index);
             }
@@ -527,7 +536,7 @@ impl SyntheticAmode {
 
     /// Add the registers mentioned by `self` to `collector`.
     pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
@@ -544,7 +553,7 @@ impl SyntheticAmode {
 
     /// Same as `get_operands`, but add the register in the "late" phase.
     pub(crate) fn get_operands_late<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
@@ -678,11 +687,11 @@ impl RegMemImm {
 
     /// Add the regs mentioned by `self` to `collector`.
     pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
-            Self::Reg { reg } => collector.reg_use(*reg),
+            Self::Reg { reg } => collector.reg_use(reg),
             Self::Mem { addr } => addr.get_operands(collector),
             Self::Imm { .. } => {}
         }
@@ -788,11 +797,11 @@ impl RegMem {
     }
     /// Add the regs mentioned by `self` to `collector`.
     pub(crate) fn get_operands<F: Fn(VReg) -> VReg>(
-        &self,
+        &mut self,
         collector: &mut OperandCollector<'_, F>,
     ) {
         match self {
-            RegMem::Reg { reg } => collector.reg_use(*reg),
+            RegMem::Reg { reg } => collector.reg_use(reg),
             RegMem::Mem { addr, .. } => addr.get_operands(collector),
         }
     }
diff --git a/cranelift/codegen/src/isa/x64/inst/mod.rs b/cranelift/codegen/src/isa/x64/inst/mod.rs
index 277bafd8e..06793ae0b 100644
--- a/cranelift/codegen/src/isa/x64/inst/mod.rs
+++ b/cranelift/codegen/src/isa/x64/inst/mod.rs
@@ -1895,10 +1895,7 @@ impl fmt::Debug for Inst {
     }
 }
 
-fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCollector<'_, F>) {
-    // FIXME: remove all remaining `mod` operands here to get to pure
-    // SSA.
-
+fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &mut Inst, collector: &mut OperandCollector<'_, F>) {
     // Note: because we need to statically know the indices of each
     // reg in the operands list in order to fetch its allocation
     // later, we put the variable-operand-count bits (the RegMem,
@@ -1913,10 +1910,10 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
-        &Inst::AluConstOp { dst, .. } => collector.reg_def(dst),
+        Inst::AluConstOp { dst, .. } => collector.reg_def(dst),
         Inst::AluRM { src1_dst, src2, .. } => {
             collector.reg_use(src2);
             src1_dst.get_operands(collector);
@@ -1924,50 +1921,65 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         Inst::AluRmRVex {
             src1, src2, dst, ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
-        &Inst::Not { src, dst, .. } => {
+        Inst::Not { src, dst, .. } => {
             collector.reg_use(src);
             collector.reg_reuse_def(dst, 0);
         }
-        &Inst::Neg { src, dst, .. } => {
+        Inst::Neg { src, dst, .. } => {
             collector.reg_use(src);
             collector.reg_reuse_def(dst, 0);
         }
         Inst::Div {
+            divisor,
             dividend_lo,
             dividend_hi,
             dst_quotient,
             dst_remainder,
             ..
+        } => {
+            divisor.get_operands(collector);
+            collector.reg_fixed_use(dividend_lo, regs::rax());
+            collector.reg_fixed_use(dividend_hi, regs::rdx());
+            collector.reg_fixed_def(dst_quotient, regs::rax());
+            collector.reg_fixed_def(dst_remainder, regs::rdx());
         }
-        | Inst::CheckedSRemSeq {
+        Inst::CheckedSRemSeq {
+            divisor,
             dividend_lo,
             dividend_hi,
             dst_quotient,
             dst_remainder,
             ..
         } => {
-            match inst {
-                Inst::Div { divisor, .. } => divisor.get_operands(collector),
-                Inst::CheckedSRemSeq { divisor, .. } => collector.reg_use(divisor),
-                _ => {}
-            }
+            collector.reg_use(divisor);
             collector.reg_fixed_use(dividend_lo, regs::rax());
             collector.reg_fixed_use(dividend_hi, regs::rdx());
-            collector.reg_fixed_def(*dst_quotient, regs::rax());
-            collector.reg_fixed_def(*dst_remainder, regs::rdx());
+            collector.reg_fixed_def(dst_quotient, regs::rax());
+            collector.reg_fixed_def(dst_remainder, regs::rdx());
         }
-        Inst::Div8 { dividend, dst, .. } | Inst::CheckedSRemSeq8 { dividend, dst, .. } => {
-            match inst {
-                Inst::Div8 { divisor, .. } => divisor.get_operands(collector),
-                Inst::CheckedSRemSeq8 { divisor, .. } => collector.reg_use(divisor),
-                _ => {}
-            }
+        Inst::Div8 {
+            divisor,
+            dividend,
+            dst,
+            ..
+        } => {
+            divisor.get_operands(collector);
             collector.reg_fixed_use(dividend, regs::rax());
-            collector.reg_fixed_def(*dst, regs::rax());
+            collector.reg_fixed_def(dst, regs::rax());
+        }
+        Inst::CheckedSRemSeq8 {
+            divisor,
+            dividend,
+            dst,
+            ..
+        } => {
+            collector.reg_use(divisor);
+            collector.reg_fixed_use(dividend, regs::rax());
+            collector.reg_fixed_def(dst, regs::rax());
         }
         Inst::Mul {
             src1,
@@ -1977,29 +1989,29 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             ..
         } => {
             collector.reg_fixed_use(src1, regs::rax());
-            collector.reg_fixed_def(*dst_lo, regs::rax());
-            collector.reg_fixed_def(*dst_hi, regs::rdx());
+            collector.reg_fixed_def(dst_lo, regs::rax());
+            collector.reg_fixed_def(dst_hi, regs::rdx());
             src2.get_operands(collector);
         }
         Inst::Mul8 {
             src1, src2, dst, ..
         } => {
             collector.reg_fixed_use(src1, regs::rax());
-            collector.reg_fixed_def(*dst, regs::rax());
+            collector.reg_fixed_def(dst, regs::rax());
             src2.get_operands(collector);
         }
         Inst::IMul {
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
         Inst::IMulImm { src1, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src1.get_operands(collector);
         }
-        &Inst::SignExtendData { size, src, dst } => {
+        Inst::SignExtendData { size, src, dst } => {
             match size {
                 OperandSize::Size8 => {
                     // Note `rax` on both src and dest: 8->16 extend
@@ -2018,11 +2030,11 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         Inst::UnaryRmR { src, dst, .. }
         | Inst::UnaryRmRVex { src, dst, .. }
         | Inst::UnaryRmRImmVex { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::XmmUnaryRmR { src, dst, .. } | Inst::XmmUnaryRmRImm { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::XmmUnaryRmREvex { src, dst, .. }
@@ -2030,21 +2042,21 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         | Inst::XmmUnaryRmRUnaligned { src, dst, .. }
         | Inst::XmmUnaryRmRVex { src, dst, .. }
         | Inst::XmmUnaryRmRImmVex { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::XmmRmR {
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
         Inst::XmmRmRUnaligned {
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
         Inst::XmmRmRBlend {
@@ -2060,27 +2072,27 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             ));
             collector.reg_use(src1);
             collector.reg_fixed_use(mask, regs::xmm0());
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
         Inst::XmmRmiRVex {
             src1, src2, dst, ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
         Inst::XmmRmRImmVex {
             src1, src2, dst, ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
         Inst::XmmVexPinsr {
             src1, src2, dst, ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
@@ -2092,7 +2104,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             collector.reg_use(src2);
             src3.get_operands(collector);
         }
@@ -2103,7 +2115,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             dst,
             ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
             collector.reg_use(mask);
@@ -2118,7 +2130,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             assert_ne!(*op, Avx512Opcode::Vpermi2b);
             collector.reg_use(src1);
             src2.get_operands(collector);
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
         }
         Inst::XmmRmREvex3 {
             op,
@@ -2132,17 +2144,17 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_use(src1);
             collector.reg_use(src2);
             src3.get_operands(collector);
-            collector.reg_reuse_def(*dst, 0); // Reuse `src1`.
+            collector.reg_reuse_def(dst, 0); // Reuse `src1`.
         }
         Inst::XmmRmRImm {
             src1, src2, dst, ..
         } => {
-            collector.reg_use(*src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_use(src1);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
-        &Inst::XmmUninitializedValue { dst } => collector.reg_def(dst),
-        &Inst::XmmMinMaxSeq { lhs, rhs, dst, .. } => {
+        Inst::XmmUninitializedValue { dst } => collector.reg_def(dst),
+        Inst::XmmMinMaxSeq { lhs, rhs, dst, .. } => {
             collector.reg_use(rhs);
             collector.reg_use(lhs);
             collector.reg_reuse_def(dst, 0); // Reuse RHS.
@@ -2151,7 +2163,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0); // Reuse RHS.
+            collector.reg_reuse_def(dst, 0); // Reuse RHS.
             src2.get_operands(collector);
         }
         Inst::XmmMovRM { src, dst, .. }
@@ -2169,16 +2181,16 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
-        &Inst::Imm { dst, .. } => {
+        Inst::Imm { dst, .. } => {
             collector.reg_def(dst);
         }
-        &Inst::MovRR { src, dst, .. } => {
+        Inst::MovRR { src, dst, .. } => {
             collector.reg_use(src);
             collector.reg_def(dst);
         }
-        &Inst::MovFromPReg { dst, src } => {
+        Inst::MovFromPReg { dst, src } => {
             debug_assert!(dst.to_reg().to_reg().is_virtual());
-            collector.reg_fixed_nonallocatable(src);
+            collector.reg_fixed_nonallocatable(*src);
             collector.reg_def(dst);
         }
         Inst::MovToPReg { dst, src } => {
@@ -2186,32 +2198,32 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_use(src);
             collector.reg_fixed_nonallocatable(*dst);
         }
-        &Inst::XmmToGpr { src, dst, .. }
-        | &Inst::XmmToGprVex { src, dst, .. }
-        | &Inst::XmmToGprImm { src, dst, .. }
-        | &Inst::XmmToGprImmVex { src, dst, .. } => {
+        Inst::XmmToGpr { src, dst, .. }
+        | Inst::XmmToGprVex { src, dst, .. }
+        | Inst::XmmToGprImm { src, dst, .. }
+        | Inst::XmmToGprImmVex { src, dst, .. } => {
             collector.reg_use(src);
             collector.reg_def(dst);
         }
         Inst::GprToXmm { src, dst, .. } | Inst::GprToXmmVex { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::CvtIntToFloat {
             src1, src2, dst, ..
         } => {
             collector.reg_use(src1);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             src2.get_operands(collector);
         }
         Inst::CvtIntToFloatVex {
             src1, src2, dst, ..
         } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             collector.reg_use(src1);
             src2.get_operands(collector);
         }
-        &Inst::CvtUint64ToFloatSeq {
+        Inst::CvtUint64ToFloatSeq {
             src,
             dst,
             tmp_gpr1,
@@ -2223,7 +2235,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_early_def(tmp_gpr1);
             collector.reg_early_def(tmp_gpr2);
         }
-        &Inst::CvtFloatToSintSeq {
+        Inst::CvtFloatToSintSeq {
             src,
             dst,
             tmp_xmm,
@@ -2235,7 +2247,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_early_def(tmp_gpr);
             collector.reg_early_def(tmp_xmm);
         }
-        &Inst::CvtFloatToUintSeq {
+        Inst::CvtFloatToUintSeq {
             src,
             dst,
             tmp_gpr,
@@ -2255,19 +2267,19 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         }
 
         Inst::MovzxRmR { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::Mov64MR { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::LoadEffectiveAddress { addr: src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::MovsxRmR { src, dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
             src.get_operands(collector);
         }
         Inst::MovRM { src, dst, .. } => {
@@ -2278,8 +2290,8 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             num_bits, src, dst, ..
         } => {
             collector.reg_use(src);
-            collector.reg_reuse_def(*dst, 0);
-            if let &Imm8Reg::Reg { reg } = num_bits.as_imm8_reg() {
+            collector.reg_reuse_def(dst, 0);
+            if let Imm8Reg::Reg { reg } = num_bits.as_imm8_reg_mut() {
                 collector.reg_fixed_use(reg, regs::rcx());
             }
         }
@@ -2288,11 +2300,11 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             src2.get_operands(collector);
         }
         Inst::Setcc { dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
         }
         Inst::Bswap { src, dst, .. } => {
             collector.reg_use(src);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
         }
         Inst::Cmove {
             consequent,
@@ -2301,7 +2313,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             ..
         } => {
             collector.reg_use(alternative);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             consequent.get_operands(collector);
         }
         Inst::XmmCmove {
@@ -2311,17 +2323,17 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             ..
         } => {
             collector.reg_use(alternative);
-            collector.reg_reuse_def(*dst, 0);
+            collector.reg_reuse_def(dst, 0);
             collector.reg_use(consequent);
         }
         Inst::Push64 { src } => {
             src.get_operands(collector);
         }
         Inst::Pop64 { dst } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
         }
         Inst::StackProbeLoop { tmp, .. } => {
-            collector.reg_early_def(*tmp);
+            collector.reg_early_def(tmp);
         }
 
         Inst::CallKnown { dest, info, .. } => {
@@ -2329,64 +2341,75 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             // regalloc, so we do not need to represent its ABI to the
             // register allocator. Assert that we don't alter that
             // arrangement.
-            let info = info.as_ref().expect("CallInfo is expected in this path");
+            let CallInfo {
+                uses,
+                defs,
+                clobbers,
+                ..
+            } = &mut **info.as_mut().expect("CallInfo is expected in this path");
             debug_assert_ne!(*dest, ExternalName::LibCall(LibCall::Probestack));
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
-            collector.reg_clobbers(info.clobbers);
+            collector.reg_clobbers(*clobbers);
         }
 
         Inst::CallUnknown { info, dest, .. } => {
-            let info = info.as_ref().expect("CallInfo is expected in this path");
+            let CallInfo {
+                uses,
+                defs,
+                clobbers,
+                callee_conv,
+                ..
+            } = &mut **info.as_mut().expect("CallInfo is expected in this path");
             match dest {
-                RegMem::Reg { reg } if info.callee_conv == CallConv::Winch => {
+                RegMem::Reg { reg } if *callee_conv == CallConv::Winch => {
                     // TODO(https://github.com/bytecodealliance/regalloc2/issues/145):
                     // This shouldn't be a fixed register constraint. r10 is caller-saved, so this
                     // should be safe to use.
-                    collector.reg_fixed_use(*reg, regs::r10())
+                    collector.reg_fixed_use(reg, regs::r10())
                 }
                 _ => dest.get_operands(collector),
             }
-            for u in &info.uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
-            for d in &info.defs {
-                collector.reg_fixed_def(d.vreg, d.preg);
+            for CallRetPair { vreg, preg } in defs {
+                collector.reg_fixed_def(vreg, *preg);
             }
-            collector.reg_clobbers(info.clobbers);
+            collector.reg_clobbers(*clobbers);
         }
 
         Inst::ReturnCallKnown { callee, info } => {
-            let ReturnCallInfo { uses, tmp, .. } = &**info;
-            collector.reg_fixed_def(*tmp, regs::r11());
+            let ReturnCallInfo { uses, tmp, .. } = &mut **info;
+            collector.reg_fixed_def(tmp, regs::r11());
             // Same as in the `Inst::CallKnown` branch.
             debug_assert_ne!(*callee, ExternalName::LibCall(LibCall::Probestack));
-            for u in uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
 
         Inst::ReturnCallUnknown { callee, info } => {
-            let ReturnCallInfo { uses, tmp, .. } = &**info;
+            let ReturnCallInfo { uses, tmp, .. } = &mut **info;
 
             // TODO(https://github.com/bytecodealliance/regalloc2/issues/145):
             // This shouldn't be a fixed register constraint, but it's not clear how to
             // pick a register that won't be clobbered by the callee-save restore code
             // emitted with a return_call_indirect. r10 is caller-saved, so this should be
             // safe to use.
-            collector.reg_fixed_use(*callee, regs::r10());
+            collector.reg_fixed_use(callee, regs::r10());
 
-            collector.reg_fixed_def(*tmp, regs::r11());
-            for u in uses {
-                collector.reg_fixed_use(u.vreg, u.preg);
+            collector.reg_fixed_def(tmp, regs::r11());
+            for CallArgPair { vreg, preg } in uses {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
 
-        &Inst::JmpTableSeq {
+        Inst::JmpTableSeq {
             idx, tmp1, tmp2, ..
         } => {
             collector.reg_use(idx);
@@ -2402,7 +2425,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         }
 
         Inst::LoadExtName { dst, .. } => {
-            collector.reg_def(*dst);
+            collector.reg_def(dst);
         }
 
         Inst::LockCmpxchg {
@@ -2412,9 +2435,9 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             dst_old,
             ..
         } => {
-            collector.reg_use(*replacement);
-            collector.reg_fixed_use(*expected, regs::rax());
-            collector.reg_fixed_def(*dst_old, regs::rax());
+            collector.reg_use(replacement);
+            collector.reg_fixed_use(expected, regs::rax());
+            collector.reg_fixed_def(dst_old, regs::rax());
             mem.get_operands(collector);
         }
 
@@ -2425,25 +2448,25 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             mem,
             ..
         } => {
-            collector.reg_late_use(*operand);
-            collector.reg_early_def(*temp);
+            collector.reg_late_use(operand);
+            collector.reg_early_def(temp);
             // This `fixed_def` is needed because `CMPXCHG` always uses this
             // register implicitly.
-            collector.reg_fixed_def(*dst_old, regs::rax());
+            collector.reg_fixed_def(dst_old, regs::rax());
             mem.get_operands_late(collector)
         }
 
         Inst::Args { args } => {
-            for arg in args {
-                collector.reg_fixed_def(arg.vreg, arg.preg);
+            for ArgPair { vreg, preg } in args {
+                collector.reg_fixed_def(vreg, *preg);
             }
         }
 
         Inst::Rets { rets } => {
             // The return value(s) are live-out; we represent this
             // with register uses on the return instruction.
-            for ret in rets.iter() {
-                collector.reg_fixed_use(ret.vreg, ret.preg);
+            for RetPair { vreg, preg } in rets {
+                collector.reg_fixed_use(vreg, *preg);
             }
         }
 
@@ -2462,7 +2485,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             // No registers are used.
         }
 
-        &Inst::ElfTlsGetAddr { dst, .. } | &Inst::MachOTlsGetAddr { dst, .. } => {
+        Inst::ElfTlsGetAddr { dst, .. } | Inst::MachOTlsGetAddr { dst, .. } => {
             collector.reg_fixed_def(dst, regs::rax());
             // All caller-saves are clobbered.
             //
@@ -2475,7 +2498,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
             collector.reg_clobbers(clobbers);
         }
 
-        &Inst::CoffTlsGetAddr { dst, tmp, .. } => {
+        Inst::CoffTlsGetAddr { dst, tmp, .. } => {
             // We also use the gs register. But that register is not allocatable by the
             // register allocator, so we don't need to mark it as used here.
 
@@ -2489,7 +2512,7 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
         Inst::Unwind { .. } => {}
 
         Inst::DummyUse { reg } => {
-            collector.reg_use(*reg);
+            collector.reg_use(reg);
         }
     }
 }
@@ -2500,8 +2523,8 @@ fn x64_get_operands<F: Fn(VReg) -> VReg>(inst: &Inst, collector: &mut OperandCol
 impl MachInst for Inst {
     type ABIMachineSpec = X64ABIMachineSpec;
 
-    fn get_operands<F: Fn(VReg) -> VReg>(&self, collector: &mut OperandCollector<'_, F>) {
-        x64_get_operands(&self, collector)
+    fn get_operands<F: Fn(VReg) -> VReg>(&mut self, collector: &mut OperandCollector<'_, F>) {
+        x64_get_operands(self, collector)
     }
 
     fn is_move(&self) -> Option<(Writable<Reg>, Reg)> {
diff --git a/cranelift/codegen/src/machinst/mod.rs b/cranelift/codegen/src/machinst/mod.rs
index 10fc224cf..1055203c3 100644
--- a/cranelift/codegen/src/machinst/mod.rs
+++ b/cranelift/codegen/src/machinst/mod.rs
@@ -96,7 +96,7 @@ pub trait MachInst: Clone + Debug {
 
     /// Return the registers referenced by this machine instruction along with
     /// the modes of reference (use, def, modify).
-    fn get_operands<F: Fn(VReg) -> VReg>(&self, collector: &mut OperandCollector<'_, F>);
+    fn get_operands<F: Fn(VReg) -> VReg>(&mut self, collector: &mut OperandCollector<'_, F>);
 
     /// If this is a simple move, return the (source, destination) tuple of registers.
     fn is_move(&self) -> Option<(Writable<Reg>, Reg)>;
diff --git a/cranelift/codegen/src/machinst/reg.rs b/cranelift/codegen/src/machinst/reg.rs
index 4421a38f4..40091fede 100644
--- a/cranelift/codegen/src/machinst/reg.rs
+++ b/cranelift/codegen/src/machinst/reg.rs
@@ -96,6 +96,12 @@ impl std::fmt::Debug for Reg {
     }
 }
 
+impl AsMut<Reg> for Reg {
+    fn as_mut(&mut self) -> &mut Reg {
+        self
+    }
+}
+
 /// A real (physical) register. This corresponds to one of the target
 /// ISA's named registers and can be used as an instruction operand.
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
@@ -321,14 +327,14 @@ impl<'a, F: Fn(VReg) -> VReg> OperandCollector<'a, F> {
     /// Add an operand.
     fn add_operand(
         &mut self,
-        reg: Reg,
+        reg: &mut Reg,
         constraint: OperandConstraint,
         kind: OperandKind,
         pos: OperandPos,
     ) {
-        let vreg = (self.renamer)(reg.into());
+        reg.0 = (self.renamer)(reg.0);
         self.operands
-            .push(Operand::new(vreg, constraint, kind, pos));
+            .push(Operand::new(reg.0, constraint, kind, pos));
     }
 
     /// Finish the operand collection and return the tuple giving the
@@ -344,59 +350,58 @@ impl<'a, F: Fn(VReg) -> VReg> OperandCollector<'a, F> {
     pub fn reg_fixed_nonallocatable(&mut self, preg: PReg) {
         debug_assert!(!self.is_allocatable_preg(preg));
         // Magic VReg which does not participate in register allocation.
-        let vreg = VReg::new(VReg::MAX, preg.class());
+        let mut reg = Reg(VReg::new(VReg::MAX, preg.class()));
         let constraint = OperandConstraint::FixedReg(preg);
         // This operand won't be allocated, so kind and pos don't matter.
-        self.add_operand(Reg(vreg), constraint, OperandKind::Use, OperandPos::Early);
+        self.add_operand(&mut reg, constraint, OperandKind::Use, OperandPos::Early);
     }
 
     /// Add a register use, at the start of the instruction (`Before`
     /// position).
-    pub fn reg_use(&mut self, reg: impl Into<Reg>) {
-        self.reg_maybe_fixed(reg.into(), OperandKind::Use, OperandPos::Early);
+    pub fn reg_use(&mut self, reg: &mut impl AsMut<Reg>) {
+        self.reg_maybe_fixed(reg.as_mut(), OperandKind::Use, OperandPos::Early);
     }
 
     /// Add a register use, at the end of the instruction (`After` position).
-    pub fn reg_late_use(&mut self, reg: impl Into<Reg>) {
-        self.reg_maybe_fixed(reg.into(), OperandKind::Use, OperandPos::Late);
+    pub fn reg_late_use(&mut self, reg: &mut impl AsMut<Reg>) {
+        self.reg_maybe_fixed(reg.as_mut(), OperandKind::Use, OperandPos::Late);
     }
 
     /// Add a register def, at the end of the instruction (`After`
     /// position). Use only when this def will be written after all
     /// uses are read.
-    pub fn reg_def(&mut self, reg: Writable<impl Into<Reg>>) {
-        self.reg_maybe_fixed(reg.to_reg().into(), OperandKind::Def, OperandPos::Late);
+    pub fn reg_def(&mut self, reg: &mut Writable<impl AsMut<Reg>>) {
+        self.reg_maybe_fixed(reg.reg.as_mut(), OperandKind::Def, OperandPos::Late);
     }
 
     /// Add a register "early def", which logically occurs at the
     /// beginning of the instruction, alongside all uses. Use this
     /// when the def may be written before all uses are read; the
     /// regalloc will ensure that it does not overwrite any uses.
-    pub fn reg_early_def(&mut self, reg: Writable<impl Into<Reg>>) {
-        self.reg_maybe_fixed(reg.to_reg().into(), OperandKind::Def, OperandPos::Early);
+    pub fn reg_early_def(&mut self, reg: &mut Writable<impl AsMut<Reg>>) {
+        self.reg_maybe_fixed(reg.reg.as_mut(), OperandKind::Def, OperandPos::Early);
     }
 
     /// Add a register "fixed use", which ties a vreg to a particular
     /// RealReg at the end of the instruction.
-    pub fn reg_fixed_late_use(&mut self, reg: impl Into<Reg>, rreg: Reg) {
-        self.reg_fixed(reg.into(), rreg, OperandKind::Use, OperandPos::Late);
+    pub fn reg_fixed_late_use(&mut self, reg: &mut impl AsMut<Reg>, rreg: Reg) {
+        self.reg_fixed(reg.as_mut(), rreg, OperandKind::Use, OperandPos::Late);
     }
 
     /// Add a register "fixed use", which ties a vreg to a particular
     /// RealReg at this point.
-    pub fn reg_fixed_use(&mut self, reg: impl Into<Reg>, rreg: Reg) {
-        self.reg_fixed(reg.into(), rreg, OperandKind::Use, OperandPos::Early);
+    pub fn reg_fixed_use(&mut self, reg: &mut impl AsMut<Reg>, rreg: Reg) {
+        self.reg_fixed(reg.as_mut(), rreg, OperandKind::Use, OperandPos::Early);
     }
 
     /// Add a register "fixed def", which ties a vreg to a particular
     /// RealReg at this point.
-    pub fn reg_fixed_def(&mut self, reg: Writable<impl Into<Reg>>, rreg: Reg) {
-        let reg = reg.to_reg().into();
-        self.reg_fixed(reg, rreg, OperandKind::Def, OperandPos::Late);
+    pub fn reg_fixed_def(&mut self, reg: &mut Writable<impl AsMut<Reg>>, rreg: Reg) {
+        self.reg_fixed(reg.reg.as_mut(), rreg, OperandKind::Def, OperandPos::Late);
     }
 
     /// Add an operand tying a virtual register to a physical register.
-    fn reg_fixed(&mut self, reg: Reg, rreg: Reg, kind: OperandKind, pos: OperandPos) {
+    fn reg_fixed(&mut self, reg: &mut Reg, rreg: Reg, kind: OperandKind, pos: OperandPos) {
         debug_assert!(reg.is_virtual());
         let rreg = rreg.to_real_reg().expect("fixed reg is not a RealReg");
         debug_assert!(
@@ -408,7 +413,7 @@ impl<'a, F: Fn(VReg) -> VReg> OperandCollector<'a, F> {
     }
 
     /// Add an operand which might already be a physical register.
-    fn reg_maybe_fixed(&mut self, reg: Reg, kind: OperandKind, pos: OperandPos) {
+    fn reg_maybe_fixed(&mut self, reg: &mut Reg, kind: OperandKind, pos: OperandPos) {
         if let Some(rreg) = reg.to_real_reg() {
             self.reg_fixed_nonallocatable(rreg.into());
         } else {
@@ -420,8 +425,8 @@ impl<'a, F: Fn(VReg) -> VReg> OperandCollector<'a, F> {
     /// Add a register def that reuses an earlier use-operand's
     /// allocation. The index of that earlier operand (relative to the
     /// current instruction's start of operands) must be known.
-    pub fn reg_reuse_def(&mut self, reg: Writable<impl Into<Reg>>, idx: usize) {
-        let reg = reg.to_reg().into();
+    pub fn reg_reuse_def(&mut self, reg: &mut Writable<impl AsMut<Reg>>, idx: usize) {
+        let reg = reg.reg.as_mut();
         if let Some(rreg) = reg.to_real_reg() {
             // In some cases we see real register arguments to a reg_reuse_def
             // constraint. We assume the creator knows what they're doing
diff --git a/cranelift/codegen/src/machinst/valueregs.rs b/cranelift/codegen/src/machinst/valueregs.rs
index 52b3c8989..7c0ee3583 100644
--- a/cranelift/codegen/src/machinst/valueregs.rs
+++ b/cranelift/codegen/src/machinst/valueregs.rs
@@ -82,10 +82,16 @@ impl<R: Clone + Copy + Debug + PartialEq + Eq + InvalidSentinel> ValueRegs<R> {
         }
     }
 
-    /// Return an iterator over the registers storing this value.
+    /// Return a slice of the registers storing this value.
     pub fn regs(&self) -> &[R] {
         &self.parts[0..self.len()]
     }
+
+    /// Return a mutable slice of the registers storing this value.
+    pub fn regs_mut(&mut self) -> &mut [R] {
+        let len = self.len();
+        &mut self.parts[0..len]
+    }
 }
 
 impl<R: Clone + Copy + Debug + PartialEq + Eq + InvalidSentinel> ValueRegs<R> {
diff --git a/cranelift/codegen/src/machinst/vcode.rs b/cranelift/codegen/src/machinst/vcode.rs
index 53cc6e7ea..a3ab6d42a 100644
--- a/cranelift/codegen/src/machinst/vcode.rs
+++ b/cranelift/codegen/src/machinst/vcode.rs
@@ -510,7 +510,7 @@ impl<I: VCodeInst> VCodeBuilder<I> {
 
     fn collect_operands(&mut self) {
         let allocatable = PRegSet::from(self.vcode.machine_env());
-        for (i, insn) in self.vcode.insts.iter().enumerate() {
+        for (i, insn) in self.vcode.insts.iter_mut().enumerate() {
             // Push operands from the instruction onto the operand list.
             //
             // We rename through the vreg alias table as we collect
@@ -585,6 +585,9 @@ impl<I: VCodeInst> VCodeBuilder<I> {
 
         self.compute_preds_from_succs();
         self.vcode.debug_value_labels.sort_unstable();
+
+        // All aliases are resolved now, so remove them from the map.
+        self.vcode.vreg_aliases.clear();
         self.vcode
     }
 }
@@ -1254,13 +1257,13 @@ impl<I: VCodeInst> VCode<I> {
 
     /// Get the fact, if any, for a given VReg.
     pub fn vreg_fact(&self, vreg: VReg) -> Option<&Fact> {
-        let vreg = self.resolve_vreg_alias(vreg);
+        self.debug_assert_no_vreg_aliases(core::iter::once(vreg));
         self.facts[vreg.vreg()].as_ref()
     }
 
     /// Set the fact for a given VReg.
     pub fn set_vreg_fact(&mut self, vreg: VReg, fact: Fact) {
-        let vreg = self.resolve_vreg_alias(vreg);
+        self.debug_assert_no_vreg_aliases(core::iter::once(vreg));
         trace!("set fact on {}: {:?}", vreg, fact);
         self.facts[vreg.vreg()] = Some(fact);
     }
diff --git a/cranelift/isle/isle/src/codegen.rs b/cranelift/isle/isle/src/codegen.rs
index d5eae5a09..76267e235 100644
--- a/cranelift/isle/isle/src/codegen.rs
+++ b/cranelift/isle/isle/src/codegen.rs
@@ -2,8 +2,8 @@
 
 use crate::sema::{ExternalSig, ReturnKind, Sym, Term, TermEnv, TermId, Type, TypeEnv, TypeId};
 use crate::serialize::{Block, ControlFlow, EvalStep, MatchArm};
+use crate::stablemapset::StableSet;
 use crate::trie_again::{Binding, BindingId, Constraint, RuleSet};
-use crate::StableSet;
 use std::fmt::Write;
 
 /// Options for code generation.
diff --git a/cranelift/isle/isle/src/disjointsets.rs b/cranelift/isle/isle/src/disjointsets.rs
new file mode 100644
index 000000000..f8064b86c
--- /dev/null
+++ b/cranelift/isle/isle/src/disjointsets.rs
@@ -0,0 +1,169 @@
+//! Implementation of [`DisjointSets`], to store disjoint sets and provide efficient operations to
+//! merge sets
+
+use std::collections::HashMap;
+use std::hash::Hash;
+
+/// Stores disjoint sets and provides efficient operations to merge two sets, and to find a
+/// representative member of a set given any member of that set. In this implementation, sets always
+/// have at least two members, and can only be formed by the `merge` operation.
+#[derive(Clone, Debug, Default)]
+pub struct DisjointSets<T> {
+    parent: HashMap<T, (T, u8)>,
+}
+
+impl<T: Copy + std::fmt::Debug + Eq + Hash> DisjointSets<T> {
+    /// Find a representative member of the set containing `x`. If `x` has not been merged with any
+    /// other items using `merge`, returns `None`. This method updates the data structure to make
+    /// future queries faster, and takes amortized constant time.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// sets.merge(1, 2);
+    /// sets.merge(1, 3);
+    /// sets.merge(2, 4);
+    /// assert_eq!(sets.find_mut(3).unwrap(), sets.find_mut(4).unwrap());
+    /// assert_eq!(sets.find_mut(10), None);
+    /// ```
+    pub fn find_mut(&mut self, mut x: T) -> Option<T> {
+        while let Some(node) = self.parent.get(&x) {
+            if node.0 == x {
+                return Some(x);
+            }
+            let grandparent = self.parent[&node.0].0;
+            // Re-do the lookup but take a mutable borrow this time
+            self.parent.get_mut(&x).unwrap().0 = grandparent;
+            x = grandparent;
+        }
+        None
+    }
+
+    /// Find a representative member of the set containing `x`. If `x` has not been merged with any
+    /// other items using `merge`, returns `None`. This method does not update the data structure to
+    /// make future queries faster, so `find_mut` should be preferred.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// sets.merge(1, 2);
+    /// sets.merge(1, 3);
+    /// sets.merge(2, 4);
+    /// assert_eq!(sets.find(3).unwrap(), sets.find(4).unwrap());
+    /// assert_eq!(sets.find(10), None);
+    /// ```
+    pub fn find(&self, mut x: T) -> Option<T> {
+        while let Some(node) = self.parent.get(&x) {
+            if node.0 == x {
+                return Some(x);
+            }
+            x = node.0;
+        }
+        None
+    }
+
+    /// Merge the set containing `x` with the set containing `y`. This method takes amortized
+    /// constant time.
+    pub fn merge(&mut self, x: T, y: T) {
+        assert_ne!(x, y);
+        let mut x = if let Some(x) = self.find_mut(x) {
+            self.parent[&x]
+        } else {
+            self.parent.insert(x, (x, 0));
+            (x, 0)
+        };
+        let mut y = if let Some(y) = self.find_mut(y) {
+            self.parent[&y]
+        } else {
+            self.parent.insert(y, (y, 0));
+            (y, 0)
+        };
+
+        if x == y {
+            return;
+        }
+
+        if x.1 < y.1 {
+            std::mem::swap(&mut x, &mut y);
+        }
+
+        self.parent.get_mut(&y.0).unwrap().0 = x.0;
+        if x.1 == y.1 {
+            let x_rank = &mut self.parent.get_mut(&x.0).unwrap().1;
+            *x_rank = x_rank.saturating_add(1);
+        }
+    }
+
+    /// Returns whether the given items have both been merged into the same set. If either is not
+    /// part of any set, returns `false`.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// sets.merge(1, 2);
+    /// sets.merge(1, 3);
+    /// sets.merge(2, 4);
+    /// sets.merge(5, 6);
+    /// assert!(sets.in_same_set(2, 3));
+    /// assert!(sets.in_same_set(1, 4));
+    /// assert!(sets.in_same_set(3, 4));
+    /// assert!(!sets.in_same_set(4, 5));
+    /// ```
+    pub fn in_same_set(&self, x: T, y: T) -> bool {
+        let x = self.find(x);
+        let y = self.find(y);
+        x.zip(y).filter(|(x, y)| x == y).is_some()
+    }
+
+    /// Remove the set containing the given item, and return all members of that set. The set is
+    /// returned in sorted order. This method takes time linear in the total size of all sets.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// sets.merge(1, 2);
+    /// sets.merge(1, 3);
+    /// sets.merge(2, 4);
+    /// assert_eq!(sets.remove_set_of(4), &[1, 2, 3, 4]);
+    /// assert_eq!(sets.remove_set_of(1), &[]);
+    /// assert!(sets.is_empty());
+    /// ```
+    pub fn remove_set_of(&mut self, x: T) -> Vec<T>
+    where
+        T: Ord,
+    {
+        let mut set = Vec::new();
+        if let Some(x) = self.find_mut(x) {
+            set.extend(self.parent.keys().copied());
+            // It's important to use `find_mut` here to avoid quadratic worst-case time.
+            set.retain(|&y| self.find_mut(y).unwrap() == x);
+            for y in set.iter() {
+                self.parent.remove(y);
+            }
+            set.sort_unstable();
+        }
+        set
+    }
+
+    /// Returns true if there are no sets. This method takes constant time.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// assert!(sets.is_empty());
+    /// sets.merge(1, 2);
+    /// assert!(!sets.is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool {
+        self.parent.is_empty()
+    }
+
+    /// Returns the total number of elements in all sets. This method takes constant time.
+    ///
+    /// ```
+    /// let mut sets = cranelift_isle::disjointsets::DisjointSets::default();
+    /// sets.merge(1, 2);
+    /// assert_eq!(sets.len(), 2);
+    /// sets.merge(3, 4);
+    /// sets.merge(3, 5);
+    /// assert_eq!(sets.len(), 5);
+    /// ```
+    pub fn len(&self) -> usize {
+        self.parent.len()
+    }
+}
diff --git a/cranelift/isle/isle/src/lib.rs b/cranelift/isle/isle/src/lib.rs
index a01d5a8da..0eddcc6a9 100644
--- a/cranelift/isle/isle/src/lib.rs
+++ b/cranelift/isle/isle/src/lib.rs
@@ -1,11 +1,6 @@
 #![doc = include_str!("../README.md")]
 #![deny(missing_docs)]
 
-use std::collections::hash_map::Entry;
-use std::collections::{HashMap, HashSet};
-use std::hash::Hash;
-use std::ops::Index;
-
 macro_rules! declare_id {
     (
         $(#[$attr:meta])*
@@ -23,244 +18,10 @@ macro_rules! declare_id {
     };
 }
 
-/// A wrapper around a [HashSet] which prevents accidentally observing the non-deterministic
-/// iteration order.
-#[derive(Clone, Debug, Default)]
-pub struct StableSet<T>(HashSet<T>);
-
-impl<T> StableSet<T> {
-    fn new() -> Self {
-        StableSet(HashSet::new())
-    }
-}
-
-impl<T: Hash + Eq> StableSet<T> {
-    /// Adds a value to the set. Returns whether the value was newly inserted.
-    pub fn insert(&mut self, val: T) -> bool {
-        self.0.insert(val)
-    }
-
-    /// Returns true if the set contains a value.
-    pub fn contains(&self, val: &T) -> bool {
-        self.0.contains(val)
-    }
-}
-
-/// A wrapper around a [HashMap] which prevents accidentally observing the non-deterministic
-/// iteration order.
-#[derive(Clone, Debug)]
-pub struct StableMap<K, V>(HashMap<K, V>);
-
-impl<K, V> StableMap<K, V> {
-    fn new() -> Self {
-        StableMap(HashMap::new())
-    }
-
-    fn len(&self) -> usize {
-        self.0.len()
-    }
-}
-
-// NOTE: Can't auto-derive this
-impl<K, V> Default for StableMap<K, V> {
-    fn default() -> Self {
-        StableMap(HashMap::new())
-    }
-}
-
-impl<K: Hash + Eq, V> StableMap<K, V> {
-    fn insert(&mut self, k: K, v: V) -> Option<V> {
-        self.0.insert(k, v)
-    }
-
-    fn contains_key(&self, k: &K) -> bool {
-        self.0.contains_key(k)
-    }
-
-    fn get(&self, k: &K) -> Option<&V> {
-        self.0.get(k)
-    }
-
-    fn entry(&mut self, k: K) -> Entry<K, V> {
-        self.0.entry(k)
-    }
-}
-
-impl<K: Hash + Eq, V> Index<&K> for StableMap<K, V> {
-    type Output = V;
-
-    fn index(&self, index: &K) -> &Self::Output {
-        self.0.index(index)
-    }
-}
-
-/// Stores disjoint sets and provides efficient operations to merge two sets, and to find a
-/// representative member of a set given any member of that set. In this implementation, sets always
-/// have at least two members, and can only be formed by the `merge` operation.
-#[derive(Clone, Debug, Default)]
-pub struct DisjointSets<T> {
-    parent: HashMap<T, (T, u8)>,
-}
-
-impl<T: Copy + std::fmt::Debug + Eq + Hash> DisjointSets<T> {
-    /// Find a representative member of the set containing `x`. If `x` has not been merged with any
-    /// other items using `merge`, returns `None`. This method updates the data structure to make
-    /// future queries faster, and takes amortized constant time.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// sets.merge(1, 2);
-    /// sets.merge(1, 3);
-    /// sets.merge(2, 4);
-    /// assert_eq!(sets.find_mut(3).unwrap(), sets.find_mut(4).unwrap());
-    /// assert_eq!(sets.find_mut(10), None);
-    /// ```
-    pub fn find_mut(&mut self, mut x: T) -> Option<T> {
-        while let Some(node) = self.parent.get(&x) {
-            if node.0 == x {
-                return Some(x);
-            }
-            let grandparent = self.parent[&node.0].0;
-            // Re-do the lookup but take a mutable borrow this time
-            self.parent.get_mut(&x).unwrap().0 = grandparent;
-            x = grandparent;
-        }
-        None
-    }
-
-    /// Find a representative member of the set containing `x`. If `x` has not been merged with any
-    /// other items using `merge`, returns `None`. This method does not update the data structure to
-    /// make future queries faster, so `find_mut` should be preferred.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// sets.merge(1, 2);
-    /// sets.merge(1, 3);
-    /// sets.merge(2, 4);
-    /// assert_eq!(sets.find(3).unwrap(), sets.find(4).unwrap());
-    /// assert_eq!(sets.find(10), None);
-    /// ```
-    pub fn find(&self, mut x: T) -> Option<T> {
-        while let Some(node) = self.parent.get(&x) {
-            if node.0 == x {
-                return Some(x);
-            }
-            x = node.0;
-        }
-        None
-    }
-
-    /// Merge the set containing `x` with the set containing `y`. This method takes amortized
-    /// constant time.
-    pub fn merge(&mut self, x: T, y: T) {
-        assert_ne!(x, y);
-        let mut x = if let Some(x) = self.find_mut(x) {
-            self.parent[&x]
-        } else {
-            self.parent.insert(x, (x, 0));
-            (x, 0)
-        };
-        let mut y = if let Some(y) = self.find_mut(y) {
-            self.parent[&y]
-        } else {
-            self.parent.insert(y, (y, 0));
-            (y, 0)
-        };
-
-        if x == y {
-            return;
-        }
-
-        if x.1 < y.1 {
-            std::mem::swap(&mut x, &mut y);
-        }
-
-        self.parent.get_mut(&y.0).unwrap().0 = x.0;
-        if x.1 == y.1 {
-            let x_rank = &mut self.parent.get_mut(&x.0).unwrap().1;
-            *x_rank = x_rank.saturating_add(1);
-        }
-    }
-
-    /// Returns whether the given items have both been merged into the same set. If either is not
-    /// part of any set, returns `false`.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// sets.merge(1, 2);
-    /// sets.merge(1, 3);
-    /// sets.merge(2, 4);
-    /// sets.merge(5, 6);
-    /// assert!(sets.in_same_set(2, 3));
-    /// assert!(sets.in_same_set(1, 4));
-    /// assert!(sets.in_same_set(3, 4));
-    /// assert!(!sets.in_same_set(4, 5));
-    /// ```
-    pub fn in_same_set(&self, x: T, y: T) -> bool {
-        let x = self.find(x);
-        let y = self.find(y);
-        x.zip(y).filter(|(x, y)| x == y).is_some()
-    }
-
-    /// Remove the set containing the given item, and return all members of that set. The set is
-    /// returned in sorted order. This method takes time linear in the total size of all sets.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// sets.merge(1, 2);
-    /// sets.merge(1, 3);
-    /// sets.merge(2, 4);
-    /// assert_eq!(sets.remove_set_of(4), &[1, 2, 3, 4]);
-    /// assert_eq!(sets.remove_set_of(1), &[]);
-    /// assert!(sets.is_empty());
-    /// ```
-    pub fn remove_set_of(&mut self, x: T) -> Vec<T>
-    where
-        T: Ord,
-    {
-        let mut set = Vec::new();
-        if let Some(x) = self.find_mut(x) {
-            set.extend(self.parent.keys().copied());
-            // It's important to use `find_mut` here to avoid quadratic worst-case time.
-            set.retain(|&y| self.find_mut(y).unwrap() == x);
-            for y in set.iter() {
-                self.parent.remove(y);
-            }
-            set.sort_unstable();
-        }
-        set
-    }
-
-    /// Returns true if there are no sets. This method takes constant time.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// assert!(sets.is_empty());
-    /// sets.merge(1, 2);
-    /// assert!(!sets.is_empty());
-    /// ```
-    pub fn is_empty(&self) -> bool {
-        self.parent.is_empty()
-    }
-
-    /// Returns the total number of elements in all sets. This method takes constant time.
-    ///
-    /// ```
-    /// let mut sets = cranelift_isle::DisjointSets::default();
-    /// sets.merge(1, 2);
-    /// assert_eq!(sets.len(), 2);
-    /// sets.merge(3, 4);
-    /// sets.merge(3, 5);
-    /// assert_eq!(sets.len(), 5);
-    /// ```
-    pub fn len(&self) -> usize {
-        self.parent.len()
-    }
-}
-
 pub mod ast;
 pub mod codegen;
 pub mod compile;
+pub mod disjointsets;
 pub mod error;
 pub mod lexer;
 mod log;
@@ -268,4 +29,5 @@ pub mod overlap;
 pub mod parser;
 pub mod sema;
 pub mod serialize;
+pub mod stablemapset;
 pub mod trie_again;
diff --git a/cranelift/isle/isle/src/sema.rs b/cranelift/isle/isle/src/sema.rs
index 49bf02d7a..62b5db69b 100644
--- a/cranelift/isle/isle/src/sema.rs
+++ b/cranelift/isle/isle/src/sema.rs
@@ -17,7 +17,7 @@ use crate::ast;
 use crate::error::*;
 use crate::lexer::Pos;
 use crate::log;
-use crate::{StableMap, StableSet};
+use crate::stablemapset::{StableMap, StableSet};
 use std::collections::hash_map::Entry;
 use std::collections::BTreeMap;
 use std::collections::BTreeSet;
diff --git a/cranelift/isle/isle/src/serialize.rs b/cranelift/isle/isle/src/serialize.rs
index 34728759b..b2e13efb6 100644
--- a/cranelift/isle/isle/src/serialize.rs
+++ b/cranelift/isle/isle/src/serialize.rs
@@ -20,9 +20,9 @@
 //! it.
 use std::cmp::Reverse;
 
+use crate::disjointsets::DisjointSets;
 use crate::lexer::Pos;
 use crate::trie_again::{Binding, BindingId, Constraint, Rule, RuleSet};
-use crate::DisjointSets;
 
 /// Decomposes the rule-set into a tree of [Block]s.
 pub fn serialize(rules: &RuleSet) -> Block {
diff --git a/cranelift/isle/isle/src/stablemapset.rs b/cranelift/isle/isle/src/stablemapset.rs
new file mode 100644
index 000000000..04b5b57c0
--- /dev/null
+++ b/cranelift/isle/isle/src/stablemapset.rs
@@ -0,0 +1,79 @@
+//! Implementations of hashmap and hashset that asvoid observing non-determinism
+//! in iteration order. In a separate module so the compiler can prevent access to the internal
+//! implementation details.
+
+use std::collections::hash_map::Entry;
+use std::collections::{HashMap, HashSet};
+use std::hash::Hash;
+use std::ops::Index;
+
+/// A wrapper around a [HashSet] which prevents accidentally observing the non-deterministic
+/// iteration order.
+#[derive(Clone, Debug, Default)]
+pub struct StableSet<T>(HashSet<T>);
+
+impl<T> StableSet<T> {
+    pub(crate) fn new() -> Self {
+        StableSet(HashSet::new())
+    }
+}
+
+impl<T: Hash + Eq> StableSet<T> {
+    /// Adds a value to the set. Returns whether the value was newly inserted.
+    pub fn insert(&mut self, val: T) -> bool {
+        self.0.insert(val)
+    }
+
+    /// Returns true if the set contains a value.
+    pub fn contains(&self, val: &T) -> bool {
+        self.0.contains(val)
+    }
+}
+
+/// A wrapper around a [HashMap] which prevents accidentally observing the non-deterministic
+/// iteration order.
+#[derive(Clone, Debug)]
+pub struct StableMap<K, V>(HashMap<K, V>);
+
+impl<K, V> StableMap<K, V> {
+    pub(crate) fn new() -> Self {
+        StableMap(HashMap::new())
+    }
+
+    pub(crate) fn len(&self) -> usize {
+        self.0.len()
+    }
+}
+
+// NOTE: Can't auto-derive this
+impl<K, V> Default for StableMap<K, V> {
+    fn default() -> Self {
+        StableMap(HashMap::new())
+    }
+}
+
+impl<K: Hash + Eq, V> StableMap<K, V> {
+    pub(crate) fn insert(&mut self, k: K, v: V) -> Option<V> {
+        self.0.insert(k, v)
+    }
+
+    pub(crate) fn contains_key(&self, k: &K) -> bool {
+        self.0.contains_key(k)
+    }
+
+    pub(crate) fn get(&self, k: &K) -> Option<&V> {
+        self.0.get(k)
+    }
+
+    pub(crate) fn entry(&mut self, k: K) -> Entry<K, V> {
+        self.0.entry(k)
+    }
+}
+
+impl<K: Hash + Eq, V> Index<&K> for StableMap<K, V> {
+    type Output = V;
+
+    fn index(&self, index: &K) -> &Self::Output {
+        self.0.index(index)
+    }
+}
diff --git a/cranelift/isle/isle/src/trie_again.rs b/cranelift/isle/isle/src/trie_again.rs
index 1e846288d..b4fc37396 100644
--- a/cranelift/isle/isle/src/trie_again.rs
+++ b/cranelift/isle/isle/src/trie_again.rs
@@ -1,9 +1,10 @@
 //! A strongly-normalizing intermediate representation for ISLE rules. This representation is chosen
 //! to closely reflect the operations we can implement in Rust, to make code generation easy.
+use crate::disjointsets::DisjointSets;
 use crate::error::{Error, Span};
 use crate::lexer::Pos;
 use crate::sema;
-use crate::{DisjointSets, StableSet};
+use crate::stablemapset::StableSet;
 use std::collections::{hash_map::Entry, HashMap};
 
 /// A field index in a tuple or an enum variant.
diff --git a/crates/c-api/src/table.rs b/crates/c-api/src/table.rs
index 404121c94..69ec5a689 100644
--- a/crates/c-api/src/table.rs
+++ b/crates/c-api/src/table.rs
@@ -33,11 +33,12 @@ impl wasm_table_t {
 }
 
 fn option_wasm_ref_t_to_ref(r: Option<&wasm_ref_t>, table_ty: &TableType) -> Ref {
-    match (r.map(|r| r.r.clone()), table_ty.element().heap_type()) {
-        (None, HeapType::NoFunc | HeapType::Func | HeapType::ConcreteFunc(_)) => Ref::Func(None),
-        (None, HeapType::Extern) => Ref::Extern(None),
-        (None, HeapType::Any | HeapType::I31 | HeapType::None) => Ref::Any(None),
+    match (r.map(|r| r.r.clone()), table_ty.element().heap_type().top()) {
         (Some(r), _) => r,
+        (None, HeapType::Func) => Ref::Func(None),
+        (None, HeapType::Extern) => Ref::Extern(None),
+        (None, HeapType::Any) => Ref::Any(None),
+        (None, ty) => unreachable!("not a top type: {ty:?}"),
     }
 }
 
diff --git a/crates/cranelift/src/func_environ.rs b/crates/cranelift/src/func_environ.rs
index 090af7f10..5547b6c40 100644
--- a/crates/cranelift/src/func_environ.rs
+++ b/crates/cranelift/src/func_environ.rs
@@ -13,7 +13,7 @@ use cranelift_frontend::Variable;
 use cranelift_wasm::{
     EngineOrModuleTypeIndex, FuncIndex, FuncTranslationState, GlobalIndex, GlobalVariable, Heap,
     HeapData, HeapStyle, MemoryIndex, TableData, TableIndex, TableSize, TargetEnvironment,
-    TypeIndex, WasmHeapType, WasmResult,
+    TypeIndex, WasmHeapTopType, WasmHeapType, WasmResult,
 };
 use std::mem;
 use wasmparser::Operator;
@@ -1228,6 +1228,8 @@ impl<'a, 'func, 'module_env> Call<'a, 'func, 'module_env> {
             | WasmHeapType::Extern
             | WasmHeapType::Any
             | WasmHeapType::I31
+            | WasmHeapType::Array
+            | WasmHeapType::ConcreteArray(_)
             | WasmHeapType::None => {
                 unreachable!()
             }
@@ -1418,15 +1420,12 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         delta: ir::Value,
         init_value: ir::Value,
     ) -> WasmResult<ir::Value> {
-        let grow = match self.module.table_plans[table_index].table.wasm_ty.heap_type {
-            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                self.builtin_functions.table_grow_func_ref(&mut pos.func)
-            }
-
-            ty @ WasmHeapType::Any
-            | ty @ WasmHeapType::I31
-            | ty @ WasmHeapType::None
-            | ty @ WasmHeapType::Extern => gc::gc_ref_table_grow_builtin(ty, self, &mut pos.func)?,
+        let ty = self.module.table_plans[table_index].table.wasm_ty.heap_type;
+        let grow = if ty.is_vmgcref_type() {
+            gc::gc_ref_table_grow_builtin(ty, self, &mut pos.func)?
+        } else {
+            debug_assert_eq!(ty.top(), WasmHeapTopType::Func);
+            self.builtin_functions.table_grow_func_ref(&mut pos.func)
         };
 
         let vmctx = self.vmctx_val(&mut pos);
@@ -1448,44 +1447,43 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         let plan = &self.module.table_plans[table_index];
         self.ensure_table_exists(builder.func, table_index);
         let table_data = self.tables[table_index].as_ref().unwrap();
-        match plan.table.wasm_ty.heap_type {
-            // GC-managed types.
-            WasmHeapType::Any | WasmHeapType::Extern | WasmHeapType::None => {
+        let heap_ty = plan.table.wasm_ty.heap_type;
+        match heap_ty.top() {
+            // `i31ref`s never need barriers, and therefore don't need to go
+            // through the GC compiler.
+            WasmHeapTopType::Any if heap_ty == WasmHeapType::I31 => {
                 let (src, flags) = table_data.prepare_table_addr(
                     builder,
                     index,
                     self.pointer_type(),
                     self.isa.flags().enable_table_access_spectre_mitigation(),
                 );
-                gc::gc_compiler(self).translate_read_gc_reference(
-                    self,
-                    builder,
-                    plan.table.wasm_ty,
-                    src,
-                    flags,
-                )
+                gc::unbarriered_load_gc_ref(self, builder, WasmHeapType::I31, src, flags)
             }
 
-            // `i31ref`s never need barriers, and therefore don't need to go
-            // through the GC compiler.
-            WasmHeapType::I31 => {
+            // GC-managed types.
+            WasmHeapTopType::Any | WasmHeapTopType::Extern => {
                 let (src, flags) = table_data.prepare_table_addr(
                     builder,
                     index,
                     self.pointer_type(),
                     self.isa.flags().enable_table_access_spectre_mitigation(),
                 );
-                gc::unbarriered_load_gc_ref(self, builder, WasmHeapType::I31, src, flags)
+                gc::gc_compiler(self).translate_read_gc_reference(
+                    self,
+                    builder,
+                    plan.table.wasm_ty,
+                    src,
+                    flags,
+                )
             }
 
             // Function types.
-            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                match plan.style {
-                    TableStyle::CallerChecksSignature => {
-                        Ok(self.get_or_init_func_ref_table_elem(builder, table_index, index))
-                    }
+            WasmHeapTopType::Func => match plan.style {
+                TableStyle::CallerChecksSignature => {
+                    Ok(self.get_or_init_func_ref_table_elem(builder, table_index, index))
                 }
-            }
+            },
         }
     }
 
@@ -1500,9 +1498,22 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         let plan = &self.module.table_plans[table_index];
         self.ensure_table_exists(builder.func, table_index);
         let table_data = self.tables[table_index].as_ref().unwrap();
-        match plan.table.wasm_ty.heap_type {
+        let heap_ty = plan.table.wasm_ty.heap_type;
+        match heap_ty.top() {
+            // `i31ref`s never need GC barriers, and therefore don't need to go
+            // through the GC compiler.
+            WasmHeapTopType::Any if heap_ty == WasmHeapType::I31 => {
+                let (addr, flags) = table_data.prepare_table_addr(
+                    builder,
+                    index,
+                    self.pointer_type(),
+                    self.isa.flags().enable_table_access_spectre_mitigation(),
+                );
+                gc::unbarriered_store_gc_ref(self, builder, WasmHeapType::I31, addr, value, flags)
+            }
+
             // GC-managed types.
-            WasmHeapType::Any | WasmHeapType::Extern | WasmHeapType::None => {
+            WasmHeapTopType::Any | WasmHeapTopType::Extern => {
                 let (dst, flags) = table_data.prepare_table_addr(
                     builder,
                     index,
@@ -1519,20 +1530,8 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
                 )
             }
 
-            // `i31ref`s never need GC barriers, and therefore don't need to go
-            // through the GC compiler.
-            WasmHeapType::I31 => {
-                let (addr, flags) = table_data.prepare_table_addr(
-                    builder,
-                    index,
-                    self.pointer_type(),
-                    self.isa.flags().enable_table_access_spectre_mitigation(),
-                );
-                gc::unbarriered_store_gc_ref(self, builder, WasmHeapType::I31, addr, value, flags)
-            }
-
             // Function types.
-            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
+            WasmHeapTopType::Func => {
                 match plan.style {
                     TableStyle::CallerChecksSignature => {
                         let (elem_addr, flags) = table_data.prepare_table_addr(
@@ -1565,14 +1564,12 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         val: ir::Value,
         len: ir::Value,
     ) -> WasmResult<()> {
-        let libcall = match self.module.table_plans[table_index].table.wasm_ty.heap_type {
-            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                self.builtin_functions.table_fill_func_ref(&mut pos.func)
-            }
-            ty @ WasmHeapType::Extern
-            | ty @ WasmHeapType::Any
-            | ty @ WasmHeapType::I31
-            | ty @ WasmHeapType::None => gc::gc_ref_table_fill_builtin(ty, self, &mut pos.func)?,
+        let ty = self.module.table_plans[table_index].table.wasm_ty.heap_type;
+        let libcall = if ty.is_vmgcref_type() {
+            gc::gc_ref_table_fill_builtin(ty, self, &mut pos.func)?
+        } else {
+            debug_assert_eq!(ty.top(), WasmHeapTopType::Func);
+            self.builtin_functions.table_fill_func_ref(&mut pos.func)
         };
 
         let vmctx = self.vmctx_val(&mut pos);
@@ -1624,11 +1621,9 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         mut pos: cranelift_codegen::cursor::FuncCursor,
         ht: WasmHeapType,
     ) -> WasmResult<ir::Value> {
-        Ok(match ht {
-            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                pos.ins().iconst(self.pointer_type(), 0)
-            }
-            WasmHeapType::Extern | WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => {
+        Ok(match ht.top() {
+            WasmHeapTopType::Func => pos.ins().iconst(self.pointer_type(), 0),
+            WasmHeapTopType::Any | WasmHeapTopType::Extern => {
                 pos.ins().null(self.reference_type(ht))
             }
         })
diff --git a/crates/cranelift/src/gc/enabled.rs b/crates/cranelift/src/gc/enabled.rs
index 602a30e75..8b2487623 100644
--- a/crates/cranelift/src/gc/enabled.rs
+++ b/crates/cranelift/src/gc/enabled.rs
@@ -2,7 +2,9 @@ use super::GcCompiler;
 use crate::func_environ::FuncEnvironment;
 use cranelift_codegen::ir::{self, InstBuilder};
 use cranelift_frontend::FunctionBuilder;
-use cranelift_wasm::{TargetEnvironment, WasmHeapType, WasmRefType, WasmResult, WasmValType};
+use cranelift_wasm::{
+    TargetEnvironment, WasmHeapTopType, WasmHeapType, WasmRefType, WasmResult, WasmValType,
+};
 use wasmtime_environ::{I31_DISCRIMINANT, NON_NULL_NON_I31_MASK};
 
 /// Get the default GC compiler.
@@ -171,12 +173,9 @@ impl FuncEnvironment<'_> {
     ) -> ir::Value {
         assert!(ty.is_vmgcref_type_and_not_i31());
 
-        let might_be_i31 = match ty.heap_type {
-            WasmHeapType::Any => true,
-            WasmHeapType::Extern | WasmHeapType::None | WasmHeapType::ConcreteFunc(_) => false,
-            WasmHeapType::Func | WasmHeapType::NoFunc | WasmHeapType::I31 => {
-                unreachable!("we don't manage instances of these types with the GC")
-            }
+        let might_be_i31 = match ty.heap_type.top() {
+            WasmHeapTopType::Any => true,
+            WasmHeapTopType::Extern | WasmHeapTopType::Func => false,
         };
 
         let ptr_ty = self.pointer_type();
diff --git a/crates/cranelift/src/lib.rs b/crates/cranelift/src/lib.rs
index fdf976891..bd50bc6d2 100644
--- a/crates/cranelift/src/lib.rs
+++ b/crates/cranelift/src/lib.rs
@@ -11,7 +11,9 @@ use cranelift_codegen::{
     settings, FinalizedMachReloc, FinalizedRelocTarget, MachTrap,
 };
 use cranelift_entity::PrimaryMap;
-use cranelift_wasm::{DefinedFuncIndex, FuncIndex, WasmFuncType, WasmHeapType, WasmValType};
+use cranelift_wasm::{
+    DefinedFuncIndex, FuncIndex, WasmFuncType, WasmHeapTopType, WasmHeapType, WasmValType,
+};
 
 use target_lexicon::Architecture;
 use wasmtime_environ::{
@@ -266,15 +268,13 @@ fn wasm_call_signature(
 
 /// Returns the reference type to use for the provided wasm type.
 fn reference_type(wasm_ht: WasmHeapType, pointer_type: ir::Type) -> ir::Type {
-    match wasm_ht {
-        WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => pointer_type,
-        WasmHeapType::Extern | WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => {
-            match pointer_type {
-                ir::types::I32 => ir::types::R32,
-                ir::types::I64 => ir::types::R64,
-                _ => panic!("unsupported pointer type"),
-            }
-        }
+    match wasm_ht.top() {
+        WasmHeapTopType::Func => pointer_type,
+        WasmHeapTopType::Any | WasmHeapTopType::Extern => match pointer_type {
+            ir::types::I32 => ir::types::R32,
+            ir::types::I64 => ir::types::R64,
+            _ => panic!("unsupported pointer type"),
+        },
     }
 }
 
diff --git a/crates/environ/src/compile/module_environ.rs b/crates/environ/src/compile/module_environ.rs
index 0257d3d2d..67f53bdde 100644
--- a/crates/environ/src/compile/module_environ.rs
+++ b/crates/environ/src/compile/module_environ.rs
@@ -1195,6 +1195,8 @@ impl ModuleTranslation<'_> {
                 WasmHeapType::Extern
                 | WasmHeapType::Any
                 | WasmHeapType::I31
+                | WasmHeapType::Array
+                | WasmHeapType::ConcreteArray(_)
                 | WasmHeapType::None => break,
             }
 
diff --git a/crates/environ/src/compile/module_types.rs b/crates/environ/src/compile/module_types.rs
index c41e88da3..009adcd65 100644
--- a/crates/environ/src/compile/module_types.rs
+++ b/crates/environ/src/compile/module_types.rs
@@ -1,10 +1,9 @@
-use crate::{Module, ModuleTypes, TypeConvert, TypeIndex, WasmHeapType};
-use cranelift_entity::EntityRef;
+use crate::{EntityRef, Module, ModuleTypes, TypeConvert};
 use std::{collections::HashMap, ops::Index};
 use wasmparser::{UnpackedIndex, Validator, ValidatorId};
 use wasmtime_types::{
-    EngineOrModuleTypeIndex, ModuleInternedRecGroupIndex, ModuleInternedTypeIndex, WasmResult,
-    WasmSubType,
+    EngineOrModuleTypeIndex, ModuleInternedRecGroupIndex, ModuleInternedTypeIndex, TypeIndex,
+    WasmCompositeType, WasmHeapType, WasmResult, WasmSubType,
 };
 
 /// A type marking the start of a recursion group's definition.
@@ -105,7 +104,9 @@ impl ModuleTypesBuilder {
 
         for id in validator_types.rec_group_elements(rec_group_id) {
             let ty = &validator_types[id];
-            let wasm_ty = WasmparserTypeConverter::new(self, module).convert_sub_type(ty)?;
+            let wasm_ty = WasmparserTypeConverter::new(self, module)
+                .with_rec_group(validator_types, rec_group_id)
+                .convert_sub_type(ty)?;
             self.wasm_sub_type_in_rec_group(id, wasm_ty);
         }
 
@@ -265,12 +266,31 @@ where
 pub struct WasmparserTypeConverter<'a> {
     types: &'a ModuleTypesBuilder,
     module: &'a Module,
+    rec_group_context: Option<(
+        wasmparser::types::TypesRef<'a>,
+        wasmparser::types::RecGroupId,
+    )>,
 }
 
 impl<'a> WasmparserTypeConverter<'a> {
     /// Construct a new type converter from `wasmparser` types to Wasmtime types.
     pub fn new(types: &'a ModuleTypesBuilder, module: &'a Module) -> Self {
-        Self { types, module }
+        Self {
+            types,
+            module,
+            rec_group_context: None,
+        }
+    }
+
+    /// Configure this converter to be within the context of defining the
+    /// current rec group.
+    pub fn with_rec_group(
+        &mut self,
+        wasmparser_types: wasmparser::types::TypesRef<'a>,
+        rec_group: wasmparser::types::RecGroupId,
+    ) -> &Self {
+        self.rec_group_context = Some((wasmparser_types, rec_group));
+        self
     }
 }
 
@@ -278,14 +298,62 @@ impl TypeConvert for WasmparserTypeConverter<'_> {
     fn lookup_heap_type(&self, index: UnpackedIndex) -> WasmHeapType {
         match index {
             UnpackedIndex::Id(id) => {
-                let signature = self.types.wasmparser_to_wasmtime[&id];
-                WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::Module(signature))
+                let interned = self.types.wasmparser_to_wasmtime[&id];
+                let index = EngineOrModuleTypeIndex::Module(interned);
+
+                // If this is a forward reference to a type in this type's rec
+                // group that we haven't converted yet, then we won't have an
+                // entry in `wasm_types` yet. In this case, fallback to a
+                // different means of determining whether this is a concrete
+                // array vs struct vs func reference. In this case, we can use
+                // the validator's type context.
+                if let Some(ty) = self.types.types.get(interned) {
+                    match &ty.composite_type {
+                        WasmCompositeType::Array(_) => WasmHeapType::ConcreteArray(index),
+                        WasmCompositeType::Func(_) => WasmHeapType::ConcreteFunc(index),
+                    }
+                } else if let Some((wasmparser_types, _)) = self.rec_group_context.as_ref() {
+                    match &wasmparser_types[id].composite_type {
+                        wasmparser::CompositeType::Array(_) => WasmHeapType::ConcreteArray(index),
+                        wasmparser::CompositeType::Func(_) => WasmHeapType::ConcreteFunc(index),
+                        wasmparser::CompositeType::Struct(_) => unreachable!(),
+                    }
+                } else {
+                    panic!("forward reference to type outside of rec group?")
+                }
             }
+
             UnpackedIndex::Module(module_index) => {
                 let module_index = TypeIndex::from_u32(module_index);
-                let interned_index = self.module.types[module_index];
-                WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::Module(interned_index))
+                let interned = self.module.types[module_index];
+                let index = EngineOrModuleTypeIndex::Module(interned);
+
+                // See comment above about `wasm_types` maybe not having the
+                // converted sub type yet. However in this case we don't have a
+                // `wasmparser::types::CoreTypeId` on hand, so we have to
+                // indirectly get one by looking it up inside the current rec
+                // group.
+                if let Some(ty) = self.types.types.get(interned) {
+                    match &ty.composite_type {
+                        WasmCompositeType::Array(_) => WasmHeapType::ConcreteArray(index),
+                        WasmCompositeType::Func(_) => WasmHeapType::ConcreteFunc(index),
+                    }
+                } else if let Some((parser_types, rec_group)) = self.rec_group_context.as_ref() {
+                    let rec_group_index = interned.index() - self.types.types.len_types();
+                    let id = parser_types
+                        .rec_group_elements(*rec_group)
+                        .nth(rec_group_index)
+                        .unwrap();
+                    match &parser_types[id].composite_type {
+                        wasmparser::CompositeType::Array(_) => WasmHeapType::ConcreteArray(index),
+                        wasmparser::CompositeType::Func(_) => WasmHeapType::ConcreteFunc(index),
+                        wasmparser::CompositeType::Struct(_) => unreachable!(),
+                    }
+                } else {
+                    panic!("forward reference to type outside of rec group?")
+                }
             }
+
             UnpackedIndex::RecGroup(_) => unreachable!(),
         }
     }
diff --git a/crates/environ/src/component/types_builder.rs b/crates/environ/src/component/types_builder.rs
index e13974495..892233061 100644
--- a/crates/environ/src/component/types_builder.rs
+++ b/crates/environ/src/component/types_builder.rs
@@ -174,6 +174,7 @@ impl ComponentTypesBuilder {
         self.module_types
             .wasm_types()
             .find(|(_, ty)| match &ty.composite_type {
+                wasmtime_types::WasmCompositeType::Array(_) => false,
                 wasmtime_types::WasmCompositeType::Func(sig) => {
                     sig.params().len() == 1
                         && sig.returns().len() == 0
diff --git a/crates/environ/src/module_types.rs b/crates/environ/src/module_types.rs
index cf9eb6a28..72768d0f1 100644
--- a/crates/environ/src/module_types.rs
+++ b/crates/environ/src/module_types.rs
@@ -25,9 +25,9 @@ impl ModuleTypes {
         self.wasm_types.iter()
     }
 
-    /// Get the type at the specified index.
-    pub fn get(&self, ty: ModuleInternedTypeIndex) -> &WasmSubType {
-        &self.wasm_types[ty]
+    /// Get the type at the specified index, if it exists.
+    pub fn get(&self, ty: ModuleInternedTypeIndex) -> Option<&WasmSubType> {
+        self.wasm_types.get(ty)
     }
 
     /// Get an iterator over all recursion groups defined in this module and
diff --git a/crates/fuzzing/src/oracles/dummy.rs b/crates/fuzzing/src/oracles/dummy.rs
index 0a504c0ad..59cba7739 100644
--- a/crates/fuzzing/src/oracles/dummy.rs
+++ b/crates/fuzzing/src/oracles/dummy.rs
@@ -45,11 +45,12 @@ pub fn dummy_value(val_ty: ValType) -> Result<Val> {
         ValType::F32 => Val::F32(0),
         ValType::F64 => Val::F64(0),
         ValType::V128 => Val::V128(0.into()),
-        ValType::Ref(r) => match r.heap_type() {
+        ValType::Ref(r) => match r.heap_type().top() {
             _ if !r.is_nullable() => bail!("cannot construct a dummy value of type `{r}`"),
             HeapType::Extern => Val::null_extern_ref(),
-            HeapType::NoFunc | HeapType::Func | HeapType::ConcreteFunc(_) => Val::null_func_ref(),
-            HeapType::Any | HeapType::I31 | HeapType::None => Val::null_any_ref(),
+            HeapType::Func => Val::null_func_ref(),
+            HeapType::Any => Val::null_any_ref(),
+            ty => unreachable!("not a top type: {ty:?}"),
         },
     })
 }
diff --git a/crates/runtime/src/instance.rs b/crates/runtime/src/instance.rs
index 8dc65abfc..d9a072e46 100644
--- a/crates/runtime/src/instance.rs
+++ b/crates/runtime/src/instance.rs
@@ -25,12 +25,12 @@ use std::ptr::NonNull;
 use std::sync::atomic::AtomicU64;
 use std::sync::Arc;
 use std::{mem, ptr};
-use wasmtime_environ::WasmHeapType;
 use wasmtime_environ::{
     packed_option::ReservedValue, DataIndex, DefinedGlobalIndex, DefinedMemoryIndex,
     DefinedTableIndex, ElemIndex, EntityIndex, EntityRef, EntitySet, FuncIndex, GlobalIndex,
     HostPtr, MemoryIndex, MemoryPlan, Module, ModuleInternedTypeIndex, PrimaryMap, TableIndex,
-    TableInitialValue, TableSegmentElements, Trap, VMOffsets, VMSharedTypeIndex, VMCONTEXT_MAGIC,
+    TableInitialValue, TableSegmentElements, Trap, VMOffsets, VMSharedTypeIndex, WasmHeapTopType,
+    VMCONTEXT_MAGIC,
 };
 #[cfg(feature = "wmemcheck")]
 use wasmtime_wmemcheck::Wmemcheck;
@@ -877,8 +877,13 @@ impl Instance {
                     .and_then(|s| s.get(..len))
                     .ok_or(Trap::TableOutOfBounds)?;
                 let mut context = ConstEvalContext::new(self, &module);
-                match module.table_plans[table_index].table.wasm_ty.heap_type {
-                    WasmHeapType::Extern => table.init_gc_refs(
+                match module.table_plans[table_index]
+                    .table
+                    .wasm_ty
+                    .heap_type
+                    .top()
+                {
+                    WasmHeapTopType::Extern => table.init_gc_refs(
                         dst,
                         exprs.iter().map(|expr| unsafe {
                             let raw = const_evaluator
@@ -887,28 +892,25 @@ impl Instance {
                             VMGcRef::from_raw_u32(raw.get_externref())
                         }),
                     )?,
-                    WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => table
-                        .init_gc_refs(
-                            dst,
-                            exprs.iter().map(|expr| unsafe {
-                                let raw = const_evaluator
-                                    .eval(&mut context, expr)
-                                    .expect("const expr should be valid");
-                                VMGcRef::from_raw_u32(raw.get_anyref())
-                            }),
-                        )?,
-                    WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                        table.init_func(
-                            dst,
-                            exprs.iter().map(|expr| unsafe {
-                                const_evaluator
-                                    .eval(&mut context, expr)
-                                    .expect("const expr should be valid")
-                                    .get_funcref()
-                                    .cast()
-                            }),
-                        )?
-                    }
+                    WasmHeapTopType::Any => table.init_gc_refs(
+                        dst,
+                        exprs.iter().map(|expr| unsafe {
+                            let raw = const_evaluator
+                                .eval(&mut context, expr)
+                                .expect("const expr should be valid");
+                            VMGcRef::from_raw_u32(raw.get_anyref())
+                        }),
+                    )?,
+                    WasmHeapTopType::Func => table.init_func(
+                        dst,
+                        exprs.iter().map(|expr| unsafe {
+                            const_evaluator
+                                .eval(&mut context, expr)
+                                .expect("const expr should be valid")
+                                .get_funcref()
+                                .cast()
+                        }),
+                    )?,
                 }
             }
         }
diff --git a/crates/runtime/src/instance/allocator.rs b/crates/runtime/src/instance/allocator.rs
index f33032ecf..143b3f268 100644
--- a/crates/runtime/src/instance/allocator.rs
+++ b/crates/runtime/src/instance/allocator.rs
@@ -10,7 +10,7 @@ use std::{alloc, any::Any, mem, ptr, sync::Arc};
 use wasmtime_environ::{
     DefinedMemoryIndex, DefinedTableIndex, HostPtr, InitMemory, MemoryInitialization,
     MemoryInitializer, MemoryPlan, Module, PrimaryMap, TableInitialValue, TablePlan, TableSegment,
-    Trap, VMOffsets, WasmValType, WASM_PAGE_SIZE,
+    Trap, VMOffsets, WasmHeapTopType, WasmValType, WASM_PAGE_SIZE,
 };
 
 #[cfg(feature = "gc")]
@@ -574,8 +574,8 @@ fn initialize_tables(instance: &mut Instance, module: &Module) -> Result<()> {
                 };
                 let idx = module.table_index(table);
                 let table = unsafe { instance.get_defined_table(table).as_mut().unwrap() };
-                match module.table_plans[idx].table.wasm_ty.heap_type {
-                    wasmtime_environ::WasmHeapType::Extern => {
+                match module.table_plans[idx].table.wasm_ty.heap_type.top() {
+                    WasmHeapTopType::Extern => {
                         let gc_ref = VMGcRef::from_raw_u32(raw.get_externref());
                         let gc_store = unsafe { (*instance.store()).gc_store() };
                         let items = (0..table.size())
@@ -583,9 +583,7 @@ fn initialize_tables(instance: &mut Instance, module: &Module) -> Result<()> {
                         table.init_gc_refs(0, items)?;
                     }
 
-                    wasmtime_environ::WasmHeapType::Any
-                    | wasmtime_environ::WasmHeapType::I31
-                    | wasmtime_environ::WasmHeapType::None => {
+                    WasmHeapTopType::Any => {
                         let gc_ref = VMGcRef::from_raw_u32(raw.get_anyref());
                         let gc_store = unsafe { (*instance.store()).gc_store() };
                         let items = (0..table.size())
@@ -593,9 +591,7 @@ fn initialize_tables(instance: &mut Instance, module: &Module) -> Result<()> {
                         table.init_gc_refs(0, items)?;
                     }
 
-                    wasmtime_environ::WasmHeapType::Func
-                    | wasmtime_environ::WasmHeapType::ConcreteFunc(_)
-                    | wasmtime_environ::WasmHeapType::NoFunc => {
+                    WasmHeapTopType::Func => {
                         let funcref = raw.get_funcref().cast::<VMFuncRef>();
                         let items = (0..table.size()).map(|_| funcref);
                         table.init_func(0, items)?;
diff --git a/crates/runtime/src/table.rs b/crates/runtime/src/table.rs
index 484dfa022..20c94f64e 100644
--- a/crates/runtime/src/table.rs
+++ b/crates/runtime/src/table.rs
@@ -11,7 +11,7 @@ use sptr::Strict;
 use std::ops::Range;
 use std::ptr::{self, NonNull};
 use wasmtime_environ::{
-    TablePlan, Trap, WasmHeapType, WasmRefType, FUNCREF_INIT_BIT, FUNCREF_MASK,
+    TablePlan, Trap, WasmHeapTopType, WasmRefType, FUNCREF_INIT_BIT, FUNCREF_MASK,
 };
 
 /// An element going into or coming out of a table.
@@ -247,13 +247,9 @@ impl From<DynamicGcRefTable> for Table {
 }
 
 fn wasm_to_table_type(ty: WasmRefType) -> TableElementType {
-    match ty.heap_type {
-        WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-            TableElementType::Func
-        }
-        WasmHeapType::Extern | WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => {
-            TableElementType::GcRef
-        }
+    match ty.heap_type.top() {
+        WasmHeapTopType::Func => TableElementType::Func,
+        WasmHeapTopType::Any | WasmHeapTopType::Extern => TableElementType::GcRef,
     }
 }
 
diff --git a/crates/runtime/src/vmcontext.rs b/crates/runtime/src/vmcontext.rs
index 840512fec..718586229 100644
--- a/crates/runtime/src/vmcontext.rs
+++ b/crates/runtime/src/vmcontext.rs
@@ -13,10 +13,10 @@ use std::ptr::{self, NonNull};
 use std::sync::atomic::{AtomicUsize, Ordering};
 use std::u32;
 pub use vm_host_func_context::{VMArrayCallHostFuncContext, VMNativeCallHostFuncContext};
-use wasmtime_environ::VMSharedTypeIndex;
-use wasmtime_environ::WasmHeapType;
-use wasmtime_environ::WasmValType;
-use wasmtime_environ::{BuiltinFunctionIndex, DefinedMemoryIndex, Unsigned, VMCONTEXT_MAGIC};
+use wasmtime_environ::{
+    BuiltinFunctionIndex, DefinedMemoryIndex, Unsigned, VMSharedTypeIndex, WasmHeapTopType,
+    WasmValType, VMCONTEXT_MAGIC,
+};
 
 /// A function pointer that exposes the array calling convention.
 ///
@@ -449,16 +449,12 @@ impl VMGlobalDefinition {
             WasmValType::F32 => *global.as_f32_bits_mut() = raw.get_f32(),
             WasmValType::F64 => *global.as_f64_bits_mut() = raw.get_f64(),
             WasmValType::V128 => *global.as_u128_mut() = raw.get_v128(),
-            WasmValType::Ref(r) => match r.heap_type {
-                WasmHeapType::Extern => {
+            WasmValType::Ref(r) => match r.heap_type.top() {
+                WasmHeapTopType::Extern => {
                     global.init_gc_ref(VMGcRef::from_raw_u32(raw.get_externref()))
                 }
-                WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => {
-                    global.init_gc_ref(VMGcRef::from_raw_u32(raw.get_anyref()))
-                }
-                WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                    *global.as_func_ref_mut() = raw.get_funcref().cast()
-                }
+                WasmHeapTopType::Any => global.init_gc_ref(VMGcRef::from_raw_u32(raw.get_anyref())),
+                WasmHeapTopType::Func => *global.as_func_ref_mut() = raw.get_funcref().cast(),
             },
         }
         global
@@ -476,18 +472,16 @@ impl VMGlobalDefinition {
             WasmValType::F32 => ValRaw::f32(*self.as_f32_bits()),
             WasmValType::F64 => ValRaw::f64(*self.as_f64_bits()),
             WasmValType::V128 => ValRaw::v128(*self.as_u128()),
-            WasmValType::Ref(r) => match r.heap_type {
-                WasmHeapType::Extern => ValRaw::externref(
+            WasmValType::Ref(r) => match r.heap_type.top() {
+                WasmHeapTopType::Extern => ValRaw::externref(
                     self.as_gc_ref()
                         .map_or(0, |r| gc_store.clone_gc_ref(r).as_raw_u32()),
                 ),
-                WasmHeapType::Any | WasmHeapType::I31 | WasmHeapType::None => ValRaw::anyref(
+                WasmHeapTopType::Any => ValRaw::anyref(
                     self.as_gc_ref()
                         .map_or(0, |r| gc_store.clone_gc_ref(r).as_raw_u32()),
                 ),
-                WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
-                    ValRaw::funcref(self.as_func_ref().cast())
-                }
+                WasmHeapTopType::Func => ValRaw::funcref(self.as_func_ref().cast()),
             },
         }
     }
diff --git a/crates/types/src/lib.rs b/crates/types/src/lib.rs
index 4a2c04ca3..2ffe76d01 100644
--- a/crates/types/src/lib.rs
+++ b/crates/types/src/lib.rs
@@ -192,6 +192,7 @@ impl TypeTrace for WasmValType {
 
 impl WasmValType {
     /// Is this a type that is represented as a `VMGcRef`?
+    #[inline]
     pub fn is_vmgcref_type(&self) -> bool {
         match self {
             WasmValType::Ref(r) => r.is_vmgcref_type(),
@@ -204,6 +205,7 @@ impl WasmValType {
     ///
     /// That is, is this a a type that actually refers to an object allocated in
     /// a GC heap?
+    #[inline]
     pub fn is_vmgcref_type_and_not_i31(&self) -> bool {
         match self {
             WasmValType::Ref(r) => r.is_vmgcref_type_and_not_i31(),
@@ -246,6 +248,7 @@ impl WasmRefType {
     };
 
     /// Is this a type that is represented as a `VMGcRef`?
+    #[inline]
     pub fn is_vmgcref_type(&self) -> bool {
         self.heap_type.is_vmgcref_type()
     }
@@ -255,6 +258,7 @@ impl WasmRefType {
     ///
     /// That is, is this a a type that actually refers to an object allocated in
     /// a GC heap?
+    #[inline]
     pub fn is_vmgcref_type_and_not_i31(&self) -> bool {
         self.heap_type.is_vmgcref_type_and_not_i31()
     }
@@ -375,14 +379,29 @@ impl EngineOrModuleTypeIndex {
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
 pub enum WasmHeapType {
     Extern,
+
     Func,
     ConcreteFunc(EngineOrModuleTypeIndex),
     NoFunc,
+
     Any,
     I31,
+    Array,
+    ConcreteArray(EngineOrModuleTypeIndex),
     None,
 }
 
+impl From<WasmHeapTopType> for WasmHeapType {
+    #[inline]
+    fn from(value: WasmHeapTopType) -> Self {
+        match value {
+            WasmHeapTopType::Extern => Self::Extern,
+            WasmHeapTopType::Any => Self::Any,
+            WasmHeapTopType::Func => Self::Func,
+        }
+    }
+}
+
 impl fmt::Display for WasmHeapType {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match self {
@@ -392,6 +411,8 @@ impl fmt::Display for WasmHeapType {
             Self::NoFunc => write!(f, "nofunc"),
             Self::Any => write!(f, "any"),
             Self::I31 => write!(f, "i31"),
+            Self::Array => write!(f, "array"),
+            Self::ConcreteArray(i) => write!(f, "array {i}"),
             Self::None => write!(f, "none"),
         }
     }
@@ -403,6 +424,7 @@ impl TypeTrace for WasmHeapType {
         F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
     {
         match *self {
+            Self::ConcreteArray(i) => func(i),
             Self::ConcreteFunc(i) => func(i),
             _ => Ok(()),
         }
@@ -413,6 +435,7 @@ impl TypeTrace for WasmHeapType {
         F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
     {
         match self {
+            Self::ConcreteArray(i) => func(i),
             Self::ConcreteFunc(i) => func(i),
             _ => Ok(()),
         }
@@ -421,14 +444,15 @@ impl TypeTrace for WasmHeapType {
 
 impl WasmHeapType {
     /// Is this a type that is represented as a `VMGcRef`?
+    #[inline]
     pub fn is_vmgcref_type(&self) -> bool {
-        match self {
+        match self.top() {
             // All `t <: (ref null any)` and `t <: (ref null extern)` are
             // represented as `VMGcRef`s.
-            Self::Extern | Self::Any | Self::I31 | Self::None => true,
+            WasmHeapTopType::Any | WasmHeapTopType::Extern => true,
 
             // All `t <: (ref null func)` are not.
-            Self::Func | Self::ConcreteFunc(_) | Self::NoFunc => false,
+            WasmHeapTopType::Func => false,
         }
     }
 
@@ -437,9 +461,39 @@ impl WasmHeapType {
     ///
     /// That is, is this a a type that actually refers to an object allocated in
     /// a GC heap?
+    #[inline]
     pub fn is_vmgcref_type_and_not_i31(&self) -> bool {
         self.is_vmgcref_type() && *self != Self::I31
     }
+
+    /// Get this type's top type.
+    #[inline]
+    pub fn top(&self) -> WasmHeapTopType {
+        match self {
+            WasmHeapType::Extern => WasmHeapTopType::Extern,
+
+            WasmHeapType::Func | WasmHeapType::ConcreteFunc(_) | WasmHeapType::NoFunc => {
+                WasmHeapTopType::Func
+            }
+
+            WasmHeapType::Any
+            | WasmHeapType::I31
+            | WasmHeapType::Array
+            | WasmHeapType::ConcreteArray(_)
+            | WasmHeapType::None => WasmHeapTopType::Any,
+        }
+    }
+}
+
+/// A top heap type.
+#[derive(Debug, Clone, Copy, Eq, PartialEq)]
+pub enum WasmHeapTopType {
+    /// The common supertype of all external references.
+    Extern,
+    /// The common supertype of all internal references.
+    Any,
+    /// The common supertype of all function references.
+    Func,
 }
 
 /// WebAssembly function type -- equivalent of `wasmparser`'s FuncType.
@@ -523,12 +577,102 @@ impl WasmFuncType {
     }
 }
 
+/// Represents storage types introduced in the GC spec for array and struct fields.
+#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
+pub enum WasmStorageType {
+    /// The storage type is i8.
+    I8,
+    /// The storage type is i16.
+    I16,
+    /// The storage type is a value type.
+    Val(WasmValType),
+}
+
+impl fmt::Display for WasmStorageType {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            WasmStorageType::I8 => write!(f, "i8"),
+            WasmStorageType::I16 => write!(f, "i16"),
+            WasmStorageType::Val(v) => fmt::Display::fmt(v, f),
+        }
+    }
+}
+
+impl TypeTrace for WasmStorageType {
+    fn trace<F, E>(&self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        match self {
+            WasmStorageType::I8 | WasmStorageType::I16 => Ok(()),
+            WasmStorageType::Val(v) => v.trace(func),
+        }
+    }
+
+    fn trace_mut<F, E>(&mut self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        match self {
+            WasmStorageType::I8 | WasmStorageType::I16 => Ok(()),
+            WasmStorageType::Val(v) => v.trace_mut(func),
+        }
+    }
+}
+
+/// The type of a struct field or array element.
+#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
+pub struct WasmFieldType {
+    /// The field's element type.
+    pub element_type: WasmStorageType,
+
+    /// Whether this field can be mutated or not.
+    pub mutable: bool,
+}
+
+impl TypeTrace for WasmFieldType {
+    fn trace<F, E>(&self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        self.element_type.trace(func)
+    }
+
+    fn trace_mut<F, E>(&mut self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        self.element_type.trace_mut(func)
+    }
+}
+
+/// A concrete array type.
+#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
+pub struct WasmArrayType(pub WasmFieldType);
+
+impl TypeTrace for WasmArrayType {
+    fn trace<F, E>(&self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        self.0.trace(func)
+    }
+
+    fn trace_mut<F, E>(&mut self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        self.0.trace_mut(func)
+    }
+}
+
 /// A function, array, or struct type.
 #[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
 pub enum WasmCompositeType {
+    Array(WasmArrayType),
     Func(WasmFuncType),
     //
-    // TODO: Array and struct types.
+    // TODO: struct types.
 }
 
 impl WasmCompositeType {
@@ -541,6 +685,7 @@ impl WasmCompositeType {
     pub fn as_func(&self) -> Option<&WasmFuncType> {
         match self {
             WasmCompositeType::Func(f) => Some(f),
+            _ => None,
         }
     }
 
@@ -548,6 +693,24 @@ impl WasmCompositeType {
     pub fn unwrap_func(&self) -> &WasmFuncType {
         self.as_func().unwrap()
     }
+
+    #[inline]
+    pub fn is_array(&self) -> bool {
+        matches!(self, Self::Array(_))
+    }
+
+    #[inline]
+    pub fn as_array(&self) -> Option<&WasmArrayType> {
+        match self {
+            WasmCompositeType::Array(f) => Some(f),
+            _ => None,
+        }
+    }
+
+    #[inline]
+    pub fn unwrap_array(&self) -> &WasmArrayType {
+        self.as_array().unwrap()
+    }
 }
 
 impl TypeTrace for WasmCompositeType {
@@ -556,6 +719,7 @@ impl TypeTrace for WasmCompositeType {
         F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
     {
         match self {
+            WasmCompositeType::Array(a) => a.trace(func),
             WasmCompositeType::Func(f) => f.trace(func),
         }
     }
@@ -565,6 +729,7 @@ impl TypeTrace for WasmCompositeType {
         F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
     {
         match self {
+            WasmCompositeType::Array(a) => a.trace_mut(func),
             WasmCompositeType::Func(f) => f.trace_mut(func),
         }
     }
@@ -594,6 +759,21 @@ impl WasmSubType {
     pub fn unwrap_func(&self) -> &WasmFuncType {
         self.composite_type.unwrap_func()
     }
+
+    #[inline]
+    pub fn is_array(&self) -> bool {
+        self.composite_type.is_array()
+    }
+
+    #[inline]
+    pub fn as_array(&self) -> Option<&WasmArrayType> {
+        self.composite_type.as_array()
+    }
+
+    #[inline]
+    pub fn unwrap_array(&self) -> &WasmArrayType {
+        self.composite_type.unwrap_array()
+    }
 }
 
 impl TypeTrace for WasmSubType {
@@ -1167,11 +1347,32 @@ pub trait TypeConvert {
             wasmparser::CompositeType::Func(f) => {
                 Ok(WasmCompositeType::Func(self.convert_func_type(f)))
             }
-            wasmparser::CompositeType::Array(_) => Err(wasm_unsupported!("wasm gc: array types")),
+            wasmparser::CompositeType::Array(a) => {
+                Ok(WasmCompositeType::Array(self.convert_array_type(a)))
+            }
             wasmparser::CompositeType::Struct(_) => Err(wasm_unsupported!("wasm gc: struct types")),
         }
     }
 
+    fn convert_array_type(&self, ty: &wasmparser::ArrayType) -> WasmArrayType {
+        WasmArrayType(self.convert_field_type(&ty.0))
+    }
+
+    fn convert_field_type(&self, ty: &wasmparser::FieldType) -> WasmFieldType {
+        WasmFieldType {
+            element_type: self.convert_storage_type(&ty.element_type),
+            mutable: ty.mutable,
+        }
+    }
+
+    fn convert_storage_type(&self, ty: &wasmparser::StorageType) -> WasmStorageType {
+        match ty {
+            wasmparser::StorageType::I8 => WasmStorageType::I8,
+            wasmparser::StorageType::I16 => WasmStorageType::I16,
+            wasmparser::StorageType::Val(v) => WasmStorageType::Val(self.convert_valtype(*v)),
+        }
+    }
+
     /// Converts a wasmparser function type to a wasmtime type
     fn convert_func_type(&self, ty: &wasmparser::FuncType) -> WasmFuncType {
         let params = ty
@@ -1216,14 +1417,14 @@ pub trait TypeConvert {
             wasmparser::HeapType::Concrete(i) => self.lookup_heap_type(i),
             wasmparser::HeapType::Any => WasmHeapType::Any,
             wasmparser::HeapType::I31 => WasmHeapType::I31,
+            wasmparser::HeapType::Array => WasmHeapType::Array,
             wasmparser::HeapType::None => WasmHeapType::None,
 
             wasmparser::HeapType::Exn
             | wasmparser::HeapType::NoExn
             | wasmparser::HeapType::NoExtern
             | wasmparser::HeapType::Eq
-            | wasmparser::HeapType::Struct
-            | wasmparser::HeapType::Array => {
+            | wasmparser::HeapType::Struct => {
                 unimplemented!("unsupported heap type {ty:?}");
             }
         }
diff --git a/crates/wasmtime/Cargo.toml b/crates/wasmtime/Cargo.toml
index fccd5ba11..1916ec8c4 100644
--- a/crates/wasmtime/Cargo.toml
+++ b/crates/wasmtime/Cargo.toml
@@ -59,6 +59,7 @@ gimli = { workspace = true }
 # debugging information.
 addr2line = { version = "0.21.0", default-features = false, optional = true }
 semver = { version = "1.0.17", optional = true }
+smallvec = { workspace = true, optional = true }
 
 [target.'cfg(target_os = "windows")'.dependencies.windows-sys]
 workspace = true
@@ -175,7 +176,12 @@ coredump = ["dep:wasm-encoder", "runtime", "wasmtime-runtime/coredump"]
 debug-builtins = ["wasmtime-runtime?/debug-builtins"]
 
 # Enable support for executing compiled Wasm modules.
-runtime = ["dep:wasmtime-runtime", "dep:wasmtime-jit-icache-coherence", "dep:wasmtime-slab"]
+runtime = [
+  "dep:wasmtime-runtime",
+  "dep:wasmtime-jit-icache-coherence",
+  "dep:wasmtime-slab",
+  "dep:smallvec",
+]
 
 # Enable support for garbage collection-related things.
 #
diff --git a/crates/wasmtime/src/compile.rs b/crates/wasmtime/src/compile.rs
index 0727f6f8a..9545cbec0 100644
--- a/crates/wasmtime/src/compile.rs
+++ b/crates/wasmtime/src/compile.rs
@@ -80,7 +80,6 @@ pub(crate) fn build_artifacts<T: FinishedObject>(
 
     let compile_inputs = CompileInputs::for_module(&types, &translation, functions);
     let unlinked_compile_outputs = compile_inputs.compile(engine)?;
-    let types = types.finish();
     let (compiled_funcs, function_indices) = unlinked_compile_outputs.pre_link();
 
     // Emplace all compiled functions into the object file with any other
@@ -99,6 +98,7 @@ pub(crate) fn build_artifacts<T: FinishedObject>(
     engine.append_bti(&mut object);
 
     let (mut object, compilation_artifacts) = function_indices.link_and_append_code(
+        &types,
         object,
         engine,
         compiled_funcs,
@@ -107,6 +107,7 @@ pub(crate) fn build_artifacts<T: FinishedObject>(
     )?;
 
     let info = compilation_artifacts.unwrap_as_module_info();
+    let types = types.finish();
     object.serialize_info(&(&info, &types));
     let result = T::finish_object(object)?;
 
@@ -159,6 +160,7 @@ pub(crate) fn build_component_artifacts<'a, T: FinishedObject>(
     engine.append_bti(&mut object);
 
     let (mut object, compilation_artifacts) = function_indices.link_and_append_code(
+        types.module_types_builder(),
         object,
         engine,
         compiled_funcs,
@@ -493,19 +495,20 @@ impl<'a> CompileInputs<'a> {
         }
 
         for signature in sigs {
-            self.push_input(move |compiler| {
-                let wasm_func_ty = types[signature].unwrap_func();
-                let trampoline = compiler.compile_wasm_to_native_trampoline(wasm_func_ty)?;
-                Ok(CompileOutput {
-                    key: CompileKey::wasm_to_native_trampoline(signature),
-                    symbol: format!(
-                        "signatures[{}]::wasm_to_native_trampoline",
-                        signature.as_u32()
-                    ),
-                    function: CompiledFunction::Function(trampoline),
-                    info: None,
-                })
-            });
+            if let Some(wasm_func_ty) = types[signature].as_func() {
+                self.push_input(move |compiler| {
+                    let trampoline = compiler.compile_wasm_to_native_trampoline(wasm_func_ty)?;
+                    Ok(CompileOutput {
+                        key: CompileKey::wasm_to_native_trampoline(signature),
+                        symbol: format!(
+                            "signatures[{}]::wasm_to_native_trampoline",
+                            signature.as_u32()
+                        ),
+                        function: CompiledFunction::Function(trampoline),
+                        info: None,
+                    })
+                });
+            }
         }
     }
 
@@ -651,6 +654,7 @@ impl FunctionIndices {
     /// them to the given ELF file.
     fn link_and_append_code<'a>(
         mut self,
+        types: &ModuleTypesBuilder,
         mut obj: object::write::Object<'static>,
         engine: &'a Engine,
         compiled_funcs: Vec<(String, Box<dyn Any + Send>)>,
@@ -839,6 +843,7 @@ impl FunctionIndices {
                     .types
                     .iter()
                     .map(|(_, ty)| *ty)
+                    .filter(|idx| types[*idx].is_func())
                     .collect::<BTreeSet<_>>();
                 let wasm_to_native_trampolines = unique_and_sorted_sigs
                     .iter()
diff --git a/crates/wasmtime/src/runtime/coredump.rs b/crates/wasmtime/src/runtime/coredump.rs
index ee98659fd..0ebaf5d41 100644
--- a/crates/wasmtime/src/runtime/coredump.rs
+++ b/crates/wasmtime/src/runtime/coredump.rs
@@ -176,19 +176,17 @@ impl WasmCoreDump {
                     // reference types. This lets us avoid needing to figure out
                     // what a concrete type reference's index is in the local
                     // core dump index space.
-                    ValType::Ref(r) => match r.heap_type() {
+                    ValType::Ref(r) => match r.heap_type().top() {
                         HeapType::Extern => wasm_encoder::ValType::EXTERNREF,
 
-                        HeapType::Func | HeapType::ConcreteFunc(_) | HeapType::NoFunc => {
-                            wasm_encoder::ValType::FUNCREF
-                        }
+                        HeapType::Func => wasm_encoder::ValType::FUNCREF,
 
-                        HeapType::Any | HeapType::I31 | HeapType::None => {
-                            wasm_encoder::ValType::Ref(wasm_encoder::RefType {
-                                nullable: true,
-                                heap_type: wasm_encoder::HeapType::Any,
-                            })
-                        }
+                        HeapType::Any => wasm_encoder::ValType::Ref(wasm_encoder::RefType {
+                            nullable: true,
+                            heap_type: wasm_encoder::HeapType::Any,
+                        }),
+
+                        ty => unreachable!("not a top type: {ty:?}"),
                     },
                 };
                 let init = match g.get(&mut store) {
diff --git a/crates/wasmtime/src/runtime/externals/global.rs b/crates/wasmtime/src/runtime/externals/global.rs
index 2af59fff7..f2dbab34e 100644
--- a/crates/wasmtime/src/runtime/externals/global.rs
+++ b/crates/wasmtime/src/runtime/externals/global.rs
@@ -133,13 +133,18 @@ impl Global {
                                 .into(),
                         ),
 
-                        HeapType::Any | HeapType::I31 | HeapType::None => definition
+                        HeapType::Any
+                        | HeapType::I31
+                        | HeapType::Array
+                        | HeapType::ConcreteArray(_) => definition
                             .as_gc_ref()
                             .map(|r| {
                                 let r = store.unwrap_gc_store_mut().clone_gc_ref(r);
                                 AnyRef::from_cloned_gc_ref(&mut store, r)
                             })
                             .into(),
+
+                        HeapType::None => Ref::Any(None),
                     };
                     debug_assert!(
                         ref_ty.is_nullable() || !reference.is_null(),
diff --git a/crates/wasmtime/src/runtime/externals/table.rs b/crates/wasmtime/src/runtime/externals/table.rs
index 81b386f76..64674ce6a 100644
--- a/crates/wasmtime/src/runtime/externals/table.rs
+++ b/crates/wasmtime/src/runtime/externals/table.rs
@@ -167,7 +167,7 @@ impl Table {
                 }
 
                 runtime::TableElement::GcRef(None) => {
-                    match self._ty(&store).element().heap_type().top(store.engine()) {
+                    match self._ty(&store).element().heap_type().top() {
                         HeapType::Any => Some(Ref::Any(None)),
                         HeapType::Extern => Some(Ref::Extern(None)),
                         HeapType::Func => {
@@ -179,7 +179,7 @@ impl Table {
 
                 #[cfg_attr(not(feature = "gc"), allow(unreachable_code, unused_variables))]
                 runtime::TableElement::GcRef(Some(x)) => {
-                    match self._ty(&store).element().heap_type().top(store.engine()) {
+                    match self._ty(&store).element().heap_type().top() {
                         HeapType::Any => {
                             let x = AnyRef::from_cloned_gc_ref(&mut store, x);
                             Some(x.into())
diff --git a/crates/wasmtime/src/runtime/func/typed.rs b/crates/wasmtime/src/runtime/func/typed.rs
index e7ae95713..9c4912c05 100644
--- a/crates/wasmtime/src/runtime/func/typed.rs
+++ b/crates/wasmtime/src/runtime/func/typed.rs
@@ -299,8 +299,8 @@ pub unsafe trait WasmTy: Send {
                 (Some(expected_ref), Some(actual_ref)) if actual_ref.heap_type().is_concrete() => {
                     expected_ref
                         .heap_type()
-                        .top(engine)
-                        .ensure_matches(engine, &actual_ref.heap_type().top(engine))
+                        .top()
+                        .ensure_matches(engine, &actual_ref.heap_type().top())
                 }
                 _ => expected.ensure_matches(engine, &actual),
             },
@@ -327,7 +327,7 @@ pub unsafe trait WasmTy: Send {
         &self,
         store: &StoreOpaque,
         nullable: bool,
-        actual: &FuncType,
+        actual: &HeapType,
     ) -> Result<()>;
 
     // Is this an externref?
@@ -391,7 +391,7 @@ macro_rules! integers {
                 true
             }
             #[inline]
-            fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+            fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
                 unreachable!()
             }
             #[inline]
@@ -439,7 +439,7 @@ macro_rules! floats {
                 true
             }
             #[inline]
-            fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+            fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
                 unreachable!()
             }
             #[inline]
@@ -486,7 +486,7 @@ unsafe impl WasmTy for NoFunc {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         match self._inner {}
     }
 
@@ -534,13 +534,13 @@ unsafe impl WasmTy for Option<NoFunc> {
         &self,
         _: &StoreOpaque,
         nullable: bool,
-        func_ty: &FuncType,
+        ty: &HeapType,
     ) -> Result<()> {
         if nullable {
             // `(ref null nofunc) <: (ref null $f)` for all function types `$f`.
             Ok(())
         } else {
-            bail!("argument type mismatch: expected (ref {func_ty}), found null reference")
+            bail!("argument type mismatch: expected non-nullable (ref {ty}), found null reference")
         }
     }
 
@@ -588,9 +588,10 @@ unsafe impl WasmTy for Func {
         &self,
         store: &StoreOpaque,
         _nullable: bool,
-        actual: &FuncType,
+        expected: &HeapType,
     ) -> Result<()> {
-        self.ensure_matches_ty(store, actual)
+        let expected = expected.unwrap_concrete_func();
+        self.ensure_matches_ty(store, expected)
             .context("argument type mismatch for reference to concrete type")
     }
 
@@ -643,15 +644,16 @@ unsafe impl WasmTy for Option<Func> {
         &self,
         store: &StoreOpaque,
         nullable: bool,
-        func_ty: &FuncType,
+        expected: &HeapType,
     ) -> Result<()> {
         if let Some(f) = self {
-            f.ensure_matches_ty(store, func_ty)
+            let expected = expected.unwrap_concrete_func();
+            f.ensure_matches_ty(store, expected)
                 .context("argument type mismatch for reference to concrete type")
         } else if nullable {
             Ok(())
         } else {
-            bail!("argument type mismatch: expected (ref {func_ty}), found null reference")
+            bail!("argument type mismatch: expected non-nullable (ref {expected}), found null reference")
         }
     }
 
@@ -808,10 +810,11 @@ macro_rules! impl_wasm_params {
                     }
 
                     if $t::valtype().is_ref() {
-                        let p = _func_ty.param(_i).unwrap();
-                        let r = p.unwrap_ref();
-                        if let Some(c) = r.heap_type().as_concrete() {
-                            $t.dynamic_concrete_type_check(_store, r.is_nullable(), c)?;
+                        let param_ty = _func_ty.param(_i).unwrap();
+                        let ref_ty = param_ty.unwrap_ref();
+                        let heap_ty = ref_ty.heap_type();
+                        if heap_ty.is_concrete() {
+                            $t.dynamic_concrete_type_check(_store, ref_ty.is_nullable(), heap_ty)?;
                         }
                     }
 
diff --git a/crates/wasmtime/src/runtime/gc/enabled/anyref.rs b/crates/wasmtime/src/runtime/gc/enabled/anyref.rs
index 87593f99f..71c57ae61 100644
--- a/crates/wasmtime/src/runtime/gc/enabled/anyref.rs
+++ b/crates/wasmtime/src/runtime/gc/enabled/anyref.rs
@@ -2,8 +2,8 @@
 
 use crate::{
     store::{AutoAssertNoGc, StoreOpaque},
-    AsContext, AsContextMut, FuncType, GcRefImpl, GcRootIndex, HeapType, ManuallyRooted, RefType,
-    Result, RootSet, Rooted, ValRaw, ValType, WasmTy, I31,
+    AsContext, AsContextMut, GcRefImpl, GcRootIndex, HeapType, ManuallyRooted, RefType, Result,
+    RootSet, Rooted, ValRaw, ValType, WasmTy, I31,
 };
 use std::num::NonZeroU64;
 use wasmtime_runtime::VMGcRef;
@@ -259,7 +259,7 @@ unsafe impl WasmTy for Rooted<AnyRef> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -314,7 +314,7 @@ unsafe impl WasmTy for Option<Rooted<AnyRef>> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -366,7 +366,7 @@ unsafe impl WasmTy for ManuallyRooted<AnyRef> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -426,7 +426,7 @@ unsafe impl WasmTy for Option<ManuallyRooted<AnyRef>> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
diff --git a/crates/wasmtime/src/runtime/gc/enabled/externref.rs b/crates/wasmtime/src/runtime/gc/enabled/externref.rs
index ebcfe62c7..1fd024475 100644
--- a/crates/wasmtime/src/runtime/gc/enabled/externref.rs
+++ b/crates/wasmtime/src/runtime/gc/enabled/externref.rs
@@ -2,8 +2,8 @@
 
 use crate::{
     store::{AutoAssertNoGc, StoreOpaque},
-    AsContextMut, FuncType, GcHeapOutOfMemory, GcRefImpl, GcRootIndex, HeapType, ManuallyRooted,
-    RefType, Result, RootSet, Rooted, StoreContext, StoreContextMut, ValRaw, ValType, WasmTy,
+    AsContextMut, GcHeapOutOfMemory, GcRefImpl, GcRootIndex, HeapType, ManuallyRooted, RefType,
+    Result, RootSet, Rooted, StoreContext, StoreContextMut, ValRaw, ValType, WasmTy,
 };
 use anyhow::Context;
 use std::any::Any;
@@ -431,7 +431,7 @@ unsafe impl WasmTy for Rooted<ExternRef> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -486,7 +486,7 @@ unsafe impl WasmTy for Option<Rooted<ExternRef>> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -538,7 +538,7 @@ unsafe impl WasmTy for ManuallyRooted<ExternRef> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
@@ -598,7 +598,7 @@ unsafe impl WasmTy for Option<ManuallyRooted<ExternRef>> {
     }
 
     #[inline]
-    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &FuncType) -> Result<()> {
+    fn dynamic_concrete_type_check(&self, _: &StoreOpaque, _: bool, _: &HeapType) -> Result<()> {
         unreachable!()
     }
 
diff --git a/crates/wasmtime/src/runtime/gc/enabled/i31.rs b/crates/wasmtime/src/runtime/gc/enabled/i31.rs
index 80c73c8f0..e67e9d1ee 100644
--- a/crates/wasmtime/src/runtime/gc/enabled/i31.rs
+++ b/crates/wasmtime/src/runtime/gc/enabled/i31.rs
@@ -6,7 +6,7 @@
 
 use crate::{
     store::{AutoAssertNoGc, StoreOpaque},
-    FuncType, HeapType, RefType, Result, ValType, WasmTy,
+    HeapType, RefType, Result, ValType, WasmTy,
 };
 use wasmtime_runtime::{VMGcRef, ValRaw};
 
@@ -237,7 +237,7 @@ unsafe impl WasmTy for I31 {
         &self,
         _store: &StoreOpaque,
         _nullable: bool,
-        _actual: &FuncType,
+        _actual: &HeapType,
     ) -> Result<()> {
         unreachable!()
     }
@@ -300,7 +300,7 @@ unsafe impl WasmTy for Option<I31> {
         &self,
         _store: &StoreOpaque,
         _nullable: bool,
-        _actual: &FuncType,
+        _actual: &HeapType,
     ) -> Result<()> {
         unreachable!()
     }
diff --git a/crates/wasmtime/src/runtime/linker.rs b/crates/wasmtime/src/runtime/linker.rs
index 3a93f9c3c..08389207c 100644
--- a/crates/wasmtime/src/runtime/linker.rs
+++ b/crates/wasmtime/src/runtime/linker.rs
@@ -343,14 +343,11 @@ impl<T> Linker<T> {
                                     ValType::V128 => Val::V128(0_u128.into()),
                                     ValType::Ref(r) => {
                                         debug_assert!(r.is_nullable());
-                                        match r.heap_type() {
-                                            HeapType::Func
-                                            | HeapType::ConcreteFunc(_)
-                                            | HeapType::NoFunc => Val::null_func_ref(),
+                                        match r.heap_type().top() {
+                                            HeapType::Func => Val::null_func_ref(),
                                             HeapType::Extern => Val::null_extern_ref(),
-                                            HeapType::Any | HeapType::I31 | HeapType::None => {
-                                                Val::null_any_ref()
-                                            }
+                                            HeapType::Any => Val::null_any_ref(),
+                                            ty => unreachable!("not a top type: {ty:?}"),
                                         }
                                     }
                                 };
diff --git a/crates/wasmtime/src/runtime/type_registry.rs b/crates/wasmtime/src/runtime/type_registry.rs
index 729570961..a41d34e69 100644
--- a/crates/wasmtime/src/runtime/type_registry.rs
+++ b/crates/wasmtime/src/runtime/type_registry.rs
@@ -463,7 +463,7 @@ impl TypeRegistryInner {
             let entry = self.register_rec_group(
                 &map,
                 module_group.clone(),
-                iter_entity_range(module_group.clone()).map(|ty| types.get(ty).clone()),
+                iter_entity_range(module_group.clone()).map(|ty| types[ty].clone()),
             );
 
             for (module_ty, engine_ty) in
diff --git a/crates/wasmtime/src/runtime/types.rs b/crates/wasmtime/src/runtime/types.rs
index 1e306acbb..ec6bd9110 100644
--- a/crates/wasmtime/src/runtime/types.rs
+++ b/crates/wasmtime/src/runtime/types.rs
@@ -2,8 +2,8 @@ use anyhow::{bail, Result};
 use std::fmt::{self, Display};
 use wasmtime_environ::{
     EngineOrModuleTypeIndex, EntityType, Global, Memory, ModuleTypes, Table, TypeTrace,
-    VMSharedTypeIndex, WasmCompositeType, WasmFuncType, WasmHeapType, WasmRefType, WasmSubType,
-    WasmValType,
+    VMSharedTypeIndex, WasmArrayType, WasmCompositeType, WasmFieldType, WasmFuncType, WasmHeapType,
+    WasmRefType, WasmStorageType, WasmSubType, WasmValType,
 };
 
 use crate::{type_registry::RegisteredType, Engine};
@@ -363,6 +363,7 @@ impl RefType {
     }
 
     /// The heap type that this is a reference to.
+    #[inline]
     pub fn heap_type(&self) -> &HeapType {
         &self.heap_type
     }
@@ -424,7 +425,7 @@ impl RefType {
     }
 
     pub(crate) fn is_gc_heap_type(&self) -> bool {
-        self.heap_type().is_gc_heap_type()
+        self.heap_type().is_vmgcref_type_and_points_to_object()
     }
 }
 
@@ -440,22 +441,22 @@ impl RefType {
 /// between types, you can use the [`HeapType::eq`] method.
 #[derive(Debug, Clone, Hash)]
 pub enum HeapType {
-    /// The `extern` heap type represents external host data.
+    /// The abstract `extern` heap type represents external host data.
     Extern,
 
-    /// The `func` heap type represents a reference to any kind of function.
+    /// The abstract `func` heap type represents a reference to any kind of
+    /// function.
     ///
     /// This is the top type for the function references type hierarchy, and is
     /// therefore a supertype of every function reference.
     Func,
 
-    /// The concrete heap type represents a reference to a function of a
-    /// specific, concrete type.
+    /// A reference to a function of a specific, concrete type.
     ///
-    /// This is a subtype of `func` and a supertype of `nofunc`.
+    /// These are subtypes of `func` and supertypes of `nofunc`.
     ConcreteFunc(FuncType),
 
-    /// The `nofunc` heap type represents the null function reference.
+    /// The abstract `nofunc` heap type represents the null function reference.
     ///
     /// This is the bottom type for the function references type hierarchy, and
     /// therefore `nofunc` is a subtype of all function reference types.
@@ -469,8 +470,26 @@ pub enum HeapType {
     Any,
 
     /// The `i31` heap type represents unboxed 31-bit integers.
+    ///
+    /// This is a subtype of `any` and a supertype of `none`.
     I31,
 
+    /// The abstract `array` heap type represents a reference to any kind of array.
+    ///
+    /// This is a subtype of `any` and a supertype of all concrete array types,
+    /// as well as a supertype of the abstract `none` heap type.
+    //
+    // TODO: add docs for subtype of `eq` once we add that heap type
+    Array,
+
+    /// A reference to an array of a specific, concrete type.
+    ///
+    /// These are subtypes of the `array` heap type (therefore also a subtype of
+    /// `any`) and supertypes of the `none` heap type.
+    //
+    // TODO: add docs for subtype of `eq` once we add that heap type
+    ConcreteArray(ArrayType),
+
     /// The abstract `none` heap type represents the null internal reference.
     ///
     /// This is the bottom type for the internal type hierarchy, and therefore
@@ -486,8 +505,10 @@ impl Display for HeapType {
             HeapType::NoFunc => write!(f, "nofunc"),
             HeapType::Any => write!(f, "any"),
             HeapType::I31 => write!(f, "i31"),
+            HeapType::Array => write!(f, "array"),
             HeapType::None => write!(f, "none"),
-            HeapType::ConcreteFunc(ty) => write!(f, "(concrete {:?})", ty.type_index()),
+            HeapType::ConcreteFunc(ty) => write!(f, "(concrete func {:?})", ty.type_index()),
+            HeapType::ConcreteArray(ty) => write!(f, "(concrete array {:?})", ty.type_index()),
         }
     }
 }
@@ -499,6 +520,13 @@ impl From<FuncType> for HeapType {
     }
 }
 
+impl From<ArrayType> for HeapType {
+    #[inline]
+    fn from(a: ArrayType) -> Self {
+        HeapType::ConcreteArray(a)
+    }
+}
+
 impl HeapType {
     /// Is this the abstract `extern` heap type?
     pub fn is_extern(&self) -> bool {
@@ -540,40 +568,76 @@ impl HeapType {
     /// Is this a concrete, user-defined heap type?
     ///
     /// Types that are not concrete, user-defined types are abstract types.
+    #[inline]
     pub fn is_concrete(&self) -> bool {
+        matches!(self, HeapType::ConcreteFunc(_) | HeapType::ConcreteArray(_))
+    }
+
+    /// Is this a concrete, user-defined function type?
+    pub fn is_concrete_func(&self) -> bool {
         matches!(self, HeapType::ConcreteFunc(_))
     }
 
-    /// Get the underlying concrete, user-defined type, if any.
+    /// Get the underlying concrete, user-defined function type, if any.
     ///
-    /// Returns `None` for abstract types.
-    pub fn as_concrete(&self) -> Option<&FuncType> {
+    /// Returns `None` if this is not a concrete function type.
+    pub fn as_concrete_func(&self) -> Option<&FuncType> {
         match self {
             HeapType::ConcreteFunc(f) => Some(f),
             _ => None,
         }
     }
 
-    /// Get the underlying concrete, user-defined type, panicking if this heap
-    /// type is not concrete.
-    pub fn unwrap_concrete(&self) -> &FuncType {
-        self.as_concrete()
-            .expect("HeapType::unwrap_concrete on non-concrete heap type")
+    /// Get the underlying concrete, user-defined type, panicking if this is not
+    /// a concrete function type.
+    pub fn unwrap_concrete_func(&self) -> &FuncType {
+        self.as_concrete_func().unwrap()
+    }
+
+    /// Is this a concrete, user-defined array type?
+    pub fn is_concrete_array(&self) -> bool {
+        matches!(self, HeapType::ConcreteArray(_))
+    }
+
+    /// Get the underlying concrete, user-defined array type, if any.
+    ///
+    /// Returns `None` for if this is not a concrete array type.
+    pub fn as_concrete_array(&self) -> Option<&ArrayType> {
+        match self {
+            HeapType::ConcreteArray(f) => Some(f),
+            _ => None,
+        }
+    }
+
+    /// Get the underlying concrete, user-defined type, panicking if this is not
+    /// a concrete array type.
+    pub fn unwrap_concrete_array(&self) -> &ArrayType {
+        self.as_concrete_array().unwrap()
     }
 
     /// Get the top type of this heap type's type hierarchy.
     ///
     /// The returned heap type is a supertype of all types in this heap type's
     /// type hierarchy.
-    pub fn top(&self, engine: &Engine) -> HeapType {
-        // The engine isn't used yet, but will be once we support Wasm GC, so
-        // future-proof our API.
-        let _ = engine;
-
+    pub fn top(&self) -> HeapType {
         match self {
             HeapType::Func | HeapType::ConcreteFunc(_) | HeapType::NoFunc => HeapType::Func,
+
             HeapType::Extern => HeapType::Extern,
-            HeapType::Any | HeapType::I31 | HeapType::None => HeapType::Any,
+
+            HeapType::Any
+            | HeapType::I31
+            | HeapType::Array
+            | HeapType::ConcreteArray(_)
+            | HeapType::None => HeapType::Any,
+        }
+    }
+
+    /// Is this the top type within its type hierarchy?
+    pub fn is_top(&self) -> bool {
+        match self {
+            HeapType::Any | HeapType::Extern | HeapType::Func => true,
+            _ => false,
         }
     }
 
@@ -602,9 +666,23 @@ impl HeapType {
             (HeapType::Func, HeapType::Func) => true,
             (HeapType::Func, _) => false,
 
-            (HeapType::None, HeapType::None | HeapType::I31 | HeapType::Any) => true,
+            (
+                HeapType::None,
+                HeapType::None
+                | HeapType::ConcreteArray(_)
+                | HeapType::Array
+                | HeapType::I31
+                | HeapType::Any,
+            ) => true,
             (HeapType::None, _) => false,
 
+            (HeapType::ConcreteArray(_), HeapType::Array | HeapType::Any) => true,
+            (HeapType::ConcreteArray(a), HeapType::ConcreteArray(b)) => a.matches(b),
+            (HeapType::ConcreteArray(_), _) => false,
+
+            (HeapType::Array, HeapType::Array | HeapType::Any) => true,
+            (HeapType::Array, _) => false,
+
             (HeapType::I31, HeapType::I31 | HeapType::Any) => true,
             (HeapType::I31, _) => false,
 
@@ -644,8 +722,10 @@ impl HeapType {
             | HeapType::NoFunc
             | HeapType::Any
             | HeapType::I31
+            | HeapType::Array
             | HeapType::None => true,
             HeapType::ConcreteFunc(ty) => ty.comes_from_same_engine(engine),
+            HeapType::ConcreteArray(ty) => ty.comes_from_same_engine(engine),
         }
     }
 
@@ -656,10 +736,14 @@ impl HeapType {
             HeapType::NoFunc => WasmHeapType::NoFunc,
             HeapType::Any => WasmHeapType::Any,
             HeapType::I31 => WasmHeapType::I31,
+            HeapType::Array => WasmHeapType::Array,
             HeapType::None => WasmHeapType::None,
             HeapType::ConcreteFunc(f) => {
                 WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::Engine(f.type_index()))
             }
+            HeapType::ConcreteArray(a) => {
+                WasmHeapType::ConcreteArray(EngineOrModuleTypeIndex::Engine(a.type_index()))
+            }
         }
     }
 
@@ -670,43 +754,53 @@ impl HeapType {
             WasmHeapType::NoFunc => HeapType::NoFunc,
             WasmHeapType::Any => HeapType::Any,
             WasmHeapType::I31 => HeapType::I31,
+            WasmHeapType::Array => HeapType::Array,
             WasmHeapType::None => HeapType::None,
             WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::Engine(idx)) => {
                 HeapType::ConcreteFunc(FuncType::from_shared_type_index(engine, *idx))
             }
+            WasmHeapType::ConcreteArray(EngineOrModuleTypeIndex::Engine(idx)) => {
+                HeapType::ConcreteArray(ArrayType::from_shared_type_index(engine, *idx))
+            }
+
             WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::Module(_))
-            | WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::RecGroup(_)) => {
-                panic!("HeapType::from_wasm_type on non-canonical heap type")
+            | WasmHeapType::ConcreteFunc(EngineOrModuleTypeIndex::RecGroup(_))
+            | WasmHeapType::ConcreteArray(EngineOrModuleTypeIndex::Module(_))
+            | WasmHeapType::ConcreteArray(EngineOrModuleTypeIndex::RecGroup(_)) => {
+                panic!("HeapType::from_wasm_type on non-canonicalized-for-runtime-usage heap type")
             }
         }
     }
 
-    pub(crate) fn is_gc_heap_type(&self) -> bool {
-        // All `t <: (ref null any)` and `t <: (ref null extern)` that are
-        // not `(ref null? i31)` are GC-managed references.
+    pub(crate) fn as_registered_type(&self) -> Option<&RegisteredType> {
         match self {
-            // These types are managed by the GC.
-            HeapType::Extern | HeapType::Any => true,
-
-            // TODO: Once we support concrete struct and array types, we will
-            // need to inspect the payload to determine whether this is a
-            // GC-managed type or not.
-            Self::ConcreteFunc(_) => false,
-
-            // These are compatible with GC references, but don't actually point
-            // to GC objecs. It would generally be safe to return `true` here,
-            // but there is no need to.
-            HeapType::I31 => false,
-
-            // These are a subtype of GC-managed types, but are uninhabited, so
-            // can never actually point to a GC object. Again, we could return
-            // `true` here but there is no need.
-            HeapType::None => false,
-
-            // These types are not managed by the GC.
-            HeapType::Func | HeapType::NoFunc => false,
+            HeapType::ConcreteFunc(f) => Some(&f.registered_type),
+            HeapType::ConcreteArray(a) => Some(&a.registered_type),
+            HeapType::Extern
+            | HeapType::Func
+            | HeapType::NoFunc
+            | HeapType::Any
+            | HeapType::I31
+            | HeapType::Array
+            | HeapType::None => None,
         }
     }
+
+    #[inline]
+    pub(crate) fn is_vmgcref_type(&self) -> bool {
+        match self.top() {
+            Self::Any | Self::Extern => true,
+            Self::Func => false,
+            ty => unreachable!("not a top type: {ty:?}"),
+        }
+    }
+
+    /// Is this a `VMGcRef` type that is not i31 and is not an uninhabited
+    /// bottom type?
+    #[inline]
+    pub(crate) fn is_vmgcref_type_and_points_to_object(&self) -> bool {
+        self.is_vmgcref_type() && !matches!(self, HeapType::I31 | HeapType::NoFunc | HeapType::None)
+    }
 }
 
 // External Types
@@ -807,6 +901,352 @@ impl From<TableType> for ExternType {
     }
 }
 
+/// The storage type of a `struct` field or `array` element.
+///
+/// This is either a packed 8- or -16 bit integer, or else it is some unpacked
+/// Wasm value type.
+#[derive(Clone, Hash)]
+pub enum StorageType {
+    /// `i8`, an 8-bit integer.
+    I8,
+    /// `i16`, a 16-bit integer.
+    I16,
+    /// A value type.
+    ValType(ValType),
+}
+
+impl From<ValType> for StorageType {
+    #[inline]
+    fn from(v: ValType) -> Self {
+        StorageType::ValType(v)
+    }
+}
+
+impl StorageType {
+    /// Is this an `i8`?
+    #[inline]
+    pub fn is_i8(&self) -> bool {
+        matches!(self, Self::I8)
+    }
+
+    /// Is this an `i16`?
+    #[inline]
+    pub fn is_i16(&self) -> bool {
+        matches!(self, Self::I16)
+    }
+
+    /// Is this a Wasm value type?
+    #[inline]
+    pub fn is_val_type(&self) -> bool {
+        matches!(self, Self::I16)
+    }
+
+    /// Get this storage type's underlying value type, if any.
+    ///
+    /// Returns `None` if this storage type is not a value type.
+    #[inline]
+    pub fn as_val_type(&self) -> Option<&ValType> {
+        match self {
+            Self::ValType(v) => Some(v),
+            _ => None,
+        }
+    }
+
+    /// Get this storage type's underlying value type, panicking if it is not a
+    /// value type.
+    pub fn unwrap_val_type(&self) -> &ValType {
+        self.as_val_type().unwrap()
+    }
+
+    /// Does this field type match the other field type?
+    ///
+    /// That is, is this field type a subtype of the other field type?
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn matches(&self, other: &Self) -> bool {
+        match (self, other) {
+            (StorageType::I8, StorageType::I8) => true,
+            (StorageType::I8, _) => false,
+            (StorageType::I16, StorageType::I16) => true,
+            (StorageType::I16, _) => false,
+            (StorageType::ValType(a), StorageType::ValType(b)) => a.matches(b),
+            (StorageType::ValType(_), _) => false,
+        }
+    }
+
+    /// Is field type `a` precisely equal to field type `b`?
+    ///
+    /// Returns `false` even if `a` is a subtype of `b` or vice versa, if they
+    /// are not exactly the same field type.
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn eq(a: &Self, b: &Self) -> bool {
+        a.matches(b) && b.matches(a)
+    }
+
+    pub(crate) fn from_wasm_storage_type(engine: &Engine, ty: &WasmStorageType) -> Self {
+        match ty {
+            WasmStorageType::I8 => Self::I8,
+            WasmStorageType::I16 => Self::I16,
+            WasmStorageType::Val(v) => ValType::from_wasm_type(engine, &v).into(),
+        }
+    }
+
+    pub(crate) fn to_wasm_storage_type(&self) -> WasmStorageType {
+        match self {
+            Self::I8 => WasmStorageType::I8,
+            Self::I16 => WasmStorageType::I16,
+            Self::ValType(v) => WasmStorageType::Val(v.to_wasm_type()),
+        }
+    }
+}
+
+/// The type of a `struct` field or an `array`'s elements.
+///
+/// This is a pair of both the field's storage type and its mutability
+/// (i.e. whether the field can be updated or not).
+#[derive(Clone, Hash)]
+pub struct FieldType {
+    mutability: Mutability,
+    element_type: StorageType,
+}
+
+impl FieldType {
+    /// Construct a new field type from the given parts.
+    #[inline]
+    pub fn new(mutability: Mutability, element_type: StorageType) -> Self {
+        Self {
+            mutability,
+            element_type,
+        }
+    }
+
+    /// Get whether or not this field type is mutable.
+    #[inline]
+    pub fn mutability(&self) -> Mutability {
+        self.mutability
+    }
+
+    /// Get this field type's storage type.
+    #[inline]
+    pub fn element_type(&self) -> &StorageType {
+        &self.element_type
+    }
+
+    /// Does this field type match the other field type?
+    ///
+    /// That is, is this field type a subtype of the other field type?
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn matches(&self, other: &Self) -> bool {
+        (other.mutability == Mutability::Var || self.mutability == Mutability::Const)
+            && self.element_type.matches(&other.element_type)
+    }
+
+    /// Is field type `a` precisely equal to field type `b`?
+    ///
+    /// Returns `false` even if `a` is a subtype of `b` or vice versa, if they
+    /// are not exactly the same field type.
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn eq(a: &Self, b: &Self) -> bool {
+        a.matches(b) && b.matches(a)
+    }
+
+    pub(crate) fn from_wasm_field_type(engine: &Engine, ty: &WasmFieldType) -> Self {
+        Self {
+            mutability: if ty.mutable {
+                Mutability::Var
+            } else {
+                Mutability::Const
+            },
+            element_type: StorageType::from_wasm_storage_type(engine, &ty.element_type),
+        }
+    }
+
+    pub(crate) fn to_wasm_field_type(&self) -> WasmFieldType {
+        WasmFieldType {
+            element_type: self.element_type.to_wasm_storage_type(),
+            mutable: matches!(self.mutability, Mutability::Var),
+        }
+    }
+}
+
+/// The type of a WebAssembly array.
+///
+/// WebAssembly arrays are dynamically-sized, but not resizable. They contain
+/// either unpacked [`Val`][crate::Val]s or packed 8-/16-bit integers.
+///
+/// # Subtyping and Equality
+///
+/// `ArrayType` does not implement `Eq`, because reference types have a
+/// subtyping relationship, and so 99.99% of the time you actually want to check
+/// whether one type matches (i.e. is a subtype of) another type. You can use
+/// the [`ArrayType::matches`] method to perform these types of checks. If,
+/// however, you are in that 0.01% scenario where you need to check precise
+/// equality between types, you can use the [`ArrayType::eq`] method.
+//
+// TODO: Once we have array values, update above docs with a reference to the
+// future `Array::matches_ty` method
+#[derive(Debug, Clone, Hash)]
+pub struct ArrayType {
+    registered_type: RegisteredType,
+}
+
+impl ArrayType {
+    /// Construct a new `ArrayType` with the given field type's mutability and
+    /// storage type.
+    ///
+    /// The result will be associated with the given engine, and attempts to use
+    /// it with other engines will panic (for example, checking whether it is a
+    /// subtype of another array type that is associated with a different
+    /// engine).
+    pub fn new(engine: &Engine, field_type: FieldType) -> Self {
+        // Same as in `FuncType::new`: we must prevent any `RegisteredType` in
+        // `field_type` from being reclaimed while constructing this array type.
+        let _registration = field_type
+            .element_type
+            .as_val_type()
+            .and_then(|v| v.as_ref())
+            .and_then(|r| r.heap_type().as_registered_type());
+
+        let wasm_ty = WasmArrayType(field_type.to_wasm_field_type());
+        Self::from_wasm_array_type(engine, wasm_ty)
+    }
+
+    /// Get the engine that this array type is associated with.
+    pub fn engine(&self) -> &Engine {
+        self.registered_type.engine()
+    }
+
+    /// Get this array's underlying field type.
+    ///
+    /// The field type contains information about both this array type's
+    /// mutability and the storage type used for its elements.
+    pub fn field_type(&self) -> FieldType {
+        FieldType::from_wasm_field_type(self.engine(), &self.as_wasm_array_type().0)
+    }
+
+    /// Get this array type's mutability and whether its instances' elements can
+    /// be updated or not.
+    ///
+    /// This is a convenience method providing a short-hand for
+    /// `my_array_type.field_type().mutability()`.
+    pub fn mutability(&self) -> Mutability {
+        if self.as_wasm_array_type().0.mutable {
+            Mutability::Var
+        } else {
+            Mutability::Const
+        }
+    }
+
+    /// Get the storage type used for this array type's elements.
+    ///
+    /// This is a convenience method providing a short-hand for
+    /// `my_array_type.field_type().element_type()`.
+    pub fn element_type(&self) -> StorageType {
+        StorageType::from_wasm_storage_type(
+            self.engine(),
+            &self.registered_type.unwrap_array().0.element_type,
+        )
+    }
+
+    /// Does this array type match the other array type?
+    ///
+    /// That is, is this function type a subtype of the other array type?
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn matches(&self, other: &ArrayType) -> bool {
+        assert!(self.comes_from_same_engine(other.engine()));
+
+        // Avoid matching on structure for subtyping checks when we have
+        // precisely the same type.
+        if self.type_index() == other.type_index() {
+            return true;
+        }
+
+        self.field_type().matches(&other.field_type())
+    }
+
+    /// Is array type `a` precisely equal to array type `b`?
+    ///
+    /// Returns `false` even if `a` is a subtype of `b` or vice versa, if they
+    /// are not exactly the same array type.
+    ///
+    /// # Panics
+    ///
+    /// Panics if either type is associated with a different engine from the
+    /// other.
+    pub fn eq(a: &ArrayType, b: &ArrayType) -> bool {
+        assert!(a.comes_from_same_engine(b.engine()));
+        a.type_index() == b.type_index()
+    }
+
+    pub(crate) fn comes_from_same_engine(&self, engine: &Engine) -> bool {
+        Engine::same(self.registered_type.engine(), engine)
+    }
+
+    pub(crate) fn type_index(&self) -> VMSharedTypeIndex {
+        self.registered_type.index()
+    }
+
+    pub(crate) fn as_wasm_array_type(&self) -> &WasmArrayType {
+        self.registered_type.unwrap_array()
+    }
+
+    /// Construct a `ArrayType` from a `WasmArrayType`.
+    ///
+    /// This method should only be used when something has already registered --
+    /// and is *keeping registered* -- any other concrete Wasm types referenced
+    /// by the given `WasmArrayType`.
+    ///
+    /// For example, this method may be called to convert an array type from
+    /// within a Wasm module's `ModuleTypes` since the Wasm module itself is
+    /// holding a strong reference to all of its types, including any `(ref null
+    /// <index>)` types used as the element type for this array type.
+    pub(crate) fn from_wasm_array_type(engine: &Engine, ty: WasmArrayType) -> ArrayType {
+        let ty = RegisteredType::new(
+            engine,
+            WasmSubType {
+                // TODO:
+                //
+                // is_final: true,
+                // supertype: None,
+                composite_type: WasmCompositeType::Array(ty),
+            },
+        );
+        Self {
+            registered_type: ty,
+        }
+    }
+
+    pub(crate) fn from_shared_type_index(engine: &Engine, index: VMSharedTypeIndex) -> ArrayType {
+        let ty = RegisteredType::root(engine, index).expect(
+            "VMSharedTypeIndex is not registered in the Engine! Wrong \
+             engine? Didn't root the index somewhere?",
+        );
+        assert!(ty.is_array());
+        Self {
+            registered_type: ty,
+        }
+    }
+}
+
 /// The type of a WebAssembly function.
 ///
 /// WebAssembly functions can have 0 or more parameters and results.
@@ -861,12 +1301,12 @@ impl FuncType {
         // the only thing keeping a type in the registry, we don't want to
         // unregister it when we convert the `ValType` into a `WasmValType` just
         // before we register our new `WasmFuncType` that will reference it.
-        let mut registrations = vec![];
+        let mut registrations = smallvec::SmallVec::<[_; 4]>::new();
 
         let mut to_wasm_type = |ty: ValType| {
             if let Some(r) = ty.as_ref() {
-                if let Some(c) = r.heap_type().as_concrete() {
-                    registrations.push(c.registered_type.clone());
+                if let Some(r) = r.heap_type().as_registered_type() {
+                    registrations.push(r.clone());
                 }
             }
             ty.to_wasm_type()
@@ -1025,6 +1465,7 @@ impl FuncType {
             "VMSharedTypeIndex is not registered in the Engine! Wrong \
              engine? Didn't root the index somewhere?",
         );
+        assert!(ty.is_func());
         Self {
             registered_type: ty,
         }
diff --git a/crates/wasmtime/src/runtime/types/matching.rs b/crates/wasmtime/src/runtime/types/matching.rs
index 9511d9b03..aa15532f2 100644
--- a/crates/wasmtime/src/runtime/types/matching.rs
+++ b/crates/wasmtime/src/runtime/types/matching.rs
@@ -115,25 +115,47 @@ fn concrete_type_mismatch(
     actual: &WasmSubType,
 ) -> anyhow::Error {
     let render = |ty: &WasmSubType| match &ty.composite_type {
+        WasmCompositeType::Array(ty) => {
+            format!(
+                "(array {})",
+                if ty.0.mutable {
+                    format!("(mut {})", ty.0.element_type)
+                } else {
+                    ty.0.element_type.to_string()
+                }
+            )
+        }
         WasmCompositeType::Func(ty) => {
-            let params = ty
-                .params()
-                .iter()
-                .map(|s| s.to_string())
-                .collect::<Vec<_>>()
-                .join(", ");
-            let returns = ty
-                .returns()
-                .iter()
-                .map(|s| s.to_string())
-                .collect::<Vec<_>>()
-                .join(", ");
-            format!("`({}) -> ({})`", params, returns)
+            let params = if ty.params().is_empty() {
+                String::new()
+            } else {
+                format!(
+                    " (param {})",
+                    ty.params()
+                        .iter()
+                        .map(|s| s.to_string())
+                        .collect::<Vec<_>>()
+                        .join(" ")
+                )
+            };
+            let returns = if ty.returns().is_empty() {
+                String::new()
+            } else {
+                format!(
+                    " (result {})",
+                    ty.returns()
+                        .iter()
+                        .map(|s| s.to_string())
+                        .collect::<Vec<_>>()
+                        .join(" ")
+                )
+            };
+            format!("(func{params}{returns})")
         }
     };
 
     anyhow!(
-        "{msg}: expected func of type {}, found func of type {}",
+        "{msg}: expected type `{}`, found type `{}`",
         render(expected),
         render(actual)
     )
@@ -205,6 +227,7 @@ fn match_heap(expected: WasmHeapType, actual: WasmHeapType, desc: &str) -> Resul
         // TODO: Wasm GC introduces subtyping between function types, so it will
         // no longer suffice to check whether canonicalized type IDs are equal.
         (H::ConcreteFunc(actual), H::ConcreteFunc(expected)) => actual == expected,
+        (H::ConcreteArray(actual), H::ConcreteArray(expected)) => actual == expected,
 
         (H::NoFunc, H::NoFunc) => true,
         (_, H::NoFunc) => false,
@@ -218,12 +241,18 @@ fn match_heap(expected: WasmHeapType, actual: WasmHeapType, desc: &str) -> Resul
         (H::Extern, H::Extern) => true,
         (_, H::Extern) => false,
 
-        (H::Any | H::I31 | H::None, H::Any) => true,
+        (H::Any | H::I31 | H::Array | H::ConcreteArray(_) | H::None, H::Any) => true,
         (_, H::Any) => false,
 
         (H::I31 | H::None, H::I31) => true,
         (_, H::I31) => false,
 
+        (H::Array | H::ConcreteArray(_) | H::None, H::Array) => true,
+        (_, H::Array) => false,
+
+        (H::None, H::ConcreteArray(_)) => true,
+        (_, H::ConcreteArray(_)) => false,
+
         (H::None, H::None) => true,
         (_, H::None) => false,
     };
diff --git a/crates/wasmtime/src/runtime/v128.rs b/crates/wasmtime/src/runtime/v128.rs
index b5528e024..c4ad50088 100644
--- a/crates/wasmtime/src/runtime/v128.rs
+++ b/crates/wasmtime/src/runtime/v128.rs
@@ -99,7 +99,7 @@ unsafe impl WasmTy for V128 {
         &self,
         _: &StoreOpaque,
         _: bool,
-        _: &crate::FuncType,
+        _: &crate::HeapType,
     ) -> anyhow::Result<()> {
         unreachable!()
     }
diff --git a/crates/wasmtime/src/runtime/values.rs b/crates/wasmtime/src/runtime/values.rs
index 0b03ade19..fc4a6d262 100644
--- a/crates/wasmtime/src/runtime/values.rs
+++ b/crates/wasmtime/src/runtime/values.rs
@@ -79,10 +79,11 @@ macro_rules! accessors {
 impl Val {
     /// Returns the null reference for the given heap type.
     pub fn null_ref(heap_type: HeapType) -> Val {
-        match heap_type {
-            HeapType::Func | HeapType::NoFunc | HeapType::ConcreteFunc(_) => Val::FuncRef(None),
+        match heap_type.top() {
+            HeapType::Func => Val::FuncRef(None),
             HeapType::Extern => Val::ExternRef(None),
-            HeapType::Any | HeapType::I31 | HeapType::None => Val::AnyRef(None),
+            HeapType::Any => Val::AnyRef(None),
+            _ => unreachable!(),
         }
     }
 
@@ -246,11 +247,18 @@ impl Val {
                     HeapType::Func | HeapType::ConcreteFunc(_) => {
                         Func::from_raw(store, raw.get_funcref()).into()
                     }
+
                     HeapType::NoFunc => Ref::Func(None),
+
                     HeapType::Extern => ExternRef::from_raw(store, raw.get_externref()).into(),
-                    HeapType::Any | HeapType::I31 => {
+
+                    HeapType::Any
+                    | HeapType::I31
+                    | HeapType::Array
+                    | HeapType::ConcreteArray(_) => {
                         AnyRef::from_raw(store, raw.get_anyref()).into()
                     }
+
                     HeapType::None => Ref::Any(None),
                 };
                 assert!(
@@ -838,7 +846,7 @@ impl Ref {
         self.ensure_matches_ty(&store, &ty)
             .context("type mismatch: value does not match table element type")?;
 
-        match (self, ty.heap_type().top(store.engine())) {
+        match (self, ty.heap_type().top()) {
             (Ref::Func(None), HeapType::Func) => {
                 assert!(ty.is_nullable());
                 Ok(TableElement::FuncRef(ptr::null_mut()))


Test patch:
diff --git a/tests/all/func.rs b/tests/all/func.rs
index ff69e172a..eafff2bf3 100644
--- a/tests/all/func.rs
+++ b/tests/all/func.rs
@@ -1600,7 +1600,7 @@ fn typed_concrete_param() -> anyhow::Result<()> {
     assert!(e.contains("argument type mismatch for reference to concrete type"));
     assert!(e.contains(
         "type mismatch: expected (type (func)), \
-         found (type (func (param (ref null (concrete VMSharedTypeIndex(0))))))"
+         found (type (func (param (ref null (concrete func VMSharedTypeIndex(0))))))"
     ));
 
     // And dynamic checks also work with a non-nullable super type.
@@ -1614,7 +1614,7 @@ fn typed_concrete_param() -> anyhow::Result<()> {
     assert!(e.contains("argument type mismatch for reference to concrete type"));
     assert!(e.contains(
         "type mismatch: expected (type (func)), \
-         found (type (func (param (ref null (concrete VMSharedTypeIndex(0))))))"
+         found (type (func (param (ref null (concrete func VMSharedTypeIndex(0))))))"
     ));
 
     // Calling `typed` with a type that is not a supertype nor a subtype fails
@@ -1671,7 +1671,7 @@ fn typed_concrete_result() -> anyhow::Result<()> {
     let e = format!("{e:?}");
     assert!(e.contains("type mismatch with results"));
     assert!(e.contains(
-        "type mismatch: expected (ref nofunc), found (ref (concrete VMSharedTypeIndex(0)))"
+        "type mismatch: expected (ref nofunc), found (ref (concrete func VMSharedTypeIndex(0)))"
     ));
 
     // Nor some unrelated type that it is neither a subtype or supertype of.
@@ -1679,7 +1679,7 @@ fn typed_concrete_result() -> anyhow::Result<()> {
     let e = format!("{e:?}");
     assert!(e.contains("type mismatch with results"));
     assert!(e.contains(
-        "type mismatch: expected (ref extern), found (ref (concrete VMSharedTypeIndex(0)))"
+        "type mismatch: expected (ref extern), found (ref (concrete func VMSharedTypeIndex(0)))"
     ));
 
     Ok(())
diff --git a/tests/all/main.rs b/tests/all/main.rs
index bb8ac88b0..2b173037a 100644
--- a/tests/all/main.rs
+++ b/tests/all/main.rs
@@ -36,6 +36,7 @@ mod store;
 mod table;
 mod threads;
 mod traps;
+mod types;
 mod wait_notify;
 mod wasi_testsuite;
 mod wast;
diff --git a/tests/all/types.rs b/tests/all/types.rs
new file mode 100644
index 000000000..7ce9f436d
--- /dev/null
+++ b/tests/all/types.rs
@@ -0,0 +1,25 @@
+use wasmtime::*;
+
+#[test]
+fn basic_array_types() -> Result<()> {
+    let engine = Engine::default();
+    for mutability in [Mutability::Const, Mutability::Var] {
+        for storage_ty in [
+            StorageType::I8,
+            StorageType::I16,
+            StorageType::ValType(ValType::I32),
+            StorageType::ValType(RefType::new(true, FuncType::new(&engine, [], []).into()).into()),
+        ] {
+            let field_ty = FieldType::new(mutability, storage_ty.clone());
+            assert_eq!(field_ty.mutability(), mutability);
+            assert!(StorageType::eq(field_ty.element_type(), &storage_ty));
+
+            let array_ty = ArrayType::new(&engine, field_ty.clone());
+            assert!(Engine::same(array_ty.engine(), &engine));
+            assert!(FieldType::eq(&array_ty.field_type(), &field_ty));
+            assert_eq!(array_ty.mutability(), mutability);
+            assert!(StorageType::eq(&array_ty.element_type(), &storage_ty));
+        }
+    }
+    Ok(())
+}
diff --git a/tests/misc_testsuite/component-model/modules.wast b/tests/misc_testsuite/component-model/modules.wast
index 80ea13d40..fc7869b2d 100644
--- a/tests/misc_testsuite/component-model/modules.wast
+++ b/tests/misc_testsuite/component-model/modules.wast
@@ -91,7 +91,7 @@
       ))
     ))
   )
-  "expected func of type `(i32) -> ()`, found func of type `() -> ()`")
+  "expected type `(func (param i32))`, found type `(func)`")
 
 (assert_unlinkable
   (component
diff --git a/tests/misc_testsuite/gc/array-types.wast b/tests/misc_testsuite/gc/array-types.wast
new file mode 100644
index 000000000..3851f172d
--- /dev/null
+++ b/tests/misc_testsuite/gc/array-types.wast
@@ -0,0 +1,20 @@
+(module
+  (type (array i8))
+  (type (array i16))
+  (type (array i32))
+  (type (array i64))
+  (type (array f32))
+  (type (array f64))
+  (type (array anyref))
+  (type (array (ref 0)))
+  (type (array (ref null 1)))
+  (type (array (mut i8)))
+  (type (array (mut i16)))
+  (type (array (mut i32)))
+  (type (array (mut i64)))
+  (type (array (mut i32)))
+  (type (array (mut i64)))
+  (type (array (mut anyref)))
+  (type (array (mut (ref 0))))
+  (type (array (mut (ref null i31))))
+)
diff --git a/tests/misc_testsuite/linking-errors.wast b/tests/misc_testsuite/linking-errors.wast
index 122c9a2b3..a3a262c53 100644
--- a/tests/misc_testsuite/linking-errors.wast
+++ b/tests/misc_testsuite/linking-errors.wast
@@ -45,8 +45,8 @@
 ;; errors on functions
 (assert_unlinkable
   (module (import "m" "f" (func (param i32))))
-  "expected func of type `(i32) -> ()`, found func of type `() -> ()`")
+  "expected type `(func (param i32))`, found type `(func)`")
 
 (assert_unlinkable
   (module (import "m" "f p1r2" (func (param i32 i32) (result f64))))
-  "expected func of type `(i32, i32) -> (f64)`, found func of type `(f32) -> (i32, i64)`")
+  "expected type `(func (param i32 i32) (result f64))`, found type `(func (param f32) (result i32 i64))`")