KOI: Assignment 7

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

Doing this assignment (and the previous ones) will give the grade 4 on the project part of the course.

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

There are two ways to pass this lab. Ideally you should do this:

Write down a short description of your results.
Show your results and discuss them with the teacher. You will get feedback directly, so you can fix any problems with your solution.
Then hand in a brief lab report in Blackboard, including your source code and the collaboration and LLM statements described below.

But as an alternative, you can instead do this.

Don't show your results to the teacher.
Hand in a more elaborate lab report in Blackboard, including your source code and the collaboration and LLM statements described below.
Wait for feedback from the teacher.
Repeat until your report passes.

About sources and collaboration:

Each group (which normally consists of one or two students) must make its own solution to each assignment, and submit or present it, but it is not forbidden to collaborate or ask other students for help. However, in that case you must clearly state who you have collaborated with. Each solution must include the name of everyone who contributed to the work, Collaboration is thus perfectly fine, but must be clearly stated.
You must add an LLM statement to the lab report, where you state if and how you have used large language models, and some experiences from that. Was the LLM helpful, and in what way? Did it help your learning, or maybe in some way hinder it?
All sources (such as books, web pages, colleagues and LLMs) used in the solution of the assignment must be stated.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) August 28, 2025