+++
title = "Frame Layout — Compiler In A Day"
prev = "02-ast.md"
next = "04-abi.md"
+++

# Frame Layout

When programs execute, their local variables' values are typically stored into a data structure called the *call stack*, or commonly just *the stack*.

This is a stack data structure whose entries are called *stack frames*.
These contain all the information that a function might need to save while calling another one.

For example, consider the following program.

```ciad
fun f(x) {
  var y;
  var z;

  y = x + 3;
  z = g(x - 1);
  return y - z;
}

fun g() {
  if x == 0 {
    return 42;
  } else {
    return f(x - 1);
  }
}

fun main(args) {
  return f(2);
}
```

When `f` calls `g`, we need to store the value of `y` somewhere, so that it can be used again after `g` returns.
We also need to store what function `f` should return to once it finishes, and we store that on the stack as well.

In general, most languages structure their stacks as something like:

```
╭───────────────────────────────╮ <-- "bottom of the stack"
│ address main should return to │          (highest address
├───────────────────────────────┤           on most current
│      saved frame pointer      │        CPU architectures)
├───────────────────────────────┤
│                               │
│ saved local variables of main │
│                               │
┝━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┥
│   address f should return to  │
├───────────────────────────────┤
│      saved frame pointer      │
├───────────────────────────────┤
│                               │
│   saved local variables of f  │
│                               │
┝━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┥
│   address g should return to  │
├───────────────────────────────┤
│      saved frame pointer      │             frame pointer
├───────────────────────────────┤ <--------- when running g
│                               │
│      local variables of g     │             stack pointer
│                               │       when running g, aka
╰───────────────────────────────╯ <----- "top of the stack"
```

The stack then "grows down" as functions are called.
When a function returns, it removes its frame from the stack, shrinking it.

The stack is kept track of with the *stack pointer*, which points to the top of the stack, i.e. the address at the _end_ of the current stack frame.

In some programs, there's also a *frame pointer*.
This points to the address at the start of local variables of the current stack frame.

With a smarter compiler than we're building in this series, the frame pointer isn't necessary.
However, it can still be useful for a debugger and some kinds of runtime introspection.

In our compiler, we'll need to have a pass that computes how much storage the local variables of each function will take up in the stack frame.

Once we know this, we can compute the address of any local variable as an offset from the frame pointer.

Alright, let's get started with the code!

The first thing we'll need to do is to extend `Arg` and `DeclVar` with the ability to store a slot index.
This the offset of the variable from the frame pointer.

```ruby
class Arg
  # ...

  attr_accessor :slot
end

class DeclVar
  # ...

  attr_accessor :slot
end
```

Then, we can add the method to perform the pass to the `Program` class.

Computing frame layouts doesn't require any sort of information that's shared between functions, so we can just tell each function declaration to compute it independently.

```ruby
class Program
  # ...

  def compute_frame_layouts
    @decls.each do |decl|
      case decl
      in DeclFun
        decl.compute_frame_layout
      in DeclVar
        # Ignore it; variables don't have any kind of frame
        # to be laid out.
      end
    end
  end
end
```

Once we're processing the function, we start with storing a counter for the number of local variables we have in the declaration.

We define a helper function (`assign_slot_to`) to be called on every `Arg` and `DeclVar` in the function as well.

```ruby
class DeclFun
  # ...

  def compute_frame_layout
    @locals_count = 0
    def assign_slot_to(var)
      var.slot = @locals_count
      @locals_count += 1
    end

    @args.each { |arg| assign_slot_to arg }

    def traverse_stmt(stmt)
      case stmt
      in DeclVar
        assign_slot_to stmt

      in StmtIf
        stmt.then_stmts.each { |stmt| traverse_stmt stmt }
        stmt.else_stmts.each { |stmt| traverse_stmt stmt }
      in StmtWhile
        stmt.body_stmts.each { |stmt| traverse_stmt stmt }

      else
        # Do nothing; nothing else needs to get a slot nor
        # contains anything that needs to get a slot.
      end
    end

    @body.each { |stmt| traverse_stmt stmt }
  end
end
```

Once this has finished running, every `DeclStmt` will have an `@locals_count`, and every `Arg` and non-global `DeclVar` will have an `@slot`.

Before we can start generating code, though, we should look at some details of exactly what code we'll be generating.