編譯器謂語優化

Question

考慮下面的例子條件/謂詞：

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

謂詞1可以簡化爲x > 20和2可以被簡化爲x == 10。編譯器是否會優化這種（或更復雜的）謂詞，如果是的話，那麼用什麼算法來實現呢？

什麼是一些常見的謂詞優化技術？

Answer 1

這取決於編譯器，但鐺和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'）。您可以看到InstructionSimplify.cpp源代碼中的轉換。

Answer 2

查看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   

由於第二個版本顯然更短，它在運行時獲得內聯的機會更大，因此我們應該期望它運行得更快一些。

最後，第三個，我們稱之爲 「最好的」（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)]揭示了運行時的行爲，這似乎仍然是兩個實現基本上不同：

例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 

有意思的是，在這兩種情況下，新的JIT幾乎都在同時運行選擇和非選擇X64版本。

問題依然是：爲什麼編譯器不能優化這些模式？我的猜測是，這是因爲像運算符重載這樣的東西，這使得編譯器無法推斷出一些正確的邏輯結論，但II可能非常關閉......而且，對於內置值類型，它應該是可能的。好吧...

最後，這裏的一對優化的好articel布爾表達式： https://hbfs.wordpress.com/2008/08/26/optimizing-boolean-expressions-for-speed/