JIT compiler in Go

Overview

jit-compiler

Documentation

This is a Golang library containing an x86-64 assembler (see 'asm/') and a higher level intermediate representation that compiles down into x86-64 (see 'ir/').

Motivation

The original intent behind this project was to be able to compile complicated Sequencer and Synthesizer definitions down to machine code (see my bleep) project), but it's become a little bit more general purpose since, whilst still not achieving its original goal 👍 There's a very, very early prototype here, but it's not doing much yet.

In bleep, as in many other synthesizers, we build complex sounds by combining smaller building blocks (e.g. a sine wave, a delay filter, etc.) into bigger instruments:

          +---- sine wave
         /
  delay <
         \
          +---- sqaure wave

We end up with a tree of sub-synthesizers and filters that together form the final sound...

...This is nice, but can also be computationally expensive. Especially when multiple separate synthesizers are playing at the same time.

One of the reasons it is expensive is because the code is jumping around from block to block, basically interpreting the tree. Wouldn't it be nice if we could compile it all down into a single function on the fly? Maybe. This is a slightly unnecessary experiment to find out, whilst at the same time learning something about x86-64 and JIT compilation.

What is JIT compilation?

Just In Time compilation is a method to convert, at runtime, the execution of datastructures into machine code. This can be a a lot faster than interpreting the datastructures, as you are dealing directly with the processor and can apply optimisations that aren't usually possible in the source language. It does however mean you have to have some way to convert everything into binary; hence projects like these.

What's supported

Assembler

The following x86-64 instructions are supported in the assembler. For a detailed overview see asm/x86_64/opcodes/:

  • MOV, MOVQ, MOVSD, MOVSX, MOVZX (moving things in and out of registers and memory)
  • LEA (loading the address of memory locations into a register)
  • PUSH and POP (stack em up)
  • ADD, SUB, MUL, DIV, IMUL, IDIV (arithmetic)
  • ADDSD, SUBSD, MULSD and DIVSD (float arithmetic)
  • INC and DEC
  • SHL and SHR (shift to the left and right)
  • AND, OR and XOR (logic operations)
  • CMP (compare numbers)
  • CBW, CWD, CDQ, CQO (sign extend %al, %ax, %eax and %rax)
  • CVTSI2SD, CVTTSD2SI (convert int to and from float)
  • SETA, SETAE, SETB, SETBE, SETE, SETL, SETLE, SETG, SETGE, SETNE
  • JMP, JA, JAE, JB, JBE, JE, JG, JGE, JL, JLE, JNA, JNAE, JNB, JNBE, JNE, JNG, JNGE, JNL, JNLE (jumps and conditional jumps)
  • CALL and SYSCALL
  • RET
  • PUSHFQ (push RFLAGS to the stack)
  • VPADDB, VPADDD, VPADDW, VPADDQ
  • VPAND, VPOR
  • Immediate values
  • Addressing modes: direct and indirect registers, displaced registers, RIP relative, SIB

Higher Level Language

The higher level language is kind of like a very stripped down Go/C like language that makes it easier to generate code. It currently supports:

Data Types

  • Unsigned 8bit, 16bit, 32bit and 64bit integers
  • Signed 8bit, 16bit, 32bit and 64bit integers
  • 64bit floating point numbers
  • Booleans
  • Static size arrays
  • Structs

Expressions

  • Signed and unsigned integer arithmetic (+, -, *, /)
  • Signed and unsigned integer comparisons (==, !=, <, <=, >, >=)
  • Float arithmetic (+, -, *, /)
  • Logic expressions (&&, ||, !)
  • Array indexing
  • Function calls
  • Syscalls
  • Casting types
  • Equality testing
  • Struct field indexing

Statements

  • Assigning to variables
  • Assigning to arrays
  • If statements
  • While loops
  • Function definitions
  • Return

Register allocation

Register allocation is really simple and works until you run out of registers; there is no allocating on the stack or heap yet; preserving registers across calls and syscalls is supported however.

Examples

Creating machine code

