JP5846005B2 - プログラム、コード生成方法および情報処理装置 - Google Patents

Description

本発明はプログラム、コード生成方法および情報処理装置に関する。

現在、ＣＰＵ（Central Processing Unit）などのプロセッサの中には、ＳＩＭＤ（Single Instruction Multiple Data）命令と呼ばれる１つの命令によって、異なるデータに対して同じ種類の演算を並列実行できるものがある。ＳＩＭＤ命令を実行するプロセッサは、並列に処理すべき異なるデータを組み合わせて格納するＳＩＭＤレジスタと呼ばれるレジスタを備える。例えば、ＳＩＭＤレジスタｓ１にデータＡ１，Ａ２が格納され、ＳＩＭＤレジスタｓ２にデータＢ１，Ｂ２が格納された状態で、プロセッサにｓ１＋ｓ２というＳＩＭＤ命令が入力されたとする。すると、プロセッサは、Ａ１＋Ｂ１およびＡ２＋Ｂ２という２つの加算を、１命令で並列に実行することになる。

ＳＩＭＤ命令を含むコードを生成する方法としては、ＳＩＭＤ命令でない複数の命令の中から、演算の種類が同じであり並列に実行できる２以上の命令を検索し、検索した命令を組み合わせてＳＩＭＤ命令を生成する方法がある。例えば、高級言語で記述されたソースコードを機械可読なオブジェクトコードに変換するコンパイラの中には、最適化処理の中で、２以上の命令を組み合わせてＳＩＭＤ命令に変換するものがある。組み合わせ可能な命令の数（並列度）は、プロセッサのアーキテクチャによって異なる。

なお、ソースコードをＲＴＬ（Register Transfer Language）で記述された中間コードに変換し、中間コードから同じ種類の演算を異なるデータに適用している命令のセットを抽出し、ＳＩＭＤ命令に変換するプログラム処理方法が提案されている。また、複数の命令の間の依存関係を示すトレース依存性ツリーを生成し、同一のレベルに属する同じ種類の演算を指定した２以上の命令をトレース依存性ツリーから検索し、検索した命令を１つのＳＩＭＤ命令にマージするコンピュータシステムが提案されている。

特開２００３−２０２９９１号公報 国際公開第２００６／００７１９３号

ＳＩＭＤ命令を生成するには、依存関係がなく並列に実行可能な命令同士を組み合わせることになる。そこで、命令の組み合わせを探索する方法としては、前述のように、命令間の依存関係を示すツリーを利用する方法が考えられる。コードを解析して複数のツリー（１つの大きなツリーに属する複数の部分ツリーでもよい）が生成されたとき、ツリー同士を比較し、異なるツリーに属する演算の種類が同じ命令同士を組み合わせることによって、組み合わせのパターンを探すことができる。

しかし、コードを解析して生成される複数のツリーは、同じ形状をしているとは限らない。このため、前述のように同じレベルにある命令同士を比較するだけでは、適切な命令の組み合わせを見つけることができないことがある。このとき、異なるレベルにある命令同士を組み合わせることが可能な場合もある。一方で、ＳＩＭＤ命令に変換できる命令の組み合わせを多く見つけるために、ツリーの構造とは関係なく命令の組み合わせを全探索しようとすると、計算量が増大し非効率的となってしまう。

一側面では、本発明は、異なるデータに対して同じ種類の演算を並列実行するよう指示する命令を生成するための命令の組み合わせを効率的に探索できるプログラム、コード生成方法および情報処理装置を提供することを目的とする。

一側面では、第１のコードから、第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成するためのプログラムが提供される。プログラムはコンピュータに以下の処理を実行させる。第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、第１の演算木の各命令で指定された演算を第１の演算木の構造に応じた順序で並べた第１の演算列と、第２の演算木の各命令で指定された演算を第２の演算木の構造に応じた順序で並べた第２の演算列とを算出する。第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出する。２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する第１の演算木の命令と第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する。

また、一側面では、第１のコードから、第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成する、コンピュータが実行するコード生成方法が提供される。コード生成方法では、第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、第１の演算木の各命令で指定された演算を第１の演算木の構造に応じた順序で並べた第１の演算列と、第２の演算木の各命令で指定された演算を第２の演算木の構造に応じた順序で並べた第２の演算列とを算出する。第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出する。２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する第１の演算木の命令と第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する。

また、一側面では、第１のコードと、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を含む第２のコードとを記憶する記憶部と、第１のコードに含まれる２以上の命令を組み合わせて特定命令を生成することで、第１のコードから第２のコードを生成する演算部と、を有する情報処理装置が提供される。演算部は、第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、第１の演算木の各命令で指定された演算を第１の演算木の構造に応じた順序で並べた第１の演算列と、第２の演算木の各命令で指定された演算を第２の演算木の構造に応じた順序で並べた第２の演算列とを算出する。第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出する。２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する第１の演算木の命令と第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する。

一側面では、異なるデータに対して同じ種類の演算を並列実行するよう指示する命令を生成するための命令の組み合わせを効率的に探索できる。

第１の実施の形態の情報処理装置を示す図である。 端末装置が備えるハードウェア例を示すブロック図である。 端末装置が備えるソフトウェア例を示すブロック図である。 ＳＩＭＤ命令とＳＩＭＤレジスタの関係例を示す図である。 ＳＩＭＤレジスタの実装例を示す図である。 命令間の依存関係の例を示す図である。 ＳＩＭＤ化により発生する転送命令の例を示す図である。 ソースコードの例を示す図である。 演算木の第１の例を示す図である。 ＬＣＳデータの例を示す図である。 ＬＣＳの算出方法の例を示す図である。 ＳＩＭＤレジスタの第１の割り当て例を示す図である。 ＳＩＭＤレジスタの第２の割り当て例を示す図である。 ＳＩＭＤレジスタの第３の割り当て例を示す図である。 演算木の第２の例を示す図である。 クロスＦＭＡ命令の実行例を示す図である。 ＳＩＭＤ化処理の手順例を示すフローチャートである。 中間コードの例を示す図である。 命令データと演算木データの例を示す図である。 演算木リストの例を示す図である。 演算木生成処理の手順例を示すフローチャートである。 演算木の間の依存関係の例を示す図である。 依存判定処理の手順例を示すフローチャートである。 演算木組データと命令組データの例を示す図である。 命令組判定処理の手順例を示すフローチャートである。 ＬＣＳマッチング処理の手順例を示すフローチャートである。 ＳＩＭＤ化数解析処理の第１の手順例を示すフローチャートである。 ＳＩＭＤ化数解析処理の第２の手順例を示すフローチャートである。

以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。情報処理装置１０は、第１のコード１１ａから、ＳＩＭＤ命令を含む第２のコード１１ｂを生成する。第１のコード１１ａは、例えば、高級言語で記述されたソースコードや、ソースコードから変換された中間コードである。第２のコード１１ｂは、例えば、情報処理装置１０または他のコンピュータのプロセッサが解釈可能なオブジェクトコードや実行コードである。情報処理装置１０は、ユーザが操作する端末装置としてのクライアントコンピュータでもよいし、端末装置からアクセスされるサーバコンピュータであってもよい。なお、ＳＩＭＤ命令は、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令の一例である。

情報処理装置１０は、記憶部１１および演算部１２を有する。記憶部１１は、第１のコード１１ａおよび第２のコード１１ｂを記憶する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。演算部１２は、第１のコード１１ａに含まれる２以上の命令を組み合わせてＳＩＭＤ命令に変換することで、第２のコード１１ｂを生成する。演算部１２は、ＣＰＵやＤＳＰ（Digital Signal Processor）などのプロセッサでもよいし、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などのプロセッサ以外の電子回路でもよい。プロセッサは、例えば、記憶部１１または他のメモリに記憶されたプログラムを実行する。

演算部１２は、第１のコード１１ａに含まれる命令の間の依存関係を示す演算木１３ａ，１３ｂを生成する。依存関係には、一方の命令で算出されるデータを他方の命令で参照するという定義・参照の関係が含まれる。ここで、演算木１３ａに属する命令と演算木１３ｂに属する命令とは異なる命令である。演算木１３ａ，１３ｂは、１つの大きな演算木に含まれる部分木であってもよい。演算部１２は、３個以上の演算木を生成してもよい。

次に、演算部１２は、演算木１３ａに属する各命令で指定された演算を、演算木１３ａの構造に応じた順序で並べた演算列１４ａを生成する。また、演算部１２は、演算木１３ｂに属する各命令で指定された演算を、演算木１３ｂの構造に応じた順序で並べた演算列１４ｂを生成する。演算には、加算（＋），減算（−），乗算（×），除算（÷）が含まれる。また、演算には、べき乗演算（逆数・平方根・平方根の逆数などを求める演算を含む）、超越関数（ｓｉｎ，ｃｏｓ，ｌｏｇ，ｅｘｐなどを含む）計算、剰余演算、符号変換、比較演算、メモリアクセス（Ｌｏａｄ，Ｓｔｏｒｅなどをくむ）が含まれる。ツリー状に関連付けられた複数の演算を一列に並べる方法としては、帰り掛け深さ優先探索や、帰り掛け幅優先探索などのアルゴリズムを用いることができる。

