JP5602599B2 - ループ検知装置、ループ検知方法及びループ検知プログラム - Google Patents

Description

本発明は、トレーシング技術に関し、特に、トレースを生成するためにループを検出するための技術に関する。

近年、動的コンパイルやバイナリ変換を行う処理系において、トレーシング技術が重要視されている（例えば、非特許文献１及び２参照）。トレーシング技術とは、プログラムの実行時に繰り返し通過するコードパスを抽出し、その軌跡、即ち、トレースを記録しコンパイルして、高速なコードを生成する手法である。トレーシング技術によれば、実際に実行されるコードだけが最適化されるので、関数（又は、メソッド、又はプロシージャ、以下同様）を単位とした従来のコンパイル手法のように、実際には使用されないコードまで最適化するといった問題や、関数間に渡る最適化が行えない又は多段に及ぶ場合などは難しいといった問題が解決又は軽減できる。

トレース単位でコンパイルを行う方法は様々あるが、最も基本的な方法は次のような手順で行われる。まず、ソースコードをバイトコード等の中間コードに変更する。次にインタプリタによって中間コードを実行し、その実行を監視する。後方分岐を検出すると、その分岐先をループ始点候補として記録する。これは、ループ処理は必ず後方分岐を伴うからであるが、後方分岐の分岐先以外の条件でもループ始点候補は作成される得る。そして、ループ始点候補から始まるコードパスが所定の回数以上繰り返し実行されることを検出すると、実行された中間コード（トレース）を記録し、記録したトレースを最適化してコンパイルし、ネイティブ・コードを生成する。

生成されたネイティブ・コードは、元となったトレースと同じパスが選択される限り、システムによって直接実行される。しかし、条件分岐の結果が異なる等、前提条件が成立しなくなると、制御はインタプリタに戻されるか、別のトレースから生成されたネイティブ・コードへと移される。このインタプリタとの切り替え、あるいは別トレースへの遷移のコストは高く、ランタイム・オーバヘッドの原因となる。そのため、インタプリタとの切り替えあるいは別トレースへの遷移を頻繁に生じさせないように、ループを正しく検出しトレースを生成することが重要となる。

非特許文献３は、命令列の先頭の命令と末尾の命令のアドレスが同じであることを条件に、その命令列をループであると判断する技術を開示する。

非特許文献４及び非特許文献５は、トレースの先頭の命令が属するメソッドからのリターン命令を含むトレースの生成を禁止する技術を開示する。

なお、以下に記載する特許文献１は、コールスタックのプッシュ／ポップをエミュレーションして各命令時点でのコールスタックを構築するコールスタック構築技術を開示する従来技術として挙げたものである。

米国特許第６７５１７８９号明細書

Vasanth Bala et al., "Dynamo: A Transparent Dynamic OptimizationSystem", ACM SIGPLAN Notices,Volume 35, p.1-12, May 2000. Andreas Gal et al., "Trace-based just-in-time type specialization for dynamic languages". In Programming Lan-guages Designand Implementation, p.1-11, ACM, 2009. David Hinikeret al., "Improving RegionSelection in Dynamic Optimization Systems", Proceedings of the 38th annual IEEE/ACM International Symposiumon Microarchitecture, p.141-154, November 12-16, 2005. Andreas Gal et al., "IncrementalDynamic Code Generation with Trace Trees", Technical Report, p.6-16, Donald Bren School of Information and ComputerScience, University of California, Irvine, November 2006. Duane Merrill et al., "TraceFragment Selection within Method-based JVMs", InProceedings of the International Conference on Virtual Execution Environments, ACM Press, p.41–50.

しかしながら、非特許文献３が開示するループ検知手法によると、本来ループでないものを誤ってループと判定してしまう場合が生じる。例として、図１０（ｂ）に示すコードにおいて、３行目の関数ｇの呼び出しにより実行される命令Ｇから実行命令の記録が始まる場合を考える。すると命令列Ｇ−Ｂ−Ｇが記録されるが、命令列Ｇ−Ｂ−Ｇの先頭Ｇのアドレスと、末尾のＧのアドレスは等しいため、命令列Ｇ−Ｂ−Ｇはループであると判定される。しかし実際には、命令Ｇの後は命令Ｃが実行されるため、命令列Ｇ−Ｂ−Ｇが繰り返し実行されることはなく、命令列Ｇ−Ｂ−Ｇは偽ループである。このように、アドレスの一致のみを条件としてループを判定する場合、偽ループを検出してしまうという問題がある。

一方、非特許文献４や５が開示する技術によれば、上述した命令列Ｇ−Ｂ−Ｇは、先頭の命令Ｇが属する関数ｇから、命令Ｂが属する関数ｆへのリターン命令を含むため、命令列Ｇ−Ｂ−Ｇをトレースとして生成することは禁止され、結果的に偽ループの検出を排除できる。しかしながら、上記非特許文献５の技術は、命令列Ｇ−Ｂ−Ｇを偽ループとして検知するものではないため、命令列Ｇ−Ｂ−Ｇはループであるとの判定に基づき、例えば、命令列Ａ−Ｇ−Ｂ−Ｇをトレースとして生成することを許してしまう。

また、命令列Ｇ−Ｂ−Ｇは偽ループであるが、実行命令の記録を続けることにより得られる命令列Ｇ−Ｂ−Ｇ−Ｃ−Ａ−Ｇは、繰り返し実行され得るため、真のループである。長いトレースの生成は、ランタイムのオーバーヘッドを減らすだけでなく、より効果的な最適化をもたらすので好ましい。しかし、非特許文献４や５が開示する技術によれば、命令列Ｇ−Ｂ−Ｇ−Ｃ−Ａ−Ｇは、先頭の命令Ｇが属する関数ｇから、命令Ｂが属する関数ｆへのリターン命令を含むため、命令列Ｇ−Ｂ−Ｇ−Ｃ−Ａ−Ｇをトレースとして生成することは禁止される。

そこで、この発明は、上記の問題点を解決するためになされたものであって、トレーシング技術において、偽ループの誤検知を排除し、また、長いトレースを含む真のループの検出ミスを防ぐことのできる、ループ検出技術を提供することを目的とする。

上記課題を解決するために、本発明の第１の態様においては、コンピュータの計算処理により、プログラムにおける各単位処理のうち連続して実行された単位処理の列がループであるか否かを判定するループ検知方法であって、前記コンピュータが、前記コンピュータの記憶部から前記単位処理の列についてアドレス情報を読み出して、前記単位処理の列内のループ始点候補の単位処理と末尾の単位処理の各々のアドレスを比較するステップと、前記コンピュータの記憶部から前記単位処理の列についてコールスタック情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックを比較するステップと、前記アドレス及び前記コールスタックの各比較結果が一致であることを条件に、前記単位処理の列がループをなすとの判定結果を出力するステップとを含む、ループ検知方法を提供する。

好ましくは、前記コールスタックの比較は、前記コールスタックを構成する各スタックフレーム内のリターンアドレスの比較である。

より好ましくは、前記各スタックフレーム内のリターンアドレスの比較は、最後に積まれたスタックフレームからｋ番目（ｋは所定の正の整数）のスタックフレームまでの各リターンアドレスの比較である。

更に好ましくは、前記単位処理の列内の各単位処理実行時のコールスタック内において最も浅いコールスタックの深さをｍ、前記ループ始点候補の単位処理の実行時におけるコールスタックの深さをｋ_１、及び前記末尾の単位処理の実行時におけるコールスタックの深さをｋ_２とした場合に、前記所定の正の整数ｋは、ｋ_１からｍを差し引いた値と、ｋ_２からｍを差し引いた値のうち小さい方の値として算出される。

また好ましくは、上記ループ検知方法は、前記コンピュータが、前記コンピュータの記憶部から前記単位処理の列について単位処理の種類情報及びアドレス情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックとを構築し、前記コールスタック情報として前記記憶部に記憶するステップを更に含む。

より好ましくは、前記単位処理の種類情報は、前記単位処理が、呼び出し側の単位処理、呼び出され側の単位処理、及びそれ以外のいずれであるかを示す情報である。

更に好ましくは、各コールスタックの構築は、前記単位処理の列について単位処理の種類情報及びアドレス情報を参照して、枝分かれしたリンクリストであって、該リンクリストの各ノードが、スタックフレームを表し、かつ、該スタックフレームのリターンアドレスと該スタックフレームの１つ前のスタックフレームを表すノードへの参照（リンク）とを記録するデータフィールドを有する、前記リンクリストを作成するステップとを含み、前記単位処理の列内の任意の単位処理の実行時のコールスタックは、該任意の単位処理に対応するスタックフレームを表すノードを出発点として前記参照に基づいて１つ前のスタックフレームのノードを順次辿っていき、辿った各ノードのリターンアドレスを繋げることにより構築される。

また好ましくは、前記単位処理は、１つの命令、基本ブロック、又は分岐命令である。

また好ましくは、上記ループ検知方法は、前記コンピュータが、前記単位処理の列内の各単位処理を前記ループ始点候補の単位処理として順次決定し、該決定ごとに各ステップを繰り返し実行するステップを更に含む。

また好ましくは、上記ループ検知方法は、前記コンピュータが、単位処理ごとに実行回数をカウントするステップと、前記実行回数が所定の値に達することを応答して、前記コンピュータの記憶部への前記単位処理の列の記録を開始するステップと、前記単位処理の列がループをなすとの判定の出力に応答して該判定に基づいて前記処理単位の列のトレースを生成し、最適化してコンパイルするステップとを実行するステップを更に含む。

