UNIT-5 Contd…
UNIT-5 TOPICS in this slide
• Peephole optimization.
• Transformation of basic blocks,
• Machine-Independent Optimizations:
• The principal sources of optimization:
• Global common Sub-Expressions,
• Copy Propagation,
• Dead-Code Elimination
PEEPHOLE OPTIMIZATION
• An effective technique for locally improving the target code is
called peephole optimization.
• A method for trying to improve the performance of the target
program by examining a short sequence of target instructions
(called peephole) and replacing these instructions by a shorter /
faster sequence, whenever possible.
• Peephole is a small, moving window on the target program. The
code in peephole need not be continuous.
• Following examples of program transformation that are
characteristic of peephole optimization
1. Redundant instruction elimination
2. Flow of control optimization
3. Algebraic simplification
4. Use of machine idioms
5. Reduction in strength
Peephole Optimization: Redundant instruction elimination
• Redundant Loads and Stores: The following instructions are
redundant
MOV R0, a // a=R0
MOV a, R0 // R0=a
• Because after loading ‘R0’ to ‘a’, immediately we are loading ‘a’
to ‘R0’ which has no meaning. Hence one of the instructions can
be eliminated.
• Unreachable code: A code which cannot be reached can be
eliminated.
gotoAn
L unlabeled instruction immediately following an
ADD jump This instruction will never be
R0, instruction
unconditional may be removed.
executed (unreachable) and hence
R1
Example:
#define debug 0 can be removed
If(debug) {
printf(“debugging This instruction will never be
info”) executed (unreachable) since
} debug is always 0
2) Flow of control optimizations
• The intermediate code generation algorithms frequently produce
jumps to jumps, jumps to conditional / unconditional jumps.
• These unnecessary jumps can be eliminated in intermediate code
/ target code by following types of peephole optimizations:
i) We can replace unconditional jump to jump sequences
goto L1
goto L2
…
L1: goto L2
ii) We can replace conditional jump to jump sequences:
if (a<b) goto L1 if (a<b) goto L2
…
L1: goto L2
Peephole Optimization
3) Algebraic Simplifications
• Statements like x=x+0, x=x*1 can be eliminated since
both of them assign ‘x’ to ‘x’.
• Wherever possible multiplications can be replaced by
additions.
• For example: 2*A can be replaced by A+A
4) Reduction in strength:
• Expensive operations can be replaced by equivalent
cheaper ones on the target machine.
• For example: x2 can be replaced by x*x as multiplication
is cheaper than exponentiation.
5) Use of Machine Idioms
• The target machine may have hardware instructions to
implement certain specific operations efficiently.
• Detecting situations that permit the use of these
instructions can reduce execution time significantly.
• For example, some machines have auto-increment and
auto-decrement addressing modes.
• Example: Increment instruction (INC) improves
the quality and the size of the code.
A=A+1 INC A (or) MOV A, R0
ADD #1, R0
TRANSFORMATIONS ON BASIC
BLOCKS
• Basic block computes set of expressions.
• Two basic blocks are equivalent if they compute same
set of expressions.
• Following transformations can be applied to a basic
block without changing the set of expressions computed
by the block.
1) Structure Preserving Transformations
a) Common sub-expression elimination
b) Dead-code elimination
c) Renaming temporary variables
d) Interchange of statements
2) Algebraic Transformations
Structure Preserving Transformations
1)(1)
Common subexpression elimination:
a:=b+c (1)
- Statements (2) and (4) both
(2) b:=a- a:=b+c compute same expression “a-
d (2) b:=a-d d”. Hence (4) replaced by d:=b.
- But (1) and (3) are not changed
(3) (3)
since statement (2) changes
c:=b+c c:=b+c the value of ‘b’
(4) d:=a- (4) d:=b
2) Dead code elimination: Code which is unreachable is known as
d dead code. Dead code can be eliminated.
3) Renaming temporary variables: Suppose we have a
statement t:=b+c, where ‘t’ is a temporary variable. If we
change to u:=b+c, where ‘u’ is a new temporary variable and
change all uses of this instance of ‘t’ to ‘u’, then the value of the
basic block is not changed.
Structure Preserving
Transformations
4) Interchange of Statements
Suppose we have a block with two adjacent
statements
t1:=b+c
t2:=x+y
Then, we can interchange the two statements
without affecting the value of the block if and only
if neither x nor y is t1 and neither b or c is t2.
ALGEBRAIC TRANSFORMATIONS
Following algebraic transformation can be
performed:
• x:=x+0 or x:=x*1 can be eliminated from a basic
block without changing the set of expressions it
computes.
• x:= y**2 can be replaced by cheaper operation
x:=y*y since multiplication is cheaper than
exponentation.
• x:=2*a can be replaced by x:=a+a since addition is
cheaper than multiplication.
PRINCIPLE SOURCES OF OPTIMIZATION
• Here, we see code improving transformations.
• A transformation is local if it can be performed by looking
only at the statements in the basic block ; otherwise, it is
global.
• Following are the principle sources of optimization
• Function preserving transformations
Common subexpression elimination
Copy propagation
Dead code elimination
• Loop optimizations
Code motion
Induction variable elimination
Reduction in strength
FUNCTION PRESERVING TRANSFORMATIONS
• Here, the compiler improves a program without changing the
function it computes.
1) Common sub-expression elimination:
• An occurrence of ‘E’ is called a common sub-expression if ‘E’ was
previously computed, and values of variables in ‘E’ have not changed since
the previous computation.
• We can avoid recomputing the expression if we can use the previously
computed value.
• For example, the unoptimized three address code for: (b+c)*(a-d)*(b+c+d)
is:1) t1=b+c Statements (1) and (3) are
computing the same expression 1) t1=b+c
2) t2=a-d
“b+c” hence statement (3) is 2) t2=a-d
3) t3=b+c
removed 3) t3=t1+d
4) t4=t3+d
4) t4=t1*t2
5) t5=t1*t2
5) t5=t4*t3
6) t6=t5*t4
FUNCTION PRESERVING TRANSFORMATIONS
2) Copy propagation:
• Common subexpression elimination sometimes yields
copies or copy statements. t:=d+ t:=d+
a:=d b:=d e e
+e +e a:=t b:=t
c:=d+
c:=t
e
• Here, when common subexpression d+e is eliminated, a
new variable ‘t’ is used to hold value of ‘d+e’ and new
copy statements a:=t, b:=t are introduced.
FUNCTION PRESERVING TRANSFORMATIONS
3) Dead Code Elimination:
• A variable is live at a point in a program if its value can be
used subsequently; else it is dead at that point.
• A related idea is dead / useless code. The statements that
compute values that never get used. For example:
x:=t3
a[t2]:=t
a[t2]:=t
5
5 Eliminate dead code
x:=t3 a[t4]:=t
a[t4]:=t
3
3
goto B2
goto B2
• Usually copy propagation yields dead code.
• Deducing at compile time that the value of an expression is a
constant and using the constant instead is called constant
folding
LOOP OPTIMIZATIONS
• The running time of a program may be improved if we decrease
the number of instructions in an inner loop, even if we increase
the code outside the loop.
1) Code Motion
• It moves code outside the loop.
• It takes the expression that yields the same result independent of
the number of times a loop is executed (a loop invariant
computation) and places the expression before the loop.
• In the following example, the transformation does not change the
value of the limit variable. It just moves the expression “limit-2”
outside the loop so that it is computed only once. However, if
limit t=limit-2;
whilewas being used inside the loop
(i<=limit- then this movement is not
possible. while
2)
(i<=t)
LOOP OPTIMIZATIONS
2) Induction variables
• An induction variable is a variable in a loop whose value
changes in a predictable pattern (e.g., increasing or
decreasing by a constant value in each iteration).
for (int i = 0; i < n; i++) {
Sum=Sum + A[i];
}
• Here, i is an induction variable because it changes in a
regular pattern (i = i + 1).
• A basic induction variable increments or decrements by a
fixed amount in each iteration. Example: i=i+1, j = j-2.
• Derived induction variable is a variable whose value is a
function of a basic induction variable. Example: j=2*i (‘j’ is a
derived induction variable which depends on basic induction
variable ‘i’)
LOOP OPTIMIZATIONS
3) Reduction in strength:
• Replace expensive operations (e.g.,
multiplication) with cheaper ones (e.g.,
addition).
• Examples:
- “a2” can be replaced by multiplication
“a*a”
- “2*a” can be replaced by addition “a+a”
