Optimization Flashcards
4 optimization methods
peephole, moving loop-invariant computations, strength reduction in for loops, copy propagation
When is peephole optimization done?
after code generation
When are moving loop-invariant computations done?
before code generation
When are strength reduction in for loops done?
before code generation
When is copy propagation done?
before code generation
Moving Loop-Invariant Computations
Finds computations inside loops that can be moved outside (speed up execution time of the loop)
Strength Reduction in for loops
Replace multiplications inside loops with addition (addition is faster)
Copy propagation
Replaces the use of a variable with a literal or another variable, can be used to uncover opportunities for loop-invariant computations
Types of peephole optimization
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)
loop invariant
same value is computed for that expression on every iteration of the loop
How do we recognize loop-invariant expressions?
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
When/how do we move loop-invariant expressions?
must consider safety and profitability
loop-invariant safety
if expression might cause error, might be problem if expression might not be executed in original code; order of events preserved
profitability
if the computation might not execute in the original program, moving the computation might actually slow the program down
When is moving a computation both safe and profitable?
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
