Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CISC458 Winter 2022 - Assignment 4

1.  (15 points) This problem is based on the simple language discussed in the code generation lectures of Week 10.

The grammar description of the language is as follows:

P ✙ D; P  | D

D ✙  def  id(ARGS)  = E;

ARGS ✙  id, ARGS  |  id

E ✙  int  |  id  |  if E1  = E2 then E3  else E4  | E1  + E2  | E1  { E2  |  id(E1,...,En)

 

Provide the code generation for the following function definition, written using the above language:

def  sumto(x)  =  if x  =  0 then  0  else x  +  sum(x-1)

sumto(x) recursively sums numbers from 0 to x.

A few notes:

❼ The generated code will be constructed as a number of templates glued together.  In

this case, you will be using the code generation functions (seen in class) for function definition, variables, constants, if-statements, functions calls, and sum.

❼ For each expression e, the value of e should end up in ✩a0, and the evaluation should

preserve ✩sp.

❼ Labels are used in MIPS to refer to the location of an instruction (e.g.  sum to entry,

true, and false below), and can be used as needed when jumping is needed.


Starting skeleton of code generation

sum to entry:

move  ✩fp  ✩sp

sw  ✩ra  0(✩sp)

....

false:    ....

....

true:    ....


2.  (10 points) Consider the following assembly language used to program a stack machine (r, r1, and r2 denote arbitrary registers):

 

push  r:   copies  the  value   of  r  and  pushes   it   onto  the   stack.

top  r:   copies  the  value   at  the  top  of  the   stack   into  r.  This   command does  not  modify  the   stack.

pop:  discards  the  value   at  the  top  of  the   stack.

swap:   swaps  the  value   at  top  of  the   stack  with  the  value   right  beneath it.  E.g.  if  the   stack  was  <✩   ...  5  2>   swap  would   change  the   stack

to  be  <✩   ...  2  5>

r1  +=  r2:  adds  r1  and  r2  and   saves  the  result   in  r1.  r1  may  be  the same   as  r2.

r1   -=  r2:   subtracts  r2  from  r1  and   saves  the  result   in  r1.  r1  may  be the   same   as  r2.

clamp  r:   sets  r  to  0  if  r  is  negative   otherwise   leaves  r  unchanged

jump  r:  jumps  to  the   address   in  r  and  resumes   execution.

ite  r1  r2  r3:  if  r1  not   is   equal  to  zero  then   jumps  to  the   address   in r2   else   jumps  to  the   address   in  r3.

loadconst  r   int:  loads  a   constant   int   into  r

loadlabel  r  label:  loads  the   address   of  a  labeled   code   segment   into  r.

Provide a code generation function for each the of these instructions, except loadlabel, tar- geting MIPS. Assume that registers used in the stack language are valid MIPS registers. Use ✩sp to hold a pointer to the top of the stack and a single temporary register ✩at which is guaranteed to not appear in the stack language.


cgen(push  r)  =

cgen(top  r)  =

cgen(pop)  =


cgen(swap) cgen(r1  += cgen(r1   -=

cgen(clamp


=

 

r2)  =

r2)  =

r)  =


cgen(jump  r)  = cgen(ite  r1  r2

cgen(loadconst


 

r3)  =

r   int)  =


3. Consider the following basic block, in which all variables are integers.

1            x   :=  0  *  5

2            y   :=  a  +  b

3            z   :=  x  *  x

4             c   :=  y  *  x

5            x   :=  x  +  4

6             e   :=  c  -  x

7            x   :=  e  *  x

8            f   :=  a  +  b

9            y   :=  y  +  f

 

(a)  (5 points) Assume that the only variables that are live at the exit of this block are x and

y, while a and b are given as inputs. In order, apply the following optimizations to this basic block.  Show the result of each transformation.  For each optimization, you must continue to apply it until no further applications of that transformation are possible (if any were), before writing out the result and moving on to the next.

i. Algebraic simplification

ii. Common sub-expression elimination

iii. Copy propagation / Constant propagation

iv. Algebraic simplification

v. Dead code elimination

(b)  (3 points) The resulting program is still not optimal. What optimizations, in what order,

can you apply to fully optimize the result? Show the maximally optimized codes (with least number of instructions).