Class 3.4: Memory management in LLVM with alloca/load/store and malloc/free

Summary

The need for memory

We’ve just spent a little bit of time with Rust, a language that’s designed to be efficient but memory-safe. Learning some rust also forced us to think about variable storage and lifetime, i.e., the time between when memory is allocated and deallocated for some value.

Now let’s jump back into how these types of memory storage are actually implemented in an LLVM-based compiler such as rustc.

In LLVM, we have essentially three places to store information at run-time:

In previous labs, with small programs that don’t have any branching or loops, it’s possible to do almost everything with registers. In places where memory operations are needed (like for string concatenation), it’s been possible to isolate those parts of the code to separate function calls that can be written in C.

But as our programs get more advanced, specifically with branching/looping (this unit) and function calls (next unit), we can’t get away with just using registers any more.

Specifically, memory will be needed to store variables whose values can change. In a typical compilation, registers are used for temporary values and memory (with load/store operations) is used for variable values. Sometimes that variable storage can be optimized away into registers, but in general that’s not always possible.

Today we will review how to allocate, use, and deallocate memory both on the stack and on the heap, and talk about when you might need to use each type of storage.

Stack memory

As you know from computer architecture, stack memory is tied to function calls. Allocating memory on the stack involves moving the stack pointer, and deallocation happens automatically when the function finishes.

In LLVM, we allocate stack memory with the alloca command, like:

%addr = alloca i32

This allocates space for a single i32 (i.e. 32-bit signed integer) and returns a pointer to it. So the %addr register here will have type ptr.

To save a value to any allocated memory location, we use store:

store i32 1234, ptr %addr

The 1234 here is a constant integer; it could also be a %reg holding some computed int value.

Finally, later in the code, to get whatever value out of that address and into a register, we could do

%value = load i32, ptr %addr

Again, there is no specific deallocation command. The stack memory will be deallocated whenever the current function finishes.

Stack memory is typically used for local variables in a function that won’t need to be referenced outside that function call. For example, the following C function:

int foo(int x) {
  x += 3;
  return x * 10;
}

might be compiled as:

define i32 @foo(i32 %origx) {
  ; allocate stack space for x and store the argument
  %xaddr = alloca i32
  store i32 %origx, ptr %xaddr

  ; the next three lines do x += 3
  %x1 = load i32, ptr %xaddr
  %x2 = add i32 %x1, 3
  store i32 %x2, ptr %xaddr

  ; the next three lines do return x * 10
  %x3 = load i32, ptr %xaddr
  %temp = mul i32 %x3, 10
  ret i32 %temp
}

Of course, we could also write this same function without using any memory at all and just registers. But we should think of the “registers-only” version as an optimization here, and it’s an optimization that’s not always possible when we have if statements or loops.

The default, unoptimized (but perfectly correct!) LLVM code will typically do a load every time a variable value is referenced, and a store every time a variable is (re)assigned.

Stack arrays and getelementptr

You can also allocate an array of values by tacking on the size (and the type of the size). For example, the following would allocate space for an array of 5 chars (remember i8 is a single byte, i.e., a char):

%array_addr = alloca 18, i64 5

Note that store and load only operate on a single value at a time, even if you allocated an entire array. So for example, to store the string "BOOM" in the array above, you would need 5 stores, like:

; the ASCII values for B O O M are 66, 79, 79, 77
store i8 66, ptr %array_addr
store i8 79, ptr %offset1
store i8 79, ptr %offset2
store i8 77, ptr %offset3
store i8 0, ptr %offset4

But wait, how do we get these pointer offsets like %offset1? For that you have to use a really annoying LLVM command called getelementptr, or GEP for short. You have to tell it the type of array element (i8 here), then the base pointer value (ptr %array_addr here), and then the offset you want, like

%offset2 = getelementptr i8, ptr %array_addr, i64 2

Here’s a complete working example to store BOOM character by character and then print it out:

declare i32 @puts(ptr)

define i32 @main() {
  ; allocate
  %array_addr = alloca i8, i64 5

  ; compute offsets and store each character
  store i8 66, ptr %array_addr
  %offset1 = getelementptr i8, ptr %array_addr, i64 1
  store i8 79, ptr %offset1
  %offset2 = getelementptr i8, ptr %array_addr, i64 2
  store i8 79, ptr %offset2
  %offset3 = getelementptr i8, ptr %array_addr, i64 3
  store i8 77, ptr %offset3
  %offset4 = getelementptr i8, ptr %array_addr, i64 4
  store i8 0, ptr %offset4

  ; print it out
  call i32 @puts(ptr %array_addr)

  ret i32 0
}
~

Heap memory

There is no built-in command in LLVM to allocate parts of heap memory. Instead we can use standard library functions like malloc. To use them in LLVM, somewhere outside of @main you would want to declare these, like:

declare ptr @malloc(i64)
declare ptr @calloc(i64, i64)
declare void @free(ptr)

For heap memory, we use exactly the same load/store commands, but the allocation and deallocation are done by calling these library functions.

For example, we can change the program above to print BOOM from heap-allocated memory rather than stack-allocated memory like this:

declare i32 @puts(ptr)
declare ptr @malloc(i64)
declare void @free(ptr)

define i32 @main() {
  ; allocate
  %array_addr = call ptr @malloc(i64 5)

  ; ... do the stores and getelementptr commands
  ; EXACTLY as above

  ; print it out
  call i32 @puts(ptr %array_addr)

  ; heap memory - don't forget to deallocate!
  call void @free(ptr %array_addr)

  ret i32 0
}