以上、ループ検知方法として本発明を説明したが、本発明は、該ループ検知方法をコンピュータに実行させるループ検知プログラム、該ループ検知プログラムをインストールしたコンピュータにより実現されるループ検知装置として把握することもできる。

本発明によれば、連続して実行された単位処理の列がループであるか否かを判定するにあたり、単位処理の列内のループ始点候補の単位処理と末尾の単位処理のアドレスの一致を条件とするだけでなく、ループ始点候補と末尾の各単位処理の実行時におけるコールスタックの一致をも条件として追加するので、偽ループを誤検出を適切に排除しつつ、真のループの検出ミスを防ぐことが可能となる。本発明のその他の効果については、各実施の形態の記載から理解される。

（ａ）は、本発明に係るループ検知装置の１実装態様を示す図である。（ｂ）は、本発明に係るループ検知装置の他の実装態様を示す図である。 本発明の第１の実施形態に係るループ検知部２００の機能ブロック図である。 本発明の第１の実施形態に係るループ検知部２００によるコールスタック比較の一例を示す図である。 本発明の第１の実施形態に係るループ検知部２００により作成されるリンクリストを示す。 本発明の第１の実施形態に係るループ検知部２００によるループ検知処理の流れを示すフローチャートである。 本発明の第１の実施形態に係るループ検知部２００によるＴｏｐｋ算出処理の流れを示すフローチャートである。 本発明の第１の実施形態に係るループ検知部２００によるリンクリスト作成処理の流れを示すフローチャートである。 図５に示すコールスタック比較処理（Ｓ５１５）の流れを示すフローチャートである。 本発明の第２の実施形態に係るループ検知部９００の機能ブロック図である。 ループ判定結果を本発明（第２の実施形態）と従来技術とで比較した結果を示す表である。 本発明の第２の実施形態に係るループ検知部９００によるループ検知処理の流れを示すフローチャートである。 図１１に示すリターン命令判定処理（Ｓ１１１０）の流れの一例を示すフローチャートである。 図１１に示すリターン命令判定処理（Ｓ１１１０）の流れの他の例を示すフローチャートである。 図１に示すコンパイラ装置１００ａ（又はコンパイラ装置１００ｂ及びトレーシングエンジン１５０）による処理の流れの一例を示すフローチャートである。 ループ判定結果をもとに生成されるトレースの例を示す図である。 ループ判定結果を従来技術と本発明とで比較した結果を示す表である。 本発明の実施形態に係るコンピュータ５０のハードウェア構成の一例を示す。

以下、本発明を実施するための形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１（ａ）は、本発明に係るループ検知装置の１実装態様を示す図である。図１（ａ）に示す実装態様では、本発明に係るループ検知装置は、トレースベースのコンパイルを行うコンパイラ装置１００ａの一機能（ループ検知部１２０ａ）として実装される。コンパイラ装置１００ａは、記憶部１０５ａ（バッファ）と、実行命令記録部１１０ａと、ループ検知部１２０ａと、トレース生成部１３０ａと、最適化部１４０ａとを備え、プログラムの実行時に繰り返し通過するコードパス、即ちループを検知し、該ループ情報に基づいてトレースを生成し最適化して、高速なネイティブ・コードを生成する。コンパイラ装置１００ａは、オプションとして更に、コールスタック記録／構築部１１５ａを備えてもよい。

図１（ｂ）は、本発明に係るループ検知装置の他の実装態様を示す図である。図１（ｂ）に示す実装態様では、本発明に係るループ検知装置は、トレースベースのコンパイルを行うコンパイラ装置１００ｂに付随するトレーシングエンジン１５０の一機能（ループ検知部１２０ｂ）として実装される。本実施態様では、頻繁に実行される連続する単位処理の列の記録、また、オプションとしての単位処理の列の実行時のコールスタック情報の記録又は構築は、トレーシングエンジン１５０の機能であり、実行命令記録部１１０ｂと、オプションとしてのコールスタック記録／構築部１１５ｂは、トレーシングエンジン内に設けられる。更に本発明に係るループ検知装置は、図示はしないが、プロセッサ内でハードウェア実装することも可能である。このように実装態様に違いはあるが、それぞれの態様における各構成要素及びその機能は等しい。そこで以下では、図１（ａ）に示す実装態様に従って、各構成要素を説明する。

実行命令記録部１１０ａは、最適化対象のプログラム内の各単位処理が実行される頻度を監視し、頻繁に実行される連続する単位処理の列を記録する。具体的には、実行命令記録部１１０ａは最適化対象のプログラム内の単位処理ごとにその実行回数をカウントし、実行回数が所定の閾値に達することを応答して、その頻繁に実行される単位処理の列の記憶部１０５ａ（バッファ）への記録を開始する。記録開始後、実行命令記録部１１０ａは、記憶部１０５ａ（バッファ）内の単位処理の列について、後述するループ検知部１２０ａにループの判定を要求する。そして、例えばループを検出した、バッファが一杯になった等、所定の命令記録終了条件が満たされた場合に、実行命令記録部１１０ａはその記録を終了する。

ここで、最適化対象のプログラム内の各単位処理とは、１つの命令、基本ブロック、又は分岐命令であってよい。なお、基本ブロックとは、最初に実行される命令及び最後に実行される命令以外の命令が、分岐命令及び分岐先の命令の何れでもない命令の集合をいう。また、実行命令記録部１１０ａが記憶部１０５ａ（バッファ）へ記録する情報は、各単位処理の種類と、そのアドレス情報を含む。ここで各単位処理の種類とは、単位処理が、呼び出し側の単位処理、呼び出され側の単位処理、及びそれ以外のいずれであるかを示す情報であってよい。例えば単位処理が１つの命令の場合、各単位処理の種類は、呼出し命令（ｍｅｔｈｏｄ ｃａｌｌ）、リターン命令（ｍｅｔｈｏｄ ｒｅｔｕｒｎ）、呼出し命令及びリターン命令以外の命令のいずれであるかを示す情報であってよい。

また、単位処理が基本ブロックの場合、各単位処理の種類は、その基本ブロック末尾の命令が、呼出し命令（ｍｅｔｈｏｄ ｃａｌｌ）、リターン命令（ｍｅｔｈｏｄ ｒｅｔｕｒｎ）、呼出し命令及びリターン命令以外の命令のいずれであるかを示す情報であってよい。また、単位処理が分岐命令の場合は、各単位処理の種類は、その分岐命令が呼出し命令（ｍｅｔｈｏｄ ｃａｌｌ）、リターン命令（ｍｅｔｈｏｄ ｒｅｔｕｒｎ）、呼出し命令及びリターン命令以外の命令のいずれであるかを示す情報であってよい。

オプションとしてのコールスタック記録／構築部１１５ａは、後述するループ検知部１２０ａが、コールスタックを構築する機能を有しない場合に、コンパイラ装置１００ａに設けられる。コールスタック記録／構築部１１５ａは、コールスタック記録部として機能する場合、実行命令記録部１１０ａによる単位処理の列の記録開始に応答して、記録される単位処理の実行時のコールスタック情報を記憶部１０５ａ（バッファ）へ記録する。コールスタック記録／構築部１１５ａが記憶部１０５ａ（バッファ）へ記録するコールスタック情報は、コールスタックを構成する各スタックフレーム内のリターンアドレス、又はスタックポインタである。

一方、コールスタック記録／構築部１１５ａは、コールスタック構築部として機能する場合、後述するループ検知部１２０ａによる処理の開始前に、記憶部１０５ａ（バッファ）に記憶される各単位処理の種類及びアドレスを参照して、コールスタックを構築する。より具体的には、コールスタック記録／構築部１１５ａは、コールスタックを構成する各スタックフレーム内のリターンアドレスを構築する。なお、コールスタックの構築は、後述するループ検知部１２０ａにより行ってもよく、詳細は、ループ検知部１２０ａに関連して後述する。

ループ検知部１２０ａは、実行命令記録部１１０ａからのループ判定要求に応答して、記憶部１０５ａ（バッファ）内の単位処理の列についてループの判定を行う。具体的には、ループ検知部１２０ａは、記憶部１０５ａ（バッファ）からアドレス情報及びコールスタック情報を読み出し、単位処理の列内のループ始点候補の単位処理と末尾の単位処理の各々のアドレスが一致すること、かつ、上記ループ始点候補の単位処理の実行時におけるコールスタックと、上記末尾の単位処理の実行時におけるコールスタックとが一致することを条件として、単位処理の列がループをなすとの判定を出力する。ループ検知部１２０ａの機能の詳細は、図２を参照して後述する。

トレース生成部１３０ａは、ループ検知部１２０ａにより検知されたループである単位処理の列に基づいてトレースを生成する。最適化部１４０ａは、生成されたトレースを最適化して、最適化後のトレースを、コンパイル結果のプログラムとして出力する。

（第１実施形態） 図２は、本発明の第１の実施形態に係るループ検知部２００の機能ブロック図である。第１の実施形態に係るループ検知部２００は、アドレス比較部２１０と、コールスタック比較部２２０と、判定結果出力部２４０とを含む。また、ループ検知部２００は、図１を参照して説明した、実行回数が所定の閾値以上である単位処理の列に関する情報を記憶する記憶部１０５ａ／ｂ（バッファ）に接続する。以下の説明では各単位処理は１つの命令であるとして説明する。