次に、演算部１２は、演算列１４ａ，１４ｂに共通のサブ演算列のうち、長さが最大である最長サブ演算列を算出する。サブ演算列は、元の演算列から、順序を入れ替えずに１またはそれ以上の演算を取り出したものである。演算列１４ａと演算列１４ｂとが同一でない場合、共通のサブ演算列は、演算列１４ａ，１４ｂの少なくとも一方から１またはそれ以上の演算を削除することで現れる。このように算出される最長サブ演算列は、演算列１４ａ，１４ｂの最長共通部分列（ＬＣＳ：Longest Common Subsequence）と呼ぶことができる。最長サブ演算列は、２以上算出されることがある。例えば、演算列１４ａ＝“＋×÷＋・・・”，演算列１４ｂ＝“＋÷÷−・・・”とする。この場合、演算列１４ａの１番目・３番目の演算と演算列１４ｂの１番目・２番目の演算を採用した最長サブ演算列１５ａ＝“＋÷・・・”と、演算列１４ａの１番目・３番目の演算と演算列１４ｂの１番目・３番目の演算を採用した最長サブ演算列１５ｂ＝“＋÷・・・”とが算出される。

そして、演算部１２は、算出された最長サブ演算列に基づいて、演算木１３ａに属する命令と演算木１３ｂに属する命令との間の組み合わせを決定する。算出された最長サブ演算列が１個である場合、演算部１２は、その最長サブ演算列に含まれる各演算に該当する演算木１３ａの命令と演算木１３ｂの命令とを組み合わせてＳＩＭＤ命令を生成する。一方、算出された最長サブ演算列が２個以上の場合、演算部１２は、最長サブ演算列毎に、その最長サブ演算列に従ってＳＩＭＤ命令を生成した場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて何れか１つの最長サブ演算列を選択する。

ここで、命令の組み合わせ方によっては、ＳＩＭＤ命令に付随して、ＳＩＭＤレジスタ間でデータを転送するための転送命令が生成されてしまうことがある。例えば、命令１：Ａ１＝Ｂ１＋Ｃ１，命令２：Ａ２＝Ｂ２＋Ｃ２，命令３：Ｄ１＝Ａ２×Ｃ１，命令４：Ｄ２＝Ａ３×Ｃ２という命令が存在し、ＳＩＭＤの並列度が２であるとする。この場合、命令１，２を組み合わせてＳＩＭＤ命令１を生成し、命令３，４を組み合わせてＳＩＭＤ命令２を生成することが考えられる。しかし、ＳＩＭＤ命令１を実行するとデータＡ１，Ａ２が同じＳＩＭＤレジスタに格納される一方、ＳＩＭＤ命令２を実行するにはデータＡ２，Ａ３を同じＳＩＭＤレジスタに格納しておくことになる。よって、この組み合わせでは、ＳＩＭＤ命令１，２の間に転送命令が挿入されてしまう。転送命令が多いほど、生成される第２のコード１１ｂの実行効率が低下する。

そこで、計算リソースの評価では、演算部１２は、各最長サブ演算列を採用した場合に発生する転送命令の数を評価し、転送命令が少ない最長サブ演算列を選択してもよい。また、演算部１２は、最長サブ演算列毎に、ＳＩＭＤ命令に変換することによる命令の減少量と、転送命令の発生による命令の増加量とを算出し、前者から後者を引いた実質的なＳＩＭＤ効率を評価して、ＳＩＭＤ効率が高い最長サブ演算列を選択してもよい。

第１の実施の形態の情報処理装置１０によれば、演算木１３ａ，１３ｂを演算列１４ａ，１４ｂに変換して最長サブ演算列を算出することで、命令の組が最も多くなるような演算木１３ａ，１３ｂの間の命令の組み合わせパターンを特定できる。このとき、演算木１３ａ，１３ｂの形状が同じでなくてもよく、また、組み合わせるべき２つの命令が演算木１３ａ，１３ｂの同じレベルに存在していなくてもよい。また、２以上の最長サブ演算列が算出されたときは、実行時の計算リソースの使用状況が有利になる最長サブ演算列が選択される。これにより、命令の組み合わせを効率的に探索することができる。

［第２の実施の形態］
図２は、端末装置が備えるハードウェア例を示すブロック図である。第２の実施の形態の端末装置１００は、高級言語で記述されたソースコードをコンパイルして、機械可読なオブジェクトコードを生成し、複数のオブジェクトコードをリンクして、端末装置１００または他のコンピュータに実行させる実行コードを生成する。ただし、第２の実施の形態で説明するコンパイルおよびリンクは、サーバコンピュータで実行することもできる。

端末装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１は、第１の実施の形態の演算部１２の一例であり、ＲＡＭ１０２やＨＤＤ１０３は、第１の実施の形態の記憶部１１の一例である。

ＣＰＵ１０１は、プログラムの命令を実行する演算器を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、端末装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。

ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや計算に用いられるデータを一時的に記憶する揮発性メモリである。なお、端末装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。

ＨＤＤ１０３は、ＯＳ（Operating System）やファームウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性記憶装置である。なお、端末装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の記憶装置を備えてもよい。

画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、端末装置１００に接続されたディスプレイ２１に画像を出力する。ディスプレイ２１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。

入力信号処理部１０５は、端末装置１００に接続された入力デバイス２２から入力信号を取得し、ＣＰＵ１０１に通知する。入力デバイス２２としては、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。

ディスクドライブ１０６は、記録媒体２３に記録されたプログラムやデータを読み取る駆動装置である。記録媒体２３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１からの命令に従って、記録媒体２３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。

通信インタフェース１０７は、ネットワーク２４を介して他のコンピュータと通信を行えるインタフェースである。通信インタフェース１０７は、有線網に接続する有線インタフェースでもよいし、無線網に接続する無線インタフェースでもよい。

図３は、端末装置が備えるソフトウェア例を示すブロック図である。端末装置１００は、ファイル記憶部１１０、コンパイラ１２０およびリンカ１３０を有する。ファイル記憶部１１０は、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域として実現できる。コンパイラ１２０およびリンカ１３０は、ＣＰＵ１０１が実行するプログラムのモジュールとして実現できる。ただし、コンパイラ１２０およびリンカ１３０の機能の一部または全部を、ソフトウェアでなく電子回路として実現することも可能である。

ファイル記憶部１１０は、ソースファイル１１１、オブジェクトファイル１１２および実行ファイル１１３を記憶する。ソースファイル１１１は、高級言語で記述されたソースコードを含む。オブジェクトファイル１１２は、ＳＩＭＤ命令を含む機械可読なオブジェクトコードを含む。実行ファイル１１３は、ＳＩＭＤ命令を解釈できる所定のアーキテクチャのプロセッサが実行できる形式のファイルである。なお、ＣＰＵ１０１は、実行ファイル１１３を実行可能であってもよいし、実行可能でなくてもよい。

コンパイラ１２０は、ファイル記憶部１１０からソースファイル１１１を読み出し、ソースコードをオブジェクトコードに変換して、オブジェクトファイル１１２をファイル記憶部１１０に格納する。コンパイラ１２０は、入出力制御部１２１、ファイル入力部１２２、中間コード生成部１２３、中間コード記憶部１２４、最適化部１２５、アセンブリコード生成部１２８およびファイル出力部１２９を有する。

入出力制御部１２１は、ファイルの種類に応じた入出力方法を選択し、ファイル入力部１２２およびファイル出力部１２９を制御する。ファイル入力部１２２は、入出力制御部１２１からの指示に応じて、ソースファイル１１１をオープンし、ソースファイル１１１からソースコードを読み出す。中間コード生成部１２３は、ファイル入力部１２２が読み出したソースコードを解析して、コンパイラ１２０の内部で利用される中間言語で記述された中間コードに変換し、中間コードを中間コード記憶部１２４に格納する。ソースコードの解析には、字句解析、構文解析、意味解析などが含まれる。中間コード記憶部１２４は、ＲＡＭ１０２に確保された記憶領域であり、中間コードを記憶する。

最適化部１２５は、中間コード記憶部１２４に記憶された中間コードを、実行速度が向上するように最適化する。最適化部１２５は、解析部１２６および最適化実行部１２７を有する。解析部１２６は、中間コードを解析して最適化方法を決定する。解析部１２６が行う最適化方法の決定には、中間コードに含まれる命令の中でＳＩＭＤ命令に変換する命令の組み合わせを決定することを含む。最適化実行部１２７は、解析部１２６が決定した最適化方法に従って中間コードを最適化する。最適化実行部１２７が行う最適化には、中間コードに含まれる命令をＳＩＭＤ命令に変換することを含む。

