Optimization

Question 1

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

Answer 1

Time it takes for the program to run

Question 2

In the context of compilation, what is heuristics?

Answer 2

Recognizing a pattern of instructions and replacing them with an equivalent set that:

a) runs quicker or
b) uses a smaller # of instructions

Question 3

Do repeated patterns in generated code come from the WLP4 source code?

Answer 3

Not necessarily, patterns can appear because code is generated from individual nodes in a parse tree

Question 4

What is the basic idea behind common subexpression elimination?

Answer 4

Store the results of common subexpressions in registers that can be called when code is generated

Question 5

How would you generate code for (a+b) * (a+b) using common subexpression elimination?

Answer 5

• Calculate a+b and store in $3
  mult $3, $3
  mflo $3

Question 6

What do you need to be careful of when using common subexpression elimination?

Answer 6

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.

Question 7

What is the justification for keeping track of live ranges?

Answer 7

• 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

Question 8

What is a live range?

Answer 8

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

Question 9

Why do we use live ranges

Answer 9

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

Question 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) ;

Answer 10

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

Question 11

How does code generation with avail work?

Answer 11

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

Question 12

Using avail and the new code(), generate code for:
expr1 -> expr2 + term

Answer 12

code(expr1, avail) = 
s = code(expr2, avail)
t = code(term, avail\{s} ) 
add $s, $s, $t 
return s

Question 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?

Answer 13

Instead of loading constants, just calculate answers involving constants at compile time:

lis $3
.word 5

Question 14

How many lines of MIPS does the following WLP4 code need without constant propogation?

int x = 2 ;
return x + x ;

Answer 14

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)

Question 15

What is constant propagation?

Give an example

Answer 15

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 ;

Question 16

How would one implement constant propagation?

Answer 16

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

Question 17

What is dead code?

Answer 17

Code that never gets executed :(

Question 18

When can dead code occur?

Answer 18

The logical test in an if statement is always false

Code is after a return statement

Question 19

What is strength reduction?

Answer 19

Replacing operations with faster ones

Question 20

What is inlining?

Answer 20

Replace the function call with the body of the entire code

Question 21

What are the pros and cons of inlining?

Answer 21

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

Question 22

How can you optimize tail recursion?

Answer 22

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

Question 23

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

Answer 23

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

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