100 Languages Speedrun: Episode 62: LLVM Intermediate Representation
Tags: llvm, assembly
Published: 2022-01-21 17:07:00

Creating a well performing programming language is just far too much work, and most of that work just repeats what other languages have done before.

So it would make so much sense for a new language to get transformed into some simple Intermediate Representation, and then something else picks it up and turns it into a high performance code specific to every target architecture like x86 or ARM or whatnot.

LLVM and its LLVM Intermediate Representation are the most popular way to do this.

### History lesson

But before I get to the LLVM, a quick history lesson - why wasn't it done before?

In theory various VMs like most notably Java Virtual Machine can support multiple languages. However as it turns out, unless your language is extremely Java-shaped, compilation is really difficult and the code will run really poorly. So it works for something like Kotlin (which is basically Better Java), but attempts at making Ruby or Python run on a JVM were both difficult and performed poorly. ([TruffleRuby runs fast on GraalVM](https://github.com/oracle/truffleruby), which is a new VM, not on the base JVM itself, it's all a complicated story).

And JVM was a relatively successful case, as far as these go. Many other attempts like Guile or ParrotVM just died, and nobody outside Microsoft really tried to target .NET VM.

The other popular target was compiling languages to JavaScript, so they can run in a browser, and that went far far worse than compiling for the JVM. Again, it worked for various "Better JavaScript" languages like CoffeeScript or ES6 JavaScript, but [Ruby on JavaScript engine](https://opalrb.com/) is crazy slow, even after making a lot of language changes to fit the JavaScript engine. Nobody even seriously thinks of making Ruby-compatible Ruby on JavaScript VM, as that would be impossibly slow. WASM also got zero traction outside cryptominers and other scams.

But before LLVM, we had the GNU Compiler Collection, an successful Open Source compiler collection with multiple programming language frontends and multiple architecture backends, so why people didn't use that?

And that's because the Free Software Foundation were fucking morons, and tried to obfuscate the intermediate representation as much as they could, to prevent people from using parts of GCC to do some spooky proprietary stuff. I'm not making this up, [there's plenty of mails from Richard Stallman himself showing this idiocy was an explicit FCC policy, even way past the point where LLVM was taking over the compiler world](https://lists.gnu.org/archive/html/emacs-devel/2015-01/msg00165.html). And it's not just new languages that need access to compiler internals. Editors need it for proper syntax highlighting, linters, refactoring tools, and all sorts of programmer utilities need this access. FSF got fuck all for their hardline approach, they just drove GCC into irrelevance. And that's how we got here.

### Getting Started with LLVM

LLVM doesn't guarantee stability of its internal representation, and it's not really meant to be too human editable. It's also difficult to write complete programs in LLVM, as it doesn't have any I/O itself, it's all up to each language.

If you know C or C++ or some other low level language with LLVM backend, the easiest way to get started is to write some simple programs in that language, then tell the compiler to generate LLVM IR.

For example if we start with C Hello, World:

```
#include <stdio.h>

int main() {
  printf("Hello, World!\n");
  return 0;
}
```

And run `clang -S -emit-llvm hello.c`, we get this `hello.ll`:

```
; ModuleID = 'hello.c'
source_filename = "hello.c"
target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx11.0.0"

@.str = private unnamed_addr constant [15 x i8] c"Hello, World!\0A\00", align 1
; Function Attrs: noinline nounwind optnone ssp uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0))
  ret i32 0
}
declare i32 @printf(i8*, ...) #1

attributes #0 = { noinline nounwind optnone ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "darwin-stkchk-strong-link" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "probe-stack"="___chkstk_darwin" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+cx8,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "darwin-stkchk-strong-link" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "probe-stack"="___chkstk_darwin" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+cx8,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0, !1, !2}
!llvm.ident = !{!3}

!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 11, i32 1]}
!1 = !{i32 1, !"wchar_size", i32 4}
!2 = !{i32 7, !"PIC Level", i32 2}
!3 = !{!"Apple clang version 12.0.0 (clang-1200.0.32.29)"}
```

That's some LLVM IR, but it contains so much extra stuff as well.

But no matter, we can just compile it like regular C files, and run. If we do it this way, they'll be linked to C library by default, so we get access to C functions like `printf`.

```
$ clang -S -emit-llvm hello.c
$ clang hello.ll -o hello
$ ./hello
Hello, World!
```

### Simplest LLVM IR program

Just like with assembly, let's start with a very simple program that just returns some exit code. In this case we're not doing any system calls, we just return from `main` function, and C library does the rest.

```
define i32 @main() {
  ret i32 7
}
```

This works, except it generates a warning message:

```
$ clang exit7.ll -o exit7
warning: overriding the module target triple with x86_64-apple-macosx11.0.0 [-Woverride-module]
1 warning generated.
```

So let's specify the target:

```
target triple = "x86_64-apple-macosx11.0.0"

define i32 @main() {
  ret i32 7
}
```

And run it:

```
$ clang exit7.ll -o exit7
$ ./exit7
$ echo $?
7
```

What's going on:

* `target` directive specifies the target triple (CPU architecture; vendor; OS version). We could do some fancy cross-compiling here.
* symbols all have prefixes, `@main` means global `main`
* LLVM types are expressed in bit length, like `i32` is 32bit integer.
* `ret i32 7` means return 32bit integer with value `7`
* `define i32 @main()` means define function `main`, with no arguments, and returning 32bit integer

### Math

Before we do anything complicated like Hello Worlds or FizzBuzzes, let's see how LLVM adds some numbers. And to keep things simple, let's return the answer as process exit code:

```
target triple = "x86_64-apple-macosx11.0.0"

define i32 @main() {
  ; There are no "assign constant" instructions in the LLVM IR
  %1 = add i32 13, 0
  %2 = add i32 3, 0
  %3 = add i32 30, 0
  ; Now do the math
  %4 = mul i32 %1, %2
  %5 = add i32 %4, %3
  ret i32 %5
}
```

```
$ clang math.ll -o math
$ ./math
$ echo $?
69
```

What's going on:

* You can have any number of local variables, they all start with sigils, `@` are globals, `%` are locals
* all names are prefixed in LLVM, so they don't conflict with keywords - this is useful, as LLVM wants to be language independent, so navigating what's a keyword in a language vs what's the keyword in LLVM IR etc. would be a lot more work than the usual compiler has to deal with
* if you don't want to bother with names, you can just call them `%1`, `%2` etc.
* every local variable can have only one definition, you cannot reassign `%1` later
* there's nothing like setting a local variable to a constant, I'm using `add i32 N, 0` here to fake it
* the reason for it is that since everything has only one definition, if `%1` is always equal `5`, then LLVM can just mass replace every occurrence of `%1` with `5`
* I'll get to how we can have "variable" variables later
* `mul i32` multiplies
* `add i32` adds

### Optimizations

Now let's look inside `math` binary LLVM produced:

```
objdump -x86-asm-syntax=intel -d math

math:	file format Mach-O 64-bit x86-64


Disassembly of section __TEXT,__text:

0000000100003f60 _main:
100003f60: 31 c0                       	xor	eax, eax
100003f62: 89 c1                       	mov	ecx, eax
100003f64: 83 c1 0d                    	add	ecx, 13
100003f67: 89 c2                       	mov	edx, eax
100003f69: 83 c2 03                    	add	edx, 3
100003f6c: 83 c0 1e                    	add	eax, 30
100003f6f: 0f af ca                    	imul	ecx, edx
100003f72: 01 c1                       	add	ecx, eax
100003f74: 89 c8                       	mov	eax, ecx
100003f76: c3                          	ret
```

That's a lot of calculations, step by step, translating this to normal assignments and ignoring "add zero":

* `xor eax, eax` - `eax = 0`
* `mov ecx, eax` - `ecx = 0`
* `add ecx, 13` - `ecx = 13`
* `mov edx, eax` - `edx = 0`
* `add edx, 3` - `edx = 3`
* `add eax, 30` - `eax = 30`
* `imul ecx, edx` - `eax (39) = ecx (13) * edx (3)`
* `add ecx, eax` - `ecx (69) = ecx (30) + eax (39)`
* `mov eax, ecx` - `eax (69) = ecx (69)`
* `ret` - `return eax (69)`

Let's turn on the optimizer and try again:

```
$ clang -O2 math.ll -o math
$ objdump -x86-asm-syntax=intel -d math

math:	file format Mach-O 64-bit x86-64


Disassembly of section __TEXT,__text:

0000000100003fb0 _main:
100003fb0: b8 45 00 00 00              	mov	eax, 69
100003fb5: c3                          	ret
```

As you can see, our language frontend (whatever we used to generate LLVM IR code) didn't need to worry about optimizing anything, it can just generate extremely naive code, and LLVM will handle optimizations for us!

### Hello, World!

Let's print a `Hello, World!` message.

```
target triple = "x86_64-apple-macosx11.0.0"

@hello = constant [15 x i8] c"Hello, World!\0A\00"

define i32 @main() {
  call i32 (i8*, ...) @printf(
    i8* getelementptr ([15 x i8], [15 x i8]* @hello, i64 0, i64 0)
  )
  ret i32 0
}
declare i32 @printf(i8*, ...)
```

```
$ clang hello2.ll -o hello2
$ ./hello2
Hello, World!
```

There's a call going on here.

* we define global `@hello` to keep our message
* we need to specify its type, `constant [15 x i8]`, which means an 15-byte constant; i8 is a byte (8-bit integer)
* `c"Hello, World!\0A\00"` is a string with a newline at the end, then a 0 byte, the way C functions want the strings to be
* as `@printf` function is external, we need to declare its interface, it's `declare i32 @printf(i8*, ...)` - that means it returns `i32`, takes `i8*` (pointer to a string) first, and `...` means it takes some extra arguments after that
* `call i32 (i8*, ...) @printf` calls the `@printf` function, I spread it over multiple lines to make it more clear
* now you'd think we could just pass `@hello` as argument, like it works in C; unfortunately LLVM IR has really convoluted pointer model, so there's a lot of `getelementptr` instructions in LLVM code

As we won't really be doing anything with `getelementptr` except pass the constant strings, I'll skip the detailed explanations. It's one of more complicated parts of LLVM IR.

### Loop - stack memory version

Let's write a loop that prints numbers from 1 to 10.

The main problem is that we want to increment the `i`, but LLVM only allows one definition per variable.

There are two ways around it, to have "variable variables" in LLVM IR:

* we can save to memory and load from memory
* we can use `phi` nodes - then value of variable in a given block depends on which block we came from

Let's try both ways, first memory version. We'll use stack for our memory:

```
target triple = "x86_64-apple-macosx11.0.0"

@fnumber = constant [4 x i8] c"%d\0A\00"

define i32 @main() {
start:
  %i = alloca i32
  store i32 1, i32* %i
  br label %loop

loop:
  %i0 = load i32, i32* %i

  call i32 (i8*, ...) @printf(
    i8* getelementptr ([4 x i8], [4 x i8]* @fnumber, i64 0, i64 0),
    i32 %i0
  )

  %i1 = add i32 %i0, 1
  store i32 %i1, i32* %i
  %t = icmp sgt i32 %i1, 10

  br i1 %t, label %exit, label %loop

exit:
  ret i32 0
}
declare i32 @printf(i8*, ...)
```

So step by step:

* we have three blocks - `start`, `loop`, and `exit`
* `start` block sets up `i=1` and goes to `loop`
* `loop` block prints `i`, increments `i`, checks depending on if it's greater than 10 goes back to `loop`, or to `exit`
* `exit` block returns 0

In the `start` block:

* `%i = alloca i32` allocates memory for `i` variable, of size `i32` - that allocation will happen on the stack
* `store i32 1, i32* %i` stores value `1` to where `i` is pointing to
* `br label %loop` jumps to `loop` unconditionally - there's no fall-through, every block needs to end with a jump (`br`), return (`ret`) or something like that

In the `loop` block:

* `%i0 = load i32, i32* %i` loads value of `i` to `i0` - this is the only definition of `i0`, so it's fine
* then we call `printf` passing two arguments, basically doing `printf("%d\n", i0)`
* we calculate `%i1 = i0 + 1` and store it to `%i`
* we calculate if `i1` is `Signed Greater Than` `10`, and store returns to `%t`
* we then have calculated branch, depending on value of `%t`, we go to `exit` or `loop`

The `exit` block just returns 0 like we did previously.

### Loop - phi version

The other way, and actually much more in line with how compilers work, is to not store anything on stack, but use `phi` instruction to define a value. `phi` instruction contains a list of blocks and their associated values - its result will depend on where we came from.

```
target triple = "x86_64-apple-macosx11.0.0"

@fnumber = constant [4 x i8] c"%d\0A\00"

define i32 @main() {
start:
  br label %loop

loop:
  %i0 = phi i32 [ 1, %start ], [ %i1, %loop ]

  call i32 (i8*, ...) @printf(
    i8* getelementptr ([4 x i8], [4 x i8]* @fnumber, i64 0, i64 0),
    i32 %i0
  )

  %i1 = add i32 %i0, 1
  %t = icmp sgt i32 %i1, 10

  br i1 %t, label %exit, label %loop

exit:
  ret i32 0
}
declare i32 @printf(i8*, ...)
```

* `start` block doesn't actually do anything, but we still label it for sake of `phi`.
* in `loop` block, `%i0 = phi i32 [ 1, %start ], [ %i1, %loop ]` means that if we came from `start`, then `i0` is `1`, and if we came from `loop` it's `i1`
* then we the rest of the `loop` block is identical to what we had before, except we don't store anything
* `exit` block is just like before

### Generated loop code

It's important to note that the shape of the LLVM IR code coming in, and the shape of generated assembly, really don't have much in common. LLVM will very aggressively optimize things. For example both loop codes end up like this:

```
Disassembly of section __TEXT,__text:

0000000100003ef0 _main:
100003ef0: 53                          	push	rbx
100003ef1: 48 8d 1d ba 00 00 00        	lea	rbx, [rip + 186]
100003ef8: 48 89 df                    	mov	rdi, rbx
100003efb: be 01 00 00 00              	mov	esi, 1
100003f00: 31 c0                       	xor	eax, eax
100003f02: e8 8b 00 00 00              	call	139 <dyld_stub_binder+0x100003f92>
100003f07: 48 89 df                    	mov	rdi, rbx
100003f0a: be 02 00 00 00              	mov	esi, 2
100003f0f: 31 c0                       	xor	eax, eax
100003f11: e8 7c 00 00 00              	call	124 <dyld_stub_binder+0x100003f92>
100003f16: 48 89 df                    	mov	rdi, rbx
100003f19: be 03 00 00 00              	mov	esi, 3
100003f1e: 31 c0                       	xor	eax, eax
100003f20: e8 6d 00 00 00              	call	109 <dyld_stub_binder+0x100003f92>
100003f25: 48 89 df                    	mov	rdi, rbx
100003f28: be 04 00 00 00              	mov	esi, 4
100003f2d: 31 c0                       	xor	eax, eax
100003f2f: e8 5e 00 00 00              	call	94 <dyld_stub_binder+0x100003f92>
100003f34: 48 89 df                    	mov	rdi, rbx
100003f37: be 05 00 00 00              	mov	esi, 5
100003f3c: 31 c0                       	xor	eax, eax
100003f3e: e8 4f 00 00 00              	call	79 <dyld_stub_binder+0x100003f92>
100003f43: 48 89 df                    	mov	rdi, rbx
100003f46: be 06 00 00 00              	mov	esi, 6
100003f4b: 31 c0                       	xor	eax, eax
100003f4d: e8 40 00 00 00              	call	64 <dyld_stub_binder+0x100003f92>
100003f52: 48 89 df                    	mov	rdi, rbx
100003f55: be 07 00 00 00              	mov	esi, 7
100003f5a: 31 c0                       	xor	eax, eax
100003f5c: e8 31 00 00 00              	call	49 <dyld_stub_binder+0x100003f92>
100003f61: 48 89 df                    	mov	rdi, rbx
100003f64: be 08 00 00 00              	mov	esi, 8
100003f69: 31 c0                       	xor	eax, eax
100003f6b: e8 22 00 00 00              	call	34 <dyld_stub_binder+0x100003f92>
100003f70: 48 89 df                    	mov	rdi, rbx
100003f73: be 09 00 00 00              	mov	esi, 9
100003f78: 31 c0                       	xor	eax, eax
100003f7a: e8 13 00 00 00              	call	19 <dyld_stub_binder+0x100003f92>
100003f7f: 48 89 df                    	mov	rdi, rbx
100003f82: be 0a 00 00 00              	mov	esi, 10
100003f87: 31 c0                       	xor	eax, eax
100003f89: e8 04 00 00 00              	call	4 <dyld_stub_binder+0x100003f92>
100003f8e: 31 c0                       	xor	eax, eax
100003f90: 5b                          	pop	rbx
100003f91: c3                          	ret
```

LLVM decided that the best way to loop this is basically with `printf("%d\n", 1); printf("%d\n", 2); ... printf("%d\n", 10);`.

### Fibonacci

Here's Fibonacci in LLVM IR:

```
target triple = "x86_64-apple-macosx11.0.0"

@format = constant [14 x i8] c"fib(%d) = %d\0A\00"

define i32 @fib(i32 %a) {
start_fib:
  ; if (a <= 2) { fib_small } else { fib_big }
  %t = icmp sle i32 %a, 2
  br i1 %t, label %fib_small, label %fib_big

fib_big:
  ; f1 = fib(a-1)
  %a1 = sub i32 %a, 1
  %f1 = call i32 @fib(i32 %a1)

  ; f2 = fib(a-1)
  %a2 = sub i32 %a, 2
  %f2 = call i32 @fib(i32 %a2)

  ; return f1 + f2
  %e = add i32 %f1, %f2
  ret i32 %e

fib_small:
  ; return 1
  ret i32 1
}

define i32 @main() {
start:
  br label %loop

loop:
  %i0 = phi i32 [ 1, %start ], [ %i1, %loop ]
  %j = call i32 @fib(i32 %i0)

  call i32 (i8*, ...) @printf(
    i8* getelementptr ([14 x i8], [14 x i8]* @format, i64 0, i64 0),
    i32 %i0,
    i32 %j
  )

  %i1 = add i32 %i0, 1
  %t = icmp sgt i32 %i1, 20

  br i1 %t, label %exit, label %loop

exit:
  ret i32 0
}
declare i32 @printf(i8*, ...)
```

This doesn't really use any new techniques.

* `if`s use same basic blocks as loops - and they need same `phi` nodes if you assign something in both `then` and `else` branches and want to use it after the `if`.
* unlike assembly, there's no "calling convention", saving registers, or any such concerns - we just do `call` and LLVM will figure out how to translate that into register actions when it's generating code

```
$clang -O2 fib.ll -o fib
$ ./fib
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765
```

### FizzBuzz

And we obviously finish with the FizzBuzz:

```
target triple = "x86_64-apple-macosx11.0.0"

@fizz = constant [6 x i8] c"Fizz\0A\00"
@buzz = constant [6 x i8] c"Buzz\0A\00"
@fizzbuzz = constant [10 x i8] c"FizzBuzz\0A\00"
@fnumber = constant [4 x i8] c"%d\0A\00"

define i32 @main() {
start:
  br label %loop

loop:
  %i0 = phi i32 [ 1, %start ], [ %i1, %loop_end ]
  %m15 = srem i32 %i0, 15
  %e15 = icmp eq i32 %m15, 0
  br i1 %e15, label %fizzbuzz, label %not_fizzbuzz

fizzbuzz:
  call i32 (i8*, ...) @printf(
    i8* getelementptr ([10 x i8], [10 x i8]* @fizzbuzz, i64 0, i64 0)
  )
  br label %loop_end

not_fizzbuzz:
  %m5 = srem i32 %i0, 5
  %e5 = icmp eq i32 %m5, 0
  br i1 %e5, label %buzz, label %not_buzz

buzz:
  call i32 (i8*, ...) @printf(
    i8* getelementptr ([6 x i8], [6 x i8]* @buzz, i64 0, i64 0)
  )
  br label %loop_end

not_buzz:
  %m3 = srem i32 %i0, 3
  %e3 = icmp eq i32 %m3, 0
  br i1 %e3, label %fizz, label %not_fizz

fizz:
  call i32 (i8*, ...) @printf(
    i8* getelementptr ([6 x i8], [6 x i8]* @fizz, i64 0, i64 0)
  )
  br label %loop_end

not_fizz:
  call i32 (i8*, ...) @printf(
    i8* getelementptr ([4 x i8], [4 x i8]* @fnumber, i64 0, i64 0),
    i32 %i0
  )
  br label %loop_end

loop_end:
  %i1 = add i32 %i0, 1
  %t = icmp sgt i32 %i1, 100

  br i1 %t, label %exit, label %loop

exit:
  ret i32 0
}
declare i32 @printf(i8*, ...)
```

There's nothing new here other than `srem` for `Signed REMinder` (that is `%`) operator.

### Should you use LLVM IR?

LLVM IR is far less human friendly than assembly, and it's really only meant to be generated by compiler frontends. If you make a typo in basic block structure, you get either completely meaningless error, or LLVM will crash during compilation.

It's only barely sufficiently human readable to let people creating compilers debug their compilers. There are some analysis tools, but all of that is also really meant mainly to debug your compiler.

So LLVM is a great tool for creating compilers, but LLVM IR is really not something you should be writing by hand.

And since this is recommendation section, don't be like the FSF. "Free Software" under centralized control that intentionally prevents it from reaching its full potential is doomed to fail.

### Code

[All code examples for the series will be in this repository](https://github.com/taw/100-languages-speedrun).

[Code for the LLVM Intermediate Representation episode is available here](https://github.com/taw/100-languages-speedrun/tree/master/episode-62-llvm-ir).