grigory-rechistov / interpreters-comparison Goto Github PK

Currently the VM lacks any procedure mechanism. The task is to add implementation and tests:

1. Add a separate return stack to store addresses
2. Add new instructions:
   • call imm - pushes current PC on return stack and jumps to PC+imm
   • ret - pops new PC value from stack

Curently mprotect() used in translated fails when attempted to be executed in Cygwin build. The task is to understand why it fails and fix it, possibly by rewriting the procedure for allocation of write-executable memory.

Write a separate program that takes an assembler listing and generates a raw machine code program for the VM from it.

It should be able to:

• Process all instructions defined in the original VM spec.
• Support labels for jumps
• Provide sane error reporting for invalid inputs (line number, problem description)

Add a mechanism to count how many times each of simulated opcode got executed.

Requirements for a solution

• It should only be active when INSTR_STAT macro is defined. I.e., it should be conditionally built in.
• It should maintain an array of counters to keep statistics for individual opcodes. After every instruction is simulated, the corresponding counter should be incremented by one.
• At the end of simulation, the results table should be produced. It should look like this:

     Opcode    Count
     -------------------
     Nop       1000
     Halt         1
     Push      1234
     ...

• It can be implemented in a generic manner to support all variants of interpreters

After the implementation is ready, it will be nice to compare performance of two builds - interpreter with stats enabled and disabled, to see the performance overhead such collection creates.

Add a mechanism to count how often the simulated CPU visits different program addresses by counting PC register values.

Requirements for a solution

• It should only be active when INSTR_STAT macro is defined. I.e., it should be conditionally built in.
• It should maintain an array of counters to keep statistics for individual PC values. After every instruction is simulated, the corresponding counter for its PC should be incremented by one.
  At the end of simulation, the results table should be produced. It should look like this:

Address Count

0x0 1000
0x2 1000
0x6 1234
...

*It can be implemented in a generic manner to support all variants of interpreters

After the implementation is ready, it will be nice to compare performance of two builds - interpreter with stats enabled and disabled, to see the performance overhead such collection creates.

Add one to three programs to the suite.

1. Calculate an approximation of square root of given number by Newton-Raphson method
2. Sort an array by any known method (bubble, quicksort, heapsort etc)
3. Looking for a substring match inside a given string

Additionally, any other computationally-intensive algorithm will be good as well

Currently the VM has 18 instructions. The task is to add and test implementation of new instructions:

1. And (a b -- a & b) - logical AND
2. Or (a b -- a | b) - logical OR
3. Xor (a b -- a ^ b) - logical Exsclusive OR
4. SHL (a shift -- a << shift) - Shift left
5. SHR (a shift -- a >> shift) - Shift right
6. SQRT (x -- √x̅) - find integer square root
7. Rot ( a b c -- b c a ) - rotate three top items on the stack
8. Pick ( a0 .. an n -- a0 .. an a0 ) - pick n-th item from the stack

Currently any "unexpected" situation inside the VM (division by zero, PC address out of range etc) puts it into the Break state. This is convenient for a software VM but unrealistic for a hardware one. For some events, an exception handling mechanism can be used to give target software a chance to correct the state.

The task is to design and implement the exception handling mechanism:

1. Add a separate return stack to store the PC of instruction that caused a problem.
2. Define what method of communication for enumerating interruption events should be used (on stack? in register? by indexing the ISR address?).
3. Define where interrupt routines are placed in the program memory
4. Add a new instruction ret to pop PC from return stack
5. Add new instructions to move data between return and data stacks (to be able to manipulate PC)
6. Add tests

Ultimately, the ISR should be capable to detect what particular interrupt happened and to correct it by either changing data state and/or emulating the instruction and skipping it in the original flow.

Currently translated variant uses MOV; CALL generated sequences to drive simulation to individual service routines. A fully inlined variant should insert copies of service routines in the generated code section. This will save a pair of call/return.

The steps required to complete the task:

1. Create relocatable service routines (possibly in assembler)
2. Make sure the state is passed and modified correctly
3. Modify the translated to copy capsules instead of CALL machine code.

Currently the project is only buildable/runnable on Linux GCC/ICC (possibly Clang) toolchain and buildable (with limited operation supported) on Cygwin on Windows. Native Windows support is needed.

The task is:

1. Use latest MS VS to create a set of projects/solutions for the code.
2. Use MS compiler to build as many variants of interpreters as possible.
3. Make tests run for them

From the article:

Наверное, эту идею можно развить и дальше — помочь предсказателю переходов правильно запоминать историю исполнения троек, четвёрок и т.д. за счёт соответствующего «разбухания» кода. Например, иметь по две копии всех сервисных процедур, и внутри DISPATCH выбирать только одну из них, в зависимости от кода предыдущей инструкции и её адреса, или какого-то другого критерия. Однако оставлю это в качестве упражнения заинтересовавшимся исследователям.

The task is to implement this mode: double-threaded interpreter

At the moment the only program the simulator can execute is statically defined as Program array during compilation. It would be great to be able to load external programs from files. That would add a lot of flexibility to the simulator.

Steps required:

1. Add a new option to argc, argv parsing for optional file name, like ./switched 1000 file.raw
   1. If the option is present, the file contents is loaded to the program memory as-is starting from address 0x0
   2. If no option is present, the default program is used
2. Proper error checking should be implemented:
   1. If the file cannot be read (missing/no permissions), an error is reported
   2. If the file is shorter than memory length, the rest of it should be padded with zeroes
   3. If file is too big (contains more words than program memory should hold), an error or at least a warning should be produced. At no circumstances buffer overflow may happen.
   4. (optional) If file contains instructions that are not valid for the processor, a warning (not error) should be produced
3. A test should be prepared that showcases the new functionality with at least one external file with some sort of a valid program.

The file loading functionality is generic, i.e., it does not depend on used interpreter mode, so it can/should be done for all variants of the interpreter/translator

The code already demonstrates threaded interpreter, and subroutined one. The task is to combine both techniques and make a threaded-subroutined one.