All roads lead to Rome: a little coding challenge

[dmsc]

Hi!

When writing my FastBasic VM, I discovered that the generated code was much faster and smaller by using a register for the TOP-OF-STACK (currently the A and X registers hold the 16-bit TOS), this allows to generate code like:

Code: Select all

  LDA #12
  JSR PUSH_BYTE  ; push #12 to the stack
  LDA #2
  LDX #1
  JSR ADD        ; Adds 258 ($102) to 12, result is 270 in A/X

In FastBasic the priority is code size over speed, with an indirectly threaded interpreter, so in reality the above is bytecode only: "LOAD_BYTE", #12, "PUSH", "LOAD_WORD", #2, #1, "ADD", 7 bytes only for the code, but I toyed with a compiler that produced the code above.

To allow 8/16 bit values, PUSH_BYTE is "LDX #0" followed by the PUSH_WORD code, same "ADD_BYTE" is "LDX #0" followed by "ADD" code, etc.

Have Fun!

[resman]

To expand little on what both drogon and dmsc wrote, PLASMA 2.0 byte code was expanded to include immediate forms of many operations. A peephole optimizer was added to the compiler that combined many simple sequences into the new byte codes. By looking at the output of the compiler for a bunch of different modules, there were sequences that made obvious choices for new byte codes. The PLASMA optimizer ended up being pretty comprehensive, but the biggest win were the simple two operation sequences, usually involving literals.

Then, during runtime, the JIT compiler converts byte code into machine code bye doing something similar to what dmsc mentioned, only going further by in-lining all simple operations and keeping track of the virtual data stack index so the X register doesn't get manically INXed and DEXed.

Looking at Taliforth, it appears only the X register is needed to index the data stack, so A and Y are available to use between subroutine calls. Extending the compiler to include a simple peephole optimizer and in-lining some operations could really improve both size and speed.

[pdragon]

peephole optimization seems like the way to go. i guess my "literal then plus" example is a special case of that.

Tali already has 'native compile' parameter to control inline vs jsr. In my case when I care mostly about space I use 0 to force almost everything as JSR, which makes it easy to look for common JSR P / JSR Q pairs which can be turned into a JSR P+Q.

I've done a bit of that by hand but automating seems like an interesting route. So my example above would be JSR LIT lo hi / JSR Q => JSR LIT+Q lo hi

[dmsc]

Hi!

resman wrote:

To expand little on what both drogon and dmsc wrote, PLASMA 2.0 byte code was expanded to include immediate forms of many operations. A peephole optimizer was added to the compiler that combined many simple sequences into the new byte codes. By looking at the output of the compiler for a bunch of different modules, there were sequences that made obvious choices for new byte codes. The PLASMA optimizer ended up being pretty comprehensive, but the biggest win were the simple two operation sequences, usually involving literals.

Yes, FastBasic also has a peephole optimizer. A big win was adding a token for "ADD VAR" that replaces "PUSH / LOAD_VAR / ADD", as this was a very common operation - specially on array indexing (the address of "A(B)" is "A + 2 * B" or "LOAD_VAR B / SHIFT_LEFT / ADD_VAR A").

Have Fun!