Code Generation/Optimization

Question 1

What is x = y - z translated to?

Answer 1

LD R1, y
LD R2, z
SUB R1, R1, R2
ST x, R1

Question 2

What is if x < y goto L translated to?

Answer 2

LD R1, x
LD R2, y
SUB R1, R1, R2
BLTZ R1, L

Question 3

What is x = *p translated to?

Answer 3

LD R1, p
LD R2, 0(R1)
ST x, R2

Question 4

What is *p = x translated to?

Answer 4

LD R1, p
LD R2, x
ST 0(R1), R2

Question 5

What is b = a[i] translated to?

Answer 5

LD R1, i
MUL R1, R1, 8 - 8 byte elements
LD R2, a(R1) - a=array
ST b, R2

Question 6

What is a[j] = c translated to?

Answer 6

LD R1, c
LD R2, j
MUL R2, R2, 8
ST a(R2), R1

Question 7

Describe the Cost Function for code generation?

Answer 7

All instructions have cost 1.
Register access has cost 0.
Accessing memory location has cost 1.

Question 8

What does a procedure call look like in assembly?

Answer 8

Initialization - ST SP, #stackStart

ADD SP, SP, #caller.recordSize
ST *SP, #next
BR callee.codeArea
SUB SP, SP, #caller.recordSize

Return - BR *0(SP)

Where SP = p.static area, p’s activation record where the return address is stored.

Question 8

What is a basic block?

Answer 8

A sequence of three-address instructions such that there are no jumps in the middle of the block and no instruction in the block halts or branches, except the last.

Question 9

What is a flow graph?

Answer 9

Has basic blocks as nodes and edges that caputre control flow between the blocks.

Question 10

How to convert a basic block into a DAG?

Answer 10

Initial values of variables are nodes.
For each statement, create a node:
- Labelled by operator
- Annotated with variable which is assigned in statement
- Children are nodes used in statement

Reconstitute a TAC once generated.

Question 11

What are the local optimizations that can take place?

Answer 11

• Local common subexpressions
• Dead code elimination
• Arithmetic transformations
• Copy propagation
• Elimination of redundant loads/stores
• Flow of control optimizations

Question 12

What is a data-flow analysis?

Answer 12

• Global optimizations depend on these.
• Derive information about the flow of data along program execution paths in a flow graph.
• Analyse state of a program before and after each statement.

Data-flow value = abstraction of the state before/after a statement.
IN[s] = data flow values before s, OUT[s] = after.