Repository: bytecodealliance/wasmtime
Pull request #8404 (2024-04-18 20:33:22)

Add support for recursion groups in the types registry
This adds support for recursion groups in Wasmtime's type registry, but still just for function types. Adding struct and array types should be relatively easy after this. At least, we won't have to be concerned with canonicalization, just updating heap type matching everywhere and all that.

Depends on https://github.com/bytecodealliance/wasm-tools/pull/1506 and updating the `wasm-tools` crates before this can land.

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

cc @saulecabrera

<details>
This issue or pull request has been labeled: "cranelift", "wasmtime:api", "winch"

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

* saulecabrera: winch

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/.github/workflows/main.yml b/.github/workflows/main.yml
index 48417841f..7c37ad5a1 100644
--- a/.github/workflows/main.yml
+++ b/.github/workflows/main.yml
@@ -454,7 +454,7 @@ jobs:
       with:
         toolchain: nightly-2024-03-21
 
-    # Ensure that fuzzers sitll build.
+    # Ensure that fuzzers still build.
     #
     # Install the OCaml packages necessary for fuzz targets that use the
     # `wasm-spec-interpreter`.
diff --git a/cranelift/entity/src/lib.rs b/cranelift/entity/src/lib.rs
index b22eeb350..3d22df490 100644
--- a/cranelift/entity/src/lib.rs
+++ b/cranelift/entity/src/lib.rs
@@ -38,6 +38,9 @@ extern crate alloc;
 #[doc(hidden)]
 pub extern crate core as __core;
 
