(57)【特許請求の範囲】
【請求項１】
第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する１つの特定命令を生成することで、当該特定命令を含む第２のコードを生成するためのプログラムであって、コンピュータに、
第１および第２の命令を組み合わせて第１の特定命令を生成することを決定すると、前記第１のコードを前記第１および第２の命令より前方に向かって検索することで、前記第１のコードから、前記第１の命令で参照されるデータを算出する第３の命令と、前記第２の命令で参照されるデータを算出する第４の命令とを検索し、
前記第１の特定命令と異なる第２の特定命令を生成するために組み合わせる命令の候補として、前記第３および第４の命令を優先的に選択する、
処理を実行させるプログラム。
【請求項２】
前記第１および第２の命令の組み合わせは、前記第１のコードに含まれる命令列を後方から前方に向かって走査することで決定する、請求項１記載のプログラム。
【請求項３】
前記コンピュータに、更に、
他の命令と組み合わせることが既に決定している命令で参照されるデータと、前記第３および第４の命令で参照されるデータとを比較して、前記第３および第４の命令を組み合わせた場合にレジスタ間でデータを転送するための転送命令が生成されるか判定し、判定結果に応じて、前記第３および第４の命令を組み合わせるか否かを決定する、
処理を実行させる請求項１または２記載のプログラム。
【請求項４】
第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する１つの特定命令を生成することで、当該特定命令を含む第２のコードを生成する、コンピュータが実行するコード生成方法であって、
第１および第２の命令を組み合わせて第１の特定命令を生成することを決定すると、前記第１のコードを前記第１および第２の命令より前方に向かって検索することで、前記第１のコードから、前記第１の命令で参照されるデータを算出する第３の命令と、前記第２の命令で参照されるデータを算出する第４の命令とを検索し、
前記第１の特定命令と異なる第２の特定命令を生成するために組み合わせる命令の候補として、前記第３および第４の命令を優先的に選択する、
コード生成方法。
【請求項５】
第１のコードと、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を含む第２のコードとを記憶する記憶部と、
前記第１のコードに含まれる２以上の命令を組み合わせて１つの特定命令を生成することで、前記第１のコードから前記第２のコードを生成する演算部と、
を有し、前記演算部は、
第１および第２の命令を組み合わせて第１の特定命令を生成することを決定すると、前記第１のコードを前記第１および第２の命令より前方に向かって検索することで、前記第１のコードから、前記第１の命令で参照されるデータを算出する第３の命令と、前記第２の命令で参照されるデータを算出する第４の命令とを検索し、
前記第１の特定命令と異なる第２の特定命令を生成するために組み合わせる命令の候補として、前記第３および第４の命令を優先的に選択する、
情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプログラム、コード生成方法および情報処理装置に関する。
【背景技術】
【０００２】
現在、ＣＰＵ（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）などのプロセッサ以外の電子回路でもよい。プロセッサは、例えば、記憶部１１または他のメモリに記憶されたプログラムを実行する。
【００１６】
演算部１２は、まず、第１のコード１１ａから、演算の種類が同じであり依存関係がない命令１３ａ，１３ｂを検出すると、命令１３ａ，１３ｂを組み合わせてＳＩＭＤ命令１４ａを生成することを決定する。依存関係には、一方の命令が算出するデータを他方の命令が参照するという定義・参照関係が含まれる。命令１３ａ，１３ｂの組み合わせは、例えば、第１のコード１１ａの命令列を後方から前方に向かって走査し、後方の命令から優先的に組み合わせを見つけることで検出したものである。
【００１７】
次に、演算部１２は、第１のコード１１ａから、命令１３ａで参照されるデータを算出する命令１３ｃと、命令１３ｂで参照されるデータを算出する命令１３ｄとを検索する。例えば、命令１３ａがＤ１＝Ａ１×Ｅ１であり、命令１３ｂがＤ２＝Ａ２×Ｅ２であるとする。この場合、演算部１２は、例えば、データＡ１を算出する命令１３ｃとしてＡ１＝Ｂ１＋Ｃ１を検索し、データＡ２を算出する命令１３ｄとしてＡ２＝Ｂ２＋Ｃ２を検索する。第１のコード１１ａにおいて、命令１３ｃは命令１３ａより前方にあり、命令１３ｄは命令１３ｂより前方に存在することが期待される。
【００１８】
そして、演算部１２は、ＳＩＭＤ命令１４ａと異なるＳＩＭＤ命令１４ｂを生成するために組み合わせる命令の候補として、命令１３ｃ，１３ｄを他の命令よりも優先的に選択する。すると、演算部１２は、選択した命令１３ｃ，１３ｄが所定の条件を満たしているか確認し、命令１３ｃ，１３ｄからＳＩＭＤ命令１４ｂを生成するか否かを最終的に決定する。例えば、演算部１２は、命令１３ｃ，１３ｄの演算の種類が異なるか、または、命令１３ｃ，１３ｄに依存関係がある場合、命令１３ｃ，１３ｄを組み合わせないと決定する。また、例えば、演算部１２は、他の命令と組み合わせることが既に決定している命令で参照されるデータと、命令１３ｃ，１３ｄで参照されるデータとを比較して、命令１３ｃ，１３ｄを組み合わせた場合に転送命令が生成されるか判定する。演算部１２は、転送命令が生成される場合は、命令１３ｃ，１３ｄを組み合わせないと決定してもよい。
【００１９】
なお、上記で挙げた例において、命令１３ａで参照されるデータＥ１と命令１３ｂで参照されるデータＥ２の組についても、組み合わせる命令の候補を検索することが可能である。また、命令１３ｃ，１３ｄを組み合わせると決定した場合、演算部１２は、命令１３ｃ，１３ｄで参照されるデータの組（例えば、データＢ１，Ｂ２の組やデータＣ１，Ｃ２の組）に基づいて、連鎖的に、他の命令の組み合わせの候補を検索することができる。
【００２０】
第１の実施の形態の情報処理装置１０によれば、組み合わせることが既に決定した命令で参照されるデータを手掛かりに、命令間の依存関係を後方から前方に向かって辿って、次に組み合わせる命令の候補が検索される。これにより、ＳＩＭＤレジスタ間でのデータ転送を抑制できるような命令の組み合わせを検索することができ、情報処理装置１０によって生成される第２のコード１１ｂの実行効率が向上する。
【００２１】
［第２の実施の形態］
図２は、端末装置が備えるハードウェア例を示すブロック図である。第２の実施の形態の端末装置１００は、高級言語で記述されたソースコードをコンパイルして、機械可読なオブジェクトコードを生成し、複数のオブジェクトコードをリンクして、端末装置１００または他のコンピュータに実行させる実行コードを生成する。ただし、第２の実施の形態で説明するコンパイルおよびリンクは、サーバコンピュータで実行することもできる。
【００２２】
端末装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１は、第１の実施の形態の演算部１２の一例であり、ＲＡＭ１０２やＨＤＤ１０３は、第１の実施の形態の記憶部１１の一例である。
【００２３】
ＣＰＵ１０１は、プログラムの命令を実行する演算器を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、端末装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。
【００２４】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや計算に用いられるデータを一時的に記憶する揮発性メモリである。なお、端末装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数のメモリを備えてもよい。
【００２５】
ＨＤＤ１０３は、ＯＳ（Operating System）やファームウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性記憶装置である。なお、端末装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の記憶装置を備えてもよい。
【００２６】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、端末装置１００に接続されたディスプレイ２１に画像を出力する。ディスプレイ２１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００２７】
入力信号処理部１０５は、端末装置１００に接続された入力デバイス２２から入力信号を取得し、ＣＰＵ１０１に通知する。入力デバイス２２としては、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００２８】
ディスクドライブ１０６は、記録媒体２３に記録されたプログラムやデータを読み取る駆動装置である。記録媒体２３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１からの命令に従って、記録媒体２３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００２９】
通信インタフェース１０７は、ネットワーク２４を介して他のコンピュータと通信を行えるインタフェースである。通信インタフェース１０７は、有線網に接続する有線インタフェースでもよいし、無線網に接続する無線インタフェースでもよい。
【００３０】
図３は、端末装置が備えるソフトウェア例を示すブロック図である。端末装置１００は、ファイル記憶部１１０、コンパイラ１２０およびリンカ１３０を有する。ファイル記憶部１１０は、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域として実現できる。コンパイラ１２０およびリンカ１３０は、ＣＰＵ１０１が実行するプログラムのモジュールとして実現できる。ただし、コンパイラ１２０およびリンカ１３０の機能の一部または全部を、ソフトウェアでなく電子回路として実現することも可能である。
【００３１】
ファイル記憶部１１０は、ソースファイル１１１、オブジェクトファイル１１２および実行ファイル１１３を記憶する。ソースファイル１１１は、高級言語で記述されたソースコードを含む。オブジェクトファイル１１２は、ＳＩＭＤ命令を含む機械可読なオブジェクトコードを含む。実行ファイル１１３は、ＳＩＭＤ命令を解釈できる所定のアーキテクチャのプロセッサが実行できる形式のファイルである。なお、ＣＰＵ１０１は、実行ファイル１１３を実行可能であってもよいし、実行可能でなくてもよい。
【００３２】
コンパイラ１２０は、ファイル記憶部１１０からソースファイル１１１を読み出し、ソースコードをオブジェクトコードに変換して、オブジェクトファイル１１２をファイル記憶部１１０に格納する。コンパイラ１２０は、入出力制御部１２１、ファイル入力部１２２、中間コード生成部１２３、中間コード記憶部１２４、最適化部１２５、アセンブリコード生成部１２８およびファイル出力部１２９を有する。
【００３３】
入出力制御部１２１は、ファイルの種類に応じた入出力方法を選択し、ファイル入力部１２２およびファイル出力部１２９を制御する。ファイル入力部１２２は、入出力制御部１２１からの指示に応じて、ソースファイル１１１をオープンし、ソースファイル１１１からソースコードを読み出す。中間コード生成部１２３は、ファイル入力部１２２が読み出したソースコードを解析して、コンパイラ１２０の内部で利用される中間言語で記述された中間コードに変換し、中間コードを中間コード記憶部１２４に格納する。ソースコードの解析には、字句解析、構文解析、意味解析などが含まれる。中間コード記憶部１２４は、ＲＡＭ１０２に確保された記憶領域であり、中間コードを記憶する。
【００３４】
最適化部１２５は、中間コード記憶部１２４に記憶された中間コードを、実行速度が向上するように最適化する。最適化部１２５は、解析部１２６および最適化実行部１２７を有する。解析部１２６は、中間コードを解析して最適化方法を決定する。解析部１２６が行う最適化方法の決定には、中間コードに含まれる命令の中でＳＩＭＤ命令に変換する命令の組み合わせを決定することを含む。最適化実行部１２７は、解析部１２６が決定した最適化方法に従って中間コードを最適化する。最適化実行部１２７が行う最適化には、中間コードに含まれる命令をＳＩＭＤ命令に変換することを含む。
【００３５】
アセンブリコード生成部１２８は、最適化された中間コードを、低級言語であるアセンブリ言語で記述されたアセンブリコードに変換する。ファイル出力部１２９は、入出力制御部１２１からの指示に応じて、オブジェクトファイル１１２を生成する。そして、ファイル出力部１２９は、アセンブリコード生成部１２８が生成したアセンブリコードをオブジェクトコードに変換し、オブジェクトファイル１１２に書き込む。
【００３６】
リンカ１３０は、ファイル記憶部１１０からオブジェクトファイル１１２を読み出し、オブジェクトコードを解析して、参照されている他のオブジェクトファイルやライブラリを検出する。そして、リンカ１３０は、オブジェクトファイル１１２と、検出した他のオブジェクトファイルやライブラリとをリンクし、実行ファイル１１３を生成する。なお、コンパイラ１２０にリンカ１３０の機能が統合されていてもよい。
【００３７】
ここで、プロセッサ内でのＳＩＭＤ命令の実行方法について説明する。
図４は、ＳＩＭＤ命令とＳＩＭＤレジスタの関係例を示す図である。ＳＩＭＤ命令を解釈できるプロセッサは、並列に処理されるデータを組み合わせて格納するＳＩＭＤレジスタを備える。各ＳＩＭＤレジスタは、プロセッサのアーキテクチャによって決まる並列度に相当する数のサブレジスタを含む。図４は、並列度が２の場合を示している。
【００３８】
例えば、図４に示すように、Ａ＝Ｂ＋Ｃ，Ｘ＝Ｙ＋Ｚという２つの命令を１つのＳＩＭＤ命令ｓ１＝ｓ２＋ｓ３に変換した場合を考える。この場合、ＳＩＭＤレジスタｓ２のサブレジスタ１にデータＢ、ＳＩＭＤレジスタｓ２のサブレジスタ２にデータＹ、ＳＩＭＤレジスタｓ３のサブレジスタ１にデータＣ、ＳＩＭＤレジスタｓ３のサブレジスタ２にデータＺを格納しておく。すると、ＳＩＭＤ命令によって、２つの加算が並列に実行されてデータＡ，Ｘが算出され、ＳＩＭＤレジスタｓ１のサブレジスタ１にデータＡ、ＳＩＭＤレジスタｓ１のサブレジスタ２にデータＸが格納されることになる。
【００３９】
ここで、同じ位置にあるサブレジスタの集合をスロットと呼ぶ。すなわち、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ１はスロット１に属し、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ２はスロット２に属する。ＳＩＭＤ命令では、同じスロットに属する複数のサブレジスタを用いて１つの演算が行われることになる。
【００４０】
図５は、ＳＩＭＤレジスタの実装例を示す図である。プロセッサ内にＳＩＭＤレジスタを実装する方式としては、図５に示すような（Ａ）分割方式と（Ｂ）結合方式がある。
分割方式では、１つの大きな物理レジスタを論理的に均等な大きさに分割して、複数のサブレジスタを形成する。並列度＝２の場合は物理レジスタの記憶領域を２等分し、並列度＝４の場合は物理レジスタの記憶領域を４等分する。物理レジスタの大きさを一定とすると、並列度が高いほど、各サブレジスタのビット数は小さくなる。分割方式では、ＳＩＭＤレジスタは物理的なレジスタを指し、サブレジスタは論理的なレジスタを指す。
【００４１】
一方、結合方式では、ビット数が等しい複数の物理レジスタをグルーピングし、各物理レジスタをサブレジスタとして用いて、ＳＩＭＤレジスタを形成する。並列度＝２の場合は２個の物理レジスタの集合をＳＩＭＤレジスタとして扱い、並列度＝４の場合は４個の物理レジスタの集合をＳＩＭＤレジスタとして扱う。物理レジスタの大きさを一定とすると、並列度が高いほど、ＳＩＭＤレジスタのビット数は大きくなる。分割方式では、ＳＩＭＤレジスタは論理的なレジスタを指し、サブレジスタは物理的なレジスタを指す。
【００４２】
次に、ＳＩＭＤ命令間に転送命令が挿入されてしまう問題について説明する。
図６は、命令のＳＩＭＤ化の例を示す図である。ここでは、次の４つの命令の最適化を考える。命令１：Ａ（Ｉ）＝Ｂ（Ｉ）＋Ｃ（Ｉ），命令２：Ａ（Ｉ＋１）＝Ｂ（Ｉ＋１）＋Ｃ（Ｉ＋１），命令３：Ｄ（Ｉ）＝Ａ（Ｉ＋１）＋Ｂ（Ｉ），命令４：Ｄ（Ｉ＋１）＝Ａ（Ｉ）＋Ｂ（Ｉ＋１）。命令３は命令２の演算結果を参照し、命令４は命令１の演算結果を参照している。すなわち、命令３は命令２に依存し、命令４は命令１に依存する。
【００４３】
ＳＩＭＤの並列数が２である場合、最適化部１２５は、命令１，２の組をＳＩＭＤ命令１に変換し、命令３，４の組をＳＩＭＤ命令２に変換することが考えられる。このとき、各命令へのスロットの割り当て方法としては、次の２通りが考えられる。（Ａ）命令３を命令１と同じスロット（スロット１）に割り当て、命令４を命令２と同じスロット（スロット２）に割り当てる。または、（Ｂ）命令４を命令１と同じスロット（スロット１）に割り当て、命令３を命令２と同じスロット（スロット２）に割り当てる。
【００４４】
図７は、転送命令とクリティカルパスの例を示す図である。
上記の割り当て方法（Ａ）を採用した場合、ＳＩＭＤ命令１が実行されると、データＡ（Ｉ）はスロット１のサブレジスタに格納され、データＡ（Ｉ＋１）はスロット２のサブレジスタに格納される。これに対し、ＳＩＭＤ命令２を実行するには、データＡ（Ｉ＋１）をスロット１のサブレジスタに格納し、データＡ（Ｉ）をスロット２のサブレジスタに格納しておくことになる。そこで、ＳＩＭＤ命令１，２の間に、ＳＩＭＤ命令１で算出されたデータＡ（Ｉ），Ａ（Ｉ＋１）を移動するための転送命令が挿入される。
【００４５】
一方、上記の割り当て方法（Ｂ）を採用した場合、データＡ（Ｉ），Ａ（Ｉ＋１）は移動しなくてよい。ただし、ＳＩＭＤ命令２を実行するには、データＢ（Ｉ＋１）をスロット１のサブレジスタに格納し、データＢ（Ｉ）をスロット２のサブレジスタに格納しておくことになる。そこで、ＳＩＭＤ命令１，２の間に、ＳＩＭＤ命令１で参照されるデータＢ（Ｉ），Ｂ（Ｉ＋１）を移動するための転送命令が挿入される。
【００４６】
このように、割り当て方法（Ａ），（Ｂ）の何れを採用しても、ＳＩＭＤ命令１，２の間に転送命令が１つ挿入される。ただし、割り当て方法（Ａ）の場合は、ＳＩＭＤ命令２が転送命令の実行を待ち、転送命令がＳＩＭＤ命令１の実行を待つ。一方、割り当て方法（Ｂ）の場合は、ＳＩＭＤ命令２がＳＩＭＤ命令１および転送命令の実行を待つが、転送命令はＳＩＭＤ命令１の実行の完了を待たなくてよい。すなわち、割り当て方法（Ａ）の方が、クリティカルパス（命令間の依存関係が直列的に並んだパスのうち最長のもの）が長くなり、命令の実行順序の制約が大きく、実行効率が低下する可能性が高くなる。
【００４７】
以上説明したように、ＳＩＭＤ命令に変換する命令の組み合わせ方によっては、ＳＩＭＤ命令の間に転送命令が挿入されることがある。また、各命令へのスロットの割り当て方によっては、挿入された転送命令がクリティカルパスに影響を与えることがある。
【００４８】
次に、ＳＩＭＤ化する命令組を探索するときの問題について説明する。
図８は、ソースコードの例を示す図である。ここでは、ソースファイル１１１に、図８に示すような８個の命令が含まれているとする。命令１，２，３，８では乗算（×）が行われ、命令６では除算（÷）が行われ、命令４，５，７では減算（−）が行われる。命令４は命令１，２が算出するデータを参照し、命令５は命令１が算出するデータを参照する。命令６は命令４，５が算出するデータを参照し、命令７は命令３が算出するデータを参照し、命令８は命令６，７が算出するデータを参照する。
【００４９】
図９は、命令依存グラフの例を示す図である。コンパイラ１２０が１度に処理するコード範囲（翻訳単位）毎に、命令間の依存関係を表す１またはそれ以上の命令依存グラフを生成することが可能である。図９に示す命令依存グラフ３０は、図８に示した命令１〜８に対応するものである。上記の通り、命令４は命令１，２に依存し、命令５は命令１に依存し、命令７は命令３に依存し、命令６は命令４，５に依存し、命令８は命令６，７に依存する。なお、最適化処理は、ソースコードから変換された中間コードに対して行われるが、図９では理解を容易にするため、各命令を高級言語の形式で記載している。
【００５０】
ここで、ＳＩＭＤの並列度が２であるとして、命令１〜８の中から１またはそれ以上の命令の組を選択しＳＩＭＤ命令に変換することを考える。中間コードの前方から後方に向かって（例えば、依存命令グラフ３０のリーフからルートノードに向かって）、ＳＩＭＤ化可能な命令組を探した場合、まず命令１，２の組が選択されることになる。
【００５１】
図１０は、ＳＩＭＤレジスタの割り当て例を示す図である。割り当て例（Ａ）は、命令１，２と命令４，５をそれぞれＳＩＭＤ化した場合を示している。割り当て例（Ｂ）は、命令１，２と命令４，７をそれぞれＳＩＭＤ化した場合を示している。割り当て例（Ｃ）は、命令１，２と命令５，７をそれぞれＳＩＭＤ化した場合を示している。
【００５２】
命令１，２に加えて命令４，５をＳＩＭＤ化すると、命令１，２の組が算出するデータ組Ａ（Ｉ），Ｂ（Ｉ）と、命令４，５の組が参照するデータ組Ａ（Ｉ），Ａ（Ｉ）が一致しないため、転送命令が挿入される。同様に、命令１，２に加えて命令４，７をＳＩＭＤ化すると、命令１，２の組が算出するデータ組と、命令４，７の組が参照するデータ組Ａ（Ｉ），Ｃ（Ｉ）とが一致しないため、転送命令が挿入される。命令１，２に加えて命令５，７をＳＩＭＤ化しても、命令１，２の組が算出するデータ組と、命令５，７の組が参照するデータ組Ａ（Ｉ），Ｃ（Ｉ）とが一致しないため、転送命令が挿入される。
【００５３】
このように、図８，９に示した命令列の場合、中間コードの前方から後方に向かって命令組を探して、命令１，２を組み合わせることを決定してしまうと、コンパイラ１２０が生成するオブジェクトコードの実行効率が高くならない。
【００５４】
図１１は、ＳＩＭＤレジスタの他の割り当て例を示す図である。図１１に示す割り当て例は、命令１，３と命令５，７をそれぞれＳＩＭＤ化した場合を示している。命令１，３と命令５，７をＳＩＭＤ化すると、命令１，３の組が算出するデータ組Ａ（Ｉ），Ｃ（Ｉ）と、命令５，７の組が参照するデータ組Ａ（Ｉ），Ｃ（Ｉ）が一致するため、２つのＳＩＭＤ命令の間に転送命令は挿入されない。よって、図１１の命令の組み合わせパターンは、図１０に示したパターンよりも実行効率が高く好ましい。ただし、中間コードの前方から後方に向かって命令組を探し、ＳＩＭＤ化可能な命令組を検出し次第ＳＩＭＤ化していく方法では、図１１のような組み合わせパターンを発見できない。
【００５５】
これに対して、中間コードにおいて一定の範囲内にある命令の間の組み合わせを全通り試して、最適な組み合わせを探す方法も考えられる。しかし、命令組を全探索する方法は、計算量が大きくなり非効率的である。例えば、演算の種類が同じ命令がＮ個あり、ＳＩＭＤの並列度が２であるとすると、命令の組み合わせパターンは２N/2×（Ｎ−１）！！通りになる（ここで“！！”は二重階乗を示す）。よって、探索範囲を広げると、命令組を全探索して最適な組み合わせパターンを算出することは難しくなる。
【００５６】
そこで、最適化部１２５は、以下に説明するような方法で命令組を探索する。
図１２は、ＳＩＭＤ化処理の手順例を示すフローチャートである。
（ステップＳ１）解析部１２６は、中間コード記憶部１２４から、１つの翻訳単位の中間コードを読み出し、読み出した中間コードに含まれる命令の依存関係を解析する。例えば、解析部１２６は、命令列を後方から前方に向かって走査することで、依存関係を解析する。そして、解析部１２６は、依存関係を示す命令依存グラフを生成する。
【００５７】
（ステップＳ２）解析部１２６は、ＳＩＭＤ化可能な命令組を探索するため、命令列を後方から前方に向かって走査することを開始する。命令列の走査する方法は、中間コード上で命令を逐次的に走査する方法でもよいし、ステップＳ１で生成した命令依存グラフ上でルートノードからリーフに向かってノードを走査する方法でもよい。
【００５８】
（ステップＳ３）解析部１２６は、ステップＳ２で開始した命令列の走査を通じて、ＳＩＭＤ化する命令組を順次決定していく。このとき、解析部１２６は、既にＳＩＭＤ化することを決定した命令組に基づいて、次にＳＩＭＤ化する命令組の候補を選択する。ステップＳ３の処理は、以下のステップＳ３ａ，Ｓ３ｂ，Ｓ３ｃの処理を含む。
【００５９】
（ステップＳ３ａ）解析部１２６は、ＳＩＭＤ化する命令組を１つ決定する。命令列の最後尾から走査を開始した後は、例えば、演算の種類が同じで互いに依存関係がない２以上の命令を、後方の命令から優先的に検出し、検出した２以上の命令を組み合わせる。
【００６０】
（ステップＳ３ｂ）解析部１２６は、ステップＳ３ａでＳＩＭＤ化を決定した各命令が参照するレジスタ（参照オペランド）を抽出する。そして、解析部１２６は、抽出した参照オペランド毎に、命令列の中から、演算結果を格納するレジスタ（定義オペランド）が参照オペランドと同じである他の命令を検索する。すなわち、解析部１２６は、命令列の中から、ＳＩＭＤ化を決定した各命令が依存する他の命令を検索する。
【００６１】
（ステップＳ３ｃ）解析部１２６は、ＳＩＭＤ化を決定した２以上の命令に対応する、ステップＳ３ｂで検索された２以上の他の命令が、演算の種類が同じで互いに依存関係のない命令であるか（ＳＩＭＤ化可能な命令か）確認する。条件を満たすとき、解析部１２６は、検索された２以上の他の命令を、次にＳＩＭＤ化する命令組の候補として優先的に選択する。このとき、ＳＩＭＤ化を決定した各命令が、２つ以上の参照オペランドを含む場合、次にＳＩＭＤ化する命令組の候補が２つ以上選択され得る。
【００６２】
解析部１２６は、ステップＳ３ｂで他の命令が検索されなくなるまで、ステップＳ３ａ，Ｓ３ｂ，Ｓ３ｃの処理を繰り返す。ステップＳ３ｂで他の命令が検索されなくなると、解析部１２６は、ステップＳ２の方法に従って、次にＳＩＭＤ化する命令組を探す。以上の処理が、命令列の先頭まで走査が完了するまで繰り返される。例えば、図８，９の命令列の例では、解析部１２６は、命令８から命令１に向かって走査し、まず命令５，７の組をＳＩＭＤ化する。その後、解析部１２６は、命令５が参照するデータＡ（Ｉ）を定義する命令１と、命令７が参照するデータＣ（Ｉ）を定義する命令３の組をＳＩＭＤ化する。
【００６３】
なお、ステップＳ３ａにおいて、ステップＳ３ｃで選択した命令組の候補を採用するか否か決定するとき、解析部１２６は、命令組の候補の参照オペランドと、既にＳＩＭＤ化が決定された命令組の参照オペランドとを比較する。そして、解析部１２６は、参照オペランドの組み合わせ方に基づいて、転送命令が生成されるか判定し、転送命令が生成されるときはその命令組の候補を採用しない（ＳＩＭＤ化しない）ようにする。
【００６４】
具体的には、解析部１２６は、次の２つの条件の両方を満たすとき、転送命令が生成されると判定する。（１）ＳＩＭＤ化候補の命令に含まれる参照オペランドが、既にＳＩＭＤ化された何れかの命令に含まれている。（２）命令組の候補における参照オペランドの組が、既に決定した命令組における参照オペランドの組と異なるか、または、命令組の候補における参照オペランドへのスロットの割り当て方が、既に決定した命令組における参照オペランドへのスロットの割り当て方と異なる。
【００６５】
以下では、上記ステップＳ３の処理の実装例について説明する。
図１３は、中間コードの例を示す図である。中間コード１４１は、中間コード記憶部１２４に記憶される。中間コード１４１のある１つの翻訳単位には、命令１〜１２が含まれている。命令１，２，４，６，７，９は、ＲＡＭからデータを読み出すためのＬＯＡＤ命令であり、命令１２は、ＲＡＭにデータを書き込むためのＳＴＯＲＥ命令である。命令３，８はＭＵＬＴ（乗算）命令であり、命令５，１０，１１はＡＤＤ（加算）命令である。
【００６６】
命令３は命令１，２に依存し、命令５は命令３，４に依存し、命令８は命令６，７に依存し、命令１０は命令８，９に依存し、命令１１は命令５，１０に依存し、命令１２は命令１１に依存している。上記の命令１〜１２からは１つの命令依存グラフが生成される。なお、図１３に記載したＲ０１，Ｒ０２，Ｒ０３，Ｒ０４，Ｒ０５，Ｒ０６，Ｒ０７，Ｒ０８，Ｒ０９，Ｒ１０，Ｒ１１は、論理的なレジスタを示す。
【００６７】
図１４は、命令データと命令組データの例を示す図である。解析部１２６は、上記のステップＳ１において命令データ１４２を生成する。また、解析部１２６は、上記のステップＳ３でＳＩＭＤ化する命令組を決定すると、命令組データ１４３を生成する。
【００６８】
命令データ１４２は、翻訳単位内の命令毎に、命令番号、命令名、定義オペランド、参照オペランド、前命令および後命令の項目を含む。命令番号は、各命令を識別するための番号である。命令名は、演算の種類を示す名称（ＡＤＤ，ＳＵＢ，ＭＵＬＴ，ＤＩＶなど）である。定義オペランドの項目には、中間コード１４１で使用されている論理的なレジスタの識別子であって、演算結果のデータを格納するレジスタの識別子が設定される。参照オペランドの項目には、参照されるデータを格納する１またはそれ以上のレジスタの識別子が設定される。前命令の項目には、中間コード１４１において１つ前の命令を示す命令番号が設定される。後命令の項目には、１つ後の命令を示す命令番号が設定される。
【００６９】
命令組データ１４３は、ＳＩＭＤ化が決定された命令組毎に、組番号、命令番号およびＳＩＭＤ命令位置の項目を含む。組番号は、命令の組を識別するための番号である。命令番号の項目には、組み合わせた各命令の命令番号が列挙される。列挙される命令番号の数は、ＳＩＭＤの並列度に一致する。命令番号によって、命令データ１４２と命令組データ１４３とが関連付けられる。ＳＩＭＤ命令位置の項目には、中間コード１４１において、生成したＳＩＭＤ命令を埋め込む位置を示す情報が設定される。
【００７０】
図１５は、命令の組み合わせ例を示す図である。中間コード１４１から図１３に示した命令１〜１２を読み込むと、解析部１２６は、まず命令５，１０の組をＳＩＭＤ化すると決定する。すると、解析部１２６は、命令５，１０の組から、参照オペランドＲ０３，Ｒ０８の組と、参照オペランドＲ０４，Ｒ０９の組を抽出する。解析部１２６は、参照オペランドＲ０３，Ｒ０８の組から、命令３，８の組をＳＩＭＤ化すると決定し、また、参照オペランドＲ０４，Ｒ０９の組から、命令４，９の組をＳＩＭＤ化すると決定する。
【００７１】
更に、解析部１２６は、命令３，８の組から、参照オペランドＲ０１，Ｒ０６の組と、参照オペランドＲ０２，Ｒ０７の組を抽出する。解析部１２６は、参照オペランドＲ０１，Ｒ０６の組から、命令１，６の組をＳＩＭＤ化すると決定し、また、参照オペランドＲ０２，Ｒ０７の組から、命令２，７の組をＳＩＭＤ化すると決定する。
【００７２】
図１６は、ＳＩＭＤ判定処理の手順例を示すフローチャートである。このフローチャートが示す処理は、前述のステップＳ３において実行される。
（ステップＳ１１）解析部１２６は、１つの命令組の候補が選択されると、その命令組から１またはそれ以上の参照オペランド組としてのレジスタ組を抽出する。そして、解析部１２６は、抽出したレジスタ組を１つ選択する。（ステップＳ１２）解析部１２６は、選択したレジスタ組に含まれるレジスタを１つ選択する。
【００７３】
（ステップＳ１３）解析部１２６は、選択したレジスタが、既にＳＩＭＤ化が決定されている命令組に参照オペランドとして現れるレジスタであるか判断する。既存の命令組に表れる場合は処理をステップＳ１４に進め、現れない場合は処理をステップＳ１５に進める。（ステップＳ１４）解析部１２６は、ステップＳ１２で選択したレジスタと他のレジスタとの組み合わせ方が、既存の命令組に現れる組み合わせ方と同じであるか判断する。具体的には、解析部１２６は、命令組の候補と既存の命令組の間で、組み合わせるレジスタが同じであり、かつ、それらレジスタに割り当てるスロットが同じであるか判断する。組み合わせ方が同じ場合は、処理をステップＳ１５に進める。組み合わせ方が同じでない場合は、選択された命令組の候補をＳＩＭＤ化しないと決定し、処理を終了する。
【００７４】
（ステップＳ１５）解析部１２６は、中間コード１４１から、ステップＳ１２で選択したレジスタを定義オペランドとして含んでいる命令（定義命令）を検索する。（ステップＳ１６）解析部１２６は、ステップＳ１２で全てのレジスタを選択したか判断する。全て選択した場合は処理をステップＳ１７に進め、未選択のレジスタがある場合は処理をステップＳ１２に進める。（ステップＳ１７）解析部１２６は、ステップＳ１１で全てのレジスタ組を選択したか判断する。全て選択した場合は処理をステップＳ１８に進め、未選択のレジスタ組がある場合は処理をステップＳ１１に進める。
【００７５】
（ステップＳ１８）解析部１２６は、選択された命令組の候補をＳＩＭＤ化すると決定し、命令組データ１４３に命令組を登録する。（ステップＳ１９）解析部１２６は、後続の命令組の候補についてステップＳ１３，Ｓ１４の判定を行うために、ステップＳ１１で抽出したレジスタ組を示すレジスタ組データを生成して、ＲＡＭ１０２に保存しておく。
【００７６】
（ステップＳ２０）解析部１２６は、ステップＳ１５で検索された２以上の定義命令の演算の種類が同じであるか判断する。演算の種類が同じ場合は処理をステップＳ２１に進め、同じでない場合は処理を終了する。（ステップＳ２１）解析部１２６は、命令依存グラフに基づいて、検索された定義命令の間に依存関係があるか判断する。依存関係がある場合は処理を終了し、依存関係がない場合は処理をステップＳ２２に進める。（ステップＳ２２）解析部１２６は、検索された２以上の定義命令の組を、ＳＩＭＤ化する命令組の候補として選択し、図１６のＳＩＭＤ判定処理を再帰的に実行する。
【００７７】
第２の実施の形態の端末装置１００によれば、命令列の後方から前方に向かってＳＩＭＤ化可能な命令組が探索され、既にＳＩＭＤ化が決定された命令組における参照オペランドの組を手掛かりに、次にＳＩＭＤ化する命令組の候補が検索される。これにより、ＳＩＭＤレジスタ間でのデータ転送が抑制されるような命令組を探すことができ、コンパイラ１２０が生成するオブジェクトコードの実行効率が向上する。また、コンパイラ１２０においてそのような命令組を効率的に探すことができる。
【００７８】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現でき、第２の実施の形態の情報処理は、端末装置１００にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。
【００７９】
プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置（例えば、ＨＤＤ１０３）に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。
【符号の説明】
【００８０】
１０  情報処理装置
１１  記憶部
１１ａ  第１のコード
１１ｂ  第２のコード
１２  演算部
１３ａ，１３ｂ，１３ｃ，１３ｄ  命令
１４ａ，１４ｂ  ＳＩＭＤ命令
【図１】
0005966509.tif 000002
【図２】
0005966509.tif 000003
【図３】
0005966509.tif 000004
【図４】
0005966509.tif 000005
【図５】
0005966509.tif 000006
【図６】
0005966509.tif 000007
【図７】
0005966509.tif 000008
【図８】
0005966509.tif 000009
【図９】
0005966509.tif 000010
【図１０】
0005966509.tif 000011
【図１１】
0005966509.tif 000012
【図１２】
0005966509.tif 000013
【図１３】
0005966509.tif 000014
【図１４】
0005966509.tif 000015
【図１５】
0005966509.tif 000016
【図１６】
0005966509.tif 000017