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
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)
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 !
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 ‘+’.