编译器是否能够避免分支指令？

Question

我一直在阅读有关 bit twiddling hacks 的文章，我想，编译器是否能够避免以下代码中的分支：

constexpr int min(const int lhs, const int rhs) noexcept {
    if (lhs < rhs) {
        return lhs;
    }
    return rhs
}

将其替换为 (explanation):

constexpr int min(const int lhs, const int rhs) noexcept {
    return rhs ^ ((lhs ^ rhs) & -(lhs < rhs));
}

Answer 1

clang++ (3.5.2-1) 似乎足够聪明 -O3 （我没有使用 c++11 或 c++14，constexpr 和 noexcept 从源代码中删除):

08048760 <_Z3minii>:
 8048760:   8b 44 24 08             mov    0x8(%esp),%eax
 8048764:   8b 4c 24 04             mov    0x4(%esp),%ecx
 8048768:   39 c1                   cmp    %eax,%ecx
 804876a:   0f 4e c1                cmovle %ecx,%eax
 804876d:   c3                      ret

gcc (4.9.3) (-O3) 而不是用 jle:

做分支

08048740 <_Z3minii>:
 8048740:       8b 54 24 08             mov    0x8(%esp),%edx
 8048744:       8b 44 24 04             mov    0x4(%esp),%eax
 8048748:       39 d0                   cmp    %edx,%eax
 804874a:       7e 02                   jle    804874e <_Z3minii+0xe>
 804874c:       89 d0                   mov    %edx,%eax
 804874e:       f3 c3                   repz ret

(x86 32 位)

这个min2（损坏）是位替代（来自gcc）：

08048750 <_Z4min2ii>:
 8048750:       8b 44 24 08             mov    0x8(%esp),%eax
 8048754:       8b 54 24 04             mov    0x4(%esp),%edx
 8048758:       31 c9                   xor    %ecx,%ecx
 804875a:       39 c2                   cmp    %eax,%edx
 804875c:       0f 9c c1                setl   %cl
 804875f:       31 c2                   xor    %eax,%edx
 8048761:       f7 d9                   neg    %ecx
 8048763:       21 ca                   and    %ecx,%edx
 8048765:       31 d0                   xor    %edx,%eax
 8048767:       c3                      ret

Answer 2

编译器有可能检测到此模式并用您的建议替换它。

但是，clang++ 和 g++ 都没有进行此优化，例如参见 [=10=]。

Answer 3

编译器是否能够...：肯定是！
我可以依赖那些优化吗？：不，你不能依赖任何优化。可能总会有一些奇怪的情况，在这种情况下，编译器会出于某些不明显的原因选择不实施某种优化，或者只是看不到这种可能性。同样总的来说，我观察到编译器有时比人们想象的要笨得多（或者人们（包括我）比他们想象的要笨）。(1)
没有问，但是一个非常重要的方面：我可以相信这实际上是一个优化吗？ 不！一方面，（尤其是在 x86 上）性能总是取决于周围的代码，并且有很多不同的优化相互作用。此外，一些架构甚至可能提供更高效地执行操作的命令。
我应该使用位旋转优化吗？：一般来说：不 - 尤其是在没有验证它们确实给你带来任何好处的情况下！即使它们确实提高了性能，它也会使您的代码更难阅读和审查，并且它会做出一些特定于体系结构和编译器的假设（整数的表示、指令的执行时间、分支预测错误的惩罚……），这可能会导致当您将代码移植到另一个体系结构时性能会更差，或者在最坏的情况下甚至会导致错误的结果。

我的建议：
如果您需要获得 特定系统 的最后一点性能，那么只需尝试两种变体并进行测量（并每次验证结果，更新您的 CPU and/or编译器）。对于任何其他情况，假设编译器至少在进行低级优化方面与您一样好。我还建议您首先了解所有与优化相关的编译器标志，并在任何情况下开始使用低级优化之前设置适当的基准。

我认为手动优化有时仍然有益的唯一领域是如果您想最佳地使用矢量单元。现代编译器可以自动矢量化很多东西，但这仍然是一个相对较新的领域，并且编译器不允许做某些事情，因为它违反了标准的某些保证（尤其是在涉及浮点运算的情况下）。

(1) 有些人似乎认为，不管他们的代码是什么样子，编译器总是会产生提供相同语义的最佳代码。首先，编译器在有限的时间内可以做什么是有限制的（有很多启发式方法在大多数情况下都有效，但并非总是如此）。其次，在很多情况下，c++标准要求编译器给出一定的保证，你目前实际上并不感兴趣，但仍然会阻止优化。

编译器是否能够避免分支指令？

Are compilers able to avoid branching instructions?

c++

c++11

bit-manipulation

c++14

micro-optimization