Sequence 5.1 – Building stack frames in LLVM

Reminder: Stack frames

We have seen earlier that:

Reminder: Stack frames (continued)

Do not hesitate to refer to the sequence from week 3 again should you need to refresh your memory.

Building stack frames in LLVM

We can use a simple yet powerful model in LLVM to build stack frames:

Isn’t that costly though?

However, the mem2reg optimization pass of LLVM will take care of removing the extra copies if we do not need to pass a pointer to this frame object to another function, in which case there will be no cost.

Could we optimize it further?

In a production-quality compiler, some optimizations would be implemented. For example:

This list of optimizations is in no way exhaustive.

Visualizing a frame (from sequence 3.3)

let var a := 3
    function f(b: int) =
      let function add() = a := a + b
    in add() end
in
  f(2); print_int(a)  /* Prints 5 */
end

Visualizing frame types in LLVM

We build LLVM types named ft_ (for frame type) followed by the full path of the function. Here is the corresponding LLVM IR:

%ft_main = type { i32 }                    # { a }
%ft_main.f = type { %ft_main*, i32 }       # { up, b }
%ft_main.f.add = type { %ft_main.f* }      # { up }

Except for main, which has no frame up since it represents the toplevel, every frame starts with a pointer to an object of the lexically outer frame type (called static link).

Building the frame type in LLVM

Creating a frame in LLVM is easy:

Manipulating an object stored in the frame

LLVM makes it easy to refer to objects through llvm::Value pointers. Such a value might be:

In fact, a llvm::Value can be viewed as a tree, and can reference other llvm::Value.

Referencing an object in the frame

The IR builder in LLVM has methods to help building complex llvm::Value objects:

Building the frame in LLVM

Here is the IR code for the function f defined previously:

define void @main.f(%ft_main* %sl, i32 %b) {
  # Allocate frame object
  %frame = alloca %ft_main.f
  # Store outer frame pointer (%sl) at first position in %frame
  %0 = getelementptr inbounds %ft_main.f, %ft_main.f* %frame,
       i32 0, i32 0
  store %ft_main* %sl, %ft_main** %0
  # Store %b parameter at second position in %frame
  %1 = getelementptr inbounds %ft_main.f, %ft_main.f* %frame,
       i32 0, i32 1
  store i32 %b, i32* %1
  # Call add function and give it a pointer to the frame object
  call void @main.f.add(%ft_main.f* %frame)
  ret void
}

Conclusion