15-411 Compiler Design

[ Home | Members | Schedule | Overview | Discussions | Assignments ]

15-411 Assignment #4

Due: 12:01am, Tuesday, April 7, 1998

Goal

The goal of this assignment is to create a compiler for the Four language. This language is an extension of c (little-C) to include functions with both value and reference parameters. Your compiler should implement global register allocation and (possibly naïve) spilling, with an option to implement coalescing as well. Note that for this and the rest of the assignments in this course, the quality of your target code will be one of the grading criteria.


Instructions

  1. Write a compiler for the Four language described below. You should implement global register allocation, for which we recommend you use the graph-coloring technique described in lecture. You should also implement some kind of spilling. It can be random with respect to which registers are spilled and where in the code they are spilled, so long as your compiler never aborts because it runs out of registers. We expect that your compiler will use all of the registers that are normally available for use, according to the standard calling convention for your target machine. In particular, it is not acceptable to spill pseudoregisters to memory if there are machine registers available.
  2. Please submit your compiler in the usual fashion in the course directory studentdir/<your-user-id>/ass4/. Please gzip your hand-in file and call it four.tar.gz so that we won't have a problem with exceeding the course directory quota.

Extra Credit

Implement coalescing.


The Four Language

The Four language is an extension of c to include simple C-style functions with the addition of call-by-reference parameters. Lexically, it is identical to c except that we have two new keywords: 'ref', used for signifying pass-by-reference (similar to 'var' in Pascal), and 'return' as in C. The syntax is an extension and slight modification of the syntax given in the previous assignment for c. Here we present the revisions. Any nonterminals not expanded or mentioned here should be assumed to have the same expansions as in the c grammar.

BNF Syntax

<program> ::= <fundeclist>
<fundeclist> ::= <fundec> <fundeclist> | <fundeclist>
<fundec> ::= <type> ID '(' <formals> ')' <block>
           | <type> ID '(' ')' <block>
           | ID '(' <formals> ')' <block>
           | ID '(' ')' <block>
<type> ::= ID
<formals> ::= <formal> | <formal> ',' <formals>
<formal> ::= <type> ID
           | <type> 'ref' ID
<simp> ::= ... | 'return' | 'return' <exp>
<fcall> ::= ID '(' <args> ')' | ID '(' ')'
<args> ::= <exp> | <exp> ',' <args>

Informal Semantics


For problems or questions regarding this web page contact [petel@cs.cmu,edu].
Last updated: March 19, 1998.