アドレス比較部２１０は、ループ検知部２００におけるループ判定の要求の受信に応答して、記憶部１０５ａ／ｂ（バッファ）から命令列のアドレス情報を読み出し、命令列内のループ始点候補の命令と末尾の命令の各々のアドレスを比較する。ここで、記憶部１０５ａ／ｂ（バッファ）に記憶される命令列をｎ＋１個の命令からなる命令列とし、該命令列を、命令の種類とアドレスとをメンバとする構造体の配列ｉｎｓｔ［０…ｎ］で表すと、ループ始点候補の命令はｉｎｓｔ［ｓ］（ｓは０≦ｓ＜ｎを満たす正の整数、以下同じ）と表される。アドレス比較部２１０によるｉｎｓｔ［ｓ］とｉｎｓｔ［ｎ］のアドレスの比較結果は、始点候補の位置情報ｓと共に、コールスタック比較部２２０及び判定結果出力部２４０へ渡される。

ここで、ループ始点候補は、図１を参照して説明した実行命令記録部１１０ａ／ｂによって決定される。即ち、実行命令記録部１１０ａ／ｂは、記憶部１０５ａ／ｂ（バッファ）に記憶される命令列ｉｎｓｔ［０…ｎ］内の各命令ｉｎｓｔ［ｉ］（ｉは０≦ｉ＜ｎを満たす任意の正の整数、以下同じ）をループ始点候補の命令ｉｎｓｔ［ｓ］として順に決定し、その都度、ループ判定の要求を、ループ始点候補の位置情報ｓと共にループ検知部２００へ渡す。これに代えて、ループ始点候補は、アドレス比較部２１０によって決定してもよい。この場合、アドレス比較部２１０は、命令列ｉｎｓｔ［０…ｎ］内の各命令ｉｎｓｔ［ｉ］をループ始点候補の命令ｉｎｓｔ［ｓ］として順に決定し、その都度、ループ始点候補の命令ｉｎｓｔ［ｓ］と末尾の命令ｉｎｓｔ［ｎ］の各々のアドレスを比較する。

コールスタック比較部２２０は、アドレス比較部２５０からのアドレス一致の判定結果に応答して、
記憶部１０５ａ／ｂ（バッファ）からコールスタック情報を読み出し、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるコールスタックと、末尾の命令ｉｎｓｔ［ｎ］の実行時におけるコールスタックとを比較する。本実施例では、記憶部１０５ａ／ｂ（バッファ）に記憶されるコールスタック情報は、各命令ｉｎｓｔ［ｉ］の実行時におけるコールスタックを構成する各スタックフレーム内のリターンアドレスである。コールスタック比較部２２０による比較結果は、始点候補の位置情報ｓと共に、判定結果出力部２４０へ渡される。

ここで、コールスタック比較部２２０によるコールスタックの比較は、コールスタックを構成する全スタックフレーム内の全リターンアドレスでなくてよい。即ち、コールスタック比較部２２０によるコールスタックの比較を、最後に積まれたスタックフレームからｋ番目（ｋは所定の正の整数）のスタックフレームまでの各リターンアドレスについての比較に代えても、適切なｋの値を設定すれば、コールスタックの一致・不一致の判定の性能に影響はほとんどない。そのような所定の正の整数ｋ＝４とすると、コールスタック比較部２２０は、図３に示すように、両命令のコールスタックの上位４つのスタックフレーム内の各リターンアドレスをそれぞれ比較して、両命令のコールスタックの一致・不一致を判定する。なお、図３に示す例では、スタックは正の方向へ成長するとしている。

コールスタックの一致・不一致の判定の性能にほとんど影響を与えない所定の正の整数ｋを求めるため、コールスタック比較部２２０は、好ましくは、ＴＯＰｋ算出部２２５を含む。そして、ＴＯＰｋ算出部２２５は、所定の正の整数ｋを次のようにして求める。即ち、ＴＯＰｋ算出部２２５は、命令列ｉｎｓｔ［０…ｎ］内の各命令ｉｎｓｔ［ｉ］の実行時のコールスタック内において最も浅いコールスタックの深さをｍ、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるコールスタックの深さをｋ_１、末尾の命令ｉｎｓｔ［ｎ］の実行時におけるコールスタックの深さをｋ_２とすると、所定の正の整数ｋを、ｋ_１からｍを差し引いた値とｋ_２からｍを差し引いた値とのうち、小さい方の値として算出する。

所定の正の整数ｋを式にして表すと次のようになる。なお、式中のｃａｌｌＳｔａｃｋ［ｉ］．ｄｅｐｔｈはｉ番目の命令ｉｎｓｔ［ｎ］の実行時のコールスタックの深さを表す。
ｋ＝ｍｉｎ（ｋ_１、ｋ_２） ―（１）
但し、ｍ＝ ｍｉｎ_{０≦ｉ≦ｎ}ｃａｌｌＳｔａｃｋ［ｉ］．ｄｅｐｔｈ ―（２）
ｋ_１＝ ｃａｌｌＳｔａｃｋ［ｓ］．ｄｅｐｔｈ − ｍ ―（３）
ｋ_２＝ ｃａｌｌＳｔａｃｋ［ｎ］．ｄｅｐｔｈ − ｍ ―（４）

ここで各命令ｉｎｓｔ［ｉ］のコールスタック情報は、上述したように、コンパイラ装置１００ａ又はトレーシングエンジン１５０内に設けられた、コールスタック記録部として機能するコールスタック記録／構築部１１５ａ／ｂにより、各命令ｉｎｓｔ［ｉ］の実行時に記憶部１０５ａ／ｂ（バッファ）に格納される。これに代えて、コールスタック比較部２２０は、コールスタック構築部２３０を有し、コールスタック構築部２３０によりコールスタックを構築してもよい。但しこの場合、ＴＯＰｋ算出部２２５による所定の正の整数ｋの算出は、コールスタック構築後に行われる。

コールスタック構築部２３０は、記憶部１０５ａ（バッファ）から各命令ｉｎｓｔ［ｉ］について命令の種類及びアドレスを読み出して、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるコールスタックと、末尾の命令ｉｎｓｔ［ｎ］の実行時におけるコールスタックとを構築し、コールスタック情報として記憶部１０５ａ／ｂ（バッファ）に記憶する。

より詳細には、コールスタック構築部２３０は、各命令ｉｎｓｔ［ｉ］について命令の種類及びアドレスを参照して、枝分かれしたリンクリストであって、該リンクリストの各ノードが、スタックフレームを表し、かつ、該スタックフレーム内のリターンアドレスを記録するａｄｄｒｅｓｓフィールドと該スタックフレームの１つ前のスタックフレームを表すノードへの参照（リンク）を記録するｐａｒｅｎｔフィールドを有する、リンクリストを作成する。 すると、命令ｉｎｓｔ［ｉ］の実行時のコールスタックは、該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードを出発点として、各ノードのｐａｒｅｎｔフィールドの参照（リンク）に基づいて１つ前のスタックフレームのレコードを順次辿っていき、辿った各ノードのａｄｄｒｅｓｓフィールドのリターンアドレスを繋げることにより構築される。

また、ＴＯＰｋ算出部２２５が所定の正の整数ｋを求めるために使用する各命令ｉｎｓｔ［ｉ］の実行時のコールスタックの深さは、該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードから、ａｄｄｒｅｓｓフィールド及びｐａｒｅｎｔフィールドが共にＮＵＬＬであるルートノードまでの深さ・段数として求められる。かかる深さ・段数は、ルートノードを基準とした相対的な深さ・段数であるが、式（２）により求められる最も浅いコールスタックの深さｍもまた相対的な深さ・段数となるため、式（３）、式（４）、式（１）によりそれぞれ求められるk1, k2, kの各値には影響はない。

図４は、コールスタック構築部２３０により作成されるリンクリスト４００の一例を示す。図４に示すリンクリスト４００は、コード４４０の実行時のコールスタックに対して作成されるリンクリストを示す。リンクリスト４００のノード４０５は、最初に実行される関数ｆのためのスタックフレームに対応するルートノードであるため、ａｄｄｒｅｓｓフィールド及びｐａｒｅｎｔフィールドにはそれぞれＮＵＬＬが登録されている。

リンクリスト４００のノード４１０は、関数ｆ内で関数ｇが呼び出された際に積まれるスタックフレームを表す。ノード４１０のａｄｄｒｅｓｓフィールドには、関数ｇの呼び出し命令の次の命令Ａのアドレスがリターンアドレスとして登録されている。また、ノード４１０のｐａｒｅｎｔフィールドには、１つ前のスタックフレームを表すノード４０５への参照４１５が登録されている。

リンクリスト４００のノード４２０は、関数ｇ内での関数ｈの最初の呼び出し時に積まれるスタックフレームを表す。ノード４２０のａｄｄｒｅｓｓフィールドには、関数ｈの最初の呼び出し命令の次の命令Ｂのアドレスがリターンアドレスとして登録されている。また、ノード４２０のｐａｒｅｎｔフィールドには、１つ前のスタックフレームを表すノード４１０への参照４２５が登録されている。

リンクリスト４００のノード４３０は、関数ｇ内での関数ｈの２度目の呼び出し時に積まれるスタックフレームを表す。ノード４３０のａｄｄｒｅｓｓフィールドには、関数ｈの２度目の呼び出し命令の次の命令Ｃのアドレスがリターンアドレスとして登録されている。また、ノード４３０ｐａｒｅｎｔフィールドには、１つ前のスタックフレームを表すノード４１０への参照４３５が登録されている。

このようなリンクリスト４００が作成されると、上述したように、コード４４０内の各命令ｉｎｓｔ［ｉ］の実行時のコールスタックは、該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードを出発点として、各ノードのｐａｒｅｎｔフィールドの参照（リンク）に基づいて１つ前のスタックフレームのレコードを順次辿っていき、辿った各ノードのａｄｄｒｅｓｓフィールドのリターンアドレスを繋げることにより構築される。

