Repository: bytecodealliance/wasmtime
Pull request #1879 (2020-06-15 14:27:01)

machinst: label ISA-specific changes as such


Patch:
diff --git a/.github/labeler.yml b/.github/labeler.yml
index ac3a8741b..b210c942f 100644
--- a/.github/labeler.yml
+++ b/.github/labeler.yml
@@ -19,19 +19,20 @@
 
 "cranelift":
   - "cranelift/**"
+  
+"cranelift:area:machinst":
+  - "cranelift/codegen/src/machinst/**"
 
 "cranelift:area:aarch64":
-  - "cranelift/codegen/src/machinst/**"
   - "cranelift/codegen/src/isa/aarch64/**"
 
+"cranelift:area:x64":
+  - "cranelift/codegen/src/isa/x64/**"
+
 "cranelift:area:peepmatic":
   - "cranelift/peepmatic/**"
   - "cranelift/codegen/src/peepmatic.rs"
 
-"cranelift:area:x64":
-  - "cranelift/codegen/src/machinst/**"
-  - "cranelift/codegen/src/isa/x64/**"
-
 "cranelift:docs":
   - "cranelift/docs/**"
 
diff --git a/Cargo.lock b/Cargo.lock
index 0298e2d04..5e4f6c155 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1,5 +1,20 @@
 # This file is automatically @generated by Cargo.
 # It is not intended for manual editing.
+[[package]]
+name = "addr2line"
+version = "0.12.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a49806b9dadc843c61e7c97e72490ad7f7220ae249012fbda9ad0609457c0543"
+dependencies = [
+ "gimli",
+]
+
+[[package]]
+name = "adler32"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "567b077b825e468cc974f0020d4082ee6e03132512f207ef1a02fd5d00d1f32d"
+
 [[package]]
 name = "ahash"
 version = "0.2.18"
@@ -85,26 +100,18 @@ checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
 
 [[package]]
 name = "backtrace"
-version = "0.3.46"
+version = "0.3.49"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "b1e692897359247cc6bb902933361652380af0f1b7651ae5c5013407f30e109e"
+checksum = "05100821de9e028f12ae3d189176b41ee198341eb8f369956407fea2f5cc666c"
 dependencies = [
- "backtrace-sys",
+ "addr2line",
  "cfg-if",
  "libc",
+ "miniz_oxide",
+ "object 0.20.0",
  "rustc-demangle",
 ]
 
-[[package]]
-name = "backtrace-sys"
-version = "0.1.37"
-source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "18fbebbe1c9d1f383a9cc7e8ccdb471b91c8d024ee9c2ca5b5346121fe8b4399"
-dependencies = [
- "cc",
- "libc",
-]
-
 [[package]]
 name = "base64"
 version = "0.11.0"
@@ -493,7 +500,7 @@ dependencies = [
  "anyhow",
  "cranelift-codegen",
  "cranelift-module",
- "object",
+ "object 0.19.0",
  "target-lexicon",
 ]
 
