循环优化 -- 不变量外提

yunlong9981

strlen_chk.c计算sum1与sum2的目标相同，但是效率是不一样；参考汇编代码strlen_chk.s ，计算sum2时，strlen函数每次循环都被调用。
编译器对于循环优化--不变量外提； 一般的表达式都能够进行归纳优化， 但对函数一般无法进行优化；写程序时最好进行人工优化。

strlen_chk.c：

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. int main(int argc, char **argv)
   
6. {
   
7.     char    buf[1024];
   
8.     int    len = 0;
   
9.     int    sum1 = 0, sum2 = 0;
   
10.     int    i = 0;
    
11. 
    
12.     len = strlen( buf );
    
13.     for( i = 0; i < len; i++ )
    
14.         sum1 += i;
    
15. 
    
16.     for( i = 0; i < strlen(buf); i++ )
    
17.         sum2 += i;
    
18. 
    
19.     return sum1 + sum2;
    
20. }
    
21. 
    

复制代码

编译 cc -S -O3  strlen_chk.c
strlen_chk.s

1. 
   
2.     .file    "strlen_chk.c"
   
3.     .text
   
4.     .p2align 4,,15
   
5. .globl main
   
6.     .type    main, @function
   
7. main:
   
8. .LFB24:
   
9.     subq    $912, %rsp
   
10. .LCFI0:
    
11.     xorl    %r11d, %r11d
    
12.     xorl    %r10d, %r10d
    
13.     leaq    -120(%rsp), %r9
    
14.     movq    %r9, %rsi
    
15. 
    
16. ---------------------------------------
    
17. *** .L2  计算 len = strlen( buf ); store in eax;
    
18. *** .L25 .L23 计算    for( i = 0; i < len; i++ )  sum1 += i;
    
19. 
    
20. .L2:
    
21.     movl    (%rsi), %eax
    
22.     addq    $4, %rsi
    
23.     leal    -16843009(%rax), %edx
    
24.     notl    %eax
    
25.     andl    %eax, %edx
    
26.     movl    %edx, %ecx
    
27.     andl    $-2139062144, %ecx
    
28.     je    .L2
    
29.     movl    %ecx, %r8d
    
30.     leaq    2(%rsi), %rdi
    
31.     shrl    $16, %r8d
    
32.     andl    $32896, %edx
    
33.     cmove    %r8d, %ecx
    
34.     cmove    %rdi, %rsi
    
35.     movl    %ecx, %edx
    
36.     addb    %cl, %dl
    
37.     sbbq    $3, %rsi
    
38.     xorl    %edx, %edx
    
39.     movl    %esi, %eax
    
40.     subl    %r9d, %eax
    
41.     jmp    .L23
    
42. .L25:
    
43.     addl    %edx, %r11d
    
44.     incl    %edx
    
45. .L23:
    
46.     cmpl    %eax, %edx
    
47.     jl    .L25
    
48.     xorl    %edi, %edi
    
49.     .p2align 4,,7
    
50. -------------------------------------------
    
51. 
    
52. -------------------------------------------
    
53. *** .L8 .L11 计算    for( i = 0; i < strlen(buf); i++ )  sum2 += i;
    
54. *** 在.L11中，每次循环 strlen(buf)都被调用;
    
55. *** 对于循环优化--不变量外提，gcc -O3无法归纳strlen函数为不变量。
    
56. 
    
57. .L8:
    
58.     movslq    %edi,%r8
    
59.     movq    %r9, %rsi
    
60.     .p2align 4,,7
    
61. .L11:
    
62.     movl    (%rsi), %ecx
    
63.     addq    $4, %rsi
    
64.     leal    -16843009(%rcx), %edx
    
65.     notl    %ecx
    
66.     andl    %ecx, %edx
    
67.     movl    %edx, %ecx
    
68.     andl    $-2139062144, %ecx
    
69.     je    .L11
    
70.     movl    %ecx, %eax
    
71.     shrl    $16, %eax
    
72.     andl    $32896, %edx
    
73.     leaq    2(%rsi), %rdx
    
74.     cmove    %eax, %ecx
    
75.     movl    %ecx, %eax
    
