Common Subexpression Elimination (CSE) by GCC

Test Program

    main()

        {

             int i, j, k, r;

             scanf("%d%d", &i, &j);

             k = i + j + 10;

             r = i + j + 30;  

             printf("%d %d %d\n", k, r);

        }

Assemly Code

AT&T format of assembly code is used.

  

    main:

            pushl   %ebp

            movl    %esp, %ebp

            andl    $-16, %esp

            subl    $32, %esp

            leal    24(%esp), %eax

            movl    %eax, 8(%esp)

            leal    28(%esp), %eax

            movl    %eax, 4(%esp)

            movl    $.LC0, (%esp)

            call    scanf

            movl    28(%esp), %edx

            movl    24(%esp), %eax

                leal    (%edx,%eax), %eax
                addl    $10, %eax

                movl    %eax, 20(%esp)

            movl    28(%esp), %edx

            movl    24(%esp), %eax

                leal    (%edx,%eax), %eax

                addl    $30, %eax

                movl    %eax, 16(%esp)

            movl    16(%esp), %eax

            movl    %eax, 8(%esp)

            movl    20(%esp), %eax

            movl    %eax, 4(%esp)

            movl    $.LC1, (%esp)

            call    printf

            leave

            ret

The two blocks in bold represents the evaluation of 'k' and 'r' in the test program respectively.

The 'leal    (%edx,%eax), %eax' command adds the two values in the 'edx' and 'eax' and stores the result in 'eax'. The 'addl' command adds a constant to the value in the 'eax'.

Here, both 'leal' and 'addl' are called two times, for the evaluation of 'k' and 'r' respectively.

 After optimization as:

    gcc -S -O3 -fomit-frame-pointer opt2.c

    less opt2.s

    main:
            pushl   %ebp
            movl    %esp, %ebp
            andl    $-16, %esp
            subl    $32, %esp
            leal    24(%esp), %eax
            movl    %eax, 8(%esp)
            leal    28(%esp), %eax
            movl    %eax, 4(%esp)
            movl    $.LC0, (%esp)
            call    scanf
                movl    24(%esp), %eax
                addl    28(%esp), %eax
                movl    $.LC1, (%esp)
                leal    30(%eax), %edx
                addl    $10, %eax
            movl    %edx, 8(%esp)
            movl    %eax, 4(%esp)
            call    printf
            leave
            ret

Here, what is seen to be done is:
1) 

'i' in the test program stored in 'eax'

2) 'j' added to 'eax'

        Now 'eax' contains 'i' + 'j'.

3) 'r' is obtained as " 30 + the value in 'eax' "

4) 'k' is obtained by adding 10 to the value in 'eax'

Observation is:

        'i' + 'j' was evaluated only once !

Common Subexpression Evaluation (CSE)

As observed, CSE is an optimization technique employed by the compiler, when the same subexpression is present in more than one expressions.

It is as if the subexpression is evaluated first, and the result is stored in a temporary variable. For all further calculations where this subexpression was a part originally, the value of this newly created temporary variable will be used.
In the test program used above, the so evaluated subexpression is ' i + j '.

Also, CSE is performed only when, in that environment, the cost to use such a temporary variable is lesser than the cost to perform the operations in the subexpression itself. Here, the operation is '+'.