剰余区間の拡張とデータ依存解析への応用

摘要

データ依存解析で扱われる数は、ループ変数や配列の添字変数等が取り得る値であり、規則的な性質を持った整数の集合である。 剰余区間はこのような整数の集合を表すのに適した表現であり、その演算規則はシンプルでコンパイラへの実装も容易である。 しかし、剰余区間演算は集合の要素間で演算した結果の集合として定義されており、剰余区間同士の演算結果は一般的には剰余区間では表すことは不可能で、近似的にしか表せない。 近似した演算規則による結果は、厳密な演算結果より大きい集合を表す性質を持つため、演算を繰り返すと演算誤差が累積することになる。 本論文では、剰余区間演算による誤差を削減するため、剰余区間を一般化した拡張剰余区間とその演算規則を考える。 また拡張剰余区間をデータ依存解析に応用し、その有効性を示す。