| Optimization Name |
Explanation |
% |
| High-level |
At or near the source level; machine independent |
|
| Procedure integration (function inlining) |
Replace procedure call by procedure body |
N.M. |
| Local |
Within straight line code |
|
| Common sub-expression elimination |
Replace two instances of the same computation by single copy
In the expression "(a+b)-(a+b)/4", "common subexpression" refers to the
duplicated "(a+b)". Compilers implementing this technique realize that "(a+b)"
won't change, and as such, only calculate its value once. |
18% |
| loop unrolling |
Attempts to reduce the overhead inherent in testing
a loop's condition by replicating the code in the loop body. Completely
unrolling a loop, of course, requires that the number of iterations be known
at compile time. |
|
| loop combining |
Another technique which attempts to reduce loop
overhead. When two adjacent loops would iterate the same number of times
(whether or not that number is known at compile time), their bodies can be
combined as long as they make no reference to each other's data. |
|
| test reordering |
if we have two tests that are the condition for
something, we can first deal with the simpler tests (e.g. comparing a variable
to something) and only then with the complex tests (e.g. those that require a
function call). This technique complements
lazy evaluation, but can be used only when the tests are not dependent on
one another. |
|
| dead (unreachable) code elimination |
Remove instructions that will not affect the
behavior of the program. For example in "int myFunc(int a){int b,c; b=a*2;
c=a*3; return b;}" the statement "c=a*3" doesn't do anything useful and can be
removed |
|
| Constant propagation (folding) |
Replace all instances of a variable that is assigned a constant with the constant
replacing expressions consisting of constants (e.g. "3 + 5") which their final
value ("8") rather than doing the calculation in run-time. Used in most modern
languages.
|
22% |
| remove recursion |
recursion is often expensive as it involves the
function call overhead, and inconvenient as it can rapidly deplete the stack.
Tail recursion algorithms can be converted to
iteration, which does not have call overhead and uses a constant amount of
the stack. |
|
| Stack height reduction |
Rearrange expression tree to minimize resources needed for expression evaluation |
N.M. |
| Global |
Across |
|
| Global sub-expression elimination |
Same as local, but this version crosses branches |
13% |
| Copy propagation |
Replace all instances of a variable A that has been assigned X (i.e. A=X) with X |
11% |
| Code motion
(factoring out of invariants) |
Remove code from a loop that computes same value each iteration of the loop
if an expression is carried out both when a condition is met and
otherwise, it can be written just once outside of the conditional statement.
Similarly, if certain types of expressions (e.g. the assignment of a constant
into a variable) appear inside a loop, they can be moved out of it because
their effect will be the same no matter if they're executed many times or just
once. Also known as total redundancy elimination. A more powerful optimization
is partial redundancy elimination (PRE).
|
16% |
| Induction variable elimination |
Simplify/eliminate array-addressing calculations within loops |
2% |
| Machine dependent |
Depends on machine knowledge |
|
| Strength Reduction |
Many examples, such as replace multiply by a constant with adds and shifts |
N.M. |
| Pipeline scheduling |
Reorder instructions to improve pipeline performance |
N.M. |
| Branch offset optimization |
Choose the shortest branch displacement that reaches target |
N.M. |