アセンブリコード生成部１２８は、最適化された中間コードを、低級言語であるアセンブリ言語で記述されたアセンブリコードに変換する。ファイル出力部１２９は、入出力制御部１２１からの指示に応じて、オブジェクトファイル１１２を生成する。そして、ファイル出力部１２９は、アセンブリコード生成部１２８が生成したアセンブリコードをオブジェクトコードに変換し、オブジェクトファイル１１２に書き込む。

リンカ１３０は、ファイル記憶部１１０からオブジェクトファイル１１２を読み出し、オブジェクトコードを解析して、参照されている他のオブジェクトファイルやライブラリを検出する。そして、リンカ１３０は、オブジェクトファイル１１２と、検出した他のオブジェクトファイルやライブラリとをリンクし、実行ファイル１１３を生成する。なお、コンパイラ１２０にリンカ１３０の機能が統合されていてもよい。

ここで、プロセッサ内でのＳＩＭＤ命令の実行方法について説明する。
図４は、ＳＩＭＤ命令とＳＩＭＤレジスタの関係例を示す図である。ＳＩＭＤ命令を解釈できるプロセッサは、並列に処理されるデータを組み合わせて格納するＳＩＭＤレジスタを備える。各ＳＩＭＤレジスタは、プロセッサのアーキテクチャによって決まる並列度に相当する数のサブレジスタを含む。図４は、並列度が２の場合を示している。

例えば、図４に示すように、Ａ＝Ｂ＋Ｃ，Ｘ＝Ｙ＋Ｚという２つの命令を１つのＳＩＭＤ命令ｓ１＝ｓ２＋ｓ３に変換した場合を考える。この場合、ＳＩＭＤレジスタｓ２のサブレジスタ１にデータＢ、ＳＩＭＤレジスタｓ２のサブレジスタ２にデータＹ、ＳＩＭＤレジスタｓ３のサブレジスタ１にデータＣ、ＳＩＭＤレジスタｓ３のサブレジスタ２にデータＺを格納しておく。すると、ＳＩＭＤ命令によって、２つの加算が並列に実行されてデータＡ，Ｘが算出され、ＳＩＭＤレジスタｓ１のサブレジスタ１にデータＡ、ＳＩＭＤレジスタｓ１のサブレジスタ２にデータＸが格納されることになる。

なお、同じ位置にあるサブレジスタの集合をスロットと呼ぶ。すなわち、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ１はスロット１に属し、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ２はスロット２に属する。ＳＩＭＤ命令では、同じスロットに属する複数のサブレジスタを用いて１つの演算が行われることになる。

図５は、ＳＩＭＤレジスタの実装例を示す図である。プロセッサ内にＳＩＭＤレジスタを実装する方式としては、図５に示すような（Ａ）分割方式と（Ｂ）結合方式がある。
分割方式では、１つの大きな物理レジスタを論理的に均等な大きさに分割して、複数のサブレジスタを形成する。並列度＝２の場合は物理レジスタの記憶領域を２等分し、並列度＝４の場合は物理レジスタの記憶領域を４等分する。物理レジスタの大きさを一定とすると、並列度が高いほど、各サブレジスタのビット数は小さくなる。分割方式では、ＳＩＭＤレジスタは物理的なレジスタを指し、サブレジスタは論理的なレジスタを指す。

一方、結合方式では、ビット数が等しい複数の物理レジスタをグルーピングし、各物理レジスタをサブレジスタとして用いて、ＳＩＭＤレジスタを形成する。並列度＝２の場合は２個の物理レジスタの集合をＳＩＭＤレジスタとして扱い、並列度＝４の場合は４個の物理レジスタの集合をＳＩＭＤレジスタとして扱う。物理レジスタの大きさを一定とすると、並列度が高いほど、ＳＩＭＤレジスタのビット数は大きくなる。分割方式では、ＳＩＭＤレジスタは論理的なレジスタを指し、サブレジスタは物理的なレジスタを指す。

次に、ＳＩＭＤ命令に変換する命令組を選択するときの問題点について説明する。
図６は、命令間の依存関係の例を示す図である。命令依存グラフ３０は、中間コードに含まれる命令間の依存関係を示す。ここでは、コンパイラ１２０が１度に処理するコード範囲（翻訳単位）に、８個の命令が含まれている場合を考える。図６に示すように、命令１，２，３，８では乗算（×）が行われ、命令４，５，７では減算（−）が行われ、命令６では除算（÷）が行われる。命令４は命令１の演算結果を参照し、命令５は命令１，２の演算結果を参照し、命令６は命令４，５の演算結果を参照し、命令７は命令３の演算結果を参照し、命令８は命令６，７の演算結果を参照している。なお、図６では、理解を容易にするため、各命令を高級言語の形式で記載している。

このような命令依存グラフ３０において、ルートからの深さが同じ命令（同じレベルの命令）の間で、ＳＩＭＤ命令に変換する（ＳＩＭＤ化する）命令の組み合わせを探すと、乗算を行う命令１，２の組と、減算を行う命令４，５の組が選択される。しかし、命令１，２および命令４，５という組み合わせは、以下に説明するように最適でない。

図７は、ＳＩＭＤ化により発生する転送命令の例を示す図である。命令１，２を組み合わせたＳＩＭＤ命令を実行すると、命令１で算出されたデータＡ（Ｉ）と命令２で算出されたデータＢ（Ｉ）が、ＳＩＭＤレジスタｓ１に格納される。一方で、命令４はデータＡ（Ｉ），Ｖ（Ｉ）を参照し、命令５はデータＡ（Ｉ），Ｂ（Ｉ）を参照する。そのため、命令４，５を組み合わせたＳＩＭＤ命令を実行するには、データＡ（Ｉ），Ａ（Ｉ）を同じＳＩＭＤレジスタに格納し、データＶ（Ｉ），Ｂ（Ｉ）を同じＳＩＭＤレジスタに格納しておくことになる。よって、２つのＳＩＭＤ命令の間に転送命令が挿入される。図７の例では、データＡ（Ｉ）がＳＩＭＤレジスタｓ１からＳＩＭＤレジスタｓ４に転送され、ＳＩＭＤレジスタｓ１のスロット１にデータＶ（Ｉ）がロードされている。

以上のようなＳＩＭＤレジスタ間のデータ転送は、レベルが異なる命令１，３を組み合わせてＳＩＭＤ化し、レベルが異なる命令５，７を組み合わせてＳＩＭＤ化すれば発生しない。このように、命令依存グラフ３０において、同じレベルの命令同士を比較するだけでは、最適な命令の組み合わせを発見できない可能性がある。また、命令間の依存関係によっては、同じ種類の演算を行う命令が同じレベルに存在するとは限らない。これに対して、中間コードにおいて一定の範囲内にある命令の間の組み合わせを全通り試して、最適な組み合わせを探す方法も考えられる。しかし、命令組を全探索する方法は、一定範囲にある命令の数をＮとすると計算量がＯ（Ｎ^N）と大きくなってしまう。

そこで、最適化部１２５は、以下に説明するような方法で命令組を探索する。
図８は、ソースコードの例を示す図である。ソースファイル１１１のある翻訳単位に、図８に示すような１０個の命令が含まれているとする。命令１，２，３，５，６，８，９，１０では加算（＋）が行われ、命令４，７で乗算（×）が行われる。命令４は命令１，２の演算結果を参照し、命令５は命令３，４の演算結果を参照する。命令９は命令６，７の演算結果を参照し、命令１０は命令８，９の演算結果を参照する。すなわち、命令１〜５の集合と命令６〜１０の集合とは、依存関係がなく並列に実行可能である。

図９は、演算木の第１の例を示す図である。最適化部１２５は、図８に示したソースファイル１１１から、図９のような演算木３１，３２を生成する。演算木３１，３２は、各命令で行われる演算、各命令で参照されるデータ、各命令によって定義される（算出される）データの間の関係を、木構造で表したものである。演算木３１，３２のリーフ（葉）には、一連の演算の出発点となるデータが記載され、ルート（根）には、一連の演算の結果として定義されるデータが記載される。上位のレベルの演算が下位のレベルの演算の結果を参照することで、リーフからルートに向かって演算が進行する。

演算木３１は命令１〜５に基づいて生成され、演算木３２は命令６〜１０に基づいて生成される。上記の通り、命令１〜５の集合と命令６〜１０の集合の間には依存関係がないため、演算木３１と演算木３２とは別個の木として生成されている。演算木３１に属する命令と演算木３２に属する命令とは、並列に実行することが可能である。そこで、最適化部１２５は、演算木３１，３２を用いて、ＳＩＭＤ化する命令の組を決定する。

