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

Due: May 20, 2008

Overview

For this lab, you are free to choose your own objective(s), selecting those that you think would be most educational and interesting.

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. I would also be happy to talk with you as you work through any of these that you choose.

Example objectives

Using analyses to detect programming errors

You could do a 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.

You could report procedures that can reach their end without passing through a return statement.

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

I would suggest you start simple.

Improved error handling

The reporting and recovery from syntactic errors is currently rather primitive in most of your compilers. You could improve this.

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.

Exploring LLVM's optimizations

The LLVM system includes an optimization program, opt, which you can use to transform the bitcode produced by your compiler into a more efficient version. You can use command-line arguments to select the particular optimization passes your want performed. You can then use the LLVM disassembler, llvm-dis, to convert the optimized program back into human-readable assembly code and write a report regarding how the optimizations turned out. You could also measure the performance impact.

Simple optimizations

Although the LLVM backend does a nice job of optimization, you could also by implement a number of simple optimizations by modifying your AST classes. Many of these would be best done through a transformation pass over the AST prior to the code generation:

• constant folding

• algebraic identities (addition of zero, multiplication by one)

• simplifying control-flow statements with constant tests

• avoiding conversions between 1-bit and 32-bit values where possible

Leftovers from prior labs

If there is anything interesting you didn't get around to in a prior lab, you could do it now.

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 reference? Multiple assignment? Whatever you miss, you are welcome to add!