logo标签列表

为什么GCC为几乎相同的C代码生成如此不同的汇编代码？

cgccassemblyx86compiler-optimization
190

在编写优化的ftol函数时，我发现GCC 4.6.1存在一些非常奇怪的行为。首先让我展示一下代码（为了清晰起见，我标记了不同之处）：

fast_trunc_one, C:

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;                       /* diff */
    } else {
        r = mantissa >> exponent;                        /* diff */
    }

    return (r ^ -sign) + sign;                           /* diff */
}

fast_trunc_two，C：

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent) ^ -sign;             /* diff */
    } else {
        r = (mantissa >> exponent) ^ -sign;              /* diff */
    }

    return r + sign;                                     /* diff */
}

看起来一样？GCC不这么认为。使用gcc -O3 -S -Wall -o test.s test.c编译后，汇编输出如下：

fast_trunc_one，生成的：

_fast_trunc_one:
LFB0:
    .cfi_startproc
    movl    4(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %edx
    andl    $8388607, %edx
    sarl    $23, %eax
    orl $8388608, %edx
    andl    $255, %eax
    subl    %eax, %ecx
    movl    %edx, %eax
    sarl    %cl, %eax
    testl   %ecx, %ecx
    js  L5
    rep
    ret
    .p2align 4,,7
L5:
    negl    %ecx
    movl    %edx, %eax
    sall    %cl, %eax
    ret
    .cfi_endproc

fast_trunc_two，生成的：

_fast_trunc_two:
LFB1:
    .cfi_startproc
    pushl   %ebx
    .cfi_def_cfa_offset 8
    .cfi_offset 3, -8
    movl    8(%esp), %eax
    movl    $150, %ecx
    movl    %eax, %ebx
    movl    %eax, %edx
    sarl    $23, %ebx
    andl    $8388607, %edx
    andl    $255, %ebx
    orl $8388608, %edx
    andl    $-2147483648, %eax
    subl    %ebx, %ecx
    js  L9
    sarl    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_remember_state
    .cfi_def_cfa_offset 4
    .cfi_restore 3
    ret
    .p2align 4,,7
L9:
    .cfi_restore_state
    negl    %ecx
    sall    %cl, %edx
    movl    %eax, %ecx
    negl    %ecx
    xorl    %ecx, %edx
    addl    %edx, %eax
    popl    %ebx
    .cfi_restore 3
    .cfi_def_cfa_offset 4
    ret
    .cfi_endproc

这是一个极端的差异。这实际上也在个人资料中显示出来，fast_trunc_one比fast_trunc_two快约30%。现在我的问题是：是什么导致了这种情况？

2
为了测试目的，我创建了一个gist，您可以轻松地复制/粘贴源代码，并查看是否可以在其他系统/版本的GCC上重现错误。 - orlp
14
将测试用例放到一个独立的目录中。使用 -S -O3 -da -fdump-tree-all 进行编译。这将创建许多中间表示的快照。依次查看它们（它们是按编号排列的），你应该能够在第一个案例中找到缺失的优化。 - zwol
1
建议二：将所有的 int 改为 unsigned int，看看差异是否消失。 - zwol
5
这两个函数似乎在进行略微不同的数学计算。虽然结果可能相同，但表达式(r + shifted) ^ sign与r + (shifted ^ sign)并不相同。我猜这使得优化器感到困惑？值得一提的是，MSVC 2010（16.00.40219.01）生成的清单几乎完全相同：https://gist.github.com/2430454 - DCoder
1
@DCoder：天啊！我没注意到。但这并不是差异的解释。让我更新问题，排除这个因素。 - orlp
显示剩余11条评论
3个回答
263

更新以与提问者的编辑同步

通过调整代码，我成功地看到了GCC如何优化第一个案例。

在我们能够理解它们为什么如此不同之前，首先我们必须理解GCC如何优化fast_trunc_one()。

信不信由你，fast_trunc_one() 被优化为这样：

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

这会产生与原始的 fast_trunc_one() 完全相同的汇编代码，包括寄存器名称等。

请注意，在fast_trunc_one() 的汇编代码中没有出现 xor 指令。这是让我知道这一点的原因。

为什么呢？

步骤 1： sign = -sign

首先，让我们来看看变量 sign。既然 sign = i & 0x80000000;，那么 sign 只有两种可能的取值：

  • sign = 0
  • sign = 0x80000000

现在认识到在这两种情况下，sign == -sign。因此，当我将原始代码更改为以下代码时：

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = mantissa << -exponent;
    } else {
        r = mantissa >> exponent;
    }

    return (r ^ sign) + sign;
}

