Semantics-Preserving Transformations
● Compiler can improve a program without changing the function it computes.
● Some of the ways are -
○ Common-subexpression elimination,
○ Copy propagation
○ Dead-code elimination,
○ Constant folding
● These are all Machine Independent Optimization Techniques
cd_sk@vit.ac.in 07/07/2023 29
Common Subexpressions
● An occurrence of an expression E is called a common subexpression if E was
previously computed and the values of the variables in E have not changed
since the previous computation.
● Avoid re-computing an already computed value
● Common Subexpression can be local or global
cd_sk@vit.ac.in 07/07/2023 30
Common Subexpressions Elimination
● Eliminating Local Common Subexpression
t6 = 4*i
x = a[t6] t6 = 4*i
t7 = 4*i x = a[t6]
B5 t8 = 4*j B5 t8 = 4*j
t9 = a[t8] t9 = a[t8]
a[t7] = t9 a[t6] = t9
t10 = 4*j a[t8] = x
a[t10] = x goto B2
goto B 2
After
Before
cd_sk@vit.ac.in 07/07/2023 31
Common Subexpressions Elimination
● B5 still has common subexpression
● Both 4*i and 4*j are common subexpression
which are global (appears in previous
blocks)
● t8 = 4*j
t6 = 4*i ● t9 = a[t8] t6 = 4*i
x = a[t6] ● a[t8] = x x = a[t6]
t8 = 4*j B5 t9 = a[t4]
B5 t9 = a[t8] can be replaced by a[t6] = t9
a[t6] = t9 a[t4] = x
a[t8] = x ● t9 = a[t4] goto B2
goto B2 ● a[t4] = x
Before
As, t4=4*j computed After After
in block B3 cd_sk@vit.ac.in 07/07/2023
05/07/2023 32
Common Subexpressions Elimination
● B5 still has common subexpression
● Both 4*i and 4*j are common subexpression
which are global (appears in previous
blocks)
t6 = 4*i ● t9 = a[t4] t6 = 4*i
x = a[t6] ● a[t6] = t9 x = a[t6]
t9 = a[t4] B5 a[t6] = t5
B5 a[t6] = t9 can be replaced by a[t4] = x
a[t4] = x goto B2
goto B2 ● a[t6] =t5
As t5 = a[t4]
Before After
computed in block
B3 cd_sk@vit.ac.in 07/07/2023 33
Common Subexpressions Elimination
● B5 still has common subexpression
● Both 4*i and 4*j are common subexpression
which are global (appears in previous
blocks)
t6 = 4*i ● t6 = 4*i x = t3
x = a[t6] ● x = a[t6] a[t2] = t5
a[t6] = t5 B5 a[t4] = x
● a[t6] = t5
B5 a[t4] = x goto B2
goto B2 can be replaced by
Before ● x=t3 After
As t2 = 4*i and
t3=a[t2] computed in 34
cd_sk@vit.ac.in 07/07/2023
block B3
Common Subexpressions Elimination
Before cd_sk@vit.ac.in 07/07/2023 35
Copy Propagation
● Copy statements like u = v are introduced by eliminating common sub-expression
● In figure (a), to eliminate common subexpression from c = d+e, use a new variable
called t, as seen in figure (b)
● We cannot do c = a or c = b as control can go to c=d+e either from a = d+e or b =
d+e
t = d+e t = d+e
a = d+e b = d+e
a=t b=t
c = d+e c=t
Figure (a) Figure (b)
cd_sk@vit.ac.in 07/07/2023 36
Copy Propagation
● In copy-propagation transformation, use v for u, wherever possible after the
copy statement u = v
● B5 can be further optimized by eliminating x, using two new Transformations.
● In B5, x = t3 is a copy
x = t3 x = t3
B5 a[t2] = t5 a[t2] = t5
B5
a[t4] = x a[t4] = t3
goto B2 goto 2
Before
After
cd_sk@vit.ac.in 07/07/2023 37
Dead-Code Elimination
● A variable is live at a point in a program if its value can be used later in the
program, otherwise, it is dead at that point.
● Copy propagation often introduces dead code
z=x+y
z=x+y
p=x
w=x+y+z
w=x+y+z
Before After
● p=x is dead as p is never used,
so remove it cd_sk@vit.ac.in 07/07/2023 38
Dead-Code Elimination
● In B5, x=t3 is dead code as x is never used, so remove it
x = t3 a[t2] = t5
B5 a[t2] = t5 a[t4] = t3
B5
a[t4] = t3 goto 2
goto 2
Before After
cd_sk@vit.ac.in 07/07/2023 39
Constant Folding
● Recognizing and evaluating constant expressions at compile time rather than
computing them at runtime.
a=2 a=2
b=a+2 b=4
c=6-a+3 c=7
Before After
cd_sk@vit.ac.in 07/07/2023 40
