Project, Phase 5: Simple Code Generation

• Assigned: Wednesday, 16 November 2011
• Due: Wednesday, 30 November 2011

We have now completed the front end of the compiler. We know how tokenize, parse, and analyze programs. We have even written programs to do these key aspects.

It is now time to generate intermediate code.

This stage of the compiler is quite important. Since Pascal is a moderate sized language, it is also a stage that we will break into multiple phases.

• In phase 5 (this phase), you will deal with straight-line programs: No conditionals, no loops, no functions and procedures.
• In phase 6 (next phase), you will add control structures: if-then statements, if-then-else statements, while loops, and for loops. (There are other control structures, but dealing with a subset of Pascal is appropriate.)
• In phase 7 (final phase), you will deal with function and procedure calls.

There are a few aspects to this stage of the program.

• Translating statements and expressions.
• Keeping track of where variables are stored.
• Keeping track of where expression results are stored.

If our programs have no procedures and control, what statements do we have to worry about?

• Assignment statements, which involve expressions and arrays.
• Input and output statements, which we are doing as a variant of Pascal. (Without input and output statements, we have no convenient way to check whether our programs work the way we expect, other than to inspect the output code.)

We also need to consider the allocation of variables. As you may recall from a previous discussion in class, you will generally allocate variables on the stack. To keep track of the variables allocated for a particular procedure (or for the program as a whole), you need to develop an activation record.

In the previous assignment, you assigned a type to every expression. In this assignment, you will have to assign a location to every expression. That is, where can we find the value of that expression in memory at run time. (Don't worry about dealing with Boolean expressions right now.)

Activation Records

It is up to you how to deal with activation records.

I would suggest that you keep a stack of activation records and provide the following functions:

• int ar_start (void) - start a new activation record, typically at the start of a program, procedure, or function.
• int ar_allocate (int amount) - allocate space in the current activation record and return the offset of the allocated space.
• int ar_total () - determine the amount of space allocated to the current activation record.
• int ar_end () - finish the current activation record, returning to the previous one on the stack.

As you will note, the only important information we store about the current activation record is the amount of memory it requires. (We do store the offset of each variable, but that gets associated with the variables and need not be part of the data structure itself.

More About Activation Records

As you may recall, when we're writing compilers, we have to keep two different times in mind - the time at which we are compiling the code and the time at which our program is running. At compile time, we make decisions that affect the code that gets executed at run time.

At run time, each executing procedure (as well as the top-level program) has its own stack frame where its parameters, local variables, temporaries, and other data are stored. The compile-time equivalent of the stack frame is the activation record. In the abstract, the activation record tells us (a) how much space the stack frame for the procedure will need at run time and (b) how that space is laid out.

In practice, the information for the current activation record is somewhat spread out. In one place, we have an indication of how much space has currently been allocated to the current activation record. In the symbol table, we keep track of the location of any named thing within the activation record. And in the parse tree, we keep track of the location of many things (e.g., expression results) within the activation record.

For example, consider the following function and suppose we have sixteen bytes of bookkeeping information in each stack frame and that each integer requires four bytes.

function f (int x, int y): integer;
 var z: integer;
begin
  z := x + y;
  f := z * z;
end;

• When we realize that we are parsing a function, we start a new activation record. (Conveniently, we have also entered a new scope in the symbol table.)
• Since this is a function, not a procedure, we'll need a space for the return value. So, bytes 17-20 of the stack frame are allocated to that return value. (I'd use %fp(-20) to refer to those bytes.) We might store that location in the symbol table and associate it with f. (We might also just decide that there's a standard offset for return variables.)
• We need space for the x. That's four bytes beyond the twenty already used, so x will be at %fp(-24). We will store that location in the symbol table.

      set_p_attribute (attributes, "address", new_relative (FP, -24));
      symtab_put ("x", attributes);
   

• We need space for the y. That's four bytes beyond the 24 already used, so y will be at %fp(-28).
• We need space for the z. That's yet another four bytes beyond those already used, so z will be at %fp(-28).
• We need a place to store the sum of x and y. That's another four bytes (%fp(-32)). In this case, that sum is an unnamed temporary, so we have to store the address in the tree node.

      set_p_attribute (expr->attributes, "address", new_relative (FP, -32));
    

• We need a place to store the product of z and z. Arguably, we can use the same location as in the previous expression. However, that may be difficult to figure out, so we'll just allocate some more stack space, and put it at %fp(-36).
• We've finished parsing the function. We know that we need 36 bytes for the stack frame. So we store that in the symbol table

      symtab_set_i_attribute (symtab, "f", "frame_size", 36);
    

  (Yes, I know that there is no symtab_set_i_attribute; this is just to indicate what is supposed to be happening.) We also end the activation record and the scope.

Now, that analysis was for a function. Of course, you're not dealing with functions at this stage of your program. However, we do have a stack frame for the top-level variables, and that's your main problem for this phase of the compiler. That is, we still need to deal with the top-level activation record and will want to do so in a way that extends naturally to nested declarations.

So, we'll keep a stack of information on activation records. For the current activation record, all we need to store is how much space it requires. When we see a parameter, local, or, temporary, we increment that counter, get the information, and store it in the appropriate place (the symbol table for parameters and local variables, in the parse tree for temporaries).

So, What Do We Have To Do For This Assignment?

1. Implement a stack of activation records. For now, you'll only deal with the first activation record (that for the top-level program). You will probably put this in pascal.y.

2. Implement something that lets you build a STAC program (an array of STAC instructions). You can look at stac.y for ideas.

3. Deal with variable declarations in pascal.y. For each variable declaration, you need to allocate space in the activation record and update the symbol table to store information on the location associated with a variable.

4. Deal with expressions. Each expression should have a type and an address.

a. For expressions that are identifiers, you can look up the address in the symbol table. You'll then store that address in the parse tree for use by other rules.

b. For expressions that are constants, you can generate a new address with new_iconstant or new_fconstant. Once again, you'll store that address in the parse tree.

c. For compound expressions, you'll need to allocate space in the activation record for the result (remember, this space really only gets created at run time, and it gets created when we create the stack frame). You'll then generate an instruction to do the appropriate computation and store in that location.

5. Deal with assignment statements. Most assignment statements will get translated as a move instruction (IMOV or FMOV).

6. Deal with output statements (print and println).