ＳＩＭＤ化できる命令組を探すにあたり、最適化部１２５は、演算木３１，３２をそれぞれ演算列に変換する。まず、最適化部１２５は、演算木３１，３２のノードを、帰り掛け深さ優先探索または帰り掛け幅優先探索の方法で辿る。帰り掛け深さ優先探索で演算木３１のノードを辿ると、Ｅ（Ｉ），Ｆ（Ｉ），＋，Ａ（Ｉ），Ｂ（Ｉ），＋，Ｃ（Ｉ），Ｄ（Ｉ），＋，×，＋という記号列が生成される。ただし、ここでは定義側のデータの記載は省略している。同様に、帰り掛け深さ優先探索で演算木３２のノードを辿ると、Ｅ（Ｉ＋１），Ｆ（Ｉ＋１），＋，Ａ（Ｉ＋１），Ｂ（Ｉ＋１），＋，Ｃ（Ｉ＋１），Ｄ（Ｉ＋１），×，＋，＋という記号列が生成される。ここで生成される記号列は、一連の演算を逆ポーランド記法（後置記法）で記述したものに相当する。

そして、最適化部１２５は、演算木３１，３２それぞれから生成した記号列から、演算（＋，−，×，÷など）のみを抽出し演算列とする。すなわち、演算木３１に対応する演算列は＋＋＋×＋となり、演算木３２に対応する演算列は＋＋×＋＋となる。最適化部１２５は、演算木３１，３２から生成した２つの演算列のＬＣＳを算出することで、演算木３１の命令と演算木３２の命令との間の組み合わせの候補を求める。

図１０は、ＬＣＳデータの例を示す図である。ＬＣＳは、２つの系列の中に共通に含まれる部分列のうち最も長いものであり、ここで言う部分列とは、ある系列から順序を変更せずに１またはそれ以上の要素を取り出したものである。最適化部１２５は、２つの演算列の間のＬＣＳを算出し、ＬＣＳを列挙したＬＣＳデータ１４１を生成する。

演算木３１に対応する演算列１＝＋＋＋×＋と演算木３２に対応する演算列２＝＋＋×＋＋の間のＬＣＳは、長さが４であり、７通り存在する。７通りのＬＣＳうち、１つは＋＋＋＋というパターンであり、残り６つは＋＋×＋というパターンである。

（１）演算列１の１，２，３，５番目と演算列２の１，２，４，５番目とを選択する。これは、命令３，８、命令１，６、命令２，９、命令５，１０の組み合わせを意味する。
（２）演算列１の１，２，４，５番目と演算列２の１，２，３，４番目とを選択する。これは、命令３，８、命令１，６、命令４，７、命令５，９の組み合わせを意味する。

（３）演算列１の１，２，４，５番目と演算列２の１，２，３，５番目とを選択する。これは、命令３，８、命令１，６、命令４，７、命令５，１０の組み合わせを意味する。
（４）演算列１の２，３，４，５番目と演算列２の１，２，３，４番目とを選択する。これは、命令１，８、命令２，６、命令４，７、命令５，９の組み合わせを意味する。

（５）演算列１の２，３，４，５番目と演算列２の１，２，３，５番目とを選択する。これは、命令１，８、命令２，６、命令４，７、命令５，１０の組み合わせを意味する。
（６）演算列１の１，３，４，５番目と演算列２の１，２，３，４番目とを選択する。これは、命令３，８、命令２，６、命令４，７、命令５，９の組み合わせを意味する。

（７）演算列１の１，３，４，５番目と演算列２の１，２，３，５番目とを選択する。これは、命令３，８、命令２，６、命令４，７、命令５，１０の組み合わせを意味する。
図１１は、ＬＣＳの算出方法の例を示す図である。最適化部１２５は、例えば、動的計画法に基づいて、図１１に示すようなマトリクスＭを作成してＬＣＳを算出する。まず、演算列１を第１行〜第５行に対応付け、演算列２を第１列〜第５列に対応付ける。また、第０行の各欄（Ｍ［０，０］〜Ｍ[０，５]）と第０列の各欄（Ｍ［０，０］〜Ｍ［５，０］）の値を全て０に設定する。そして、次のルールに従って、マトリクスＭの左上（Ｍ［１，１］）から右下（Ｍ［５，５］）に向かって各欄の値を計算していく。

Ｍ［ｉ，ｊ］の値は、演算列１のｉ番目の演算と演算列２のｊ番目の演算が一致している場合、（ａ１）左上の欄Ｍ［ｉ−１，ｊ−１］の値＋１，（ｂ１）左の欄Ｍ［ｉ，ｊ−１］の値，（ｃ１）上の欄Ｍ［ｉ−１，ｊ］の値の中から、最も大きいものを選択する。また、演算列１のｉ番目の演算と演算列２のｊ番目の演算が異なる場合、（ａ２）左上の欄Ｍ［ｉ−１，ｊ−１］の値，（ｂ２）左の欄Ｍ［ｉ，ｊ−１］の値，（ｃ２）上の欄Ｍ［ｉ−１，ｊ］の値の中から、最も大きいものを選択する。

上記のルールで算出されるＭ［５，５］の値が、演算木３１，３２の間のＬＣＳの長さを示す。そして、Ｍ［５，５］からマトリクスＭの左上に向かって、Ｍ［５，５］の値が算出されたときのパスを逆方向に辿ることで、ＬＣＳを算出することができる。ＬＣＳに含まれる演算は、Ｍ［５，５］から左上に向かってパスを辿ったときに、値が減少する直前の欄の行・列に対応付けられている演算である。例えば、Ｍ［４，３］＝３からＭ［３，２］＝２を辿った場合、Ｍ［４，３］に対応する演算×がＬＣＳに含まれる。

ＬＣＳの長さが４であることは、最大で、演算木３１に属する４つの命令と演算木３２に属する４つの命令とを組み合わせて４つのＳＩＭＤ命令を生成できることを意味する。上記の７通りのＬＣＳが示す命令の組み合わせのパターンは、ＳＩＭＤ命令に変換できる命令の数に差異がない。ただし、７通りの組み合わせパターンの何れを採用するかによって、生成されるオブジェクトコードの実行効率に違いが生じる。また、４つの命令組をＳＩＭＤ化できる場合であっても、そのうち一部の命令組をＳＩＭＤ化しない方が、生成されるオブジェクトコードの実行効率が高くなる場合もある。

図１２は、ＳＩＭＤレジスタの第１の割り当て例を示す図である。ここでは、上記の１番目の組み合わせパターンを採用し、４つの命令組を全てＳＩＭＤ化した場合を考える。図１２に示すように、４つのＳＩＭＤ命令を実行するために、１２個のＳＩＭＤレジスタが使用される。また、命令１，６から生成された２番目のＳＩＭＤ命令と、命令２，９から生成された３番目のＳＩＭＤ命令の間に、転送命令が１つ挿入されている。

すなわち、ＳＩＭＤ化による命令の減少数が４である一方、転送命令の発生による命令の増加数が１であるため、転送命令による損失なしにＳＩＭＤ化できた命令の数（実効ＳＩＭＤ化数）は３である。ここで、もし命令２，９をＳＩＭＤ化しなければ（３番目のＳＩＭＤ命令ｓ１１＝ｓ１０＋ｓ７を生成しなければ）、転送命令は発生しない。

図１３は、ＳＩＭＤレジスタの第２の割り当て例を示す図である。ここでは、上記の１番目の組み合わせパターンに含まれる４つの命令組のうち、命令２，９をＳＩＭＤ化せずに、残りの３つの命令組をＳＩＭＤ化した場合を考える。図１３のＳＩＭＤ化方法では、使用されるＳＩＭＤレジスタの数および命令の総数は、図１２の場合と同じである。ただし、図１３のＳＩＭＤ化方法では、ＳＩＭＤ命令間に転送命令が挿入されていない。転送命令が存在すると、転送命令とその前後にあるＳＩＭＤ命令の間に依存関係が生じることから、命令の実行順序に制約が生じ、オブジェクトコードの実行効率が低下するおそれがある。よって、図１３のＳＩＭＤ化方法の方が、図１２よりも有利であると言える。

図１４は、ＳＩＭＤレジスタの第３の割り当て例を示す図である。ここでは、上記の２番目の組み合わせパターンを採用し、４つの命令組を全てＳＩＭＤ化した場合を考える。図１４のＳＩＭＤ化方法では、使用されるＳＩＭＤレジスタの数は１２であり、命令の総数は８である。また、転送命令が２個挿入されており、実効ＳＩＭＤ化数は２である。従って、図１４のＳＩＭＤ化方法は、図１２，１３のＳＩＭＤ化方法より不利である。

以上のように、最適化部１２５は、算出されたＬＣＳが示す命令の組み合わせパターンそれぞれについて、当該組み合わせパターンに含まれる一部または全部の命令組をＳＩＭＤ化した場合の、プロセッサのリソースの使用状況を評価する。最適化部１２５は、リソースの使用状況が最も有利なＳＩＭＤ化方法を採用すればよい。リソースの使用状況を評価するための評価指標としては、使用するＳＩＭＤレジスタの数、命令の総数、転送命令の数、実効ＳＩＭＤ化数などを用いることができる。また、評価指標として、メモリの使用領域の大きさ、クリティカルパス（命令間の依存関係が直列的に並んだパスのうち最長のもの）の長さ、実行時間、プロセッサの消費電力などを用いることもできる。