它生成与原始的fast_trunc_one()完全相同的汇编代码。我就不给你看汇编代码了，但它是完全一样的 - 包括寄存器名称。

步骤2：数学简化：x + (y ^ x) = y

sign只能取两个值，0或0x80000000。

  • 当x = 0时，x + (y ^ x) = y trivial（无需证明）成立。
  • 加上0x80000000并通过异或运算，效果相同。它会翻转符号位。因此，当x = 0x80000000时，x + (y ^ x) = y也成立。

因此，x + (y ^ x)简化为y。代码简化为：

int fast_trunc_one(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = (mantissa << -exponent);
    } else {
        r = (mantissa >> exponent);
    }

    return r;
}

同样，这个编译成的汇编代码完全相同-包括寄存器名字。

上述版本最终简化为：

int fast_trunc_one(int i) {
    int mantissa, exponent;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);

    if (exponent < 0) {
        return (mantissa << -exponent);             /* diff */
    } else {
        return (mantissa >> exponent);              /* diff */
    }
}

这几乎与GCC在汇编中生成的内容完全相同。

那么为什么编译器不会将fast_trunc_two()优化成相同的结果呢？

fast_trunc_one()的关键部分是x + (y ^ x) = y的优化。而在fast_trunc_two()中，x + (y ^ x)表达式分布在分支语句之间。

我认为这可能足以使GCC无法进行此优化。（它需要将^ -sign提升出分支，并将其合并到最后的r + sign中。）

例如，这将产生与fast_trunc_one()相同的汇编代码：

int fast_trunc_two(int i) {
    int mantissa, exponent, sign, r;

    mantissa = (i & 0x07fffff) | 0x800000;
    exponent = 150 - ((i >> 23) & 0xff);
    sign = i & 0x80000000;

    if (exponent < 0) {
        r = ((mantissa << -exponent) ^ -sign) + sign;             /* diff */
    } else {
        r = ((mantissa >> exponent) ^ -sign) + sign;              /* diff */
    }

    return r;                                     /* diff */
}
4
看起来我回答了第二版修订。当前修订翻转了两个示例并稍微更改了代码……这很令人困惑。 - Mysticial
2
@nightcracker 不用担心，我已经更新了我的答案以与当前版本同步。 - Mysticial
1
@Mysticial：随着新版本的推出，你的最终陈述不再正确，使得你的答案无效（它没有回答最重要的问题：“为什么GCC会生成如此不同的汇编代码”）。 - orlp
11
更新回答了。我不确定是否足够满意。但我认为如果不确切了解相关的GCC优化传递如何工作，我无法做出更好的改进。 - Mysticial
4
严格来说，只要在这段代码中错误地使用了有符号类型，编译器所做的几乎所有转换都是在行为未定义的情况下进行的... - R.. GitHub STOP HELPING ICE
显示剩余4条评论
64
这就是编译器的本质。假设它们会采取最快或最佳路径，是完全错误的。任何建议你不需要对代码进行优化就可以使用“现代编译器”自动填充空白、执行最佳作业、生成最快代码等的人都是错误的。实际上，至少在ARM上我看到 GCC 从 3.x 到 4.x 变得更糟了。4.x 可能在这一点上已经赶上了 3.x，但是早期它生成的代码更慢。通过练习，你可以学习如何编写代码，使编译器不必工作得那么努力，并因此产生更一致和符合预期的结果。
这里的 bug 是你对将要生成的内容的期望，而不是实际生成的内容。如果你希望编译器生成相同的输出，请提供相同的输入。不是数学意义上的相同，不是有点相同，而是确切地相同，没有不同的路径，没有从一个版本共享或分布操作到另一个版本。这是一个很好的练习，可以理解如何编写你的代码并查看编译器如何处理它。不要犯这样的错误，认为因为某个处理器目标的 GCC 的一个版本在某一天生成了某个结果，那就是所有编译器和所有代码的规则。你必须使用许多编译器和许多目标才能了解发生了什么。
GCC 相当差劲，我邀请你看看幕后，看看 GCC 的内在机制，尝试添加一个目标或自己修改一些东西。它几乎是由胶带和铁丝固定在一起的。在关键位置添加或删除一行代码，它就会崩溃。它已经生成可用的代码是值得高兴的事情，而不是担心为什么它没有达到其他期望。
你看过不同版本的 GCC 生成了什么吗？特别是 3.x 和 4.x，例如 4.5 vs. 4.6 vs. 4.7 等等？以及不同的目标处理器，x86、ARM、MIPS 等，或者如果这是您使用的本地编译器，则是不同的 x86 版本，32 位 vs. 64 位等等？然后 LLVM（Clang）针对不同的目标呢？
Mystical 在分析/优化代码所需的思维过程中做得非常好，期望编译器产生任何这样的结果是不合理的“现代编译器”的任何预期。除了数学属性外，此形式的代码。
if (exponent < 0) {
  r = mantissa << -exponent;                       /* diff */
} else {
  r = mantissa >> exponent;                        /* diff */
}
return (r ^ -sign) + sign;                           /* diff */

