Code Generation - Runtime Storage

Local Variables and Method Parameters

In order to support recursion (a required Dream language feature), the Dream runtime must be able to dynamically allocate memory for local variables, so that multiple invocations of a method can each have their own values for parameters and local variables.

The usual technique involves storing the local variables (and method parameters) on the runtime stack.

During semantic processing, your compiler must assign a numeric offset to each local variable and method parameter. The offset is relative to the frame pointer (aka base pointer), which is kept in the BP register, and points to the start of the local variable section of the activation record.

Here’s an activation record inside the call to g(i, j, k) in multparm.c:

Thus, in your code, a reference to j would look like this:

movl 12(%ebp), %eax # Load j into EAX

Note: You should generate a comment for each variable access instruction, as shown. This will be invaluable in debugging your output.

Return Values

C returns values in the EAX register. For a return statement, the compiler evaluates the return expression, stores it in EAX, and returns.

Dream does not have a return statement. Instead, the return value of a method is set by assigning a value to the method name:

sum(a: int; b: int): int is
  c: int
begin
  c := in.readint()
  sum := a + b + c
end sum

Assignment to the method name (sum := a + b + c) does not cause the method to return; it merely assigns the return value. Therefore, your compiler can’t just evaluate the expression and store it in AX, since other code can follow that assignment statement, and might destroy the contents of AX.

Thus, your Dream compiler needs to reserve space in the activation record for return values:

Thus, in your code, a reference to c would look like this:

movl -8(%ebp), %eax # Load c into EAX

Now, when your Dream compiler generates code for sum := a + b + c, it will store the expression’s value in -4(%ebp). At the end of your method, the standard method exit code will move the saved return value to AX, restore the old BP, and exit:

movl -4(%ebp), %eax  # put return value in AX
movl %ebp, %esp  # clear off local variables
popl %ebp # restore old BP
ret

A call to sum

x := sum(3, 5)

would look like this:

pushl $5
pushl $3
call _sum
addl $8, %esp  # remove parameters from stack
pushl %eax     # push return value onto stack as result of call

popl %eax
movl %eax, x # store return value in x

Implementing Stack Memory Management

Variable Declarations

Add an offset attribute to the VarDecl class:

class VarDecl extends Declaration {
  ...
  int offset;
  ...
}

Add code to the semantic checker’s visitVarDecl to assign an appropriate offset for each local variable as it’s declared.

Do something similar for arguments in, ex., visitMethodDecl.

Variable References

The semantic checker should decorate the syntax tree with information about variables, so that come code generation, the appropriate offsets are available.

During semantic checking, decorate IdExpr nodes with the identifier’s symbol object.

For example, in SemanticChecker:

void visitIdExpr(IdExprContext ctx) {
...
Symbol sym = symtab.lookup(node.getId().getText());
... do normal stuff ...
ctx.symbol = sym;
}

In the CodeGen phase, you can access the symbol in CodeGen:

void visitIdExpr(IdExprContext ctx) {
  Symbol sym = ctx.symbol;
  if (sym.scope == LOCAL_SCOPE) {
    int offset = sym.getDeclarationInfo().getOffset();
    emit("pushl", offset + "(%ebp)");
  } else {
    // instance variable ...
  }
}