コンパイラ述語の最適化

Question

次の例の条件/述語を考える：1. x > 20と2に簡略化することができる

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

x >= 10 and x <= 10別名述語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   

2番目のバージョンが明らかに短いため、実行時にインライン化する可能性が高くなりますので、少し速く実行する必要があります。

最後に、3つ目は、のは（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   

ニースと簡潔な。

ケース1：10ない試験の候補（負の場合）

Benchmark.NETを使用してベンチマークを実行し、[MethodImpl(MethodImplOptions.NoInlining)]は、2つの実装のために依然として実質的に異なると思われる実行時の動作を明らかにする。

 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はOPTと非オプトX64版のほぼ同じ時間に実行されることです。

質問はまだあります：なぜコンパイラはこの種のパターンを最適化しないのですか？コンパイラがいくつかの正しい論理的結論を推論することは不可能になるが、IIは非常にオフになる可能性があるオペレータのオーバーロードのようなものだと私の推測だろう...また、組み込みの値の型については可能でなければならない。しかたがない...

最後には、ここでのブール式の最適化には良いarticelです： https://hbfs.wordpress.com/2008/08/26/optimizing-boolean-expressions-for-speed/