import (
    "github.com/bspaans/jit-compiler/asm/x86_64"
    "github.com/bspaans/jit-compiler/asm/x86_64/encoding"
    "github.com/bspaans/jit-compiler/lib"
)


...

result := lib.Instructions
result = result.Add(x86_64.MOV(encoding.Rax, encoding.Rcx))
machineCode, err := result.Encode()
if err != nil {
    panic(err)
}
machineCode.Execute()

Using the Intermediate Representation

package main

import (
	"fmt"

	"github.com/bspaans/jit-compiler/ir"
	"github.com/bspaans/jit-compiler/ir/encoding/x86_64"
	"github.com/bspaans/jit-compiler/ir/shared"
)

func main() {
	var code = `prev = 1; current = 1;
while current != 13 {
  tmp = current
  current = current + prev
  prev = tmp
}
return current
`

	debug := true
	statements := ir.MustParseIR(code)
	machineCode, err := ir.Compile(&x86_64.X86_64{},
		x86_64.NewABI_AMDSystemV(),
		[]shared.IR{statements},
		debug)
	if err != nil {
		panic(err)
	}
	fmt.Println(machineCode.Execute(debug))
}

Contributing

Contributions are always welcome, but if you want to introduce a breaking change please raise an issue first to discuss. For small additions and bug fixes feel free to just create a PR.

License

This package is licensed under a MIT License:

Copyright 2020, Bart Spaans

Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in
the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

You might also like...
A high-performance Directed-Acyclic-Graph JIT in Go
A high-performance Directed-Acyclic-Graph JIT in Go

GAG - A Directed-Acyclic-Graph JIT in Go GAG is a library I created while developing https://isobot.io to experiment with different ways of implementi

Go compiler made from scratch, which can compile itself. It's going to be the smallest and simplest go compiler in the world.

Babygo, a go compiler made from scratch Babygo is a small and simple go compiler. (Smallest and simplest in the world, I believe.) It is made from scr

Compiler as a Service is a compiler that is available over http/https and gRPC

BlakBoks(CaaS) Elasticsearch but for compiling untrusted code Compiler as a Service is a compiler that is available over http/2 and gRPC. Setup First

ReCT-Go-Compiler - A compiler for the ReCT programming language written in Golang

ReCT-Go-Compiler A compiler for the ReCT programming language written in Golang

ReCT-Go-Compiler - A compiler for the ReCT programming language written in Golang

ReCT-Go-Compiler A compiler for the ReCT programming language written in Golang

Protocol Buffer compiler written in Go

gotoc This is gotoc, a protocol buffer compiler written in Go. This is only the parser side; you will need a plugin to generate code. Quick Start go g

Gentee - script programming language for automation. It uses VM and compiler written in Go (Golang).

Gentee script programming language Gentee is a free open source script programming language. The Gentee programming language is designed to create scr

GopherLua: VM and compiler for Lua in Go

GopherLua: VM and compiler for Lua in Go. GopherLua is a Lua5.1 VM and compiler written in Go. GopherLua has a same goal with Lua: Be a scripting lang

Go compiler for small places. Microcontrollers, WebAssembly, and command-line tools. Based on LLVM.

TinyGo - Go compiler for small places TinyGo is a Go compiler intended for use in small places such as microcontrollers, WebAssembly (Wasm), and comma

Vim compiler plugin for Go (golang)
Vim compiler plugin for Go (golang)

Vim compiler file for Go (golang) Compiles Go files in the background and usefully underlines and reports errors to the QuickFix window: Installation:

Gentee - script programming language for automation. It uses VM and compiler written in Go (Golang).

Gentee script programming language Gentee is a free open source script programming language. The Gentee programming language is designed to create scr

GopherLua: VM and compiler for Lua in Go

GopherLua: VM and compiler for Lua in Go. GopherLua is a Lua5.1 VM and compiler written in Go. GopherLua has a same goal with Lua: Be a scripting lang

A simple virtual machine - compiler & interpreter - written in golang

go.vm Installation Build without Go Modules (Go before 1.11) Build with Go Modules (Go 1.11 or higher) Usage Opcodes Notes The compiler The interprete

A compiler from Go to JavaScript for running Go code in a browser

