大域配列データフロー解析法
金田 泰, 石田 和久, 布広 永二, 情報処理学会論文誌, Vol. 28, No. 6, pp. 567-576, 1987.
[ English page ]
[ PDF 版論文へのいりぐち (IPSJ) ]
要旨: 配列参照どうしのデータ依存関係としてフロー依存，出力依存および 逆依存があり，これらをグラフ化したのがデータ依存グラフである． 配列参照どうしのデーク依存関係は，従来，各配列参照の添字を 比較してその結果から直接もとめていたが，この方法ではプログラムの 制御構造を反映したデータ依存関係をもとめることがむずかしい． 筆者らは，多重ループの添字を解析することができる添字比較法と， 到達定義 (reaching definitions) や露出使用 (exposed uses) を もとめる変数の大域データフロー解析法とをくみあわせることによって， 条件文や多重ループなどの制御構造を反映したデータ依存グラフを もとめる，配列の大域データフロー解析法を開発した． この解析法では，データ依存関係をループ独立依存， ループ運搬依存などに分類することができる． ここで， ループ独立依存とはプログラム中のループ内の文を1回実行する あいだに生じるデータ依存関係のことをいい，ループ運搬依存とは それを 2 回以上実行することによってはじめて生じる データ依存関係のことをいう． この解析法によって， 従来より強力なベクトル化や最適化ができるようになった．
研究テーマ紹介: ベクトル / 並列計算機のためのプログラミング言語処理