编译器谓词优化

Question

考虑以下示例 conditions/predicates：

x > 10 and x > 20
(x > 10 or x == 10) and (x < 10 or x == 10) 又名 x >= 10 and x <= 10

谓词1.可以简化为x > 20，谓词2.可以简化为x == 10。编译器会优化这种（或更复杂的）谓词吗？如果是，使用什么算法来优化？

谓词有哪些常见的优化技术？

Answer 1

看看C#编译器为以下方法吐出的IL代码，至少在这种情况下编译器似乎不够聪明。但是，不确定当 IL 代码被翻译成本机代码或什至稍后在处理器管道中会发生什么 - 将会有进一步的优化：

private static bool Compare(int x)
{
   return (x > 10 || x == 10) && (x < 10 || x == 10);
}

对应的IL：

IL_0000: ldarg.0      // x
IL_0001: ldc.i4.s     10 // 0x0a
IL_0003: bgt.s        IL_000a
IL_0005: ldarg.0      // x
IL_0006: ldc.i4.s     10 // 0x0a
IL_0008: bne.un.s     IL_0017
IL_000a: ldarg.0      // x
IL_000b: ldc.i4.s     10 // 0x0a
IL_000d: blt.s        IL_0015
IL_000f: ldarg.0      // x
IL_0010: ldc.i4.s     10 // 0x0a
IL_0012: ceq          
IL_0014: ret          
IL_0015: ldc.i4.1     
IL_0016: ret          
IL_0017: ldc.i4.0     
IL_0018: ret

这是第二个（优化的）版本：

private static bool Compare(int x)
{
   return x >= 10 && x <= 10;
}

并且，相应的 IL 代码：

IL_0000: ldarg.0      // x
IL_0001: ldc.i4.s     10 // 0x0a
IL_0003: blt.s        IL_000e
IL_0005: ldarg.0      // x
IL_0006: ldc.i4.s     10 // 0x0a
IL_0008: cgt          
IL_000a: ldc.i4.0     
IL_000b: ceq          
IL_000d: ret          
IL_000e: ldc.i4.0     
IL_000f: ret

由于第二个版本明显更短，它在运行时内联的可能性更大，因此我们应该期望它运行快一点。

最后，第三个，姑且称之为"the best"(x == 10):

private static bool Compare(int x)
{
    return x == 10;
}

及其IL：

IL_0000: ldarg.0      // x
IL_0001: ldc.i4.s     10 // 0x0a
IL_0003: ceq          
IL_0005: ret

简洁明了。

运行使用 Benchmark.NET 和 [MethodImpl(MethodImplOptions.NoInlining)] 的基准测试揭示了运行time 行为，这两个实现似乎仍然有很大不同：

案例 1：非 10 的测试候选人（负案例）。

     Method |       Jit | Platform |     Mean 
----------- |---------- |--------- |----------
   TestBest | LegacyJit |      X64 | 2.329 ms
    TestOpt | LegacyJit |      X64 | 2.704 ms
 TestNonOpt | LegacyJit |      X64 | 3.324 ms
   TestBest | LegacyJit |      X86 | 1.956 ms
    TestOpt | LegacyJit |      X86 | 2.178 ms
 TestNonOpt | LegacyJit |      X86 | 2.796 ms
   TestBest |    RyuJit |      X64 | 2.480 ms
    TestOpt |    RyuJit |      X64 | 2.489 ms
 TestNonOpt |    RyuJit |      X64 | 3.101 ms
   TestBest |    RyuJit |      X86 | 1.865 ms
    TestOpt |    RyuJit |      X86 | 2.170 ms
 TestNonOpt |    RyuJit |      X86 | 2.853 ms

案例 2：使用 10（阳性案例）进行测试。

     Method |       Jit | Platform |     Mean
----------- |---------- |--------- |---------
   TestBest | LegacyJit |      X64 | 2.396 ms
    TestOpt | LegacyJit |      X64 | 2.780 ms
 TestNonOpt | LegacyJit |      X64 | 3.370 ms
   TestBest | LegacyJit |      X86 | 2.044 ms
    TestOpt | LegacyJit |      X86 | 2.199 ms
 TestNonOpt | LegacyJit |      X86 | 2.533 ms
   TestBest |    RyuJit |      X64 | 2.470 ms
    TestOpt |    RyuJit |      X64 | 2.532 ms
 TestNonOpt |    RyuJit |      X64 | 2.552 ms
   TestBest |    RyuJit |      X86 | 1.911 ms
    TestOpt |    RyuJit |      X86 | 2.210 ms
 TestNonOpt |    RyuJit |      X86 | 2.753 ms

有趣的是，在这两种情况下，选择和非选择 X64 版本的新 JIT 运行几乎同时出现。

问题仍然是：为什么编译器不优化这些类型的模式？我的猜测是，这是因为诸如运算符重载之类的东西使得编译器无法推断出一些正确的逻辑结论，但 II 可能非常不正确......此外，对于内置值类型，它应该是可能的。哦好吧...

最后，这里有一篇关于布尔表达式优化的好文章： https://hbfs.wordpress.com/2008/08/26/optimizing-boolean-expressions-for-speed/

Answer 2

这取决于编译器，但 clang 和 gcc 会执行此优化：

#include <stdio.h>

void foo(int x) {
  if (x > 10 && x > 20)
    puts("foo");
}

void foo2(int x) {
  if ((x > 10 || x == 10) && (x < 10 || x == 10))
    puts("foo2");
}

您可以 see the assembly here -- 两个函数都包含一个比较。

对于 clang（使用 LLVM），它使用 instruction combine pass ('instcombine'). You can see of the transformations in the InstructionSimplify.cpp 源代码。

编译器谓词优化

Compiler predicate optimizations

performance

predicate

compiler-optimization