KOI: Lab Exercise 7

In this exercise you will generate a target program for a simple virtual machine. You will also write a simple optimizer that transforms a syntax tree.

You don't have to do this exercise if you don't have time.

Part A: Generating and executing stack machine code

Take the syntax trees from lab 5, those that you have already executed in lab 6, and translate them into stack-machine code.

The lecture notes from lecture 9 (or at least, the old lecture 9) contain some hints about how to generate code for a stack machine.

Use the class StackMachine (source code available here) to manage and execute the target program. Study the program stacktest.cpp (source code available in the same place) to see how instructions can be added to the stack machine's program, and how to run it.

Part B: Optimization

It is more common for real compilers to perform optimization on three-address code, or so-called peep-hole optimization on the generated machine code, but it is also possible to optimize a tree representation of a program.

Write an optimizer that simplifies a syntax tree by

  1. Removing useless calculations. Examples: Replace x + 0 with x, and x * 1 with x. You don't have to identify all useless calculations, but your optimizer should handle at least some cases.
  2. Pre-calculate constant expressions. Examples: Replace 2 + 3 with 5. Again, you don't have to identify all constant expressions, but your optimizer should handle at least some cases.
  3. Pre-evaluate if statements with constant conditions. Example: Replace if (2 > 3) a = 1; else a = 2; with a = 2;.
Hint: Traverse the syntax tree, and build a new tree at the same time. The default case for a node is to build a new, exactly similar node, but in some cases you can simplify the new tree.

You may assume that there is a garbage collector, so you don't have to bother with deleting unused tree nodes.

Insert the optimizer at the proper place in your compiler.

Report!

You don't have to do this exercise if you don't have time.

Show your results and discuss them with the teacher,
or,
send an e-mail:


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) September 15, 2007