(57)【特許請求の範囲】
【請求項１】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出するループ判別手段と、
この検出したループを最適化するループ最適化手段と、
最適化したループを保持する最適化ループ保持手段を具備し、
前記ループを実行するとき、前記ループ最適化手段により、このループのプログラムを最適化してこれにもとづき動作を実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【請求項２】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、ブランチ命令を検出することにより動的にループを検出するループ判別手段と、
この検出したループを最適化するループ最適化手段と、
最適化したループを保持する最適化ループ保持手段を具備し、
前記ループを実行するとき、前記ループ最適化手段により、このループのプログラムを最適化してこれにもとづき動作を実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【請求項３】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出するループ判別手段と、
この検出したループを最適化して、アンローリングを行うループ最適化・アンローリング手段と、
最適化したループを保持する最適化ループ保持手段を具備し、
前記ループを実行するとき、前記ループ最適化・アンローリング手段により、このループのプログラムを最適化し、アンローリングを行い、これにもとづき動作を実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【請求項４】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、ブランチ命令を検出することにより動的にループを検出するループ判別手段と、
この検出したループを最適化して、アンローリングを行うループ最適化・アンローリング手段と、
最適化したループを保持する最適化ループ保持手段を具備し、
前記ループを実行するとき、前記ループ最適化・アンローリング手段によりこのループのプログラムを最適化し、アンローリングを行い、これにもとづき動作を実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【請求項５】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出し、またコンパイラが付加した記号によりループがプログラム中で複数回参照されるか否かを判別して検出するループ判別・複数回参照判別手段と、
検出したループを最適化するループ最適化手段と、
最適化したループを保持する最適化ループ保持手段と、
メモリ内の前記該当ループを最適化したループへ書き換える書き換え手段とを具備し、
前記複数回参照されるループを実行するとき、前記ループ最適化手段によりこのループプログラムを最適化し、この最適化したもので前記該当ループを書き換え、実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【請求項６】
ＶＬＩＷ形式のプロセッサであって、
命令キャッシュから取り出した命令列において、ブランチ命令を検出することにより動的にループを検出し、またループがプログラム中で複数回参照されるか否かを動的に判別して検出するループ判別・複数回参照判別手段と、
検出したループを最適化するループ最適化手段と、
最適化したループを保持する最適化ループ保持手段と、
メモリ内の前記該当ループを最適化したループへ書き換える書き換え手段とを具備し、
前記複数回参照されるループを実行するとき、前記ループ最適化手段によりこのループプログラムを最適化し、この最適化したもので前記ループを書き換え、実行することを特徴とするＶＬＩＷ形式のプロセッサ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＶＬＩＷプロセッサ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ  Ｐｒｏｃｅｓｓｏｒ）に係り、特にＶＬＩＷ形式の命令におけるループ動作を動作時間が短縮できるように、最適化処理するＶＬＩＷプロセッサに関する。
【０００２】
【従来の技術】
ＶＬＩＷプロセッサは１命令で、例えば３つの複数の処理を指定して並列に実行するため、高速にデータ処理を行うことができる。
【０００３】
図１６（Ａ）に示す如く、ＶＬＩＷプロセッサでは、複数の操作「ａｄｄ（加算）、ｓｕｂ（減算）、ｌｄ（ロード）」を１個の命令内に、並列に動作可能な操作として指定できるので、ＶＬＩＷプロセッサでは１個のプログラムの実行に要する命令数が減少する。またＶＬＩＷプロセッサにおいては、後述する依存関係がなければ、１命令に記述してある操作は全て同じタイミングのクロックで実行される。つまり並列に実行される。
【０００４】
ところで、ある先行操作が結果として出力するレジスタの内容を、後述操作が入力として利用する場合、この２つの操作間には依存関係が生じる。この依存関係を真の依存関係と呼ぶ。この依存は解消することができず、実行サイクル数に大きな影響を与える。
【０００５】
また先行操作が入力とするレジスタに後続操作が出力として書き込む場合、この２つの操作間には依存関係が生じる。この依存関係を逆依存関係と呼ぶ。さらに先行操作が出力とするレジスタに後続操作が出力として書き込む場合にも、この２つの操作間には依存関係が生じる。この依存関係を出力依存関係と呼ぶ。
【０００６】
真の依存関係とは、図１６（Ｂ）に示す如く、先行操作ａｄｄ（レジスタｆｒ３  のデータとレジスタｆｒ４  のデータを加算してレジスタｆｒ５  に入力する操作）のレジスタｆｒ５  のデータを、後続操作ｓｕｂ（レジスタｆｒ５  のデータからレジスタｆｒ６  のデータを引きレジスタｆｒ７  に入力する操作）が入力して利用する場合をいう。
【０００７】
逆依存関係とは、図１６（Ｃ）に示す如く、先行操作ａｄｄ（レジスタｆｒ２  のデータとレジスタｆｒ３  のデータを加算してレジスタｆｒ４  に入力する操作）の入力とするレジスタｆｒ２  に、後続操作ｓｕｂ（レジスタｆｒ５  のデータからレジスタｆｒ６  のデータを引き、レジスタｆｒ２  にこの結果を入力する操作）が出力として書き込む場合をいう。
【０００８】
出力依存関係とは、図１６（Ｄ）に示す如く、先行操作ａｄｄ（レジスタｆｒ２  のデータとレジスタｆｒ３  のデータを加算してレジスタｆｒ４  にこの結果を出力する操作）の出力とするレジスタｆｒ４  に、後続操作ｓｕｂ（レジスタｆｒ５  のデータからレジスタｆｒ６  のデータを引きレジスタｆｒ４  にこの結果を出力する操作）が出力として書き込む場合をいう。
【０００９】
これらにおいて、図１６（Ｃ）（Ｄ）に示す如く、後続操作において、出力データ書き込み先のレジスタをｆｒ８  あるいはｆｒ９  の如く、先行操作におけるレジスタと一致しないように、付加的なレジスタｆｒ８  、ｆｒ９  を用いる、レジスタリネーミングという手法により、逆依存関係と出力依存関係を解消することができる。このように、逆依存関係と出力依存関係においては、付加的なレジスタを設け、レジスタと値との間の対応関係を再構築することにより、先行操作と後続操作との操作状態を改善することができる。勿論真の依存関係を解消することはできない。
【００１０】
このようにして、レジスタリネーミングを行うことにより、逆依存関係及び出力依存関係を解消し、データ処理速度を向上することができる。しかしながらＶＬＩＷ形式のプロセッサの場合、この解消した依存関係の中に真の依存関係が絡んでいると、レジスタリネーミングの効果が発揮できない場合がある。これはＶＬＩＷ形式のプロセッサであるため、１命令中に複数の操作を持つためである。
【００１１】
例えば図１７に示す如く、１命令中に最大３操作を含むことができる場合において、命令１の中に操作Ａが含まれ、後続の命令２の中に操作Ｂと操作Ｃが含まれており、操作Ｂが操作Ａに対して逆依存関係を持ち、操作Ｃが操作Ａに対して真の依存関係を持つものとする。
【００１２】
いまレジスタリネーミングにより操作Ａと操作Ｂ間の逆依存関係は解消されるものとしても、操作Ａと操作Ｃの間の真の依存関係は解消されない。このため命令１の操作Ａのレーテンシつまり実行時間の分だけ、後続の命令２の実行が待たされることになる。操作Ｃにとっては真の依存関係であるために必要なレーテンシであるが、操作Ｂにとってはレジスタリネーミングでレーテンシの分のおくれを解消しようとした効果が活かされていない。勿論出力依存関係が存在する場合も同様である。従来のＶＬＩＷ形式のプロセッサではこのような問題があった。
【００１３】
【発明が解決しようとする課題】
このように、ＶＬＩＷ形式のプロセッサでは、先行命令と後続命令との間に、真の依存関係と逆依存関係（または出力依存関係）が含まれているときに、レジスタリネーミングにより逆依存関係（または出力依存関係）を解消しても、真の依存関係が存在するため実行性能は向上しなかった。
【００１４】
したがって、本発明の目的は、真の依存関係が存在する場合でも、レジスタリネーミングにより依存関係を解消することで得られる命令列に対して、十分な性能向上を可能にしたＶＬＩＷ形式のプロセッサを提供することである。
【００１５】
【課題を解決するための手段】
本発明の原理図を図１に示す。図１において、１はメモリ、２は命令キャッシュ、３はセレクタ、４はデコーダ、５はレジスタリネーミング部、６はループ判別部、７はループ最適化部、８は演算部、９は最適化ループメモリである。本発明の前記目的は下記の構成により構成することができる。
【００１６】
（１）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出するループ判別手段６と、この検出したループを最適化するループ最適化手段７と、最適化したループを保持する最適化ループ保持手段９を具備し、前記ループを実行するとき、前記ループ最適化手段により、このループのプログラムを最適化してこれにもとづき動作を実行することを特徴とする。
【００１７】
（２）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、ブランチ命令を検出することにより動的にループを検出するループ判別手段と、この検出したループを最適化するループ最適化手段７と、最適化したループを保持する最適化ループ保持手段９を具備し、前記ループを実行するとき、前記ループ最適化手段により、このループのプログラムを最適化してこれにもとづき動作を実行することを特徴とする。
【００１８】
（３）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出するループ判別手段６と、この検出したループを最適化して、アンローリングを行うループ最適化・アンローリング手段と、最適化したループを保持する最適化ループ保持手段９を具備し、前記ループを実行するとき、前記ループ最適化・アンローリング手段により、このループのプログラムを最適化し、アンローリングを行い、これにもとづき動作を実行することを特徴とする。
【００１９】
（４）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、ブランチ命令を検出することにより動的にループを検出するループ判別手段と、この検出したループを最適化して、アンローリングを行うループ最適化・アンローリング手段と、最適化したループを保持する最適化ループ保持手段９を具備し、前記ループを実行するとき、前記ループ最適化・アンローリング手段によりこのループのプログラムを最適化し、アンローリングを行い、これにもとづき動作を実行することを特徴とする。
【００２０】
（５）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、コンパイラが付加した記号によりループを判別してループを検出し、またコンパイラが付加した記号によりループがプログラム中で複数回参照されるか否かを判別して検出するループ判別・複数回参照判別手段と、検出したループを最適化するループ最適化手段７と、最適化したループを保持する最適化ループ保持手段９と、メモリ内の前記該当ループを最適化したループへ書き換える書き換え手段とを具備し、前記複数回参照されるループを実行するとき、前記ループ最適化手段９によりこのループプログラムを最適化し、この最適化したもので前記該当ループを書き換え、実行することを特徴とする。
【００２１】
（６）ＶＬＩＷ形式のプロセッサであって、命令キャッシュ２から取り出した命令列において、ブランチ命令を検出することにより動的にループを検出し、またループがプログラム中で複数回参照されるか否かを動的に判別して検出するループ判別・複数回参照判別手段と、検出したループを最適化するループ最適化手段と、最適化したループを保持する最適化ループ保持手段９と、メモリ内の前記該当ループを最適化したループへ書き換える書き換え手段とを具備し、前記複数回参照されるループを実行するとき、前記ループ最適化手段によりこのループプログラムを最適化し、この最適化したもので前記ループを書き換え、実行することを特徴とする。
【００２２】
これにより下記の作用効果を奏する。
【００２３】
（１）ループを検出し、このループについて逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行うので、真の依存関係がある操作が存在する場合でも、ループを高速に実行することができる。
【００２４】
（２）ループの存在を、その命令を動的に判別することにより検出し、このループについての操作において逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行うので、コンパイラにループマークの付加等の余分の負担をかけることなく、真の依存関係がある操作が存在する場合でも、ループを高速に実行することができる。
【００２５】
（３）ループについての操作において、逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、この最適化後にこの最適化したものをコピーするアンローリングを行い、これを実行するように構成したので、ループ全体の実行サイクルを大きく削減することができる。
【００２６】
（４）ループの存在を、その命令を動的に判別することにより検出し、これにおける逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、この最適化後にこの最適化したものをコピーするアンローリングを行い、これを実行するように構成したので、コンパイラにループマークの付加等の余分の負担をかけることなく、真の依存関係がある操作が存在する場合でもループを高速に実行することができる。
【００２７】
（５）ループについての操作において、逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、またこのループがプログラム中で複数回参照される場合、前記と同様に最適化されたループを高速処理できるのみならず、２回目以降このループを呼び出す場合、メモリ内のループを示す命令列を最適化されたループの命令列に書き換えることにより、今度はループの１回目から最適化された命令列を実行することができ、２回目以降に呼び出されたループも高速実行することができる。しかもメモリ内のループを書き換えた場合、２回目以降にそのループを実行することになってもループ最適化手段を使用する必要がない。
【００２８】
（６）ループの存在をその命令を動的に判別することにより検出し、また同時にこのループがプログラム中で複数回参照されることを動的に検出し、ループについての操作において逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移動する最適化処理を行い、またこのループがプログラム中で複数回参照される場合、前記と同様に最適化されたループを高速処理できるのみならず、２回目以降このループを呼び出す場合、メモリ内のループを示す命令列を最適化されたループの命令列に書き換えることにより、今度はループの１回目から最適化された命令列を実行することができ、２回目以降に呼び出されたループも高速実行することができる。しかもメモリ内のループを書き換えた場合、２回目以降にそのループを実行することになってもループ最適化手段を使用する必要がない。
【００２９】
【発明の実施の形態】
本発明の一実施の形態を図２〜図４にもとづき説明する。図２は本発明の一実施の形態を示し、図３は本発明のレジスタリネーミング及び最適化状態動作説明図を示し、図４はループの実行サイクル説明図である。
【００３０】
図２において、他図と同記号は同一部を示し、１はメモリ、２は命令キャッシュ、３はセレクタ、４はデコーダ、５はレジスタリネーミング部、６はループ判別部、７はループ最適化部、８は演算部、９は最適化ループメモリ、１０はファイル、１１はループ記号付与コンパイラである。
【００３１】
メモリ１は、ループ記号付与コンパイラ１１により、ソースプログラムからコンパイラされた機械語化されたプログラムが保持されるものである。なお、ループ命令の初めと終わりには、ループ命令を示すループ記号が、ループ記号付与コンパイラ１１により付与されている。
【００３２】
命令キャッシュ２は、演算に必要な命令部分があらかじめメモリ１から出力され保持されるものである。
【００３３】
セレクタ３は、制御信号にもとづき、命令キャッシュ２または最適化ループメモリ９のいずれからか伝達された命令を出力するものである。
【００３４】
デコーダ４は、セレクタ３から出力された命令を解読するものである。
【００３５】
レジスタリネーミング部５は、前記デコーダ４で解読された命令に、逆依存関係あるいは出力依存関係が存在したとき、これをリネーミングして解消するものである。
【００３６】
ループ判別部６は、実行すべき命令にループが存在するか否かを、例えばループ記号付与コンパイラ１１の付与したループ記号にもとづき判別するものである。
【００３７】
ループ最適化部７は、ループ部分の命令について、逆依存関係あるいは出力依存関係の解消にもとづき、後述するように、その操作タイミングを前の方に移動する最適化を行うものである。
【００３８】
演算部８は、前記デコーダ４により解読され、レジスタリネーミング部５、ループ判別部６等を経由された命令を実行するものであり、複数の操作を実行できるＶＬＩＷ形の演算部である。
【００３９】
最適化ループメモリ９は、ループ最適化部７により最適化された命令が保持されるものである。
【００４０】
ファイル１０は、ソースプログラムが保持されるプログラム保持部である。
【００４１】
ループ記号付与コンパイラ１１は、ファイル１０から出力されたソースプログラムをコンパイルするものであるが、ループ部分が存在することを検出してこれにループであることを示すループ記号を付与するものである。
【００４２】
図２の動作を説明する。
【００４３】
ループ記号付与コンパイラ１１は、ファイル１０から取り出されたソースプログラムをコンパイルして機械語に変換する。このとき、ループ記号付与コンパイラ１１はループの有無をチェックし、ループを検出したとき、ループの先頭と末尾にループを示すループ記号を付与する。
【００４４】
このようにしてコンパイルされた命令列はプログラムの実行にともない命令キャッシュ２に格納される。
【００４５】
セレクタ３は、通常は命令キャッシュ２側からの命令を出力し、ループ判別部６から判別記号が印加されたとき最適化ループメモリ９からの命令を出力するように構成されているので、命令キャッシュ２から取り出された命令がデコーダ４に送出されてデコードされる。
【００４６】
いま命令キャッシュ２から取り出した命令列が、図３（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（７）の場合を考える。ＶＬＩＷ（１）は、操作ａ１と２つのｎｐ（ｎｏ  ｏｐｅｒａｔｉｏｎ）から構成され、ＶＬＩＷ（２）は操作ａ２と２つのｎｐから構成され、ＶＬＩＷ（３）は操作ｂ１、ａ３と１つのｎｐから構成され、ＶＬＩＷ（４）は操作ｂ２と２つのｎｐから構成され、ＶＬＩＷ（５）は操作ｃ１、ｂ３と１つのｎｐから構成され、ＶＬＩＷ（６）は操作ｃ２と２つのｎｐから構成され、ＶＬＩＷ（７）は操作ｃ３と２つのｎｐから構成されている。
【００４７】
そして操作ａ１とａ２、ａ２とａ３の間、操作ｂ１とｂ２、ｂ２とｂ３の間、また操作ｃ１とｃ２、ｃ２とｃ３の間に真の依存関係があり、操作ａ２とｂ１、ｂ２とｃ１の間に逆依存関係のある命令列を考える。
【００４８】
また、各々の命令のレーテンシは３τとする。
【００４９】
そしてこの命令列はループ内部の命令列とし、メモリ１に格納され、プログラムの実行にともなって命令キャッシュ２に格納されているものとする。なお、ループ終了の条件判別に関わる命令の実行時間は考えないものとする。
【００５０】
この命令列はメモリ１から命令キャッシュ２に転送され、その後セレクタ３を通り、デコーダ４に転送されて、デコードされる。
【００５１】
このデコーダ４でデコードされたあとで、レジスタリネーミング部５により、図３（Ｂ）に示す如く、操作ａ２−ｂ１及び操作ｂ２−ｃ１における逆依存関係が解消される。
【００５２】
それから、ループ判別部６に、図３（Ｂ）に示す如き、逆依存関係の解消された命令列が入力される。ループ判別部６では、前記ループ記号付与コンパイラ１１により付加されたループ記号により、これらの命令列がループ内の命令列であることを判別し、セレクタ５に判別信号を送出する。
【００５３】
この判別後、演算部８及びループ最適化部７にこれらの命令列を送り、演算部８において、１回目のループを実行する。このとき、操作ａ１とａ２、ａ２とａ３の間、操作ｂ１とｂ２、ｂ２とｂ３の間、また操作ｃ１とｃ２、ｃ２とｃ３の間の真の依存関係が解決されないので、この図４（Ａ）の命令列の実行サイクルは、図４（Ｂ）に示す如く、２１τを必要とする。
【００５４】
またループ最適化部７に転送された、図３（Ｂ）に示す命令列は、このループ最適化部７において、図３（Ｃ）に示す如く、最適化される。すなわち、操作ａ２−ｂ１における逆依存関係及び操作ｂ２−ｃ１における逆依存関係がそれぞれ解消されたので、操作ｂ１はａ２と同じ命令におくことができ、それに伴って操作ｂ１に対して真の依存関係がある操作ｂ２も操作ａ３と同じ命令に置けることになり、ｂ１〜ｂ３の操作が１命令ずつ、もとの命令列よりも前の命令に置くことができる。
【００５５】
同様にｃ１〜ｃ３の操作が２命令ずつ、もとの命令列よりも前の命令に置くことができる。この結果、図３（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（７）を、同（Ｃ）に示す如き命令列新ＶＬＩＷ（１）〜新ＶＬＩＷ（５）に最適化することができる。そしてこの図３（Ｃ）に示す如く、最適化された命令列を最適化ループメモリ９に転送し、保持する。
【００５６】
セレクタ３には、ループ判別部６から前記判別信号が印加されているので、２回目のループからは、図３（Ｃ）に示す最適化された命令列を出力し、これにもとづき演算部８が実行する。この最適化されたループは、図４（Ｃ）、（Ｄ）に示す如く、各命令のレーテンシが、同様に３τとすれば１５τで実行サイクルが終了し、前記（Ａ）、（Ｂ）に示す場合の２１τに比較すれば１回のループで実行されるサイクル数を約７０％に削減することができる。
【００５７】
本発明の第２の実施の形態を図５及び図６にもとづき、他図を参照して説明する。
【００５８】
第２の実施の形態では、命令列がループの中にあるか否かの判断を命令列を解析することで動的に判断するループ判別部６′を使用する。またコンパイラ１１′もループに対して記号をつけない通常のものを使用する。また図２と同記号は同一部である。
【００５９】
ループの検出は、例えば図６に示す如く、ブランチ命令ｂｒｃを検出することにより行う。図６は、レジスタｇｒ２５の内容を１００回行うセット命令と、１回終了毎にレジスタｇｒ２５の値から１を引きレジスタｇｒ２５に再記入することと、ｇｒ２５の値が０でなければ跳ぶことを求めるブランチ命令ｂｒｃを示している。
【００６０】
従ってこのブランチ命令を検出することによりループ判別部６′は動的にループの存在を判断することができる。
【００６１】
通常は命令キャッシュ２−セレクタ３−デコーダ４−レジスタリネーミング部５−ループ判別部６′−演算部８というルートで演算が行われるが、ループ判別部６′がループを検出すると、ループ最適化部７が、前記図３（Ｃ）に示す如く、これに対し最適化処理を行い、最適化ループメモリ９に、図３（Ｃ）に示した如き命令列を格納する。
【００６２】
ループの２回目以降は、図２と同様にループ判別部６′からの判別信号にもとづきセレクタ３が最適化ループメモリ９から取り出された、図３（Ｃ）に示す最適化された命令列を出力し、これにもとづき演算部８が実行する。
【００６３】
これにより、図２の場合と同様に、最適化されたループでは、図４（Ｃ）、（Ｄ）に示す如く、図４（Ａ）、（Ｂ）に示す場合の約７０％に実行されるサイクル数を削減することができる。
【００６４】
本発明の第３の実施の形態を図７〜図１１にもとづき、他図を参照して説明する。図７は本発明の第３の実施の形態を示し、図８はレジスタリネーミング及び最適化状態説明図、図９はアンローリング状態説明図、図１０は最適化を行う前の実行サイクル説明図、図１１は最適化とループアンローリングを行った後のループの実行サイクル説明図である。
【００６５】
本発明の第３の実施の形態では、検出したループを最適化し、これをアンローリングつまり複数回コピーして使用するものである。図７において図２と同記号は同一部分を示し、７−１はループ最適化・アンローリング部である。
【００６６】
ループ最適化・アンローリング部７−１は、レジスタリネーミング部５により、図８（Ａ）に示す如き命令列が同（Ｂ）に示す如く、逆依存関係が解消されたものを、同（Ｃ）に示す如く、最適化処理を行うとともに、ループ終了の条件判別のための命令列新ＶＬＩＷ（６）と新ＶＬＩＷ（７）を除いた部分Ａ″を、図９に示す如く、複数重コピーするアンローリングを行い、これを最適化ループメモリ９に格納する。例えば１０１回まわるループが存在するとき、アンローリングを１０重で行い、演算部８がこのアンローリングされたループを１０回実行すれば、最適化する前の命令列の実行に加えて１０重回したループを１０回回転するので、１０１回ループを行うことになり、全体の実行サイクルを後述するように大きく削減することができる。
【００６７】
図７の動作を説明する。
【００６８】
ループ信号付与コンパイラ１１は、ファイル１０から取り出されたソースプログラムをコンパイルして機械語に変換するが、前記図２と同様に、ループの有無をチェックし、ループを検出したとき、図８（Ａ）に示す如く、ループの先頭と末尾にループ記号（Ｌ）、（Ｌ、Ｌ）を付与する。そしてコンパイルされた命令列はプログラムの実行にともない命令キャッシュ２に格納される。
【００６９】
セレクタ３は通常は命令キャッシュ２側からの命令を出力するように構成されているので、命令キャッシュ２から取り出された命令がデコーダ４に送出されてデコードされる。
【００７０】
いま命令キャッシュ２から取り出した命令列が図８（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（９）の場合を考える。ＶＬＩＷ（１）は操作ａ１と２つのｎｐ（ｎｏ  ｏｐｅｒａｔｉｏｎ）から構成されＶＬＩＷ（２）は操作ａ２と２つのｎｐから構成され、ＶＬＩＷ（３）は操作ｂ１、ａ３と１つのｎｐから構成され、ＶＬＩＷ（４）は操作ｂ２と２つのｎｐから構成され、ＶＬＩＷ（５）は操作ｃ１、ｂ３と１つのｎｐから構成され、ＶＬＩＷ（６）は操作ｃ２と２つのｎｐから構成され、ＶＬＩＷ（７）は操作ｃ３と２つのｎｐから構成され、ＶＬＩＷ（８）は操作ｄ１と２つのｎｐから構成され、ＶＬＩＷ（９）は操作ｅ１と２つのｎｐから構成されている。
【００７１】
そして操作ａ１とａ２、ａ２とａ３の間、ｂ１とｂ２、ｂ２とｂ３の間、またｃ１とｃ２、ｃ２とｃ３の間に真の依存関係があり、操作ａ２とｂ１、ｂ２とｃ１の間に逆依存関係のある命令列を考える。さらに操作ｄ１とｅ１はループ終了のための条件判別のための命令列とし、操作ｄ１はｃ３に、操作ｅ１はｄ１に真の依存関係があるとする。そしてａ１〜ａ３、ｂ１〜ｂ３、ｃ１〜ｃ３、ｄ１の各々の命令のレーテンシは３τとし、ｅ１のレーテンシは１３τとする。ｅ１はブランチ命令なのでレーテンシが大きい。
【００７２】
これらの命令列はループ内部の命令列とし、メモリ１に格納され、プログラムの実行にともなって命令キャッシュ２に格納されるものとする。
【００７３】
この命令列はメモリ１から命令キャッシュ２に転送され、その後セレクタ３を通りデコーダ４に転送され、デコードされる。
【００７４】
それからレジスタリネーミング部５に送出されて、図８（Ｂ）に示す如く、操作ａ２−ｃ１及び操作ｂ２−ｃ１における逆依存関係が解消される。
【００７５】
それからループ判別部６に、図８（Ｂ）に示す如き、逆依存関係の解消された命令列が入力される。ループ判別部６では、前記ループ記号付与コンパイラ１１により付加されたループ記号により、ループ内の命令列であることが判別される。そしてセレクタ３にループ検出信号を送出する。
【００７６】
この判別後、図７の演算部８及びループ最適化・アンローリング部７−１にこれらの命令列が送られ、演算部８において１回目のループを実行する。この第１回目のループでは、後述するように最適化処理が行われていないので、図１０のＡに示す如く、１回のループの実行サイクルは３７τを必要とする。
【００７７】
ところで、ループ最適化・アンローリング部７−１に転送された、図８（Ｂ）に示す命令列は、図８（Ｃ）に示す如く、最適化される。すなわち操作ａ２−ｂ１における逆依存関係及び操作ｂ２−ｃ１における逆依存関係がそれぞれ解消されたので、操作ｂ１はａ２と同じ命令におくことができ、それに伴って操作ｂ１に対して真の依存関係がある操作ｂ２も操作ａ３と同じ命令に置けることになり、結局ｂ１〜ｂ３の操作が１命令ずつ、もとの命令列よりも前の命令に置くことができる。
【００７８】
同様にｃ１〜ｃ３の操作が２命令ずつ、もとの命令列よりも前の命令に置くことができる。この結果、図８（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（９）を、同（Ｃ）に示す如き命令列新ＶＬＩＷ（１）〜新ＶＬＩＷ（７）に最適化することができる。
【００７９】
そしてループ最適化・アンローリング部７−１は、この最適化後に図８（Ｃ）に示す命令列Ａ′から条件判別の命令列である新ＶＬＩＷ（６）、新ＶＬＩＷ（７）を除いた部分Ａ″を複数回、図９に示す如く、最適化ループメモリ９上にコピー展開するアンローリングを行う。いまこのループが１０１回まわるものとし、アンローリングは１０重で行うもの、つまり図９に示すＡ″の部分を１０回展開することで行うものと仮定すれば、２回目以降のループでは図９に示す如き命令列となる。
【００８０】
すなわち図８（Ｃ）の命令列Ａ′の条件判別の命令列を除いた部分Ａ″が１０重に展開され、最後に条件分岐の命令列のついた、図９に示す命令列がアンローリングされた新しいループとなる。この図９に示す、アンローリングされたループを１回実行すると、アンローリングする前のループを１０回実行したものと等価になる。
【００８１】
このように最適化され、アンローリングされた命令列が最適化ループメモリ９に格納される。
【００８２】
セレクタ３には、ループ判別部６から前記ループ検出信号が伝達されているので、２回目のループからは、最適化ループメモリ９から、前記図９に示す命令列を読み出し、演算部８はこれにもとづき実行する。
【００８３】
図９に示す命令列は、アンローリングを１０重に行っているので、前記１０１回ループをまわす場合、アンローリングしたループの回転数は１０回になる。１回あたりのアンローリングしたループの実行に要する実行サイクル数は、図１１にＢで示す部分の実行サイクル数である１６６τであり、これを１０回まわしたものと、最初の１回目のループのサイクル数３７τを加算した１６９７τが全体のループを実行した実行サイクル数となる。
【００８４】
これに対して、最適化およびアンローリング処理を行わなかったときの１回あたりのループの実行に要するサイクル数は３７τであり、これを１０１回まわすと３７３７τとなる。したがって、本発明の第３の実施の形態により実行サイクル数を約４５％に削除することができる。
【００８５】
本発明の第４の実施の形態を図１２にもとづき、他図を参照して説明する。
【００８６】
第４の実施の形態では、命令列がループであるか否かの判断を、命令列を解析することで動的に判断するループ判別部６′を使用する。またコンパイラ１１′も、ループに対して記号をつけない通常のものを使用する。また図１２で他図と同記号は同一部である。
【００８７】
ループの検出は、図５、図６の場合と同様に例えばブランチ命令を検出することにより行う。従ってこのブランチ命令を検出することにより、ループ判別部６′は動的にループの存在を判断することができる。
【００８８】
あとは、前記図７に示す第３の実施の形態と同様の動作を行うものであり、説明簡略のため、動作の詳細については省略する。
【００８９】
本発明の第５の実施の形態を図１３及び図１４にもとづき、他図を参照して説明する。図１３は本発明の第５の実施の形態を示し、図１４は本発明の動作状態説明図である。
【００９０】
本発明の第５の実施の形態では、命令列がループの中にある命令か否かということと、このループがプログラム中において複数回参照されるか否かを判別し、ループを最適化するとともに、最適化したループをメモリに書き戻し、２回目以降のループ参照の場合にはこの書き戻したループを参照するので、第１の実施の形態や第２の実施の形態のように、参照する毎に必要とした最適化処理を２回目以降の参照の場合は省略することができ、その分だけ第１の実施の形態や第２の実施の形態に比べ動作を向上させることができる。
【００９１】
図１３において、図２と同記号は同一部分を示し、６−１はループ判別・複数回参照判別部、１２はライトバック部である。第５の実施の形態である図１３では、ループ記号付与コンパイラ１１は、図１４に示す如く、ループの先頭と末尾にこれを示す記号Ｌ、ＬＬを付加するのみならず、このループがプログラム中において参照されるとき記号αを付加するものである。そしてループ判別・複数回参照判別部６−１はこのループの先頭と終わりに付加された記号によりループを判別するのみならず、このループがプログラム中において参照されたときに付加されたループ参照記号αの回数を読み取ることによりループが複数回参照されることを判断するものである。図１４におけるループ参照記号αはループ記号付与コンパイラ１１が付加したものであり、記号αの横の（１）、（２）、（３）はループ判別・複数回参照判別部６−１が判断したこのループが参照された回数である。例えばα（３）はループ記号付与コンパイラ１１が付加したループ参照記号αが３回検出されたことを示す。
【００９２】
図１３の動作を説明する。
【００９３】
ループ記号付与コンパイラ１１は、ファイル１０から取り出したソースプログラムをコンパイルして機械語に変換するが、前記図２、図７と同様に、ループの有無をチェックし、ループを検出したとき、図１４に示す如く、ループの先頭と末尾にループ記号（Ｌ）、（ＬＬ）を付与する。さらにこのループがプログラム中で複数回参照か否かを判断し、参照されているブランチ部分にこれを示すループ参照記号αを付加し、メモリ１に格納する。そしてコンパイルされた命令列はプログラムの実行にともない命令キャッシュ２に格納される。
【００９４】
セレクタ３は通常は命令キャッシュ２側から命令を出力するように構成されているので、命令キャッシュ２から取り出された命令がデコーダ４に送られてデコードされる。
【００９５】
いま命令キャッシュ２から取り出した命令列が、図３（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（７）の場合を考える。ＶＬＩＷ（１）は、操作ａ１と２つのｎｐ（ｎｏ  ｏｐｅｒａｔｉｏｎ）から構成され、ＶＬＩＷ（２）は操作ａ２と２つのｎｐから構成され、ＶＬＩＷ（３）は操作ｂ１、ａ３と１つのｎｐから構成され、ＶＬＩＷ（４）は操作ｂ２と２つのｎｐから構成され、ＶＬＩＷ（５）は操作ｃ１、ｂ３と１つのｎｐから構成され、ＶＬＩＷ（６）は操作ｃ２と２つのｎｐから構成され、ＶＬＩＷ（７）は操作ｃ３と２つのｎｐから構成されている。
【００９６】
そして操作ａ１とａ２、ａ２とａ３の間、操作ｂ１とｂ２、ｂ２とｂ３の間、また操作ｃ１とｃ２、ｃ２とｃ３の間に真の依存関係があり、操作ａ２とｂ１、ｂ２とｃ１の間に逆依存関係のある命令列を考える。
【００９７】
また、各々の命令のレーテンシは３τとする。
【００９８】
そしてこの命令列はループ内部の命令列とし、メモリ１に格納され、プログラムの実行にともなって命令キャッシュ２に格納されているものとする。なお、ループ終了の条件判別に関わる命令の実行時間は考えないものとする。
【００９９】
この命令列はメモリ１から命令キャッシュ２に転送され、その後セレクタ３を通り、デコーダ４に転送されて、デコードされる。
【０１００】
このデコーダ４でデコードされたあとで、レジスタリネーミング部５により、図３（Ｂ）に示す如く、操作ａ２−ｂ１及び操作ｂ２−ｃ１における逆依存関係が解消される。
【０１０１】
それから、ループ判別・複数回参照判別部６−１に、図３（Ｂ）に示す如き、逆依存関係の解消された命令列が入力される。ループ判別・複数回参照判別部６−１では、前記ループ記号付与コンパイラ１１により付加されたループ記号により、これらの命令列がループ内の命令列であることを判別し、セレクタ５に判別信号を送出する。
【０１０２】
この判別後、演算部８及びループ最適化部７にこれらの命令列を送り、演算部８において、１回目のループを実行する。このとき、後述する最適化処理が行われていないので、解決されないので、この図４（Ａ）の命令列の実行サイクルは、図４（Ｂ）に示す如く、２１τを必要とする。
【０１０３】
またループ最適化部７に転送された、図３（Ｂ）に示す命令列は、このループ最適化部７において、図３（Ｃ）に示す如く、最適化される。すなわち、操作ａ２−ｂ１における逆依存関係及び操作ｂ２−ｃ１における逆依存関係がそれぞれ解消されたので、操作ｂ１はａ２と同じ命令におくことができ、それに伴って操作ｂ１に対して真の依存関係がある操作ｂ２も操作ａ３と同じ命令に置けることになり、ｂ１〜ｂ３の操作が１命令ずつ、もとの命令列よりも前の命令に置くことができる。
【０１０４】
同様にｃ１〜ｃ３の操作が２命令ずつ、もとの命令列よりも前の命令に置くことができる。この結果、図３（Ａ）に示す如き命令列ＶＬＩＷ（１）〜ＶＬＩＷ（７）を、同（Ｃ）に示す如き命令列新ＶＬＩＷ（１）〜新ＶＬＩＷ（５）に最適化することができる。そしてこの図３（Ｃ）に示す如く、最適化された命令列を最適化ループメモリ９に転送し、保持する。
【０１０５】
セレクタ３には、ループ判別・複数回参照判別部６−１から前記判別信号が印加されているので、２回目のループからは、図３（Ｃ）に示す最適化された命令列を出力し、これにもとづき演算部８が実行する。この最適化されたループは、図４（Ｃ）、（Ｄ）に示す如く、各命令のレーテンシが、同様に３τとすれば１５τで実行サイクルが終了し、前記（Ａ）、（Ｂ）に示す場合の２１τに比較すれば１回のループで実行されるサイクル数を約７０％に削減することができる。
【０１０６】
ところで、ループ判別・複数回参照判別部６−１は、前記ループ参照記号αを複数個検出して、ループがプログラム中に複数回参照されると判断すると、ループ判別・複数回参照判別部６−１はライトバック部１２に制御記号を送出する。これにより、ライトバック部１２は、最適化ループメモリ９に格納されている。前記図３（Ｃ）で示した最適化された命令列を読み出して、メモリ１内の前記ループをこの最適化された命令列に書き換える。
【０１０７】
ループ判別・複数回参照判別部６−１は、セレクタ３にも制御信号を送り、セレクタ３からメモリ１側のつまり前記メモリ１から出力される最適化された命令列をデコーダ４側に送出するように制御する。
【０１０８】
これにより今度は、２回目以降にこのループを呼び出した場合、図３（Ｃ）に示す最適化された命令列で、ループの１回目から実行されることになる。ここでライトバック部１２を用いてメモリ１内のループを書き換えた場合、２回目以降にそのループを実行することになっても、ループ最適化部７は使用されないものとする。
【０１０９】
このように、２回目以降にこのループを実行する場合、ループの１回目から最適化された命令列で実行されるので、前記の如くループが１０１回実行されるとき、実行サイクルには１５τ×１０１となり、最初に必要であった図４（Ｂ）に示す実行サイクル数２１τを１５τに節約したものとすることができる。また図１４に示す如く、３回目のループ参照が行われたときは、第１の実施の形態や第２の実施の形態よりも、さらに実行サイクルを節約することができる。
【０１１０】
本発明の第６の実施の形態を図１５にもとづき、他図を参照して説明する。第６の実施の形態も、第５の実施の形態と同様に、ループが複数回参照される場合、２回目以降はプログラムのループ部分を最適化された命令列で書き換えられたものを使用するものであるが、第６の実施の形態ではループがプログラム中で複数回参照されるか否かをループ判別・複数回参照判別部６−２で動的に判断するものである。
【０１１１】
またコンパイラ１１′も、ループに対して特別な記号をつけない、またループを参照する命令に対してもこれまた特別な記号をつけない通常のものを使用する。なお図１５で他図と同記号は同一部である。
【０１１２】
ループの検出や参照先の検出は、例えばブランチ命令を検出することにより行うことができる。他の動作は前記図１３、図１４と同様に動作を行うものであり、説明簡略のため、動作の詳細については省略する。
【０１１３】
【発明の効果】
本発明によれば下記の効果を奏することができる。
【０１１４】
（１）ループを検出し、このループについて逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行うので、真の依存関係がある操作が存在する場合でも、ループを高速に実行することができる。
【０１１５】
（２）ループの存在を、その命令を動的に判別することにより検出し、このループについての操作において逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行うので、コンパイラにループマークの付加等の余分の負担をかけることなく、真の依存関係がある操作が存在する場合でも、ループを高速に実行することができる。
【０１１６】
（３）ループについての操作において、逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、この最適化後にこの最適化したものをコピーするアンローリングを行い、これを実行するように構成したので、ループ全体の実行サイクルを大きく削減することができる。
【０１１７】
（４）ループの存在を、その命令を動的に判別することにより検出し、これにおける逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、この最適化後にこの最適化したものをコピーするアンローリングを行い、これを実行するように構成したので、コンパイラにループマークの付加等の余分の負担をかけることなく、真の依存関係がある操作が存在する場合でもループを高速に実行することができる。
【０１１８】
（５）ループについての操作において、逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移行する最適化処理を行い、またこのループがプログラム中で複数回参照される場合、前記と同様に最適化されたループを高速処理できるのみならず、２回目以降このループを呼び出す場合、メモリ内のループを示す命令列を最適化されたループの命令列に書き換えることにより、今度はループの１回目から最適化された命令列を実行することができ、２回目以降に呼び出されたループも高速実行することができる。しかもメモリ内のループを書き換えた場合、２回目以降にそのループを実行することになってもループ最適化手段を使用する必要がない。
【０１１９】
（６）ループの存在をその命令を動的に判別することにより検出し、また同時にこのループがプログラム中で複数回参照されることを動的に検出し、ループについての操作において逆依存関係や出力依存関係を解消し、その操作タイミングを元の命令列よりも前に移動する最適化処理を行い、またこのループがプログラム中で複数回参照される場合、前記と同様に最適化されたループを高速処理できるのみならず、２回目以降このループを呼び出す場合、メモリ内のループを示す命令列を最適化されたループの命令列に書き換えることにより、今度はループの１回目から最適化された命令列を実行することができ、２回目以降に呼び出されたループも高速実行することができる。しかもメモリ内のループを書き換えた場合、２回目以降にそのループを実行することになってもループ最適化手段を使用する必要がない。
【図面の簡単な説明】
【図１】本発明の原理図である。
【図２】本発明の第１の実施の形態である。
【図３】本発明におけるレジスタリネーミング及び最適化状態動作説明図である。
【図４】本発明におけるループ実行サイクル説明図である。
【図５】本発明の第２の実施の形態である。
【図６】ループ状態説明図である。
【図７】本発明の第３の実施の形態である。
【図８】本発明の第３の実施の形態におけるレジスタリネーミング及び最適化状態動作説明図である。
【図９】本発明の第３の実施の形態におけるアンローリング状態説明図である。
【図１０】本発明の最適化を行う前の実行サイクル説明図である。
【図１１】本発明の最適化とループアンローリングを行った後のループの実行サイクル説明図である。
【図１２】本発明の第４の実施の形態である。
【図１３】本発明の第５の実施の形態である。
【図１４】本発明の第５の実施の形態の動作説明図である。
【図１５】本発明の第６の実施の形態である。
【図１６】ＶＬＩＷ命令説明図である。
【図１７】ＶＬＩＷ形式のプロセッサの問題点説明図である。
【符号の説明】
１  メモリ
２  命令キャッシュ
３  セレクタ
４  デコーダ
５  レジスタリネーミング部
６  ループ判定部
７  ループ最適化部
８  演算部
９  最適化ループメモリ
【図１】
0003583656.tif 000002
【図２】
0003583656.tif 000003
【図３】
0003583656.tif 000004
【図４】
0003583656.tif 000005
【図５】
0003583656.tif 000006
【図６】
0003583656.tif 000007
【図７】
0003583656.tif 000008
【図８】
0003583656.tif 000009
【図９】
0003583656.tif 000010
【図１０】
0003583656.tif 000011
【図１１】
0003583656.tif 000012
【図１２】
0003583656.tif 000013
【図１３】
0003583656.tif 000014
【図１４】
0003583656.tif 000015
【図１５】
0003583656.tif 000016
【図１６】
0003583656.tif 000017
【図１７】
0003583656.tif 000018