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
- 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.
- 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
- A Four program, as you can tell from the syntax, is just
a list of functions.
- The main function must be called 'main'. It can have any
return type (though the return value will be ignored) but
it can take no arguments.
- All functions are available to one another (order of
definition doesn't matter) and can be called recursively
in their own bodies, but no two can have the same name.
This is manageable as all function types are explicit in
the function headers and there are no global variables.
- There are no new types at the Four language level.
Functions cannot be passed as arguments to other
functions, and, though functions with no return type can
be thought of as returning void (and implemented as such
in your elaborator) the type 'void' is not available to
the Four programmer. One can signify a void return type
by simply omitting the typename (see syntax).
- Parameters are either pass-by-value or pass-by-reference.
Pass-by-reference parameters are distinguished by placing
the keyword 'ref' between the typename and the formal
parameter. When calling functions, arguments
corresponding to pass-by-reference parameters must be
variables.
- All "return" <exp> commands in a function
should break out of the code and return the <exp>,
which must be of the same type as the return type of the
function. For functions with no return type, there should
be no <exp>'s with the "return"s. Since
it is undecidable whether or not a function will execute
a "return" statement every time it is run, your
compiler should add a "return" <exp>
statement to the end of each function, where <exp>
is the default value of the return type (0 for int,
'\000' for char, false for bool). This "return"
will clearly only be executed if the function completes
and has not "return"ed on its own.
- Formal parameters to a function have scope throughout the
body, but local variables can shadow them.
- The semantics of function bodies is governed by the
semantics of c, except as otherwise
noted.
- The built-in functions are as in c
except that we are revising the definition of the print
functions so that a newline is not printed along
with each printi, printc, or printb. This allows one to
print more than one char on a line.
For problems or questions regarding this web page contact [petel@cs.cmu,edu].
Last updated: March 19, 1998.