例として、コード４４０内の関数ｈが実行された際のコールスタックの構築を考える。関数ｈは関数ｇ内で命令Ｆの条件が満たされた場合に２回呼び出されているため、関数ｈの１回目の呼出し命令により命令Ｈが実行される場合を考える。すると、そのような命令Ｈに対応するスタックフレームを表すのは、リンクリスト４００のノード４２０である。従って、ノード４２０を出発点とすると、ｐａｒｅｎｔフィールドの参照に従って、ノード４１０、ノード４０５と順にノードを辿ることができる。そして辿った各ノードのａｄｄｒｅｓｓフィールドのリターンアドレスを繋げると、Ｂ−Ａ−ＮＵＬＬ、即ち、コールスタックＢＡ４５５を構築できる。

次に、関数ｈの２回目の呼出し命令により命令Ｈが実行される場合を考える。すると、そのような命令Ｈに対応するスタックフレームを表すのは、リンクリスト４００のノード４３０である。従って、ノード４３０を出発点とすると、ｐａｒｅｎｔフィールドの参照に従って、ノード４１０、ノード４０５とノードを順に辿ることができる。そして辿った各ノードのａｄｄｒｅｓｓフィールドのリターンアドレスを繋げると、Ｃ−Ａ−ＮＵＬＬ、即ち、コールスタックＣＡ４６０を構築できる。

なお、各命令ｉｎｓｔ［ｉ］と、該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードとの対応付けは、リンクリストの作成と、リンクリストのノードと命令ｉｎｓｔ［ｉ］との対応付けを平行して行うことによりなされる。そのような処理の詳細は、図７に示すリンクリスト作成のフローチャートを参照して後述する。

判定結果出力部２４０は、アドレス比較部２１０とコールスタック比較部２２０による各比較結果が共に一致であることを条件に、命令列ｉｎｓｔ［ｓ…ｎ］がループをなすとの判定結果を出力する。例として図４に示すコード４４０内の関数ｇの実行により得られる実行命令列Ｈ−Ｂ−Ｈを考える。命令列の先頭Ｈは、関数ｈの１回目の呼出し命令により実行された命令Ｈである。一方、命令列の末尾Ｈは、関数ｈの２回目の呼び出し命令により実行された命令Ｈである。従って、命令列の先頭Ｈと命令列の末尾Ｈのアドレスは一致するが、両命令の実行時のコールスタックは、図４を参照して説明したように、先頭ＨがＢＡ４５５であるのに対し、末尾ＨはＣＡ４６０であるため、一致しない。従って、判定結果出力部２４０は、実行命令列Ｈ−Ｂ−Ｈに対し、ループをなさない、即ち偽ループであるとの判定結果を出力する。

実際、実行命令列Ｈ−Ｂ−Ｈの次に実行される命令はＣであり、実行命令列Ｈ−Ｂ−Ｈは繰り返されないので偽ループである。このように、第１実施形態に係るループ検知部２００では、ループであるか否かの判定を、アドレスの一致だけでなく、コールスタックの一致をも条件として行うので、偽ループをループとする従来技術の誤検知の問題を解決できる。

また、他の例として、図４に示すコード４４０内の関数ｇの実行により得られる実行命令列Ｈ−Ｂ−Ｈ−Ｃ−Ａ−Ｈを考える。この場合、命令列の先頭Ｈと末尾Ｈはいずれも関数ｈの１回目の呼出し命令により実行された命令Ｈである。従って、先頭Ｈと末尾Ｈの実行時のコールスタックは、いずれもＢＡ４５５であり、先頭Ｈと末尾Ｈはアドレスだけでなく実行時のコールスタックも一致する。従って、判定結果出力部２４０は、実行命令列Ｈ−Ｂ−Ｈ−Ｃ−Ａ−Ｈに対し、ループをなすとの判定結果を出力する。

実際、実行命令列Ｈ−Ｂ−Ｈ−Ｃ−Ａ−Ｈに続いて順に実行される命令はＢ、Ｈ、Ｃ、Ａであり、実行命令列Ｈ−Ｂ−Ｈ−Ｃ−Ａ−Ｈは繰り返され得るので真のループである。このように、第１実施形態に係るループ検知部２００では、ループであるか否かの判定を、アドレスの一致と、コールスタックの一致を条件として行うので、命令列の先頭の命令が属する関数からのリターン命令を含む真のループを偽ループとする従来技術の検出ミスの問題を解決できる。

次に図５から図８を参照して、第１の実施形態に係るループ検知部２００による処理の流れを説明する。図５は、第１の実施形態に係るループ検知部２００によるループ検知処理全体の流れを示すフローチャートである。図６は、Ｔｏｐｋ算出処理の流れを示すフローチャートである。図７は、リンクリスト作成処理の流れを示すフローチャートである。図８は、リンクリストを用いたコールスタック比較処理の流れを示すフローチャートである。

図５に示す処理は、ステップ５００から開始し、ループ検知部２００において、ループの始点候補ｓ（０≦ｓ＜ｎ）の情報を含むループ判定要求が受信される。続いて、アドレス比較部２１０は、ループ判定の要求の受信に応答して、記憶部１０５ａ／ｂ（バッファ）からループ始点候補ｉｎｓｔ［ｓ］と命令列の末尾ｉｎｓｔ［ｎ］のアドレス情報を読み出し、始点候補と末尾の両命令のアドレスが一致するか否かを判定する（ステップ５０５）。

始点候補と末尾の両命令のアドレスが一致する場合（ステップ５０５：ＹＥＳ）、処理はステップ５１０へ進み、コールスタック比較部２２０は、アドレスが一致するとの判定結果に応答して、記憶部１０５ａ／ｂ（バッファ）からループ始点候補ｉｎｓｔ［ｓ］と命令列の末尾ｉｎｓｔ［ｎ］のコールスタック情報を読み出し、始点候補と末尾の両命令のそれぞれの実行時のコールスタックが一致するか否かを判定する。

始点候補と末尾の両命令のコールスタックスが一致する場合（ステップ５１０：ＹＥＳ）、処理はステップ５１５へ進み、判定結果出力部２４０は、命令列ｉｎｓｔ［ｓ…ｎ］についてループであるとの肯定の判定結果を出力する。一方、ステップ５０５においてアドレスが一致しないと判定された場合、又は、ステップ５１０においてコールスタックが一致しないと判定された場合、処理はステップ５２０へ進み、判定結果出力部２４０は、命令列ｉｎｓｔ［ｓ…ｎ］はループでないとの否定の判定結果を出力する。ステップ５１５又はステップ５２０の後処理は終了する。

図６に示すＴＯＰｋ算出処理は、記憶部１０５ａ／ｂ（バッファ）に命令列ｉｎｓｔ［ｓ…ｎ］のコールスタック情報が記憶されている状態において、ＴＯＰｋ算出部２２５により、図５に示すコールスタック比較処理（Ｓ５１５）前のいずれかのタイミングでオプションとして実行される。処理はステップ６００から開始し、ＴＯＰｋ算出部２２５は、命令列ｉｎｓｔ［０…ｎ］内の各命令の実行時のコールスタックの中で最も浅いコールスタックの深さｍｉｎ_{０≦ｉ≦ｎ}ｃａｌｌＳｔａｃｋ［ｉ］．ｄｅｐｔｈをｍに設定する。

続いて、ＴＯＰｋ算出部２２５は、ループ開始候補のコールスタックの深さｃａｌｌＳｔａｃｋ［ｓ］．ｄｅｐｔｈからｍを差し引いた値をｋ_１に設定する（ステップ６０５）。同様に、ＴＯＰｋ算出部２２５は、命令列の末尾のコールスタックの深さｃａｌｌＳｔａｃｋ［ｎ］．ｄｅｐｔｈからｍを差し引いた値をｋ_２に設定する（ステップ６１０）。

続いて、ＴＯＰｋ算出部２２５は、ｋ_１とｋ_２のうち小さいほうの値ｍｉｎ（ｋ_１、ｋ_２）を、ｋに設定し（ステップ６１５）、ｋを比較すべき上位のリターンアドレス数として出力する（ステップ６２０）。そして処理は終了する。

図７に示すリンクリスト作成処理は、コールスタック情報が実行命令の記録時に記録されない場合に、コールスタック構築部２３０（又はコールスタック記録／構築部１１５ａ、ｂ）により、図５に示すコールスタック比較処理（Ｓ５１５）前のいずれかのタイミングで実行される。上述したように、図７に示すリンクリスト作成処理では、リンクリストの作成と同時に、各命令ｉｎｓｔ［ｉ］と該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードとの対応付けを行う。具体的には、命令ｉｎｓｔ［ｉ］ごとに、対応するリンクリストのノードの情報を格納するためのｃａｌｌＳｔａｃｋＮｏｄｅ［ｉ］を用意し、リンクリストのノードを作成しながら、作成したノードの参照を、対応する命令のｃａｌｌＳｔａｃｋＮｏｄｅに登録していく。

図７において処理はステップ７００から開始し、コールスタック構築部２３０は、記憶部１０５ａ／ｂ（バッファ）から命令列ｉｎｓｔ［０…ｎ］を読み出す。続いて、コールスタック構築部２３０は、ａｄｄｒｅｓｓフィールド及びｐａｒｅｎｔフィールドの値を共にＮＵＬＬとするルートノードを生成し、リンクリストの現在の処理対象ノードＰをルートノードで、また、現在の処理対象の命令の識別子ｉを値０で、それぞれ初期化する（ステップ７０５）。

