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.


About Odol Shinu

I've completed my B Tech in Information Technology in 2010 from Government Engineering College Sreekrishnapuram Palakkad under Calicut University.

Posted on October 19, 2010, in C Language. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: