Assignment 4: Frame Analysis

Due: class time (6 pm), Thursday, March 22.

Note: Projects 4 and 5 are due on the same date---that is, they are handed in together. (This is because it is hard to debug the frame analyser without having the IR generator, its downstream client, to exercise it.) Since the IR generator's official start date is 3/8, you should set 3/8 as an internal deadline for having your frame analyser finished. The IR generator is a very ambitious piece of code, one of the two hardest modules in the entire compiler.

Project 4 is to read chapter six of the text and build a frame analyzer for Appel's Tiger language.

Your code should take an AST and:

  1. Analyze it to determine which variables escape (are referenced from inner procedures) and hence must be stack-allocated.
  2. Lay out the stack frame for the top-level program and each declared procedure, allocating an abstract register ("temp") or a stack frame for each variable.

You should implement a MipsFrame structure satisfying the FRAME signature as discussed in chapter 6 of the course text. Note that this is not the final version of the FRAME interface; we'll be extending the FRAME signature in the future. For a complete description of the signature, see program 12.1, which is on page 260 of my edition of the textbook. (This may explain why you may be hunting in vain through chapter 6 and $TIGER/chap6 for the signature…)

You will need to augment your existing Semant and Env structures as well as implement at least three other structures: FindEscape (escape analysis), and MipsFrame & Translate (managing stack frames and lexical nesting).

You are required to allocate "temps" (abstract registers) for non-escaping variables; they should not go in the stack frame. While this happens first in the processing of the AST, I advise you to write it last.

Undergraduates are not required to handle more than four procedure parameters. That is, you can assume all parameters are passed in the registers. You are encouraged, however, to handle more than four (and you'll receive extra credit for doing so).

You should submit the following files:

Word to the wise: The tricky part of this project is working with the "static link" pointers in the frames to access non-local variables that occur in outer scopes. This requires small amounts of code but large amounts of thought.

  -Olin

CS4410