B4A Library TinyVM - 64Bit Virtual Machine

wonder

Expert
Licensed User

TinyVM is an experimental Virtual Machine implementation written in C.

//VM control
HALT
PAUSE

//Stack / Register management
PUSH
PUSHINT
PUSHFLOAT
POP
CLR
SET
MOV
SWAP
RSP

//Int64 stack operations
ADD
SUB
MUL
DIV
MOD
POWER
SQRT
CHS
TOFLOAT

//Float64 stack operations
FADD
FSUB
FMUL
FDIV
FPOWER
FSQRT
FCHS
FCMP
TOINT

//Logical stack operations
AND
OR
NEG
RSHIFT
LSHIFT
XOR
CMP

//Program flow control
JMP
JNE
JEQ
JG
JL
JGE
JLE

//Int64 register / register operations
RADD
RSUB
RMUL
RDIV
RMOD
RPOWER
RSQRT
RCHS
RCMP
RINC
RDEC
RTOFLOAT

//Int64 register / value operations
RCMPV
RADDV
RSUBV
RMULV
RDIVV
RMODV
RPOWERV

//Float64 register / register operations
RFADD
RFSUB
RFMUL
RFDIV
RFPOWER
RFSQRT
RFCHS
RFCMP
RTOINT

//Float64 register / value operations
RFCMPV
RFADDV
RFSUBV
RFMULV
RFDIVV
RFPOWERV

//Logical operations [Register vs Register]
RAND
ROR
RNEG
RRSHIFT
RLSHIFT
RXOR

//Logical operations [Register vs Value]
RANDV
RORV
RXORV

Compiling this lib with NLG 3.00+:
1. Copy-paste the TinyVM project path into the "C/C++ Project" field in NLG and click "Load".
2. Click "Generate B4A Library"
The library source files used for compilation are 'TinyVM.cpp' and 'TinyVM.h'.

Tiny example:
B4X:
Dim VM as TinyVM
Dim VMStack() as Long

VM.Initialize
VM.SetStackLength(1024)
VM.Compile(File.ReadString(File.DirAssets, "primes.asm"))
VM.Execute : VMStack = VM.StackAsLongArray
VM.Kill

For Each entry As Long In VMStack
    Log(entry)
Next

';---------------------------------------------------------------------
';PROGRAM: primes.asm                        
';---------------------------------------------------------------------
'START:                                      
'         set             0        r1 ;     a = 0
'LOOP_0:                              ;     do {
'         rcmpv     r1,1000           ;         if (a >= 1,000) {
'         jeq           END           ;             goto end }
'         rcmpv        r1,2           ;         if (a == 2) {
'         jeq      RETURN_1           ;             goto return true}
'         rcmpv        r1,1           ;         if (a <= 1) {
'         jle      RETURN_0           ;             goto return false }
'         rmodv        r1,2        r3 ;         r3 = (a % 2)
'         rcmpv        r3,0           ;         if (r3 == 0) {
'         jeq      RETURN_0           ;             goto return false }
'         rsqrt          r1        r4 ;         max = sqrt(a)
'         set             3        r2 ;         n = 3
'LOOP_1:                              ;         do {
'         rcmp        r2,r4           ;             if (n > max) {
'         jg       RETURN_1           ;                 goto return true }
'         rmod        r1,r2        r3 ;             res = (a % n)
'         rcmpv        r3,0           ;             if (res == 0) {
'         jeq      RETURN_0           ;                 goto return false }
'         rinc         r2,2           ;             n += 2
'         jmp        LOOP_1           ;         } goto loop 1
'                                     ;     }
';---------------------------------------------------------------------
'RETURN_0:                                  
'         rinc         r1,1           ;     i++;
'         jmp        LOOP_0           ;     goto loop 0
';---------------------------------------------------------------------
'RETURN_1:                                  
'         push           r1           ;     stack.push(r1)
'         rinc         r1,1           ;     i++;
'         jmp        LOOP_0           ;     goto loop_0
';---------------------------------------------------------------------
'END:                                        
';---------------------------------------------------------------------
 

Attachments

Last edited:

Daniel-White

Active Member
Licensed User
Ninja Dynamic, I enjoyed years ago work with Assembly intel, I prefer to make a stupid question and kill my curiosity.

Are you working with Lego Mindstorms right? I don't know anything about it, so with this library TinyVM, the idea is ??? develop something in assembly and run in the TinyVM ? what can we achieve with it?
 