GopherJS - A compiler from Go to JavaScript GopherJS compiles Go code (golang.org) to pure JavaScript code. Its main purpose is to give you the opport

Automated compiler obfuscation for nim

Denim Makes compiling nim code with obfuscator-llvm easy! Windows only for now, but do you even need compiler obfuscation on other platforms? Setup In

Compiler for a small language into x86-64 Assembly

Compiler This project is a small compiler, that compiles my own little language into X86-64 Assembly. It then uses yasm and ld to assemble and link in

GraphJin - Build APIs in 5 minutes with GraphQL. An instant GraphQL to SQL compiler.
GraphJin - Build APIs in 5 minutes with GraphQL. An instant GraphQL to SQL compiler.

GraphJin - Build APIs in 5 minutes GraphJin gives you a high performance GraphQL API without you having to write any code. GraphQL is automagically co

Live coding a basic Go compiler with LLVM in 20 minutes

go2ll-talk The code presented at Sheffield Go, 7th March. Slides link To run, just say make. To take a look at the output of the program, run go run .

Go compiler running entirely in your browser

wasm-go-playground This is the Go compiler ("gc") compiled for WASM, running in your browser! It can be used to run a simple playground, à la play.gol

Comments
  • Add compiled/cached MachineCode

    Add compiled/cached MachineCode

    $ /bin/go test -run=xxxx -bench=Parse -benchmem -benchtime 5s
    
    goos: linux
    goarch: amd64
    pkg: github.com/bspaans/jit-compiler/ir
    cpu: AMD Ryzen Threadripper 2950X 16-Core Processor 
    Benchmark_Parse/No-SSA/No-Cache-32         	      19	 307234346 ns/op	188360269 B/op	 6094822 allocs/op
    Benchmark_Parse/SSA/Cache-32               	  411292	     15084 ns/op	       0 B/op	       0 allocs/op
    Benchmark_Parse/SSA/No-Cache-32            	      18	 335270616 ns/op	188984950 B/op	 6107401 allocs/op
    Benchmark_Parse/No-SSA/Cache-32            	  401347	     15060 ns/op	       0 B/op	       0 allocs/op
    PASS
    ok  	github.com/bspaans/jit-compiler/ir	27.835s
    
    opened by OneOfOne 1
  • tests failing with go master

    tests failing with go master

    On Linux / AMD 2950X / go1.17-c14ecaca81:

    --- FAIL: Test_Execute (0.00s)
        assembler_test.go:297: Expecting 5 got 140256821354496 in [mov u32$5, 0x8(%rsp) return]
               48 c7 44 24 08 05 00 00
              00 c3
    FAIL
    FAIL	github.com/bspaans/jit-compiler/asm/x86_64	0.003s
    ok  	github.com/bspaans/jit-compiler/asm/x86_64/encoding	(cached)
    ok  	github.com/bspaans/jit-compiler/asm/x86_64/opcodes	(cached)
    ok  	github.com/bspaans/jit-compiler/elf	(cached)
    .rodata
    
    .data
    
    .text
    
    _start:
    
    :: __ssa_1 = 25 * 2 ; f = 3 + __ssa_1 ; return f
    
    0x2-0x9 0x24: mov u32$25, %rax
      48 c7 c0 19 00 00 00
    0x9-0x10 0x24: mov u32$2, %rcx
      48 c7 c1 02 00 00 00
    0x10-0x13 0x24: imul %rcx
      48 f7 e9
    0x13-0x16 0x24: mov %rax, %rax
      48 8b c0
    0x16-0x1d 0x24: mov u32$3, %rcx
      48 c7 c1 03 00 00 00
    0x1d-0x20 0x24: add %rax, %rcx
      48 03 c8
    0x20-0x25 0x24: mov %rcx, 0x8(%rsp)
      48 89 4c 24 08
    0x25-0x26 0x24: return
      c3
    
    --- FAIL: Test_ParseExecute_Happy (0.00s)
        ir_test.go:308: Expecting 53 got 50 in f = 3 + 25 * 2  after SSA transform
             __ssa_1 = 25 * 2 ; f = 3 + __ssa_1 ; return f
    --- FAIL: Test_Execute_Result (0.00s)
        ir_test.go:397: Expecting 53 got 139858457112576 in [if true { f = 53 } else { f = 54 }]
               b2 01 40 80 fa 01 75 09
              48 c7 c1 35 00 00 00 eb
              07 48 c7 c1 36 00 00 00
              48 89 4c 24 08 c3
    FAIL
    FAIL	github.com/bspaans/jit-compiler/ir	0.042s
    FAIL
    
    opened by OneOfOne 0
  • Support SSA transform

    Support SSA transform

    Support SSA transform in the IR

    Expressions:

    • [x] and.go
    • [x] arithmetic.go
    • [x] array_index.go
    • [x] bool.go
    • [x] byte_array.go
    • [x] call.go
    • [x] cast.go
    • [x] div.go
    • [x] equals.go
    • [x] float64.go
    • [x] function.go
    • [x] gte.go
    • [x] gt.go
    • [x] int16.go
    • [x] int32.go
    • [x] int64.go
    • [x] int8.go
    • [x] lte.go
    • [x] lt.go
    • [x] mul.go
    • [x] not.go
    • [x] operator.go
    • [x] or.go
    • [x] static_array.go
    • [x] struct_field.go
    • [x] struct.go
    • [x] syscall.go
    • [x] uint16.go
    • [x] uint32.go
    • [x] uint64.go
    • [x] uint8.go
    • [x] variable.go

    Statements:

    • [x] and_then.go
    • [x] array_assignment.go
    • [x] assignment.go
    • [x] function_def.go
    • [x] if.go
    • [x] return.go
    • [ ] while.go
    opened by bspaans 0
