Question

Consider the basic block B :
q = 3
r = 10
s = q +r
$t=2^{\ast }r+s$
t = q
u = q +r
w = 3 +x

Now consider the following basic block $B_2$.
q = 3
r = 10
s = q +r
$t_1=s$
$t=2^{\ast }r+s$
t = q
$u=t_1$
$w=3+x$

State which optimaization was performed on the basic block B to get $B_2$ :

• A. Common sub-expression elimination
• B. Constant propagation /folding
• C. Dead code elimination
• D. Copy propagation

Answer 1

The correct option is A Common sub-expression elimination

Option (c)

Common sub-expression elimination (CSE) is a compiler optimization that searches for instances of Identical expressions (I.e.; they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value. In basic block B, the common sub-expression q+ r at 6 is eliminated with a single variable $t_1$.