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
- 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.
- 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.
- 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:
-
The e-mail should contain clear and full explanations of what you have done.
-
Include well-chosen and commented test runs with input and output.
-
Send your e-mail in plain text format,
not as HTML or Word documents
or with unnecessary attachments.
-
Include relevant source code, with any changes clearly marked.
-
Except for this report, you should also send all
the source code that is required to compile the final version of the program,
as a Zip file or equivalent.
Thomas Padron-McCarthy
(Thomas.Padron-McCarthy@oru.se)
September 15, 2007