前述の７通りの組み合わせパターンを実効ＳＩＭＤ化数の観点から評価すると、１番目および３番目の組み合わせパターンが最適であると判定される。なお、以上説明した例では、四則演算（加算・減算・乗算・除算）を行う命令をＳＩＭＤ化したが、他の種類の演算やメモリアクセスを行う命令をＳＩＭＤ化することもできる。また、以上説明した例では、形状が同じ演算木３１，３２からＳＩＭＤ化する命令組を決定したが、形状が異なる２つの演算木からＳＩＭＤ化する命令組を決定することもできる。

図１５は、演算木の第２の例を示す図である。演算木３３は命令１１〜１７に基づいて生成される。命令１１，１３，１４，１５，１７では加算（＋）が行われ、命令１２，１６では乗算（×）が行われる。命令１３は命令１１，１２の演算結果を参照し、命令１６は命令１３，１４の演算結果を参照し、命令１７は命令１５，１６の演算結果を参照する。演算木３２に属する命令と演算木３３に属する命令の間には、依存関係がない。

演算木３２，３３から、上記の演算木３１，３２の場合と同様の方法でＳＩＭＤ化する命令組を探索すると、次の５つの命令組が選択される：命令６，１１、命令７，１２、命令９，１３、命令８，１５、命令１０，１７。このように、最適化部１２５は、異なる形状の２つの演算木から、ＳＩＭＤ化する命令組を探索できる。このとき、異なるレベルにある命令の組が、ＳＩＭＤ化する命令組として選択されることがある。

次に、一部のプロセッサのアーキテクチャでサポートされているクロスＦＭＡ（Fused Multiply and Add）命令について説明する。ＦＭＡ命令は、乗算と加算または減算とを組み合わせた演算を指定する命令である。例えば、Ａ×Ｂ＋Ｃという演算を、１つのＦＭＡ命令で指定することができる。演算の種類が同じ２以上のＦＭＡ命令を組み合わせてＳＩＭＤ命令に変換することもできる。例えば、Ａ×Ｂ＋ＣというＦＭＡ命令とＸ×Ｙ＋ＺというＦＭＡ命令を、１つのＳＩＭＤ命令に変換することができる。

クロスＦＭＡ命令は、ＦＭＡ命令から生成されたＳＩＭＤ命令を拡張したものである。クロスＦＭＡ命令では、転送命令がなくても仮想的にスロット間でデータの転送やコピーが行われたものと仮定して、当該データに対して演算が行われる。例えば、Ａ×Ｂ＋Ｃ，Ｘ×Ｙ＋Ｃという演算をクロスＦＭＡ命令で指定すると、データＣをコピーしておかなくても、クロスＦＭＡ命令の中でデータＣが仮想的にコピーされたものとして扱われる。

実行ファイル１１３が、クロスＦＭＡ命令をサポートするプロセッサに実行させるものである場合、クロスＦＭＡ命令を利用することで、ＳＩＭＤ化に伴う転送命令の発生を回避できることがある。そこで、最適化部１２５は、クロスＦＭＡ命令を利用可能であるか否かを考慮して、各ＳＩＭＤ化方法に対応するリソースの使用状況を評価する。なお、ＦＭＡ命令でない命令を組み合わせてクロスＦＭＡ命令を生成するには、乗算対象のデータの１つを“１”にするか、加算対象のデータの１つを“０”にすればよい。

図１６は、クロスＦＭＡ命令の実行例を示す図である。ここでは、ソースコードに次の４つの命令が含まれている場合を考える。命令１：Ｃ２．ｒｅａｌ＝Ｃ１．ｒｅａｌ＋Ｒ１，命令２：Ｃ２．ｉｍｇ＝Ｃ１．ｉｍｇ＋Ｒ１，命令３：Ｃ３．ｒｅａｌ＝Ｃ２．ｒｅａｌ×Ｒ２，命令４：Ｃ３．ｉｍｇ＝Ｃ２．ｉｍｇ×Ｒ２。

命令１はＣ２．ｒｅａｌ＝Ｃ１．ｒｅａｌ×１．０＋Ｒ１と解釈し、命令２はＣ２．ｉｍｇ＝Ｃ１．ｉｍｇ×１．０＋Ｒ１と解釈することで、ＦＭＡ命令に置き換えられる。また、命令３はＣ３．ｒｅａｌ＝Ｃ２．ｒｅａｌ×Ｒ２＋０と解釈し、命令４はＣ３．ｉｍｇ＝Ｃ２．ｉｍｇ×Ｒ２＋０と解釈することで、ＦＭＡ命令に置き換えられる。そこで、命令１，２および命令３，４の組から、クロスＦＭＡ命令を生成することにする。

例えば、ＳＩＭＤレジスタｓ１にＣ１．ｒｅａｌ，Ｃ１．ｉｍｇを格納し、ＳＩＭＤレジスタｓ２にＲ１，Ｒ２を格納し、ＳＩＭＤレジスタｓ３に１．０，１．０を格納する。この状態で、命令１，２から生成されたクロスＦＭＡ命令を実行すると、ＳＩＭＤレジスタｓ２のＲ１が仮想的にコピーされたものとして扱われて、Ｃ２．ｒｅａｌ，Ｃ２．ｉｍｇが算出される。このとき、ＳＩＭＤレジスタｓ２のＲ１は、物理的に移動しているわけではない。同様に、ＳＩＭＤレジスタｓ４に０，０を格納した状態で、命令３，４から生成されたクロスＦＭＡ命令を実行すると、ＳＩＭＤレジスタｓ２のＲ２が仮想的にコピーされたものとして扱われて、Ｃ３．ｒｅａｌ，Ｃ３．ｉｍｇが算出される。このとき、ＳＩＭＤレジスタｓ２のＲ２は、物理的に移動しているわけではない。

次に、解析部１２６で実行される処理の手順について説明する。
図１７は、ＳＩＭＤ化処理の手順例を示すフローチャートである。
（ステップＳ１）解析部１２６は、中間コード記憶部１２４から、１つの翻訳単位の中間コードを読み出し、読み出した中間コードに含まれる命令の間の依存関係を解析する。そして、解析部１２６は、命令間の依存関係に従って、複数の演算木を生成する。

（ステップＳ２）解析部１２６は、ステップＳ１で生成した演算木の間の依存関係を確認する。演算木の間の依存関係は、ある演算木のルートノードと他の演算木のルートノード、および、ある演算木のリーフと他の演算木のルートノードを比較することで確認できる。

（ステップＳ３）解析部１２６は、ステップＳ１で生成した複数の演算木の間の組み合わせと、各組の演算木の中におけるＳＩＭＤ化する命令の組み合わせとを決定する。このとき、ステップＳ２で依存関係があると判断された演算木同士は、組み合わせないようにする。１つの組に属する演算木の数は、ＳＩＭＤの並列度と一致させる。ステップＳ３の処理は、以下のステップＳ３ａ，Ｓ３ｂ，Ｓ３ｃの処理を含む。

（ステップＳ３ａ）解析部１２６は、演算木の組を１つ選択する。
（ステップＳ３ｂ）解析部１２６は、ステップＳ３ａで選択した組に属する演算木それぞれを演算列に変換し、複数の演算列の間のＬＣＳを全て算出する。

（ステップＳ３ｃ）解析部１２６は、ステップＳ３ｂで算出したＬＣＳ毎に、そのＬＣＳが示す命令の組み合わせパターンを採用した場合のリソースの利用状況を評価する。そして、解析部１２６は、評価結果が最良の命令の組み合わせを選択する。

以下では、図１７に示した処理手順の実装例について説明する。まず、中間コードから演算木を生成する手順について説明する。
図１８は、中間コードの例を示す図である。中間コード１４２は、中間コード記憶部１２４に記憶される。中間コード１４２のある１つの翻訳単位には、命令１〜１２が含まれている。命令１，２，４，６，７，９は、ＲＡＭからデータを読み出すためのＬＯＡＤ命令であり、命令１２は、ＲＡＭにデータを書き込むためのＳＴＯＲＥ命令である。命令３，８はＭＵＬＴ（乗算）命令であり、命令５，１０，１１はＡＤＤ（加算）命令である。

命令３は命令１，２に依存し、命令５は命令３，４に依存し、命令８は命令６，７に依存し、命令１０は命令８，９に依存し、命令１１は命令５，１０に依存し、命令１２は命令１１に依存している。なお、図１８に記載したＲ０１，Ｒ０２，Ｒ０３，Ｒ０４，Ｒ０５，Ｒ０６，Ｒ０７，Ｒ０８，Ｒ０９，Ｒ１０，Ｒ１１は、論理的なレジスタを示す。

