What is x = y - z translated to?
LD R1, y
LD R2, z
SUB R1, R1, R2
ST x, R1
What is if x < y goto L translated to?
LD R1, x
LD R2, y
SUB R1, R1, R2
BLTZ R1, L
What is x = *p translated to?
LD R1, p
LD R2, 0(R1)
ST x, R2
What is *p = x translated to?
LD R1, p
LD R2, x
ST 0(R1), R2
What is b = a[i] translated to?
LD R1, i
MUL R1, R1, 8 - 8 byte elements
LD R2, a(R1) - a=array
ST b, R2
What is a[j] = c translated to?
LD R1, c
LD R2, j
MUL R2, R2, 8
ST a(R2), R1
Describe the Cost Function for code generation?
All instructions have cost 1.
Register access has cost 0.
Accessing memory location has cost 1.
What does a procedure call look like in assembly?
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.
What is a basic block?
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.
What is a flow graph?
Has basic blocks as nodes and edges that caputre control flow between the blocks.
How to convert a basic block into a DAG?
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.
What are the local optimizations that can take place?
- Local common subexpressions
- Dead code elimination
- Arithmetic transformations
- Copy propagation
- Elimination of redundant loads/stores
- Flow of control optimizations
What is a data-flow analysis?
- 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.
