variables - 還元変数とは何ですか？誰かが私にいくつかの例を教えてもらえますか？

Question

還元変数とは何ですか？誰かが私にいくつかの例を教えてもらえますか？

Answer 1

配列の合計を計算する C ライクな言語の簡単な例を次に示します。

int x = 0;
for (int i = 0; i < n; i++) {
    x += a[i];
}

この例では、

• i誘導変数です-各反復で、定数によって変化します。+1(上記の例のように) or or*2など/3になりますが、重要なのは、すべての反復で数が同じであるということです。

  言い換えれば、各反復ではi_new = i_old op constant、 whereopは+、*などであり、反復間で変化することopもありません。constant

• xリダクション変数です。ある反復から次の反復までのデータを累積します。常にいくつかの初期化があり (x = 0この場合)、蓄積されたデータは反復ごとに異なる可能性がありますが、オペレーターは同じままです。

  言い換えれば、各反復x_new = x_old op dataで 、およびopはすべての反復で同じままです (ただし、data変更される可能性があります)。

多くの言語では、このようなことを実行するための特別な構文があります- 多くの場合、「fold」または「reduce」または「accumulate」と呼ばれます (他の名前もあります) - しかし、LLVM IR のコンテキストでは、帰納変数は次のように表されます。ループ内の 2 項演算とその前の初期化値の間のループ内の phi ノード。

リダクション変数の可換*演算 (加算など) は、最適化コンパイラにとって特に興味深いものです。たとえば、上記の例はベクトル化された形式に書き直すことができます。たとえば、一度に 4 つの数値を追加し、その後に小さなループを追加して、最終的なベクトルを 1 つの値に合計します。

_{* 実際には、このようなベクトル化を適用する前にリダクション変数が満たさなければならない条件が他にもありますが、それは実際にはここでは範囲外です}