Common Subexpression Elimination
Common Subexpression Elimination is an optimization technique used by the gcc compiler. This searches for identical expressions, which calculates to same value, and replaces them with a variable to which the result after execution of the pattern is stored.
A simple example is:
a = i + j + k
b = i + j + l
In both the cases ‘i + j’ is common, therefore we can use a temp,
temp = i + j
a = temp + k
b = temp + l
The above is only a simple example. The situation can get complex. The i and j can become results of some functions. In those situations this optimization becomes handy.This optimization can be understood easily by looking into the assembly code before and after optimization.
We can look at the assembly of the following code segment.
This is a simple example similar to the above example.
Only a small section of the assembly code is shown here.
The steps after scanf is listed here. ‘leal (%edx, %eax), %eax’ adds the value in registers ‘edx’ and ‘eax’ and stores in ‘eax’. Then 10 is added to it and stored in a memory address. The similar step is done and 30 is added to the value. Thus the same step is done twice.
After the optimization
The part of the assembly is shown below.
The repeated pattern is calculated and stored in the register ‘eax’. This is the only time the pattern is evaluated. The value in register ‘eax’ is used to add with 30 and 10. The underlined two lines does the above described steps.