这将引导编译器进行 A 方式的实现，执行 if-then-else 语句，然后收敛于公共代码并完成返回；或者 B 方式，由于这是函数的尾部，因此不需要保存一个分支。同时也不需要使用或保存 r。

if (exponent < 0) {
  return((mantissa << -exponent)^-sign)+sign;
} else {
  return((mantissa << -exponent)^-sign)+sign;
}

就像Mystical指出的那样，对于代码中写的内容，sign变量完全消失了。我不会期望编译器能够看到sign变量消失，所以你应该自己做这个，而不是强迫编译器去尝试解决。

这是一个很好的机会去深入研究gcc源码。看起来，你已经发现了一种情况，在一种情况下优化器会看到一件事情，然后在另一种情况下会看到另一件事情。接下来，可以尝试让gcc看到这种情况。每个优化都存在，因为某些人或组织意识到这种优化，并有意地将其放在那里。为了使这种优化存在并且每次都有效，必须有人将其放在那里（然后测试它，然后将其保持到未来）。

绝对不要认为代码越少越快，代码越多越慢，很容易创建和找到反例。虽然通常可能是代码越少越快的情况，但正如我从一开始就演示的那样，你可以创建更多的代码来保存分支或循环等，最终结果也是更快的代码。

最重要的是，你给编译器提供了不同的源代码，并期望得到相同的结果。问题不是编译器输出，而是用户的期望。可以很容易地证明，对于特定的编译器和处理器，添加一行代码可能会使整个函数的速度显着变慢。例如，为什么将a=b+2;更改为a=b+c+2;会导致_fill_in_the_blank_compiler_name_生成完全不同且速度更慢的代码？当然，答案是编译器在输入时得到了不同的代码，因此编译器生成不同的输出是完全有效的。（甚至更好的是，当你交换两行不相关的代码并导致输出发生巨大变化时）输入复杂度和大小与输出复杂度和大小之间没有任何预期的关系。将这样的内容输入到clang中：

for(ra=0;ra<20;ra++) dummy(ra);

它生成了大约60至100行的汇编代码。它展开了循环。我没有数过行数，但如果你仔细想一下，它必须进行添加、将结果复制到函数调用的输入中、进行函数调用等至少三个操作。因此，取决于目标平台，可能至少需要60条指令，如果每个循环4个，则需要80条，如果每个循环5个，则需要100条等。

