MCS-388 Lab 6: Wildcard Lab (Spring 2005)

Due: May 18, 2005

Overview

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 us.)

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.

Example objectives

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 uninitialized.

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 int and do the appropriate type checking, introduction of conversion operations, and emission of correct code for the overloaded operators on each type.

Arrays

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 the -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.

Improved documentation

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 these areas.

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.

Boolean operators

You could add the boolean operators &&, ||, and !. 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 && or ||, 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 <max@gac.edu>