Flashcards in Optimization Deck (23):
1
What criteria do we us to decide if one compiled MIPS code is better than another?
Time it takes for the program to run
2
In the context of compilation, what is heuristics?
Recognizing a pattern of instructions and replacing them with an equivalent set that:
a) runs quicker or
b) uses a smaller # of instructions
3
Do repeated patterns in generated code come from the WLP4 source code?
Not necessarily, patterns can appear because code is generated from individual nodes in a parse tree
4
What is the basic idea behind common subexpression elimination?
Store the results of common subexpressions in registers that can be called when code is generated
5
How would you generate code for (a+b) * (a+b) using common subexpression elimination?
- Calculate a+b and store in $3
mult $3, $3
mflo $3
6
What do you need to be careful of when using common subexpression elimination?
It may not work with functions (e.g. f(1) + (f(1) ) because the function may have side effects that won't be repeated if you only run the function once.
7
What is the justification for keeping track of live ranges?
- We want a way to store common subexpressions
- But what if we have a lot of local variables or subexpressions?
- We want to use registers as much as possible since accessing registers is quick and reduces the amount of time we have to use lw and sw
- So we want a way to optimize our register allocation
8
What is a live range?
The live range of a variable is the range starting from where it is a assigned a value to where it is last used with that value
9
Why do we use live ranges
Live ranges allow us to determine if we can re-use registers for values. If the live ranges of two variables don't intersect, then the register can be reused
10
What are the live ranges for each variable?
int x = 0 ;
int y = 0 ;
int z = 0 ;
x = 4 ;
y = 5 ;
x = x + 1 ;
println(x) ;
println(y) ;
z = 7 ;
println(z) ;
The live range for x is 4-7 inclusive
The live range for y is 5-8 inclusive
The live range for z is 9-10 inclusive
11
How does code generation with avail work?
Avail - List of available registers
Code(Parse tree node, avail) -> register where result is located
When evaluating more than one node, the next code() is called with the old avail, without the register used to store the previous result
This allows us to keep track of what registers are being used to store results
12
Using avail and the new code(), generate code for:
expr1 -> expr2 + term
code(expr1, avail) =
s = code(expr2, avail)
t = code(term, avail\{s} )
add $s, $s, $t
return s
13
This is the code for (2 + 5):
lis $3
; load 2
lis $3
.word 2
.word 5
sw $3, -4(30) ; push 2 on stack
sub $30, $30, $4
lis $3 ; load 3
.word 3
lw $5, 0($30) ; pop 2 off stack
add $30, $30, $4
add $3, $5, $3 ; answer
How can you use constant folding to make this more efficient?
Instead of loading constants, just calculate answers involving constants at compile time:
lis $3
.word 5
14
How many lines of MIPS does the following WLP4 code need without constant propogation?
int x = 2 ;
return x + x ;
Answer: 10
- load 2 into $3 (2: lis, .word)
- store result in x (1: sw)
- push onto stack (3: lw, sw, sub)
- load value stored in x into $3 (1: lw)
- move x from stack into $5 (2: lw, sub)
- add $5, $3, store in $3 (1: add)
15
What is constant propagation?
Give an example
When the compiler recognizes that a constant can be used in place of a variable, greatly simplifying the code associated with the instruction.
The compiler recognizes that:
x = 5 ;
y = 3 ;
z = x + y ;
Is the same as:
z = 8 ;
16
How would one implement constant propagation?
When nodes of a parse tree are evaluated, instead of just placing the value in $3, return an (encoding, value) pair.
This way, most expressions can be evaluated with two lines of MIPS
e.g. expr1 -> expr2 + term
expr2 -> (const, 2)
term -> (const, 3)
So expr1 is just (const, 5), which is just
lis $3
.word 5
17
What is dead code?
Code that never gets executed :(
18
When can dead code occur?
The logical test in an if statement is always false
Code is after a return statement
19
What is strength reduction?
Replacing operations with faster ones
20
What is inlining?
Replace the function call with the body of the entire code
21
What are the pros and cons of inlining?
Pros:
- No need to generate code for that function
- Save overhead of creating a stack frame for f
Cons:
- If the function is used often, generate a lot of extra code
- Difficult for recursive functions
22
How can you optimize tail recursion?
Since the recursive call is the very last thing a function does, you can re-use the stack frame since you dont need to save the local variables
23