Question

The following is the original code,

(add, t1, 3, 5)

(assign, a, t1)

(add, t2, 3, 5)

(sub, t3, t2, z)

(assign, b, t3)

Constant folding is applied to give the following,

(assign, t1, 8)

(assign, a, t1)

(assign, t2, 8)

(sub, t3, t2, z)

(assign, b, t3)

After the constant folding is applied, the (assign, t2, 8) becomes redundant. What optimizations should take place in order to remove this redundancy in the constant folded code? Also show the optimized code.

Answer 1

Constant folding is an optimization method used in compiler design.

In this problem, we have already applied it. But (assign,t2,8) is redundant.

we can solve it by using common sub-expression elimination followed by constant propagation.

In common sub-expression elimination, we can replace a repeated expression with one expression or variable.

In this code, the assign operation is repeated as (assign,t1,8) and (assign,t2,8)

so we can replace it by (assign, temp,8) and we can use this variable temp whenever we see t1 or t2.

so we get the new code as

(assign, temp, 8)

(assign, a, temp)

(sub, t3, temp, z)

(assign, b, t3)

Now the problem of redundancy of (assign t2,8) is resolved.

But we can further optimize this using Constant propagation.

Constant propagation is the process of substituting known values in the expression. T

In this code in line (assign, temp,8) we can see that we are assigning the value 8. so now the compiler knows that temp is 8 it can simply replace temp with 8 anywhere we see temp.

so we get

(assign, temp, 8)

(assign, a, 8)

(sub, t3, 8, z)

(assign, b, t3)

The second step is not actually needed to eliminate the redundancy of assign operation. Only the sub-expression elimination is needed. But I provided extra knowledge so that you can understand what happens next.