CISC458 Winter 2022 - Assignment 4
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).
2022-03-31