CSE2304, Prac' 2, week 3 and 4, 15-26 March 1999

The simple parser for arithmetic expressions builds a parse tree for expressions such as a*b+c*d; see the C/Tree/ directory. The objective is to add a routine which will generate assembly code for a hypothetical MIPS-style computer while traversing such a parse tree. The value of the expression is to be left in register one. (Register zero holds the constant zero.)

Write a routine which traverses the parse tree, compiling code to evaluate the expression into register `n'. If the operand of the next operator is simple, i.e. an identifier, code is compiled to load it into register `n+1' and then combine it with the partial result already in register n (see *b below). If the next operand is a complex sub-expression, code must be compiled to evaluate the subexpression into register `n+1' first (see c*d/e below).

<op>     ::= <memopcode> <reg> <identifier> |
             <opcode> <reg> <reg> <reg>
<opcode> ::= ADD | SUB | MULT | DIV
<memopcode> ::= LOAD | STORE
<reg>    ::= R0 | R1 | R2 | ...

The computer has a large number of general purpose registers R1, R2, ... etc.. Each opcode, other than LOAD and STORE, acts on three registers.

a*b+c*d/e  --->  LOAD R1 a          -- R1<-a
                 LOAD R2 b
                 MULT R1 R1 R2      -- R1<-a*b
                 LOAD R2 c          -- NB. R2
                 LOAD R3 d
                 MULT R2 R2 R3
                 LOAD R3 e
                 DIV  R2 R2 R3
                 ADD  R1 R1 R2      -- R1<-R1+R2

[CSE2304: 5 marks.]
[CSC2040: 6 marks.]

2.

The computer is actually more complex than sketched above: Multiplication and division use two extra registers `Hi' and `Lo'. Multiplication produces a double-length result in <Hi,Lo>. Division produces a remainder and a quotient in Hi and Lo respectively. Data can be `MOVE'd between Hi, Lo and the other registers. Modify the code generator to deal with this.

<op> ::= <memopcode> <reg> <identifier> |
         <opcode> <reg> <reg> <reg> |
	 <MDop> <reg> <reg> |
	 MOVE <reg> <hilo> | MOVE <hilo> <reg>
<opcode> ::= PLUS | SUB
<MDop> ::= MULT | DIV
<memopcode> ::= LOAD | STORE
<hilo> :== Hi | Lo

e.g. a*b    ---> LOAD R1 a
	         LOAD R2 b
	         MULT R1 R2     -- result in <Hi,Lo>
	         MOVE Lo R1

[CSE2304: 1 mark.]
[CSC2040: Optional, 2 mark bonus.]

3. Advanced

If the number of registers is limited, the simple compilation strategy may eventually run out of registers for a sufficiently complex expression.

Modify your compiler so that it can store `partial results' out of the registers into temporary variables in memory, and therefore compile more complex expressions.

The number of registers needed can also be reduced by reordering suitable expressions so that more complex operands come first,

a+b*c (3 registers) ---> b*c+a (2 registers)

[CSE2304: Optional, 2 bonus marks.]
[CSC2040: do not attempt, zero marks.]

L.Allison, Comp. Sci. and S.W.E., Monash University, Australia.