解析部１２６は、命令列を後方から前方に向かって走査し、命令間の依存関係を解析して演算木を生成する。上記の命令１〜１２からは１つの演算木が生成される。ここで、１つの演算木の中で表現する依存関係は、木構造にするため、ある命令により１回だけ定義され他の命令により１回だけ参照されるレジスタに関する依存関係に限定する。

図１９は、命令データと演算木データの例を示す図である。解析部１２６は、中間コード１４２から命令を１つずつ抽出して命令データ１５１を生成し、命令データ１５１を解析して命令の依存関係を判定することで演算木データ１５２を生成する。

命令データ１５１は、命令毎に、命令番号、命令名、定義オペランド、参照オペランド、前命令および後命令の項目を含む。命令番号は、各命令を識別するための番号である。命令名は、演算の種類を示す名称（ＡＤＤ，ＳＵＢ，ＭＵＬＴ，ＤＩＶなど）である。定義オペランドの項目には、中間コード１４２で使用されている論理的なレジスタの識別子であって、演算結果のデータを格納するレジスタの識別子が設定される。参照オペランドの項目には、参照されるデータを格納する１またはそれ以上のレジスタの識別子が設定される。前命令の項目には、中間コード１４２において１つ前の命令を示す命令番号が設定される。後命令の項目には、１つ後の命令を示す命令番号が設定される。

演算木データ１５２は、ノードデータおよびリーフデータを含む。
ノードデータは、ノード番号、命令番号、親ノード番号および子ノード番号の項目を含む。ノード番号は、演算木の各ノードを識別するための番号である。命令番号は、命令データ１５１に含まれるものと同じである。命令番号によって、命令データ１５１と演算木データ１５２とが関連付けられる。親ノード番号は、自ノードの命令の定義オペランドを参照している他の命令に対応するノード番号である。子ノード番号は、自ノードの命令の参照オペランドを定義した他の命令に対応するノード番号である。親ノード番号と子ノード番号によって、複数のノードに対応するノードデータが相互に関連付けられる。

リーフデータは、リーフ番号、オペランドおよび親ノード番号の項目を含む。リーフ番号は、演算木の各リーフを識別するための番号である。オペランドの項目には、データをレジスタにロードするときにアクセスするＲＡＭの記憶領域を示す識別子が設定される。親ノード番号は、そのリーフと依存関係にあるノードに対応するノード番号である。

図２０は、演算木リストの例を示す図である。解析部１２６は、演算木データ１５２を含む複数の演算木に相当する演算木データから、演算木リスト１５３を生成する。演算木リスト１５３は、演算木毎に、演算木番号、ルートノード番号、ルート命令番号、ノード数およびリーフ数の項目を含む。演算木番号は、各演算木を識別するための番号である。ルートノード番号は、演算木のルートノードに付与された番号である。ルート命令番号は、ルートノードに対応する命令を示す命令番号である。ノード数は、演算木に含まれるノードの数である。リーフ数は、演算木に含まれるリーフの数である。

図２１は、演算木生成処理の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ１において実行される。
（ステップＳ１１１）解析部１２６は、翻訳単位内の命令列の後方から優先的に、命令を１つ選択する。（ステップＳ１１２）解析部１２６は、選択した命令が既に何れかの演算木に属しているか判断する。命令が何れかの演算木に属する場合、処理をステップＳ１１１に進め、それ以外の場合は処理をステップＳ１１３に進める。（ステップＳ１１３）解析部１２６は、選択した命令で行う演算が、ＳＩＭＤ化の対象となる演算であるか判断する。ＳＩＭＤ化対象とならない演算には、例えば、分岐命令やバリア命令などの制御命令が含まれる。ＳＩＭＤ化対象となる演算である場合、処理をステップＳ１１４に進め、ＳＩＭＤ化対象とならない演算である場合、処理をステップＳ１２４に進める。

（ステップＳ１１４）解析部１２６は、ステップＳ１１１で選択した命令に対応するノードを、ルートノードとして生成する。また、解析部１２６は、選択した命令の参照オペランドを抽出する。（ステップＳ１１５）解析部１２６は、未処理の参照オペランドを１つ選択する。（ステップＳ１１６）解析部１２６は、命令データ１５１から、選択した参照オペランドと同じレジスタを定義オペランドにもつ他の命令（定義命令）を検索する。（ステップＳ１１７）解析部１２６は、ステップＳ１１５で選択した参照オペランドであるレジスタが、翻訳単位内で、１つの命令によって１回だけ定義され、１つの命令によって１回だけ参照されるものであるか判断する。条件を満たす場合は処理をステップＳ１１８に進め、条件を満たさない場合は処理をステップＳ１２０に進める。

（ステップＳ１１８）解析部１２６は、ステップＳ１１５で選択した参照オペランドをもつ命令（参照命令）と定義命令との間の依存関係が、複数の演算木を跨がる依存関係であるか判断する。条件を満たす場合は処理をステップＳ１２０に進め、条件を満たさない場合は処理をステップＳ１１９に進める。（ステップＳ１１９）解析部１２６は、ステップＳ１１６で検索された定義命令に対応するノードを生成し、処理をステップＳ１２１に進める。また、解析部１２６は、定義命令から参照オペランドを抽出する。（ステップＳ１２０）解析部１２６は、ステップＳ１１５で選択した参照オペランドに対応するリーフを生成する。（ステップＳ１２１）解析部１２６は、参照命令に対応するノードと、定義命令に対応するノードまたはリーフの間の親子関係を、演算木データ１５２に登録する。

（ステップＳ１２２）解析部１２６は、ステップＳ１１４およびステップＳ１１９で抽出された参照オペランドが、全て処理されたか判断する。未処理の参照オペランドがある場合は処理をステップＳ１１５に進め、全ての参照オペランドを処理した場合は処理をステップＳ１２３に進める。（ステップＳ１２３）解析部１２６は、ステップＳ１１１で選択した命令をルートとする演算木が完成したと判断し、完成した演算木を演算木リスト１５３に登録する。（ステップＳ１２４）解析部１２６は、翻訳単位内の全ての命令をステップＳ１１１において選択したか判断する。全ての命令を選択した場合は処理を終了し、未選択の命令がある場合は処理をステップＳ１１１に進める。

次に、演算木間の依存関係を確認する手順について説明する。
図２２は、演算木の間の依存関係の例を示す図である。演算木間の依存関係は、一方の演算木に属する命令と他方の演算木に属する命令との間に実行順序の制約がある関係であり、一方の演算木に属する命令で定義されるレジスタが、他の演算木に属する命令で参照される関係を含む。ここでは、演算木Ａ，Ｂ，Ｃ，Ｄが生成された場合を考える。

演算木Ａのリーフの参照オペランドはｍｅｍ０１，ｍｅｍ０２であり、演算木Ａのルートノードの定義オペランドはＲ０３である。演算木Ｂのリーフの参照オペランドはｍｅｍ０５であり、演算木Ｂのルートノードの定義オペランドはＲ０８である。演算木Ｃのリーフの参照オペランドはｍｅｍ０３，ｍｅｍ０４であり、演算木Ｃのルートノードの定義オペランドはｍｅｍ０５である。演算木Ｄのリーフの参照オペランドはＲ０３，Ｒ０８であり、演算木Ｄのルートノードの定義オペランドはｍｅｍ０７である。中間コード１４２では、演算木Ａ，Ｂ，Ｃ，Ｄの順に命令が並んでいるとする。

上記の図２１の手順で演算木を生成した場合、解析部１２６は、各演算木のルートノードの定義オペランドとリーフの参照オペランドを確認すれば、依存関係を確認できる。２つの演算木のルートノードの定義オペランドが同じであるか、または、一方の演算木のリーフの参照オペランドと他方の演算木のルートノードの定義オペランドとが同じであるとき、２つの演算木は依存関係をもつ。図２２の例の場合、演算木Ｃは演算木Ａ，Ｂの両方に依存し、演算木Ｄも演算木Ａ，Ｂの両方に依存する。演算木Ｃ，Ｄの間には依存関係がないため、演算木Ｃの命令と演算木Ｄの命令は並列に実行できる。なお、３つ以上の演算木の間の依存関係には、推移律が成立する。例えば、演算木Ｃに依存する演算木Ｅが存在する場合、この演算木Ｅは演算木Ａにも依存していると言える。

図２３は、依存判定処理の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ２において実行される。
（ステップＳ１３１）解析部１２６は、複数の演算木のうち、演算木番号の小さいものを優先的に、演算木＃１として１つ選択する。（ステップＳ１３２）解析部１２６は、複数の演算木のうち、演算木＃１より演算木番号の大きいものを、演算木＃２として１つ選択する。（ステップＳ１３３）解析部１２６は、演算木＃１，＃２のルートノードの定義オペランドが同一であるか判断する。同一である場合は処理をステップＳ１３５に進め、同一でない場合は処理をステップＳ１３４に進める。（ステップＳ１３４）解析部１２６は、演算木＃２のリーフの参照オペランドの中に、演算木＃１のルートノードの定義オペランドが含まれているか判断する。条件を満たす場合は処理をステップＳ１３５に進め、条件を満たさない場合は処理をステップＳ１３６に進める。

