MyJIT

MyJIT is a library that allows to generate machine code at run-time and afterwards execute it. The project has started as a part of the Just-in-Time compiler of the Schemik (http://schemik.sourceforge.net) programming language and as a replacement for the GNU lightning library (http://www.gnu.org/software/lightning/) fixing some of its design issues. However, it has evolved into a more powerful tool. Therefore, MyJIT has a very similar instruction set as GNU lightning but it differs in some key aspects. The most important features which make MyJIT different or which should be highlighted are:

Getting MyJIT

The source code including this documentation and examples is available at SourceForge (http://sourceforge.net/projects/myjit/files) as of other information (http://sourceforge.net/projects/myjit)

You can also checkout the latest release from the Bazaar repository (bzr://myjit.bzr.sourceforge.net/bzrroot/myjit).

Instruction Set

The instruction set of the MyJIT intermediate language is inspired by GNU lightning and in some aspects resembles architecture of RISC processors. Each operation has up to four operands which can be immediate values (numbers, constants) or registers. The number of available registers is virtually unlimited.

All general purpose registers and integer values are treated as signed integers and have the same size which corresponds to the register size of the CPU. Note that i386 and SPARC processors have 32 bit wide registers and AMD64 has 64 bit wide registers. In order to overcome this inconsistency, MyJIT provides the jit_value type which has the same size as the CPU's general purpose register. In specific cases, e.g., if smaller or unsigned value is needed and it is appropriate, you may specify the size or type of the value. This topic is discussed in the sequel.

All floating-point numbers and registers are internally treated as double precision values. However, if necessary, the value can be converted into a single precision value.

Typically, name of each instruction consists of three parts:

Registers

MyJIT supports arbitrary number of register. If the number of used registers is higher than the number of available hardware registers, MyJIT emulates them. Nevertheless, to achieve the best performance, it is a good practice not to use too many registers. All registers are denoted by positive integers including zero. To refer to these registers you should use macros R(x) and FR(x) identifying general purpose and floating point registers, respectively. Registers R(x) and FR(x) are completely different register and do not occupy the same space.

Besides, MyJIT has two special purpose registers---R_FP and R_OUT. R_FP serves as the frame pointer and is used to access dynamically allocated memory on the stack. The R_OUT can be used to handle the return values more efficiently. It can be used to read the return value right after the return from the function. Otherwise, the value of the register is undefined. Furthermore, it can be used right before the return from the function to set the return value more efficiently. If the value is set earlier, it can lead to undefined behavior. However, in most cases register allocator can optimize this which makes this register almost obsolete.

Notation

In order to describe instruction set, we are using symbols reg and freg to denote general purpose and floating-point registers, respectively. Analogously, imm and fimm denote immediate integer values and floating-point values. Particular instructions (e.g., load and store operations) have an extra operand which specifies the size (number of bytes) of data they work with. This operand shall be denoted by size and fsize. The value passed by the operand size can be 1, 2, 4, or 8. However, only the AMD64 port supports operation processing 8 bytes long values. The value passed by the operand fsize can be either 4 or 8. In other words, fsize denotes precision of the value.

Transfer Operations

These operations allow to assign a value into a register. The first operand is always a register and the second one, can be either an immediate value or register.

movi  reg, imm          O1 := O2
movr  reg, reg          O1 := O2

fmovr freg, freg        O1 := O2
fmov  freg, fimm        O1 := O2

Binary Arithmetic Operations

Each binary arithmetic operation has exactly three operands. First two operands are always registers and the last one can be an immediate value or register. These operations are fully compatible with those in the GNU lightning instruction set.

addr   reg, reg, reg      O1 := O2 + O3
addi   reg, reg, imm      O1 := O2 + O3
addxr  reg, reg, reg      O1 := O2 + (O3 + carry)
addxi  reg, reg, imm      O1 := O2 + (O3 + carry)
addcr  reg, reg, reg      O1 := O2 + O3, set carry
addci  reg, reg, imm      O1 := O2 + O3, set carry

subr   reg, reg, reg      O1 := O2 - O3
subi   reg, reg, imm      O1 := O2 - O3
subxr  reg, reg, reg      O1 := O2 - (O3 + carry)
subxi  reg, reg, imm      O1 := O2 - (O3 + carry)
subcr  reg, reg, reg      O1 := O2 - O3, set carry
subci  reg, reg, imm      O1 := O2 - O3, set carry
rsbr   reg, reg, reg      O1 := O3 - O2
rsbi   reg, reg, imm      O1 := O3 - O2

mulr   reg, reg, reg      O1 := O2 * O3
muli   reg, reg, imm      O1 := O2 * O3
hmulr  reg, reg, reg      O1 := high bits of O2 * O3
hmuli  reg, reg, imm      O1 := high bits of O2 * O3

divr   reg, reg, reg      O1 := O2 / O3
divi   reg, reg, imm      O1 := O2 / O3
modr   reg, reg, reg      O1 := O2 % O3
modi   reg, reg, imm      O1 := O2 % O3

andr   reg, reg, reg      O1 := O2 & O3
andi   reg, reg, imm      O1 := O2 & O3
orr    reg, reg, reg      O1 := O2 | O3
ori    reg, reg, imm      O1 := O2 | O3
xorr   reg, reg, reg      O1 := O2 ^ O3
xori   reg, reg, imm      O1 := O2 ^ O3

lshr   reg, reg, reg      O1 := O2 << O3
lshi   reg, reg, imm      O1 := O2 << O3
rshr   reg, reg, reg      O1 := O2 >> O3
rshi   reg, reg, imm      O1 := O2 >> O3
rshr_u reg, reg, reg      O1 := O2 >> O3  (unsigned variant)
rshi_u reg, reg, imm      O1 := O2 >> O3  (unsigned variant)

Operations subx and addx have to directly follow subc and addc otherwise the result is undefined. Note that you can use the unsigned flag with the rshr operation to propagate the first bit accordingly.

There are also equivalent operations for floating-point values.

faddr   freg, freg, freg      O1 := O2 + O3
faddi   freg, freg, fimm      O1 := O2 + O3
fsubr   freg, freg, freg      O1 := O2 - O3
fsubi   freg, freg, fimm      O1 := O2 - O3
frsbr   freg, freg, freg      O1 := O3 - O2
frsbi   freg, freg, fimm      O1 := O3 - O2
fmulr   freg, freg, freg      O1 := O2 * O3
fmuli   freg, freg, fimm      O1 := O2 * O3
fdivr   freg, freg, freg      O1 := O2 / O3
fdivi   freg, freg, fimm      O1 := O2 / O3

Unary Arithmetic Operations

These operations have two operands, both of which have to be registers.

negr  reg      O1 := -O2
notr  reg      O1 := ~O2
fnegr freg     O1 := -O2

Load Operations

These operations transfer data from the memory into a register. Each operation has 3 or 4 operands. The last operand is an immediate value indicating the "size" of the data processed by this operation, i.e., a number of bytes copied from the memory to the register. It can be one of the following values: 1, 2, 4, or 8. Furthermore, the size cannot be larger than the size of the register. If the size of the data copied from the memory is smaller than the size of the register, the value is expanded to fit the entire register. Therefore, it may be necessary to specify additional sign flag.

ldr      reg, reg, size             O1 := *O2
ldi      reg, imm, size             O1 := *O2
ldr_u    reg, reg, size             O1 := *O2         (unsigned variant)
ldi_u    reg, imm, size             O1 := *O2         (unsigned variant)

ldxr     reg, reg, reg, size        O1 := *(O2 + O3)
ldxi     reg, reg, imm, size        O1 := *(O2 + O3)
ldxr_u   reg, reg, reg, size        O1 := *(O2 + O3)  (unsigned variant)
ldxi_u   reg, reg, imm, size        O1 := *(O2 + O3)  (unsigned variant)

fldr     freg, reg, fsize           O1 := *O2
fldi     freg, imm, fsize           O1 := *O2

fldxr    freg, reg, reg, fsize      O1 := *(O2 + O3)
fldxi    freg, reg, imm, fsize      O1 := *(O2 + O3)

Store Operations

These operations transfer data from the register into the memory. Each operation has 3 or 4 operands. The last operand is an immediate value and indicates the "size" of the data, see "Load Operations" for more details. The first operand can be either an immediate or register. Other operands must be registers.

str     reg, reg, size              *O1 := O2
sti     imm, reg, size              *O1 := O2

stxr    reg, reg, reg, size         *(O1 + O2) := O3
stxi    imm, reg, reg, size         *(O1 + O2) := O3

fstr    reg, freg, fsize            *O1 := O2
fsti    imm, freg, fsize            *O1 := O2

fstxr   reg, reg, freg, fsize       *(O1 + O2) := O3
fstxi   imm, reg, freg, fsize       *(O1 + O2) := O3

Compare Instructions

These operations compare last two operands and store one or zero (if the condition was met or not, respectively) into the first operand. All these operations have three operands. The first two operands have to be registers and the last one can be either a register or an immediate value.

ltr    reg, reg, reg      O1 := (O2 <  O3)
lti    reg, reg, imm      O1 := (O2 <  O3)
ltr_u  reg, reg, reg      O1 := (O2 <  O3)  (unsigned variant)
lti_u  reg, reg, imm      O1 := (O2 <  O3)  (unsigned variant)

ler    reg, reg, reg      O1 := (O2 <= O3)
lei    reg, reg, imm      O1 := (O2 <= O3)
ler_u  reg, reg, reg      O1 := (O2 <= O3)  (unsigned variant)
lei_u  reg, reg, imm      O1 := (O2 <= O3)  (unsigned variant)

gtr    reg, reg, reg      O1 := (O2 >  O3)
gti    reg, reg, imm      O1 := (O2 >  O3)
gtr_u  reg, reg, reg      O1 := (O2 >  O3)  (unsigned variant)
gti_u  reg, reg, imm      O1 := (O2 >  O3)  (unsigned variant)

ger    reg, reg, reg      O1 := (O2 >= O3)
gei    reg, reg, imm      O1 := (O2 >= O3)
ger_u  reg, reg, reg      O1 := (O2 >= O3)  (unsigned variant)
gei_u  reg, reg, imm      O1 := (O2 >= O3)  (unsigned variant)

eqr    reg, reg, reg      O1 := (O2 == O3)
eqi    reg, reg, imm      O1 := (O2 == O3)

ner    reg, reg, reg      O1 := (O2 != O3)
nei    reg, reg, imm      O1 := (O2 != O3)

Conversion

Register for integer and floating-pint values are independent and in order to convert value from one type to another you have to use the following operations.

extr    freg, reg        O1 := O2
truncr  reg, freg        O1 := trunc(O2)
ceilr   reg, freg        O1 := ceil(O2)
floorr  reg, freg        O1 := floor(O2)
roundr  reg, freg        O1 := round(O2)

The operation truncr rounds the value towards zero and is the fastest one. Operations floorr and ceilr rounds the value towards negative or positive infinity, respectively. roundr rounds the given value to the nearest integer.

Function Calls

The following operations and auxiliary macros help to create a function, read its arguments, and return value.

Function calls

Each function call is done in three steps. The call is initiated by the operation prepare having no argument. In the second step, arguments are passed to a function using putarg or fputarg. (The arguments are passed in the normal order not in reverse, cf. GNU Lightning.) Afterwards, the function is called with the call operation. To retrieve the returned value you can use operations retval or fretval.

Let us make few notes on function calls:

List of operations related to function calls:

Jumps

Operations jmpi and jmpr can be used to implement unconditional jumps. Both operations have one operand, an address to jump to. To obtain this address you can use the get_label operation or use the forward declaration along with the patch operation.

op = jmpi JIT_FORWARD
     ;
     ; some code
     ;
     patch op

Branch Operations

Branch operations represent conditional jumps and all have three operands. The first operand is an immediate value and represents the address to jump to. The latter two are values to be compared. The last operand can be either an immediate value or register.

bltr      imm, reg, reg       if (O2 <  O3) goto O1
blti      imm, reg, imm       if (O2 <  O3) goto O1
bltr_u    imm, reg, reg       if (O2 <  O3) goto O1
blti_u    imm, reg, imm       if (O2 <  O3) goto O1

bler      imm, reg, reg       if (O2 <= O3) goto O1
blei      imm, reg, imm       if (O2 <= O3) goto O1
bler_u    imm, reg, reg       if (O2 <= O3) goto O1
blei_u    imm, reg, imm       if (O2 <= O3) goto O1

bgtr      imm, reg, reg       if (O2 >  O3) goto O1
bgti      imm, reg, imm       if (O2 >  O3) goto O1
bgtr_u    imm, reg, reg       if (O2 >  O3) goto O1
bgti_u    imm, reg, imm       if (O2 >  O3) goto O1

bger      imm, reg, reg       if (O2 >= O3) goto O1
bgei      imm, reg, imm       if (O2 >= O3) goto O1
bger_u    imm, reg, reg       if (O2 >= O3) goto O1
bgei_u    imm, reg, imm       if (O2 >= O3) goto O1

beqr      imm, reg, reg       if (O2 == O3) goto O1
beqi      imm, reg, imm       if (O2 == O3) goto O1
bner      imm, reg, reg       if (O2 != O3) goto O1
bnei      imm, reg, imm       if (O2 != O3) goto O1

bmsr      imm, reg, reg       if (O2 &  O3) goto O1
bmsi      imm, reg ,imm       if (O2 &  O3) goto O1
bmcr      imm, reg ,reg       if !(O2 & O3) goto O1
bmci      imm, reg ,imm       if !(O2 & O3) goto O1

boaddr    imm, reg, reg       O2 += O3, goto O1 on overflow
boaddi    imm, reg, imm       O2 += O3, goto O1 on overflow
boaddr_u  imm, reg, reg       O2 += O3, goto O1 on overflow
boaddi_u  imm, reg, imm       O2 += O3, goto O1 on overflow

bosubr    imm, reg, reg       O2 -= O3, goto O1 on overflow
bosubi    reg, reg, imm       O2 -= O3, goto O1 on overflow
bosubr_u  imm, reg, reg       O2 -= O3, goto O1 on overflow
bosubi_u  imm, reg, imm       O2 -= O3, goto O1 on overflow

fbltr     imm, freg, freg     if (O2 <  O3) goto O1
fblti     imm, freg, fimm     if (O2 <  O3) goto O1
fbler     imm, freg, freg     if (O2 <= O3) goto O1
fblei     imm, freg, fimm     if (O2 <= O3) goto O1

fbgtr     imm, freg, freg     if (O2 >  O3) goto O1
fbgti     imm, freg, fimm     if (O2 >  O3) goto O1
fbger     imm, freg, freg     if (O2 >= O3) goto O1
fbgei     imm, freg, fimm     if (O2 >= O3) goto O1

fbeqr     imm, freg, freg     if (O2 == O3) goto O1
fbeqi     imm, freg, fimm     if (O2 == O3) goto O1
fbner     imm, freg, freg     if (O2 != O3) goto O1
fbnei     imm, freg, fimm     if (O2 != O3) goto O1

Getting Started

We start with a really simple example---function returning its argument incremented by one. The source code of this example can be found in demo1.c which is part of the MyJIT package.

#include <stdlib.h>
#include <stdio.h>

// includes the header file
#include "myjit/jitlib.h"

// pointer to a function accepting one argument of type long and returning long value
typedef long (* plfl)(long);

int main()
{
        // creates a new instance of the compiler
        struct jit * p = jit_init();

        plfl foo;

        // the code generated by the compiler will be assigned to the function `foo'
        jit_prolog(p, &foo);

        // the first argument of the function
        jit_declare_arg(p, JIT_SIGNED_NUM, sizeof(long));

        // moves the first argument into the register R(0)
        jit_getarg(p, R(0), 0);

        // takes the value in R(0), increments it by one, and stores the result into the
        // register R(1)
        jit_addi(p, R(1), R(0), 1);

        // returns from the function and returns the value stored in the register R(1)
        jit_retr(p, R(1));

        // compiles the above defined code
        jit_generate_code(p);

        // checks, if it works
        printf("Check #1: %li\n", foo(1));
        printf("Check #2: %li\n", foo(100));
        printf("Check #3: %li\n", foo(255));

        // if you are interested, you can dump the machine code
        // this functionality is provided through the `gcc' and `objdump'
        // jit_dump_code(p, 0);

        // cleanup
        jit_free(p);
        return 0;
}

We assume that the code above is quite (self-)explanatory, and thus, we do not include more comments on this. However, let us make a note on compiling programs using MyJIT. To start with MyJIT, it is sufficient to copy the myjit subdirectory into your project. Programs using the MyJIT should include the #include "myjit/jitlib.h" header file. In order to link the application and build a proper executable file, it is necessary to also compile "myjit/libjit-core.c".

For instance, to build a program with gcc you may use the following steps:

gcc -c -g -Winline -Wall -std=c99 -pedantic -D_XOPEN_SOURCE=600 demo1.c
gcc -c -g -Winline -Wall -std=c99 -pedantic -D_XOPEN_SOURCE=600 myjit/jitlib-core.c
gcc -o demo1 -g -Wall -std=c99 -pedantic demo1.o jitlib-core.o

The first command compiles the example, the second one compiles functions used by MyJIT, and the last one links the object files together and creates an execute file---demo1.

It should be emphasized that MyJIT conforms to the C99 standard and all MyJIT files should be compiled according to this standard.

We also recommend to check out the demo2.c and demo3.c examples which are also included in the MyJIT package.

Debugging

MyJIT contains several tools simplifying application development. The first one is the msg operation which prints out given message or a value of the given register. The msg operation has one or two operands. The first one is always an immediate value which is the string to display. The second operand is optional and it must be a register. In this case the first string serves as the format string for printf and the value of the register is printed out using this string. The example of the msg operation usage:

jit_msg(jit, "Simple message\n");
jit_msgr(jit, "Reg 1: %l\n", R(1));

MyJIT also provides two functions jit_dump_ops and jit_dump_code which allow to print out the code. The first one prints out the high level code and the second one prints out the final machine code. Both functions take two arguments---the reference to the compiler and the verbosity level. However, the second argument is not used and its value should be always zero.

Examples of the outputs for the above mentioned source code.

prolog      0xbfe62858
declarg     integer, 0x4
getarg      r0, 0x0
addi        r1, r0, 0x1
retr        r1
00000000 <main>:
   0:   55                      push   ebp
   1:   8b ec                   mov    ebp,esp
   3:   83 ec 08                sub    esp,0x8
   6:   8b 55 08                mov    edx,DWORD PTR [ebp+0x8]
   9:   8b ca                   mov    ecx,edx
   b:   83 c1 01                add    ecx,0x1
   e:   8b c1                   mov    eax,ecx
  10:   8b e5                   mov    esp,ebp
  12:   5d                      pop    ebp
  13:   c3                      ret

NOTICE! Do not use the debugging operations and functions in the production code. These operations are not efficient and may lead to a poor performance. You should rather call the printf function explicitly. The jit_dump_code is using gcc and objdump to disassemble the code, therefore, these two programs have to be present in the system.

Optimizations

Support for multiple optimizations is available since release 0.7. These optimizations may speed up your code but the code generation may take longer. Therefore, you can turn particular optimization off and on using jit_disable_optimization and jit_enable_optimization functions, respectively. Currently, there are available the following optimizations:

The optimized code for above mentioned example looks like this:

00000000 <main>:
   0:   8b 4c 24 04             mov    ecx,DWORD PTR [esp+0x4]
   4:   8d 41 01                lea    eax,[ecx+0x1]
   7:   c3                      ret

Or, like this:

0000000000000000 <main>:
   0:   48 8d 47 01             lea    rax,[rdi+1]
   4:   c3                      ret

License

MyJIT is distributed under the terms of GNU Lesser General Public License v.3 or later (at your option).

Despite the fact that MyJIT is very similar to GNU Lightning, it does not share any source code with this project. However, some files come from the Mono project by Novel. (http://www.mono-project.com)

Notes on Development

Get MyJIT at SourceForge.net. Fast, secure and Free Open Source software downloads