6. Strength Reduction using Induction Variable

One type of code optimization is strength reduction in which a "costly" operation is replaced by a less expensive one. For example, the evaluation of x² is much more efficient if we multiply x by x rather than call the exponentiation routine. One place where this optimization can be applied is in loops. Many times in a loop, one variable changes in synchronization with the loop variable. Such a variable is called as induction variable. Induction variables give the compiler a chance to apply strength reduction, as can be seen from the following program.

 1 : /* test5.c */
 2 : /* demonstration of induction variable elimination */
 3 : int main()
 4 : {
 5 :     int i, j;
 6 :
 7 :     for(i = 0; i < 10; i++)
 8 :     {
 9 :         j = i * 7;
10 :         printf("i = %d, j = %d", i, j);
11 :     }
12 :     return 0;
13 : }
14 : /* end test5.c */
15 :
16 : /* --------------------------------------------------------------- */
17 : /* optimized assembly language code */
18 :     .file   "test5.c"
19 :     .version    "01.01"
20 : gcc2_compiled.:
21 : .section    .rodata
22 : .LC0:
23 :     .string "i = %d, j = %d"
24 : .text
25 :     .align 4
26 : .globl main
27 :     .type    main,@function
28 : main:
29 :     pushl %ebp                  /* save EBP on stack */
30 :     movl %esp,%ebp              /* ESP = EBP */
31 :
32 :     pushl %esi                  /* ESI will hold 'j' */
33 :     pushl %ebx                  /* EBX will hold 'i' */
34 :     xorl %ebx,%ebx              /* both are initialized to zero */
35 :     xorl %esi,%esi
36 :     .p2align 4,,7
37 : .L5:
38 :     /* printf("i = %d, j = %d", i, j); */
39 :     pushl %esi                  /* push value of j */
40 :     pushl %ebx                  /* push value of i */
41 :     pushl $.LC0                 /* push address of string */
42 :     call printf
43 :     addl $12,%esp               /* stack cleanup */
44 :
45 :     /* instead of saying j = i * 7, its efficient to say j = j + 7 */
46 :     addl $7,%esi
47 :     incl %ebx                   /* i++ */
48 :     cmpl $9,%ebx                /* is i <= 9, then repeat the loop */
49 :     jle .L5
50 :
51 :     /* return 0; */
52 :     xorl %eax,%eax
53 :     leal -8(%ebp),%esp
54 :     popl %ebx
55 :     popl %esi
56 :     leave
57 :     ret
58 : .Lfe1:
59 :     .size    main,.Lfe1-main
60 :     .ident  "GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"
61 :
62 : /* end optimized assembly code */
63 : /* ----------------------------------------------------------------- */

Here i is the loop variable whereas j is the induction variable as j always changes in lock step with i. In the generated assembly language code, the compiler has decided to use registers to store both i and j with i in EBX and j in ESI. Line 34 initializes EBX(=i) to zero, as is indicated in the initialization part of the for loop. The compiler sees that during the first pass, j will be assigned a value of 0, so it also initialized ESI to 0 in line 35. The loop starts at line 37 and continues till line 49. Since j already has its value assigned to it, the first thing the compiler does inside the loop is to call the printf() function. Here, the compiler has adjusted the order of the statements in the loop so as to enable it to use strength reduction. After analyzing the program, the compiler sees that inside the loop, the value of i is always going to increase by 1 and since j is an induction variable, its value is always going to increase by 7. Therefore, instead of multiplying i by 7 (which is costly), it adds 7 to the old value of j before going on to the next iteration. Thus a costly operation of multiplication has been replaced by addition which is cheaper (in terms of time).