(57)【特許請求の範囲】
【請求項１】
第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成するためのプログラムであって、コンピュータに、
前記第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成し、
前記第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、前記第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替え、
高さの変更および順序の入れ替えを行った後の前記第１および第２のツリーを対比して、前記第１のツリーの命令と前記第２のツリーの命令との間の組み合わせを決定する、
処理を実行させるプログラム。
【請求項２】
前記順序の入れ替えでは、更に、
前記第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ複数のロード命令が存在するとき、各ロード命令でロードされるデータを示す変数名に応じて前記複数のロード命令の順序を入れ替える、
請求項１記載のプログラム
【請求項３】
前記順序の入れ替えでは、前記第１および第２のツリーそれぞれについて、ルートからの深さが同じ命令の間で、演算の種類に応じて命令をソートする、請求項１または２記載のプログラム。
【請求項４】
第１のコードから、前記第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成する、コンピュータが実行するコード生成方法であって、
前記第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成し、
前記第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、前記第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替え、
高さの変更および順序の入れ替えを行った後の前記第１および第２のツリーを対比して、前記第１のツリーの命令と前記第２のツリーの命令との間の組み合わせを決定する、
コード生成方法。
【請求項５】
第１のコードと、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を含む第２のコードとを記憶する記憶部と、
前記第１のコードに含まれる２以上の命令を組み合わせて前記特定命令を生成することで、前記第１のコードから前記第２のコードを生成する演算部と、
を有し、前記演算部は、
前記第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成し、
前記第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、前記第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替え、
高さの変更および順序の入れ替えを行った後の前記第１および第２のツリーを対比して、前記第１のツリーの命令と前記第２のツリーの命令との間の組み合わせを決定する、
情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプログラム、コード生成方法および情報処理装置に関する。
【背景技術】
【０００２】
現在、ＣＰＵ（Central Processing Unit）などのプロセッサの中には、ＳＩＭＤ（Single Instruction Multiple Data）命令と呼ばれる１つの命令によって、異なるデータに対して同じ種類の演算を並列実行できるものがある。ＳＩＭＤ命令を実行するプロセッサは、並列に処理すべき異なるデータを組み合わせて格納するＳＩＭＤレジスタと呼ばれるレジスタを備える。例えば、ＳＩＭＤレジスタｓ１にデータＡ１，Ａ２が格納され、ＳＩＭＤレジスタｓ２にデータＢ１，Ｂ２が格納された状態で、プロセッサにｓ１＋ｓ２というＳＩＭＤ命令が入力されたとする。すると、プロセッサは、Ａ１＋Ｂ１およびＡ２＋Ｂ２という２つの加算を、１命令で並列に実行することになる。
【０００３】
ＳＩＭＤ命令を含むコードを生成する方法としては、ＳＩＭＤ命令でない複数の命令の中から、演算の種類が同じであり並列に実行できる２以上の命令を検索し、検索した命令を組み合わせてＳＩＭＤ命令を生成する方法がある。例えば、高級言語で記述されたソースコードを機械可読なオブジェクトコードに変換するコンパイラの中には、最適化処理の中で、２以上の命令を組み合わせてＳＩＭＤ命令に変換するものがある。組み合わせ可能な命令の数（並列度）は、プロセッサのアーキテクチャによって異なる。
【０００４】
なお、複数の命令の間の依存関係を示すトレース依存性ツリーを生成し、同一のレベルに属する同じ種類の演算を指定した２以上の命令をトレース依存性ツリーから検索し、検索した命令を１つのＳＩＭＤ命令にマージするコンピュータシステムが提案されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２００６／００７１９３号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ＳＩＭＤ命令を生成するには、依存関係がなく並列に実行可能な命令同士を組み合わせることになる。そこで、命令の組み合わせを探索する方法としては、前述のように、命令間の依存関係を示すツリーを利用する方法が考えられる。コードを解析して複数のツリー（１つの大きなツリーに属する複数の部分ツリーでもよい）が生成されたとき、ツリー同士を比較し、異なるツリーに属する演算の種類が同じ命令同士を組み合わせることによって、組み合わせのパターンを探すことができる。
【０００７】
しかし、コードを解析して生成される複数のツリーは、同じ形状をしているとは限らない。このため、前述のように同じレベルにある命令同士を比較するだけでは、適切な命令の組み合わせを見つけることができないことがある。このとき、異なるレベルにある命令同士を組み合わせることが可能な場合もある。一方で、ＳＩＭＤ命令に変換できる命令の組み合わせを多く見つけるために、ツリーの構造とは関係なく命令の組み合わせを全探索しようとすると、計算量が増大し非効率的となってしまう。
【０００８】
一側面では、本発明は、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成するための命令の組み合わせを効率的に探索できるプログラム、コード生成方法および情報処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
一側面では、第１のコードから、第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成するためのプログラムが提供される。プログラムはコンピュータに以下の処理を実行させる。第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成する。第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替える。高さの変更および順序の入れ替えを行った後の第１および第２のツリーを対比して、第１のツリーの命令と第２のツリーの命令との間の組み合わせを決定する。
【００１０】
また、一側面では、第１のコードから、第１のコードに含まれる２以上の命令を組み合わせて、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成することで、当該特定命令を含む第２のコードを生成する、コンピュータが実行するコード生成方法が提供される。コード生成方法では、第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成する。第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替える。高さの変更および順序の入れ替えを行った後の第１および第２のツリーを対比して、第１のツリーの命令と第２のツリーの命令との間の組み合わせを決定する。
【００１１】
また、一側面では、第１のコードと、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を含む第２のコードとを記憶する記憶部と、第１のコードに含まれる２以上の命令を組み合わせて特定命令を生成することで、第１のコードから第２のコードを生成する演算部と、を有する情報処理装置が提供される。演算部は、第１のコードから命令の間の依存関係を示す第１および第２のツリーを生成する。第１および第２のツリーのうち高さの小さいツリーについて、演算の前後でデータの内容が変化しない疑似命令を挿入して高さを変更し、また、第１および第２のツリーの少なくとも一方について、ルートからの深さが同じ命令の間で、各命令で指定された演算の種類に応じて命令の順序を入れ替える。高さの変更および順序の入れ替えを行った後の第１および第２のツリーを対比して、第１のツリーの命令と第２のツリーの命令との間の組み合わせを決定する。
【発明の効果】
【００１２】
一側面では、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令を生成するための命令の組み合わせを効率的に探索できる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の情報処理装置を示す図である。
【図２】端末装置が備えるハードウェア例を示すブロック図である。
【図３】端末装置が備えるソフトウェア例を示すブロック図である。
【図４】ＳＩＭＤ命令とＳＩＭＤレジスタの関係例を示す図である。
【図５】ＳＩＭＤレジスタの実装例を示す図である。
【図６】依存ツリーの例を示す図である。
【図７】ＳＩＭＤ化処理の手順例を示すフローチャートである。
【図８】中間コードの例を示す図である。
【図９】依存ツリーの他の例を示す図である。
【図１０】命令データと依存データの例を示す図である。
【図１１】依存解析処理の手順例を示すフローチャートである。
【図１２】依存ツリーの第１の変形例を示す図である。
【図１３】依存ツリーの第２の変形例を示す図である。
【図１４】依存ツリーの第３の変形例を示す図である。
【図１５】高さ調整処理の手順例を示すフローチャートである。
【図１６】ノード入替処理の手順例を示すフローチャートである。
【図１７】依存ツリーの分割例を示す図である。
【図１８】基点データの例を示す図である。
【図１９】基点選択処理の手順例を示すフローチャートである。
【図２０】レベル算出のサブルーチンの手順例を示すフローチャートである。
【図２１】変換データの例を示す図である。
【図２２】符号化処理の手順例を示すフローチャートである。
【図２３】エッジデータとパックデータの例を示す図である。
【図２４】候補算出処理の手順例を示すフローチャートである。
【図２５】エッジデータ設定のサブルーチンの手順例を示すフローチャートである。
【図２６】エッジデータ生成の流れの例を示す図である。
【図２７】パックデータの候補の例を示す図である。
【図２８】符号データからスコアを算出する例を示す図である。
【図２９】ＳＩＭＤ化判定処理の手順例を示すフローチャートである。
【図３０】パックデータ設定のサブルーチンの手順例を示すフローチャートである。
【図３１】スコア算出処理の手順例を示すフローチャートである。
【図３２】パックデータ生成の流れの例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。情報処理装置１０は、第１のコード１１ａから、ＳＩＭＤ命令を含む第２のコード１１ｂを生成する。第１のコード１１ａは、例えば、高級言語で記述されたソースコードや、ソースコードから変換された中間コードである。第２のコード１１ｂは、例えば、情報処理装置１０または他のコンピュータのプロセッサが解釈可能なオブジェクトコードや実行コードである。情報処理装置１０は、ユーザが操作する端末装置としてのクライアントコンピュータでもよいし、端末装置からアクセスされるサーバコンピュータであってもよい。なお、ＳＩＭＤ命令は、異なるデータに対して同じ種類の演算を並列実行するよう指示する特定命令の一例である。
【００１５】
情報処理装置１０は、記憶部１１および演算部１２を有する。記憶部１１は、第１のコード１１ａおよび第２のコード１１ｂを記憶する。記憶部１１は、ＲＡＭ（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）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１からの命令に従って、記録媒体２３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００２９】
通信インタフェース１０７は、ネットワーク２４を介して他のコンピュータと通信を行えるインタフェースである。通信インタフェース１０７は、有線網に接続する有線インタフェースでもよいし、無線網に接続する無線インタフェースでもよい。
【００３０】
図３は、端末装置が備えるソフトウェア例を示すブロック図である。端末装置１００は、ファイル記憶部１１０、コンパイラ１２０およびリンカ１３０を有する。ファイル記憶部１１０は、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域として実現できる。コンパイラ１２０およびリンカ１３０は、ＣＰＵ１０１が実行するプログラムのモジュールとして実現できる。ただし、コンパイラ１２０およびリンカ１３０の機能の一部または全部を、ソフトウェアでなく電子回路として実現することも可能である。
【００３１】
ファイル記憶部１１０は、ソースファイル１１１、オブジェクトファイル１１２および実行ファイル１１３を記憶する。ソースファイル１１１は、高級言語で記述されたソースコードを含む。オブジェクトファイル１１２は、ＳＩＭＤ命令を含む機械可読なオブジェクトコードを含む。実行ファイル１１３は、ＳＩＭＤ命令を解釈できる所定のアーキテクチャのプロセッサが実行できる形式のファイルである。なお、ＣＰＵ１０１は、実行ファイル１１３を実行可能であってもよいし、実行可能でなくてもよい。
【００３２】
コンパイラ１２０は、ファイル記憶部１１０からソースファイル１１１を読み出し、ソースコードをオブジェクトコードに変換して、オブジェクトファイル１１２をファイル記憶部１１０に格納する。コンパイラ１２０は、入出力制御部１２１、ファイル入力部１２２、中間コード生成部１２３、中間コード記憶部１２４、最適化部１２５、アセンブリコード生成部１２８およびファイル出力部１２９を有する。
【００３３】
入出力制御部１２１は、ファイルの種類に応じた入出力方法を選択し、ファイル入力部１２２およびファイル出力部１２９を制御する。ファイル入力部１２２は、入出力制御部１２１からの指示に応じて、ソースファイル１１１をオープンし、ソースファイル１１１からソースコードを読み出す。中間コード生成部１２３は、ファイル入力部１２２が読み出したソースコードを解析して、コンパイラ１２０の内部で利用される中間言語で記述された中間コードに変換し、中間コードを中間コード記憶部１２４に格納する。ソースコードの解析には、字句解析、構文解析、意味解析などが含まれる。中間コード記憶部１２４は、ＲＡＭ１０２に確保された記憶領域であり、中間コードを記憶する。
【００３４】
最適化部１２５は、中間コード記憶部１２４に記憶された中間コードを、実行速度が向上するように最適化する。最適化部１２５は、解析部１２６および最適化実行部１２７を有する。解析部１２６は、中間コードを解析して最適化方法を決定する。解析部１２６が行う最適化方法の決定には、中間コードに含まれる命令の中でＳＩＭＤ命令に変換する命令の組み合わせを決定することを含む。最適化実行部１２７は、解析部１２６が決定した最適化方法に従って中間コードを最適化する。最適化実行部１２７が行う最適化には、中間コードに含まれる命令をＳＩＭＤ命令に変換することを含む。
【００３５】
アセンブリコード生成部１２８は、最適化された中間コードを、低級言語であるアセンブリ言語で記述されたアセンブリコードに変換する。ファイル出力部１２９は、入出力制御部１２１からの指示に応じて、オブジェクトファイル１１２を生成する。そして、ファイル出力部１２９は、アセンブリコード生成部１２８が生成したアセンブリコードをオブジェクトコードに変換し、オブジェクトファイル１１２に書き込む。
【００３６】
リンカ１３０は、ファイル記憶部１１０からオブジェクトファイル１１２を読み出し、オブジェクトコードを解析して、参照されている他のオブジェクトファイルやライブラリを検出する。そして、リンカ１３０は、オブジェクトファイル１１２と、検出した他のオブジェクトファイルやライブラリとをリンクし、実行ファイル１１３を生成する。なお、コンパイラ１２０にリンカ１３０の機能が統合されていてもよい。
【００３７】
ここで、プロセッサ内でのＳＩＭＤ命令の実行方法について説明する。
図４は、ＳＩＭＤ命令とＳＩＭＤレジスタの関係例を示す図である。ＳＩＭＤ命令を解釈できるプロセッサは、並列に処理されるデータを組み合わせて格納するＳＩＭＤレジスタを備える。各ＳＩＭＤレジスタは、プロセッサのアーキテクチャによって決まる並列度に相当する数のサブレジスタを含む。図４は、並列度が２の場合を示している。
【００３８】
例えば、図４に示すように、Ａ＝Ｂ＋Ｃ，Ｘ＝Ｙ＋Ｚという２つの命令を１つのＳＩＭＤ命令ｓ１＝ｓ２＋ｓ３に変換した場合を考える。この場合、ＳＩＭＤレジスタｓ２のサブレジスタ１にデータＢ、ＳＩＭＤレジスタｓ２のサブレジスタ２にデータＹ、ＳＩＭＤレジスタｓ３のサブレジスタ１にデータＣ、ＳＩＭＤレジスタｓ３のサブレジスタ２にデータＺを格納しておく。すると、ＳＩＭＤ命令によって、２つの加算が並列に実行されてデータＡ，Ｘが算出され、ＳＩＭＤレジスタｓ１のサブレジスタ１にデータＡ、ＳＩＭＤレジスタｓ１のサブレジスタ２にデータＸが格納されることになる。
【００３９】
なお、同じ位置にあるサブレジスタの集合をスロットと呼ぶ。すなわち、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ１はスロット１に属し、ＳＩＭＤレジスタｓ１，ｓ２，ｓ３の各サブレジスタ２はスロット２に属する。ＳＩＭＤ命令では、同じスロットに属する複数のサブレジスタを用いて１つの演算が行われることになる。
【００４０】
図５は、ＳＩＭＤレジスタの実装例を示す図である。プロセッサ内にＳＩＭＤレジスタを実装する方式としては、図５に示すような（Ａ）分割方式と（Ｂ）結合方式がある。
分割方式では、１つの大きな物理レジスタを論理的に均等な大きさに分割して、複数のサブレジスタを形成する。並列度＝２の場合は物理レジスタの記憶領域を２等分し、並列度＝４の場合は物理レジスタの記憶領域を４等分する。物理レジスタの大きさを一定とすると、並列度が高いほど、各サブレジスタのビット数は小さくなる。分割方式では、ＳＩＭＤレジスタは物理的なレジスタを指し、サブレジスタは論理的なレジスタを指す。
【００４１】
一方、結合方式では、ビット数が等しい複数の物理レジスタをグルーピングし、各物理レジスタをサブレジスタとして用いて、ＳＩＭＤレジスタを形成する。並列度＝２の場合は２個の物理レジスタの集合をＳＩＭＤレジスタとして扱い、並列度＝４の場合は４個の物理レジスタの集合をＳＩＭＤレジスタとして扱う。物理レジスタの大きさを一定とすると、並列度が高いほど、ＳＩＭＤレジスタのビット数は大きくなる。分割方式では、ＳＩＭＤレジスタは論理的なレジスタを指し、サブレジスタは物理的なレジスタを指す。
【００４２】
次に、ＳＩＭＤ命令に変換する命令組を探索するときの問題点について説明する。
図６は、依存ツリーの例を示す図である。依存ツリー３１，３２は、中間コードに含まれる命令間の依存関係を示す。ここでは、コンパイラ１２０が１度に処理するコード範囲（翻訳単位）に、命令１〜１６が含まれているとする。命令１〜４，８，１０〜１４は、ＲＡＭからレジスタにデータを読み込むためのＬＯＡＤ命令である。命令３，７，１５はＭＵＬＴ（乗算）命令であり、命令６，９，１２，１６はＡＤＤ（加算）命令である。
【００４３】
命令３は命令１，２に依存し、命令６は命令４，５に依存し、命令７は命令３，６に依存し、命令９は命令７，８に依存する。命令１２は命令１０，１１に依存し、命令１５は命令１３，１４に依存し、命令１６は命令１２，１５に依存する。命令１〜９が依存ツリー３１を形成し、命令１０〜１６が依存ツリー３２を形成する。すなわち、命令１〜９の集合と命令１０〜１６の集合とは、互いに依存関係がなく並列に実行できる。
【００４４】
そこで、最適化部１２５は、依存ツリー３１に属する命令と依存ツリー３２に属する命令を組み合わせて、ＳＩＭＤ命令に変換する（ＳＩＭＤ化する）ことが考えられる。しかし、依存ツリー３１，３２は形状が異なるため、そのままではＳＩＭＤ化できる命令組を探索することが容易でない。例えば、ルートノードからの深さが同じ命令の間でＳＩＭＤ化できる命令組を探すだけでは、命令７，１５の組と命令９，１６の組しか検出できない。この場合、依存ツリー３１に属する命令のうちＳＩＭＤ化される命令の比率（ＳＩＭＤ化率）は、２÷９＝０．２２（２２％）に過ぎない。
【００４５】
これに対し、中間コードにおいて一定の範囲内にある命令の間の組み合わせを全通り試して、ＳＩＭＤ化可能な命令組を探す方法も考えられる。しかし、命令組を全探索する方法は、計算量や計算に要するメモリ領域が大きくなり非効率的である。例えば、演算の種類が同じ命令がｎ個あるとき、命令の組み合わせパターンはｎＰｎ通り存在することになり、ｎ＝８の場合は４０３２０通り存在する。よって、中間コードにおける探索範囲を広げると、命令組を全探索して最適な組み合わせパターンを算出することは難しくなる。
【００４６】
そこで、最適化部１２５は、以下に説明するような方法で命令組を探索する。
図７は、ＳＩＭＤ化処理の手順例を示すフローチャートである。
（ステップＳ１）解析部１２６は、中間コード記憶部１２４から、１つの翻訳単位の中間コードを読み出し、読み出した中間コードに含まれる命令の間の依存関係を解析する。そして、解析部１２６は、命令間の依存関係を示す複数の依存ツリーを生成する。
【００４７】
（ステップＳ２）解析部１２６は、ステップＳ１で生成した複数の依存ツリーの少なくとも１つを、命令組の探索が容易になるように変形する（正規化）。ステップＳ２の処理は、以下のステップＳ２ａ，Ｓ２ｂ，Ｓ２ｃの処理を含む。
【００４８】
（ステップＳ２ａ）解析部１２６は、複数の依存ツリーの高さが同じになるように、少なくとも１つの依存ツリーに疑似命令を挿入する（高さ調整）。（ステップＳ２ｂ）解析部１２６は、依存ツリー毎に、同じ深さにある命令間で、演算の種類に応じて命令をソートする。（ステップＳ２ｃ）解析部１２６は、依存ツリー毎に、同じ深さにあるＬＯＡＤ命令間で、読み込むデータの変数名に応じて命令をソートする。
【００４９】
（ステップＳ３）解析部１２６は、依存ツリー同士の比較を容易にするため、依存ツリーの中から１またはそれ以上の基点となる命令を選択し、選択した基点がルートノードになるように依存ツリーを分割する（レベル管理）。第２の実施の形態では、基点命令として、ＲＡＭにデータを書き出すＳＴＯＲＥ命令を用いる。
【００５０】
（ステップＳ４）解析部１２６は、依存ツリー間での命令の比較を効率的に行えるように、各依存ツリーを符号化する。すなわち、解析部１２６は、依存ツリー毎に、演算の種類を示す符号を当該依存ツリーの構造に従って並べた符号データを生成する。
【００５１】
（ステップＳ５）解析部１２６は、依存ツリーの組の候補を全通り算出する。１つの組に属する依存ツリーの数は、ＳＩＭＤの並列度に一致させる。例えば、並列度が２である場合、解析部１２６は、所定の条件（例えば、高さが同じである、互いに依存関係がないなどの条件）を満たす２つの依存ツリーの組を全通り算出する。なお、ステップＳ４の処理とステップＳ５の処理は、逆順で行ってもよいし並列に行ってもよい。
【００５２】
（ステップＳ６）解析部１２６は、ステップＳ５で算出した依存ツリーの組の候補について、ステップＳ４で生成した符号データ同士を比較して、命令の一致度を示すスコアを算出する（スコアリング）。スコアリングでは、複数の依存ツリーの間の対応するノードに、同じ種類の演算を行う命令が存在するか評価される。解析部１２６は、算出したスコアに基づいて、依存ツリーの組を決定し、組み合わせた依存ツリーの対応するノードにある命令同士を組み合わせてＳＩＭＤ化することを決定する。
【００５３】
以下では、図７に示した処理手順の実装例について説明する。まず、中間コードから命令間の依存関係を解析して依存ツリーを生成する手順について説明する。
図８は、中間コードの例を示す図である。中間コード１４１は、中間コード記憶部１２４に記憶される。中間コード１４１の１つの翻訳単位に、命令１〜１３が含まれている。命令１，２，４，６，７，９はＬＯＡＤ命令であり、命令１２，１３はＳＴＯＲＥ命令である。命令３，８はＭＵＬＴ命令であり、命令５，１０，１１はＡＤＤ命令である。
【００５４】
命令３は命令１，２でロードされたデータを参照し、命令８は命令６，７でロードされたデータを参照している。命令１０は命令８，９で算出されたデータを参照し、命令１１は命令５，１０で算出されたデータを参照し、命令１２は命令１１で算出されたデータを参照している。命令１３は命令１〜１２でロードまたは算出されたデータの何れも参照していない。なお、図８に記載したＲ０１〜Ｒ１２は、論理的なレジスタを示す。ｍｅｍ０１〜ｍｅｍ０８は、ＲＡＭ上の論理的な記憶領域を示す。
【００５５】
図９は、依存ツリーの他の例を示す図である。依存ツリー４１は、図８に示した命令１〜１２から生成される。命令１〜１２と依存関係がない命令１３は、依存ツリー４１に属さない。依存ツリー４１では、一方の命令が他方の命令に依存しているとき、一方の命令が親ノードに対応付けられ、他方の命令が子ノードに対応付けられる。依存ツリー４１のリーフノードからルートノードに向かって演算が進行することになる。命令３は命令１，２に依存し、命令５は命令３，４に依存し、命令８は命令６，７に依存し、命令１０は命令８，９に依存し、命令１１は命令５，１０に依存し、命令１２は命令１１に依存する。
【００５６】
図１０は、命令データと依存データの例を示す図である。最適化部１２５は、依存関係の解析を通じて、命令データ１５１および依存データ１５２を生成する。
命令データ１５１は、命令毎に、命令番号、解析済フラグ、命令名、定義オペランドおよび参照オペランドの項目を含む。命令番号は、各命令を識別するための番号である。解析済フラグは、依存関係の解析などの処理の際に、その命令が解析済か否かを識別するために利用されるフラグである。解析済フラグの初期値はＯＦＦに設定される。命令名は、演算の種類を示す名称（ＡＤＤ，ＳＵＢ，ＭＵＬＴ，ＤＩＶ，ＬＯＡＤ，ＳＴＯＲＥなど）である。定義オペランドの項目には、中間コード１４１で使用されている論理的なレジスタまたはＲＡＭの記憶領域を示す識別子であって、データの格納先を示す識別子が設定される。参照オペランドの項目には、参照するデータが格納されている１またはそれ以上の論理的なレジスタまたはＲＡＭの記憶領域を示す識別子が設定される。
【００５７】
依存データ１５２は、定義命令の命令番号と参照命令の命令番号の組を１つ以上含む。定義命令は、定義オペランドであるレジスタまたはＲＡＭ領域が、他の命令によって参照される命令である。参照命令は、他の命令が定義オペランドとして定義したレジスタまたはＲＡＭの記憶領域を、参照オペランドとして参照している命令である。
【００５８】
図１１は、依存解析処理の手順例を示すフローチャートである。図１１のフローチャートが示す処理は、前述のステップＳ１において実行される。
（ステップＳ１１１）解析部１２６は、翻訳単位に含まれる命令を、前方から優先的に１つ選択する。（ステップＳ１１２）解析部１２６は、選択した命令から命令名、定義オペランドおよび参照オペランドを抽出し、命令番号を付与して命令データ１５１にその命令を登録する。（ステップＳ１１３）解析部１２６は、ステップＳ１１１で翻訳単位の末尾まで全ての命令を選択したか判断する。全て選択した場合は処理をステップＳ１１４に進め、未選択の命令がある場合は処理をステップＳ１１１に進める。
【００５９】
（ステップＳ１１４）解析部１２６は、翻訳単位に含まれる命令を、後方から優先的に１つ選択する。（ステップＳ１１５）解析部１２６は、選択した命令が依存ツリーに含めるべき命令か判断する。条件を満たす場合は処理をステップＳ１１６に進め、条件を満たさない場合は処理をステップＳ１２３に進める。（ステップＳ１１６）解析部１２６は、選択した命令の解析済フラグがＯＮであるか（解析済であるか）判断する。ＯＮの場合は処理をステップＳ１２３に進め、ＯＦＦの場合は処理をステップＳ１１７に進める。
【００６０】
（ステップＳ１１７）解析部１２６は、ステップＳ１１４で選択した命令の参照オペランドを１つ選択する。（ステップＳ１１８）解析部１２６は、翻訳単位から、選択した参照オペランドに対応する定義オペランドをもつ命令（定義命令）を検索する。（ステップＳ１１９）解析部１２６は、検索した定義命令が、現在の翻訳単位の依存ツリーに属するべきものか（例えば、他の翻訳単位の命令でないか）判断する。条件を満たす場合は処理をステップＳ１２０に進め、条件を満たさない場合は処理をステップＳ１２１に進める。（ステップＳ１２０）解析部１２６は、ステップＳ１１９で検索した定義命令からステップＳ１１４で選択した命令（参照命令）への依存関係を、依存データ１５２に登録する。
【００６１】
（ステップＳ１２１）解析部１２６は、ステップＳ１１７で、選択した命令に含まれる全ての参照オペランドを選択したか判断する。全て選択した場合は処理をステップＳ１２２に進め、未選択の参照オペランドがある場合は処理をステップＳ１１７に進める。（ステップＳ１２２）解析部１２６は、ステップＳ１１４で選択した命令の解析済フラグをＯＮに設定する。（ステップＳ１２３）解析部１２６は、ステップＳ１１４で翻訳単位の先頭まで全ての命令を選択したか判断する。全て選択した場合は処理を終了し、未選択の命令がある場合は処理をステップＳ１１４に進める。
【００６２】
次に、依存ツリーの変形（正規化）について説明する。
図１２は、依存ツリーの第１の変形例を示す図である。図６に示した依存ツリー３１の高さ（ルートノードから最も深いリーフノードまでに並んだノードの数）は４である一方、依存ツリー３２の高さは３であり、両者の高さが異なる。そこで、解析部１２６は、高さの小さい依存ツリー３２を、疑似命令を挿入することで依存ツリー３３に変形する。
【００６３】
疑似命令は、演算前のデータと演算後のデータが同じ内容になる命令である。疑似加算（疑似ＡＤＤ）は入力値に０を加えるものであり、疑似減算（疑似ＳＵＢ）は入力値から０を引くものであり、疑似乗算（疑似ＭＵＬＴ）は入力値に１を掛けるものであり、疑似除算（疑似ＤＩＶ）は入力値を１で割るものである。疑似ＬＯＡＤはレジスタのデータが変化しないように同じデータを再度読み込むものであり、疑似ＳＴＯＲＥはＲＡＭのデータが変化しないように同じデータをＲＡＭに上書きするものである。
【００６４】
依存ツリー３３は、命令１０〜１６を含む依存ツリー３２に対して、命令１７，１８を挿入したものである。命令１７は、依存ツリー３１の命令９に対応するように挿入された疑似ＡＤＤ命令である。命令１８は、依存ツリー３１の命令８に対応するように挿入された疑似ＬＯＡＤ命令である。命令１７は命令１６，１８に依存する。命令１７，１８が挿入されることで、依存ツリー３３の高さは依存ツリー３１と同じになっている。このように、解析部１２６は、依存ツリー３１と高さが同じになり、かつ、できる限り同じ深さに同じ種類の演算を指定した命令がくるように、依存ツリー３２に疑似命令を挿入する。
【００６５】
図１３は、依存ツリーの第２の変形例を示す図である。解析部１２６は、依存ツリー３１，３３の対応する位置に、同じ種類の演算を指定した命令が存在する確率を高くするため、順序を入れ替え可能な命令の間で、演算の種類に応じて命令をソートする。演算順序の入れ替えは、依存ツリー３１，３３それぞれに対して行う。図１３は、依存ツリー３３を、演算順序を入れ替えて依存ツリー３４に変形する例を示している。
【００６６】
命令をソートするにあたり、解析部１２６は、演算の優先順位を予め定めておく。例えば、四則演算については、乗算（ＭＵＬＴ）＞除算（ＤＩＶ）＞加算（ＡＤＤ）＞減算（ＤＩＶ）のように優先順位を定める。この場合、同じ命令（命令１６）と依存関係のある命令１２，１５が入れ替え可能な命令の組として検出され、演算の優先順位に従って、ＭＵＬＴ命令である命令１５がＡＤＤ命令である命令１２よりもツリー上で左側に並べられる。一方、上記の演算の優先順位を採用した場合、依存ツリー３１は変形しなくてよい。
【００６７】
図１４は、依存ツリーの第３の変形例を示す図である。解析部１２６は、ＬＯＡＤ命令の組をＳＩＭＤ化するとき、組み合わせるＬＯＡＤ命令同士ができる限りＲＡＭの近い記憶領域にアクセスすることになるよう、変数名に応じてＬＯＡＤ命令をソートする。変数名の入れ替えは、依存ツリー３１，３４それぞれに対して行う。図１４は、依存ツリー３４を、変数名を入れ替えて依存ツリー３５に変形する例を示している。
【００６８】
例えば、命令１０がデータＤ（Ｉ＋１）、命令１１がデータＢ（Ｉ＋１）、命令１３がデータＣ（Ｉ＋１）、命令１４がデータＡ（Ｉ＋１）をロードするものであるとする。この場合、同じ命令（命令１２）と依存関係のある命令１０，１１が入れ替え可能なＬＯＡＤ命令の組として検出され、変数名に従って、命令１１が命令１０よりもツリー上で左側に並べられる。また、同じ命令（命令１５）と依存関係のある命令１３，１４が入れ替え可能なＬＯＡＤ命令の組として検出され、変数名に従って、命令１４が命令１３よりもツリー上で左側に並べられる。変数名の優先順位は、例えば、辞書式順序により決定する。変数名の情報は、中間コード記憶部１２４に記憶された中間コードに含まれている。
【００６９】
なお、図１３では命令の内容と共に命令番号も移動しているが、後述するように、解析部１２６の内部処理では、命令の内容のみを入れ替えて命令番号は入れ替えない。このため、例えば、命令番号＝１２の命令が、ＡＤＤ命令からＭＵＬＴ命令に変換されることになる。同様に、図１４ではロードするデータの変数名と共に命令番号も移動しているが、解析部１２６の内部処理では、変数名のみを入れ替えて命令番号は入れ替えない。このため、例えば、命令番号＝１３の命令でロードされるデータの変数名が、Ｃ（Ｉ＋１）からＡ（Ｉ＋１）に変換されることになる。また、図１３で説明した演算順序の入れ替えと図１４で説明した変数名の入れ替えは、何れを先に実行してもよい。
【００７０】
図１５は、高さ調整処理の手順例を示すフローチャートである。図１５のフローチャートが示す処理は、前述のステップＳ２において実行される。この処理は、複数の依存ツリーのうち最も高さの大きい依存ツリーと対比して、他の各依存ツリーに対して行われる。
【００７１】
（ステップＳ１３１）解析部１２６は、依存ツリーの中で疑似命令を挿入できる位置を列挙する。例えば、依存ツリー３２の場合、７つの位置、すなわち、命令１０〜１６に対応する各ノードから１つ上位の（深さが小さくなる方向の）位置が選択される。（ステップＳ１３２）解析部１２６は、ステップＳ１３１で列挙された位置のべき集合（位置の組み合わせのパターン全て）を算出する。例えば、７つの位置が列挙された場合、Φ（空集合），｛位置１｝，｛位置１，２｝，｛位置１，２，３｝，・・・，｛位置６｝，｛位置６，７｝，｛位置７｝のように、位置の組み合わせを全パターン算出する。
【００７２】
（ステップＳ１３３）解析部１２６は、ステップＳ１３２で算出された位置の組み合わせのうち１つを選択する。（ステップＳ１３４）解析部１２６は、選択した組み合わせの各位置に疑似命令を挿入することで、依存ツリーの高さが、対比する他の依存ツリーと同じになるか判断する。高さが同じになる場合は処理をステップＳ１３５に進める。高さが同じにならない場合は処理をステップＳ１３７に進める。
【００７３】
（ステップＳ１３５）解析部１２６は、ステップＳ１３３で選択した組み合わせの各位置に疑似命令を挿入する。このとき、解析部１２６は、疑似命令を挿入する依存ツリーと、対比する他の依存ツリーとの間で、同じ深さにできる限り同じ種類の演算を指定した命令がくるように、疑似命令の演算の種類を選択する。（ステップＳ１３６）解析部１２６は、疑似命令を挿入した依存ツリーと他の依存ツリーとの間で、同じ深さにある命令を比較してＳＩＭＤ化可能な命令組を検出し、疑似命令を挿入した依存ツリーのＳＩＭＤ化率（または、ＳＩＭＤ化される命令の数（ＳＩＭＤ化数）でもよい）を算出する。
【００７４】
（ステップＳ１３７）解析部１２６は、ステップＳ１３３で全ての組み合わせを選択したか判断する。全て選択した場合は処理をステップＳ１３８に進める。未選択の組み合わせがある場合は、疑似命令の挿入を取り消して依存ツリーを元に戻し、処理をステップＳ１３３に進める。（ステップＳ１３８）解析部１２６は、ステップＳ１３６で算出されたＳＩＭＤ化率（またはＳＩＭＤ化数）が最大になる位置の組み合わせを判定し、判定された組み合わせに従って依存ツリーに疑似命令を挿入する。
【００７５】
図１６は、ノード入替処理の手順例を示すフローチャートである。図１６のフローチャートが示す処理は、前述のステップＳ２において実行される。この処理は、図１５のフローチャートが示す処理の後に、各依存ツリーに対して行われる。
【００７６】
（ステップＳ１４１）解析部１２６は、依存ツリーから、中間コード１４１において後方にある命令（ルートノードに近い命令）から優先的に、命令を１つ選択する。（ステップＳ１４２）解析部１２６は、依存ツリーにおいて、選択した命令から見て子ノードに相当する命令が２つ以上存在するか判断する。存在する場合は処理をステップＳ１４３に進め、存在しない場合は処理をステップＳ１４８に進める。
【００７７】
（ステップＳ１４３）解析部１２６は、依存ツリーの左側から順に、子ノードに相当する命令の命令番号を、ＲＡＭ１０２に確保した記憶領域であるスタックＡに格納する。（ステップＳ１４４）解析部１２６は、命令番号に対応する順序で、子ノードに相当する命令のデータを、ＲＡＭ１０２に確保した他の記憶領域であるスタックＢに格納する。例えば、ステップＳ１４１で依存ツリー３３の命令１６を選択した場合、命令番号＝１２，１５がスタックＡに格納され、命令１２，１５のデータがスタックＢに格納される。
【００７８】
（ステップＳ１４５）解析部１２６は、各命令の命令名に基づいて、スタックＢの中で命令のデータをソートする。例えば、命令１２，１５の順にデータがスタックＢに格納されている場合、命令１５，１２の順にデータが入れ替えられる。（ステップＳ１４６）解析部１２６は、スタックＢに２以上のＬＯＡＤ命令のデータが格納されているとき、各ＬＯＡＤ命令に対応する変数名を、中間コード１４１を参照して確認する。そして、解析部１２６は、変数名に基づいて、スタックＢの中でＬＯＡＤ命令のデータをソートする。
【００７９】
（ステップＳ１４７）解析部１２６は、命令データ１５１におけるスタックＡの命令番号が示す位置に、スタックＢに格納された命令のデータを上書きする。スタックＡの命令番号はソート前の順序で並んでいるため、命令番号と命令の内容との対応関係が更新されることになる。例えば、命令１５のデータが命令番号＝１２の位置に上書きされ、命令１２のデータが命令番号＝１５の位置に上書きされる。（ステップＳ１４８）解析部１２６は、ステップＳ１４１で全ての命令を選択したか判断する。全て選択した場合は処理を終了し、未選択の命令がある場合は処理をステップＳ１４１に進める。
【００８０】
次に、基点命令の選択および依存ツリーの分割（レベル管理）について説明する。
図１７は、依存ツリーの分割例を示す図である。ここでは、図１７に示す命令１〜１４を含む依存ツリー４２が生成された場合を考える。命令３，９はＭＵＬＴ命令であり、命令５，１１，１３はＡＤＤ命令である。命令１，２，４，７，８，１０はＬＯＡＤ命令であり、命令６，１２，１４はＳＴＯＲＥ命令である。命令３は命令１，２に依存し、命令５は命令３，４に依存し、命令６は命令５に依存している。命令９は命令７，８に依存し、命令１１は命令９，１０に依存し、命令１２は命令１１に依存している。命令１３は命令６，１２に依存し、命令１３は命令１４に依存している。
【００８１】
第２の実施の形態では、依存ツリー間の比較を容易にするため、ＳＴＯＲＥ命令である命令６，１２，１４を基点にして、依存ツリー４２を３つの小さな依存ツリーに分割する。すなわち、解析部１２６は、依存ツリー４２を、命令６が基点命令（ルートの命令）であり命令１〜６を含む依存ツリーと、命令１２が基点命令であり命令７〜１２を含む依存ツリーと、命令１４が基点命令であり命令１３，１４を含む依存ツリーとに分割する。
【００８２】
このとき、解析部１２６は、各基点命令についてレベルを算出しておく。基点命令のレベルは、分割前の依存ツリー４２において、基点命令のノードとそのノードの配下にある各リーフノードとの間のパスのうち、最長のパス上に並ぶノードの数である。例えば、命令６のレベルは、命令６と命令１（または命令２）とを結ぶパス上に４個のノードが並ぶことから、４である。命令１２のレベルは、命令１２と命令７（または命令８）とを結ぶパス上に４個のノードが並ぶことから、４である。命令１４のレベルは、命令１４と命令１（または命令２，７，８）とを結ぶパス上に６個のノードが並ぶことから、６である。
【００８３】
図１８は、基点データの例を示す図である。解析部１２６は、基点命令を選択して依存ツリー４２を分割すると、基点データ１５３を生成する。基点データ１５３は、分割後の依存ツリー毎に、ツリーＩＤ（Identifier）、基点番号、レベルおよび命令番号の項目を含む。ツリーＩＤは、分割後の各依存ツリーを識別するための識別子である。基点番号は、基点命令の命令番号である。レベルは、上記のように算出された基点命令のレベルである。命令番号の項目には、分割後の依存ツリーに含まれる命令の命令番号が列挙される。
【００８４】
図１９は、基点選択処理の手順例を示すフローチャートである。図１９のフローチャートが示す処理は、前述のステップＳ３において、依存ツリー毎に実行される。
（ステップＳ１５１）解析部１２６は、ルートノードに近い命令から優先的に、依存ツリーに含まれる命令を１つ選択する。（ステップＳ１５２）解析部１２６は、選択した命令がＳＴＯＲＥ命令であるか判断する。選択した命令がＳＴＯＲＥ命令である場合、その命令を基点命令に採用し、処理をステップＳ１５３に進める。ＳＴＯＲＥ命令でない場合は、その命令を基点命令に採用せず、処理をステップＳ１５６に進める。
【００８５】
（ステップＳ１５３）解析部１２６は、カウンタＣ＝０，レベルＬ＝０に初期化する。（ステップＳ１５４）解析部１２６は、後述するサブルーチンを用いて、基点命令のレベルを算出する。（ステップＳ１５５）解析部１２６は、採用した基点命令をルートノードとする依存ツリーの情報を基点データ１５３に登録する。（ステップＳ１５６）解析部１２６は、ステップＳ１５１で全ての命令を選択したか判断する。全て選択した場合は処理を終了し、未選択の命令がある場合は処理をステップＳ１５１に進める。
【００８６】
図２０は、レベル算出のサブルーチンの手順例を示すフローチャートである。図２０に示すサブルーチンは、パラメータとしてカウンタＣとレベルＬを受け取る。このサブルーチンは、上記のステップＳ１５４において呼び出される。
【００８７】
（ステップＳ１６１）解析部１２６は、カウンタＣをインクリメント（値を１だけ加算）する。（ステップＳ１６２）解析部１２６は、現在のレベルＬの値がカウンタＣの値よりも小さいか判断する。レベルＬの値がカウンタＣの値より小さい場合は処理をステップＳ１６３に進め、それ以外の場合は処理をステップＳ１６４に進める。（ステップＳ１６３）解析部１２６は、レベルＬにカウンタＣの値を代入する。
【００８８】
（ステップＳ１６４）解析部１２６は、現在着目している命令の子ノードに相当する命令が、次のステップＳ１６５で全て選択されたか判断する。全て選択された場合は処理をステップＳ１６７に進め、未選択の命令がある場合は処理をステップＳ１６５に進める。（ステップＳ１６５）解析部１２６は、子ノードに相当する命令を１つ選択する。（ステップＳ１６６）解析部１２６は、ステップＳ１６５で選択した、子ノードに相当する命令について、この時点のレベルＬとカウンタＣをパラメータとして渡して、図２０のサブルーチンを再帰的に呼び出す。その後、処理をステップＳ１６４に進める。（ステップＳ１６７）解析部１２６は、カウンタＣをデクリメント（値を１だけ減算）する。
【００８９】
次に、依存ツリーの符号化について説明する。
図２１は、変換データの例を示す図である。変換データ１４２は、演算の種類と符号との対応関係を示す。解析部１２６は、依存ツリーに含まれる各命令を、変換データ１４２に従って符号に変換する。図２１の例によれば、ＭＵＬＴ命令は“１”に変換され、ＤＩＶ命令は“２”に変換され、ＡＤＤ命令は“３”に変換され、ＳＵＢ命令は“４”に変換され、ＬＯＡＤ命令は“５”に変換され、ＳＴＯＲＥ命令は“６”に変換される。
【００９０】
図２２は、符号化処理の手順例を示すフローチャートである。図２２のフローチャートが示す処理は、前述のステップＳ４において実行される。
（ステップＳ１７１）解析部１２６は、基点データ１５３を参照して、依存ツリーを１つ選択する。（ステップＳ１７２）解析部１２６は、選択した依存ツリーに含まれる命令の数に相当する大きさの配列を、符号データとして生成する。
【００９１】
（ステップＳ１７３）解析部１２６は、ステップＳ１７１で選択した依存ツリーから、木構造に応じた順序で、命令を１つ選択する。例えば、解析部１２６は、帰り掛け深さ優先探索により、依存ツリーを探索して命令を選択する。図１７に示した命令６を基点とする依存ツリーの場合、命令１，２，３，４，５，６の順に選択していく。（ステップＳ１７４）解析部１２６は、変換データ１４２から、選択した命令で行われる演算の種類に対応する符号を検索し、検索した符号を配列に格納する。ステップＳ１７３でｉ個目の命令を選択すると、その命令に対応する符号は配列のｉ番目に格納される。例えば、図１７に示した命令６を基点とする依存ツリーの場合、この依存ツリーに対応する符号データとして、５，５，１，５，３，６という符号列が生成される。
【００９２】
（ステップＳ１７５）解析部１２６は、ステップＳ１７３で全ての命令を選択したか判断する。全て選択した場合は処理をステップＳ１７６に進め、未選択の命令がある場合は処理をステップＳ１７３に進める。（ステップＳ１７６）解析部１２６は、ステップＳ１７１で全ての依存ツリーを選択したか判断する。全て選択した場合は処理を終了し、未選択の依存ツリーがある場合は処理をステップＳ１７１に進める。
【００９３】
次に、依存ツリーの組の候補の算出および依存ツリーの組の決定について説明する。
図２３は、エッジデータとパックデータの例を示す図である。解析部１２６は、依存ツリーの組の候補を算出することで、エッジデータ１５４を生成する。また、解析部１２６は、依存ツリーの組を決定することで、パックデータ１５５を生成する。
【００９４】
エッジデータ１５４は、依存ツリーの組毎に、エッジ番号および２以上の基点番号の項目を含む。エッジ番号は、エッジ（依存ツリーの組）を識別するための番号である。基点番号［Ｓ］（Ｓ＝１，２，・・・）の項目には、依存ツリーの基点命令の命令番号が設定される。基点番号の個数は、ＳＩＭＤの並列度に一致する。ＳＩＭＤ化の際は、基点番号［Ｓ］に対応する依存ツリーの命令に、Ｓ番目のスロットが割り当てられることになる。すなわち、基点番号［１］に対応する依存ツリーの命令にスロット１が割り当てられ、基点番号［２］に対応する依存ツリーの命令にスロット２が割り当てられる。
【００９５】
パックデータ１５５は、エッジデータ１５４に登録された依存ツリーの組のうち、ＳＩＭＤ命令を生成するために採用する１またはそれ以上の依存ツリーの組の集合（パック）を示す。パックデータ１５５は、１またはそれ以上のエッジ番号の項目を含む。エッジデータ１５４とパックデータ１５５とは、エッジ番号によって関連付けられる。
【００９６】
図２４は、候補算出処理の手順例を示すフローチャートである。図２４のフローチャートが示す処理は、前述のステップＳ５において実行される。
（ステップＳ２１１）解析部１２６は、１つのエッジ分のデータを格納するための空のフレームＥ0を生成する。フレームＥ0に含まれる基点番号の項目の数は、ＳＩＭＤの並列度に一致させる。（ステップＳ２１２）解析部１２６は、変数として基点Ｋ，スロットＳを定義し、基点Ｋ＝１，スロットＳ＝１に初期化する。
【００９７】
（ステップＳ２１３）解析部１２６は、後述するサブルーチンを用いて、フレームＥ0およびフレームＥ0からコピーされたフレームに、基点番号を設定していく。このとき、解析部１２６は、フレームＥ0，基点Ｋ，スロットＳを、パラメータとしてサブルーチンに渡す。（ステップＳ２１４）解析部１２６は、基点Ｋをインクリメント（値を１だけ加算）する。（ステップＳ２１５）解析部１２６は、基点Ｋの値が、基点命令の総数（生成された依存ツリーの総数）以下であるか判断する。条件を満たす場合は処理をステップＳ２１３に進め、条件を満たさない場合は処理を終了する。
【００９８】
図２５は、エッジデータ設定のサブルーチンの手順例を示すフローチャートである。図２５のサブルーチンは、パラメータとしてフレームＥ，基点Ｋ，スロットＳを受け取る。このサブルーチンは、上記のステップＳ２１３において呼び出される。
【００９９】
（ステップＳ２２１）解析部１２６は、スロットＳの値がＳＩＭＤの並列度以下であるか、すなわち、フレームＥの基点番号の項目にまだ空の項目が存在するか判断する。空の基点番号の項目がある場合は処理をステップＳ２２２に進め、基点番号の項目が全て埋まった場合は処理をステップＳ２２８に進める。（ステップＳ２２２）解析部１２６は、フレームＥの基点番号［Ｓ］の項目に、Ｋ番目の基点命令の命令番号を設定する。（ステップＳ２２３）解析部１２６は、スロットＳの値をインクリメント（値を１だけ加算）する。また、解析部１２６は、変数として基点Ｃを定義し、Ｃ＝１に初期化する。
【０１００】
（ステップＳ２２４）解析部１２６は、フレームＥをコピーしてフレームＥｃを生成する。フレームＥからフレームＥｃへは、設定済の基点番号が引き継がれる。（ステップＳ２２５）解析部１２６は、現在のフレームＥｃ，基点Ｃ，スロットＳをパラメータとして渡して、図２５のサブルーチンを再帰的に呼び出す。（ステップＳ２２６）解析部１２６は、基点Ｃをインクリメントする。（ステップＳ２２７）解析部１２６は、基点Ｃの値が、基点命令の総数以下であるか判断する。条件を満たす場合は処理をステップＳ２２４に進め、条件を満たさない場合はサブルーチンを終了する。
【０１０１】
（ステップＳ２２８）解析部１２６は、フレームＥに、重複する命令番号が基点番号として含まれているか判断する。同じ命令番号が含まれる場合は処理をステップＳ２３３に進め、それ以外の場合は処理をステップＳ２２９に進める。（ステップＳ２２９）解析部１２６は、フレームＥに含まれる基点番号が示す基点命令の「レベル」が全て同じであるか判断する。レベルが同じ場合は処理をステップＳ２３０に進め、レベルが異なる場合は処理をステップＳ２３３に進める。（ステップＳ２３０）解析部１２６は、フレームＥが示す複数の依存ツリーの間に、依存関係があるか判断する。依存関係がある場合は処理をステップＳ２３３に進め、依存関係がない場合は処理をステップＳ２３１に進める。
【０１０２】
（ステップＳ２３１）解析部１２６は、フレームＥが示す複数の依存ツリーに属する命令を組み合わせることが、プロセッサのアーキテクチャに反するか判断する。アーキテクチャ違反の例としては、メモリ割り当ての制約を満たさない、データの型（整数型や浮動小数点型など）がＳＩＭＤ命令で扱うことができない型である、などが挙げられる。アーキテクチャに反する場合は処理をステップＳ２３３に進め、それ以外の場合は処理をステップＳ２３２に進める。（ステップＳ２３２）解析部１２６は、フレームＥのデータをエッジデータ１５４に登録し、サブルーチンを終了する。（ステップＳ２３３）解析部１２６は、フレームＥのデータを破棄し、サブルーチンを終了する。
【０１０３】
図２６は、エッジデータ生成の流れの例を示す図である。図２５に示したサブルーチンを再帰的に実行していくことで、基点番号［１］，基点番号［２］，・・・の順に、基点命令の命令番号がフレームＥに１つずつ設定されていく。そして、全ての基点番号の項目が埋まった時点で、フレームＥが示す複数の依存ツリーを組み合わせ可能か判定され、組み合わせ不可な複数の依存ツリーを示すデータは破棄される。例えば、基点番号［１］＝６，基点番号［２］＝６というデータは破棄される。また、複数の基点命令のレベルが全て同じか判定され、レベルが異なる基点命令の組を示すデータは破棄される。例えば、基点番号＝６の基点命令のレベルと基点番号＝１４の基点命令のレベルとが異なるとき、基点番号［１］＝６，基点番号［２］＝１４というデータは破棄される。
【０１０４】
図２７は、パックデータの候補の例を示す図である。解析部１２６は、複数のエッジのべき集合をパックの集合として算出し、各パックをＳＩＭＤ化できる命令の数の観点から評価することで、パックを１つ選択する。例えば、互いに独立なエッジ１，２が存在するとき、エッジ１のみを採用したパック１と、エッジ２のみを採用したパック２と、エッジ１，２の両方を採用したパック３とが評価される。
【０１０５】
図２８は、符号データからスコアを算出する例を示す図である。パックを評価するために、解析部１２６は、各パックのスコアを算出する。スコアの高いパックほど、ＳＩＭＤ化できる命令が多いパックであることを示している。解析部１２６は、エッジ毎に、複数の依存ツリーの間で符号データを比較して、対応する位置にある命令の組であって演算の種類が同じ命令の組の数を、エッジのスコアとして算出する。そして、解析部１２６は、エッジ毎のスコアを合算して、パックのスコアとする。
【０１０６】
図２９は、ＳＩＭＤ化判定処理の手順例を示すフローチャートである。図２９のフローチャートが示す処理は、前述のステップＳ６において実行される。
（ステップＳ２４１）解析部１２６は、変数としてエッジｅとパックＰを定義し、エッジｅ＝０，パックＰ＝Φ（空集合）に初期化する。（ステップＳ２４２）解析部１２６は、変数として最大スコアＺを定義し、最大スコアＺ＝−１に初期化する。（ステップＳ２４３）解析部１２６は、後述するサブルーチンを用いて、スコアが最大となるパックを探索する。
【０１０７】
（ステップＳ２４４）解析部１２６は、最大スコアＺの値が初期値＝−１のままであるか、すなわち、パックを１つも発見できなかったか判断する。最大スコアＺ＝−１の場合は処理をステップＳ２４６に進め、それ以外の場合は処理をステップＳ２４５に進める。（ステップＳ２４５）解析部１２６は、パックデータ１５５からＳＩＭＤ化する命令組を決定する。組み合わせる命令は、同じエッジに含まれる複数の依存ツリーの間の対応する位置にある命令同士である。（ステップＳ２４６）解析部１２６は、中間コード１４１における現在の翻訳単位に含まれる命令をＳＩＭＤ化することを中止する。
【０１０８】
図３０は、パックデータ設定のサブルーチンの手順例を示すフローチャートである。図３０のサブルーチンは、パラメータとしてエッジｅ，パックＰを受け取る。このサブルーチンは、上記のステップＳ２４３において呼び出される。
【０１０９】
（ステップＳ２５１）解析部１２６は、後述する方法によって、符号データを用いて、パックＰのスコアを算出する。（ステップＳ２５２）解析部１２６は、エッジｅをインクリメント（値を１だけ加算）する。（ステップＳ２５３）解析部１２６は、エッジｅの値が、最大のエッジ番号以下であるか判断する。条件を満たす場合は処理をステップＳ２５４に進め、条件を満たさない場合はサブルーチンを終了する。
【０１１０】
（ステップＳ２５４）解析部１２６は、ｅ番目のエッジ（エッジ番号＝ｅのエッジ）を含むパックを評価する必要があるか判断する。次の３つの条件の少なくとも１つに該当するとき、ｅ番目のエッジを含むパックを評価しなくてよいと判断する。（１）ｅ番目のエッジの依存ツリーが、パックＰに既に含まれている。（２）ｅ番目のエッジの依存ツリーが、パックＰに既に含まれている何れかの依存ツリーと依存関係にある。（３）現時点のパックＰのスコアが、計算済の他のパックのスコアの最大値よりも所定差以上下回っており、パックＰにｅ番目のエッジを追加しても最良のパックになる見込みがない。ｅ番目のエッジを含むパックを評価する必要がある場合、処理をステップＳ２５５に進め、そのようなパックを評価する必要がない場合、処理をステップＳ２５８に進める。
【０１１１】
（ステップＳ２５５）解析部１２６は、ｅ番目のエッジをパックＰに追加する。（ステップＳ２５６）解析部１２６は、ｅ番目のエッジを含むパックＰとエッジｅをパラメータとして渡し、図３０に示すサブルーチンを再帰的に呼び出す。（ステップＳ２５７）解析部１２６は、ステップＳ２５５で追加したｅ番目のエッジをパックＰから削除する。（ステップＳ２５８）解析部１２６は、ｅ番目のエッジを含まないパックＰとエッジｅをパラメータとして渡し、図３０に示すサブルーチンを再帰的に呼び出す。
【０１１２】
図３１は、スコア算出処理の手順例を示すフローチャートである。図３１のフローチャートが示す処理は、上記のステップＳ２５１において実行される。
（ステップＳ２６１）解析部１２６は、パックに含まれるエッジを１つ選択する。（ステップＳ２６２）解析部１２６は、配列に含まれる符号を特定するためのインデックスｐの値を１つ選択する。インデックスｐの値は、１から、エッジに属する複数の依存ツリーに対応する複数の配列の中で最も長い配列の配列長まで変化する。（ステップＳ２６３）解析部１２６は、変数としてスロットＳを定義し、スロットＳ＝１に初期化する。
【０１１３】
（ステップＳ２６４）解析部１２６は、ステップＳ２６１で選択したエッジの基点番号［Ｓ］に対応する依存ツリーを選択し、その依存ツリーに対応する符号データである配列を取得する。そして、解析部１２６は、ＲＡＭ１０２に確保した記憶領域であるスタックＸに、取得した配列に含まれるｐ番目の符号を格納する。なお、取得した配列の配列長がｐより小さいときは、命令が無いことを示す所定の符号（例えば“０”）をスタックＸに格納する。（ステップＳ２６５）解析部１２６は、スロットＳをインクリメント（値を１だけ加算）する。（ステップＳ２６６）解析部１２６は、スロットＳの値がＳＩＭＤの並列度以下であるか判断する。スロットＳの値が並列度以下の場合は処理をステップＳ２６４に進め、並列度より大きい場合は処理をステップＳ２６７に進める。
【０１１４】
（ステップＳ２６７）解析部１２６は、スタックＸに格納された符号が全て同じであるか、すなわち、対応する位置にある命令間で演算の種類が全て同じか判断する。全て同じ場合は処理をステップＳ２６８に進め、同じでない場合は処理をステップＳ２６９に進める。（ステップＳ２６８）解析部１２６は、パックのスコアをインクリメントする。
【０１１５】
（ステップＳ２６９）解析部１２６は、ステップＳ２６２で全てのインデックスｐの値を選択したか判断する。全て選択した場合は処理をステップＳ２７０に進め、未選択のインデックスｐの値がある場合は処理をステップＳ２６２に進める。（ステップＳ２７０）解析部１２６は、ステップＳ２６１で全てのエッジを選択したか判断する。全て選択した場合は処理をステップＳ２７１に進め、未選択のエッジがある場合は処理をステップＳ２６１に進める。（ステップＳ２７１）解析部１２６は、ステップＳ２６８の処理を通じて算出されたパックのスコアが、現在の最大スコアＺより大きいか判断し、現在の最大スコアＺより大きい場合は、最大スコアＺを算出されたスコアに置き換える。
【０１１６】
図３２は、パックデータ生成の流れの例を示す図である。図３０に示したサブルーチンが再帰的に呼び出されることで、スコア評価の処理が、ｅ番目のエッジがパックＰに含まれるときの処理と含まれないときの処理とに分岐していく。まず、１番目のエッジをパックＰに含めるか否かによって、処理が２つに分岐する。次に、２番目のエッジをパックＰに含めるか否かによって、２つに分岐した処理それぞれが更に２つに分岐し、合計で処理が４つに分岐することになる。以下、エッジの数に応じて処理の分岐が発生する。
【０１１７】
第２の実施の形態の端末装置１００によれば、中間コード１４１に含まれる命令の間の依存関係を表した複数の依存ツリーが、高さの調整や演算順序の入れ替えなどを通じて変形される。これにより、複数の依存ツリーができる限り同じ形状になり、また、依存ツリー間の対応する位置に同じ種類の演算を指定した命令が存在する確率が高くなる。このため、変形した依存ツリーの間で、対応する位置にある命令同士を比較すれば、ＳＩＭＤ化可能な命令組を発見することができ、ＳＩＭＤ化可能な命令組を効率的に探索できる。
【０１１８】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現でき、第２の実施の形態の情報処理は、端末装置１００にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。
【０１１９】
プログラムを流通させる場合、例えば、当該プログラムを記録した可搬記録媒体が提供される。また、プログラムを他のコンピュータの記憶装置に格納しておき、ネットワーク経由でプログラムを配布することもできる。コンピュータは、例えば、可搬記録媒体に記録されたプログラムまたは他のコンピュータから受信したプログラムを、記憶装置（例えば、ＨＤＤ１０３）に格納し、当該記憶装置からプログラムを読み込んで実行する。ただし、可搬記録媒体から読み込んだプログラムを直接実行してもよく、他のコンピュータからネットワークを介して受信したプログラムを直接実行してもよい。
【符号の説明】
【０１２０】
１０  情報処理装置
１１  記憶部
１１ａ  第１のコード
１１ｂ  第２のコード
１２  演算部
１３ａ，１３ｂ  ツリー
【図１】
0005846006.tif 000002
【図２】
0005846006.tif 000003
【図３】
0005846006.tif 000004
【図４】
0005846006.tif 000005
【図５】
0005846006.tif 000006
【図６】
0005846006.tif 000007
【図７】
0005846006.tif 000008
【図８】
0005846006.tif 000009
【図９】
0005846006.tif 000010
【図１０】
0005846006.tif 000011
【図１１】
0005846006.tif 000012
【図１２】
0005846006.tif 000013
【図１３】
0005846006.tif 000014
【図１４】
0005846006.tif 000015
【図１５】
0005846006.tif 000016
【図１６】
0005846006.tif 000017
【図１７】
0005846006.tif 000018
【図１８】
0005846006.tif 000019
【図１９】
0005846006.tif 000020
【図２０】
0005846006.tif 000021
【図２１】
0005846006.tif 000022
【図２２】
0005846006.tif 000023
【図２３】
0005846006.tif 000024
【図２４】
0005846006.tif 000025
【図２５】
0005846006.tif 000026
【図２６】
0005846006.tif 000027
【図２７】
0005846006.tif 000028
【図２８】
0005846006.tif 000029
【図２９】
0005846006.tif 000030
【図３０】
0005846006.tif 000031
【図３１】
0005846006.tif 000032
【図３２】
0005846006.tif 000033