続いてコールスタック構築部２３０は、現在の処理対象の命令ｉｎｓｔ［ｉ］に対応するノードの情報を格納するｃａｌｌＳｔａｃｋＮｏｄｅ［ｉ］に、現在の処理対象ノードＰを設定する（ステップ７１０）。なお、初めてステップ７１０の処理が行われるとき、変数ｉの値は０であり、ｃａｌｌＳｔａｃｋＮｏｄｅ［０］には、リンクリストのルートノードの参照が設定される。これは、命令列の中に、先頭の命令ｉｎｓｔ［０］が属する関数を呼出し先とする呼出し命令がないことを意味するが、必ずしもそうである必要はない。そのような呼出し命令があった場合は、後述するステップ７４０、７４５において新規にルートノードが生成され、以前のルートノードのａｄｄｒｅｓｓフィールド及びｐａｒｅｎｔフィールドは適切な値で更新される。

続いてコールスタック構築部２３０は、変数ｉがｎに等しいか否かを判定する（ステップ７１５）。
現在の処理対処の命令がまだｎ番目の命令でない場合（ステップ７１５：ＮＯ）、処理はステップ７２０へ進み、コールスタック構築部２３０は、現在の処理対象の命令ｉｎｓｔ［ｉ］の命令の種類を判定する。命令の種類が関数の呼び出し命令である場合、処理はステップ７２５へ進み、コールスタック構築部２３０は、リンクリストのノードを新たに生成する。そしてコールスタック構築部２３０は、新規に生成したノードのａｄｄｒｅｓｓフィールドに、呼び出し命令である現在の処理対象の命令ｉｎｓｔ［ｉ］のプログラムアドレス順での次の命令のアドレス（リターンアドレス）を設定し、ｐａｒｅｎｔフィールドに現在の処理対象ノードＰを設定する。その後コールスタック構築部２３０は、現在の処理対象ノードＰを、ステップ７２５において新規に生成したノードで更新する（ステップ７３０）。

一方ステップ７２０において命令の種類がリターン命令である場合、処理はステップ７３５へ進み、コールスタック構築部２３０は、現在の処理対象ノードＰのｐａｒｅｎｔフィールドの値がＮＵＬＬであるか否かを判定する。ｐａｒｅｎｔフィールドの値がＮＵＬＬである場合（ステップ７３５：ＹＥＳ）、処理はステップ７４０へ進み、コールスタック構築部２３０は、ａｄｄｒｅｓｓフィールド及びｐａｒｅｎｔフィールドの値を共にＮＵＬＬとするリンクリストのノードを新たに生成する。続いてコールスタック構築部２３０は、現在の処理対象ノードＰのａｄｄｒｅｓｓフィールドを、現在の処理対象の命令ｉｎｓｔ［ｉ］の命令列ｉｎｓｔ［０…ｎ］内の順番での次の命令ｉｎｓｔ［ｉ＋１］のアドレスで更新し、また、ｐａｒｅｎｔフィールドをステップ７４０において新規に生成したノードで更新する（ステップ７４５）。ｉｎｓｔ［ｉ＋１］は、リターン命令ｉｎｓｔ［ｉ］の戻り先の命令と考えられる。

ステップ７４５から、又はステップ７３５において現在の処理対象ノードＰのｐａｒｅｎｔフィールドの値がＮＵＬＬでない場合、処理はステップ７５０へ進み、コールスタック構築部２３０は、現在の処理対象ノードＰを、Ｐのｐａｒｅｎｔフィールドの値、即ちＰ．ｐａｒｅｎｔで更新する。ステップ７３０若しくはステップ７５０から、又はステップ７２０において命令の種類がリターン命令でも呼出命令でもない場合、処理はステップ７５５へ進み、コールスタック構築部２３０は、変数ｉを１インクリメントしてステップ７１０の処理へ戻り、一連の処理を繰り返す。

ステップ７１５において、変数ｉがｎに等しい場合、即ち、リンクリストの作成と、各命令ｉｎｓｔ［ｉ］と該命令ｉｎｓｔ［ｉ］に対応するスタックフレームを表すノードとの対応付けとが完了すると、コールスタック構築部２３０は、ｃａｌｌＳｔａｃｋＮｏｄｅ［０…ｎ］を出力し（ステップ７６０）、その後処理は終了する。

図８は、図５に示すコールスタック比較処理（Ｓ５１５）を、リンクリストを用いて行う場合の処理の詳細を示すフローチャートである。処理はステップ８００から開始し、コールスタック比較部２２０はカウンタｃを値０で初期化する。続いてコールスタック比較部２２０は、変数ｐに、ループ始点候補の命令ｉｎｓｔ［ｓ］に対応するノード情報ｃａｌｌＳｔａｃｋＮｏｄｅ［ｓ］を設定し、変数ｑに、末尾の命令ｉｎｓｔ［ｎ］に対応するノード情報ｃａｌｌＳｔａｃｋＮｏｄｅ［ｎ］を設定する（ステップ８０５）。

続いてコールスタック比較部２２０は、ｐ．ａｄｄｒｅｓｓとｑ．ａｄｄｒｅｓｓを比較する（ステップ８１０）。両アドレスが一致しない場合（ステップ８１０：ＮＯ）、コールスタック比較部２２０は、コールスタックは一致しないとの判定結果をもって処理を終了する。一方、両アドレスが一致する場合（ステップ８１０：ＹＥＳ）、処理はステップ８１５へ進み、コールスタック比較部２２０は、変数ｐをｐ．ｐａｒｅｎｔで、変数ｑをｑ．ｐａｒｅｎｔでそれぞれ更新する。

続いて、コールスタック比較部２２０は、カウンタｃを１インクリメントし（ステップ８２０）、カウンタｃが、比較すべき上位のリターンアドレス数ｋに等しいか否かを判定する（ステップ８２５）。カウンタｃが、比較すべき上位のリターンアドレス数ｋに等しくない場合（ステップ８２５：ＮＯ）、コールスタック比較部２２０はステップ８１０の処理へ戻り、一連の処理を繰り返す。一方、カウンタｃが比較すべき上位のリターンアドレス数ｋに等しい場合（ステップ８２５：ＹＥＳ）、コールスタック比較部２２０は、コールスタックは一致するとの判定結果をもって処理を終了する。

（第２実施形態） 図９は、本発明の第２の実施形態に係るループ検知部９００の機能ブロック図である。第２の実施形態に係るループ検知部９００は、アドレス比較部９０５と、リターン判定部９１０と、判定結果出力部９１５とを備え、ループ始点候補の命令と末尾の命令とでアドレスが一致すること、かつ、命令列が、ループの先頭の命令が属する関数からのリターン命令を含まないことを条件としてループであるとの判定を行う。ループ検知部９００はまた、図１を参照して説明した、実行回数が所定の閾値以上である命令列に関する情報を記憶する記憶部１０５ａ／ｂ（バッファ）に接続する。以下の説明では、記憶部１０５ａ／ｂ（バッファ）には、ｎ＋１個の命令からなる命令列ｉｎｓｔ［０…ｎ］が記憶されているものとして説明する。

アドレス比較部９０５は、ループ検知部９００におけるループ判定の要求の受信に応答して、記憶部１０５ａ／ｂ（バッファ）から命令列のアドレス情報を読み出して、命令列内のループ始点候補の命令ｉｎｓｔ［ｓ］と末尾の命令ｉｎｓｔ［ｎ］の各々のアドレスを比較する。アドレス比較部９０５によるｉｎｓｔ［ｓ］とｉｎｓｔ［ｎ］のアドレスの比較結果は、始点候補の位置情報ｓと共に、リターン判定部９１０及び判定結果出力部９１５へ渡される。アドレス比較部９０５による処理は、本発明の第１の実施形態に係るループ検知部２００におけるアドレス比較部２１０による処理と同じであるため、これ以上の説明は省略する。

リターン判定部９１０は、アドレス比較部９０５からのアドレス一致の判定結果に応答して、命令列ｉｎｓｔ［ｓ…ｎ］の中に、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれるか否かを判定する。リターン判定部９１０による判定結果は、始点候補の位置情報ｓと共に、判定結果出力部９２０へ渡される。

リターン判定部９１０は、上記判定を、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるスタックポインタＳＰと、命令列ｉｎｓｔ［ｓ…ｎ］内の各命令実行時におけるスタックポインタＳＰとを比較することにより行う。より具体的には、リターン判定部９１０は、命令列ｉｎｓｔ［ｓ…ｎ］内に、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるスタックポインタＳＰよりも大きいスタックポインタＳＰを有する命令が存在する場合に、命令列ｉｎｓｔ［ｓ…ｎ］内にループ始点候補からのリターン命令が含まれると判定してよい。但し、この場合スタックは負の方向へ成長するものとする。

これに代えて、リターン判定部９１０は、上記判定を、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるスタックコールの深さと、命令列ｉｎｓｔ［ｓ…ｎ］内の各命令実行時におけるコールスタックの深さとを比較することにより行ってもよい。より具体的には、リターン判定部９１０は、命令列ｉｎｓｔ［ｓ…ｎ］内の各命令について、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるコールスタックの深さを基準（＝０）とした相対的なコールスタックの深さｌｅｖｅｌを求め、該深さｌｅｖｅｌの値が負となるような命令が命令列ｉｎｓｔ［ｓ…ｎ］内に存在する場合に、命令列ｉｎｓｔ［ｓ…ｎ］内にループ始点候補からのリターン命令が含まれると判定してよい。

