From 9ebb4b9d82decbd9e8ea901e6d240e1af9f190b3 Mon Sep 17 00:00:00 2001 From: johannst Date: Wed, 11 Dec 2024 21:52:27 +0000 Subject: deploy: aedbcbf6c8e45367364a852d5b10d45b27b61c44 --- src/bf/bf.rs.html | 144 +++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 115 insertions(+), 29 deletions(-) (limited to 'src/bf') diff --git a/src/bf/bf.rs.html b/src/bf/bf.rs.html index 25b814e..9bd6202 100644 --- a/src/bf/bf.rs.html +++ b/src/bf/bf.rs.html @@ -290,7 +290,50 @@ 289 290 291 -292
//! Brainfuck VM.
+292
+293
+294
+295
+296
+297
+298
+299
+300
+301
+302
+303
+304
+305
+306
+307
+308
+309
+310
+311
+312
+313
+314
+315
+316
+317
+318
+319
+320
+321
+322
+323
+324
+325
+326
+327
+328
+329
+330
+331
+332
+333
+334
+335
//! Brainfuck VM.
 //!
 //! This example implements a simple
 //! [brainfuck](https://en.wikipedia.org/wiki/Brainfuck) interpreter
@@ -313,7 +356,9 @@
 use juicebox_asm::Runtime;
 use juicebox_asm::{Asm, Imm64, Imm8, Label, MemOp, MemOp8, Reg64, Reg8};
 
