プログラムの最適化装置、最適化方法および最適化プログラム
【課題】 関数呼び出しを含む複数の命令から構成されるバイナリ列を動的に書き換えることができる装置や方法を提供する。
【解決手段】 この装置は、トランザクションの排他制御を可能にするトランザクショナル・メモリを備える装置である。この装置は、プログラムを解釈し、プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部200と、指定された処理に応じて、所定のタイミングで複数の命令を用いて第2コードを生成する第2コード生成部201と、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むコード書込部202とを備える。
【解決手段】 この装置は、トランザクションの排他制御を可能にするトランザクショナル・メモリを備える装置である。この装置は、プログラムを解釈し、プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部200と、指定された処理に応じて、所定のタイミングで複数の命令を用いて第2コードを生成する第2コード生成部201と、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むコード書込部202とを備える。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数の命令から構成されるプログラムを動的に書き換えて最適化する装置、最適化する方法、およびその方法を実現するためのコンピュータ可読な最適化プログラムに関する。
【背景技術】
【0002】
コンピュータに所定の作業をさせるためのプログラムは、プログラミング言語を用いて記述されている。プログラミング言語には、コンピュータが直接解釈し、実行することができる機械語や、そのマシン語と一対一で対応し、マシン語に近いアセンブリ言語といった低級言語と、マシン語と一対一で対応せず、より人間が理解しやすいテキスト形式で記述されたC、C++、Java(登録商標)等の高級言語とがある。
【0003】
コンピュータは、アセンブリ言語または高級言語で記述されたプログラムを直接解釈し、実行することができないため、アセンブラまたはコンパイラと呼ばれるソフトウェアにより、コンピュータが直接解釈して実行することができる機械語へ変換し実行する。
【0004】
アセンブリ言語によるプログラムは、例えば、実行速度やプログラムサイズに制限があるアプリケーション実行時のコンパイラの最適化能力では実現することができない最適化作業を行いたい場合や、プログラマがCPUの動作を制御する必要がある場合や、メモリ容量や演算実行速度等のリソースに制約がある場合等に行われている。また、カーネルやデバイスドライバの開発等にもこのアセンブリ言語が用いられている。
【0005】
高級言語によるプログラムは、テキスト形式で記述することができることから、一般に広く行われている。このプログラムは、コンパイラにより機械語へ変換されるが、その際に一旦アセンブリ言語へ変換して出力し、アセンブラで機械語へ変換される。
【0006】
アセンブラには、高級言語で記述されたプログラムの中にアセンブリ言語による記述を含めるインライン・アセンブラと呼ばれるものがある。このインライン・アセンブラは、プログラムの実行時間の多くを占める部分をアセンブリ言語による記述に置き換えて最適化し、アセンブリ言語で記述したプログラムに近い実行速度を実現するものである。
【0007】
このようなアセンブリ言語によるプログラムや、インライン・アセンブラを用いることにより、プログラムを最適化し、プログラムの実行速度を向上させることが従来から行われている。プログラムの最適化技術の1つに、複数の命令から構成されるバイナリ列を動的に書き換える技術が知られている。
【0008】
例えば、コンペア・アンド・スワップ(CAS)命令といったCPUの特別な命令を用い、バイナリの動的な書き換えを行う技術がある。この技術は、あるメモリ位置の値を読み取り、それを記憶しておき、その値に基づき新しい値を計算し、その後、そのメモリ位置にその新しい値を格納するが、その際、計算に用いた値が書き換えるときにも記憶されていることを確認し、記憶されていない場合、最初から処理をやり直すというものである。このため、プロセッサ間の衝突を防ぐことができ、アトミックにメモリ位置を確認して変更することができる。
【0009】
また、ロードおよびストア命令をパッチ領域に分岐する分岐命令に置き換える技術がある(例えば、非特許文献1参照)。この技術は、対称型マルチプロセッシング環境において、命令を後埋めする技術で、オリジナル・コードの最初のワードのみを変更し、同期プロトコルが使用され、すべてのプロセッサが最終的に後埋めコードを参照することを保証するというものである。
【0010】
具体的には、図1(a)に示すオリジナル・コードの最初のワードである「nop」を、図1(b)に示すような「jmp Label3」へ変更する。「nop」は、何もしないことを意味する命令で、後に命令を追加する予定の場所にダミーとして置かれる。「jmp」は、分岐命令で、ある条件が成立した場合にのみ分岐する条件分岐と、無条件に分岐する無条件分岐とがあり、図1(b)は無条件分岐を示し、「Label3」へ無条件に分岐することを表している。機械語の命令列は、逐次実行されるので、Label1、Label2、Label3、戻ってLabel2の順に実行されるが、このような変更により、Label1、Label2をとばしてLabel3を実行した後、Label2を実行することができるので、プログラムの最適化を図ることができる。
【0011】
また、ハードウェア・トランザクショナル・メモリ(HTM)を用いて命令列であるバイナリ列を動的に書き換える技術がある(例えば、特許文献1参照)。マルチコア・プロセッサでは、並列に実行されるスレッドがデータを共有して扱う共有メモリ型の並列プログラムが用いられることが多いが、アクセスが競合しないようにする手法として、ロックを用いる手法や、ロックを用いないHTMと呼ばれる手法がある。
【0012】
このHTMは、ハードウェアとして実装されるトランザクショナル・メモリであり、共有リソースに対するロックを事前に行うのではなく、実行しているスレッドの各々がそのコピーをローカルにもっていて、処理が終了した時点でその共有リソースの値とローカルにもつコピーの値が変更されていないことを確認し、その処理結果を一気に書き込み、他のスレッドにより書き換えられている場合はそれらの値が変更されているため、処理そのものを廃棄してやり直すというものである。ここで、トランザクションとは、1つのスレッドで実行される一連の処理をまとめたものである。
【0013】
この技術では、バイナリ列を書き換えるとき、メモリのストアをトランザクションで行う。このため、トランザクションの処理が他のトランザクションの処理と競合しない限り、バイナリ列を書き換えることができ、競合した場合であっても、初めから再実行されるので、その再実行されるときに競合しない限り、バイナリ列を書き換えることができる。
【先行技術文献】
【特許文献】
【0014】
【特許文献1】米国特許出願公開第2009/0006750号明細書
【非特許文献】
【0015】
【非特許文献1】Bowen Alpern, Mark Charney, Jong-Deok Choi, Anthony Cocchi, Derek Lieber,“Dynamic Linking on a Shared-Memory Multiprocessor”、[online]、1999年、インターネット、<URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8877&rep=rep1&type=pdf>
【発明の概要】
【発明が解決しようとする課題】
【0016】
上記のCAS命令を用いてバイナリ列を動的に書き換える手法では、高々1〜2命令の書き換えしかできない。これでは、複数の命令から構成されるバイナリ列を動的に書き換えることはできない。
【0017】
上記の分岐命令に置き換える手法では、分岐命令が増加し、コード・サイズも増加することから、命令キャッシュ・ミスが増加するという問題がある。また、この手法も、1命令のみ書き換えるので、複数の命令から構成されるバイナリ列を動的に書き換えることはできない。
【0018】
上記のHTMを用いる手法では、バイナリ列を動的に書き換えることは可能であるが、書き換え対象のバイナリ列に関数呼び出しを含むことができない。これは、例えばスレッド1が元のバイナリ列を実行しているときにスレッド2が書き換えを行う場合、スレッド1が実行している関数が呼び出し先の関数であれば、この時点では元のバイナリ列を実行していないので、スレッド2によるバイナリ列の書き換えは失敗しないからである。このため、スレッド1が呼び出し元に戻ったときには、バイナリ列が書き換えられているという状態となり、これでは正しい実行結果を得ることができない。
【0019】
呼び出される関数を呼び出し元に展開するインライニングという最適化技術があるが、この技術では、コード・サイズの増加を防止するために、コード・サイズがある閾値に達したところでインライニングが終了する。また、Java(登録商標)のような動的にクラスをロードする言語で、呼び出し対象の関数の実体がコンパイル時に不明である場合は、インラインすることができない。このため、インラインされずに残された関数呼び出しをインラインするには、元の関数を再コンパイルしなければならない。これではコンパイル・コストがかかるという問題がある。
【0020】
また、HTMを用いた最適化技術には、投機実行される分岐を伴う処理に対し、ホット・トレースから制御依存による制約を取り除いて最適化を行う技術がある。この技術では、コンパイル時に条件分岐でアボートする命令のある分岐先を削除してトレースを作成し、実行時にアボートが頻発すればそのトレースを廃棄し、再コンパイルして新たなトレースを作成するというものである。これも、再コンパイルが必要であるため、コンパイル・コストがかかるという問題がある。
【0021】
したがって、関数呼び出しを含む複数の命令から構成されるバイナリ列を動的に書き換えることができ、また、再コンパイルすることなく、関数呼び出し処理を動的にインラインし、トレースを新たなトレースに動的に置き換えることができる装置や方法の提供が望まれていた。
【課題を解決するための手段】
【0022】
本発明は、上記課題に鑑み、トランザクションの排他制御を可能にするトランザクショナル・メモリを備える装置において、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部と、指定された処理に応じて、所定のタイミングで複数の命令を用いて第2コードを生成する第2コード生成部と、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むコード書込部とを備える、プログラムの最適化装置を提供することができる。
【0023】
トランザクショナル・メモリを用いた処理では、トランザクションが投機実行されるが、他のスレッドのメモリ・アクセスと競合してアトミックにトランザクションを実行することができない場合、トランザクションを停止し、それまでの処理を破棄し、再実行する。これにより、トランザクションの排他制御を実現している。このため、指定された処理に対し、トランザクションの開始命令と終了命令とを挿入してトランザクションを構成することにより、他のスレッドのメモリ・アクセスと競合した場合に、確実にトランザクションを停止し、再実行することができるので、正しい実行結果を得ることができる。
【0024】
ここで、投機実行とは、プログラムが途中で条件分岐している場合に、分岐した先の処理を予め実行しておくことをいい、アトミックとは、他のスレッドからトランザクション内の各命令による処理が1つの処理に見え、途中経過が観測されないことを意味する。
【0025】
指定された処理は、例えば、関数呼び出し処理や分岐を伴う処理である。関数呼び出し処理は、その関数を呼び出すために、引数の設定、関数の呼び出し、返り値の読み出しを含み、複数の命令として、引数を設定する命令、関数を呼び出す命令、返り値を読み出す命令を含む。分岐を伴う処理は、少なくとも1つの分岐を含み、複数の命令として、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む。
【0026】
第2コード生成部は、具体的には、所定のタイミングとして、プログラムの実行中に呼び出した関数を解釈した際、それに応答して、命令列内の関数を呼び出す命令を、その呼び出した関数内の値を読み出す命令で置換し、置換した値を読み出す命令内のパラメータを変更し、命令列内の引数を設定する命令および返し値を読み出す命令を含む不要な命令群を削除して、最適化した第2コードを生成する。
【0027】
この最適化装置は、指定された処理を実行するための複数の命令から構成される命令列をトランザクションで囲み、その囲まれた命令列に基づき、最適化したコードを作り、それをその命令列上に書き込むことで、関数呼び出しを含む複数の命令から構成されるバイナリ列を動的に書き換えることができる。また、実行時にコンパイルするのは呼び出し先の関数のみであるため、プログラムを再コンパイルすることなく、関数呼び出し処理を動的にインラインすることができる。
【0028】
また、この最適化装置は、第2コードのコード・サイズが第1コードの命令列のコード・サイズ以下であるかを判定するサイズ判定部をさらに含むことができる。これにより、サイズ判定部が命令列のコード・サイズ以下と判定した場合に、これを受けて、コード書込部が、第1コードの命令列に第2コードを上書きすることができる。コード・サイズが閾値を超える場合は、命令列は書き換えない。
【0029】
上記のサイズ判定部とは別に、プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定する頻度判定部を含むことができる。この場合、第2コード生成部は、上記の所定のタイミングとして、プログラムを解釈した際の分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された分岐先の直前の分岐命令までの一連の制御フローである、第2コードを構成するためのトレースを生成する。
【0030】
また、プログラムの実行中に分岐先の命令がアボートした回数が設定値を超えたか否かを判定するアボート判定部と、その設定値を超えたと判定した場合に、アボートを発生させた命令を含まないトレースを、第2コード生成部が生成した複数のトレースの中から検索するトレース検索部とを含むことができる。この場合、コード書込部は、トランザクション内で第1コードの一部に、トレース検索部により検索されたトレースから構成される第2コードを書き込む。
【0031】
上記の第1コード生成部、第2コード生成部、コード書込部に加えて、頻度判定部、アボート判定部、トレース検索部を含む構成を採用することで、実行頻度から第1トレースを作り、それをトランザクションで囲んで第1コードを生成し、この第1トレースから少なくとも1つの第2トレースを作り、これにトランザクション終了命令を挿入して第2コードを生成し、アボートが頻発する場合に、生成した第2コードの中からアボートしないものを検索して選び、それを書き込むので、プログラムを再コンパイルすることなく、トレースを新たなトレースに動的に置き換えることができ、アプリケーションの性能を向上させることができる。
【0032】
本発明では、上述したプログラムの最適化装置のほかに、その最適化装置において行われる最適化方法も提供できる。この方法は、トランザクショナル・メモリを備えるプログラムの最適化装置により実行され、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成するステップと、指定された処理に応じて、プログラムを解釈した際またはプログラムの実行中に複数の命令を用いて第2コードを生成するステップと、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むステップとを含んで構成される。
【0033】
また、その方法を実現するための装置可読な最適化プログラムも提供することができる。この最適化プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納して提供することができ、PC等のコンピュータにより読み出し実行することにより、そのコンピュータを最適化装置として機能させることができる。
【図面の簡単な説明】
【0034】
【図1】ロードおよびストア命令をパッチ領域に分岐する分岐命令に置き換える前後のプログラムを例示した図。
【図2】本発明のプログラムの最適化装置のハードウェア構成の一例を示した図。
【図3】本発明のプログラムの最適化装置の機能ブロック図。
【図4】関数呼び出しを実行するためのコード、それをコンパイルしたコードを例示した図。
【図5】関数呼び出し処理を実行するための命令列を上書きして最適化する処理の流れを示したフローチャート図。
【図6】呼び出し先のコード、それをコンパイルしたコードを例示した図。
【図7】命令を置き換え、不要な命令を削除して最適化されたコードを例示した図。
【図8】制御フローグラフを例示した図。
【図9】第1トレースおよび第2トレースを例示した図。
【図10】第1コード上に第2コードを書き込み、最適化されたコードを例示した図。
【図11】第1トレースに第2トレースを書き込み、最適化する処理の流れを示したフローチャート図。
【発明を実施するための形態】
【0035】
以下、本発明を図面に示した具体的な実施の形態に沿って説明するが、本発明は、後述する実施の形態に限定されるものではない。図2は、本発明のプログラムの最適化装置のハードウェア構成を例示した図である。この最適化装置100は、上述したアセンブリ言語、C、C++、Java(登録商標)等のプログラミング言語により記述された、処理対象のプログラムを受け取り、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列を書き換え、そのプログラムを最適化する装置である。以下、単にプログラムと記載されるものは、この処理対象のプログラムを意味する。
【0036】
この最適化装置100は、上記の処理を実現するための最適化プログラムを格納し、それを実行することができる装置であってもよく、PC、サーバ、ワークステーション等を最適化装置とすることが可能である。
【0037】
最適化装置100は、ハードウェアとして例えば、ホスト・コントローラ101により相互に接続されるCPU102と、RAM103と、グラフィック・コントローラ104および表示装置105を備える周辺装置と、入出力コントローラ106によりホスト・コントローラ101に接続される通信インタフェース107と、ハードディスク・ドライブ(HDD)108、CD/DVDドライブ109等を備える入出力装置と、入出力コントローラ106に接続されるROM110と、入出力チップ111を備えるレガシー入出力装置とを含んで構成することができる。この装置はそのほかに、記録媒体の1つとして使用されるSDカードに記録された最適化プログラム、処理対象のプログラム、その他プログラムやデータを読み取るSDカード・リーダ等を含むことができる。
【0038】
ホスト・コントローラ101は、RAM103と、高い転送レートでRAM103をアクセスするCPU102およびグラフィック・コントローラ104とを接続する。CPU102は、ROM110およびRAM103に格納された上記の最適化プログラム等に基づいて動作し、各部の制御を行う。このCPU102は、並列処理が可能なマルチプロセッサとされ、HTM102aを含んで構成される。HTM102aは、ハードウェアとして実装されるトランザクショナル・メモリで、上述したように、共有リソースに対するロックを事前に行うのではなく、実行しているスレッドの各々がそのコピーをローカルにもち、処理が終了した時点でその共有リソースの値とローカルにもつコピーの値が変更されていないことを確認し、その処理結果を一気に書き込むことができる。また、HTM102aは、他のスレッドにより書き換えられている場合は、それらの値が変更されているため、処理そのものを廃棄してやり直すことができる。
【0039】
グラフィック・コントローラ104は、CPU102等がRAM103内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置105上に表示させる。グラフィック・コントローラ104は、CPU102等が生成する画像データを格納するフレーム・バッファを、このグラフィック・コントローラ104の内部に備えることもできる。
【0040】
入出力コントローラ106は、ホスト・コントローラ101と、比較的高速な入出力装置である通信インタフェース107、HDD108、CD/DVDドライブ109を接続する。通信インタフェース107は、ネットワークを介して他の装置と通信する。HDD108は、上記の最適化プログラムやその他のプログラム、各種データを格納することができる。CD/DVDドライブ109は、CD-ROMやDVDに上記最適化プログラム、処理対象のプログラム、その他のプログラム、各種データが記録されている場合、それらを読み取り、RAM103を介して入出力チップ111に提供することができる。
【0041】
入出力コントローラ106は、ROM110と、入出力チップ111等の比較的低速な入出力装置とが接続される。ROM110は、HDD108からOSをロードして起動するためのブート・プログラムや、コンピュータや機器の初期設定情報等を記録したファームウェア等を格納する。入出力チップ111は、パラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各部の入出力装置を接続する。
【0042】
最適化プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納されてユーザに提供される。この最適化プログラムは、この記録媒体から読み出され、入出力コントローラ106を介してHDD108等にインストールされ、CPU102により読み出されて実行される。本発明では、これに限られるものではなく、ネットワークに接続されたサーバのHDD等に格納され、このサーバのHDD等から読み出し、実行することも可能である。
【0043】
プログラムは、上記のプログラミング言語で記述されたプログラムであればいかなるプログラムやアプリケーションであってもよく、HDD108や記録媒体から読み出し、また、ネットワークに接続される他のPC等から受信して、コンパイルおよび実行することができる。
【0044】
図3は、本発明のプログラムの最適化装置の機能ブロック図である。この最適化装置は、トランザクショナル・メモリを備えるため、トランザクションの処理が競合した場合、一方のトランザクション処理をすべて破棄し、初めから再実行して、排他制御を実現することができる。トランザクションの処理を実現するために、この装置は、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部200を備える。
【0045】
また、この装置は、指定された処理に応じて、所定のタイミングで、具体的にはプログラムを解釈した際またはプログラムの実行中に、命令列の複数の命令を用い、命令を置換、削除、選択する等して最適化した第2コードを生成する第2コード生成部201と、トランザクション内で、上記のプログラムの実行中に第1コードの命令列を第2コードで上書きし、または上記のプログラムを解釈した際に第1コードの一部に第2コードを書き込むコード書込部202とを備える。
【0046】
第1コード生成部200は、プログラムをコンパイルすることにより解釈し、そのプログラム内の関数呼び出し処理や分岐を伴う処理といった予め指定された処理を実行するための複数の命令から構成される命令列を特定する。具体的には、例えば、図4(a)に示すコードをコンパイルして図4(b)に示すようなアセンブラ言語で記述された命令列を得、その中の引数の設定から返り値の読み出しまでの6つの命令から構成される命令列を特定する。
【0047】
図4(b)に示される6つの命令は、関数を呼び出すときに渡す値である引数を設定する命令と、呼び出し先の関数のアドレスを保持する関数テーブルをロードする命令、呼び出し先の関数のアドレスをロードしてレジスタに設定する命令、カウント・レジスタにコピーする命令、関数Foo2.getValue()を呼び出す命令、返り値を読み出す命令とされている。
【0048】
そして、第1コード生成部200は、その特定した命令列の前、すなわち引数を設定する命令の前に、トランザクションを開始させる開始命令「tbegin」を挿入し、その特定した命令列の後、すなわち返り値を読み出す命令の直後に、トランザクションを終了させる終了命令「tend」を挿入する。これにより、「tbegin」と「tend」で囲まれた部分の命令列が1つのトランザクションを構成し、このトランザクションをあるスレッドが実行しているときに、他のスレッドが書き換えを行おうとしても、それが任意の関数(例えば、関数add)の実行中であっても、その書き換えは失敗となり、正しい実行結果を得ることができる。
【0049】
プログラムのコンパイル時、上述したインライニングして、呼び出される関数を呼び出し元の関数に展開することができるが、このインライニングは、コンパイル時にプログラム内のすべての関数をインラインし、また、インラインすることができるわけではない。これは、コード・サイズの増加を防止するため、コード・サイズがある閾値に達したところでインラインを終了することから、残った関数はインラインされず、また、Java(登録商標)のような動的にクラスをロードする言語で記述されたプログラムは、実行時でなければ呼び出し対象の関数が確定しないことから、コンパイル段階ではその実体が不明でインラインすることができないためである。
【0050】
このインラインされずに残った関数呼び出しをインラインするためには、呼び出し元の関数を再コンパイルすればインラインすることができるが、本発明の最適化装置では、プログラムの実行により呼び出し対象の関数の実体が確定し、インラインすることができるようになった時点で、その呼び出し先の関数をコンパイルするのみで、インラインすることができる。
【0051】
第2コード生成部201は、呼び出し先の関数をコンパイルし、インラインすることができるようになったことに応答して、プログラム実行中に書き換え対象の命令列の中の複数の命令を用い、呼び出し先の関数の変数の値を読み出す命令と関数を呼び出す命令とを置換し、その置換した変数の値を読み出す命令のパラメータを変更し、これによって不要となった命令を削除して、第2コードを生成する。
【0052】
コード書込部202は、第2コードが生成されたことに応答して、トランザクション内で第1コードの書き換え対象の命令列を第2コードで上書きする。これにより、実行されるプログラムは最適化されるので、プログラムの性能を向上させることができ、また、関数を呼び出すことなく、直接に変数の値を読み出すことができるので、処理速度を向上させることができる。
【0053】
図5に示すフローチャートを参照して、本発明のプログラムの最適化装置を用いて関数呼び出しをインラインする処理について詳細に説明する。この処理は、ステップ500から開始し、ステップ510で、まず、関数のコンパイル時にインラインすることができなかった関数呼び出し処理を実行するための命令列を特定する。具体的には、プログラムを解釈して、関数を呼び出す命令を探し、そのうち呼び出し元の関数に呼び出し先の関数が展開されていないものを特定する。そして、その関数を呼び出す命令に関連する、その関数へ渡す引数の値を設定する命令やその関数の返り値を読み出す命令等を特定し、これらの複数の命令から構成される命令列を書き換え対象の命令列と特定する。次に、ステップ520で、その書き換え対象として特定した命令列の前後にトランザクションの開始命令と終了命令を挿入し、第1コードを生成する。
【0054】
プログラムが、例えばJava(登録商標)といった動的にクラスをロードする言語で記述されたプログラムである場合、そのプログラムが実行されたときに関数の呼び出し先が確定し、この確定によりインラインが可能となった段階で、ステップ530において、その呼び出し先の関数をコンパイルする。この呼び出し先の関数は、図6(a)で示され、これをコンパイルすると、図6(b)に示すように、変数「value」の値を読み出す命令と、呼び出し元へ戻る命令の2つから構成されたコードへ変換される。
【0055】
再び図5を参照して、次にステップ540において、ステップ510でコンパイル時に生成した第1コードの中の関数を呼び出す命令、すなわち図4(b)に示す「bctrl」を、ステップ530でコンパイルして変換された変数の値を読み出す命令、すなわち図6(b)に示す「lwz r3,16(r3)」に置き換える。これにより、図7(a)に示すようなコードが生成され、呼び出し先の関数を呼び出すことなく、直接に変数の値を読み出すことが可能となる。
【0056】
続いてステップ550において、置き換えられた変数の値の読み出す命令に、変数の値の読み出しに必要な引数と、読み出す返り値とを代入し、これによって不要となった引数を設定する命令、関数テーブルをロードする命令、呼び出し先関数のアドレスをロードする命令、返り値を読み出す命令を削除し、第2コードを生成する。
【0057】
第2コードは、図7(b)に示すように、変数「value」の値を読み出す命令のみで表され、その他の命令が記述されていた部分には、何もしないという「nop」が書き込まれる。
【0058】
そして、ステップ560において、第2コードのコード・サイズが関数呼び出しを行う命令列のコード・サイズ以下であるかを判定する。コード・サイズは、そのコードを格納するために必要とされるメモリ容量とすることができる。なお、この判定は、最適化装置が備えるサイズ判定部が行うことができる。
【0059】
図4に示す関数呼び出しを行う命令列は、6つの命令から構成され、図7に示す第2コードは、「nop」が5つあるものの、実質的に1つの命令から構成されることから、大幅に実行時間を削減することができているものと考えられる。このため、この実施例では、第2コードのコード・サイズが関数呼び出しを行う命令列のコード・サイズ以下であると判定される。
【0060】
ステップ560における判定で、関数呼び出し行う命令列のコード・サイズを超える場合は、コード・サイズが増加することからインラインを行うことなく、ステップ580の終了へ進む。
【0061】
一方、そのコード・サイズ以下である場合は、ステップ570へ進み、トランザクション内で関数呼び出しを行う命令列上にこの第2コードを上書きする。上書きは、命令列を構成する「ori r3, r5, 0」の上に「lwz r8, 16(r5)」を書き込み、それ以降の命令上に「nop」を書き込むことにより行われる。この上書きが終了したところで、ステップ580へ進み、この処理を終了する。このようにコードを上書きするので、プログラムのサイズが大きくなることはなく、プログラムの実行時に必要とされるメモリ・サイズが増加し、メモリ不足や処理速度が低下するといった問題が生じることはない。
【0062】
これまで、指定された処理として関数呼び出し処理を例に挙げ、再コンパイルすることなくインラインしてプログラムを最適化することについて詳細に説明してきた。指定された処理はこれに限られるものではなく、分岐を伴う処理を挙げることができる。この分岐を伴う処理は、分岐命令を含む命令列により実現されることから、分岐命令を探すことにより見分けることができる。
【0063】
プログラムによる処理は、図8に示すように制御フローグラフによって表すことができる。この制御フローグラフは、プログラムを実行した場合に通過する可能性がある全パスをグラフで表したものであり、四角は基本ブロックを示し、基本ブロックの矢印は基本ブロック間の制御の流れを示すエッジである。基本ブロック内には、制御の遷移のない一連の命令列が含まれる。図8中では、基本ブロックAの最後で、「br1」で示される条件付分岐命令を実行し、いずれかの分岐先へ進み、その分岐先の命令列を実行後、基本ブロックDへ進み、「br2」で示される条件付分岐命令を実行し、いずれかの分岐先へ進み、その分岐先の命令列を実行するような流れとなっている。ここで、条件付分岐とは、条件判定を行い、その条件を満足した場合に一方の分岐先へ飛び、満足しない場合には他方の分岐先へ飛ぶというものである。これに対し、条件付アボート命令は、ある条件が成立した際、トランザクションをアボートさせ、命令の実行をトランザクションの先頭に戻すための命令である。
【0064】
プログラムの実行中、最適化等のために、条件付分岐命令を実行する際、その成立回数および不成立回数を計測し、それを履歴情報として記録することができる。分岐先の命令が正常に実行されれば、成立回数が1つ増加し、それ以外では不成立回数が1つ増加するように計測される。この計測は、例えばカウンタを用いて行うことができる。成立回数と不成立回数は、実行頻度(%)を算出するために用いられ、実行頻度が高いほど成立回数が多く、不成立回数が少ないことを示す。履歴情報は、上記回数に限られるものではなく、算出された実行頻度であってもよい。なお、実行頻度は、成立回数を全回数で除し、100を乗算した値とすることができる。
【0065】
図8では、条件付分岐命令「br1」を実行した後、向かって左側の基本ブロックBの実行頻度が90%、右側の基本ブロックCの実行頻度が10%となっており、次の条件付分岐命令「br2」を実行した後、向かって左側の基本ブロックEの実行頻度が70%、右側の基本ブロックFの実行頻度が30%となっている。
【0066】
これを基に、第1コード生成部200は、プログラムのコンパイル時に、実行頻度が高い基本ブロックを選択しながら第1トレースを生成する。図8に示す制御フローグラフを参照して第1トレースを生成する場合、図9(a)に示すように、実行頻度が高い基本ブロックを選択し、基本ブロックA、B、D、Eから構成されるトレースが生成される。このとき、基本ブロックA、Dの中の条件付分岐命令「br1」、「br2」は、トレースに含まれない基本ブロックに分岐する可能性があるため、条件付アボート命令「ab1」、「ab2」へと変更される。
【0067】
プログラムのコンパイル時、第1コード生成部200により第1トレースが生成されたことに応答して、最適化装置が備える頻度判定部が、第1トレース内の命令列を後方からたどり、実行頻度が閾値以下のエッジを検出したかを判定する。そして、第2コード生成部201が、所定のタイミングとして、プログラムのコンパイル時の第1トレースが生成され、さらに閾値以下のエッジが検出されたことに応答して、その検出されたエッジ直前の分岐命令までのトレースを第2トレースとして生成する。
【0068】
例えば、経験値によって閾値を70%とした場合、図8に示す例では、基本ブロックDからEへのエッジの実行頻度が70%であるため、閾値以下であると判定し、図9(b)に示すような、そのエッジの直前の分岐命令「br2」までの、A、B、Dから構成されるトレースが第2トレースとして生成される。ここでは、このトレースのみが生成されるため、第2トレースは1つであるが、アボートの頻発等を考慮して2以上のトレースを生成しておくことができる。
【0069】
第1コード生成部200は、図10(a)に示すような、生成した第1トレースの前後にトランザクションの開始命令と終了命令を挿入し、第1コードを生成する。第2コード生成部201は、図10(b)に示すような、第2トレースの最後の分岐命令「br2」の直前にトランザクションの終了命令「tend」を挿入し、分岐命令「br2」の後に無条件分岐命令「b」を挿入し、第2コードを生成する。そして、実際にプログラムを実行し、第1コードの実行でアボートが頻発する場合、アボートが発生する命令を特定し、その命令を含まない第2トレースを検索する。この検索は、最適化装置が備えるトレース検索部により行うことができる。コード書込部202は、その命令を含まない第2トレースが存在する場合、その第2トレースから構成される第2コードを第1トレース上にトランザクション内で書き込む。なお、図10(b)に示す第2コードを書き込み、実行させると、第2トレースの実行が終了した後、基本ブロックEへ無条件にジャンプし、基本ブロックEを実行することになる。ここでは、図10(b)に示すトレースを例示したが、「ab2」でアボートが頻発する場合、条件分岐命令「br2」の条件成立の結果が基本ブロックFへ変わったことを意味することから、効率的に処理するために、基本ブロックA、B、D、Fから構成されるトレースを生成し、このトレースを採用することも可能である。
【0070】
図11を参照して、分岐を伴う処理を実行するための複数の命令から構成される命令列を書き換えて最適化する処理について説明する。ステップ1100からこの処理を開始し、ステップ1110において、プログラムをコンパイルする際、制御フローグラフを構築し、回数あるいは実行頻度を含む履歴情報を用い、実行頻度が高い方のエッジを選択して、プログラム中の実行頻度が高い一連の制御フローである第1トレースを生成する。第1トレースは、分岐命令を含む命令列と、少なくとも2つの分岐先となる命令もしくは命令列とを含んで構成される。
【0071】
ステップ1120では、頻度判定部が、ステップ1110において生成した第1トレースを後方からたどり、実行頻度が閾値以下のエッジを検出したかを判定する。閾値以下のエッジが検出された場合、ステップ1130へ進み、第2コード生成部201が、その検出されたエッジ直前の分岐命令までのトレースを第2トレースとして生成する。一方、エッジを検出しない場合、トレースが生成されないので、ステップ1200へ進み、処理を終了する。
【0072】
実行頻度は30%と低いものの、基本ブロックA、B、D、Fから構成されるトレースを第2トレースとして生成しておき、第1トレースのアボート命令「ab2」が相当な高確率でアボートするようであれば、このような第2トレースで第1トレースを置き換えることができる。このため、第2トレースは複数生成することができ、トレース検索部がそれら複数の第2トレースの中からアボートが頻発する命令を含まないトレースを検索し、そのトレースを書き込むことができる。
【0073】
ステップ1140において、第1コード生成部200は、プログラムの実行時に、ステップ1110で生成した第1トレースの前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令を挿入し、第1コードを生成する。
【0074】
次にステップ1150において、第2コード生成部201が、ステップ1130で生成した第2トレースの最後の分岐命令の直前にトランザクションの終了命令を挿入し、第2コードを生成する。これにより、トランザクション内で第2トレースを実行することができ、他のスレッドがトレースを書き込もうとしても失敗し、確実にトランザクションを実行することができる。
【0075】
プログラムの実行時に、ある命令でアボートが頻発する場合、ステップ1160で、最適化装置が備えるアボート判定部が、アボートする回数が設定値を超えたかどうかを判定する。回数でなく、アボート率(%)であってもよい。超えない場合は、第2コードを書き込むことなく、ステップ1200へ進み、この処理を終了する。
【0076】
これに対し、設定値を超えた場合は、ステップ1170へ進み、そのアボートが頻発する命令を含まない第2コードを、ステップ1150で生成した複数の第2コードの中から検索する。そして、ステップ1180において、第2コードが存在するかを判定し、存在する場合はステップ1190へ進み、その第2コードを、第1トレースの対応する部分にトランザクション内で書き込み、ステップ1200で処理を終了する。
【0077】
一方、存在しない場合はステップ1200へ進み、第1トレースに何も書き込むことなく、処理を終了する。これは書き込むべきトレースが存在しないからである。
【0078】
これまで、本発明の最適化装置および最適化方法について、図面を参照して詳細に説明してきたが、他の実施形態や、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【0079】
また、最適化方法は、コンピュータにより読み取り可能な最適化プログラムにより実現することができ、本発明では、この最適化プログラムを提供することも可能である。なお、最適化プログラムは、CD-ROM、DVD-ROM、SDカード、HDD等の記録媒体に格納して提供することができる。
【0080】
近年、複数のプロセッサ・コアを1つのチップ上に集積したマルチコア・プロセッサが広く普及しており、複数のスレッドを並列に実行することができるようになってきており、並列プログラミングの重要性が高まってきている。この並列プログラミングにおいて、ロックを用いた同期機構が広く用いられているが、ロックを用いると、デッドロックや不要なロックによる並列性の低下が生じることから、ロックを用いないトランザクショナル・メモリを用いた同期機構が提案されている。このため、様々なプロセッサにこのトランザクショナル・メモリが搭載される可能性があり、本発明のトランザクショナル・メモリを備える最適化装置の提供は、特に関数呼び出しを含むプログラムを動的に最適化することができる点で、アプリケーションの性能を向上させ、高速処理を実現することができるので有用である。
【符号の説明】
【0081】
100…最適化装置、101…ホスト・コントローラ、102…CPU、102a…トランザクショナル・メモリ、103…RAM、104…グラフィック・コントローラ、105…表示装置、106…入出力コントローラ、107…通信インタフェース、108…HDD、109…CD/DVDドライブ、110…ROM、111…入出力チップ、200…第1コード生成部、201…第2コード生成部、202…コード書込部
【技術分野】
【0001】
本発明は、複数の命令から構成されるプログラムを動的に書き換えて最適化する装置、最適化する方法、およびその方法を実現するためのコンピュータ可読な最適化プログラムに関する。
【背景技術】
【0002】
コンピュータに所定の作業をさせるためのプログラムは、プログラミング言語を用いて記述されている。プログラミング言語には、コンピュータが直接解釈し、実行することができる機械語や、そのマシン語と一対一で対応し、マシン語に近いアセンブリ言語といった低級言語と、マシン語と一対一で対応せず、より人間が理解しやすいテキスト形式で記述されたC、C++、Java(登録商標)等の高級言語とがある。
【0003】
コンピュータは、アセンブリ言語または高級言語で記述されたプログラムを直接解釈し、実行することができないため、アセンブラまたはコンパイラと呼ばれるソフトウェアにより、コンピュータが直接解釈して実行することができる機械語へ変換し実行する。
【0004】
アセンブリ言語によるプログラムは、例えば、実行速度やプログラムサイズに制限があるアプリケーション実行時のコンパイラの最適化能力では実現することができない最適化作業を行いたい場合や、プログラマがCPUの動作を制御する必要がある場合や、メモリ容量や演算実行速度等のリソースに制約がある場合等に行われている。また、カーネルやデバイスドライバの開発等にもこのアセンブリ言語が用いられている。
【0005】
高級言語によるプログラムは、テキスト形式で記述することができることから、一般に広く行われている。このプログラムは、コンパイラにより機械語へ変換されるが、その際に一旦アセンブリ言語へ変換して出力し、アセンブラで機械語へ変換される。
【0006】
アセンブラには、高級言語で記述されたプログラムの中にアセンブリ言語による記述を含めるインライン・アセンブラと呼ばれるものがある。このインライン・アセンブラは、プログラムの実行時間の多くを占める部分をアセンブリ言語による記述に置き換えて最適化し、アセンブリ言語で記述したプログラムに近い実行速度を実現するものである。
【0007】
このようなアセンブリ言語によるプログラムや、インライン・アセンブラを用いることにより、プログラムを最適化し、プログラムの実行速度を向上させることが従来から行われている。プログラムの最適化技術の1つに、複数の命令から構成されるバイナリ列を動的に書き換える技術が知られている。
【0008】
例えば、コンペア・アンド・スワップ(CAS)命令といったCPUの特別な命令を用い、バイナリの動的な書き換えを行う技術がある。この技術は、あるメモリ位置の値を読み取り、それを記憶しておき、その値に基づき新しい値を計算し、その後、そのメモリ位置にその新しい値を格納するが、その際、計算に用いた値が書き換えるときにも記憶されていることを確認し、記憶されていない場合、最初から処理をやり直すというものである。このため、プロセッサ間の衝突を防ぐことができ、アトミックにメモリ位置を確認して変更することができる。
【0009】
また、ロードおよびストア命令をパッチ領域に分岐する分岐命令に置き換える技術がある(例えば、非特許文献1参照)。この技術は、対称型マルチプロセッシング環境において、命令を後埋めする技術で、オリジナル・コードの最初のワードのみを変更し、同期プロトコルが使用され、すべてのプロセッサが最終的に後埋めコードを参照することを保証するというものである。
【0010】
具体的には、図1(a)に示すオリジナル・コードの最初のワードである「nop」を、図1(b)に示すような「jmp Label3」へ変更する。「nop」は、何もしないことを意味する命令で、後に命令を追加する予定の場所にダミーとして置かれる。「jmp」は、分岐命令で、ある条件が成立した場合にのみ分岐する条件分岐と、無条件に分岐する無条件分岐とがあり、図1(b)は無条件分岐を示し、「Label3」へ無条件に分岐することを表している。機械語の命令列は、逐次実行されるので、Label1、Label2、Label3、戻ってLabel2の順に実行されるが、このような変更により、Label1、Label2をとばしてLabel3を実行した後、Label2を実行することができるので、プログラムの最適化を図ることができる。
【0011】
また、ハードウェア・トランザクショナル・メモリ(HTM)を用いて命令列であるバイナリ列を動的に書き換える技術がある(例えば、特許文献1参照)。マルチコア・プロセッサでは、並列に実行されるスレッドがデータを共有して扱う共有メモリ型の並列プログラムが用いられることが多いが、アクセスが競合しないようにする手法として、ロックを用いる手法や、ロックを用いないHTMと呼ばれる手法がある。
【0012】
このHTMは、ハードウェアとして実装されるトランザクショナル・メモリであり、共有リソースに対するロックを事前に行うのではなく、実行しているスレッドの各々がそのコピーをローカルにもっていて、処理が終了した時点でその共有リソースの値とローカルにもつコピーの値が変更されていないことを確認し、その処理結果を一気に書き込み、他のスレッドにより書き換えられている場合はそれらの値が変更されているため、処理そのものを廃棄してやり直すというものである。ここで、トランザクションとは、1つのスレッドで実行される一連の処理をまとめたものである。
【0013】
この技術では、バイナリ列を書き換えるとき、メモリのストアをトランザクションで行う。このため、トランザクションの処理が他のトランザクションの処理と競合しない限り、バイナリ列を書き換えることができ、競合した場合であっても、初めから再実行されるので、その再実行されるときに競合しない限り、バイナリ列を書き換えることができる。
【先行技術文献】
【特許文献】
【0014】
【特許文献1】米国特許出願公開第2009/0006750号明細書
【非特許文献】
【0015】
【非特許文献1】Bowen Alpern, Mark Charney, Jong-Deok Choi, Anthony Cocchi, Derek Lieber,“Dynamic Linking on a Shared-Memory Multiprocessor”、[online]、1999年、インターネット、<URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.8877&rep=rep1&type=pdf>
【発明の概要】
【発明が解決しようとする課題】
【0016】
上記のCAS命令を用いてバイナリ列を動的に書き換える手法では、高々1〜2命令の書き換えしかできない。これでは、複数の命令から構成されるバイナリ列を動的に書き換えることはできない。
【0017】
上記の分岐命令に置き換える手法では、分岐命令が増加し、コード・サイズも増加することから、命令キャッシュ・ミスが増加するという問題がある。また、この手法も、1命令のみ書き換えるので、複数の命令から構成されるバイナリ列を動的に書き換えることはできない。
【0018】
上記のHTMを用いる手法では、バイナリ列を動的に書き換えることは可能であるが、書き換え対象のバイナリ列に関数呼び出しを含むことができない。これは、例えばスレッド1が元のバイナリ列を実行しているときにスレッド2が書き換えを行う場合、スレッド1が実行している関数が呼び出し先の関数であれば、この時点では元のバイナリ列を実行していないので、スレッド2によるバイナリ列の書き換えは失敗しないからである。このため、スレッド1が呼び出し元に戻ったときには、バイナリ列が書き換えられているという状態となり、これでは正しい実行結果を得ることができない。
【0019】
呼び出される関数を呼び出し元に展開するインライニングという最適化技術があるが、この技術では、コード・サイズの増加を防止するために、コード・サイズがある閾値に達したところでインライニングが終了する。また、Java(登録商標)のような動的にクラスをロードする言語で、呼び出し対象の関数の実体がコンパイル時に不明である場合は、インラインすることができない。このため、インラインされずに残された関数呼び出しをインラインするには、元の関数を再コンパイルしなければならない。これではコンパイル・コストがかかるという問題がある。
【0020】
また、HTMを用いた最適化技術には、投機実行される分岐を伴う処理に対し、ホット・トレースから制御依存による制約を取り除いて最適化を行う技術がある。この技術では、コンパイル時に条件分岐でアボートする命令のある分岐先を削除してトレースを作成し、実行時にアボートが頻発すればそのトレースを廃棄し、再コンパイルして新たなトレースを作成するというものである。これも、再コンパイルが必要であるため、コンパイル・コストがかかるという問題がある。
【0021】
したがって、関数呼び出しを含む複数の命令から構成されるバイナリ列を動的に書き換えることができ、また、再コンパイルすることなく、関数呼び出し処理を動的にインラインし、トレースを新たなトレースに動的に置き換えることができる装置や方法の提供が望まれていた。
【課題を解決するための手段】
【0022】
本発明は、上記課題に鑑み、トランザクションの排他制御を可能にするトランザクショナル・メモリを備える装置において、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部と、指定された処理に応じて、所定のタイミングで複数の命令を用いて第2コードを生成する第2コード生成部と、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むコード書込部とを備える、プログラムの最適化装置を提供することができる。
【0023】
トランザクショナル・メモリを用いた処理では、トランザクションが投機実行されるが、他のスレッドのメモリ・アクセスと競合してアトミックにトランザクションを実行することができない場合、トランザクションを停止し、それまでの処理を破棄し、再実行する。これにより、トランザクションの排他制御を実現している。このため、指定された処理に対し、トランザクションの開始命令と終了命令とを挿入してトランザクションを構成することにより、他のスレッドのメモリ・アクセスと競合した場合に、確実にトランザクションを停止し、再実行することができるので、正しい実行結果を得ることができる。
【0024】
ここで、投機実行とは、プログラムが途中で条件分岐している場合に、分岐した先の処理を予め実行しておくことをいい、アトミックとは、他のスレッドからトランザクション内の各命令による処理が1つの処理に見え、途中経過が観測されないことを意味する。
【0025】
指定された処理は、例えば、関数呼び出し処理や分岐を伴う処理である。関数呼び出し処理は、その関数を呼び出すために、引数の設定、関数の呼び出し、返り値の読み出しを含み、複数の命令として、引数を設定する命令、関数を呼び出す命令、返り値を読み出す命令を含む。分岐を伴う処理は、少なくとも1つの分岐を含み、複数の命令として、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む。
【0026】
第2コード生成部は、具体的には、所定のタイミングとして、プログラムの実行中に呼び出した関数を解釈した際、それに応答して、命令列内の関数を呼び出す命令を、その呼び出した関数内の値を読み出す命令で置換し、置換した値を読み出す命令内のパラメータを変更し、命令列内の引数を設定する命令および返し値を読み出す命令を含む不要な命令群を削除して、最適化した第2コードを生成する。
【0027】
この最適化装置は、指定された処理を実行するための複数の命令から構成される命令列をトランザクションで囲み、その囲まれた命令列に基づき、最適化したコードを作り、それをその命令列上に書き込むことで、関数呼び出しを含む複数の命令から構成されるバイナリ列を動的に書き換えることができる。また、実行時にコンパイルするのは呼び出し先の関数のみであるため、プログラムを再コンパイルすることなく、関数呼び出し処理を動的にインラインすることができる。
【0028】
また、この最適化装置は、第2コードのコード・サイズが第1コードの命令列のコード・サイズ以下であるかを判定するサイズ判定部をさらに含むことができる。これにより、サイズ判定部が命令列のコード・サイズ以下と判定した場合に、これを受けて、コード書込部が、第1コードの命令列に第2コードを上書きすることができる。コード・サイズが閾値を超える場合は、命令列は書き換えない。
【0029】
上記のサイズ判定部とは別に、プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定する頻度判定部を含むことができる。この場合、第2コード生成部は、上記の所定のタイミングとして、プログラムを解釈した際の分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された分岐先の直前の分岐命令までの一連の制御フローである、第2コードを構成するためのトレースを生成する。
【0030】
また、プログラムの実行中に分岐先の命令がアボートした回数が設定値を超えたか否かを判定するアボート判定部と、その設定値を超えたと判定した場合に、アボートを発生させた命令を含まないトレースを、第2コード生成部が生成した複数のトレースの中から検索するトレース検索部とを含むことができる。この場合、コード書込部は、トランザクション内で第1コードの一部に、トレース検索部により検索されたトレースから構成される第2コードを書き込む。
【0031】
上記の第1コード生成部、第2コード生成部、コード書込部に加えて、頻度判定部、アボート判定部、トレース検索部を含む構成を採用することで、実行頻度から第1トレースを作り、それをトランザクションで囲んで第1コードを生成し、この第1トレースから少なくとも1つの第2トレースを作り、これにトランザクション終了命令を挿入して第2コードを生成し、アボートが頻発する場合に、生成した第2コードの中からアボートしないものを検索して選び、それを書き込むので、プログラムを再コンパイルすることなく、トレースを新たなトレースに動的に置き換えることができ、アプリケーションの性能を向上させることができる。
【0032】
本発明では、上述したプログラムの最適化装置のほかに、その最適化装置において行われる最適化方法も提供できる。この方法は、トランザクショナル・メモリを備えるプログラムの最適化装置により実行され、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成するステップと、指定された処理に応じて、プログラムを解釈した際またはプログラムの実行中に複数の命令を用いて第2コードを生成するステップと、トランザクション内で第1コードの命令列を第2コードで上書きまたは第1コードの一部に第2コードを書き込むステップとを含んで構成される。
【0033】
また、その方法を実現するための装置可読な最適化プログラムも提供することができる。この最適化プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納して提供することができ、PC等のコンピュータにより読み出し実行することにより、そのコンピュータを最適化装置として機能させることができる。
【図面の簡単な説明】
【0034】
【図1】ロードおよびストア命令をパッチ領域に分岐する分岐命令に置き換える前後のプログラムを例示した図。
【図2】本発明のプログラムの最適化装置のハードウェア構成の一例を示した図。
【図3】本発明のプログラムの最適化装置の機能ブロック図。
【図4】関数呼び出しを実行するためのコード、それをコンパイルしたコードを例示した図。
【図5】関数呼び出し処理を実行するための命令列を上書きして最適化する処理の流れを示したフローチャート図。
【図6】呼び出し先のコード、それをコンパイルしたコードを例示した図。
【図7】命令を置き換え、不要な命令を削除して最適化されたコードを例示した図。
【図8】制御フローグラフを例示した図。
【図9】第1トレースおよび第2トレースを例示した図。
【図10】第1コード上に第2コードを書き込み、最適化されたコードを例示した図。
【図11】第1トレースに第2トレースを書き込み、最適化する処理の流れを示したフローチャート図。
【発明を実施するための形態】
【0035】
以下、本発明を図面に示した具体的な実施の形態に沿って説明するが、本発明は、後述する実施の形態に限定されるものではない。図2は、本発明のプログラムの最適化装置のハードウェア構成を例示した図である。この最適化装置100は、上述したアセンブリ言語、C、C++、Java(登録商標)等のプログラミング言語により記述された、処理対象のプログラムを受け取り、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列を書き換え、そのプログラムを最適化する装置である。以下、単にプログラムと記載されるものは、この処理対象のプログラムを意味する。
【0036】
この最適化装置100は、上記の処理を実現するための最適化プログラムを格納し、それを実行することができる装置であってもよく、PC、サーバ、ワークステーション等を最適化装置とすることが可能である。
【0037】
最適化装置100は、ハードウェアとして例えば、ホスト・コントローラ101により相互に接続されるCPU102と、RAM103と、グラフィック・コントローラ104および表示装置105を備える周辺装置と、入出力コントローラ106によりホスト・コントローラ101に接続される通信インタフェース107と、ハードディスク・ドライブ(HDD)108、CD/DVDドライブ109等を備える入出力装置と、入出力コントローラ106に接続されるROM110と、入出力チップ111を備えるレガシー入出力装置とを含んで構成することができる。この装置はそのほかに、記録媒体の1つとして使用されるSDカードに記録された最適化プログラム、処理対象のプログラム、その他プログラムやデータを読み取るSDカード・リーダ等を含むことができる。
【0038】
ホスト・コントローラ101は、RAM103と、高い転送レートでRAM103をアクセスするCPU102およびグラフィック・コントローラ104とを接続する。CPU102は、ROM110およびRAM103に格納された上記の最適化プログラム等に基づいて動作し、各部の制御を行う。このCPU102は、並列処理が可能なマルチプロセッサとされ、HTM102aを含んで構成される。HTM102aは、ハードウェアとして実装されるトランザクショナル・メモリで、上述したように、共有リソースに対するロックを事前に行うのではなく、実行しているスレッドの各々がそのコピーをローカルにもち、処理が終了した時点でその共有リソースの値とローカルにもつコピーの値が変更されていないことを確認し、その処理結果を一気に書き込むことができる。また、HTM102aは、他のスレッドにより書き換えられている場合は、それらの値が変更されているため、処理そのものを廃棄してやり直すことができる。
【0039】
グラフィック・コントローラ104は、CPU102等がRAM103内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置105上に表示させる。グラフィック・コントローラ104は、CPU102等が生成する画像データを格納するフレーム・バッファを、このグラフィック・コントローラ104の内部に備えることもできる。
【0040】
入出力コントローラ106は、ホスト・コントローラ101と、比較的高速な入出力装置である通信インタフェース107、HDD108、CD/DVDドライブ109を接続する。通信インタフェース107は、ネットワークを介して他の装置と通信する。HDD108は、上記の最適化プログラムやその他のプログラム、各種データを格納することができる。CD/DVDドライブ109は、CD-ROMやDVDに上記最適化プログラム、処理対象のプログラム、その他のプログラム、各種データが記録されている場合、それらを読み取り、RAM103を介して入出力チップ111に提供することができる。
【0041】
入出力コントローラ106は、ROM110と、入出力チップ111等の比較的低速な入出力装置とが接続される。ROM110は、HDD108からOSをロードして起動するためのブート・プログラムや、コンピュータや機器の初期設定情報等を記録したファームウェア等を格納する。入出力チップ111は、パラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各部の入出力装置を接続する。
【0042】
最適化プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納されてユーザに提供される。この最適化プログラムは、この記録媒体から読み出され、入出力コントローラ106を介してHDD108等にインストールされ、CPU102により読み出されて実行される。本発明では、これに限られるものではなく、ネットワークに接続されたサーバのHDD等に格納され、このサーバのHDD等から読み出し、実行することも可能である。
【0043】
プログラムは、上記のプログラミング言語で記述されたプログラムであればいかなるプログラムやアプリケーションであってもよく、HDD108や記録媒体から読み出し、また、ネットワークに接続される他のPC等から受信して、コンパイルおよび実行することができる。
【0044】
図3は、本発明のプログラムの最適化装置の機能ブロック図である。この最適化装置は、トランザクショナル・メモリを備えるため、トランザクションの処理が競合した場合、一方のトランザクション処理をすべて破棄し、初めから再実行して、排他制御を実現することができる。トランザクションの処理を実現するために、この装置は、プログラムを解釈し、そのプログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部200を備える。
【0045】
また、この装置は、指定された処理に応じて、所定のタイミングで、具体的にはプログラムを解釈した際またはプログラムの実行中に、命令列の複数の命令を用い、命令を置換、削除、選択する等して最適化した第2コードを生成する第2コード生成部201と、トランザクション内で、上記のプログラムの実行中に第1コードの命令列を第2コードで上書きし、または上記のプログラムを解釈した際に第1コードの一部に第2コードを書き込むコード書込部202とを備える。
【0046】
第1コード生成部200は、プログラムをコンパイルすることにより解釈し、そのプログラム内の関数呼び出し処理や分岐を伴う処理といった予め指定された処理を実行するための複数の命令から構成される命令列を特定する。具体的には、例えば、図4(a)に示すコードをコンパイルして図4(b)に示すようなアセンブラ言語で記述された命令列を得、その中の引数の設定から返り値の読み出しまでの6つの命令から構成される命令列を特定する。
【0047】
図4(b)に示される6つの命令は、関数を呼び出すときに渡す値である引数を設定する命令と、呼び出し先の関数のアドレスを保持する関数テーブルをロードする命令、呼び出し先の関数のアドレスをロードしてレジスタに設定する命令、カウント・レジスタにコピーする命令、関数Foo2.getValue()を呼び出す命令、返り値を読み出す命令とされている。
【0048】
そして、第1コード生成部200は、その特定した命令列の前、すなわち引数を設定する命令の前に、トランザクションを開始させる開始命令「tbegin」を挿入し、その特定した命令列の後、すなわち返り値を読み出す命令の直後に、トランザクションを終了させる終了命令「tend」を挿入する。これにより、「tbegin」と「tend」で囲まれた部分の命令列が1つのトランザクションを構成し、このトランザクションをあるスレッドが実行しているときに、他のスレッドが書き換えを行おうとしても、それが任意の関数(例えば、関数add)の実行中であっても、その書き換えは失敗となり、正しい実行結果を得ることができる。
【0049】
プログラムのコンパイル時、上述したインライニングして、呼び出される関数を呼び出し元の関数に展開することができるが、このインライニングは、コンパイル時にプログラム内のすべての関数をインラインし、また、インラインすることができるわけではない。これは、コード・サイズの増加を防止するため、コード・サイズがある閾値に達したところでインラインを終了することから、残った関数はインラインされず、また、Java(登録商標)のような動的にクラスをロードする言語で記述されたプログラムは、実行時でなければ呼び出し対象の関数が確定しないことから、コンパイル段階ではその実体が不明でインラインすることができないためである。
【0050】
このインラインされずに残った関数呼び出しをインラインするためには、呼び出し元の関数を再コンパイルすればインラインすることができるが、本発明の最適化装置では、プログラムの実行により呼び出し対象の関数の実体が確定し、インラインすることができるようになった時点で、その呼び出し先の関数をコンパイルするのみで、インラインすることができる。
【0051】
第2コード生成部201は、呼び出し先の関数をコンパイルし、インラインすることができるようになったことに応答して、プログラム実行中に書き換え対象の命令列の中の複数の命令を用い、呼び出し先の関数の変数の値を読み出す命令と関数を呼び出す命令とを置換し、その置換した変数の値を読み出す命令のパラメータを変更し、これによって不要となった命令を削除して、第2コードを生成する。
【0052】
コード書込部202は、第2コードが生成されたことに応答して、トランザクション内で第1コードの書き換え対象の命令列を第2コードで上書きする。これにより、実行されるプログラムは最適化されるので、プログラムの性能を向上させることができ、また、関数を呼び出すことなく、直接に変数の値を読み出すことができるので、処理速度を向上させることができる。
【0053】
図5に示すフローチャートを参照して、本発明のプログラムの最適化装置を用いて関数呼び出しをインラインする処理について詳細に説明する。この処理は、ステップ500から開始し、ステップ510で、まず、関数のコンパイル時にインラインすることができなかった関数呼び出し処理を実行するための命令列を特定する。具体的には、プログラムを解釈して、関数を呼び出す命令を探し、そのうち呼び出し元の関数に呼び出し先の関数が展開されていないものを特定する。そして、その関数を呼び出す命令に関連する、その関数へ渡す引数の値を設定する命令やその関数の返り値を読み出す命令等を特定し、これらの複数の命令から構成される命令列を書き換え対象の命令列と特定する。次に、ステップ520で、その書き換え対象として特定した命令列の前後にトランザクションの開始命令と終了命令を挿入し、第1コードを生成する。
【0054】
プログラムが、例えばJava(登録商標)といった動的にクラスをロードする言語で記述されたプログラムである場合、そのプログラムが実行されたときに関数の呼び出し先が確定し、この確定によりインラインが可能となった段階で、ステップ530において、その呼び出し先の関数をコンパイルする。この呼び出し先の関数は、図6(a)で示され、これをコンパイルすると、図6(b)に示すように、変数「value」の値を読み出す命令と、呼び出し元へ戻る命令の2つから構成されたコードへ変換される。
【0055】
再び図5を参照して、次にステップ540において、ステップ510でコンパイル時に生成した第1コードの中の関数を呼び出す命令、すなわち図4(b)に示す「bctrl」を、ステップ530でコンパイルして変換された変数の値を読み出す命令、すなわち図6(b)に示す「lwz r3,16(r3)」に置き換える。これにより、図7(a)に示すようなコードが生成され、呼び出し先の関数を呼び出すことなく、直接に変数の値を読み出すことが可能となる。
【0056】
続いてステップ550において、置き換えられた変数の値の読み出す命令に、変数の値の読み出しに必要な引数と、読み出す返り値とを代入し、これによって不要となった引数を設定する命令、関数テーブルをロードする命令、呼び出し先関数のアドレスをロードする命令、返り値を読み出す命令を削除し、第2コードを生成する。
【0057】
第2コードは、図7(b)に示すように、変数「value」の値を読み出す命令のみで表され、その他の命令が記述されていた部分には、何もしないという「nop」が書き込まれる。
【0058】
そして、ステップ560において、第2コードのコード・サイズが関数呼び出しを行う命令列のコード・サイズ以下であるかを判定する。コード・サイズは、そのコードを格納するために必要とされるメモリ容量とすることができる。なお、この判定は、最適化装置が備えるサイズ判定部が行うことができる。
【0059】
図4に示す関数呼び出しを行う命令列は、6つの命令から構成され、図7に示す第2コードは、「nop」が5つあるものの、実質的に1つの命令から構成されることから、大幅に実行時間を削減することができているものと考えられる。このため、この実施例では、第2コードのコード・サイズが関数呼び出しを行う命令列のコード・サイズ以下であると判定される。
【0060】
ステップ560における判定で、関数呼び出し行う命令列のコード・サイズを超える場合は、コード・サイズが増加することからインラインを行うことなく、ステップ580の終了へ進む。
【0061】
一方、そのコード・サイズ以下である場合は、ステップ570へ進み、トランザクション内で関数呼び出しを行う命令列上にこの第2コードを上書きする。上書きは、命令列を構成する「ori r3, r5, 0」の上に「lwz r8, 16(r5)」を書き込み、それ以降の命令上に「nop」を書き込むことにより行われる。この上書きが終了したところで、ステップ580へ進み、この処理を終了する。このようにコードを上書きするので、プログラムのサイズが大きくなることはなく、プログラムの実行時に必要とされるメモリ・サイズが増加し、メモリ不足や処理速度が低下するといった問題が生じることはない。
【0062】
これまで、指定された処理として関数呼び出し処理を例に挙げ、再コンパイルすることなくインラインしてプログラムを最適化することについて詳細に説明してきた。指定された処理はこれに限られるものではなく、分岐を伴う処理を挙げることができる。この分岐を伴う処理は、分岐命令を含む命令列により実現されることから、分岐命令を探すことにより見分けることができる。
【0063】
プログラムによる処理は、図8に示すように制御フローグラフによって表すことができる。この制御フローグラフは、プログラムを実行した場合に通過する可能性がある全パスをグラフで表したものであり、四角は基本ブロックを示し、基本ブロックの矢印は基本ブロック間の制御の流れを示すエッジである。基本ブロック内には、制御の遷移のない一連の命令列が含まれる。図8中では、基本ブロックAの最後で、「br1」で示される条件付分岐命令を実行し、いずれかの分岐先へ進み、その分岐先の命令列を実行後、基本ブロックDへ進み、「br2」で示される条件付分岐命令を実行し、いずれかの分岐先へ進み、その分岐先の命令列を実行するような流れとなっている。ここで、条件付分岐とは、条件判定を行い、その条件を満足した場合に一方の分岐先へ飛び、満足しない場合には他方の分岐先へ飛ぶというものである。これに対し、条件付アボート命令は、ある条件が成立した際、トランザクションをアボートさせ、命令の実行をトランザクションの先頭に戻すための命令である。
【0064】
プログラムの実行中、最適化等のために、条件付分岐命令を実行する際、その成立回数および不成立回数を計測し、それを履歴情報として記録することができる。分岐先の命令が正常に実行されれば、成立回数が1つ増加し、それ以外では不成立回数が1つ増加するように計測される。この計測は、例えばカウンタを用いて行うことができる。成立回数と不成立回数は、実行頻度(%)を算出するために用いられ、実行頻度が高いほど成立回数が多く、不成立回数が少ないことを示す。履歴情報は、上記回数に限られるものではなく、算出された実行頻度であってもよい。なお、実行頻度は、成立回数を全回数で除し、100を乗算した値とすることができる。
【0065】
図8では、条件付分岐命令「br1」を実行した後、向かって左側の基本ブロックBの実行頻度が90%、右側の基本ブロックCの実行頻度が10%となっており、次の条件付分岐命令「br2」を実行した後、向かって左側の基本ブロックEの実行頻度が70%、右側の基本ブロックFの実行頻度が30%となっている。
【0066】
これを基に、第1コード生成部200は、プログラムのコンパイル時に、実行頻度が高い基本ブロックを選択しながら第1トレースを生成する。図8に示す制御フローグラフを参照して第1トレースを生成する場合、図9(a)に示すように、実行頻度が高い基本ブロックを選択し、基本ブロックA、B、D、Eから構成されるトレースが生成される。このとき、基本ブロックA、Dの中の条件付分岐命令「br1」、「br2」は、トレースに含まれない基本ブロックに分岐する可能性があるため、条件付アボート命令「ab1」、「ab2」へと変更される。
【0067】
プログラムのコンパイル時、第1コード生成部200により第1トレースが生成されたことに応答して、最適化装置が備える頻度判定部が、第1トレース内の命令列を後方からたどり、実行頻度が閾値以下のエッジを検出したかを判定する。そして、第2コード生成部201が、所定のタイミングとして、プログラムのコンパイル時の第1トレースが生成され、さらに閾値以下のエッジが検出されたことに応答して、その検出されたエッジ直前の分岐命令までのトレースを第2トレースとして生成する。
【0068】
例えば、経験値によって閾値を70%とした場合、図8に示す例では、基本ブロックDからEへのエッジの実行頻度が70%であるため、閾値以下であると判定し、図9(b)に示すような、そのエッジの直前の分岐命令「br2」までの、A、B、Dから構成されるトレースが第2トレースとして生成される。ここでは、このトレースのみが生成されるため、第2トレースは1つであるが、アボートの頻発等を考慮して2以上のトレースを生成しておくことができる。
【0069】
第1コード生成部200は、図10(a)に示すような、生成した第1トレースの前後にトランザクションの開始命令と終了命令を挿入し、第1コードを生成する。第2コード生成部201は、図10(b)に示すような、第2トレースの最後の分岐命令「br2」の直前にトランザクションの終了命令「tend」を挿入し、分岐命令「br2」の後に無条件分岐命令「b」を挿入し、第2コードを生成する。そして、実際にプログラムを実行し、第1コードの実行でアボートが頻発する場合、アボートが発生する命令を特定し、その命令を含まない第2トレースを検索する。この検索は、最適化装置が備えるトレース検索部により行うことができる。コード書込部202は、その命令を含まない第2トレースが存在する場合、その第2トレースから構成される第2コードを第1トレース上にトランザクション内で書き込む。なお、図10(b)に示す第2コードを書き込み、実行させると、第2トレースの実行が終了した後、基本ブロックEへ無条件にジャンプし、基本ブロックEを実行することになる。ここでは、図10(b)に示すトレースを例示したが、「ab2」でアボートが頻発する場合、条件分岐命令「br2」の条件成立の結果が基本ブロックFへ変わったことを意味することから、効率的に処理するために、基本ブロックA、B、D、Fから構成されるトレースを生成し、このトレースを採用することも可能である。
【0070】
図11を参照して、分岐を伴う処理を実行するための複数の命令から構成される命令列を書き換えて最適化する処理について説明する。ステップ1100からこの処理を開始し、ステップ1110において、プログラムをコンパイルする際、制御フローグラフを構築し、回数あるいは実行頻度を含む履歴情報を用い、実行頻度が高い方のエッジを選択して、プログラム中の実行頻度が高い一連の制御フローである第1トレースを生成する。第1トレースは、分岐命令を含む命令列と、少なくとも2つの分岐先となる命令もしくは命令列とを含んで構成される。
【0071】
ステップ1120では、頻度判定部が、ステップ1110において生成した第1トレースを後方からたどり、実行頻度が閾値以下のエッジを検出したかを判定する。閾値以下のエッジが検出された場合、ステップ1130へ進み、第2コード生成部201が、その検出されたエッジ直前の分岐命令までのトレースを第2トレースとして生成する。一方、エッジを検出しない場合、トレースが生成されないので、ステップ1200へ進み、処理を終了する。
【0072】
実行頻度は30%と低いものの、基本ブロックA、B、D、Fから構成されるトレースを第2トレースとして生成しておき、第1トレースのアボート命令「ab2」が相当な高確率でアボートするようであれば、このような第2トレースで第1トレースを置き換えることができる。このため、第2トレースは複数生成することができ、トレース検索部がそれら複数の第2トレースの中からアボートが頻発する命令を含まないトレースを検索し、そのトレースを書き込むことができる。
【0073】
ステップ1140において、第1コード生成部200は、プログラムの実行時に、ステップ1110で生成した第1トレースの前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令を挿入し、第1コードを生成する。
【0074】
次にステップ1150において、第2コード生成部201が、ステップ1130で生成した第2トレースの最後の分岐命令の直前にトランザクションの終了命令を挿入し、第2コードを生成する。これにより、トランザクション内で第2トレースを実行することができ、他のスレッドがトレースを書き込もうとしても失敗し、確実にトランザクションを実行することができる。
【0075】
プログラムの実行時に、ある命令でアボートが頻発する場合、ステップ1160で、最適化装置が備えるアボート判定部が、アボートする回数が設定値を超えたかどうかを判定する。回数でなく、アボート率(%)であってもよい。超えない場合は、第2コードを書き込むことなく、ステップ1200へ進み、この処理を終了する。
【0076】
これに対し、設定値を超えた場合は、ステップ1170へ進み、そのアボートが頻発する命令を含まない第2コードを、ステップ1150で生成した複数の第2コードの中から検索する。そして、ステップ1180において、第2コードが存在するかを判定し、存在する場合はステップ1190へ進み、その第2コードを、第1トレースの対応する部分にトランザクション内で書き込み、ステップ1200で処理を終了する。
【0077】
一方、存在しない場合はステップ1200へ進み、第1トレースに何も書き込むことなく、処理を終了する。これは書き込むべきトレースが存在しないからである。
【0078】
これまで、本発明の最適化装置および最適化方法について、図面を参照して詳細に説明してきたが、他の実施形態や、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。
【0079】
また、最適化方法は、コンピュータにより読み取り可能な最適化プログラムにより実現することができ、本発明では、この最適化プログラムを提供することも可能である。なお、最適化プログラムは、CD-ROM、DVD-ROM、SDカード、HDD等の記録媒体に格納して提供することができる。
【0080】
近年、複数のプロセッサ・コアを1つのチップ上に集積したマルチコア・プロセッサが広く普及しており、複数のスレッドを並列に実行することができるようになってきており、並列プログラミングの重要性が高まってきている。この並列プログラミングにおいて、ロックを用いた同期機構が広く用いられているが、ロックを用いると、デッドロックや不要なロックによる並列性の低下が生じることから、ロックを用いないトランザクショナル・メモリを用いた同期機構が提案されている。このため、様々なプロセッサにこのトランザクショナル・メモリが搭載される可能性があり、本発明のトランザクショナル・メモリを備える最適化装置の提供は、特に関数呼び出しを含むプログラムを動的に最適化することができる点で、アプリケーションの性能を向上させ、高速処理を実現することができるので有用である。
【符号の説明】
【0081】
100…最適化装置、101…ホスト・コントローラ、102…CPU、102a…トランザクショナル・メモリ、103…RAM、104…グラフィック・コントローラ、105…表示装置、106…入出力コントローラ、107…通信インタフェース、108…HDD、109…CD/DVDドライブ、110…ROM、111…入出力チップ、200…第1コード生成部、201…第2コード生成部、202…コード書込部
【特許請求の範囲】
【請求項1】
トランザクションの排他制御を可能にするトランザクショナル・メモリを備えるプログラムの最適化装置であって、
プログラムを解釈し、前記プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部と、
前記指定された処理に応じて、所定のタイミングで前記複数の命令を用いて第2コードを生成する第2コード生成部と、
トランザクション内で前記第1コードの前記命令列を前記第2コードで上書き、または前記第1コードの一部に前記第2コードを書き込むコード書込部とを備える、プログラムの最適化装置。
【請求項2】
前記指定された処理は、関数呼び出し処理で、前記複数の命令は、引数を設定する命令と、関数を呼び出す命令と、返し値を読み出す命令とを含む、請求項1に記載のプログラムの最適化装置。
【請求項3】
前記所定のタイミングは、前記プログラムの実行中に呼び出した関数を解釈した際である、請求項2に記載のプログラムの最適化装置。
【請求項4】
前記第2コード生成部は、前記呼び出した関数が解釈されたことに応答して、前記命令列内の前記関数を呼び出す命令を、前記呼び出した関数内の値を読み出す命令で置換し、置換した前記値を読み出す命令内のパラメータを変更し、前記命令列内の前記引数を設定する命令および前記返し値を読み出す命令を含む不要な命令群を削除して、最適化した前記第2コードを生成する、請求項3に記載のプログラムの最適化装置。
【請求項5】
前記第2コードのコード・サイズが前記第1コードの前記命令列のコード・サイズ以下であるかを判定するサイズ判定部をさらに含み、
前記命令列のコード・サイズ以下と判定された場合に、前記コード書込部が、前記第1コードの前記命令列に前記第2コードを上書きする、請求項1〜4のいずれか1項に記載のプログラムの最適化装置。
【請求項6】
前記指定された処理は、分岐を伴う処理で、前記複数の命令は、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む、請求項1に記載のプログラムの最適化装置。
【請求項7】
前記プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定する頻度判定部をさらに含み、
前記第2コード生成部は、前記所定のタイミングとして、前記プログラムを解釈した際の前記頻度判定部により分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された前記分岐先の直前の前記分岐命令までの一連の制御フローである、前記第2コードを構成するためのトレースを生成する、請求項6に記載のプログラムの最適化装置。
【請求項8】
前記プログラムの実行中に前記分岐先の命令がアボートした回数が設定値を超えたか否かを判定するアボート判定部と、前記設定値を超えたと判定した場合に、アボートを発生させた命令を含まない前記トレースを、前記第2コード生成部が生成した複数のトレースの中から検索するトレース検索部とを含み、
前記コード書込部が、トランザクション内で前記第1コードの一部に、検索された前記トレースから構成される前記第2コードを書き込む、請求項7に記載のプログラムの最適化装置。
【請求項9】
トランザクションの排他制御を可能にするトランザクショナル・メモリを備えるプログラムの最適化装置により実行される方法であって、
プログラムを解釈し、前記プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成するステップと、
前記指定された処理に応じて、所定のタイミングで前記複数の命令を用いて第2コードを生成するステップと、
トランザクション内で前記第1コードの前記命令列を前記第2コードで上書き、または前記第1コードの一部に前記第2コードを書き込むステップとを含む、プログラムの最適化方法。
【請求項10】
前記指定された処理は、関数呼び出し処理で、前記複数の命令は、引数を設定する命令と、関数を呼び出す命令と、返し値を読み出す命令とを含む、請求項9に記載のプログラムの最適化方法。
【請求項11】
前記所定のタイミングは、前記プログラムの実行中に呼び出した関数を解釈した際である、請求項10に記載のプログラムの最適化方法。
【請求項12】
前記第2コードを生成するステップは、前記呼び出した関数が解釈されたことに応答して、前記命令列内の前記関数を呼び出す命令を、前記呼び出した関数内の値を読み出す命令で置換し、置換した前記値を読み出す命令内のパラメータを変更し、前記命令列内の前記引数を設定する命令および前記返し値を読み出す命令を含む不要な命令群を削除して、最適化した前記第2コードを生成する、請求項11に記載のプログラムの最適化方法。
【請求項13】
前記第2コードのコード・サイズが前記第1コードの前記命令列のコード・サイズ以下であるかを判定するステップをさらに含み、
前記書き込むステップでは、前記命令列のコード・サイズ以下と判定された場合に前記第1コードの前記命令列に前記第2コードを上書きする、請求項9〜12のいずれか1項に記載のプログラムの最適化方法。
【請求項14】
前記指定された処理は、分岐を伴う処理で、前記複数の命令は、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む、請求項9に記載のプログラムの最適化方法。
【請求項15】
前記プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定するステップをさらに含み、
前記第2コードを生成するステップでは、前記所定のタイミングとして、前記プログラムを解釈した際の前記分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された前記分岐先の直前の前記分岐命令までの一連の制御フローである、前記第2コードを構成するためのトレースを生成する、請求項14に記載のプログラムの最適化方法。
【請求項16】
前記プログラムの実行中に前記分岐先の命令がアボートした回数が設定値を超えたか否かを判定するステップと、前記設定値を超えたと判定した場合に、アボートを発生させた命令を含まない前記トレースを、前記第2コード生成部が生成した複数のトレースの中から検索するステップとを含み、
前記第2コードを書き込むステップにおいて、トランザクション内で前記第1コードの一部に、検索された前記トレースから構成される前記第2コードを書き込む、請求項15に記載のプログラムの最適化方法。
【請求項17】
請求項9〜16のいずれか1項に記載の方法を実行するためのコンピュータ可読な最適化プログラム。
【請求項1】
トランザクションの排他制御を可能にするトランザクショナル・メモリを備えるプログラムの最適化装置であって、
プログラムを解釈し、前記プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成する第1コード生成部と、
前記指定された処理に応じて、所定のタイミングで前記複数の命令を用いて第2コードを生成する第2コード生成部と、
トランザクション内で前記第1コードの前記命令列を前記第2コードで上書き、または前記第1コードの一部に前記第2コードを書き込むコード書込部とを備える、プログラムの最適化装置。
【請求項2】
前記指定された処理は、関数呼び出し処理で、前記複数の命令は、引数を設定する命令と、関数を呼び出す命令と、返し値を読み出す命令とを含む、請求項1に記載のプログラムの最適化装置。
【請求項3】
前記所定のタイミングは、前記プログラムの実行中に呼び出した関数を解釈した際である、請求項2に記載のプログラムの最適化装置。
【請求項4】
前記第2コード生成部は、前記呼び出した関数が解釈されたことに応答して、前記命令列内の前記関数を呼び出す命令を、前記呼び出した関数内の値を読み出す命令で置換し、置換した前記値を読み出す命令内のパラメータを変更し、前記命令列内の前記引数を設定する命令および前記返し値を読み出す命令を含む不要な命令群を削除して、最適化した前記第2コードを生成する、請求項3に記載のプログラムの最適化装置。
【請求項5】
前記第2コードのコード・サイズが前記第1コードの前記命令列のコード・サイズ以下であるかを判定するサイズ判定部をさらに含み、
前記命令列のコード・サイズ以下と判定された場合に、前記コード書込部が、前記第1コードの前記命令列に前記第2コードを上書きする、請求項1〜4のいずれか1項に記載のプログラムの最適化装置。
【請求項6】
前記指定された処理は、分岐を伴う処理で、前記複数の命令は、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む、請求項1に記載のプログラムの最適化装置。
【請求項7】
前記プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定する頻度判定部をさらに含み、
前記第2コード生成部は、前記所定のタイミングとして、前記プログラムを解釈した際の前記頻度判定部により分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された前記分岐先の直前の前記分岐命令までの一連の制御フローである、前記第2コードを構成するためのトレースを生成する、請求項6に記載のプログラムの最適化装置。
【請求項8】
前記プログラムの実行中に前記分岐先の命令がアボートした回数が設定値を超えたか否かを判定するアボート判定部と、前記設定値を超えたと判定した場合に、アボートを発生させた命令を含まない前記トレースを、前記第2コード生成部が生成した複数のトレースの中から検索するトレース検索部とを含み、
前記コード書込部が、トランザクション内で前記第1コードの一部に、検索された前記トレースから構成される前記第2コードを書き込む、請求項7に記載のプログラムの最適化装置。
【請求項9】
トランザクションの排他制御を可能にするトランザクショナル・メモリを備えるプログラムの最適化装置により実行される方法であって、
プログラムを解釈し、前記プログラム内の指定された処理を実行するための複数の命令から構成される命令列の前後にトランザクションを開始させる開始命令とトランザクションを終了させる終了命令とを挿入した第1コードを生成するステップと、
前記指定された処理に応じて、所定のタイミングで前記複数の命令を用いて第2コードを生成するステップと、
トランザクション内で前記第1コードの前記命令列を前記第2コードで上書き、または前記第1コードの一部に前記第2コードを書き込むステップとを含む、プログラムの最適化方法。
【請求項10】
前記指定された処理は、関数呼び出し処理で、前記複数の命令は、引数を設定する命令と、関数を呼び出す命令と、返し値を読み出す命令とを含む、請求項9に記載のプログラムの最適化方法。
【請求項11】
前記所定のタイミングは、前記プログラムの実行中に呼び出した関数を解釈した際である、請求項10に記載のプログラムの最適化方法。
【請求項12】
前記第2コードを生成するステップは、前記呼び出した関数が解釈されたことに応答して、前記命令列内の前記関数を呼び出す命令を、前記呼び出した関数内の値を読み出す命令で置換し、置換した前記値を読み出す命令内のパラメータを変更し、前記命令列内の前記引数を設定する命令および前記返し値を読み出す命令を含む不要な命令群を削除して、最適化した前記第2コードを生成する、請求項11に記載のプログラムの最適化方法。
【請求項13】
前記第2コードのコード・サイズが前記第1コードの前記命令列のコード・サイズ以下であるかを判定するステップをさらに含み、
前記書き込むステップでは、前記命令列のコード・サイズ以下と判定された場合に前記第1コードの前記命令列に前記第2コードを上書きする、請求項9〜12のいずれか1項に記載のプログラムの最適化方法。
【請求項14】
前記指定された処理は、分岐を伴う処理で、前記複数の命令は、少なくとも1つの分岐命令と、分岐先で実行すべき命令とを含む、請求項9に記載のプログラムの最適化方法。
【請求項15】
前記プログラムを解釈した際に、計測された分岐命令の成立回数および不成立回数から得られる実行頻度を用い、分岐先の実行頻度が閾値より低くなるかどうかを判定するステップをさらに含み、
前記第2コードを生成するステップでは、前記所定のタイミングとして、前記プログラムを解釈した際の前記分岐先の実行頻度が閾値より低くなると判断されたことに応答して、低くなると判断された前記分岐先の直前の前記分岐命令までの一連の制御フローである、前記第2コードを構成するためのトレースを生成する、請求項14に記載のプログラムの最適化方法。
【請求項16】
前記プログラムの実行中に前記分岐先の命令がアボートした回数が設定値を超えたか否かを判定するステップと、前記設定値を超えたと判定した場合に、アボートを発生させた命令を含まない前記トレースを、前記第2コード生成部が生成した複数のトレースの中から検索するステップとを含み、
前記第2コードを書き込むステップにおいて、トランザクション内で前記第1コードの一部に、検索された前記トレースから構成される前記第2コードを書き込む、請求項15に記載のプログラムの最適化方法。
【請求項17】
請求項9〜16のいずれか1項に記載の方法を実行するためのコンピュータ可読な最適化プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−128628(P2012−128628A)
【公開日】平成24年7月5日(2012.7.5)
【国際特許分類】
【出願番号】特願2010−279022(P2010−279022)
【出願日】平成22年12月15日(2010.12.15)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【復代理人】
【識別番号】100110607
【弁理士】
【氏名又は名称】間山 進也
【Fターム(参考)】
【公開日】平成24年7月5日(2012.7.5)
【国際特許分類】
【出願日】平成22年12月15日(2010.12.15)
【出願人】(390009531)インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】INTERNATIONAL BUSINESS MASCHINES CORPORATION
【復代理人】
【識別番号】100110607
【弁理士】
【氏名又は名称】間山 進也
【Fターム(参考)】
[ Back to top ]