なお、スタックポインタＳＰ情報は、図１を参照して説明したコールスタック記録／構築部１１５ａ、ｂが、実行命令記録部１１０ａによる命令列の記録開始に応答して、記憶部１０５ａ（バッファ）へ記録してよい。また、相対的なコールスタックの深さｌｅｖｅｌ情報は、リターン判定部９１０が、命令列ｉｎｓｔ［ｓ…ｎ］内の各命令の種類に応じて、コールスタックの深さｌｅｖｅｌを増減させることにより求めてよい。詳細は図１２を参照して後述する。

判定結果出力部９１５は、アドレス比較部９０５からアドレス一致との比較結果を、また、リターン判定部９１０からループ始点候補からのリターン命令は含まれないとの判定結果を受け取ることを条件に、命令列ｉｎｓｔ［ｓ…ｎ］がループであるとの判定結果を出力する。

ここで、図１０（ｂ）に示すコードを例として、本発明の第２の実施形態に係るループ検知部９００のよるループ判定結果を説明する。図１０（ａ）は、トレースの先頭の命令が属する関数からのリターン命令を含むトレースの生成を禁止する従来手法によるループ判定結果と、本発明の第２の実施形態に係るループ検知部９００によるループ判定結果とを比較した表である。表では、図１０（ｂ）に示すコードから得られる４種類の命令列（上から順に、Ｇ−Ｂ−Ｇ、Ａ−Ｇ−Ｂ−Ｇ、Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａ、Ｇ−Ｂ−Ｇ−Ｃ―Ａ−Ｇ）について、それぞれの手法によるループ判定結果を比較している。なお、命令列の下に描かれている２つの矢印は、上段がトレースの先頭位置を、下段がループの先頭位置を示している。なお、従来手法によるループ判定結果は、正確には、トレースの生成の許可・禁止の結果である。

まず１つ目の命令列Ｇ−Ｂ−Ｇについて検討する。命令列Ｇ−Ｂ−Ｇは、トレースの先頭Ｇとループの先頭Ｇが同じであるため、ループ判定結果は従来手法と本発明とで異ならない。即ち、命令列Ｇ−Ｂ−ＧのＧ−Ｂにより、トレース／ループの先頭命令Ｇの属する関数ｇからのリターン命令が命令列に含まれることが示されるので、どちらの手法でも偽ループとの判定結果が得られている。実際、命令列Ｇ−Ｂ−Ｇに続いて実行されるのは命令Ｃであるため、命令列Ｇ−Ｂ−Ｇは偽ループであり、両手法による判定結果は正しい。

次に３つ目の命令列Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａについて検討する。命令列Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａもまた、トレースの先頭Ａとループの先頭Ａが同じであるため、ループ判定結果は従来手法と本発明とで異ならない。即ち、命令列Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａには、トレース／ループの先頭命令Ａの属する関数ｆからのリターン命令が含まれないため、どちらの手法でもループとの判定結果が得られている。実際、命令列Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａは繰り返し実行され得る命令列であるため、真のループであり、両手法による判定結果は正しい。

次に２つ目の命令列について検討する。命令列Ａ−Ｇ−Ｂ−Ｇについては、トレースの先頭Ａとループの先頭Ｇが異なるため、ループ判定結果は従来手法と本発明とで異なる。即ち、従来手法では、トレースの先頭命令Ａの属する関数ｆからのリターン命令が命令列に含まれないため、ループとの判定結果が得られている。これに対し本発明では、命令列Ａ−Ｇ−Ｂ−ＧのＧ−Ｂにより、ループの先頭命令Ｇの属する関数ｇからのリターン命令が命令列に含まれることが示されるので、偽ループとの判定結果が得られている。実際、命令列Ｇ−Ｂ−Ｇに続いて実行されるのは命令Ｃであり、命令列Ｇ−Ｂ−Ｇは繰り返し実行されないので、偽ループである。このように、従来手法において結果的に偽ループとして判定していたケースについても、本発明によれば正しくループの判定を行うことができる。

次に４つ目の命令列について検討する。命令列Ｇ−Ｂ−Ｇ−Ｃ―Ａ−Ｇは、トレースの先頭Ｇとループの先頭Ｇが同じであるため、ループ判定結果は従来手法と本発明とで異ならない。即ち、命令列Ｇ−Ｂ−Ｇ−Ｃ―Ａ−ＧのＧ−Ｂにより、トレース／ループの先頭命令Ｇの属する関数ｇからのリターン命令が命令列に含まれることが示されるので、どちらの手法でも偽ループとの判定結果が得られている。しかし実際は、命令列Ｇ−Ｂ−Ｇ−Ｃ―Ａ−Ｇは繰り返し実行され得る命令列であるため、真のループであり、両手法による判定結果は間違いである。但し、命令列Ｇ−Ｂ−Ｇ−Ｃ―Ａ−Ｇについては、開始点がＡ−Ｇ−Ｂ−Ｇ−Ｃ−Ａに比べると非典型的であるため、システムによってはこのようなループの検出要求は低い。また、偽ループをループとする誤検出ではないため、かかる判定ミスは許容範囲といえる。

次に図１１から図１３を参照して、第２の実施形態に係るループ検知部９００による処理の流れを説明する。図１１は、第２の実施形態に係るループ検知部９００によるループ検知処理全体の流れを示すフローチャートである。図１２は、図１１に示すフローチャートのステップ１１１０のリターン命令判定処理の流れの一例を示すフローチャートである。図１３は、図１１に示すフローチャートのステップ１１１０のリターン命令判定処理の流れの他の例を示すフローチャートである。

図１１に示す処理は、ステップ１１００から開始され、ループ検知部９００において、ループの始点候補ｓ（０≦ｓ＜ｎ）の情報を含むループ判定要求が受信される。続いて、アドレス比較部９０５は、ループ判定の要求の受信に応答して、記憶部１０５ａ／ｂ（バッファ）からループ始点候補ｉｎｓｔ［ｓ］と命令列の末尾ｉｎｓｔ［ｎ］のアドレス情報を読み出し、始点候補と末尾の両命令のアドレスが一致するか否かを判定する（ステップ１１０５）。

始点候補と末尾の両命令のアドレスが一致する場合（ステップ１１０５：ＹＥＳ）、処理はステップ１１１０へ進み、リターン判定部９１０は、アドレスが一致するとの判定結果に応答して、命令列ｉｎｓｔ［ｓ…ｎ］の中に、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれるか否かを判定する。

リターン命令が含まれない場合（ステップ１１１０：ＹＥＳ）、処理はステップ１１１５へ進み、判定結果出力部９１５は、命令列ｉｎｓｔ［ｓ…ｎ］はループであるとの肯定の判定結果を出力する。一方、ステップ１１０５においてアドレスが一致しないと判定された場合、又はステップ１１１０においてリターン命令が含まれると判定された場合、処理はステップ１１２０へ進み、判定結果出力部９１５は、命令列ｉｎｓｔ［ｓ…ｎ］はループでないとの否定の判定結果を出力する。ステップ１１１５又はステップ１１２０の後処理は終了する。

図１２に示す第１実施例のリターン命令判定処理は、ステップ１２００から開始され、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるスタックポインタＳＰと、命令列ｉｎｓｔ［ｓ…ｎ］内の各命令実行時におけるスタックポインタＳＰとを比較して、命令列ｉｎｓｔ［ｓ…ｎ］内に、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるスタックポインタＳＰよりも大きいスタックポインタＳＰを有する命令が存在するか否かを判定する。

そのような命令が命令列ｉｎｓｔ［ｓ…ｎ］内に存在する場合（ステップ１２００：ＹＥＳ）、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれるとの判定結果をもって処理を終了する。一方、そのような命令が命令列ｉｎｓｔ［ｓ…ｎ］内に存在しない場合（ステップ１２００：ＮＯ）、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれないとの判定結果をもって処理を終了する。なお、ここでは、スタックは負の方向へ成長するものとしている。

図１３に示す第２実施例のリターン命令判定処理は、ステップ１３００から開始され、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］の実行時におけるコールスタックの深さを基準（＝０）とした相対的なコールスタックの深さの現在の値を示す変数ｌｅｖｅｌを用意し、値０で初期化する。続いてリターン判定部９１０は、命令列ｉｎｓｔ［ｓ…ｎ］の内、現在の処理対象命令を識別する変数ｉを、ループ始点候補の識別子ｓで初期化する（ステップ１３０５）。

続いてリターン判定部９１０は、現在の処理対象命令の識別子ｉがｎ以下であるか否かを判定する（ステップ１３１０）。現在の処理対象命令の識別子ｉがｎ以下である場合（ステップ１３１０：ＹＥＳ）、処理はステップ１３１５へ進み、リターン判定部９１０は、現在の処理対象命令ｉｎｓｔ［ｉ］の命令の種類を判定する。

ステップ１３１５において命令の種類が関数の呼び出し命令である場合、処理はステップ１３２０へ進み、リターン判定部９１０は現在のコールスタックの相対的な深さｌｅｖｅｌを１インクリメントする。そして、リターン判定部９１０は、現在の処理対象命令を識別する変数ｉを１インクリメントして（ステップ１３２５）、ステップ１３１０の処理へ戻り、一連の処理を繰り返す。

ステップ１３１５において命令の種類が関数の呼び出し命令でもリターン命令でもない場合、処理はステップ１３２５へ進み、リターン判定部９１０は現在の処理対象命令を識別する変数ｉを１インクリメントして（ステップ１３２５）、ステップ１３１０の処理へ戻り、一連の処理を繰り返す。

