diff options
| -rw-r--r-- | crates/parser/src/conversion.rs | 24 | ||||
| -rw-r--r-- | crates/tinywasm/src/error.rs | 6 | ||||
| -rw-r--r-- | crates/tinywasm/src/runtime/executor/macros.rs | 13 | ||||
| -rw-r--r-- | crates/tinywasm/src/runtime/executor/mod.rs | 68 | ||||
| -rw-r--r-- | crates/tinywasm/src/runtime/stack.rs | 2 | ||||
| -rw-r--r-- | crates/tinywasm/src/runtime/stack/blocks.rs | 21 | ||||
| -rw-r--r-- | crates/tinywasm/src/runtime/stack/call_stack.rs | 52 | ||||
| -rw-r--r-- | examples/wasm/loop.wat | 104 |
8 files changed, 174 insertions, 116 deletions
diff --git a/crates/parser/src/conversion.rs b/crates/parser/src/conversion.rs index 7803d08..5e7be0e 100644 --- a/crates/parser/src/conversion.rs +++ b/crates/parser/src/conversion.rs @@ -1,4 +1,5 @@ use alloc::{boxed::Box, format, string::ToString, vec::Vec}; +use log::info; use tinywasm_types::{BlockArgs, Export, ExternalKind, FuncType, Instruction, MemArg, ValType}; use wasmparser::{FuncValidator, ValidatorResources}; @@ -113,9 +114,11 @@ pub fn process_operators<'a>( mut validator: FuncValidator<ValidatorResources>, ) -> Result<Box<[Instruction]>> { let mut instructions = Vec::new(); - let mut last_label_pointer = Option::None; + let mut labels_ptrs = Vec::new(); for (i, op) in ops.enumerate() { + info!("op: {:?}", op); + let op = op?; validator.op(offset, &op)?; offset += 1; @@ -134,19 +137,19 @@ pub fn process_operators<'a>( Unreachable => Instruction::Unreachable, Nop => Instruction::Nop, Block { blockty } => { - last_label_pointer = Some(i); + labels_ptrs.push(instructions.len()); Instruction::Block(convert_blocktype(blockty), 0) } Loop { blockty } => { - last_label_pointer = Some(i); + labels_ptrs.push(instructions.len()); Instruction::Loop(convert_blocktype(blockty), 0) } If { blockty } => { - last_label_pointer = Some(i); + labels_ptrs.push(instructions.len()); Instruction::If(convert_blocktype(blockty), 0) } End => { - if let Some(label_pointer) = last_label_pointer { + if let Some(label_pointer) = labels_ptrs.pop() { // last_label_pointer is Some if we're ending a block match instructions[label_pointer] { Instruction::Block(_, ref mut end) @@ -154,7 +157,6 @@ pub fn process_operators<'a>( | Instruction::Else(ref mut end) | Instruction::If(_, ref mut end) => { *end = i + 1; // Set the end position to be one after the End instruction - last_label_pointer = None; } _ => { return Err(crate::ParseError::UnsupportedOperator( @@ -170,7 +172,7 @@ pub fn process_operators<'a>( } } Else => { - let Some(label_pointer) = last_label_pointer else { + let Some(label_pointer) = labels_ptrs.pop() else { return Err(crate::ParseError::UnsupportedOperator( "Expected to end an if block, but the last label was None".to_string(), )); @@ -187,7 +189,6 @@ pub fn process_operators<'a>( } } - last_label_pointer = Some(i); Instruction::Else(0) } Br { relative_depth } => Instruction::Br(relative_depth), @@ -369,6 +370,13 @@ pub fn process_operators<'a>( instructions.push(res); } + if !labels_ptrs.is_empty() { + panic!( + "last_label_pointer should be None after processing all instructions: {:?}", + labels_ptrs + ); + } + validator.finish(offset)?; Ok(instructions.into_boxed_slice()) diff --git a/crates/tinywasm/src/error.rs b/crates/tinywasm/src/error.rs index dc53106..bea97fa 100644 --- a/crates/tinywasm/src/error.rs +++ b/crates/tinywasm/src/error.rs @@ -39,8 +39,8 @@ pub enum Error { /// The stack is empty StackUnderflow, - /// The block stack is empty - BlockStackUnderflow, + /// The label stack is empty + LabelStackUnderflow, /// The call stack is empty CallStackEmpty, @@ -63,7 +63,7 @@ impl Display for Error { Self::Other(message) => write!(f, "unknown error: {}", message), Self::UnsupportedFeature(feature) => write!(f, "unsupported feature: {}", feature), Self::FuncDidNotReturn => write!(f, "function did not return"), - Self::BlockStackUnderflow => write!(f, "block stack underflow"), + Self::LabelStackUnderflow => write!(f, "label stack underflow"), Self::StackUnderflow => write!(f, "stack underflow"), Self::CallStackEmpty => write!(f, "call stack empty"), Self::InvalidStore => write!(f, "invalid store"), diff --git a/crates/tinywasm/src/runtime/executor/macros.rs b/crates/tinywasm/src/runtime/executor/macros.rs index 01a7186..91d48d3 100644 --- a/crates/tinywasm/src/runtime/executor/macros.rs +++ b/crates/tinywasm/src/runtime/executor/macros.rs @@ -31,7 +31,7 @@ macro_rules! div_instr { /// Less than signed instruction macro_rules! lts_instr { ($ty:ty, $stack:ident) => {{ - let [b, a] = $stack.values.pop_n_const::<2>()?; + let [a, b] = $stack.values.pop_n_const::<2>()?; let a: $ty = a.into(); let b: $ty = b.into(); $stack.values.push(((a < b) as i32).into()); @@ -58,9 +58,20 @@ macro_rules! eq_instr { }}; } +/// Greater or equal than signed instruction +macro_rules! ges_instr { + ($ty:ty, $stack:ident) => {{ + let [a, b] = $stack.values.pop_n_const::<2>()?; + let a: $ty = a.into(); + let b: $ty = b.into(); + $stack.values.push(((a >= b) as i32).into()); + }}; +} + pub(super) use add_instr; pub(super) use div_instr; pub(super) use eq_instr; +pub(super) use ges_instr; pub(super) use lts_instr; pub(super) use mul_instr; pub(super) use sub_instr; diff --git a/crates/tinywasm/src/runtime/executor/mod.rs b/crates/tinywasm/src/runtime/executor/mod.rs index 662b080..25c7601 100644 --- a/crates/tinywasm/src/runtime/executor/mod.rs +++ b/crates/tinywasm/src/runtime/executor/mod.rs @@ -1,10 +1,11 @@ use super::{DefaultRuntime, Stack}; use crate::{ log::debug, - runtime::{BlockFrame, BlockFrameInner, RawWasmValue}, + runtime::{BlockType, LabelFrame, RawWasmValue}, CallFrame, Error, ModuleInstance, Result, Store, }; use alloc::vec::Vec; +use log::info; use tinywasm_types::{BlockArgs, Instruction}; mod macros; @@ -64,6 +65,9 @@ enum ExecResult { Trap(crate::Trap), } +/// Run a single step of the interpreter +/// A seperate function is used so later, we can more easily implement +/// a step-by-step debugger (using generators once they're stable?) #[inline] fn exec_one( cf: &mut CallFrame, @@ -74,6 +78,9 @@ fn exec_one( module: &ModuleInstance, ) -> Result<ExecResult> { use tinywasm_types::Instruction::*; + + info!("ptr: {} instr: {:?}", cf.instr_ptr, instr); + match instr { Nop => { /* do nothing */ } Unreachable => return Ok(ExecResult::Trap(crate::Trap::Unreachable)), // we don't need to include the call frame here because it's already on the stack @@ -117,23 +124,23 @@ fn exec_one( } Loop(args, end_offset) => { - cf.block_frames.push(BlockFrame { + cf.labels.push(LabelFrame { instr_ptr: cf.instr_ptr, end_instr_ptr: cf.instr_ptr + *end_offset, stack_ptr: stack.values.len(), args: *args, - block: BlockFrameInner::Loop, + ty: BlockType::Loop, }); stack.values.block_args(*args)?; } Block(args, end_offset) => { - cf.block_frames.push(BlockFrame { + cf.labels.push(LabelFrame { instr_ptr: cf.instr_ptr, end_instr_ptr: cf.instr_ptr + *end_offset, stack_ptr: stack.values.len(), args: *args, - block: BlockFrameInner::Block, + ty: BlockType::Block, }); stack.values.block_args(*args)?; } @@ -163,7 +170,7 @@ fn exec_one( } EndFunc => { - if cf.block_frames.len() > 0 { + if cf.labels.len() > 0 { panic!("endfunc: block frames not empty, this should have been validated by the parser"); } @@ -178,44 +185,24 @@ fn exec_one( } EndBlockFrame => { - let blocks = &mut cf.block_frames; + let blocks = &mut cf.labels; + + // remove the label from the label stack let Some(block) = blocks.pop() else { - panic!("end: no block to end, this should have been validated by the parser"); + panic!("end: no label to end, this should have been validated by the parser"); }; - debug!("end, blocks: {:?}", blocks); - debug!(" instr_ptr: {}", cf.instr_ptr); - let res: &[RawWasmValue] = match block.args { BlockArgs::Empty => &[], BlockArgs::Type(_t) => todo!(), BlockArgs::FuncType(_t) => todo!(), }; - match block.block { - BlockFrameInner::Loop => { - debug!("end(loop): continue loop"); + // trim the lable's stack from the stack + stack.values.trim(block.stack_ptr); - // remove the loop values from the stack - stack.values.trim(block.stack_ptr); - - // set the instruction pointer to the start of the loop - cf.instr_ptr = block.instr_ptr; - - // push the loop back onto the stack - blocks.push(block); - } - BlockFrameInner::Block => { - // remove the block values from the stack - stack.values.trim(block.stack_ptr); - - // push the block result values to the stack - stack.values.extend(res.iter().copied()); - } - _ => { - panic!("end: unimplemented block type end: {:?}", block.block); - } - } + // push the block result values to the stack + stack.values.extend(res.iter().copied()); } LocalGet(local_index) => { @@ -244,17 +231,16 @@ fn exec_one( F32Sub => sub_instr!(f32, stack), F64Sub => sub_instr!(f64, stack), - I32LtS => { - let [b, a] = stack.values.pop_n_const::<2>()?; - let a: i32 = a.into(); - let b: i32 = b.into(); - stack.values.push(((a < b) as i32).into()); - debug!("i32.lt_s: {} < {} = {}", a, b, a < b); - } + I32LtS => lts_instr!(i32, stack), I64LtS => lts_instr!(i64, stack), F32Lt => lts_instr!(f32, stack), F64Lt => lts_instr!(f64, stack), + I32GeS => ges_instr!(i32, stack), + I64GeS => ges_instr!(i64, stack), + F32Ge => ges_instr!(f32, stack), + F64Ge => ges_instr!(f64, stack), + I32DivS => div_instr!(i32, stack), I64DivS => div_instr!(i64, stack), F32Div => div_instr!(f32, stack), diff --git a/crates/tinywasm/src/runtime/stack.rs b/crates/tinywasm/src/runtime/stack.rs index 8e921b6..ed978bb 100644 --- a/crates/tinywasm/src/runtime/stack.rs +++ b/crates/tinywasm/src/runtime/stack.rs @@ -3,7 +3,7 @@ mod call_stack; mod value_stack; use self::{call_stack::CallStack, value_stack::ValueStack}; -pub(crate) use blocks::{BlockFrame, BlockFrameInner}; +pub(crate) use blocks::{BlockType, LabelFrame}; pub(crate) use call_stack::CallFrame; /// A WebAssembly Stack diff --git a/crates/tinywasm/src/runtime/stack/blocks.rs b/crates/tinywasm/src/runtime/stack/blocks.rs index 4979fa2..d0ce02a 100644 --- a/crates/tinywasm/src/runtime/stack/blocks.rs +++ b/crates/tinywasm/src/runtime/stack/blocks.rs @@ -3,28 +3,33 @@ use log::info; use tinywasm_types::BlockArgs; #[derive(Debug, Default, Clone)] -pub(crate) struct Blocks(Vec<BlockFrame>); +pub(crate) struct Labels(Vec<LabelFrame>); -impl Blocks { +impl Labels { pub(crate) fn len(&self) -> usize { self.0.len() } #[inline] - pub(crate) fn push(&mut self, block: BlockFrame) { + pub(crate) fn push(&mut self, block: LabelFrame) { self.0.push(block); } #[inline] + pub(crate) fn top(&self) -> Option<&LabelFrame> { + self.0.last() + } + + #[inline] /// get the block at the given index, where 0 is the top of the stack - pub(crate) fn get_relative_to_top(&self, index: usize) -> Option<&BlockFrame> { + pub(crate) fn get_relative_to_top(&self, index: usize) -> Option<&LabelFrame> { info!("get block: {}", index); info!("blocks: {:?}", self.0); self.0.get(self.0.len() - index - 1) } #[inline] - pub(crate) fn pop(&mut self) -> Option<BlockFrame> { + pub(crate) fn pop(&mut self) -> Option<LabelFrame> { self.0.pop() } @@ -36,7 +41,7 @@ impl Blocks { } #[derive(Debug, Clone)] -pub(crate) struct BlockFrame { +pub(crate) struct LabelFrame { // position of the instruction pointer when the block was entered pub(crate) instr_ptr: usize, // position of the end instruction of the block @@ -45,12 +50,12 @@ pub(crate) struct BlockFrame { // position of the stack pointer when the block was entered pub(crate) stack_ptr: usize, pub(crate) args: BlockArgs, - pub(crate) block: BlockFrameInner, + pub(crate) ty: BlockType, } #[derive(Debug, Copy, Clone)] #[allow(dead_code)] -pub(crate) enum BlockFrameInner { +pub(crate) enum BlockType { Loop, If, Else, diff --git a/crates/tinywasm/src/runtime/stack/call_stack.rs b/crates/tinywasm/src/runtime/stack/call_stack.rs index 0fc1d12..3005953 100644 --- a/crates/tinywasm/src/runtime/stack/call_stack.rs +++ b/crates/tinywasm/src/runtime/stack/call_stack.rs @@ -1,9 +1,9 @@ -use crate::{runtime::RawWasmValue, Error, Result}; +use crate::{runtime::RawWasmValue, BlockType, Error, Result}; use alloc::{boxed::Box, vec::Vec}; -use log::info; +use log::{debug, info}; use tinywasm_types::{ValType, WasmValue}; -use super::blocks::Blocks; +use super::blocks::Labels; // minimum call stack size const CALL_STACK_SIZE: usize = 1024; @@ -73,7 +73,7 @@ pub(crate) struct CallFrame { pub(crate) instr_ptr: usize, pub(crate) func_ptr: usize, - pub(crate) block_frames: Blocks, + pub(crate) labels: Labels, pub(crate) locals: Box<[RawWasmValue]>, pub(crate) local_count: usize, } @@ -82,18 +82,42 @@ impl CallFrame { /// Break to a block at the given index (relative to the current frame) #[inline] pub(crate) fn break_to(&mut self, break_to_relative: u32, value_stack: &mut super::ValueStack) -> Result<()> { - info!("we're in block_index: {}", self.block_frames.len()); - info!("block_frames: {:?}", self.block_frames); - info!("break_to_relative: {}", break_to_relative); - - let block_frame = self - .block_frames + let current_label = self.labels.top().ok_or(Error::LabelStackUnderflow)?; + let break_to = self + .labels .get_relative_to_top(break_to_relative as usize) - .ok_or(Error::BlockStackUnderflow)?; + .ok_or(Error::LabelStackUnderflow)?; + + info!("current label: {:?}", current_label); + info!("we're breaking to: {:?} ?", break_to); + + // instr_ptr points to the label instruction, but the next step + // will increment it by 1 since we're changing the "current" instr_ptr + match break_to.ty { + BlockType::Loop => { + // this is a loop, so we want to jump back to the start of the loop + self.instr_ptr = break_to.instr_ptr; + value_stack.trim(break_to.stack_ptr); + + // we also want to trim the label stack to the loop (but not including the loop) + self.labels.trim(self.labels.len() - break_to_relative as usize); + } + BlockType::Block => { + debug!("current instr_ptr: {}", self.instr_ptr); - info!("so we're breaking to: {:?} ?", block_frame); + // this is a block, so we want to jump to the end of the block + self.instr_ptr = break_to.end_instr_ptr; + value_stack.trim(break_to.stack_ptr); - todo!("break based on the type of the block we're breaking to"); + // we also want to trim the label stack, including the block + self.labels.trim(self.labels.len() - break_to_relative as usize + 1); + + debug!("break_to.end_instr_ptr: {}", self.instr_ptr); + + panic!() + } + _ => unimplemented!("break to block type: {:?}", current_label.ty), + } // self.instr_ptr = block_frame.instr_ptr; // value_stack.trim(block_frame.stack_ptr); @@ -121,7 +145,7 @@ impl CallFrame { func_ptr, local_count: locals.len(), locals: locals.into_boxed_slice(), - block_frames: Blocks::default(), + labels: Labels::default(), } } diff --git a/examples/wasm/loop.wat b/examples/wasm/loop.wat index 6224ea0..0dcd191 100644 --- a/examples/wasm/loop.wat +++ b/examples/wasm/loop.wat @@ -1,43 +1,3 @@ -;; (module -;; (func $test (export "test") (result i32) -;; (local i32) ;; Local 0: Counter for the outer loop -;; (local i32) ;; Local 1: Counter for the inner loop -;; (local i32) ;; Local 2: Result variable - -;; ;; Initialize variables -;; (local.set 0 (i32.const 0)) ;; Initialize outer loop counter -;; (local.set 1 (i32.const 0)) ;; Initialize inner loop counter -;; (local.set 2 (i32.const 0)) ;; Initialize result variable - -;; (block $outer ;; Outer loop label -;; (loop $outer_loop -;; (local.set 1 (i32.const 5)) ;; Reset inner loop counter for each iteration of the outer loop - -;; (block $inner ;; Inner loop label -;; (loop $inner_loop -;; (br_if $inner (i32.eqz (local.get 1))) ;; Break to $inner if inner loop counter is zero - -;; ;; Computation: Adding product of counters to the result -;; (local.set 2 (i32.add (local.get 2) (i32.mul (local.get 0) (local.get 1)))) - -;; ;; Decrement inner loop counter -;; (local.set 1 (i32.sub (local.get 1) (i32.const 1))) -;; ) -;; ) - -;; ;; Increment outer loop counter -;; (local.set 0 (i32.add (local.get 0) (i32.const 1))) - -;; ;; Break condition for outer loop: break if outer loop counter >= 5 -;; (br_if $outer (i32.ge_s (local.get 0) (i32.const 5))) -;; ) -;; ) - -;; ;; Return the result -;; (local.get 2) -;; ) -;; ) - (module (func $loop_test (export "loop_test") (result i32) (local i32) ;; Local 0: Counter @@ -57,4 +17,68 @@ ;; Return the counter value (local.get 0) ) + + (func $loop_test3 (export "loop_test3") (result i32) + (local i32) ;; Local 0: Counter + + ;; Initialize the counter + (local.set 0 (i32.const 0)) + + ;; Loop starts here + (block $exit_loop ;; Label for exiting the loop + (loop $my_loop + ;; Increment the counter + (local.set 0 (i32.add (local.get 0) (i32.const 1))) + + ;; Prepare an index for br_table + ;; Here, we use the counter, but you could modify this + ;; For simplicity, 0 will continue the loop, any other value will exit + (local.get 0) + (i32.const 10) + (i32.lt_s) + (br_table $my_loop $exit_loop) + ) + ) + + ;; Return the counter value + (local.get 0) + ) + + (func $calculate (export "loop_test2") (result i32) + (local i32) ;; Local 0: Counter for the outer loop + (local i32) ;; Local 1: Counter for the inner loop + (local i32) ;; Local 2: Result variable + + ;; Initialize variables + (local.set 0 (i32.const 0)) ;; Initialize outer loop counter + (local.set 1 (i32.const 0)) ;; Initialize inner loop counter + (local.set 2 (i32.const 0)) ;; Initialize result variable + + (block $outer ;; Outer loop label + (loop $outer_loop + (local.set 1 (i32.const 5)) ;; Reset inner loop counter for each iteration of the outer loop + + (block $inner ;; Inner loop label + (loop $inner_loop + (br_if $inner (i32.eqz (local.get 1))) ;; Break to $inner if inner loop counter is zero + + ;; Computation: Adding product of counters to the result + (local.set 2 (i32.add (local.get 2) (i32.mul (local.get 0) (local.get 1)))) + + ;; Decrement inner loop counter + (local.set 1 (i32.sub (local.get 1) (i32.const 1))) + ) + ) + + ;; Increment outer loop counter + (local.set 0 (i32.add (local.get 0) (i32.const 1))) + + ;; Break condition for outer loop: break if outer loop counter >= 5 + (br_if $outer (i32.ge_s (local.get 0) (i32.const 5))) + ) + ) + + ;; Return the result + (local.get 2) + ) )
\ No newline at end of file |