（ステップＳ１３５）解析部１２６は、演算木＃１から演算木＃２への依存関係（演算木＃２が演算木＃１に依存する関係）があると判定する。（ステップＳ１３６）解析部１２６は、ステップＳ１３２において演算木＃１よりも演算木番号の大きい演算木を全て選択したか判断する。全て選択した場合は処理をステップＳ１３７に進め、未選択の演算木がある場合は処理をステップＳ１３２に進める。（ステップＳ１３７）解析部１２６は、ステップＳ１３１において全ての演算木を選択したか判断する。全て選択した場合は処理を終了し、未選択の演算木がある場合は処理をステップＳ１３１に進める。

次に、ＳＩＭＤ化する命令組を決定する手順について説明する。
図２４は、演算木組データと命令組データの例を示す図である。解析部１２６は、ＳＩＭＤ化する命令組を決定すると、演算木組データ１５４および命令組データ１５５を生成する。また、解析部１２６は、ＳＩＭＤ化する命令組を探索している間、一時保存データ１５６を生成してＲＡＭ１０２上に保存しておく。

演算木組データ１５４は、演算木の組毎に、木組番号、演算木番号および命令組番号の項目を含む。木組番号は、演算木の組を識別するための番号である。演算木番号の項目には、組み合わせた各演算木を識別するための番号が列挙される。列挙される演算木番号の数は、ＳＩＭＤの並列度に一致する。命令組番号の項目には、命令組データ１５５で定義された命令組番号のうち、その演算木の組についての命令組を示す命令組番号が列挙される。演算木組データ１５４と命令組データ１５５とは、命令組番号で関連付けられる。

命令組データ１５５は、命令の組毎に、命令組番号、命令番号およびＳＩＭＤ命令位置の項目を含む。命令組番号は、命令の組を識別するための番号である。命令番号の項目には、組み合わせた各命令を識別するための番号が列挙される。列挙される命令番号の数は、ＳＩＭＤの並列度、すなわち、演算木組データ１５４の演算木番号の項目に列挙される演算木番号の数に一致する。ＳＩＭＤ命令位置の項目には、中間コード１４２において、生成したＳＩＭＤ命令を埋め込む位置を示す情報が設定される。

一時保存データ１５６は、演算木番号、最大ＬＣＳ長および最大実効ＳＩＭＤ化数の項目を含む。演算木番号の項目は、確定前の演算木の組の候補の中で、現時点で最良と判断した演算木の組を示す。以下の説明では、実効ＳＩＭＤ化数を用いて演算木の組の優劣を評価するものとする。最大ＬＣＳ長は、最良と判断した演算木の組のＬＣＳ長である。最大実効ＳＩＭＤ化数は、最良と判断した演算木の組についての実効ＳＩＭＤ化数のうち、最良な命令の組み合わせパターンを選択したときの値（最大値）である。

図２５は、命令組判定処理の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ３において実行される。
（ステップＳ１４１）解析部１２６は、生成された演算木が、全ての組み合わせを探索できる程度の量であるか、すなわち、演算木の数が閾値以下であるか判断する。閾値は、端末装置１００の計算能力に応じて変更してもよい。演算木の数が閾値以下の場合は処理をステップＳ１４４に進め、閾値を超える場合は処理をステップＳ１４２に進める。（ステップＳ１４２）解析部１２６は、後述する方法により、ノード数の多い演算木から優先的に他の演算木との間のＬＣＳを算出し、演算木の組を１つ決定する。（ステップＳ１４３）解析部１２６は、全ての演算木を処理したか判断する。全ての演算木を処理した場合は処理を終了し、未処理の演算木がある場合は処理をステップＳ１４２に進める。

（ステップＳ１４４）解析部１２６は、演算木の組み合わせパターンを全て算出する。例えば、ＳＩＭＤの並列度が２である場合、演算木を２個ずつ組にするパターンを全て算出する。（ステップＳ１４５）解析部１２６は、ステップＳ１４４で算出したパターンを１つ選択する。（ステップＳ１４６）解析部１２６は、選択した演算木の組み合わせパターンについて、最適な命令の組み合わせを選択した場合の実効ＳＩＭＤ化数を算出する。この処理は、後述するＬＣＳマッチング処理のアルゴリズムの一部を用いて実現される。

（ステップＳ１４７）解析部１２６は、ステップＳ１４６で算出した実効ＳＩＭＤ化数が、現時点の最大実効ＳＩＭＤ化数以上である場合、最大実効ＳＩＭＤ化数を更新する。（ステップＳ１４８）解析部１２６は、ステップＳ１４５で全ての演算木の組み合わせパターンを選択したか判断する。全て選択した場合は処理をステップＳ１４９に進め、未選択のパターンがある場合は処理をステップＳ１４５に進める。（ステップＳ１４９）解析部１２６は、最大実効ＳＩＭＤ化数が算出されたときの演算木の組み合わせ、および、その演算木の組み合わせ内での命令の組み合わせを採用する。

図２６は、ＬＣＳマッチング処理の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ１４２において実行される。また、ステップＳ１５３〜Ｓ１６１の処理は、前述のステップＳ１４６でも利用される。なお、図２６に示す処理ではＳＩＭＤの並列度が２である場合を考える。

（ステップＳ１５１）解析部１２６は、演算木組データ１５４に未登録の演算木（まだ他の演算木と組み合わせることが決定していない演算木）の中から、ノード数が最大のもの１つを演算木＃１として選択する。解析部１２６は、演算木＃１を選択する毎に、前述の一時保存データ１５６を初期化する。（ステップＳ１５２）解析部１２６は、演算木＃１以外の演算木であって、演算木組データ１５４に未登録の演算木の中から、ノード数の多い方から優先的に１つを演算木＃２として選択する。

（ステップＳ１５３）解析部１２６は、演算木＃１，＃２の間に依存関係があるか判断する。依存関係がある場合は処理をステップＳ１６２に進め、依存関係がない場合は処理をステップＳ１５４に進める。（ステップＳ１５４）解析部１２６は、演算木＃２のノード数が、現時点の最大ＬＣＳ長以上であるか判断する。ノード数が最大ＬＣＳ長以上の場合は処理をステップＳ１５５に進め、最大ＬＣＳ長未満の場合は処理をステップＳ１６２に進める。（ステップＳ１５５）解析部１２６は、演算木＃１，＃２の間のＬＣＳを算出する。（ステップＳ１５６）解析部１２６は、算出したＬＣＳの長さが、現時点の最大ＬＣＳ長以上であるか判断する。ＬＣＳ長が最大ＬＣＳ長以上の場合は処理をステップＳ１５７に進め、最大ＬＣＳ長未満の場合は処理をステップＳ１６２に進める。

（ステップＳ１５７）解析部１２６は、ステップＳ１５５で算出したＬＣＳを１つ選択する。（ステップＳ１５８）解析部１２６は、後述する方法により、選択したＬＣＳが示す演算木＃１，＃２の間の命令の組み合わせパターンについて、１またはそれ以上の命令組を採用して実効ＳＩＭＤ化数を算出する。（ステップＳ１５９）解析部１２６は、ステップＳ１５８で算出した実効ＳＩＭＤ化数が、現時点の最大実効ＳＩＭＤ化数以上であるか判断する。実効ＳＩＭＤ化数が最大実効ＳＩＭＤ化数以上の場合は処理をステップＳ１６０に進め、最大実効ＳＩＭＤ化数未満の場合は処理をステップＳ１６１に進める。

（ステップＳ１６０）解析部１２６は、演算木＃１，＃２の組を一時保存データ１５６に登録し、最大ＬＣＳ長と最大実効ＳＩＭＤ化数を更新する。また、解析部１２６は、ステップＳ１５８で実効ＳＩＭＤ化数を算出するにあたって採用した命令の組を保存しておく。（ステップＳ１６１）解析部１２６は、ステップＳ１５７で全てのＬＣＳを選択したか判断する。全て選択した場合は処理をステップＳ１６２に進め、未選択のＬＣＳがある場合は処理をステップＳ１５７に進める。（ステップＳ１６２）解析部１２６は、ステップＳ１５２で条件に当てはまる全ての演算木を選択したか判断する。全て選択した場合は処理をステップＳ１６３に進め、未選択の演算木がある場合は処理をステップＳ１５２に進める。（ステップＳ１６３）解析部１２６は、一時保存データ１５６の演算木組および最良の１またはそれ以上の命令組を、演算木組データ１５４に登録する。

