Question

Suppose we have the following,

(jf, A, LABEL1)
(add, t4, i, j)
(add, t5, t4, 3)
(assign, a, t5)
(LABEL1:)
(add, t6, i, j)
(add, t7, t6, 5)
(assign, b, t7)

Can Common Sub-expression Elimination be applied? If so, show the new code.

Answer 1

Yes. We can apply common sub-expression Elimination here. Sub expression elimination is used when we have identical computations or operations repeated that can be replaced with another variable so that we only need to compute that once. If the assignment and retrieval of this value is having less cost than performing the o[eration multiple times we can then use the sub-expression elimination.

In the given example we can see that adding I and j is repeated. so we can use the Sub expression elimination by introducing an extra variable to store the result of the addition of i and j so that we can use this variable whenever we need (i+j)

so we can add a variable temp and assign the value of i+j to it as shown

(add,temp,i,j)

now we can use it to eliminate line 2 and line 6. Because in these lines we just find i+j and assign it to t4 and t6 respectively. Now we have i+j in temp so we don't need to assign it to any other variable we can straight up use the variable temp instead of this. so the line 3 and 7 in question becomes :

line 3: (add,t5,temp,3)

line 7: (add,t7,temp,5)

The complete code after common sub-expression elimination is given below

(if,A,LABEL1)
(add,temp,i,j)
(add,t5,temp,3)
(assign,a,t5)
(LABEL1:)
(add,t7,temp,5)
(assign,b,t7)