MCS-388 Lab 6: Wildcard Lab (Spring 2005)
Due: May 18, 2005
For this lab, you are free to choose your own objective(s), selecting
those that you think would be most educational and interesting.
(Presumably these two attributes go together. Learning is
interesting, and we learn best while working on that which interests
I list below some example objectives. You are welcome to choose from
among them, or to come up with other ideas of your own. Particularly
if you come up with other ideas of your own, it would be wise to
discuss them with me in advance, to get a second opinion regarding
whether the degree of ambitiousness is appropriate.
If you choose a relatively ambitious objective, a single objective
should be sufficient to generate a piece of work worthy of being
called an MCS-388 lab report. If you stick with small, incremental
objectives, you may need to assemble a few of them together to make a
lab's worth. If you are unsure whether the scope of what you are
undertaking is appropriate, talk with me.
Checking for uses of potentially uninitialized variables
Using data-flow analysis to do optimizing transformations is perhaps
over-ambitious, but using data-flow analysis to provide warning or
error messages is comparatively straightforward. You could, for
example, do a structured live-variable analysis to discover those
non-parameter local variables that are live at the start of a
procedure, and report them as being used while potentially
Ordering the evaluation of operands
I showed in class how to select the evaluation order of operands so as
to minimize the number of temporaries used. You could integrate this
into your compiler.
Adding another basic type
You could add
float as an alternative to
and do the appropriate type checking, introduction of conversion
operations, and emission of correct code for the overloaded operators
on each type.
There are lots of possible variations on this, such as:
- one-dimensional vs. multi-dimensional
- local vs. global
- size must be a constant vs. size must be a constant expression
vs. size can be any expression
- passing by reference vs. by copying vs. not at all
Code quality comparison
You could compare the quality of your generated code with that of
the gcc compiler, both with and without gcc's
-O (optimize) flag.
To allow you to do this, I've had a cross-compiler version of gcc
installed on our Linux PCs, which produces MIPS assembly language
output rather than compiling for the Intel architecture. This
cross-compiler is called
mips-gcc and you will need to provide
-S flag to specify that you want assembly language output.
That is, if you start with a C program in
foo.c, you could
compile it to the assembly language version
foo.s by the command
mips-gcc -S foo.c
or for the optimized version,
mips-gcc -S -O foo.c
Now you can manually compare the assembly language files with your own
compiler's output looking
for interesting differences.
Improved error handling
The reporting and recovery from syntactic errors is currently rather
primitive in most of your compilers. The same is generally true for
semantic errors as well. You could improve the reporting and/or recovery
for either or both classes of errors.
Currently my handouts provide very limited documentation of the
language you are compiling. Similarly, most of you have not done much
documenting of implementation strategies or conventions (nor have I!),
nor of implementation restrictions. You could tackle any or all of
Overcoming implementation restrictions
Right now, procedures can only take four arguments, can have a limited
number of local variables, and can deal with expressions of limited
complexity. You could relax one or more of these restrictions. For
example, you could pass additional arguments on the stack, or could
use the stack frame for additional local variables or temporaries.
You could add the boolean operators
!. For the first two, you'll
probably want to do "short-circuit" evaluation, like in the C family
of languages. That is, depending on the value of the left-hand
operand of a
||, it may not be
necessary to evaluate the right-hand operand at all.
Other language features
What is your favorite language feature that is missing? Do you long
for fancier control flow structures? Assignment operators like
+= in C? Call by value-result? Multiple assignment?
Whatever you miss, you are welcome to add!
Graph-coloring register allocation
This would be a particularly ambitious project, since you would need
to implement both the live-variable analysis (needed as an input to
the interference-graph construction) and the graph construction and
coloring algorithms themselves. However, one talented student pulled
this off in a prior year, so I don't want to say you can't too.
Instructor: Max Hailperin <firstname.lastname@example.org>