pref: optimize loops

Signed-off-by: Henry Gressmann <mail@henrygressmann.de>

4 files changed, 27 insertions, 18 deletions

diff --git a/benches/fibonacci.rs b/benches/fibonacci.rs
index 7ccde02..5d8a0bd 100644
--- a/benches/fibonacci.rs
+++ b/benches/fibonacci.rs
@@ -1,19 +1,19 @@
 mod util;
-use criterion::{criterion_group, criterion_main, Criterion};
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
 use tinywasm::types::TinyWasmModule;
 use util::tinywasm_module;
 
-fn run_tinywasm(module: TinyWasmModule) {
+fn run_tinywasm(module: TinyWasmModule, iterations: i32) {
     use tinywasm::*;
     let module = Module::from(module);
     let mut store = Store::default();
     let imports = Imports::default();
     let instance = ModuleInstance::instantiate(&mut store, module, Some(imports)).expect("instantiate");
     let hello = instance.exported_func::<i32, i32>(&mut store, "fibonacci").expect("exported_func");
-    hello.call(&mut store, 28).expect("call");
+    hello.call(&mut store, iterations).expect("call");
 }
 
-fn run_wasmi() {
+fn run_wasmi(iterations: i32) {
     use wasmi::*;
     let engine = Engine::default();
     let module = wasmi::Module::new(&engine, FIBONACCI).expect("wasmi::Module::new");
@@ -21,7 +21,7 @@ fn run_wasmi() {
     let linker = <Linker<()>>::new(&engine);
     let instance = linker.instantiate(&mut store, &module).expect("instantiate").start(&mut store).expect("start");
     let hello = instance.get_typed_func::<i32, i32>(&mut store, "fibonacci").expect("get_typed_func");
-    hello.call(&mut store, 28).expect("call");
+    hello.call(&mut store, iterations).expect("call");
 }
 
 const FIBONACCI: &[u8] = include_bytes!("../examples/rust/out/fibonacci.wasm");
@@ -29,8 +29,8 @@ fn criterion_benchmark(c: &mut Criterion) {
     let module = tinywasm_module(FIBONACCI);
 
     let mut group = c.benchmark_group("fibonacci");
-    group.bench_function("tinywasm", |b| b.iter(|| run_tinywasm(module.clone())));
-    group.bench_function("wasmi", |b| b.iter(|| run_wasmi()));
+    group.bench_function("tinywasm", |b| b.iter(|| run_tinywasm(module.clone(), black_box(50))));
+    group.bench_function("wasmi", |b| b.iter(|| run_wasmi(black_box(50))));
 }
 
 criterion_group!(
diff --git a/crates/tinywasm/src/runtime/stack/call_stack.rs b/crates/tinywasm/src/runtime/stack/call_stack.rs
index 9ba6ad2..dbe420d 100644
--- a/crates/tinywasm/src/runtime/stack/call_stack.rs
+++ b/crates/tinywasm/src/runtime/stack/call_stack.rs
@@ -77,15 +77,20 @@ impl CallFrame {
         // 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
-                // We also want to push the params to the stack
-                value_stack.break_to(break_to.stack_ptr, break_to.params);
-
                 self.instr_ptr = break_to.instr_ptr;
 
-                // we also want to trim the label stack to the loop (but not including the loop)
-                self.labels.truncate(self.labels.len() - break_to_relative as usize);
+                // check if we're breaking to the loop
+                if break_to_relative != 0 {
+                    // this is a loop, so we want to jump back to the start of the loop
+                    // We also want to push the params to the stack
+                    value_stack.break_to(break_to.stack_ptr, break_to.params);
+
+                    // we also want to trim the label stack to the loop (but not including the loop)
+                    self.labels.truncate(self.labels.len() - break_to_relative as usize);
+                    return Some(());
+                }
             }
+
             BlockType::Block | BlockType::If | BlockType::Else => {
                 // this is a block, so we want to jump to the next instruction after the block ends
                 // We also want to push the block's results to the stack
diff --git a/crates/tinywasm/tests/generated/2.0.csv b/crates/tinywasm/tests/generated/2.0.csv
index 0d233ee..b5ea4cc 100644
--- a/crates/tinywasm/tests/generated/2.0.csv
+++ b/crates/tinywasm/tests/generated/2.0.csv
@@ -1,2 +1,2 @@
 0.3.0,26722,1161,[{"name":"address.wast","passed":260,"failed":0},{"name":"align.wast","passed":156,"failed":0},{"name":"binary-leb128.wast","passed":91,"failed":0},{"name":"binary.wast","passed":112,"failed":0},{"name":"block.wast","passed":223,"failed":0},{"name":"br.wast","passed":97,"failed":0},{"name":"br_if.wast","passed":118,"failed":0},{"name":"br_table.wast","passed":174,"failed":0},{"name":"bulk.wast","passed":8,"failed":109},{"name":"call.wast","passed":91,"failed":0},{"name":"call_indirect.wast","passed":170,"failed":0},{"name":"comments.wast","passed":8,"failed":0},{"name":"const.wast","passed":778,"failed":0},{"name":"conversions.wast","passed":619,"failed":0},{"name":"custom.wast","passed":11,"failed":0},{"name":"data.wast","passed":61,"failed":0},{"name":"elem.wast","passed":98,"failed":1},{"name":"endianness.wast","passed":69,"failed":0},{"name":"exports.wast","passed":96,"failed":0},{"name":"f32.wast","passed":2514,"failed":0},{"name":"f32_bitwise.wast","passed":364,"failed":0},{"name":"f32_cmp.wast","passed":2407,"failed":0},{"name":"f64.wast","passed":2514,"failed":0},{"name":"f64_bitwise.wast","passed":364,"failed":0},{"name":"f64_cmp.wast","passed":2407,"failed":0},{"name":"fac.wast","passed":8,"failed":0},{"name":"float_exprs.wast","passed":900,"failed":0},{"name":"float_literals.wast","passed":163,"failed":0},{"name":"float_memory.wast","passed":90,"failed":0},{"name":"float_misc.wast","passed":441,"failed":0},{"name":"forward.wast","passed":5,"failed":0},{"name":"func.wast","passed":172,"failed":0},{"name":"func_ptrs.wast","passed":36,"failed":0},{"name":"global.wast","passed":110,"failed":0},{"name":"i32.wast","passed":460,"failed":0},{"name":"i64.wast","passed":416,"failed":0},{"name":"if.wast","passed":241,"failed":0},{"name":"imports.wast","passed":171,"failed":12},{"name":"inline-module.wast","passed":1,"failed":0},{"name":"int_exprs.wast","passed":108,"failed":0},{"name":"int_literals.wast","passed":51,"failed":0},{"name":"labels.wast","passed":29,"failed":0},{"name":"left-to-right.wast","passed":96,"failed":0},{"name":"linking.wast","passed":132,"failed":0},{"name":"load.wast","passed":97,"failed":0},{"name":"local_get.wast","passed":36,"failed":0},{"name":"local_set.wast","passed":53,"failed":0},{"name":"local_tee.wast","passed":97,"failed":0},{"name":"loop.wast","passed":120,"failed":0},{"name":"memory.wast","passed":79,"failed":0},{"name":"memory_copy.wast","passed":3928,"failed":522},{"name":"memory_fill.wast","passed":64,"failed":36},{"name":"memory_grow.wast","passed":96,"failed":0},{"name":"memory_init.wast","passed":177,"failed":63},{"name":"memory_redundancy.wast","passed":8,"failed":0},{"name":"memory_size.wast","passed":42,"failed":0},{"name":"memory_trap.wast","passed":182,"failed":0},{"name":"names.wast","passed":486,"failed":0},{"name":"nop.wast","passed":88,"failed":0},{"name":"ref_func.wast","passed":9,"failed":8},{"name":"ref_is_null.wast","passed":4,"failed":12},{"name":"ref_null.wast","passed":1,"failed":2},{"name":"return.wast","passed":84,"failed":0},{"name":"select.wast","passed":148,"failed":0},{"name":"skip-stack-guard-page.wast","passed":11,"failed":0},{"name":"stack.wast","passed":7,"failed":0},{"name":"start.wast","passed":20,"failed":0},{"name":"store.wast","passed":68,"failed":0},{"name":"switch.wast","passed":28,"failed":0},{"name":"table-sub.wast","passed":2,"failed":0},{"name":"table.wast","passed":19,"failed":0},{"name":"table_copy.wast","passed":1613,"failed":115},{"name":"table_fill.wast","passed":23,"failed":22},{"name":"table_get.wast","passed":10,"failed":6},{"name":"table_grow.wast","passed":21,"failed":29},{"name":"table_init.wast","passed":594,"failed":186},{"name":"table_set.wast","passed":19,"failed":7},{"name":"table_size.wast","passed":8,"failed":31},{"name":"token.wast","passed":58,"failed":0},{"name":"traps.wast","passed":36,"failed":0},{"name":"type.wast","passed":3,"failed":0},{"name":"unreachable.wast","passed":64,"failed":0},{"name":"unreached-invalid.wast","passed":118,"failed":0},{"name":"unreached-valid.wast","passed":7,"failed":0},{"name":"unwind.wast","passed":50,"failed":0},{"name":"utf8-custom-section-id.wast","passed":176,"failed":0},{"name":"utf8-import-field.wast","passed":176,"failed":0},{"name":"utf8-import-module.wast","passed":176,"failed":0},{"name":"utf8-invalid-encoding.wast","passed":176,"failed":0}]
-0.4.0-alpha.0,26841,1042,[{"name":"address.wast","passed":260,"failed":0},{"name":"align.wast","passed":156,"failed":0},{"name":"binary-leb128.wast","passed":91,"failed":0},{"name":"binary.wast","passed":112,"failed":0},{"name":"block.wast","passed":223,"failed":0},{"name":"br.wast","passed":97,"failed":0},{"name":"br_if.wast","passed":118,"failed":0},{"name":"br_table.wast","passed":174,"failed":0},{"name":"bulk.wast","passed":8,"failed":109},{"name":"call.wast","passed":91,"failed":0},{"name":"call_indirect.wast","passed":170,"failed":0},{"name":"comments.wast","passed":8,"failed":0},{"name":"const.wast","passed":778,"failed":0},{"name":"conversions.wast","passed":619,"failed":0},{"name":"custom.wast","passed":11,"failed":0},{"name":"data.wast","passed":61,"failed":0},{"name":"elem.wast","passed":99,"failed":0},{"name":"endianness.wast","passed":69,"failed":0},{"name":"exports.wast","passed":96,"failed":0},{"name":"f32.wast","passed":2514,"failed":0},{"name":"f32_bitwise.wast","passed":364,"failed":0},{"name":"f32_cmp.wast","passed":2407,"failed":0},{"name":"f64.wast","passed":2514,"failed":0},{"name":"f64_bitwise.wast","passed":364,"failed":0},{"name":"f64_cmp.wast","passed":2407,"failed":0},{"name":"fac.wast","passed":8,"failed":0},{"name":"float_exprs.wast","passed":900,"failed":0},{"name":"float_literals.wast","passed":163,"failed":0},{"name":"float_memory.wast","passed":90,"failed":0},{"name":"float_misc.wast","passed":441,"failed":0},{"name":"forward.wast","passed":5,"failed":0},{"name":"func.wast","passed":172,"failed":0},{"name":"func_ptrs.wast","passed":36,"failed":0},{"name":"global.wast","passed":110,"failed":0},{"name":"i32.wast","passed":460,"failed":0},{"name":"i64.wast","passed":416,"failed":0},{"name":"if.wast","passed":241,"failed":0},{"name":"imports.wast","passed":183,"failed":0},{"name":"inline-module.wast","passed":1,"failed":0},{"name":"int_exprs.wast","passed":108,"failed":0},{"name":"int_literals.wast","passed":51,"failed":0},{"name":"labels.wast","passed":29,"failed":0},{"name":"left-to-right.wast","passed":96,"failed":0},{"name":"linking.wast","passed":132,"failed":0},{"name":"load.wast","passed":97,"failed":0},{"name":"local_get.wast","passed":36,"failed":0},{"name":"local_set.wast","passed":53,"failed":0},{"name":"local_tee.wast","passed":97,"failed":0},{"name":"loop.wast","passed":120,"failed":0},{"name":"memory.wast","passed":79,"failed":0},{"name":"memory_copy.wast","passed":3928,"failed":522},{"name":"memory_fill.wast","passed":64,"failed":36},{"name":"memory_grow.wast","passed":96,"failed":0},{"name":"memory_init.wast","passed":177,"failed":63},{"name":"memory_redundancy.wast","passed":8,"failed":0},{"name":"memory_size.wast","passed":42,"failed":0},{"name":"memory_trap.wast","passed":182,"failed":0},{"name":"names.wast","passed":486,"failed":0},{"name":"nop.wast","passed":88,"failed":0},{"name":"ref_func.wast","passed":9,"failed":8},{"name":"ref_is_null.wast","passed":4,"failed":12},{"name":"ref_null.wast","passed":1,"failed":2},{"name":"return.wast","passed":84,"failed":0},{"name":"select.wast","passed":148,"failed":0},{"name":"skip-stack-guard-page.wast","passed":11,"failed":0},{"name":"stack.wast","passed":7,"failed":0},{"name":"start.wast","passed":20,"failed":0},{"name":"store.wast","passed":68,"failed":0},{"name":"switch.wast","passed":28,"failed":0},{"name":"table-sub.wast","passed":2,"failed":0},{"name":"table.wast","passed":19,"failed":0},{"name":"table_copy.wast","passed":1613,"failed":115},{"name":"table_fill.wast","passed":23,"failed":22},{"name":"table_get.wast","passed":10,"failed":6},{"name":"table_grow.wast","passed":21,"failed":29},{"name":"table_init.wast","passed":700,"failed":80},{"name":"table_set.wast","passed":19,"failed":7},{"name":"table_size.wast","passed":8,"failed":31},{"name":"token.wast","passed":58,"failed":0},{"name":"traps.wast","passed":36,"failed":0},{"name":"type.wast","passed":3,"failed":0},{"name":"unreachable.wast","passed":64,"failed":0},{"name":"unreached-invalid.wast","passed":118,"failed":0},{"name":"unreached-valid.wast","passed":7,"failed":0},{"name":"unwind.wast","passed":50,"failed":0},{"name":"utf8-custom-section-id.wast","passed":176,"failed":0},{"name":"utf8-import-field.wast","passed":176,"failed":0},{"name":"utf8-import-module.wast","passed":176,"failed":0},{"name":"utf8-invalid-encoding.wast","passed":176,"failed":0}]
+0.4.0-alpha.0,26861,1022,[{"name":"address.wast","passed":260,"failed":0},{"name":"align.wast","passed":156,"failed":0},{"name":"binary-leb128.wast","passed":91,"failed":0},{"name":"binary.wast","passed":112,"failed":0},{"name":"block.wast","passed":223,"failed":0},{"name":"br.wast","passed":97,"failed":0},{"name":"br_if.wast","passed":118,"failed":0},{"name":"br_table.wast","passed":174,"failed":0},{"name":"bulk.wast","passed":8,"failed":109},{"name":"call.wast","passed":91,"failed":0},{"name":"call_indirect.wast","passed":170,"failed":0},{"name":"comments.wast","passed":8,"failed":0},{"name":"const.wast","passed":778,"failed":0},{"name":"conversions.wast","passed":619,"failed":0},{"name":"custom.wast","passed":11,"failed":0},{"name":"data.wast","passed":61,"failed":0},{"name":"elem.wast","passed":99,"failed":0},{"name":"endianness.wast","passed":69,"failed":0},{"name":"exports.wast","passed":96,"failed":0},{"name":"f32.wast","passed":2514,"failed":0},{"name":"f32_bitwise.wast","passed":364,"failed":0},{"name":"f32_cmp.wast","passed":2407,"failed":0},{"name":"f64.wast","passed":2514,"failed":0},{"name":"f64_bitwise.wast","passed":364,"failed":0},{"name":"f64_cmp.wast","passed":2407,"failed":0},{"name":"fac.wast","passed":8,"failed":0},{"name":"float_exprs.wast","passed":900,"failed":0},{"name":"float_literals.wast","passed":163,"failed":0},{"name":"float_memory.wast","passed":90,"failed":0},{"name":"float_misc.wast","passed":441,"failed":0},{"name":"forward.wast","passed":5,"failed":0},{"name":"func.wast","passed":172,"failed":0},{"name":"func_ptrs.wast","passed":36,"failed":0},{"name":"global.wast","passed":110,"failed":0},{"name":"i32.wast","passed":460,"failed":0},{"name":"i64.wast","passed":416,"failed":0},{"name":"if.wast","passed":241,"failed":0},{"name":"imports.wast","passed":183,"failed":0},{"name":"inline-module.wast","passed":1,"failed":0},{"name":"int_exprs.wast","passed":108,"failed":0},{"name":"int_literals.wast","passed":51,"failed":0},{"name":"labels.wast","passed":29,"failed":0},{"name":"left-to-right.wast","passed":96,"failed":0},{"name":"linking.wast","passed":132,"failed":0},{"name":"load.wast","passed":97,"failed":0},{"name":"local_get.wast","passed":36,"failed":0},{"name":"local_set.wast","passed":53,"failed":0},{"name":"local_tee.wast","passed":97,"failed":0},{"name":"loop.wast","passed":120,"failed":0},{"name":"memory.wast","passed":79,"failed":0},{"name":"memory_copy.wast","passed":3928,"failed":522},{"name":"memory_fill.wast","passed":64,"failed":36},{"name":"memory_grow.wast","passed":96,"failed":0},{"name":"memory_init.wast","passed":177,"failed":63},{"name":"memory_redundancy.wast","passed":8,"failed":0},{"name":"memory_size.wast","passed":42,"failed":0},{"name":"memory_trap.wast","passed":182,"failed":0},{"name":"names.wast","passed":486,"failed":0},{"name":"nop.wast","passed":88,"failed":0},{"name":"ref_func.wast","passed":9,"failed":8},{"name":"ref_is_null.wast","passed":4,"failed":12},{"name":"ref_null.wast","passed":1,"failed":2},{"name":"return.wast","passed":84,"failed":0},{"name":"select.wast","passed":148,"failed":0},{"name":"skip-stack-guard-page.wast","passed":11,"failed":0},{"name":"stack.wast","passed":7,"failed":0},{"name":"start.wast","passed":20,"failed":0},{"name":"store.wast","passed":68,"failed":0},{"name":"switch.wast","passed":28,"failed":0},{"name":"table-sub.wast","passed":2,"failed":0},{"name":"table.wast","passed":19,"failed":0},{"name":"table_copy.wast","passed":1613,"failed":115},{"name":"table_fill.wast","passed":23,"failed":22},{"name":"table_get.wast","passed":10,"failed":6},{"name":"table_grow.wast","passed":21,"failed":29},{"name":"table_init.wast","passed":720,"failed":60},{"name":"table_set.wast","passed":19,"failed":7},{"name":"table_size.wast","passed":8,"failed":31},{"name":"token.wast","passed":58,"failed":0},{"name":"traps.wast","passed":36,"failed":0},{"name":"type.wast","passed":3,"failed":0},{"name":"unreachable.wast","passed":64,"failed":0},{"name":"unreached-invalid.wast","passed":118,"failed":0},{"name":"unreached-valid.wast","passed":7,"failed":0},{"name":"unwind.wast","passed":50,"failed":0},{"name":"utf8-custom-section-id.wast","passed":176,"failed":0},{"name":"utf8-import-field.wast","passed":176,"failed":0},{"name":"utf8-import-module.wast","passed":176,"failed":0},{"name":"utf8-invalid-encoding.wast","passed":176,"failed":0}]
diff --git a/examples/rust/src/fibonacci.rs b/examples/rust/src/fibonacci.rs
index 7493132..3e4be73 100644
--- a/examples/rust/src/fibonacci.rs
+++ b/examples/rust/src/fibonacci.rs
@@ -8,10 +8,14 @@ fn panic(_info: &core::panic::PanicInfo) -> ! {
 }
 
 #[no_mangle]
-// The rust compiler will convert this to an iterative algorithm.
 pub extern "C" fn fibonacci(n: i32) -> i32 {
-    if n <= 1 {
-        return n;
+    let mut sum = 0;
+    let mut last = 0;
+    let mut curr = 1;
+    for _i in 1..n {
+        sum = last + curr;
+        last = curr;
+        curr = sum;
     }
-    fibonacci(n - 1) + fibonacci(n - 2)
+    sum
 }