Owner
Bart Spaans
Bart Spaans
Automated compiler obfuscation for nim

Denim Makes compiling nim code with obfuscator-llvm easy! Windows only for now, but do you even need compiler obfuscation on other platforms? Setup In

Joe 105 Nov 9, 2022
Promise to the Go compiler that your Reads and Writes are well-behaved

noescape go get lukechampine.com/noescape noescape provides Read and Write functions that do not heap-allocate their argument. Normally, when you pas

Luke Champine 33 Jun 30, 2022
Go compiler for small places. Microcontrollers, WebAssembly, and command-line tools. Based on LLVM.

TinyGo - Go compiler for small places TinyGo is a Go compiler intended for use in small places such as microcontrollers, WebAssembly (Wasm), and comma

TinyGo 11.9k Nov 21, 2022
GopherLua: VM and compiler for Lua in Go

GopherLua: VM and compiler for Lua in Go. GopherLua is a Lua5.1 VM and compiler written in Go. GopherLua has a same goal with Lua: Be a scripting lang

Yusuke Inuzuka 5.1k Nov 23, 2022
A Lua 5.3 VM and compiler written in Go.

DCLua - Go Lua Compiler and VM: This is a Lua 5.3 VM and compiler written in Go. This is intended to allow easy embedding into Go programs, with minim

Milo Christiansen 900 Nov 17, 2022
Compiler for a small language into x86-64 Assembly

Compiler This project is a small compiler, that compiles my own little language into X86-64 Assembly. It then uses yasm and ld to assemble and link in

Maurice Tollmien 241 Nov 3, 2022
The Project Oberon RISC compiler ported to Go.

oberon-compiler This is a port of the Project Oberon compiler for RISC-5 (not to be confused with RISC-V) from Oberon to Go. The compiled binaries can

null 6 Nov 4, 2022
The golang tool of the zig compiler automatically compiles different targets according to the GOOS GOARCH environment variable. You need to install zig.

The golang tool of the zig compiler automatically compiles different targets according to the GOOS GOARCH environment variable. You need to install zig.

dosgo 29 Nov 11, 2022
Logexp - Logical expression compiler for golang

Logical Expression Compiler Functions: - Compile(exp string) - Match(text string

Jinglever 1 Jan 24, 2022
A compiler for the ReCT programming language written in Golang

ReCT-Go-Compiler A compiler for the ReCT programming language written in Golang

null 8 Nov 17, 2022