3

次のような疑似コードがあるとします。

main() {
    BOOL b = get_bool_from_environment(); //get it from a file, network, registry, whatever
    while(true) {
        do_stuff(b);
    }
}

do_stuff(BOOL b) {
    if(b)
        path_a();
    else
        path_b();
}

ここで、外部環境が影響get_bool_from_environment()を与えて真または偽の結果を生成する可能性if(b)があることがわかっているので、 の真と偽の両方のブランチのコードをバイナリに含める必要があることがわかります。path_a();コードから単に省略したり、コードから除外したりすることはできませんpath_b();。

BUT -- 設定BOOL bは 1 回だけで、プログラムの初期化後は常に同じ値を再利用します。

この有効な C コードを作成し、 を使用してコンパイルするとgcc -O0、が呼び出されるif(b)たびにプロセッサ上で繰り返し評価され、do_stuff(b)基本的に静的なブランチのパイプラインに不要な命令が挿入されると考えられます。初期化後。

と同じくらい愚かなコンパイラを実際に持っていると仮定すると、gcc -O0このコードを書き直して、関数ポインタと、テストを実行しない2 つの別個の関数do_stuff_a()とを含めることになりますが、単に先に進んで、 2 つのパスのいずれかを実行します。次に、の値に基づいて関数ポインタを割り当て、ループ内でその関数を呼び出します。これにより分岐がなくなりますが、確かに関数ポインターの逆参照のためのメモリアクセスが追加されます (アーキテクチャの実装により、私は本当にそれについて心配する必要はないと思います)。do_stuff_b()if(b)main()b

原則として、コンパイラが元の疑似コード サンプルと同じスタイルのコードを取得し、 の値がbに一度割り当てられると、テストが不要であることに気付くことは可能main()ですか? もしそうなら、このコンパイラー最適化の理論上の名前は何ですか? また、これを行う実際のコンパイラー実装 (オープンソースまたはそれ以外) の例を教えてください。

コンパイラは実行時に動的コードを生成できず、原則としてそれを実行できるシステムは、バイトコード仮想マシンまたはインタープリター (Java、.NET、Ruby など) だけであることを認識しています。これを静的に実行して、path_a();ブランチとブランチのpath_b()両方を含むコードを生成できるかどうか。 if(b)do_stuff(b);

4

1 に答える 1

3

コンパイラに最適化するように指示すると、if(b)が 1 回だけ評価される可能性が高くなります。

_Boolの代わりに標準を使用して、指定された例をわずかに変更しBOOL、不足している戻り値の型と宣言を追加します。

_Bool get_bool_from_environment(void);
void path_a(void);
void path_b(void);

void do_stuff(_Bool b) {
    if(b)
        path_a();
    else
        path_b();
}

int main(void) {
    _Bool b = get_bool_from_environment(); //get it from a file, network, registry, whatever
    while(1) {
        do_stuff(b);
    }
}

clang -O3[clang-3.0]によって生成されたアセンブリ (の関連部分) は、

    callq   get_bool_from_environment
    cmpb    $1, %al
    jne     .LBB1_2
    .align  16, 0x90
.LBB1_1:                                # %do_stuff.exit.backedge.us
                                        # =>This Inner Loop Header: Depth=1
    callq   path_a
    jmp     .LBB1_1
    .align  16, 0x90
.LBB1_2:                                # %do_stuff.exit.backedge
                                        # =>This Inner Loop Header: Depth=1
    callq   path_b
    jmp     .LBB1_2

bは 1 回だけテストされ、 の値に応じてまたはmainの無限ループにジャンプします。とが十分に小さい場合、それらはインライン化されます (私は強く期待しています)。と を使用すると、clang によって生成されたコードは、ループの各反復で評価されます。path_apath_bbpath_apath_b-O-O2b

gcc (4.6.2) は次の場合と同様に動作し-O3ます。

    call    get_bool_from_environment
    testb   %al, %al
    jne     .L8
    .p2align 4,,10
    .p2align 3
.L9:
    call    path_b
    .p2align 4,,6
    jmp     .L9
.L8:
    .p2align 4,,8
    call    path_a
    .p2align 4,,8
    call    path_a
    .p2align 4,,5
    jmp     .L8

奇妙なことに、 for のループを展開しましたが、 for は展開しpath_aませんでしたpath_b。-O2またはを使用すると、無限ループで-O呼び出されます。do_stuff

したがって、

原則として、コンパイラが元の疑似コード サンプルと同じスタイルのコードを取得し、 の値がbに一度割り当てられると、テストが不要であることに気付くことは可能main()ですか?

はい、コンパイラがこれを認識し、その事実を利用することは可能です。優れたコンパイラは、ハードな最適化を求められたときに実行します。

もしそうなら、このコンパイラー最適化の理論上の名前は何ですか? また、これを行う実際のコンパイラー実装 (オープンソースまたはそれ以外) の例を教えてください。

最適化の名前はわかりませんが、それを行っている 2 つの実装は gcc と clang (少なくとも最近の十分なリリース) です。

于 2013-01-15T19:56:11.057 に答える