(57)【要約】【課題】一括ロード・ストア命令を使用する場合、ループ繰り返しの際の動的アライメント計算回数を削減する。【解決手段】  ソースプログラム又は中間コードから、メモリ上の複数データに対して、アドレス境界の制約に応じたアクセスをするメモリアクセス命令を含むコードを生成する際、アドレス境界までのオフセットパターン数及びアドレス境界までのオフセット計算の挿入位置を決定し、アドレス境界までのオフセットパターン回数分、最内側ループの１つ外側のループを展開し、展開した各ループにアドレス境界を考慮したコード変換を行う。【選択図】  図９
2014137657.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラム又は中間コードから、メモリ上の複数データに対して、アドレス境界の制約に応じたアクセスをするメモリアクセス命令を含むコードを生成するコード生成方法であって、
計算機が、
前記アドレス境界までのオフセットパターン数を決定するステップと、
前記アドレス境界までのオフセット計算の挿入位置を決定するステップと、
前記アドレス境界までのオフセットパターン回数分、最内側ループの１つ外側のループを展開するステップと、
展開した各ループに前記アドレス境界を考慮したコード変換を行うステップと
を含む、コード生成方法。
【請求項２】
請求項１に記載のコード生成方法であって、前記アドレス境界までのオフセットパターン数を決定するステップは、配列参照の、最内側ループの１つ外側のループ繰り返しごとの参照位置の変化量を利用して求めるステップを含む、コード生成方法。
【請求項３】
請求項１に記載のコード生成方法であって、前記アドレス境界までのオフセット計算の挿入位置を決定するステップは、配列参照の、最内側ループよりも外側のループ繰り返しごとの参照位置の変化量を利用して求めるステップを含む、コード生成方法。
【請求項４】
請求項１に記載のコードの生成方法であって、展開した各ループに前記アドレスの境界を考慮したコード変換を行うステップは、最内側ループの１つ外側のループ繰返し毎のオフセット変化量を求めるコードを、前記アドレス境界までのオフセット計算の挿入位置に挿入するステップと、
配列初回参照から前記アドレス境界までのオフセットを求めるコードを、前記アドレス境界までのオフセット計算挿入位置へ挿入するステップと、
前記アドレス境界までのオフセットパターン毎に、アドレス境界に合うまでのループ実行回数計算コードを前記アドレス境界までのオフセット計算の挿入位置に挿入するステップと、
展開後の各最内側ループの直前に、前記アドレス境界までのオフセットパターン毎に、アドレス境界に合うまでループ実行を行うコードを挿入するステップと
を含むコード生成方法。
【請求項５】
請求項４に記載のコード生成方法であって、
複数のアドレス境界までのオフセット計算対象がある場合、基準配列参照と、その他の配列参照の初回参照オフセットとを比較するコードを挿入するステップと、
前記基準配列参照と、その他の配列参照のループ繰返しに対するストライドオフセットと、を比較するコードを挿入するステップと、
前記比較の結果がすべて等しい場合に実行するブロックに、前記配列初回参照から前記アドレス境界までのオフセットを求めるコードを挿入するステップと、
前記比較の結果が異なる場合に実行するブロックに、元のソースコードを挿入するステップと
を含むコード生成方法。
【請求項６】
ソースプログラム又は中間コードから、メモリ上の複数データに対して、アドレス境界の制約に応じてアクセスするメモリアクセス命令を用いたコード生成を計算機に実行させるコンパイラであって、
前記アドレス境界までのオフセットパターン数を決定させるステップと、
前記アドレス境界までのオフセット計算の挿入位置を決定させるステップと、
前記アドレス境界までのオフセットパターン回数分、最内側ループの１つ外側のループを展開させるステップと、
展開された各ループに前記アドレス境界を考慮したコード変換を実行させるステップと
を計算機に実行させるコンパイラ。
【請求項７】
請求項６に記載のコンパイラであって、
前記アドレス境界までのオフセットパターン数を決定させるステップで、配列参照の、最内側ループの１つ外側のループ繰り返しごとの参照位置の変化量を利用して求めさせるステップを計算機に実行させるコンパイラ。
【請求項８】
請求項６に記載のコンパイラであって、
前記アドレス境界までのオフセット計算の挿入位置を決定させるステップで、配列参照の、最内側ループよりも外側のループ繰り返しごとの参照位置の変化量を利用して求めさせるステップを計算機に実行させるコンパイラ。
【請求項９】
請求項６に記載のコンパイラであって、
前記展開された各ループに前記アドレスの境界を考慮したコード変換を実行させるステップで、
最内側ループの１つ外側のループ繰返し毎のオフセット変化量を求めるコードを、前記アドレス境界までのオフセット計算の挿入位置に挿入させるステップと、
配列初回参照から前記アドレス境界までのオフセットを求めるコードを、前記アドレス境界までのオフセット計算挿入位置へ挿入させるステップと、
前記アドレス境界までのオフセットパターン毎に、アドレス境界に合うまでのループ実行回数計算コードを前記アドレス境界までのオフセット計算の挿入位置に挿入させるステップと、
展開後の各最内側ループの直前に、前記アドレス境界までのオフセットパターン毎に、アドレス境界に合うまでループ実行を行うコードを挿入させるステップと
を計算機に実行させるコンパイラ。
【請求項１０】
請求項９に記載のコンパイラであって、
複数のアドレス境界までのオフセット計算対象がある場合、基準配列参照と、その他の配列参照の初回参照オフセットとを比較するコードを挿入させるステップと、
前記基準配列参照と、その他の配列参照のループ繰返しに対するストライドオフセットと、を比較するコードを挿入させるステップと、
前記比較の結果がすべて等しい場合に実行するブロックに、前記配列初回参照から前記アドレス境界までのオフセットを求めるコードを挿入させるステップと、
前記比較の結果が異なる場合に実行するブロックに、元のソースコードを挿入させるステップと
を計算機に実行させるコンパイラ。
【請求項１１】
ソースプログラム又は中間コードから、メモリ上の複数データに対して、アドレス境界の制約に応じたアクセスをするメモリアクセス命令を用いたコードを生成する計算機であって、
前記計算機の制御部が、
前記アドレス境界までのオフセットパターン数を決定し、
前記アドレス境界までのオフセット計算の挿入位置を決定し、
前記アドレス境界までのオフセットパターン回数分、最内側ループの１つ外側のループを展開し、
展開した各ループに前記アドレス境界を考慮したコード変換を実行する
計算機。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コード生成方法、コンパイラ及び計算機に係り、特に、複数データに対するメモリアクセスを行う命令を用いたコード生成方法、コンパイラ技術及び計算機に関する。
【背景技術】
【０００２】
１つのレジスタ上に複数のデータを保持し、その複数データに対して並列演算を実行できる命令を有するアーキテクチャが一般的になってきている。例えば、非特許文献２に記載されているマルチメディア命令拡張ＳＳＥでは、１６バイトのレジスタを用いて複数のデータを一括して扱うことができるようになっている。４バイトの単精度浮動小数点データの場合、４個のデータに対する演算を１つのレジスタ上で並列に実行することができる。このような命令をＳＩＭＤ（Single Instruction Multiple Data）命令と呼び、ＳＩＭＤ命令を用いたコード生成を行う最適化をＳＩＭＤ最適化と呼ぶ。
【０００３】
レジスタ上で並列に演算を実行する方法として、複数のデータを１個のレジスタに載せる際、メモリ上に連続的に配置されているデータ（配列等を含む）を対象とする場合には、複数のデータを一括してロードする方法がある。逆に、１個のレジスタ上の複数データを、一括してメモリ上にストアする方法もある。
【０００４】
図２０に示すソースコード８００の例では、最内側ループ制御変数の増分値が「１」で、最内側ループの制御変数が配列Ａの連続次元（１次元目）の添字となっている。よって、配列Ａは、ストライド１の連続参照であり、一括ロード・ストアの対象となる。配列Ａの型はｆｌｏａｔ型で、データサイズが４バイトであり、レジスタサイズが１６バイトとすると、一括ロード・ストア命令によって、４個のデータに対し、同時にアクセス可能である。このような時、ＳＩＭＤ並列度は「４」であるという。なお、ストライドとは、ループを１回繰り返すごとに変化する配列要素のアクセス幅である。
【０００５】
図２１に、ソースコード８００をＳＩＭＤ化した後の変換後コード８１０のイメージを示す。ｊループに対して、４倍のループ展開を適用し、配列Ａの１次元目の添字を「ｊ：ｊ＋３」に変更している。「ｊ：ｊ＋３」は、ｊ、ｊ＋１、ｊ＋２、ｊ＋３の４要素のアクセスを示す記法とする。このように、ＳＩＭＤ化対象のループ内では、元の４個の文に相当する処理が１文で行われるようになる。
なお、ループ長がＳＩＭＤ並列度の倍数になっていない場合には、余りの繰返しをＳＩＭＤループ後に実行する必要があることから、元のソースコードをＳＩＭＤループの後に挿入する必要がある。
【０００６】
一括ロード・ストア命令は、アクセスするメモリアドレスがアクセスサイズの倍数となる制約を持つことが多い。例えば、前述のＳＳＥにおいても、アドレスが１６バイト境界の場合のみ利用できる一括ロード・ストア命令がある。アドレスが制約を満たさないデータに対しては、境界制約を満たさないデータに対して用いる一括ロード・ストア命令を使用する。境界制約を満たすデータに対して用いる一括ロード・ストア命令の方が高速に実行されるのが一般的である。境界制約を満たさないデータに対して用いる一括ロード・ストア命令が無いアーキテクチャでは、各データを個別にレジスタにロードしてから、レジスタ上のデータ操作により複数データの組を１個のレジスタ上に生成する場合もある。
【０００７】
また、一括ロード・ストア命令を命令セットに持つ他の例として、非特許文献１には、ＶＳＸ（Vector Scalar eXtension）が開示されている。ＶＳＸでは、アドレスが１６バイト境界を満たさない状況で一括ロード・ストア命令を使用し続けると、性能劣化が発生する。
【０００８】
上述のように、一括ロード・ストア命令を使用する場合、対象データの先頭アドレスを意識する必要がある。
アクセス対象のデータのアドレスがコンパイル時に不明な場合、動的にアドレス計算を行い、対象データの先頭アドレスが境界条件を満たさない場合は、非ＳＩＭＤ演算を実行し、逆に先頭アドレスが境界条件を満たしている場合は、ＳＩＭＤ演算を実行する方法がある。この方法について、上述したソースプログラム８００（図２０）及び変換後コード８１０（図２１）を例に説明する。
【０００９】
非特許文献１の（特に、）１３５頁〜１３８頁には、マルチバージョン化の例が開示されている。マルチバージョン化では、非ＳＩＭＤコードとＳＩＭＤコードを用意し、動的に初回参照アドレスのアライン境界オフセットを計算した後、いずれかのコードを実行するようになっている。
【００１０】
図２０のソースコード８００に対するマルチバージョン化コード８１０の例を図２１に示す。レジスタサイズ、アラインサイズは１６バイトとする。図２１のコードは、iループの制御変数が更新されるごとに、配列初回参照アドレスの１６バイトオフセットを計算させ、オフセットが「０」になっているか、すなわち、１６バイト境界に合っているか否かを演算装置に判定させるように記述されている。判定の結果、１６バイト境界に合っていない場合、ｉｆブロック中の非ＳＩＭＤコード８１１を実行させるようになっている。逆に、１６バイト境界に合っている場合、ｅｌｓｅブロック中のＳＩＭＤコード８１２を実行させるようになっている。
このように、マルチバージョン化コードにより、アラインサイズ境界に合っていない場合の一括ロード・ストアを防ぐことができる。
【００１１】
また、非特許文献１の１３８頁〜１４１頁には、動的ピーリングの例が開示されている。動的ピーリングでは、動的に初回参照アドレスのアライン境界オフセットを計算した後、アライン境界に合うまで非ＳＩＭＤ演算を実行し、その後、アライン境界に合った状態からＳＩＭＤ演算を行う方式である。
【００１２】
図２２に、ソースコード８００に対する動的ピーリングコード８３０の例を示す。また、メモリアクセスの様子を図２３に模式的に示す。レジスタサイズ、アラインサイズは１６バイトとする。図２２の８３１では、iループの制御変数が更新される度に、配列初回参照アドレスの１６バイトオフセットが演算部に計算されるように記述されている。８３２のコード(ｉｆ文条件式中)では、８３１で求めたオフセットが「０」であるか否か、即ち１６バイト境界に合っているか否かを判定させるようになっている。１６バイト境界に合っていない場合、ｉｆブロック中で、１６バイト境界に合うまでに必要なループ実行回数（「ピーリング回数」と呼ぶ。）を求める（８３３）。そして、８３３で求めた回数だけ、非ＳＩＭＤコードを実行させる（８３４）。その後、１６バイト境界に合った状態から、ＳＩＭＤコードを実行させる（８３５）。
【００１３】
図２３を用いて、図２２に示した動的ピーリングコード８３０のメモリアクセスの様子を説明する。図２３の１マスは４バイトとする。また、マスの中の数字は配列Ａの１次元目の添字を表すものとする。８５１は、ｉが「１」、ｊが「２」の時のアドレスである。図に示すように、ｉが「１」の時の初回参照位置は、１６バイト境界から１要素だけずれた位置であるため、１６バイト境界に合うのは、ｊループを３回実行した後である。この「３回」が、図２２の８３３で求めている値である。ループを３回実行した後は、４要素ずつ一括ロード（ストア）を行うため、毎回一括ロード（ストア）対象データの先頭アドレスは１６バイト境界に合った状態になることとなる。
【００１４】
動的ピーリングにより、アラインサイズ境界に合っていない場合の一括ロード・ストアを防ぐことができる。また、初回参照がアラインサイズ境界に合っていない場合でも、アラインサイズ境界に合わせた後にＳＩＭＤ化を行うことができる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】ＩＢＭ“Ｐｏｗｅｒ  ＩＳＡ  Ｖｅｒｓｉｏｎ  ２．０６Ｒｅｖｉｓｉｏｎ  Ｂ“、[online]、２０１０年７月２３日、[平成２４年１０月１日検索]、インターネット(https://www.power.org/wpcontent/uploads/2012/07/PowerISA_V2.06B_V2_PUBLIC.pdf)
【非特許文献２】Ａａｒｔ  Ｊ.Ｃ.Ｂｉｋ、“Ｔｈｅ  Ｓｏｆｔｗａｒｅ  ＶｅｃｔｏｒｉｚａｔｉｏｎＨａｎｄｂｏｏｋ”、Ｉｎｔｅｌ  Ｐｒｅｓｓ、[online]、２００４年、[平成２４年１０月１日検索]、インターネット（http://www.intel.com/intelpress/excerpts/excerpt_vmmx3.pdf）
【発明の概要】
【発明が解決しようとする課題】
【００１６】
上述のように、一括ロード・ストア命令を使用する場合、対象データの先頭アドレスがアライン境界に合っているか否かを意識する必要がある。動的に初回参照アドレスのアライン境界オフセットを計算し、アライン境界に合っている時若しくはアライン境界に合わせた後、一括ロード・ストア命令を使用する方法が提案されているが、多重ループの場合、外側ループ繰り返し毎に、初回参照アドレスのアライン境界オフセットを計算し直す必要があることから、これがオーバーヘッドの増加原因になるという問題がある。
【００１７】
また、アラインメントには規則性があり冗長な計算となっている。図２４に、ソースコード８００（図２０）における、外側ループ繰り返し毎の配列Ａの初回参照の様子を模式的に示す。外側ループを制御しているｉの値が「１」の時、初回参照は１６バイト境界から１要素だけずれた状態になる(Ｓ９０１)。ソースコード８００において、ｉループは配列Ａの２次元目を制御させており、配列Ａの１次元目の要素数は「１０１」であることから、ｉループ繰り返し毎に、初回参照位置は１要素だけずれることになる。従って、外側ループを制御しているｉの値が「２」の時は、初回参照は１６バイト境界から２要素だけずれた状態になる（Ｓ９０３）。
【００１８】
同様に、ｉの値が「３」の時、初回参照は１６バイト境界から３要素だけずれた状態になり（Ｓ９０５）、ｉの値が「４」の時は、１６バイト境界に合っている状態になる（Ｓ９０７）。ｉの値が「５」以上の時も、初回参照が１要素ずつずれていく状態を繰り返す。つまり、アラインメントのパターンはＳ９０１〜Ｓ９０７の４通りしか存在しないといえる。従って、ｉループ繰り返しの度に初回参照を計算することは、冗長であるという問題がある。本発明の主な課題の１つは、動的アラインメント計算回数を削減することである。
【課題を解決するための手段】
【００１９】
本発明の代表的な一形態は、対象ループを解析して、アラインパターン数を決定する手段と、アライン計算挿入位置を決定する手段と、最内側ループの親ループをアラインパターン回展開する手段と、展開した各ループにアラインを考慮したコード変換を行う手段から成る。
【００２０】
アラインを考慮したコード変換にピーリングを採用する場合、最内側ループの親ループ繰り返しごとのオフセット変化量を求めるコードを、前記で求めたアライン計算挿入位置へ挿入する手段と、配列初回参照からアライン境界までのオフセットを求めるコードを、前記で求めたアライン計算挿入位置へ挿入する手段と、アラインパターンごとのピーリング回数計算コードを前記で求めたアライン計算挿入位置へ挿入する手段と、展開後の各最内側ループの直前に、前記で求めたアラインパターンごとのピーリング回数分ピーリングを行うコードを挿入する手段を含む。
【発明の効果】
【００２１】
本発明によれば、一括ロード・ストア対象のデータのアドレスがコンパイル時に不明である場合の動的アラインメント計算回数が削減され、演算装置の実行性能が向上するという効果を奏する。
【図面の簡単な説明】
【００２２】
【図１】本発明を適用した、一実施の形態であるコンパイラを実行する計算機の構成例を示したブロック図である。
【図２】本実施形態のループ表を示す模式図である。
【図３】本実施形態の配列表を示す模式図である。
【図４】本実施形態の配列参照表を示す模式図である。
【図５】本実施形態におけるコンパイル処理の全体概要処理を示すフロー図である。
【図６】本実施形態におけるＳＩＭＤ最適化処理の流れを示すフロー図である。
【図７】本実施形態におけるアライメント計算付きＳＩＭＤ変換処理の流れを示すフロー図である。
【図８】本実施形態における動的配列参照情報利用コード変換処理の流れを示すフロー図である。
【図９】本実施形態における単一アライメント向きコード変換処理の流れを示すフロー図である。
【図１０】本実施形態における単一アライメント向きコード変換処理で用いるソースプログラムの例を示す図である。
【図１１】本実施形態における単一アライメント向きコード変換処理で変換された変換後のコード例を示す図である。
【図１２】本実施形態における単一アライメント向きコード変換処理の一事例で利用するソースプログラムの例を示す図である。
【図１３】本実施形態における単一アライメント向きコード変換処理の一事例の処理の様を示す模式図である。
【図１４】本実施形態における単一アライメント向きコード変換処理の一事例で変換した後の変換後コードの例を示す図である。
【図１５】本実施形態における単一アライメント向きコード変換処理の他の事例で利用するソースプログラムの例を示す図である。
【図１６】本実施形態における単一アライメント向きコード変換処理の他の事例の処理の様を示す模式図である。
【図１７】本実施形態における単一アライメント向きコード変換処理の他の事例で変換した後の変換後コードの例を示す図である。
【図１８】本発明の実施形態による複数アラインメント向きコード変換処理の流れを示すフロー図である。
【図１９】本発明の実施形態による複数アラインメント向きコード変換処理によって変換された後の変換後コードの例を示す図である。
【図２０】従来技術におけるソースプログラム例を示す図である。
【図２１】従来技術におけるマルチバージョン化コードの例を示す図である。
【図２２】従来技術における動的ピーリングコードの例を示す図である。
【図２３】従来技術の処理の様を示す模式図である。
【図２４】従来技術の課題を示す模式図である。
【発明を実施するための形態】
【００２３】
以下、図面を用いて本発明を実施するための形態を詳細に説明する。
本発明を適用した一実施形態であるコンパイラの例は、アラインメントを意識する必要があるアーキテクチャにおいて、複数データに対するメモリアクセスを行う場合に有用な技術である。以下の説明では、ＳＩＭＤ最適化を例に説明するが、本発明はこれに限定はするものではなく種々の処理に適用することができる。また、本実施形態ではアラインメント計算付きコード変換の例として、ピーリングを採用しているが、バージョニングや、その他のループ変換技術を利用することも可能である。
【００２４】
また、本実施形態では、配列要素のアドレスを取得する部分があるが、配列要素のアドレスは、要素サイズ境界に合っていることを前提とする。つまり、配列要素が４バイトデータの場合、必ずアドレスは４の倍数になっている。これは一般的な前提である。
【００２５】
図１に、本発明を適用した第１実施形態であるコンパイラが稼働する計算機１の構成を模式的に示す。計算機１は、汎用のサーバ装置等であり、ＣＰＵ２、主記憶装置３、ＨＤＤやＳＳＤ等から構成される補助記憶としての外部記憶装置４、ディスプレイ等の出力装置５及びキーボード、マウス並びにタッチパネル等の入力装置６を備える。入力装置６を介して、ユーザからのコンパイラ起動命令を受け付け、コンパイラ終了メッセージやエラーメッセージが、出力装置５に出力されるようになっている。主記憶装置３には、ＣＰＵ２と、プログラムとの協働により、コンパイラ１０が実現され、コンパイル過程で必要になる中間コード１１、ループ表１２、配列表１３及び配列参照表１４が保持される。外部記憶装置４には、ソースプログラム２０とオブジェクトプログラム２１が格納される。
【００２６】
図２に、ループ表１２の一例を模式的に示す。ループ表１２には、ループ番号１２１、親ループ１２２、子ループ１２３、制御変数１２４、下限値１２５、上限値１２６、増分値１２７及びループ長１２８の各項目欄が設けられ、これらに対する値が対応付けられて格納されるようになっている。
【００２７】
ループ番号１２１には、コンパイラ１０内でループを識別するための番号が格納される。親ループ１２２には、対象ループを取り囲む外側ループのうち、最も内側のループのループ番号が登録される。なお、対象ループが最も外側のループである場合、「なし」が登録される。子ループ１２３には、対象ループの内側ループのうち、最も外側のループのループ番号が登録される。なお、対象ループが最も内側のループである場合、「なし」が登録されるようになっている。また、上記内側ループが複数ある場合には、全て登録されるようになっている。制御変数１２４には、対象ループの繰返しを制御するループ制御変数が登録される。下限値１２５、上限値１２６、増分値１２７には、夫々制御変数１２４の下限値、上限値及び繰返し毎の増分値が登録される。ループ長１２８は、ループの繰返し回数が登録される。
【００２８】
図３に、配列表１３の一例を示す。配列表１３には、配列名１３１、静的アドレス１３２、型１３３、次元数１３４、次元１３５、添字範囲１３６及びサイズ１３７の各項目が設けられ、各項目に対する値が対応付けられて格納されるようになっている。各値は、コンパイラ１０によって、ソースプログラム２０に定義されている各配列変数の宣言文から抽出されるようになっている。なお、ソースプログラム２０が、宣言のないプログラミング言語で記述されている場合、コンパイラ２０によって、ループ実行文中の配列変数から抽出されるようになっている。
【００２９】
配列名１３１には、配列変数の変数名が登録される。例えば、添字部分を除いた変数が格納される。静的アドレス１３２には、静的に配列の先頭アドレスが判明できるか否かを示す情報が登録される。静的にアドレスが判明できる場合、「ＴＲＵＥ」、静的にアドレスが不明な場合は「ＦＡＬＳＥ」が登録される。静的に配列の先頭アドレスが判明できる例としては、配列がローカル変数として宣言されている場合等がある。他方、静的に配列の先頭アドレスが不明な例としては、配列が関数の仮引数として宣言されている場合等がある。型１３３には、配列変数のデータ型が登録される。次元数１３４には、配列変数の添字の次元数が登録される。例えば、宣言文中に「Ａ［ＩＮＵＭ，ＮＵＭ］」がある場合、次元数１３４は「２」である。本実施形態では、配列は右側が連続次元とし最右側から１次元目、２次元目、…と呼ぶものとする。コンパイラ１０は、次元の個数分、「１」から順番に次元番号を次元１３５に登録するようになっている。
【００３０】
添字範囲１３６及びサイズ１３７には、次元１３５毎の添字範囲と、サイズの情報とが登録される。本実施形態では、添字は「１」から始まるものとする。例えば、宣言文中に「Ａ［ＩＮＵＭ，ＮＵＭ］」がある場合、１次元目のサイズは「ＮＵＭ」であり、コンパイラ１０によって、これがサイズ１３７に登録されるようになっている。また、コンパイラ１０によって、添字範囲１３６には、「１：ＮＵＭ」が登録される。また、２次元目のサイズは「ＩＮＵＭ」であり、コンパイラ１０によって、これがサイズ１３７に登録される。添字範囲１３６には、コンパイラ１０によって「１：ＩＮＵＭ」が登録される。
【００３１】
図４に、配列参照表１４の一例を模式的に示す。配列参照表１４は、コンパイラ１０の構文解析処理（Ｓ１０１）によって抽出されたループ処理毎に生成される。配列参照表１４には、配列名１４１、配列参照形式１４２及び初回参照の静的判明１４３の各項目が設けられ、これらに対する値が対応付けられて登録されるようになっている。各値は、コンパイラ１０の構文解析処理（Ｓ１０１）において、ループ処理の中で配列参照が検出されると、配列参照表１４に登録されるようになっている。
配列名１４１には、配列表１３の説明で述べたのと同様に、配列変数の変数名が登録される。配列参照形式１４２には、ループ制御変数も含めた配列参照形式が登録される。例えば、ループ中で制御変数ｉ，ｊによって「Ａ［i，j］」と参照されている場合、Ａ［i，j］が配列参照形式１４２に登録される。初回参照の静的判明１４３には、静的に配列の初回参照アドレスが判明できるか否かを示す情報が登録される。例えば、静的に配列の初回参照アドレスが判明できる場合には「ＴＲＵＥ」が、不明な場合には「ＦＡＬＳＥ」が、コンパイラ１０によって登録されるようになっている。なお、配列が静的に配置されており、初回参照位置も静的に分かる場合、静的に配列の初回参照アドレスが判明できる。つまり、静的に配列の初回参照アドレスが判明できるのは、配列名１４１が登録されている配列表１４のエントリの静的アドレス１３２が「ＴＲＵＥ」で、配列参照表１４における配列参照形式１４２の添字式にループ制御変数以外の変数を含まない状態であり且つ配列参照を制御している制御変数が登録されているループ表１２のエントリの下限値１２５が、全て定数の状態にある場合である。
【００３２】
次に、計算機１の処理の流れについて説明する。
図５に、コンパイラ１０の全体処理の概要を示す。
Ｓ１０１で、コンパイラ１０は、ソースプログラム２０を入力として構文解析処理を実行し、中間コード１１、ループ表１２、配列表１３及び配列参照表１４を出力する。以下のコンパイル処理では、中間コード１１を対象に変換を行う。構文解析の方法や中間コード生成の方法については、公知の方法を利用できる。
【００３３】
Ｓ１０３で、コンパイラ１０は、ＳＩＭＤ最適化処理を実行する。本処理では、本実施形態の特徴の１つである「アライメントを考慮したコード変換処理」が含まれる。詳細は後述する。
Ｓ１０５で、コンパイラ１０は、レジスタ割付処理を実行し、その後、Ｓ１０７でコード生成処理を実行し、中間コード１１をオブジェクトプログラム２１に変換して出力する。なお、レジスタ割付処理やコード生成処理に関しては、種々の公知の方法によって実行する。
【００３４】
図６に、ＳＩＭＤ最適化処理（図５のＳ１０３）の詳細な処理の流れを示す。なお、本ＳＩＭＤ最適化処理はループを処理単位として実施する。
Ｓ２０１で、コンパイラ１０は、未処理のループがあるか否かを判定し、未処理のループがある場合（Ｓ201：Yes）、Ｓ２０２に進む。未処理のループが無い場合（S201：No）本処理を終了する。
Ｓ２０３で、コンパイラ１０は、ＳＩＭＤ最適化対象のループであるか否かを判定する。対象ループで無い場合（S203:No）、Ｓ２０１に戻る。対象ループである場合（S203：Yes）、Ｓ２０５に進む。
【００３５】
ここで、コンパイラ１０は、次の６つの条件を満たす場合に、ＳＩＭＤ最適化の対象ループであると判例するようになっている。
（１）最内側ループである。
（２）ループ内の全演算及びオペランドの型が一致する。
（３）ループ内の演算がＳＩＭＤ命令をもっている。
（４）ループ内のオペランドが配列参照の場合に、ストライド１の連続参照である。
（５）ループ内の配列参照以外のオペランドが、ループ不変な定数・変数である。
（６）ループの繰り返しに跨るデータ依存がない。
なお、これらの条件は例示であり、種々の条件が適用可能である。例えば、全演算がＳＩＭＤ命令対象でない場合には、ＳＩＭＤ化適用部分と非適用部分に分けることができるなど、上述の条件以外にも、ＳＩＭＤ最適化が適用可能な場合がある。
【００３６】
Ｓ２０５で、コンパイラ１０は、ＳＩＭＤ並列度を求める。なお、対象アーキテクチャにより、各データ型に対するＳＩＭＤ並列度は決まっている。例えば、データが４バイトでＳＩＭＤ演算用のレジスタが１６バイトの場合、一度に４個のデータを処理できるため４並列である。ループ内の演算の型を調べ、その型に対する並列度を求める。
【００３７】
Ｓ２０７で、コンパイラ１０は、一括ロード・ストア対象の配列参照があるか否かを調べる。これは、配列参照表１４（図４）の１次元目の制御変数が、ループ表１２において、最内側ループの制御変数となっている配列参照があるか否かを調べるようにして行う。一括ロード・ストア対象の配列参照がある場合（S207:Yes）、Ｓ２０９に進み、「アラインメント計算付きＳＩＭＤコード変換」を行う。本処理の内容は、後述する。一括ロード・ストア対象の配列参照がない場合（S207:No）、Ｓ２１１に進み、通常のＳＩＭＤコード変換を実行し、Ｓ２０１に戻る。
【００３８】
図７に、「アラインメント計算付きＳＩＭＤコード変換（図６のＳ２０９）」の詳細な処理の流れを示す。
Ｓ３０１で、コンパイラ１０は、ループが１重ループであるか否かを判定する。１重ループである場合（S301:Yes）、Ｓ３０３に進み、従来のアラインメント計算付きＳＩＭＤコード変換を行い、処理を終了する。従来のアラインメント計算付きＳＩＭＤコード変換については、背景技術で説明済である。
１重ループでない場合（S301:No.）、Ｓ３０５に進む。
【００３９】
Ｓ３０５で、コンパイラ１０は、初回参照アドレスが不明な一括ロード・ストア対象の配列参照があるか否かを判定する。この判定は、配列参照表１４（図４）において、初回参照の静的判明１４３に「ＦＡＬＳＥ」が登録されている一括ロード・ストア対象の配列参照があるか否かを調べることにより行う。一括ロード・ストアの調べ方については、図６のＳ２０７（図６）と同様である。
初回参照アドレスが不明な一括ロード・ストア対象の配列参照がある場合（S305:Yes）、Ｓ３０７に進む。初回参照アドレスが不明な一括ロード・ストア対象の配列参照がない場合（S305:No.）、Ｓ３０９に進む。
【００４０】
Ｓ３０７で、コンパイラ１０は、「動的配列参照情報利用コード変換」の処理を行う。本処理の詳細な説明は、後述する。
Ｓ３０９で、コンパイラ１０は、「静的配列参照情報利用コード変換」の処理を行い、処理を終了する。
【００４１】
図８に、「動的配列参照情報利用コード変換」の詳細な処理の流れを示す。
Ｓ４０１で、コンパイラ１０は、一括ロード・ストア対象の配列参照が複数あるか否かを判定する。配列参照表１４に複数の一括ロード・ストア対象の配列参照が登録されているかどうかを調べることにより行う。なお、一括ロード・ストアの調べ方は、図６のＳ２０７と同様である。
一括ロード・ストア対象の配列参照が複数ある場合（S401:Yes）、Ｓ４０３に進む。一括ロード・ストア対象の配列参照が１つの場合（S401:No.）、本配列参照を基準配列参照としてＳ４０５に進み、「単一アラインメント向けコード変換」を行い、処理を終了する。なお、「単一アラインメント向けコード変換」の詳細な処理は後述する。
【００４２】
Ｓ４０３で、複数の一括ロード・ストア対象配列参照間で、ループ繰り返し中、常にアラインメントの状況が等しいかどうかを調べる。即ち各一括ロード・ストア対象の配列参照に対して、『１．配列初回参照アドレスのオフセットが等しい』か否か、『２：ループ繰り返しごとのオフセット変化量が等しい』か否か、を判定する。オフセットはアライン境界からのオフセットを示す。
【００４３】
ここで、『１．配列初回参照アドレスのオフセットが等しい』とは、例えば、関数の引数として配列を渡しているソースコードがある場合、配列の先頭アドレスは不明であり、配列表１４の静的アドレス１３２には「ＦＡＬＳＥ」が登録されるが、コンパイル時のオプションやソース中の指示文などによりコンパイラ１０に配列先頭アドレスのオフセット情報を明示できる場合や、配列の添字式が等しい配列参照はオフセットが等しいとみなす場合には、配列初回参照アドレスのオフセットが等しいとみなす。
【００４４】
他方『２．ループ繰り返し毎のオフセット変化量が等しい』とする場合について、ソースコード例を用いて説明する。例えば、図１０のようなソースコード例の場合、一括ロード・ストア対象の配列参照は「Ａ［ｉ，ｊ］」と「Ｂ［ｉ，ｊ］」である。ｊループに対するストライドは、Ａ、Ｂともに「１」であり、ｉループに対するストライドはＡ、Ｂともに「ＮＵＭ」である。ストライドとは、ループを１回繰り返すごとに変化する配列要素のアクセス幅である。従って、ストライドが等しい場合は、ループ繰り返し毎のオフセット変化量は等しいとみなす。
【００４５】
Ｓ４０３の判定で等しいとする場合（S403:Yes）、コンパイラ１０は、配列参照表１４に登録されている最初の一括ロード・ストア対象の配列参照を基準配列参照とし、Ｓ４０３に進む。Ｓ４０３の判定で、等しく無いとする場合（S403:No.）、Ｓ４０７に進み、「複数アライメント向けコード変換」の処理を行う。
【００４６】
次いで、Ｓ４０５の「単一アラインメント向けコード変換」及びＳ４０７の「複数アラインメント向けコード変換」の各処理について、詳細に説明する。なお、以下の説明では、先ず、「単一アラインメント向けコード変換」の処理を説明し、更に、この処理について、２つのソースプログラム例を用いてより詳細に説明する（図１２〜図１７）。その後、「複数アラインメント向けコード変換」について説明する。
【００４７】
図９に、「単一アラインメント向けコード変換（図８／Ｓ４０５）」の処理の流れを示す。
まず、「単一アラインメント向けコード変換(Ｓ４０５)」の概要について説明する。上述のように、単一アラインメント向けコード変換は、初回参照アドレスが不明な一括ロード・ストア対象の配列参照が１つの場合又は複数ある場合にアラインメントの状況が全て等しいとみなせる時に実施する処理である。
【００４８】
上述の背景技術において、図２４を用いて述べたように、アラインメントには周期性がある。「単一アラインメント向けコード変換」では、１つの配列参照に着目し、アラインメントのパターンそれぞれ（図２４のＳ９０１〜Ｓ９０７）に対するピーリング回数を求め、それを周期ごとに利用するためのコード変換を行うようになっている。
【００４９】
Ｓ５０１で、コンパイラ１０は、最内側ループの親ループをＯＵＴＥＲＬＯＯＰとする。
Ｓ５０３で、コンパイラ１０は、基準配列のＯＵＴＥＲＬＯＯＰに対するストライドがＳＩＭＤ並列度で割り切れるか否かを判定する（ストライドについては、図８／Ｓ４０３参照）。基準配列のＯＵＴＥＲＬＯＯＰに対するストライドがＳＩＭＤ並列度で割り切れる場合（Ｓ503:Yes)、Ｓ５０５に進み、コンパイラ１０は、アライン計算を１パターンとする。基準配列のＯＵＴＥＲＬＯＯＰに対するストライドがＳＩＭＤ並列度で割り切れない場合（S503:No）、Ｓ５０７に進む。
【００５０】
Ｓ５０７で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かを判定する。ＯＵＴＥＲＬＯＯＰに親ループがある場合（S507:Yes）、Ｓ５０９に進み、ＯＵＴＥＲＬＯＯＰに親ループがない場合（S507:No）、Ｓ５１３に進む。
【００５１】
Ｓ５０９で、基準配列のＯＵＴＥＲＬＯＯＰの親ループに対するストライドがＳＩＭＤ並列度で割り切れるか否かを判定する。基準配列のＯＵＴＥＲＬＯＯＰの親ループに対するストライドがＳＩＭＤ並列度で割り切れる場合（S509:Yes）、Ｓ５１１に進み、ＯＵＴＥＲＬＯＯＰの親ループをＯＵＴＥＲＬＯＯＰとし、その後、Ｓ５０７の処理に戻る。基準配列のＯＵＴＥＲＬＯＯＰの親ループに対するストライドがＳＩＭＤ並列度で割り切れない場合（S509:No）、Ｓ５１３に進む。
Ｓ５０７からＳ５１１において、コンパイラ１０は、アライン計算位置を何番目のループの直前に挿入するかを決定することとなる。
【００５２】
ここで、Ｓ５１１までの処理について、図１０のソースプログラム２００を例にして、補足的に説明する。本説明では、レジスタサイズ、アラインサイズは１６バイトとする、なお、他のサイズでも同様に本発明を適用可能である。レジスタサイズが１６バイトで、ソースプログラム２００の配列データのサイズが４バイトであるため、ＳＩＭＤ並列度は「４」とする。また、構文解析Ｓ１０１（図５）の処理によって、ソースプログラム２００から、ループ表１２（図２）、配列表１３（図３）、配列参照表４（図１４）の３つは生成済とする。ソースプログラム２００は、２つの配列参照、「Ａ［ｉ，ｊ］」、「Ｂ［ｉ，ｊ］」が含まれ、２つのアラインメントの状況は等しいものとする（図８のＳ４０３で「Yes]のため。）。よって、配列参照「Ａ［ｉ，ｊ］」を基準に以降の処理を進める。
【００５３】
まず、ソースプログラム２００では、最内側ｊループの親ループはｉループであるため、ｉループがＯＵＴＥＲＬＯＯＰとなる（Ｓ５０１）。基準配列のｉループに対するストライドは、「ＮＵＭ」であり、ＳＩＭＤ配列度「４」で割り切れるか否かは不明であるためＳ５０７に進む（S503:No）。Ｓ５０７で、現在のＯＵＴＥＲＬＯＯＰであるｉループには親ループが存在しないためＳ５１３に進む（S507:No）こととなる。なお、親ループが存在するか否かはループ表１２の親ループ１２２を参照すればよい。以上が、Ｓ５１１までの補足説明である。
【００５４】
引き続き図９のＳ５１３以降の処理について説明する。なお、以下の説明では、図１０に示したソースプログラム２００に対して、Ｓ５１３からＳ５２３までの処理をすべて実施することによって生成される変換後コード２１０（図１１）を同時に参照しながら説明する。
【００５５】
Ｓ５１３で、コンパイラ１０は、最内側ループの親ループ繰り返しごとのオフセット変化量を求めるコードをＯＵＴＥＲＬＯＯＰの直前に挿入する（変換後コード２１０の２１１）。ソースプログラム２００は、上述のように、ＯＵＴＥＲＬＯＯＰはｉループであるため、ｉループの直前に本コードを挿入する。ソースプログラム２００では、最内側ループがｊループ、その親ループがｉループであるため、ｉループ繰り返しごとのオフセット変化量を求めるコードを挿入する。ｉループ繰り返しごとのオフセット変化量は、ｉループが制御している配列次元の添字式、ｉループの増分値及びｉループが制御している配列次元以下の配列Ａの要素数（サイズ）から求められる。
【００５６】
配列参照表１４の配列参照形式１４２から、ｉループが制御している配列次元の添字式は「ｉ」であり、ループ表１２の増分値１２７から、ｉループの増分値は「１」である。また、ｉループが制御している配列Ａの２次元目以下の要素数は「ＮＵＭ」である。従って、ｉループが１回繰り返されるごとに、「ＮＵＭ」ずつ配列参照位置が変化する。これをＳＩＭＤ並列度の「４」で割った余り、「ＮＵＭ％４」がｉループ繰り返しごとに変化する１６バイト境界からのオフセットになる。ピーリングでは、１６バイト境界までのオフセットを求める必要があるため、「４−ＮＵＭ％４」という値を求めるコードを挿入する（変換後コード２１０の２１１）。
【００５７】
なお、上記コード挿入位置は、ＯＵＴＥＲＬＯＯＰの直前にすることは常に可能であるが、ループ繰り返しにおいて変化しない場合は、最外側ループの直前に配置することも可能である。例えば、ソースコード２００の場合、「４−ＮＵＭ％４」という値を求めるコードを挿入するにあたり、本値はループの制御変数を含まないため、最外側ループの直前に配置することが可能である。ループの外側に配置することで、本コードを実行する回数を削減することができる。ただし、２重ループの場合、ＯＵＴＥＲＬＯＯＰと最外側ループは一致する。
【００５８】
Ｓ５１５で、コンパイラ１０は、配列初回参照からアライン境界までのオフセットを求めるコードをＯＵＴＥＲＬＯＯＰの直前に挿入する。（変換後コード２１０の２１２）。ソースプログラム２００は、上述のように、ＯＵＴＥＲＬＯＯＰがｉループであるため、ｉループの直前にコードを挿入する。配列初回参照からアライン境界までのオフセットは「（アラインサイズ−配列初回参照アドレスのアラインサイズオフセット）／配列要素のデータ型のサイズ」で求めることができる。特に、１６バイトアラインで配列データがｆｌｏａｔの場合、「（１６−配列初回参照アドレス％１６）／４」が求める値になる。配列データの型は、配列表１３の型１３３から求められる。
【００５９】
Ｓ５１７で、アラインパターンごとのピーリング回数計算コードをＯＵＴＥＲＬＯＯＰの直前に挿入する（変換後コード２１０の２１３〜２１６）。アラインパターンはアラインサイズや配列データの型により決定できる。一例として、「アラインサイズ／配列データの型サイズ」で求めることができる。アラインサイズとレジスタサイズが一致していることも多いため、その場合はＳＩＭＤ並列度とアラインパターン数が一致する。また後述するように、配列要素数が静的にわかる場合には、更に、アラインパターンを限定することができる。
【００６０】
変換後コード２１０のコード２１３〜２１６について説明する。「アラインサイズ／配列データの型サイズ」をアラインパターン数とすると、ソースプログラム２００では、「１６／４」から、アラインパターン数が「４」になる。コード２１３では、１つ目のアラインパターンに対する１６バイト境界までのオフセットが求められる。「４」で基準化しているのは、その前のコード２１２の結果によって、１６バイト境界までのオフセットが「４」であった場合、ピーリング回数を０回にするためである。
【００６１】
コード２１４では、２つ目のアラインパターンに対する１６バイト境界までのオフセットを求められる。１つ目のアラインパターンに対する１６バイト境界までのオフセット「ｐｅｅｌｃｏｕｎｔ＿０」に、Ｓ５１３で挿入した、最内側ループの親ループ繰り返し毎のオフセット変化量を求めるコードの左辺の値「ｇａｐ」を足したコードを右辺として、左辺の「ｐｅｅｌｃｏｕｎｔ＿１」に代入している。「４」で基準化しているのは、「ｐｅｅｌｃｏｕｎｔ＿０」に「ｇａｐ」を足すことにより、「４」を超える可能性があるためである。もし、１６バイト境界までのオフセット（必要なピーリング回数）が「７」だった場合、実際に必要なピーリング回数は「４」で除した余りである「３」である。
【００６２】
コード２１５では、３つ目のアラインパターンに対する１６バイト境界までのオフセットを求めている。１つ目のアラインパターンに対する１６バイト境界までのオフセット「ｐｅｅｌｃｏｕｎｔ＿０」に、ステップ１０７で挿入した、最内側ループの親ループ繰り返しごとのオフセット変化量を求めるコードの左辺「ｇａｐ」を２倍して足している。「４」での基準化は先ほどと同様である。
【００６３】
コード２１６では、４つ目のアラインパターンに対する１６バイト境界までのオフセットが求められる。１つ目のアラインパターンに対する１６バイト境界までのオフセット「ｐｅｅｌｃｏｕｎｔ＿０」に、ステップ１０７で挿入した、最内側ループの親ループ繰り返しごとのオフセット変化量を求めるコードの左辺「ｇａｐ」を３倍して足している。「４」での基準化は先ほどと同様である。
【００６４】
コード２１３〜２１６では、背景技術で説明した図２４のＳ９０１〜Ｓ９０７に示す各パターンにおける１６バイト境界に合わせるために必要なピーリング回数を求めている。従来技術では、最内側ループの親ループが更新されるごとにピーリング回数を計算するため、ｉのループ長である「ＩＵ−ＩＬ＋１」回の計算が必要となっていた。本実施形態の場合は、コード２１３〜２１６が、これらピーリング回数を求めるコードとなっていることから、これよりも少ない「４回」の計算ですむという利点がある。
【００６５】
Ｓ５１９で、コンパイラ１０は、最内側ループの親ループをアラインパターン回展開する（変換後コード２１０の２１７及び２２０、２２２、２２４、２２６（のＳＩＭＤ化前））。アラインパターンは「４」であるため、最内側ループの親ループを「４回」展開する。すなわち、ループの増分値を「＋４」にし、上限値を３だけ削減し、最内側ループを４倍に複写する。なお、余りループは省略している。
【００６６】
Ｓ５２１で、コンパイラ１０は、展開後の各最内側ループの直前にＳ５１７で求めた回数だけピーリングを行うコードを挿入する（変換後コード２１０の２１９、２２１、２２３、２２５）。また、Ｓ５１９で展開したコードの下限値を、本ステップで挿入したピーリングの続きから始まるように変更する（図２４において、各パターンに対してピーリングを実現させるためのコードとなる）。
【００６７】
Ｓ５２３で、コンパイラ１０は、展開後の各最内側ループをＳＩＭＤ化 する（変換後コード２１０の２２０、２２２、２２４、２２６）。なお、本実施例は、ＳＩＭＤ最適化処理を例に説明しているために、Ｓ５２３でＳＩＭＤ化するようにしているが、本発明はこれに限るものではなく、これに代わる別処理を適用することもできる。
以上が、「単一アラインメント向けコード変換」の処理の説明である。
【００６８】
ここで、「単一アラインメント向けコード変換」を用いて、アライン計算方法を簡略化できる様を実際のソースプログラムに当て嵌めた例を２点紹介する。
１点目は、「図１２のソースプログラム３００に対して、『単一アラインメント向けコード変換』を実施した場合の処理例である。なお、ループ表や配列表は前述のように作成済とする。
【００６９】
Ｓ５０１で、コンパイラ１０は、ｊループをＯＵＴＥＲＬＯＯＰとする。ソースプログラム３００の最内側ループはｋループで、その親ループはｊループであるからである。
【００７０】
Ｓ５０３で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに対するストライドが「４」で割り切れるか否かを判定する。ソースプログラム３００の配列参照「Ａ［ｉ，ｊ，ｋ］」について、ＯＵＴＥＲＬＯＯＰに対するストライド、即ちｊループに対するストライドは、配列１次元目の要素数「１００」と、ｊループの増分値「１」と、添式字「ｊ」とから「１００」と求まる。これは、ＳＩＭＤ並列度「４」で割り切れるため、コンパイラ１０はＳ５０５に進む。
【００７１】
Ｓ５０５で、コンパイラ１０は、アラインパターンを「１パターン」とする。図１３の模式図を用いてその理由を説明する。図１３において、１マスは４バイトデータを表し、マスの中の数字は１次元目の添字を表している。ソースプログラム３００では、配列参照「Ａ［ｉ，ｊ，ｋ］」のｊループに対するストライドは「１００」で、ｊ＝１の時の初回参照からｊ＝２の時の初回参照までの要素数は「１００」であり、ＳＩＭＤ並列度「４」で割り切れる。従って、ｊ＝１の時もｊ＝２の時も１６バイト境界からのオフセットの状況に変化はない。これは他のｊについても同様である。つまり、任意のｊについて１６バイト境界からのオフセットが等しいため、アラインパターンは「１パターン」としてよい。
【００７２】
Ｓ５０７で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かの判定を行う。現在のＯＵＴＥＲＬＯＯＰであるｊループには、親ループのｉループがあるため、Ｓ５０９に進む。
Ｓ５０９で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰの親ループの並列度がＳＩＭＤ並列度で割り切れるか否かを判定する。配列参照「Ａ［ｉ，ｊ，ｋ］」のｉループに対するストライドは「９９００」で、ＳＩＭＤ並列度「４」で割り切れるためＳ５１１に進む。
【００７３】
Ｓ５１１で、コンパイラ１０は、ｉループをＯＵＴＥＲＬＯＯＰとする。そして、Ｓ５０７に戻る。
Ｓ５０７で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かを判定するが、現在のＯＵＴＥＲＬＯＯＰであるｉループには、親ループが存在しないため、Ｓ５１３に進む。Ｓ５１３以降の処理は図９と同様である。
【００７４】
図１４に、このようにして生成された変換後のコード３１０の例を示す。Ｓ５０５で求めたように、アラインパターンは「１つ」で、アライン計算位置はＳ５０７〜Ｓ５１１で求めたＯＵＴＥＲＬＯＯＰであるｉループの直前となる。
以上が、１つ目の簡略化例である。
【００７５】
次に、もう一方の例について説明する。本例では、図１５に示す、ソースプログラム４００を用いて説明する。なお、ループ表や配列表は前述のように作成済とする。
Ｓ５０１で、コンパイラ１０は、ソースプログラム４００は、最内側ループがｋループで、その親ループはｊループであるため、ｊループをＯＵＴＥＲＬＯＯＰとする。
【００７６】
Ｓ５０３で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰの親ループの並列度がＳＩＭＤ並列度で割り切れるか否かを判定する。配列参照「Ａ［ｉ，ｊ，ｋ］」のＯＵＴＥＲＬＯＯＰに対するストライド、即ちｊループに対するストライドは、配列１次元目の要素数が「９９」と、ｊループの増分値「１」と、添式字「ｊ」とから「９９」と求まる。これは、ＳＩＭＤ並列度「４」で割り切れないため、Ｓ５０７に進む。
【００７７】
Ｓ５０７で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かを判定する。現在のＯＵＴＥＲＬＯＯＰであるｊループには、親ループのｉループがあるため、Ｓ５０９に進む。
Ｓ５０９で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰの親ループの並列度がＳＩＭＤ並列度で割り切れるか否かを判定する。配列参照「Ａ［ｉ，ｊ，ｋ］」のｉループに対するストライドは、「９９００」であり、ＳＩＭＤ並列度「４」で割り切れるため、Ｓ５１１に進む。
【００７８】
Ｓ５１１で、コンパイラ１０は、ｉループをＯＵＴＥＲＬＯＯＰとする。そして、Ｓ５０７に戻る。
Ｓ５０７で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かを判定するが、現在のＯＵＴＥＲＬＯＯＰであるｉループには、親ループが存在しないため、Ｓ５１３に進む。Ｓ５１３以降の処理は図１５を用いた時と同様である。
【００７９】
図１７に、このようにして生成された変換後のコード４１０の例を示す。アライン計算位置はＳ５０７からＳ５１１で求めたＯＵＴＥＲＬＯＯＰであるｉループの直前となっている。図１６を用いてその理由を説明する。図１６では、１マスは４バイトデータを表し、マスの中の数字は１次元目の添字を表している。配列参照「Ａ［ｉ，ｊ，ｋ］」のｊループに対するストライドは、「９９」であり、ＳＩＭＤ並列度「４」で割り切れないため、ｊ＝１、ｊ＝２で初回参照の１６バイト境界オフセットは異なるが、ｉループに対するストライドは、「９９００」であり、ＳＩＭＤ並列度「４」で割り切れる。このため、図に示すように、ｉ＝１の時とｉ＝２の時で初回参照の１６バイト境界からのオフセットは等しくなる。これは他のｉについても同様であり、つまり任意でのｉで初回参照の１６バイト境界からのオフセットは等しくなる。従って、ｉごとに初回参照の１６バイト境界からのオフセットが異なることがないため、ｉループの直前に初回参照を用いたアラインメントの計算コードを挿入できる。
以上が、「単一アライメント向けコード変換」の他の例である。
【００８０】
最後に、「複数アラインメント向けコード変換（図８／Ｓ４０７）」の処理の詳細について説明する。本処理は、アライン計算が必要な配列参照が複数ある場合の処理である。
特に、アラインメントが一致しない可能性のある配列参照がある場合、初回参照や、ループ繰り返しごとの変化量（ストライド）を用いて、アラインメントが不一致となるパターンをループに入る前に発見する点が特徴の１つである。
【００８１】
図１８に、「複数アラインメント向けコード変換」処理の流れを示す。また、本処理では、図１５に示すソースプログラム２００に処理を実行するものとする。その結果変換された変換後コード６００を、図１９に例示する。なお、ループ表１２や配列表１３は作成済とする。
【００８２】
Ｓ６０１で、コンパイラ１０は、最外側ループをｉｆブロックで囲む（図１９の６１０）。
Ｓ６０３で、コンパイラ１０は、一括ロード・ストア配列参照のうち最初のエントリを基準配列参照とする。一括ロード・ストア配列参照は、配列参照表１４から検索する。配列参照表１４では、一括ロード・ストア配列参照は、「Ａ［ｉ，ｊ］」と「Ｂ［ｉ，ｊ］」である。最初にエントリされているのは、「Ａ［ｉ，ｊ］」であるため、「Ａ［ｉ，ｊ］」を基準配列参照とする。
【００８３】
Ｓ６０５で、コンパイラ１０は、基準配列参照以外で未処理の配列参照があるか否かを判定する。基準配列参照以外で未処理の配列参照がある場合（S605:Yes）、Ｓ６０７に進む。基準配列参照以外で未処理の配列参照がない場合（S605:No.）、Ｓ６１１に進む。ソースプログラム２００では、配列参照表１４によると、基準配列参照以外に未処理の配列参照「Ｂ［ｉ，ｊ］」が存在するため、Ｓ６０５の結果は「Ｙｅｓ」となり、Ｓ６０７に進む。
【００８４】
Ｓ６０７で、コンパイラ１０は、取り出した配列参照と基準配列参照の初回参照オフセットが異なるか否かを比較する文をｉｆブロックの条件式に挿入する（図１９の６１１）。ソースプログラム２００では、基準配列参照「Ａ［ｉ，ｊ］」の初回参照オフセット「＆Ａ［ＩＬ，Ｌ］％１６」と、取り出した配列参照「Ｂ［ｉ，ｊ］」の初回参照オフセット「＆Ｂ［ＩＬ，Ｌ］％１６」とが異なるか否かを比較する文がｉｆブロックの条件式に挿入される。
【００８５】
Ｓ６０９で、コンパイラ１０は、ＯＲを表す「｜｜」をｉｆブロックの条件式に挿入する。その後、Ｓ６０５に戻り、未処理の配列参照がなくなるまで本処理を繰り返す。ソースプログラム２００では、配列参照「Ｂ［ｉ，ｊ］」を処理した後には、未処理の配列参照が存在しないため（S605:No）、Ｓ６１１に進む。
【００８６】
Ｓ６１１で、コンパイラ１０は、最内側ループの親ループをＯＵＴＥＲＬＯＯＰとする。ソースプログラム２００の場合、最内側ループｊループの親ループであるｉループがＯＵＴＥＲＬＯＯＰとなる。
Ｓ６１３で、コンパイラ１０は、配列参照表１４に対し、もう一度、最初のエントリを基準配列参照として、他のエントリを取り出す。
【００８７】
Ｓ６１５で、コンパイラ１０は、取り出した配列参照と基準配列参照に対し、ＯＵＴＥＲＬＯＯＰに対するストライドのオフセットが異なるか否かを比較する文をｉｆブロックの条件式に挿入する。ソースプログラム２００では、最初のエントリである「Ａ［ｉ，ｊ］」と、次のエントリである「Ｂ［ｉ，ｊ］」とに対し、ＯＵＴＥＲＬＯＯＰに対するストライドのオフセットが異なるか否かを比較する文がｉｆブロックの条件式に挿入される。そして、現在のＯＵＴＥＲＬＯＯＰは、ｉループであるため、「Ａ［ｉ，ｊ］」と「Ｂ［ｉ，ｊ］」に対し、ｉループに対するストライドのオフセットが異なるか否かを比較する文が作成される。
【００８８】
「Ａ［ｉ，ｊ］」のｉループに対するストライドのオフセットは「ＮＵＭ％４」、「Ｂ［ｉ，ｊ］」のｉループに対するストライドのオフセットは「ＮＵＭ％４」であり、この２つが異なるか否かを比較する文がｉｆブロックの条件式に挿入される（図１９の６１３）。なお、コード６１３のように、ストライドのオフセットが一致することが明らかな場合は判定を省略することも可能である。
【００８９】
Ｓ６１７で、コンパイラ１０は、ＯＲを表す「｜｜」をｉｆブロックの条件式に挿入する。そして、Ｓ６１３に戻り、未処理の配列参照がなくなるまで本処理を繰り返す。ソースプログラム２００では、配列参照「Ｂ［ｉ，ｊ］」を処理した後には、未処理の配列参照が存在しないため（S613:No.）、Ｓ６１９に進む。
【００９０】
Ｓ６１９で、コンパイラ１０は、ＯＵＴＥＲＬＯＯＰに親ループがあるか否かを判定する。ＯＵＴＥＲＬＯＯＰに親ループがある場合（S619:Yes）、Ｓ６２５に進み、ＯＵＴＥＲＬＯＯＰの親ループをＯＵＴＥＲＬＯＯＰとし、Ｓ６１３からＳ６１７の処理を繰り返す。ＯＵＴＥＲＬＯＯＰに親ループがない場合（S619:No.）、Ｓ６２１に進み、最後に挿入したＯＲ(｜｜)を削除し、Ｓ６２３に進む。ソースプログラム２００では、現在のＯＵＴＥＲＬＯＯＰであるｉループには親ループが存在しないため（S619:No.）、Ｓ６２１に進み、最後に挿入したＯＲ(｜｜)を削除し、Ｓ６２３に進む。
【００９１】
Ｓ６２３で、コンパイラ１０は、ｅｌｓｅブロックを作成し、基準配列を利用した単一アラインメント向けコードを挿入する。ソースプログラム２００の場合、ｅｌｓｅブロック中に、基準配列Ａ［ｉ，ｊ］を利用した単一アラインメント向けコードが挿入される。
【００９２】
以上が、「複数アラインメント向けコード変換」の処理の流れである。初回参照や、ループ繰り返しごとの変化量（ストライド）を用いた判定を行うことにより、配列参照間でアラインメントが不一致となるパターンをループに入る前に発見することができる。
【符号の説明】
【００９３】
１０・・・コンパイラ、１１・・・中間コード、１２・・・ループ表、１３・・・配列表、１４・・・配列参照表、ソースプログラム２０
【図１】
2014137657.tif 000003
【図２】
2014137657.tif 000004
【図３】
2014137657.tif 000005
【図４】
2014137657.tif 000006
【図５】
2014137657.tif 000007
【図６】
2014137657.tif 000008
【図７】
2014137657.tif 000009
【図８】
2014137657.tif 000010
【図９】
2014137657.tif 000011
【図１０】
2014137657.tif 000012
【図１１】
2014137657.tif 000013
【図１２】
2014137657.tif 000014
【図１３】
2014137657.tif 000015
【図１４】
2014137657.tif 000016
【図１５】
2014137657.tif 000017
【図１６】
2014137657.tif 000018
【図１７】
2014137657.tif 000019
【図１８】
2014137657.tif 000020
【図１９】
2014137657.tif 000021
【図２０】
2014137657.tif 000022
【図２１】
2014137657.tif 000023
【図２２】
2014137657.tif 000024
【図２３】
2014137657.tif 000025
【図２４】
2014137657.tif 000026