-struct BrainfuckInterp {
+// -- BRAINFUCK INTERPRETER ----------------------------------------------------
+
+struct BrainfuckInterp {
     pc: usize,
     imem: Vec<char>,
     dptr: usize,
@@ -323,8 +368,9 @@
 
 impl BrainfuckInterp {
     fn new(prog: &str) -> Result<Self, String> {
-        // Do a first pass over the bf program to filter whitespace and detect invalid tokens.
-        // Additionally validate all conditional branches, and compute their branch target.
+        // Do a first pass over the bf program to filter whitespace and detect
+        // invalid tokens. Additionally validate all conditional branches, and
+        // compute their branch target.
         let (imem, branches) = {
             // Instruction memory holding the final bf program.
             let mut imem = Vec::new();
@@ -422,7 +468,7 @@
     }
 }
 
-// -- BRAINFUCK JIT --------------------------------------------------------------
+// -- BRAINFUCK JIT ------------------------------------------------------------
 
 #[cfg(not(any(target_arch = "x86_64", target_os = "linux")))]
 compile_error!("Only supported on x86_64 with SystemV abi");
@@ -434,7 +480,8 @@
 
 impl BrainfuckJit {
     fn new(prog: &str) -> Result<Self, String> {
-        // Do a first pass over the bf program to filter whitespace and detect invalid tokens.
+        // Do a first pass over the bf program to filter whitespace and detect
+        // invalid tokens.
         let imem = prog
             .chars()
             .filter(|c| !c.is_whitespace())
@@ -460,25 +507,25 @@
 fn run_jit(prog: &str) {
     let mut vm = BrainfuckJit::new(prog).unwrap();
 
-    // Use callee saved registers to hold vm state, such that we don't
-    // need to save any state before calling out to putchar.
+    // Use callee saved registers to hold vm state, such that we don't need to
+    // save any state before calling out to putchar.
     let dmem_base = Reg64::rbx;
     let dmem_idx = Reg64::r12;
 
     let mut asm = Asm::new();
-    // Move data memory pointer (argument on jit entry) into correct
-    // register.
+    // Move data memory pointer (argument on jit entry) into correct register.
     asm.mov(dmem_base, Reg64::rdi);
     // Clear data memory index.
     asm.xor(dmem_idx, dmem_idx);
 
-    // A stack of label pairs, used to link up forward and backward
-    // jumps for a given '[]' pair.
+    // A stack of label pairs, used to link up forward and backward jumps for a
+    // given '[]' pair.
     let mut label_stack = Vec::new();
 
     // Generate code for each instruction in the bf program.
-    for insn in vm.imem {
-        match insn {
+    let mut pc = 0;
+    while pc < vm.imem.len() {
+        match vm.imem[pc] {
             '>' => {
                 // TODO: generate runtime bounds check.
                 asm.inc(dmem_idx);
@@ -488,18 +535,53 @@
                 asm.dec(dmem_idx);
             }
             '+' => {
-                asm.inc(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx)));
+                // Apply optimization to fold consecutive '+' instructions to a
+                // single add instruction during compile time.
+
+                match vm.imem[pc..].iter().take_while(|&&i| i.eq(&'+')).count() {
+                    1 => asm.inc(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx))),
+                    cnt if cnt <= i8::MAX as usize => {
+                        // For add m64, imm8, the immediate is sign-extend and
+                        // hence treated as signed.
+                        asm.add(
+                            MemOp::IndirectBaseIndex(dmem_base, dmem_idx),
+                            Imm8::from(cnt as u8),
+                        );
+
+                        // Advance pc, but account for pc increment at the end
+                        // of the loop.
+                        pc += cnt - 1;
+                    }
+                    cnt @ _ => unimplemented!("cnt={cnt} oob, add with larger imm"),
+                }
             }
             '-' => {
-                asm.dec(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx)));
+                // Apply optimization to fold consecutive '-' instructions to a
+                // single sub instruction during compile time.
+
+                match vm.imem[pc..].iter().take_while(|&&i| i.eq(&'-')).count() {
+                    1 => asm.dec(MemOp8::from(MemOp::IndirectBaseIndex(dmem_base, dmem_idx))),
+                    cnt if cnt <= i8::MAX as usize => {
+                        // For sub m64, imm8, the immediate is sign-extend and
+                        // hence treated as signed.
+                        asm.sub(
+                            MemOp::IndirectBaseIndex(dmem_base, dmem_idx),
+                            Imm8::from(cnt as u8),
+                        );
+
+                        // Advance pc, but account for pc increment at the end
+                        // of the loop.
+                        pc += cnt - 1;
+                    }
+                    cnt @ _ => unimplemented!("cnt={cnt} oob, sub with larger imm"),
+                }
             }
             '.' => {
-                // Load data memory from active cell into di register,
-                // which is the first argument register according to
-                // the SystemV abi, then call into putchar. Since we
-                // stored all out vm state in callee saved registers
-                // we don't need to save any registers before the
-                // call.
+                // Load data memory from active cell into di register, which is
+                // the first argument register according to the SystemV abi,
+                // then call into putchar. Since we stored all out vm state in
+                // callee saved registers we don't need to save any registers
+                // before the call.
                 asm.mov(Reg8::dil, MemOp::IndirectBaseIndex(dmem_base, dmem_idx));
                 asm.mov(Reg64::rax, Imm64::from(putchar as usize));
                 asm.call(Reg64::rax);
@@ -521,8 +603,8 @@
                 );
                 asm.jz(&mut label_pair.0);
 
-                // Bind label_pair.1 after the jump instruction, which
-                // will be the branch target for the matching ']'.
+                // Bind label_pair.1 after the jump instruction, which will be
+                // the branch target for the matching ']'.
                 asm.bind(&mut label_pair.1);
             }
             ']' => {
@@ -530,8 +612,7 @@
                     .pop()
                     .expect("encountered un-balanced brackets, found ']' without matching '['");
 
-                // Goto label_pair.1 if data memory at active cell is
-                // not 0.
+                // Goto label_pair.1 if data memory at active cell is not 0.
                 //   if vm.dmem[vm.dptr] != 0 goto label_pair.1
                 asm.cmp(
                     MemOp::IndirectBaseIndex(dmem_base, dmem_idx),
@@ -539,12 +620,15 @@
                 );
                 asm.jnz(&mut label_pair.1);
 
-                // Bind label_pair.0 after the jump instruction, which
-                // is the branch target for the matching '['.
+                // Bind label_pair.0 after the jump instruction, which is the
+                // branch target for the matching '['.
                 asm.bind(&mut label_pair.0);
             }
             _ => unreachable!(),
         }
+
+        // Increment pc to next instruction.
+        pc += 1;
     }
 
     // Return from bf program.
@@ -560,7 +644,9 @@
     bf_entry(&mut vm.dmem as *mut u8);
 }
 
-fn main() {
+// -- MAIN ---------------------------------------------------------------------
+
+fn main() {
     // https://en.wikipedia.org/wiki/Brainfuck#Adding_two_values
     //let inp = "++>+++++ [<+>-] ++++++++[<++++++>-]<.";
     //println!("add-print-7 (wikipedia.org) - interp");
-- 
cgit v1.2.3