你为什么要破坏你的回答？Oded 似乎也不同意这个编辑 ;-). - Peter - Reinstate Monica
@PeterA.Schneider所有的回答似乎在同一天被破坏了。我认为有人使用他（被盗？）的帐户数据做了这件事。 - trinity420
23
Mysticial已经给出了很好的解释，但我想补充一下，毫无疑问，编译器优化一个而不优化另一个并没有什么固有的原因。例如，LLVM的clang编译器为这两个函数提供相同的代码（除了函数名称），结果如下：
_fast_trunc_two:                        ## @fast_trunc_one
        movl    %edi, %edx
        andl    $-2147483648, %edx      ## imm = 0xFFFFFFFF80000000
        movl    %edi, %esi
        andl    $8388607, %esi          ## imm = 0x7FFFFF
        orl     $8388608, %esi          ## imm = 0x800000
        shrl    $23, %edi
        movzbl  %dil, %eax
        movl    $150, %ecx
        subl    %eax, %ecx
        js      LBB0_1
        shrl    %cl, %esi
        jmp     LBB0_3
LBB0_1:                                 ## %if.then
        negl    %ecx
        shll    %cl, %esi
LBB0_3:                                 ## %if.end
        movl    %edx, %eax
        negl    %eax
        xorl    %esi, %eax
        addl    %edx, %eax
        ret

这段代码不像OP提供的第一个gcc版本那么短，但也不像第二个那么长。

来自另一个编译器（我不会透露名字），编译x86_64时，对两个函数都产生了如下代码：

fast_trunc_one:
        movl      %edi, %ecx        
        shrl      $23, %ecx         
        movl      %edi, %eax        
        movzbl    %cl, %edx         
        andl      $8388607, %eax    
        negl      %edx              
        orl       $8388608, %eax    
        addl      $150, %edx        
        movl      %eax, %esi        
        movl      %edx, %ecx        
        andl      $-2147483648, %edi
        negl      %ecx              
        movl      %edi, %r8d        
        shll      %cl, %esi         
        negl      %r8d              
        movl      %edx, %ecx        
        shrl      %cl, %eax         
        testl     %edx, %edx        
        cmovl     %esi, %eax        
        xorl      %r8d, %eax        
        addl      %edi, %eax        
        ret

在这个例子中，计算机会同时计算if语句的两个条件分支，然后使用条件移动在结尾处选择正确的分支。

Open64编译器生成以下代码：

fast_trunc_one: 
    movl %edi,%r9d                  
    sarl $23,%r9d                   
    movzbl %r9b,%r9d                
    addl $-150,%r9d                 
    movl %edi,%eax                  
    movl %r9d,%r8d                  
    andl $8388607,%eax              
    negl %r8d                       
    orl $8388608,%eax               
    testl %r8d,%r8d                 
    jl .LBB2_fast_trunc_one         
    movl %r8d,%ecx                  
    movl %eax,%edx                  
    sarl %cl,%edx                   
.Lt_0_1538:
    andl $-2147483648,%edi          
    movl %edi,%eax                  
    negl %eax                       
    xorl %edx,%eax                  
    addl %edi,%eax                  
    ret                             
    .p2align 5,,31
.LBB2_fast_trunc_one:
    movl %r9d,%ecx                  
    movl %eax,%edx                  
    shll %cl,%edx                   
    jmp .Lt_0_1538

还有类似但不完全相同的代码，用于fast_trunc_two。

无论如何，在优化方面，这是一个彩票 - 就是它了...并不总是容易知道为什么你的代码会以特定的方式被编译。

12
你不愿透露名称的编译器是否是某个高度机密的超级编译器？ - orlp
5
最高机密编译器可能是英特尔的“icc”。我只有32位的版本，但它生成的代码非常类似于这个。 - Janus Troelsen
5
我也相信这是ICC。编译器知道处理器可以进行指令级并行计算，因此两个分支可以同时计算。条件移动的开销要比错误的分支预测的开销低得多。 - Filip Navara
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接