コンパイラのFor文の最適化

本ブログ作成文は、講義を目指して製作されました。 また、作成された文章の情報も間違っている可能性がありますので、ご注意ください。

CPUの立場でFor文に使われるJMP命令は、 パイプラインを壊したり、分岐予測が失敗した場合、パフォーマンスが低下するため、 コンパイラは、条件を満たしていればJMP命令を使用しないようにします。

1. 繰り返し回数がコンパイル時に定数に確定したとき。

最適化可能: for (int i = 0; i < 4; i++) (4回繰り返されることを意味) 最適化の難しさ: for (int i = 0; i < n; i++) (n が実行時に決定される変数の場合)

//オリジナルコード
for (int i = 0; i < 3; i++) {
    arr[i] = 0;
}

//コンパイラの最適化後
arr[0] = 0;
arr[1] = 0;
arr[2] = 0;

最適化前のアセンブリ

.L2:
    cmp     DWORD PTR [rbp-4], 2    ;i < 3認知比較
    jg      .L3                     ;条件が合わない場合はループ終了（L3にジャンプ）
    mov     eax, DWORD PTR [rbp-4]
    cdqe
    mov     DWORD PTR [rbp-32+rax*4], 0 ;arr[i] = 0 代入
    add     DWORD PTR [rbp-4], 1    ; i++
    jmp     .L2                     ;再びループ開始点（.L2）に無条件にジャンプ（JMP）
.L3:

最適化されたアセンブリ

mov     DWORD PTR [rdi], 0      ; arr[0] = 0
mov     DWORD PTR [rdi+4], 0    ;arr[1] = 0 (int は 4 バイトなので +4)
mov     DWORD PTR [rdi+8], 0    ;arr[2] = 0 (int は 4 バイトなので +8)

1. コンパイル時に最終結果値を事前に計算できる場合。

ループ内部のロジックが外部入出に依存しない場合、結果値を定数に置き換えてしまう。

//オリジナルコード
int sum = 0;
for (int i = 1; i <= 100; i++) {
    sum += i;
}
return sum;

//コンパイラの最適化後
//JMPはこんにちは加算演算でさえランタイムにしない。
return 5050;

最適化前のアセンブリ

.L5:
    cmp     DWORD PTR [rbp-4], 100  ;i <= 100認知比較
    jg      .L6                     ;またはループ終了
    mov     eax, DWORD PTR [rbp-4]
    add     DWORD PTR [rbp-8], eax  ; sum += i
    add     DWORD PTR [rbp-4], 1    ; i++
    jmp     .L5                     ;ループ開始点（.L5）にジャンプ（JMP）
.L6:
    mov     eax, DWORD PTR [rbp-8]  ;結果値を返す準備

最適化後のアセンブリ

mov     eax, 5050                   ;計算された結果値5050をeaxレジスタに挿入
ret                                 ;すぐに返す

1. ループ展開をしてもコード長が短いとき。

1番コードのようにループを展開することをループ展開またはLoop Unrollingという。 ループ展開をすることでコード長が長すぎると、CPUの命令キャッシュメモリを無駄にするわけになるので ループ内部のコードサイズが小さくない場合、Loop Unrolling最適化をしない。

1. ループ内に複雑な制御フローがない場合。

ループ内に break、continue、goto、または複雑な if-else ステートメントがあるか、 外部関数呼び出しが含まれている場合、コンパイラはむしろループを展開しません。

printfのようなI / O関数が含まれている場合、 画面に出力する付随効果を守らなければならないので、ループを省略せずに正直にJMPを回して関数を呼び出す。

番外でコンパイラ最適化オプションがオンになってこそ、上記のように最適化を試みる。