(57)【特許請求の範囲】
【請求項１】
ソースプログラムまたは中間コードから、複数データに対して並列演算を実行するSIMD命令を用いるコードを生成するコンピュータのコード生成方法であって、
中間コードのループを解析して、一定値以下の定数長のSIMD命令適用対象データ列を含む内側データ部のデータ列の長さである内側データ長、およびSIMD命令により何個のデータを並列に処理するかを表わすSIMD並列度を取得する構造解析ステップと、
前記構造解析ステップで求めた前記内側データ長を前記SIMD並列度で割ったときの余りの値である端数を計算し、前記SIMD並列度と前記端数との公倍数を端数で割った値を、前記内側データ部を囲む外側ループのループ展開数として求める展開数計算ステップと、
前記展開数計算ステップで求めたループ展開数に従いループを展開するループ展開ステップと、
をコンピュータが実行することを特徴とするコード生成方法。
【請求項２】
請求項１のコード生成方法であって、
前記公倍数は、SIMD並列度と端数の最小公倍数であることを特徴とするコンピュータのコード生成方法。
【請求項３】
請求項１のコード生成方法であって、
前記公倍数は、SIMD並列度に端数を乗じた値であることを特徴とするコンピュータのコード生成方法。
【請求項４】
請求項１のコード生成方法であって、
前記中間コードのループについて外側ループ及び内側ループの情報を記載したループ表を参照して、前記構造解析ステップ、前記展開数計算ステップおよび前記ループ展開ステップを前記ループに対して行うかどうか判断するステップをコンピュータが更に実行することを特徴とするコンピュータのコード生成方法。
【請求項５】
ソースプログラムまたは中間コードから、複数データに対して並列演算を実行させるSIMD命令を用いるコードをコンピュータに生成させるコンパイラであって、
コードのループを解析して、一定値以下の定数長のSIMD命令適用対象データ列を含む内側データ部のデータ列の長さである内側データ長、およびSIMD命令により何個のデータを並列に処理するかを表わすSIMD並列度を取得する構造解析ステップと、
前記構造解析ステップで求めた前記内側データ長を前記SIMD並列度で割ったときの余りの値である端数を計算し、前記SIMD並列度と、前記端数との公倍数を端数で割った値を前記内側データ部を囲む外側ループのループ展開数として求める展開数計算ステップと、
前記展開数計算ステップで求めたループ展開数に従いループを展開するループ展開変換ステップと、
をコンピュータに実行させることを特徴とするコンパイラ。
【請求項６】
請求項５のコンパイラであって、
前記公倍数は、前記SIMD並列度と前記端数の最小公倍数であることを特徴とするコンパイラ。
【請求項７】
請求項５のコンパイラであって、
前記公倍数は、前記SIMD並列度に前記端数を乗じた値であることを特徴とするコンパイラ。
【請求項８】
請求項５のコンパイラであって、
前記中間コードのループについて外側ループ及び内側ループの情報を記載したループ表を参照して、前記構造解析ステップ、前記展開数計算ステップ及び前記ループ展開変換ステップを前記ループに対して処理を行わせるかどうか判断するステップを更にコンピュータに実行させることを特徴とするコンパイラ。
【請求項９】
ソースプログラムまたは中間コードから、複数データに対して並列演算を実行するSIMD命令を用いるコードを生成するコンピュータであって、
中間コードのループを解析して、一定値以下の定数長のSIMD命令適用対象データ列を含む内側データ部のデータ列の長さである内側データ長、およびSIMD命令により何個のデータを並列に処理するかを表わすSIMD並列度を取得する構造解析部と、
前記構造解析ステップで求めた前記内側データ長を前記SIMD並列度で割ったときの余りの値である端数を計算し、前記SIMD並列度と前記端数との公倍数を端数で割った値を、前記内側データ部を囲む外側ループのループ展開数として求める展開数計算部と、
前記展開数計算ステップで求めたループ展開数に従いループを展開するループ展開変換
部と、
を有することを特徴とするコンピュータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル技術に関し、特に、複数データに対するメモリアクセスや演算を行うSIMD命令を使用するためのコンパイル技術に関する。
【背景技術】
【０００２】
１つのレジスタ上に複数のデータを保持し、複数データに対して並列演算を実行できる命令を備えたアーキテクチャが一般的になってきている。例えば非特許文献１に記載されているマルチメディア命令拡張SSEでは、16バイトのレジスタを用いて複数のデータを一括して扱える。例えば4バイトの単精度浮動小数点データの場合、4個のデータに対する演算を、1つのレジスタ上で並列に実行できる。このような命令をSIMD(single-instruction-multiple-data)命令と呼び、SIMD命令を用いたコード生成を行う最適化をSIMD最適化と呼ぶ。
【０００３】
SIMD最適化を実現する方式としては、主としてストライド１の配列要素参照を用いた演算式を含むループに対してベクトル化の手法を用いた変換を行う方式（ベクトル化方式と呼ぶ）と、ループと無関係に、近傍の参照から隣接要素の組を見つけ、これらを結合することによる変換を行う方式（命令結合方式と呼ぶ）の二方式がある。ベクトル化方式については非特許文献１の第5章に記載されている。命令結合方式については、非特許文献２に記載されている。
【０００４】
ベクトル方式による変換例を図５に示す。図５(a)のソースプログラム（C言語で記述）において、最内側のkループに着目する。配列aのアクセスは、ループ制御変数kが最下位次元の配列添え字となっているため、ストライド１の連続参照であり、本ループはベクトル化可能である。配列aの型(int型)に対して、SIMD命令により4個のデータを同時にアクセス可能である（SIMD並列度4）とすると、kループに対して4倍のループ展開（アンローリング）を適用し、SIMD化変換を行う。変換後のコードイメージを図５(b)に示す。kループ内の文で、配列aの添え字の’k:k+3’は、kからk+3、即ちｋ、ｋ＋１、ｋ＋２、ｋ＋３の4要素のアクセスを示す記法とする。左辺はa[i][j][k]を先頭とする4要素への代入を示し、右辺は4個のv2を1つのレジスタ上にまとめたデータを示す。このように、SIMD化対象のループ内では元の4個の文に相当する処理を1文で行う。kループの元のループ長は5であるから、4倍ループ展開による余りは１である。余りの要素a[i][j][4]に対しては、ループ後に通常の代入処理を行うコードを生成する。
【０００５】
次に、命令結合方式による変換例を図７に示す。図７(a)のソースプログラム（C言語で記述）において、ループ内の3個の文に着目する。配列aのSIMD並列度を2と仮定すると、a[i][0]とa[i][1]は隣接する要素で同時アクセス可能であるから、先頭の2文を結合する。変換後のコードイメージを図７（ｂ）に示す。
【０００６】
【非特許文献１】Aart J.C. Bik, The Software Vectorization Handbook, Intel Press, 2004.
【非特許文献２】Samuel Larsen and Saman Amarasinghe, Exploiting Superword Level Parallelism with Multimedia Instruction Sets, Proc. of the SIGPLAN 2000 Conference on Programming Language Design and Implementation, 2000.
【発明の開示】
【発明が解決しようとする課題】
【０００７】
SIMD最適化の対象とする範囲のデータ長が短い場合、データ長がSIMD並列度で割り切れない場合には、端数部分にはSIMD化が適用されない。実際には連続でSIMD化適用が可能な長いデータ列があり、最適化対象に選択した部分（例えば最内側ループの参照）がそのデータ列の一部の短データ列であった場合には、端数部分にSIMD化が適用されない分、SIMD化適用率が低下し実行性能向上への効果が小さくなってしまう。例えば、図５(a)のソースプログラムの場合、kループおよびjループのアクセス範囲が配列aの3次元目と2次元目の宣言と一致しており、3重ループによりaの全要素を連続的に参照する。この場合、並列度４のSIMD化適用により、aへのストア命令は4分の1に削減可能である。ところが、図5（ｂ）のような変換では、ループ展開後のkループは1イタレーションしか実行されず、長さ5のデータ列を2命令で実行することになるため、ストア命令数の削減率は5分の2となり、実行性能の向上が不十分である。また、図7(a)のソースプログラムにおいても配列aを連続的に参照しているため、ストア命令を2分の1に削減可能であるが、図7(b)の変換における削減率は３分の２である。
【０００８】
本発明の目的は、従来のSIMD化方式による対象データ列が、外側ループに跨った長い連続データ列の一部分である場合に、外側ループを考慮したSIMD化変換を実施することにより、端数部分のないSIMD化コードを生成する方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明は、対象ループを解析して、内側データ長およびSIMD並列度を取得する構造解析手段と、内側データ部を囲む外側ループのループ展開数を求める展開数計算手段と、展開数計算手段で求めた展開数に従いループを展開するループ展開手段、および展開後のループに対してSIMDコードの生成を行うSIMDコード変換手段から成る。
【００１０】
展開数計算手段では、内側データ長をSIMD並列度で割ったときの余りの値（端数と呼ぶ）を計算し、SIMD並列度と端数の公倍数を端数で割った値を展開数とする。
【００１１】
内側データ長の取得においては、ベクトル化方式対象ループについては内側の定数ループ長を解析し、命令結合方式対象ループについては内側ループ内の連続参照から成る内側データ列のデータ長を解析する。
【発明の効果】
【００１２】
本発明によれば、内側ループに属する短データで外側ループのイタレーション間で連続なデータ列にSIMD化を適用する際、内側短データ長がSIMD並列度で割り切れない場合の端数部分に対してSIMD化が非適用になることがなくなり、SIMD命令の適用率を向上させることで生成コードの実行性能向上を図ることができる。
【発明を実施するための最良の形態】
【００１３】
以下に、本発明の実施の形態を説明する。
【実施例１】
【００１４】
以下、図面を用いて本発明の実施の形態について説明する。
【００１５】
図２に本実施形態によるコンパイラが稼動する計算機システムの構成図を示す。この計算機システムは、制御手段としてのＣＰＵ(Central Processing Unit)２０１、表示手段としてのディスプレイ装置２０２、入力手段としてのキーボード２０３、記憶手段としての主記憶装置２０４、および記憶手段としての外部記憶装置２０５から構成されている。キーボード２０３により、ユーザからのコンパイラ起動命令を受け付ける。コンパイラ終了メッセージやエラーメッセージは、ディスプレイ装置２０２に表示される。外部記憶装置２０５には、ソースプログラム２０９と、オブジェクトプログラム２１０が格納される。主記憶装置２０４には、コンパイラ２０６、コンパイル過程で必要となる中間コード２０７およびループ表２０８が格納される。コンパイル処理はＣＰＵ２０１がコンパイラ２０６を実行することにより行われる。
【００１６】
本発明によるコンパイラはSIMD最適化部２１１を含む。本最適化部内の特徴的な処理部として、内側データ長解析部２１２、SIMD並列度解析部２１３、ループ展開数計算部２１４、ループ展開変換部２１５がある（内側データ長解析部２１２とSIMD並列度解析部２１３をまとめて構造解析部と称す。）。これらSIMD最適化部の処理については、本発明の特徴的な部分であるので、後で詳細に説明する。
【００１７】
図３に、図２のシステムで稼動するコンパイラ２０６の処理手順を示す。
【００１８】
コンパイラ２０６は、ステップ３０１において、ソースプログラム２０９を入力として構文解析を行い、中間コード２０７を出力する。以下のコンパイル処理ではこの中間コードを対象に変換を行う。構文解析の方法や中間コードの例については、例えば、「Aho, Sethi, Ullman著, “Compilers: Principles, Techniques, and Tools”, Addison-Wesley, 1986」に記載されている。
【００１９】
次にステップ３０２のループ解析において、コンパイラ２０６は、プログラム内に含まれるループの集合を、求め、ループ表２０８に記録する。ループ解析の方法に関しては、例えば、Michael Wolfe著「High Performance Compilers for Parallel Computing」、Addison-Wesley Publishing Company, 1996の６７頁に記載されている。
【００２０】
次にステップ３０３において、コンパイラ２０６のSIMD最適化部２１１がSIMD最適化３０３を行う。本ステップの処理手順については、本発明の特徴となる部分であるので、後述する。
【００２１】
次に、コンパイラ２０６が、ステップ３０４において、レジスタ割付けを行った後、ステップ３０５においてコード生成を行い、中間コード２０７をオブジェクトプログラム２１０に変換して出力する。レジスタ割付けやコード生成の方法に関しては、前述のAhoらの文献に記載されている。
【００２２】
ここで、上記ステップ３０２のループ解析により生成されるループ表２０８について説明する。図８にループ表２０８の一例を示す。ループ表２０８には、ループ番号８０１、親ループ８０２、子ループ803、制御変数８０４、初期値８０５、終値８０６、増分値８０７、ループ長８０８が格納される。
【００２３】
ループ番号８０１は、コンパイラ内でループを識別するための番号である。親ループ８０２は、対象ループを取り囲む外側ループのうち最も内側のループのループ番号である。対象ループが最も外側のループの場合、「なし」が登録される。子ループ８０３は、対象ループの内側ループのうち最も外側のループのループ番号である。対象ループが最も内側のループの場合、「なし」が登録される。制御変数８０４は、対象ループの繰り返しを制御するループ制御変数である。初期値８０５、終値８０６、増分値８０７は、それぞれ、制御変数８０４の初期値、終値、繰り返しごとの増分である。ループ長８０８は、ループの繰り返し回数である。ループ長は、ループ制御変数の初期値、終値、増分値から求められる。
【００２４】
以下、本発明の特徴であるSIMD最適化３０３の処理の詳細について説明する。図１にSIMD最適化３０３の処理手順の詳細を示す。
【００２５】
本実施例におけるSIMD最適化は、ループを処理単位として実施する。そこで、ステップ１０１では、コンパイラ２０６が、未処理のループがあるかどうかを判定し、あれば未処理のループを１つ処理対象として取り出してステップ１０２へ進む。未処理のループがなければ処理を終了する。
【００２６】
ステップ１０２では、コンパイラ２０６が、SIMD最適化の対象ループであるかを判定する。対象ループでなければステップ１０１へ戻り、次のループの処理に進む。
【００２７】
ステップ１０２の処理手順の詳細を図９に従って説明する。本実施形態例では、背景技術の項で述べたベクトル化方式と命令結合方式の2方式を対象とする。
【００２８】
本実施形態例では、最内側ループを処理対象とする。ステップ９０１において、最内側ループかどうかを判定する。最内側ループかどうかはループ表２０８の子ループ欄８０３を参照し、子ループがないかどうかで判定できる。最内側ループであればステップ９０２に進み、最内側ループでなければステップ９０９へ進み、SIMD最適化対象でないと判定して処理を終了する。
【００２９】
ステップ９０２、９０３、９０４は、ベクトル化方式の条件を判定する処理である。
【００３０】
ステップ９０２では、ループ表の増分値欄８０７により、制御変数の増分が１であるかどうかを判定する。
【００３１】
ステップ９０３では、ループ運搬依存の有無を判定する。
【００３２】
ステップ９０４では、ループ本体中のコードを調べ、条件を満たすかどうかを判定する。まず、全演算およびオペランドの型が一致することを条件とする。SIMD演算で同時に扱うデータを示すSIMD並列度は通常、対象アーキテクチャにより型ごとに定義されているため、本実施形態では簡単のため、型が全て同一の場合のみを対象とする。次に、ループ内の演算がSIMD命令を持つ演算かどうかを判定する。例えば対象アーキテクチャが備えるSIMD演算命令が加算と乗算のみの場合、除算を含むループはSIMD最適化対象外とする。次にオペランドが配列参照の場合、ストライド１の連続参照であるかどうかを調べる。また、配列参照以外のオペランドはループ不変な変数であることを条件とする。
【００３３】
ステップ９０２、９０３、９０４の条件を全て満たす場合、ステップ９０５に進み、ベクトル化方式によるSIMD最適化対象であると判定して処理を終了する。
【００３４】
ステップ９０２、９０３、９０４において条件を満たさない場合にはステップ９０６に進み、命令結合方式によるSIMD最適化の条件を判定する。命令結合方式では通常、ループ本体内から、同型な演算式で配列参照などによるメモリ参照が連続参照の組を探し、SIMD結合の対象とする。例えば、’a[i]+b[i+1]+v0’と’a[i+1]+b[i+2]+v1’は結合対象である。本実施形態では簡単のため、全文が同型な場合のみを対象とする。このためステップ９０６では、ループ本体中のコードを調べ、全ての文が同型であるかどうかを調べる。同型である場合、次の条件を満たすかどうかを調べる。まず、全演算およびオペランドの型が一致すること、および全演算がSIMD命令を持つこと、配列参照以外のオペランドがループ不変であることについては、ステップ９０４の判定と同様である。配列参照については、隣接する文間でストライド１かどうかを調べる。例えば第1文がa[i]、第2文がa[i+1]、第3文がa[i+2]のような場合には、本条件を満たす。また、隣接文間で依存がないことを条件とする。
【００３５】
ステップ９０６の条件を満たす場合には、ステップ９０７へ進み、命令結合方式によるSIMD最適化対象であると判定して処理を終了する。条件を満たさない場合には、ステップ９０８へ進み、SIMD最適化対象でないと判定して処理を終了する。
【００３６】
尚、ステップ１０２のSIMD最適化対象判定は、従来技術に属する部分であり、図９の処理手順による判定は、本発明の範囲に制約を与えるものではない。例えばストライド１の配列参照以外に、構造体内の隣接メンバーのようなメモリ上で連続となる領域もSIMD結合の対象となる。また、全演算がSIMD命令対象でない場合には、SIMD化適用部分と非適用部分に分けることができるなど、図９の条件以外にもSIMD最適化が適用可能な場合がある。
【００３７】
以上で、図9およびステップ１０２の説明を終了する。
【００３８】
ステップ１０３では、コンパイラのSIMD並列度解析部２１３が、SIMD並列度を求める。対象アーキテクチャにより、各データ型に対するSIMD並列度が決まっている。例えばデータが4バイトの整数型でSIMD演算用のレジスタが16バイトの場合は、4並列である。ループ内の演算の型を調べ、その型に対する並列度を求める。
【００３９】
ステップ１０４では、コンパイラの内側データ長解析部２１２が、内側データ部を解析し、内側データ長Nと、展開用外側ループを求める。本ステップの処理手順を図４に従い詳細に説明する。
【００４０】
ステップ４０１では、内側データ長Nの初期値として1を設定し、展開用外側ループを求めるための変数UNROLLLOOPの初期値を未設定とする。
【００４１】
ステップ４０２では、現在処理対象のループがベクトル化可能かどうかを判定する。ステップ１０２（図９）の判定において、ステップ９０５でベクトル化方式によるSIMD最適化対象と判定したケースはベクトル化可能である。ベクトル化可能な場合にはステップ４０３へ進み、ベクトル方式によるSIMD化向けの処理を行う。ベクトル化可能でない場合にはステップ４１０へ進み、命令結合方式によるSIMD化向けの処理を行う。
【００４２】
ステップ４０３では、ベクトル方式対象のループに対して、OUTERLOOPに現在の処理対象の最内側ループを設定する。
【００４３】
ステップ４０４，４０５，４０６，４０７，４０８，４０９は、親ループを辿って処理を行い、展開用外側ループを外側に広げていくための処理である。
【００４４】
ステップ４０４では、OUTERLOOPの親ループがあるかどうかを判定する。本判定はループ表２０８の親ループ欄８０２により行う。親ループがあればステップ４０５へ進み、なければループを外側に辿る処理を終了し、ステップ４１２に進む。
【００４５】
ステップ４０５では、LOOPにOUTERLOOPを設定し、OUTERLOOPに現在のOUTERLOOPの親ループを設定する。
【００４６】
ステップ４０６ではLOOPのループ長を調べる。ループ長はループ表２０８のループ長欄８０８から取得できる。ループ長が定数であればその値をN1に設定し、ステップ４０７へ進む。定数でなければステップ４１２へ進む。
【００４７】
ステップ４０７では定数NとN1の積を計算し、この値が一定値以下であるかどうかを判定する。本判定に用いる一定値には、内側データ部の短データ長として妥当な値となるような上限値を選択すればよい。例えば、対象としているアーキテクチャのSIMD並列度の最大値の数倍程度の値を選択する。値が一定値以下ならばステップ４０８へ進み、そうでなければステップ４１２へ進む。
【００４８】
ステップ４０８では、SIMD化対象の各配列参照が、OUTERLOOPのイタレーション間で連続かどうかを判定する。連続かどうかは、OUTERLOOPのi回目の最後の参照とi+1回目の最初の参照が連続するかどうかを判定する。例えば、図5(a)のソースプログラム例において、OUTERLOOPがjループの場合、a[i][j][4]とa[i][j+1][0]を比較すると、aの最下位次元の要素が0から4であることから、これらの要素は連続である。連続であればステップ４０９へ進み、そうでなければステップ４１２へ進む。
【００４９】
ステップ４０９では、展開対象ループを外側に更新し、次の外側ループの処理に進む。即ち、Nの値をN*N1に更新し、UNROLLLOOPにOUTERLOOPを設定する。その後、ステップ４０４に戻り、更新したOUTERLOOPの処理を行う。
【００５０】
ステップ４１０は、命令結合方式によるSIMD化対象のループの処理である。処理対象ループ内の連続参照列を解析し、そのデータ長をN1に設定する。
【００５１】
ステップ４１１では、OUTERLOOPに現在処理対象の最内側ループを設定する。その後、ステップ４０７へ進み、ベクトル化方式対象のループと同様の処理を行う。
【００５２】
ステップ４１２では、UNROLLLOOPが未設定かどうかを判定する。
【００５３】
未設定ならば、ステップ４１３に進み、判定結果を「内側データ部なし」として処理を終了する。
【００５４】
UNROLLLOOPが設定されていれば、ステップ４１４に進み、内側データ長をN、展開用外側ループをUNROLLLOOPとして、処理を終了する。
【００５５】
以上で、図4およびステップ１０４の処理手順の説明を終了する。
【００５６】
ステップ１０５では、コンパイラのループ展開数計算部２１４が、ステップ１０４の判定結果により、内側データ部があるかどうかを調べ、あればステップ１０６に進む。内側データ部がない場合は、本発明の適用対象外であるので、ステップ１１２に進み、従来技術による通常のSIMD最適化処理を行い、本ループの処理を終了してステップ１０１に戻る。
【００５７】
ステップ１０６では、コンパイラのループ展開数計算部２１４が、ステップ１０４で求めた内側データ長Nが、SIMD並列度で割り切れるかどうかを判定する。割り切れる場合には、ステップ１１２に進み、通常のSIMD最適化処理を行い、本ループの処理を終了する。割り切れない場合にはステップ１０７へ進む。
【００５８】
ステップ１０７では、コンパイラのループ展開数計算部２１４が、内側データ部にループがあるかどうかを調べる。内側データ部は、展開用外側ループの内側であるので、図８のループ表２０８の子ループ８０３を用いて展開用外側ループに子ループがあるかどうかにより判定する。内側ループがあればステップ１０８に進み、内側ループを解消する。内側ループが多重ループの場合（展開用外側ループの子ループがさらに子ループを持つ場合）、多重ループを構成するループ全てを最内側から順に解消する。内側データ部にループがない場合には、ステップ１０９へ進む。
【００５９】
ステップ１０９では、コンパイラのループ展開数計算部２１４が、展開用外側ループのループ展開数を計算する。まず、内側データ長NをSIMD並列度で割り、その余りを「端数」とする。次に、SIMD並列度と端数の公倍数を求め、その値を端数で割った商を、展開用外側ループの展開数とする。公倍数の計算においては、最小公倍数を求めると、展開数を最小にすることができる。また単純な計算方法としては、SIMD並列度と端数の積を公倍数として採用する方法もある。
【００６０】
ステップ１１０では、ステップ１０９で求めた展開数に従い、コンパイラのループ展開変換部２１５が、展開用外側ループのループ展開処理を行う。
【００６１】
ステップ１１１では、コンパイラ２０６が、展開後の最内側ループ内のコードをSIMD化を適用したコードに変換する。以上で、１つのループの処理を終了し、ステップ１０１に戻り、次のループの処理に進む。
【００６２】
以上で、図１およびステップ３０３の処理手順の詳細の説明を終了する。
【００６３】
次に、図５(a)のソースプログラム（C言語で記述）に対して、本実施例を適用した場合の処理手順を説明する。
【００６４】
ループ番号を外側から順に1,2,3とする。各ループの情報は図８に記載されている通りである。
【００６５】
ステップ１０２のSIMD最適化対象ループの判定において、ループ１と２は最内側ループでないので、条件を満たさない。ループ３（kループ）の処理を説明する。ステップ９０２で制御変数の増分が１であることを判定し、本ループは依存を持たないためステップ９０３でループ運搬依存がないことを判定する。ステップ９０４でループ内のコードを調べる。ループ本体の文は演算を持たず、配列参照とループ不変変数v2のみである。型はint型で一致している。配列参照a[i][j][k]は最下位次元の添え字ｋがループ制御変数と一致しているため、ストライド１の連続参照である。条件を満たすので、ステップ９０５でSIMD最適化対象であると判定する。ステップ１０３において、例えば対象アーキテクチャのSIMDレジスタサイズが16バイト、int型のデータサイズが4バイト、int型に対するSIMD命令の並列度が4とすると、SIMD並列度を4に設定する。
【００６６】
ステップ１０４では、内側データ部の解析を行う。ステップ４０２で処理対象のkループはベクトル化可能であるから、ステップ４０３へ進み、OUTERLOOPにkループを設定する。ステップ４０４の判定後、ステップ４０５で、LOOPにkループを、OUTERLOOPにjループを設定する。ステップ４０６では、kループのループ長が定数5であることを判定し、ステップ４０７で、N*N1の値5が一定値以下かどうかを判定する。本実施形態においては、例えば一定値を32とすると、一定以下であると判定してステップ４０８へ進む。ステップ４０８において、配列参照a[i][j][k]がOUTERLOOP（jループ）のイタレーション間で連続かどうかを調べる。ｊループの1回目の最終参照はa[i][0][4]、jループの2回目の最初の参照はa[i][1][0]で、配列aの宣言と照らし合わせるとこれらは隣接する要素であるから、連続であると判定する。ステップ４０９では、Nに5を設定し、UNROLLLOOPにｊループを設定する。
【００６７】
ステップ４０４に戻り、OUTERLOOPの親ループを調べ、ステップ４０５でLOOPをｊループに、OUTERLOOPをiループに更新する。ｊループのループ長は3、Nとの積は15で32以下であるから、ステップ４０８へ進む。iループの1回目の最終参照はa[0][2][4]、jループの2回目の最初の参照はa[1][0][0]で、配列aの宣言と照らし合わせるとこれらは隣接する要素であるから、連続であると判定する。ステップ４０９でNを15に、UNROLLLOOPをiループに更新し、ステップ４０４に戻る。iループの親ループはないので、ステップ４１２に進み、UNROLLLOOPが設定されているので、ステップ４１４に進む。内側データ長を15、展開用外側ループをiループとして、ステップ１０４の処理を終了する。
【００６８】
ステップ１０５で内側データ部ありと判定し、ステップ１０６で、内側データ長15がSIMD並列度4で割り切れるかどうかを判定する。割り切れないので、ステップ１０７へ進む。内側データ部にはｊループとkループがあるので、ステップ１０８で内側ループを解消する。初めに内側のkループを解消した後、さらにｊループを解消する。解消後のコード例を図６(a)に示す。
【００６９】
ステップ１０９において、端数は15を4で割った余りの3となる。展開数はSIMD並列度4と端数3の最小公倍数12を端数3で割り、４とする。ステップ１１０においてiループを4倍に展開する。展開後のコード列を図６(b)に示す。
【００７０】
ステップ１１１において、SIMDコードへの変換を行う。ここでは配列aへの代入文を先頭から順に4個ずつまとめ、１つの文に変換する。変換後のコード例を図６(c)に示す。本コードにおいて、a[i][0][1:3]はaの4要素への代入を示している。また(v2,v2,v2,v2)は変数v2を4個並べた値を示している。(a[i][0][4],a[i][1][0:2])は、a[i][0][4]と、これに連続するa[i][1][0]からa[i][1][2]までの3要素の合計4要素にまとめて代入することを示す。以下同様である。
【００７１】
以上で、図５(a)のソースコード例に対する変換例の説明を終了する。
【００７２】
次に、図７(a)ソースプログラム（C言語で記述）に対して、本実施例を適用した場合の処理手順を説明する。
【００７３】
iループのループ番号を4とする。本ループの情報は図８に記載されている通りである。
【００７４】
ステップ１０２のSIMD最適化対象ループの判定において、ステップ９０２で制御変数の増分が１であることを判定し、本ループは依存を持たないためステップ９０３でループ運搬依存がないことを判定する。ステップ９０４の判定において、配列参照a[i][0]はストライド1でないので、条件を満たさず、ステップ９０６へ進む。
【００７５】
ステップ９０６では、ループ内の3個の文を比較し、各文とも左辺が配列参照、右辺が変数であるので、同型であると判定する。型は全てdouble型で一致する。配列参照に着目すると、3個の文の参照が連続している。これらの判定からステップ９０６の条件を満たすと判定し、ステップ９０７で命令結合方式によるSIMD最適化対象とする。
【００７６】
ステップ１０３において、double型に対するSIMD命令の並列度が2とすると、SIMD並列度を2に設定する。
【００７７】
ステップ１０４では、内側データ部の解析を行う。ステップ４０２で処理対象のiループはベクトル化可能でないからステップ４１０に進み、処理対象ループ中の連続参照列を調べる。本ループの参照列は、a[i][0],a[i][1],a[i][2]であるので、データ長N1に3を設定する。ステップ４１１では、iループをOUTERLOOPに設定する。
【００７８】
ステップ４０７に進み、N*N1は3であるので、一定以下と判定する。
【００７９】
ステップ４０８において、iループのイタレーション間の連続性を調べる。iループの1回目における配列aの参照列の最後のデータはa[0][2]である。2回目の最初のデータはa[1][0]である。配列aの宣言と照らし合わせるとこれらは隣接する要素であるから、連続であると判定する。
【００８０】
ステップ４０９では、Nに3を設定し、UNROLLLOOPにiループを設定する。
【００８１】
ステップ４０４に戻り、iループの親ループはないので、ステップ４１２に進み、UNROLLLOOPが設定されているので、ステップ４１４に進む。内側データ長を3、展開用外側ループをiループとして、ステップ１０４の処理を終了する。
【００８２】
ステップ１０５で内側データ部ありと判定し、ステップ１０６で、内側データ長3がSIMD並列度2で割り切れるかどうかを判定する。割り切れないので、ステップ１０７へ進む。内側データ部にループはないので、ステップ１０９に進む。
【００８３】
ステップ１０９において、端数は3を2で割った余りの1となる。展開数はSIMD並列度2と端数1の最小公倍数2を端数1で割り、2とする。ステップ１１０においてiループを2倍に展開する。展開後のコード列を図７（ｂ)に示す。
【００８４】
ステップ１１１において、SIMDコードへの変換を行う。ここでは配列aへの代入文を先頭から順に2個ずつまとめ、１つの文に変換する。変換後のコード例を図７(c)に示す。
【００８５】
以上で、図７(a)のソースコード例に対する変換例の説明を終了する。
【産業上の利用可能性】
【００８６】
本発明のコード生成方法は、複数データに対するメモリアクセスや演算を行うSIMD命令を備えたターゲットマシンに対するコード生成を行うコンパイラにおいて利用することができる。
【図面の簡単な説明】
【００８７】
【図１】本発明の実施形態によるSIMD最適化の処理手順を示す図である。
【図２】本発明の実施形態によるコンパイラが稼動する計算機システムの構成図である。
【図３】本発明の実施形態のコンパイラの処理手順の例を示す。
【図４】本発明の実施形態によるSIMD最適化において、内側データ部およびデータ長を解析する処理手順を示す図である。
【図５】ソースプログラムの例および、従来技術によるSIMD最適化の変換例を示す。
【図６】本発明によるコード変換過程の一例を示す。
【図７】ソースプログラムの例と、従来技術および本発明によるコード変換の一例を示す。
【図８】本実施形態のループ表の一例である。
【図９】本発明の実施形態によるSIMD最適化において、SIMD最適化対象ループの判定を行う処理手順を示す図である。
【符号の説明】
【００８８】
204・・・主記憶装置、206・・・コンパイラ、207・・・中間コード、208・・・ループ表、209・・・ソースプログラム、211・・・SIMD最適化部、212・・・内側データ長解析部、213・・・SIMD並列度解析部、214・・・ループ展開数計算部、215・・・ループ展開変換部
【図１】
0005227646.tif 000002
【図２】
0005227646.tif 000003
【図３】
0005227646.tif 000004
【図４】
0005227646.tif 000005
【図５】
0005227646.tif 000006
【図６】
0005227646.tif 000007
【図７】
0005227646.tif 000008
【図８】
0005227646.tif 000009
【図９】
0005227646.tif 000010