go0

Overview ¶

Go0 is a [self] educational toy Go compiler for a minimalistic subset of Go. It demonstrates how to use the modernc.org/libqbe compiler back end.

Supported targets ¶

Go0 builds, runs and was tested to correctly produce native executable files on

GOOS/GOARCH
-----------
darwin/amd64
darwin/arm64
freebsd/amd64
freebsd/arm64
linux/amd64
linux/arm64
linux/riscv64
netbsd/amd64
openbsd/amd64

The input ¶

This is a valid, self-contained Go program:

package main

func fib(a int) int {
	if a < 2 {
		return a
	}
	return fib(a-1) + fib(a-2)
}

func main() {
	println(fib(42))
}

Go0 can handle the code above and nothing else.

What Go0 does ¶

When executed, the "compiler" creates a package in a temporary directory with import path "example.com/fib" in its go.mod file, containing one Go file, fib.go with the input program as seen above.

It then uses golang.org/x/tools/go/packages to load the package and the golang.org/x/tools/go/ssa{,/ssautil} packages to construct its SSA form.

Next step is to generate QBE IL from the SSA. Then we use modernc.org/libqbe to generate fib.s, its assembler version.

We can use the system assembler (like GNU as) and linker to produce the executable. However, it is easier to just hand over the fib.s file to the system C compiler. It'll do the same for us in one step. It also takes care of adding proper startup code etc.

Then Go0 shows the size of the executable binary file, its type via file(1) and finally the output the executable produces along with time used to compute the result.

The compiler SLOC ¶

~/src/modernc.org/go0$ gocloc main.go
-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Go                               1             31              3            192
-------------------------------------------------------------------------------
TOTAL                            1             31              3            192
-------------------------------------------------------------------------------
~/src/modernc.org/go0$

Example session ¶

This output was produced on a Linux/Amd64 machine.

~/src/modernc.org/go0$ go0
---- Go
package main

func fib(a int) int {
	if a < 2 {
		return a
	}
	return fib(a-1) + fib(a-2)
}

func main() {
	println(fib(42))
}

---- SSA
# Name: example.com/fib.init
# Package: example.com/fib
# Synthetic: package initializer
func init():
0:                                                                entry P:0 S:2
	t0 = *init$guard                                                   bool
	if t0 goto 2 else 1
1:                                                           init.start P:1 S:1
	*init$guard = true:bool
	jump 2
2:                                                            init.done P:2 S:0
	return

# Name: example.com/fib.fib
# Package: example.com/fib
# Location: /tmp/go0-1743633831/fib.go:3:6
func fib(a int) int:
0:                                                                entry P:0 S:2
	t0 = a < 2:int                                                     bool
	if t0 goto 1 else 2
1:                                                              if.then P:1 S:0
	return a
2:                                                              if.done P:1 S:0
	t1 = a - 1:int                                                      int
	t2 = fib(t1)                                                        int
	t3 = a - 2:int                                                      int
	t4 = fib(t3)                                                        int
	t5 = t2 + t4                                                        int
	return t5

# Name: example.com/fib.main
# Package: example.com/fib
# Location: /tmp/go0-1743633831/fib.go:10:6
func main():
0:                                                                entry P:0 S:0
	t0 = fib(42:int)                                                    int
	t1 = println(t0)                                                     ()
	return

---- QBE
function l $fib(l %a) {
@.0
	%t0 =w csltl %a, 2
	jnz %t0, @.1, @.2
@.1
	ret %a
@.2
	%t1 =l sub %a, 1
	%t2 =l call $fib(l %t1)
	%t3 =l sub %a, 2
	%t4 =l call $fib(l %t3)
	%t5 =l add %t2, %t4
	ret %t5
}

export function w $main() {
@.0
	%t0 =l call $fib(l 42)
	call $printf(l $fmt, ..., l %t0)
	ret 0
}

data $fmt = { b "%d\n", b 0 }

---- ASM
.text
fib:
	pushq %rbp
	movq %rsp, %rbp
	subq $8, %rsp
	pushq %rbx
	movq %rdi, %rbx
	cmpq $2, %rbx
	jl .Lbb2
	movq %rbx, %rdi
	subq $1, %rdi
	callq fib
	xchgq %rax, %rbx
	movq %rax, %rdi
	subq $2, %rdi
	callq fib
	addq %rbx, %rax
	jmp .Lbb3
.Lbb2:
	movq %rbx, %rax
.Lbb3:
	popq %rbx
	leave
	ret
.type fib, @function
.size fib, .-fib
/* end function fib */

.text
.globl main
main:
	pushq %rbp
	movq %rsp, %rbp
	movl $42, %edi
	callq fib
	movq %rax, %rsi
	leaq fmt(%rip), %rdi
	movl $0, %eax
	callq printf
	movl $0, %eax
	leave
	ret
.type main, @function
.size main, .-main
/* end function main */

.data
.balign 8
fmt:
	.ascii "%d\n"
	.byte 0
/* end data */

.section .note.GNU-stack,"",@progbits

---- Outputs
-rwxr-xr-x 1 jnml jnml 16024 Nov 17 15:07 /tmp/go0-1743633831/fib
/tmp/go0-1743633831/fib: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=058411db3a5de732ea39648339e88d636aef0e2a, for GNU/Linux 3.2.0, not stripped
267914296
1.94user 0.00system 0:01.94elapsed 100%CPU (0avgtext+0avgdata 1408maxresident)k
0inputs+0outputs (0major+92minor)pagefaults 0swaps
~/src/modernc.org/go0$