3. Constant Folding

Constant folding is the simplest code optimization to understand. Let us suppose that you write the statement x = 45 * 88; in your C program. A non-optimizing compiler will generate code to multiply 45 by 88 and store the value in x. An optimizing compiler will detect that both 45 and 88 are constants, so their product will also be a constant. Hence it will find 45 * 88 = 3960 and generate code that simply copies 3960 into x. This is constant folding, and means the calculation is done just once, at compile time, rather than every time the program is run. To illustrate this, create the file test2.c as shown below. Generate the assembly code for this program as was shown earlier. Since by default, GCC does not optimize the program, you will see that the assembly code is a straightforward translation of the C program (Lines 18 to 62).

 1 : /* test2.c */
 2 : /* Demonstration of constant propagation */
 3 : #include <stdio.h>
 4 : 
 5 : int main()
 6 : {
 7 :     int x, y, z;
 8 :     x = 10;
 9 :     y = x + 45;
10 :     z = y + 4;
11 :     printf("The value of z = %d", z);
12 :     return 0;
13 : }
14 : /* end of test2.c */
15 : 
16 : /* ---------------------------------------------------------------- */
17 : /* assembly language file without any optimizations */
18 :     .file   "test2.c"
19 :     .version    "01.01"
20 : gcc2_compiled.:
21 : .section    .rodata
22 : .LC0:
23 :     .string "The value of z = %d"
24 : .text
25 :     .align 4
26 : .globl main
27 :     .type    main,@function
28 : main:
29 :     pushl %ebp             /* save EBP register on stack */
30 :     movl %esp,%ebp         /* EBP = ESP */
31 :     subl $12,%esp          /* Create stack frame. 3 variables x 4 bytes */
32 : 
33 :     /* x = 10; */
34 :     movl $10,-4(%ebp)      /* x = 10. x is topmost on the stack */
35 : 
36 :     /* y = x + 45; */
37 :     movl -4(%ebp),%edx     /* EDX = x */
38 :     addl $45,%edx          /* EDX = EDX + 45 */
39 :     movl %edx,-8(%ebp)     /* y = EDX. y is second from top of stack */
40 : 
41 :     /* z = y + 4 */
42 :     movl -8(%ebp),%edx     /* EDX = y */
43 :     addl $4,%edx           /* EDX = EDX + 4 */
44 :     movl %edx,-12(%ebp)    /* z = EDX. z is third from top of stack */
45 : 
46 :     /* printf("The value of z = ", z); */
47 :     movl -12(%ebp),%eax    /* EAX = z */
48 :     pushl %eax             /* push EAX(=z) as first parameter of printf */
49 :     pushl $.LC0            /* second parameter for printf */
50 :     call printf                 
51 :     addl $8,%esp           /* clear stack */
52 : 
53 :     /* return 0; */
54 :     xorl %eax,%eax         /* for return 0 */
55 :     jmp .L1
56 :     .p2align 4,,7
57 : .L1:
58 :     leave
59 :     ret
60 : .Lfe1:
61 :     .size    main,.Lfe1-main
62 :     .ident  "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
63 : /* end of assembly language code */
64 : /* ---------------------------------------------------------------- */
65 : 
66 : /* ---------------------------------------------------------------- */
67 : /* generated assembly language code after optimization */
68 : 
69 :     .file   "test2.c"
70 :     .version    "01.01"
71 : gcc2_compiled.:
72 : .section    .rodata
73 : .LC0:
74 :     .string "The value of z = %d"
75 : .text
76 :     .align 4
77 : .globl main
78 :     .type    main,@function
79 : main:
80 :     pushl %ebp             /* Save EBP register on stack */
81 :     movl %esp,%ebp         /* EBP = ESP */
82 : 
83 :     /* by constant propagation, z will always be 59 */
84 :     /* printf("The value of z = %d", z); */
85 :     pushl $59              /* first printf parameter */
86 :     pushl $.LC0            /* second printf parameter */
87 :     call printf
88 :                            /* no need of cleanup, we are exiting anyway */
89 :     /* return 0; */
90 :     xorl %eax,%eax              
91 :     leave
92 :     ret
93 : .Lfe1:
94 :     .size    main,.Lfe1-main
95 :     .ident  "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
96 : /* end of assembly language code */
97 : /* ----------------------------------------------------------------- */

There are some new things in the assembly code that we need to understand. First of all, the main() function defines 3 local variables for whom space will be allocated on the stack. Also, to access these variables, we will be using the indexed addressing mode and we will be using EBP for that. So the first statement saves the current value of EBP onto the stack. Then the stack pointer ESP is copied into EBP (note that the source ESP is first) so that EBP can be used for accessing the local variables. Finally, we need to create space for three 4-byte variables on the stack, so we subtract 12 from ESP; i.e., we grow the stack by 12 bytes. x will be the bottom-most stack element and at an offset of -4 from EBP. See the diagram below.

             EBP-----> ---------------
                       |      x      |       4 Bytes
                       ---------------
                       |      y      |       4 Bytes
                       ---------------
                       |      z      |       4 Bytes
             ESP-----> ---------------
                       |             |
                       |             |
                   ^   |             |
                   |         ...
Address increases  |   |             |
as we go up        | 0 ---------------  

Similarly, the offset of y from EBP is -8 and that of z is -12. Now consider the assignment x = 10;. The statement to implement it on line 34 is movl $10, -4(%ebp). The indexed addressing mode is written as <offset>(<base register>). Thus the above statement will copy the constant 10 to the address (EBP - 4) i.e. the address of x on the stack. In a similar manner, -8(%ebp) is used to access y and -12(%ebp) is used to access z. Lines 37, 38 and 39 evaluate x + 45 and assign the result to y. To do so, the value of x is first copied into the EDX register, 45 is added to it and the result which is in EDX is copied to y. The code for z = y + 4 is similar. In line 47 the parameters for printf() are pushed on the stack. The last parameter (z) is pushed first and then the address of the string is pushed. In line 51, we cleanup the stack by adding 8 to ESP. I guess that since we pushed two 4-byte parameters, we had to add 8 to ESP. In the first example, we pushed only one parameter and hence we had to add just 4 to ESP. The rest of the code is easy to understand.

Now if we look at the above program, when we evaluate x + 45, the value of x is always going to be 10 because of the assignment x = 10. Therefore x + 45 will always evaluate to 55. So the statement always assigns 55 to y. Similarly, when evaluating y + 4, the result will always be 59. If the optimization is enabled, the compiler will be in a position to detect this. To enable optimization, use the -O2 option. Enter the following command:

gcc -c -S -O2 test2.c

The assembly code generated with optimization enabled is shown in lines 69 to 95. Notice that on line 85, the compiler directly pushes the constant 59 on the stack followed by the address of the string and calls printf(). Thus, by constant folding, the compiler evaluates the various expressions in the program only once and plugs the final value into the generated code. One more interesting thing to observe is that after constant folding, there is no need of the variables x, y and z. Therefore no space for them is allocated on the stack, thus reducing the memory requirement of the program. This brings out the fact that one optimization may lead to another one. In the above case constant folding lead to a decrease in run time (since all the computations are done at compile time) and also to a decrease in the space requirements.