1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
+++
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.
|
