プログラミング言語 C の新機能 Part XXVI: restrict ポインタ
(1999/10/18 [月])
C 言語は高級言語としてはポインタをかなり自由に使える言語です。その結果、プログラマがポインタを上手に使えば早いプログラムを書けるようになりました。しかしその一方で、ポインタの別名を簡単に作ることができるようになってしまったので、コンパイラがデータ解析や最適化コードを生成する時の障害になってきました。例えば、次の例を見てください。
(1)の部分のsumup 関数は array1 に array2 の内容を n 個分足し込む関数です。ただしここでこのプログラム中では n の値が 4 の倍数で array1 と array2 は同じ内容を指していない呼び出ししかしないと仮定できることとします。するとそれに対応して SIMD 命令を使用できる CPU 上のアセンブラのコードのループ部分は (2) のように最適化することができます。まず array1 の 4 要素分を r1 レジスタに格納します。そして同様に array2 の 4 要素分を r2 レジスタに入れ、それを r1 と加算して、結果となる r1 を array1 に書き戻します。たった一命例で配列 4 要素分の加算ができ、また結果として n/4 回のループで計算できるのでこのコードは効率的です。
しかし現実にはコンパイラはこのような効率的なコードを生成することはできませんでした。なぜならば、コンパイラは array1 と array2 が同じ内容を指していないと仮定してよいことはまったく知りません。したがって、(3) のような呼び出しにも対応する (2) よりも劣るコード (4) を生成する必要があります。(4) は配列の要素一つずつ加算していくので n 回のループと加算が行われることになります。
(3) の呼び出し後の正しい array の値は、つまり (4) で計算した結果は { 1, 2, 4, 6, 9, 12, } になるはずです。しかし、(2) のコードでは、この値は、{ 1, 2, 4, 6, 8, 10, } になってしまい、(4) で計算した結果の値と異なった値を返すことになります。このように、現在の C 言語ではコンパイラによる解析やコード生成を妨げる要因が含まれています。
今回の C 言語から利用できるようになる restrict 修飾子は、前述したようなポインタが同じ内容を指していないという情報をコンパイラに提供することができます。restrict はポインタだけを修飾するために利用することができます。(1) に restrict 修飾したコードを (5) に示します。
(5) では計算中に array1 と array2 がけっして同じ内容を指していないという情報をコンパイラに与えています。したがって、コンパイラはこの情報を元に (2) のようなコードを生成することができます。このようなことから、(6) のような呼び出しは正しく動作しますが、(7) のような呼び出しをした場合には、言語的には未定義の動作になり、たぶん正しい結果を残さないでしょう。
なお、ライブラリの中のポインタを引数に持つ複数の関数プロトタイプが restrict 修飾子付きの宣言に変更されました。
//(1)
void sumup(int n, int *array1, int *array2)
{
assert((n % 4)== 0);
for(int i = 0; i < n; i++) array1[i] += array2[i];
}
//(2)
trymore:
r1 ← array1[i+0]:[i+1]:[i+2]:[i+3]
r2 ← array2[i+0]:[i+1]:[i+2]:[i+3]
r1 += r2
array1[i+0]:[i+1]:[i+2]:[i+3] ← r1
i += 4
if( i < n ) goto trymore
|
(1)の部分のsumup 関数は array1 に array2 の内容を n 個分足し込む関数です。ただしここでこのプログラム中では n の値が 4 の倍数で array1 と array2 は同じ内容を指していない呼び出ししかしないと仮定できることとします。するとそれに対応して SIMD 命令を使用できる CPU 上のアセンブラのコードのループ部分は (2) のように最適化することができます。まず array1 の 4 要素分を r1 レジスタに格納します。そして同様に array2 の 4 要素分を r2 レジスタに入れ、それを r1 と加算して、結果となる r1 を array1 に書き戻します。たった一命例で配列 4 要素分の加算ができ、また結果として n/4 回のループで計算できるのでこのコードは効率的です。
しかし現実にはコンパイラはこのような効率的なコードを生成することはできませんでした。なぜならば、コンパイラは array1 と array2 が同じ内容を指していないと仮定してよいことはまったく知りません。したがって、(3) のような呼び出しにも対応する (2) よりも劣るコード (4) を生成する必要があります。(4) は配列の要素一つずつ加算していくので n 回のループと加算が行われることになります。
//(3)
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, }
sumup(4, array+2, array);
//(4)
trymore:
r1 ← array1[i]
r2 ← array2[i]
r1 += r2
array1[i] ← r1
i ++
if( i < n ) goto trymore
|
(3) の呼び出し後の正しい array の値は、つまり (4) で計算した結果は { 1, 2, 4, 6, 9, 12, } になるはずです。しかし、(2) のコードでは、この値は、{ 1, 2, 4, 6, 8, 10, } になってしまい、(4) で計算した結果の値と異なった値を返すことになります。このように、現在の C 言語ではコンパイラによる解析やコード生成を妨げる要因が含まれています。
今回の C 言語から利用できるようになる restrict 修飾子は、前述したようなポインタが同じ内容を指していないという情報をコンパイラに提供することができます。restrict はポインタだけを修飾するために利用することができます。(1) に restrict 修飾したコードを (5) に示します。
//(5)
void sumup(int n, int * restrict array1, int * restrict array2)
{
assert((n % 4)== 0);
for(int i = 0; i < n; i++) array1[i] += array2[i];
}
//(6)
sumup(4, array+4, array);
//(7)
sumup(4, array+2, array);
|
(5) では計算中に array1 と array2 がけっして同じ内容を指していないという情報をコンパイラに与えています。したがって、コンパイラはこの情報を元に (2) のようなコードを生成することができます。このようなことから、(6) のような呼び出しは正しく動作しますが、(7) のような呼び出しをした場合には、言語的には未定義の動作になり、たぶん正しい結果を残さないでしょう。
なお、ライブラリの中のポインタを引数に持つ複数の関数プロトタイプが restrict 修飾子付きの宣言に変更されました。
by seclan