Machine-Independent
Optimization
Saumya Debray
Dept. of Computer Science
The University of Arizona Tucson, AZ 85721
Code Optimization
• Aim: to improve program performance.
– “optimization” a misnomer: attaining “optimal”
performance is impossible or impractical in general.
• Criteria:
– must be “safe,” i.e., preserve program semantics;
– on average, should improve performance measurably;
• occasionally, a few programs may suffer performance
degradation.
– the transformation should be worth the effort.
Program Analysis and Optimization 2
Code Optimizer Organization
Program Analysis and Optimization 3
Code Optimization: Basic
Requirements
• Fundamental Requirement: safety.
The “observable behavior” of the program (i.e., the
output computed for any given input) must not
change.
• Program analyses must be correspondingly
safe.
– most runtime properties of a program are statically
undecidable.
– static program analyses are (necessarily) imprecise.
– any imprecision must be in the direction of safety.
Program Analysis and Optimization 4
Some Important Optimizations
• Loop transformations:
– reduces the number and/or cost of instructions within
loops. Examples:
• invariant code motion out of loops
• induction variable elimination
• loop unrolling
• Function-preserving transformations:
– reduces unnecessary computations, but not aimed
specifically at loops. Examples:
• common subexpression elimination
• copy propagation
• dead/unreachable code elimination
• function inlining
Program Analysis and Optimization 5
Optimization 1. Common Subexpression
Elimination
• Goal: to detect and eliminate repeated
computations of the same expression.
• Can be done at two different levels:
– Local CSE:
• scope limited to a single basic block
• uses value numbering (discussed under DAG
representation) to identify common subexpressions.
– Global CSE:
• applies across basic block boundaries
• uses available expressions analysis.
Program Analysis and Optimization 6
Global Common Subexpression
Elimination
Uses available expression
information to identify
common
subexpressions
Program Analysis and Optimization 7
Global CSE: Algorithm
• Compute available expressions for each block.
• Process each block B as follows:
• for each instruction I ‘x = y z’ where ‘y z’ is
available immediately before I, do:
1. find the evaluations of ‘y z’ that reach I:
traverse B, and then the control flow edges, backwards, not
going beyond any block that evaluates ‘y z’.
2. create a new variable u.
3. replace each instruction ‘w = y z’ found in (1) by the
following:
u=yz
w=u
4. replace instruction I by ‘x = u’.
Program Analysis and Optimization 8
Comments on Global CSE
• For “lightweight” expressions (e.g., ‘*p’), CSE may be
profitable only if the expression can be kept in a register.
But this means that the register is unavailable for other uses.
• The algorithm given will miss the fact that ‘t1*4’ and ‘t3*4’
have the same value in
t1 = x+y
t2 = t1*4
t3 = x+y
t4 = t3*4
This can be handled by iterative applications of global
CSE, or alternatively via copy propagation.
Program Analysis and Optimization 9
Optimization 2. Copy Propagation
• Copy instructions:
– of the form ‘x = y’
– arise from normal code generation (e.g., assignment
of an expression), and also as a result of
optimizations such as global CSE.
• Goal of Copy Propagation:
Given a copy instruction ‘x = y’, attempt to replace
subsequent uses of x by y.
Program Analysis and Optimization 10
Copy Propagation: Example
Program Analysis and Optimization 11
When is Copy Propagation Legal?
• OK:
• Not OK:
• Not OK:
Program Analysis and Optimization 12
Legality Conditions for Copy
Propagation
A copy instruction s ‘x = y’ can be propagated to
a use u of x if:
1. s is the only definition of x reaching u; and
2. there is no path from s to u that redefines y and
which does not then go through s again.
Condition 1 can be checked using u-d chains.
This is is generalization of reaching definitions that
associates, with each use u of a variable x, all the
definitions of x that reach u.
Program Analysis and Optimization 13
Effects of Copy Propagation
• When a copy instruction s ‘x = y’ is propagated
to uses of x, the no. of uses of s decreases.
• If the number of uses of s goes to 0, then s
becomes dead code, and can be eliminated.
Program Analysis and Optimization 14
Optimization 3. Dead Code
Elimination
• Definition: An instruction is dead if the value it
computes can be guaranteed to not be used.
I ‘x = e’ is dead if
– x is dead at the point immediately after I, and
– the evaluation of e has no side effects on any variable
that is live at the point after I.
Dead code can arise due to other optimizations,
e.g., constant propagation, copy propagation.
Program Analysis and Optimization 15
Dead Code and its Elimination
• Eliminating a dead instruction can cause other
instructions to become dead:
(1) x = y + z
v dead; w, x live
(2) w = 4 * x
v, x dead; w live
(3) v = w + 1
v, w, x dead; instr. (3) dead
Goal: Identify instructions that are (a) dead, or (b) will
become dead once other dead instructions are
eliminated.
Program Analysis and Optimization 16
Dead Code Elimination: Algorithm
1. mark all instructions ‘live’;
2. repeat
for each instruction I ‘x = …’ {
if the value of x defined by I
(i) is not visible outside the current function; and
(ii) is not used by any instruction J (J I) marked
‘live’ {
mark I ‘dead’;
}
}
until no more instructions can be marked.
Program Analysis and Optimization 17