C++コンパイラは "for"ループ内のif文を最適化できますか？

Question

flagがforループ内で変更されない場合、これは意味的に次のようになります。

for (condition) 
    if (flag) 
    do_something(); 
    else 
    do_something_else(); 

最初のケースでのみ、より長い（例えば、いくつかのforループが使用される場合、またはdo_something()がほとんどdo_something_else()と同一のコードブロックである場合）、2番目のケースではフラグが何度もチェックされます。

現在のC++コンパイラ（最も重要なのはg ++）が、forループ内で繰り返されるテストを取り除くために2番目の例を最適化できるかどうか不思議です。もしそうなら、これはどのような条件下で可能ですか？

Answer 1

はい、フラグが変更されず、do_somethingまたはdo_something_elseによって変更できないと判断された場合、ループ外に引き出すことができます。私はループホイストと呼ばれるこのことについて聞いたことがありますが、Wikipediaには「ループ不変コード運動」と呼ばれるentryがあります。

フラグがローカル変数の場合、コンパイラは生成されたコードの動作に影響を与えないことが保証されているため、この最適化を実行できるはずです。

フラグがグローバル変数で、ループ内で関数を呼び出すと、最適化が実行されない可能性があります。これらの関数がグローバルを変更するかどうかを判断できない場合があります。

これは最適化の種類によっても影響を受ける可能性があります。サイズを最適化すると非ホイストバージョンが優先され、スピードが最適化されるのはおそらくホイストバージョンが優先されます。

プロファイリングがホットスポットであり、効率的ではないコードが実際にコンパイラのアセンブリを経由して生成されていることがわかっていない限り、これはあなたが気にするべきことではありません出力する。このようなマイクロ最適化は、あなたが絶対に必要としない限り、コンパイラに任せておくだけです。

Answer 2

私は、コンパイラはフラグが一定に保たれることを確認できた場合、それはいくつかのshuffllingを行うことができます確信している：

const bool flag = /* ... */; 
for (..;..;..;) 
{ 
    if (flag) 
    { 
     // ... 
    } 
    else 
    { 
     // ... 
    } 
} 

flagがconstされていない場合、コンパイラは必ずしもループを最適化することはできません、それはので、 flagは変更されません。それは静的解析を行うことができますが、すべてのコンパイラではできません。 constは、フラグが変更されないことをコンパイラに伝える確実な方法です。

いつものように、プロファイルは実際に問題があるかどうかを調べます。

Answer 3

それは不変ループと呼ばれていますし、最適化がループ不変コードの移動とを巻き上げもコードと呼ばれます。条件付きであるという事実は、コード分析をより複雑にし、コンパイラは、オプティマイザの巧妙さに依存して、ループおよび条件付きを反転させることができるかどうかを決定する。

この種の質問には、一般的な答えがあります。これは、プログラムをコンパイルし、生成されたコードを調べることです。

Answer 4

私はそれがそうであると言うことを躊躇します。この値、または別のスレッドによって値が変更されないことを保証できますか？

つまり、コードの2番目のバージョンは一般的に読みやすく、おそらくコードブロック内で最後に最適化することになります。

Answer 5

通常、はいです。しかし、保証はなく、コンパイラが行う場所はおそらくまれです。

問題なくほとんどのコンパイラが行うことは、ループから不変な評価を引き出すことです。あなたの条件が

if (a<b) .... 

の場合、aとbがループの影響を受けない場合、ループの前に一度比較が行われます。

これは、条件が変化しないとコンパイラが判断できる場合は、テストが安価であり、ジャンプwenllが予測したことを意味します。これは、テスト自体が1サイクルまたは全くサイクルを要しないことを意味する（実際には）。

ループを分割するとどのような場合に有益でしょうか？両方の部分とループ全体が今、コードキャッシュ

に適合しない

a）の1サイクルは、大幅なコスト
bは非常にタイトなループ）、コンパイラはコードのみについての仮定を行うことができます通常、1つのブランチがキャッシュに収まるようにコードを注文することができます。任意のテストせず

、I'dexpectそれは常にNTO良い選択だbecasueこのような最適化は、適用されるa）の場合のみ：ループを分割する場合は悪いだろう

ていますか？

ループを分割してコード・キャッシュを超えてコード・サイズを増やすと、大きなヒットになります。これは、ループ自体が別のループ内で呼び出された場合にのみ影響しますが、コンパイラが通常判別できないものです。

私は

extern volatile int vflag = 0; 

int foo(int count) 
{ 
    int sum = 0; 
    int flag = vflag; 
    for(int i=0; i<count; ++i) 
    { 
     if (flag) 
     sum += i; 
     else 
     sum -= i; 
    } 

    return sum; 
} 

VC9は、次のループを分割する（それが実際に有益であるかもしれないいくつかの例1）を得ることができませんでした[編集]
[編集2]
int flag = true;では、2番目のブランチは最適化されています。 （いいえ、constはここで違いはありません;））

それはどういう意味ですか？

一般的に、私はこれが非常に少数のケースでしか価値がない最適化であることを想起し、実行することができますほとんどのシナリオで簡単に手作業で行うことができます。

Answer 6

多くの人が言っているとおりです。

確かめたい場合は、コンパイル時の決定を強制するようにしてください。 GCCおよび-O3で試してみました

for (condition) 
    do_it<flag>(); 

Answer 7

：

void foo(); 
void bar(); 

int main() 
{ 
    bool doesnt_change = true; 
    for (int i = 0; i != 3; ++i) { 
     if (doesnt_change) { 
      foo(); 
     } 
     else { 
      bar(); 
     } 
    } 
} 

メインのための結果：

_main: 
pushl %ebp 
movl %esp, %ebp 
andl $-16, %esp 
call ___main 
call __Z3foov 
call __Z3foov 
call __Z3foov 
xorl %eax, %eax 
leave 
ret 

だから、選択肢を離れて最適化しない（とアンロールテンプレートは、多くの場合、このために便利になりますより小さなループ）。

doesnt_changeがグローバルである場合、この最適化は行われません。