Tutorial Week 8
Introduction. The purpose of this week’s lab is to get more familiar with assembly programming.
Task 1. For all the programs below, given in pseudo-code, produce an assembler program (using the stack-machine see here) that implements the same functionality. In each case, we assume that various variables (named x, a, …) sit in memory, and we have a program that we want to express in assembly language. Make sure to clean up the stack if necessary, i.e. after the computation is finished, the stack pointer (SP) should not point to an intermediate value in the computation.
Example. We want to compute a := a+4. Here is one way of doing this.
PushAbs “a” // Push the content of a on the stack.
PushImm 4 // Push the constant 4 on the stack.
Plus // Add the two top elements of the stack, and
// return the result on the stack
Pop “a” // Pop (remove) the top of the stack, and store
// that value in a
Programs. Here are the programs that you should translate into assembly.
1. a := a + b + c
2. x := (a – b) – c
3. x := a – (b – c)
4. x := a*b + c
5. c := c + a*b
6. x := (a + b)/(c – d)
7. x := a*a / b*b
8. x := a*a – a*a
9. x := maximum ( b, c )
10. x := minimum ( b, c )
11. x := x + 1; y := y – x
12. x := 100; for i = 1 to 50 { x := x-i }
Note. The ‘commands’ maximum and minimum are short for the maximum and minimum of two numbers. E.g. maximum( 3, 4 ) = 4, and maximum( 4, 4 ) = 4.
Task 2. Finish the code generator for the accumulator machine (see slides here). Again this means thinking about codegen for statements.
Task 3. Finish the code generator for register machines with unlimited registers (see slides here). This means thinking about codegen for statements.
Task 4. In the lectures we devised a way of compiling for register machines with a fixed number of registers (where each register can function as an accumulator). We learned how to generate code for register machines with a fixed number of registers using a hybrid strategy:
• As long as we have enough registers, we employ the code generation strategy for register machines with an unbounded number of registers (i.e. we freely allocate new registers).
• Once we are down to just one register, we switch to the code generation strategy for accumulator machines, using the last available register as an accumulator. This is always possible with modern CPUs, because every register in modern CPUs (except possibly special purpose registers like the PC and the SP) can act as accumulators, i.e. we can perform operations like addition on each register, with the missing argument being fetched from the stack.
(Modern industrial strength compilers use more sophisticated strategies that we may look at later.) In the lectures I gave you only the key clauses of the code generator that uses this hybrid strategy. I also only sketched the machine code of CPUs with a fixed number of registers, where registers can be used as accumulators. The reason for this brevity was that both are very similar to what you’ve seen previously (reproduced below).
Your task is to supply the missing bits:
• Explain the semantics of the machine code for the register machine (with a fixed number of registers, all of which can act as accumulators). This would be a suitable combination of the machine code for register machines with an unbounded number of registers, and the machine code for the accumulator machine. In other words, you need machine instructions that perform operations with arguments in registers, and instructions with one argument in a register and one on the stack. Give the machine instructions, and describe (formally or informally) the meaning of the (new) instructions, e.g. the new command Plus means: r := r + mem(SP); SP := SP-1 % maxMem
(The expression % maxMem takes care of wrapping the stack pointer if memory is finite and of size maxMem. If you don’t worry about overflows, you can ignore it.)
• Write down (in pseudo code or in Java with the visitor pattern, depending on your preferences) the full code generator (targeting the register machine with a fixed number of registers, using the hybrid compilation strategy) for the simple source language we’ve used in class (with the addition of bracketing): P ::= P; P’ | for x = E to E’ { P } | x := E | { P }
•
• E ::= n | x | E + E’ | E – E’ | E * E’ | E / E’ | -E | ( E )
You can find the pseudo code for ASTs in the source language I used here if you want to use it. The parts of the code generator I gave you in the lectures that you need to complete is here.