76.     cmove    %rdx, %rsi
    
77.     addb    %cl, %al
    
78.     sbbq    $3, %rsi
    
79.     subq    %r9, %rsi
    
80.     cmpq    %rsi, %r8
    
81.     jae    .L26
    
82.     addl    %edi, %r10d
    
83.     incl    %edi
    
84.     jmp    .L8
    
85. ---------------------------------------
    
86. .L26:
    
87.     leal    (%r11,%r10), %eax
    
88.     addq    $912, %rsp
    
89.     ret
    
90. .LFE24:
    
91.     .size    main, .-main
    
92.     .section    .eh_frame,"a",@progbits
    
93. .Lframe1:
    
94.     .long    .LECIE1-.LSCIE1
    
95. .LSCIE1:
    
96.     .long    0x0
    
97.     .byte    0x1
    
98.     .string    ""
    
99.     .uleb128 0x1
    
100.     .sleb128 -8
     
101.     .byte    0x10
     
102.     .byte    0xc
     
103.     .uleb128 0x7
     
104.     .uleb128 0x8
     
105.     .byte    0x90
     
106.     .uleb128 0x1
     
107.     .align 8
     
108. .LECIE1:
     
109. .LSFDE1:
     
110.     .long    .LEFDE1-.LASFDE1
     
111. .LASFDE1:
     
112.     .long    .LASFDE1-.Lframe1
     
113.     .quad    .LFB24
     
114.     .quad    .LFE24-.LFB24
     
115.     .byte    0x4
     
116.     .long    .LCFI0-.LFB24
     
117.     .byte    0xe
     
118.     .uleb128 0x398
     
119.     .align 8
     
120. .LEFDE1:
     
121.     .section    .note.GNU-stack,"",@progbits
     
122.     .ident    "GCC: (GNU) 3.4.6 20060404 (Red Hat 3.4.6-3)"
     
123. 
     

复制代码

5毛党党员

这个标题很容易让人产生误解啊

converse

好的编译器会帮你做这个优化的.LZ试试用O2级别去编译程序再看看汇编码.

freearth

绝大多数编译器都不能做这个优化。
如果想要做这个不变量外提，必须让编译器判断出每次调用函数strlen(buf)都会返回相同的值。如果没有strlen函数的内部信息（一般情况下，系统只有strlen的二进制版本，没有源码），编译器不能判断。所以，为了正确性，绝对不能做这个优化。
即便有strlen的内部信息，也需要非常好的别名分析和过程间分析，保证两点：
1、对于strlen，参数不变，返回值不变；
2、sum2和buf没有关系；

在一般意义上，这两个问题都是不可判定的。

原帖由 converse 于 2008-8-15 11:37 发表
好的编译器会帮你做这个优化的.LZ试试用O2级别去编译程序再看看汇编码.

xi2008wang

空间换时间
使用len = strlen(buf);多用了一个变量

虑而后能得

编译器会自动进行这种优化的

qliu00

原帖由 freearth 于 2008-8-15 16:53 发表
绝大多数编译器都不能做这个优化。
如果想要做这个不变量外提，必须让编译器判断出每次调用函数strlen(buf)都会返回相同的值。如果没有strlen函数的内部信息（一般情况下，系统只有strlen的二进制版本，没有源 ...

绝大多数编译器都不能做这个优化,最好是自己优化

blizzard213

原帖由 yunlong9981 于 2008-8-15 10:30 发表
strlen_chk.c计算sum1与sum2的目标相同，但是效率是不一样；参考汇编代码strlen_chk.s ，计算sum2时，strlen函数每次循环都被调用。
编译器对于循环优化--不变量外提； 一般的表达式都能够进行归纳优化， 但对 ...

优化和编程风格有时候有些矛盾
需要取舍

周杰伦

就算是自己写的函数，有代码，也未必可以优化。有人把编译器想的太智能了。

5楼考虑一下临时变量。

blizzard213

原帖由 xi2008wang 于 2008-8-15 18:04 发表
空间换时间
使用len = strlen(buf);多用了一个变量

4个字节能对性能造成影响？
讨论至此已经没有任何意义