(57)【特許請求の範囲】
【請求項１】
プロファイル作成用にセクション内のループを準備するために、コンピュータがコンパイラを実行して、プログラム・コードのセクションにエントリ計測スロットを配置する方法であって、少なくとも１つのループのエントリ点が定められており、
コンピュータがコンパイラを実行して、あらかじめ定められた数のエントリ計測スロットをループのエントリ点の前に挿入するステップと、
コンピュータがコンパイラを実行して、ループの外に配置された分岐命令のターゲットを、該ターゲットがループ内にある場合、エントリ計測スロットの第１の命令を指すように変更するステップと、
コンピュータがコンパイラを実行して、ループ内からエントリ計測スロットへのフォール・スルーがあれば、エントリ計測スロットを迂回して分岐するようにエントリ計測スロットの第１の命令の前に分岐命令を挿入するステップと、を含む方法。
【請求項２】
プロファイル作成用にセクション内のループを準備するために、コンピュータがコンパイラを実行して、プログラム・コードのセクションに終了計測スロットを配置する方法であって、暗示的終了点、およびループの外側にターゲットを有する少なくとも１つの明示的終了命令が定められており、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第１の終了計測スロットを、ループの暗示的終了点の次に挿入するステップと、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第２の終了命令スロットを明示的終了命令のターゲットの前に挿入するステップと、
コンピュータがコンパイラを実行して、セクション内に第２の終了計測スロットへのフォール・スルーがあれば、第２の終了計測スロットを迂回して分岐するように、第２の終了計測スロットの第１の命令の前に分岐命令を挿入するステップと、
コンピュータがコンパイラを実行して、第２の終了計測スロットの第１の命令を指すように明示的終了命令のターゲットを変更するステップと、を含み、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第１の終了計測スロットが暗示的終了点の直後に挿入される方法。
【請求項３】
コンピュータがコンパイラを実行して、プロファイル作成用にプログラム・コードのセクション内のループを準備する方法であって、少なくとも１つのエントリ点およびループの暗示的終了点が定められており、
コンピュータがコンパイラを実行して、あらかじめ定められた数のエントリ計測スロットをループのエントリ点の前に挿入するステップと、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第１の終了計測スロットをループの暗示的終了点の次に挿入するステップと、を含み、
前記ループがエントリ計測スロットへのフォール・スルーを有し、
前記方法が、コンピュータがコンパイラを実行して、エントリ計測スロットを迂回して分岐するように、エントリ計測スロットの第１の命令の前に分岐命令を挿入するステップを含む方法。
【請求項４】
コンピュータがコンパイラを実行して、プロファイル作成用にプログラム・コードのセクション内のループを準備する方法であって、少なくとも１つのエントリ点およびループの暗示的終了点が定められており、
コンピュータがコンパイラを実行して、あらかじめ定められた数のエントリ計測スロットをループのエントリ点の前に挿入するステップと、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第１の終了計測スロットをループの暗示的終了点の次に挿入するステップと、を含み、
ループの外側にターゲットを有する少なくとも１つの明示的終了命令が定められており、
コンピュータがコンパイラを実行して、あらかじめ定められた数の第２の終了計測スロットを明示的終了命令のターゲットの前に挿入するステップをさらに含み、
前記セクションが第２の終了計測スロットへのフォール・スルーを有し、
前記方法が、コンピュータがコンパイラを実行して、第２の終了計測スロットを迂回して分岐するように、第２の終了計測スロットの第１の命令の前に分岐命令を挿入するステップをさらに含む方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般にコンピュータ・システム・コンパイラに関し、さらに詳細には、ループ実行特性の正確な割当てを可能にするために、コード中のいくつかの点に計測（ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ：インストルメンテーション）スロットを配置することによってプログラム・コード中のループ構造のプロファイルを作成する方法に関する。
【０００２】
【従来の技術】
コンパイラは、通常高水準言語で書かれたソース・プログラムを、一般に機械命令またはアセンブリ言語のシーケンスから構成される低水準言語に変換する。ソース・プログラム中の構成は、アセンブリ言語命令のシーケンスに変換される。最大限の動作効率を得るためには、プログラムが実行にどのくらいの時間を要するかを正確に知ることが重要である。プログラムの、効率の改善を必要とする部分に集中するために、プログラムが実行に要する時間の長さ、およびプログラム実行に関する他の統計を、関数レベル、ループ・レベル、および基本ブロック・レベルで決定しなければならない。
【０００３】
従来技術の技法は、プロファイラを使用して、ループに関する情報を収集する。しかしながら、これは、単一エントリ（ｅｎｔｒｙ：入口、開始）のループで複数のエントリ点を有しないループしか処理することができない。さらに、従来技術のプロファイラは、ネスト・ループを有するループを処理することができない。また、これには、ネスト・ループおよび複数のエントリ点を有するループの問題があった。これらのループは高水準言語の大部分をなすので、これらのタイプのループに関する情報を収集することは非常に重要であり、また各ループが実行にどのくらいの時間を要するか、ならびにキャッシュ・ミスやヒット率など、他の特性を正確に決定することはプログラムの実行を最適化するために重要である。
【０００４】
従来技術のプロファイラにはまた、共通の終了（ｅｘｉｔ：終了、出口）点を有するネスト・ループに関するプロファイル作成情報を収集する問題がある。これらの場合、従来技術のプロファイラは、動作を中断し、これらのループについてプロファイルを作成することができないことをユーザに通知するだけであった。したがって、ユーザは、これらのループが実行にどのくらいの時間を要するかを知ることができず、またこれらのループに関する統計を決定することができなかった。これは、プログラム中の多数のループは共通の出口を有するループであるので重大な問題である。ユーザが書く最も一般的なループの１つは、制御をループ・ネストから剥奪し、プログラム中の異なる場所に送るエラー文、すなわちｇｏｔｏ  ｅｒｒｏｒを含むループである。これらのループは、従来技術の技法を使用する従来技術のプロファイラではプロファイルを作成することができない。
【０００５】
他の問題は、プロファイラがループに関する情報の収集を試みる態様である。すなわち、プロファイラは、ループが実行したやり方を変更する。従来技術のプロファイル作成技法がループに関する情報を収集するために使用した考えは、ループを変更し、したがって収集された情報をゆがめる。プロファイラが情報をゆがめる１つの形は、プロファイラがループの実行時間を変更することである。プロファイラはまた、命令をループ内に入れるので命令キャッシュの挙動を変更する。プロセッサが使用するキャッシュ置換アルゴリズムに応じて、これらの命令をキャッシュ中にロードし、次いでパージしなければならないので、命令キャッシュの挙動が変化する。
【０００６】
プログラムを実行するとき、命令が主メモリから入れられ、次いで実行される。プログラムの速度を上げるために、キャッシュと呼ばれるより速いメモリがＣＰＵと主メモリとの間に配置される。一般に、キャッシュ・メモリは、ＳＲＡＭから構成され、かなりサイズが小さい。通常、キャッシュは、一般にスーパーコンピュータでは約１または２ギガバイトである主メモリに対して、約１Ｋまたは２Ｋのサイズである。プログラムの速度をさらに上げるために、様々な種類のキャッシュ交換アルゴリズムが使用される。ＣＰＵは、主メモリからの命令を実行したい場合、主メモリからの命令をキャッシュ中に入れ、次いでそれらの命令を実行する。これで、キャッシュは本当に速いので、コンピュータは、命令をキャッシュからＣＰＵ中に非常に迅速に取り出し、次いでそれらの命令を実行することができる。それに比較した場合、コンピュータが主メモリから命令を取り出す場合、コンピュータは、命令を実行するのにはるかに長い時間を要する。
【０００７】
一般に、プログラムは命令を密なループ内で実行し、命令が繰り返し実行される場合、命令のシーケンスを主メモリ中ではなくキャッシュ中に記憶しておくことがより効率的であり、したがってこれによりプログラムの実行の速度が上がる。しかしながら、ＣＰＵによって実行されている命令のシーケンスのサイズが本当に大きい場合、例えばキャッシュの代表的なサイズである１Ｋよりも大きい場合、コンピュータは、キャッシュ中にロードされた任意の命令を再使用することができなくなる。これは、ロードすべき後続の命令用の空きをつくるために命令をキャッシュからパージしなければならないためであり、これは極めて非効率的である。したがって、プロファイラが計測命令をループ内に入れた場合、ループ内の命令の数が増加し、ループ命令シーケンスがキャッシュ・サイズよりも大きくなる。このことは、ループがキャッシュ中に収まらず、実行すべき各命令を主メモリから取り出さなければならず、したがってプログラムの実行に要する時間が増大することを意味する。したがって、従来技術のプロファイラは、プロファイルを作成するループのサイズを大きくし、ループがキャッシュ・メモリ中に収まらなくなり、主メモリ中に記憶しなければならなくなる。主メモリはキャッシュ・メモリよりもかなり遅いので、従来技術のプロファイラは、ループの正確な実行時間を決定することができない。
【０００８】
ループに関する特性を決定するために、コンパイラは、区間分析と呼ばれるアルゴリズムなど標準のアルゴリズムを使用して、ループを認識する。区間分析では、ループのエントリ点および終了点を決定する。ループに関する情報を収集するために、従来技術のプロファイラは、ループ内のエントリ点にいくつかの計測スロットを配置し、それによりプロファイラは特定のループに入ったことを知る。また、プロファイラは、終了点にいくつかの計測スロットを配置し、それによりプロファイラはループから出たか否かを決定することができる。これらの計測スロットは制御がループに出入りし、かつプロファイラがループに関する情報を収集する場所であるので、これらの計測スロットの配置は非常に重要である。
【０００９】
【発明が解決しようとする課題】
従来技術の技法は、単一のエントリ点および単一または複数の終了点を有するループに対してのみ作用する。これは、この技法が関数（ｆｕｎｃｔｉｏｎ：関数、機能）レベルのプロファイル作成から派生したものであり、関数が１つのエントリ点および１つの終了点しか持たないためである。計測スロットは、制御が関数に入ったこと、および制御が関数から出たことを示すために、関数のエントリ点の直前、次いで関数の終了点の直後に配置される。この技法は、ループに関する情報を収集するために適していた。しかしながら、ループは一般に関数とは異なり複数のエントリ点および複数の終了点を有するので、関数よりも情報を収集することが困難である。
【００１０】
このように従来技術のプロファイラおよびプロファイル作成技法は、ループの挙動および特性を変更し収集された情報を信頼性のないものにしてしまう。さらに、従来技術のプロファイラおよびプロファイル作成技法は、多数のタイプのループ、特に複数のエントリ点を有するループまたは共通の出口を有するネスト・ループのプロファイルを作成することができない。
【００１１】
【課題を解決するための手段】
上記その他の目的、特徴および技術的利点は、ループの挙動に大きな影響を及ぼすことなく、多数の様々なタイプのループに関する情報を収集することができるシステムおよび方法によって達成される。様々なタイプのループは、ネスト・ループ、共通の出口を有するループ、複数のエントリ点を有するループ、および複数の終了点を有するループである。本発明は、これらの様々なタイプのすべてのループまたはその組合せについて同様に情報を収集することができる。本発明は、ループのすべてのエントリ点に計測スロットを配置し、またループのすべての終了点に計測スロットを配置することによって動作するが、スロットはループ本体外に配置する。本発明はまた、分岐が終了点でループから取り出される態様、および分岐がエントリ点でループ内に取り入れられる態様を変更する。こうして、計測スロットをループ外のエントリ点および終了点のところに配置することによって、ループの性能に全く影響を及ぼさず、したがってループ実行に関する正確な情報を容易に決定することができる。
【００１２】
以上、以下の本発明の詳細な説明がよりよく理解できるように本発明の特徴および技術的利点についてかなり概略的に説明した。以下では、本発明の請求の範囲の主題をなす本発明の追加の特徴および利点について説明する。概念および開示した特定の実施形態は、本発明の同じ目的を達成する他の構造を修正または設計する基礎として容易に利用できることが当業者なら理解できよう。また、これらの均等な構成は、請求の範囲に記載されている本発明の精神および範囲から逸脱しないことが当業者なら理解できよう。
【００１３】
【発明の実施の形態】
本発明の理解を助けるために、従来技術のプロファイラ技法およびそれがどのようにして計測スロットをコンピュータ・コード中に配置するかを検討することが有利であると考えられる。
【００１４】
図１に、従来技術のプロファイラ技法のモデル１００を示す。コンパイラは、プログラム・ループをループ・コード１０２として示す。コードのこのセクションについてプロファイルを作成するために、プロファイラ１０１は、本体ループ１０７の直前かつループ・コード１０２のエントリ点の後にエントリ計測コード１０３を配置し、かつ本体ループ１０７の直後かつループ・コード１０２の終了点の前に終了計測コード１０４を配置する。プロファイラ１０１は、このループに関する情報を収集したい場合、入るかまたは出るべき特定のループを識別する命令を計測スロット１０９中に入れる。プロファイラ１０１は、データ・ポインタ１０５を割り振ってループに関するデータを収容することによって情報を収集する。アーク１１０は、計測スロットと、考慮中のプログラム構成に関するプロファイル作成データを収集するプロファイル作成ルーチンとの間での制御の委譲を示す。ループ・コード１０２からのアークは、制御がデータ収集ルーチンに委譲されることを示し、ループ・コード１０２へのアークは、制御が計測スロットに戻されることを示す。アーク１１１は、データが計測スロットからプロファイラのプロファイル・データ領域に戻されることを示す。このデータはすべて、プロファイラ１０１の制御下にある何らかのメモリまたはレジスタ領域１０６中に入れられる。
【００１５】
この従来技術の技法では、エントリ計測コード１０３および終了計測コード１０４を含むループ・コード１０２は、ループであると考えられる。プログラマは元々ループ本体１０７しか書いていないが、プロファイラ１０１は、エントリコード１０３および終了コード１０４を追加しており、またループ・コード１０２の末尾に終了コード１０４からエントリコードに走る分岐１０８を追加している。したがって、プロファイラはループを大幅に変更しており、したがってループ・コード１０２全体が実行用のループであると考えられる。したがって、このコード・シーケンス全体は、実行のためにキャッシュ中に記憶されるようにループ用のキャッシュに収まらなければならない。ループ本体１０７はループ・コード１０２よりもはるかに小さいことに留意されたい。ループ本体１０７がキャッシュ中に収まる場合であっても、ループ・コード１０２は大きすぎて収まらず、したがって、実行時、プロファイラ１０１によって変更されたプログラムは、キャッシュ・ミスをヒットする。このように、プロファイラによって収集されたループに関する情報は不正確になる。
【００１６】
ループは、プログラムの制御フロー・グラフ中の構造である。ループは、一般に、そのエントリ点および終了点によって特徴付けられる。エントリ点は、制御がループ外から入ることができるループ内の場所である。例えば、図２（Ａ）では、点Ｌ１  ２０１がループ２００のエントリ点である。ループの終了点は、制御がループから流れ出ることができるループ内の場所であり、点ＥＸ１  ２０２がループの終了点である。ループ２００は、Ｌ１  ２０１とＩＭ１  ２０３との間にコードを含む。さらに、ＥＸ１  ２０２は、ループ２００の外に出る点Ｅ１２０４への分岐を有し、したがって、ＥＸ１  ２０２は終了点であると考えられることに留意されたい。エントリ点および終了点がループ内にあるかどうかを検出するいくつかの適切な標準のアルゴリズムがある。
【００１７】
次に、ループに関するプロファイル作成情報を収集するために、エントリ点および終了点に配置された計測スロットは、いくつかの条件を満足しなければならない。満足しなければならない第１の条件は、ループのエントリ計測コードの実行が常にループの終了計測コードの実行の後で実施されることである。満足しなければならない第２の条件は、ループの終了計測コードがそのエントリ計測コードの実行の前に実行されないことである。満足しなければならない第３の条件は、ただ１つの終了計測コードがループのエントリ計測コードの実行の後で実行されることである。これら３つの設計基準は、エントリ計測スロットおよび終了計測スロットの配置に従わなければならない。
【００１８】
エントリ点は、ループの先頭またはループ内の点であり、そこで制御がループ外の少なくとも１つの点からそれに委譲される。ループ内には複数のエントリ点がある。例えば、図３（Ａ）では、点Ｌ１  ３０１および点Ｌ３  ３０２のところにある命令がループエントリ点である。これらのループエントリ点は、コンパイラ中にある標準のアルゴリズムを使用して検出される。
【００１９】
ループのエントリ点に対して計測スロットを配置するためには、次の規則を使用する。エントリ規則１：所要の数のエントリ計測スロットをループ内のループのエントリ点の直前に導入する。エントリ規則２：ループ外のすべての分岐命令のターゲットは、エントリ計測コードの第１の命令を指すように変更される。エントリ規則３：次いで、ループ内からループのエントリ点へのフォール・スルーがある場合、エントリ計測コードの第１の命令の前に、エントリ計測コードを迂回して分岐する分岐命令を入れる。これは、制御がループ内からループのエントリ点に流れたときにエントリ計測コードを実行しないようにするために必要である。
【００２０】
必要な計測スロットの数は、使用中のプロファイラ、またプロファイラがループに関して収集したい情報の様々なタイプに応じて異なる。例えば、必要なスロットの数は、プログラムの実行時間に関する収集情報と、ループ内のキャッシュ・ミスまたはキャッシュ・ヒットの合計数に関する情報の収集とで異なる。
【００２１】
フォール・スルーは、１つの命令から次の命令への制御の委譲である。制御の委譲は、分岐命令の一部として指定されたプログラム中の位置に対して制御を明示的に変更する分岐命令によってフォール・スルーなしに行われることに留意されたい。図３（Ａ）に示すように、点Ｌ２  ３０３は、制御をプログラム中のエントリ点Ｌ３  ３０２に委譲する、ループ３００の外にある分岐命令である。また、ループ内から点Ｌ３  ３０２へのフォール・スルーがある。制御は、ループ外からフォール・スルーを介してエントリ点Ｌ１  ３０１に委譲される。ループ３００は、Ｌ１  ３０１とＩＭ１３０４との間にコードを含む。
【００２２】
図３（Ｂ）に、ループエントリ点に対する計測配置規則に従った後の図３（Ａ）のコードを示す。エントリ規則１に従って、計測スロット３０５および３０９がそれぞれエントリ点Ｌ１  ３０１およびＬ３  ３０２の前に配置されている。エントリ規則２に従って、図３（Ａ）に示すように分岐命令Ｌ２  ３０３のターゲットであったＬ３を、そのターゲットエントリ点のエントリ計測コード３０７の第１の命令を指すポインタＰＬ３  ３０６に変更する。エントリ規則３に従って、エントリ点Ｌ３  ３０２への内部フォール・スルーの前に、エントリ点Ｌ３３０２に分岐する分岐命令ＢＬ３  ３０８を配置し、それによりエントリ計測スロット３０９の実行を回避する。
【００２３】
ループ計測スロット３０５はループ外に配置され、したがってこれらのスロットは命令キャッシュ・ミスまたはキャッシュ・ヒットに影響を及ぼさないことに留意されたい。しかしながら、計測スロット３０９はループ内に配置され、これらは、Ｌ３  ３０２がループ内に存在するエントリ点であるので必要である。
【００２４】
終了点には、暗示的終了と明示的終了の２つのタイプがある。暗示的終了は、分岐命令の失敗により制御がループから出される終了である。例えば、図２（Ａ）では、ＩＭ１  ２０３が暗示的終了である。したがって、定義によれば、ループ内には暗示的終了は１つしか存在しない。他の種類の終了は明示的終了であり、これらは、命令が制御をループ外に明示的に委譲する終了であり、したがって一般にこれは分岐命令である。図２（Ａ）では、点ＥＸ１  ２０２のところにある命令が明示的終了である。
【００２５】
ループの終了点に計測スロットを配置するためには、次の規則を使用する。暗示的終了規則：計測スロットを明示的終了の直後に追加する。明示的終了規則１：計測スロットを終了命令のターゲットのところに追加する。明示的終了規則２：終了のターゲットの前の命令から終了のターゲットへのフォール・スルーがある場合、計測コードをスキップする分岐を計測コードの第１の命令の前に追加する。明示的終了規則３：終了命令のターゲットを、終了計測コードの先頭を指すように変更する。
【００２６】
図２（Ｂ）に、ループ終了点に対する計測配置規則に従った後の図２（Ａ）のコードを示す。暗示的終了規則に従って、計測コードまたは計測スロット２０５を暗示的終了ＩＭ１  ２０３の後に配置した。明示的終了規則１に従って、計測コードまたは計測スロット２０６を終了命令ＥＸ１  ２０２のターゲットＥ１  ２０４のところに配置した。明示的終了規則２に従って、Ｅ１  ２０４に分岐する終了命令ＥＸ１  ２０２のターゲットＥ１  ２０４への内部フォール・スルーの前に分岐命令ＢＥ１  ２０７を配置し、それにより終了計測スロット２０６の実行を回避する。明示的終了規則３に従って、終了命令ＥＸ１  ２０２のターゲットを、終了計測コード２０６の先頭を指すポインタＰＥ１  ２０８に変更する。
【００２７】
終了計測スロット２０５および２０６はループ２００の外にあることに留意されたい。したがって、スロットは、このループが実行されているときにキャッシュに影響を及ぼさない。
【００２８】
図４（Ａ）に、外部ループ４０１および内部ループ４０２を有するネスト・ループ４００を示す。ループ４００はまた、ループ・ネスト４００全体から制御を取り出す終了点４０３を含む。すなわち、どちらのループも単一の出口から出る。内部ループ４０２および外部ループ４０１は、それぞれただ１つのエントリ点Ｌ１  ４０４およびＬ２  ４０５を含む。２つのループが存在するので、ループからの２つの暗示的終了のみ、すなわち内部ループ４０２用のＩＭ１  ４０６および外部ループ４０１用のＩＭ２  ４０７が存在する。ループ４０６は、Ｌ１  ４０４からＩＭ２  ４０７へのコードを含む。
【００２９】
図４（Ｂ）に、ループエントリ点およびループ終了点に対する計測配置規則に従った後の図４（Ａ）のコードを示す。エントリ規則１に従って、計測スロット４０８および４０９をそれぞれエントリ点Ｌ１  ４０４およびＬ２  ４０５の前に配置した。暗示的終了規則に従って、計測コードまたはスロット４１０および４１１をそれぞれ暗示的終了ＩＭ１  ４０６およびＩＭ２  ４０７の後に配置した。明示的終了規則１に従って、計測コードまたはスロット４１２および４１３を終了命令ＥＸ  ４０３のターゲットＥＸＩＴ  ４１４のところに配置した。どちらのループからもこの命令が出るので２組のスロットがある。明示的終了規則２に従って、ＥＸＩＴ  ４１４に分岐する終了命令ＥＸ  ４０３のターゲットＥＸＩＴ  ４１４への内部フォール・スルーの前に分岐命令Ｂ  ＥＸＩＴ  ４１５を配置し、それによりエントリ計測スロット４１２および４１３の実行を回避する。明示的終了規則３に従って、終了命令ＥＸ  ４０３のターゲットを、終了計測コード４１２の先頭を指すポインタＰＥＸＩＴ  ４１６に変更する。したがって、終了計測コードまたはスロットは、終了命令から入ったときにのみ実行される。
【００３０】
図５（Ａ）に、同じターゲットに出る複数の終了点を有するループ５００を示す。どちらも、ループの外にある同じ終了点Ｅ１  ５０３に分岐する２つの明示的終了点ＥＸ１  ５０１およびＥＸ２  ５０２がある。また、暗示的終了点ＩＭ１  ５０４がある。ループ５００はまた、１つの入力点Ｌ１  ５０５を有する。ループ５００は、Ｌ１  ５０５からＩＭ１  ５０４までのコードを含む。
【００３１】
図５（Ｂ）に、ループエントリ点およびループ終了点に対する計測配置規則に従った後の図５（Ａ）のコードを示す。エントリ規則１に従って、計測スロット５０６をエントリ点Ｌ１  ５０５の前に配置した。暗示的終了規則に従って、計測コードまたはスロット５０７を暗示的終了ＩＭ１  ５０４の後に配置した。明示的終了規則１に従って、計測コードまたはスロット５０８および５０９を終了命令ＥＸ１  ５０１およびＥＸ２  ５０２のターゲットＥ１  ５０３のところに配置した。この終了点から２つの終了命令が出るので２組のスロットがある。明示的終了規則２に従って、Ｅ１  ５０３に分岐する終了命令ＥＸ１  ５０１のターゲットＥ１  ５０３への内部フォール・スルーの前に分岐命令Ｂ  Ｅ１  ５１０を配置し、それによりエントリ計測スロット５０８の実行を回避する。明示的終了規則２に従って、Ｅ１  ５０３に分岐する終了命令ＥＸ２  ５０２のターゲットＥ１  ５０３への内部フォール・スルーの前に分岐命令Ｂ  Ｅ１  ５１１を配置し、それによりエントリ計測スロット５０９の実行を回避する。明示的終了規則３に従って、終了命令ＥＸ１  ５０１のターゲットを、終了計測コード５０８の先頭を指すポインタＰＥ１  ５１２に変更する。明示的終了規則３に従って、終了命令ＥＸ２  ５０２のターゲットを、終了計測コード５０９の先頭を指すポインタＰＥ２  ５１３に変更する。
【００３２】
図５（Ｂ）のループを慎重に検討すれば、ＰＥ２のところの計測コード５０９は不要であり、またＥＸ２のところの明示的終了はＰＥ１に分岐するように変更でき、なお同じ結果をもたらすことが分かる。したがって、計測スロット５０９、分岐命令Ｂ  Ｅ１  ５１１、およびターゲット・ポインタＰＥ２  ５１３はすべて冗長である。１組の計測スロット５０８、ならびに付随する分岐命令Ｂ  Ｅ１  ５１０、およびターゲット・ポインタＰＥ１  ５１２は必要である。これを達成するためには、任意の時刻に置換された終了ターゲットのリストを置換中に思い出し、置換する必要がある新しいターゲットをリストと比較して、ターゲットがすでに前の明示的終了命令によって処理されているかどうかを確認する。このようにすれば、より小さくかつより効率的なコードが得られる。これを図６に示す。図６は、明示的終了ＥＸ１  ５０１およびＥＸ２  ５０２がどちらも同じ終了計測コード５０８に分岐するポインタＰＥ１  ５１２を有することを示す。これが内部ループ内に存在する場合、この改善は、内部ループのサイズを小さくし、それにより内部ループがキャッシュに収まるようになるので非常に重要である。
【００３３】
比較すると、従来技術の技法は、計測をループ内のＬ１  ５０１の後、終了点ＥＸ１  ５０１およびＥＸ２  ５０２の前に配置した。本発明の技法は、ループ内から命令スロットをなくす。従来技術はまた、終了命令ＥＸ１  ５０１およびＥＸ２  ５０２をループ内の終了計測スロットの前で非条件（ｎｏｔ−ｃｏｎｄｉｔｉｏｎ）分岐で置き換え、終了ターゲットＥ１  ５０３への分岐を終了計測スロットの後に挿入した。したがって、従来技術は、各終了命令ごとに２つの分岐命令を挿入する。従来技術が２つの分岐を有することに対して、本発明の技法はまたループから出る際にとられる分岐の総数を少なくし、ただ１つの分岐をループの外に配置する。したがって、本発明の技法は、情報を収集する時間を短縮する。
【００３４】
以上、本発明およびその利点について詳細に説明したが、特許請求の範囲によって定義される本発明の精神および範囲から逸脱することなく本発明において様々な交換、代用および変更を行うことができることが理解できよう。
この発明は、例として次の実施形態を含む。
（１）  所定の数のエントリ計測スロット（３０５）をループのエントリ点（３０１）の前に挿入するステップと、所定の数の終了計測スロット（２０５）をループの暗示的終了点（２０３）の後に挿入するステップとを含む、プログラム・コードのセクション内に、プロファイル作成用に少なくとも１つのエントリ点および暗示的終了点を有するループ（２００、３００）を作成する方法。
（２）  セクションが、ループの外に配置された分岐命令（３０３）を含み、かつループ内にターゲット（３０２）を有し、分岐命令のターゲットを、エントリ計測スロットの第１の命令（３０７）を指示するように変更するステップを更に含む、１に記載の方法。
（３）  ループが入力計測スロット（３０９）へのフォール・スルーを有し、エントリ計測スロットの第１の命令の前にエントリ計測スロットを迂回して分岐する分岐命令（３０８）を挿入するステップを更に含む、１に記載の方法。
（４）  ループが、ループの外にあるターゲット（２０４）を有する少なくとも１つの明示的終了命令（２０２）を有する、１に記載の方法。
（５）  所定の数の第２の終了計測スロット（２０６）を明示的終了命令（２０２）のターゲット（２０４）の前に挿入するステップをさらに含む、４に記載の方法。
（６）  明示的終了命令のターゲットを、第２の終了計測スロット（２０６）の第１の命令（２０８）を指示するように変更するステップをさらに含む、５に記載の方法。
（７）  ループが、共通のターゲット（５０３）を参照する少なくとも２つの明示的終了命令（５０１、５０２）を有し、冗長な終了計測スロット（５０９）を除去するステップをさらに含む、６に記載の方法。
（８）  ターゲットを変更するステップによって交換されたターゲット（５０３）のリストを記憶するステップと、各ターゲットがリスト上にあるかどうかを決定するために各ターゲットをリストに比較するステップと、終了計測スロットの直後のターゲット（５０３）がリスト上にある場合に、終了計測スロット（５０９）を冗長なスロットに指定するステップとを含む、７に記載の方法。
（９）  セクションが、第２の終了計測スロットへのフォール・スルーを有し、第２の終了計測スロット（５０８）の第１の命令の前に第２の終了計測スロットを迂回して分岐する分岐命令（５１０）を挿入するステップをさらに含む、５に記載の方法。
（１０）  ループの暗示的終了点（５０４）を決定するステップと、ループの複数の明示的終了命令（５０１、５０２）を決定するステップと、ループの複数の終了命令の各明示的終了命令の各ターゲットの前に所定の数の第２の終了計測スロット（５０８、５０９）を挿入するステップとを含む、４に記載の方法。
【００３５】
【発明の効果】
この発明によると、計測スロットをエントリ点およびループ外の終了点のところに配置することによって、ループの性能に全く影響を及ぼさずにループ実行に関する正確な情報を容易に決定することができる。
【図面の簡単な説明】
【図１】従来技術のプロファイラ技法のモデルを示す図。
【図２】暗示的終了点および明示的終了命令を有するループを有するコードのセクションを示す図。
【図３】２つのエントリ点を有するループを有するコードのセクションを示す図。
【図４】ネスト・ループを有するコードのセクションを示す図。
【図５】共通のターゲットを有する複数の明示的終了命令を有するループを有するコードのセクションを示す図。
【図６】計測交換規則の改善を実施した後の図５（Ｂ）のコードを示す図。
【符号の説明】
２００、３００      ループ
２０３              暗示的終了点
２０５              終了計測スロット
３０１              エントリ点
３０５              エントリ計測スロット
【図１】
0003623360.tif 000002
【図２】
0003623360.tif 000003
【図３】
0003623360.tif 000004
【図４】
0003623360.tif 000005
【図５】
0003623360.tif 000006
【図６】
0003623360.tif 000007