从一个无关的例子开始 #

HPC 课上提到，函数的副作用会阻碍编译优化。当时给了这样的一个例子：

void lower1(char* s) {
    size_t i;
    for (i = 0; i < my_strlen(s); i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            s[i] -= 'A' - 'a';
        }
    }
}

假定我们的 my_strlen 是自己造的轮子，大概长这样：

size_t my_strlen(const char* s) {
    size_t i = 0;
    while (s[i] != '0') {
        i++;
    }
    return i;
}

这个时候 lower1 的时间复杂度是 $O(n^2)$，因为每次循环条件判定的时候，都要调用 my_strlen。

看一下生成的汇编（编译选项 -Og），确实是这样的。my_strlen 内部生成了一个循环，lower1 再循环调用 my_strlen。

my_strlen(char const*):
        movl    $0, %eax
        jmp     .L2
.L3:
        addq    $1, %rax
.L2:
        cmpb    $48, (%rdi,%rax)
        jne     .L3
        ret
lower1(char*):
        pushq   %rbp
        pushq   %rbx
        movq    %rdi, %rbp
        movl    $0, %ebx
        jmp     .L5
.L6:
        addq    $1, %rbx
.L5:
        movq    %rbp, %rdi
        call    my_strlen(char const*)
        cmpq    %rax, %rbx
        jnb     .L9
        leaq    0(%rbp,%rbx), %rdx
        movzbl  (%rdx), %eax
        leal    -65(%rax), %ecx
        cmpb    $25, %cl
        ja      .L6
        addl    $32, %eax
        movb    %al, (%rdx)
        jmp     .L6
.L9:
        popq    %rbx
        popq    %rbp
        ret

假如编译器帮助我们把 my_strlen 的调用放到循环外面，用一个临时变量保存它的值，这样就能把时间复杂度优化到 $O(n)$。然而，即使是 -Ofast 优化，也仅仅是把我们的 my_strlen 内联到了 lower1 中。这是因为编译器无法确定 my_strlen 是否是有副作用的。假如我们自己造的 my_strlen 同时会修改一个全局变量，那么将其提到循环外面就会导致出错。

gcc 的内建函数 #

有了这样一个概念之后，很多人可能以为 gcc 对这样用户自己造轮子的场景就无事可做了。实际上，尽管 gcc 确实不会自作主张更改 lower1 的控制流，但在特定的情况下，它会对 my_strlen 做手脚。

改写 my_strlen 成下面这样（貌似会让 gcc 更好地理解它的语义，我也不知道为什么）：

size_t my_strlen(const char* s) {
    size_t i;
    for (i = 0; s[i]; i++);
    return i;
}

打开 -O2 进行编译，我们会得到这样的汇编：

my_strlen:
        cmpb    $0, (%rdi)
        je      .L3
        subq    $8, %rsp
        addq    $1, %rdi
        call    strlen
        addq    $8, %rsp
        addq    $1, %rax
        ret
.L3:
        xorl    %eax, %eax
        ret

这里直接 call 了 strlen。这就是 gcc 的内建函数优化。gcc 识别到你写的函数等价于 strlen，并且认为你写的肯定不如 glibc 里有的厉害，于是这里直接调用 glibc 的 strlen 去了。编译成可执行文件然后 objdump -d 可以得到更清楚的视角：

0000000000001160 <_Z9my_strlenPKc>:
    1160:       80 3f 00                cmpb   $0x0,(%rdi)
    1163:       74 1b                   je     1180 <_Z9my_strlenPKc+0x20> # 直接返回咯
    1165:       48 83 ec 08             sub    $0x8,%rsp
    1169:       48 83 c7 01             add    $0x1,%rdi
    116d:       e8 be fe ff ff          call   1030 <strlen@plt> # 去 plt 找 strlen
    1172:       48 83 c4 08             add    $0x8,%rsp
    1176:       48 83 c0 01             add    $0x1,%rax
    117a:       c3                      ret
    117b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
    1180:       31 c0                   xor    %eax,%eax
    1182:       c3                      ret
    1183:       66 66 2e 0f 1f 84 00    data16 cs nopw 0x0(%rax,%rax,1)
    118a:       00 00 00 00
    118e:       66 90                   xchg   %ax,%ax

plt 段如下：

Disassembly of section .plt:

0000000000001020 <strlen@plt-0x10>:
    1020:       ff 35 ca 2f 00 00       push   0x2fca(%rip)        # 3ff0 <_GLOBAL_OFFSET_TABLE_+0x8>
    1026:       ff 25 cc 2f 00 00       jmp    *0x2fcc(%rip)        # 3ff8 <_GLOBAL_OFFSET_TABLE_+0x10>
    102c:       0f 1f 40 00             nopl   0x0(%rax)

0000000000001030 <strlen@plt>:
    1030:       ff 25 ca 2f 00 00       jmp    *0x2fca(%rip)        # 4000 <strlen@GLIBC_2.2.5>
    1036:       68 00 00 00 00          push   $0x0
    103b:       e9 e0 ff ff ff          jmp    1020 <_init+0x20>

可以很清楚地看到，跑到 glibc 里头去了。

另外经测试发现，即使 my_strlen 有副作用，一样会在函数中调用 glibc。懒得贴代码了。

隐患 #

这种随便跳到共享库里的行为其实挺不好的。假如我们编译出来的东西要在单片机这种没有 glibc 的环境下执行，直接就会出现找不到符号的错误。

另外假如自己造轮子的时候，直接就把 my_strlen 就叫 strlen，然后就会得到这种汇编：

strlen:
        cmpb    $0, (%rdi)
        je      .L3
        subq    $8, %rsp
        addq    $1, %rdi
        call    strlen
        addq    $8, %rsp
        addq    $1, %rax
        ret
.L3:
        xorl    %eax, %eax
        ret

由于符号名字相同，这里反而不会进到 glibc 里了，而是变成了递归调用自己。注意由于这里先给 rdi +1 的操作，并不会造成无限递归，也就是说代码的功能起码是正确的。

但假如开启了 -Os，让 gcc 优化一下生成的代码的大小，就会变成这样：

strlen:
        jmp     strlen

注意这里还看不出来到底会跳到哪里去，正常情况下还是会跳转到 glibc。但如果你同时还开了 -nostdlib，编译出来就会是：

Disassembly of section .text:

0000000000001000 <strlen>:
    1000:       e9 fb ff ff ff          jmp    1000 <strlen>

直接完蛋。

一种解决方法是加上 -fno-builtin 编译选项。这会阻止所有的内建函数优化。