+use core::iter::FusedIterator;
+use core::ops::Range;
+
 /// A type wrapping a small integer index should implement `EntityRef` so it can be used as the key
 /// of an `SecondaryMap` or `SparseMap`.
 pub trait EntityRef: Copy + Eq {
@@ -49,6 +52,67 @@ pub trait EntityRef: Copy + Eq {
     fn index(self) -> usize;
 }
 
+/// Iterate over a `Range<E: EntityRef>`, yielding a sequence of `E` items.
+#[inline]
+pub fn iter_entity_range<E>(range: Range<E>) -> IterEntityRange<E>
+where
+    E: EntityRef,
+{
+    IterEntityRange {
+        range: range.start.index()..range.end.index(),
+        _phantom: core::marker::PhantomData,
+    }
+}
+
+/// Iterator type returned by `iter_entity_range`.
+pub struct IterEntityRange<E> {
+    range: Range<usize>,
+    _phantom: core::marker::PhantomData<E>,
+}
+
+impl<E> Iterator for IterEntityRange<E>
+where
+    E: EntityRef,
+{
+    type Item = E;
+
+    #[inline]
+    fn next(&mut self) -> Option<Self::Item> {
+        let i = self.range.next()?;
+        Some(E::new(i))
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.range.size_hint()
+    }
+}
+
+impl<E> DoubleEndedIterator for IterEntityRange<E>
+where
+    E: EntityRef,
+{
+    #[inline]
+    fn next_back(&mut self) -> Option<Self::Item> {
+        let i = self.range.next_back()?;
+        Some(E::new(i))
+    }
+}
+
+impl<E> FusedIterator for IterEntityRange<E>
+where
+    E: EntityRef,
+    Range<usize>: FusedIterator,
+{
+}
+
+impl<E> ExactSizeIterator for IterEntityRange<E>
+where
+    E: EntityRef,
+    Range<usize>: ExactSizeIterator,
+{
+}
+
 /// Macro which provides the common implementation of a 32-bit entity reference.
 #[macro_export]
 macro_rules! entity_impl {
diff --git a/crates/cranelift/src/func_environ.rs b/crates/cranelift/src/func_environ.rs
index 5e02e721c..5ffcf2cda 100644
--- a/crates/cranelift/src/func_environ.rs
+++ b/crates/cranelift/src/func_environ.rs
@@ -18,8 +18,8 @@ use cranelift_wasm::{
 use std::mem;
 use wasmparser::Operator;
 use wasmtime_environ::{
-    BuiltinFunctionIndex, MemoryPlan, MemoryStyle, Module, ModuleTranslation, ModuleType,
-    ModuleTypesBuilder, PtrSize, TableStyle, Tunables, TypeConvert, VMOffsets, WASM_PAGE_SIZE,
+    BuiltinFunctionIndex, MemoryPlan, MemoryStyle, Module, ModuleTranslation, ModuleTypesBuilder,
+    PtrSize, TableStyle, Tunables, TypeConvert, VMOffsets, WASM_PAGE_SIZE,
 };
 use wasmtime_environ::{FUNCREF_INIT_BIT, FUNCREF_MASK};
 
@@ -1204,7 +1204,7 @@ impl<'a, 'func, 'module_env> Call<'a, 'func, 'module_env> {
                 // If `ty_index` matches `table_ty`, then this call is
                 // statically known to have the right type, so no checks are
                 // necessary.
-                let ModuleType::Function(specified_ty) = self.env.module.types[ty_index];
+                let specified_ty = self.env.module.types[ty_index];
                 if specified_ty == table_ty {
                     return CheckIndirectCallTypeSignature::StaticMatch {
                         may_be_null: table.table.wasm_ty.nullable,
@@ -1244,6 +1244,7 @@ impl<'a, 'func, 'module_env> Call<'a, 'func, 'module_env> {
             // validation error to perform a call through a non-function table,
             // so these cases are dynamically not reachable.
             WasmHeapType::Concrete(EngineOrModuleTypeIndex::Engine(_))
+            | WasmHeapType::Concrete(EngineOrModuleTypeIndex::RecGroup(_))
             | WasmHeapType::Extern
             | WasmHeapType::Any
             | WasmHeapType::I31
@@ -1265,7 +1266,7 @@ impl<'a, 'func, 'module_env> Call<'a, 'func, 'module_env> {
             base,
             i32::try_from(self.env.offsets.vmctx_type_ids_array()).unwrap(),
         );
-        let sig_index = self.env.module.types[ty_index].unwrap_function();
+        let sig_index = self.env.module.types[ty_index];
         let offset =
             i32::try_from(sig_index.as_u32().checked_mul(sig_id_type.bytes()).unwrap()).unwrap();
         let caller_sig_id = self
@@ -1390,11 +1391,7 @@ impl<'a, 'func, 'module_env> Call<'a, 'func, 'module_env> {
 
 impl TypeConvert for FuncEnvironment<'_> {
     fn lookup_heap_type(&self, ty: wasmparser::UnpackedIndex) -> WasmHeapType {
-        wasmtime_environ::WasmparserTypeConverter {
-            module: self.module,
-            types: self.types,
-        }
-        .lookup_heap_type(ty)
+        wasmtime_environ::WasmparserTypeConverter::new(self.types, self.module).lookup_heap_type(ty)
     }
 }
 
@@ -2005,7 +2002,7 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         func: &mut ir::Function,
         index: TypeIndex,
     ) -> WasmResult<ir::SigRef> {
-        let index = self.module.types[index].unwrap_function();
+        let index = self.module.types[index];
         let sig = crate::wasm_call_signature(self.isa, &self.types[index], &self.tunables);
         Ok(func.import_signature(sig))
     }
diff --git a/crates/environ/examples/factc.rs b/crates/environ/examples/factc.rs
index 979e617b4..ac55c4296 100644
--- a/crates/environ/examples/factc.rs
+++ b/crates/environ/examples/factc.rs
@@ -82,8 +82,6 @@ impl Factc {
     fn execute(self) -> Result<()> {
         env_logger::init();
 
-        let mut types = ComponentTypesBuilder::default();
-
         // Manufactures a unique `CoreDef` so all function imports get unique
         // function imports.
         let mut next_def = 0;
@@ -118,9 +116,11 @@ impl Factc {
             }
         };
 
+        let mut validator = Validator::new();
+        let mut types = ComponentTypesBuilder::new(&validator);
+
         let mut adapters = Vec::new();
         let input = wat::parse_file(&self.input)?;
-        let mut validator = Validator::new();
         let wasm_types = validator
             .validate_all(&input)
             .context("failed to validate input wasm")?;
diff --git a/crates/environ/src/component/translate.rs b/crates/environ/src/component/translate.rs
index 964ea41fa..a80266f44 100644
--- a/crates/environ/src/component/translate.rs
+++ b/crates/environ/src/component/translate.rs
@@ -1,4 +1,5 @@
 use crate::component::*;
+use crate::Module;
 use crate::ScopeVec;
 use crate::{
     EntityIndex, ModuleEnvironment, ModuleTranslation, ModuleTypesBuilder, PrimaryMap, Tunables,
@@ -14,6 +15,7 @@ use wasmparser::types::{
 };
 use wasmparser::{Chunk, ComponentImportName, Encoding, Parser, Payload, Validator};
 use wasmtime_types::ModuleInternedTypeIndex;
+use wasmtime_types::WasmResult;
 
 mod adapt;
 pub use self::adapt::*;
@@ -487,7 +489,7 @@ impl<'a, 'data> Translator<'a, 'data> {
                             let lower_ty = types.component_function_at(func_index);
                             let func = ComponentFuncIndex::from_u32(func_index);
                             let options = self.canonical_options(&options);
-                            let canonical_abi = self.core_func_signature(core_func_index);
+                            let canonical_abi = self.core_func_signature(core_func_index)?;
 
                             core_func_index += 1;
                             LocalInitializer::Lower {
@@ -499,19 +501,19 @@ impl<'a, 'data> Translator<'a, 'data> {
                         }
                         wasmparser::CanonicalFunction::ResourceNew { resource } => {
                             let resource = types.component_any_type_at(resource).unwrap_resource();
-                            let ty = self.core_func_signature(core_func_index);
+                            let ty = self.core_func_signature(core_func_index)?;
                             core_func_index += 1;
                             LocalInitializer::ResourceNew(resource, ty)
                         }
                         wasmparser::CanonicalFunction::ResourceDrop { resource } => {
                             let resource = types.component_any_type_at(resource).unwrap_resource();
-                            let ty = self.core_func_signature(core_func_index);
+                            let ty = self.core_func_signature(core_func_index)?;
                             core_func_index += 1;
                             LocalInitializer::ResourceDrop(resource, ty)
                         }
                         wasmparser::CanonicalFunction::ResourceRep { resource } => {
                             let resource = types.component_any_type_at(resource).unwrap_resource();
-                            let ty = self.core_func_signature(core_func_index);
+                            let ty = self.core_func_signature(core_func_index)?;
                             core_func_index += 1;
                             LocalInitializer::ResourceRep(resource, ty)
                         }
@@ -911,12 +913,14 @@ impl<'a, 'data> Translator<'a, 'data> {
         return ret;
     }
 
-    fn core_func_signature(&mut self, idx: u32) -> ModuleInternedTypeIndex {
+    /// Get the interned type index for the `index`th core function.
+    fn core_func_signature(&mut self, index: u32) -> WasmResult<ModuleInternedTypeIndex> {
         let types = self.validator.types(0).unwrap();
-        let id = types.core_function_at(idx);
-        let ty = types[id].unwrap_func();
-        let ty = self.types.convert_func_type(ty);
-        self.types.module_types_builder().wasm_func_type(id, ty)
+        let id = types.core_function_at(index);
+        let module = Module::default();
+        self.types
+            .module_types_builder()
+            .intern_type(&module, types, id)
     }
 }
 
diff --git a/crates/environ/src/component/translate/adapt.rs b/crates/environ/src/component/translate/adapt.rs
index d112fa808..aeb60da23 100644
--- a/crates/environ/src/component/translate/adapt.rs
+++ b/crates/environ/src/component/translate/adapt.rs
@@ -119,7 +119,6 @@ use crate::component::translate::*;
 use crate::fact;
 use crate::EntityType;
 use std::collections::HashSet;
-use wasmparser::WasmFeatures;
 
 /// Metadata information about a fused adapter.
 #[derive(Debug, Clone, Hash, Eq, PartialEq)]
@@ -212,12 +211,10 @@ impl<'data> Translator<'_, 'data> {
             // specifically enabled here since the adapter module is highly
             // likely to use that if anything is actually indirected through
             // memory.
-            let mut validator = Validator::new_with_features(
-                *self.validator.features() | WasmFeatures::MULTI_MEMORY,
-            );
+            self.validator.reset();
             let translation = ModuleEnvironment::new(
                 self.tunables,
-                &mut validator,
+                &mut self.validator,
                 self.types.module_types_builder(),
             )
             .translate(Parser::new(0), wasm)
diff --git a/crates/environ/src/component/types.rs b/crates/environ/src/component/types.rs
index 327d23b13..93d002baf 100644
--- a/crates/environ/src/component/types.rs
+++ b/crates/environ/src/component/types.rs
@@ -1,7 +1,7 @@
 use crate::component::{Export, MAX_FLAT_PARAMS, MAX_FLAT_RESULTS};
 use crate::{
-    CompiledModuleInfo, EntityType, ModuleTypes, ModuleTypesBuilder, PrimaryMap, TypeConvert,
-    WasmHeapType, WasmValType,
+    CompiledModuleInfo, EntityType, Module, ModuleTypes, ModuleTypesBuilder, PrimaryMap,
+    TypeConvert, WasmHeapType, WasmValType,
 };
 use anyhow::{bail, Result};
 use cranelift_entity::EntityRef;
@@ -11,7 +11,7 @@ use std::collections::HashMap;
 use std::hash::{Hash, Hasher};
 use std::ops::Index;
 use wasmparser::names::KebabString;
-use wasmparser::types;
+use wasmparser::{types, Validator};
 use wasmtime_component_util::{DiscriminantSize, FlagsSize};
 use wasmtime_types::ModuleInternedTypeIndex;
 
@@ -255,13 +255,13 @@ pub struct ComponentTypes {
     results: PrimaryMap<TypeResultIndex, TypeResult>,
     resource_tables: PrimaryMap<TypeResourceTableIndex, TypeResourceTable>,
 
-    module_types: ModuleTypes,
+    module_types: Option<ModuleTypes>,
 }
 
 impl ComponentTypes {
     /// Returns the core wasm module types known within this component.
     pub fn module_types(&self) -> &ModuleTypes {
-        &self.module_types
+        self.module_types.as_ref().unwrap()
     }
 
     /// Returns the canonical ABI information about the specified type.
@@ -341,7 +341,7 @@ where
 {
     type Output = <ModuleTypes as Index<T>>::Output;
     fn index(&self, idx: T) -> &Self::Output {
-        self.module_types.index(idx)
+        self.module_types.as_ref().unwrap().index(idx)
     }
 }
 
@@ -359,7 +359,6 @@ where
 ///
 /// This contains tables to intern any component types found as well as
 /// managing building up core wasm [`ModuleTypes`] as well.
-#[derive(Default)]
 pub struct ComponentTypesBuilder {
     functions: HashMap<TypeFunc, TypeFuncIndex>,
     lists: HashMap<TypeList, TypeListIndex>,
@@ -398,6 +397,26 @@ macro_rules! intern_and_fill_flat_types {
 }
 
 impl ComponentTypesBuilder {
+    /// Construct a new `ComponentTypesBuilder` for use with the given validator.
+    pub fn new(validator: &Validator) -> Self {
+        Self {
+            module_types: ModuleTypesBuilder::new(validator),
+
+            functions: HashMap::default(),
+            lists: HashMap::default(),
+            records: HashMap::default(),
+            variants: HashMap::default(),
+            tuples: HashMap::default(),
+            enums: HashMap::default(),
+            flags: HashMap::default(),
+            options: HashMap::default(),
+            results: HashMap::default(),
+            component_types: ComponentTypes::default(),
+            type_info: TypeInformationCache::default(),
+            resources: ResourcesBuilder::default(),
+        }
+    }
+
     fn export_type_def(
         &mut self,
         static_modules: &PrimaryMap<StaticModuleIndex, CompiledModuleInfo>,
@@ -457,7 +476,7 @@ impl ComponentTypesBuilder {
         }
         let ty = self.component_types.components.push(component_ty);
 
-        self.component_types.module_types = self.module_types.finish();
+        self.component_types.module_types = Some(self.module_types.finish());
         (self.component_types, ty)
     }
 
@@ -517,6 +536,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentFuncTypeId,
     ) -> Result<TypeFuncIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ty = &types[id];
         let params = ty
             .params
@@ -542,6 +562,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: types::ComponentEntityType,
     ) -> Result<TypeDef> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         Ok(match ty {
             types::ComponentEntityType::Module(id) => {
                 TypeDef::Module(self.convert_module(types, id)?)
@@ -574,6 +595,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentAnyTypeId,
     ) -> Result<TypeDef> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         Ok(match id {
             types::ComponentAnyTypeId::Defined(id) => {
                 TypeDef::Interface(self.defined_type(types, id)?)
@@ -598,6 +620,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentTypeId,
     ) -> Result<TypeComponentIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ty = &types[id];
         let mut result = TypeComponent::default();
         for (name, ty) in ty.imports.iter() {
@@ -620,6 +643,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentInstanceTypeId,
     ) -> Result<TypeComponentInstanceIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ty = &types[id];
         let mut result = TypeComponentInstance::default();
         for (name, ty) in ty.exports.iter() {
@@ -636,6 +660,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentCoreModuleTypeId,
     ) -> Result<TypeModuleIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ty = &types[id];
         let mut result = TypeModule::default();
         for ((module, field), ty) in ty.imports.iter() {
@@ -657,16 +682,14 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::EntityType,
     ) -> Result<EntityType> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         Ok(match ty {
-            types::EntityType::Func(idx) => {
-                let ty = types[*idx].unwrap_func();
-                let ty = self.convert_func_type(ty);
-                EntityType::Function(
-                    self.module_types_builder_mut()
-                        .wasm_func_type(*idx, ty)
-                        .into(),
-                )
-            }
+            types::EntityType::Func(id) => EntityType::Function({
+                let module = Module::default();
+                self.module_types_builder_mut()
+                    .intern_type(&module, types, *id)?
+                    .into()
+            }),
             types::EntityType::Table(ty) => EntityType::Table(self.convert_table_type(ty)),
             types::EntityType::Memory(ty) => EntityType::Memory(ty.clone().into()),
             types::EntityType::Global(ty) => EntityType::Global(self.convert_global_type(ty)),
@@ -679,6 +702,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         id: types::ComponentDefinedTypeId,
     ) -> Result<InterfaceType> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ret = match &types[id] {
             types::ComponentDefinedType::Primitive(ty) => ty.into(),
             types::ComponentDefinedType::Record(e) => {
@@ -718,6 +742,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::ComponentValType,
     ) -> Result<InterfaceType> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         match ty {
             types::ComponentValType::Primitive(p) => Ok(p.into()),
             types::ComponentValType::Type(id) => self.defined_type(types, *id),
@@ -729,6 +754,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::RecordType,
     ) -> Result<TypeRecordIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let fields = ty
             .fields
             .iter()
@@ -752,6 +778,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::VariantType,
     ) -> Result<TypeVariantIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let cases = ty
             .cases
             .iter()
@@ -783,6 +810,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::TupleType,
     ) -> Result<TypeTupleIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let types = ty
             .types
             .iter()
@@ -822,6 +850,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::ComponentValType,
     ) -> Result<TypeOptionIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ty = self.valtype(types, ty)?;
         let (info, abi) = VariantInfo::new([None, Some(self.component_types.canonical_abi(&ty))]);
         Ok(self.add_option_type(TypeOption { ty, abi, info }))
@@ -833,6 +862,7 @@ impl ComponentTypesBuilder {
         ok: &Option<types::ComponentValType>,
         err: &Option<types::ComponentValType>,
     ) -> Result<TypeResultIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let ok = match ok {
             Some(ty) => Some(self.valtype(types, ty)?),
             None => None,
@@ -853,6 +883,7 @@ impl ComponentTypesBuilder {
         types: types::TypesRef<'_>,
         ty: &types::ComponentValType,
     ) -> Result<TypeListIndex> {
+        assert_eq!(types.id(), self.module_types.validator_id());
         let element = self.valtype(types, ty)?;
         Ok(self.add_list_type(TypeList { element }))
     }
diff --git a/crates/environ/src/module.rs b/crates/environ/src/module.rs
index e4f22f0db..bc63c1ceb 100644
--- a/crates/environ/src/module.rs
+++ b/crates/environ/src/module.rs
@@ -476,26 +476,6 @@ pub enum TableElementExpression {
     Null,
 }
 
-/// Different types that can appear in a module.
-///
-/// Note that each of these variants are intended to index further into a
-/// separate table.
-#[derive(Debug, Copy, Clone, Serialize, Deserialize)]
-#[allow(missing_docs)]
-pub enum ModuleType {
-    Function(ModuleInternedTypeIndex),
-}
-
-impl ModuleType {
-    /// Asserts this is a `ModuleType::Function`, returning the underlying
-    /// `SignatureIndex`.
-    pub fn unwrap_function(&self) -> ModuleInternedTypeIndex {
-        match self {
-            ModuleType::Function(f) => *f,
-        }
-    }
-}
-
 /// A translated WebAssembly module, excluding the function bodies and
 /// memory initializers.
 #[derive(Default, Debug, Serialize, Deserialize)]
@@ -528,7 +508,7 @@ pub struct Module {
     pub passive_data_map: BTreeMap<DataIndex, Range<u32>>,
 
     /// Types declared in the wasm module.
-    pub types: PrimaryMap<TypeIndex, ModuleType>,
+    pub types: PrimaryMap<TypeIndex, ModuleInternedTypeIndex>,
 
     /// Number of imported or aliased functions in the module.
     pub num_imported_funcs: usize,
diff --git a/crates/environ/src/module_environ.rs b/crates/environ/src/module_environ.rs
index 77e96db9c..0c119ae74 100644
--- a/crates/environ/src/module_environ.rs
+++ b/crates/environ/src/module_environ.rs
@@ -1,6 +1,6 @@
 use crate::module::{
     FuncRefIndex, Initializer, MemoryInitialization, MemoryInitializer, MemoryPlan, Module,
-    ModuleType, TableElementExpression, TablePlan, TableSegment, TableSegmentElements,
+    TableElementExpression, TablePlan, TableSegment, TableSegmentElements,
 };
 use crate::{
     DataIndex, DefinedFuncIndex, ElemIndex, EntityIndex, EntityType, FuncIndex, GlobalIndex,
@@ -15,11 +15,10 @@ use std::collections::HashMap;
 use std::mem;
 use std::path::PathBuf;
 use std::sync::Arc;
-use wasmparser::types::{CoreTypeId, Types};
 use wasmparser::{
-    CompositeType, CustomSectionReader, DataKind, ElementItems, ElementKind, Encoding,
-    ExternalKind, FuncToValidate, FunctionBody, NameSectionReader, Naming, Operator, Parser,
-    Payload, TypeRef, Validator, ValidatorResources, WasmFeatures,
+    types::Types, CustomSectionReader, DataKind, ElementItems, ElementKind, Encoding, ExternalKind,
+    FuncToValidate, FunctionBody, NameSectionReader, Naming, Operator, Parser, Payload, TypeRef,
+    Validator, ValidatorResources, WasmFeatures,
 };
 use wasmtime_types::ModuleInternedTypeIndex;
 
@@ -236,14 +235,56 @@ impl<'a, 'data> ModuleEnvironment<'a, 'data> {
 
             Payload::TypeSection(types) => {
                 self.validator.type_section(&types)?;
-                let num = usize::try_from(types.count()).unwrap();
-                self.result.module.types.reserve(num);
-                self.types.reserve_wasm_signatures(num);
-
-                for i in 0..types.count() {
-                    let types = self.validator.types(0).unwrap();
-                    let ty = types.core_type_at(i);
-                    self.declare_type(ty.unwrap_sub())?;
+
+                let count = types.count();
+                let capacity = usize::try_from(count).unwrap();
+                self.result.module.types.reserve(capacity);
+                self.types.reserve_wasm_signatures(capacity);
+
+                // Iterate over each *rec group* -- not type -- defined in the
+                // types section. Rec groups are the unit of canonicalization
+                // and therefore the unit at which we need to process at a
+                // time. `wasmparser` has already done the hard work of
+                // de-duplicating and canonicalizing the rec groups within the
+                // module for us, we just need to translate them into our data
+                // structures. Note that, if the Wasm defines duplicate rec
+                // groups, we need copy the duplicates over (shallowly) as well,
+                // so that our types index space doesn't have holes.
+                let mut type_index = 0;
+                for _ in 0..count {
+                    let validator_types = self.validator.types(0).unwrap();
+
+                    // Get the rec group for the current type index, which is
+                    // always the first type defined in a rec group.
+                    let core_type_id = validator_types.core_type_at(type_index).unwrap_sub();
+                    log::trace!(
+                        "about to intern rec group for {core_type_id:?} = {:?}",
+                        validator_types[core_type_id]
+                    );
+                    let rec_group_id = validator_types.rec_group_id_of(core_type_id);
+                    debug_assert_eq!(
+                        validator_types
+                            .rec_group_elements(rec_group_id)
+                            .position(|id| id == core_type_id),
+                        Some(0)
+                    );
+
+                    // Intern the rec group and then fill in this module's types
+                    // index space.
+                    let interned = self.types.intern_rec_group(
+                        &self.result.module,
+                        validator_types,
+                        rec_group_id,
+                    )?;
+                    let elems = self.types.rec_group_elements(interned);
+                    let len = elems.len();
+                    self.result.module.types.reserve(len);
+                    for ty in elems {
+                        self.result.module.types.push(ty);
+                    }
+
+                    // Advance `type_index` to the start of the next rec group.
+                    type_index += u32::try_from(len).unwrap();
                 }
             }
 
@@ -258,11 +299,11 @@ impl<'a, 'data> ModuleEnvironment<'a, 'data> {
                     let ty = match import.ty {
                         TypeRef::Func(index) => {
                             let index = TypeIndex::from_u32(index);
-                            let sig_index = self.result.module.types[index].unwrap_function();
+                            let interned_index = self.result.module.types[index];
                             self.result.module.num_imported_funcs += 1;
                             self.result.debuginfo.wasm_file.imported_func_count += 1;
                             EntityType::Function(wasmtime_types::EngineOrModuleTypeIndex::Module(
-                                sig_index,
+                                interned_index,
                             ))
                         }
                         TypeRef::Memory(ty) => {
@@ -294,8 +335,8 @@ impl<'a, 'data> ModuleEnvironment<'a, 'data> {
                 for entry in functions {
                     let sigindex = entry?;
                     let ty = TypeIndex::from_u32(sigindex);
-                    let sig_index = self.result.module.types[ty].unwrap_function();
-                    self.result.module.push_function(sig_index);
+                    let interned_index = self.result.module.types[ty];
+                    self.result.module.push_function(interned_index);
                 }
             }
 
@@ -842,25 +883,6 @@ and for re-adding support for interface types you can see this issue:
         self.result.module.num_escaped_funcs += 1;
     }
 
-    fn declare_type(&mut self, id: CoreTypeId) -> WasmResult<()> {
-        let types = self.validator.types(0).unwrap();
-        let ty = &types[id];
-        assert!(ty.is_final);
-        assert!(ty.supertype_idx.is_none());
-        match &ty.composite_type {
-            CompositeType::Func(ty) => {
-                let wasm = self.convert_func_type(ty);
-                let sig_index = self.types.wasm_func_type(id, wasm);
-                self.result
-                    .module
-                    .types
-                    .push(ModuleType::Function(sig_index));
-            }
-            CompositeType::Array(_) | CompositeType::Struct(_) => unimplemented!(),
-        }
-        Ok(())
-    }
-
     /// Parses the Name section of the wasm module.
     fn name_section(&mut self, names: NameSectionReader<'data>) -> WasmResult<()> {
         for subsection in names {
@@ -933,11 +955,7 @@ and for re-adding support for interface types you can see this issue:
 
 impl TypeConvert for ModuleEnvironment<'_, '_> {
     fn lookup_heap_type(&self, index: wasmparser::UnpackedIndex) -> WasmHeapType {
-        WasmparserTypeConverter {
-            types: &self.types,
-            module: &self.result.module,
-        }
-        .lookup_heap_type(index)
+        WasmparserTypeConverter::new(&self.types, &self.result.module).lookup_heap_type(index)
     }
 }
 
diff --git a/crates/environ/src/module_types.rs b/crates/environ/src/module_types.rs
index 06d11e772..693175e8f 100644
--- a/crates/environ/src/module_types.rs
+++ b/crates/environ/src/module_types.rs
@@ -1,10 +1,15 @@
-use crate::{Module, ModuleType, PrimaryMap, TypeConvert, WasmFuncType, WasmHeapType};
+use crate::{Module, PrimaryMap, TypeConvert, TypeIndex, WasmFuncType, WasmHeapType};
+use cranelift_entity::EntityRef;
 use serde_derive::{Deserialize, Serialize};
-use std::collections::HashMap;
-use std::ops::Index;
-use wasmparser::types::CoreTypeId;
-use wasmparser::UnpackedIndex;
-use wasmtime_types::{EngineOrModuleTypeIndex, ModuleInternedTypeIndex, TypeIndex};
+use std::{
+    collections::HashMap,
+    ops::{Index, Range},
+};
+use wasmparser::{CompositeType, UnpackedIndex, Validator, ValidatorId};
+use wasmtime_types::{
+    wasm_unsupported, EngineOrModuleTypeIndex, ModuleInternedRecGroupIndex,
+    ModuleInternedTypeIndex, WasmResult,
+};
 
 /// All types used in a core wasm module.
 ///
@@ -14,17 +19,42 @@ use wasmtime_types::{EngineOrModuleTypeIndex, ModuleInternedTypeIndex, TypeIndex
 /// Note that accesing this type is primarily done through the `Index`
 /// implementations for this type.
 #[derive(Default, Serialize, Deserialize)]
-#[allow(missing_docs)]
 pub struct ModuleTypes {
+    rec_groups: PrimaryMap<ModuleInternedRecGroupIndex, Range<ModuleInternedTypeIndex>>,
     wasm_types: PrimaryMap<ModuleInternedTypeIndex, WasmFuncType>,
 }
 
 impl ModuleTypes {
     /// Returns an iterator over all the wasm function signatures found within
     /// this module.
-    pub fn wasm_types(&self) -> impl Iterator<Item = (ModuleInternedTypeIndex, &WasmFuncType)> {
+    pub fn wasm_types(
+        &self,
+    ) -> impl ExactSizeIterator<Item = (ModuleInternedTypeIndex, &WasmFuncType)> {
         self.wasm_types.iter()
     }
+
+    /// Get the type at the specified index.
+    pub fn get(&self, ty: ModuleInternedTypeIndex) -> &WasmFuncType {
+        &self.wasm_types[ty]
+    }
+
+    /// Get an iterator over all recursion groups defined in this module and
+    /// their elements.
+    pub fn rec_groups(
+        &self,
+    ) -> impl ExactSizeIterator<Item = (ModuleInternedRecGroupIndex, Range<ModuleInternedTypeIndex>)> + '_
+    {
+        self.rec_groups.iter().map(|(k, v)| (k, v.clone()))
+    }
+
+    /// Get the elements within an already-defined rec group.
+    pub fn rec_group_elements(
+        &self,
+        rec_group: ModuleInternedRecGroupIndex,
+    ) -> impl ExactSizeIterator<Item = ModuleInternedTypeIndex> {
+        let range = &self.rec_groups[rec_group];
+        (range.start.as_u32()..range.end.as_u32()).map(|i| ModuleInternedTypeIndex::from_u32(i))
+    }
 }
 
 impl Index<ModuleInternedTypeIndex> for ModuleTypes {
@@ -35,38 +65,235 @@ impl Index<ModuleInternedTypeIndex> for ModuleTypes {
     }
 }
 
+/// A type marking the start of a recursion group's definition.
+///
+/// This is initialized by `ModuleTypesBuilder::start_rec_group` and then
+/// finished in `ModuleTypes::end_rec_group` after all of the types in the rec
+/// group have been defined.
+struct RecGroupStart {
+    rec_group_index: ModuleInternedRecGroupIndex,
+    start: ModuleInternedTypeIndex,
+    end: ModuleInternedTypeIndex,
+}
+
 /// A builder for [`ModuleTypes`].
-#[derive(Default)]
-#[allow(missing_docs)]
 pub struct ModuleTypesBuilder {
+    /// The ID of the validator that this builder is configured for. Using a
+    /// different validator, or multiple validators, with this builder would
+    /// result in silliness because our `wasmparser::types::*Id`s are only
+    /// unique within the context of a particular validator. Getting this wrong
+    /// could result in generating calls to functions of the wrong type, for
+    /// example. So therefore we always assert that a builder instances is only
+    /// ever paired with a particular validator context.
+    validator_id: ValidatorId,
+
+    /// The canonicalized and deduplicated set of types we are building.
     types: ModuleTypes,
-    interned_func_types: HashMap<WasmFuncType, ModuleInternedTypeIndex>,
-    wasmparser_to_wasmtime: HashMap<CoreTypeId, ModuleInternedTypeIndex>,
+
+    /// A map from already-interned `wasmparser` types to their corresponding
+    /// Wasmtime type.
+    wasmparser_to_wasmtime: HashMap<wasmparser::types::CoreTypeId, ModuleInternedTypeIndex>,
+
+    /// The set of recursion groups we have already seen and interned.
+    already_seen: HashMap<wasmparser::types::RecGroupId, ModuleInternedRecGroupIndex>,
+
+    /// If we are in the middle of defining a recursion group, this is the
+    /// metadata about the recursion group we started defining.
+    defining_rec_group: Option<RecGroupStart>,
 }
 
 impl ModuleTypesBuilder {
+    /// Construct a new `ModuleTypesBuilder` using the given validator.
+    pub fn new(validator: &Validator) -> Self {
+        Self {
+            validator_id: validator.id(),
+            types: ModuleTypes::default(),
+            wasmparser_to_wasmtime: HashMap::default(),
+            already_seen: HashMap::default(),
+            defining_rec_group: None,
+        }
+    }
+
     /// Reserves space for `amt` more type signatures.
     pub fn reserve_wasm_signatures(&mut self, amt: usize) {
         self.types.wasm_types.reserve(amt);
+        self.wasmparser_to_wasmtime.reserve(amt);
+        self.already_seen.reserve(amt);
     }
 
-    /// Interns the `sig` specified and returns a unique `SignatureIndex` that
-    /// can be looked up within [`ModuleTypes`] to recover the [`WasmFuncType`]
-    /// at runtime.
-    pub fn wasm_func_type(&mut self, id: CoreTypeId, sig: WasmFuncType) -> ModuleInternedTypeIndex {
-        let sig = self.intern_func_type(sig);
-        self.wasmparser_to_wasmtime.insert(id, sig);
-        sig
+    /// Get the id of the validator that this builder is configured for.
+    pub fn validator_id(&self) -> ValidatorId {
+        self.validator_id
     }
 
-    fn intern_func_type(&mut self, sig: WasmFuncType) -> ModuleInternedTypeIndex {
-        if let Some(idx) = self.interned_func_types.get(&sig) {
-            return *idx;
+    /// Intern a recursion group and all of its types into this builder.
+    ///
+    /// If the recursion group has already been interned, then it is reused.
+    ///
+    /// Panics if given types from a different validator than the one that this
+    /// builder is associated with.
+    pub fn intern_rec_group(
+        &mut self,
+        module: &Module,
+        validator_types: wasmparser::types::TypesRef<'_>,
+        rec_group_id: wasmparser::types::RecGroupId,
+    ) -> WasmResult<ModuleInternedRecGroupIndex> {
+        assert_eq!(validator_types.id(), self.validator_id);
+
+        if let Some(interned) = self.already_seen.get(&rec_group_id) {
+            return Ok(*interned);
         }
 
-        let idx = self.types.wasm_types.push(sig.clone());
-        self.interned_func_types.insert(sig, idx);
-        return idx;
+        self.define_new_rec_group(module, validator_types, rec_group_id)
+    }
+
+    /// Define a new recursion group that we haven't already interned.
+    fn define_new_rec_group(
+        &mut self,
+        module: &Module,
+        validator_types: wasmparser::types::TypesRef<'_>,
+        rec_group_id: wasmparser::types::RecGroupId,
+    ) -> WasmResult<ModuleInternedRecGroupIndex> {
+        assert_eq!(validator_types.id(), self.validator_id);
+
+        self.start_rec_group(
+            validator_types,
+            validator_types.rec_group_elements(rec_group_id),
+        );
+
+        for id in validator_types.rec_group_elements(rec_group_id) {
+            let ty = &validator_types[id];
+            if ty.supertype_idx.is_some() {
+                return Err(wasm_unsupported!("wasm gc: explicit subtyping"));
+            }
+            match &ty.composite_type {
+                CompositeType::Func(ty) => {
+                    let wasm_ty = WasmparserTypeConverter::new(self, module).convert_func_type(ty);
+                    self.wasm_func_type_in_rec_group(id, wasm_ty);
+                }
+                CompositeType::Array(_) => return Err(wasm_unsupported!("wasm gc: array types")),
+                CompositeType::Struct(_) => return Err(wasm_unsupported!("wasm gc: struct types")),
+            }
+        }
+
+        Ok(self.end_rec_group(rec_group_id))
+    }
+
+    /// Start defining a recursion group.
+    fn start_rec_group(
+        &mut self,
+        validator_types: wasmparser::types::TypesRef<'_>,
+        elems: impl ExactSizeIterator<Item = wasmparser::types::CoreTypeId>,
+    ) {
+        log::trace!("Starting rec group of length {}", elems.len());
+
+        assert!(self.defining_rec_group.is_none());
+        assert_eq!(validator_types.id(), self.validator_id);
+
+        // Eagerly define the reverse map's entries for this rec group's types
+        // so that we can use them when converting `wasmparser` types to our
+        // types.
+        let len = elems.len();
+        for (i, wasmparser_id) in elems.enumerate() {
+            let interned = ModuleInternedTypeIndex::new(self.types.wasm_types.len() + i);
+            log::trace!(
+                "Reserving {interned:?} for {wasmparser_id:?} = {:?}",
+                validator_types[wasmparser_id]
+            );
+
+            let old_entry = self.wasmparser_to_wasmtime.insert(wasmparser_id, interned);
+            debug_assert_eq!(
+                old_entry, None,
+                "should not have already inserted {wasmparser_id:?}"
+            );
+        }
+
+        self.defining_rec_group = Some(RecGroupStart {
+            rec_group_index: self.types.rec_groups.next_key(),
+            start: self.types.wasm_types.next_key(),
+            end: ModuleInternedTypeIndex::new(self.types.wasm_types.len() + len),
+        });
+    }
+
+    /// Finish defining a recursion group.
+    fn end_rec_group(
+        &mut self,
+        rec_group_id: wasmparser::types::RecGroupId,
+    ) -> ModuleInternedRecGroupIndex {
+        let RecGroupStart {
+            rec_group_index,
+            start,
+            end,
+        } = self
+            .defining_rec_group
+            .take()
+            .expect("should be defining a rec group");
+
+        log::trace!("Ending rec group {start:?}..{end:?}");
+
+        debug_assert!(start.index() < self.types.wasm_types.len());
+        debug_assert_eq!(
+            end,
+            self.types.wasm_types.next_key(),
+            "should have defined the number of types declared in `start_rec_group`"
+        );
+
+        let idx = self.types.rec_groups.push(start..end);
+        debug_assert_eq!(idx, rec_group_index);
+
+        self.already_seen.insert(rec_group_id, rec_group_index);
+        rec_group_index
+    }
+
+    /// Intern a type into this builder and get its Wasmtime index.
+    ///
+    /// This will intern not only the single given type, but the type's entire
+    /// rec group. This helper method is provided as a convenience so that
+    /// callers don't have to get the type's rec group, intern the rec group,
+    /// and then look up the Wasmtime index for the original type themselves.
+    pub fn intern_type(
+        &mut self,
+        module: &Module,
+        validator_types: wasmparser::types::TypesRef<'_>,
+        id: wasmparser::types::CoreTypeId,
+    ) -> WasmResult<ModuleInternedTypeIndex> {
+        assert!(self.defining_rec_group.is_none());
+        assert_eq!(validator_types.id(), self.validator_id);
+
+        let rec_group_id = validator_types.rec_group_id_of(id);
+        debug_assert!(validator_types
+            .rec_group_elements(rec_group_id)
+            .any(|e| e == id));
+
+        let interned_rec_group = self.intern_rec_group(module, validator_types, rec_group_id)?;
+
+        let interned_type = self.wasmparser_to_wasmtime[&id];
+        debug_assert!(self
+            .rec_group_elements(interned_rec_group)
+            .any(|e| e == interned_type));
+
+        Ok(interned_type)
+    }
+
+    /// Define a new Wasm function type while we are defining a rec group.
+    fn wasm_func_type_in_rec_group(
+        &mut self,
+        id: wasmparser::types::CoreTypeId,
+        func_ty: WasmFuncType,
+    ) -> ModuleInternedTypeIndex {
+        assert!(
+            self.defining_rec_group.is_some(),
+            "must be defining a rec group to define new types"
+        );
+
+        let module_interned_index = self.types.wasm_types.push(func_ty);
+        debug_assert_eq!(
+            self.wasmparser_to_wasmtime.get(&id),
+            Some(&module_interned_index),
+            "should have reserved the right module-interned index for this wasmparser type already"
+        );
+
+        module_interned_index
     }
 
     /// Returns the result [`ModuleTypes`] of this builder.
@@ -74,6 +301,14 @@ impl ModuleTypesBuilder {
         self.types
     }
 
+    /// Get the elements within an already-defined rec group.
+    pub fn rec_group_elements(
+        &self,
+        rec_group: ModuleInternedRecGroupIndex,
+    ) -> impl ExactSizeIterator<Item = ModuleInternedTypeIndex> {
+        self.types.rec_group_elements(rec_group)
+    }
+
     /// Returns an iterator over all the wasm function signatures found within
     /// this module.
     pub fn wasm_signatures(
@@ -95,10 +330,17 @@ where
     }
 }
 
-#[allow(missing_docs)]
+/// A convert from `wasmparser` types to Wasmtime types.
 pub struct WasmparserTypeConverter<'a> {
-    pub types: &'a ModuleTypesBuilder,
-    pub module: &'a Module,
+    types: &'a ModuleTypesBuilder,
+    module: &'a Module,
+}
+
+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 }
+    }
 }
 
 impl TypeConvert for WasmparserTypeConverter<'_> {
@@ -108,15 +350,12 @@ impl TypeConvert for WasmparserTypeConverter<'_> {
                 let signature = self.types.wasmparser_to_wasmtime[&id];
                 WasmHeapType::Concrete(EngineOrModuleTypeIndex::Module(signature))
             }
-            UnpackedIndex::RecGroup(_) => unreachable!(),
-            UnpackedIndex::Module(i) => {
-                let i = TypeIndex::from_u32(i);
-                match self.module.types[i] {
-                    ModuleType::Function(sig) => {
-                        WasmHeapType::Concrete(EngineOrModuleTypeIndex::Module(sig))
-                    }
-                }
+            UnpackedIndex::Module(module_index) => {
+                let module_index = TypeIndex::from_u32(module_index);
+                let interned_index = self.module.types[module_index];
+                WasmHeapType::Concrete(EngineOrModuleTypeIndex::Module(interned_index))
             }
+            UnpackedIndex::RecGroup(_) => unreachable!(),
         }
     }
 }
diff --git a/crates/types/src/lib.rs b/crates/types/src/lib.rs
index 81d1c5e70..b9c7a67fb 100644
--- a/crates/types/src/lib.rs
+++ b/crates/types/src/lib.rs
@@ -5,7 +5,7 @@ pub use wasmparser;
 
 use cranelift_entity::entity_impl;
 use serde_derive::{Deserialize, Serialize};
-use std::fmt;
+use std::{fmt, ops::Range};
 
 mod error;
 pub use error::*;
@@ -29,10 +29,28 @@ pub trait TypeTrace {
     where
         F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>;
 
+    /// Trace all `VMSharedTypeIndex` edges, ignoring other edges.
+    fn trace_engine_indices<F, E>(&self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(VMSharedTypeIndex) -> Result<(), E>,
+    {
+        self.trace(&mut |idx| match idx {
+            EngineOrModuleTypeIndex::Engine(idx) => func(idx),
+            EngineOrModuleTypeIndex::Module(_) | EngineOrModuleTypeIndex::RecGroup(_) => Ok(()),
+        })
+    }
+
     /// Canonicalize `self` by rewriting all type references inside `self` from
     /// module-level interned type indices to engine-level interned type
     /// indices.
-    fn canonicalize<F>(&mut self, module_to_engine: &mut F)
+    ///
+    /// This produces types that are suitable for usage by the runtime (only
+    /// contains `VMSharedTypeIndex` type references).
+    ///
+    /// This does not produce types that are suitable for hash consing types
+    /// (must have recgroup-relative indices for type indices referencing other
+    /// types in the same recgroup).
+    fn canonicalize_for_runtime_usage<F>(&mut self, module_to_engine: &mut F)
     where
         F: FnMut(ModuleInternedTypeIndex) -> VMSharedTypeIndex,
     {
@@ -43,9 +61,72 @@ pub trait TypeTrace {
                 *idx = EngineOrModuleTypeIndex::Engine(engine_index);
                 Ok(())
             }
+            EngineOrModuleTypeIndex::RecGroup(_) => {
+                panic!("should not already be canonicalized for hash consing")
+            }
         })
         .unwrap()
     }
+
+    /// Is this type canonicalized for runtime usage?
+    fn is_canonicalized_for_runtime_usage(&self) -> bool {
+        self.trace(&mut |idx| match idx {
+            EngineOrModuleTypeIndex::Engine(_) => Ok(()),
+            EngineOrModuleTypeIndex::Module(_) | EngineOrModuleTypeIndex::RecGroup(_) => Err(()),
+        })
+        .is_ok()
+    }
+
+    /// Canonicalize `self` by rewriting all type references inside `self` from
+    /// module-level interned type indices to either engine-level interned type
+    /// indices or recgroup-relative indices.
+    ///
+    /// This produces types that are suitable for hash consing and deduplicating
+    /// recgroups (types may have recgroup-relative indices for references to
+    /// other types within the same recgroup).
+    ///
+    /// This does *not* produce types that are suitable for usage by the runtime
+    /// (only contain `VMSharedTypeIndex` type references).
+    fn canonicalize_for_hash_consing<F>(
+        &mut self,
+        rec_group_range: Range<ModuleInternedTypeIndex>,
+        module_to_engine: &mut F,
+    ) where
+        F: FnMut(ModuleInternedTypeIndex) -> VMSharedTypeIndex,
+    {
+        self.trace_mut::<_, ()>(&mut |idx| match *idx {
+            EngineOrModuleTypeIndex::Engine(_) => Ok(()),
+            EngineOrModuleTypeIndex::Module(module_index) => {
+                *idx = if rec_group_range.start <= module_index {
+                    // Any module index within the recursion group gets
+                    // translated into a recgroup-relative index.
+                    debug_assert!(module_index < rec_group_range.end);
+                    let relative = module_index.as_u32() - rec_group_range.start.as_u32();
+                    let relative = RecGroupRelativeTypeIndex::from_u32(relative);
+                    EngineOrModuleTypeIndex::RecGroup(relative)
+                } else {
+                    // Cross-group indices are translated directly into
+                    // `VMSharedTypeIndex`es.
+                    debug_assert!(module_index < rec_group_range.start);
+                    EngineOrModuleTypeIndex::Engine(module_to_engine(module_index))
+                };
+                Ok(())
+            }
+            EngineOrModuleTypeIndex::RecGroup(_) => {
+                panic!("should not already be canonicalized for hash consing")
+            }
+        })
+        .unwrap()
+    }
+
+    /// Is this type canonicalized for hash consing?
+    fn is_canonicalized_for_hash_consing(&self) -> bool {
+        self.trace(&mut |idx| match idx {
+            EngineOrModuleTypeIndex::Engine(_) | EngineOrModuleTypeIndex::RecGroup(_) => Ok(()),
+            EngineOrModuleTypeIndex::Module(_) => Err(()),
+        })
+        .is_ok()
+    }
 }
 
 /// WebAssembly value type -- equivalent of `wasmparser::ValType`.
@@ -193,9 +274,15 @@ pub enum EngineOrModuleTypeIndex {
     /// An index within an engine, canonicalized among all modules that can
     /// interact with each other.
     Engine(VMSharedTypeIndex),
+
     /// An index within the current Wasm module, canonicalized within just this
     /// current module.
     Module(ModuleInternedTypeIndex),
+
+    /// An index within the containing type's rec group. This is only used when
+    /// hashing and canonicalizing rec groups, and should never appear outside
+    /// of the engine's type registry.
+    RecGroup(RecGroupRelativeTypeIndex),
 }
 
 impl From<ModuleInternedTypeIndex> for EngineOrModuleTypeIndex {
@@ -209,6 +296,7 @@ impl fmt::Display for EngineOrModuleTypeIndex {
         match self {
             Self::Engine(i) => write!(f, "(engine {})", i.bits()),
             Self::Module(i) => write!(f, "(module {})", i.as_u32()),
+            Self::RecGroup(i) => write!(f, "(recgroup {})", i.as_u32()),
         }
     }
 }
@@ -223,14 +311,14 @@ impl EngineOrModuleTypeIndex {
     pub fn as_engine_type_index(self) -> Option<VMSharedTypeIndex> {
         match self {
             Self::Engine(e) => Some(e),
-            Self::Module(_) => None,
+            Self::RecGroup(_) | Self::Module(_) => None,
         }
     }
 
     /// Get the underlying engine-level type index, or panic.
     pub fn unwrap_engine_type_index(self) -> VMSharedTypeIndex {
         self.as_engine_type_index()
-            .expect("`unwrap_engine_type_index` on module type index")
+            .unwrap_or_else(|| panic!("`unwrap_engine_type_index` on {self:?}"))
     }
 
     /// Is this an module-level type index?
@@ -242,14 +330,33 @@ impl EngineOrModuleTypeIndex {
     pub fn as_module_type_index(self) -> Option<ModuleInternedTypeIndex> {
         match self {
             Self::Module(e) => Some(e),
-            Self::Engine(_) => None,
+            Self::RecGroup(_) | Self::Engine(_) => None,
         }
     }
 
     /// Get the underlying module-level type index, or panic.
     pub fn unwrap_module_type_index(self) -> ModuleInternedTypeIndex {
         self.as_module_type_index()
-            .expect("`unwrap_module_type_index` on engine type index")
+            .unwrap_or_else(|| panic!("`unwrap_module_type_index` on {self:?}"))
+    }
+
+    /// Is this an recgroup-level type index?
+    pub fn is_rec_group_type_index(self) -> bool {
+        matches!(self, Self::RecGroup(_))
+    }
+
+    /// Get the underlying recgroup-level type index, if any.
+    pub fn as_rec_group_type_index(self) -> Option<RecGroupRelativeTypeIndex> {
+        match self {
+            Self::RecGroup(r) => Some(r),
+            Self::Module(_) | Self::Engine(_) => None,
+        }
+    }
+
+    /// Get the underlying module-level type index, or panic.
+    pub fn unwrap_rec_group_type_index(self) -> RecGroupRelativeTypeIndex {
+        self.as_rec_group_type_index()
+            .unwrap_or_else(|| panic!("`unwrap_rec_group_type_index` on {self:?}"))
     }
 }
 
@@ -406,6 +513,44 @@ impl WasmFuncType {
     }
 }
 
+/// A recursive type group.
+///
+/// Types within a recgroup can have forward references to each other, which
+/// allows for cyclic types, for example a function `$f` that returns a
+/// reference to a function `$g` which returns a reference to a function `$f`:
+///
+/// ```ignore
+/// (rec (type (func $f (result (ref null $g))))
+///      (type (func $g (result (ref null $f)))))
+/// ```
+#[derive(Debug, Clone, Eq, PartialEq, Hash, Serialize, Deserialize)]
+pub struct WasmRecGroup {
+    /// The types inside of this recgroup.
+    pub types: Box<[WasmFuncType]>,
+}
+
+impl TypeTrace for WasmRecGroup {
+    fn trace<F, E>(&self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        for ty in self.types.iter() {
+            ty.trace(func)?;
+        }
+        Ok(())
+    }
+
+    fn trace_mut<F, E>(&mut self, func: &mut F) -> Result<(), E>
+    where
+        F: FnMut(&mut EngineOrModuleTypeIndex) -> Result<(), E>,
+    {
+        for ty in self.types.iter_mut() {
+            ty.trace_mut(func)?;
+        }
+        Ok(())
+    }
+}
+
 /// Index type of a function (imported or defined) inside the WebAssembly module.
 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Serialize, Deserialize)]
 pub struct FuncIndex(u32);
@@ -451,11 +596,32 @@ entity_impl!(GlobalIndex);
 pub struct MemoryIndex(u32);
 entity_impl!(MemoryIndex);
 
+/// Index type of a canonicalized recursive type group inside a WebAssembly
+/// module (as opposed to canonicalized within the whole engine).
+#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Serialize, Deserialize)]
+pub struct ModuleInternedRecGroupIndex(u32);
+entity_impl!(ModuleInternedRecGroupIndex);
+
+/// Index type of a canonicalized recursive type group inside the whole engine
+/// (as opposed to canonicalized within just a single Wasm module).
+#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Serialize, Deserialize)]
+pub struct EngineInternedRecGroupIndex(u32);
+entity_impl!(EngineInternedRecGroupIndex);
+
 /// Index type of a type (imported or defined) inside the WebAssembly module.
 #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Serialize, Deserialize)]
 pub struct TypeIndex(u32);
 entity_impl!(TypeIndex);
 
+/// A canonicalized type index referencing a type within a single recursion
+/// group from another type within that same recursion group.
+///
+/// This is only suitable for use when hash consing and deduplicating rec
+/// groups.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug, Serialize, Deserialize)]
+pub struct RecGroupRelativeTypeIndex(u32);
+entity_impl!(RecGroupRelativeTypeIndex);
+
 /// A canonicalized type index for a type within a single WebAssembly module.
 ///
 /// Note that this is deduplicated only at the level of a single WebAssembly
diff --git a/crates/wasmtime/src/compile.rs b/crates/wasmtime/src/compile.rs
index c2994850b..15e316e31 100644
--- a/crates/wasmtime/src/compile.rs
+++ b/crates/wasmtime/src/compile.rs
@@ -34,8 +34,8 @@ use wasmtime_environ::component::Translator;
 use wasmtime_environ::{
     BuiltinFunctionIndex, CompiledFunctionInfo, CompiledModuleInfo, Compiler, DefinedFuncIndex,
     FinishedObject, FunctionBodyData, ModuleEnvironment, ModuleInternedTypeIndex,
-    ModuleTranslation, ModuleType, ModuleTypes, ModuleTypesBuilder, ObjectKind, PrimaryMap,
-    RelocationTarget, StaticModuleIndex, WasmFunctionInfo,
+    ModuleTranslation, ModuleTypes, ModuleTypesBuilder, ObjectKind, PrimaryMap, RelocationTarget,
+    StaticModuleIndex, WasmFunctionInfo,
 };
 
 mod code_builder;
@@ -68,9 +68,9 @@ pub(crate) fn build_artifacts<T: FinishedObject>(
     // about the wasm module. This is where the WebAssembly is parsed and
     // validated. Afterwards `types` will have all the type information for
     // this module.
-    let mut validator = wasmparser::Validator::new_with_features(engine.config().features.clone());
     let parser = wasmparser::Parser::new(0);
-    let mut types = Default::default();
+    let mut validator = wasmparser::Validator::new_with_features(engine.config().features.clone());
+    let mut types = ModuleTypesBuilder::new(&validator);
     let mut translation = ModuleEnvironment::new(tunables, &mut validator, &mut types)
         .translate(parser, wasm)
         .context("failed to parse WebAssembly module")?;
@@ -122,7 +122,9 @@ pub(crate) fn build_component_artifacts<T: FinishedObject>(
     engine: &Engine,
     binary: &[u8],
 ) -> Result<(T, Option<wasmtime_environ::component::ComponentArtifacts>)> {
-    use wasmtime_environ::component::{CompiledComponentInfo, ComponentArtifacts};
+    use wasmtime_environ::component::{
+        CompiledComponentInfo, ComponentArtifacts, ComponentTypesBuilder,
+    };
     use wasmtime_environ::ScopeVec;
 
     let tunables = engine.tunables();
@@ -130,7 +132,7 @@ pub(crate) fn build_component_artifacts<T: FinishedObject>(
 
     let scope = ScopeVec::new();
     let mut validator = wasmparser::Validator::new_with_features(engine.config().features.clone());
-    let mut types = Default::default();
+    let mut types = ComponentTypesBuilder::new(&validator);
     let (component, mut module_translations) =
         Translator::new(tunables, &mut validator, &mut types, &scope)
             .translate(binary)
@@ -481,9 +483,7 @@ impl<'a> CompileInputs<'a> {
                 }
             }
 
-            sigs.extend(translation.module.types.iter().map(|(_, ty)| match ty {
-                ModuleType::Function(ty) => *ty,
-            }));
+            sigs.extend(translation.module.types.iter().map(|(_, ty)| *ty));
         }
 
         for signature in sigs {
@@ -825,9 +825,7 @@ impl FunctionIndices {
                     .module
                     .types
                     .iter()
-                    .map(|(_, ty)| match ty {
-                        ModuleType::Function(ty) => *ty,
-                    })
+                    .map(|(_, ty)| *ty)
                     .collect::<BTreeSet<_>>();
                 let wasm_to_native_trampolines = unique_and_sorted_sigs
                     .iter()
diff --git a/crates/wasmtime/src/runtime/component/instance.rs b/crates/wasmtime/src/runtime/component/instance.rs
index 6ade89cd4..7a10c3cc6 100644
--- a/crates/wasmtime/src/runtime/component/instance.rs
+++ b/crates/wasmtime/src/runtime/component/instance.rs
@@ -319,11 +319,11 @@ impl<'a> Instantiator<'a> {
         // below, but the funcrefs can all be configured here.
         for (idx, sig) in env_component.trampolines.iter() {
             let ptrs = self.component.trampoline_ptrs(idx);
-            let signature = self
-                .component
-                .signatures()
-                .shared_type(*sig)
-                .expect("found unregistered signature");
+            let signature = match self.component.signatures().shared_type(*sig) {
+                Some(s) => s,
+                None => panic!("found unregistered signature: {sig:?}"),
+            };
+
             self.data.state.set_trampoline(
                 idx,
                 ptrs.wasm_call,
@@ -468,8 +468,8 @@ impl<'a> Instantiator<'a> {
             // made, so double-check this property of wasmtime in debug mode.
 
             if cfg!(debug_assertions) {
-                let (_, _, expected) = imports.next().unwrap();
-                self.assert_type_matches(store, module, arg, expected);
+                let (imp_module, imp_name, expected) = imports.next().unwrap();
+                self.assert_type_matches(store, module, arg, imp_module, imp_name, expected);
             }
 
             // The unsafety here should be ok since the `export` is loaded
@@ -490,6 +490,8 @@ impl<'a> Instantiator<'a> {
         store: &mut StoreOpaque,
         module: &Module,
         arg: &CoreDef,
+        imp_module: &str,
+        imp_name: &str,
         expected: EntityType,
     ) {
         let export = self.data.lookup_def(store, arg);
@@ -502,9 +504,18 @@ impl<'a> Instantiator<'a> {
             let expected = match expected.unwrap_func() {
                 EngineOrModuleTypeIndex::Engine(e) => Some(e),
                 EngineOrModuleTypeIndex::Module(m) => module.signatures().shared_type(m),
+                EngineOrModuleTypeIndex::RecGroup(_) => unreachable!(),
             };
             let actual = unsafe { f.func_ref.as_ref().type_index };
-            assert_eq!(expected, Some(actual));
+            assert_eq!(
+                expected,
+                Some(actual),
+                "type mismatch for import {imp_module:?} {imp_name:?}!!!\n\n\
+                 expected {:#?}\n\n\
+                 found {:#?}",
+                expected.and_then(|e| store.engine().signatures().borrow(e)),
+                store.engine().signatures().borrow(actual)
+            );
             return;
         }
 
diff --git a/crates/wasmtime/src/runtime/externals/global.rs b/crates/wasmtime/src/runtime/externals/global.rs
index 2b471c161..5f78ca9ad 100644
--- a/crates/wasmtime/src/runtime/externals/global.rs
+++ b/crates/wasmtime/src/runtime/externals/global.rs
@@ -227,7 +227,7 @@ impl Global {
         wasmtime_export
             .global
             .wasm_ty
-            .canonicalize(&mut |module_index| {
+            .canonicalize_for_runtime_usage(&mut |module_index| {
                 wasmtime_runtime::Instance::from_vmctx(wasmtime_export.vmctx, |instance| {
                     instance.engine_type_index(module_index)
                 })
diff --git a/crates/wasmtime/src/runtime/externals/table.rs b/crates/wasmtime/src/runtime/externals/table.rs
index 648362178..81b386f76 100644
--- a/crates/wasmtime/src/runtime/externals/table.rs
+++ b/crates/wasmtime/src/runtime/externals/table.rs
@@ -403,7 +403,7 @@ impl Table {
             .table
             .table
             .wasm_ty
-            .canonicalize(&mut |module_index| {
+            .canonicalize_for_runtime_usage(&mut |module_index| {
                 wasmtime_runtime::Instance::from_vmctx(wasmtime_export.vmctx, |instance| {
                     instance.engine_type_index(module_index)
                 })
diff --git a/crates/wasmtime/src/runtime/instance.rs b/crates/wasmtime/src/runtime/instance.rs
index 5d55fb888..c018d864d 100644
--- a/crates/wasmtime/src/runtime/instance.rs
+++ b/crates/wasmtime/src/runtime/instance.rs
@@ -982,7 +982,7 @@ fn typecheck<I>(
     }
     let cx = matching::MatchCx::new(module.engine());
     for ((name, field, mut expected_ty), actual) in env_module.imports().zip(imports) {
-        expected_ty.canonicalize(&mut |module_index| {
+        expected_ty.canonicalize_for_runtime_usage(&mut |module_index| {
             module.signatures().shared_type(module_index).unwrap()
         });
 
diff --git a/crates/wasmtime/src/runtime/trampoline/table.rs b/crates/wasmtime/src/runtime/trampoline/table.rs
index 5950b51ae..4128c8fc4 100644
--- a/crates/wasmtime/src/runtime/trampoline/table.rs
+++ b/crates/wasmtime/src/runtime/trampoline/table.rs
@@ -2,7 +2,7 @@ use crate::store::{InstanceId, StoreOpaque};
 use crate::trampoline::create_handle;
 use crate::TableType;
 use anyhow::Result;
-use wasmtime_environ::{EngineOrModuleTypeIndex, EntityIndex, Module, TypeTrace};
+use wasmtime_environ::{EntityIndex, Module, TypeTrace};
 
 pub fn create_table(store: &mut StoreOpaque, table: &TableType) -> Result<InstanceId> {
     let mut module = Module::new();
@@ -10,17 +10,11 @@ pub fn create_table(store: &mut StoreOpaque, table: &TableType) -> Result<Instan
     let wasmtime_table = table.wasmtime_table().clone();
     let tunables = store.engine().tunables();
 
-    if cfg!(debug_assertions) {
-        wasmtime_table
-            .wasm_ty
-            .trace(&mut |idx| match idx {
-                EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                EngineOrModuleTypeIndex::Module(module_idx) => Err(format!(
-                    "found module-level canonicalized type index: {module_idx:?}"
-                )),
-            })
-            .expect("element type should be engine-level canonicalized");
-    }
+    debug_assert!(
+        wasmtime_table.wasm_ty.is_canonicalized_for_runtime_usage(),
+        "should be canonicalized for runtime usage: {:?}",
+        wasmtime_table.wasm_ty
+    );
 
     let table_plan = wasmtime_environ::TablePlan::for_table(wasmtime_table, tunables);
     let table_id = module.table_plans.push(table_plan);
diff --git a/crates/wasmtime/src/runtime/type_registry.rs b/crates/wasmtime/src/runtime/type_registry.rs
index a8c1b291b..4262a40eb 100644
--- a/crates/wasmtime/src/runtime/type_registry.rs
+++ b/crates/wasmtime/src/runtime/type_registry.rs
@@ -1,7 +1,7 @@
 //! Implement a registry of types: function, struct, and array definitions.
 //!
 //! Helps implement fast indirect call signature checking, reference type
-//! casting, and etc.
+//! downcasting, and etc...
 
 use crate::Engine;
 use std::{
@@ -9,7 +9,7 @@ use std::{
     collections::{HashMap, HashSet},
     fmt::Debug,
     hash::{Hash, Hasher},
-    ops::Deref,
+    ops::Range,
     sync::{
         atomic::{
             AtomicUsize,
@@ -19,18 +19,13 @@ use std::{
     },
 };
 use wasmtime_environ::{
-    EngineOrModuleTypeIndex, ModuleInternedTypeIndex, ModuleTypes, PrimaryMap, TypeTrace,
-    VMSharedTypeIndex, WasmFuncType,
+    iter_entity_range, EngineOrModuleTypeIndex, ModuleInternedTypeIndex, ModuleTypes, PrimaryMap,
+    TypeTrace, VMSharedTypeIndex, WasmFuncType, WasmRecGroup,
 };
 use wasmtime_slab::{Id as SlabId, Slab};
 
 // ### Notes on the Lifetime Management of Types
 //
-// (The below refers to recursion groups even though at the time of writing we
-// don't support Wasm GC yet, which introduced recursion groups. Until that
-// time, you can think of each type implicitly being in a singleton recursion
-// group, so types and recursion groups are effectively one to one.)
-//
 // All defined types from all Wasm modules loaded into Wasmtime are interned
 // into their engine's `TypeRegistry`.
 //
@@ -38,18 +33,18 @@ use wasmtime_slab::{Id as SlabId, Slab};
 // cared about canonicalizing types so that `call_indirect` was fast and we
 // didn't waste memory on many copies of the same function type definition.
 // Function types could only take and return simple scalars (i32/f64/etc...) and
-// there were no type-to-type references. We could simply deduplicate types and
-// reference count their entries in the registry.
+// there were no type-to-type references. We could simply deduplicate function
+// types and reference count their entries in the registry.
 //
 // The typed function references and GC proposals change everything. The former
 // introduced function types that take a reference to a function of another
 // specific type. This is a type-to-type reference. The latter introduces struct
 // and array types that can have references to other struct, array, and function
 // types, as well as recursion groups that allow cyclic references between
-// types. Now type canonicalization additionally enables fast type checks
-// *across* modules: so that two modules which define the same struct type, for
-// example, can pass instances of that struct type to each other, and we can
-// quickly check that those instances are in fact of the expected types.
+// types. Now type canonicalization additionally enables fast type checks and
+// downcasts *across* modules: so that two modules which define the same struct
+// type, for example, can pass instances of that struct type to each other, and
+// we can quickly check that those instances are in fact of the expected types.
 //
 // But how do we manage the lifetimes of types that can reference other types as
 // Wasm modules are dynamically loaded and unloaded from the engine? These
@@ -87,6 +82,7 @@ use wasmtime_slab::{Id as SlabId, Slab};
 /// when dropped.
 pub struct TypeCollection {
     engine: Engine,
+    rec_groups: Vec<RecGroupEntry>,
     types: PrimaryMap<ModuleInternedTypeIndex, VMSharedTypeIndex>,
     reverse_types: HashMap<VMSharedTypeIndex, ModuleInternedTypeIndex>,
 }
@@ -95,10 +91,12 @@ impl Debug for TypeCollection {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         let TypeCollection {
             engine: _,
+            rec_groups,
             types,
             reverse_types: _,
         } = self;
         f.debug_struct("TypeCollection")
+            .field("rec_groups", rec_groups)
             .field("types", types)
             .finish_non_exhaustive()
     }
@@ -109,11 +107,12 @@ impl TypeCollection {
     pub fn new_for_module(engine: &Engine, types: &ModuleTypes) -> Self {
         let engine = engine.clone();
         let registry = engine.signatures();
-        let types = registry.0.write().unwrap().register_for_module(types);
+        let (rec_groups, types) = registry.0.write().unwrap().register_module_types(types);
         let reverse_types = types.iter().map(|(k, v)| (*v, k)).collect();
 
         Self {
             engine,
+            rec_groups,
             types,
             reverse_types,
         }
@@ -142,7 +141,7 @@ impl TypeCollection {
 
 impl Drop for TypeCollection {
     fn drop(&mut self) {
-        if !self.types.is_empty() {
+        if !self.rec_groups.is_empty() {
             self.engine
                 .signatures()
                 .0
@@ -173,14 +172,22 @@ fn slab_id_to_shared_type_index(id: SlabId) -> VMSharedTypeIndex {
 /// Dereferences to its underlying `WasmFuncType`.
 pub struct RegisteredType {
     engine: Engine,
-    entry: Entry,
+    entry: RecGroupEntry,
+    ty: Arc<WasmFuncType>,
+    index: VMSharedTypeIndex,
 }
 
 impl Debug for RegisteredType {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        let RegisteredType { engine: _, entry } = self;
+        let RegisteredType {
+            engine: _,
+            entry: _,
+            ty,
+            index,
+        } = self;
         f.debug_struct("RegisteredType")
-            .field("entry", entry)
+            .field("index", index)
+            .field("ty", ty)
             .finish_non_exhaustive()
     }
 }
@@ -191,6 +198,8 @@ impl Clone for RegisteredType {
         RegisteredType {
             engine: self.engine.clone(),
             entry: self.entry.clone(),
+            ty: self.ty.clone(),
+            index: self.index,
         }
     }
 }
@@ -203,7 +212,7 @@ impl Drop for RegisteredType {
                 .0
                 .write()
                 .unwrap()
-                .unregister_entry(self.entry.0.index);
+                .unregister_entry(self.entry.clone());
         }
     }
 }
@@ -212,7 +221,7 @@ impl std::ops::Deref for RegisteredType {
     type Target = WasmFuncType;
 
     fn deref(&self) -> &Self::Target {
-        &self.entry.0.ty
+        &self.ty
     }
 }
 
@@ -223,11 +232,9 @@ impl PartialEq for RegisteredType {
         if cfg!(debug_assertions) {
             if eq {
                 assert!(Engine::same(&self.engine, &other.engine));
+                assert_eq!(self.ty, other.ty);
             } else {
-                assert!(
-                    self.entry.0.index != other.entry.0.index
-                        || !Engine::same(&self.engine, &other.engine)
-                );
+                assert!(self.ty != other.ty || !Engine::same(&self.engine, &other.engine));
             }
         }
 
@@ -248,23 +255,29 @@ impl RegisteredType {
     /// Constructs a new `RegisteredType`, registering the given type with the
     /// engine's `TypeRegistry`.
     pub fn new(engine: &Engine, ty: WasmFuncType) -> RegisteredType {
-        let entry = {
+        let (entry, index, ty) = {
+            log::trace!("RegisteredType::new({ty:?})");
+
             let mut inner = engine.signatures().0.write().unwrap();
 
-            log::trace!("RegisteredType::new({ty:?})");
+            // It shouldn't be possible for users to construct non-canonical
+            // types via the embedding API, and the only other types they can
+            // get are already-canonicalized types from modules, so we shouldn't
+            // ever get non-canonical types here. Furthermore, this is only
+            // called internally to Wasmtime, so we shouldn't ever have an
+            // engine mismatch; those should be caught earlier.
+            inner.assert_canonicalized_for_runtime_usage_in_this_registry(&ty);
 
-            // It shouldn't be possible for users to construct non-canonical types
-            // via the embedding API, and the only other types they can get are
-            // already-canonicalized types from modules, so we shouldn't ever get
-            // non-canonical types here.
-            assert!(
-                inner.is_canonicalized(&ty),
-                "ty is not already canonicalized: {ty:?}"
-            );
+            let entry = inner.register_singleton_rec_group(ty);
 
-            inner.register_canonicalized(ty)
+            let index = entry.0.shared_type_indices[0];
+            let id = shared_type_index_to_slab_id(index);
+            let ty = inner.types[id].clone();
+
+            (entry, index, ty)
         };
-        RegisteredType::from_parts(engine.clone(), entry)
+
+        RegisteredType::from_parts(engine.clone(), entry, index, ty)
     }
 
     /// Create an owning handle to the given index's associated type.
@@ -275,10 +288,12 @@ impl RegisteredType {
     /// Returns `None` if `index` is not registered in the given engine's
     /// registry.
     pub fn root(engine: &Engine, index: VMSharedTypeIndex) -> Option<RegisteredType> {
-        let entry = {
+        let (entry, ty) = {
             let id = shared_type_index_to_slab_id(index);
             let inner = engine.signatures().0.read().unwrap();
-            let e = inner.entries.get(id)?;
+
+            let ty = inner.types.get(id)?.clone();
+            let entry = inner.type_to_rec_group[&index].clone();
 
             // NB: make sure to incref while the lock is held to prevent:
             //
@@ -286,26 +301,36 @@ impl RegisteredType {
             // * Other thread: drops `RegisteredType` for entry E, decref
             //   reaches zero, write locks registry, unregisters entry
             // * This thread: increfs entry, but it isn't in the registry anymore
-            e.incref("RegisteredType::root");
+            entry.incref("RegisteredType::root");
 
-            e.clone()
+            (entry, ty)
         };
 
-        Some(RegisteredType::from_parts(engine.clone(), entry))
+        Some(RegisteredType::from_parts(engine.clone(), entry, index, ty))
     }
 
     /// Construct a new `RegisteredType`.
     ///
     /// It is the caller's responsibility to ensure that the entry's reference
     /// count has already been incremented.
-    fn from_parts(engine: Engine, entry: Entry) -> Self {
+    fn from_parts(
+        engine: Engine,
+        entry: RecGroupEntry,
+        index: VMSharedTypeIndex,
+        ty: Arc<WasmFuncType>,
+    ) -> Self {
         debug_assert!(entry.0.registrations.load(Acquire) != 0);
-        RegisteredType { engine, entry }
+        RegisteredType {
+            engine,
+            entry,
+            ty,
+            index,
+        }
     }
 
     /// Get this registered type's index.
     pub fn index(&self) -> VMSharedTypeIndex {
-        self.entry.0.index
+        self.index
     }
 
     /// Get the engine whose registry this type is registered within.
@@ -314,55 +339,66 @@ impl RegisteredType {
     }
 }
 
-/// A Wasm function type, its `VMSharedTypeIndex`, and its registration count.
-#[derive(Debug)]
-struct EntryInner {
-    ty: WasmFuncType,
-    index: VMSharedTypeIndex,
-    registrations: AtomicUsize,
-}
-
+/// An entry in the type registry.
+///
 /// Implements `Borrow`, `Eq`, and `Hash` by forwarding to the underlying Wasm
-/// function type, so that this can be a hash consing key in
-/// `TypeRegistryInner::map`.
-#[derive(Clone, Debug)]
-struct Entry(Arc<EntryInner>);
+/// rec group, so that this can be a hash consing key. (We can't use
+/// `Arc<RecGroupEntryInner>` directly for this purpose because `Arc<T>` doesn't
+/// implement `Borrow<U>` when `T: Borrow<U>`).
+#[derive(Clone)]
+struct RecGroupEntry(Arc<RecGroupEntryInner>);
 
-impl Deref for Entry {
-    type Target = WasmFuncType;
+impl Debug for RecGroupEntry {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+        struct Ptr<'a, P>(&'a P);
+        impl<P: std::fmt::Pointer> Debug for Ptr<'_, P> {
+            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+                write!(f, "{:#p}", *self.0)
+            }
+        }
 
-    fn deref(&self) -> &Self::Target {
-        &self.0.ty
+        f.debug_struct("RecGroupEntry")
+            .field("ptr", &Ptr(&self.0))
+            .field("shared_type_indices", &self.0.shared_type_indices)
+            .field("hash_consing_key", &self.0.hash_consing_key)
+            .field("registrations", &self.0.registrations.load(Acquire))
+            .finish()
     }
 }
 
-impl PartialEq for Entry {
+struct RecGroupEntryInner {
+    /// The Wasm rec group, canonicalized for hash consing.
+    hash_consing_key: WasmRecGroup,
+    shared_type_indices: Box<[VMSharedTypeIndex]>,
+    registrations: AtomicUsize,
+}
+
+impl PartialEq for RecGroupEntry {
     fn eq(&self, other: &Self) -> bool {
-        self.0.ty == other.0.ty
+        self.0.hash_consing_key == other.0.hash_consing_key
     }
 }
 
-impl Eq for Entry {}
+impl Eq for RecGroupEntry {}
 
-impl Hash for Entry {
+impl Hash for RecGroupEntry {
     fn hash<H: Hasher>(&self, state: &mut H) {
-        self.0.ty.hash(state);
+        self.0.hash_consing_key.hash(state);
     }
 }
 
-impl Borrow<WasmFuncType> for Entry {
-    fn borrow(&self) -> &WasmFuncType {
-        &self.0.ty
+impl Borrow<WasmRecGroup> for RecGroupEntry {
+    fn borrow(&self) -> &WasmRecGroup {
+        &self.0.hash_consing_key
     }
 }
 
-impl Entry {
+impl RecGroupEntry {
     /// Increment the registration count.
     fn incref(&self, why: &str) {
         let old_count = self.0.registrations.fetch_add(1, AcqRel);
         log::trace!(
-            "increment registration count for {:?} (registrations -> {}): {why}",
-            self.0.index,
+            "increment registration count for {self:?} (registrations -> {}): {why}",
             old_count + 1
         );
     }
@@ -374,8 +410,7 @@ impl Entry {
         let old_count = self.0.registrations.fetch_sub(1, AcqRel);
         debug_assert_ne!(old_count, 0);
         log::trace!(
-            "decrement registration count for {:?} (registrations -> {}): {why}",
-            self.0.index,
+            "decrement registration count for {self:?} (registrations -> {}): {why}",
             old_count - 1
         );
         old_count == 1
@@ -384,156 +419,272 @@ impl Entry {
 
 #[derive(Debug, Default)]
 struct TypeRegistryInner {
-    // A map from the Wasm function type to a `VMSharedTypeIndex`, for all
-    // the Wasm function types we have already registered.
-    map: HashSet<Entry>,
+    // A hash map from a canonicalized-for-hash-consing rec group to its
+    // `VMSharedTypeIndex`es.
+    //
+    // There is an entry in this map for every rec group we have already
+    // registered. Before registering new rec groups, we first check this map to
+    // see if we've already registered an identical rec group that we should
+    // reuse instead.
+    hash_consing_map: HashSet<RecGroupEntry>,
 
     // A map from `VMSharedTypeIndex::bits()` to the type index's associated
     // Wasm type.
-    entries: Slab<Entry>,
+    //
+    // These types are always canonicalized for runtime usage.
+    types: Slab<Arc<WasmFuncType>>,
+
+    // A map that lets you walk backwards from a `VMSharedTypeIndex` to its
+    // `RecGroupEntry`.
+    type_to_rec_group: HashMap<VMSharedTypeIndex, RecGroupEntry>,
 
     // An explicit stack of entries that we are in the middle of dropping. Used
     // to avoid recursion when dropping a type that is holding the last
     // reference to another type, etc...
-    drop_stack: Vec<VMSharedTypeIndex>,
+    drop_stack: Vec<RecGroupEntry>,
 }
 
 impl TypeRegistryInner {
-    fn register_for_module(
+    fn register_module_types(
         &mut self,
         types: &ModuleTypes,
-    ) -> PrimaryMap<ModuleInternedTypeIndex, VMSharedTypeIndex> {
-        log::trace!("Registering module types");
-        let mut map = PrimaryMap::default();
-        for (idx, ty) in types.wasm_types() {
-            let mut ty = ty.clone();
-            self.canonicalize(&map, &mut ty);
-            let entry = self.register_canonicalized(ty);
-            let map_idx = map.push(entry.0.index);
-            assert_eq!(idx, map_idx);
-        }
-        map
-    }
+    ) -> (
+        Vec<RecGroupEntry>,
+        PrimaryMap<ModuleInternedTypeIndex, VMSharedTypeIndex>,
+    ) {
+        log::trace!("Start registering module types");
 
-    /// Is the given type canonicalized for this registry?
-    fn is_canonicalized(&self, ty: &WasmFuncType) -> bool {
-        let result = ty.trace::<_, ()>(&mut |index| match index {
-            EngineOrModuleTypeIndex::Module(_) => Err(()),
-            EngineOrModuleTypeIndex::Engine(id) => {
-                let id = shared_type_index_to_slab_id(id);
-                assert!(
-                    self.entries.contains(id),
-                    "canonicalized in a different engine? {ty:?}"
-                );
-                Ok(())
+        let mut entries = Vec::with_capacity(types.rec_groups().len());
+        let mut map = PrimaryMap::<ModuleInternedTypeIndex, VMSharedTypeIndex>::with_capacity(
+            types.wasm_types().len(),
+        );
+
+        for (_rec_group_index, module_group) in types.rec_groups() {
+            let entry = self.register_rec_group(
+                &map,
+                module_group.clone(),
+                iter_entity_range(module_group.clone()).map(|ty| types.get(ty).clone()),
+            );
+
+            for (module_ty, engine_ty) in
+                iter_entity_range(module_group).zip(entry.0.shared_type_indices.iter())
+            {
+                let module_ty2 = map.push(*engine_ty);
+                assert_eq!(module_ty, module_ty2);
             }
-        });
-        result.is_ok()
+
+            entries.push(entry);
+        }
+
+        log::trace!("End registering module types");
+
+        (entries, map)
     }
 
-    /// Canonicalize a type, such that its type-to-type references are via
-    /// engine-level `VMSharedTypeIndex`es rather than module-local via
-    /// `ModuleInternedTypeIndex`es.
+    /// Register a rec group in this registry.
     ///
-    /// This makes the type suitable for deduplication in the registry.
+    /// The rec group may be either module-level canonical (i.e. straight from
+    /// `wasmparser`) or engine-level canonicalized for runtime usage in this
+    /// registry. It may *not* be engine-level canonicalized for hash consing or
+    /// engine-level canonicalized for a different type registry instance.
     ///
-    /// Panics on already-canonicalized types. They might be canonicalized for
-    /// another engine's registry, and we wouldn't know how to recanonicalize
-    /// them for this registry.
-    fn canonicalize(
-        &self,
-        module_to_shared: &PrimaryMap<ModuleInternedTypeIndex, VMSharedTypeIndex>,
-        ty: &mut WasmFuncType,
-    ) {
-        ty.canonicalize(&mut |module_index| module_to_shared[module_index]);
-        debug_assert!(self.is_canonicalized(ty))
-    }
-
-    /// Add a new type to this registry.
+    /// If this rec group is determined to be a duplicate of an
+    /// already-registered rec group, the existing rec group is reused.
     ///
-    /// The type must be canonicalized and must not already exist in the
-    /// registry.
+    /// Parameters:
     ///
-    /// Initializes the new entry's registration count to one, and callers
-    /// should not further increment the registration count.
-    fn register_new(&mut self, ty: WasmFuncType) -> Entry {
-        assert!(
-            self.is_canonicalized(&ty),
-            "ty is not already canonicalized: {ty:?}"
-        );
+    /// * `map`: A map that we use to canonicalize inter-group type references
+    ///   from module-canonical to engine-canonical indices. This must contain
+    ///   entries for each inter-group type reference that this rec group
+    ///   contains.
+    ///
+    /// * `range`: The range of (module-level) types defined by this rec
+    ///   group. This is used to determine which type references inside this rec
+    ///   group are inter- vs intra-group.
+    ///
+    /// * `types`: The types defined within this rec group. Must have the same
+    ///   length as `range`.
+    ///
+    /// The returned entry will have already had its reference count incremented
+    /// on behalf of callers.
+    fn register_rec_group(
+        &mut self,
+        map: &PrimaryMap<ModuleInternedTypeIndex, VMSharedTypeIndex>,
+        range: Range<ModuleInternedTypeIndex>,
+        types: impl ExactSizeIterator<Item = WasmFuncType>,
+    ) -> RecGroupEntry {
+        debug_assert_eq!(iter_entity_range(range.clone()).len(), types.len());
+
+        let mut non_canon_types = Vec::with_capacity(types.len());
+        let hash_consing_key = WasmRecGroup {
+            types: types
+                .zip(iter_entity_range(range.clone()))
+                .map(|(mut ty, module_index)| {
+                    non_canon_types.push((module_index, ty.clone()));
+                    ty.canonicalize_for_hash_consing(range.clone(), &mut |idx| {
+                        debug_assert!(idx < range.clone().start);
+                        map[idx]
+                    });
+                    ty
+                })
+                .collect::<Box<[_]>>(),
+        };
 
-        // Increment the ref count of each existing type that is referenced from
-        // this new type. Those types shouldn't be dropped while this type is
-        // still alive.
-        ty.trace::<_, ()>(&mut |idx| match idx {
-            EngineOrModuleTypeIndex::Engine(id) => {
-                let i = shared_type_index_to_slab_id(id);
-                let e = &self.entries[i];
-                e.incref("new type references existing type in TypeRegistryInner::register_new");
-                Ok(())
-            }
-            EngineOrModuleTypeIndex::Module(_) => unreachable!("should be canonicalized"),
-        })
-        .unwrap();
+        // If we've already registered this rec group before, reuse it.
+        if let Some(entry) = self.hash_consing_map.get(&hash_consing_key) {
+            entry.incref(
+                "hash consed to already-registered type in `TypeRegistryInner::register_rec_group`",
+            );
+            return entry.clone();
+        }
 
-        let id = self.entries.next_id();
-        let index = slab_id_to_shared_type_index(id);
-        log::trace!("create {index:?} = {ty:?} (registrations -> 1)");
-        let entry = Entry(Arc::new(EntryInner {
-            ty,
-            index,
+        // Inter-group edges: increment the referenced group's ref
+        // count, because these other rec groups shouldn't be dropped
+        // while this rec group is still alive.
+        hash_consing_key
+            .trace_engine_indices::<_, ()>(&mut |index| {
+                let entry = &self.type_to_rec_group[&index];
+                entry.incref(
+                    "new cross-group type reference to existing type in `register_rec_group`",
+                );
+                Ok(())
+            })
+            .unwrap();
+
+        // Register the individual types.
+        //
+        // Note that we can't update the reverse type-to-rec-group map until
+        // after we've constructed the `RecGroupEntry`, since that map needs to
+        // the fully-constructed entry for its values.
+        let module_rec_group_start = range.start;
+        let engine_rec_group_start = u32::try_from(self.types.len()).unwrap();
+        let shared_type_indices = non_canon_types
+            .into_iter()
+            .map(|(module_index, mut ty)| {
+                ty.canonicalize_for_runtime_usage(&mut |idx| {
+                    if idx < module_rec_group_start {
+                        map[idx]
+                    } else {
+                        let rec_group_offset = idx.as_u32() - module_rec_group_start.as_u32();
+                        VMSharedTypeIndex::from_u32(engine_rec_group_start + rec_group_offset)
+                    }
+                });
+                self.insert_one_type_from_rec_group(module_index, ty)
+            })
+            .collect();
+
+        let entry = RecGroupEntry(Arc::new(RecGroupEntryInner {
+            hash_consing_key,
+            shared_type_indices,
             registrations: AtomicUsize::new(1),
         }));
-        let is_new_entry = self.map.insert(entry.clone());
-        assert!(is_new_entry);
+        log::trace!("create new entry {entry:?} (registrations -> 1)");
 
-        let id = self.entries.alloc(entry.clone());
-        assert_eq!(id, shared_type_index_to_slab_id(index));
+        let is_new_entry = self.hash_consing_map.insert(entry.clone());
+        debug_assert!(is_new_entry);
+
+        // Now that we've construct the entry, we can update the reverse
+        // type-to-rec-group map.
+        for ty in entry.0.shared_type_indices.iter() {
+            let old_entry = self.type_to_rec_group.insert(*ty, entry.clone());
+            debug_assert!(old_entry.is_none());
+        }
 
         entry
     }
 
-    /// Register the given canonicalized type, incrementing its reference count.
-    fn register_canonicalized(&mut self, ty: WasmFuncType) -> Entry {
+    /// Is the given type canonicalized for runtime usage this registry?
+    fn assert_canonicalized_for_runtime_usage_in_this_registry(&self, ty: &WasmFuncType) {
+        ty.trace::<_, ()>(&mut |index| match index {
+            EngineOrModuleTypeIndex::RecGroup(_) | EngineOrModuleTypeIndex::Module(_) => {
+                panic!("not canonicalized for runtime usage: {ty:?}")
+            }
+            EngineOrModuleTypeIndex::Engine(idx) => {
+                let id = shared_type_index_to_slab_id(idx);
+                assert!(
+                    self.types.contains(id),
+                    "canonicalized in a different engine? {ty:?}"
+                );
+                Ok(())
+            }
+        })
+        .unwrap();
+    }
+
+    /// Insert a new type as part of registering a new rec group.
+    ///
+    /// The type must be canonicalized for runtime usage in this registry and
+    /// its rec group must be a new one that we are currently registering, not
+    /// an already-registered rec group.
+    fn insert_one_type_from_rec_group(
+        &mut self,
+        module_index: ModuleInternedTypeIndex,
+        ty: WasmFuncType,
+    ) -> VMSharedTypeIndex {
+        // Despite being canonicalized for runtime usage, this type may still
+        // have forward references to other types in the rec group we haven't
+        // yet registered. Therefore, we can't use our usual
+        // `assert_canonicalized_for_runtime_usage_in_this_registry` helper here
+        // as that will see the forward references and think they must be
+        // references to types in other registries.
         assert!(
-            self.is_canonicalized(&ty),
-            "type is not already canonicalized: {ty:?}"
+            ty.is_canonicalized_for_runtime_usage(),
+            "type is not canonicalized for runtime usage: {ty:?}"
         );
 
-        if let Some(entry) = self.map.get(&ty) {
-            entry.incref(
-                "registering already-registered type in TypeRegistryInner::register_canonicalized",
-            );
-            entry.clone()
-        } else {
-            self.register_new(ty)
-        }
+        let id = self.types.alloc(Arc::new(ty));
+        let engine_index = slab_id_to_shared_type_index(id);
+        log::trace!(
+            "registered type {module_index:?} as {engine_index:?} = {:?}",
+            &self.types[id]
+        );
+        engine_index
+    }
+
+    /// Register a rec group consisting of a single type.
+    ///
+    /// The type must already be canonicalized for runtime usage in this
+    /// registry.
+    ///
+    /// The returned entry will have already had its reference count incremented
+    /// on behalf of callers.
+    fn register_singleton_rec_group(&mut self, ty: WasmFuncType) -> RecGroupEntry {
+        self.assert_canonicalized_for_runtime_usage_in_this_registry(&ty);
+
+        // This type doesn't have any module-level type references, since it is
+        // already canonicalized for runtime usage in this registry, so an empty
+        // map suffices.
+        let map = PrimaryMap::default();
+
+        // This must have `range.len() == 1`, even though we know this type
+        // doesn't have any intra-group type references, to satisfy
+        // `register_rec_group`'s preconditions.
+        let range = ModuleInternedTypeIndex::from_bits(u32::MAX - 1)
+            ..ModuleInternedTypeIndex::from_bits(u32::MAX);
+
+        self.register_rec_group(&map, range, std::iter::once(ty))
     }
 
+    /// Unregister all of a type collection's rec groups.
     fn unregister_type_collection(&mut self, collection: &TypeCollection) {
-        for (_, id) in collection.types.iter() {
-            let i = shared_type_index_to_slab_id(*id);
-            let e = &self.entries[i];
-            if e.decref("TypeRegistryInner::unregister_type_collection") {
-                self.unregister_entry(*id);
+        for entry in &collection.rec_groups {
+            if entry.decref("TypeRegistryInner::unregister_type_collection") {
+                self.unregister_entry(entry.clone());
             }
         }
     }
 
-    /// Remove an entry from the registry.
+    /// Remove a zero-refcount entry from the registry.
     ///
     /// This does *not* decrement the entry's registration count, it should
-    /// instead be invoked after a previous decrement operation observed zero
-    /// remaining registrations.
-    fn unregister_entry(&mut self, index: VMSharedTypeIndex) {
-        log::trace!("unregistering {index:?}");
-
+    /// instead be invoked only after a previous decrement operation observed
+    /// zero remaining registrations.
+    fn unregister_entry(&mut self, entry: RecGroupEntry) {
         debug_assert!(self.drop_stack.is_empty());
-        self.drop_stack.push(index);
+        self.drop_stack.push(entry);
 
-        while let Some(index) = self.drop_stack.pop() {
-            let slab_id = shared_type_index_to_slab_id(index);
-            let entry = &self.entries[slab_id];
+        while let Some(entry) = self.drop_stack.pop() {
+            log::trace!("Start unregistering {entry:?}");
 
             // We need to double check whether the entry is still at zero
             // registrations: Between the time that we observed a zero and
@@ -548,37 +699,52 @@ impl TypeRegistryInner {
             let registrations = entry.0.registrations.load(Acquire);
             if registrations != 0 {
                 log::trace!(
-                    "{index:?} was concurrently resurrected and no longer has zero \
-                     registrations (registrations -> {registrations})"
+                    "{entry:?} was concurrently resurrected and no longer has \
+                     zero registrations (registrations -> {registrations})",
                 );
                 continue;
             }
 
-            // Decrement any other types that this type was
-            // (shallowly/non-transitively) keeping alive.
+            // Decrement any other types that this type was shallowly
+            // (i.e. non-transitively) referencing and keeping alive. If this
+            // was the last thing keeping them registered, its okay to
+            // unregister them as well now.
+            debug_assert!(entry.0.hash_consing_key.is_canonicalized_for_hash_consing());
             entry
                 .0
-                .ty
-                .trace::<_, ()>(&mut |child_index| match child_index {
-                    EngineOrModuleTypeIndex::Engine(child_index) => {
-                        let child_slab_id = shared_type_index_to_slab_id(child_index);
-                        let child_entry = &self.entries[child_slab_id];
-                        if child_entry.decref(
-                            "referenced by unregistered type in TypeCollection::unregister_entry",
-                        ) {
-                            self.drop_stack.push(child_index);
-                        }
-                        Ok(())
-                    }
-                    EngineOrModuleTypeIndex::Module(_) => {
-                        unreachable!("should be canonicalized")
+                .hash_consing_key
+                .trace_engine_indices::<_, ()>(&mut |other_index| {
+                    let other_entry = self.type_to_rec_group[&other_index].clone();
+                    if other_entry.decref(
+                        "referenced by dropped entry in \
+                         `TypeCollection::unregister_entry`",
+                    ) {
+                        self.drop_stack.push(other_entry);
                     }
+                    Ok(())
                 })
                 .unwrap();
 
-            log::trace!("removing {index:?} from registry");
-            self.map.remove(entry);
-            self.entries.dealloc(slab_id);
+            // Remove the entry from the hash-consing map. If we register a
+            // duplicate definition of this rec group again in the future, it
+            // will be as if it is the first time it has ever been registered,
+            // and it will be inserted into the hash-consing map again at that
+            // time.
+            self.hash_consing_map.remove(&entry);
+
+            // Similarly, remove the rec group's types from the registry, as
+            // well as their entries from the reverse type-to-rec-group map.
+            for ty in entry.0.shared_type_indices.iter() {
+                log::trace!("removing {ty:?} from registry");
+
+                let removed_entry = self.type_to_rec_group.remove(ty);
+                debug_assert_eq!(removed_entry.unwrap(), entry);
+
+                let id = shared_type_index_to_slab_id(*ty);
+                self.types.dealloc(id);
+            }
+
+            log::trace!("End unregistering {entry:?}");
         }
     }
 }
@@ -588,13 +754,27 @@ impl TypeRegistryInner {
 #[cfg(debug_assertions)]
 impl Drop for TypeRegistryInner {
     fn drop(&mut self) {
+        let TypeRegistryInner {
+            hash_consing_map,
+            types,
+            type_to_rec_group,
+            drop_stack,
+        } = self;
+        assert!(
+            hash_consing_map.is_empty(),
+            "type registry not empty: hash consing map is not empty"
+        );
+        assert!(
+            types.is_empty(),
+            "type registry not empty: types slab is not empty"
+        );
         assert!(
-            self.map.is_empty(),
-            "type registry not empty: still have registered types in self.map"
+            type_to_rec_group.is_empty(),
+            "type registry not empty: type-to-rec-group map is not empty"
         );
         assert!(
-            self.entries.is_empty(),
-            "type registry not empty: not all entries are vacant"
+            drop_stack.is_empty(),
+            "type registry not empty: drop stack is not empty"
         );
     }
 }
@@ -620,9 +800,9 @@ impl TypeRegistry {
     /// still using the resulting value! Use the `RegisteredType::root`
     /// constructor if you need to ensure that property and you don't have some
     /// other mechanism already keeping the type registered.
-    pub fn borrow(&self, index: VMSharedTypeIndex) -> Option<impl Deref<Target = WasmFuncType>> {
+    pub fn borrow(&self, index: VMSharedTypeIndex) -> Option<Arc<WasmFuncType>> {
         let id = shared_type_index_to_slab_id(index);
         let inner = self.0.read().unwrap();
-        inner.entries.get(id).cloned()
+        inner.types.get(id).cloned()
     }
 }
diff --git a/crates/wasmtime/src/runtime/types.rs b/crates/wasmtime/src/runtime/types.rs
index bf978db76..1cca5e5a9 100644
--- a/crates/wasmtime/src/runtime/types.rs
+++ b/crates/wasmtime/src/runtime/types.rs
@@ -671,7 +671,8 @@ impl HeapType {
             WasmHeapType::Concrete(EngineOrModuleTypeIndex::Engine(idx)) => {
                 HeapType::Concrete(FuncType::from_shared_type_index(engine, *idx))
             }
-            WasmHeapType::Concrete(EngineOrModuleTypeIndex::Module(_)) => {
+            WasmHeapType::Concrete(EngineOrModuleTypeIndex::Module(_))
+            | WasmHeapType::Concrete(EngineOrModuleTypeIndex::RecGroup(_)) => {
                 panic!("HeapType::from_wasm_type on non-canonical heap type")
             }
         }
@@ -769,6 +770,7 @@ impl ExternType {
                 EngineOrModuleTypeIndex::Module(m) => {
                     FuncType::from_wasm_func_type(engine, types[*m].clone()).into()
                 }
+                EngineOrModuleTypeIndex::RecGroup(_) => unreachable!(),
             },
             EntityType::Global(ty) => GlobalType::from_wasmtime_global(engine, ty).into(),
             EntityType::Memory(ty) => MemoryType::from_wasmtime_memory(ty).into(),
@@ -1089,16 +1091,10 @@ impl TableType {
     pub fn new(element: RefType, min: u32, max: Option<u32>) -> TableType {
         let wasm_ty = element.to_wasm_type();
 
-        if cfg!(debug_assertions) {
-            wasm_ty
-                .trace(&mut |idx| match idx {
-                    EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                    EngineOrModuleTypeIndex::Module(module_idx) => Err(format!(
-                        "found module-level canonicalized type index: {module_idx:?}"
-                    )),
-                })
-                .expect("element type should be engine-level canonicalized");
-        }
+        debug_assert!(
+            wasm_ty.is_canonicalized_for_runtime_usage(),
+            "should be canonicalized for runtime usage: {wasm_ty:?}"
+        );
 
         TableType {
             element,
diff --git a/crates/wasmtime/src/runtime/types/matching.rs b/crates/wasmtime/src/runtime/types/matching.rs
index 9b12cae8a..45504aceb 100644
--- a/crates/wasmtime/src/runtime/types/matching.rs
+++ b/crates/wasmtime/src/runtime/types/matching.rs
@@ -1,8 +1,8 @@
 use crate::{linker::DefinitionType, Engine, FuncType};
 use anyhow::{anyhow, bail, Result};
 use wasmtime_environ::{
-    EngineOrModuleTypeIndex, EntityType, Global, Memory, ModuleTypes, Table, TypeTrace,
-    VMSharedTypeIndex, WasmFuncType, WasmHeapType, WasmRefType, WasmValType,
+    EntityType, Global, Memory, ModuleTypes, Table, TypeTrace, VMSharedTypeIndex, WasmFuncType,
+    WasmHeapType, WasmRefType, WasmValType,
 };
 
 pub struct MatchCx<'a> {
@@ -245,25 +245,14 @@ fn match_ref(expected: WasmRefType, actual: WasmRefType, desc: &str) -> Result<(
 fn match_ty(expected: WasmValType, actual: WasmValType, desc: &str) -> Result<()> {
     // Assert that both our types are engine-level canonicalized. We can't
     // compare types otherwise.
-    if cfg!(debug_assertions) {
-        expected
-            .trace(&mut |idx| match idx {
-                EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                EngineOrModuleTypeIndex::Module(mod_idx) => {
-                    Err(format!("found module-level index: {mod_idx:?}"))
-                }
-            })
-            .expect("expected type should be engine-level canonicalized");
-
-        actual
-            .trace(&mut |idx| match idx {
-                EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                EngineOrModuleTypeIndex::Module(mod_idx) => {
-                    Err(format!("found module-level index: {mod_idx:?}"))
-                }
-            })
-            .expect("actual type should be engine-level canonicalized");
-    }
+    debug_assert!(
+        expected.is_canonicalized_for_runtime_usage(),
+        "expected type should be canonicalized for runtime usage: {expected:?}"
+    );
+    debug_assert!(
+        actual.is_canonicalized_for_runtime_usage(),
+        "actual type should be canonicalized for runtime usage: {actual:?}"
+    );
 
     match (actual, expected) {
         (WasmValType::Ref(actual), WasmValType::Ref(expected)) => match_ref(expected, actual, desc),
@@ -274,25 +263,14 @@ fn match_ty(expected: WasmValType, actual: WasmValType, desc: &str) -> Result<()
 fn equal_ty(expected: WasmValType, actual: WasmValType, desc: &str) -> Result<()> {
     // Assert that both our types are engine-level canonicalized. We can't
     // compare types otherwise.
-    if cfg!(debug_assertions) {
-        expected
-            .trace(&mut |idx| match idx {
-                EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                EngineOrModuleTypeIndex::Module(mod_idx) => {
-                    Err(format!("found module-level index: {mod_idx:?}"))
-                }
-            })
-            .expect("expected type should be engine-level canonicalized");
-
-        actual
-            .trace(&mut |idx| match idx {
-                EngineOrModuleTypeIndex::Engine(_) => Ok(()),
-                EngineOrModuleTypeIndex::Module(mod_idx) => {
-                    Err(format!("found module-level index: {mod_idx:?}"))
-                }
-            })
-            .expect("actual type should be engine-level canonicalized");
-    }
+    debug_assert!(
+        expected.is_canonicalized_for_runtime_usage(),
+        "expected type should be canonicalized for runtime usage: {expected:?}"
+    );
+    debug_assert!(
+        actual.is_canonicalized_for_runtime_usage(),
+        "actual type should be canonicalized for runtime usage: {actual:?}"
+    );
 
     if expected == actual {
         return Ok(());
diff --git a/winch/codegen/src/codegen/env.rs b/winch/codegen/src/codegen/env.rs
index 377bbcb72..6818c30f8 100644
--- a/winch/codegen/src/codegen/env.rs
+++ b/winch/codegen/src/codegen/env.rs
@@ -197,8 +197,7 @@ impl<'a, 'translation, 'data, P: PtrSize> FuncEnv<'a, 'translation, 'data, P> {
                 BlockSig::new(control::BlockType::single(ty))
             }
             FuncType(idx) => {
-                let sig_index =
-                    self.translation.module.types[TypeIndex::from_u32(idx)].unwrap_function();
+                let sig_index = self.translation.module.types[TypeIndex::from_u32(idx)];
                 let sig = &self.types[sig_index];
                 BlockSig::new(control::BlockType::func(sig.clone()))
             }
@@ -340,7 +339,7 @@ impl<'a, 'translation, 'data, P: PtrSize> FuncEnv<'a, 'translation, 'data, P> {
             }
             Callee::FuncRef(idx) => {
                 let val = || {
-                    let sig_index = self.translation.module.types[*idx].unwrap_function();
+                    let sig_index = self.translation.module.types[*idx];
                     let ty = &self.types[sig_index];
                     let sig = wasm_sig::<A>(ty);
                     sig
@@ -392,11 +391,8 @@ pub(crate) struct TypeConverter<'a, 'data: 'a> {
 
 impl TypeConvert for TypeConverter<'_, '_> {
     fn lookup_heap_type(&self, idx: wasmparser::UnpackedIndex) -> WasmHeapType {
-        wasmtime_environ::WasmparserTypeConverter {
-            module: &self.translation.module,
-            types: self.types,
-        }
-        .lookup_heap_type(idx)
+        wasmtime_environ::WasmparserTypeConverter::new(self.types, &self.translation.module)
+            .lookup_heap_type(idx)
     }
 }
 
diff --git a/winch/codegen/src/codegen/mod.rs b/winch/codegen/src/codegen/mod.rs
index 3017dc812..e298e81bb 100644
--- a/winch/codegen/src/codegen/mod.rs
+++ b/winch/codegen/src/codegen/mod.rs
@@ -323,7 +323,7 @@ where
         let ptr_size: OperandSize = self.env.ptr_type().into();
         let sig_index_bytes = self.env.vmoffsets.size_of_vmshared_type_index();
         let sig_size = OperandSize::from_bytes(sig_index_bytes);
-        let sig_index = self.env.translation.module.types[type_index].unwrap_function();
+        let sig_index = self.env.translation.module.types[type_index];
         let sig_offset = sig_index
             .as_u32()
             .checked_mul(sig_index_bytes.into())


Test patch:
diff --git a/tests/all/wast.rs b/tests/all/wast.rs
index 96f975b71..c7f94c144 100644
--- a/tests/all/wast.rs
+++ b/tests/all/wast.rs
@@ -23,7 +23,8 @@ fn run_wast(wast: &str, strategy: Strategy, pooling: bool) -> anyhow::Result<()>
     let wast = Path::new(wast);
 
     let memory64 = feature_found(wast, "memory64");
-    let multi_memory = feature_found(wast, "multi-memory");
+    let multi_memory =
+        feature_found(wast, "multi-memory") || feature_found(wast, "component-model");
     let threads = feature_found(wast, "threads");
     let gc = feature_found(wast, "gc");
     let function_references = gc || feature_found(wast, "function-references");
diff --git a/tests/misc_testsuite/gc/rec-group-funcs.wast b/tests/misc_testsuite/gc/rec-group-funcs.wast
new file mode 100644
index 000000000..3f8b27983
--- /dev/null
+++ b/tests/misc_testsuite/gc/rec-group-funcs.wast
@@ -0,0 +1,38 @@
+;; Test that we properly canonicalize function types across modules, at the
+;; engine level. We rely on this canonicalization to make cross-module imports
+;; work among other things.
+
+(module $m1
+  ;; A pair of recursive types.
+  (rec (type $type_a (sub final (func (result i32 (ref null $type_b)))))
+       (type $type_b (sub final (func (result i32 (ref null $type_a))))))
+
+  (func (export "func_a") (type $type_a)
+    i32.const 1234
+    ref.null $type_b
+  )
+
+  (func (export "func_b") (type $type_b)
+    i32.const 4321
+    ref.null $type_a
+  )
+)
+(register "m1")
+
+(module $m2
+  ;; The same pair of recursive types.
+  (rec (type $type_a (sub final (func (result i32 (ref null $type_b)))))
+       (type $type_b (sub final (func (result i32 (ref null $type_a))))))
+
+  (import "m1" "func_a" (func $func_a (type $type_a)))
+  (import "m1" "func_b" (func $func_b (type $type_b)))
+
+  (func (export "call") (result i32 i32)
+    call $func_a
+    drop
+    call $func_b
+    drop
+  )
+)
+
+(assert_return (invoke "call") (i32.const 1234) (i32.const 4321))