一方、ステップ１３１５において命令の種類がリターン命令である場合、処理はステップ１３３０へ進み、リターン判定部９１０はコールスタックの現在の相対的な深さｌｅｖｅｌを１デクリメントする。続いてリターン判定部９１０は、コールスタックの現在の相対的な深さｌｅｖｅｌが０より小さいか否かを判定する（ステップ１３３５）。コールスタックの現在の相対的な深さｌｅｖｅｌが０より小さい場合（ステップ１３３５：ＹＥＳ）、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれるとの判定結果をもって、処理を終了する。コールスタックの現在の相対的な深さｌｅｖｅｌが０以上である場合（ステップ１３３５：ＮＯ）、リターン判定部９１０は、現在の処理対象命令を識別する変数ｉを１インクリメントして（ステップ１３２５）、ステップ１３１０の処理へ戻り、一連の処理を繰り返す。

一方、ステップ１３１０において、現在の処理対象命令の識別子ｉがｎより大きい場合（ステップ１３１０：ＮＯ）、即ち、命令列ｉｎｓｔ［ｓ…ｎ］内の全ての命令について相対的なコールスタックの深さｌｅｖｅｌが検討され、かつ、相対的なコールスタックの深さｌｅｖｅｌが負になることがなかった場合、リターン判定部９１０は、ループ始点候補の命令ｉｎｓｔ［ｓ］が属する関数からのリターン命令が含まれないとの判定結果をもって、処理を終了する。

上述したように、本発明に係るループ検知装置は、トレースベースのコンパイルを行うコンパイラ装置１００ａの一機能（ループ検知部１２０ａ）として実装されてもよく、或いは、トレースベースのコンパイルを行うコンパイラ装置１００ｂに付随するトレーシングエンジン１５０の一機能（ループ検知部１２０ｂ）として実装されてもよい。以下では、図１４を参照して、コンパイラ装置１００ａ又はコンパイラ装置１００ｂ及びトレーシングエンジン１５０によるコンパイル処理の流れを説明する。

図１４は、コンパイラ装置１００ａ又はコンパイラ装置１００ｂ及びトレーシングエンジン１５０によるコンパイル処理の流れを示すフローチャートである。処理はステップ１４００から開始し、コンパイラ装置１００ａの実行命令記録部１１０ａ又はトレーシングエンジン１５０の実行命令記録部１１０ｂは、インタプリタによる命令の実行に応答して、実行命令に割り当てられたカウンタを１増加する。続いて、実行命令記録部１１０ａ／ｂは、カウンタが所定の閾値に達したことに応答して、実行命令を格納する記憶部１０５ａ／ｂ（バッファ）を空にする（ステップ１４１０）。

続いて、実行命令記録部１１０ａ／ｂは、実行命令記録終了条件が満たされているか否かを判定する（ステップ１４１５）。ここで実行命令記録終了条件とは、例えば、ループを検出した、バッファが一杯になった等、所定の命令記録終了条件をいう。実行命令記録終了条件がまだ満たされない場合（ステップ１４１５：ＮＯ）、処理はステップ１４２０へ進み、実行命令記録部１１０ａ／ｂは、実行命令を記憶部１０５ａ／ｂ（バッファ）の末尾に追加する。

続いて、処理はステップ１４２５へ進み、実行命令記録部１１０ａ／ｂは、記憶部１０５ａ／ｂ（バッファ）に記憶されているｎ＋１個の命令列ｉｎｓｔ［０…ｎ］に対して、ループ始点候補の位置ｓを０≦ｓ＜ｎの範囲で順次決定する。決定されたループ始点候補の位置ｓはループ検知部１２０ａ／ｂへ渡され、ループ検知部１２０ａ／ｂは、命令列ｉｎｓｔ［ｓ…ｎ］に対して、ループ判定を行う（ステップ１４３０）。ループ判定処理の詳細は、図５〜図８、図１１〜図１３を参照して既に説明した通りであるから、ここでは省略する。

ループ検知部１２０ａ／ｂは、ループ始点候補の位置として実行命令記録部１１０ａ／ｂにより決定された全てのｓについてループ判定結果を得ると、ループを検出されたｓが１以上あったか否かを判定する（ステップ１４３５）。ループを検出されたｓが１つもなかった場合（ステップ１４３５：ＮＯ）、処理はステップ１４１５へ戻り、一連の処理が繰り返される。

一方、ループを検出されたｓが１以上あった場合（ステップ１４３５：ＹＥＳ）、又は１４１５において、実行命令記録終了条件が満たされると判定された場合（ステップ１４１５：ＹＥＳ）、処理はステップ１４４０へ進み、トレース生成部１３０ａ／ｂは、ループであると判定された命令列ｉｎｓｔ［ｓ…ｎ］に基づいてトレースを生成する（ステップ１４４０）。続いて、最適化部１４０ａ／ｂは、生成されたトレースを最適化してコンパイルし、ネイティブ・コードを生成する（ステップ１４４５）。そして処理は終了する。なお、生成されたネイティブ・コードはコンパイラ装置１００ａ／ｂにより実行される。

次に図１５を参照して、トレース生成部１３０ａ／ｂにより生成されるトレースについて説明する。図１５に示す例は、命令列ｉｎｓｔ［０…ｎ］に対し、ループ始点候補の位置ｓ＝２についてループが検出された場合を示す。トレース生成部１３０ａ／ｂが生成するトレースは、ループ部分のないトレース１５００であってもよく、又はループの手前で終了するトレース１５０５であってもよく、或いはループでないトレース１５１０とループをなすトレース１５１５とからなるトレース１５２０であってもよい。このようにトレース生成部１３０ａ／ｂは、ループ判定結果に基づき処理系全体の目的に応じたトレースを生成する。

図１６に、図１０（ｂ）に示すコードを例として、上述した本発明に係るループ検知手法によるループ判定結果をまとめる。なお、比較のため、図１６には従来手法によるループ判定結果も記載する。表中の従来技術の欄に記載されるNoFLFは、命令列の先頭の命令と末尾の命令のアドレスが同じであることを条件に、その命令列をループであると判断する従来手法を示す。また、FLFno Return Traceは、トレースの先頭の命令が属する関数からのリターン命令を含むトレースの生成を禁止する従来手法を示す。

また、表中本発明の欄に記載されるFLFCall Stackは、本発明の第１実施形態に係るループ検知部２００によるループ検知方法を示す。また、FLFNo Return Loopは、本発明の第２実施形態に係るループ検知部９００によるループ検知方法を示す。更に、FLFtwo iterationsは、ある命令列が２回繰り返されることを検知した場合にその命令列をループと判定するループ検知方法を示す。

なお、図１６に示す表では、図１０（ｂ）に示すコードから得られる５種類の命令列について、それぞれの手法によるループ判定結果を比較している。５種類の命令列のうち、Ｇ−Ｂ−Ｇ、Ａ−Ｇ−Ｂ−Ｇ、Ａ−Ｇ−Ｂ−Ｇ−Ｃ−Ａ、Ｇ−Ｂ−Ｇ−Ｃ―Ａ−Ｇの４種類は、図１０（ａ）を参照して説明した命令列と同じであり、命令列を囲む矩形はループを示している。左から４番目の命令列、Non-looptrace with return from head は、ループ先頭の属する関数からのリターンを含む、ループではない命令列のトレースを示す。該命令列はループではないので、該命令列に対する判定結果は、「許可」又は「禁止」のいずれかである。

図１６の表に示すように、全ての種類の命令列に対し望ましい判定結果を出すのは、FLF callstackとFLF two iterationsの２つである。しかし、FLF two iterationsは、命令列が２回繰り返されることを条件としてループを検知するため、ループの判定に時間を要し、また、トレースの合計サイズが大きくなることから、FLF callstackのほうがより好ましいループ検知方法であるといえる。

図１７は、本発明を実施するためのコンピュータ５０のハードウェア構成の一例を示した図である。コンピュータ５０は、バス２に接続されたメインＣＰＵ（中央処理装置）１とメインメモリ４を含んでいる。ハードディスク装置１３、３０、及びＣＤ−ＲＯＭ装置２６、２９、フレキシブル・ディスク装置２０、ＭＯ装置２８、ＤＶＤ装置３１のようなリムーバブル・ストレージ（記録メディアを交換可能な外部記憶システム）がフレキシブル・ディスクコントローラ１９、ＩＤＥコントローラ２５、ＳＣＳＩコントローラ２７などを経由してバス２へ接続されている。

フレキシブル・ディスク、ＭＯ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭのような記憶メディアが、リムーバブル・ストレージに挿入される。これらの記憶メディアやハードディスク装置１３、３０、ＲＯＭ１４には、オペレーティング・システムと協働してＣＰＵ等に命令を与え、本発明を実施するためのコンピュータ・プログラムのコードを記録することができる。即ち、上記説明した数々の記憶装置には、コンピュータ５０にインストールされ、コンピュータ５０をループ検知部２００／９００、コンパイラ装置１００ａ／ｂ、またトレーシングエンジン１５０として機能させるプログラムを記録することができる。

コンピュータ５０をループ検知部２００として機能させる上記プログラムは、アドレス比較モジュール、コールスタック比較モジュール、判定結果出力モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、アドレス比較２１０、コールスタック比較部２２０、判定結果出力部２４０としてそれぞれ機能させる。また、コールスタック比較モジュールは、更に、ＴＯＰｋ算出モジュールと、コールスタック構築モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、ＴＯＰｋ算出部２２５、コールスタック構築部２３０としてそれぞれ機能させる。

コンピュータ５０をループ検知部９００として機能させる上記プログラムは、アドレス比較モジュール、リターン判定モジュール、判定結果出力モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、アドレス比較部９０５、リターン判定部９１０、判定結果出力部９１５としてそれぞれ機能させる。

