ICS 142 Homework 6 Due 5/24

Consider the following target machine instruction set description:
- (Note you will not need all these instructions for this assignment.)
- There are arbitrary number of general purpose, single-word registers:
  - r0, r1, r2, and so on
- There is an activation record frame pointer called fp (or ar which ever you prefer, but be consistent).
- There is a top of stack pointer called sp. The stack is in the high end of memory and grows upward towards the lower addresses. Stack space is allocated by subtracting from sp or deallocated by adding to sp. Typically, space must be allocated for local variables upon entering a subroutine and deallocated before returning from a subroutine.
- address modes:
  - immediate: 4, means the constant value 4
  - absolute: M, address: M
  - register: R, address: R
  - indexed: c(R), address: constant c + contents(R)
  - indirect register: *R, address: contents(R)
  - indirect indexed: *c(R), address: contents(constant c + contents(R))
  - label: L10 is a symbolic label
- The machine is byte addressable. Words are four bytes.
- The operations are:
  - add, sub, mul, div, mov, neg
  - EG
```
move 0(fp), r0
add 4(fp), r0 
move r0, 8(fp) # means 8(fp) := 0(fp) + 4(fp)
```
  - compare left, right - compares left and right to be used by jump
  - jump cc where cc is optional and may be lt, gt, le, ge, eq, ne
  - EG
```
compare r1, r2
jumplt	L10 # jumps to L10 if value of r1 < value of r2
jump L20 # unconditionally jump to L20
```
  - push - move word to the top of stack and decrement sp by 4
  - pop - move word from the top of stack into argument, increment sp by 4
  - call - pushes address of next instruction, jumps to label argument
  - EG
```
push 4(fp)
push 1
call foo # calls foo(1, X) if X's offset is 4
```
  - ret - jumps to address on top of stack, pops off that return address
  - addr 8(fp), r1 - puts the address of variable into r1
- Instructions may be labelled with one or more labels
  - EG
```
L10: move r1, r2
```

Consider the following tiny-ada program as a test case for the problems below:

declare
  x,y,z,a,b,c,d,e,f,g,h,i,j,k,l,m: integer;
begin
  x := x+y+z+a+b+c+d+e+f+g+h+i+j+k+l+m;
  y := x+(y+(z+(a+(b+(c+(d+(e+(f+(g+(h+(i+(j+(k+(l+m))))))))))))));
  z := -x-y-z-a-b-c-d-e-f-g-h-i-j-k-l+-m;
  a := -x-(y-(z-(a-(b-(c-(d-(e-(f-(g-(h-(i-(j-(k-(l+-m))))))))))))));
  b := -x-y-z/a-b-c/d-e-f/g-h-i/j-k-l/m;
end;

(10 points) Define a syntax-directed definition to build abstract syntax trees for arbitrary Tiny-Ada programs involving operators plus, minus, multiplication, division, and unary minus. You need not handle And, Not, or '<', but you must handle parenthesized expressions. You should also modify your grammar to allow lists of identifiers in variable declarations as in the example above. You may assume all variables will be integers.
(2 points) Assign positive offsets into the activation record assuming offsets start at zero and variables are referenced c(fp) where fp is a pointer to the top of the activation record and c is the constant offset of the variable. You needn't overlay variables from disjoint declare blocks as we did in an earlier homework.
You should generate code in the order these items are discussed below.
(2 points) Push the old fp onto the stack, so you can restore it when you return.
(3 points) Allocate enough stack space for all your local variables at once by subtracting from the sp.
(2 points) Copy the sp to the fp so the fp will point to the top of your local variables.
(3 points) Push any registers you use to evaluate your expressions. You may assume you will use them from lowest number first (R0) up to the number you need (say R3 if you need four registers). You will later pop them to restore their value, but you must pop them in the reverse order because they are on the stack.
(10 points) Generate machine code for the assignment statements for the machine described above. You may use simple left-to-right operand evaluation if you only get this far, but you will do better as you finish the points below. This is similar to the generation of three address code from an earlier homework, but you must modify the algorithm somewhat. You may use your temporary manager to manage register allocation.
(3 points) Restore the values to the registers you used, but be sure to restore them in reverse order to what you saved them.
(3 points) Deallocate the stack space for local variables.
(2 points) Restore the old fp from the value you saved on the stack.
The remainder of these items are improvements in the quality of code you generate.
(20 points) Assign Sethi-Ullman labels to each node in the tree. (Reference: page 562 of the text).
(20 points) Use the Sethi-Ullman labels to generate code for the machine above using minimal number of registers. (Reference: page 564 of the text).
(20 points) Exploit the algebraic properties of the commutative operators: + and * to swap operands whenever the register count of the left operand is less than the register count of the right operand.
Do not do any other optimizations.
Prove how well your code generator does by giving interesting test inputs and showing the real code it generates with operand switching and generating different operands depending on the sethi-ullman labels.

Elaboration:

Suppose you need 64 bytes for local variables (as you would need in the example above) and you required three registers to evaluate the worst subexpression in your program. You would output something like this:

push fp # save the caller's fp
sub 64,sp # allocate all the local variable space
mov sp,fp # setup our fp, so we can access local variables offset(fp)
push r0 # save the registers we will use (caller may need values)
push r1
push r2
mov ... # code for assignment statements
pop r2 # restore the registers we saved
pop r1
pop r0
add 64,sp # deallocate the local variable space
pop fp # restore the caller's fp
ret # return to the caller (whose address is on top of stack)