Assignment 4: Frame Analysis

Due: 10:00 pm, Wednesday, October 27.

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:

• mipsframe.sml — MipsFrame structure
• findescape.sml — FindEscape structure
• translate.sml — Translate structure
• semant.sml — Updated Semant structure
• Any other source files you wrote to support your checker.
• Your sources.cm file
• A text file describing
  • The members of your team
  • Anything you think is of interest about your code.

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.

CS4410