Repository: bytecodealliance/wasmtime
Pull request #2611 (2021-01-27 22:32:56)

Implement limiting WebAssembly execution with fuel
This PR lifts a feature from Lucet to wasmtime where generated code can count instructions or account for "fuel" during execution. The purpose of this feature is similar to the interrupt support via `InterruptHandle`, but it mainly allows deterministically interrupting a wasm module instead of relying on a timer. Additionally a future goal of this PR is to extend the `async` support of wasmtime to leverage fuel to periodically "interrupt" executing wasm code to yield back to the host. This would enable wasmtime futures to never take "too long" in `Future::poll` since if they would otherwise take awhile they'd yield back to the host and allow preemption and/or other things like future timeouts.

Thee implementation here is nearly copied verbatim from Lucet itself, with tweaks as appropriate for the different vmctx representation in Wasmtime. The main difference is that Wasmtime's fuel counter is two levels of indirection away from the vmctx rather than one in Lucet. To help with this a new `Variable` stores the `VMInterrupts` pointer value to avoid reloading the same value each time from the vmctx.

Support for this feature is exposed through a few new APIs:

* `Config::consume_fuel` - enables codegen options for wasm to consume fuel, and behaves similar to `interruptable`.
* `Store::set_fuel_remaining` - this is how fuel is injected into a `Store` for execution of wasm. Note that stores always start with 0 fuel so this is required to be called.
* `Store::fuel_consumed` - this can be used to check how much fuel has been consumed so far.

The current behavior, which cannot be changed, is that when fuel runs out a wasm trap is generated. I hope to make this configurable in the future so that for async stores when fuel runs out it's automatically re-injected with fuel but only after a yield back to the host happens.

I've done a bit of benchmarking with this using criterion and the benchmarks here -- https://github.com/bytecodealliance/sightglass/tree/main/benchmarks-next. The benchmarks are relatively limited at this time but were able to produce some useful data in the meantime. This shows to be a 35-45% slowdown on my personal laptop for the runtime execution of the benchmarked porttion of the code for blake3-scalar and shootout-ackermann. At least for ackermann this is somewhat expected because the loops/function calls are all tiny, so the overhead is quite noticeable. For blake3-scalar I assume it's similar but haven't dug in yet. Note that these numbers were with the new backend since the old x86 backend seems significantly worse than the x64 one.

I do think there might be some relatively low-hanging fruit with respect to performance, but further tweaks would require changes to cranelift itself to optimize instruction selection. For example one optimization might be to not have a `fuel_var` and instead periodically do `addq $fuel_consumed, offset(%vminterrupts_ptr)` which avoids consuming extra registers. Similarly `cmpq $0, offset(%vminterrupts_ptr)` could be generated as well. I couldn't get the x64 backend to emit those forms of instructions at this time though. I'm also not 100% certain that it'll be faster.

Note that for now this doesn't depend on the `async` PR, but I plan on having a future PR after these two land which implements the periodically-yield option.

cfallin: I'll take a look -- thanks for putting this together so quickly! A few quick notes on the isel thoughts:

> For example one optimization might be to not have a fuel_var and instead periodically do addq $fuel_consumed, offset(%vminterrupts_ptr) which avoids consuming extra registers. Similarly cmpq $0, offset(%vminterrupts_ptr) could be generated as well

The former is an RMW compound op and could be done pretty reasonably with the current load-op merging framework; we haven't gotten around to it yet, but it's clear how to do so if we decide it's important. The latter is actually a bit more interesting: I recently fixed a bug (#2576) that arose because of certain combinations of load-and-compare that would sink a load beyond its first use by simply disallowing compare-from-memory. That too can be re-optimized but would take more machinery.

Anyway, all that to say that there are reasons you couldn't get either of those instructions to come out the backend :-)
alexcrichton: Oh also to clarify, I don't think it's just isel that can be improved, but rather I think the frontend codegen could also be improved if we decide the time should be invested. For example an empty function `(func nop)` generates this x86 code with the new backend (annotated by me): 

```asm
0000000000000000 _wasm_function_4:
       ;; prologue stack-check to ensure we're not out of stack space
       ;; note that this is only here because function calls are made internally
       0: 55                           	pushq	%rbp
       1: 48 89 e5                     	movq	%rsp, %rbp
       4: 4c 8b 17                     	movq	(%rdi), %r10
       7: 4d 8b 12                     	movq	(%r10), %r10
       a: 49 39 e2                     	cmpq	%rsp, %r10
       d: 0f 86 02 00 00 00            	jbe	2 <_wasm_function_4+0x15>
      13: 0f 0b                        	ud2

      ;; allocating stack space, saving registers
      15: 48 83 ec 10                  	subq	$16, %rsp
      19: 4c 89 24 24                  	movq	%r12, (%rsp)

      ;; load vminterrupts_ptr into r12
      1d: 4c 8b 27                     	movq	(%rdi), %r12

      ;; increment the fuel consumed by 1 where 8(%r12) is where the previous count is
      20: be 01 00 00 00               	movl	$1, %esi
      25: 49 03 74 24 08               	addq	8(%r12), %rsi

      ;; check if fuel is gerater than zero
      2a: 48 31 c0                     	xorq	%rax, %rax
      2d: 48 39 c6                     	cmpq	%rax, %rsi
      30: 0f 8c 13 00 00 00            	jl	19 <_wasm_function_4+0x49>

      ;; save the fuel count, load the intrinsic address, call it
      36: 49 89 74 24 08               	movq	%rsi, 8(%r12)
      3b: 48 8b b7 f0 06 00 00         	movq	1776(%rdi), %rsi
      42: ff d6                        	callq	*%rsi

      ;; restore the fuel_var for this function (unnecessary instruction, happens uncondititonally after call)
      44: 49 8b 74 24 08               	movq	8(%r12), %rsi
    
      ;; save fuel_var at the end of the function (unnecessary instruction, happens unconditionally at function end)
      49: 49 89 74 24 08               	movq	%rsi, 8(%r12)

      ;; function epilogue
      4e: 4c 8b 24 24                  	movq	(%rsp), %r12
      52: 48 83 c4 10                  	addq	$16, %rsp
      56: 48 89 ec                     	movq	%rbp, %rsp
      59: 5d                           	popq	%rbp
      5a: c3                           	retq
```

Larger functions like https://github.com/bytecodealliance/sightglass/blob/faf101e50f7af6243fe3e910cf9455eecd9e1368/benchmarks-next/shootout-ackermann/benchmark.wat#L25-L49 end up having a lot more code generated with instrumentation enabled. I haven't yet gone through instruction-by-instruction yet, though, to see what could be improved.
github-actions[bot]: #### Subscribe to Label Action

cc @fitzgen, @peterhuene

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

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

* fitzgen: fuzzing
* peterhuene: wasmtime:api

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