wonder

Expert
Licensed User
Hi! :)

Well, what purpose does it serve? That's a hell of a good question! :D

I created this lib mainly for three reasons:
- I wanted to know if I was capable of writing a VM from scratch
- Improve my C coding skills
- Having a way of implementing user-scripting in my games.

I'll try to document it properly until the end of next week (editing the first post).
Hopefully I'll come-up with one or two interesting examples.

Are you working with Lego Mindstorms right
Mmmm... I'm not familiar with Lego Mindstorms, so no.
 

stanmiller

Active Member
Licensed User
@wonder Interesting project. Often these simple VM's are implemented with a switch/case for "goto" performance between instructions. I see you're using an array of function pointers. Was there a specific design choice that led you down that path?

Also, I see you have allocated the VM in a structure. That makes it easy to implement multitasking. You would allocate a VM for each 'process', store them in a linklist of VM structs, then taskswitch with something like:
B4X:
currentVM = currentVM->nextProcess;
 
Last edited:

wonder

Expert
Licensed User
@wonder Interesting project.
Thank you! The inspiration came from your project! :)

I see you're using an array of function pointers. Was there a specific design choice that led you down that path?
I chose this path because I really wanted / needed to get comfortable with pointers to functions... Also, in principle, it should be faster, right?

That makes it easy to implement multitasking.
Yes, I want to keep that door open.

Thank you so much for your interest! ^__^
Feel free to explore, modify and utilize my code!

EDIT:
Minor update:
- Removed some hardcoded values
- Fixed function names
- Fixed minor bugs
- Added new instruction CLR (clear registers)
 
Last edited:

wonder

Expert
Licensed User

stanmiller

Active Member
Licensed User
Thank you! The inspiration came from your project! :)
I chose this path because I really wanted / needed to get comfortable with pointers to functions... Also, in principle, it should be faster, right?
Creating a compiler/vm is a good project to get comfortable with lots of things. The more you learn about the inner workings (of really anything) the better you understand the overlying subject.:)

A switch/case will be faster as it compiles down to a jump instruction. The case value becomes the offset (jump to IP+<casevalue>). Thus it's important to enumerate the instructions sequentially. Unlike C and Java, B4X's implementation of select/case doesn't follow a jump+offset convention. Internally it's more like an if/then.

Implementing the VM instructions as function pointers will likely require several steps. The pointer has to be dereferenced and as a function a stackframe may be created despite tagging them inline adding more overhead. When in doubt, compile the source without optimizations and generate an assembly listing, then compare. Then do the same with optimizations enabled.

Over the years I've worked on several C compiler/VM projects. Here are a couple I drew inspiration from.

Retargetable Concurrent Small C
http://www.drdobbs.com/cpp/retargetable-concurrent-small-c/184410255

Interactive C from Randy Sargent and Fred Martin
http://handyboard.com/oldhb/software/icsource.html

What's cool about the Concurrent Small C project is that it outputs pcode then translates it to the target platform. So in essence you can toss aside the translation part and write a VM that emulates the CSC processor and instruction set.

Then the Interactive C project was a bytecode C compiler/VM from the start. Plus they implemented multi-tasking in their VM.
 
Last edited:

stanmiller

Active Member
Licensed User
Thank you so much for sharing. I'll try to write a switch/case version and benchmark it against this one. :)
If possible, could you recommend a nice disassembler for Windows?
Typically the compiler will have an option to request an assembly listing. For Visual C/C++, the option is /FA.

Visual Studio 2015 - /FA, /Fa (Listing File)
https://msdn.microsoft.com/en-us/library/367y26c6.aspx

But for a switch/case they all seem to work the same. A switch over an enumerated list of integers compiles to jumps.

For example, here's the CLR disassembly of the VM part of MteEVAL in C#.

C:\> ildasm mteEVAL.DLL



MteEVAL C# edition at GitHub
https://github.com/macthomasengineering/MteEVAL-CSharp
 
Last edited:

wonder

Expert
Licensed User
@stanmiller, done. ^_^
B4X:
Benchmark        :   Find all prime numbers between 0 and 10,000,000.
Environment      :   Android MEmu Emulator (PC)
Old algorithm    :   ~46 seconds
New algorithm    :   ~30 seconds
35% faster!!! :)

So it seems that with the switch/case, the VM works definitely faster!!
Thanks!!! :D

First post updated.
 
Last edited:
Top