"MiniC to LC-2" Compiler, Optimizer, and Scheduler

Language:  C/C++

This project was a semester-long attempt at understanding how compilers worked, as well as how to optimize and schedule the results from the compiler.  It is divided into three parts:  the compiler, the optimizer, and the scheduler.

When we wrote the project, we were given a few assumptions.  We used a virtual register file (with infinite registers), as well as a simulator that could be buggy at times.  I've included the simulator, in case you want to see the LC-2 code in action.

Note:  I used Cygwin to develop these projects.  You will need it to run the programs.

The Compiler

This had to be the hardest project I worked on at school.  We were given three weeks to have a working MiniC to LC-2 compiler.  That time included learning how to use the compiler tools (flex and bison), as well as working through an immense grammar by ourselves.  The only outside help we could get from each other was coding strategies or more help with the compiler tools, making this a VERY hard three weeks.  I had to drop one of my courses to do all that this project demanded.  I got a 95 on this project, failing only one test case.

A Brief Description of MiniC

MiniC (or Mini-C), is a language that we "invented" for the purposes of learning how compilers worked. It is very similar to C, with a few exceptions.

  • All variables are integer
  • Variables can be either scalars, pointers, or arrays
  • All functions take at most one parameter
  • All functions may or may not return a result
  • No pre-processor directives (i.e. #include, #pragma, #define, etc.)
  • No I/O
  • No shifting

To my knowledge, that's about all there is to MiniC.

A Brief Description of LC-2

The LC-2 processor, to my knowledge, does not exist.  It's instruction set, similar to the MIPS processor, is very small (16 instructions total), as well as its register file (8 registers, I believe).  But the important part here is that it is a simple, instructional assembly language meant to teach assembly programming strategies and processor design.

The version of LC-2 that we used is called "S3".  I've provided a copy of the specification here:  S3 Description

The Optimizer

The optimizer is very simple.  It takes some LC-2 code and uses Common Sub-Expression Elimination (CSE) to (hopefully) make the program run faster.  I got a score of 95 on this project.  I only failed one test case, and I used "copy" instructions instead of an immediate add, though that wasn't counted against me.  Other versions of the Optimizer would remove NOP instructions, as well as perform other scalar optimizations (specifically copy propagation).

One of the problems I had with this project was the makefile.  I mean, I could not get the program to compile unless I did some special things in one of my files.  So if you download this, make sure you follow the instructions in the README.

A Brief explanation of CSE

The optimizer replaces operations with the same operands with (hopefully) faster instructions.  For example, say you had the following sequence of LC-2 Instructions:

set r1, #5

set r2, #2

mult r3, r1, r2

mult r4, r1, r2

mult r5, r1, r2

Now, assume that the mult instruction takes 3 cycles.  That's a long time to wait for 3 multiplies that end up with the same result.  Rather than have that long of a wait, we could replace these instructions with faster ones.  Let's assume that the copy instruction (or a modified add instruction) takes only one cycle.  After CSE, the code would be:

set r1, #5

set r2, #2

mult r10, r1, r2

add r3, r10, #0

add r4, r10, #0

add r5, r10, #0

Now, instead of taking more than 9 cycles to do the work, we've done it in 6.  That's a 33% performance increase!

The Scheduler

As a final project, we developed a VLIW scheduler for the LC-2 code.  This was the easier of the three projects, because I could reuse the code from the optimizer.  The result was a fully functioning VLIW scheduler, given the length of the VLIW word and a scheduling algorithm to run.  I got a 100 on this project.  I was also the first person to finish it in the class.

The only problem I had with this is the same as I had with the Optimizer--the makefile.  Like before, if you download this, follow the instructions in the README file.

A Brief Idea of Scheduling

The main idea behind scheduling is that you want to use as much of the processor to process as many instructions as you can.  For instance, if your processor has four ALU's, you want all of them working so that your program can run as fast as it can. 

But you can't just shove the next four instructions into the ALU.  Those instructions might be dependent on the results from previous instructions.  They may also have different execution times.  This is why scheduling is so important.

The VLIW (or "Very Large Instruction Word"), in my case, relates to how many ALU's the processor has.  Therefore, the longer the word, the more instructions I can put in.  But you've also got to take into account instruction dependency (that is, which instructions have to wait for the results from other instructions).  Also, you have to take into account the execution time for each instruction before you schedule it.

To make a long story short, just think "LOTS OF MATH, LOTS OF CONSIDERATIONS".  But I think it's fun.  I don't know why.  I've just always liked this kind of work.

This site was last updated 05/23/03