[Learn more.](https://github.com/bytecodealliance/subscribe-to-label-action)
</details>
alexcrichton: Ok this should be rebased and updated to have `add_fuel` 

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index ead0ab841..352bcee78 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -3138,6 +3138,7 @@ dependencies = [
  "wasmtime-wasi-crypto",
  "wasmtime-wasi-nn",
  "wasmtime-wast",
+ "wast 32.0.0",
  "wat",
 ]
 
@@ -3149,6 +3150,7 @@ dependencies = [
  "cranelift-entity",
  "cranelift-frontend",
  "cranelift-wasm",
+ "wasmparser",
  "wasmtime-environ",
 ]
 
diff --git a/Cargo.toml b/Cargo.toml
index c1d0cc8ed..00cd71f52 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -55,6 +55,7 @@ test-programs = { path = "crates/test-programs" }
 wasmtime-fuzzing = { path = "crates/fuzzing" }
 wasmtime-runtime = { path = "crates/runtime" }
 tracing-subscriber = "0.2.0"
+wast = "32.0.0"
 
 [build-dependencies]
 anyhow = "1.0.19"
diff --git a/cranelift/codegen/src/isa/x64/inst/emit.rs b/cranelift/codegen/src/isa/x64/inst/emit.rs
index 095256ab4..0a029301a 100644
--- a/cranelift/codegen/src/isa/x64/inst/emit.rs
+++ b/cranelift/codegen/src/isa/x64/inst/emit.rs
@@ -2094,7 +2094,9 @@ pub(crate) fn emit(
                 SseOpcode::Pextrd => (LegacyPrefixes::_66, 0x0F3A16, 3),
                 SseOpcode::Pshufd => (LegacyPrefixes::_66, 0x0F70, 2),
                 SseOpcode::Roundps => (LegacyPrefixes::_66, 0x0F3A08, 3),
+                SseOpcode::Roundss => (LegacyPrefixes::_66, 0x0F3A0A, 3),
                 SseOpcode::Roundpd => (LegacyPrefixes::_66, 0x0F3A09, 3),
+                SseOpcode::Roundsd => (LegacyPrefixes::_66, 0x0F3A0B, 3),
                 _ => unimplemented!("Opcode {:?} not implemented", op),
             };
             let rex = if *is64 {
diff --git a/cranelift/codegen/src/isa/x64/inst/mod.rs b/cranelift/codegen/src/isa/x64/inst/mod.rs
index bab28f2aa..76bde8e13 100644
--- a/cranelift/codegen/src/isa/x64/inst/mod.rs
+++ b/cranelift/codegen/src/isa/x64/inst/mod.rs
@@ -566,7 +566,7 @@ impl Inst {
 
 impl Inst {
     pub(crate) fn nop(len: u8) -> Self {
-        debug_assert!(len <= 16);
+        debug_assert!(len <= 15);
         Self::Nop { len }
     }
 
@@ -1823,7 +1823,7 @@ impl fmt::Debug for Inst {
 fn x64_get_regs(inst: &Inst, collector: &mut RegUsageCollector) {
     // This is a bit subtle. If some register is in the modified set, then it may not be in either
     // the use or def sets. However, enforcing that directly is somewhat difficult. Instead,
-    // regalloc.rs will "fix" this for us by removing the the modified set from the use and def
+    // regalloc.rs will "fix" this for us by removing the modified set from the use and def
     // sets.
     match inst {
         Inst::AluRmiR { src, dst, .. } => {
@@ -1895,6 +1895,10 @@ fn x64_get_regs(inst: &Inst, collector: &mut RegUsageCollector) {
                 || *op == SseOpcode::Pextrw
                 || *op == SseOpcode::Pextrd
                 || *op == SseOpcode::Pshufd
+                || *op == SseOpcode::Roundss
+                || *op == SseOpcode::Roundsd
+                || *op == SseOpcode::Roundps
+                || *op == SseOpcode::Roundpd
             {
                 src.get_regs_as_uses(collector);
                 collector.add_def(*dst);
@@ -2236,6 +2240,10 @@ fn x64_map_regs<RUM: RegUsageMapper>(inst: &mut Inst, mapper: &RUM) {
                 || *op == SseOpcode::Pextrw
                 || *op == SseOpcode::Pextrd
                 || *op == SseOpcode::Pshufd
+                || *op == SseOpcode::Roundss
+                || *op == SseOpcode::Roundsd
+                || *op == SseOpcode::Roundps
+                || *op == SseOpcode::Roundpd
             {
                 src.map_uses(mapper);
                 map_def(mapper, dst);
@@ -2594,11 +2602,11 @@ impl MachInst for Inst {
     }
 
     fn gen_zero_len_nop() -> Inst {
-        Inst::Nop { len: 0 }
+        Inst::nop(0)
     }
 
     fn gen_nop(preferred_size: usize) -> Inst {
-        Inst::nop((preferred_size % 16) as u8)
+        Inst::nop(std::cmp::min(preferred_size, 15) as u8)
     }
 
     fn maybe_direct_reload(&self, _reg: VirtualReg, _slot: SpillSlot) -> Option<Inst> {
diff --git a/cranelift/codegen/src/isa/x64/lower.rs b/cranelift/codegen/src/isa/x64/lower.rs
index 45014fca1..6c002dd6c 100644
--- a/cranelift/codegen/src/isa/x64/lower.rs
+++ b/cranelift/codegen/src/isa/x64/lower.rs
@@ -8,7 +8,7 @@ use crate::ir::{
 use crate::isa::x64::abi::*;
 use crate::isa::x64::inst::args::*;
 use crate::isa::x64::inst::*;
-use crate::isa::{x64::X64Backend, CallConv};
+use crate::isa::{x64::settings as x64_settings, x64::X64Backend, CallConv};
 use crate::machinst::lower::*;
 use crate::machinst::*;
 use crate::result::CodegenResult;
@@ -1330,6 +1330,7 @@ fn lower_insn_to_regs<C: LowerCtx<I = Inst>>(
     ctx: &mut C,
     insn: IRInst,
     flags: &Flags,
+    isa_flags: &x64_settings::Flags,
     triple: &Triple,
 ) -> CodegenResult<()> {
     let op = ctx.data(insn).opcode();
@@ -4211,11 +4212,29 @@ fn lower_insn_to_regs<C: LowerCtx<I = Inst>>(
         }
 
         Opcode::Ceil | Opcode::Floor | Opcode::Nearest | Opcode::Trunc => {
-            // TODO use ROUNDSS/ROUNDSD after sse4.1.
-
-            // Lower to VM calls when there's no access to SSE4.1.
             let ty = ty.unwrap();
-            if !ty.is_vector() {
+            if isa_flags.use_sse41() {
+                let mode = match op {
+                    Opcode::Ceil => RoundImm::RoundUp,
+                    Opcode::Floor => RoundImm::RoundDown,
+                    Opcode::Nearest => RoundImm::RoundNearest,
+                    Opcode::Trunc => RoundImm::RoundZero,
+                    _ => panic!("unexpected opcode {:?} in Ceil/Floor/Nearest/Trunc", op),
+                };
+                let op = match ty {
+                    types::F32 => SseOpcode::Roundss,
+                    types::F64 => SseOpcode::Roundsd,
+                    types::F32X4 => SseOpcode::Roundps,
+                    types::F64X2 => SseOpcode::Roundpd,
+                    _ => panic!("unexpected type {:?} in Ceil/Floor/Nearest/Trunc", ty),
+                };
+                let src = input_to_reg_mem(ctx, inputs[0]);
+                let dst = get_output_reg(ctx, outputs[0]).only_reg().unwrap();
+                ctx.emit(Inst::xmm_rm_r_imm(op, src, dst, mode.encode(), false));
+            } else {
+                // Lower to VM calls when there's no access to SSE4.1.
+                // Note, for vector types on platforms that don't support sse41
+                // the execution will panic here.
                 let libcall = match (op, ty) {
                     (Opcode::Ceil, types::F32) => LibCall::CeilF32,
                     (Opcode::Ceil, types::F64) => LibCall::CeilF64,
@@ -4231,28 +4250,6 @@ fn lower_insn_to_regs<C: LowerCtx<I = Inst>>(
                     ),
                 };
                 emit_vm_call(ctx, flags, triple, libcall, insn, inputs, outputs)?;
-            } else {
-                let (op, mode) = match (op, ty) {
-                    (Opcode::Ceil, types::F32X4) => (SseOpcode::Roundps, RoundImm::RoundUp),
-                    (Opcode::Ceil, types::F64X2) => (SseOpcode::Roundpd, RoundImm::RoundUp),
-                    (Opcode::Floor, types::F32X4) => (SseOpcode::Roundps, RoundImm::RoundDown),
-                    (Opcode::Floor, types::F64X2) => (SseOpcode::Roundpd, RoundImm::RoundDown),
-                    (Opcode::Trunc, types::F32X4) => (SseOpcode::Roundps, RoundImm::RoundZero),
-                    (Opcode::Trunc, types::F64X2) => (SseOpcode::Roundpd, RoundImm::RoundZero),
-                    (Opcode::Nearest, types::F32X4) => (SseOpcode::Roundps, RoundImm::RoundNearest),
-                    (Opcode::Nearest, types::F64X2) => (SseOpcode::Roundpd, RoundImm::RoundNearest),
-                    _ => panic!("Unknown op/ty combination (vector){:?}", ty),
-                };
-                let src = put_input_in_reg(ctx, inputs[0]);
-                let dst = get_output_reg(ctx, outputs[0]).only_reg().unwrap();
-                ctx.emit(Inst::gen_move(dst, src, ty));
-                ctx.emit(Inst::xmm_rm_r_imm(
-                    op,
-                    RegMem::from(dst),
-                    dst,
-                    mode.encode(),
-                    false,
-                ));
             }
         }
 
@@ -5389,7 +5386,7 @@ impl LowerBackend for X64Backend {
     type MInst = Inst;
 
     fn lower<C: LowerCtx<I = Inst>>(&self, ctx: &mut C, ir_inst: IRInst) -> CodegenResult<()> {
-        lower_insn_to_regs(ctx, ir_inst, &self.flags, &self.triple)
+        lower_insn_to_regs(ctx, ir_inst, &self.flags, &self.x64_flags, &self.triple)
     }
 
     fn lower_branch_group<C: LowerCtx<I = Inst>>(
diff --git a/cranelift/codegen/src/machinst/mod.rs b/cranelift/codegen/src/machinst/mod.rs
index 297d53195..d65fd9b3c 100644
--- a/cranelift/codegen/src/machinst/mod.rs
+++ b/cranelift/codegen/src/machinst/mod.rs
@@ -178,7 +178,7 @@ pub trait MachInst: Clone + Debug {
     /// request a NOP of that size, or as close to it as possible. The machine
     /// backend may return a NOP whose binary encoding is smaller than the
     /// preferred size, but must not return a NOP that is larger. However,
-    /// the instruction must have a nonzero size.
+    /// the instruction must have a nonzero size if preferred_size is nonzero.
     fn gen_nop(preferred_size: usize) -> Self;
 
     /// Get the register universe for this backend.
diff --git a/cranelift/entity/src/list.rs b/cranelift/entity/src/list.rs
index 68cab8166..dfb8fac64 100644
--- a/cranelift/entity/src/list.rs
+++ b/cranelift/entity/src/list.rs
@@ -91,17 +91,20 @@ type SizeClass = u8;
 
 /// Get the size of a given size class. The size includes the length field, so the maximum list
 /// length is one less than the class size.
+#[inline]
 fn sclass_size(sclass: SizeClass) -> usize {
     4 << sclass
 }
 
 /// Get the size class to use for a given list length.
 /// This always leaves room for the length element in addition to the list elements.
+#[inline]
 fn sclass_for_length(len: usize) -> SizeClass {
     30 - (len as u32 | 3).leading_zeros() as SizeClass
 }
 
 /// Is `len` the minimum length in its size class?
+#[inline]
 fn is_sclass_min_length(len: usize) -> bool {
     len > 3 && len.is_power_of_two()
 }
@@ -387,14 +390,34 @@ impl<T: EntityRef + ReservedValue> EntityList<T> {
         &mut pool.data[block + 1..block + 1 + new_len]
     }
 
+    /// Constructs a list from an iterator.
+    pub fn from_iter<I>(elements: I, pool: &mut ListPool<T>) -> Self
+    where
+        I: IntoIterator<Item = T>,
+    {
+        let mut list = Self::new();
+        list.extend(elements, pool);
+        list
+    }
+
     /// Appends multiple elements to the back of the list.
     pub fn extend<I>(&mut self, elements: I, pool: &mut ListPool<T>)
     where
         I: IntoIterator<Item = T>,
     {
-        // TODO: use `size_hint()` to reduce reallocations.
-        for x in elements {
-            self.push(x, pool);
+        let iterator = elements.into_iter();
+        let (len, upper) = iterator.size_hint();
+        // On most iterators this check is optimized down to `true`.
+        if upper == Some(len) {
+            let data = self.grow(len, pool);
+            let offset = data.len() - len;
+            for (src, dst) in iterator.zip(data[offset..].iter_mut()) {
+                *dst = src;
+            }
+        } else {
+            for x in iterator {
+                self.push(x, pool);
+            }
         }
     }
 
@@ -630,6 +653,10 @@ mod tests {
             list.as_slice(pool),
             &[i1, i2, i3, i4, i1, i1, i2, i2, i3, i3, i4, i4]
         );
+
+        let list2 = EntityList::from_iter([i1, i1, i2, i2, i3, i3, i4, i4].iter().cloned(), pool);
+        assert_eq!(list2.len(pool), 8);
+        assert_eq!(list2.as_slice(pool), &[i1, i1, i2, i2, i3, i3, i4, i4]);
     }
 
     #[test]
diff --git a/cranelift/src/souper_harvest.rs b/cranelift/src/souper_harvest.rs
index 5bfa1fe62..e92a50230 100644
--- a/cranelift/src/souper_harvest.rs
+++ b/cranelift/src/souper_harvest.rs
@@ -12,7 +12,7 @@ static WASM_MAGIC: &[u8] = &[0x00, 0x61, 0x73, 0x6D];
 /// Harvest candidates for superoptimization from a Wasm or Clif file.
 ///
 /// Candidates are emitted in Souper's text format:
-/// https://github.com/google/souper
+/// <https://github.com/google/souper>
 #[derive(StructOpt)]
 pub struct Options {
     /// Specify an input file to be used. Use '-' for stdin.
diff --git a/cranelift/wasm/src/code_translator.rs b/cranelift/wasm/src/code_translator.rs
index 266e002ae..a20975b25 100644
--- a/cranelift/wasm/src/code_translator.rs
+++ b/cranelift/wasm/src/code_translator.rs
@@ -261,7 +261,7 @@ pub fn translate_operator<FE: FuncEnvironment + ?Sized>(
                 .extend_from_slice(builder.block_params(loop_body));
 
             builder.switch_to_block(loop_body);
-            environ.translate_loop_header(builder.cursor())?;
+            environ.translate_loop_header(builder)?;
         }
         Operator::If { ty } => {
             let val = state.pop1();
diff --git a/cranelift/wasm/src/environ/spec.rs b/cranelift/wasm/src/environ/spec.rs
index 84978dc0d..0bd3c4874 100644
--- a/cranelift/wasm/src/environ/spec.rs
+++ b/cranelift/wasm/src/environ/spec.rs
@@ -295,6 +295,12 @@ pub trait FuncEnvironment: TargetEnvironment {
         ReturnMode::NormalReturns
     }
 
+    /// Called after the locals for a function have been parsed, and the number
+    /// of variables defined by this function is provided.
+    fn after_locals(&mut self, num_locals_defined: usize) {
+        drop(num_locals_defined);
+    }
+
     /// Set up the necessary preamble definitions in `func` to access the global variable
     /// identified by `index`.
     ///
@@ -637,7 +643,7 @@ pub trait FuncEnvironment: TargetEnvironment {
     ///
     /// This can be used to insert explicit interrupt or safepoint checking at
     /// the beginnings of loops.
-    fn translate_loop_header(&mut self, _pos: FuncCursor) -> WasmResult<()> {
+    fn translate_loop_header(&mut self, _builder: &mut FunctionBuilder) -> WasmResult<()> {
         // By default, don't emit anything.
         Ok(())
     }
diff --git a/cranelift/wasm/src/func_translator.rs b/cranelift/wasm/src/func_translator.rs
index 7a8f9c19d..97e5354c6 100644
--- a/cranelift/wasm/src/func_translator.rs
+++ b/cranelift/wasm/src/func_translator.rs
@@ -170,6 +170,8 @@ fn parse_local_decls<FE: FuncEnvironment + ?Sized>(
         declare_locals(builder, count, ty, &mut next_local, environ)?;
     }
 
+    environ.after_locals(next_local);
+
     Ok(())
 }
 
diff --git a/crates/cranelift/Cargo.toml b/crates/cranelift/Cargo.toml
index 99ccc5a49..9b4e0972b 100644
--- a/crates/cranelift/Cargo.toml
+++ b/crates/cranelift/Cargo.toml
@@ -17,3 +17,4 @@ cranelift-wasm = { path = "../../cranelift/wasm", version = "0.69.0" }
 cranelift-codegen = { path = "../../cranelift/codegen", version = "0.69.0" }
 cranelift-frontend = { path = "../../cranelift/frontend", version = "0.69.0" }
 cranelift-entity = { path = "../../cranelift/entity", version = "0.69.0" }
+wasmparser = "0.73.0"
diff --git a/crates/cranelift/src/func_environ.rs b/crates/cranelift/src/func_environ.rs
index 6b94824f9..a9481aca9 100644
--- a/crates/cranelift/src/func_environ.rs
+++ b/crates/cranelift/src/func_environ.rs
@@ -7,11 +7,14 @@ use cranelift_codegen::ir::{AbiParam, ArgumentPurpose, Function, InstBuilder, Si
 use cranelift_codegen::isa::{self, TargetFrontendConfig};
 use cranelift_entity::{EntityRef, PrimaryMap};
 use cranelift_frontend::FunctionBuilder;
+use cranelift_frontend::Variable;
 use cranelift_wasm::{
-    self, FuncIndex, GlobalIndex, GlobalVariable, MemoryIndex, SignatureIndex, TableIndex,
-    TargetEnvironment, TypeIndex, WasmError, WasmResult, WasmType,
+    self, FuncIndex, FuncTranslationState, GlobalIndex, GlobalVariable, MemoryIndex,
+    SignatureIndex, TableIndex, TargetEnvironment, TypeIndex, WasmError, WasmResult, WasmType,
 };
 use std::convert::TryFrom;
+use std::mem;
+use wasmparser::Operator;
 use wasmtime_environ::{
     BuiltinFunctionIndex, MemoryPlan, MemoryStyle, Module, TableStyle, Tunables, VMOffsets,
     INTERRUPTED, WASM_PAGE_SIZE,
@@ -125,6 +128,20 @@ pub struct FuncEnvironment<'module_environment> {
     pub(crate) offsets: VMOffsets,
 
     tunables: &'module_environment Tunables,
+
+    /// A function-local variable which stores the cached value of the amount of
+    /// fuel remaining to execute. If used this is modified frequently so it's
+    /// stored locally as a variable instead of always referenced from the field
+    /// in `*const VMInterrupts`
+    fuel_var: cranelift_frontend::Variable,
+
+    /// A function-local variable which caches the value of `*const
+    /// VMInterrupts` for this function's vmctx argument. This pointer is stored
+    /// in the vmctx itself, but never changes for the lifetime of the function,
+    /// so if we load it up front we can continue to use it throughout.
+    vminterrupts_ptr: cranelift_frontend::Variable,
+
+    fuel_consumed: i64,
 }
 
 impl<'module_environment> FuncEnvironment<'module_environment> {
@@ -151,6 +168,12 @@ impl<'module_environment> FuncEnvironment<'module_environment> {
             builtin_function_signatures,
             offsets: VMOffsets::new(target_config.pointer_bytes(), module),
             tunables,
+            fuel_var: Variable::new(0),
+            vminterrupts_ptr: Variable::new(0),
+
+            // Start with at least one fuel being consumed because even empty
+            // functions should consume at least some fuel.
+            fuel_consumed: 1,
         }
     }
 
@@ -418,6 +441,241 @@ impl<'module_environment> FuncEnvironment<'module_environment> {
             (global, 0)
         }
     }
+
+    fn declare_vminterrupts_ptr(&mut self, builder: &mut FunctionBuilder<'_>) {
+        // We load the `*const VMInterrupts` value stored within vmctx at the
+        // head of the function and reuse the same value across the entire
+        // function. This is possible since we know that the pointer never
+        // changes for the lifetime of the function.
+        let pointer_type = self.pointer_type();
+        builder.declare_var(self.vminterrupts_ptr, pointer_type);
+        let vmctx = self.vmctx(builder.func);
+        let base = builder.ins().global_value(pointer_type, vmctx);
+        let offset = i32::try_from(self.offsets.vmctx_interrupts()).unwrap();
+        let interrupt_ptr = builder
+            .ins()
+            .load(pointer_type, ir::MemFlags::trusted(), base, offset);
+        builder.def_var(self.vminterrupts_ptr, interrupt_ptr);
+    }
+
+    fn fuel_function_entry(&mut self, builder: &mut FunctionBuilder<'_>) {
+        // On function entry we load the amount of fuel into a function-local
+        // `self.fuel_var` to make fuel modifications fast locally. This cache
+        // is then periodically flushed to the Store-defined location in
+        // `VMInterrupts` later.
+        builder.declare_var(self.fuel_var, ir::types::I64);
+        self.fuel_load_into_var(builder);
+        self.fuel_check(builder);
+    }
+
+    fn fuel_function_exit(&mut self, builder: &mut FunctionBuilder<'_>) {
+        // On exiting the function we need to be sure to save the fuel we have
+        // cached locally in `self.fuel_var` back into the Store-defined
+        // location.
+        self.fuel_save_from_var(builder);
+    }
+
+    fn fuel_before_op(
+        &mut self,
+        op: &Operator<'_>,
+        builder: &mut FunctionBuilder<'_>,
+        reachable: bool,
+    ) {
+        if !reachable {
+            // In unreachable code we shouldn't have any leftover fuel we
+            // haven't accounted for since the reason for us to become
+            // unreachable should have already added it to `self.fuel_var`.
+            debug_assert_eq!(self.fuel_consumed, 0);
+            return;
+        }
+
+        self.fuel_consumed += match op {
+            // Nop and drop generate no code, so don't consume fuel for them.
+            Operator::Nop | Operator::Drop => 0,
+
+            // Control flow may create branches, but is generally cheap and
+            // free, so don't consume fuel. Note the lack of `if` since some
+            // cost is incurred with the conditional check.
+            Operator::Block { .. }
+            | Operator::Loop { .. }
+            | Operator::Unreachable
+            | Operator::Return
+            | Operator::Else
+            | Operator::End => 0,
+
+            // everything else, just call it one operation.
+            _ => 1,
+        };
+
+        match op {
+            // Exiting a function (via a return or unreachable) or otherwise
+            // entering a different function (via a call) means that we need to
+            // update the fuel consumption in `VMInterrupts` because we're
+            // about to move control out of this function itself and the fuel
+            // may need to be read.
+            //
+            // Before this we need to update the fuel counter from our own cost
+            // leading up to this function call, and then we can store
+            // `self.fuel_var` into `VMInterrupts`.
+            Operator::Unreachable
+            | Operator::Return
+            | Operator::CallIndirect { .. }
+            | Operator::Call { .. }
+            | Operator::ReturnCall { .. }
+            | Operator::ReturnCallIndirect { .. } => {
+                self.fuel_increment_var(builder);
+                self.fuel_save_from_var(builder);
+            }
+
+            // To ensure all code preceding a loop is only counted once we
+            // update the fuel variable on entry.
+            Operator::Loop { .. }
+
+            // Entering into an `if` block means that the edge we take isn't
+            // known until runtime, so we need to update our fuel consumption
+            // before we take the branch.
+            | Operator::If { .. }
+
+            // Control-flow instructions mean that we're moving to the end/exit
+            // of a block somewhere else. That means we need to update the fuel
+            // counter since we're effectively terminating our basic block.
+            | Operator::Br { .. }
+            | Operator::BrIf { .. }
+            | Operator::BrTable { .. }
+
+            // Exiting a scope means that we need to update the fuel
+            // consumption because there are multiple ways to exit a scope and
+            // this is the only time we have to account for instructions
+            // executed so far.
+            | Operator::End
+
+            // This is similar to `end`, except that it's only the terminator
+            // for an `if` block. The same reasoning applies though in that we
+            // are terminating a basic block and need to update the fuel
+            // variable.
+            | Operator::Else => self.fuel_increment_var(builder),
+
+            // This is a normal instruction where the fuel is buffered to later
+            // get added to `self.fuel_var`.
+            //
+            // Note that we generally ignore instructions which may trap and
+            // therefore result in exiting a block early. Current usage of fuel
+            // means that it's not too important to account for a precise amount
+            // of fuel consumed but rather "close to the actual amount" is good
+            // enough. For 100% precise counting, however, we'd probably need to
+            // not only increment but also save the fuel amount more often
+            // around trapping instructions. (see the `unreachable` instruction
+            // case above)
+            //
+            // Note that `Block` is specifically omitted from incrementing the
+            // fuel variable. Control flow entering a `block` is unconditional
+            // which means it's effectively executing straight-line code. We'll
+            // update the counter when exiting a block, but we shouldn't need to
+            // do so upon entering a block.
+            _ => {}
+        }
+    }
+
+    fn fuel_after_op(&mut self, op: &Operator<'_>, builder: &mut FunctionBuilder<'_>) {
+        // After a function call we need to reload our fuel value since the
+        // function may have changed it.
+        match op {
+            Operator::Call { .. } | Operator::CallIndirect { .. } => {
+                self.fuel_load_into_var(builder);
+            }
+            _ => {}
+        }
+    }
+
+    /// Adds `self.fuel_consumed` to the `fuel_var`, zero-ing out the amount of
+    /// fuel consumed at that point.
+    fn fuel_increment_var(&mut self, builder: &mut FunctionBuilder<'_>) {
+        let consumption = mem::replace(&mut self.fuel_consumed, 0);
+        if consumption == 0 {
+            return;
+        }
+
+        let fuel = builder.use_var(self.fuel_var);
+        let fuel = builder.ins().iadd_imm(fuel, consumption);
+        builder.def_var(self.fuel_var, fuel);
+    }
+
+    /// Loads the fuel consumption value from `VMInterrupts` into `self.fuel_var`
+    fn fuel_load_into_var(&mut self, builder: &mut FunctionBuilder<'_>) {
+        let (addr, offset) = self.fuel_addr_offset(builder);
+        let fuel = builder
+            .ins()
+            .load(ir::types::I64, ir::MemFlags::trusted(), addr, offset);
+        builder.def_var(self.fuel_var, fuel);
+    }
+
+    /// Stores the fuel consumption value from `self.fuel_var` into
+    /// `VMInterrupts`.
+    fn fuel_save_from_var(&mut self, builder: &mut FunctionBuilder<'_>) {
+        let (addr, offset) = self.fuel_addr_offset(builder);
+        let fuel_consumed = builder.use_var(self.fuel_var);
+        builder
+            .ins()
+            .store(ir::MemFlags::trusted(), fuel_consumed, addr, offset);
+    }
+
+    /// Returns the `(address, offset)` of the fuel consumption within
+    /// `VMInterrupts`, used to perform loads/stores later.
+    fn fuel_addr_offset(
+        &mut self,
+        builder: &mut FunctionBuilder<'_>,
+    ) -> (ir::Value, ir::immediates::Offset32) {
+        (
+            builder.use_var(self.vminterrupts_ptr),
+            i32::from(self.offsets.vminterrupts_fuel_consumed()).into(),
+        )
+    }
+
+    /// Checks the amount of remaining, and if we've run out of fuel we call
+    /// the out-of-fuel function.
+    fn fuel_check(&mut self, builder: &mut FunctionBuilder) {
+        self.fuel_increment_var(builder);
+        let out_of_gas_block = builder.create_block();
+        let continuation_block = builder.create_block();
+
+        // Note that our fuel is encoded as adding positive values to a
+        // negative number. Whenever the negative number goes positive that
+        // means we ran out of fuel.
+        //
+        // Compare to see if our fuel is positive, and if so we ran out of gas.
+        // Otherwise we can continue on like usual.
+        let zero = builder.ins().iconst(ir::types::I64, 0);
+        let fuel = builder.use_var(self.fuel_var);
+        let cmp = builder.ins().ifcmp(fuel, zero);
+        builder
+            .ins()
+            .brif(IntCC::SignedGreaterThanOrEqual, cmp, out_of_gas_block, &[]);
+        builder.ins().jump(continuation_block, &[]);
+        builder.seal_block(out_of_gas_block);
+
+        // If we ran out of gas then we call our out-of-gas intrinsic and it
+        // figures out what to do. Note that this may raise a trap, or do
+        // something like yield to an async runtime. In either case we don't
+        // assume what happens and handle the case the intrinsic returns.
+        //
+        // Note that we save/reload fuel around this since the out-of-gas
+        // intrinsic may alter how much fuel is in the system.
+        builder.switch_to_block(out_of_gas_block);
+        self.fuel_save_from_var(builder);
+        let out_of_gas_sig = self.builtin_function_signatures.out_of_gas(builder.func);
+        let (vmctx, out_of_gas) = self.translate_load_builtin_function_address(
+            &mut builder.cursor(),
+            BuiltinFunctionIndex::out_of_gas(),
+        );
+        builder
+            .ins()
+            .call_indirect(out_of_gas_sig, out_of_gas, &[vmctx]);
+        self.fuel_load_into_var(builder);
+        builder.ins().jump(continuation_block, &[]);
+        builder.seal_block(continuation_block);
+
+        builder.switch_to_block(continuation_block);
+    }
 }
 
 impl<'module_environment> TargetEnvironment for FuncEnvironment<'module_environment> {
@@ -437,6 +695,11 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         index >= 2
     }
 
+    fn after_locals(&mut self, num_locals: usize) {
+        self.vminterrupts_ptr = Variable::new(num_locals);
+        self.fuel_var = Variable::new(num_locals + 1);
+    }
+
     fn make_table(&mut self, func: &mut ir::Function, index: TableIndex) -> WasmResult<ir::Table> {
         let pointer_type = self.pointer_type();
 
@@ -1482,36 +1745,90 @@ impl<'module_environment> cranelift_wasm::FuncEnvironment for FuncEnvironment<'m
         Ok(*pos.func.dfg.inst_results(call_inst).first().unwrap())
     }
 
-    fn translate_loop_header(&mut self, mut pos: FuncCursor) -> WasmResult<()> {
-        if !self.tunables.interruptable {
-            return Ok(());
-        }
-
-        // Start out each loop with a check to the interupt flag to allow
-        // interruption of long or infinite loops.
+    fn translate_loop_header(&mut self, builder: &mut FunctionBuilder) -> WasmResult<()> {
+        // If enabled check the interrupt flag to prevent long or infinite
+        // loops.
         //
         // For more information about this see comments in
         // `crates/environ/src/cranelift.rs`
-        let vmctx = self.vmctx(&mut pos.func);
-        let pointer_type = self.pointer_type();
-        let base = pos.ins().global_value(pointer_type, vmctx);
-        let offset = i32::try_from(self.offsets.vmctx_interrupts()).unwrap();
-        let interrupt_ptr = pos
-            .ins()
-            .load(pointer_type, ir::MemFlags::trusted(), base, offset);
-        let interrupt = pos.ins().load(
-            pointer_type,
-            ir::MemFlags::trusted(),
-            interrupt_ptr,
-            i32::from(self.offsets.vminterrupts_stack_limit()),
-        );
-        // Note that the cast to `isize` happens first to allow sign-extension,
-        // if necessary, to `i64`.
-        let interrupted_sentinel = pos.ins().iconst(pointer_type, INTERRUPTED as isize as i64);
-        let cmp = pos
-            .ins()
-            .icmp(IntCC::Equal, interrupt, interrupted_sentinel);
-        pos.ins().trapnz(cmp, ir::TrapCode::Interrupt);
+        if self.tunables.interruptable {
+            let pointer_type = self.pointer_type();
+            let interrupt_ptr = builder.use_var(self.vminterrupts_ptr);
+            let interrupt = builder.ins().load(
+                pointer_type,
+                ir::MemFlags::trusted(),
+                interrupt_ptr,
+                i32::from(self.offsets.vminterrupts_stack_limit()),
+            );
+            // Note that the cast to `isize` happens first to allow sign-extension,
+            // if necessary, to `i64`.
+            let interrupted_sentinel = builder
+                .ins()
+                .iconst(pointer_type, INTERRUPTED as isize as i64);
+            let cmp = builder
+                .ins()
+                .icmp(IntCC::Equal, interrupt, interrupted_sentinel);
+            builder.ins().trapnz(cmp, ir::TrapCode::Interrupt);
+        }
+
+        // Additionally if enabled check how much fuel we have remaining to see
+        // if we've run out by this point.
+        if self.tunables.consume_fuel {
+            self.fuel_check(builder);
+        }
+
+        Ok(())
+    }
+
+    fn before_translate_operator(
+        &mut self,
+        op: &Operator,
+        builder: &mut FunctionBuilder,
+        state: &FuncTranslationState,
+    ) -> WasmResult<()> {
+        if self.tunables.consume_fuel {
+            self.fuel_before_op(op, builder, state.reachable());
+        }
+        Ok(())
+    }
+
+    fn after_translate_operator(
+        &mut self,
+        op: &Operator,
+        builder: &mut FunctionBuilder,
+        state: &FuncTranslationState,
+    ) -> WasmResult<()> {
+        if self.tunables.consume_fuel && state.reachable() {
+            self.fuel_after_op(op, builder);
+        }
+        Ok(())
+    }
+
+    fn before_translate_function(
+        &mut self,
+        builder: &mut FunctionBuilder,
+        _state: &FuncTranslationState,
+    ) -> WasmResult<()> {
+        // If the `vminterrupts_ptr` variable will get used then we initialize
+        // it here.
+        if self.tunables.consume_fuel || self.tunables.interruptable {
+            self.declare_vminterrupts_ptr(builder);
+        }
+        // Additionally we initialize `fuel_var` if it will get used.
+        if self.tunables.consume_fuel {
+            self.fuel_function_entry(builder);
+        }
+        Ok(())
+    }
+
+    fn after_translate_function(
+        &mut self,
+        builder: &mut FunctionBuilder,
+        state: &FuncTranslationState,
+    ) -> WasmResult<()> {
+        if self.tunables.consume_fuel && state.reachable() {
+            self.fuel_function_exit(builder);
+        }
         Ok(())
     }
 }
diff --git a/crates/environ/src/builtin.rs b/crates/environ/src/builtin.rs
index f2bb33021..1bbc06424 100644
--- a/crates/environ/src/builtin.rs
+++ b/crates/environ/src/builtin.rs
@@ -57,6 +57,8 @@ macro_rules! foreach_builtin_function {
             memory_atomic_wait64(vmctx, i32, i32, i64, i64) -> (i32);
             /// Returns an index for wasm's `memory.atomic.wait64` for imported memories.
             imported_memory_atomic_wait64(vmctx, i32, i32, i64, i64) -> (i32);
+            /// Invoked when fuel has run out while executing a function.
+            out_of_gas(vmctx) -> ();
         }
     };
 }
diff --git a/crates/environ/src/tunables.rs b/crates/environ/src/tunables.rs
index 939861504..bd86fef23 100644
--- a/crates/environ/src/tunables.rs
+++ b/crates/environ/src/tunables.rs
@@ -23,6 +23,10 @@ pub struct Tunables {
     /// calls and interrupts are implemented through the `VMInterrupts`
     /// structure, or `InterruptHandle` in the `wasmtime` crate.
     pub interruptable: bool,
+
+    /// Whether or not fuel is enabled for generated code, meaning that fuel
+    /// will be consumed every time a wasm instruction is executed.
+    pub consume_fuel: bool,
 }
 
 impl Default for Tunables {
@@ -57,6 +61,7 @@ impl Default for Tunables {
             generate_native_debuginfo: false,
             parse_wasm_debuginfo: true,
             interruptable: false,
+            consume_fuel: false,
         }
     }
 }
diff --git a/crates/environ/src/vmoffsets.rs b/crates/environ/src/vmoffsets.rs
index 8673a38d3..7f74f4675 100644
--- a/crates/environ/src/vmoffsets.rs
+++ b/crates/environ/src/vmoffsets.rs
@@ -258,6 +258,11 @@ impl VMOffsets {
     pub fn vminterrupts_stack_limit(&self) -> u8 {
         0
     }
+
+    /// Return the offset of the `fuel_consumed` field of `VMInterrupts`
+    pub fn vminterrupts_fuel_consumed(&self) -> u8 {
+        self.pointer_size
+    }
 }
 
 /// Offsets for `VMCallerCheckedAnyfunc`.
diff --git a/crates/fuzzing/src/generators.rs b/crates/fuzzing/src/generators.rs
index a35bd186a..b44af8daf 100644
--- a/crates/fuzzing/src/generators.rs
+++ b/crates/fuzzing/src/generators.rs
@@ -64,6 +64,8 @@ pub struct Config {
     debug_info: bool,
     canonicalize_nans: bool,
     interruptable: bool,
+    #[allow(missing_docs)]
+    pub consume_fuel: bool,
 
     // Note that we use 32-bit values here to avoid blowing the 64-bit address
     // space by requesting ungodly-large sizes/guards.
@@ -82,7 +84,8 @@ impl Config {
             .dynamic_memory_guard_size(self.dynamic_memory_guard_size.unwrap_or(0).into())
             .cranelift_nan_canonicalization(self.canonicalize_nans)
             .cranelift_opt_level(self.opt_level.to_wasmtime())
-            .interruptable(self.interruptable);
+            .interruptable(self.interruptable)
+            .consume_fuel(self.consume_fuel);
         return cfg;
     }
 }
diff --git a/crates/fuzzing/src/oracles.rs b/crates/fuzzing/src/oracles.rs
index 093ffbacd..2fc4532de 100644
--- a/crates/fuzzing/src/oracles.rs
+++ b/crates/fuzzing/src/oracles.rs
@@ -40,6 +40,20 @@ fn log_wasm(wasm: &[u8]) {
     }
 }
 
+/// Methods of timing out execution of a WebAssembly module
+#[derive(Debug)]
+pub enum Timeout {
+    /// No timeout is used, it should be guaranteed via some other means that
+    /// the input does not infinite loop.
+    None,
+    /// A time-based timeout is used with a sleeping thread sending a signal
+    /// after the specified duration.
+    Time(Duration),
+    /// Fuel-based timeouts are used where the specified fuel is all that the
+    /// provided wasm module is allowed to consume.
+    Fuel(u64),
+}
+
 /// Instantiate the Wasm buffer, and implicitly fail if we have an unexpected
 /// panic or segfault or anything else that can be detected "passively".
 ///
@@ -51,7 +65,7 @@ pub fn instantiate(wasm: &[u8], known_valid: bool, strategy: Strategy) {
     // pre-module-linking modules due to imports
     let mut cfg = crate::fuzz_default_config(strategy).unwrap();
     cfg.wasm_module_linking(false);
-    instantiate_with_config(wasm, known_valid, cfg, None);
+    instantiate_with_config(wasm, known_valid, cfg, Timeout::None);
 }
 
 /// Instantiate the Wasm buffer, and implicitly fail if we have an unexpected
@@ -64,28 +78,38 @@ pub fn instantiate_with_config(
     wasm: &[u8],
     known_valid: bool,
     mut config: Config,
-    timeout: Option<Duration>,
+    timeout: Timeout,
 ) {
     crate::init_fuzzing();
 
-    config.interruptable(timeout.is_some());
+    config.interruptable(match &timeout {
+        Timeout::Time(_) => true,
+        _ => false,
+    });
+    config.consume_fuel(match &timeout {
+        Timeout::Fuel(_) => true,
+        _ => false,
+    });
     let engine = Engine::new(&config);
     let store = Store::new(&engine);
 
-    // If a timeout is requested then we spawn a helper thread to wait for the
-    // requested time and then send us a signal to get interrupted. We also
-    // arrange for the thread's sleep to get interrupted if we return early (or
-    // the wasm returns within the time limit), which allows the thread to get
-    // torn down.
-    //
-    // This prevents us from creating a huge number of sleeping threads if this
-    // function is executed in a loop, like it does on nightly fuzzing
-    // infrastructure.
-
     let mut timeout_state = SignalOnDrop::default();
-    if let Some(timeout) = timeout {
-        let handle = store.interrupt_handle().unwrap();
-        timeout_state.spawn_timeout(timeout, move || handle.interrupt());
+    match timeout {
+        Timeout::Fuel(fuel) => store.add_fuel(fuel),
+        // If a timeout is requested then we spawn a helper thread to wait for
+        // the requested time and then send us a signal to get interrupted. We
+        // also arrange for the thread's sleep to get interrupted if we return
+        // early (or the wasm returns within the time limit), which allows the
+        // thread to get torn down.
+        //
+        // This prevents us from creating a huge number of sleeping threads if
+        // this function is executed in a loop, like it does on nightly fuzzing
+        // infrastructure.
+        Timeout::Time(timeout) => {
+            let handle = store.interrupt_handle().unwrap();
+            timeout_state.spawn_timeout(timeout, move || handle.interrupt());
+        }
+        Timeout::None => {}
     }
 
     log_wasm(wasm);
@@ -98,11 +122,14 @@ pub fn instantiate_with_config(
 
     match Instance::new(&store, &module, &imports) {
         Ok(_) => {}
-        // Allow traps which can happen normally with `unreachable`
+        // Allow traps which can happen normally with `unreachable` or a timeout
         Err(e) if e.downcast_ref::<Trap>().is_some() => {}
         // Allow resource exhaustion since this is something that our wasm-smith
         // generator doesn't guarantee is forbidden.
         Err(e) if e.to_string().contains("resource limit exceeded") => {}
+        // Also allow errors related to fuel consumption
+        Err(e) if e.to_string().contains("all fuel consumed") => {}
+        // Everything else should be a bug in the fuzzer
         Err(e) => panic!("failed to instantiate {}", e),
     }
 }
@@ -383,13 +410,16 @@ pub fn make_api_calls(api: crate::generators::api::ApiCalls) {
 /// Executes the wast `test` spectest with the `config` specified.
 ///
 /// Ensures that spec tests pass regardless of the `Config`.
-pub fn spectest(config: crate::generators::Config, test: crate::generators::SpecTest) {
+pub fn spectest(fuzz_config: crate::generators::Config, test: crate::generators::SpecTest) {
     crate::init_fuzzing();
-    log::debug!("running {:?} with {:?}", test.file, config);
-    let mut config = config.to_wasmtime();
+    log::debug!("running {:?} with {:?}", test.file, fuzz_config);
+    let mut config = fuzz_config.to_wasmtime();
     config.wasm_reference_types(false);
     config.wasm_bulk_memory(false);
     let store = Store::new(&Engine::new(&config));
+    if fuzz_config.consume_fuel {
+        store.add_fuel(u64::max_value());
+    }
     let mut wast_context = WastContext::new(store);
     wast_context.register_spectest().unwrap();
     wast_context
@@ -398,16 +428,22 @@ pub fn spectest(config: crate::generators::Config, test: crate::generators::Spec
 }
 
 /// Execute a series of `table.get` and `table.set` operations.
-pub fn table_ops(config: crate::generators::Config, ops: crate::generators::table_ops::TableOps) {
+pub fn table_ops(
+    fuzz_config: crate::generators::Config,
+    ops: crate::generators::table_ops::TableOps,
+) {
     let _ = env_logger::try_init();
 
     let num_dropped = Rc::new(Cell::new(0));
 
     {
-        let mut config = config.to_wasmtime();
+        let mut config = fuzz_config.to_wasmtime();
         config.wasm_reference_types(true);
         let engine = Engine::new(&config);
         let store = Store::new(&engine);
+        if fuzz_config.consume_fuel {
+            store.add_fuel(u64::max_value());
+        }
 
         let wasm = ops.to_wasm_binary();
         log_wasm(&wasm);
@@ -520,6 +556,9 @@ pub fn differential_wasmi_execution(wasm: &[u8], config: &crate::generators::Con
     wasmtime_config.cranelift_nan_canonicalization(true);
     let wasmtime_engine = Engine::new(&wasmtime_config);
     let wasmtime_store = Store::new(&wasmtime_engine);
+    if config.consume_fuel {
+        wasmtime_store.add_fuel(u64::max_value());
+    }
     let wasmtime_module =
         Module::new(&wasmtime_engine, &wasm).expect("Wasmtime can compile module");
     let wasmtime_instance = Instance::new(&wasmtime_store, &wasmtime_module, &[])
diff --git a/crates/profiling/src/jitdump_linux.rs b/crates/profiling/src/jitdump_linux.rs
index ef6684c95..0f3a4bb00 100644
--- a/crates/profiling/src/jitdump_linux.rs
+++ b/crates/profiling/src/jitdump_linux.rs
@@ -1,6 +1,6 @@
 //! Support for jitdump files which can be used by perf for profiling jitted code.
 //! Spec definitions for the output format is as described here:
-//! https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/perf/Documentation/jitdump-specification.txt
+//! <https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/perf/Documentation/jitdump-specification.txt>
 //!
 //! Usage Example:
 //!     Record
diff --git a/crates/runtime/src/externref.rs b/crates/runtime/src/externref.rs
index dd0a4f147..b5a8ef30b 100644
--- a/crates/runtime/src/externref.rs
+++ b/crates/runtime/src/externref.rs
@@ -97,7 +97,7 @@
 //!
 //! 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
+//! <https://openresearch-repository.anu.edu.au/bitstream/1885/42030/2/hon-thesis.pdf>
 
 use std::alloc::Layout;
 use std::any::Any;
diff --git a/crates/runtime/src/libcalls.rs b/crates/runtime/src/libcalls.rs
index 61e8ca4a2..026738a8a 100644
--- a/crates/runtime/src/libcalls.rs
+++ b/crates/runtime/src/libcalls.rs
@@ -581,3 +581,8 @@ pub unsafe extern "C" fn wasmtime_imported_memory_atomic_wait64(
         "wasm atomics (fn wasmtime_imported_memory_atomic_wait64) unsupported",
     ))));
 }
+
+/// Hook for when an instance runs out of fuel.
+pub unsafe extern "C" fn wasmtime_out_of_gas(_vmctx: *mut VMContext) {
+    crate::traphandlers::out_of_gas()
+}
diff --git a/crates/runtime/src/traphandlers.rs b/crates/runtime/src/traphandlers.rs
index e554e54c3..feaf2c4a9 100644
--- a/crates/runtime/src/traphandlers.rs
+++ b/crates/runtime/src/traphandlers.rs
@@ -410,6 +410,13 @@ pub fn with_last_info<R>(func: impl FnOnce(Option<&dyn Any>) -> R) -> R {
     tls::with(|state| func(state.map(|s| s.trap_info.as_any())))
 }
 
+/// Invokes the contextually-defined context's out-of-gas function.
+///
+/// (basically delegates to `wasmtime::Store::out_of_gas`)
+pub fn out_of_gas() {
+    tls::with(|state| state.unwrap().trap_info.out_of_gas())
+}
+
 /// Temporary state stored on the stack which is registered in the `tls` module
 /// below for calls into wasm.
 pub struct CallThreadState<'a> {
@@ -442,6 +449,12 @@ pub unsafe trait TrapInfo {
     /// Returns the maximum size, in bytes, the wasm native stack is allowed to
     /// grow to.
     fn max_wasm_stack(&self) -> usize;
+
+    /// Callback invoked whenever WebAssembly has entirely consumed the fuel
+    /// that it was allotted.
+    ///
+    /// This function may return, and it may also `raise_lib_trap`.
+    fn out_of_gas(&self);
 }
 
 enum UnwindReason {
diff --git a/crates/runtime/src/vmcontext.rs b/crates/runtime/src/vmcontext.rs
index 3eebdabd4..c20a42b5e 100644
--- a/crates/runtime/src/vmcontext.rs
+++ b/crates/runtime/src/vmcontext.rs
@@ -4,6 +4,7 @@
 use crate::externref::VMExternRef;
 use crate::instance::Instance;
 use std::any::Any;
+use std::cell::UnsafeCell;
 use std::ptr::NonNull;
 use std::sync::atomic::{AtomicUsize, Ordering::SeqCst};
 use std::u32;
@@ -612,6 +613,7 @@ impl VMBuiltinFunctionsArray {
             wasmtime_memory_atomic_wait64 as usize;
         ptrs[BuiltinFunctionIndex::imported_memory_atomic_wait64().index() as usize] =
             wasmtime_imported_memory_atomic_wait64 as usize;
+        ptrs[BuiltinFunctionIndex::out_of_gas().index() as usize] = wasmtime_out_of_gas as usize;
 
         if cfg!(debug_assertions) {
             for i in 0..ptrs.len() {
@@ -658,8 +660,7 @@ impl VMInvokeArgument {
     }
 }
 
-/// Structure used to control interrupting wasm code, currently with only one
-/// atomic flag internally used.
+/// Structure used to control interrupting wasm code.
 #[derive(Debug)]
 #[repr(C)]
 pub struct VMInterrupts {
@@ -668,6 +669,14 @@ pub struct VMInterrupts {
     /// This is used to control both stack overflow as well as interrupting wasm
     /// modules. For more information see `crates/environ/src/cranelift.rs`.
     pub stack_limit: AtomicUsize,
+
+    /// Indicator of how much fuel has been consumed and is remaining to
+    /// WebAssembly.
+    ///
+    /// This field is typically negative and increments towards positive. Upon
+    /// turning positive a wasm trap will be generated. This field is only
+    /// modified if wasm is configured to consume fuel.
+    pub fuel_consumed: UnsafeCell<i64>,
 }
 
 impl VMInterrupts {
@@ -682,6 +691,7 @@ impl Default for VMInterrupts {
     fn default() -> VMInterrupts {
         VMInterrupts {
             stack_limit: AtomicUsize::new(usize::max_value()),
+            fuel_consumed: UnsafeCell::new(0),
         }
     }
 }
diff --git a/crates/wasmtime/src/config.rs b/crates/wasmtime/src/config.rs
index 3edbfebb2..a662599dc 100644
--- a/crates/wasmtime/src/config.rs
+++ b/crates/wasmtime/src/config.rs
@@ -137,6 +137,28 @@ impl Config {
         self
     }
 
+    /// Configures whether execution of WebAssembly will "consume fuel" to
+    /// either halt or yield execution as desired.
+    ///
+    /// This option is similar in purpose to [`Config::interruptable`] where
+    /// you can prevent infinitely-executing WebAssembly code. The difference
+    /// is that this option allows deterministic execution of WebAssembly code
+    /// by instrumenting generated code consume fuel as it executes. When fuel
+    /// runs out the behavior is defined by configuration within a [`Store`],
+    /// and by default a trap is raised.
+    ///
+    /// Note that a [`Store`] starts with no fuel, so if you enable this option
+    /// you'll have to be sure to pour some fuel into [`Store`] before
+    /// executing some code.
+    ///
+    /// By default this option is `false`.
+    ///
+    /// [`Store`]: crate::Store
+    pub fn consume_fuel(&mut self, enable: bool) -> &mut Self {
+        self.tunables.consume_fuel = enable;
+        self
+    }
+
     /// Configures the maximum amount of native stack space available to
     /// executing WebAssembly code.
     ///
diff --git a/crates/wasmtime/src/store.rs b/crates/wasmtime/src/store.rs
index cc86011fb..10564d79d 100644
--- a/crates/wasmtime/src/store.rs
+++ b/crates/wasmtime/src/store.rs
@@ -6,6 +6,7 @@ use anyhow::{bail, Result};
 use std::any::Any;
 use std::cell::{Cell, RefCell};
 use std::collections::HashSet;
+use std::convert::TryFrom;
 use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::rc::{Rc, Weak};
@@ -72,6 +73,10 @@ pub(crate) struct StoreInner {
     instance_count: Cell<usize>,
     memory_count: Cell<usize>,
     table_count: Cell<usize>,
+
+    /// An adjustment to add to the fuel consumed value in `interrupts` above
+    /// to get the true amount of fuel consumed.
+    fuel_adj: Cell<i64>,
 }
 
 struct HostInfoKey(VMExternRef);
@@ -117,6 +122,7 @@ impl Store {
                 instance_count: Default::default(),
                 memory_count: Default::default(),
                 table_count: Default::default(),
+                fuel_adj: Cell::new(0),
             }),
         }
     }
@@ -427,6 +433,64 @@ impl Store {
             );
         }
     }
+
+    /// Returns the amount of fuel consumed by this store's execution so far.
+    ///
+    /// If fuel consumption is not enabled via
+    /// [`Config::consume_fuel`](crate::Config::consume_fuel) then this
+    /// function will return `None`. Also note that fuel, if enabled, must be
+    /// originally configured via [`Store::add_fuel`].
+    pub fn fuel_consumed(&self) -> Option<u64> {
+        if !self.engine().config().tunables.consume_fuel {
+            return None;
+        }
+        let consumed = unsafe { *self.inner.interrupts.fuel_consumed.get() };
+        Some(u64::try_from(self.inner.fuel_adj.get() + consumed).unwrap())
+    }
+
+    /// Adds fuel to this [`Store`] for wasm to consume while executing.
+    ///
+    /// For this method to work fuel consumption must be enabled via
+    /// [`Config::consume_fuel`](crate::Config::consume_fuel). By default a
+    /// [`Store`] starts with 0 fuel for wasm to execute with (meaning it will
+    /// immediately trap). This function must be called for the store to have
+    /// some fuel to allow WebAssembly to execute.
+    ///
+    /// Note that at this time when fuel is entirely consumed it will cause
+    /// wasm to trap. More usages of fuel are planned for the future.
+    ///
+    /// # Panics
+    ///
+    /// This function will panic if the store's [`Config`](crate::Config) did
+    /// not have fuel consumption enabled.
+    pub fn add_fuel(&self, fuel: u64) {
+        assert!(self.engine().config().tunables.consume_fuel);
+
+        // Fuel is stored as an i64, so we need to cast it. If the provided fuel
+        // value overflows that just assume that i64::max will suffice. Wasm
+        // execution isn't fast enough to burn through i64::max fuel in any
+        // reasonable amount of time anyway.
+        let fuel = i64::try_from(fuel).unwrap_or(i64::max_value());
+        let adj = self.inner.fuel_adj.get();
+        let consumed_ptr = unsafe { &mut *self.inner.interrupts.fuel_consumed.get() };
+
+        match (consumed_ptr.checked_sub(fuel), adj.checked_add(fuel)) {
+            // If we succesfully did arithmetic without overflowing then we can
+            // just update our fields.
+            (Some(consumed), Some(adj)) => {
+                self.inner.fuel_adj.set(adj);
+                *consumed_ptr = consumed;
+            }
+
+            // Otherwise something overflowed. Make sure that we preserve the
+            // amount of fuel that's already consumed, but otherwise assume that
+            // we were given infinite fuel.
+            _ => {
+                self.inner.fuel_adj.set(i64::max_value());
+                *consumed_ptr = (*consumed_ptr + adj) - i64::max_value();
+            }
+        }
+    }
 }
 
 unsafe impl TrapInfo for Store {
@@ -448,6 +512,23 @@ unsafe impl TrapInfo for Store {
     fn max_wasm_stack(&self) -> usize {
         self.engine().config().max_wasm_stack
     }
+
+    fn out_of_gas(&self) {
+        #[derive(Debug)]
+        struct OutOfGas;
+
+        impl fmt::Display for OutOfGas {
+            fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+                f.write_str("all fuel consumed by WebAssembly")
+            }
+        }
+
+        impl std::error::Error for OutOfGas {}
+
+        unsafe {
+            wasmtime_runtime::raise_lib_trap(wasmtime_runtime::Trap::User(Box::new(OutOfGas)))
+        }
+    }
 }
 
 impl Default for Store {
@@ -481,6 +562,13 @@ pub struct InterruptHandle {
     interrupts: Arc<VMInterrupts>,
 }
 
+// The `VMInterrupts` type is a pod-type with no destructor, and we only access
+// `interrupts` from other threads, so add in these trait impls which are
+// otherwise not available due to the `fuel_consumed` variable in
+// `VMInterrupts`.
+unsafe impl Send for InterruptHandle {}
+unsafe impl Sync for InterruptHandle {}
+
 impl InterruptHandle {
     /// Flags that execution within this handle's original [`Store`] should be
     /// interrupted.
diff --git a/fuzz/fuzz_targets/instantiate-maybe-invalid.rs b/fuzz/fuzz_targets/instantiate-maybe-invalid.rs
index 219986a25..46a749f5e 100644
--- a/fuzz/fuzz_targets/instantiate-maybe-invalid.rs
+++ b/fuzz/fuzz_targets/instantiate-maybe-invalid.rs
@@ -4,13 +4,18 @@ use libfuzzer_sys::fuzz_target;
 use std::time::Duration;
 use wasm_smith::MaybeInvalidModule;
 use wasmtime::Strategy;
-use wasmtime_fuzzing::oracles;
+use wasmtime_fuzzing::oracles::{self, Timeout};
 
-fuzz_target!(|module: MaybeInvalidModule| {
+fuzz_target!(|pair: (bool, MaybeInvalidModule)| {
+    let (timeout_with_time, module) = pair;
     oracles::instantiate_with_config(
         &module.to_bytes(),
         false,
         wasmtime_fuzzing::fuzz_default_config(Strategy::Auto).unwrap(),
-        Some(Duration::from_secs(20)),
+        if timeout_with_time {
+            Timeout::Time(Duration::from_secs(20))
+        } else {
+            Timeout::Fuel(100_000)
+        },
     );
 });
diff --git a/fuzz/fuzz_targets/instantiate-swarm.rs b/fuzz/fuzz_targets/instantiate-swarm.rs
index d9c5bdb64..b534cc497 100644
--- a/fuzz/fuzz_targets/instantiate-swarm.rs
+++ b/fuzz/fuzz_targets/instantiate-swarm.rs
@@ -4,11 +4,21 @@ use libfuzzer_sys::fuzz_target;
 use std::time::Duration;
 use wasm_smith::{Config, ConfiguredModule, SwarmConfig};
 use wasmtime::Strategy;
-use wasmtime_fuzzing::oracles;
+use wasmtime_fuzzing::oracles::{self, Timeout};
 
-fuzz_target!(|module: ConfiguredModule<SwarmConfig>| {
+fuzz_target!(|pair: (bool, ConfiguredModule<SwarmConfig>)| {
+    let (timeout_with_time, module) = pair;
     let mut cfg = wasmtime_fuzzing::fuzz_default_config(Strategy::Auto).unwrap();
     cfg.wasm_multi_memory(true);
     cfg.wasm_module_linking(module.config().module_linking_enabled());
-    oracles::instantiate_with_config(&module.to_bytes(), true, cfg, Some(Duration::from_secs(20)));
+    oracles::instantiate_with_config(
+        &module.to_bytes(),
+        true,
+        cfg,
+        if timeout_with_time {
+            Timeout::Time(Duration::from_secs(20))
+        } else {
+            Timeout::Fuel(100_000)
+        },
+    );
 });


Test patch:
diff --git a/tests/all/fuel.rs b/tests/all/fuel.rs
new file mode 100644
index 000000000..b1b73bc6a
--- /dev/null
+++ b/tests/all/fuel.rs
@@ -0,0 +1,124 @@
+use anyhow::Result;
+use wasmtime::*;
+use wast::parser::{self, Parse, ParseBuffer, Parser};
+
+mod kw {
+    wast::custom_keyword!(assert_fuel);
+}
+
+struct FuelWast<'a> {
+    assertions: Vec<(wast::Span, u64, wast::Module<'a>)>,
+}
+
+impl<'a> Parse<'a> for FuelWast<'a> {
+    fn parse(parser: Parser<'a>) -> parser::Result<Self> {
+        let mut assertions = Vec::new();
+        while !parser.is_empty() {
+            assertions.push(parser.parens(|p| {
+                let span = p.parse::<kw::assert_fuel>()?.0;
+                Ok((span, p.parse()?, p.parens(|p| p.parse())?))
+            })?);
+        }
+        Ok(FuelWast { assertions })
+    }
+}
+
+#[test]
+fn run() -> Result<()> {
+    let test = std::fs::read_to_string("tests/all/fuel.wast")?;
+    let buf = ParseBuffer::new(&test)?;
+    let mut wast = parser::parse::<FuelWast<'_>>(&buf)?;
+    for (span, fuel, module) in wast.assertions.iter_mut() {
+        let consumed = fuel_consumed(&module.encode()?);
+        if consumed == *fuel {
+            continue;
+        }
+        let (line, col) = span.linecol_in(&test);
+        panic!(
+            "tests/all/fuel.wast:{}:{} - expected {} fuel, found {}",
+            line + 1,
+            col + 1,
+            fuel,
+            consumed
+        );
+    }
+    Ok(())
+}
+
+fn fuel_consumed(wasm: &[u8]) -> u64 {
+    let mut config = Config::new();
+    config.consume_fuel(true);
+    let engine = Engine::new(&config);
+    let module = Module::new(&engine, wasm).unwrap();
+    let store = Store::new(&engine);
+    store.add_fuel(u64::max_value());
+    drop(Instance::new(&store, &module, &[]));
+    store.fuel_consumed().unwrap()
+}
+
+#[test]
+fn iloop() {
+    iloop_aborts(
+        r#"
+            (module
+                (start 0)
+                (func loop br 0 end)
+            )
+        "#,
+    );
+    iloop_aborts(
+        r#"
+            (module
+                (start 0)
+                (func loop i32.const 1 br_if 0 end)
+            )
+        "#,
+    );
+    iloop_aborts(
+        r#"
+            (module
+                (start 0)
+                (func loop i32.const 0 br_table 0 end)
+            )
+        "#,
+    );
+    iloop_aborts(
+        r#"
+            (module
+                (start 0)
+                (func $f0 call $f1 call $f1)
+                (func $f1 call $f2 call $f2)
+                (func $f2 call $f3 call $f3)
+                (func $f3 call $f4 call $f4)
+                (func $f4 call $f5 call $f5)
+                (func $f5 call $f6 call $f6)
+                (func $f6 call $f7 call $f7)
+                (func $f7 call $f8 call $f8)
+                (func $f8 call $f9 call $f9)
+                (func $f9 call $f10 call $f10)
+                (func $f10 call $f11 call $f11)
+                (func $f11 call $f12 call $f12)
+                (func $f12 call $f13 call $f13)
+                (func $f13 call $f14 call $f14)
+                (func $f14 call $f15 call $f15)
+                (func $f15 call $f16 call $f16)
+                (func $f16)
+            )
+        "#,
+    );
+
+    fn iloop_aborts(wat: &str) {
+        let mut config = Config::new();
+        config.consume_fuel(true);
+        let engine = Engine::new(&config);
+        let module = Module::new(&engine, wat).unwrap();
+        let store = Store::new(&engine);
+        store.add_fuel(10_000);
+        let error = Instance::new(&store, &module, &[]).err().unwrap();
+        assert!(
+            error.to_string().contains("all fuel consumed"),
+            "bad error: {}",
+            error
+        );
+    }
+}
diff --git a/tests/all/fuel.wast b/tests/all/fuel.wast
new file mode 100644
index 000000000..bb3450b6c
--- /dev/null
+++ b/tests/all/fuel.wast
@@ -0,0 +1,208 @@
+(assert_fuel 0 (module))
+
+(assert_fuel 1
+  (module
+    (func $f)
+    (start $f)))
+
+(assert_fuel 2
+  (module
+    (func $f
+      i32.const 0
+      drop
+    )
+    (start $f)))
+
+(assert_fuel 1
+  (module
+    (func $f
+      block
+      end
+    )
+    (start $f)))
+
+(assert_fuel 1
+  (module
+    (func $f
+      unreachable
+    )
+    (start $f)))
+
+(assert_fuel 7
+  (module
+    (func $f
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      unreachable
+    )
+    (start $f)))
+
+(assert_fuel 1
+  (module
+    (func $f
+      return
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      i32.const 0
+      unreachable
+    )
+    (start $f)))
+
+(assert_fuel 3
+  (module
+    (func $f
+      i32.const 0
+      if
+        call $f
+      end
+    )
+    (start $f)))
+
+(assert_fuel 4
+  (module
+    (func $f
+      i32.const 1
+      if
+        i32.const 0
+        drop
+      end
+    )
+    (start $f)))
+
+(assert_fuel 4
+  (module
+    (func $f
+      i32.const 1
+      if
+        i32.const 0
+        drop
+      else
+        call $f
+      end
+    )
+    (start $f)))
+
+(assert_fuel 4
+  (module
+    (func $f
+      i32.const 0
+      if
+        call $f
+      else
+        i32.const 0
+        drop
+      end
+    )
+    (start $f)))
+
+(assert_fuel 3
+  (module
+    (func $f
+      block
+        i32.const 1
+        br_if 0
+        i32.const 0
+        drop
+      end
+    )
+    (start $f)))
+
+(assert_fuel 4
+  (module
+    (func $f
+      block
+        i32.const 0
+        br_if 0
+        i32.const 0
+        drop
+      end
+    )
+    (start $f)))
+
+;; count code before unreachable
+(assert_fuel 2
+  (module
+    (func $f
+      i32.const 0
+      unreachable
+    )
+    (start $f)))
+
+;; count code before return
+(assert_fuel 2
+  (module
+    (func $f
+      i32.const 0
+      return
+    )
+    (start $f)))
+
+;; cross-function fuel works
+(assert_fuel 3
+  (module
+    (func $f
+      call $other
+    )
+    (func $other)
+    (start $f)))
+(assert_fuel 5
+  (module
+    (func $f
+      i32.const 0
+      call $other
+      i32.const 0
+      drop
+    )
+    (func $other (param i32))
+    (start $f)))
+(assert_fuel 4
+  (module
+    (func $f
+      call $other
+      drop
+    )
+    (func $other (result i32)
+      i32.const 0
+    )
+    (start $f)))
+(assert_fuel 4
+  (module
+    (func $f
+      i32.const 0
+      call_indirect
+    )
+    (func $other)
+    (table funcref (elem $other))
+    (start $f)))
+
+;; loops!
+(assert_fuel 1
+  (module
+    (func $f
+      loop
+      end
+    )
+    (start $f)))
+(assert_fuel 53 ;; 5 loop instructions, 10 iterations, 2 header instrs, 1 func
+  (module
+    (func $f
+      (local i32)
+      i32.const 10
+      local.set 0
+
+      loop
+        local.get 0
+        i32.const 1
+        i32.sub
+        local.tee 0
+        br_if 0
+      end
+    )
+    (start $f)))
diff --git a/tests/all/fuzzing.rs b/tests/all/fuzzing.rs
index 3e46af2d7..e5c190688 100644
--- a/tests/all/fuzzing.rs
+++ b/tests/all/fuzzing.rs
@@ -6,7 +6,7 @@
 //! `include_bytes!("./fuzzing/some-descriptive-name.wasm")`.
 
 use wasmtime::{Config, Strategy};
-use wasmtime_fuzzing::oracles;
+use wasmtime_fuzzing::oracles::{self, Timeout};
 
 #[test]
 fn instantiate_empty_module() {
@@ -26,5 +26,5 @@ fn instantiate_module_that_compiled_to_x64_has_register_32() {
     let mut config = Config::new();
     config.debug_info(true);
     let data = wat::parse_str(include_str!("./fuzzing/issue694.wat")).unwrap();
-    oracles::instantiate_with_config(&data, true, config, None);
+    oracles::instantiate_with_config(&data, true, config, Timeout::None);
 }
diff --git a/tests/all/main.rs b/tests/all/main.rs
index 1f6cb8045..c20b2dddc 100644
--- a/tests/all/main.rs
+++ b/tests/all/main.rs
@@ -2,6 +2,7 @@ mod cli_tests;
 mod custom_signal_handler;
 mod debug;
 mod externals;
+mod fuel;
 mod func;
 mod fuzzing;
 mod globals;