@@ -633,12 +640,13 @@ dependencies = [
 
 [[package]]
 name = "crossbeam-queue"
-version = "0.2.2"
+version = "0.2.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ab6bffe714b6bb07e42f201352c34f51fefd355ace793f9e638ebd52d23f98d2"
+checksum = "774ba60a54c213d409d5353bda12d49cd68d14e45036a285234c8d6f91f92570"
 dependencies = [
  "cfg-if",
  "crossbeam-utils",
+ "maybe-uninit",
 ]
 
 [[package]]
@@ -981,9 +989,9 @@ dependencies = [
 
 [[package]]
 name = "hermit-abi"
-version = "0.1.13"
+version = "0.1.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "91780f809e750b0a89f5544be56617ff6b1227ee485bcb06ebe10cdf89bd3b71"
+checksum = "b9586eedd4ce6b3c498bc3b4dd92fc9f11166aa908a914071953768066c67909"
 dependencies = [
  "libc",
 ]
@@ -1181,6 +1189,15 @@ dependencies = [
  "autocfg 1.0.0",
 ]
 
+[[package]]
+name = "miniz_oxide"
+version = "0.3.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "791daaae1ed6889560f8c4359194f56648355540573244a5448a83ba1ecc7435"
+dependencies = [
+ "adler32",
+]
+
 [[package]]
 name = "more-asserts"
 version = "0.2.1"
@@ -1189,9 +1206,9 @@ checksum = "0debeb9fcf88823ea64d64e4a815ab1643f33127d995978e099942ce38f25238"
 
 [[package]]
 name = "num-integer"
-version = "0.1.42"
+version = "0.1.43"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3f6ea62e9d81a77cd3ee9a2a5b9b609447857f3d358704331e4ef39eb247fcba"
+checksum = "8d59457e662d541ba17869cf51cf177c0b5f0cbf476c66bdc90bf1edac4f875b"
 dependencies = [
  "autocfg 1.0.0",
  "num-traits",
@@ -1199,9 +1216,9 @@ dependencies = [
 
 [[package]]
 name = "num-traits"
-version = "0.2.11"
+version = "0.2.12"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c62be47e61d1842b9170f0fdeec8eba98e60e90e5446449a0545e5152acd7096"
+checksum = "ac267bcc07f48ee5f8935ab0d24f316fb722d7a1292e2913f0cc196b29ffd611"
 dependencies = [
  "autocfg 1.0.0",
 ]
@@ -1232,6 +1249,12 @@ dependencies = [
  "indexmap",
 ]
 
+[[package]]
+name = "object"
+version = "0.20.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1ab52be62400ca80aa00285d25253d7f7c437b7375c4de678f5405d3afe82ca5"
+
 [[package]]
 name = "once_cell"
 version = "1.4.0"
@@ -1613,10 +1636,11 @@ dependencies = [
 
 [[package]]
 name = "rayon"
-version = "1.3.0"
+version = "1.3.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "db6ce3297f9c85e16621bb8cca38a06779ffc31bb8184e1be4bed2be4678a098"
+checksum = "62f02856753d04e03e26929f820d0a0a337ebe71f849801eea335d464b349080"
 dependencies = [
+ "autocfg 1.0.0",
  "crossbeam-deque",
  "either",
  "rayon-core",
@@ -1624,9 +1648,9 @@ dependencies = [
 
 [[package]]
 name = "rayon-core"
-version = "1.7.0"
+version = "1.7.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "08a89b46efaf957e52b18062fb2f4660f8b8a4dde1807ca002690868ef2c85a9"
+checksum = "e92e15d89083484e11353891f1af602cc661426deb9564c298b270c726973280"
 dependencies = [
  "crossbeam-deque",
  "crossbeam-queue",
@@ -1715,9 +1739,9 @@ dependencies = [
 
 [[package]]
 name = "remove_dir_all"
-version = "0.5.2"
+version = "0.5.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "4a83fa3702a688b9359eccba92d153ac33fd2e8462f9e0e3fdf155239ea7792e"
+checksum = "3acd125665422973a33ac9d3dd2df85edad0f4ae9b00dafb1a05e43a9f5ef8e7"
 dependencies = [
  "winapi",
 ]
@@ -1832,18 +1856,18 @@ checksum = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
 
 [[package]]
 name = "serde"
-version = "1.0.111"
+version = "1.0.112"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c9124df5b40cbd380080b2cc6ab894c040a3070d995f5c9dc77e18c34a8ae37d"
+checksum = "736aac72d1eafe8e5962d1d1c3d99b0df526015ba40915cb3c49d042e92ec243"
 dependencies = [
  "serde_derive",
 ]
 
 [[package]]
 name = "serde_derive"
-version = "1.0.111"
+version = "1.0.112"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "3f2c3ac8e6ca1e9c80b8be1023940162bf81ae3cffbb1809474152f2ce1eb250"
+checksum = "bf0343ce212ac0d3d6afd9391ac8e9c9efe06b533c8d33f660f6390cc4093f57"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -1852,9 +1876,9 @@ dependencies = [
 
 [[package]]
 name = "serde_json"
-version = "1.0.53"
+version = "1.0.55"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "993948e75b189211a9b31a7528f950c6adc21f9720b6438ff80a7fa2f864cea2"
+checksum = "ec2c5d7e739bc07a3e73381a39d61fdb5f671c60c1df26a130690665803d8226"
 dependencies = [
  "itoa",
  "ryu",
@@ -1941,9 +1965,9 @@ dependencies = [
 
 [[package]]
 name = "syn"
-version = "1.0.30"
+version = "1.0.31"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "93a56fabc59dce20fe48b6c832cc249c713e7ed88fa28b0ee0a3bfcaae5fe4e2"
+checksum = "b5304cfdf27365b7585c25d4af91b35016ed21ef88f17ced89c7093b43dba8b6"
 dependencies = [
  "proc-macro2",
  "quote",
@@ -2348,8 +2372,9 @@ dependencies = [
  "filecheck",
  "humantime",
  "libc",
+ "log",
  "more-asserts",
- "object",
+ "object 0.19.0",
  "pretty_env_logger",
  "rayon",
  "structopt",
@@ -2376,7 +2401,7 @@ dependencies = [
  "anyhow",
  "gimli",
  "more-asserts",
- "object",
+ "object 0.19.0",
  "target-lexicon",
  "thiserror",
  "wasmparser 0.57.0",
@@ -2477,7 +2502,7 @@ version = "0.18.0"
 dependencies = [
  "anyhow",
  "more-asserts",
- "object",
+ "object 0.19.0",
  "wasmtime-environ",
 ]
 
@@ -2491,7 +2516,7 @@ dependencies = [
  "ittapi-rs",
  "lazy_static",
  "libc",
- "object",
+ "object 0.19.0",
  "scroll",
  "serde",
  "target-lexicon",
@@ -2509,6 +2534,7 @@ dependencies = [
  "indexmap",
  "lazy_static",
  "libc",
+ "log",
  "memoffset",
  "more-asserts",
  "region",
@@ -2746,18 +2772,18 @@ dependencies = [
 
 [[package]]
 name = "zstd"
-version = "0.5.2+zstd.1.4.5"
+version = "0.5.3+zstd.1.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "644352b10ce7f333d6e0af85bd4f5322dc449416dc1211c6308e95bca8923db4"
+checksum = "01b32eaf771efa709e8308605bbf9319bf485dc1503179ec0469b611937c0cd8"
 dependencies = [
  "zstd-safe",
 ]
 
 [[package]]
 name = "zstd-safe"
-version = "2.0.4+zstd.1.4.5"
+version = "2.0.5+zstd.1.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "7113c0c9aed2c55181f2d9f5b0a36e7d2c0183b11c058ab40b35987479efe4d7"
+checksum = "1cfb642e0d27f64729a639c52db457e0ae906e7bc6f5fe8f5c453230400f1055"
 dependencies = [
  "libc",
  "zstd-sys",
@@ -2765,9 +2791,9 @@ dependencies = [
 
 [[package]]
 name = "zstd-sys"
-version = "1.4.16+zstd.1.4.5"
+version = "1.4.17+zstd.1.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "c442965efc45353be5a9b9969c9b0872fff6828c7e06d118dda2cb2d0bb11d5a"
+checksum = "b89249644df056b522696b1bb9e7c18c87e8ffa3e2f0dc3b0155875d6498f01b"
 dependencies = [
  "cc",
  "glob",
diff --git a/Cargo.toml b/Cargo.toml
index b95970a33..d7b22090f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -38,6 +38,7 @@ pretty_env_logger = "0.4.0"
 file-per-thread-logger = "0.1.1"
 wat = "1.0.18"
 libc = "0.2.60"
+log = "0.4.8"
 rayon = "1.2.1"
 humantime = "1.3.0"
 
@@ -86,3 +87,6 @@ maintenance = { status = "actively-developed" }
 [[test]]
 name = "host_segfault"
 harness = false
+
+[profile.dev.package.backtrace]
+debug = false # FIXME(#1813)
diff --git a/build.rs b/build.rs
index 2cbb4b381..08ac51f65 100644
--- a/build.rs
+++ b/build.rs
@@ -209,9 +209,14 @@ fn ignore(testsuite: &str, testname: &str, strategy: &str) -> bool {
             // testsuite repo.
             ("simd", "simd_const") => return true,
 
+            ("reference_types", "table_copy_on_imported_tables")
+            | ("reference_types", "externref_id_function") => {
+                // TODO(#1886): Ignore if this isn't x64, because Cranelift only
+                // supports reference types on x64.
+                return env::var("CARGO_CFG_TARGET_ARCH").unwrap() != "x86_64";
+            }
+
             // Still working on implementing these. See #929.
-            ("reference_types", "table_copy_on_imported_tables") => return false,
-            ("reference_types", "externref_id_function") => return false,
             ("reference_types", _) => return true,
 
             _ => {}
diff --git a/cranelift/codegen/src/binemit/stackmap.rs b/cranelift/codegen/src/binemit/stackmap.rs
index 4db9b9292..45716dcae 100644
--- a/cranelift/codegen/src/binemit/stackmap.rs
+++ b/cranelift/codegen/src/binemit/stackmap.rs
@@ -103,7 +103,7 @@ impl Stackmap {
 
         // Refer to the doc comment for `Stackmap` above to understand the
         // bitmap representation used here.
-        let map_size = (dbg!(info.frame_size) + dbg!(info.inbound_args_size)) as usize;
+        let map_size = (info.frame_size + info.inbound_args_size) as usize;
         let word_size = isa.pointer_bytes() as usize;
         let num_words = map_size / word_size;
 
diff --git a/cranelift/codegen/src/isa/x64/abi.rs b/cranelift/codegen/src/isa/x64/abi.rs
index 2505286e0..51fbddeac 100644
--- a/cranelift/codegen/src/isa/x64/abi.rs
+++ b/cranelift/codegen/src/isa/x64/abi.rs
@@ -280,7 +280,7 @@ impl ABIBody for X64ABIBody {
                     return Inst::mov_r_r(/*is64=*/ true, from_reg.to_reg(), to_reg);
                 } else if from_reg.get_class() == RegClass::V128 {
                     // TODO: How to support Movss. Should is64 always be true?
-                    return Inst::xmm_r_r(SSE_Op::SSE2_Movsd, from_reg.to_reg(), to_reg);
+                    return Inst::xmm_r_r(SseOpcode::Movsd, from_reg.to_reg(), to_reg);
                 }
                 unimplemented!("moving from non-int arg to vreg {:?}", from_reg.get_class());
             }
@@ -315,11 +315,9 @@ impl ABIBody for X64ABIBody {
                         from_reg.to_reg(),
                         Writable::<Reg>::from_reg(to_reg.to_reg()),
                     ))
-                } else if to_reg.get_class() == RegClass::V128
-                    || to_reg.get_class() == RegClass::V128
-                {
+                } else if to_reg.get_class() == RegClass::V128 {
                     ret.push(Inst::xmm_r_r(
-                        SSE_Op::SSE2_Movsd,
+                        SseOpcode::Movsd,
                         from_reg.to_reg(),
                         Writable::<Reg>::from_reg(to_reg.to_reg()),
                     ))
@@ -390,7 +388,7 @@ impl ABIBody for X64ABIBody {
 
             // The "traditional" pre-preamble
             // RSP before the call will be 0 % 16.  So here, it is 8 % 16.
-            insts.push(Inst::push64(RMI::reg(r_rbp)));
+            insts.push(Inst::push64(RegMemImm::reg(r_rbp)));
             // RSP is now 0 % 16
             insts.push(Inst::mov_r_r(true, r_rsp, w_rbp));
         }
@@ -403,7 +401,7 @@ impl ABIBody for X64ABIBody {
             let r_reg = reg.to_reg();
             match r_reg.get_class() {
                 RegClass::I64 => {
-                    insts.push(Inst::push64(RMI::reg(r_reg.to_reg())));
+                    insts.push(Inst::push64(RegMemImm::reg(r_reg.to_reg())));
                     callee_saved_used += 8;
                 }
                 _ => unimplemented!(),
@@ -436,8 +434,8 @@ impl ABIBody for X64ABIBody {
             if frame_size > 0 {
                 insts.push(Inst::alu_rmi_r(
                     true,
-                    RMI_R_Op::Sub,
-                    RMI::imm(frame_size as u32),
+                    AluRmiROpcode::Sub,
+                    RegMemImm::imm(frame_size as u32),
                     w_rsp,
                 ));
             }
@@ -464,8 +462,8 @@ impl ABIBody for X64ABIBody {
 
                 insts.push(Inst::alu_rmi_r(
                     true,
-                    RMI_R_Op::Add,
-                    RMI::imm(frame_size as u32),
+                    AluRmiROpcode::Add,
+                    RegMemImm::imm(frame_size as u32),
                     w_rsp,
                 ));
             }
diff --git a/cranelift/codegen/src/isa/x64/inst/args.rs b/cranelift/codegen/src/isa/x64/inst/args.rs
index 6f4b52156..10541c86f 100644
--- a/cranelift/codegen/src/isa/x64/inst/args.rs
+++ b/cranelift/codegen/src/isa/x64/inst/args.rs
@@ -5,6 +5,7 @@ use std::string::{String, ToString};
 
 use regalloc::{RealRegUniverse, Reg, RegClass, RegUsageCollector};
 
+use crate::ir::condcodes::IntCC;
 use crate::machinst::*;
 
 use super::regs::show_ireg_sized;
@@ -13,10 +14,10 @@ use super::regs::show_ireg_sized;
 #[derive(Clone)]
 pub(crate) enum Addr {
     /// Immediate sign-extended and a Register.
-    IR { simm32: u32, base: Reg },
+    ImmReg { simm32: u32, base: Reg },
 
     /// sign-extend-32-to-64(Immediate) + Register1 + (Register2 << Shift)
-    IRRS {
+    ImmRegRegShift {
         simm32: u32,
         base: Reg,
         index: Reg,
@@ -25,18 +26,16 @@ pub(crate) enum Addr {
 }
 
 impl Addr {
-    // Constructors.
-
     pub(crate) fn imm_reg(simm32: u32, base: Reg) -> Self {
         debug_assert!(base.get_class() == RegClass::I64);
-        Self::IR { simm32, base }
+        Self::ImmReg { simm32, base }
     }
 
     pub(crate) fn imm_reg_reg_shift(simm32: u32, base: Reg, index: Reg, shift: u8) -> Self {
         debug_assert!(base.get_class() == RegClass::I64);
         debug_assert!(index.get_class() == RegClass::I64);
         debug_assert!(shift <= 3);
-        Addr::IRRS {
+        Self::ImmRegRegShift {
             simm32,
             base,
             index,
@@ -47,10 +46,10 @@ impl Addr {
     /// Add the regs mentioned by `self` to `collector`.
     pub(crate) fn get_regs_as_uses(&self, collector: &mut RegUsageCollector) {
         match self {
-            Addr::IR { simm32: _, base } => {
+            Addr::ImmReg { simm32: _, base } => {
                 collector.add_use(*base);
             }
-            Addr::IRRS {
+            Addr::ImmRegRegShift {
                 simm32: _,
                 base,
                 index,
@@ -66,8 +65,10 @@ impl Addr {
 impl ShowWithRRU for Addr {
     fn show_rru(&self, mb_rru: Option<&RealRegUniverse>) -> String {
         match self {
-            Addr::IR { simm32, base } => format!("{}({})", *simm32 as i32, base.show_rru(mb_rru)),
-            Addr::IRRS {
+            Addr::ImmReg { simm32, base } => {
+                format!("{}({})", *simm32 as i32, base.show_rru(mb_rru))
+            }
+            Addr::ImmRegRegShift {
                 simm32,
                 base,
                 index,
@@ -88,46 +89,44 @@ impl ShowWithRRU for Addr {
 /// the lower 8 or 16 bits of `simm32` is relevant.  In the 64-bit case, the value denoted by
 /// `simm32` is its sign-extension out to 64 bits.
 #[derive(Clone)]
-pub(crate) enum RMI {
-    R { reg: Reg },
-    M { addr: Addr },
-    I { simm32: u32 },
+pub(crate) enum RegMemImm {
+    Reg { reg: Reg },
+    Mem { addr: Addr },
+    Imm { simm32: u32 },
 }
 
-impl RMI {
-    // Constructors
-
-    pub(crate) fn reg(reg: Reg) -> RMI {
+impl RegMemImm {
+    pub(crate) fn reg(reg: Reg) -> Self {
         debug_assert!(reg.get_class() == RegClass::I64);
-        RMI::R { reg }
+        Self::Reg { reg }
     }
-    pub(crate) fn mem(addr: Addr) -> RMI {
-        RMI::M { addr }
+    pub(crate) fn mem(addr: Addr) -> Self {
+        Self::Mem { addr }
     }
-    pub(crate) fn imm(simm32: u32) -> RMI {
-        RMI::I { simm32 }
+    pub(crate) fn imm(simm32: u32) -> Self {
+        Self::Imm { simm32 }
     }
 
     /// Add the regs mentioned by `self` to `collector`.
     pub(crate) fn get_regs_as_uses(&self, collector: &mut RegUsageCollector) {
         match self {
-            RMI::R { reg } => collector.add_use(*reg),
-            RMI::M { addr } => addr.get_regs_as_uses(collector),
-            RMI::I { simm32: _ } => {}
+            Self::Reg { reg } => collector.add_use(*reg),
+            Self::Mem { addr } => addr.get_regs_as_uses(collector),
+            Self::Imm { simm32: _ } => {}
         }
     }
 }
 
-impl ShowWithRRU for RMI {
+impl ShowWithRRU for RegMemImm {
     fn show_rru(&self, mb_rru: Option<&RealRegUniverse>) -> String {
         self.show_rru_sized(mb_rru, 8)
     }
 
     fn show_rru_sized(&self, mb_rru: Option<&RealRegUniverse>, size: u8) -> String {
         match self {
-            RMI::R { reg } => show_ireg_sized(*reg, mb_rru, size),
-            RMI::M { addr } => addr.show_rru(mb_rru),
-            RMI::I { simm32 } => format!("${}", *simm32 as i32),
+            Self::Reg { reg } => show_ireg_sized(*reg, mb_rru, size),
+            Self::Mem { addr } => addr.show_rru(mb_rru),
+            Self::Imm { simm32 } => format!("${}", *simm32 as i32),
         }
     }
 }
@@ -135,48 +134,45 @@ impl ShowWithRRU for RMI {
 /// An operand which is either an integer Register or a value in Memory.  This can denote an 8, 16,
 /// 32 or 64 bit value.
 #[derive(Clone)]
-pub(crate) enum RM {
-    R { reg: Reg },
-    M { addr: Addr },
+pub(crate) enum RegMem {
+    Reg { reg: Reg },
+    Mem { addr: Addr },
 }
 
-impl RM {
-    // Constructors.
-
+impl RegMem {
     pub(crate) fn reg(reg: Reg) -> Self {
         debug_assert!(reg.get_class() == RegClass::I64 || reg.get_class() == RegClass::V128);
-        RM::R { reg }
+        Self::Reg { reg }
     }
-
     pub(crate) fn mem(addr: Addr) -> Self {
-        RM::M { addr }
+        Self::Mem { addr }
     }
 
     /// Add the regs mentioned by `self` to `collector`.
     pub(crate) fn get_regs_as_uses(&self, collector: &mut RegUsageCollector) {
         match self {
-            RM::R { reg } => collector.add_use(*reg),
-            RM::M { addr } => addr.get_regs_as_uses(collector),
+            RegMem::Reg { reg } => collector.add_use(*reg),
+            RegMem::Mem { addr } => addr.get_regs_as_uses(collector),
         }
     }
 }
 
-impl ShowWithRRU for RM {
+impl ShowWithRRU for RegMem {
     fn show_rru(&self, mb_rru: Option<&RealRegUniverse>) -> String {
         self.show_rru_sized(mb_rru, 8)
     }
 
     fn show_rru_sized(&self, mb_rru: Option<&RealRegUniverse>, size: u8) -> String {
         match self {
-            RM::R { reg } => show_ireg_sized(*reg, mb_rru, size),
-            RM::M { addr } => addr.show_rru(mb_rru),
+            RegMem::Reg { reg } => show_ireg_sized(*reg, mb_rru, size),
+            RegMem::Mem { addr } => addr.show_rru(mb_rru),
         }
     }
 }
 
 /// Some basic ALU operations.  TODO: maybe add Adc, Sbb.
 #[derive(Clone, PartialEq)]
-pub enum RMI_R_Op {
+pub enum AluRmiROpcode {
     Add,
     Sub,
     And,
@@ -186,89 +182,173 @@ pub enum RMI_R_Op {
     Mul,
 }
 
-impl RMI_R_Op {
-    pub(crate) fn to_string(&self) -> String {
-        match self {
-            RMI_R_Op::Add => "add".to_string(),
-            RMI_R_Op::Sub => "sub".to_string(),
-            RMI_R_Op::And => "and".to_string(),
-            RMI_R_Op::Or => "or".to_string(),
-            RMI_R_Op::Xor => "xor".to_string(),
-            RMI_R_Op::Mul => "imul".to_string(),
-        }
+impl fmt::Debug for AluRmiROpcode {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        let name = match self {
+            AluRmiROpcode::Add => "add",
+            AluRmiROpcode::Sub => "sub",
+            AluRmiROpcode::And => "and",
+            AluRmiROpcode::Or => "or",
+            AluRmiROpcode::Xor => "xor",
+            AluRmiROpcode::Mul => "imul",
+        };
+        write!(fmt, "{}", name)
     }
 }
 
-impl fmt::Debug for RMI_R_Op {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "{}", self.to_string())
+impl ToString for AluRmiROpcode {
+    fn to_string(&self) -> String {
+        format!("{:?}", self)
     }
 }
 
-/// Some scalar SSE operations requiring 2 operands r/m and r
-/// Each instruction is prefixed with the SSE version that introduced
-/// the particular instructions.
-/// TODO: Below only includes scalar operations. To be seen if packed will
-/// be added here.
-#[derive(Clone, PartialEq)]
-pub enum SSE_Op {
-    SSE_Addss,
-    SSE2_Addsd,
-    SSE_Comiss,
-    SSE2_Comisd,
-    SSE2_Cvtsd2ss,
-    SSE2_Cvtsd2si,
-    SSE_Cvtsi2ss,
-    SSE2_Cvtsi2sd,
-    SSE_Cvtss2si,
-    SSE2_Cvtss2sd,
-    SSE_Cvttss2si,
-    SSE2_Cvttsd2si,
-    SSE_Divss,
-    SSE2_Divsd,
-    SSE_Maxss,
-    SSE2_Maxsd,
-    SSE_Minss,
-    SSE2_Minsd,
-    SSE_Movss,
-    SSE2_Movsd,
-    SSE_Mulss,
-    SSE2_Mulsd,
-    SSE_Rcpss,
-    SSE41_Roundss,
-    SSE41_Roundsd,
-    SSE_Rsqrtss,
-    SSE_Sqrtss,
-    SSE2_Sqrtsd,
-    SSE_Subss,
-    SSE2_Subsd,
-    SSE_Ucomiss,
-    SSE2_Ucomisd,
+pub(crate) enum InstructionSet {
+    SSE,
+    SSE2,
+    SSE41,
 }
 
-/// Some SSE operations requiring 3 operands i, r/m, and r
+/// Some scalar SSE operations requiring 2 operands r/m and r.
+/// TODO: Below only includes scalar operations. To be seen if packed will be added here.
 #[derive(Clone, PartialEq)]
-pub enum SSE_RMI_Op {
-    SSE_Cmpss,
-    SSE2_Cmpsd,
-    SSE41_Insertps,
+pub enum SseOpcode {
+    Addss,
+    Addsd,
+    Comiss,
+    Comisd,
+    Cmpss,
+    Cmpsd,
+    Cvtsd2ss,
+    Cvtsd2si,
+    Cvtsi2ss,
+    Cvtsi2sd,
+    Cvtss2si,
+    Cvtss2sd,
+    Cvttss2si,
+    Cvttsd2si,
+    Divss,
+    Divsd,
+    Insertps,
+    Maxss,
+    Maxsd,
+    Minss,
+    Minsd,
+    Movss,
+    Movsd,
+    Mulss,
+    Mulsd,
+    Rcpss,
+    Roundss,
+    Roundsd,
+    Rsqrtss,
+    Sqrtss,
+    Sqrtsd,
+    Subss,
+    Subsd,
+    Ucomiss,
+    Ucomisd,
 }
 
-impl SSE_Op {
+impl SseOpcode {
+    /// Which `InstructionSet` is the first supporting this opcode?
+    pub(crate) fn available_from(&self) -> InstructionSet {
+        use InstructionSet::*;
+        match self {
+            SseOpcode::Addss
+            | SseOpcode::Cvtsi2ss
+            | SseOpcode::Cvtss2si
+            | SseOpcode::Cvttss2si
+            | SseOpcode::Divss
+            | SseOpcode::Maxss
+            | SseOpcode::Minss
+            | SseOpcode::Movss
+            | SseOpcode::Mulss
+            | SseOpcode::Rcpss
+            | SseOpcode::Rsqrtss
+            | SseOpcode::Subss
+            | SseOpcode::Ucomiss
+            | SseOpcode::Sqrtss
+            | SseOpcode::Comiss
+            | SseOpcode::Cmpss => SSE,
+
+            SseOpcode::Addsd
+            | SseOpcode::Cvtsd2ss
+            | SseOpcode::Cvtsd2si
+            | SseOpcode::Cvtsi2sd
+            | SseOpcode::Cvtss2sd
+            | SseOpcode::Cvttsd2si
+            | SseOpcode::Divsd
+            | SseOpcode::Maxsd
+            | SseOpcode::Minsd
+            | SseOpcode::Movsd
+            | SseOpcode::Mulsd
+            | SseOpcode::Sqrtsd
+            | SseOpcode::Subsd
+            | SseOpcode::Ucomisd
+            | SseOpcode::Comisd
+            | SseOpcode::Cmpsd => SSE2,
+
+            SseOpcode::Insertps | SseOpcode::Roundss | SseOpcode::Roundsd => SSE41,
+        }
+    }
+
     pub(crate) fn to_string(&self) -> String {
         match self {
-            SSE_Op::SSE_Addss => "addss".to_string(),
-            SSE_Op::SSE_Subss => "subss".to_string(),
-            SSE_Op::SSE_Movss => "movss".to_string(),
-            SSE_Op::SSE2_Movsd => "movsd".to_string(),
+            SseOpcode::Addss => "addss".to_string(),
+            SseOpcode::Subss => "subss".to_string(),
+            SseOpcode::Movss => "movss".to_string(),
+            SseOpcode::Movsd => "movsd".to_string(),
             _ => "unimplemented sse_op".to_string(),
         }
     }
 }
 
-impl fmt::Debug for SSE_Op {
+impl fmt::Debug for SseOpcode {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "{}", self.to_string())
+        let name = match self {
+            SseOpcode::Addss => "addss",
+            SseOpcode::Addsd => "addsd",
+            SseOpcode::Comiss => "comiss",
+            SseOpcode::Comisd => "comisd",
+            SseOpcode::Cvtsd2ss => "cvtsd2ss",
+            SseOpcode::Cvtsd2si => "cvtsd2si",
+            SseOpcode::Cvtsi2ss => "cvtsi2ss",
+            SseOpcode::Cvtsi2sd => "cvtsi2sd",
+            SseOpcode::Cvtss2si => "cvtss2si",
+            SseOpcode::Cvtss2sd => "cvtss2sd",
+            SseOpcode::Cvttss2si => "cvttss2si",
+            SseOpcode::Cvttsd2si => "cvttsd2si",
+            SseOpcode::Divss => "divss",
+            SseOpcode::Divsd => "divsd",
+            SseOpcode::Maxss => "maxss",
+            SseOpcode::Maxsd => "maxsd",
+            SseOpcode::Minss => "minss",
+            SseOpcode::Minsd => "minsd",
+            SseOpcode::Movss => "movss",
+            SseOpcode::Movsd => "movsd",
+            SseOpcode::Mulss => "mulss",
+            SseOpcode::Mulsd => "mulsd",
+            SseOpcode::Rcpss => "rcpss",
+            SseOpcode::Roundss => "roundss",
+            SseOpcode::Roundsd => "roundsd",
+            SseOpcode::Rsqrtss => "rsqrtss",
+            SseOpcode::Sqrtss => "srtqss",
+            SseOpcode::Sqrtsd => "sqrtsd",
+            SseOpcode::Subss => "subss",
+            SseOpcode::Subsd => "subsd",
+            SseOpcode::Ucomiss => "ucomiss",
+            SseOpcode::Ucomisd => "ucomisd",
+            SseOpcode::Cmpss => "cmpss",
+            SseOpcode::Cmpsd => "cmpsd",
+            SseOpcode::Insertps => "insertps",
+        };
+        write!(fmt, "{}", name)
+    }
+}
+
+impl ToString for SseOpcode {
+    fn to_string(&self) -> String {
+        format!("{:?}", self)
     }
 }
 
@@ -289,30 +369,30 @@ pub enum ExtMode {
 }
 
 impl ExtMode {
-    pub(crate) fn to_string(&self) -> String {
-        match self {
-            ExtMode::BL => "bl".to_string(),
-            ExtMode::BQ => "bq".to_string(),
-            ExtMode::WL => "wl".to_string(),
-            ExtMode::WQ => "wq".to_string(),
-            ExtMode::LQ => "lq".to_string(),
-        }
-    }
-
     pub(crate) fn dst_size(&self) -> u8 {
         match self {
-            ExtMode::BL => 4,
-            ExtMode::BQ => 8,
-            ExtMode::WL => 4,
-            ExtMode::WQ => 8,
-            ExtMode::LQ => 8,
+            ExtMode::BL | ExtMode::WL => 4,
+            ExtMode::BQ | ExtMode::WQ | ExtMode::LQ => 8,
         }
     }
 }
 
 impl fmt::Debug for ExtMode {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "{}", self.to_string())
+        let name = match self {
+            ExtMode::BL => "bl",
+            ExtMode::BQ => "bq",
+            ExtMode::WL => "wl",
+            ExtMode::WQ => "wq",
+            ExtMode::LQ => "lq",
+        };
+        write!(fmt, "{}", name)
+    }
+}
+
+impl ToString for ExtMode {
+    fn to_string(&self) -> String {
+        format!("{:?}", self)
     }
 }
 
@@ -324,19 +404,20 @@ pub enum ShiftKind {
     RightS,
 }
 
-impl ShiftKind {
-    pub(crate) fn to_string(&self) -> String {
-        match self {
-            ShiftKind::Left => "shl".to_string(),
-            ShiftKind::RightZ => "shr".to_string(),
-            ShiftKind::RightS => "sar".to_string(),
-        }
+impl fmt::Debug for ShiftKind {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        let name = match self {
+            ShiftKind::Left => "shl",
+            ShiftKind::RightZ => "shr",
+            ShiftKind::RightS => "sar",
+        };
+        write!(fmt, "{}", name)
     }
 }
 
-impl fmt::Debug for ShiftKind {
-    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "{}", self.to_string())
+impl ToString for ShiftKind {
+    fn to_string(&self) -> String {
+        format!("{:?}", self)
     }
 }
 
@@ -382,26 +463,24 @@ pub enum CC {
 }
 
 impl CC {
-    pub(crate) fn to_string(&self) -> String {
-        match self {
-            CC::O => "o".to_string(),
-            CC::NO => "no".to_string(),
-            CC::B => "b".to_string(),
-            CC::NB => "nb".to_string(),
-            CC::Z => "z".to_string(),
-            CC::NZ => "nz".to_string(),
-            CC::BE => "be".to_string(),
-            CC::NBE => "nbe".to_string(),
-            CC::S => "s".to_string(),
-            CC::NS => "ns".to_string(),
-            CC::L => "l".to_string(),
-            CC::NL => "nl".to_string(),
-            CC::LE => "le".to_string(),
-            CC::NLE => "nle".to_string(),
+    pub(crate) fn from_intcc(intcc: IntCC) -> Self {
+        match intcc {
+            IntCC::Equal => CC::Z,
+            IntCC::NotEqual => CC::NZ,
+            IntCC::SignedGreaterThanOrEqual => CC::NL,
+            IntCC::SignedGreaterThan => CC::NLE,
+            IntCC::SignedLessThanOrEqual => CC::LE,
+            IntCC::SignedLessThan => CC::L,
+            IntCC::UnsignedGreaterThanOrEqual => CC::NB,
+            IntCC::UnsignedGreaterThan => CC::NBE,
+            IntCC::UnsignedLessThanOrEqual => CC::BE,
+            IntCC::UnsignedLessThan => CC::B,
+            IntCC::Overflow => CC::O,
+            IntCC::NotOverflow => CC::NO,
         }
     }
 
-    pub(crate) fn invert(&self) -> CC {
+    pub(crate) fn invert(&self) -> Self {
         match self {
             CC::O => CC::NO,
             CC::NO => CC::O,
@@ -433,7 +512,29 @@ impl CC {
 
 impl fmt::Debug for CC {
     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
-        write!(fmt, "{}", self.to_string())
+        let name = match self {
+            CC::O => "o",
+            CC::NO => "no",
+            CC::B => "b",
+            CC::NB => "nb",
+            CC::Z => "z",
+            CC::NZ => "nz",
+            CC::BE => "be",
+            CC::NBE => "nbe",
+            CC::S => "s",
+            CC::NS => "ns",
+            CC::L => "l",
+            CC::NL => "nl",
+            CC::LE => "le",
+            CC::NLE => "nle",
+        };
+        write!(fmt, "{}", name)
+    }
+}
+
+impl ToString for CC {
+    fn to_string(&self) -> String {
+        format!("{:?}", self)
     }
 }
 
diff --git a/cranelift/codegen/src/isa/x64/inst/emit.rs b/cranelift/codegen/src/isa/x64/inst/emit.rs
index 77ed7fcb4..22a750111 100644
--- a/cranelift/codegen/src/isa/x64/inst/emit.rs
+++ b/cranelift/codegen/src/isa/x64/inst/emit.rs
@@ -1,12 +1,12 @@
 use crate::isa::x64::inst::*;
 use regalloc::Reg;
 
-fn low8willSXto64(x: u32) -> bool {
+fn low8_will_sign_extend_to_64(x: u32) -> bool {
     let xs = (x as i32) as i64;
     xs == ((xs << 56) >> 56)
 }
 
-fn low8willSXto32(x: u32) -> bool {
+fn low8_will_sign_extend_to_32(x: u32) -> bool {
     let xs = x as i32;
     xs == ((xs << 24) >> 24)
 }
@@ -21,266 +21,310 @@ fn low8willSXto32(x: u32) -> bool {
 // "enc" in the following means "hardware register encoding number".
 
 #[inline(always)]
-fn mkModRegRM(m0d: u8, encRegG: u8, rmE: u8) -> u8 {
+fn encode_modrm(m0d: u8, enc_reg_g: u8, rm_e: u8) -> u8 {
     debug_assert!(m0d < 4);
-    debug_assert!(encRegG < 8);
-    debug_assert!(rmE < 8);
-    ((m0d & 3) << 6) | ((encRegG & 7) << 3) | (rmE & 7)
+    debug_assert!(enc_reg_g < 8);
+    debug_assert!(rm_e < 8);
+    ((m0d & 3) << 6) | ((enc_reg_g & 7) << 3) | (rm_e & 7)
 }
 
 #[inline(always)]
-fn mkSIB(shift: u8, encIndex: u8, encBase: u8) -> u8 {
+fn encode_sib(shift: u8, enc_index: u8, enc_base: u8) -> u8 {
     debug_assert!(shift < 4);
-    debug_assert!(encIndex < 8);
-    debug_assert!(encBase < 8);
-    ((shift & 3) << 6) | ((encIndex & 7) << 3) | (encBase & 7)
+    debug_assert!(enc_index < 8);
+    debug_assert!(enc_base < 8);
+    ((shift & 3) << 6) | ((enc_index & 7) << 3) | (enc_base & 7)
 }
 
-/// Get the encoding number from something which we sincerely hope is a real
-/// register of class I64.
+/// Get the encoding number of a GPR.
 #[inline(always)]
-fn iregEnc(reg: Reg) -> u8 {
+fn int_reg_enc(reg: Reg) -> u8 {
     debug_assert!(reg.is_real());
+    debug_assert_eq!(reg.get_class(), RegClass::I64);
     reg.get_hw_encoding()
 }
 
-// F_*: these flags describe special handling of the insn to be generated.  Be
-// careful with these.  It is easy to create nonsensical combinations.
-const F_NONE: u32 = 0;
+/// Get the encoding number of any register.
+#[inline(always)]
+fn reg_enc(reg: Reg) -> u8 {
+    debug_assert!(reg.is_real());
+    reg.get_hw_encoding()
+}
+
+/// A small bit field to record a REX prefix specification:
+/// - bit 0 set to 1 indicates REX.W must be 0 (cleared).
+/// - bit 1 set to 1 indicates the REX prefix must always be emitted.
+#[repr(transparent)]
+#[derive(Clone, Copy)]
+struct RexFlags(u8);
 
-/// Emit the REX prefix byte even if it appears to be redundant (== 0x40).
-const F_RETAIN_REDUNDANT_REX: u32 = 1;
+impl RexFlags {
+    /// By default, set the W field, and don't always emit.
+    #[inline(always)]
+    fn set_w() -> Self {
+        Self(0)
+    }
+    /// Creates a new RexPrefix for which the REX.W bit will be cleared.
+    #[inline(always)]
+    fn clear_w() -> Self {
+        Self(1)
+    }
+
+    #[inline(always)]
+    fn always_emit(&mut self) -> &mut Self {
+        self.0 = self.0 | 2;
+        self
+    }
 
-/// Set the W bit in the REX prefix to zero.  By default it will be set to 1,
-/// indicating a 64-bit operation.
-const F_CLEAR_REX_W: u32 = 2;
+    #[inline(always)]
+    fn must_clear_w(&self) -> bool {
+        (self.0 & 1) != 0
+    }
+    #[inline(always)]
+    fn must_always_emit(&self) -> bool {
+        (self.0 & 2) != 0
+    }
+
+    #[inline(always)]
+    fn emit_two_op(&self, sink: &mut MachBuffer<Inst>, enc_g: u8, enc_e: u8) {
+        let w = if self.must_clear_w() { 0 } else { 1 };
+        let r = (enc_g >> 3) & 1;
+        let x = 0;
+        let b = (enc_e >> 3) & 1;
+        let rex = 0x40 | (w << 3) | (r << 2) | (x << 1) | b;
+        if rex != 0x40 || self.must_always_emit() {
+            sink.put1(rex);
+        }
+    }
+
+    #[inline(always)]
+    fn emit_three_op(&self, sink: &mut MachBuffer<Inst>, enc_g: u8, enc_index: u8, enc_base: u8) {
+        let w = if self.must_clear_w() { 0 } else { 1 };
+        let r = (enc_g >> 3) & 1;
+        let x = (enc_index >> 3) & 1;
+        let b = (enc_base >> 3) & 1;
+        let rex = 0x40 | (w << 3) | (r << 2) | (x << 1) | b;
+        if rex != 0x40 || self.must_always_emit() {
+            sink.put1(rex);
+        }
+    }
+}
 
-/// For specifying the legacy prefixes (or `PfxNone` if no prefix required) to
-/// be used at the start an instruction. A select prefix may be required for
+/// For specifying the legacy prefixes (or `None` if no prefix required) to
+/// be used at the start an instruction. A given prefix may be required for
 /// various operations, including instructions that operate on GPR, SSE, and Vex
 /// registers.
 enum LegacyPrefix {
-    PfxNone,
-    Pfx66,
-    PfxF2,
-    PfxF3,
+    None,
+    _66,
+    _F2,
+    _F3,
+}
+
+impl LegacyPrefix {
+    #[inline(always)]
+    fn emit(&self, sink: &mut MachBuffer<Inst>) {
+        match self {
+            LegacyPrefix::_66 => sink.put1(0x66),
+            LegacyPrefix::_F2 => sink.put1(0xF2),
+            LegacyPrefix::_F3 => sink.put1(0xF3),
+            LegacyPrefix::None => (),
+        }
+    }
 }
+
 /// This is the core 'emit' function for instructions that reference memory.
 ///
-/// For an instruction that has as operands a register `encG` and a memory
-/// address `memE`, create and emit, first the REX prefix, then caller-supplied
-/// opcode byte(s) (`opcodes` and `numOpcodes`), then the MOD/RM byte, then
-/// optionally, a SIB byte, and finally optionally an immediate that will be
-/// derived from the `memE` operand.  For most instructions up to and including
-/// SSE4.2, that will be the whole instruction.
+/// For an instruction that has as operands a reg encoding `enc_g` and a memory address `mem_e`,
+/// create and emit:
+/// - first the REX prefix,
+/// - then caller-supplied opcode byte(s) (`opcodes` and `num_opcodes`),
+/// - then the MOD/RM byte,
+/// - then optionally, a SIB byte,
+/// - and finally optionally an immediate that will be derived from the `mem_e` operand.
+///
+/// For most instructions up to and including SSE4.2, that will be the whole instruction: this is
+/// what we call "standard" instructions, and abbreviate "std" in the name here. VEX instructions
+/// will require their own emitter functions.
 ///
-/// The opcodes are written bigendianly for the convenience of callers.  For
-/// example, if the opcode bytes to be emitted are, in this order, F3 0F 27,
-/// then the caller should pass `opcodes` == 0xF3_0F_27 and `numOpcodes` == 3.
+/// This will also work for 32-bits x86 instructions, assuming no REX prefix is provided.
 ///
-/// The register operand is represented here not as a `Reg` but as its hardware
-/// encoding, `encG`.  `flags` can specify special handling for the REX prefix.
-/// By default, the REX prefix will indicate a 64-bit operation and will be
-/// deleted if it is redundant (0x40).  Note that for a 64-bit operation, the
-/// REX prefix will normally never be redundant, since REX.W must be 1 to
+/// The opcodes are written bigendianly for the convenience of callers.  For example, if the opcode
+/// bytes to be emitted are, in this order, F3 0F 27, then the caller should pass `opcodes` ==
+/// 0xF3_0F_27 and `num_opcodes` == 3.
+///
+/// The register operand is represented here not as a `Reg` but as its hardware encoding, `enc_g`.
+/// `rex` can specify special handling for the REX prefix.  By default, the REX prefix will
+/// indicate a 64-bit operation and will be deleted if it is redundant (0x40).  Note that for a
+/// 64-bit operation, the REX prefix will normally never be redundant, since REX.W must be 1 to
 /// indicate a 64-bit operation.
-fn emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE(
+fn emit_std_enc_mem(
     sink: &mut MachBuffer<Inst>,
     prefix: LegacyPrefix,
     opcodes: u32,
-    mut numOpcodes: usize,
-    encG: u8,
-    memE: &Addr,
-    flags: u32,
+    mut num_opcodes: usize,
+    enc_g: u8,
+    mem_e: &Addr,
+    rex: RexFlags,
 ) {
-    // General comment for this function: the registers in `memE` must be
+    // General comment for this function: the registers in `mem_e` must be
     // 64-bit integer registers, because they are part of an address
-    // expression.  But `encG` can be derived from a register of any class.
-    let clearRexW = (flags & F_CLEAR_REX_W) != 0;
-    let retainRedundant = (flags & F_RETAIN_REDUNDANT_REX) != 0;
-
-    // Lower the prefix if applicable.
-    match prefix {
-        LegacyPrefix::Pfx66 => sink.put1(0x66),
-        LegacyPrefix::PfxF2 => sink.put1(0xF2),
-        LegacyPrefix::PfxF3 => sink.put1(0xF3),
-        LegacyPrefix::PfxNone => (),
-    }
-    match memE {
-        Addr::IR { simm32, base: regE } => {
-            // First, cook up the REX byte.  This is easy.
-            let encE = iregEnc(*regE);
-            let w = if clearRexW { 0 } else { 1 };
-            let r = (encG >> 3) & 1;
-            let x = 0;
-            let b = (encE >> 3) & 1;
-            let rex = 0x40 | (w << 3) | (r << 2) | (x << 1) | b;
-            if rex != 0x40 || retainRedundant {
-                sink.put1(rex);
-            }
+    // expression.  But `enc_g` can be derived from a register of any class.
+
+    prefix.emit(sink);
+
+    match mem_e {
+        Addr::ImmReg { simm32, base } => {
+            // First, the REX byte.
+            let enc_e = int_reg_enc(*base);
+            rex.emit_two_op(sink, enc_g, enc_e);
+
             // Now the opcode(s).  These include any other prefixes the caller
             // hands to us.
-            while numOpcodes > 0 {
-                numOpcodes -= 1;
-                sink.put1(((opcodes >> (numOpcodes << 3)) & 0xFF) as u8);
+            while num_opcodes > 0 {
+                num_opcodes -= 1;
+                sink.put1(((opcodes >> (num_opcodes << 3)) & 0xFF) as u8);
             }
+
             // Now the mod/rm and associated immediates.  This is
             // significantly complicated due to the multiple special cases.
             if *simm32 == 0
-                && encE != regs::ENC_RSP
-                && encE != regs::ENC_RBP
-                && encE != regs::ENC_R12
-                && encE != regs::ENC_R13
+                && enc_e != regs::ENC_RSP
+                && enc_e != regs::ENC_RBP
+                && enc_e != regs::ENC_R12
+                && enc_e != regs::ENC_R13
             {
                 // FIXME JRS 2020Feb11: those four tests can surely be
                 // replaced by a single mask-and-compare check.  We should do
                 // that because this routine is likely to be hot.
-                sink.put1(mkModRegRM(0, encG & 7, encE & 7));
-            } else if *simm32 == 0 && (encE == regs::ENC_RSP || encE == regs::ENC_R12) {
-                sink.put1(mkModRegRM(0, encG & 7, 4));
+                sink.put1(encode_modrm(0, enc_g & 7, enc_e & 7));
+            } else if *simm32 == 0 && (enc_e == regs::ENC_RSP || enc_e == regs::ENC_R12) {
+                sink.put1(encode_modrm(0, enc_g & 7, 4));
                 sink.put1(0x24);
-            } else if low8willSXto32(*simm32) && encE != regs::ENC_RSP && encE != regs::ENC_R12 {
-                sink.put1(mkModRegRM(1, encG & 7, encE & 7));
+            } else if low8_will_sign_extend_to_32(*simm32)
+                && enc_e != regs::ENC_RSP
+                && enc_e != regs::ENC_R12
+            {
+                sink.put1(encode_modrm(1, enc_g & 7, enc_e & 7));
                 sink.put1((simm32 & 0xFF) as u8);
-            } else if encE != regs::ENC_RSP && encE != regs::ENC_R12 {
-                sink.put1(mkModRegRM(2, encG & 7, encE & 7));
+            } else if enc_e != regs::ENC_RSP && enc_e != regs::ENC_R12 {
+                sink.put1(encode_modrm(2, enc_g & 7, enc_e & 7));
                 sink.put4(*simm32);
-            } else if (encE == regs::ENC_RSP || encE == regs::ENC_R12) && low8willSXto32(*simm32) {
+            } else if (enc_e == regs::ENC_RSP || enc_e == regs::ENC_R12)
+                && low8_will_sign_extend_to_32(*simm32)
+            {
                 // REX.B distinguishes RSP from R12
-                sink.put1(mkModRegRM(1, encG & 7, 4));
+                sink.put1(encode_modrm(1, enc_g & 7, 4));
                 sink.put1(0x24);
                 sink.put1((simm32 & 0xFF) as u8);
-            } else if encE == regs::ENC_R12 || encE == regs::ENC_RSP {
+            } else if enc_e == regs::ENC_R12 || enc_e == regs::ENC_RSP {
                 //.. wait for test case for RSP case
                 // REX.B distinguishes RSP from R12
-                sink.put1(mkModRegRM(2, encG & 7, 4));
+                sink.put1(encode_modrm(2, enc_g & 7, 4));
                 sink.put1(0x24);
                 sink.put4(*simm32);
             } else {
-                unreachable!("emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE: IR");
+                unreachable!("ImmReg");
             }
         }
-        // Bizarrely, the IRRS case is much simpler.
-        Addr::IRRS {
+
+        Addr::ImmRegRegShift {
             simm32,
-            base: regBase,
-            index: regIndex,
+            base: reg_base,
+            index: reg_index,
             shift,
         } => {
-            let encBase = iregEnc(*regBase);
-            let encIndex = iregEnc(*regIndex);
-            // The rex byte
-            let w = if clearRexW { 0 } else { 1 };
-            let r = (encG >> 3) & 1;
-            let x = (encIndex >> 3) & 1;
-            let b = (encBase >> 3) & 1;
-            let rex = 0x40 | (w << 3) | (r << 2) | (x << 1) | b;
-            if rex != 0x40 || retainRedundant {
-                sink.put1(rex);
-            }
-            // All other prefixes and opcodes
-            while numOpcodes > 0 {
-                numOpcodes -= 1;
-                sink.put1(((opcodes >> (numOpcodes << 3)) & 0xFF) as u8);
+            let enc_base = int_reg_enc(*reg_base);
+            let enc_index = int_reg_enc(*reg_index);
+
+            // The rex byte.
+            rex.emit_three_op(sink, enc_g, enc_index, enc_base);
+
+            // All other prefixes and opcodes.
+            while num_opcodes > 0 {
+                num_opcodes -= 1;
+                sink.put1(((opcodes >> (num_opcodes << 3)) & 0xFF) as u8);
             }
-            // modrm, SIB, immediates
-            if low8willSXto32(*simm32) && encIndex != regs::ENC_RSP {
-                sink.put1(mkModRegRM(1, encG & 7, 4));
-                sink.put1(mkSIB(*shift, encIndex & 7, encBase & 7));
+
+            // modrm, SIB, immediates.
+            if low8_will_sign_extend_to_32(*simm32) && enc_index != regs::ENC_RSP {
+                sink.put1(encode_modrm(1, enc_g & 7, 4));
+                sink.put1(encode_sib(*shift, enc_index & 7, enc_base & 7));
                 sink.put1(*simm32 as u8);
-            } else if encIndex != regs::ENC_RSP {
-                sink.put1(mkModRegRM(2, encG & 7, 4));
-                sink.put1(mkSIB(*shift, encIndex & 7, encBase & 7));
+            } else if enc_index != regs::ENC_RSP {
+                sink.put1(encode_modrm(2, enc_g & 7, 4));
+                sink.put1(encode_sib(*shift, enc_index & 7, enc_base & 7));
                 sink.put4(*simm32);
             } else {
-                panic!("emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE: IRRS");
+                panic!("ImmRegRegShift");
             }
         }
     }
 }
 
-/// This is the core 'emit' function for instructions that do not reference
-/// memory.
+/// This is the core 'emit' function for instructions that do not reference memory.
 ///
-/// This is conceptually the same as
-/// emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE, except it is for the case
-/// where the E operand is a register rather than memory.  Hence it is much
-/// simpler.
-fn emit_REX_OPCODES_MODRM_encG_encE(
+/// This is conceptually the same as emit_modrm_sib_enc_ge, except it is for the case where the E
+/// operand is a register rather than memory.  Hence it is much simpler.
+fn emit_std_enc_enc(
     sink: &mut MachBuffer<Inst>,
     prefix: LegacyPrefix,
     opcodes: u32,
-    mut numOpcodes: usize,
-    encG: u8,
-    encE: u8,
-    flags: u32,
+    mut num_opcodes: usize,
+    enc_g: u8,
+    enc_e: u8,
+    rex: RexFlags,
 ) {
     // EncG and EncE can be derived from registers of any class, and they
     // don't even have to be from the same class.  For example, for an
     // integer-to-FP conversion insn, one might be RegClass::I64 and the other
     // RegClass::V128.
-    let clearRexW = (flags & F_CLEAR_REX_W) != 0;
-    let retainRedundant = (flags & F_RETAIN_REDUNDANT_REX) != 0;
-
-    // The operand-size override
-    match prefix {
-        LegacyPrefix::Pfx66 => sink.put1(0x66),
-        LegacyPrefix::PfxF2 => sink.put1(0xF2),
-        LegacyPrefix::PfxF3 => sink.put1(0xF3),
-        LegacyPrefix::PfxNone => (),
-    }
 
-    // The rex byte
-    let w = if clearRexW { 0 } else { 1 };
-    let r = (encG >> 3) & 1;
-    let x = 0;
-    let b = (encE >> 3) & 1;
-    let rex = 0x40 | (w << 3) | (r << 2) | (x << 1) | b;
+    // The operand-size override.
+    prefix.emit(sink);
 
-    if rex != 0x40 || retainRedundant {
-        sink.put1(rex);
-    }
+    // The rex byte.
+    rex.emit_two_op(sink, enc_g, enc_e);
 
-    // All other prefixes and opcodes
-    while numOpcodes > 0 {
-        numOpcodes -= 1;
-        sink.put1(((opcodes >> (numOpcodes << 3)) & 0xFF) as u8);
+    // All other prefixes and opcodes.
+    while num_opcodes > 0 {
+        num_opcodes -= 1;
+        sink.put1(((opcodes >> (num_opcodes << 3)) & 0xFF) as u8);
     }
+
     // Now the mod/rm byte.  The instruction we're generating doesn't access
     // memory, so there is no SIB byte or immediate -- we're done.
-    sink.put1(mkModRegRM(3, encG & 7, encE & 7));
+    sink.put1(encode_modrm(3, enc_g & 7, enc_e & 7));
 }
 
 // These are merely wrappers for the above two functions that facilitate passing
 // actual `Reg`s rather than their encodings.
 
-fn emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+fn emit_std_reg_mem(
     sink: &mut MachBuffer<Inst>,
     prefix: LegacyPrefix,
     opcodes: u32,
-    numOpcodes: usize,
-    regG: Reg,
-    memE: &Addr,
-    flags: u32,
+    num_opcodes: usize,
+    reg_g: Reg,
+    mem_e: &Addr,
+    rex: RexFlags,
 ) {
-    // JRS FIXME 2020Feb07: this should really just be `regEnc` not `iregEnc`
-    let encG = iregEnc(regG);
-    emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE(sink, prefix, opcodes, numOpcodes, encG, memE, flags);
+    let enc_g = reg_enc(reg_g);
+    emit_std_enc_mem(sink, prefix, opcodes, num_opcodes, enc_g, mem_e, rex);
 }
 
-fn emit_REX_OPCODES_MODRM_regG_regE(
+fn emit_std_reg_reg(
     sink: &mut MachBuffer<Inst>,
     prefix: LegacyPrefix,
     opcodes: u32,
-    numOpcodes: usize,
-    regG: Reg,
-    regE: Reg,
-    flags: u32,
+    num_opcodes: usize,
+    reg_g: Reg,
+    reg_e: Reg,
+    rex: RexFlags,
 ) {
-    // JRS FIXME 2020Feb07: these should really just be `regEnc` not `iregEnc`
-    let encG = iregEnc(regG);
-    let encE = iregEnc(regE);
-    emit_REX_OPCODES_MODRM_encG_encE(sink, prefix, opcodes, numOpcodes, encG, encE, flags);
+    let enc_g = reg_enc(reg_g);
+    let enc_e = reg_enc(reg_e);
+    emit_std_enc_enc(sink, prefix, opcodes, num_opcodes, enc_g, enc_e, rex);
 }
 
 /// Write a suitable number of bits from an imm64 to the sink.
@@ -289,7 +333,7 @@ fn emit_simm(sink: &mut MachBuffer<Inst>, size: u8, simm32: u32) {
         8 | 4 => sink.put4(simm32),
         2 => sink.put2(simm32 as u16),
         1 => sink.put1(simm32 as u8),
-        _ => panic!("x64::Inst::emit_simm: unreachable"),
+        _ => unreachable!(),
     }
 }
 
@@ -348,490 +392,504 @@ fn emit_simm(sink: &mut MachBuffer<Inst>, size: u8, simm32: u32) {
 pub(crate) fn emit(inst: &Inst, sink: &mut MachBuffer<Inst>) {
     match inst {
         Inst::Nop { len: 0 } => {}
+
         Inst::Alu_RMI_R {
             is_64,
             op,
-            src: srcE,
-            dst: regG,
+            src,
+            dst: reg_g,
         } => {
-            let flags = if *is_64 { F_NONE } else { F_CLEAR_REX_W };
-            if *op == RMI_R_Op::Mul {
+            let rex = if *is_64 {
+                RexFlags::set_w()
+            } else {
+                RexFlags::clear_w()
+            };
+
+            if *op == AluRmiROpcode::Mul {
                 // We kinda freeloaded Mul into RMI_R_Op, but it doesn't fit the usual pattern, so
                 // we have to special-case it.
-                match srcE {
-                    RMI::R { reg: regE } => {
-                        emit_REX_OPCODES_MODRM_regG_regE(
+                match src {
+                    RegMemImm::Reg { reg: reg_e } => {
+                        emit_std_reg_reg(
                             sink,
-                            LegacyPrefix::PfxNone,
+                            LegacyPrefix::None,
                             0x0FAF,
                             2,
-                            regG.to_reg(),
-                            *regE,
-                            flags,
+                            reg_g.to_reg(),
+                            *reg_e,
+                            rex,
                         );
                     }
-                    RMI::M { addr } => {
-                        emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+
+                    RegMemImm::Mem { addr } => {
+                        emit_std_reg_mem(
                             sink,
-                            LegacyPrefix::PfxNone,
+                            LegacyPrefix::None,
                             0x0FAF,
                             2,
-                            regG.to_reg(),
+                            reg_g.to_reg(),
                             addr,
-                            flags,
+                            rex,
                         );
                     }
-                    RMI::I { simm32 } => {
-                        let useImm8 = low8willSXto32(*simm32);
+
+                    RegMemImm::Imm { simm32 } => {
+                        let useImm8 = low8_will_sign_extend_to_32(*simm32);
                         let opcode = if useImm8 { 0x6B } else { 0x69 };
-                        // Yes, really, regG twice.
-                        emit_REX_OPCODES_MODRM_regG_regE(
+                        // Yes, really, reg_g twice.
+                        emit_std_reg_reg(
                             sink,
-                            LegacyPrefix::PfxNone,
+                            LegacyPrefix::None,
                             opcode,
                             1,
-                            regG.to_reg(),
-                            regG.to_reg(),
-                            flags,
+                            reg_g.to_reg(),
+                            reg_g.to_reg(),
+                            rex,
                         );
                         emit_simm(sink, if useImm8 { 1 } else { 4 }, *simm32);
                     }
                 }
             } else {
-                let (opcode_R, opcode_M, subopcode_I) = match op {
-                    RMI_R_Op::Add => (0x01, 0x03, 0),
-                    RMI_R_Op::Sub => (0x29, 0x2B, 5),
-                    RMI_R_Op::And => (0x21, 0x23, 4),
-                    RMI_R_Op::Or => (0x09, 0x0B, 1),
-                    RMI_R_Op::Xor => (0x31, 0x33, 6),
-                    RMI_R_Op::Mul => panic!("unreachable"),
+                let (opcode_r, opcode_m, subopcode_i) = match op {
+                    AluRmiROpcode::Add => (0x01, 0x03, 0),
+                    AluRmiROpcode::Sub => (0x29, 0x2B, 5),
+                    AluRmiROpcode::And => (0x21, 0x23, 4),
+                    AluRmiROpcode::Or => (0x09, 0x0B, 1),
+                    AluRmiROpcode::Xor => (0x31, 0x33, 6),
+                    AluRmiROpcode::Mul => panic!("unreachable"),
                 };
-                match srcE {
-                    RMI::R { reg: regE } => {
-                        // Note.  The arguments .. regE .. regG .. sequence
+
+                match src {
+                    RegMemImm::Reg { reg: regE } => {
+                        // Note.  The arguments .. regE .. reg_g .. sequence
                         // here is the opposite of what is expected.  I'm not
                         // sure why this is.  But I am fairly sure that the
                         // arg order could be switched back to the expected
-                        // .. regG .. regE .. if opcode_rr is also switched
+                        // .. reg_g .. regE .. if opcode_rr is also switched
                         // over to the "other" basic integer opcode (viz, the
                         // R/RM vs RM/R duality).  However, that would mean
                         // that the test results won't be in accordance with
                         // the GNU as reference output.  In other words, the
                         // inversion exists as a result of using GNU as as a
                         // gold standard.
-                        emit_REX_OPCODES_MODRM_regG_regE(
+                        emit_std_reg_reg(
                             sink,
-                            LegacyPrefix::PfxNone,
-                            opcode_R,
+                            LegacyPrefix::None,
+                            opcode_r,
                             1,
                             *regE,
-                            regG.to_reg(),
-                            flags,
+                            reg_g.to_reg(),
+                            rex,
                         );
                         // NB: if this is ever extended to handle byte size
                         // ops, be sure to retain redundant REX prefixes.
                     }
-                    RMI::M { addr } => {
+
+                    RegMemImm::Mem { addr } => {
                         // Whereas here we revert to the "normal" G-E ordering.
-                        emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                        emit_std_reg_mem(
                             sink,
-                            LegacyPrefix::PfxNone,
-                            opcode_M,
+                            LegacyPrefix::None,
+                            opcode_m,
                             1,
-                            regG.to_reg(),
+                            reg_g.to_reg(),
                             addr,
-                            flags,
+                            rex,
                         );
                     }
-                    RMI::I { simm32 } => {
-                        let useImm8 = low8willSXto32(*simm32);
+
+                    RegMemImm::Imm { simm32 } => {
+                        let useImm8 = low8_will_sign_extend_to_32(*simm32);
                         let opcode = if useImm8 { 0x83 } else { 0x81 };
                         // And also here we use the "normal" G-E ordering.
-                        let encG = iregEnc(regG.to_reg());
-                        emit_REX_OPCODES_MODRM_encG_encE(
+                        let enc_g = int_reg_enc(reg_g.to_reg());
+                        emit_std_enc_enc(
                             sink,
-                            LegacyPrefix::PfxNone,
+                            LegacyPrefix::None,
                             opcode,
                             1,
-                            subopcode_I,
-                            encG,
-                            flags,
+                            subopcode_i,
+                            enc_g,
+                            rex,
                         );
                         emit_simm(sink, if useImm8 { 1 } else { 4 }, *simm32);
                     }
                 }
             }
         }
+
         Inst::Imm_R {
             dst_is_64,
             simm64,
             dst,
         } => {
-            let encDst = iregEnc(dst.to_reg());
+            let enc_dst = int_reg_enc(dst.to_reg());
             if *dst_is_64 {
                 // FIXME JRS 2020Feb10: also use the 32-bit case here when
                 // possible
-                sink.put1(0x48 | ((encDst >> 3) & 1));
-                sink.put1(0xB8 | (encDst & 7));
+                sink.put1(0x48 | ((enc_dst >> 3) & 1));
+                sink.put1(0xB8 | (enc_dst & 7));
                 sink.put8(*simm64);
             } else {
-                if ((encDst >> 3) & 1) == 1 {
+                if ((enc_dst >> 3) & 1) == 1 {
                     sink.put1(0x41);
                 }
-                sink.put1(0xB8 | (encDst & 7));
+                sink.put1(0xB8 | (enc_dst & 7));
                 sink.put4(*simm64 as u32);
             }
         }
+
         Inst::Mov_R_R { is_64, src, dst } => {
-            let flags = if *is_64 { F_NONE } else { F_CLEAR_REX_W };
-            emit_REX_OPCODES_MODRM_regG_regE(
-                sink,
-                LegacyPrefix::PfxNone,
-                0x89,
-                1,
-                *src,
-                dst.to_reg(),
-                flags,
-            );
+            let rex = if *is_64 {
+                RexFlags::set_w()
+            } else {
+                RexFlags::clear_w()
+            };
+            emit_std_reg_reg(sink, LegacyPrefix::None, 0x89, 1, *src, dst.to_reg(), rex);
         }
+
         Inst::MovZX_M_R { extMode, addr, dst } => {
             match extMode {
                 ExtMode::BL => {
                     // MOVZBL is (REX.W==0) 0F B6 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FB6,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 ExtMode::BQ => {
                     // MOVZBQ is (REX.W==1) 0F B6 /r
                     // I'm not sure why the Intel manual offers different
                     // encodings for MOVZBQ than for MOVZBL.  AIUI they should
                     // achieve the same, since MOVZBL is just going to zero out
                     // the upper half of the destination anyway.
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FB6,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
+
                 ExtMode::WL => {
                     // MOVZWL is (REX.W==0) 0F B7 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FB7,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 ExtMode::WQ => {
                     // MOVZWQ is (REX.W==1) 0F B7 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FB7,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
+
                 ExtMode::LQ => {
                     // This is just a standard 32 bit load, and we rely on the
                     // default zero-extension rule to perform the extension.
                     // MOV r/m32, r32 is (REX.W==0) 8B /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x8B,
                         1,
                         dst.to_reg(),
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
             }
         }
-        Inst::Mov64_M_R { addr, dst } => emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+
+        Inst::Mov64_M_R { addr, dst } => emit_std_reg_mem(
             sink,
-            LegacyPrefix::PfxNone,
+            LegacyPrefix::None,
             0x8B,
             1,
             dst.to_reg(),
             addr,
-            F_NONE,
+            RexFlags::set_w(),
         ),
+
         Inst::MovSX_M_R { extMode, addr, dst } => {
             match extMode {
                 ExtMode::BL => {
                     // MOVSBL is (REX.W==0) 0F BE /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FBE,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 ExtMode::BQ => {
                     // MOVSBQ is (REX.W==1) 0F BE /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FBE,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
+
                 ExtMode::WL => {
                     // MOVSWL is (REX.W==0) 0F BF /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FBF,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 ExtMode::WQ => {
                     // MOVSWQ is (REX.W==1) 0F BF /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x0FBF,
                         2,
                         dst.to_reg(),
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
+
                 ExtMode::LQ => {
                     // MOVSLQ is (REX.W==1) 63 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x63,
                         1,
                         dst.to_reg(),
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
             }
         }
+
         Inst::Mov_R_M { size, src, addr } => {
             match size {
                 1 => {
                     // This is one of the few places where the presence of a
                     // redundant REX prefix changes the meaning of the
                     // instruction.
-                    let encSrc = iregEnc(*src);
-                    let retainRedundantRex = if encSrc >= 4 && encSrc <= 7 {
-                        F_RETAIN_REDUNDANT_REX
-                    } else {
-                        0
+                    let mut rex = RexFlags::clear_w();
+
+                    let enc_src = int_reg_enc(*src);
+                    if enc_src >= 4 && enc_src <= 7 {
+                        rex.always_emit();
                     };
+
                     // MOV r8, r/m8 is (REX.W==0) 88 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
-                        sink,
-                        LegacyPrefix::PfxNone,
-                        0x88,
-                        1,
-                        *src,
-                        addr,
-                        F_CLEAR_REX_W | retainRedundantRex,
-                    )
+                    emit_std_reg_mem(sink, LegacyPrefix::None, 0x88, 1, *src, addr, rex)
                 }
+
                 2 => {
                     // MOV r16, r/m16 is 66 (REX.W==0) 89 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::Pfx66,
+                        LegacyPrefix::_66,
                         0x89,
                         1,
                         *src,
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 4 => {
                     // MOV r32, r/m32 is (REX.W==0) 89 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x89,
                         1,
                         *src,
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     )
                 }
+
                 8 => {
                     // MOV r64, r/m64 is (REX.W==1) 89 /r
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0x89,
                         1,
                         *src,
                         addr,
-                        F_NONE,
+                        RexFlags::set_w(),
                     )
                 }
+
                 _ => panic!("x64::Inst::Mov_R_M::emit: unreachable"),
             }
         }
+
         Inst::Shift_R {
             is_64,
             kind,
             num_bits,
             dst,
         } => {
-            let encDst = iregEnc(dst.to_reg());
+            let enc_dst = int_reg_enc(dst.to_reg());
             let subopcode = match kind {
                 ShiftKind::Left => 4,
                 ShiftKind::RightZ => 5,
                 ShiftKind::RightS => 7,
             };
+
+            let rex = if *is_64 {
+                RexFlags::set_w()
+            } else {
+                RexFlags::clear_w()
+            };
+
             match num_bits {
                 None => {
                     // SHL/SHR/SAR %cl, reg32 is (REX.W==0) D3 /subopcode
                     // SHL/SHR/SAR %cl, reg64 is (REX.W==1) D3 /subopcode
-                    emit_REX_OPCODES_MODRM_encG_encE(
-                        sink,
-                        LegacyPrefix::PfxNone,
-                        0xD3,
-                        1,
-                        subopcode,
-                        encDst,
-                        if *is_64 { F_NONE } else { F_CLEAR_REX_W },
-                    );
+                    emit_std_enc_enc(sink, LegacyPrefix::None, 0xD3, 1, subopcode, enc_dst, rex);
                 }
+
                 Some(num_bits) => {
                     // SHL/SHR/SAR $ib, reg32 is (REX.W==0) C1 /subopcode ib
                     // SHL/SHR/SAR $ib, reg64 is (REX.W==1) C1 /subopcode ib
                     // When the shift amount is 1, there's an even shorter encoding, but we don't
                     // bother with that nicety here.
-                    emit_REX_OPCODES_MODRM_encG_encE(
-                        sink,
-                        LegacyPrefix::PfxNone,
-                        0xC1,
-                        1,
-                        subopcode,
-                        encDst,
-                        if *is_64 { F_NONE } else { F_CLEAR_REX_W },
-                    );
+                    emit_std_enc_enc(sink, LegacyPrefix::None, 0xC1, 1, subopcode, enc_dst, rex);
                     sink.put1(*num_bits);
                 }
             }
         }
+
         Inst::Cmp_RMI_R {
             size,
-            src: srcE,
-            dst: regG,
+            src: src_e,
+            dst: reg_g,
         } => {
-            let mut retainRedundantRex = 0;
-            let mut prefix = LegacyPrefix::PfxNone;
-            if *size == 1 {
-                // Here, a redundant REX prefix changes the meaning of the
-                // instruction.
-                let encG = iregEnc(*regG);
-                if encG >= 4 && encG <= 7 {
-                    retainRedundantRex = F_RETAIN_REDUNDANT_REX;
-                }
-            }
+            let mut prefix = LegacyPrefix::None;
             if *size == 2 {
-                prefix = LegacyPrefix::Pfx66;
+                prefix = LegacyPrefix::_66;
             }
-            let mut flags = match size {
-                8 => F_NONE,
-                4 | 2 => F_CLEAR_REX_W,
-                1 => F_CLEAR_REX_W | retainRedundantRex,
+
+            let mut rex = match size {
+                8 => RexFlags::set_w(),
+                4 | 2 => RexFlags::clear_w(),
+                1 => {
+                    let mut rex = RexFlags::clear_w();
+                    // Here, a redundant REX prefix changes the meaning of the instruction.
+                    let enc_g = int_reg_enc(*reg_g);
+                    if enc_g >= 4 && enc_g <= 7 {
+                        rex.always_emit();
+                    }
+                    rex
+                }
                 _ => panic!("x64::Inst::Cmp_RMI_R::emit: unreachable"),
             };
-            match srcE {
-                RMI::R { reg: regE } => {
+
+            match src_e {
+                RegMemImm::Reg { reg: regE } => {
                     let opcode = if *size == 1 { 0x38 } else { 0x39 };
                     if *size == 1 {
                         // We also need to check whether the E register forces
                         // the use of a redundant REX.
-                        let encE = iregEnc(*regE);
+                        let encE = int_reg_enc(*regE);
                         if encE >= 4 && encE <= 7 {
-                            flags |= F_RETAIN_REDUNDANT_REX;
+                            rex.always_emit();
                         }
                     }
                     // Same comment re swapped args as for Alu_RMI_R.
-                    emit_REX_OPCODES_MODRM_regG_regE(sink, prefix, opcode, 1, *regE, *regG, flags);
+                    emit_std_reg_reg(sink, prefix, opcode, 1, *regE, *reg_g, rex);
                 }
-                RMI::M { addr } => {
+
+                RegMemImm::Mem { addr } => {
                     let opcode = if *size == 1 { 0x3A } else { 0x3B };
                     // Whereas here we revert to the "normal" G-E ordering.
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
-                        sink, prefix, opcode, 1, *regG, addr, flags,
-                    );
+                    emit_std_reg_mem(sink, prefix, opcode, 1, *reg_g, addr, rex);
                 }
-                RMI::I { simm32 } => {
+
+                RegMemImm::Imm { simm32 } => {
                     // FIXME JRS 2020Feb11: there are shorter encodings for
                     // cmp $imm, rax/eax/ax/al.
-                    let useImm8 = low8willSXto32(*simm32);
+                    let use_imm8 = low8_will_sign_extend_to_32(*simm32);
                     let opcode = if *size == 1 {
                         0x80
-                    } else if useImm8 {
+                    } else if use_imm8 {
                         0x83
                     } else {
                         0x81
                     };
+
                     // And also here we use the "normal" G-E ordering.
-                    let encG = iregEnc(*regG);
-                    emit_REX_OPCODES_MODRM_encG_encE(
-                        sink, prefix, opcode, 1, 7, /*subopcode*/
-                        encG, flags,
-                    );
-                    emit_simm(sink, if useImm8 { 1 } else { *size }, *simm32);
+                    let enc_g = int_reg_enc(*reg_g);
+                    emit_std_enc_enc(sink, prefix, opcode, 1, 7 /*subopcode*/, enc_g, rex);
+                    emit_simm(sink, if use_imm8 { 1 } else { *size }, *simm32);
                 }
             }
         }
+
         Inst::Push64 { src } => {
             match src {
-                RMI::R { reg } => {
-                    let encReg = iregEnc(*reg);
-                    let rex = 0x40 | ((encReg >> 3) & 1);
+                RegMemImm::Reg { reg } => {
+                    let enc_reg = int_reg_enc(*reg);
+                    let rex = 0x40 | ((enc_reg >> 3) & 1);
                     if rex != 0x40 {
                         sink.put1(rex);
                     }
-                    sink.put1(0x50 | (encReg & 7));
+                    sink.put1(0x50 | (enc_reg & 7));
                 }
-                RMI::M { addr } => {
-                    emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE(
+
+                RegMemImm::Mem { addr } => {
+                    emit_std_enc_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0xFF,
                         1,
                         6, /*subopcode*/
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     );
                 }
-                RMI::I { simm32 } => {
-                    if low8willSXto64(*simm32) {
+
+                RegMemImm::Imm { simm32 } => {
+                    if low8_will_sign_extend_to_64(*simm32) {
                         sink.put1(0x6A);
                         sink.put1(*simm32 as u8);
                     } else {
@@ -841,8 +899,9 @@ pub(crate) fn emit(inst: &Inst, sink: &mut MachBuffer<Inst>) {
                 }
             }
         }
+
         Inst::Pop64 { dst } => {
-            let encDst = iregEnc(dst.to_reg());
+            let encDst = int_reg_enc(dst.to_reg());
             if encDst >= 8 {
                 // 0x41 == REX.{W=0, B=1}.  It seems that REX.W is irrelevant
                 // here.
@@ -850,36 +909,36 @@ pub(crate) fn emit(inst: &Inst, sink: &mut MachBuffer<Inst>) {
             }
             sink.put1(0x58 + (encDst & 7));
         }
-        //
-        // ** Inst::CallKnown
-        //
+
         Inst::CallUnknown { dest } => {
             match dest {
-                RM::R { reg } => {
-                    let regEnc = iregEnc(*reg);
-                    emit_REX_OPCODES_MODRM_encG_encE(
+                RegMem::Reg { reg } => {
+                    let reg_enc = int_reg_enc(*reg);
+                    emit_std_enc_enc(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0xFF,
                         1,
                         2, /*subopcode*/
-                        regEnc,
-                        F_CLEAR_REX_W,
+                        reg_enc,
+                        RexFlags::clear_w(),
                     );
                 }
-                RM::M { addr } => {
-                    emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE(
+
+                RegMem::Mem { addr } => {
+                    emit_std_enc_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0xFF,
                         1,
                         2, /*subopcode*/
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     );
                 }
             }
         }
+
         Inst::Ret {} => sink.put1(0xC3),
 
         Inst::JmpKnown { dest } => {
@@ -895,6 +954,7 @@ pub(crate) fn emit(inst: &Inst, sink: &mut MachBuffer<Inst>) {
             sink.put1(0xE9);
             sink.put4(disp);
         }
+
         Inst::JmpCondSymm {
             cc,
             taken,
@@ -935,83 +995,100 @@ pub(crate) fn emit(inst: &Inst, sink: &mut MachBuffer<Inst>) {
             sink.put1(0xE9);
             sink.put4(nt_disp);
         }
+
         Inst::JmpUnknown { target } => {
             match target {
-                RM::R { reg } => {
-                    let regEnc = iregEnc(*reg);
-                    emit_REX_OPCODES_MODRM_encG_encE(
+                RegMem::Reg { reg } => {
+                    let reg_enc = int_reg_enc(*reg);
+                    emit_std_enc_enc(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0xFF,
                         1,
                         4, /*subopcode*/
-                        regEnc,
-                        F_CLEAR_REX_W,
+                        reg_enc,
+                        RexFlags::clear_w(),
                     );
                 }
-                RM::M { addr } => {
-                    emit_REX_OPCODES_MODRM_SIB_IMM_encG_memE(
+
+                RegMem::Mem { addr } => {
+                    emit_std_enc_mem(
                         sink,
-                        LegacyPrefix::PfxNone,
+                        LegacyPrefix::None,
                         0xFF,
                         1,
                         4, /*subopcode*/
                         addr,
-                        F_CLEAR_REX_W,
+                        RexFlags::clear_w(),
                     );
                 }
             }
         }
+
         Inst::XMM_R_R { op, src, dst } => {
-            let flags = F_CLEAR_REX_W;
             let opcode = match op {
-                SSE_Op::SSE_Movss => 0x0F10,
-                SSE_Op::SSE2_Movsd => 0x0F10,
+                SseOpcode::Movss => 0x0F10,
+                SseOpcode::Movsd => 0x0F10,
                 _ => unimplemented!("XMM_R_R opcode"),
             };
+
             let prefix = match op {
-                SSE_Op::SSE_Movss => LegacyPrefix::PfxF3,
-                SSE_Op::SSE2_Movsd => LegacyPrefix::PfxF2,
+                SseOpcode::Movss => LegacyPrefix::_F3,
+                SseOpcode::Movsd => LegacyPrefix::_F2,
                 _ => unimplemented!("XMM_R_R opcode"),
             };
-            emit_REX_OPCODES_MODRM_regG_regE(sink, prefix, opcode, 2, dst.to_reg(), *src, flags);
+
+            emit_std_reg_reg(
+                sink,
+                prefix,
+                opcode,
+                2,
+                dst.to_reg(),
+                *src,
+                RexFlags::clear_w(),
+            );
         }
+
         Inst::XMM_RM_R {
             op,
             src: srcE,
-            dst: regG,
+            dst: reg_g,
         } => {
-            let flags = F_CLEAR_REX_W;
+            let rex = RexFlags::clear_w();
+
             let opcode = match op {
-                SSE_Op::SSE_Addss => 0x0F58,
-                SSE_Op::SSE_Subss => 0x0F5C,
+                SseOpcode::Addss => 0x0F58,
+                SseOpcode::Subss => 0x0F5C,
                 _ => unimplemented!("XMM_RM_R opcode"),
             };
+
             match srcE {
-                RM::R { reg: regE } => {
-                    emit_REX_OPCODES_MODRM_regG_regE(
+                RegMem::Reg { reg: regE } => {
+                    emit_std_reg_reg(
                         sink,
-                        LegacyPrefix::PfxF3,
+                        LegacyPrefix::_F3,
                         opcode,
                         2,
-                        regG.to_reg(),
+                        reg_g.to_reg(),
                         *regE,
-                        flags,
+                        rex,
                     );
                 }
-                RM::M { addr } => {
-                    emit_REX_OPCODES_MODRM_SIB_IMM_regG_memE(
+
+                RegMem::Mem { addr } => {
+                    emit_std_reg_mem(
                         sink,
-                        LegacyPrefix::PfxF3,
+                        LegacyPrefix::_F3,
                         opcode,
                         2,
-                        regG.to_reg(),
+                        reg_g.to_reg(),
                         addr,
-                        flags,
+                        rex,
                     );
                 }
             }
         }
+
         _ => panic!("x64_emit: unhandled: {} ", inst.show_rru(None)),
     }
 }
diff --git a/cranelift/codegen/src/isa/x64/inst/mod.rs b/cranelift/codegen/src/isa/x64/inst/mod.rs
index 132d93e16..0852f3085 100644
--- a/cranelift/codegen/src/isa/x64/inst/mod.rs
+++ b/cranelift/codegen/src/isa/x64/inst/mod.rs
@@ -44,8 +44,8 @@ pub(crate) enum Inst {
     /// (add sub and or xor mul adc? sbb?) (32 64) (reg addr imm) reg
     Alu_RMI_R {
         is_64: bool,
-        op: RMI_R_Op,
-        src: RMI,
+        op: AluRmiROpcode,
+        src: RegMemImm,
         dst: Writable<Reg>,
     },
 
@@ -103,12 +103,12 @@ pub(crate) enum Inst {
     /// cmp (b w l q) (reg addr imm) reg
     Cmp_RMI_R {
         size: u8, // 1, 2, 4 or 8
-        src: RMI,
+        src: RegMemImm,
         dst: Reg,
     },
 
     /// pushq (reg addr imm)
-    Push64 { src: RMI },
+    Push64 { src: RegMemImm },
 
     /// popq reg
     Pop64 { dst: Writable<Reg> },
@@ -122,7 +122,7 @@ pub(crate) enum Inst {
 
     /// callq (reg mem)
     CallUnknown {
-        dest: RM,
+        dest: RegMem,
         //uses: Set<Reg>,
         //defs: Set<Writable<Reg>>,
     },
@@ -149,18 +149,18 @@ pub(crate) enum Inst {
     },
 
     /// jmpq (reg mem)
-    JmpUnknown { target: RM },
+    JmpUnknown { target: RegMem },
 
     /// (add sub and or xor mul adc? sbb?) (32 64) (reg addr imm) reg
     XMM_RM_R {
-        op: SSE_Op,
-        src: RM,
+        op: SseOpcode,
+        src: RegMem,
         dst: Writable<Reg>,
     },
 
     /// mov (64 32) reg reg
     XMM_R_R {
-        op: SSE_Op,
+        op: SseOpcode,
         src: Reg,
         dst: Writable<Reg>,
     },
@@ -181,7 +181,12 @@ impl Inst {
         Self::Nop { len }
     }
 
-    pub(crate) fn alu_rmi_r(is_64: bool, op: RMI_R_Op, src: RMI, dst: Writable<Reg>) -> Self {
+    pub(crate) fn alu_rmi_r(
+        is_64: bool,
+        op: AluRmiROpcode,
+        src: RegMemImm,
+        dst: Writable<Reg>,
+    ) -> Self {
         debug_assert!(dst.to_reg().get_class() == RegClass::I64);
         Self::Alu_RMI_R {
             is_64,
@@ -209,13 +214,13 @@ impl Inst {
         Inst::Mov_R_R { is_64, src, dst }
     }
 
-    pub(crate) fn xmm_r_r(op: SSE_Op, src: Reg, dst: Writable<Reg>) -> Inst {
+    pub(crate) fn xmm_r_r(op: SseOpcode, src: Reg, dst: Writable<Reg>) -> Inst {
         debug_assert!(src.get_class() == RegClass::V128);
         debug_assert!(dst.to_reg().get_class() == RegClass::V128);
         Inst::XMM_R_R { op, src, dst }
     }
 
-    pub(crate) fn xmm_rm_r(op: SSE_Op, src: RM, dst: Writable<Reg>) -> Self {
+    pub(crate) fn xmm_rm_r(op: SseOpcode, src: RegMem, dst: Writable<Reg>) -> Self {
         debug_assert!(dst.to_reg().get_class() == RegClass::V128);
         Self::XMM_RM_R { op, src, dst }
     }
@@ -267,7 +272,7 @@ impl Inst {
 
     pub(crate) fn cmp_rmi_r(
         size: u8, // 1, 2, 4 or 8
-        src: RMI,
+        src: RegMemImm,
         dst: Reg,
     ) -> Inst {
         debug_assert!(size == 8 || size == 4 || size == 2 || size == 1);
@@ -275,7 +280,7 @@ impl Inst {
         Inst::Cmp_RMI_R { size, src, dst }
     }
 
-    pub(crate) fn push64(src: RMI) -> Inst {
+    pub(crate) fn push64(src: RegMemImm) -> Inst {
         Inst::Push64 { src }
     }
 
@@ -283,7 +288,7 @@ impl Inst {
         Inst::Pop64 { dst }
     }
 
-    pub(crate) fn call_unknown(dest: RM) -> Inst {
+    pub(crate) fn call_unknown(dest: RegMem) -> Inst {
         Inst::CallUnknown { dest }
     }
 
@@ -307,7 +312,7 @@ impl Inst {
         }
     }
 
-    pub(crate) fn jmp_unknown(target: RM) -> Inst {
+    pub(crate) fn jmp_unknown(target: RegMem) -> Inst {
         Inst::JmpUnknown { target }
     }
 }
@@ -645,11 +650,11 @@ fn map_mod<RUM: RegUsageMapper>(m: &RUM, r: &mut Writable<Reg>) {
 impl Addr {
     fn map_uses<RUM: RegUsageMapper>(&mut self, map: &RUM) {
         match self {
-            Addr::IR {
+            Addr::ImmReg {
                 simm32: _,
                 ref mut base,
             } => map_use(map, base),
-            Addr::IRRS {
+            Addr::ImmRegRegShift {
                 simm32: _,
                 ref mut base,
                 ref mut index,
@@ -662,21 +667,21 @@ impl Addr {
     }
 }
 
-impl RMI {
+impl RegMemImm {
     fn map_uses<RUM: RegUsageMapper>(&mut self, map: &RUM) {
         match self {
-            RMI::R { ref mut reg } => map_use(map, reg),
-            RMI::M { ref mut addr } => addr.map_uses(map),
-            RMI::I { simm32: _ } => {}
+            RegMemImm::Reg { ref mut reg } => map_use(map, reg),
+            RegMemImm::Mem { ref mut addr } => addr.map_uses(map),
+            RegMemImm::Imm { simm32: _ } => {}
         }
     }
 }
 
-impl RM {
+impl RegMem {
     fn map_uses<RUM: RegUsageMapper>(&mut self, map: &RUM) {
         match self {
-            RM::R { ref mut reg } => map_use(map, reg),
-            RM::M { ref mut addr } => addr.map_uses(map),
+            RegMem::Reg { ref mut reg } => map_use(map, reg),
+            RegMem::Mem { ref mut addr } => addr.map_uses(map),
         }
     }
 }
@@ -811,6 +816,11 @@ impl MachInst for Inst {
         // %reg.
         match self {
             Self::Mov_R_R { is_64, src, dst } if *is_64 => Some((*dst, *src)),
+            Self::XMM_R_R { op, src, dst }
+                if *op == SseOpcode::Movss || *op == SseOpcode::Movsd =>
+            {
+                Some((*dst, *src))
+            }
             _ => None,
         }
     }
@@ -838,16 +848,19 @@ impl MachInst for Inst {
         }
     }
 
-    fn gen_move(dst_reg: Writable<Reg>, src_reg: Reg, _ty: Type) -> Inst {
+    fn gen_move(dst_reg: Writable<Reg>, src_reg: Reg, ty: Type) -> Inst {
         let rc_dst = dst_reg.to_reg().get_class();
         let rc_src = src_reg.get_class();
         // If this isn't true, we have gone way off the rails.
         debug_assert!(rc_dst == rc_src);
         match rc_dst {
             RegClass::I64 => Inst::mov_r_r(true, src_reg, dst_reg),
-            // TODO: How do you just move 32 bits?
-            RegClass::V128 => Inst::xmm_r_r(SSE_Op::SSE2_Movsd, src_reg, dst_reg),
-            _ => panic!("gen_move(x64): unhandled regclass"),
+            RegClass::V128 => match ty {
+                F32 => Inst::xmm_r_r(SseOpcode::Movss, src_reg, dst_reg),
+                F64 => Inst::xmm_r_r(SseOpcode::Movsd, src_reg, dst_reg),
+                _ => panic!("unexpected V128 type in gen_move"),
+            },
+            _ => panic!("gen_move(x64): unhandled gen_move"),
         }
     }
 
diff --git a/cranelift/codegen/src/isa/x64/lower.rs b/cranelift/codegen/src/isa/x64/lower.rs
index f306d867b..6aa1e3df4 100644
--- a/cranelift/codegen/src/isa/x64/lower.rs
+++ b/cranelift/codegen/src/isa/x64/lower.rs
@@ -3,12 +3,12 @@
 #![allow(dead_code)]
 #![allow(non_snake_case)]
 
+use log::trace;
 use regalloc::{Reg, RegClass, Writable};
 
-use crate::ir::condcodes::IntCC;
 use crate::ir::types;
 use crate::ir::Inst as IRInst;
-use crate::ir::{InstructionData, Opcode, Type};
+use crate::ir::{condcodes::IntCC, InstructionData, Opcode, Type};
 
 use crate::machinst::lower::*;
 use crate::machinst::*;
@@ -86,23 +86,6 @@ fn inst_condcode(data: &InstructionData) -> IntCC {
     }
 }
 
-fn intCC_to_x64_CC(cc: IntCC) -> CC {
-    match cc {
-        IntCC::Equal => CC::Z,
-        IntCC::NotEqual => CC::NZ,
-        IntCC::SignedGreaterThanOrEqual => CC::NL,
-        IntCC::SignedGreaterThan => CC::NLE,
-        IntCC::SignedLessThanOrEqual => CC::LE,
-        IntCC::SignedLessThan => CC::L,
-        IntCC::UnsignedGreaterThanOrEqual => CC::NB,
-        IntCC::UnsignedGreaterThan => CC::NBE,
-        IntCC::UnsignedLessThanOrEqual => CC::BE,
-        IntCC::UnsignedLessThan => CC::B,
-        IntCC::Overflow => CC::O,
-        IntCC::NotOverflow => CC::NO,
-    }
-}
-
 fn input_to_reg<'a>(ctx: Ctx<'a>, iri: IRInst, input: usize) -> Reg {
     let inputs = ctx.get_input(iri, input);
     ctx.use_input_reg(inputs);
@@ -117,10 +100,10 @@ fn output_to_reg<'a>(ctx: Ctx<'a>, iri: IRInst, output: usize) -> Writable<Reg>
 // Top-level instruction lowering entry point, for one instruction.
 
 /// Actually codegen an instruction's results into registers.
-fn lower_insn_to_regs<'a>(ctx: Ctx<'a>, iri: IRInst) {
-    let op = ctx.data(iri).opcode();
-    let ty = if ctx.num_outputs(iri) == 1 {
-        Some(ctx.output_ty(iri, 0))
+fn lower_insn_to_regs<'a>(ctx: Ctx<'a>, inst: IRInst) {
+    let op = ctx.data(inst).opcode();
+    let ty = if ctx.num_outputs(inst) == 1 {
+        Some(ctx.output_ty(inst, 0))
     } else {
         None
     };
@@ -128,54 +111,53 @@ fn lower_insn_to_regs<'a>(ctx: Ctx<'a>, iri: IRInst) {
     // This is all outstandingly feeble.  TODO: much better!
     match op {
         Opcode::Iconst => {
-            if let Some(w64) = iri_to_u64_immediate(ctx, iri) {
+            if let Some(w64) = iri_to_u64_immediate(ctx, inst) {
                 // Get exactly the bit pattern in 'w64' into the dest.  No
                 // monkeying with sign extension etc.
-                let dstIs64 = w64 > 0xFFFF_FFFF;
-                let regD = output_to_reg(ctx, iri, 0);
-                ctx.emit(Inst::imm_r(dstIs64, w64, regD));
+                let dst_is_64 = w64 > 0xFFFF_FFFF;
+                let dst = output_to_reg(ctx, inst, 0);
+                ctx.emit(Inst::imm_r(dst_is_64, w64, dst));
             } else {
                 unimplemented!();
             }
         }
 
         Opcode::Iadd | Opcode::Isub => {
-            let regD = output_to_reg(ctx, iri, 0);
-            let regL = input_to_reg(ctx, iri, 0);
-            let regR = input_to_reg(ctx, iri, 1);
-            let is64 = int_ty_is_64(ty.unwrap());
-            let how = if op == Opcode::Iadd {
-                RMI_R_Op::Add
+            let dst = output_to_reg(ctx, inst, 0);
+            let lhs = input_to_reg(ctx, inst, 0);
+            let rhs = input_to_reg(ctx, inst, 1);
+            let is_64 = int_ty_is_64(ty.unwrap());
+            let alu_op = if op == Opcode::Iadd {
+                AluRmiROpcode::Add
             } else {
-                RMI_R_Op::Sub
+                AluRmiROpcode::Sub
             };
-            ctx.emit(Inst::mov_r_r(true, regL, regD));
-            ctx.emit(Inst::alu_rmi_r(is64, how, RMI::reg(regR), regD));
+            ctx.emit(Inst::mov_r_r(true, lhs, dst));
+            ctx.emit(Inst::alu_rmi_r(is_64, alu_op, RegMemImm::reg(rhs), dst));
         }
 
         Opcode::Ishl | Opcode::Ushr | Opcode::Sshr => {
             // TODO: implement imm shift value into insn
-            let tySL = ctx.input_ty(iri, 0);
-            let tyD = ctx.output_ty(iri, 0); // should be the same as tySL
-            let regSL = input_to_reg(ctx, iri, 0);
-            let regSR = input_to_reg(ctx, iri, 1);
-            let regD = output_to_reg(ctx, iri, 0);
-            if tyD == tySL && (tyD == types::I32 || tyD == types::I64) {
-                let how = match op {
-                    Opcode::Ishl => ShiftKind::Left,
-                    Opcode::Ushr => ShiftKind::RightZ,
-                    Opcode::Sshr => ShiftKind::RightS,
-                    _ => unreachable!(),
-                };
-                let is64 = tyD == types::I64;
-                let r_rcx = regs::rcx();
-                let w_rcx = Writable::<Reg>::from_reg(r_rcx);
-                ctx.emit(Inst::mov_r_r(true, regSL, regD));
-                ctx.emit(Inst::mov_r_r(true, regSR, w_rcx));
-                ctx.emit(Inst::shift_r(is64, how, None /*%cl*/, regD));
-            } else {
-                unimplemented!()
-            }
+            let dst_ty = ctx.output_ty(inst, 0);
+            assert_eq!(ctx.input_ty(inst, 0), dst_ty);
+            assert!(dst_ty == types::I32 || dst_ty == types::I64);
+
+            let lhs = input_to_reg(ctx, inst, 0);
+            let rhs = input_to_reg(ctx, inst, 1);
+            let dst = output_to_reg(ctx, inst, 0);
+
+            let shift_kind = match op {
+                Opcode::Ishl => ShiftKind::Left,
+                Opcode::Ushr => ShiftKind::RightZ,
+                Opcode::Sshr => ShiftKind::RightS,
+                _ => unreachable!(),
+            };
+
+            let is_64 = dst_ty == types::I64;
+            let w_rcx = Writable::from_reg(regs::rcx());
+            ctx.emit(Inst::mov_r_r(true, lhs, dst));
+            ctx.emit(Inst::mov_r_r(true, rhs, w_rcx));
+            ctx.emit(Inst::shift_r(is_64, shift_kind, None /*%cl*/, dst));
         }
 
         Opcode::Uextend | Opcode::Sextend => {
@@ -183,34 +165,53 @@ fn lower_insn_to_regs<'a>(ctx: Ctx<'a>, iri: IRInst) {
             // don't accept a register source operand.  They should be changed
             // so as to have _RM_R form.
             // TODO2: if the source operand is a load, incorporate that.
-            let isZX = op == Opcode::Uextend;
-            let tyS = ctx.input_ty(iri, 0);
-            let tyD = ctx.output_ty(iri, 0);
-            let regS = input_to_reg(ctx, iri, 0);
-            let regD = output_to_reg(ctx, iri, 0);
-            ctx.emit(Inst::mov_r_r(true, regS, regD));
-            match (tyS, tyD, isZX) {
+            let zero_extend = op == Opcode::Uextend;
+            let src_ty = ctx.input_ty(inst, 0);
+            let dst_ty = ctx.output_ty(inst, 0);
+            let src = input_to_reg(ctx, inst, 0);
+            let dst = output_to_reg(ctx, inst, 0);
+
+            ctx.emit(Inst::mov_r_r(true, src, dst));
+            match (src_ty, dst_ty, zero_extend) {
                 (types::I8, types::I64, false) => {
-                    ctx.emit(Inst::shift_r(true, ShiftKind::Left, Some(56), regD));
-                    ctx.emit(Inst::shift_r(true, ShiftKind::RightS, Some(56), regD));
+                    ctx.emit(Inst::shift_r(true, ShiftKind::Left, Some(56), dst));
+                    ctx.emit(Inst::shift_r(true, ShiftKind::RightS, Some(56), dst));
                 }
                 _ => unimplemented!(),
             }
         }
 
         Opcode::FallthroughReturn | Opcode::Return => {
-            for i in 0..ctx.num_inputs(iri) {
-                let src_reg = input_to_reg(ctx, iri, i);
+            for i in 0..ctx.num_inputs(inst) {
+                let src_reg = input_to_reg(ctx, inst, i);
                 let retval_reg = ctx.retval(i);
                 if src_reg.get_class() == RegClass::I64 {
                     ctx.emit(Inst::mov_r_r(true, src_reg, retval_reg));
                 } else if src_reg.get_class() == RegClass::V128 {
-                    ctx.emit(Inst::xmm_r_r(SSE_Op::SSE2_Movsd, src_reg, retval_reg));
+                    ctx.emit(Inst::xmm_r_r(SseOpcode::Movsd, src_reg, retval_reg));
                 }
             }
             // N.B.: the Ret itself is generated by the ABI.
         }
 
+        Opcode::Fadd | Opcode::Fsub => {
+            let dst = output_to_reg(ctx, inst, 0);
+            let lhs = input_to_reg(ctx, inst, 0);
+            let rhs = input_to_reg(ctx, inst, 1);
+            let is_64 = flt_ty_is_64(ty.unwrap());
+            if !is_64 {
+                let sse_op = if op == Opcode::Fadd {
+                    SseOpcode::Addss
+                } else {
+                    SseOpcode::Subss
+                };
+                ctx.emit(Inst::xmm_r_r(SseOpcode::Movss, lhs, dst));
+                ctx.emit(Inst::xmm_rm_r(sse_op, RegMem::reg(rhs), dst));
+            } else {
+                unimplemented!("unimplemented lowering for opcode {:?}", op);
+            }
+        }
+
         Opcode::IaddImm
         | Opcode::ImulImm
         | Opcode::UdivImm
@@ -240,23 +241,7 @@ fn lower_insn_to_regs<'a>(ctx: Ctx<'a>, iri: IRInst) {
         | Opcode::SshrImm => {
             panic!("ALU+imm and ALU+carry ops should not appear here!");
         }
-        Opcode::Fadd | Opcode::Fsub => {
-            let regD = output_to_reg(ctx, iri, 0);
-            let regL = input_to_reg(ctx, iri, 0);
-            let regR = input_to_reg(ctx, iri, 1);
-            let is64 = flt_ty_is_64(ty.unwrap());
-            if !is64 {
-                let inst = if op == Opcode::Fadd {
-                    SSE_Op::SSE_Addss
-                } else {
-                    SSE_Op::SSE_Subss
-                };
-                ctx.emit(Inst::xmm_r_r(SSE_Op::SSE_Movss, regL, regD));
-                ctx.emit(Inst::xmm_rm_r(inst, RM::reg(regR), regD));
-            } else {
-                unimplemented!("unimplemented lowering for opcode {:?}", op);
-            }
-        }
+
         _ => unimplemented!("unimplemented lowering for opcode {:?}", op),
     }
 }
@@ -287,60 +272,60 @@ impl LowerBackend for X64Backend {
         // verifier pass.
         assert!(branches.len() <= 2);
 
-        let mut unimplemented = false;
-
         if branches.len() == 2 {
             // Must be a conditional branch followed by an unconditional branch.
             let op0 = ctx.data(branches[0]).opcode();
             let op1 = ctx.data(branches[1]).opcode();
 
-            println!(
-                "QQQQ lowering two-branch group: opcodes are {:?} and {:?}",
-                op0, op1
+            trace!(
+                "lowering two-branch group: opcodes are {:?} and {:?}",
+                op0,
+                op1
             );
-
             assert!(op1 == Opcode::Jump || op1 == Opcode::Fallthrough);
+
             let taken = BranchTarget::Label(targets[0]);
             let not_taken = match op1 {
                 Opcode::Jump => BranchTarget::Label(targets[1]),
                 Opcode::Fallthrough => BranchTarget::Label(fallthrough.unwrap()),
                 _ => unreachable!(), // assert above.
             };
+
             match op0 {
                 Opcode::Brz | Opcode::Brnz => {
-                    let tyS = ctx.input_ty(branches[0], 0);
-                    if is_int_ty(tyS) {
-                        let rS = input_to_reg(ctx, branches[0], 0);
+                    let src_ty = ctx.input_ty(branches[0], 0);
+                    if is_int_ty(src_ty) {
+                        let src = input_to_reg(ctx, branches[0], 0);
                         let cc = match op0 {
                             Opcode::Brz => CC::Z,
                             Opcode::Brnz => CC::NZ,
                             _ => unreachable!(),
                         };
-                        let sizeB = int_ty_to_sizeB(tyS);
-                        ctx.emit(Inst::cmp_rmi_r(sizeB, RMI::imm(0), rS));
+                        let sizeB = int_ty_to_sizeB(src_ty);
+                        ctx.emit(Inst::cmp_rmi_r(sizeB, RegMemImm::imm(0), src));
                         ctx.emit(Inst::jmp_cond_symm(cc, taken, not_taken));
                     } else {
-                        unimplemented = true;
+                        unimplemented!("brz/brnz with non-int type");
                     }
                 }
+
                 Opcode::BrIcmp => {
-                    let tyS = ctx.input_ty(branches[0], 0);
-                    if is_int_ty(tyS) {
-                        let rSL = input_to_reg(ctx, branches[0], 0);
-                        let rSR = input_to_reg(ctx, branches[0], 1);
-                        let cc = intCC_to_x64_CC(inst_condcode(ctx.data(branches[0])));
-                        let sizeB = int_ty_to_sizeB(tyS);
+                    let src_ty = ctx.input_ty(branches[0], 0);
+                    if is_int_ty(src_ty) {
+                        let lhs = input_to_reg(ctx, branches[0], 0);
+                        let rhs = input_to_reg(ctx, branches[0], 1);
+                        let cc = CC::from_intcc(inst_condcode(ctx.data(branches[0])));
+                        let byte_size = int_ty_to_sizeB(src_ty);
                         // FIXME verify rSR vs rSL ordering
-                        ctx.emit(Inst::cmp_rmi_r(sizeB, RMI::reg(rSR), rSL));
+                        ctx.emit(Inst::cmp_rmi_r(byte_size, RegMemImm::reg(rhs), lhs));
                         ctx.emit(Inst::jmp_cond_symm(cc, taken, not_taken));
                     } else {
-                        unimplemented = true;
+                        unimplemented!("bricmp with non-int type");
                     }
                 }
+
                 // TODO: Brif/icmp, Brff/icmp, jump tables
-                _ => {
-                    unimplemented = true;
-                }
+                _ => unimplemented!("branch opcode"),
             }
         } else {
             assert!(branches.len() == 1);
@@ -355,16 +340,12 @@ impl LowerBackend for X64Backend {
                     ctx.emit(Inst::jmp_known(BranchTarget::Label(targets[0])));
                 }
                 Opcode::Trap => {
-                    unimplemented = true;
+                    unimplemented!("trap");
                 }
                 _ => panic!("Unknown branch type!"),
             }
         }
 
-        if unimplemented {
-            unimplemented!("lower_branch_group(x64): can't handle: {:?}", branches);
-        }
-
         Ok(())
     }
 }
diff --git a/cranelift/codegen/src/machinst/vcode.rs b/cranelift/codegen/src/machinst/vcode.rs
index 81c59f5f2..74c99b3af 100644
--- a/cranelift/codegen/src/machinst/vcode.rs
+++ b/cranelift/codegen/src/machinst/vcode.rs
@@ -137,13 +137,10 @@ impl<I: VCodeInst> VCodeBuilder<I> {
     /// Set the type of a VReg.
     pub fn set_vreg_type(&mut self, vreg: VirtualReg, ty: Type) {
         if self.vcode.vreg_types.len() <= vreg.get_index() {
-            self.vcode.vreg_types.resize(
-                self.vcode.vreg_types.len()
-                    + ((vreg.get_index() + 1) - self.vcode.vreg_types.len()),
-                ir::types::I8,
-            )
+            self.vcode
+                .vreg_types
+                .resize(vreg.get_index() + 1, ir::types::I8);
         }
-
         self.vcode.vreg_types[vreg.get_index()] = ty;
     }
 
diff --git a/crates/environ/src/cache.rs b/crates/environ/src/cache.rs
index 290a54033..5b1788216 100644
--- a/crates/environ/src/cache.rs
+++ b/crates/environ/src/cache.rs
@@ -1,5 +1,5 @@
 use crate::address_map::{ModuleAddressMap, ValueLabelsRanges};
-use crate::compilation::{Compilation, Relocations, Traps};
+use crate::compilation::{Compilation, Relocations, StackMaps, Traps};
 use cranelift_codegen::ir;
 use cranelift_entity::PrimaryMap;
 use cranelift_wasm::DefinedFuncIndex;
@@ -35,6 +35,7 @@ pub struct ModuleCacheData {
     value_ranges: ValueLabelsRanges,
     stack_slots: PrimaryMap<DefinedFuncIndex, ir::StackSlots>,
     traps: Traps,
+    stack_maps: StackMaps,
 }
 
 /// A type alias over the module cache data as a tuple.
@@ -45,6 +46,7 @@ pub type ModuleCacheDataTupleType = (
     ValueLabelsRanges,
     PrimaryMap<DefinedFuncIndex, ir::StackSlots>,
     Traps,
+    StackMaps,
 );
 
 struct Sha256Hasher(Sha256);
@@ -204,6 +206,7 @@ impl ModuleCacheData {
             value_ranges: data.3,
             stack_slots: data.4,
             traps: data.5,
+            stack_maps: data.6,
         }
     }
 
@@ -215,6 +218,7 @@ impl ModuleCacheData {
             self.value_ranges,
             self.stack_slots,
             self.traps,
+            self.stack_maps,
         )
     }
 }
diff --git a/crates/environ/src/compilation.rs b/crates/environ/src/compilation.rs
index 3382d89ae..b08e82fd4 100644
--- a/crates/environ/src/compilation.rs
+++ b/crates/environ/src/compilation.rs
@@ -144,6 +144,22 @@ pub struct TrapInformation {
 /// Information about traps associated with the functions where the traps are placed.
 pub type Traps = PrimaryMap<DefinedFuncIndex, Vec<TrapInformation>>;
 
+/// The offset within a function of a GC safepoint, and its associated stack
+/// map.
+#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
+pub struct StackMapInformation {
+    /// The offset of the GC safepoint within the function's native code. It is
+    /// relative to the beginning of the function.
+    pub code_offset: binemit::CodeOffset,
+
+    /// The stack map for identifying live GC refs at the GC safepoint.
+    pub stack_map: binemit::Stackmap,
+}
+
+/// Information about GC safepoints and their associated stack maps within each
+/// function.
+pub type StackMaps = PrimaryMap<DefinedFuncIndex, Vec<StackMapInformation>>;
+
 /// An error while compiling WebAssembly to machine code.
 #[derive(Error, Debug)]
 pub enum CompileError {
diff --git a/crates/environ/src/cranelift.rs b/crates/environ/src/cranelift.rs
index d7d0146a6..89a7dfd6f 100644
--- a/crates/environ/src/cranelift.rs
+++ b/crates/environ/src/cranelift.rs
@@ -88,7 +88,8 @@
 use crate::address_map::{FunctionAddressMap, InstructionAddressMap};
 use crate::cache::{ModuleCacheDataTupleType, ModuleCacheEntry};
 use crate::compilation::{
-    Compilation, CompileError, CompiledFunction, Relocation, RelocationTarget, TrapInformation,
+    Compilation, CompileError, CompiledFunction, Relocation, RelocationTarget, StackMapInformation,
+    TrapInformation,
 };
 use crate::func_environ::{get_func_name, FuncEnvironment};
 use crate::{CacheConfig, FunctionBodyData, ModuleLocal, ModuleTranslation, Tunables};
@@ -204,6 +205,27 @@ impl binemit::TrapSink for TrapSink {
     }
 }
 
+#[derive(Default)]
+struct StackMapSink {
+    infos: Vec<StackMapInformation>,
+}
+
+impl binemit::StackmapSink for StackMapSink {
+    fn add_stackmap(&mut self, code_offset: binemit::CodeOffset, stack_map: binemit::Stackmap) {
+        self.infos.push(StackMapInformation {
+            code_offset,
+            stack_map,
+        });
+    }
+}
+
+impl StackMapSink {
+    fn finish(mut self) -> Vec<StackMapInformation> {
+        self.infos.sort_unstable_by_key(|info| info.code_offset);
+        self.infos
+    }
+}
+
 fn get_function_address_map<'data>(
     context: &Context,
     data: &FunctionBodyData<'data>,
@@ -294,6 +316,7 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
     let mut value_ranges = PrimaryMap::with_capacity(env.function_body_inputs.len());
     let mut stack_slots = PrimaryMap::with_capacity(env.function_body_inputs.len());
     let mut traps = PrimaryMap::with_capacity(env.function_body_inputs.len());
+    let mut stack_maps = PrimaryMap::with_capacity(env.function_body_inputs.len());
 
     env.function_body_inputs
         .into_iter()
@@ -354,14 +377,14 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
             let mut code_buf: Vec<u8> = Vec::new();
             let mut reloc_sink = RelocSink::new(func_index);
             let mut trap_sink = TrapSink::new();
-            let mut stackmap_sink = binemit::NullStackmapSink {};
+            let mut stack_map_sink = StackMapSink::default();
             context
                 .compile_and_emit(
                     isa,
                     &mut code_buf,
                     &mut reloc_sink,
                     &mut trap_sink,
-                    &mut stackmap_sink,
+                    &mut stack_map_sink,
                 )
                 .map_err(|error| {
                     CompileError::Codegen(pretty_error(&context.func, Some(isa), error))
@@ -391,6 +414,7 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
                 context.func.stack_slots,
                 trap_sink.traps,
                 unwind_info,
+                stack_map_sink.finish(),
             ))
         })
         .collect::<Result<Vec<_>, CompileError>>()?
@@ -405,6 +429,7 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
                 sss,
                 function_traps,
                 unwind_info,
+                stack_map,
             )| {
                 functions.push(CompiledFunction {
                     body: function,
@@ -416,6 +441,7 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
                 value_ranges.push(ranges.unwrap_or_default());
                 stack_slots.push(sss);
                 traps.push(function_traps);
+                stack_maps.push(stack_map);
             },
         );
 
@@ -428,6 +454,7 @@ fn compile(env: CompileEnv<'_>) -> Result<ModuleCacheDataTupleType, CompileError
         value_ranges,
         stack_slots,
         traps,
+        stack_maps,
     ))
 }
 
diff --git a/crates/environ/src/data_structures.rs b/crates/environ/src/data_structures.rs
index 30d00d1d0..c9aaa5c92 100644
--- a/crates/environ/src/data_structures.rs
+++ b/crates/environ/src/data_structures.rs
@@ -1,6 +1,7 @@
 #![doc(hidden)]
 
 pub mod ir {
+    pub use cranelift_codegen::binemit::Stackmap;
     pub use cranelift_codegen::ir::{
         types, AbiParam, ArgumentPurpose, Signature, SourceLoc, StackSlots, TrapCode, Type,
         ValueLabel, ValueLoc,
diff --git a/crates/environ/src/func_environ.rs b/crates/environ/src/func_environ.rs
index 52e4fbb64..0f9b8f755 100644
--- a/crates/environ/src/func_environ.rs
+++ b/crates/environ/src/func_environ.rs
@@ -658,13 +658,6 @@ impl<'module_environment> TargetEnvironment for FuncEnvironment<'module_environm
     fn target_config(&self) -> TargetFrontendConfig {
         self.target_config
     }
-
-    fn reference_type(&self) -> ir::Type {
-        // For now, the only reference types we support are `externref`, which
-        // don't require tracing GC and stack maps. So we just use the target's
-        // pointer type. This will have to change once we move to tracing GC.
-        self.pointer_type()
-    }
 }
 
 impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'module_environment> {
@@ -1192,7 +1185,7 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         _table: ir::Table,
     ) -> WasmResult<ir::Value> {
         Err(WasmError::Unsupported(
-            "bulk memory: `table.size`".to_string(),
+            "reference types: `table.size`".to_string(),
         ))
     }
 
diff --git a/crates/environ/src/lib.rs b/crates/environ/src/lib.rs
index f059795f9..fa32e116e 100644
--- a/crates/environ/src/lib.rs
+++ b/crates/environ/src/lib.rs
@@ -47,7 +47,7 @@ pub use crate::cache::create_new_config as cache_create_new_config;
 pub use crate::cache::CacheConfig;
 pub use crate::compilation::{
     Compilation, CompileError, CompiledFunction, Compiler, Relocation, RelocationTarget,
-    Relocations, TrapInformation, Traps,
+    Relocations, StackMapInformation, StackMaps, TrapInformation, Traps,
 };
 pub use crate::cranelift::Cranelift;
 pub use crate::data_structures::*;
diff --git a/crates/environ/src/lightbeam.rs b/crates/environ/src/lightbeam.rs
index f4a32ec5d..49fda2f8a 100644
--- a/crates/environ/src/lightbeam.rs
+++ b/crates/environ/src/lightbeam.rs
@@ -34,6 +34,7 @@ impl crate::compilation::Compiler for Lightbeam {
         );
         let mut relocations = PrimaryMap::with_capacity(translation.function_body_inputs.len());
         let mut traps = PrimaryMap::with_capacity(translation.function_body_inputs.len());
+        let stack_maps = PrimaryMap::with_capacity(translation.function_body_inputs.len());
 
         let mut codegen_session: CodeGenSession<_> = CodeGenSession::new(
             translation.function_body_inputs.len() as u32,
@@ -81,6 +82,7 @@ impl crate::compilation::Compiler for Lightbeam {
             ValueLabelsRanges::new(),
             PrimaryMap::new(),
             traps,
+            stack_maps,
         ))
     }
 }
diff --git a/crates/environ/src/module_environ.rs b/crates/environ/src/module_environ.rs
index 755321511..4876c3c2e 100644
--- a/crates/environ/src/module_environ.rs
+++ b/crates/environ/src/module_environ.rs
@@ -92,13 +92,6 @@ impl<'data> TargetEnvironment for ModuleEnvironment<'data> {
     fn target_config(&self) -> TargetFrontendConfig {
         self.result.target_config
     }
-
-    fn reference_type(&self) -> ir::Type {
-        // For now, the only reference types we support are `externref`, which
-        // don't require tracing GC and stack maps. So we just use the target's
-        // pointer type. This will have to change once we move to tracing GC.
-        self.pointer_type()
-    }
 }
 
 /// This trait is useful for `translate_module` because it tells how to translate
diff --git a/crates/environ/src/vmoffsets.rs b/crates/environ/src/vmoffsets.rs
index 940792557..0d7f08073 100644
--- a/crates/environ/src/vmoffsets.rs
+++ b/crates/environ/src/vmoffsets.rs
@@ -5,6 +5,8 @@
 //
 // struct VMContext {
 //      interrupts: *const VMInterrupts,
+//      externref_activations_table: *mut VMExternRefActivationsTable,
+//      stack_map_registry: *mut StackMapRegistry,
 //      signature_ids: [VMSharedSignatureIndex; module.num_signature_ids],
 //      imported_functions: [VMFunctionImport; module.num_imported_functions],
 //      imported_tables: [VMTableImport; module.num_imported_tables],
@@ -286,9 +288,23 @@ impl VMOffsets {
         0
     }
 
+    /// The offset of the `VMExternRefActivationsTable` member.
+    pub fn vmctx_externref_activations_table(&self) -> u32 {
+        self.vmctx_interrupts()
+            .checked_add(u32::from(self.pointer_size))
+            .unwrap()
+    }
+
+    /// The offset of the `*mut StackMapRegistry` member.
+    pub fn vmctx_stack_map_registry(&self) -> u32 {
+        self.vmctx_externref_activations_table()
+            .checked_add(u32::from(self.pointer_size))
+            .unwrap()
+    }
+
     /// The offset of the `signature_ids` array.
     pub fn vmctx_signature_ids_begin(&self) -> u32 {
-        self.vmctx_interrupts()
+        self.vmctx_stack_map_registry()
             .checked_add(u32::from(self.pointer_size))
             .unwrap()
     }
@@ -591,6 +607,19 @@ impl VMOffsets {
     }
 }
 
+/// Offsets for `VMExternRefActivationsTable`.
+impl VMOffsets {
+    /// Return the offset for `VMExternRefActivationsTable::next`.
+    pub fn vm_extern_ref_activation_table_next(&self) -> u32 {
+        0
+    }
+
+    /// Return the offset for `VMExternRefActivationsTable::end`.
+    pub fn vm_extern_ref_activation_table_end(&self) -> u32 {
+        self.pointer_size.into()
+    }
+}
+
 /// Target specific type for shared signature index.
 #[derive(Debug, Copy, Clone)]
 pub struct TargetSharedSignatureIndex(u32);
diff --git a/crates/jit/src/compiler.rs b/crates/jit/src/compiler.rs
index a53656e99..04af38ed7 100644
--- a/crates/jit/src/compiler.rs
+++ b/crates/jit/src/compiler.rs
@@ -15,7 +15,7 @@ use wasmtime_environ::wasm::{DefinedFuncIndex, DefinedMemoryIndex, MemoryIndex,
 use wasmtime_environ::{
     CacheConfig, CompileError, CompiledFunction, Compiler as _C, Module, ModuleAddressMap,
     ModuleMemoryOffset, ModuleTranslation, ModuleVmctxInfo, Relocation, RelocationTarget,
-    Relocations, Traps, Tunables, VMOffsets, ValueLabelsRanges,
+    Relocations, StackMaps, Traps, Tunables, VMOffsets, ValueLabelsRanges,
 };
 use wasmtime_runtime::{InstantiationError, VMFunctionBody, VMTrampoline};
 
@@ -138,6 +138,7 @@ pub struct Compilation {
     pub jt_offsets: PrimaryMap<DefinedFuncIndex, ir::JumpTableOffsets>,
     pub dwarf_sections: Vec<DwarfSection>,
     pub traps: Traps,
+    pub stack_maps: StackMaps,
     pub address_transform: ModuleAddressMap,
 }
 
@@ -165,27 +166,34 @@ impl Compiler {
     ) -> Result<Compilation, SetupError> {
         let mut code_memory = CodeMemory::new();
 
-        let (compilation, relocations, address_transform, value_ranges, stack_slots, traps) =
-            match self.strategy {
-                // For now, interpret `Auto` as `Cranelift` since that's the most stable
-                // implementation.
-                CompilationStrategy::Auto | CompilationStrategy::Cranelift => {
-                    wasmtime_environ::cranelift::Cranelift::compile_module(
-                        translation,
-                        &*self.isa,
-                        &self.cache_config,
-                    )
-                }
-                #[cfg(feature = "lightbeam")]
-                CompilationStrategy::Lightbeam => {
-                    wasmtime_environ::lightbeam::Lightbeam::compile_module(
-                        translation,
-                        &*self.isa,
-                        &self.cache_config,
-                    )
-                }
+        let (
+            compilation,
+            relocations,
+            address_transform,
+            value_ranges,
+            stack_slots,
+            traps,
+            stack_maps,
+        ) = match self.strategy {
+            // For now, interpret `Auto` as `Cranelift` since that's the most stable
+            // implementation.
+            CompilationStrategy::Auto | CompilationStrategy::Cranelift => {
+                wasmtime_environ::cranelift::Cranelift::compile_module(
+                    translation,
+                    &*self.isa,
+                    &self.cache_config,
+                )
+            }
+            #[cfg(feature = "lightbeam")]
+            CompilationStrategy::Lightbeam => {
+                wasmtime_environ::lightbeam::Lightbeam::compile_module(
+                    translation,
+                    &*self.isa,
+                    &self.cache_config,
+                )
             }
-            .map_err(SetupError::Compile)?;
+        }
+        .map_err(SetupError::Compile)?;
 
         let dwarf_sections = if debug_data.is_some() && !compilation.is_empty() {
             transform_dwarf_data(
@@ -239,6 +247,7 @@ impl Compiler {
             jt_offsets,
             dwarf_sections,
             traps,
+            stack_maps,
             address_transform,
         })
     }
diff --git a/crates/jit/src/instantiate.rs b/crates/jit/src/instantiate.rs
index 12152c708..97b0ef05e 100644
--- a/crates/jit/src/instantiate.rs
+++ b/crates/jit/src/instantiate.rs
@@ -18,13 +18,13 @@ use wasmtime_environ::isa::TargetIsa;
 use wasmtime_environ::wasm::{DefinedFuncIndex, SignatureIndex};
 use wasmtime_environ::{
     CompileError, DataInitializer, DataInitializerLocation, Module, ModuleAddressMap,
-    ModuleEnvironment, ModuleTranslation, Traps,
+    ModuleEnvironment, ModuleTranslation, StackMaps, Traps,
 };
 use wasmtime_profiling::ProfilingAgent;
 use wasmtime_runtime::VMInterrupts;
 use wasmtime_runtime::{
     GdbJitImageRegistration, InstanceHandle, InstantiationError, RuntimeMemoryCreator,
-    SignatureRegistry, VMFunctionBody, VMTrampoline,
+    SignatureRegistry, StackMapRegistry, VMExternRefActivationsTable, VMFunctionBody, VMTrampoline,
 };
 
 /// An error condition while setting up a wasm instance, be it validation,
@@ -69,6 +69,7 @@ pub struct CompiledModule {
     trampolines: PrimaryMap<SignatureIndex, VMTrampoline>,
     data_initializers: Box<[OwnedDataInitializer]>,
     traps: Traps,
+    stack_maps: StackMaps,
     address_transform: ModuleAddressMap,
 }
 
@@ -99,6 +100,7 @@ impl CompiledModule {
             jt_offsets,
             dwarf_sections,
             traps,
+            stack_maps,
             address_transform,
         } = compiler.compile(&translation, debug_data)?;
 
@@ -149,6 +151,7 @@ impl CompiledModule {
             trampolines,
             data_initializers,
             traps,
+            stack_maps,
             address_transform,
         })
     }
@@ -169,6 +172,8 @@ impl CompiledModule {
         mem_creator: Option<&dyn RuntimeMemoryCreator>,
         interrupts: Arc<VMInterrupts>,
         host_state: Box<dyn Any>,
+        externref_activations_table: *mut VMExternRefActivationsTable,
+        stack_map_registry: *mut StackMapRegistry,
     ) -> Result<InstanceHandle, InstantiationError> {
         // Compute indices into the shared signature table.
         let signatures = {
@@ -200,6 +205,8 @@ impl CompiledModule {
             signatures.into_boxed_slice(),
             host_state,
             interrupts,
+            externref_activations_table,
+            stack_map_registry,
         )
     }
 
@@ -229,11 +236,16 @@ impl CompiledModule {
         &self.finished_functions.0
     }
 
-    /// Returns the a map for all traps in this module.
+    /// Returns the map for all traps in this module.
     pub fn traps(&self) -> &Traps {
         &self.traps
     }
 
+    /// Returns the map for each of this module's stack maps.
+    pub fn stack_maps(&self) -> &StackMaps {
+        &self.stack_maps
+    }
+
     /// Returns a map of compiled addresses back to original bytecode offsets.
     pub fn address_transform(&self) -> &ModuleAddressMap {
         &self.address_transform
diff --git a/crates/runtime/Cargo.toml b/crates/runtime/Cargo.toml
index b862d2589..9ed855d2f 100644
--- a/crates/runtime/Cargo.toml
+++ b/crates/runtime/Cargo.toml
@@ -15,12 +15,13 @@ edition = "2018"
 wasmtime-environ = { path = "../environ", version = "0.18.0" }
 region = "2.0.0"
 libc = { version = "0.2.70", default-features = false }
+log = "0.4.8"
 memoffset = "0.5.3"
 indexmap = "1.0.2"
 thiserror = "1.0.4"
 more-asserts = "0.2.1"
 cfg-if = "0.1.9"
-backtrace = "0.3.42"
+backtrace = "0.3.49"
 lazy_static = "1.3.0"
 
 [target.'cfg(target_os = "windows")'.dependencies]
diff --git a/crates/runtime/src/externref.rs b/crates/runtime/src/externref.rs
index 8e8aeecfe..04c2bddbe 100644
--- a/crates/runtime/src/externref.rs
+++ b/crates/runtime/src/externref.rs
@@ -58,29 +58,59 @@
 //! need a ton of excess padding between the `VMExternData` and the value for
 //! values with large alignment.
 //!
-//! ## Reference Counting Protocol and Wasm Functions
+//! ## Reference Counting, Wasm Functions, and Garbage Collection
 //!
-//! Currently, `VMExternRef`s passed into compiled Wasm functions have move
-//! semantics: the host code gives up ownership and does not decrement the
-//! reference count. Similarly, `VMExternRef`s returned from compiled Wasm
-//! functions also have move semantics: host code takes ownership and the
-//! reference count is not incremented.
+//! For host VM code, we use plain reference counting, where cloning increments
+//! the reference count, and dropping decrements it. We can avoid many of the
+//! on-stack increment/decrement operations that typically plague the
+//! performance of reference counting via Rust's ownership and borrowing system.
+//! Moving a `VMExternRef` avoids mutating its reference count, and borrowing it
+//! either avoids the reference count increment or delays it until if/when the
+//! `VMExternRef` is cloned.
 //!
-//! This works well when a reference is passed into Wasm and then passed back
-//! out again. However, if a reference is passed into Wasm, but not passed back
-//! out, then the reference is leaked. This is only a temporary state, and
-//! follow up work will leverage stack maps to fix this issue. Follow
-//! https://github.com/bytecodealliance/wasmtime/issues/929 to keep an eye on
-//! this.
+//! When passing a `VMExternRef` into compiled Wasm code, we don't want to do
+//! reference count mutations for every compiled `local.{get,set}`, nor for
+//! every function call. Therefore, we use a variation of **deferred reference
+//! counting**, where we only mutate reference counts when storing
+//! `VMExternRef`s somewhere that outlives the activation: into a global or
+//! table. Simultaneously, we over-approximate the set of `VMExternRef`s that
+//! are inside Wasm function activations. Periodically, we walk the stack at GC
+//! safe points, and use stack map information to precisely identify the set of
+//! `VMExternRef`s inside Wasm activations. Then we take the difference between
+//! this precise set and our over-approximation, and decrement the reference
+//! count for each of the `VMExternRef`s that are in our over-approximation but
+//! not in the precise set. Finally, the over-approximation is replaced with the
+//! precise set.
+//!
+//! The `VMExternRefActivationsTable` implements the over-approximized set of
+//! `VMExternRef`s referenced by Wasm activations. Calling a Wasm function and
+//! passing it a `VMExternRef` moves the `VMExternRef` into the table, and the
+//! compiled Wasm function logically "borrows" the `VMExternRef` from the
+//! table. Similarly, `global.get` and `table.get` operations clone the gotten
+//! `VMExternRef` into the `VMExternRefActivationsTable` and then "borrow" the
+//! reference out of the table.
+//!
+//! When a `VMExternRef` is returned to host code from a Wasm function, the host
+//! increments the reference count (because the reference is logically
+//! "borrowed" from the `VMExternRefActivationsTable` and the reference count
+//! from the table will be dropped at the next GC).
+//!
+//! For more general information on deferred reference counting, see *An
+//! Examination of Deferred Reference Counting and Cycle Detection* by Quinane:
+//! https://openresearch-repository.anu.edu.au/bitstream/1885/42030/2/hon-thesis.pdf
 
 use std::alloc::Layout;
 use std::any::Any;
-use std::cell::UnsafeCell;
+use std::cell::{Cell, RefCell, UnsafeCell};
 use std::cmp::Ordering;
-use std::hash::Hasher;
+use std::collections::BTreeMap;
+use std::collections::HashSet;
+use std::hash::{Hash, Hasher};
 use std::mem;
 use std::ops::Deref;
 use std::ptr::{self, NonNull};
+use std::rc::Rc;
+use wasmtime_environ::{ir::Stackmap, StackMapInformation};
 
 /// An external reference to some opaque data.
 ///
@@ -309,33 +339,39 @@ impl VMExternRef {
 
     /// Turn this `VMExternRef` into a raw, untyped pointer.
     ///
-    /// This forgets `self` and does *not* decrement the reference count on the
-    /// pointed-to data.
+    /// Unlike `into_raw`, this does not consume and forget `self`. It is *not*
+    /// safe to use `from_raw` on pointers returned from this method; only use
+    /// `clone_from_raw`!
     ///
-    /// This `VMExternRef` may be recovered with `VMExternRef::from_raw`.
-    pub fn into_raw(self) -> *mut u8 {
+    ///  Nor does this method increment the reference count. You must ensure
+    ///  that `self` (or some other clone of `self`) stays alive until
+    ///  `clone_from_raw` is called.
+    pub fn as_raw(&self) -> *mut u8 {
         let ptr = self.0.cast::<u8>().as_ptr();
-        mem::forget(self);
         ptr
     }
 
-    /// Create a `VMExternRef` from a pointer returned from a previous call to
-    /// `VMExternRef::into_raw`.
+    /// Recreate a `VMExternRef` from a pointer returned from a previous call to
+    /// `VMExternRef::as_raw`.
     ///
     /// # Safety
     ///
     /// Wildly unsafe to use with anything other than the result of a previous
-    /// `into_raw` call!
+    /// `as_raw` call!
     ///
-    /// This method does *not* increment the reference count on the pointed-to
-    /// data, so `from_raw` must be called at most *once* on the result of a
-    /// previous `into_raw` call. (Ideally, every `into_raw` is later followed
-    /// by a `from_raw`, but it is technically memory safe to never call
-    /// `from_raw` after `into_raw`: it will leak the pointed-to value, which is
-    /// memory safe).
-    pub unsafe fn from_raw(ptr: *mut u8) -> Self {
+    /// Additionally, it is your responsibility to ensure that this raw
+    /// `VMExternRef`'s reference count has not dropped to zero. Failure to do
+    /// so will result in use after free!
+    pub unsafe fn clone_from_raw(ptr: *mut u8) -> Self {
         debug_assert!(!ptr.is_null());
-        VMExternRef(NonNull::new_unchecked(ptr).cast())
+        let x = VMExternRef(NonNull::new_unchecked(ptr).cast());
+        x.extern_data().increment_ref_count();
+        x
+    }
+
+    /// Get the strong reference count for this `VMExternRef`.
+    pub fn strong_count(&self) -> usize {
+        self.extern_data().get_ref_count()
     }
 
     #[inline]
@@ -393,6 +429,640 @@ impl Deref for VMExternRef {
     }
 }
 
+/// A wrapper around a `VMExternRef` that implements `Eq` and `Hash` with
+/// pointer semantics.
+///
+/// We use this so that we can morally put `VMExternRef`s inside of `HashSet`s
+/// even though they don't implement `Eq` and `Hash` to avoid foot guns.
+#[derive(Clone)]
+struct VMExternRefWithTraits(VMExternRef);
+
+impl Hash for VMExternRefWithTraits {
+    fn hash<H>(&self, hasher: &mut H)
+    where
+        H: Hasher,
+    {
+        VMExternRef::hash(&self.0, hasher)
+    }
+}
+
+impl PartialEq for VMExternRefWithTraits {
+    fn eq(&self, other: &Self) -> bool {
+        VMExternRef::eq(&self.0, &other.0)
+    }
+}
+
+impl Eq for VMExternRefWithTraits {}
+
+type TableElem = UnsafeCell<Option<VMExternRef>>;
+
+/// A table that over-approximizes the set of `VMExternRef`s that any Wasm
+/// activation on this thread is currently using.
+///
+/// Under the covers, this is a simple bump allocator that allows duplicate
+/// entries. Deduplication happens at GC time.
+#[repr(C)]
+pub struct VMExternRefActivationsTable {
+    /// Bump-allocation finger within the `chunk`.
+    ///
+    /// NB: this is an `UnsafeCell` because it is written to by compiled Wasm
+    /// code.
+    next: UnsafeCell<NonNull<TableElem>>,
+
+    /// Pointer to just after the `chunk`.
+    ///
+    /// This is *not* within the current chunk and therefore is not a valid
+    /// place to insert a reference!
+    end: NonNull<TableElem>,
+
+    /// Bump allocation chunk that stores fast-path insertions.
+    chunk: Box<[TableElem]>,
+
+    /// When unioned with `chunk`, this is an over-approximation of the GC roots
+    /// on the stack, inside Wasm frames.
+    ///
+    /// This is used by slow-path insertion, and when a GC cycle finishes, is
+    /// re-initialized to the just-discovered precise set of stack roots (which
+    /// immediately becomes an over-approximation again as soon as Wasm runs and
+    /// potentially drops references).
+    over_approximated_stack_roots: RefCell<HashSet<VMExternRefWithTraits>>,
+
+    /// The precise set of on-stack, inside-Wasm GC roots that we discover via
+    /// walking the stack and interpreting stack maps.
+    ///
+    /// This is *only* used inside the `gc` function, and is empty otherwise. It
+    /// is just part of this struct so that we can reuse the allocation, rather
+    /// than create a new hash set every GC.
+    precise_stack_roots: RefCell<HashSet<VMExternRefWithTraits>>,
+
+    /// A pointer to a `u8` on the youngest host stack frame before we called
+    /// into Wasm for the first time. When walking the stack in garbage
+    /// collection, if we don't find this frame, then we failed to walk every
+    /// Wasm stack frame, which means we failed to find all on-stack,
+    /// inside-a-Wasm-frame roots, and doing a GC could lead to freeing one of
+    /// those missed roots, and use after free.
+    stack_canary: Cell<Option<NonNull<u8>>>,
+}
+
+impl VMExternRefActivationsTable {
+    const CHUNK_SIZE: usize = 4096 / mem::size_of::<usize>();
+
+    /// Create a new `VMExternRefActivationsTable`.
+    pub fn new() -> Self {
+        let chunk = Self::new_chunk(Self::CHUNK_SIZE);
+        let next = chunk.as_ptr() as *mut TableElem;
+        let end = unsafe { next.add(chunk.len()) };
+
+        VMExternRefActivationsTable {
+            next: UnsafeCell::new(NonNull::new(next).unwrap()),
+            end: NonNull::new(end).unwrap(),
+            chunk,
+            over_approximated_stack_roots: RefCell::new(HashSet::with_capacity(Self::CHUNK_SIZE)),
+            precise_stack_roots: RefCell::new(HashSet::with_capacity(Self::CHUNK_SIZE)),
+            stack_canary: Cell::new(None),
+        }
+    }
+
+    fn new_chunk(size: usize) -> Box<[UnsafeCell<Option<VMExternRef>>]> {
+        assert!(size >= Self::CHUNK_SIZE);
+        (0..size).map(|_| UnsafeCell::new(None)).collect()
+    }
+
+    /// Try and insert a `VMExternRef` into this table.
+    ///
+    /// This is a fast path that only succeeds when the bump chunk has the
+    /// capacity for the requested insertion.
+    ///
+    /// If the insertion fails, then the `VMExternRef` is given back. Callers
+    /// may attempt a GC to free up space and try again, or may call
+    /// `insert_slow_path` to infallibly insert the reference (potentially
+    /// allocating additional space in the table to hold it).
+    #[inline]
+    pub fn try_insert(&self, externref: VMExternRef) -> Result<(), VMExternRef> {
+        unsafe {
+            let next = *self.next.get();
+            if next == self.end {
+                return Err(externref);
+            }
+
+            debug_assert!((*next.as_ref().get()).is_none());
+            ptr::write(next.as_ptr(), UnsafeCell::new(Some(externref)));
+
+            let next = NonNull::new_unchecked(next.as_ptr().add(1));
+            debug_assert!(next <= self.end);
+            *self.next.get() = next;
+
+            Ok(())
+        }
+    }
+
+    /// Insert a reference into the table, falling back on a GC to clear up
+    /// space if the table is already full.
+    ///
+    /// # Unsafety
+    ///
+    /// The same as `gc`.
+    #[inline]
+    pub unsafe fn insert_with_gc(
+        &self,
+        externref: VMExternRef,
+        stack_maps_registry: &StackMapRegistry,
+    ) {
+        if let Err(externref) = self.try_insert(externref) {
+            self.gc_and_insert_slow(externref, stack_maps_registry);
+        }
+    }
+
+    #[inline(never)]
+    unsafe fn gc_and_insert_slow(
+        &self,
+        externref: VMExternRef,
+        stack_maps_registry: &StackMapRegistry,
+    ) {
+        gc(stack_maps_registry, self);
+
+        // Might as well insert right into the hash set, rather than the bump
+        // chunk, since we are already on a slow path and we get de-duplication
+        // this way.
+        let mut roots = self.over_approximated_stack_roots.borrow_mut();
+        roots.insert(VMExternRefWithTraits(externref));
+    }
+
+    fn num_filled_in_bump_chunk(&self) -> usize {
+        let next = unsafe { *self.next.get() };
+        let bytes_unused = (self.end.as_ptr() as usize) - (next.as_ptr() as usize);
+        let slots_unused = bytes_unused / mem::size_of::<TableElem>();
+        self.chunk.len().saturating_sub(slots_unused)
+    }
+
+    fn elements(&self, mut f: impl FnMut(&VMExternRef)) {
+        let roots = self.over_approximated_stack_roots.borrow();
+        for elem in roots.iter() {
+            f(&elem.0);
+        }
+
+        // The bump chunk is not all the way full, so we only iterate over its
+        // filled-in slots.
+        let num_filled = self.num_filled_in_bump_chunk();
+        for slot in self.chunk.iter().take(num_filled) {
+            if let Some(elem) = unsafe { &*slot.get() } {
+                f(elem);
+            }
+        }
+    }
+
+    fn insert_precise_stack_root(&self, root: NonNull<VMExternData>) {
+        let mut precise_stack_roots = self.precise_stack_roots.borrow_mut();
+        let root = unsafe { VMExternRef::clone_from_raw(root.as_ptr() as *mut _) };
+        precise_stack_roots.insert(VMExternRefWithTraits(root));
+    }
+
+    /// Sweep the bump allocation table after we've discovered our precise stack
+    /// roots.
+    fn sweep(&self) {
+        // Sweep our bump chunk.
+        let num_filled = self.num_filled_in_bump_chunk();
+        for slot in self.chunk.iter().take(num_filled) {
+            unsafe {
+                *slot.get() = None;
+            }
+        }
+        debug_assert!(
+            self.chunk
+                .iter()
+                .all(|slot| unsafe { (*slot.get()).as_ref().is_none() }),
+            "after sweeping the bump chunk, all slots should be `None`"
+        );
+
+        // Reset our `next` bump allocation finger.
+        unsafe {
+            let next = self.chunk.as_ptr() as *mut TableElem;
+            debug_assert!(!next.is_null());
+            *self.next.get() = NonNull::new_unchecked(next);
+        }
+
+        // The current `precise_roots` becomes our new over-appoximated set for
+        // the next GC cycle.
+        let mut precise_roots = self.precise_stack_roots.borrow_mut();
+        let mut over_approximated = self.over_approximated_stack_roots.borrow_mut();
+        mem::swap(&mut *precise_roots, &mut *over_approximated);
+
+        // And finally, the new `precise_roots` should be cleared and remain
+        // empty until the next GC cycle.
+        precise_roots.clear();
+    }
+
+    /// Set the stack canary around a call into Wasm.
+    ///
+    /// The return value should not be dropped until after the Wasm call has
+    /// returned.
+    ///
+    /// While this method is always safe to call (or not call), it is unsafe to
+    /// call the `wasmtime_runtime::gc` function unless this method is called at
+    /// the proper times and its return value properly outlives its Wasm call.
+    ///
+    /// For `gc` to be safe, this is only *strictly required* to surround the
+    /// oldest host-->Wasm stack frame transition on this thread, but repeatedly
+    /// calling it is idempotent and cheap, so it is recommended to call this
+    /// for every host-->Wasm call.
+    ///
+    /// # Example
+    ///
+    /// ```no_run
+    /// use wasmtime_runtime::*;
+    ///
+    /// # let get_table_from_somewhere = || unimplemented!();
+    /// let table: &VMExternRefActivationsTable = get_table_from_somewhere();
+    ///
+    /// // Set the canary before a Wasm call. The canary should always be a
+    /// // local on the stack.
+    /// let canary = 0;
+    /// let auto_reset_canary = table.set_stack_canary(&canary);
+    ///
+    /// // Do the call into Wasm.
+    /// # let call_into_wasm = || unimplemented!();
+    /// call_into_wasm();
+    ///
+    /// // Only drop the value returned by `set_stack_canary` after the Wasm
+    /// // call has returned.
+    /// drop(auto_reset_canary);
+    /// ```
+    pub fn set_stack_canary<'a>(&'a self, canary: &u8) -> impl Drop + 'a {
+        let should_reset = if self.stack_canary.get().is_none() {
+            let canary = canary as *const u8 as *mut u8;
+            self.stack_canary.set(Some(unsafe {
+                debug_assert!(!canary.is_null());
+                NonNull::new_unchecked(canary)
+            }));
+            true
+        } else {
+            false
+        };
+
+        return AutoResetCanary {
+            table: self,
+            should_reset,
+        };
+
+        struct AutoResetCanary<'a> {
+            table: &'a VMExternRefActivationsTable,
+            should_reset: bool,
+        }
+
+        impl Drop for AutoResetCanary<'_> {
+            fn drop(&mut self) {
+                if self.should_reset {
+                    debug_assert!(self.table.stack_canary.get().is_some());
+                    self.table.stack_canary.set(None);
+                }
+            }
+        }
+    }
+}
+
+/// A registry of stack maps for currently active Wasm modules.
+#[derive(Default)]
+pub struct StackMapRegistry {
+    inner: RefCell<StackMapRegistryInner>,
+}
+
+#[derive(Default)]
+struct StackMapRegistryInner {
+    /// A map from the highest pc in a module, to its stack maps.
+    ///
+    /// For details, see the comment above `GlobalFrameInfo::ranges`.
+    ranges: BTreeMap<usize, ModuleStackMaps>,
+}
+
+#[derive(Debug)]
+struct ModuleStackMaps {
+    /// The range of PCs that this module covers. Different modules must always
+    /// have distinct ranges.
+    range: std::ops::Range<usize>,
+
+    /// A map from a PC in this module (that is a GC safepoint) to its
+    /// associated stack map.
+    pc_to_stack_map: Vec<(usize, Rc<Stackmap>)>,
+}
+
+impl StackMapRegistry {
+    /// Register the stack maps for a given module.
+    ///
+    /// The stack maps should be given as an iterator over a function's PC range
+    /// in memory (that is, where the JIT actually allocated and emitted the
+    /// function's code at), and the stack maps and code offsets within that
+    /// range for each of its GC safepoints.
+    pub fn register_stack_maps<'a>(
+        &self,
+        stack_maps: impl IntoIterator<Item = (std::ops::Range<usize>, &'a [StackMapInformation])>,
+    ) {
+        let mut min = usize::max_value();
+        let mut max = 0;
+        let mut pc_to_stack_map = vec![];
+
+        for (range, infos) in stack_maps {
+            let len = range.end - range.start;
+
+            min = std::cmp::min(min, range.start);
+            max = std::cmp::max(max, range.end);
+
+            for info in infos {
+                assert!((info.code_offset as usize) < len);
+                pc_to_stack_map.push((
+                    range.start + (info.code_offset as usize),
+                    Rc::new(info.stack_map.clone()),
+                ));
+            }
+        }
+
+        if pc_to_stack_map.is_empty() {
+            // Nothing to register.
+            return;
+        }
+
+        let module_stack_maps = ModuleStackMaps {
+            range: min..max,
+            pc_to_stack_map,
+        };
+
+        let mut inner = self.inner.borrow_mut();
+
+        // Check if we've already registered this module.
+        if let Some(existing_module) = inner.ranges.get(&max) {
+            assert_eq!(existing_module.range, module_stack_maps.range);
+            debug_assert_eq!(
+                existing_module.pc_to_stack_map,
+                module_stack_maps.pc_to_stack_map,
+            );
+            return;
+        }
+
+        // Assert that this chunk of ranges doesn't collide with any other known
+        // chunks.
+        if let Some((_, prev)) = inner.ranges.range(max..).next() {
+            assert!(prev.range.start > max);
+        }
+        if let Some((prev_end, _)) = inner.ranges.range(..=min).next_back() {
+            assert!(*prev_end < min);
+        }
+
+        let old = inner.ranges.insert(max, module_stack_maps);
+        assert!(old.is_none());
+    }
+
+    /// Lookup the stack map for the given PC, if any.
+    pub fn lookup_stack_map(&self, pc: usize) -> Option<Rc<Stackmap>> {
+        let inner = self.inner.borrow();
+        let stack_maps = inner.module_stack_maps(pc)?;
+
+        // Do a binary search to find the stack map for the given PC.
+        //
+        // Because GC safepoints are technically only associated with a single
+        // PC, we should ideally only care about `Ok(index)` values returned
+        // from the binary search. However, safepoints are inserted right before
+        // calls, and there are two things that can disturb the PC/offset
+        // associated with the safepoint versus the PC we actually use to query
+        // for the stack map:
+        //
+        // 1. The `backtrace` crate gives us the PC in a frame that will be
+        //    *returned to*, and where execution will continue from, rather than
+        //    the PC of the call we are currently at. So we would need to
+        //    disassemble one instruction backwards to query the actual PC for
+        //    the stack map.
+        //
+        //    TODO: One thing we *could* do to make this a little less error
+        //    prone, would be to assert/check that the nearest GC safepoint
+        //    found is within `max_encoded_size(any kind of call instruction)`
+        //    our queried PC for the target architecture.
+        //
+        // 2. Cranelift's stack maps only handle the stack, not
+        //    registers. However, some references that are arguments to a call
+        //    may need to be in registers. In these cases, what Cranelift will
+        //    do is:
+        //
+        //      a. spill all the live references,
+        //      b. insert a GC safepoint for those references,
+        //      c. reload the references into registers, and finally
+        //      d. make the call.
+        //
+        //    Step (c) adds drift between the GC safepoint and the location of
+        //    the call, which is where we actually walk the stack frame and
+        //    collect its live references.
+        //
+        //    Luckily, the spill stack slots for the live references are still
+        //    up to date, so we can still find all the on-stack roots.
+        //    Furthermore, we do not have a moving GC, so we don't need to worry
+        //    whether the following code will reuse the references in registers
+        //    (which would not have been updated to point to the moved objects)
+        //    or reload from the stack slots (which would have been updated to
+        //    point to the moved objects).
+        let index = match stack_maps
+            .pc_to_stack_map
+            .binary_search_by_key(&pc, |(pc, _stack_map)| *pc)
+        {
+            // Exact hit.
+            Ok(i) => i,
+
+            Err(n) => {
+                // `Err(0)` means that the associated stack map would have been
+                // the first element in the array if this pc had an associated
+                // stack map, but this pc does not have an associated stack
+                // map. That doesn't make sense since every call and trap inside
+                // Wasm is a GC safepoint and should have a stack map, and the
+                // only way to have Wasm frames under this native frame is if we
+                // are at a call or a trap.
+                debug_assert!(n != 0);
+
+                n - 1
+            }
+        };
+
+        let stack_map = stack_maps.pc_to_stack_map[index].1.clone();
+        Some(stack_map)
+    }
+}
+
+impl StackMapRegistryInner {
+    fn module_stack_maps(&self, pc: usize) -> Option<&ModuleStackMaps> {
+        let (end, stack_maps) = self.ranges.range(pc..).next()?;
+        if pc < stack_maps.range.start || *end < pc {
+            None
+        } else {
+            Some(stack_maps)
+        }
+    }
+}
+
+#[derive(Debug, Default)]
+struct DebugOnly<T> {
+    inner: T,
+}
+
+impl<T> std::ops::Deref for DebugOnly<T> {
+    type Target = T;
+
+    fn deref(&self) -> &T {
+        if cfg!(debug_assertions) {
+            &self.inner
+        } else {
+            panic!(
+                "only deref `DebugOnly` when `cfg(debug_assertions)` or \
+                 inside a `debug_assert!(..)`"
+            )
+        }
+    }
+}
+
+impl<T> std::ops::DerefMut for DebugOnly<T> {
+    fn deref_mut(&mut self) -> &mut T {
+        if cfg!(debug_assertions) {
+            &mut self.inner
+        } else {
+            panic!(
+                "only deref `DebugOnly` when `cfg(debug_assertions)` or \
+                 inside a `debug_assert!(..)`"
+            )
+        }
+    }
+}
+
+/// Perform garbage collection of `VMExternRef`s.
+///
+/// # Unsafety
+///
+/// You must have called `VMExternRefActivationsTable::set_stack_canary` for at
+/// least the oldest host-->Wasm stack frame transition on this thread's stack
+/// (it is idempotent to call it more than once) and keep its return value alive
+/// across the duration of that host-->Wasm call.
+///
+/// Additionally, you must have registered the stack maps for every Wasm module
+/// that has frames on the stack with the given `stack_maps_registry`.
+pub unsafe fn gc(
+    stack_maps_registry: &StackMapRegistry,
+    externref_activations_table: &VMExternRefActivationsTable,
+) {
+    log::debug!("start GC");
+
+    debug_assert!({
+        // This set is only non-empty within this function. It is built up when
+        // walking the stack and interpreting stack maps, and then drained back
+        // into the activations table's bump-allocated space at the
+        // end. Therefore, it should always be empty upon entering this
+        // function.
+        let precise_stack_roots = externref_activations_table.precise_stack_roots.borrow();
+        precise_stack_roots.is_empty()
+    });
+
+    // Whenever we call into Wasm from host code for the first time, we set a
+    // stack canary. When we return to that host code, we unset the stack
+    // canary. If there is *not* a stack canary, then there must be zero Wasm
+    // frames on the stack. Therefore, we can simply reset the table without
+    // walking the stack.
+    let stack_canary = match externref_activations_table.stack_canary.get() {
+        None => {
+            if cfg!(debug_assertions) {
+                // Assert that there aren't any Wasm frames on the stack.
+                backtrace::trace(|frame| {
+                    let stack_map = stack_maps_registry.lookup_stack_map(frame.ip() as usize);
+                    assert!(stack_map.is_none());
+                    true
+                });
+            }
+            externref_activations_table.sweep();
+            log::debug!("end GC");
+            return;
+        }
+        Some(canary) => canary.as_ptr() as usize,
+    };
+
+    // There is a stack canary, so there must be Wasm frames on the stack. The
+    // rest of this function consists of:
+    //
+    // * walking the stack,
+    //
+    // * finding the precise set of roots inside Wasm frames via our stack maps,
+    //   and
+    //
+    // * resetting our bump-allocated table's over-approximation to the
+    //   newly-discovered precise set.
+
+    // The SP of the previous (younger) frame we processed.
+    let mut last_sp = None;
+
+    // Whether we have found our stack canary or not yet.
+    let mut found_canary = false;
+
+    // The `activations_table_set` is used for `debug_assert!`s checking that
+    // every reference we read out from the stack via stack maps is actually in
+    // the table. If that weren't true, than either we forgot to insert a
+    // reference in the table when passing it into Wasm (a bug) or we are
+    // reading invalid references from the stack (another bug).
+    let mut activations_table_set: DebugOnly<HashSet<_>> = Default::default();
+    if cfg!(debug_assertions) {
+        externref_activations_table.elements(|elem| {
+            activations_table_set.insert(elem.as_raw() as *mut VMExternData);
+        });
+    }
+
+    backtrace::trace(|frame| {
+        let pc = frame.ip() as usize;
+        let sp = frame.sp() as usize;
+
+        if let Some(stack_map) = stack_maps_registry.lookup_stack_map(pc) {
+            debug_assert!(sp != 0, "we should always get a valid SP for Wasm frames");
+
+            for i in 0..(stack_map.mapped_words() as usize) {
+                if stack_map.get_bit(i) {
+                    // Stack maps have one bit per word in the frame, and the
+                    // zero^th bit is the *lowest* addressed word in the frame,
+                    // i.e. the closest to the SP. So to get the `i`^th word in
+                    // this frame, we add `i * sizeof(word)` to the SP.
+                    let ptr_to_ref = sp + i * mem::size_of::<usize>();
+
+                    let r = std::ptr::read(ptr_to_ref as *const *mut VMExternData);
+                    debug_assert!(
+                        r.is_null() || activations_table_set.contains(&r),
+                        "every on-stack externref inside a Wasm frame should \
+                         have an entry in the VMExternRefActivationsTable"
+                    );
+                    if let Some(r) = NonNull::new(r) {
+                        externref_activations_table.insert_precise_stack_root(r);
+                    }
+                }
+            }
+        }
+
+        if let Some(last_sp) = last_sp {
+            // We've found the stack canary when we walk over the frame that it
+            // is contained within.
+            found_canary |= last_sp <= stack_canary && stack_canary <= sp;
+        }
+        last_sp = Some(sp);
+
+        // Keep walking the stack until we've found the canary, which is the
+        // oldest frame before we ever called into Wasm. We can stop once we've
+        // found it because there won't be any more Wasm frames, and therefore
+        // there won't be anymore on-stack, inside-a-Wasm-frame roots.
+        !found_canary
+    });
+
+    // Only sweep and reset the table if we found the stack canary, and
+    // therefore know that we discovered all the on-stack, inside-a-Wasm-frame
+    // roots. If we did *not* find the stack canary, then `libunwind` failed to
+    // walk the whole stack, and we might be missing roots. Reseting the table
+    // would free those missing roots while they are still in use, leading to
+    // use-after-free.
+    if found_canary {
+        externref_activations_table.sweep();
+    } else {
+        log::warn!("did not find stack canary; skipping GC sweep");
+        let mut roots = externref_activations_table.precise_stack_roots.borrow_mut();
+        roots.clear();
+    }
+
+    log::debug!("end GC");
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -434,4 +1104,56 @@ mod tests {
             actual_offset.try_into().unwrap(),
         );
     }
+
+    #[test]
+    fn table_next_is_at_correct_offset() {
+        let table = VMExternRefActivationsTable::new();
+
+        let table_ptr = &table as *const _;
+        let next_ptr = &table.next as *const _;
+
+        let actual_offset = (next_ptr as usize) - (table_ptr as usize);
+
+        let offsets = wasmtime_environ::VMOffsets {
+            pointer_size: 8,
+            num_signature_ids: 0,
+            num_imported_functions: 0,
+            num_imported_tables: 0,
+            num_imported_memories: 0,
+            num_imported_globals: 0,
+            num_defined_tables: 0,
+            num_defined_memories: 0,
+            num_defined_globals: 0,
+        };
+        assert_eq!(
+            offsets.vm_extern_ref_activation_table_next() as usize,
+            actual_offset
+        );
+    }
+
+    #[test]
+    fn table_end_is_at_correct_offset() {
+        let table = VMExternRefActivationsTable::new();
+
+        let table_ptr = &table as *const _;
+        let end_ptr = &table.end as *const _;
+
+        let actual_offset = (end_ptr as usize) - (table_ptr as usize);
+
+        let offsets = wasmtime_environ::VMOffsets {
+            pointer_size: 8,
+            num_signature_ids: 0,
+            num_imported_functions: 0,
+            num_imported_tables: 0,
+            num_imported_memories: 0,
+            num_imported_globals: 0,
+            num_defined_tables: 0,
+            num_defined_memories: 0,
+            num_defined_globals: 0,
+        };
+        assert_eq!(
+            offsets.vm_extern_ref_activation_table_end() as usize,
+            actual_offset
+        );
+    }
 }
diff --git a/crates/runtime/src/instance.rs b/crates/runtime/src/instance.rs
index 8642da2ae..b77bd8f02 100644
--- a/crates/runtime/src/instance.rs
+++ b/crates/runtime/src/instance.rs
@@ -3,9 +3,10 @@
 //! `InstanceHandle` is a reference-counting handle for an `Instance`.
 
 use crate::export::Export;
+use crate::externref::{StackMapRegistry, VMExternRefActivationsTable};
 use crate::imports::Imports;
 use crate::memory::{DefaultMemoryCreator, RuntimeLinearMemory, RuntimeMemoryCreator};
-use crate::table::Table;
+use crate::table::{Table, TableElement};
 use crate::traphandlers::Trap;
 use crate::vmcontext::{
     VMBuiltinFunctionsArray, VMCallerCheckedAnyfunc, VMContext, VMFunctionBody, VMFunctionImport,
@@ -238,6 +239,16 @@ impl Instance {
         unsafe { self.vmctx_plus_offset(self.offsets.vmctx_interrupts()) }
     }
 
+    /// Return a pointer to the `VMExternRefActivationsTable`.
+    pub fn externref_activations_table(&self) -> *mut *mut VMExternRefActivationsTable {
+        unsafe { self.vmctx_plus_offset(self.offsets.vmctx_externref_activations_table()) }
+    }
+
+    /// Return a pointer to the `StackMapRegistry`.
+    pub fn stack_map_registry(&self) -> *mut *mut StackMapRegistry {
+        unsafe { self.vmctx_plus_offset(self.offsets.vmctx_stack_map_registry()) }
+    }
+
     /// Return a reference to the vmctx used by compiled wasm code.
     pub fn vmctx(&self) -> &VMContext {
         &self.vmctx
@@ -455,11 +466,7 @@ impl Instance {
     }
 
     // Get table element by index.
-    fn table_get(
-        &self,
-        table_index: DefinedTableIndex,
-        index: u32,
-    ) -> Option<VMCallerCheckedAnyfunc> {
+    fn table_get(&self, table_index: DefinedTableIndex, index: u32) -> Option<TableElement> {
         self.tables
             .get(table_index)
             .unwrap_or_else(|| panic!("no table for index {}", table_index.index()))
@@ -470,7 +477,7 @@ impl Instance {
         &self,
         table_index: DefinedTableIndex,
         index: u32,
-        val: VMCallerCheckedAnyfunc,
+        val: TableElement,
     ) -> Result<(), ()> {
         self.tables
             .get(table_index)
@@ -547,7 +554,7 @@ impl Instance {
         // TODO(#983): investigate replacing this get/set loop with a `memcpy`.
         for (dst, src) in (dst..dst + len).zip(src..src + len) {
             table
-                .set(dst, elem[src as usize].clone())
+                .set(dst, TableElement::FuncRef(elem[src as usize].clone()))
                 .expect("should never panic because we already did the bounds check above");
         }
 
@@ -774,6 +781,10 @@ impl InstanceHandle {
     /// internally if you'd like to do so. If possible it's recommended to use
     /// the `wasmtime` crate API rather than this type since that is vetted for
     /// safety.
+    ///
+    /// It is your responsibility to ensure that the given raw
+    /// `externref_activations_table` and `stack_map_registry` outlive this
+    /// instance.
     pub unsafe fn new(
         module: Arc<Module>,
         code: Arc<dyn Any>,
@@ -784,7 +795,12 @@ impl InstanceHandle {
         vmshared_signatures: BoxedSlice<SignatureIndex, VMSharedSignatureIndex>,
         host_state: Box<dyn Any>,
         interrupts: Arc<VMInterrupts>,
+        externref_activations_table: *mut VMExternRefActivationsTable,
+        stack_map_registry: *mut StackMapRegistry,
     ) -> Result<Self, InstantiationError> {
+        debug_assert!(!externref_activations_table.is_null());
+        debug_assert!(!stack_map_registry.is_null());
+
         let tables = create_tables(&module);
         let memories = create_memories(&module, mem_creator.unwrap_or(&DefaultMemoryCreator {}))?;
 
@@ -878,6 +894,8 @@ impl InstanceHandle {
             VMBuiltinFunctionsArray::initialized(),
         );
         *instance.interrupts() = &*instance.interrupts;
+        *instance.externref_activations_table() = externref_activations_table;
+        *instance.stack_map_registry() = stack_map_registry;
 
         // Perform infallible initialization in this constructor, while fallible
         // initialization is deferred to the `initialize` method.
@@ -993,11 +1011,7 @@ impl InstanceHandle {
     /// Get table element reference.
     ///
     /// Returns `None` if index is out of bounds.
-    pub fn table_get(
-        &self,
-        table_index: DefinedTableIndex,
-        index: u32,
-    ) -> Option<VMCallerCheckedAnyfunc> {
+    pub fn table_get(&self, table_index: DefinedTableIndex, index: u32) -> Option<TableElement> {
         self.instance().table_get(table_index, index)
     }
 
@@ -1008,7 +1022,7 @@ impl InstanceHandle {
         &self,
         table_index: DefinedTableIndex,
         index: u32,
-        val: VMCallerCheckedAnyfunc,
+        val: TableElement,
     ) -> Result<(), ()> {
         self.instance().table_set(table_index, index, val)
     }
@@ -1174,7 +1188,10 @@ fn initialize_tables(instance: &Instance) -> Result<(), InstantiationError> {
         for (i, func_idx) in init.elements.iter().enumerate() {
             let anyfunc = instance.get_caller_checked_anyfunc(*func_idx);
             table
-                .set(u32::try_from(start + i).unwrap(), anyfunc)
+                .set(
+                    u32::try_from(start + i).unwrap(),
+                    TableElement::FuncRef(anyfunc),
+                )
                 .unwrap();
         }
     }
diff --git a/crates/runtime/src/lib.rs b/crates/runtime/src/lib.rs
index 6f2896054..f0a8d8427 100644
--- a/crates/runtime/src/lib.rs
+++ b/crates/runtime/src/lib.rs
@@ -37,14 +37,14 @@ pub mod debug_builtins;
 pub mod libcalls;
 
 pub use crate::export::*;
-pub use crate::externref::VMExternRef;
+pub use crate::externref::*;
 pub use crate::imports::Imports;
 pub use crate::instance::{InstanceHandle, InstantiationError, LinkError};
 pub use crate::jit_int::GdbJitImageRegistration;
 pub use crate::memory::{RuntimeLinearMemory, RuntimeMemoryCreator};
 pub use crate::mmap::Mmap;
 pub use crate::sig_registry::SignatureRegistry;
-pub use crate::table::Table;
+pub use crate::table::{Table, TableElement};
 pub use crate::traphandlers::{
     catch_traps, init_traps, raise_lib_trap, raise_user_trap, resume_panic, SignalHandler, Trap,
 };
diff --git a/crates/runtime/src/table.rs b/crates/runtime/src/table.rs
index 5439eec97..aa2f793f8 100644
--- a/crates/runtime/src/table.rs
+++ b/crates/runtime/src/table.rs
@@ -3,7 +3,7 @@
 //! `Table` is to WebAssembly tables what `LinearMemory` is to WebAssembly linear memories.
 
 use crate::vmcontext::{VMCallerCheckedAnyfunc, VMTableDefinition};
-use crate::Trap;
+use crate::{Trap, VMExternRef};
 use std::cell::RefCell;
 use std::convert::{TryFrom, TryInto};
 use wasmtime_environ::wasm::TableElementType;
@@ -12,25 +12,46 @@ use wasmtime_environ::{ir, TablePlan, TableStyle};
 /// A table instance.
 #[derive(Debug)]
 pub struct Table {
-    vec: RefCell<Vec<VMCallerCheckedAnyfunc>>,
+    elements: RefCell<TableElements>,
     maximum: Option<u32>,
 }
 
+/// An element going into or coming out of a table.
+#[derive(Clone, Debug)]
+pub enum TableElement {
+    /// A `funcref`.
+    FuncRef(VMCallerCheckedAnyfunc),
+    /// An `exrernref`.
+    ExternRef(Option<VMExternRef>),
+}
+
+#[derive(Debug)]
+enum TableElements {
+    FuncRefs(Vec<VMCallerCheckedAnyfunc>),
+    ExternRefs(Vec<Option<VMExternRef>>),
+}
+
 impl Table {
     /// Create a new table instance with specified minimum and maximum number of elements.
     pub fn new(plan: &TablePlan) -> Self {
-        match plan.table.ty {
-            TableElementType::Func => (),
-            TableElementType::Val(ty) => {
-                unimplemented!("tables of types other than anyfunc ({})", ty)
-            }
-        };
-        match plan.style {
-            TableStyle::CallerChecksSignature => Self {
-                vec: RefCell::new(vec![
+        let elements =
+            RefCell::new(match plan.table.ty {
+                TableElementType::Func => TableElements::FuncRefs(vec![
                     VMCallerCheckedAnyfunc::default();
                     usize::try_from(plan.table.minimum).unwrap()
                 ]),
+                TableElementType::Val(ty)
+                    if (cfg!(target_pointer_width = "64") && ty == ir::types::R64)
+                        || (cfg!(target_pointer_width = "32") && ty == ir::types::R32) =>
+                {
+                    let min = usize::try_from(plan.table.minimum).unwrap();
+                    TableElements::ExternRefs(vec![None; min])
+                }
+                TableElementType::Val(ty) => unimplemented!("unsupported table type ({})", ty),
+            });
+        match plan.style {
+            TableStyle::CallerChecksSignature => Self {
+                elements,
                 maximum: plan.table.maximum,
             },
         }
@@ -38,7 +59,10 @@ impl Table {
 
     /// Returns the number of allocated elements.
     pub fn size(&self) -> u32 {
-        self.vec.borrow().len().try_into().unwrap()
+        match &*self.elements.borrow() {
+            TableElements::FuncRefs(x) => x.len().try_into().unwrap(),
+            TableElements::ExternRefs(x) => x.len().try_into().unwrap(),
+        }
     }
 
     /// Grow table by the specified amount of elements.
@@ -61,33 +85,45 @@ impl Table {
                 return None;
             }
         };
-        self.vec.borrow_mut().resize(
-            usize::try_from(new_len).unwrap(),
-            VMCallerCheckedAnyfunc::default(),
-        );
+        let new_len = usize::try_from(new_len).unwrap();
+        match &mut *self.elements.borrow_mut() {
+            TableElements::FuncRefs(x) => x.resize(new_len, VMCallerCheckedAnyfunc::default()),
+            TableElements::ExternRefs(x) => x.resize(new_len, None),
+        }
         Some(size)
     }
 
     /// Get reference to the specified element.
     ///
     /// Returns `None` if the index is out of bounds.
-    pub fn get(&self, index: u32) -> Option<VMCallerCheckedAnyfunc> {
-        self.vec.borrow().get(index as usize).cloned()
+    pub fn get(&self, index: u32) -> Option<TableElement> {
+        match &*self.elements.borrow() {
+            TableElements::FuncRefs(x) => x.get(index as usize).cloned().map(TableElement::FuncRef),
+            TableElements::ExternRefs(x) => {
+                x.get(index as usize).cloned().map(TableElement::ExternRef)
+            }
+        }
     }
 
     /// Set reference to the specified element.
     ///
-    /// # Panics
+    /// # Errors
     ///
-    /// Panics if `index` is out of bounds.
-    pub fn set(&self, index: u32, func: VMCallerCheckedAnyfunc) -> Result<(), ()> {
-        match self.vec.borrow_mut().get_mut(index as usize) {
-            Some(slot) => {
-                *slot = func;
-                Ok(())
+    /// Returns an error if `index` is out of bounds or if this table type does
+    /// not match the element type.
+    pub fn set(&self, index: u32, elem: TableElement) -> Result<(), ()> {
+        let mut elems = self.elements.borrow_mut();
+        match &mut *elems {
+            TableElements::FuncRefs(x) => {
+                let slot = x.get_mut(index as usize).ok_or(())?;
+                *slot = elem.try_into().or(Err(()))?;
+            }
+            TableElements::ExternRefs(x) => {
+                let slot = x.get_mut(index as usize).ok_or(())?;
+                *slot = elem.try_into().or(Err(()))?;
             }
-            None => Err(()),
         }
+        Ok(())
     }
 
     /// Copy `len` elements from `src_table[src_index..]` into `dst_table[dst_index..]`.
@@ -137,10 +173,37 @@ impl Table {
 
     /// Return a `VMTableDefinition` for exposing the table to compiled wasm code.
     pub fn vmtable(&self) -> VMTableDefinition {
-        let mut vec = self.vec.borrow_mut();
-        VMTableDefinition {
-            base: vec.as_mut_ptr() as *mut u8,
-            current_elements: vec.len().try_into().unwrap(),
+        match &*self.elements.borrow() {
+            TableElements::FuncRefs(x) => VMTableDefinition {
+                base: x.as_ptr() as *const u8 as *mut u8,
+                current_elements: x.len().try_into().unwrap(),
+            },
+            TableElements::ExternRefs(x) => VMTableDefinition {
+                base: x.as_ptr() as *const u8 as *mut u8,
+                current_elements: x.len().try_into().unwrap(),
+            },
+        }
+    }
+}
+
+impl TryFrom<TableElement> for VMCallerCheckedAnyfunc {
+    type Error = TableElement;
+
+    fn try_from(e: TableElement) -> Result<Self, Self::Error> {
+        match e {
+            TableElement::FuncRef(f) => Ok(f),
+            _ => Err(e),
+        }
+    }
+}
+
+impl TryFrom<TableElement> for Option<VMExternRef> {
+    type Error = TableElement;
+
+    fn try_from(e: TableElement) -> Result<Self, Self::Error> {
+        match e {
+            TableElement::ExternRef(x) => Ok(x),
+            _ => Err(e),
         }
     }
 }
diff --git a/crates/wasmtime/src/externals.rs b/crates/wasmtime/src/externals.rs
index 5e6cf3aca..77e75f64f 100644
--- a/crates/wasmtime/src/externals.rs
+++ b/crates/wasmtime/src/externals.rs
@@ -2,8 +2,10 @@ use crate::trampoline::{
     generate_global_export, generate_memory_export, generate_table_export, StoreInstanceHandle,
 };
 use crate::values::{from_checked_anyfunc, into_checked_anyfunc, Val};
-use crate::{ExternType, GlobalType, MemoryType, Mutability, TableType, ValType};
-use crate::{Func, Store, Trap};
+use crate::{
+    ExternRef, ExternType, Func, GlobalType, MemoryType, Mutability, Store, TableType, Trap,
+    ValType,
+};
 use anyhow::{anyhow, bail, Result};
 use std::slice;
 use wasmtime_environ::wasm;
@@ -299,7 +301,11 @@ fn set_table_item(
     item: wasmtime_runtime::VMCallerCheckedAnyfunc,
 ) -> Result<()> {
     instance
-        .table_set(table_index, item_index, item)
+        .table_set(
+            table_index,
+            item_index,
+            runtime::TableElement::FuncRef(item),
+        )
         .map_err(|()| anyhow!("table element index out of bounds"))
 }
 
@@ -348,7 +354,16 @@ impl Table {
     pub fn get(&self, index: u32) -> Option<Val> {
         let table_index = self.wasmtime_table_index();
         let item = self.instance.table_get(table_index, index)?;
-        Some(from_checked_anyfunc(item, &self.instance.store))
+        match item {
+            runtime::TableElement::FuncRef(f) => {
+                Some(from_checked_anyfunc(f, &self.instance.store))
+            }
+            runtime::TableElement::ExternRef(None) => Some(Val::ExternRef(None)),
+            runtime::TableElement::ExternRef(Some(x)) => Some(Val::ExternRef(Some(ExternRef {
+                inner: x,
+                store: self.instance.store.weak(),
+            }))),
+        }
     }
 
     /// Writes the `val` provided into `index` within this table.
diff --git a/crates/wasmtime/src/func.rs b/crates/wasmtime/src/func.rs
index 119c87ac8..53c7e5ab0 100644
--- a/crates/wasmtime/src/func.rs
+++ b/crates/wasmtime/src/func.rs
@@ -194,7 +194,8 @@ macro_rules! getters {
                     >(export.address);
                     let mut ret = None;
                     $(let $args = $args.into_abi();)*
-                    catch_traps(export.vmctx, &instance.store, || {
+
+                    invoke_wasm_and_catch_traps(export.vmctx, &instance.store, || {
                         ret = Some(fnptr(export.vmctx, ptr::null_mut(), $($args,)*));
                     })?;
 
@@ -265,14 +266,14 @@ impl Func {
             // values produced are correct. There could be a bug in `func` that
             // produces the wrong number or wrong types of values, and we need
             // to catch that here.
-            for (i, (ret, ty)) in returns.iter_mut().zip(ty_clone.results()).enumerate() {
+            for (i, (ret, ty)) in returns.into_iter().zip(ty_clone.results()).enumerate() {
                 if ret.ty() != *ty {
                     return Err(Trap::new(
                         "function attempted to return an incompatible value",
                     ));
                 }
                 unsafe {
-                    ret.write_value_to(values_vec.add(i));
+                    ret.write_value_to(&store, values_vec.add(i));
                 }
             }
             Ok(())
@@ -535,7 +536,7 @@ impl Func {
 
         // Store the argument values into `values_vec`.
         let param_tys = my_ty.params().iter();
-        for ((arg, slot), ty) in params.iter().zip(&mut values_vec).zip(param_tys) {
+        for ((arg, slot), ty) in params.iter().cloned().zip(&mut values_vec).zip(param_tys) {
             if arg.ty() != *ty {
                 bail!(
                     "argument type mismatch: found {} but expected {}",
@@ -547,12 +548,12 @@ impl Func {
                 bail!("cross-`Store` values are not currently supported");
             }
             unsafe {
-                arg.write_value_to(slot);
+                arg.write_value_to(&self.instance.store, slot);
             }
         }
 
         // Call the trampoline.
-        catch_traps(self.export.vmctx, &self.instance.store, || unsafe {
+        invoke_wasm_and_catch_traps(self.export.vmctx, &self.instance.store, || unsafe {
             (self.trampoline)(
                 self.export.vmctx,
                 ptr::null_mut(),
@@ -729,13 +730,18 @@ impl fmt::Debug for Func {
     }
 }
 
-pub(crate) fn catch_traps(
+pub(crate) fn invoke_wasm_and_catch_traps(
     vmctx: *mut VMContext,
     store: &Store,
     closure: impl FnMut(),
 ) -> Result<(), Trap> {
     let signalhandler = store.signal_handler();
     unsafe {
+        let canary = 0;
+        let _auto_reset_canary = store
+            .externref_activations_table()
+            .set_stack_canary(&canary);
+
         wasmtime_runtime::catch_traps(
             vmctx,
             store.engine().config().max_wasm_stack,
diff --git a/crates/wasmtime/src/instance.rs b/crates/wasmtime/src/instance.rs
index ed39a70d4..1477c0a0b 100644
--- a/crates/wasmtime/src/instance.rs
+++ b/crates/wasmtime/src/instance.rs
@@ -50,6 +50,8 @@ fn instantiate(
             config.memory_creator.as_ref().map(|a| a as _),
             store.interrupts().clone(),
             host,
+            &*store.externref_activations_table() as *const _ as *mut _,
+            &*store.stack_map_registry() as *const _ as *mut _,
         )?;
 
         // After we've created the `InstanceHandle` we still need to run
@@ -89,7 +91,7 @@ fn instantiate(
         };
         let vmctx_ptr = instance.handle.vmctx_ptr();
         unsafe {
-            super::func::catch_traps(vmctx_ptr, store, || {
+            super::func::invoke_wasm_and_catch_traps(vmctx_ptr, store, || {
                 mem::transmute::<
                     *const VMFunctionBody,
                     unsafe extern "C" fn(*mut VMContext, *mut VMContext),
@@ -183,10 +185,14 @@ impl Instance {
             bail!("cross-`Engine` instantiation is not currently supported");
         }
 
-        let info = module.register_frame_info();
-        store.register_jit_code(module.compiled_module().jit_code_ranges());
+        let host_info = Box::new({
+            let frame_info_registration = module.register_frame_info();
+            store.register_jit_code(module.compiled_module().jit_code_ranges());
+            store.register_stack_maps(&module);
+            frame_info_registration
+        });
 
-        let handle = instantiate(store, module.compiled_module(), imports, Box::new(info))?;
+        let handle = instantiate(store, module.compiled_module(), imports, host_info)?;
 
         Ok(Instance {
             handle,
diff --git a/crates/wasmtime/src/ref.rs b/crates/wasmtime/src/ref.rs
index 3f87dbd8a..988c15900 100644
--- a/crates/wasmtime/src/ref.rs
+++ b/crates/wasmtime/src/ref.rs
@@ -36,6 +36,11 @@ impl ExternRef {
         &*self.inner
     }
 
+    /// Get the strong reference count for this `ExternRef`.
+    pub fn strong_count(&self) -> usize {
+        self.inner.strong_count()
+    }
+
     /// Does this `ExternRef` point to the same inner value as `other`?0
     ///
     /// This is *only* pointer equality, and does *not* run any inner value's
diff --git a/crates/wasmtime/src/runtime.rs b/crates/wasmtime/src/runtime.rs
index f6eb0e97e..f57fdc8a2 100644
--- a/crates/wasmtime/src/runtime.rs
+++ b/crates/wasmtime/src/runtime.rs
@@ -1,6 +1,7 @@
 use crate::externals::MemoryCreator;
 use crate::r#ref::ExternRef;
 use crate::trampoline::{MemoryCreatorProxy, StoreInstanceHandle};
+use crate::Module;
 use anyhow::{bail, Result};
 use std::any::Any;
 use std::cell::RefCell;
@@ -14,12 +15,13 @@ use std::rc::{Rc, Weak};
 use std::sync::Arc;
 use wasmparser::{OperatorValidatorConfig, ValidatingParserConfig};
 use wasmtime_environ::settings::{self, Configurable};
-use wasmtime_environ::{ir, wasm, CacheConfig, Tunables};
+use wasmtime_environ::{ir, isa::TargetIsa, wasm, CacheConfig, Tunables};
 use wasmtime_jit::{native, CompilationStrategy, Compiler};
 use wasmtime_profiling::{JitDumpAgent, NullProfilerAgent, ProfilingAgent, VTuneAgent};
 use wasmtime_runtime::{
     debug_builtins, InstanceHandle, RuntimeMemoryCreator, SignalHandler, SignatureRegistry,
-    VMExternRef, VMInterrupts, VMSharedSignatureIndex,
+    StackMapRegistry, VMExternRef, VMExternRefActivationsTable, VMInterrupts,
+    VMSharedSignatureIndex,
 };
 
 // Runtime Environment
@@ -194,10 +196,16 @@ impl Config {
         self.validating_config
             .operator_config
             .enable_reference_types = enable;
-        // The reference types proposal depends on the bulk memory proposal
+
+        self.flags
+            .set("enable_safepoints", if enable { "true" } else { "false" })
+            .unwrap();
+
+        // The reference types proposal depends on the bulk memory proposal.
         if enable {
             self.wasm_bulk_memory(true);
         }
+
         self
     }
 
@@ -591,8 +599,12 @@ impl Config {
         self
     }
 
+    pub(crate) fn target_isa(&self) -> Box<dyn TargetIsa> {
+        native::builder().finish(settings::Flags::new(self.flags.clone()))
+    }
+
     fn build_compiler(&self) -> Compiler {
-        let isa = native::builder().finish(settings::Flags::new(self.flags.clone()));
+        let isa = self.target_isa();
         Compiler::new(
             isa,
             self.strategy,
@@ -792,6 +804,8 @@ pub(crate) struct StoreInner {
     signal_handler: RefCell<Option<Box<SignalHandler<'static>>>>,
     jit_code_ranges: RefCell<Vec<(usize, usize)>>,
     host_info: RefCell<HashMap<HostInfoKey, Rc<RefCell<dyn Any>>>>,
+    externref_activations_table: Rc<VMExternRefActivationsTable>,
+    stack_map_registry: Rc<StackMapRegistry>,
 }
 
 struct HostInfoKey(VMExternRef);
@@ -832,6 +846,8 @@ impl Store {
                 signal_handler: RefCell::new(None),
                 jit_code_ranges: RefCell::new(Vec::new()),
                 host_info: RefCell::new(HashMap::new()),
+                externref_activations_table: Rc::new(VMExternRefActivationsTable::new()),
+                stack_map_registry: Rc::new(StackMapRegistry::default()),
             }),
         }
     }
@@ -904,6 +920,24 @@ impl Store {
         }
     }
 
+    pub(crate) fn register_stack_maps(&self, module: &Module) {
+        let module = &module.compiled_module();
+        self.stack_map_registry().register_stack_maps(
+            module
+                .finished_functions()
+                .values()
+                .zip(module.stack_maps().values())
+                .map(|(func, stack_maps)| unsafe {
+                    let ptr = (**func).as_ptr();
+                    let len = (**func).len();
+                    let start = ptr as usize;
+                    let end = ptr as usize + len;
+                    let range = start..end;
+                    (range, &stack_maps[..])
+                }),
+        );
+    }
+
     pub(crate) unsafe fn add_instance(&self, handle: InstanceHandle) -> StoreInstanceHandle {
         self.inner.instances.borrow_mut().push(handle.clone());
         StoreInstanceHandle {
@@ -1074,6 +1108,27 @@ impl Store {
             bail!("interrupts aren't enabled for this `Store`")
         }
     }
+
+    pub(crate) fn externref_activations_table(&self) -> &Rc<VMExternRefActivationsTable> {
+        &self.inner.externref_activations_table
+    }
+
+    pub(crate) fn stack_map_registry(&self) -> &Rc<StackMapRegistry> {
+        &self.inner.stack_map_registry
+    }
+
+    /// Perform garbage collection of `ExternRef`s.
+    pub fn gc(&self) {
+        // For this crate's API, we ensure that `set_stack_canary` invariants
+        // are upheld for all host-->Wasm calls, and we register every module
+        // used with this store in `self.inner.stack_map_registry`.
+        unsafe {
+            wasmtime_runtime::gc(
+                &*self.inner.stack_map_registry,
+                &*self.inner.externref_activations_table,
+            );
+        }
+    }
 }
 
 impl Default for Store {
diff --git a/crates/wasmtime/src/trampoline/create_handle.rs b/crates/wasmtime/src/trampoline/create_handle.rs
index 6d2f691cc..12faef120 100644
--- a/crates/wasmtime/src/trampoline/create_handle.rs
+++ b/crates/wasmtime/src/trampoline/create_handle.rs
@@ -46,6 +46,8 @@ pub(crate) fn create_handle(
             signatures.into_boxed_slice(),
             state,
             store.interrupts().clone(),
+            &*store.externref_activations_table() as *const _ as *mut _,
+            &*store.stack_map_registry() as *const _ as *mut _,
         )?;
         Ok(store.add_instance(handle))
     }
diff --git a/crates/wasmtime/src/trampoline/func.rs b/crates/wasmtime/src/trampoline/func.rs
index b4a614357..fd095e6d1 100644
--- a/crates/wasmtime/src/trampoline/func.rs
+++ b/crates/wasmtime/src/trampoline/func.rs
@@ -208,11 +208,7 @@ pub fn create_handle_with_function(
     func: Box<dyn Fn(*mut VMContext, *mut u128) -> Result<(), Trap>>,
     store: &Store,
 ) -> Result<(StoreInstanceHandle, VMTrampoline)> {
-    let isa = {
-        let isa_builder = native::builder();
-        let flag_builder = settings::builder();
-        isa_builder.finish(settings::Flags::new(flag_builder))
-    };
+    let isa = store.engine().config().target_isa();
 
     let pointer_type = isa.pointer_type();
     let sig = match ft.get_wasmtime_signature(pointer_type) {
diff --git a/crates/wasmtime/src/types.rs b/crates/wasmtime/src/types.rs
index 75c67ae18..96f5ce9f3 100644
--- a/crates/wasmtime/src/types.rs
+++ b/crates/wasmtime/src/types.rs
@@ -106,6 +106,10 @@ impl ValType {
             ValType::F32 => Some(ir::types::F32),
             ValType::F64 => Some(ir::types::F64),
             ValType::V128 => Some(ir::types::I8X16),
+            #[cfg(target_pointer_width = "64")]
+            ValType::ExternRef => Some(ir::types::R64),
+            #[cfg(target_pointer_width = "32")]
+            ValType::ExternRef => Some(ir::types::R32),
             _ => None,
         }
     }
@@ -117,6 +121,10 @@ impl ValType {
             ir::types::F32 => Some(ValType::F32),
             ir::types::F64 => Some(ValType::F64),
             ir::types::I8X16 => Some(ValType::V128),
+            #[cfg(target_pointer_width = "64")]
+            ir::types::R64 => Some(ValType::ExternRef),
+            #[cfg(target_pointer_width = "32")]
+            ir::types::R32 => Some(ValType::ExternRef),
             _ => None,
         }
     }
diff --git a/crates/wasmtime/src/values.rs b/crates/wasmtime/src/values.rs
index 9c598cd51..7885e26c5 100644
--- a/crates/wasmtime/src/values.rs
+++ b/crates/wasmtime/src/values.rs
@@ -79,15 +79,21 @@ impl Val {
         }
     }
 
-    pub(crate) unsafe fn write_value_to(&self, p: *mut u128) {
+    pub(crate) unsafe fn write_value_to(self, store: &Store, p: *mut u128) {
         match self {
-            Val::I32(i) => ptr::write(p as *mut i32, *i),
-            Val::I64(i) => ptr::write(p as *mut i64, *i),
-            Val::F32(u) => ptr::write(p as *mut u32, *u),
-            Val::F64(u) => ptr::write(p as *mut u64, *u),
-            Val::V128(b) => ptr::write(p as *mut u128, *b),
+            Val::I32(i) => ptr::write(p as *mut i32, i),
+            Val::I64(i) => ptr::write(p as *mut i64, i),
+            Val::F32(u) => ptr::write(p as *mut u32, u),
+            Val::F64(u) => ptr::write(p as *mut u64, u),
+            Val::V128(b) => ptr::write(p as *mut u128, b),
             Val::ExternRef(None) => ptr::write(p, 0),
-            Val::ExternRef(Some(x)) => ptr::write(p as *mut *mut u8, x.inner.clone().into_raw()),
+            Val::ExternRef(Some(x)) => {
+                let externref_ptr = x.inner.as_raw();
+                store
+                    .externref_activations_table()
+                    .insert_with_gc(x.inner, store.stack_map_registry());
+                ptr::write(p as *mut *mut u8, externref_ptr)
+            }
             _ => unimplemented!("Val::write_value_to"),
         }
     }
@@ -105,7 +111,7 @@ impl Val {
                     Val::ExternRef(None)
                 } else {
                     Val::ExternRef(Some(ExternRef {
-                        inner: VMExternRef::from_raw(raw),
+                        inner: VMExternRef::clone_from_raw(raw),
                         store: store.weak(),
                     }))
                 }
diff --git a/src/obj.rs b/src/obj.rs
index 72cb46189..63929f619 100644
--- a/src/obj.rs
+++ b/src/obj.rs
@@ -99,19 +99,26 @@ pub fn compile_to_obj(
         .translate(wasm)
         .context("failed to translate module")?;
 
-    // TODO: use the traps information
-    let (compilation, relocations, address_transform, value_ranges, stack_slots, _traps) =
-        match strategy {
-            Strategy::Auto | Strategy::Cranelift => {
-                Cranelift::compile_module(&translation, &*isa, cache_config)
-            }
-            #[cfg(feature = "lightbeam")]
-            Strategy::Lightbeam => Lightbeam::compile_module(&translation, &*isa, cache_config),
-            #[cfg(not(feature = "lightbeam"))]
-            Strategy::Lightbeam => bail!("lightbeam support not enabled"),
-            other => bail!("unsupported compilation strategy {:?}", other),
+    // TODO: use the traps and stack maps information.
+    let (
+        compilation,
+        relocations,
+        address_transform,
+        value_ranges,
+        stack_slots,
+        _traps,
+        _stack_maps,
+    ) = match strategy {
+        Strategy::Auto | Strategy::Cranelift => {
+            Cranelift::compile_module(&translation, &*isa, cache_config)
         }
-        .context("failed to compile module")?;
+        #[cfg(feature = "lightbeam")]
+        Strategy::Lightbeam => Lightbeam::compile_module(&translation, &*isa, cache_config),
+        #[cfg(not(feature = "lightbeam"))]
+        Strategy::Lightbeam => bail!("lightbeam support not enabled"),
+        other => bail!("unsupported compilation strategy {:?}", other),
+    }
+    .context("failed to compile module")?;
 
     if compilation.is_empty() {
         bail!("no functions were found/compiled");


Test patch:
diff --git a/cranelift/codegen/src/isa/x64/inst/emit_tests.rs b/cranelift/codegen/src/isa/x64/inst/emit_tests.rs
index 6b54c7a1f..e1a91633c 100644
--- a/cranelift/codegen/src/isa/x64/inst/emit_tests.rs
+++ b/cranelift/codegen/src/isa/x64/inst/emit_tests.rs
@@ -882,184 +882,274 @@ fn test_x64_emit() {
     //
     // Alu_RMI_R
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Add, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Add, RegMemImm::reg(r15), w_rdx),
         "4C01FA",
         "addq    %r15, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::reg(rcx), w_r8),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Add, RegMemImm::reg(rcx), w_r8),
         "4101C8",
         "addl    %ecx, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::reg(rcx), w_rsi),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Add, RegMemImm::reg(rcx), w_rsi),
         "01CE",
         "addl    %ecx, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Add, RMI::mem(Addr::imm_reg(99, rdi)), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Add,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
+            w_rdx,
+        ),
         "48035763",
         "addq    99(%rdi), %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::mem(Addr::imm_reg(99, rdi)), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
+            w_r8,
+        ),
         "44034763",
         "addl    99(%rdi), %r8d",
     ));
     insns.push((
         Inst::alu_rmi_r(
             false,
-            RMI_R_Op::Add,
-            RMI::mem(Addr::imm_reg(99, rdi)),
+            AluRmiROpcode::Add,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
             w_rsi,
         ),
         "037763",
         "addl    99(%rdi), %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Add, RMI::imm(-127i32 as u32), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-127i32 as u32),
+            w_rdx,
+        ),
         "4883C281",
         "addq    $-127, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Add, RMI::imm(-129i32 as u32), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-129i32 as u32),
+            w_rdx,
+        ),
         "4881C27FFFFFFF",
         "addq    $-129, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Add, RMI::imm(76543210), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Add, RegMemImm::imm(76543210), w_rdx),
         "4881C2EAF48F04",
         "addq    $76543210, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(-127i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-127i32 as u32),
+            w_r8,
+        ),
         "4183C081",
         "addl    $-127, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(-129i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-129i32 as u32),
+            w_r8,
+        ),
         "4181C07FFFFFFF",
         "addl    $-129, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(-76543210i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-76543210i32 as u32),
+            w_r8,
+        ),
         "4181C0160B70FB",
         "addl    $-76543210, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(-127i32 as u32), w_rsi),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-127i32 as u32),
+            w_rsi,
+        ),
         "83C681",
         "addl    $-127, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(-129i32 as u32), w_rsi),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Add,
+            RegMemImm::imm(-129i32 as u32),
+            w_rsi,
+        ),
         "81C67FFFFFFF",
         "addl    $-129, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Add, RMI::imm(76543210), w_rsi),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Add, RegMemImm::imm(76543210), w_rsi),
         "81C6EAF48F04",
         "addl    $76543210, %esi",
     ));
     // This is pretty feeble
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Sub, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Sub, RegMemImm::reg(r15), w_rdx),
         "4C29FA",
         "subq    %r15, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::And, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::And, RegMemImm::reg(r15), w_rdx),
         "4C21FA",
         "andq    %r15, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Or, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Or, RegMemImm::reg(r15), w_rdx),
         "4C09FA",
         "orq     %r15, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Xor, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Xor, RegMemImm::reg(r15), w_rdx),
         "4C31FA",
         "xorq    %r15, %rdx",
     ));
     // Test all mul cases, though
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Mul, RMI::reg(r15), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Mul, RegMemImm::reg(r15), w_rdx),
         "490FAFD7",
         "imulq   %r15, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::reg(rcx), w_r8),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Mul, RegMemImm::reg(rcx), w_r8),
         "440FAFC1",
         "imull   %ecx, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::reg(rcx), w_rsi),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Mul, RegMemImm::reg(rcx), w_rsi),
         "0FAFF1",
         "imull   %ecx, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Mul, RMI::mem(Addr::imm_reg(99, rdi)), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Mul,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
+            w_rdx,
+        ),
         "480FAF5763",
         "imulq   99(%rdi), %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::mem(Addr::imm_reg(99, rdi)), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
+            w_r8,
+        ),
         "440FAF4763",
         "imull   99(%rdi), %r8d",
     ));
     insns.push((
         Inst::alu_rmi_r(
             false,
-            RMI_R_Op::Mul,
-            RMI::mem(Addr::imm_reg(99, rdi)),
+            AluRmiROpcode::Mul,
+            RegMemImm::mem(Addr::imm_reg(99, rdi)),
             w_rsi,
         ),
         "0FAF7763",
         "imull   99(%rdi), %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Mul, RMI::imm(-127i32 as u32), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-127i32 as u32),
+            w_rdx,
+        ),
         "486BD281",
         "imulq   $-127, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Mul, RMI::imm(-129i32 as u32), w_rdx),
+        Inst::alu_rmi_r(
+            true,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-129i32 as u32),
+            w_rdx,
+        ),
         "4869D27FFFFFFF",
         "imulq   $-129, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(true, RMI_R_Op::Mul, RMI::imm(76543210), w_rdx),
+        Inst::alu_rmi_r(true, AluRmiROpcode::Mul, RegMemImm::imm(76543210), w_rdx),
         "4869D2EAF48F04",
         "imulq   $76543210, %rdx",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(-127i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-127i32 as u32),
+            w_r8,
+        ),
         "456BC081",
         "imull   $-127, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(-129i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-129i32 as u32),
+            w_r8,
+        ),
         "4569C07FFFFFFF",
         "imull   $-129, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(-76543210i32 as u32), w_r8),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-76543210i32 as u32),
+            w_r8,
+        ),
         "4569C0160B70FB",
         "imull   $-76543210, %r8d",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(-127i32 as u32), w_rsi),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-127i32 as u32),
+            w_rsi,
+        ),
         "6BF681",
         "imull   $-127, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(-129i32 as u32), w_rsi),
+        Inst::alu_rmi_r(
+            false,
+            AluRmiROpcode::Mul,
+            RegMemImm::imm(-129i32 as u32),
+            w_rsi,
+        ),
         "69F67FFFFFFF",
         "imull   $-129, %esi",
     ));
     insns.push((
-        Inst::alu_rmi_r(false, RMI_R_Op::Mul, RMI::imm(76543210), w_rsi),
+        Inst::alu_rmi_r(false, AluRmiROpcode::Mul, RegMemImm::imm(76543210), w_rsi),
         "69F6EAF48F04",
         "imull   $76543210, %esi",
     ));
@@ -1837,314 +1927,318 @@ fn test_x64_emit() {
     // ========================================================
     // CmpRMIR
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::reg(r15), rdx),
+        Inst::cmp_rmi_r(8, RegMemImm::reg(r15), rdx),
         "4C39FA",
         "cmpq    %r15, %rdx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::reg(rcx), r8),
+        Inst::cmp_rmi_r(8, RegMemImm::reg(rcx), r8),
         "4939C8",
         "cmpq    %rcx, %r8",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::reg(rcx), rsi),
+        Inst::cmp_rmi_r(8, RegMemImm::reg(rcx), rsi),
         "4839CE",
         "cmpq    %rcx, %rsi",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::mem(Addr::imm_reg(99, rdi)), rdx),
+        Inst::cmp_rmi_r(8, RegMemImm::mem(Addr::imm_reg(99, rdi)), rdx),
         "483B5763",
         "cmpq    99(%rdi), %rdx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::mem(Addr::imm_reg(99, rdi)), r8),
+        Inst::cmp_rmi_r(8, RegMemImm::mem(Addr::imm_reg(99, rdi)), r8),
         "4C3B4763",
         "cmpq    99(%rdi), %r8",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::mem(Addr::imm_reg(99, rdi)), rsi),
+        Inst::cmp_rmi_r(8, RegMemImm::mem(Addr::imm_reg(99, rdi)), rsi),
         "483B7763",
         "cmpq    99(%rdi), %rsi",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::imm(76543210), rdx),
+        Inst::cmp_rmi_r(8, RegMemImm::imm(76543210), rdx),
         "4881FAEAF48F04",
         "cmpq    $76543210, %rdx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::imm(-76543210i32 as u32), r8),
+        Inst::cmp_rmi_r(8, RegMemImm::imm(-76543210i32 as u32), r8),
         "4981F8160B70FB",
         "cmpq    $-76543210, %r8",
     ));
     insns.push((
-        Inst::cmp_rmi_r(8, RMI::imm(76543210), rsi),
+        Inst::cmp_rmi_r(8, RegMemImm::imm(76543210), rsi),
         "4881FEEAF48F04",
         "cmpq    $76543210, %rsi",
     ));
     //
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::reg(r15), rdx),
+        Inst::cmp_rmi_r(4, RegMemImm::reg(r15), rdx),
         "4439FA",
         "cmpl    %r15d, %edx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::reg(rcx), r8),
+        Inst::cmp_rmi_r(4, RegMemImm::reg(rcx), r8),
         "4139C8",
         "cmpl    %ecx, %r8d",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::reg(rcx), rsi),
+        Inst::cmp_rmi_r(4, RegMemImm::reg(rcx), rsi),
         "39CE",
         "cmpl    %ecx, %esi",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::mem(Addr::imm_reg(99, rdi)), rdx),
+        Inst::cmp_rmi_r(4, RegMemImm::mem(Addr::imm_reg(99, rdi)), rdx),
         "3B5763",
         "cmpl    99(%rdi), %edx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::mem(Addr::imm_reg(99, rdi)), r8),
+        Inst::cmp_rmi_r(4, RegMemImm::mem(Addr::imm_reg(99, rdi)), r8),
         "443B4763",
         "cmpl    99(%rdi), %r8d",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::mem(Addr::imm_reg(99, rdi)), rsi),
+        Inst::cmp_rmi_r(4, RegMemImm::mem(Addr::imm_reg(99, rdi)), rsi),
         "3B7763",
         "cmpl    99(%rdi), %esi",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::imm(76543210), rdx),
+        Inst::cmp_rmi_r(4, RegMemImm::imm(76543210), rdx),
         "81FAEAF48F04",
         "cmpl    $76543210, %edx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::imm(-76543210i32 as u32), r8),
+        Inst::cmp_rmi_r(4, RegMemImm::imm(-76543210i32 as u32), r8),
         "4181F8160B70FB",
         "cmpl    $-76543210, %r8d",
     ));
     insns.push((
-        Inst::cmp_rmi_r(4, RMI::imm(76543210), rsi),
+        Inst::cmp_rmi_r(4, RegMemImm::imm(76543210), rsi),
         "81FEEAF48F04",
         "cmpl    $76543210, %esi",
     ));
     //
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::reg(r15), rdx),
+        Inst::cmp_rmi_r(2, RegMemImm::reg(r15), rdx),
         "664439FA",
         "cmpw    %r15w, %dx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::reg(rcx), r8),
+        Inst::cmp_rmi_r(2, RegMemImm::reg(rcx), r8),
         "664139C8",
         "cmpw    %cx, %r8w",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::reg(rcx), rsi),
+        Inst::cmp_rmi_r(2, RegMemImm::reg(rcx), rsi),
         "6639CE",
         "cmpw    %cx, %si",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::mem(Addr::imm_reg(99, rdi)), rdx),
+        Inst::cmp_rmi_r(2, RegMemImm::mem(Addr::imm_reg(99, rdi)), rdx),
         "663B5763",
         "cmpw    99(%rdi), %dx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::mem(Addr::imm_reg(99, rdi)), r8),
+        Inst::cmp_rmi_r(2, RegMemImm::mem(Addr::imm_reg(99, rdi)), r8),
         "66443B4763",
         "cmpw    99(%rdi), %r8w",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::mem(Addr::imm_reg(99, rdi)), rsi),
+        Inst::cmp_rmi_r(2, RegMemImm::mem(Addr::imm_reg(99, rdi)), rsi),
         "663B7763",
         "cmpw    99(%rdi), %si",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::imm(23210), rdx),
+        Inst::cmp_rmi_r(2, RegMemImm::imm(23210), rdx),
         "6681FAAA5A",
         "cmpw    $23210, %dx",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::imm(-7654i32 as u32), r8),
+        Inst::cmp_rmi_r(2, RegMemImm::imm(-7654i32 as u32), r8),
         "664181F81AE2",
         "cmpw    $-7654, %r8w",
     ));
     insns.push((
-        Inst::cmp_rmi_r(2, RMI::imm(7654), rsi),
+        Inst::cmp_rmi_r(2, RegMemImm::imm(7654), rsi),
         "6681FEE61D",
         "cmpw    $7654, %si",
     ));
     //
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r15), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r15), rdx),
         "4438FA",
         "cmpb    %r15b, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), r8),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), r8),
         "4138C8",
         "cmpb    %cl, %r8b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), rsi),
         "4038CE",
         "cmpb    %cl, %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::mem(Addr::imm_reg(99, rdi)), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::mem(Addr::imm_reg(99, rdi)), rdx),
         "3A5763",
         "cmpb    99(%rdi), %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::mem(Addr::imm_reg(99, rdi)), r8),
+        Inst::cmp_rmi_r(1, RegMemImm::mem(Addr::imm_reg(99, rdi)), r8),
         "443A4763",
         "cmpb    99(%rdi), %r8b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::mem(Addr::imm_reg(99, rdi)), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::mem(Addr::imm_reg(99, rdi)), rsi),
         "403A7763",
         "cmpb    99(%rdi), %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::imm(70), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::imm(70), rdx),
         "80FA46",
         "cmpb    $70, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::imm(-76i32 as u32), r8),
+        Inst::cmp_rmi_r(1, RegMemImm::imm(-76i32 as u32), r8),
         "4180F8B4",
         "cmpb    $-76, %r8b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::imm(76), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::imm(76), rsi),
         "4080FE4C",
         "cmpb    $76, %sil",
     ));
     // Extra byte-cases (paranoia!) for cmp_rmi_r for first operand = R
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rax), rbx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rax), rbx),
         "38C3",
         "cmpb    %al, %bl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rbx), rax),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rbx), rax),
         "38D8",
         "cmpb    %bl, %al",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), rdx),
         "38CA",
         "cmpb    %cl, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), rsi),
         "4038CE",
         "cmpb    %cl, %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), r10),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), r10),
         "4138CA",
         "cmpb    %cl, %r10b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rcx), r14),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rcx), r14),
         "4138CE",
         "cmpb    %cl, %r14b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rbp), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rbp), rdx),
         "4038EA",
         "cmpb    %bpl, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rbp), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rbp), rsi),
         "4038EE",
         "cmpb    %bpl, %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rbp), r10),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rbp), r10),
         "4138EA",
         "cmpb    %bpl, %r10b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(rbp), r14),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(rbp), r14),
         "4138EE",
         "cmpb    %bpl, %r14b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r9), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r9), rdx),
         "4438CA",
         "cmpb    %r9b, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r9), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r9), rsi),
         "4438CE",
         "cmpb    %r9b, %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r9), r10),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r9), r10),
         "4538CA",
         "cmpb    %r9b, %r10b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r9), r14),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r9), r14),
         "4538CE",
         "cmpb    %r9b, %r14b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r13), rdx),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r13), rdx),
         "4438EA",
         "cmpb    %r13b, %dl",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r13), rsi),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r13), rsi),
         "4438EE",
         "cmpb    %r13b, %sil",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r13), r10),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r13), r10),
         "4538EA",
         "cmpb    %r13b, %r10b",
     ));
     insns.push((
-        Inst::cmp_rmi_r(1, RMI::reg(r13), r14),
+        Inst::cmp_rmi_r(1, RegMemImm::reg(r13), r14),
         "4538EE",
         "cmpb    %r13b, %r14b",
     ));
 
     // ========================================================
     // Push64
-    insns.push((Inst::push64(RMI::reg(rdi)), "57", "pushq   %rdi"));
-    insns.push((Inst::push64(RMI::reg(r8)), "4150", "pushq   %r8"));
+    insns.push((Inst::push64(RegMemImm::reg(rdi)), "57", "pushq   %rdi"));
+    insns.push((Inst::push64(RegMemImm::reg(r8)), "4150", "pushq   %r8"));
     insns.push((
-        Inst::push64(RMI::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
+        Inst::push64(RegMemImm::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
         "FFB4CE41010000",
         "pushq   321(%rsi,%rcx,8)",
     ));
     insns.push((
-        Inst::push64(RMI::mem(Addr::imm_reg_reg_shift(321, r9, rbx, 2))),
+        Inst::push64(RegMemImm::mem(Addr::imm_reg_reg_shift(321, r9, rbx, 2))),
         "41FFB49941010000",
         "pushq   321(%r9,%rbx,4)",
     ));
-    insns.push((Inst::push64(RMI::imm(0)), "6A00", "pushq   $0"));
-    insns.push((Inst::push64(RMI::imm(127)), "6A7F", "pushq   $127"));
-    insns.push((Inst::push64(RMI::imm(128)), "6880000000", "pushq   $128"));
+    insns.push((Inst::push64(RegMemImm::imm(0)), "6A00", "pushq   $0"));
+    insns.push((Inst::push64(RegMemImm::imm(127)), "6A7F", "pushq   $127"));
     insns.push((
-        Inst::push64(RMI::imm(0x31415927)),
+        Inst::push64(RegMemImm::imm(128)),
+        "6880000000",
+        "pushq   $128",
+    ));
+    insns.push((
+        Inst::push64(RegMemImm::imm(0x31415927)),
         "6827594131",
         "pushq   $826366247",
     ));
     insns.push((
-        Inst::push64(RMI::imm(-128i32 as u32)),
+        Inst::push64(RegMemImm::imm(-128i32 as u32)),
         "6A80",
         "pushq   $-128",
     ));
     insns.push((
-        Inst::push64(RMI::imm(-129i32 as u32)),
+        Inst::push64(RegMemImm::imm(-129i32 as u32)),
         "687FFFFFFF",
         "pushq   $-129",
     ));
     insns.push((
-        Inst::push64(RMI::imm(-0x75c4e8a1i32 as u32)),
+        Inst::push64(RegMemImm::imm(-0x75c4e8a1i32 as u32)),
         "685F173B8A",
         "pushq   $-1975838881",
     ));
@@ -2161,15 +2255,23 @@ fn test_x64_emit() {
 
     // ========================================================
     // CallUnknown
-    insns.push((Inst::call_unknown(RM::reg(rbp)), "FFD5", "call    *%rbp"));
-    insns.push((Inst::call_unknown(RM::reg(r11)), "41FFD3", "call    *%r11"));
     insns.push((
-        Inst::call_unknown(RM::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
+        Inst::call_unknown(RegMem::reg(rbp)),
+        "FFD5",
+        "call    *%rbp",
+    ));
+    insns.push((
+        Inst::call_unknown(RegMem::reg(r11)),
+        "41FFD3",
+        "call    *%r11",
+    ));
+    insns.push((
+        Inst::call_unknown(RegMem::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
         "FF94CE41010000",
         "call    *321(%rsi,%rcx,8)",
     ));
     insns.push((
-        Inst::call_unknown(RM::mem(Addr::imm_reg_reg_shift(321, r10, rdx, 2))),
+        Inst::call_unknown(RegMem::mem(Addr::imm_reg_reg_shift(321, r10, rdx, 2))),
         "41FF949241010000",
         "call    *321(%r10,%rdx,4)",
     ));
@@ -2192,15 +2294,19 @@ fn test_x64_emit() {
 
     // ========================================================
     // JmpUnknown
-    insns.push((Inst::jmp_unknown(RM::reg(rbp)), "FFE5", "jmp     *%rbp"));
-    insns.push((Inst::jmp_unknown(RM::reg(r11)), "41FFE3", "jmp     *%r11"));
+    insns.push((Inst::jmp_unknown(RegMem::reg(rbp)), "FFE5", "jmp     *%rbp"));
+    insns.push((
+        Inst::jmp_unknown(RegMem::reg(r11)),
+        "41FFE3",
+        "jmp     *%r11",
+    ));
     insns.push((
-        Inst::jmp_unknown(RM::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
+        Inst::jmp_unknown(RegMem::mem(Addr::imm_reg_reg_shift(321, rsi, rcx, 3))),
         "FFA4CE41010000",
         "jmp     *321(%rsi,%rcx,8)",
     ));
     insns.push((
-        Inst::jmp_unknown(RM::mem(Addr::imm_reg_reg_shift(321, r10, rdx, 2))),
+        Inst::jmp_unknown(RegMem::mem(Addr::imm_reg_reg_shift(321, r10, rdx, 2))),
         "41FFA49241010000",
         "jmp     *321(%r10,%rdx,4)",
     ));
@@ -2209,32 +2315,32 @@ fn test_x64_emit() {
     // XMM_RM_R
 
     insns.push((
-        Inst::xmm_rm_r(SSE_Op::SSE_Addss, RM::reg(xmm1), w_xmm0),
+        Inst::xmm_rm_r(SseOpcode::Addss, RegMem::reg(xmm1), w_xmm0),
         "F30F58C1",
         "addss   %xmm1, %xmm0",
     ));
     insns.push((
-        Inst::xmm_rm_r(SSE_Op::SSE_Subss, RM::reg(xmm0), w_xmm1),
+        Inst::xmm_rm_r(SseOpcode::Subss, RegMem::reg(xmm0), w_xmm1),
         "F30F5CC8",
         "subss   %xmm0, %xmm1",
     ));
 
     insns.push((
-        Inst::xmm_rm_r(SSE_Op::SSE_Addss, RM::reg(xmm11), w_xmm13),
+        Inst::xmm_rm_r(SseOpcode::Addss, RegMem::reg(xmm11), w_xmm13),
         "F3450F58EB",
         "addss   %xmm11, %xmm13",
     ));
 
     insns.push((
-        Inst::xmm_rm_r(SSE_Op::SSE_Subss, RM::reg(xmm12), w_xmm1),
+        Inst::xmm_rm_r(SseOpcode::Subss, RegMem::reg(xmm12), w_xmm1),
         "F3410F5CCC",
         "subss   %xmm12, %xmm1",
     ));
 
     insns.push((
         Inst::xmm_rm_r(
-            SSE_Op::SSE_Addss,
-            RM::mem(Addr::imm_reg_reg_shift(123, r10, rdx, 2)),
+            SseOpcode::Addss,
+            RegMem::mem(Addr::imm_reg_reg_shift(123, r10, rdx, 2)),
             w_xmm0,
         ),
         "F3410F5844927B",
@@ -2243,8 +2349,8 @@ fn test_x64_emit() {
 
     insns.push((
         Inst::xmm_rm_r(
-            SSE_Op::SSE_Subss,
-            RM::mem(Addr::imm_reg_reg_shift(321, r10, rax, 3)),
+            SseOpcode::Subss,
+            RegMem::mem(Addr::imm_reg_reg_shift(321, r10, rax, 3)),
             w_xmm10,
         ),
         "F3450F5C94C241010000",
@@ -2255,13 +2361,13 @@ fn test_x64_emit() {
     // XMM_R_R
 
     insns.push((
-        Inst::xmm_r_r(SSE_Op::SSE_Movss, xmm3, w_xmm2),
+        Inst::xmm_r_r(SseOpcode::Movss, xmm3, w_xmm2),
         "F30F10D3",
         "movss   %xmm3, %xmm2",
     ));
 
     insns.push((
-        Inst::xmm_r_r(SSE_Op::SSE2_Movsd, xmm4, w_xmm3),
+        Inst::xmm_r_r(SseOpcode::Movsd, xmm4, w_xmm3),
         "F20F10DC",
         "movsd   %xmm4, %xmm3",
     ));
diff --git a/crates/environ/src/cache/tests.rs b/crates/environ/src/cache/tests.rs
index d45437117..35dc6c613 100644
--- a/crates/environ/src/cache/tests.rs
+++ b/crates/environ/src/cache/tests.rs
@@ -100,5 +100,6 @@ fn new_module_cache_data() -> Result<ModuleCacheDataTupleType, ()> {
         PrimaryMap::new(),
         PrimaryMap::new(),
         PrimaryMap::new(),
+        PrimaryMap::new(),
     ))
 }
diff --git a/tests/all/gc.rs b/tests/all/gc.rs
new file mode 100644
index 000000000..e6950ccbb
--- /dev/null
+++ b/tests/all/gc.rs
@@ -0,0 +1,228 @@
+use std::cell::Cell;
+use std::rc::Rc;
+use wasmtime::*;
+
+fn ref_types_module(source: &str) -> anyhow::Result<(Store, Module)> {
+    let _ = env_logger::try_init();
+
+    let mut config = Config::new();
+    config.wasm_reference_types(true);
+
+    let engine = Engine::new(&config);
+    let store = Store::new(&engine);
+
+    let module = Module::new(&engine, source)?;
+
+    Ok((store, module))
+}
+
+#[test]
+fn smoke_test_gc() -> anyhow::Result<()> {
+    let (store, module) = ref_types_module(
+        r#"
+            (module
+                (import "" "" (func $do_gc))
+                (func $recursive (export "func") (param i32 externref) (result externref)
+                    local.get 0
+                    i32.eqz
+                    if (result externref)
+                        call $do_gc
+                        local.get 1
+                    else
+                        local.get 0
+                        i32.const 1
+                        i32.sub
+                        local.get 1
+                        call $recursive
+                    end
+                )
+            )
+        "#,
+    )?;
+
+    let do_gc = Func::wrap(&store, {
+        let store = store.clone();
+        move || {
+            // Do a GC with `externref`s on the stack in Wasm frames.
+            store.gc();
+        }
+    });
+    let instance = Instance::new(&store, &module, &[do_gc.into()])?;
+    let func = instance.get_func("func").unwrap();
+
+    let inner_dropped = Rc::new(Cell::new(false));
+    let r = ExternRef::new(&store, SetFlagOnDrop(inner_dropped.clone()));
+    {
+        let args = [Val::I32(5), Val::ExternRef(Some(r.clone()))];
+        func.call(&args)?;
+    }
+
+    // Still held alive by the `VMExternRefActivationsTable` (potentially in
+    // multiple slots within the table) and by this `r` local.
+    assert!(r.strong_count() >= 2);
+
+    // Doing a GC should see that there aren't any `externref`s on the stack in
+    // Wasm frames anymore.
+    store.gc();
+    assert_eq!(r.strong_count(), 1);
+
+    // Dropping `r` should drop the inner `SetFlagOnDrop` value.
+    drop(r);
+    assert!(inner_dropped.get());
+
+    return Ok(());
+
+    struct SetFlagOnDrop(Rc<Cell<bool>>);
+
+    impl Drop for SetFlagOnDrop {
+        fn drop(&mut self) {
+            self.0.set(true);
+        }
+    }
+}
+
+#[test]
+fn wasm_dropping_refs() -> anyhow::Result<()> {
+    let (store, module) = ref_types_module(
+        r#"
+            (module
+                (func (export "drop_ref") (param externref)
+                    nop
+                )
+            )
+        "#,
+    )?;
+
+    let instance = Instance::new(&store, &module, &[])?;
+    let drop_ref = instance.get_func("drop_ref").unwrap();
+
+    let num_refs_dropped = Rc::new(Cell::new(0));
+
+    // NB: 4096 is greater than the initial `VMExternRefActivationsTable`
+    // capacity, so this will trigger at least one GC.
+    for _ in 0..4096 {
+        let r = ExternRef::new(&store, CountDrops(num_refs_dropped.clone()));
+        let args = [Val::ExternRef(Some(r))];
+        drop_ref.call(&args)?;
+    }
+
+    assert!(num_refs_dropped.get() > 0);
+
+    // And after doing a final GC, all the refs should have been dropped.
+    store.gc();
+    assert_eq!(num_refs_dropped.get(), 4096);
+
+    return Ok(());
+
+    struct CountDrops(Rc<Cell<usize>>);
+
+    impl Drop for CountDrops {
+        fn drop(&mut self) {
+            self.0.set(self.0.get() + 1);
+        }
+    }
+}
+
+#[test]
+fn many_live_refs() -> anyhow::Result<()> {
+    let mut wat = r#"
+        (module
+            ;; Make new `externref`s.
+            (import "" "make_ref" (func $make_ref (result externref)))
+
+            ;; Observe an `externref` so it is kept live.
+            (import "" "observe_ref" (func $observe_ref (param externref)))
+
+            (func (export "many_live_refs")
+    "#
+    .to_string();
+
+    // This is more than the initial `VMExternRefActivationsTable` capacity, so
+    // it will need to allocate additional bump chunks.
+    const NUM_LIVE_REFS: usize = 1024;
+
+    // Push `externref`s onto the stack.
+    for _ in 0..NUM_LIVE_REFS {
+        wat.push_str("(call $make_ref)\n");
+    }
+
+    // Pop `externref`s from the stack. Because we pass each of them to a
+    // function call here, they are all live references for the duration of
+    // their lifetimes.
+    for _ in 0..NUM_LIVE_REFS {
+        wat.push_str("(call $observe_ref)\n");
+    }
+
+    wat.push_str(
+        "
+            ) ;; func
+        ) ;; module
+        ",
+    );
+
+    let (store, module) = ref_types_module(&wat)?;
+
+    let live_refs = Rc::new(Cell::new(0));
+
+    let make_ref = Func::new(
+        &store,
+        FuncType::new(
+            vec![].into_boxed_slice(),
+            vec![ValType::ExternRef].into_boxed_slice(),
+        ),
+        {
+            let store = store.clone();
+            let live_refs = live_refs.clone();
+            move |_caller, _params, results| {
+                results[0] = Val::ExternRef(Some(ExternRef::new(
+                    &store,
+                    CountLiveRefs::new(live_refs.clone()),
+                )));
+                Ok(())
+            }
+        },
+    );
+
+    let observe_ref = Func::new(
+        &store,
+        FuncType::new(
+            vec![ValType::ExternRef].into_boxed_slice(),
+            vec![].into_boxed_slice(),
+        ),
+        |_caller, params, _results| {
+            let r = params[0].externref().unwrap().unwrap();
+            let r = r.data().downcast_ref::<CountLiveRefs>().unwrap();
+            assert!(r.live_refs.get() > 0);
+            Ok(())
+        },
+    );
+
+    let instance = Instance::new(&store, &module, &[make_ref.into(), observe_ref.into()])?;
+    let many_live_refs = instance.get_func("many_live_refs").unwrap();
+
+    many_live_refs.call(&[])?;
+
+    store.gc();
+    assert_eq!(live_refs.get(), 0);
+
+    return Ok(());
+
+    struct CountLiveRefs {
+        live_refs: Rc<Cell<usize>>,
+    }
+
+    impl CountLiveRefs {
+        fn new(live_refs: Rc<Cell<usize>>) -> Self {
+            let live = live_refs.get();
+            live_refs.set(live + 1);
+            Self { live_refs }
+        }
+    }
+
+    impl Drop for CountLiveRefs {
+        fn drop(&mut self) {
+            let live = self.live_refs.get();
+            self.live_refs.set(live - 1);
+        }
+    }
+}
diff --git a/tests/all/main.rs b/tests/all/main.rs
index e7409c21d..e278d0750 100644
--- a/tests/all/main.rs
+++ b/tests/all/main.rs
@@ -18,3 +18,7 @@ mod table;
 mod traps;
 mod use_after_drop;
 mod wast;
+
+// TODO(#1886): Cranelift only supports reference types on x64.
+#[cfg(target_arch = "x86_64")]
+mod gc;