(57)【要約】  プロセッサ１００は、インタプリタプログラム２００ａを読み出してインタプリタを起動し、インタプリタは、ソースプログラム２００ｂを実行する場合に必要となる間接分岐命令の代わりに、間接分岐命令の分岐先のアドレスを逆順にリンクレジスタ１２０ｃ（プロセッサ１００の内部的には、リターン・アドレス・スタック１３０にも分岐先のアドレスが積まれる）に格納し、リターン・アドレス・スタック１３０からアドレスを順次読み出して分岐予測を行う。
2009004709.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムを実行する場合に必要となる間接分岐命令の代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐コードを生成するコード生成手順と、
前記コード生成手順によって生成された擬似間接分岐コードを記憶装置に記憶させる記憶手順と、
前記記憶装置に記憶された擬似間接分岐コードの命令を逐次読み出して実行する実行手順と、
を実行させるための間接分岐処理プログラム。
【請求項２】
前記コード生成手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる命令で代用した擬似間接分岐コードを生成することを特徴とする請求項１に記載の間接分岐処理プログラム。
【請求項３】
前記擬似間接分岐コードを前記コンピュータに実行させて、間接的に、前記コンピュータに搭載された所定の記憶領域に間接分岐命令の分岐先のアドレスを逆順に格納させることを特徴とする請求項２に記載の間接分岐処理プログラム。
【請求項４】
前記ソースプログラムは分岐を伴う制御文が記述されており、前記擬似間接分岐コードは、前記制御文が記述されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にレジスタに格納する命令を含んでいることを特徴とする請求項３に記載の間接分岐処理プログラム。
【請求項５】
コンピュータに、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムを実行する場合に必要となる間接分岐命令の代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐コードを生成するコード生成手順と、
前記コード生成手順によって生成された擬似間接分岐コードを記憶装置に記憶させる記憶手順と、
前記記憶装置に記憶された擬似間接分岐コードの命令を逐次読み出して実行する実行手順と、
を実行させるためのコンピュータ読取可能なプログラムを記憶する記憶媒体。
【請求項６】
前記コード生成手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる命令で代用した擬似間接分岐コードを生成することを特徴とする請求項５に記載の記憶媒体。
【請求項７】
前記擬似間接分岐コードを前記コンピュータに実行させて、間接的に、前記コンピュータに搭載された所定の記憶領域に間接分岐命令の分岐先のアドレスを逆順に格納させることを特徴とする請求項６に記載の記憶媒体。
【請求項８】
前記ソースプログラムは分岐を伴う制御文が記述されており、前記擬似間接分岐コードは、前記制御文が記述されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にレジスタに格納する命令を含んでいることを特徴とする請求項７に記載の記憶媒体。
【請求項９】
記憶装置に記憶されたソースプログラムを読み出して処理を実行するコンピュータの間接分岐処理方法であって、
前記コンピュータは、
記憶装置に記憶されたソースプログラムを読み込む読込工程と、
前記ソースプログラムを実行する場合に必要となる間接分岐命令の代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐コードを生成するコード生成工程と、
前記コード生成工程によって生成された擬似間接分岐コードを記憶装置に記憶させる記憶工程と、
前記記憶装置に記憶された擬似間接分岐コードの命令を逐次読み出して実行する実行工程と、
を含んだことを特徴とする間接分岐処理方法。
【請求項１０】
ソースプログラムを解釈し、ソースプログラムの内容に応じた処理コードを選択して当該処理コードを呼び出すインタプリタをコンピュータに実行させるための間接分岐処理プログラムであって、
前記インタプリタは、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムに応じた処理コードを選択し、当該処理コードが間接分岐命令に対応する処理コードである場合に、前記間接分岐命令に対応する処理コードの代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐命令に対応する処理コードを呼び出す呼出手順と、
を含んだことを特徴とする。
【請求項１１】
前記呼出手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令の処理コードを、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる擬似間接分岐命令の処理コードで代用することを特徴とする請求項１０に記載の間接分岐処理プログラム。
【請求項１２】
前記擬似間接分岐命令の処理コードを前記コンピュータに実行させて、間接的に、前記コンピュータに搭載された所定の記憶領域に間接分岐命令の分岐先のアドレスを逆順に格納させることを特徴とする請求項１１に記載の間接分岐処理プログラム。
【請求項１３】
前記ソースプログラムは分岐を伴う制御文が記述されており、前記擬似間接分岐命令の処理コードは、前記制御文が記述されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んでいることを特徴とする請求項１２に記載の間接分岐処理プログラム。
【請求項１４】
ソースプログラムを解釈し、ソースプログラムの内容に応じた処理コードを選択して当該処理コードを呼び出すインタプリタをコンピュータに実行させるための間接分岐処理プログラムを記憶する記憶媒体であって、
前記インタプリタは、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムに応じた処理コードを選択し、当該処理コードが間接分岐命令に対応する処理コードである場合に、前記間接分岐命令に対応する処理コードの代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐命令に対応する処理コードを呼び出す呼出手順と、
を含んだことを特徴とする。
【請求項１５】
前記呼出手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令の処理コードを、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる擬似間接分岐命令の処理コードで代用することを特徴とする請求項１４に記載の記憶媒体。
【請求項１６】
前記擬似間接分岐命令の処理コードを前記コンピュータに実行させて、間接的に、前記コンピュータに搭載された所定の記憶領域に間接分岐命令の分岐先のアドレスを逆順に格納させることを特徴とする請求項１５に記載の記憶媒体。
【請求項１７】
前記ソースプログラムは分岐を伴う制御文が記述されており、前記擬似間接分岐命令の処理コードは、前記制御文が記述されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にレジスタに格納する命令を含んでいることを特徴とする請求項１６に記載の記憶媒体。
【請求項１８】
ソースプログラムを解釈し、ソースプログラムの内容に応じた処理コードを選択して当該処理コードを呼び出すインタプリタをコンピュータに実行させる間接分岐処理方法であって、
前記インタプリタは、
記憶装置に記憶されたソースプログラムを読み込む読込工程と、
前記ソースプログラムに応じた処理コードを選択し、当該処理コードが間接分岐命令に対応する処理コードである場合に、前記間接分岐命令に対応する処理コードの代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐命令に対応する処理コードを呼び出す呼出工程と、
を含んでいることを特徴とする間接分岐処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、間接分岐命令の代わりに擬似的な間接分岐命令をコンピュータに実行させる間接分岐処理プログラムおよび間接分岐処理方法に関するものである。
【背景技術】
【０００２】
従来より、計算機（ＣＰＵ（Central  Processing  Unit）等）は、コンパイル方式あるいはインタプリタ方式によって人間により記述されたソースプログラムを実行している。コンパイル方式は、ソースプログラムをコンパイラと呼ばれる変換プログラムにより計算機上で実行できるバイナリ形式に変換した後に、バイナリ形式に変換したコードを実行する方式であり、インタプリタ方式は、インタプリタと呼ばれる特別なバイナリコードを計算機上で実行し、インタプリタがソースプログラムを逐次解釈しながら内容に応じた処理を随時行う方式である。【０００３】
ところで、近年では、計算機の処理を高速化するために、計算機をスーパースカラと呼ばれる方式に基づいて設計している。この方式では、パイプライン方式で処理を行うことを前提としている。パイプライン方式では、各命令処理が複数のステージに分割され、それぞれのステージが個別のユニットにより処理される。そのため、次に実行すべき命令が確定していれば、先行命令の第二ステージの実行と並行して、後続命令の第一ステージを実行することができ、分割したステージの数だけ並列動作による高速な実行が可能となる。【０００４】
ここで、パイプライン処理が巧く機能する条件として、次に実行すべき命令が確定しているという条件が存在する。つまり、命令１の次に実行すべき命令２（命令が命令１、命令２、命令３・・・の順で実行される場合）が、命令１の第１ステージの実行が完了するまでに確定していない時、次の命令２の処理を並列して実行することができない（命令２に続く命令も同様である）。【０００５】
このような状態が発生する代表的な例が、分岐命令である。分岐命令においては、直前の分岐条件判定命令（例えば、比較命令）の結果が判明するまで、次に処理するべき命令が確定せず、パイプライン処理を行うことができないため、計算機全体の処理速度が大幅に低下してしまう。【０００６】
パイプライン処理の性能低下を防止するために、分岐予測と呼ばれる技術が考案され実用化されている。かかる分岐予測の原理としては、過去に実行したプログラムの分岐結果を履歴に残しておき、その延長線上で分岐結果を予測するというアイデアが基本となっている（例えば、非特許文献１参照）。【０００７】
また、分岐命令には、通常の分岐命令だけではなく、レジスタに記憶されたアドレスを基にして分岐する間接分岐命令も存在する。間接分岐命令は、上述したインタプリタを実装する際などに頻繁に利用されている。しかし、間接分岐命令は、スーパースカラ方式の計算機においてコストの高い命令となっているため、間接分岐命令に焦点を当てた予測手法の研究も行われている（例えば、非特許文献２、非特許文献３参照）。【０００８】
なお、特許文献１では、狭いアドレス空間のみを取り扱うプロセッサ用に書かれたコードを、間接コールを用いずに広いアドレス空間を取り扱うプロセッサに適用する技術が示されている。【０００９】
【非特許文献１】John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture-A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.
【非特許文献２】P.-Y.  Chang,  E.  Hao,  and  Y.  N.  Patt.  “Target  Prediction  for  Indirect  Jumps”,  In  Proceedings  of  24th  International  Symposium  on  Computer  Architecture,  pp.  274~283,  1997.
【非特許文献３】K.  Driesen  and  U.  HAolzle.  “Accurate  Indirect  Branch  Prediction”,  In  Proceedings  of  25th  International  Symposium  on  Computer  Architecture,  pp.  167~178,  1998.
【特許文献１】特開２０００−２８４９６５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来の技術では、プログラム中に記載されたある間接分岐命令の次にどの命令が実行されるかを履歴から予測しても、予測した命令と実際に次に実行される命令が一致する確率が低いという問題があった。【００１１】
実行のたびに異なる分岐先を持つような間接分岐命令に対しては、非特許文献２および非特許文献３の技術を利用したとしても、精度のよい予測を行うことができず、間接分岐命令は、スーパースカラ方式によってプログラムを実行する計算機にとって依然、コストの高い命令となっている。【００１２】
本発明は、上記に鑑みてなされたものであって、分岐予測を精度よく行うことができる間接分岐処理プログラムおよび間接分岐処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決し、目的を達成するために、コンピュータ上のインタプリタに、記憶装置に記憶されたソースプログラムを読み込む読込手順と、前記ソースプログラムを解釈し、内容にあったインタプリタ内の処理コードを選択する手順と、前記コード選択手順によって選択された処理コードを呼び出す手順を実行させるが、当該インタプリタは、前記処理コード選択、呼び出し手順において、選択したコードに分岐するために、間接分岐命令を利用する代わりに、選択したコードのアドレスを処理の順序とは逆順にコールスタックに格納し、疑似的な間接分岐命令によって呼び出し処理を行う。【００１４】
また、本発明は、上記発明において、前記処理コード呼び出し手順の、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記コールスタックに分岐先のアドレスを格納し、そのアドレスに処理を移行させる命令で代用した擬似間接分岐コードで代用することを特徴とする。【００１５】
また、本発明は、上記発明において、前記コンピュータに搭載された所定のスタック、またはリンクレジスタに間接分岐命令の分岐先のアドレスを格納することで、間接的に計算機内部の復帰アドレス予測テーブルを更新し、疑似的な間接分岐を処理する際に分岐予測を成功させることを特徴とする。【００１６】
また、本発明は、上記発明において、前記ソースプログラムには、処理の分岐を伴う制御文が記述されており、前記インタプリタ内の擬似間接分岐コードは、前記制御文の条件判定部が記述されるまでの区間ごとに前記処理コードのアドレスを逆順にコールスタックに格納する命令を含んでいることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、コンピュータに、記憶装置に記憶されたソースプログラムを読み込む読込手順と、ソースプログラムを解釈し、内容にあったインタプリタ内の処理コードを選択する手順と、コード選択手順によって選択された処理コードを呼び出す手順と、を実行させ、この処理により、間接的に計算機内部の復帰アドレス予測テーブルを更新し、処理コード呼び出し手順の際には、この予測テーブルを用いて分岐予測が行われるので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。【００１８】
また、本発明によれば、コンピュータに実行させるコードの呼び出し手順において、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記コールスタックに岐先のアドレスを格納し、そのアドレスに処理を移行させる命令で代用した擬似間接分岐コードで代用するので、ソースプログラムを実行するコンピュータの処理性能を向上させることができる。【００１９】
また、本発明によれば、コンピュータに搭載された所定のスタック、またはリンクレジスタに間接分岐命令の分岐先のアドレスを逆順に格納することで、間接的に計算機内部の復帰アドレス予測テーブルを更新し、疑似的な間接分岐を処理する際に分岐予測を成功させるので、コンピュータの分岐予測の精度を向上させ、ソースプログラムを実行するコンピュータの処理性能を向上させることができる。【００２０】
また、本発明によれば、ソースプログラムには、処理の分岐を行う制御文が記述されており、インタプリタ内の擬似間接分岐コードは、制御文の条件判定部が記載されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にコールスタックに格納する命令を含んでいるため、より効率よく高速に擬似間接分岐を実行することができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、分岐処理を説明するための図である。
【図２】図２は、複数の分岐処理と間接分岐処理とを説明するための図である。
【図３】図３は、コンパイル方式とインタプリタ方式との違いを説明するための図である。
【図４】図４は、従来のインタプリタの処理を示すフローチャートである。
【図５】図５は、パイプライン処理を説明するための図である。
【図６】図６は、関数呼び出しの様子を説明するための図である。
【図７】図７は、間接分岐命令を用いるインタプリタの一例を示す図である。
【図８】図８は、擬似的な間接命令を用いるインタプリタの一例を示す図である。
【図９】図９は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。
【図１０】図１０は、複数の間接分岐命令を実行するインタプリタの一例を示す図である。
【図１１】図１１は、図１０に示した「call  %r6」と等価のプログラムを示す図である。
【図１２】図１２は、複数の擬似的な間接分岐命令を実行するインタプリタの一例を示す図である。
【図１３】図１３は、インタプリタの処理手順を示すフローチャート（１）である
【図１４】図１４は、インタプリタの処理手順を示すフローチャート（２）である。
【図１５】図１５は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。
【符号の説明】
【００２２】
１００，３００    プロセッサ
１１０，３１０    メモリアクセス制御部
１２０，３２０    レジスタ
１２０ａ，３２０ａ  汎用レジスタ群
１２０ｂ，３２０ｂ  プログラムカウンタ
１２０ｃ，３２０ｃ  リンクレジスタ
１３０，３３０    リターン・アドレス・スタック
１４０，３４０    分岐予測部
１５０，３５０    デコード・制御部
１６０，３６０    演算パイプライン部
２００，４００    メインメモリ
２００ａ  インタプリタプログラム
２００ｂ，４００ｂ  ソースプログラム
４００ｃ  擬似間接分岐プログラム
２００ｃ，４００ｄ  退避データ
４００ａ  コンパイラプログラム
【発明を実施するための最良の形態】
【００２３】
以下に、本発明にかかる間接分岐処理プログラムおよび間接分岐処理方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。【００２４】
まず、本願発明にかかる実施例の説明を行う前に、本願発明に関わる従来の技術（間接分岐命令、インタプリタ方式およびコンパイル方式、スーパースカラプロセッサとパイプライン処理、分岐予測、関数からの復帰処理、リターン・アドレス・スタック、ハードウェアによるインタプリタ支援、Just  In  Timeコンパイル方式）について順に説明する。【００２５】
（間接分岐命令）
ＣＰＵ（Central  Processing  Unit）等の計算機上で動作するプログラムについて、途中結果に応じて異なる処理を行うために分岐と呼ばれる命令が用いられる。計算機システムにおいて、プログラムはメモリ上に順に配置され、配置された順に従い、計算機により逐次実行される。図１は、分岐処理を説明するための図である。実行が分岐命令に差し掛かると、直前の条件判定結果において特定の条件を満たした場合に、次に処理すべき命令アドレスを指定されたメモリアドレスに変更する（図１では、条件に応じて、処理３あるいは処理５に移行することとなる）。この条件判定命令あるいは分岐命令においては、メモリアドレスや条件は、命令の一部として符号化された固定値である。【００２６】
一方、条件に応じて複数の分岐先へ処理を移したい場合が存在する。図２は、複数の分岐処理と間接分岐処理とを説明するための図である。図２の左側に示すように、条件判定と分岐を必要な種類だけ並べて実現する事もできるが、多くの条件判定を伴う分岐は効率が悪い。そこで用いられるのが間接分岐命令と呼ばれる処理である。この処理では、次に実行すべきアドレスとしてレジスタの値が用いられる。即ち、過去の計算結果そのものを次の命令アドレスとして指定できる。これにより、プログラム自身で分岐先命令アドレスを計算し、その値により間接分岐を行う事が可能となり、任意の処理への分岐が実現できる（図２の右側参照）。【００２７】
（インタプリタ方式およびコンパイル方式）
計算機上で動作するプログラムの実行方式には、大きく分けて２つの方式が存在する。１つがコンパイル方式であり、もう１つがこのインタプリタ方式である。コンパイル方式においては、ソースファイルに記述されたプログラムを、事前にコンパイラにより実行バイナリに変換する必要がある。このコンパイラにより変換された実行バイナリは、計算機上で直接実行される。【００２８】
一方、インタプリタ方式において計算機上で直接実行されるのは、インタプリタと呼ばれるソフトウェアである。インタプリタは、ソースファイルを逐次解釈しながら、プログラム記述に沿った処理を行う。このため、コンパイル方式に比べ、プログラムの処理には時間がかかる。しかしその一方で、異なる設計の計算機システムにおいても、共通仕様のインタプリタが存在すれば、同一のプログラムをそのまま利用する事が可能というメリットも存在する。【００２９】
図３は、コンパイル方式とインタプリタ方式との違いを説明するための図である。図３の左側に示すように、インタプリタ方式では、ハードウェア上で直接動作するのは基本ソフトとインタプリタであり、インタプリタは、基本ソフトの機能を利用しながら動作する。プログラムはこのインタプリタ上で解釈・実行される。一方、図３の右側に示すように、コンパイル方式ではプログラムはコンパイルされ、実行ファイルに変換される。実行ファイルは基本ソフトの機能を利用しながら、直接ハードウェアで実行される。【００３０】
インタプリタは、それ自身１つのソフトウェアとして記述されている。インタプリタの基本動作は、プログラムを逐次解釈し、その内容に応じた処理を行う事の繰り返しである。図４は、従来のインタプリタの処理を示すフローチャートである。ここで注目したいのが、中央にある分岐処理「命令に応じた処理へ分岐」である。この分岐は、図４からもわかる通り複数の処理へ分岐する必要があり（例えば、処理Ａ、処理Ｂ、・・・処理Ｙ、処理Ｚのいずれかに分岐する必要があり）、この分岐としては間接分岐を用いる必要がある。よって、インタプリタの動作速度は、この間接分岐の処理効率に大きく左右される事になる。【００３１】
（スーパースカラプロセッサとパイプライン処理）
現在の高性能計算機は、内部はスーパースカラと呼ばれる方式に基づいて設計されている。この方式ではパイプライン方式で処理を行う事を前提としており、パイプライン方式では各命令の処理は複数のステージに分割され、それぞれのステージが個別のユニットにより処理される。【００３２】
図５は、パイプライン処理を説明するための図である。図５における横軸が時間の流れを示し、縦軸が命令の流れを示す。図５に示す例では、命令処理をＩＦ、ＩＤ、ＥＸ、ＭＥＭ、ＷＢと５つのステージに分割している。最新のプロセッサでは、このステージ数が増加する傾向にあり、十数段のステージに分割されている事も稀ではない。【００３３】
さて、ＩＦを処理するユニット（ＩＦユニット）について考える。このＩＦユニットでは、特定の命令のＩＦに該当する処理を行い、結果を次のＩＤユニットに引き渡す。よって、次のサイクルにおいてＩＤの処理が行われている際には、ＩＦユニットが命令に対して行うべき処理はない。同様にして次のサイクルではＥＸユニットが処理を行い、ＩＦユニット、ＩＤユニットの行うべき処理はない。【００３４】
これを利用して、次のサイクルではＩＦユニットは次の命令のＩＦ処理を行うようにする。このようにして後続する命令の処理を平行して分割実行する事で、１つの命令の処理の完了まで５サイクルかかっていたとしても、長い時間で見ると、平均して１サイクル毎に１つの命令の処理が完了する事になる。このようにＮサイクルかかる処理を分割・並列実行する事で見かけ上の処理時間を１サイクルにするような技術をパイプライン技術と呼ぶ。【００３５】
ただし、このパイプライン処理が巧く機能する条件として、次に実行すべき命令が確定している、という条件が存在する。つまり、命令１の次に実行すべき命令が、命令１の実行が完了するまで確定していない時、次の命令の処理を並列して開始する事ができない。このような状態が発生する代表的な例が、分岐命令である。【００３６】
分岐命令においては、直前の条件判定命令の結果が判明するまで、次に処理するべき命令が確定しない。このため、パイプライン処理を行う事ができずに、全体として性能が大きく低下してしまう。これを回避するための技術が分岐予測と呼ばれる技術である。分岐予測に関する詳しい説明は後述するが、簡単に説明すると、これは条件判定結果をあらかじめ予測し、分岐命令の時点で比較結果が確定していない時にも、この予測に基づき次に実行すべき命令を推測し、その推測に従って処理を進める方式である。【００３７】
この方式を用いれば、予測の精度が十分に高い場合に、分岐による性能低下はなくなる。また、予測がはずれた場合には、それ以降の命令処理を破棄し、仮定に基づき実行した命令が処理される前の状態に巻き戻した上で、正しい命令列を改めて実行しなおす事で、実行結果に影響は与えない。スーパースカラプロセッサに関する詳細は文献［２]（Mike  Johnson.  “Superscalar  Microprocessor  Design,”  Prentice-Hallm  Inc,  ISBN  0138756341.）に記載されており、計算機全般に関する技術の詳細は文献[１]（John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture-A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.）に記載されている。【００３８】
（分岐予測）
上記の「スーパースカラプロセッサとパイプライン処理」の節で述べた通り、精度の良い分岐予測を行うことは、スーパースカラ方式の計算機にとって重要な課題である。しかし、予測は条件判定結果に先立って、即座に行う事ができないと意味がなく、またハードウェアとして実装するため、大規模なデータベースを用いた予測なども行えない。よって、限られた資源でなるべく精度の高い予測が行えるよう工夫がなされている。【００３９】
分岐予測の原理としては、過去の分岐結果を記憶しておき、その延長線上で分岐結果を予想するというアイデアが基本となっている。過去数回の分岐結果を命令毎に記憶しておき、過去の分岐傾向に従い予測するだけの単純な予測で、９０％以上の精度で予測が当たるとされている。【００４０】
ただし、実際には全ての分岐命令に対し個別の履歴を用意する事は難しく、分岐命令の命令アドレスの下位ビットをインデックスとして履歴を参照する方法が用いられる。この場合、運が悪い時には複数の分岐命令で同じ履歴を共有してしまい、正しく予測が行えない。【００４１】
また、精度向上の工夫として、分岐間の相関を利用する方法がある。これは、特定の分岐結果は、その分岐命令に至るまでに通過した分岐命令の結果と相関関係がある事を利用している。これらは広域分岐予測と呼ばれ、９５％前後の制度で予測する事が可能となる。さらには複数の予測機構を組み合わせて使うなど、様々な工夫により分岐予測精度の向上が図られている。予測機構については、文献[１]の３．４節以降に詳しく説明されている。また、ウィキペディア日本語版「分岐予測」の項[３]にも分岐予測の説明がなされている（“分岐予測”、ウィキペディア日本語版,http://ja.wikipedia.org/を参照）。【００４２】
一方、これらの分岐予測手法は通常の分岐命令だけに焦点をあてた方法である。つまり複数の分岐先を持つような間接分岐命令に対しては、有効な予測手段を提供していない。間接分岐に焦点を当てた予測手法の研究は文献[４]（P.-Y.  Chang,  E.  Hao,  and  Y.  N.  Patt.  “Target  Prediction  for  Indirect  Jumps”,  In  Proceedings  of  24th  International  Symposium  on  Computer  Architecture,  pp.  274~283,  1997.）および文献[５]（K.  Driesen  and  U.  HAolzle.  “Accurate  Indirect  Branch  Prediction”,  In  Proceedings  of  25th  International  Symposium  on  Computer  Architecture,  pp.  167~178,  1998.）などが存在する。【００４３】
また、商用プロセッサにおいてはIntel(R)  Pentium(R)  Mが間接分岐予測器を搭載したプロセッサとして存在する。この予測の仕組みについては例えば、文献[６]（S.  Gochman,  R.  Ronen,  I.  Anati,  A.  Berkovits,  T.  Kurts,  A.  Naveh,  A.  Saeed,  Z.  Sperber,  and  R.  C.  Valentine.  “The  Intel  Pentium  M  Processor:  Microarchitecture  and  Performance”,  Intel  Technology  Journal,  7(2):21~36,  2003.）に記述されている。【００４４】
また、分岐予測以外にもコンパイラと協調して分岐先アドレスをフォワーディングし、予測しなくてもペナルティが発生しない手法も研究されている（文献[７]（豊島隆志、入江英嗣、五島正裕、and坂井修一.“レジスタ間接分岐ターゲット・フォワーディング”,  SACSIS  2006））。しかしながら、間接分岐を考慮した予測機構を備えた商用プロセッサは少なく、また搭載されていたとしても、通常の分岐命令に比べ精度の良い予測を行うことはできていない。従って、間接分岐命令は、スーパースカラ方式のプロセッサにとって、コストの高い命令となっている。【００４５】
（関数からの復帰処理）
特殊な形式の分岐を必要とする処理に「関数呼び出し」機能が挙げられる。図６は、関数呼び出しの様子を説明するための図である。同図に示す例では、メインの処理から関数Ａが、関数Ａから関数Ｂが呼び出される様子を示している。図６からもわかるように関数Ａはメイン処理の複数の箇所から呼び出される。【００４６】
一般に関数は、プログラム中のいずれの場所からも呼び出し可能であり、関数の実行が終了した際に移る次の処理というのは、呼び出し元箇所の次の命令となる。つまり、関数から戻る際には、複数の分岐先を持った分岐処理を行う必要がある。このために特殊な命令が用意されている事が多く、一般的には復帰命令（リターン命令）と呼ばれる命令が定義されている。【００４７】
リターン命令は、それに対応するリンク処理が必要とされる。多くの計算機においては、関数を呼び出す際に、「Jump  and  Link」と呼ばれるリンク付き分岐命令を用いる。これは分岐と同時に現在実行中の命令アドレスを特定の場所に退避する命令である。復帰命令が呼ばれた際には、この時に退避された命令アドレスを用いて、呼び出し元のアドレスを特定し、呼び出し元に再分岐する。関数は入れ子状で呼び出されるため、この退避場所はスタック構造を持つ資源に格納される事が多い。あるいは特定の場所に一時退避し、次のリンク処理により上書きされる前に、一時退避済みのアドレスをソフトウェア的に再退避する事で入れ子状の呼び出しにも対応している。【００４８】
（リターン・アドレス・スタック）
上記のリンク処理と復帰処理は特定の命令により実施される事が多く、プロセッサ内部で関数の呼び出し、復帰箇所を特定する事ができる。プロセッサ内部では、この復帰処理にかかる分岐のコストを最小限にするため、復帰処理に特化した分岐予測機構を備えている事が多い。現在利用されている商用プロセッサにおいては、例外なくこの予測機構は搭載されている。【００４９】
この機構はリターン・アドレス・スタックと呼ばれ、リンク時に呼び出し元を内部のリターン・アドレス・スタックに積み、復帰時にはこのスタックから降ろしたアドレスを用いて分岐予測を行う。このリターン・アドレス・スタックとは、プログラムから見える外部仕様的な戻りアドレス退避場所とは異なり、プロセッサ内部で予測のためだけに用いられる特殊な記憶領域である。リターン・アドレス・スタックについては、文献［８]（C.F.Webb.  Subroutine.“call/return  stack”,IBM  Technical  Disclosure  Bulletin,  30(11):18~20,1988.）の技術解説、あるいは文献[９]（D.R.Kaeli  and  P.G.Emma.“Branch  History  Table  Prediction  of  Moving  Target  Branches  Due  to  Subroutine  Returns”,In  Proceedings  of  18th  International  Symposium  of  Computer  Architecture,pages  34~42,1991.）、文献[１０]（K.Skadron,P.S.Ahuja,M.Martonosi,  and  D.  W.Clark.“Improving  Prediction  for  Procedure  Return  with  Return-Address-Stack  Repair  Mechanisms”,In  Proceedings  of  31st  International  Symposium  on  Microarchitecture,pages  259~271,1998.）などの研究結果がある。【００５０】
（ハードウェアによるインタプリタ支援）
インタプリタを高速に実行するための仕組みとして、計算機上にハードウェア的な支援機構を設ける場合もある。このような例の1つがMIPS社によるSmartMIPS(R)（文献[１１]（MIPS  Technologies  Inc.“MIPS32(R)  Architecture  for  Programmers  Volume  IV-d:  The  SmartMIPS(R)  Application-Specific  Extension  to  the  MIPS32(R)  Architecture”,Document  Number:  MD00101  Revision  2.50,July  1,2005.））である。【００５１】
これはMIPS32(R)アーキテクチャ向けの拡張仕様の１つで、組み込み分野をターゲットとした仕様になっている。この拡張は大きく分けて、暗号向け演算アクセラレータ、命令密度の最適化、インタプリタ支援、そしてリソース保護の４本柱になっている。このうちインタプリタ支援については文献[１１]の３．４．３節で概要が触れられ、具体的な命令についての説明は５．１節に記述されている。【００５２】
この拡張では、インタプリタの最内ループ処理を可能な限り少ない命令数で実現できるようにＣＩＳＣ的な命令が定義されている。ＣＩＳＣとは、スーパースカラ登場以前に主流だった計算機の方式で、現在主流のＲＩＳＣ（Reduced  Instruction  Set  Computers）とは対照的に１つ１つの命令が高機能である（Complex  Instruction  Setである）事が特徴となっている。ＣＩＳＣとＲＩＳＣについては文献[１]の２．１６節内に「Reduced  Instruction  Set  Computers」と題されて解説されている。【００５３】
（Just  In  Timeコンパイル方式）
インタプリタを高速に実装するためのソフトウェア側の工夫としてJust  In  Timeコンパイル方式と呼ばれる技術が存在する。この方式ではまずインタプリタとしての動作でプログラムを解釈・実行し、それと同時にプログラムの動作について簡単な統計情報を作成する。この統計情報によりHot  Spot（頻繁に実行される箇所）と判断されたプログラム部分に関しては、その時点でプログラムの解釈をまとめて行い、計算機上で直接実行可能な命令列に変換する。【００５４】
以降、その命令に該当する箇所に実行がさしかかると、インタプリタによる動作をやめ、変換後の直接実行可能な命令列に制御を移す。この方式は、インタプリタ方式とコンパイラ方式の折衷方式と考えることができ、コンパイルにかかる時間的なコストと、直接実行される事による高速化の効果を比較し、効果の方が十分大きい場合に限って用いる事が可能な技術と言える。また、高速化の効果はコンパイル時にどれだけ複雑な最適化を行うかにも影響しており、多くの面でトレード・オフが存在する。また、計算機の性能や広大なメモリを要求するため、この方式は一般的に大規模なシステム上で利用される事が多い。
【実施例１】
【００５５】
続いて、本実施例１の説明を行う。まず、本実施例１にかかるプロセッサの概要および特徴について説明する。本実施例１にかかるインタプリタは、ソースプログラムを逐次実行する場合に、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を実行するように実装されている。【００５６】
このように、本実施例１にかかるインタプリタは、ソースプログラムを実行する場合に、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を実行するので、インタプリタを実行しているプロセッサは、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。【００５７】
なお、本実施例１では、インタプリタを用いて説明するが、これに限定されるものではなく、その他のプログラムによって代用することができる。【００５８】
次に、間接分岐命令と、間接分岐命令の代わりとなる擬似的な間接分岐命令とを比較して説明する。図７は、間接分岐命令を用いるインタプリタの一例を示す図であり、図８は、擬似的な間接命令を用いるインタプリタの一例を示す図である。【００５９】
図７において、「call  %r6」が間接分岐命令に対応する。具体的に、「call  %r6」の処理内容は、プログラムカウンタに格納されたアドレスをリンクレジスタに格納した後に、プロセッサに搭載された汎用レジスタ「r6」に格納された分岐先のアドレスに処理を移行するという内容である。レジスタ「r6」に記憶されるアドレスに応じて分岐先がかわるため間接分岐命令となる。かかる間接分岐命令では、汎用レジスタに格納される分岐先のアドレスが多岐にわたるため、分岐命令の次に実行すべき命令を精度よく実行することができなかった。【００６０】
一方、図８の「move  %link_reg=%r6」および「ret」が擬似的な間接分岐命令に対応する。すなわち、本実施例１のインタプリタは、図７に示したような間接分岐命令「call  %r6」を用いる必要がある場合であっても、かかる間接分岐命令を用いる代わりに、図８に示したような擬似的な間接分岐命令「move  %link_reg=%r6」、「ret」を用いる。【００６１】
図８に示す「move  %link_reg=%r6」の処理内容は、プロセッサに搭載された、分岐元のアドレスを格納するレジスタ（以下、リンクレジスタ）に汎用レジスタ「r6」に格納された分岐先のアドレスを移動させるという内容である。つづく「ret」は、リンクレジスタに格納された分岐元に復帰するための命令であるが、本実施例においては、分岐先のアドレスが格納されているため、分岐先のアドレスに処理を移行する。【００６２】
ここで、リンクレジスタにアドレスを格納するたびに、プロセッサに搭載されたリターン・アドレス・スタック（リターン・アドレス・スタックに関する説明は上記の内容を参照）にアドレスが順に積まれていく。プロセッサは、リンク付き分岐命令を実行した後の復帰時にリターン・アドレス・スタックに積まれた分岐先のアドレスを抽出する（新しく積まれた順にアドレスを抽出する）ことによって、精度よく復帰先のアドレスを予測することができる。【００６３】
次に、本実施例１にかかるプロセッサの構成（構成の一例）について説明する。図９は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ１００は、メモリアクセス制御部１１０と、レジスタ１２０と、リターン・アドレス・スタック１３０と、分岐予測部１４０と、デコード・制御部１５０と、演算パイプライン部１６０とを備えて構成される。【００６４】
また、プロセッサ１００は、各種のデータおよびプログラムを記憶するメインメモリ２００に接続され、メインメモリ２００に記憶された各種データ・プログラムを読み出して各種の処理を逐次実行する。【００６５】
メインメモリ２００は、各種のデータおよびプログラムを記憶する記憶装置であり、特に本発明に密接に関連するものとしては、インタプリタプログラム２００ａ、ソースプログラム２００ｂ、退避データ２００ｃを記憶している。【００６６】
このうち、インタプリタプログラム２００ａは、ソースプログラム２００ｂを逐次読み出して実行するためのプログラムである。プロセッサ１００は、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出してインタプリタを起動することにより、ソースプログラム２００ｂを逐次実行することとなる。また、インタプリタは、ソースプログラム２００ｂを逐次実行する過程において、間接分岐を行う必要がある場合でも、間接分岐命令の代わりに、擬似的な間接分岐命令を用いるように実装されている。【００６７】
例えば、プロセッサ１００により起動されたインタプリタは、ソースプログラム２００ｂを実行する場合に、間接分岐命令「call  %rN（Nは０以上の整数）」（図７参照）が必要となった場合にでも、かかる間接分岐命令を用いず、擬似的な間接分岐命令「move  %link_reg=%rN」、「ret」（図８参照）で代用するように実装されている。【００６８】
続いて、プロセッサ１００の構成の説明に移ると、メモリアクセス制御部１１０は、メインメモリ２００との間で行われるデータの入出力を制御する処理部である。レジスタ１２０は、各種のデータを記憶する記憶装置であり、特に本発明に密接に関連するものとしては、汎用レジスタ群１２０ａ、プログラムカウンタ１２０ｂ、リンクレジスタ１２０ｃを備える。【００６９】
このうち、汎用レジスタ群１２０ａは、各種プログラム（インタプリタプログラム２００ａ等）を実行する場合に利用されるデータ、分岐先のアドレス等を格納するレジスタ群である。図９に示す例では、汎用レジスタ群は、汎用レジスタr0〜rN（Nは整数）を含んでいる。【００７０】
プログラムカウンタ１２０ｂは、次に実行する命令が格納されたアドレスを格納するレジスタであり、リンクレジスタ１２０ｃは、分岐元のアドレスを格納するレジスタである。なお、リンクレジスタ１２０ｃは、メインメモリ２００と協働して、擬似的なスタックを構成する事が可能である。例えば、リンクレジスタ１２０ｃにアドレスＡが格納されている状態で、新たにアドレスＢをリンクレジスタ１２０ｃに格納する場合には、アドレスＡがメインメモリ２００の退避データ２００ｃに退避される。すなわち、リンクレジスタ１２０ｃは新たなアドレスを格納するたびに、退避データ２００ｃにアドレスを退避させる。【００７１】
また、リンクレジスタ１２０ｃにアドレスＢが格納され、メインメモリ２００の退避データ２００ｃにアドレスＡが退避されている状態で、リンクレジスタ１２０ｃのアドレスＡが取り出された場合に、退避データ２００ｃに退避していたアドレスＢをリンクレジスタ１２０ｃに戻す処理を行う。すなわち、リンクレジスタ１２０ｃに格納されたアドレスが取り出されるたびに、退避されたアドレスがリンクレジスタ１２０ｃに戻される（新しく退避データに退避された順番で、アドレスがリンクレジスタ１２０ｃに戻される）。【００７２】
リターン・アドレス・スタック１３０は、リンクレジスタ１２０ｃに分岐元となるアドレスが格納されるたびに、リンクレジスタ１２０ｃに格納されたアドレスと等しいアドレスを順番に格納するレジスタである。例えば、リンクレジスタ１２０ｃにアドレスＡ、アドレスＢ、アドレスＣ・・・の順番でアドレスが格納された場合には、リターン・アドレス・スタック１３０は、アドレスＡ、アドレスＢ、アドレスＣ・・・の順番で、アドレスを記憶する。ただし、メインメモリ２００から読み出した値をリンクレジスタ１２０ｃに格納した場合には、リターン・アドレス・スタック１３０の更新は行わない。なぜなら、メインメモリ２００からの読み出しは、退避していた分岐元アドレスをリンクレジスタ１２０ｃに戻す処理であり、ここでリターン・アドレス・スタック１３０を更新した場合は、格納と抽出の対応が取れなくなるためである。【００７３】
リターン・スタック・アドレス１３０に記憶された各アドレスは、サブルーチン移行後の復帰命令時に、新しく格納したアドレスから順番に分岐予測部１４０に抽出され分岐予測が行われる。【００７４】
分岐予測部１４０は、リターン・アドレス・スタック１３０に記憶された分岐先のアドレスを読み出して、復帰命令時による分岐予測を行う装置である。具体的に、分岐予測部１４０は、リターン・アドレス・スタック１３０に記憶された分岐先のアドレスを、新しく格納された順番で抽出し、抽出した分岐先のアドレスを復帰命令時の分岐先のアドレスとして判定する。【００７５】
デコード・制御部１５０は、分岐予測部１４０から分岐予測結果を取得し、メインメモリ２００に記憶された命令を、メモリアクセス制御部１１０、レジスタ１２０を経由して順次読み出し、実行すべき処理を判定し、判定結果となる制御命令を演算パイプライン部１６０に出力して各種演算を実行させる装置である。また、演算パイプライン部１６０は、デコード・制御部１５０から制御命令を取得し、スーパースカラ方式によって複数の処理を並列して実行する演算装置である。デコード・制御部１５０は、メインメモリ２００から取得した命令が復帰命令の時に、リターン・アドレス・スタック１３０から戻りアドレスを降ろして分岐予測を行い、予測に従って次に実行すべき命令をメインメモリ２００から読み出す。また、演算パイプライン部１６０へ復帰命令を処理する制御命令を送る。演算パイプライン部１６０は、デコード制御部１５０から制御命令を取得し、復帰命令、すなわちリンクレジスタ１２０ｃに格納されたアドレスを読み出し、そのアドレスが次に取得・解釈すべき命令のアドレスであると、デコード・制御部１５０に通達する。【００７６】
図８に示した擬似的な間接分岐を構成する命令、move命令とret命令との間に十分多くの命令を挿入することができれば、リンクレジスタ１２０に書き込まれた値がリターン・アドレス・スタック１３０に積まれることになり、復帰命令を実施する際に復帰先を正しく予想することができる。【００７７】
上述してきたように、本実施例１にかかるプロセッサ１００は、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出してインタプリタを起動し、インタプリタプログラム２００ａがソースプログラム２００ｂを実行する場合において、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を用いて分岐先のアドレスをリンクレジスタ１２０ｃに格納するようにインタプリタプログラム２００ａが実装されているので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。
【実施例２】
【００７８】
上述した実施例１では、インタプリタが、単一の間接分岐命令の代わりに、擬似的な間接分岐命令を用いる場合を例にあげて説明したが、本実施例２では、複数の間接分岐命令が必要な場合に、かかる複数の間接分岐命令の代わりに擬似的な間接分岐命令を実行する場合について説明する。なお、実施例２にかかるプロセッサおよびメインメモリの構成は、実施例１に示したプロセッサ１００およびメインメモリ２００と同様であるので、適宜、図９を用いて実施例２の説明を行う。【００７９】
まず、複数の間接分岐命令を実行するインタプリタを例示する。図１０は、複数の間接分岐命令を実行するインタプリタの一例を示す図である。図１０に示す各種命令を順に説明する。「move  %r6=Func_a」によって、関数「Func_a」を開始するアドレスが汎用レジスタ「r6」に格納され、「move  %r7=Func_b」によって、関数「Func_b」を開始するアドレスが汎用レジスタ「r7」に格納される。【００８０】
そして、「call  %r6」によって汎用レジスタ「r6」に格納されたアドレスに処理が移行して関数「Func_a」が実行され、「call  %r7」によって汎用レジスタ「r7」に格納されたアドレスに処理が移行して関数「Func_b」が移行される。なお、図１０に示す「Func_a:」〜「ret」は、関数「Func_a」のコードであり、「Func_b:」〜「ret」は、関数「Func_b」のコードである。【００８１】
ここで、図１０に示した「call  %r6」と等価の処理を説明する。図１１は、図１０に示した「call  %r6」と等価のプログラムを示す図である。同図に示すように、「call  %r6」と等価のプログラムが「move  %link_reg=%pc」、「jump  %r6」となる。【００８２】
ここで、「move  %link_reg=%pc」は、プログラムカウンタ１２０ｂに格納されたアドレスをリンクレジスタ１２０ｃに格納する命令を示している（プログラムカウンタ１２０ｂおよびリンクレジスタ１２０ｃは図９を参照）。そして、「jump  %r6」によって汎用レジスタ「r6」に格納されたアドレス（図１０の場合では、関数「Funk_a」のアドレス）に移行する命令となる。すなわち、call命令は、リンク処理と間接分岐処理を同時に行う、リンク付き間接分岐命令である。【００８３】
本実施例２のインタプリタは、図１０、図１１に示したような複数の間接分岐命令の代わりに擬似的な間接分岐命令を実行する。図１２は、複数の擬似的な間接分岐命令を実行するインタプリタの一例を示す図である。【００８４】
図１２において、「move  %r6=Func_a」によって、関数「Func_a」を開始するアドレスが汎用レジスタ「r6」に格納され、「move  %r7=Func_b」によって、関数「Func_b」を開始するアドレスが汎用レジスタ「r7」に格納される。【００８５】
そして、「move  %link_reg=%r7」によって、汎用レジスタ「r7」に格納されたアドレスがリンクレジスタ１２０ｃに格納され、「store  (%r1)=%link_reg」によって、リンクレジスタ１２０ｃに格納されたアドレスが、メインメモリ２００の所定領域に退避される。【００８６】
ここで、「move  %link_reg=%r7」は、図１０に示した間接分岐命令「call  %r7」に代わる擬似的な間接分岐のための前処理となる。プロセッサ１００は、「move  %link_reg=%r7」を実行してリンクレジスタ１２０ｃに汎用レジスタ「r7」に格納されたアドレスを書き込むことによって、プロセッサ１００内部では、復帰先アドレスとして汎用レジスタ「r7」で指定されたアドレスをリターン・アドレス・スタック１３０に記憶する。これは、プロセッサ１００の内部で利用するための挙動で、外部には非公開の挙動である。【００８７】
続いて、「move  %link_reg=%r6」によって、汎用レジスタ「%r6」に格納されたアドレスがリンクレジスタ１２０ｃに格納される。なお、関数「Func_a」を実行するバイナリコードには、末尾に「load  %link_reg=(%r1)」、「ret」が含まれ、「load  %link_reg=(%r1)」によってメインメモリ２００の所定領域に退避していたアドレスをリンクレジスタ１２０ｃに格納し、「ret」によって処理が元の関数に戻される。なお、「Func_b:」〜「ret」は、関数「Func_b」のコードであり、「Func_a:」〜「ret」と同様の各種コードが含まれる。【００８８】
「store  (%r1)=%link_reg」を実行することで、リンクレジスタ１２０ｃに書き込まれたアドレスを即座にメインメモリ２００に退避し、「move  %link_reg=%r6」を実行することで、汎用レジスタ「r6」で指定されたアドレスをリンクレジスタ１２０ｃに格納している。【００８９】
上記命令をプロセッサが実行することによって、リンクレジスタ１２０ｃに格納されていたアドレスが上書きされてしまうことになるが、リターン・アドレス・スタック１３０は、その名の通り、スタックとしての構造を持っており、復帰先のアドレスが上書きされるわけではなく、直近の復帰先が汎用レジスタ「r6」に格納されていたアドレスとなり、その次の復帰先が汎用レジスタ「r7」に格納されていたアドレスとなる。【００９０】
その後、復帰命令により現在のリンクレジスタ１２０ｃの値（汎用レジスタr6の値に対応）で指定された命令アドレスに処理を移す。これが復帰命令により擬似的に間接分岐を行っている部分である。続いて、その関数の最後において、退避したアドレスを再度リンクレジスタ１２０ｃに取り戻して復帰命令を実行している。【００９１】
ここでリンクレジスタ１２０ｃに値を取り戻したのは、リターン・アドレス・スタック１３０に積まれたアドレスが、あくまでも分岐予測のための情報でしかないためである。仮にリンクレジスタ１２０ｃの値を元に戻さずに復帰してしまえば、再び現在のリンクレジスタ１２０ｃの値、つまり「Func_a」の先頭に処理は移動し、同時に分岐予測も外れる。２つ目の分岐アドレスがリンクレジスタ１２０ｃに格納されるのは呼び出し（＝復帰）の直前なのだが、リターン・アドレス・スタック１３０への積載は「Func_a」呼び出し以前にまとめて行われているため、結果としてはリターン・アドレス・スタック１３０を用いた分岐予測はデコード・制御部１５０による命令の取得に間に合い、ヒットする事になる。【００９２】
ところで、プロセッサ１００は、インタプリタプログラム２００ａを読み出して、インタプリタを起動し、インタプリタがソースプログラム２００ｂを実行する場合に、複数の間接分岐命令（図１０、図１１を参照）の代わりに、擬似的な間接分岐命令（図１２を参照）を用いる。すなわち、プロセッサ１００は、間接分岐を行うことなく各命令を実行することができる。【００９３】
具体的に、プロセッサ１００が、インタプリタを起動した場合には、本実施例のインタプリタは、ソースプログラム２００ｂを実行する上で必要となる複数の間接分岐命令（例えば、call命令など）を逆順に抽出し（図１０に示す例では、「call  %r7」、「call  %r6」の順番で抽出し）、抽出した間接分岐命令に対応する分岐先のアドレスを逆順に（図１０に示す例では、「Func_bのアドレス」、「Func_aのアドレス」の順番）、リンクレジスタ１２０ｃに格納するような擬似的な間接分岐命令のための前処理を実行するように実装されている。【００９４】
なお、間接分岐命令の置き替えに関して、事前処理をどこまでまとめて行えるかは、ソースプログラム中の分岐を伴う制御文（条件文、Switch文、仮想関数呼び出しなど）単位となる。【００９５】
次に、本実施例２にかかるプロセッサ１００が、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出して起動するインタプリタの処理手順について説明する。図１３、図１４は、インタプリタの処理手順を示すフローチャートである。【００９６】
同図に示すように、インタプリタは、「プログラム読込開始位置」としてプログラム（ソースプログラム）の先頭位置を設定し（ステップＳ１０１）、「プログラム読込開始位置」に「プログラム読込現在位置」を設定し（ステップＳ１０２）、「プログラム読込現在位置」から１処理分のプログラムを読み込み、解釈する（ステップＳ１０３）。【００９７】
そして、インタプリタは、「プログラム読込現在位置」を１処理分だけ先に進め（ステップＳ１０４）、解釈した命令が分岐処理であるか否かを判定する（ステップＳ１０５）。解釈した命令が分岐命令でない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０３に移行する。【００９８】
一方、解釈した命令が分岐命令である場合には（ステップＳ１０６，Ｙｅｓ）、「プログラム読込停止位置」に「プログラム読込現在位置」を設定し（ステップＳ１０７）、リンクレジスタ１２０ｃに格納されたアドレスをメインメモリ２００上のスタックに退避し（ステップＳ１０８）、「プログラム読込現在位置」から１処理分のプログラムを読み込み、解釈する（ステップＳ１０９）。【００９９】
続いて、解釈した命令に対応する処理を行うインタプリタ上の関数を調べ（ステップＳ１１０）、求めた関数のアドレスをリンクレジスタ１２０ｃに格納し（ステップＳ１１１）、「プログラム読込現在位置」を１処理分だけ後ろに戻す（ステップＳ１１２）。【０１００】
そして、インタプリタは、「プログラム読込現在位置」と「プログラム読込開始位置」とが等しいか否かを判定し（ステップＳ１１３）、等しくない場合には（ステップＳ１１４，Ｎｏ）、ステップＳ１０８に移行する。【０１０１】
一方、「プログラム読込現在位置」と「プログラム読込開始位置」とが等しい場合には（ステップＳ１１４，Ｙｅｓ）、「ret」命令を実行し、リンクレジスタ１２０ｃに格納された関数へ分岐する（ステップＳ１１５）。【０１０２】
そして、インタプリタは、分岐先の関数で、プログラム中の１処理に対応した処理を行い（ステップＳ１１６）、分岐処理を行う関数か否かを判定し（ステップＳ１１７）、分岐処理を行なわない場合には（ステップＳ１１８，Ｎｏ）、分岐先の関数末尾で、メインメモリ２００上のスタックに退避したリンクレジスタ１２０ｃの値を１つリンクレジスタに取り出し（ステップＳ１１９）、ステップＳ１１５に移行する。【０１０３】
一方、分岐処理を行う関数である場合には（ステップＳ１１８，Ｙｅｓ）、分岐処理に対応する関数を実行し（ステップＳ１２０）、「プログラム読込開始位置」として「プログラム実行停止位置」から１処理分だけ先に進めた位置を設定し（ステップＳ１２１）、ステップＳ１０２に移行する。【０１０４】
このように、インタプリタが、間接分岐命令の代わりに擬似的な間接分岐を実行するように実装されているので、インタプリタによって最も頻繁に実行されるループの高速化が期待され、間接分岐命令単体だけではなく、プログラム全体としても大きな性能向上を見込める。【０１０５】
上述してきたように、本実施例２にかかるプロセッサ１００は、インタプリタプログラム２００ａを読み出してインタプリタを起動し、ソースプログラム２００ｂを実行する上で必要となる間接分岐命令の代わりに、間接分岐命令の分岐先のアドレスを逆順にリンクレジスタ１２０ｃに格納し、復帰命令によって分岐するといった擬似的な間接分岐命令を利用する（プロセッサ１００は、内部的に、リンクレジスタ１２０ｃに格納された値を、自動的にリターン・アドレス・スタック１３０に積む）ので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。また、分岐先アドレスをまとめてリンクレジスタ１２０ｃに登録することで、実際の分岐処理に十分に先立って、分岐先アドレスをリンクレジスタ１２０ｃに登録しており、復帰命令により疑似的な間接分岐が実行される時までに、プロセッサ１００によって、リンクレジスタ１２０ｃに登録されたデータをリターン・アドレス・スタック１３０に登録する作業が完了しており、分岐予測が間に合う（＝予測がヒットする）。【０１０６】
なお、上述の実施例１および実施例２では、インタプリタが間接分岐命令を実行する代わりに擬似的な間接分岐命令を用いる場合を例にあげて説明したが、かかる実行方式を仮想マシンに適用することも可能である。すなわち、仮想マシン（Ｊａｖａ（登録商標）等）がバイナリを実行する際に、間接分岐命令が必要となっても、かかる間接分岐命令の代わりに擬似的な間接分岐命令を実行して、プロセッサ１００に分岐先となるアドレスをリターン・アドレス・スタック１３０に格納させ、分岐予測を成功させることができる。
【実施例３】
【０１０７】
上述した実施例１、２では、インタプリタがソースプログラムを逐次実行する場合において、間接分岐命令の代わりに擬似的な間接分岐命令を利用していたが、コンパイラによって、間接分岐命令の代わりに疑似的な間接分岐命令を利用するコードを生成することも可能である。【０１０８】
すなわち、コンパイラによってソースプログラムをコンパイルし、間接分岐命令の代わりに擬似的な間接分岐命令を含んだプログラム（以下、擬似間接分岐プログラムと表記する）を生成し、プロセッサが、かかる擬似間接分岐プログラムを実行することによって、間接分岐命令に相当する処理を高速化することができる。【０１０９】
次に、本実施例３にかかるプロセッサの構成について説明する。図１５は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ３００は、メインメモリ４００に接続され、メモリアクセス制御部３１０と、レジスタ３２０と、リターン・アドレス・スタック３３０と、分岐予測部３４０と、デコード・制御部３５０と、演算パイプライン部３６０とを備えて構成される。【０１１０】
ここで、メモリアクセス制御部３１０、レジスタ３２０、リターン・アドレス・スタック３３０、分岐予測部３４０、デコード・制御部３５０、演算パイプライン部３６０は、図９において説明したメモリアクセス制御部１１０、レジスタ１２０、リターン・アドレス・スタック１３０、分岐予測部１４０、デコード・制御部１５０、演算パイプライン部１６０に対応するため、説明を省略する。【０１１１】
また、メインメモリ４００は、各種のデータおよびプログラムを記憶する記憶装置であり、コンパイラプログラム４００ａと、ソースプログラム４００ｂと、擬似間接分岐プログラム４００ｃと、退避データ４００ｄとを記憶する。【０１１２】
このうち、コンパイラプログラム４００ａは、プロセッサ３００が実行可能な、コンパイルを行うためのプログラムである。プロセッサ３００が、コンパイラを起動することによって、ソースプログラム４００ｂをコンパイルし、擬似間接分岐プログラム４００ｃを生成する。【０１１３】
コンパイラを起動したプロセッサ３００は、ソースプログラム４００ｂをコンパイルする過程において、ソースプログラム４００ｂの命令を間接分岐命令（図７、図１０参照）に変換する必要がある場合に、かかる間接分岐命令の代わりに擬似的な間接分岐命令に変換する（図８、図１２参照）。すなわち、従来では、図７のようにソースプログラム４００ｂをコンパイルしていたものを、図８のようにコンパイルする。あるいは、図１０のようにソースプログラム４００ｂをコンパイルしていたものを、図１２のようにコンパイルする。【０１１４】
プロセッサ３００は、コンパイラによって擬似間接分岐プログラム４００ｃを生成した後に、擬似間接分岐プログラム４００ｃを読み出して、擬似間接分岐プログラム４００ｃに応じた処理を実行する。この擬似間接分岐プログラム４００ｃには、間接分岐命令の代わりに擬似的な間接分岐命令が含まれているので、間接分岐命令に相当する処理を高速化することができる。【０１１５】
上述してきたように、本実施例３にかかるプロセッサ３００は、コンパイラを起動してソースプログラム４００ｂをコンパイルし、間接分岐命令の代わりに擬似的な間接分岐命令を含んだ擬似間接分岐プログラム４００ｃを生成し、プロセッサ３００が、かかる擬似間接分岐プログラム４００ｃを実行するので、間接分岐命令に相当する処理を高速化することができる。【０１１６】
なお、本実施例３では、プロセッサ３００がコンパイラを起動して、ソースプログラム４００ｂから擬似間接分岐プログラム４００ｃを作成していたが、これに限定されるものではなく、コンパイルを専用に実行するコンパイラ装置によって、ソースプログラム４００ｂをコンパイルし、間接分岐命令の代わりに擬似間接分岐命令を含んだ擬似間接分岐プログラム４００ｃを生成し、かかる擬似間接分岐プログラム４００ｃをプロセッサ３００、あるいはプロセッサ１００が実行するようにしても構わない。【０１１７】
ところで、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部あるいは一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。【０１１８】
また、図９および図１５に示したプロセッサ１００，３００の構成は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。【０１１９】
また、図９および図１５のメモリ２００，４００に記憶された各種プログラム（インタプリタプログラム２００ａ、ソースプログラム２００ｂ，４００ｂ、コンパイラプログラム４００ａ、擬似間接分岐プログラム４００ｃ）は、必ずしも最初からメインメモリ２００，４００に記憶させておく必要はない。たとえば、コンピュータに挿入されるフロッピー（登録商標）ディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータの内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータに接続される「他のコンピュータ（またはサーバ）」などに各種プログラムを記憶しておき、コンピュータ（プロセッサ）がこれらから各種プログラムを読み出して実行するようにしてもよい。【０１２０】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。
【産業上の利用可能性】
【０１２１】
上述したように、本発明は、現在広く利用されているインタプリタ等に対して、高速な実装方法を提供する物である。この手法は、現在利用されている計算機上で実現可能であり、また実装にかかるコストも大きくはない。また、産業上大きなインパクトを持つＪａｖａ（商標登録）をはじめとする仮想マシンに対しても有効な最適化手法であるため、実用上の価値も高い。また、インタプリタを作り直すだけで、その上で動いていた全てのプログラムが高速に動作するようになる点も評価できる。
【図１】
2009004709.tif 000003
【図２】
2009004709.tif 000004
【図３】
2009004709.tif 000005
【図４】
2009004709.tif 000006
【図５】
2009004709.tif 000007
【図６】
2009004709.tif 000008
【図７】
2009004709.tif 000009
【図８】
2009004709.tif 000010
【図９】
2009004709.tif 000011
【図１０】
2009004709.tif 000012
【図１１】
2009004709.tif 000013
【図１２】
2009004709.tif 000014
【図１３】
2009004709.tif 000015
【図１４】
2009004709.tif 000016
【図１５】
2009004709.tif 000017
【手続補正書】
【提出日】平成21年10月27日(2009.10.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータに、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムを実行する場合に必要となる間接分岐命令の代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐コードを生成するコード生成手順と、
前記コード生成手順によって生成された擬似間接分岐コードを記憶装置に記憶させる記憶手順と、
前記記憶装置に記憶された擬似間接分岐コードの命令を逐次読み出して実行する実行手順と、
を実行させるための間接分岐処理プログラム。
【請求項２】
前記コード生成手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる命令で代用した擬似間接分岐コードを生成することを特徴とする請求項１に記載の間接分岐処理プログラム。
【請求項３】
記憶装置に記憶されたソースプログラムを読み出して処理を実行するコンピュータの間接分岐処理方法であって、
前記コンピュータは、
記憶装置に記憶されたソースプログラムを読み込む読込工程と、
前記ソースプログラムを実行する場合に必要となる間接分岐命令の代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐コードを生成するコード生成工程と、
前記コード生成工程によって生成された擬似間接分岐コードを記憶装置に記憶させる記憶工程と、
前記記憶装置に記憶された擬似間接分岐コードの命令を逐次読み出して実行する実行工程と、
を含んだことを特徴とする間接分岐処理方法。
【請求項４】
ソースプログラムを解釈し、ソースプログラムの内容に応じた処理コードを選択して当該処理コードを呼び出すインタプリタをコンピュータに実行させるための間接分岐処理プログラムであって、
前記インタプリタは、
記憶装置に記憶されたソースプログラムを読み込む読込手順と、
前記ソースプログラムに応じた処理コードを選択し、当該処理コードが間接分岐命令に対応する処理コードである場合に、前記間接分岐命令に対応する処理コードの代わりに、当該間接分岐命令の分岐先のアドレスを逆順にレジスタおよび／またはメモリに格納する命令を含んだ擬似間接分岐命令に対応する処理コードを呼び出す呼出手順と、
を含んだことを特徴とする。
【請求項５】
前記呼出手順は、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令の処理コードを、前記レジスタおよび／またはメモリに格納された分岐先のアドレスに処理を移行させる擬似間接分岐命令の処理コードで代用することを特徴とする請求項４に記載の間接分岐処理プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、間接分岐命令の代わりに擬似的な間接分岐命令をコンピュータに実行させる間接分岐処理プログラムおよび間接分岐処理方法に関するものである。
【背景技術】
【０００２】
従来より、計算機（ＣＰＵ（Central  Processing  Unit）等）は、コンパイル方式あるいはインタプリタ方式によって人間により記述されたソースプログラムを実行している。コンパイル方式は、ソースプログラムをコンパイラと呼ばれる変換プログラムにより計算機上で実行できるバイナリ形式に変換した後に、バイナリ形式に変換したコードを実行する方式であり、インタプリタ方式は、インタプリタと呼ばれる特別なバイナリコードを計算機上で実行し、インタプリタがソースプログラムを逐次解釈しながら内容に応じた処理を随時行う方式である。
【０００３】
ところで、近年では、計算機の処理を高速化するために、計算機をスーパースカラと呼ばれる方式に基づいて設計している。この方式では、パイプライン方式で処理を行うことを前提としている。パイプライン方式では、各命令処理が複数のステージに分割され、それぞれのステージが個別のユニットにより処理される。そのため、次に実行すべき命令が確定していれば、先行命令の第二ステージの実行と並行して、後続命令の第一ステージを実行することができ、分割したステージの数だけ並列動作による高速な実行が可能となる。
【０００４】
ここで、パイプライン処理が巧く機能する条件として、次に実行すべき命令が確定しているという条件が存在する。つまり、命令１の次に実行すべき命令２（命令が命令１、命令２、命令３・・・の順で実行される場合）が、命令１の第１ステージの実行が完了するまでに確定していない時、次の命令２の処理を並列して実行することができない（命令２に続く命令も同様である）。
【０００５】
このような状態が発生する代表的な例が、分岐命令である。分岐命令においては、直前の分岐条件判定命令（例えば、比較命令）の結果が判明するまで、次に処理するべき命令が確定せず、パイプライン処理を行うことができないため、計算機全体の処理速度が大幅に低下してしまう。
【０００６】
パイプライン処理の性能低下を防止するために、分岐予測と呼ばれる技術が考案され実用化されている。かかる分岐予測の原理としては、過去に実行したプログラムの分岐結果を履歴に残しておき、その延長線上で分岐結果を予測するというアイデアが基本となっている（例えば、非特許文献１参照）。
【０００７】
また、分岐命令には、通常の分岐命令だけではなく、レジスタに記憶されたアドレスを基にして分岐する間接分岐命令も存在する。間接分岐命令は、上述したインタプリタを実装する際などに頻繁に利用されている。しかし、間接分岐命令は、スーパースカラ方式の計算機においてコストの高い命令となっているため、間接分岐命令に焦点を当てた予測手法の研究も行われている（例えば、非特許文献２、非特許文献３参照）。
【０００８】
なお、特許文献１では、狭いアドレス空間のみを取り扱うプロセッサ用に書かれたコードを、間接コールを用いずに広いアドレス空間を取り扱うプロセッサに適用する技術が示されている。
【０００９】
【非特許文献１】John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture-A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.
【非特許文献２】P.-Y.  Chang,  E.  Hao,  and  Y.  N.  Patt.  “Target  Prediction  for  Indirect  Jumps”,  In  Proceedings  of  24th  International  Symposium  on  Computer  Architecture,  pp.  274~283,  1997.
【非特許文献３】K.  Driesen  and  U.  HAolzle.  “Accurate  Indirect  Branch  Prediction”,  In  Proceedings  of  25th  International  Symposium  on  Computer  Architecture,  pp.  167~178,  1998.
【特許文献１】特開２０００−２８４９６５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来の技術では、プログラム中に記載されたある間接分岐命令の次にどの命令が実行されるかを履歴から予測しても、予測した命令と実際に次に実行される命令が一致する確率が低いという問題があった。
【００１１】
実行のたびに異なる分岐先を持つような間接分岐命令に対しては、非特許文献２および非特許文献３の技術を利用したとしても、精度のよい予測を行うことができず、間接分岐命令は、スーパースカラ方式によってプログラムを実行する計算機にとって依然、コストの高い命令となっている。
【００１２】
本発明は、上記に鑑みてなされたものであって、分岐予測を精度よく行うことができる間接分岐処理プログラムおよび間接分岐処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上述した課題を解決し、目的を達成するために、コンピュータ上のインタプリタに、記憶装置に記憶されたソースプログラムを読み込む読込手順と、前記ソースプログラムを解釈し、内容にあったインタプリタ内の処理コードを選択する手順と、前記コード選択手順によって選択された処理コードを呼び出す手順を実行させるが、当該インタプリタは、前記処理コード選択、呼び出し手順において、選択したコードに分岐するために、間接分岐命令を利用する代わりに、選択したコードのアドレスを処理の順序とは逆順にコールスタックに格納し、疑似的な間接分岐命令によって呼び出し処理を行う。
【００１４】
また、本発明は、上記発明において、前記処理コード呼び出し手順の、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記コールスタックに分岐先のアドレスを格納し、そのアドレスに処理を移行させる命令で代用した擬似間接分岐コードで代用することを特徴とする。
【００１５】
また、本発明は、上記発明において、前記コンピュータに搭載された所定のスタック、またはリンクレジスタに間接分岐命令の分岐先のアドレスを格納することで、間接的に計算機内部の復帰アドレス予測テーブルを更新し、疑似的な間接分岐を処理する際に分岐予測を成功させることを特徴とする。
【００１６】
また、本発明は、上記発明において、前記ソースプログラムには、処理の分岐を伴う制御文が記述されており、前記インタプリタ内の擬似間接分岐コードは、前記制御文の条件判定部が記述されるまでの区間ごとに前記処理コードのアドレスを逆順にコールスタックに格納する命令を含んでいることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、コンピュータに、記憶装置に記憶されたソースプログラムを読み込む読込手順と、ソースプログラムを解釈し、内容にあったインタプリタ内の処理コードを選択する手順と、コード選択手順によって選択された処理コードを呼び出す手順と、を実行させ、この処理により、間接的に計算機内部の復帰アドレス予測テーブルを更新し、処理コード呼び出し手順の際には、この予測テーブルを用いて分岐予測が行われるので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。
【００１８】
また、本発明によれば、コンピュータに実行させるコードの呼び出し手順において、汎用レジスタに記憶された分岐先のアドレスに処理を移行させる間接分岐命令を、前記コールスタックに岐先のアドレスを格納し、そのアドレスに処理を移行させる命令で代用した擬似間接分岐コードで代用するので、ソースプログラムを実行するコンピュータの処理性能を向上させることができる。
【００１９】
また、本発明によれば、コンピュータに搭載された所定のスタック、またはリンクレジスタに間接分岐命令の分岐先のアドレスを逆順に格納することで、間接的に計算機内部の復帰アドレス予測テーブルを更新し、疑似的な間接分岐を処理する際に分岐予測を成功させるので、コンピュータの分岐予測の精度を向上させ、ソースプログラムを実行するコンピュータの処理性能を向上させることができる。
【００２０】
また、本発明によれば、ソースプログラムには、処理の分岐を行う制御文が記述されており、インタプリタ内の擬似間接分岐コードは、制御文の条件判定部が記載されるまでの区間ごとに前記間接分岐命令の分岐先のアドレスを逆順にコールスタックに格納する命令を含んでいるため、より効率よく高速に擬似間接分岐を実行することができる。
【発明を実施するための最良の形態】
【００２１】
以下に、本発明にかかる間接分岐処理プログラムおよび間接分岐処理方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００２２】
まず、本願発明にかかる実施例の説明を行う前に、本願発明に関わる従来の技術（間接分岐命令、インタプリタ方式およびコンパイル方式、スーパースカラプロセッサとパイプライン処理、分岐予測、関数からの復帰処理、リターン・アドレス・スタック、ハードウェアによるインタプリタ支援、Just  In  Timeコンパイル方式）について順に説明する。
【００２３】
（間接分岐命令）
ＣＰＵ（Central  Processing  Unit）等の計算機上で動作するプログラムについて、途中結果に応じて異なる処理を行うために分岐と呼ばれる命令が用いられる。計算機システムにおいて、プログラムはメモリ上に順に配置され、配置された順に従い、計算機により逐次実行される。図１は、分岐処理を説明するための図である。実行が分岐命令に差し掛かると、直前の条件判定結果において特定の条件を満たした場合に、次に処理すべき命令アドレスを指定されたメモリアドレスに変更する（図１では、条件に応じて、処理３あるいは処理５に移行することとなる）。この条件判定命令あるいは分岐命令においては、メモリアドレスや条件は、命令の一部として符号化された固定値である。
【００２４】
一方、条件に応じて複数の分岐先へ処理を移したい場合が存在する。図２は、複数の分岐処理と間接分岐処理とを説明するための図である。図２の左側に示すように、条件判定と分岐を必要な種類だけ並べて実現する事もできるが、多くの条件判定を伴う分岐は効率が悪い。そこで用いられるのが間接分岐命令と呼ばれる処理である。この処理では、次に実行すべきアドレスとしてレジスタの値が用いられる。即ち、過去の計算結果そのものを次の命令アドレスとして指定できる。これにより、プログラム自身で分岐先命令アドレスを計算し、その値により間接分岐を行う事が可能となり、任意の処理への分岐が実現できる（図２の右側参照）。
【００２５】
（インタプリタ方式およびコンパイル方式）
計算機上で動作するプログラムの実行方式には、大きく分けて２つの方式が存在する。１つがコンパイル方式であり、もう１つがこのインタプリタ方式である。コンパイル方式においては、ソースファイルに記述されたプログラムを、事前にコンパイラにより実行バイナリに変換する必要がある。このコンパイラにより変換された実行バイナリは、計算機上で直接実行される。
【００２６】
一方、インタプリタ方式において計算機上で直接実行されるのは、インタプリタと呼ばれるソフトウェアである。インタプリタは、ソースファイルを逐次解釈しながら、プログラム記述に沿った処理を行う。このため、コンパイル方式に比べ、プログラムの処理には時間がかかる。しかしその一方で、異なる設計の計算機システムにおいても、共通仕様のインタプリタが存在すれば、同一のプログラムをそのまま利用する事が可能というメリットも存在する。
【００２７】
図３は、コンパイル方式とインタプリタ方式との違いを説明するための図である。図３の左側に示すように、インタプリタ方式では、ハードウェア上で直接動作するのは基本ソフトとインタプリタであり、インタプリタは、基本ソフトの機能を利用しながら動作する。プログラムはこのインタプリタ上で解釈・実行される。一方、図３の右側に示すように、コンパイル方式ではプログラムはコンパイルされ、実行ファイルに変換される。実行ファイルは基本ソフトの機能を利用しながら、直接ハードウェアで実行される。
【００２８】
インタプリタは、それ自身１つのソフトウェアとして記述されている。インタプリタの基本動作は、プログラムを逐次解釈し、その内容に応じた処理を行う事の繰り返しである。図４は、従来のインタプリタの処理を示すフローチャートである。ここで注目したいのが、中央にある分岐処理「命令に応じた処理へ分岐」である。この分岐は、図４からもわかる通り複数の処理へ分岐する必要があり（例えば、処理Ａ、処理Ｂ、・・・処理Ｙ、処理Ｚのいずれかに分岐する必要があり）、この分岐としては間接分岐を用いる必要がある。よって、インタプリタの動作速度は、この間接分岐の処理効率に大きく左右される事になる。
【００２９】
（スーパースカラプロセッサとパイプライン処理）
現在の高性能計算機は、内部はスーパースカラと呼ばれる方式に基づいて設計されている。この方式ではパイプライン方式で処理を行う事を前提としており、パイプライン方式では各命令の処理は複数のステージに分割され、それぞれのステージが個別のユニットにより処理される。
【００３０】
図５は、パイプライン処理を説明するための図である。図５における横軸が時間の流れを示し、縦軸が命令の流れを示す。図５に示す例では、命令処理をＩＦ、ＩＤ、ＥＸ、ＭＥＭ、ＷＢと５つのステージに分割している。最新のプロセッサでは、このステージ数が増加する傾向にあり、十数段のステージに分割されている事も稀ではない。
【００３１】
さて、ＩＦを処理するユニット（ＩＦユニット）について考える。このＩＦユニットでは、特定の命令のＩＦに該当する処理を行い、結果を次のＩＤユニットに引き渡す。よって、次のサイクルにおいてＩＤの処理が行われている際には、ＩＦユニットが命令に対して行うべき処理はない。同様にして次のサイクルではＥＸユニットが処理を行い、ＩＦユニット、ＩＤユニットの行うべき処理はない。
【００３２】
これを利用して、次のサイクルではＩＦユニットは次の命令のＩＦ処理を行うようにする。このようにして後続する命令の処理を平行して分割実行する事で、１つの命令の処理の完了まで５サイクルかかっていたとしても、長い時間で見ると、平均して１サイクル毎に１つの命令の処理が完了する事になる。このようにＮサイクルかかる処理を分割・並列実行する事で見かけ上の処理時間を１サイクルにするような技術をパイプライン技術と呼ぶ。
【００３３】
ただし、このパイプライン処理が巧く機能する条件として、次に実行すべき命令が確定している、という条件が存在する。つまり、命令１の次に実行すべき命令が、命令１の実行が完了するまで確定していない時、次の命令の処理を並列して開始する事ができない。このような状態が発生する代表的な例が、分岐命令である。
【００３４】
分岐命令においては、直前の条件判定命令の結果が判明するまで、次に処理するべき命令が確定しない。このため、パイプライン処理を行う事ができずに、全体として性能が大きく低下してしまう。これを回避するための技術が分岐予測と呼ばれる技術である。分岐予測に関する詳しい説明は後述するが、簡単に説明すると、これは条件判定結果をあらかじめ予測し、分岐命令の時点で比較結果が確定していない時にも、この予測に基づき次に実行すべき命令を推測し、その推測に従って処理を進める方式である。
【００３５】
この方式を用いれば、予測の精度が十分に高い場合に、分岐による性能低下はなくなる。また、予測がはずれた場合には、それ以降の命令処理を破棄し、仮定に基づき実行した命令が処理される前の状態に巻き戻した上で、正しい命令列を改めて実行しなおす事で、実行結果に影響は与えない。スーパースカラプロセッサに関する詳細は文献［２]（Mike  Johnson.  “Superscalar  Microprocessor  Design,”  Prentice-Hallm  Inc,  ISBN  0138756341.）に記載されており、計算機全般に関する技術の詳細は文献[１]（John  L.  Hennessy,  and  David  A.  Patterson.  “Computer  Architecture-A  Quantitative  Approach  3rd  Edition,”  MORGAN  KAUFMANN  PUBLISHERS,  ISBN  1-55860-724-2.）に記載されている。
【００３６】
（分岐予測）
上記の「スーパースカラプロセッサとパイプライン処理」の節で述べた通り、精度の良い分岐予測を行うことは、スーパースカラ方式の計算機にとって重要な課題である。しかし、予測は条件判定結果に先立って、即座に行う事ができないと意味がなく、またハードウェアとして実装するため、大規模なデータベースを用いた予測なども行えない。よって、限られた資源でなるべく精度の高い予測が行えるよう工夫がなされている。
【００３７】
分岐予測の原理としては、過去の分岐結果を記憶しておき、その延長線上で分岐結果を予想するというアイデアが基本となっている。過去数回の分岐結果を命令毎に記憶しておき、過去の分岐傾向に従い予測するだけの単純な予測で、９０％以上の精度で予測が当たるとされている。
【００３８】
ただし、実際には全ての分岐命令に対し個別の履歴を用意する事は難しく、分岐命令の命令アドレスの下位ビットをインデックスとして履歴を参照する方法が用いられる。この場合、運が悪い時には複数の分岐命令で同じ履歴を共有してしまい、正しく予測が行えない。
【００３９】
また、精度向上の工夫として、分岐間の相関を利用する方法がある。これは、特定の分岐結果は、その分岐命令に至るまでに通過した分岐命令の結果と相関関係がある事を利用している。これらは広域分岐予測と呼ばれ、９５％前後の制度で予測する事が可能となる。さらには複数の予測機構を組み合わせて使うなど、様々な工夫により分岐予測精度の向上が図られている。予測機構については、文献[１]の３．４節以降に詳しく説明されている。また、ウィキペディア日本語版「分岐予測」の項[３]にも分岐予測の説明がなされている（“分岐予測”、ウィキペディア日本語版,http://ja.wikipedia.org/を参照）。
【００４０】
一方、これらの分岐予測手法は通常の分岐命令だけに焦点をあてた方法である。つまり複数の分岐先を持つような間接分岐命令に対しては、有効な予測手段を提供していない。間接分岐に焦点を当てた予測手法の研究は文献[４]（P.-Y.  Chang,  E.  Hao,  and  Y.  N.  Patt.  “Target  Prediction  for  Indirect  Jumps”,  In  Proceedings  of  24th  International  Symposium  on  Computer  Architecture,  pp.  274~283,  1997.）および文献[５]（K.  Driesen  and  U.  HAolzle.  “Accurate  Indirect  Branch  Prediction”,  In  Proceedings  of  25th  International  Symposium  on  Computer  Architecture,  pp.  167~178,  1998.）などが存在する。
【００４１】
また、商用プロセッサにおいてはIntel(R)  Pentium(R)  Mが間接分岐予測器を搭載したプロセッサとして存在する。この予測の仕組みについては例えば、文献[６]（S.  Gochman,  R.  Ronen,  I.  Anati,  A.  Berkovits,  T.  Kurts,  A.  Naveh,  A.  Saeed,  Z.  Sperber,  and  R.  C.  Valentine.  “The  Intel  Pentium  M  Processor:  Microarchitecture  and  Performance”,  Intel  Technology  Journal,  7(2):21~36,  2003.）に記述されている。
【００４２】
また、分岐予測以外にもコンパイラと協調して分岐先アドレスをフォワーディングし、予測しなくてもペナルティが発生しない手法も研究されている（文献[７]（豊島隆志、入江英嗣、五島正裕、and坂井修一.“レジスタ間接分岐ターゲット・フォワーディング”,  SACSIS  2006））。しかしながら、間接分岐を考慮した予測機構を備えた商用プロセッサは少なく、また搭載されていたとしても、通常の分岐命令に比べ精度の良い予測を行うことはできていない。従って、間接分岐命令は、スーパースカラ方式のプロセッサにとって、コストの高い命令となっている。
【００４３】
（関数からの復帰処理）
特殊な形式の分岐を必要とする処理に「関数呼び出し」機能が挙げられる。図６は、関数呼び出しの様子を説明するための図である。同図に示す例では、メインの処理から関数Ａが、関数Ａから関数Ｂが呼び出される様子を示している。図６からもわかるように関数Ａはメイン処理の複数の箇所から呼び出される。
【００４４】
一般に関数は、プログラム中のいずれの場所からも呼び出し可能であり、関数の実行が終了した際に移る次の処理というのは、呼び出し元箇所の次の命令となる。つまり、関数から戻る際には、複数の分岐先を持った分岐処理を行う必要がある。このために特殊な命令が用意されている事が多く、一般的には復帰命令（リターン命令）と呼ばれる命令が定義されている。
【００４５】
リターン命令は、それに対応するリンク処理が必要とされる。多くの計算機においては、関数を呼び出す際に、「Jump  and  Link」と呼ばれるリンク付き分岐命令を用いる。これは分岐と同時に現在実行中の命令アドレスを特定の場所に退避する命令である。復帰命令が呼ばれた際には、この時に退避された命令アドレスを用いて、呼び出し元のアドレスを特定し、呼び出し元に再分岐する。関数は入れ子状で呼び出されるため、この退避場所はスタック構造を持つ資源に格納される事が多い。あるいは特定の場所に一時退避し、次のリンク処理により上書きされる前に、一時退避済みのアドレスをソフトウェア的に再退避する事で入れ子状の呼び出しにも対応している。
【００４６】
（リターン・アドレス・スタック）
上記のリンク処理と復帰処理は特定の命令により実施される事が多く、プロセッサ内部で関数の呼び出し、復帰箇所を特定する事ができる。プロセッサ内部では、この復帰処理にかかる分岐のコストを最小限にするため、復帰処理に特化した分岐予測機構を備えている事が多い。現在利用されている商用プロセッサにおいては、例外なくこの予測機構は搭載されている。
【００４７】
この機構はリターン・アドレス・スタックと呼ばれ、リンク時に呼び出し元を内部のリターン・アドレス・スタックに積み、復帰時にはこのスタックから降ろしたアドレスを用いて分岐予測を行う。このリターン・アドレス・スタックとは、プログラムから見える外部仕様的な戻りアドレス退避場所とは異なり、プロセッサ内部で予測のためだけに用いられる特殊な記憶領域である。リターン・アドレス・スタックについては、文献［８]（C.F.Webb.  Subroutine.“call/return  stack”,IBM  Technical  Disclosure  Bulletin,  30(11):18~20,1988.）の技術解説、あるいは文献[９]（D.R.Kaeli  and  P.G.Emma.“Branch  History  Table  Prediction  of  Moving  Target  Branches  Due  to  Subroutine  Returns”,In  Proceedings  of  18th  International  Symposium  of  Computer  Architecture,pages  34~42,1991.）、文献[１０]（K.Skadron,P.S.Ahuja,M.Martonosi,  and  D.  W.Clark.“Improving  Prediction  for  Procedure  Return  with  Return-Address-Stack  Repair  Mechanisms”,In  Proceedings  of  31st  International  Symposium  on  Microarchitecture,pages  259~271,1998.）などの研究結果がある。
【００４８】
（ハードウェアによるインタプリタ支援）
インタプリタを高速に実行するための仕組みとして、計算機上にハードウェア的な支援機構を設ける場合もある。このような例の1つがMIPS社によるSmartMIPS(R)（文献[１１]（MIPS  Technologies  Inc.“MIPS32(R)  Architecture  for  Programmers  Volume  IV-d:  The  SmartMIPS(R)  Application-Specific  Extension  to  the  MIPS32(R)  Architecture”,Document  Number:  MD00101  Revision  2.50,July  1,2005.））である。
【００４９】
これはMIPS32(R)アーキテクチャ向けの拡張仕様の１つで、組み込み分野をターゲットとした仕様になっている。この拡張は大きく分けて、暗号向け演算アクセラレータ、命令密度の最適化、インタプリタ支援、そしてリソース保護の４本柱になっている。このうちインタプリタ支援については文献[１１]の３．４．３節で概要が触れられ、具体的な命令についての説明は５．１節に記述されている。
【００５０】
この拡張では、インタプリタの最内ループ処理を可能な限り少ない命令数で実現できるようにＣＩＳＣ的な命令が定義されている。ＣＩＳＣとは、スーパースカラ登場以前に主流だった計算機の方式で、現在主流のＲＩＳＣ（Reduced  Instruction  Set  Computers）とは対照的に１つ１つの命令が高機能である（Complex  Instruction  Setである）事が特徴となっている。ＣＩＳＣとＲＩＳＣについては文献[１]の２．１６節内に「Reduced  Instruction  Set  Computers」と題されて解説されている。
【００５１】
（Just  In  Timeコンパイル方式）
インタプリタを高速に実装するためのソフトウェア側の工夫としてJust  In  Timeコンパイル方式と呼ばれる技術が存在する。この方式ではまずインタプリタとしての動作でプログラムを解釈・実行し、それと同時にプログラムの動作について簡単な統計情報を作成する。この統計情報によりHot  Spot（頻繁に実行される箇所）と判断されたプログラム部分に関しては、その時点でプログラムの解釈をまとめて行い、計算機上で直接実行可能な命令列に変換する。
【００５２】
以降、その命令に該当する箇所に実行がさしかかると、インタプリタによる動作をやめ、変換後の直接実行可能な命令列に制御を移す。この方式は、インタプリタ方式とコンパイラ方式の折衷方式と考えることができ、コンパイルにかかる時間的なコストと、直接実行される事による高速化の効果を比較し、効果の方が十分大きい場合に限って用いる事が可能な技術と言える。また、高速化の効果はコンパイル時にどれだけ複雑な最適化を行うかにも影響しており、多くの面でトレード・オフが存在する。また、計算機の性能や広大なメモリを要求するため、この方式は一般的に大規模なシステム上で利用される事が多い。
【００５３】
続いて、本実施例１の説明を行う。まず、本実施例１にかかるプロセッサの概要および特徴について説明する。本実施例１にかかるインタプリタは、ソースプログラムを逐次実行する場合に、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を実行するように実装されている。
【００５４】
このように、本実施例１にかかるインタプリタは、ソースプログラムを実行する場合に、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を実行するので、インタプリタを実行しているプロセッサは、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。
【００５５】
なお、本実施例１では、インタプリタを用いて説明するが、これに限定されるものではなく、その他のプログラムによって代用することができる。
【００５６】
次に、間接分岐命令と、間接分岐命令の代わりとなる擬似的な間接分岐命令とを比較して説明する。図７は、間接分岐命令を用いるインタプリタの一例を示す図であり、図８は、擬似的な間接命令を用いるインタプリタの一例を示す図である。
【００５７】
図７において、「call  %r6」が間接分岐命令に対応する。具体的に、「call  %r6」の処理内容は、プログラムカウンタに格納されたアドレスをリンクレジスタに格納した後に、プロセッサに搭載された汎用レジスタ「r6」に格納された分岐先のアドレスに処理を移行するという内容である。レジスタ「r6」に記憶されるアドレスに応じて分岐先がかわるため間接分岐命令となる。かかる間接分岐命令では、汎用レジスタに格納される分岐先のアドレスが多岐にわたるため、分岐命令の次に実行すべき命令を精度よく実行することができなかった。
【００５８】
一方、図８の「move  %link_reg=%r6」および「ret」が擬似的な間接分岐命令に対応する。すなわち、本実施例１のインタプリタは、図７に示したような間接分岐命令「call  %r6」を用いる必要がある場合であっても、かかる間接分岐命令を用いる代わりに、図８に示したような擬似的な間接分岐命令「move  %link_reg=%r6」、「ret」を用いる。
【００５９】
図８に示す「move  %link_reg=%r6」の処理内容は、プロセッサに搭載された、分岐元のアドレスを格納するレジスタ（以下、リンクレジスタ）に汎用レジスタ「r6」に格納された分岐先のアドレスを移動させるという内容である。つづく「ret」は、リンクレジスタに格納された分岐元に復帰するための命令であるが、本実施例においては、分岐先のアドレスが格納されているため、分岐先のアドレスに処理を移行する。
【００６０】
ここで、リンクレジスタにアドレスを格納するたびに、プロセッサに搭載されたリターン・アドレス・スタック（リターン・アドレス・スタックに関する説明は上記の内容を参照）にアドレスが順に積まれていく。プロセッサは、リンク付き分岐命令を実行した後の復帰時にリターン・アドレス・スタックに積まれた分岐先のアドレスを抽出する（新しく積まれた順にアドレスを抽出する）ことによって、精度よく復帰先のアドレスを予測することができる。
【００６１】
次に、本実施例１にかかるプロセッサの構成（構成の一例）について説明する。図９は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ１００は、メモリアクセス制御部１１０と、レジスタ１２０と、リターン・アドレス・スタック１３０と、分岐予測部１４０と、デコード・制御部１５０と、演算パイプライン部１６０とを備えて構成される。
【００６２】
また、プロセッサ１００は、各種のデータおよびプログラムを記憶するメインメモリ２００に接続され、メインメモリ２００に記憶された各種データ・プログラムを読み出して各種の処理を逐次実行する。
【００６３】
メインメモリ２００は、各種のデータおよびプログラムを記憶する記憶装置であり、特に本発明に密接に関連するものとしては、インタプリタプログラム２００ａ、ソースプログラム２００ｂ、退避データ２００ｃを記憶している。
【００６４】
このうち、インタプリタプログラム２００ａは、ソースプログラム２００ｂを逐次読み出して実行するためのプログラムである。プロセッサ１００は、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出してインタプリタを起動することにより、ソースプログラム２００ｂを逐次実行することとなる。また、インタプリタは、ソースプログラム２００ｂを逐次実行する過程において、間接分岐を行う必要がある場合でも、間接分岐命令の代わりに、擬似的な間接分岐命令を用いるように実装されている。
【００６５】
例えば、プロセッサ１００により起動されたインタプリタは、ソースプログラム２００ｂを実行する場合に、間接分岐命令「call  %rN（Nは０以上の整数）」（図７参照）が必要となった場合にでも、かかる間接分岐命令を用いず、擬似的な間接分岐命令「move  %link_reg=%rN」、「ret」（図８参照）で代用するように実装されている。
【００６６】
続いて、プロセッサ１００の構成の説明に移ると、メモリアクセス制御部１１０は、メインメモリ２００との間で行われるデータの入出力を制御する処理部である。レジスタ１２０は、各種のデータを記憶する記憶装置であり、特に本発明に密接に関連するものとしては、汎用レジスタ群１２０ａ、プログラムカウンタ１２０ｂ、リンクレジスタ１２０ｃを備える。
【００６７】
このうち、汎用レジスタ群１２０ａは、各種プログラム（インタプリタプログラム２００ａ等）を実行する場合に利用されるデータ、分岐先のアドレス等を格納するレジスタ群である。図９に示す例では、汎用レジスタ群は、汎用レジスタr0〜rN（Nは整数）を含んでいる。
【００６８】
プログラムカウンタ１２０ｂは、次に実行する命令が格納されたアドレスを格納するレジスタであり、リンクレジスタ１２０ｃは、分岐元のアドレスを格納するレジスタである。なお、リンクレジスタ１２０ｃは、メインメモリ２００と協働して、擬似的なスタックを構成する事が可能である。例えば、リンクレジスタ１２０ｃにアドレスＡが格納されている状態で、新たにアドレスＢをリンクレジスタ１２０ｃに格納する場合には、アドレスＡがメインメモリ２００の退避データ２００ｃに退避される。すなわち、リンクレジスタ１２０ｃは新たなアドレスを格納するたびに、退避データ２００ｃにアドレスを退避させる。
【００６９】
また、リンクレジスタ１２０ｃにアドレスＢが格納され、メインメモリ２００の退避データ２００ｃにアドレスＡが退避されている状態で、リンクレジスタ１２０ｃのアドレスＡが取り出された場合に、退避データ２００ｃに退避していたアドレスＢをリンクレジスタ１２０ｃに戻す処理を行う。すなわち、リンクレジスタ１２０ｃに格納されたアドレスが取り出されるたびに、退避されたアドレスがリンクレジスタ１２０ｃに戻される（新しく退避データに退避された順番で、アドレスがリンクレジスタ１２０ｃに戻される）。
【００７０】
リターン・アドレス・スタック１３０は、リンクレジスタ１２０ｃに分岐元となるアドレスが格納されるたびに、リンクレジスタ１２０ｃに格納されたアドレスと等しいアドレスを順番に格納するレジスタである。例えば、リンクレジスタ１２０ｃにアドレスＡ、アドレスＢ、アドレスＣ・・・の順番でアドレスが格納された場合には、リターン・アドレス・スタック１３０は、アドレスＡ、アドレスＢ、アドレスＣ・・・の順番で、アドレスを記憶する。ただし、メインメモリ２００から読み出した値をリンクレジスタ１２０ｃに格納した場合には、リターン・アドレス・スタック１３０の更新は行わない。なぜなら、メインメモリ２００からの読み出しは、退避していた分岐元アドレスをリンクレジスタ１２０ｃに戻す処理であり、ここでリターン・アドレス・スタック１３０を更新した場合は、格納と抽出の対応が取れなくなるためである。
【００７１】
リターン・スタック・アドレス１３０に記憶された各アドレスは、サブルーチン移行後の復帰命令時に、新しく格納したアドレスから順番に分岐予測部１４０に抽出され分岐予測が行われる。
【００７２】
分岐予測部１４０は、リターン・アドレス・スタック１３０に記憶された分岐先のアドレスを読み出して、復帰命令時による分岐予測を行う装置である。具体的に、分岐予測部１４０は、リターン・アドレス・スタック１３０に記憶された分岐先のアドレスを、新しく格納された順番で抽出し、抽出した分岐先のアドレスを復帰命令時の分岐先のアドレスとして判定する。
【００７３】
デコード・制御部１５０は、分岐予測部１４０から分岐予測結果を取得し、メインメモリ２００に記憶された命令を、メモリアクセス制御部１１０、レジスタ１２０を経由して順次読み出し、実行すべき処理を判定し、判定結果となる制御命令を演算パイプライン部１６０に出力して各種演算を実行させる装置である。また、演算パイプライン部１６０は、デコード・制御部１５０から制御命令を取得し、スーパースカラ方式によって複数の処理を並列して実行する演算装置である。デコード・制御部１５０は、メインメモリ２００から取得した命令が復帰命令の時に、リターン・アドレス・スタック１３０から戻りアドレスを降ろして分岐予測を行い、予測に従って次に実行すべき命令をメインメモリ２００から読み出す。また、演算パイプライン部１６０へ復帰命令を処理する制御命令を送る。演算パイプライン部１６０は、デコード制御部１５０から制御命令を取得し、復帰命令、すなわちリンクレジスタ１２０ｃに格納されたアドレスを読み出し、そのアドレスが次に取得・解釈すべき命令のアドレスであると、デコード・制御部１５０に通達する。
【００７４】
図８に示した擬似的な間接分岐を構成する命令、move命令とret命令との間に十分多くの命令を挿入することができれば、リンクレジスタ１２０に書き込まれた値がリターン・アドレス・スタック１３０に積まれることになり、復帰命令を実施する際に復帰先を正しく予想することができる。
【００７５】
上述してきたように、本実施例１にかかるプロセッサ１００は、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出してインタプリタを起動し、インタプリタプログラム２００ａがソースプログラム２００ｂを実行する場合において、間接分岐命令が必要な状況であっても、間接分岐命令の代わりに擬似的な間接分岐命令を用いて分岐先のアドレスをリンクレジスタ１２０ｃに格納するようにインタプリタプログラム２００ａが実装されているので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。
【実施例２】
【００７６】
上述した実施例１では、インタプリタが、単一の間接分岐命令の代わりに、擬似的な間接分岐命令を用いる場合を例にあげて説明したが、本実施例２では、複数の間接分岐命令が必要な場合に、かかる複数の間接分岐命令の代わりに擬似的な間接分岐命令を実行する場合について説明する。なお、実施例２にかかるプロセッサおよびメインメモリの構成は、実施例１に示したプロセッサ１００およびメインメモリ２００と同様であるので、適宜、図９を用いて実施例２の説明を行う。
【００７７】
まず、複数の間接分岐命令を実行するインタプリタを例示する。図１０は、複数の間接分岐命令を実行するインタプリタの一例を示す図である。図１０に示す各種命令を順に説明する。「move  %r6=Func_a」によって、関数「Func_a」を開始するアドレスが汎用レジスタ「r6」に格納され、「move  %r7=Func_b」によって、関数「Func_b」を開始するアドレスが汎用レジスタ「r7」に格納される。
【００７８】
そして、「call  %r6」によって汎用レジスタ「r6」に格納されたアドレスに処理が移行して関数「Func_a」が実行され、「call  %r7」によって汎用レジスタ「r7」に格納されたアドレスに処理が移行して関数「Func_b」が移行される。なお、図１０に示す「Func_a:」〜「ret」は、関数「Func_a」のコードであり、「Func_b:」〜「ret」は、関数「Func_b」のコードである。
【００７９】
ここで、図１０に示した「call  %r6」と等価の処理を説明する。図１１は、図１０に示した「call  %r6」と等価のプログラムを示す図である。同図に示すように、「call  %r6」と等価のプログラムが「move  %link_reg=%pc」、「jump  %r6」となる。
【００８０】
ここで、「move  %link_reg=%pc」は、プログラムカウンタ１２０ｂに格納されたアドレスをリンクレジスタ１２０ｃに格納する命令を示している（プログラムカウンタ１２０ｂおよびリンクレジスタ１２０ｃは図９を参照）。そして、「jump  %r6」によって汎用レジスタ「r6」に格納されたアドレス（図１０の場合では、関数「Funk_a」のアドレス）に移行する命令となる。すなわち、call命令は、リンク処理と間接分岐処理を同時に行う、リンク付き間接分岐命令である。
【００８１】
本実施例２のインタプリタは、図１０、図１１に示したような複数の間接分岐命令の代わりに擬似的な間接分岐命令を実行する。図１２は、複数の擬似的な間接分岐命令を実行するインタプリタの一例を示す図である。
【００８２】
図１２において、「move  %r6=Func_a」によって、関数「Func_a」を開始するアドレスが汎用レジスタ「r6」に格納され、「move  %r7=Func_b」によって、関数「Func_b」を開始するアドレスが汎用レジスタ「r7」に格納される。
【００８３】
そして、「move  %link_reg=%r7」によって、汎用レジスタ「r7」に格納されたアドレスがリンクレジスタ１２０ｃに格納され、「store  (%r1)=%link_reg」によって、リンクレジスタ１２０ｃに格納されたアドレスが、メインメモリ２００の所定領域に退避される。
【００８４】
ここで、「move  %link_reg=%r7」は、図１０に示した間接分岐命令「call  %r7」に代わる擬似的な間接分岐のための前処理となる。プロセッサ１００は、「move  %link_reg=%r7」を実行してリンクレジスタ１２０ｃに汎用レジスタ「r7」に格納されたアドレスを書き込むことによって、プロセッサ１００内部では、復帰先アドレスとして汎用レジスタ「r7」で指定されたアドレスをリターン・アドレス・スタック１３０に記憶する。これは、プロセッサ１００の内部で利用するための挙動で、外部には非公開の挙動である。
【００８５】
続いて、「move  %link_reg=%r6」によって、汎用レジスタ「%r6」に格納されたアドレスがリンクレジスタ１２０ｃに格納される。なお、関数「Func_a」を実行するバイナリコードには、末尾に「load  %link_reg=(%r1)」、「ret」が含まれ、「load  %link_reg=(%r1)」によってメインメモリ２００の所定領域に退避していたアドレスをリンクレジスタ１２０ｃに格納し、「ret」によって処理が元の関数に戻される。なお、「Func_b:」〜「ret」は、関数「Func_b」のコードであり、「Func_a:」〜「ret」と同様の各種コードが含まれる。
【００８６】
「store  (%r1)=%link_reg」を実行することで、リンクレジスタ１２０ｃに書き込まれたアドレスを即座にメインメモリ２００に退避し、「move  %link_reg=%r6」を実行することで、汎用レジスタ「r6」で指定されたアドレスをリンクレジスタ１２０ｃに格納している。
【００８７】
上記命令をプロセッサが実行することによって、リンクレジスタ１２０ｃに格納されていたアドレスが上書きされてしまうことになるが、リターン・アドレス・スタック１３０は、その名の通り、スタックとしての構造を持っており、復帰先のアドレスが上書きされるわけではなく、直近の復帰先が汎用レジスタ「r6」に格納されていたアドレスとなり、その次の復帰先が汎用レジスタ「r7」に格納されていたアドレスとなる。
【００８８】
その後、復帰命令により現在のリンクレジスタ１２０ｃの値（汎用レジスタr6の値に対応）で指定された命令アドレスに処理を移す。これが復帰命令により擬似的に間接分岐を行っている部分である。続いて、その関数の最後において、退避したアドレスを再度リンクレジスタ１２０ｃに取り戻して復帰命令を実行している。
【００８９】
ここでリンクレジスタ１２０ｃに値を取り戻したのは、リターン・アドレス・スタック１３０に積まれたアドレスが、あくまでも分岐予測のための情報でしかないためである。仮にリンクレジスタ１２０ｃの値を元に戻さずに復帰してしまえば、再び現在のリンクレジスタ１２０ｃの値、つまり「Func_a」の先頭に処理は移動し、同時に分岐予測も外れる。２つ目の分岐アドレスがリンクレジスタ１２０ｃに格納されるのは呼び出し（＝復帰）の直前なのだが、リターン・アドレス・スタック１３０への積載は「Func_a」呼び出し以前にまとめて行われているため、結果としてはリターン・アドレス・スタック１３０を用いた分岐予測はデコード・制御部１５０による命令の取得に間に合い、ヒットする事になる。
【００９０】
ところで、プロセッサ１００は、インタプリタプログラム２００ａを読み出して、インタプリタを起動し、インタプリタがソースプログラム２００ｂを実行する場合に、複数の間接分岐命令（図１０、図１１を参照）の代わりに、擬似的な間接分岐命令（図１２を参照）を用いる。すなわち、プロセッサ１００は、間接分岐を行うことなく各命令を実行することができる。
【００９１】
具体的に、プロセッサ１００が、インタプリタを起動した場合には、本実施例のインタプリタは、ソースプログラム２００ｂを実行する上で必要となる複数の間接分岐命令（例えば、call命令など）を逆順に抽出し（図１０に示す例では、「call  %r7」、「call  %r6」の順番で抽出し）、抽出した間接分岐命令に対応する分岐先のアドレスを逆順に（図１０に示す例では、「Func_bのアドレス」、「Func_aのアドレス」の順番）、リンクレジスタ１２０ｃに格納するような擬似的な間接分岐命令のための前処理を実行するように実装されている。
【００９２】
なお、間接分岐命令の置き替えに関して、事前処理をどこまでまとめて行えるかは、ソースプログラム中の分岐を伴う制御文（条件文、Switch文、仮想関数呼び出しなど）単位となる。
【００９３】
次に、本実施例２にかかるプロセッサ１００が、メインメモリ２００に記憶されたインタプリタプログラム２００ａを読み出して起動するインタプリタの処理手順について説明する。図１３、図１４は、インタプリタの処理手順を示すフローチャートである。
【００９４】
同図に示すように、インタプリタは、「プログラム読込開始位置」としてプログラム（ソースプログラム）の先頭位置を設定し（ステップＳ１０１）、「プログラム読込開始位置」に「プログラム読込現在位置」を設定し（ステップＳ１０２）、「プログラム読込現在位置」から１処理分のプログラムを読み込み、解釈する（ステップＳ１０３）。
【００９５】
そして、インタプリタは、「プログラム読込現在位置」を１処理分だけ先に進め（ステップＳ１０４）、解釈した命令が分岐処理であるか否かを判定する（ステップＳ１０５）。解釈した命令が分岐命令でない場合には（ステップＳ１０６，Ｎｏ）、ステップＳ１０３に移行する。
【００９６】
一方、解釈した命令が分岐命令である場合には（ステップＳ１０６，Ｙｅｓ）、「プログラム読込停止位置」に「プログラム読込現在位置」を設定し（ステップＳ１０７）、リンクレジスタ１２０ｃに格納されたアドレスをメインメモリ２００上のスタックに退避し（ステップＳ１０８）、「プログラム読込現在位置」から１処理分のプログラムを読み込み、解釈する（ステップＳ１０９）。
【００９７】
続いて、解釈した命令に対応する処理を行うインタプリタ上の関数を調べ（ステップＳ１１０）、求めた関数のアドレスをリンクレジスタ１２０ｃに格納し（ステップＳ１１１）、「プログラム読込現在位置」を１処理分だけ後ろに戻す（ステップＳ１１２）。
【００９８】
そして、インタプリタは、「プログラム読込現在位置」と「プログラム読込開始位置」とが等しいか否かを判定し（ステップＳ１１３）、等しくない場合には（ステップＳ１１４，Ｎｏ）、ステップＳ１０８に移行する。
【００９９】
一方、「プログラム読込現在位置」と「プログラム読込開始位置」とが等しい場合には（ステップＳ１１４，Ｙｅｓ）、「ret」命令を実行し、リンクレジスタ１２０ｃに格納された関数へ分岐する（ステップＳ１１５）。
【０１００】
そして、インタプリタは、分岐先の関数で、プログラム中の１処理に対応した処理を行い（ステップＳ１１６）、分岐処理を行う関数か否かを判定し（ステップＳ１１７）、分岐処理を行なわない場合には（ステップＳ１１８，Ｎｏ）、分岐先の関数末尾で、メインメモリ２００上のスタックに退避したリンクレジスタ１２０ｃの値を１つリンクレジスタに取り出し（ステップＳ１１９）、ステップＳ１１５に移行する。
【０１０１】
一方、分岐処理を行う関数である場合には（ステップＳ１１８，Ｙｅｓ）、分岐処理に対応する関数を実行し（ステップＳ１２０）、「プログラム読込開始位置」として「プログラム実行停止位置」から１処理分だけ先に進めた位置を設定し（ステップＳ１２１）、ステップＳ１０２に移行する。
【０１０２】
このように、インタプリタが、間接分岐命令の代わりに擬似的な間接分岐を実行するように実装されているので、インタプリタによって最も頻繁に実行されるループの高速化が期待され、間接分岐命令単体だけではなく、プログラム全体としても大きな性能向上を見込める。
【０１０３】
上述してきたように、本実施例２にかかるプロセッサ１００は、インタプリタプログラム２００ａを読み出してインタプリタを起動し、ソースプログラム２００ｂを実行する上で必要となる間接分岐命令の代わりに、間接分岐命令の分岐先のアドレスを逆順にリンクレジスタ１２０ｃに格納し、復帰命令によって分岐するといった擬似的な間接分岐命令を利用する（プロセッサ１００は、内部的に、リンクレジスタ１２０ｃに格納された値を、自動的にリターン・アドレス・スタック１３０に積む）ので、分岐予測を精度よく行うことができ、分岐によるペナルティなしに任意のアドレスへの分岐を完了することができる。結果、間接分岐命令に相当する処理を数倍〜数十倍高速に実行することができる。また、分岐先アドレスをまとめてリンクレジスタ１２０ｃに登録することで、実際の分岐処理に十分に先立って、分岐先アドレスをリンクレジスタ１２０ｃに登録しており、復帰命令により疑似的な間接分岐が実行される時までに、プロセッサ１００によって、リンクレジスタ１２０ｃに登録されたデータをリターン・アドレス・スタック１３０に登録する作業が完了しており、分岐予測が間に合う（＝予測がヒットする）。
【０１０４】
なお、上述の実施例１および実施例２では、インタプリタが間接分岐命令を実行する代わりに擬似的な間接分岐命令を用いる場合を例にあげて説明したが、かかる実行方式を仮想マシンに適用することも可能である。すなわち、仮想マシン（Ｊａｖａ（登録商標）等）がバイナリを実行する際に、間接分岐命令が必要となっても、かかる間接分岐命令の代わりに擬似的な間接分岐命令を実行して、プロセッサ１００に分岐先となるアドレスをリターン・アドレス・スタック１３０に格納させ、分岐予測を成功させることができる。
【実施例３】
【０１０５】
上述した実施例１、２では、インタプリタがソースプログラムを逐次実行する場合において、間接分岐命令の代わりに擬似的な間接分岐命令を利用していたが、コンパイラによって、間接分岐命令の代わりに疑似的な間接分岐命令を利用するコードを生成することも可能である。
【０１０６】
すなわち、コンパイラによってソースプログラムをコンパイルし、間接分岐命令の代わりに擬似的な間接分岐命令を含んだプログラム（以下、擬似間接分岐プログラムと表記する）を生成し、プロセッサが、かかる擬似間接分岐プログラムを実行することによって、間接分岐命令に相当する処理を高速化することができる。
【０１０７】
次に、本実施例３にかかるプロセッサの構成について説明する。図１５は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。同図に示すように、このプロセッサ３００は、メインメモリ４００に接続され、メモリアクセス制御部３１０と、レジスタ３２０と、リターン・アドレス・スタック３３０と、分岐予測部３４０と、デコード・制御部３５０と、演算パイプライン部３６０とを備えて構成される。
【０１０８】
ここで、メモリアクセス制御部３１０、レジスタ３２０、リターン・アドレス・スタック３３０、分岐予測部３４０、デコード・制御部３５０、演算パイプライン部３６０は、図９において説明したメモリアクセス制御部１１０、レジスタ１２０、リターン・アドレス・スタック１３０、分岐予測部１４０、デコード・制御部１５０、演算パイプライン部１６０に対応するため、説明を省略する。
【０１０９】
また、メインメモリ４００は、各種のデータおよびプログラムを記憶する記憶装置であり、コンパイラプログラム４００ａと、ソースプログラム４００ｂと、擬似間接分岐プログラム４００ｃと、退避データ４００ｄとを記憶する。
【０１１０】
このうち、コンパイラプログラム４００ａは、プロセッサ３００が実行可能な、コンパイルを行うためのプログラムである。プロセッサ３００が、コンパイラを起動することによって、ソースプログラム４００ｂをコンパイルし、擬似間接分岐プログラム４００ｃを生成する。
【０１１１】
コンパイラを起動したプロセッサ３００は、ソースプログラム４００ｂをコンパイルする過程において、ソースプログラム４００ｂの命令を間接分岐命令（図７、図１０参照）に変換する必要がある場合に、かかる間接分岐命令の代わりに擬似的な間接分岐命令に変換する（図８、図１２参照）。すなわち、従来では、図７のようにソースプログラム４００ｂをコンパイルしていたものを、図８のようにコンパイルする。あるいは、図１０のようにソースプログラム４００ｂをコンパイルしていたものを、図１２のようにコンパイルする。
【０１１２】
プロセッサ３００は、コンパイラによって擬似間接分岐プログラム４００ｃを生成した後に、擬似間接分岐プログラム４００ｃを読み出して、擬似間接分岐プログラム４００ｃに応じた処理を実行する。この擬似間接分岐プログラム４００ｃには、間接分岐命令の代わりに擬似的な間接分岐命令が含まれているので、間接分岐命令に相当する処理を高速化することができる。
【０１１３】
上述してきたように、本実施例３にかかるプロセッサ３００は、コンパイラを起動してソースプログラム４００ｂをコンパイルし、間接分岐命令の代わりに擬似的な間接分岐命令を含んだ擬似間接分岐プログラム４００ｃを生成し、プロセッサ３００が、かかる擬似間接分岐プログラム４００ｃを実行するので、間接分岐命令に相当する処理を高速化することができる。
【０１１４】
なお、本実施例３では、プロセッサ３００がコンパイラを起動して、ソースプログラム４００ｂから擬似間接分岐プログラム４００ｃを作成していたが、これに限定されるものではなく、コンパイルを専用に実行するコンパイラ装置によって、ソースプログラム４００ｂをコンパイルし、間接分岐命令の代わりに擬似間接分岐命令を含んだ擬似間接分岐プログラム４００ｃを生成し、かかる擬似間接分岐プログラム４００ｃをプロセッサ３００、あるいはプロセッサ１００が実行するようにしても構わない。
【０１１５】
ところで、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部あるいは一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１１６】
また、図９および図１５に示したプロセッサ１００，３００の構成は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１１７】
また、図９および図１５のメモリ２００，４００に記憶された各種プログラム（インタプリタプログラム２００ａ、ソースプログラム２００ｂ，４００ｂ、コンパイラプログラム４００ａ、擬似間接分岐プログラム４００ｃ）は、必ずしも最初からメインメモリ２００，４００に記憶させておく必要はない。たとえば、コンピュータに挿入されるフロッピー（登録商標）ディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータの内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータに接続される「他のコンピュータ（またはサーバ）」などに各種プログラムを記憶しておき、コンピュータ（プロセッサ）がこれらから各種プログラムを読み出して実行するようにしてもよい。
【０１１８】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、特許請求の範囲に記載した技術的思想の範囲内において種々の異なる実施例にて実施されてもよいものである。
【産業上の利用可能性】
【０１１９】
上述したように、本発明は、現在広く利用されているインタプリタ等に対して、高速な実装方法を提供する物である。この手法は、現在利用されている計算機上で実現可能であり、また実装にかかるコストも大きくはない。また、産業上大きなインパクトを持つＪａｖａ（商標登録）をはじめとする仮想マシンに対しても有効な最適化手法であるため、実用上の価値も高い。また、インタプリタを作り直すだけで、その上で動いていた全てのプログラムが高速に動作するようになる点も評価できる。
【図面の簡単な説明】
【０１２０】
【図１】図１は、分岐処理を説明するための図である。
【図２】図２は、複数の分岐処理と間接分岐処理とを説明するための図である。
【図３】図３は、コンパイル方式とインタプリタ方式との違いを説明するための図である。
【図４】図４は、従来のインタプリタの処理を示すフローチャートである。
【図５】図５は、パイプライン処理を説明するための図である。
【図６】図６は、関数呼び出しの様子を説明するための図である。
【図７】図７は、間接分岐命令を用いるインタプリタの一例を示す図である。
【図８】図８は、擬似的な間接命令を用いるインタプリタの一例を示す図である。
【図９】図９は、本実施例１にかかるプロセッサの構成を示す機能ブロック図である。
【図１０】図１０は、複数の間接分岐命令を実行するインタプリタの一例を示す図である。
【図１１】図１１は、図１０に示した「call  %r6」と等価のプログラムを示す図である。
【図１２】図１２は、複数の擬似的な間接分岐命令を実行するインタプリタの一例を示す図である。
【図１３】図１３は、インタプリタの処理手順を示すフローチャート（１）である
【図１４】図１４は、インタプリタの処理手順を示すフローチャート（２）である。
【図１５】図１５は、本実施例３にかかるプロセッサの構成を示す機能ブロック図である。
【符号の説明】
【０１２１】
１００，３００    プロセッサ
１１０，３１０    メモリアクセス制御部
１２０，３２０    レジスタ
１２０ａ，３２０ａ  汎用レジスタ群
１２０ｂ，３２０ｂ  プログラムカウンタ
１２０ｃ，３２０ｃ  リンクレジスタ
１３０，３３０    リターン・アドレス・スタック
１４０，３４０    分岐予測部
１５０，３５０    デコード・制御部
１６０，３６０    演算パイプライン部
２００，４００    メインメモリ
２００ａ  インタプリタプログラム
２００ｂ，４００ｂ  ソースプログラム
４００ｃ  擬似間接分岐プログラム
２００ｃ，４００ｄ  退避データ
４００ａ  コンパイラプログラム
【国際調査報告】
2009004709.tif 000018
2009004709.tif 000019
2009004709.tif 000020
2009004709.tif 000021
2009004709.tif 000022
2009004709.tif 000023