コンピュータ５０をコンパイラ装置１００ａとして機能させる上記プログラムは、記憶モジュール、実行命令記録モジュール、コールスタック記録／構築モジュール、ループ検知モジュール、トレース生成モジュール、最適化モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、記憶部１０５ａ、実行命令記録部１１０ａ、コールスタック記録／構築部１１５ａ、ループ検知部１２０ａ、トレース生成部１３０ａ、最適化部１４０ａとしてそれぞれ機能させる。

コンピュータ５０をコンパイラ装置１００ｂとして機能させる上記プログラムは、トレース生成モジュール、最適化モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、トレース生成部１３０ｂ、最適化部１４０ｂとしてそれぞれ機能させる。コンピュータ５０をトレーシングエンジン１５０として機能させる上記プログラムは、記憶モジュール、実行命令記録モジュール、コールスタック記録／構築モジュール、ループ検知モジュールを含む。これらモジュールは、ＣＰＵ１等に働きかけて、コンピュータ５０を、記憶部１０５ｂ、実行命令記録部１１０ｂ、コールスタック記録／構築部１１５ｂ、ループ検知部１２０ｂとしてそれぞれ機能させる。コンピュータ・プログラムは圧縮し、また複数に分割して複数の媒体に記録することもできる。

コンピュータ５０は、キーボード／マウス・コントローラ５を経由して、キーボード６やマウス７のような入力デバイスからの入力を受ける。コンピュータ５０は、オーディオコントローラ２１を経由して、マイク２４からの入力を受け、またスピーカー２３から音声を出力する。コンピュータ５０は、視覚データをユーザに提示するための表示装置１１に、グラフィックスコントローラ１０を経由して接続される。コンピュータ５０は、ネットワーク・アダプタ１８（イーサネット（登録商標）・カードやトークンリング・カード）等を介してネットワークに接続し、他のコンピュータ等と通信を行うことが可能である。

以上の説明により、本実施形態に係るコンピュータ５０は、通常のパーソナルコンピュータ、ワークステーション、メインフレームなどの情報処理装置、又は、これらの組み合わせによって実現されることが容易に理解されるであろう。なお、上記説明した構成要素は例示であり、そのすべての構成要素が本発明の必須構成要素となるわけではない。

以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。

Claims (11)

1. コンピュータの計算処理により、プログラムにおける各単位処理のうち連続して実行された単位処理の列がループであるか否かを判定するループ検知方法であって、前記コンピュータが、
   前記コンピュータの記憶部から前記単位処理の列についてアドレス情報を読み出して、前記単位処理の列内のループ始点候補の単位処理と末尾の単位処理の各々のアドレスを比較するステップと、
   前記コンピュータの記憶部から前記単位処理の列についてコールスタック情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックを比較するステップと、
   前記アドレス及び前記コールスタックの各比較結果が一致であることを条件に、前記単位処理の列がループをなすとの判定結果を出力するステップと、
   を含み、
   前記コールスタックの比較は、前記コールスタックを構成する各スタックフレーム内のリターンアドレスの比較であり、
   前記各スタックフレーム内のリターンアドレスの比較は、最後に積まれたスタックフレームからｋ番目（ｋは所定の正の整数）のスタックフレームまでの各リターンアドレスの比較であって、
   前記単位処理の列内の各単位処理実行時のコールスタック内において最も浅いコールスタックの深さをｍ、前記ループ始点候補の単位処理の実行時におけるコールスタックの深さをｋ _１ 、及び前記末尾の単位処理の実行時におけるコールスタックの深さをｋ _２ とした場合に、前記所定の正の整数ｋは、ｋ _１ からｍを差し引いた値と、ｋ _２ からｍを差し引いた値のうち小さい方の値として算出される、ループ検知方法。
2. 前記コンピュータが、前記コンピュータの記憶部から前記単位処理の列について単位処理の種類情報及びアドレス情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックとを構築し、前記コールスタック情報として前記記憶部に記憶するステップを更に含む、請求項１に記載のループ検知方法。
3. 前記単位処理の種類情報は、前記単位処理が、呼び出し側の単位処理、呼び出され側の単位処理、及びそれ以外のいずれであるかを示す情報である、請求項２に記載のループ検知方法。
4. 各コールスタックの構築は、前記単位処理の列について単位処理の種類情報及びアドレス情報を参照して、枝分かれしたリンクリストであって、該リンクリストの各ノードが、
   スタックフレームを表し、かつ、該スタックフレームのリターンアドレスと該スタックフレームの１つ前のスタックフレームを表すノードへの参照（リンク）とを記録するデータフィールドを有する、前記リンクリストを作成するステップとを含み、前記単位処理の列内の任意の単位処理の実行時のコールスタックは、該任意の単位処理に対応するスタックフレームを表すノードを出発点として前記参照に基づいて１つ前のスタックフレームのノードを順次辿っていき、辿った各ノードのリターンアドレスを繋げることにより構築される、請求項３に記載のループ検知方法。
5. 前記単位処理は、１つの命令、基本ブロック、又は分岐命令である、請求項１に記載のループ検知方法。
6. 前記コンピュータが、前記単位処理の列内の各単位処理を前記ループ始点候補の単位処理として順次決定し、該決定ごとに各ステップを繰り返し実行するステップを更に含む、請求項１に記載のループ検知方法。
7. 前記コンピュータが、単位処理ごとに実行回数をカウントするステップと、前記実行回数が所定の値に達することを応答して、前記コンピュータの記憶部への前記単位処理の列の記録を開始するステップと、前記単位処理の列がループをなすとの判定の出力に応答して該判定に基づいて前記単位処理の列のトレースを生成し、最適化してコンパイルするステップとを更に実行する、請求項１に記載のループ検知方法。
8. コンピュータに、請求項１〜７のいずれか１項に記載の方法の各ステップを実行させるループ検知プログラム。
9. プログラムにおける各単位処理のうち連続して実行された単位処理の列がループをなすか否かを判定するループ検知装置であって、
   前記単位処理の列についてアドレス情報及びコールスタック情報を記憶する記憶部と、
   前記記憶部から前記単位処理の列についてアドレス情報を読み出して、前記単位処理の列内のループ始点候補の単位処理と末尾の単位処理の各々のアドレスを比較するアドレス比較部と、
   前記記憶部から前記単位処理の列についてコールスタック情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックを比較するコールスタック比較部と、
   前記アドレス及び前記コールスタックの各比較結果が一致であることを条件に、前記単位処理の列がループをなすとの判定結果を出力する出力部と、
   を含み、
   前記コールスタック比較部は、前記コールスタックの比較は、前記コールスタックを構成する各スタックフレーム内のリターンアドレスの比較を、最後に積まれたスタックフレームからｋ番目（ｋは所定の正の整数）のスタックフレームまでの各リターンアドレスの比較により実行し、
   前記単位処理の列内の各単位処理実行時のコールスタック内において最も浅いコールスタックの深さをｍ、前記ループ始点候補の単位処理の実行時におけるコールスタックの深さをｋ _１ 、及び前記末尾の単位処理の実行時におけるコールスタックの深さをｋ _２ とした場合に、前記所定の正の整数ｋは、ｋ _１ からｍを差し引いた値と、ｋ _２ からｍを差し引いた値のうち小さい方の値として算出する、
   ループ検知装置。
10. プログラムにおける各単位処理のうち連続して実行された単位処理の列がループをなすか否かを判定するループ検知装置であって、
    前記単位処理の列の各単位処理についてアドレス情報及び該単位処理の種類情報を記憶する記憶部と、
    前記記憶部から前記単位処理の列についてアドレス情報を読み出して、前記単位処理の列内のループ始点候補の単位処理と末尾の単位処理の各々のアドレスを比較するアドレス比較部と、
    前記記憶部から前記単位処理の種類情報及び前記アドレス情報を読み出して、前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックとを構築する、コールスタック構築部と、
    前記ループ始点候補の単位処理の実行時におけるコールスタックと、前記末尾の単位処理の実行時におけるコールスタックを比較するコールスタック比較部と、
    前記アドレス及び前記コールスタックの各比較結果が一致であることを条件に、前記単位処理の列がループをなすとの判定結果を出力する出力部と、
    を含み、
    前記コールスタック比較部は、前記コールスタックの比較は、前記コールスタックを構成する各スタックフレーム内のリターンアドレスの比較を、最後に積まれたスタックフレームからｋ番目（ｋは所定の正の整数）のスタックフレームまでの各リターンアドレスの比較により実行し、
    前記単位処理の列内の各単位処理実行時のコールスタック内において最も浅いコールスタックの深さをｍ、前記ループ始点候補の単位処理の実行時におけるコールスタックの深さをｋ _１ 、及び前記末尾の単位処理の実行時におけるコールスタックの深さをｋ _２ とした場合に、前記所定の正の整数ｋは、ｋ _１ からｍを差し引いた値と、ｋ _２ からｍを差し引いた値のうち小さい方の値として算出する、
    ループ検知装置。
11. 前記コールスタックの構築部は、前記単位処理の列について単位処理の種類情報及びアドレス情報を参照して、枝分かれしたリンクリストであって、該リンクリストの各レコードが、スタックフレームを表し、かつ、リターンアドレスと１つ前のスタックフレームを表すレコードへの参照（リンク）とを記録する、前記リンクリストを作成し、求めるべき単位処理の実行時のコールスタックを、該単位処理に対応するスタックフレームを表すレコードを出発点として前記参照に基づいて１つ前のスタックフレームのレコードを順次辿っていき、各レコードのリターンアドレスを繋げることにより構築する、請求項１０に記載のループ検知装置。

Images