図２７は、ＳＩＭＤ化数解析処理の第１の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ１５８において実行される。
（ステップＳ１７１）解析部１２６は、ＬＣＳに基づいて、演算木＃１に属する命令と演算木＃２に属する命令との組を１つ選択する。（ステップＳ１７２）解析部１２６は、ステップＳ１７１で選択した命令組を仮にＳＩＭＤ命令に変換する。（ステップＳ１７３）解析部１２６は、ステップＳ１７２の変換を行った後の中間コードについて、プロセッサのリソースの使用状況を評価し、変換前のリソースの使用状況と比較する。前述のように、リソースの使用状況として、例えば、ＳＩＭＤレジスタの数、命令の総数、転送命令の数などを評価する。リソースの使用状況を評価するため、解析部１２６は、例えば、ＳＩＭＤレジスタの割り当てをシミュレーションする。

（ステップＳ１７４）解析部１２６は、ステップＳ１７２の変換によってリソースの使用状況が悪化したか（例えば、命令の総数や転送命令の数が増加したか）判断する。悪化した場合は処理をステップＳ１７６に進め、悪化していない場合は処理をステップＳ１７５に進める。（ステップＳ１７５）解析部１２６は、ＬＣＳが示す命令の組み合わせパターンの実効ＳＩＭＤ化数を１増加させる。（ステップＳ１７６）解析部１２６は、ステップＳ１７２のＳＩＭＤ命令への変換をキャンセルする。（ステップＳ１７７）解析部１２６は、ステップＳ１７１でＬＣＳが示す全ての命令組を選択したか判断する。全て選択した場合は処理を終了し、未選択の命令組がある場合は処理をステップＳ１７１に進める。

以上のようにして、解析部１２６は、ＬＣＳが示す命令の組み合わせパターン毎に、実効ＳＩＭＤ化数が最大になるように、１またはそれ以上の命令の組を採用する。ただし、ＳＩＭＤの並列度が２であり、リソースの使用状況として転送命令の数を評価すればよい場合、上記のステップＳ１７３の処理を簡略化することも可能である。

図２８は、ＳＩＭＤ化数解析処理の第２の手順例を示すフローチャートである。このフローチャートが示す処理は、図２７の処理に代えて実行できる。
（ステップＳ１８１）解析部１２６は、ＬＣＳに基づいて、演算木＃１に属する命令と演算木＃２に属する命令との組を１つ選択する。（ステップＳ１８２）解析部１２６は、命令組の一方の命令に含まれるオペランドと他方の命令に含まれるオペランドの組を１つ選択する。ここで選択するオペランドには、参照オペランドと定義オペランドの両方が含まれる。（ステップＳ１８３）解析部１２６は、ステップＳ１８２で選択した２つのオペランドの少なくとも一方が、採用することが既に決定された命令組に出現するオペランドであるか判断する。出現済のオペランドである場合は処理をステップＳ１８４に進め、未出現のオペランドである場合は処理をステップＳ１８９に進める。

（ステップＳ１８４）解析部１２６は、ステップＳ１８２で選択したオペランド組が、出現済のオペランド組と同じ組み合わせ方であるか判断する。組み合わせ方が同じ場合は処理をステップＳ１８９に進め、組み合わせ方が異なる場合は処理をステップＳ１８５に進める。（ステップＳ１８５）解析部１２６は、選択した各オペランドに割り当てられるスロットが、前に割り当てられたスロットと同じであるか判断する。同じ場合は処理をステップＳ１８７に進め、異なる場合は処理をステップＳ１８６に進める。

（ステップＳ１８６）解析部１２６は、生成されるオブジェクトコードでクロスＦＭＡ命令を利用可能か（クロスＦＭＡ命令をサポートするプロセッサ用のオブジェクトコードか）判断する。クロスＦＭＡ命令を利用可能な場合は処理をステップＳ１８９に進め、利用可能でない場合は処理をステップＳ１９１に進める。（ステップＳ１８７）解析部１２６は、選択したオペランドが後続の命令で参照されるか、すなわち、後続の命令と依存関係があるか判断する。依存関係がある場合は処理をステップＳ１９１に進め、依存関係がない場合は処理をステップＳ１８８に進める。（ステップＳ１８８）解析部１２６は、ステップＳ１８７の判定が、選択した命令組について１回目か判断する。１回目の場合は処理をステップＳ１８９に進め、１回目でない場合は処理をステップＳ１９１に進める。

（ステップＳ１８９）解析部１２６は、ステップＳ１８２で全てのオペランド組を選択したか判断する。全て選択した場合は処理をステップＳ１９０に進め、未選択のオペランド組がある場合は処理をステップＳ１８２に進める。（ステップＳ１９０）解析部１２６は、ＬＣＳが示す命令の組み合わせパターンについての実効ＳＩＭＤ化数を１増加させ、処理をステップＳ１９２に進める。（ステップＳ１９１）解析部１２６は、ステップＳ１８１で選択した命令組のＳＩＭＤ化をキャンセルする。（ステップＳ１９２）解析部１２６は、ステップＳ１８１で全ての命令組を選択したか判断する。全て選択した場合は処理を終了し、未選択の命令組がある場合は処理をステップＳ１８１に進める。

第２の実施の形態の端末装置１００によれば、複数の演算木それぞれを演算列に変換してＬＣＳを算出することで、命令組が最も多くなるような演算木の間の命令の組み合わせパターンを特定できる。このとき、演算木の形状が同じでなくてもよく、また、組み合わせるべき２つの命令が演算木の同じレベルに存在していなくてもよい。また、リソースの使用状況が最も有利になるように、ＬＣＳおよび採用する命令組が選択される。これにより、コンパイラ１２０の最適化処理を効率的に実行できる。

なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現でき、第２の実施の形態の情報処理は、端末装置１００にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。

プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置（例えば、ＨＤＤ１０３）に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。

１０ 情報処理装置
１１ 記憶部
１１ａ 第１のコード
１１ｂ 第２のコード
１２ 演算部
１３ａ，１３ｂ 演算木
１４ａ，１４ｂ 演算列
１５ａ，１５ｂ 最長サブ演算列

Claims (6)

1. 第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成するためのプログラムであって、コンピュータに、
   前記第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、前記第１の演算木の各命令で指定された演算を前記第１の演算木の構造に応じた順序で並べた第１の演算列と、前記第２の演算木の各命令で指定された演算を前記第２の演算木の構造に応じた順序で並べた第２の演算列とを算出し、
   前記第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、前記第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出し、
   ２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する前記第１の演算木の命令と前記第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する、
   処理を実行させるプログラム。
2. 前記計算リソースの使用状況の評価では、前記第２のコードに、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を挿入することに伴って生成される、当該特定命令で参照されるデータをレジスタ間で転送するための転送命令の数を評価する、請求項１記載のプログラム。
3. 前記計算リソースの使用状況の評価では、前記第１のコードに含まれる命令を、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令に変換することによる命令の減少量と、前記転送命令が生成されることによる命令の増加量とに応じた指標値を算出する、請求項２記載のプログラム。
4. 前記計算リソースの使用状況の評価では、前記第２のコードを実行するプロセッサが、前記転送命令が入力されなくても仮想的にレジスタ間でデータが転送されたと扱って当該データに対して演算を行うクロス演算命令をサポートしているか判定し、判定結果に応じて、生成される前記転送命令の数を評価する、請求項２または３記載のプログラム。
5. 第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成する、コンピュータが実行するコード生成方法であって、
   前記第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、前記第１の演算木の各命令で指定された演算を前記第１の演算木の構造に応じた順序で並べた第１の演算列と、前記第２の演算木の各命令で指定された演算を前記第２の演算木の構造に応じた順序で並べた第２の演算列とを算出し、
   前記第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、前記第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出し、
   ２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する前記第１の演算木の命令と前記第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する、
   コード生成方法。
6. 第１のコードと、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を含む第２のコードとを記憶する記憶部と、
   前記第１のコードに含まれる２以上の命令を組み合わせて前記特定命令を生成することで、前記第１のコードから前記第２のコードを生成する演算部と、
   を有し、前記演算部は、
   前記第１のコードに含まれる命令の間の依存関係を示す第１および第２の演算木を生成し、前記第１の演算木の各命令で指定された演算を前記第１の演算木の構造に応じた順序で並べた第１の演算列と、前記第２の演算木の各命令で指定された演算を前記第２の演算木の構造に応じた順序で並べた第２の演算列とを算出し、
   前記第１および第２の演算列の少なくとも一方から１またはそれ以上の演算を削除することで現れる、前記第１および第２の演算列に共通のサブ演算列のうち、長さが最大である１またはそれ以上の最長サブ演算列を算出し、
   ２以上の最長サブ演算列が算出されたとき、各最長サブ演算列について、当該最長サブ演算列に含まれる各演算に該当する前記第１の演算木の命令と前記第２の演算木の命令とを組み合わせた場合の、実行時の計算リソースの使用状況を評価し、評価結果に基づいて、何れかの最長サブ演算列が示す命令の組み合わせのパターンを選択する、
   情報処理装置。

Images