Optimization Flashcards Preview

CS 241 > Optimization > Flashcards

Flashcards in Optimization Deck (23):

What criteria do we us to decide if one compiled MIPS code is better than another?

Time it takes for the program to run


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


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


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


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


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.


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


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


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


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


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


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


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


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)


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 ;


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


What is dead code?

Code that never gets executed :(


When can dead code occur?

The logical test in an if statement is always false

Code is after a return statement


What is strength reduction?

Replacing operations with faster ones


What is inlining?

Replace the function call with the body of the entire code


What are the pros and cons of inlining?

- No need to generate code for that function
- Save overhead of creating a stack frame for f

- If the function is used often, generate a lot of extra code
- Difficult for recursive functions


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


Since patterns are hard to find in source code, what can we do?

Use intermediate code after lexical, syntactic and semantic analysis is finished.

The intermediate code is easier to optimize and is then converted into assembly.