Optimization Flashcards

1
Q

4 optimization methods

A

peephole, moving loop-invariant computations, strength reduction in for loops, copy propagation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

When is peephole optimization done?

A

after code generation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

When are moving loop-invariant computations done?

A

before code generation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

When are strength reduction in for loops done?

A

before code generation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

When is copy propagation done?

A

before code generation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Moving Loop-Invariant Computations

A

Finds computations inside loops that can be moved outside (speed up execution time of the loop)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Strength Reduction in for loops

A

Replace multiplications inside loops with addition (addition is faster)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Copy propagation

A

Replaces the use of a variable with a literal or another variable, can be used to uncover opportunities for loop-invariant computations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Types of peephole optimization

A

remove redundant load, remove redundant push/pop, replace a jump to a jump, remove a jump to next instruction, replace a jump around jump, remove useless operations, reduction in strength (use faster, specialized registers instead of slow general-purpose)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

loop invariant

A

same value is computed for that expression on every iteration of the loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How do we recognize loop-invariant expressions?

A

An expression is an invariant if 1) it is a literal or 2) it is a variable that gets its value only from outside the loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

When/how do we move loop-invariant expressions?

A

must consider safety and profitability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

loop-invariant safety

A

if expression might cause error, might be problem if expression might not be executed in original code; order of events preserved

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

profitability

A

if the computation might not execute in the original program, moving the computation might actually slow the program down

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

When is moving a computation both safe and profitable?

A

1) it can be determined the loop with execute at least once and code is guarunteed to execute if it does
2) the expression is in a non-short circuited part of the loop test/loop bounds

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

induction expression in strength reduction in for loops

A

L*M + C

L = loop index

17
Q

copy propagation

A

x = y -> replace x with y if no changes in x or y

18
Q

Why is copy propagation useful?

A

if all uses of x reached by d are replaced, then definition of d is useless, lead to improved code (MIPs has faster registers for int literals),