JP5536593B2 - 最適化装置、最適化方法およびコンパイラ・プログラム - Google Patents

Description

本発明は、動的言語により記述されたプログラムの実行中、頻繁に行われるメソッドや変数（シンボル）へのアクセス速度を向上させるように最適な処理を行い、最適化前と同じ動作を保証する最適化装置、最適化方法およびその方法を実現するための装置可読なコンパイラ・プログラムに関する。

機械やコンピュータを制御するためにプログラミング言語が使用されている。このプログラム言語には、手続き型言語で、コンパイラ言語として設計されたC言語、このC言語の拡張として開発されたC^＋＋、Java（登録商標）といった静的言語と、PHP、Ruby（登録商標）、Python（登録商標）、JavaScript（登録商標）といった動的言語とがある。

静的言語は、コンパイル時にすべての変数の型について確認し、矛盾があるものはエラーとなり、すべてが矛盾しない場合に実行される。実行形式の１つにコンパイル後実行がある。この実行形式では、プログラムをコンパイルし、プログラムを使用するコンピュータに合った機械言語（バイナリ）へ変換する。機械言語は、CPUが直接理解し、実行することができる言語である。この静的言語は、処理するデータを数字型、文字列型、構造型のような型によって分類するため、型を宣言する必要があり、文字列型（ストリング）を数値型として何ら宣言することなく使用すれば、コンパイル時にエラーとなる。

これに対し、動的言語は、クラスに、実行時に動的にメソッドや変数（シンボル）を削除、追加することができる言語で、型の限定を行わないため、型検査が行われず、実行前にエラーとなることはない。このように、動的言語は、対象に特定の型を要求しないため、変更への対応が静的言語に比較して柔軟である。また、動的言語は、静的言語に比較してコードの量が少なくて済み、そのコードが比較的に読みやすいという利点を有している。このことから、動的言語は、開発効率が高く、近年、規模の大きなシステムで用いられるようになってきている。

こうしたプログラミング言語で記述するプログラミング技法として、データとそれを操作する手続き（メソッド）をオブジェクトと呼ばれる単位とし、このオブジェクトの組み合わせとしてプログラムを記述するオブジェクト指向プログラミングが多く採用されるようになってきている。このオブジェクト指向プログラミングにより記述されたプログラムを実行すると、オブジェクトを構成するメソッドや、データを一定期間記憶し利用できるように固有の名前が与えられた変数（シンボル）へのアクセスが頻繁に行われることになる。

近年のプログラムの実行による処理速度の高速化は、そのシンボルに格納された値の取得の速度によるところも大きく、その取得の高速化が望まれている。しかしながら、静的言語より遅い動的言語の普及に伴い、その取得の高速化が抑制されている。この理由は、静的言語ではメモリ・アクセス１命令で取得可能であるが、動的言語の主な実装においてはハッシュ・テーブル・アクセスになり、メモリ・アクセスが増加してしまうからである。

静的言語では、コンパイル時もしくは初めての実行時に、シンボル名がメモリ上のoffset値（offset_x）へ変換される。このため、図１（ａ）に示すようなプログラムは、静的言語では、図１（ｂ）に示すような、定数であるoffset_xとr10のレジスタの内容を足した値のアドレスから64ビットを読み込み、r31に代入する命令のみのコードで表される。ここで64ビットは、int（整数型）が64ビットの値をもつことを意味する。このように、静的言語では１命令によりシンボルに格納された値を取得することができる。なお、上記では64ビットとしたが、32ビットの値を示す変数であれば、32ビット分を読み込んで代入することも可能である。

動的言語では、シンボル名をkeyとし、値をvalueとしたシンボル・テーブル（例えば、オープン・ハッシュ・テーブル）に格納し、そのシンボル・テーブルを使用してアクセスする。このため、図１（ａ）に示すプログラムは、動的言語では、図１（ｃ）に示すような、シンボルxを示す整数値をr3に代入する命令と、get_symbol()というメソッドを呼び出し、そのr3に従ってシンボルに格納された値を取得しr31に代入する命令とを含むコードで表される。このように、動的言語では複数の命令を実行し、シンボルに格納された値を取得することから、メモリ・アクセスが増加し、その結果、静的言語に比較してシンボルに格納された値の取得が遅くなる。なお、図１（ｂ）および（ｃ）中、ld、liは、PowerPCのアセンブラである。

このようなハッシュ・テーブル・アクセスにおいても、シンボルへのアクセスを高速化する技術がいくつか提案されている（例えば、非特許文献１および２、特許文献１参照）。非特許文献１では、HREFK命令によりスペシャライズされた場合、ハッシュ・キーとkeyが一致しないとき、処理を終了し、一致する場合に、そのハッシュ・キーに対応する値を読み出し、また、値を書き込むようにすることで高速処理を実現している。

非特許文献２では、ハッシュの値をコンパイル時に計算し、実行時に計算しないようにすることにより、また、特定の機能が実行時のコード生成を行わないことが静的に保証される場合、シンボル・テーブルを削除し、生成されたコードにおいて直接値にアクセスすることにより、最適化して高速処理を実現している。

また、特許文献１では、ホスト・システムからRAMに転送したリローケータブル・オブジェクト・ファイルの各シンボルのロード・アドレス情報よりプログラム・ローダが各シンボルの配置アドレスを決定し、フック情報よりシンボル間のフック処理を行い、さらにプログラム・ローダがデフォルト・シンボル作成機能を有することにより、シンボル毎のターゲット・システムへのきめ細かいシンボル配置やデバッグ効率を向上させている。

プログラムを最適化し、高速処理を実現する装置および方法として、例外を発生しうる命令の実行順序を変更する装置および方法が提案されている（例えば、特許文献２参照）。この装置および方法では、例外を発生しうる第１命令を検出し、第１命令より先に実行され、第１命令の例外を発生させないことを保証する第２命令を検出し、第１命令を選択的に実行させる条件分岐命令より先、かつ第２命令より後に実行させるように、第１命令の実行順序を変更する構成とされている。これにより、コンパイラが、処理に多くの時間を要するメモリ・アクセス等の実行時間を早め、その結果、最適化対象プログラムを高速化することができる。

特開２００２−１３２５２１号公報 特開２００４−６２５２０号公報

"Subject: LuaJIT 2.0 intellectual property disclosure and research opportunities"、[online]、２００９年１１月２日、インターネット、<URL: http://lua-users.org/lists/lua-1/2009-11/msg00089.html> "A Practical Solution for Scripting Language Compilers"、[online]、２００９年８月１７日、インターネット<URL: http://paulbiggar.com/research/wip-sac-journal.pdf>

上記非特許文献１に記載の技術では、HREFK命令によるスペシャライズが外れたとき、従来の遅いアクセスになってしまうという問題がある。

非特許文献２に記載の技術では、予めハッシュの値を計算しておくことから、処理速度を向上させることができるが、シンボルが実行時に削除された場合に対応することができない。また、この技術では、シンボル・テーブルを削除してしまうことから、プログラムの一部だけシンボル・テーブルのアクセスが必要ないという場合に対応することができない。

また、特許文献１に記載の装置および方法では、特別な装置を使用しなくともユーザが指定したターゲット・システム上のアドレスにシンボルを配置し、実行時にすべてのシンボルのアドレス解決が行われなくともシステム暴走を防止することができるが、シンボルへのアクセス速度を向上させるものではない。

さらに、特許文献２に記載の装置および方法も、例外を発生しうる命令の実行順序の変更のほか、ダミー命令により命令の実行順序を制限し、冗長である命令を除去し、ループ内において不変の値を読み出すメモリ・アクセス命令をループ外に移動することにより最適化することができるが、シンボルへのアクセス速度を向上させるものではない。

このため、動的言語で記述されたプログラムの実行中に、頻繁に行われるシンボルへのアクセス速度を向上させ、これにより処理速度を向上させることができる装置や方法の提供が望まれていた。

本発明は、上記課題に鑑み、同一シンボルへのアクセスに関し、シンボルに対応するエントリ（シンボル名であるkeyと値の組）のアドレスが変更されない実装のシンボル・テーブルへのアクセスを最初の一度だけとし、その後はエントリへのアクセスに置き換える際、シンボルが存在するか否かを確認する見張りコードの実行時オーバーヘッドを減らすように、コード生成時、シンボルの生成、シンボルの削除、シンボル内の値の読み出し、シンボル内の値の書き込みといった５つの操作に伴い、適切な処理を行い、最適化前と同じ動作（具体的には例外発生）を保証する構成とする。

このように、シンボル・テーブルへのアクセスを最初の一度だけとし、その後はエントリへのアクセスによりシンボルへアクセスすることができるので、軽量なアクセスとなり、それに加えて、最適化前と同じ動作を保証するように、上記の見張りコードをシンボルが削除されたときに生成するといった適切な処理を行うことにより、低コストで見張りコードを生成することができ、見張りコードの実行時オーバーヘッドを減少させることができ、動的言語におけるシンボルへのアクセス速度を向上させることができる。

このような適切な処理を行い、シンボルへのアクセス速度を向上させることができる装置として、本発明では、動的言語により記述されたプログラムを最適化するための最適化装置を提供することができる。この装置は、プログラムを解釈し、そのプログラムの中の同一シンボルをアクセスする命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定する範囲特定部と、シンボルを識別するためのキーとシンボルに格納された値である値オブジェクトとを対応付けて格納するシンボル・テーブルに、特定された範囲に含まれる命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、そのキーに基づき対応するシンボルに格納される値オブジェクトのアドレスを保持するシンボルエントリのアドレスを取得してアドレス格納部に格納する命令を含む、特定された範囲に含まれる複数の命令に基づき最適化された複数の命令を生成する命令生成部と、特定された範囲から命令を１つずつ取り出す命令抽出部と、取り出した命令がシンボルへアクセスする命令に該当するか否かを判定する命令判定部とを含む構成とされる。

この命令生成部は、命令判定部がシンボルへアクセスする命令に該当すると判定した場合、その命令に基づき、最適化された命令として、アドレス格納部に格納されたシンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、シンボルが存在するとき、シンボルが存在するか否かの確認を高速に可能にする命令を生成する。このような命令を生成する適切な処理を行い、プログラムを最適化することにより、シンボルへのアクセス速度を向上させることができる。

このプログラムを最適化する処理は、上述したように、コンパイル時に行われるコード生成時、生成されたコードの実行時にシンボルが生成されたとき、シンボルが削除されたとき、シンボルに格納される値オブジェクトを読み出すとき、シンボルへ値オブジェクトを書き込むときの５つの操作が行われるときに実施される。

シンボルへアクセスする命令は、シンボルに格納される値オブジェクトを読み出す命令、シンボルへ値オブジェクトを書き込む命令、シンボルを削除する命令が挙げられる。２つの値の加算等の演算命令やメソッドの実行命令は、シンボルへのアクセスが不要であることから、シンボルへアクセスする命令には該当せず、従来から知られた命令生成処理により、それらの命令は生成される。

また、最適化装置は、シンボルが存在するか否かを判定するシンボル判定部をさらに含み、シンボル判定部が、シンボルが存在しないと判定した場合に、命令生成部が、シンボルが存在するか否かを確認する命令（上記の見張りコード）と、存在しない場合に例外を発生させる命令とを生成する。シンボルが削除された等のシンボルが存在しない場合に、確実に例外を発生させることができ、その存在しない場合にのみ見張りコードを実行させるため、シンボルへのアクセス速度を向上させることができる。

命令生成部は、シンボルを削除する命令である場合、アドレス格納部に格納された該シンボルエントリが持つ、値オブジェクトのアドレスを不正なアドレスに書き換える命令を生成する。不正なアドレスに書き換えられると、次に読み出されるとき、その不正なアドレスが読み出されることになる。この不正なアドレスの読み出しは、例外を発生させることから、シンボルが存在しない場合に、確実に例外発生を保証することができる。また、シンボルが存在する場合は、不正なアドレスに書き換えられないため、即座にそのシンボルエントリのアドレスを使用してシンボルへアクセスすることができる。

命令生成部は、シンボル内の値オブジェクトを読み出す命令または書き込む命令である場合、アドレス格納部に格納されたシンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、アクセスして取得したシンボルに格納される値オブジェクトのアドレスを0と比較する命令を生成し、シンボルを削除する命令である場合、値オブジェクトのアドレスとして0を代入する命令を生成する。シンボルが存在する場合は、値オブジェクトのアドレスを読み出した後に0と高速で比較し、0ではないので、次の命令の実行へ移行することができ、シンボルが存在しない場合は、高速で比較し、同じ0であるため、例外が発生し、確実に例外発生を保証することができる。

命令生成部は、シンボルを削除する命令である場合、読み出されたときに例外を発生させるハンドラを実行する値を値オブジェクトのアドレスの値として代入する命令を生成する。この場合も、シンボルが存在する場合は、値オブジェクトのアドレスがハンドラを実行する値とは異なるので、ハンドラは実行されず、シンボルが存在しない場合は、ハンドラを実行する値が読み出されるので、ハンドラが実行され、確実に例外発生を保証することができる。

本発明では、上述した最適化装置のほかに、その最適化装置において行われる最適化方法も提供できる。この方法は、プログラムを解釈し、そのプログラムの中の同一シンボルをアクセスする命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定するステップと、シンボルを識別するためのキーとシンボルに格納される値とを対応付けて格納するシンボル・テーブルに、特定された範囲に含まれる命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、そのキーに基づき対応するシンボルに格納される値のアドレスを保持するシンボルエントリのアドレスを取得してアドレス格納部に格納する命令を生成するステップと、特定された範囲から命令を１つずつ取り出すステップと、取り出した命令がシンボルへアクセスする命令に該当するか否かを判定するステップと、シンボルへアクセスする命令に該当すると判定された場合、該命令に基づき、最適化された命令として、アドレス格納部に格納されたシンボルエントリのアドレスを使用してそのシンボルへアクセスする命令を生成する際、シンボルが存在するとき、シンボルが存在するか否かを確認することなく即座にそのシンボルへのアクセスを可能にする命令を生成するステップとを含む。

また、その方法を実現するための装置可読なコンパイラ・プログラムも提供することができる。このコンパイラ・プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納して提供することができ、PC等のコンピュータにより読み出し実行することにより、そのコンピュータを最適化装置として機能させることができる。

静的言語と動的言語で変換されたプログラムを例示した図。 本発明の最適化装置のハードウェア構成の一例を示した図。 従来のコンパイラにより変換されたプログラムの一例を示した図。 最適化装置の機能ブロック図。 最適化装置により書き換えられ、最適化されたプログラムの第１実施形態を示した図。 図５に示す最適化処理の流れを示したフローチャート図。 ステップ６１９で行われる処理の流れを示した図。 最適化装置により書き換えられ、最適化されたプログラムの第２実施形態を示した図。 図８に示す最適化処理の流れを示したフローチャート図。 ステップ９１０で行われる処理の流れを示した図。 最適化装置により書き換えられ、最適化されたプログラムの第３実施形態を示した図。 図１１に示す最適化処理の流れを示したフローチャート図。 ステップ１２１０で行われる処理の流れを示した図。 最適化装置により書き換えられ、最適化されたプログラムの第４実施形態を示した図。 図１４に示す最適化処理の流れを示したフローチャート図。 ステップ１５１０で行われる処理の流れを示した図。

以下、本発明を図面に示した具体的な実施の形態に沿って説明するが、本発明は、後述する実施の形態に限定されるものではない。図２は、本発明の最適化装置のハードウェア構成を例示した図である。この最適化装置２００は、外部からソース・プログラムを受け取り、そのソース・プログラムに所定の変換を行ってJava（登録商標）バイトコードやPython（登録商標）やRuby（登録商標）等の動的言語用のバイトコードといった中間表現にした後、あるいはJavaScript（登録商標）といった動的言語であればそのソース・プログラム自体を、コンピュータが実行可能なコードを生成するために解析し、コード生成を行い、ソース・プログラムをコンピュータが実行可能な実行コードへ変換する装置である。そのコード生成の際に、最適化したプログラムを生成し、また、コード実行時にプログラムの書き換えを行い、コード生成し、その実行を可能にする装置である。

最適化装置２００は、上記の処理を実現するためのコンパイラ・プログラムを格納し、それを実行することができる装置であってもよく、PC、サーバ、ワークステーション等を最適化装置とすることが可能である。なお、上記の外部は、例えば、この最適化装置２００にネットワーク等を介して接続されるPC等とすることができる。

最適化装置２００は、ハードウェアとして、ホスト・コントローラ２０１により相互に接続されるCPU２０２と、RAM２０３と、グラフィック・コントローラ２０４および表示装置２０５を備える周辺装置と、入出力コントローラ２０６によりホスト・コントローラ２０１に接続される通信インタフェース２０７と、ハードディスク・ドライブ（HDD）２０８、CD/DVDドライブ２０９等を備える入出力装置と、入出力コントローラ２０６に接続されるROM２１０と、入出力チップ２１１を備えるレガシー入出力装置とを含んで構成される。そのほか、記録媒体の１つとして使用されるSDカードに記録されたプログラムやデータを読み取るSDカード・リーダ等を含むことができる。

ホスト・コントローラ２０１は、RAM２０３と、高い転送レートでRAM２０３をアクセスするCPU２０２およびグラフィック・コントローラ２０４とを接続する。CPU２０２は、ROM２１０およびRAM２０３に格納された上記のコンパイラ・プログラム等に基づいて動作し、各部の制御を行う。グラフィック・コントローラ２０４は、CPU２０２等がRAM２０３内に設けたフレーム・バッファ上に生成する画像データを取得し、表示装置２０５上に表示させる。グラフィック・コントローラ２０４は、CPU２０２等が生成する画像データを格納するフレーム・バッファを、このグラフィック・コントローラ２０４の内部に備えることもできる。

入出力コントローラ２０６は、ホスト・コントローラ２０１と、比較的高速な入出力装置である通信インタフェース２０７、HDD２０８、CD/DVDドライブ２０９を接続する。通信インタフェース２０７は、ネットワークを介して他の装置と通信する。HDD２０８は、上記のコンパイラ・プログラムやその他のプログラム、各種データを格納することができる。CD/DVDドライブ２０９は、CD-ROMやDVDに上記最のコンパイラ・プログラムやその他のプログラム、各種データが記録されている場合、それらを読み取り、RAM２０３を介して入出力チップ２１１に提供することができる。

入出力コントローラ２０６は、ROM２１０と、入出力チップ２１１等の比較的低速な入出力装置とが接続される。ROM２１０は、HDD２０８からOSをロードして起動するためのブート・プログラムや、コンピュータや機器の初期設定情報等を記録したファームウェア等を格納する。入出力チップ２１１は、パラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各部の入出力装置を接続する。

コンパイラ・プログラムは、CD-ROM、DVD、SDカード等の記録媒体に格納されてユーザに提供される。コンパイラ・プログラムは、この記録媒体から読み出され、入出力コントローラ２０６を介してHDD２０８等にインストールされ、CPU２０２により読み出されて実行される。これに限られるものではなく、ネットワークに接続されたサーバのHDD等に格納され、このサーバのHDD等から読み出し、実行することも可能である。

ソース・プログラムは、C言語、C^＋＋、Java（登録商標）といった静的言語のほか、PHP、Ruby（登録商標）、Python（登録商標）、JavaScript（登録商標）といった動的言語で記述される場合があり、最近、開発効率の高さから、規模の大きいシステムにおいても動的言語が用いられている。

しかしながら、動的言語は、上述したように静的言語に比較してメモリ・アクセスに複数命令が必要であるため、アクセス速度が低下するという問題がある。これは、静的言語では直接メモリ上の所定アドレスにアクセスするが、動的言語ではハッシュ・テーブルにアクセスするからである。ハッシュ・テーブルは、ハッシュ・キーと値の組（エントリ）を格納し、キーにハッシュ関数を適用してハッシュ値を計算した後、そのハッシュ値に格納されているエントリを読み出すことにより値を取得することができるものである。

ハッシュ・テーブルへのアクセスを各命令につき行うと、処理速度が低下することから、ハッシュ・テーブルへアクセスする回数を減らすことにより、処理速度の低下を抑制することができる。本発明では、同一のシンボルに関するアクセスに対し、そのシンボルに対応するエントリのアドレスが変更されない実装、例えばオープン・ハッシュ・テーブルへのアクセスを最初の一度だけにし、その後はエントリへのアクセスに置き換える。

具体的には、図３（ａ）に示すソース・プログラムあるいは中間表現の元のプログラムから、図３（ｂ）に示すような最適化したプログラムを生成することができる。図３（ａ）に示す元のプログラムは、オブジェクトaのシンボルxの値を変数ｉに代入する（i=a.x）等のオブジェクトaのシンボルxをアクセスする命令が複数記述されている。これをコンパイラが解釈し、最適化し、その後コード生成を行うが、この最適化されたときに生成されるプログラムは、図３（ｂ）に示すように、同じオブジェクトaのシンボルxへアクセスする命令が含まれる範囲（ここでは、i=a.xからk=a.xまで）を、シンボルのアクセスを共通化できる範囲として特定し、その範囲において、オブジェクトaのシンボルxを管理するハッシュ・エントリを取得し、_Entxというアドレスを格納するアドレス格納部に代入する命令を生成する。

Entryは、複数の値をまとめて格納できる構造体として定義されるもので、このEntryの_Entxに値を格納できることから、_Entxは上記のアドレス格納部として機能するものである。get_symbol_entry()は、シンボル・テーブル内のエントリのアドレスを返すという命令である。get_symbol_entry()によりシンボル・テーブルへ最初の一度だけアクセスし、その後は、_Entxに格納したアドレスを使用してエントリへアクセスすることができる。

上記のi=a.xは、i=_Entx->valとして、エントリ内の値を読み出す命令へ置き換えられる。しかしながら、エントリに対応するシンボルが削除された場合、エントリが空（NULL）となり、これだけでは、適切に例外を発生させることができない。このため、エントリ内の値を読み出し、それが空であるか判断し、空である場合、例外を発生させる命令を生成し、この命令に置き換えられることになる。このように、エントリ内の値の読み出しやエントリ内の値の書き込み毎に、エントリが空であるかを確認する見張りコードを設けることにより、例外を発生させるべきときに確実に例外を発生させることを保証する。なお、エントリに対応する変数が削除された場合、_Entx->valにはNULLを代入し、上記命令において確実に例外を発生させることができるように保証する。

しかしながら、このようなコードでは、エントリ内の値をそのつど読み出し、それが空であるかどうかを判断しており、高速処理を実現することができるにしても限界がある。エントリ内に値があるにもかかわらず、エントリ内の値を読み出し、それが空であるかを判断することは無駄な処理だからである。

そこで、本発明では、シンボルへアクセスする命令、具体的にはシンボルの値の読み出し、書き込み、シンボルの削除といった命令につき、適切な処理を行う命令を生成することで、このような無駄な処理をなくし、実行時の高速処理を実現する。

上記の適切な処理の具体的な例として、以下の（１）〜（４）に例示する処理を挙げることができる。
（１）実行時にコードを書き換え、例外発生が必要かどうかを確認する頻度を減少させる。
（２）実行時のメモリ・アクセスを契機として、例外発生のための処理を行う。
（３）例外発生の確認のため、実行コストが低い命令を利用する。
（４）特別な値を読み込んだ際、例外発生のための処理を行う。

このような処理を行って採用することにより、不定回実行されるループを含み、キャッシュ・ミスを起こしやすいハッシュ・テーブルへのアクセスをより軽量なアクセスに置き換え、見張りコードの実行時のオーバーヘッドを減少させることができる。その結果、動的言語におけるシンボルへのアクセス速度を向上させることができる。

図４に、これらの方法を実施するための最適化装置の機能ブロック図を例示する。この装置４００は、図２に示すハードウェア構成とされ、ROM２１０およびRAM２０３に格納されたコンパイラ・プログラムをCPU２０２が実行することにより各部として機能し、これら各部を備えるものとされる。

この装置４００は、範囲特定部４０１と、命令生成部４０２と、命令抽出部４０３と、命令判定部４０４とを含む構成とされる。範囲特定部４０１は、プログラムを解釈し、同一シンボルをアクセスする命令が並ぶ命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定する。

図３（ａ）に示すように、同じオブジェクトaのシンボルxをアクセスする命令が含まれる範囲、すなわち１行ずつ命令が並ぶように記述されたプログラムにおいてi=a.xからk=a.xまでの同じシンボルxを読み書き使用する範囲を特定する。このような範囲を特定するために、これまでに知られたいかなる方法や範囲特定プログラムを採用し、特定することができる。この範囲にある命令は、最初に一度だけシンボル・テーブルへアクセスし、エントリのアドレスを取得し、_Entxに代入しておき、_Entxにあるエントリのアドレスを使用し、エントリ内の値を読み出し、また、書き込むことにより、シンボル・テーブルへアクセスしなくても処理を実現することができる。

命令生成部４０２は、メソッドや変数といったシンボルを識別するためのキーとシンボルに格納される値オブジェクトとを対応付けて格納するシンボル・テーブルに、範囲特定部４０１により特定された範囲に含まれる命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、そのキーに基づき対応するシンボルの値オブジェクトのアドレスを保持するシンボルエントリのアドレスを取得して_Entxに代入する命令を含む、その特定された範囲に含まれる複数の命令に基づき最適化された複数の命令を生成する。

命令抽出部４０３は、命令生成部４０２により最初に上記の_Entxに代入する命令が生成された後、範囲特定部４０１により特定された範囲に含まれる命令の中から１つずつ命令を取り出す。命令は、プログラムに記述されている順に、１つずつ取り出すことができる。命令判定部４０４は、命令抽出部４０３により取り出した命令が、シンボルへアクセスする命令、具体的にはシンボル内の値である値オブジェクトの読み出し命令、シンボル内への値オブジェクトの書き込み命令、シンボルの削除命令に該当するか否かを判定する。その他の加算、減算、乗算、除算等の演算命令やメソッド実行命令は、読み出し命令により読み出された値を使用するため、シンボルへアクセスすることはないので、シンボルへアクセスする命令には該当しない。

命令生成部４０２は、命令判定部４０４がシンボルへアクセスする命令に該当すると判定した場合、その命令に基づき、最適化された命令として、_Entxにあるシンボルエントリのアドレスを使用してシンボルへアクセスする命令を生成する。このように、_Entxにあるシンボルエントリのアドレスを使用することで、シンボル・テーブルへのアクセスを減らすことができる。その命令を生成する際、シンボルが存在するときは、シンボルが存在するか否かを確認することなく即座にシンボルへのアクセスを可能にする命令を生成する。シンボルが存在する場合は、エントリ内の値を読み書きできるので、確認する必要はなく、このような確認作業を省略することで、高速処理を実現することができる。また、シンボルの存在の確認を高速化した命令列を生成し、高速処理を実現することができる。

図４に示す各部を備える最適化装置は、シンボルが存在する場合はシンボルが存在するか否かを確認する作業を省略するような命令を生成し、生成された命令を含むプログラムからCPUが直接実行可能なコードを生成し、そのコードを実行することにより高速処理を実現するが、その命令の生成に関し、上記（１）〜（４）のいずれかの適切な処理により見張りコードの実行時オーバーヘッドを減らし、シンボルへのアクセス速度を向上させることができる。これらの適切な処理を以下に詳細に説明する。なお、これらの処理は例示であって、アクセス速度の向上のためには、これらの処理に限定されるものではない。

上記（１）では、ソース・プログラムを解釈し、コード生成する際にシンボルが存在する場合、もしくはそのコードの実行中にシンボルが生成された場合、またはそのシンボル内の値（値オブジェクト）を読み書きする場合はシンボル内に値が存在することが明らかであるため、見張りコードを生成せず、シンボルが存在しない場合やシンボルが削除された場合にのみ見張りコードを生成する。例えば、元のプログラムが、図５（ａ）に示すようなプログラムであった場合、シンボルが存在する場合には、図５（ｂ）に示すように、何もしないというNOPと、i=_Entx->valという命令を生成する。

ここで、NOPは、後で命令を追加する予定の場所にダミーとして置かれるものであり、後にシンボルが削除された場合に命令を置き換えることを可能にする。また、i=_Entx->valは、アロー（->）演算子を用いた式で、ポインタを介して値にアクセスし、その値を変数iに代入することを意味する。このように、以降のシンボルのアクセスを共通化できる範囲として特定した複数の命令の各々につき、NOPおよび_Entx->valを用いて置き換える。ここでは、NOPを用いて記述したが、これに限られるものではなく、JUMP命令を用いて特定の命令位置へジャンプさせることも可能である。

シンボルが存在しない場合やシンボルが削除された場合、図５（ｃ）に示すように、_Entx->valがNULLであるかを判断する見張りコードを生成し、そうであるなら、例外を発生させる命令も生成する。ここでは、_Entx->valによりエントリの値を直接読みに行き、判断するようにしている。なお、シンボルが削除された場合、_Entx->valにNULLを代入する。

図６に示すフローチャートを参照して、この処理について詳細に説明する。ステップ６００から処理を開始し、ステップ６０１において、コンパイラ・プログラムによりソース・プログラムを解釈し、同じオブジェクトの同じシンボルの読み書き等を行う範囲として、シンボルのアクセスを共通化できる範囲を特定する。

ステップ６０２において、オブジェクトaのシンボルxを管理するハッシュ・エントリを取得し、_Entxに代入する命令を生成する。すなわち、Entry ^*_Entx=get_symbol_entry(a,”x”); を生成する。

ステップ６０３において、特定した共通化できる範囲の中に記述されている命令から１つの命令を取り出す。取り出す方法としては、例えば、その範囲の先頭から順に１つずつ取り出すことができる。

次に、ステップ６０４において、その範囲の中の命令をすべて取り出し、空になったかを判定する。空になった場合は、処理する対象が存在しないので、ステップ６２２へ進み、この処理を終了する。

空でない場合はステップ６０５へ進み、取り出した命令が、シンボルへアクセスする命令であるシンボル内のオブジェクトの読み込みであるかを判定する。具体的には、i=a.xのような命令であるかを判定する。読み込みである場合は、ステップ６０６において、シンボルエントリが持つ値オブジェクトのアドレスがNULLかを判定する。NULLの場合は、シンボルは存在せず、NULLでない場合は、シンボルが存在することになる。

シンボルエントリの値オブジェクトのアドレスがNULLでない場合、ステップ６０７へ進み、後ほど命令を挿入できる場所が確保できればどのような命令であってもよいが、例えば、NOPを生成し、そのアドレスを登録する。NOPから他の命令に変更する場合、そのアドレスにアクセスし、他の命令をそのアドレスに登録することにより、命令を置き換えることができる。

NULLの場合、ステップ６０８へ進み、NULLかどうかを確認する命令と、NULLの場合に実行する処理（例えば、例外発生）に関する命令を生成する。すなわち、if(_Entx->val==NULL) throw noEntryExceptionを生成する。ステップ６０７およびステップ６０８でそれぞれ命令を生成した後、ステップ６０９へ進み、_Entx->valから値を取り出し、変数iに代入する命令（i=_Entx->val;）を生成する。その後、ステップ６０４へ戻り、次の命令が取り出される。

ステップ６０５でオブジェクトの読み込みでないと判定された場合、ステップ６１０において、取り出した命令が、シンボルへアクセスする命令であるオブジェクトの書き込みであるかを判定する。具体的には、a.x=123のような命令であるかを判定する。書き込みである場合は、ステップ６１１において、シンボルエントリが持つ値オブジェクトのアドレスがNULLかを判定する。NULLの場合は、シンボルが存在せず、NULLでない場合は、シンボルが存在することになる。

NULLでない場合、ステップ６１２へ進み、後ほど命令を挿入できる場所が確保できればどのような命令であってもよいが、例えば、NOPを生成し、そのアドレスを登録する。NOPから他の命令に変更する場合、そのアドレスにアクセスし、他の命令をそのアドレスに登録することにより、命令を書き換えることができる。

NULLの場合、ステップ６１３へ進み、上記のステップ６０８と同様の、NULLかどうかを確認する命令と、NULLの場合に実行する処理（例えば、例外発生）に関する命令を生成する。ステップ６１２およびステップ６１３でそれぞれ命令を生成した後、ステップ６１４へ進み、_Entx->valへ値オブジェクト（obj）を代入する命令（_Entx->val=obj;）を生成する。その後、ステップ６０４へ戻り、次の命令が取り出される。

ステップ６１０で書き込みでもないと判定された場合、ステップ６１５において、取り出した命令が、シンボルへアクセスする命令であるシンボルの削除であるかを判定する。具体的には、del=a.xのような命令であるかを判定する。ここで、動的言語における削除構文は、ハッシュ（hoge）を用いて表現すると、例えばJavaScript（登録商標）ではdelete hoge、Python（登録商標）ではdel hoge、Perl（登録商標）ではundef $hoge、PHPではunset($hoge)である。削除である場合は、ステップ６１６において、シンボルエントリが持つ値オブジェクトのアドレスがNULLかを判定する。NULLの場合は、シンボルが存在せず、NULLでない場合は、シンボルが存在することになる。

NULLでない場合、ステップ６１７へ進み、後ほど命令を挿入できる場所が確保できればどのような命令であってもよいが、例えば、NOPを生成し、そのアドレスを登録する。NOPから他の命令に変更する場合、そのアドレスにアクセスし、他の命令をそのアドレスに登録することにより、命令を置き換えることができる。

NULLの場合、ステップ６１８へ進み、上記のステップ６０８やステップ６１３と同様の、NULLかどうかを確認する命令と、NULLの場合に実行する処理（例えば、例外発生）に関する命令を生成する。ステップ６１７およびステップ６１８でそれぞれ命令を生成した後、ステップ６１９へ進み、登録したアドレスに、チェック命令を生成するコード（call InstUpdatehelper;）を生成する。その後、ステップ６２０へ進み、_Entx->valにNULLを代入する命令を生成する。そして、ステップ６０４へ戻り、次の命令が取り出される。

ステップ６１５において取り出した命令がシンボルを削除するものでもない場合、ステップ６２１へ進み、ソース・プログラムを参照し、従来から知られた命令生成処理により対応する命令を生成し、その後、ステップ６０４へ戻り、次の命令を取り出す。ここでの命令は、高速処理を行うのに影響を及ぼさない命令であり、例えば、加算、減算、乗算、除算等の演算命令やメソッドの実行命令が挙げられる。これらの命令は、従来の記載方法により記述されたものと同様の命令とすることができる。

なお、上記NOPを生成し、プログラムの中に入れておくことで、新たなコードとして見張りコードを生成した場合に、その見張りコードに置き換えることを可能にするが、必ずしもNOPを入れておく必要はなく、見張りコードを生成する場所に存在した命令を塗りつぶす、同じ処理をする命令を別の位置に生成しておき、見張りコードを生成した際に別の位置に生成しておいた命令も実行するようにして、NOPを出さない実装も可能である。

図７は、図６のステップ６１９で行われる処理を示したフローチャートである。ステップ７００のInstUpdateHelperを実行し、ステップ７０１で、コンパイル時に登録されたアドレスに、シンボルエントリの値オブジェクトのアドレスがNULLかを確認する命令と、NULLの場合に実行する処理（例えば、例外発生）に関する命令を生成する。これらの命令は、上記ステップ６０８等で生成される命令と同様のものである。生成後は、図６に示すステップ６０４へ戻り、次の命令が取り出される。

次に、上記（２）について説明する。この処理では、図８に示すように、コード生成時に、シンボルに格納される値が読み出し、書き込みされる場所に、_Entx->valへのメモリ・アクセス命令を生成する。コード実行時において、シンボルが生成された場合、_Entx->valにオブジェクトのアドレスを登録し、格納する。そして、シンボルが削除された場合、その_Entx->valにメモリ例外が発生するようなアドレスを生成し、格納する。

シンボルに格納される値を読み出し、書き込む場合、_Entx->valの値を読み出し、書き込む。このため、_Entx->valへのアクセスの際、メモリ例外が発生するようなアドレスが格納されていれば、そのアドレスを返し、メモリ例外を発生させることができる。

具体的には、図８に示すように、ソース・プログラムのdel a.xに対応して、_Entx->val=0xbaadfoodという不正なアドレスを代入する命令を生成し、_Entx->valを読み出す命令（i=_Entx->val;）の次の行にt=i->_typeというオブジェクトaの中のデータであるフィールド（_type）を読み出す命令を追加する。ここではメモリ例外を発生させるために、不正なアドレスを0xbaadfoodとしたが、これに限られるものではない。

シンボルが削除されると、_Entx->valに0xbaadfoodが代入され、変数iやjにはこの0xbaadfoodが代入されることになる。メモリ例外はメモリ番地を読み込んだ際に発生するので、iやjの値を、ポインタを介して読み出し、その後に追加されたフィールドを読み出す命令により、フィールドを読み出すことによってメモリ例外を発生させることができる。

この処理の詳細について、図９に示すフローチャートを参照して説明する。ステップ９００から処理を開始し、まず、ステップ９０１において、シンボルのアクセスを共通化できる範囲を特定する。

ステップ９０２において、オブジェクトaのシンボルxを管理するハッシュ・エントリを取得して_Entxに代入する命令を生成する。このように、シンボル・テーブルへのアクセスを最初の１回だけにして、その後はエントリへのアクセスに置き換えることにより、軽量なアクセスとし、アクセス速度を向上させることができる。

次に、ステップ９０３において、特定された範囲から命令を１つ取り出す。これも、上記と同様、特定された範囲に順に並ぶ命令を、順に取り出すことができる。

ステップ９０４において、取り出す命令があるかどうかを判定する。取り出す命令がなくなった場合は、ステップ９１２へ進み、この処理を終了する。これに対し、取り出す命令がある場合は、ステップ９０５へ進み、その取り出した命令が、シンボル内のオブジェクトの読み込みであるかを判定する。すなわち、i=a.xのような命令であるかを判断する。その命令が読み込みである場合、ステップ９０６へ進み、_Entx->valからオブジェクトを取り出し、変数iに代入する命令を生成する。また、オブジェクトの中のフィールド（_type）を読み出す命令も生成する。これは、シンボルが削除されている場合、_Entx->valには0xbaadfoodが代入されるが、メモリ例外を発生させるためには実際の値を読み取る必要があるからである。この命令が生成されると、ステップ９０４へ戻り、次の命令が取り出される。

ステップ９０５で、取り出した命令が、シンボル内のオブジェクトの読み込みではない場合、ステップ９０７へ進み、取り出した命令が、シンボルへのオブジェクトの書き込みであるかを判定する。すなわち、a.x=123のような命令であるかを判断する。その命令が書き込みである場合、ステップ９０８へ進み、_Entx->valが指し示すオブジェクトの要素（_type）を読み込む命令と、_Entx->valにオブジェクト（obj）を代入する命令とを生成する。これらの命令は、_Entx->valが指し示すオブジェクトの要素（_type）を読み出し、その_Entx->valにobjを書き込むものである。これは、_Entx->valに0xbaadfoodが書き込まれたままであると、メモリ例外を発生させ、書き込みを行うことができないことから、一度値を読み込み、メモリ例外が発生しないことを確認して、書き込みを行うようにするためである。この命令が生成されると、ステップ９０４へ戻り、次の命令が取り出される。

ステップ９０７で、取り出した命令が書き込みでないと判定された場合、ステップ９０９へ進み、取り出した命令が、シンボルの削除であるかを判定する。その命令が削除である場合、ステップ９１０へ進み、_Entx->valに、メモリ例外を発生させるような不正なアドレスを代入する命令を生成する。すなわち、メモリ番地を読み込んだ際に例外が発生するようなアドレスである。ここでは、そのアドレスが0xbaadfoodとされている。この命令が生成されると、ステップ９０４へ戻り、次の命令が取り出される。

ステップ９０９において取り出した命令がシンボルを削除するものでもない場合、ステップ９１１へ進み、ソース・プログラムを参照し、対応する命令を生成する処理を行い、その後、ステップ９０４へ戻り、次の命令を取り出す。ここでの命令は、高速処理を行うのに影響を及ぼさない命令であり、例えば、加算、減算、乗算、除算等の演算命令やメソッドの実行命令が挙げられる。これらの命令を従来から知られた命令生成処理により生成する。

図１０は、メモリ例外処理ハンドラが呼ばれたときの処理の流れを示したフローチャートである。ステップ１０００から処理を開始し、ステップ１００１において、メモリ例外を発生させた命令が、図９のステップ９１０で生成した不正なアドレスが代入され、その結果、呼ばれたハンドラかどうかを判定する。そうである場合、ステップ１００２へ進み、削除されたシンボルにアクセスしたときに行われる処理を実行する。具体的には、throw noEntryExceptionというハンドラを実行する。そうでない場合は、ステップ１００３へ進み、従来のメモリ例外処理として強制終了等の処理が実行される。

上記（３）について説明する。この処理では、図１１に示すように、コード生成時に、条件分岐の不成立方向は高速に実行可能な命令を用い、シンボルに格納される値が読み出し、書き込みされる場所で、_Entx->valの値のチェックを行い、シンボルが存在しない場合に実行する処理、すなわち例外を発生させる命令を生成する。例えば、PowerPCでは、trap命令に相当し、このtrap命令では、条件不成立において１クロックで次の命令に実行を移し、条件が成立した場合は数十クロックかかってハンドラへ飛ぶ。そして、コード実行時において、シンボルが生成された場合、_Entx->valにオブジェクトのアドレスを登録し、格納する。なお、この処理は、プロセッサに分岐しないパスが高速に実行できる命令が実装されていることが条件とされる。

シンボルに格納される値を読み出し、書き込む場合、_Entx->valの値を読み出し、書き込み、値をチェックする。そして、シンボルが削除された場合、_Entx->valに0を代入する。これは、trapi命令が、trap命令で即値と比較するもので、0と0を比較し、条件を成立させ、例外を発生させるためである。この例外発生が、条件成立により実行されるハンドラである。

具体的には、図１１に示すように、ソース・プログラムのdel a.xに対応して、_Entx->val=0というコードが生成され、_Entx->valを読み出す命令（i=_Entx->val）の次の行にtrapi eq,i,0という命令が追加される。この命令が、iと0を比較し、一致すれば条件成立となり、ハンドラヘ飛び、例外を発生させる。

この処理では、シンボルの削除がめったに起きないという実行分布を利用しており、この実行分布が通常と反対であったなら、再コンパイルし、条件分岐を反対にする。

この処理の詳細について、図１２に示すフローチャートを参照して説明する。ステップ１２００から処理を開始し、まず、ステップ１２０１において、シンボルのアクセスを共通化できる範囲を特定する。

ステップ１２０２において、オブジェクトaのシンボルxを管理するハッシュ・エントリのアドレスを取得して_Entxに代入する命令を生成する。このように、シンボル・テーブルへのアクセスを最初の１回だけにして、その後はエントリへのアクセスに置き換えることにより、軽量なアクセスとし、アクセス速度を向上させることができる。

次に、ステップ１２０３において、特定された範囲から命令を１つ取り出す。これも、上記と同様、特定された範囲に順に並ぶ命令を、順に取り出すことができる。

ステップ１２０４において、取り出す命令があるかどうかを判定する。取り出す命令がなくなった場合は、ステップ１２１２へ進み、この処理を終了する。これに対し、取り出す命令がある場合は、ステップ１２０５へ進み、その取り出した命令が、シンボル内のオブジェクトの読み込みであるかを判定する。すなわち、i=a.xのような命令であるかを判断する。その命令が読み込みである場合、ステップ１２０６へ進み、_Entx->valからオブジェクトを取り出し、変数iに代入する命令を生成する。また、その結果を高速に比較することができる命令（trapi命令）を用いて0と比較するコードを生成する。これは、シンボルが削除されている場合、_Entx->valには0が代入され、この0と上記の0とを比較し、一致することから条件成立となり、例外を発生させるためである。これらの命令が生成されると、ステップ１２０４へ戻り、次の命令が取り出される。

ステップ１２０５で、取り出した命令が、シンボル内のオブジェクトの読み込みではない場合、ステップ１２０７へ進み、取り出した命令が、シンボルへのオブジェクトの書き込みであるかを判定する。すなわち、a.x=123のような命令であるかを判断する。その命令が書き込みである場合、ステップ１２０８へ進み、_Entx->valからオブジェクトを取り出し、一時変数tに代入する命令と、その結果を高速に比較することができる命令（trapi命令）を用いて0と比較するコードと、比較結果が不成立の場合に_Entx->valにオブジェクト（obj）を代入する命令とを生成する。これは、比較するためにはオブジェクトを読み出す必要があり、比較を行い、条件不成立であることを確認した後に、オブジェクトの書き込みを行うようにするためである。これらの命令が生成されると、ステップ１２０４へ戻り、次の命令が取り出される。

ステップ１２０７で、取り出した命令が書き込みでないと判定された場合、ステップ１２０９へ進み、取り出した命令が、シンボルの削除であるかを判定する。その命令が削除である場合、ステップ１２１０へ進み、_Entx->valに0を代入する命令を生成する。次の処理においてtrapi命令で0と比較し、条件成立にし、適切にハンドラヘ飛ばすためである。この命令が生成されると、ステップ１２０４へ戻り、次の命令が取り出される。

ステップ１２０９において取り出した命令がシンボルを削除するものでもない場合、ステップ１２１１へ進み、ソース・プログラムを参照し、対応する命令を生成する処理を行い、その後、ステップ１２０４へ戻り、次の命令を取り出す。ここでの命令は、高速処理を行うのに影響を及ぼさない命令であり、例えば、加算、減算、乗算、除算等の演算命令やメソッドの実行命令が挙げられる。これらの命令を従来から知られた命令生成処理により生成する。

図１３は、trapi命令で条件が成立した場合に実行される処理の流れを示したフローチャートである。ステップ１３００から処理を開始し、ステップ１３０１において、この命令が、図１２のステップ１２０６または１２０７で生成した命令により0と比較され、その結果、呼ばれたハンドラかどうかを判定する。そうである場合、ステップ１３０２へ進み、削除されたシンボルにアクセスしたときに行われる処理を実行する。具体的には、throw noEntryExceptionというハンドラを実行する。そうでない場合は、ステップ１３０３へ進み、従来のメモリ例外処理として強制終了等の処理が実行される。

最後に、上記（４）について説明する。この処理では、図１４に示すように、コード生成時に、シンボルに格納される値が読み出し、書き込みされる場所に、任意のメモリ・アドレスから特別な値、ここでは0x80000000を読み出すとハンドラが実行される命令を用いて、_Entx->valの値を読み出すコードを生成する。コード実行時において、シンボルが生成された場合、_Entx->valにオブジェクトのアドレスを登録し、格納する。

シンボルに格納される値を読み出す場合、_Entx->valの値を読み出すことにより行う。シンボルへ書き込みを行う場合、_Entx->valの値を読み出した後、_Entx->valへ値を書き込むことにより行う。これは、シンボルが削除された場合、_Entx->valに特別な値、ここでは0x80000000を代入する。そして、ハンドラには、シンボルがないときに実行される処理を生成する。この処理は、上記と同様、throw noEntryExceptionというハンドラである。

この処理の詳細について、図１５に示すフローチャートを参照して説明する。ステップ１５００から処理を開始し、まず、ステップ１５０１において、シンボルのアクセスを共通化できる範囲を特定する。

ステップ１５０２において、オブジェクトaのシンボルxを管理するハッシュ・エントリを取得して_Entxに代入する命令を生成する。このように、シンボル・テーブルへのアクセスを最初の１回だけにして、その後はエントリへのアクセスに置き換えることにより、軽量なアクセスとし、アクセス速度を向上させることができる。

次に、ステップ１５０３において、特定された範囲から命令を１つ取り出す。これも、上記と同様、特定された範囲に順に並ぶ命令を、順に取り出すことができる。

ステップ１５０４において、取り出す命令があるかどうかを判定する。取り出す命令がなくなった場合は、ステップ１５１２へ進み、この処理を終了する。これに対し、取り出す命令がある場合は、ステップ１５０５へ進み、その取り出した命令が、シンボル内のオブジェクトの読み込みであるかを判定する。すなわち、i=a.xのような命令であるかを判断する。その命令が読み込みである場合、ステップ１５０６へ進み、_Entx->valからオブジェクトを取り出し、変数iに代入する命令を生成する。図９に示す処理のように、オブジェクトの中のフィールド（_type）を読み出す命令は必要とされない。これは、シンボルが削除されている場合、_Entx->valには0x80000000が代入され、それを読み出すことにより例外を発生させることができるからである。この命令が生成されると、ステップ１５０３へ戻り、次の命令が取り出される。

ステップ１５０５で、取り出した命令が、シンボル内のオブジェクトの読み込みではない場合、ステップ１５０７へ進み、取り出した命令が、シンボルへのオブジェクトの書き込みであるかを判定する。すなわち、a.x=123のような命令であるかを判断する。その命令が書き込みである場合、ステップ１５０８へ進み、_Entx->valの値を読み込んで一時変数tに代入する命令と、_Entx->valにオブジェクト（obj）を代入する命令とを生成する。

ここで、_Entx->valの値を読み込んで一時変数tに代入する命令を生成するのは、ハンドラが実行される値であるかを確認し、それでない場合に、書き込みを行うためである。これらの命令が生成されると、ステップ１５０４へ戻り、次の命令が取り出される。

ステップ１５０７で、取り出した命令が書き込みでないと判定された場合、ステップ１５０９へ進み、取り出した命令が、シンボルの削除であるかを判定する。その命令が削除である場合、ステップ１５１０へ進み、_Entx->valに特別な命令で読み込んだ際にハンドラが実行される値0x80000000を代入する命令を生成する。この命令が生成されると、ステップ１５０４へ戻り、次の命令が取り出される。

ステップ１５０９おいて取り出した命令がシンボルを削除するものでもない場合、ステップ１５１１へ進み、ソース・プログラムを参照し、対応する命令を生成する処理を行い、その後、ステップ１５０４へ戻り、次の命令を取り出す。ここでの命令は、高速処理を行うのに影響を及ぼさない命令であり、例えば、加算、減算、乗算、除算等の演算命令やメソッドの実行命令が挙げられる。これらの命令を従来から知られた命令生成処理により生成する。

図１６は、特別な値が読み出されたときにハンドラが実行する処理の流れを示したフローチャートである。ステップ１６００から処理を開始し、ステップ１６０１において、読み出された特別な値が、図１５のステップ１５１０で生成された命令によるものであるかを判定する。そうである場合、ステップ１６０２へ進み、削除されたシンボルにアクセスしたときに行われる処理を実行する。具体的には、throw noEntryExceptionというハンドラを実行する。そうでない場合は、ステップ１６０３へ進み、従来のメモリ例外処理として強制終了等の処理が実行される。

これまで、本発明の最適化装置および最適化方法について、図面を参照して詳細に説明してきたが、他の実施形態や、追加、変更、削除など、当業者が想到することができる範囲内で変更することができ、いずれの態様においても本発明の作用・効果を奏する限り、本発明の範囲に含まれるものである。

また、最適化方法は、コンピュータにより読み取り可能なコンパイラ・プログラムにより実現することができ、本発明では、このコンパイラ・プログラムを提供することも可能である。なお、コンパイラ・プログラムは、CD-ROM、DVD-ROM、SDカード、HDD等の記録媒体に格納して提供することができる。

動的言語は、開発効率の高さから、規模の大きなシステムにも採用されるようになってきており、それに対応して動的言語の処理系を含むプログラム製品が多く出荷されている。このように動的言語を使用する機会が増加することに伴い、処理速度の向上は重要であり、この処理速度の向上において本発明の最適化装置、その方法およびコンパイラ・プログラムを提供することは有用である。

２００…最適化装置、２０１…ホスト・コントローラ、２０２…CPU、２０３…RAM、２０４…グラフィック・コントローラ、２０５…表示装置、２０６…入出力コントローラ、２０７…通信インタフェース、２０８…HDD、２０９…CD/DVDドライブ、２１０…ROM、２１１…入出力チップ、４００・・・装置、４０１…範囲特定部、４０２…命令生成部、４０３…命令抽出部、４０４…命令判定部

Claims (22)

1. 動的言語により記述されたプログラムを最適化するための最適化装置であって、
   前記プログラムを解釈し、前記プログラムの中の同一変数（シンボル）をアクセスする命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定する範囲特定部と、
   シンボルを識別するためのキーとシンボルに格納される値オブジェクトのアドレスとを対応付けて格納するシンボル・テーブルに、特定された前記範囲に含まれる前記命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、前記キーに基づき対応するシンボルに格納される値オブジェクトのアドレスを保持するシンボルエントリのアドレスを取得してアドレス格納部に格納する命令を含む、前記特定された範囲に含まれる複数の命令に基づき最適化された複数の命令を生成する命令生成部と、
   前記特定された範囲から命令を１つずつ取り出す命令抽出部と、
   取り出した前記命令が前記シンボルへアクセスする命令に該当するか否かを判定する命令判定部とを含み、
   前記命令生成部は、前記命令判定部が前記シンボルへアクセスする命令に該当すると判定した場合、前記命令に基づき、最適化された命令として、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、前記シンボルが存在するとき、前記シンボルが存在するか否かを確認することなく即座に該シンボルへのアクセスを可能にする命令を生成する、最適化装置。
2. 前記プログラムを最適化する処理を、コンパイル時に行われるコード生成時、生成されたコードの実行時にシンボルが生成されたとき、前記実行時のシンボルが削除されたとき、前記実行時のシンボルに格納される値オブジェクトを読み出すとき、前記実行時のシンボルへ値オブジェクトを書き込むときの５つの操作が行われるときに実施する、請求項１に記載の最適化装置。
3. 前記シンボルへアクセスする命令は、前記シンボルに格納される値オブジェクトを読み出す命令、もしくは前記シンボルへ値オブジェクトを書き込む命令、または前記シンボルを削除する命令のいずれかである、請求項１に記載の最適化装置。
4. 前記シンボルが存在するか否かを判定するシンボル判定部をさらに含み、前記シンボル判定部が、前記シンボルが存在しないと判定した場合に、前記命令生成部が、前記シンボルが存在するか否かを確認する命令と、存在しない場合に例外を発生させる命令とを生成する、請求項１に記載の最適化装置。
5. 前記命令生成部は、前記命令判定部が前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、前記アドレス格納部に格納された前記シンボルエントリ内の値オブジェクトのアドレスを不正なアドレスに書き換える命令を生成する、請求項１に記載の最適化装置。
6. 前記命令生成部は、前記命令判定部が前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルの値オブジェクトを読み出す命令または書き込む命令である場合、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、アクセスして取得したシンボルに格納される値オブジェクトのアドレスを０と比較する命令も生成し、前記シンボルを削除する命令である場合、前記値オブジェクトのアドレスとして０を代入する命令を生成する、請求項１に記載の最適化装置。
7. 前記命令生成部は、前記命令判定部が前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、読み出されたときに例外を発生させるハンドラを実行する値を前記値オブジェクトのアドレスの値として代入する命令を生成する、請求項１に記載の最適化装置。
8. 動的言語により記述されたプログラムを最適化するための最適化装置において行われる最適化方法であって、
   前記プログラムを解釈し、前記プログラムの中の同一変数（シンボル）をアクセスする命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定するステップと、
   シンボルを識別するためのキーとシンボルに格納される値オブジェクトのアドレスとを対応付けて格納するシンボル・テーブルに、特定された前記範囲に含まれる前記命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、前記キーに基づき対応するシンボルに格納される値オブジェクトのアドレスを保持するシンボルエントリのアドレスを取得してアドレス格納部に格納する命令を生成するステップと、
   前記特定された範囲から命令を１つずつ取り出すステップと、
   取り出した前記命令が前記シンボルへアクセスする命令に該当するか否かを判定するステップと、
   前記シンボルへアクセスする命令に該当すると判定された場合、前記命令に基づき、最適化された命令として、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、前記シンボルが存在するとき、前記シンボルが存在するか否かを確認することなく即座に該シンボルへのアクセスを可能にする命令を生成するステップとを含む、最適化方法。
9. 前記最適化方法を、コンパイル時に行われるコード生成時、生成されたコードの実行時にシンボルが生成されたとき、前記実行時のシンボルが削除されたとき、前記実行時のシンボルに格納される値オブジェクトを読み出すとき、前記実行時のシンボルへ値オブジェクトを書き込むときの５つの操作が行われるときに実施する、請求項８に記載の最適化方法。
10. 前記シンボルへアクセスする命令は、前記シンボルに格納される値オブジェクトを読み出す命令、もしくは前記シンボルへ値オブジェクトを書き込む命令、または前記シンボルを削除する命令のいずれかである、請求項８に記載の最適化方法。
11. 前記シンボルが存在するか否かを判定するステップをさらに含み、前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルが存在しないと判定された場合に、前記アクセスを可能にする命令を生成するステップにおいて、前記シンボルが存在するか否かを確認する命令と、存在しない場合に例外を発生させる命令とを生成する、請求項８に記載の最適化方法。
12. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、前記アドレス格納部に格納された前記シンボルエントリ内の値オブジェクトのアドレスを不正なアドレスに書き換える命令を生成する、請求項８に記載の最適化方法。
13. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルの値オブジェクトを読み出す命令または書き込む命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、アクセスして取得したシンボルに格納される値オブジェクトのアドレスを０と比較する命令も生成し、前記シンボルを削除する命令である場合、前記値オブジェクトのアドレスとして０を代入する命令を生成する、請求項８に記載の最適化方法。
14. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、読み出されたときに例外を発生させるハンドラを実行する値を前記値オブジェクトのアドレスの値として代入する命令を生成する、請求項８に記載の最適化方法。
15. 動的言語により記述されたプログラムを最適化する最適化方法を実行するためのコンピュータ可読なコンパイラ・プログラムであって、前記コンパイラ・プログラムは、コンピュータに、
    前記プログラムを解釈し、前記プログラムの中の同一変数（シンボル）をアクセスする命令群が含まれる範囲を、シンボルのアクセスを共通化できる範囲として特定するステップと、
    シンボルを識別するためのキーとシンボルに格納される値オブジェクトのアドレスとを対応付けて格納するシンボル・テーブルに、特定された前記範囲に含まれる前記命令群がアクセスするシンボルを識別するためのキーを使用してアクセスし、前記キーに基づき対応するシンボルに格納される値オブジェクトのアドレスを保持するシンボルエントリのアドレスを取得してアドレス格納部に格納する命令を生成するステップと、
    前記特定された範囲から命令を１つずつ取り出すステップと、
    取り出した前記命令が前記シンボルへアクセスする命令に該当するか否かを判定するステップと、
    前記シンボルへアクセスする命令に該当すると判定された場合、前記命令に基づき、最適化された命令として、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、前記シンボルが存在するとき、前記シンボルが存在するか否かを確認することなく即座に該シンボルへのアクセスを可能にする命令を生成するステップとを実行させる、コンパイラ・プログラム。
16. 前記最適化方法を、コンパイル時に行われるコード生成時、生成されたコードの実行時にシンボルが生成されたとき、前記実行時のシンボルが削除されたとき、前記実行時のシンボルに格納される値オブジェクトを読み出すとき、前記実行時のシンボルへ値オブジェクトを書き込むときの５つの操作が行われるときに実施させる、請求項１５に記載のコンパイラ・プログラム。
17. 前記シンボルへアクセスする命令は、前記シンボルに格納される値オブジェクトを読み出す命令、もしくは前記シンボルへ値オブジェクトを書き込む命令、または前記シンボルを削除する命令のいずれかである、請求項１５に記載のコンパイラ・プログラム。
18. 前記シンボルが存在するか否かを判定するステップをさらに実行させ、前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルが存在しないと判定された場合に、前記アクセスを可能にする命令を生成するステップにおいて、前記シンボルが存在するか否かを確認する命令と、存在しない場合に例外を発生させる命令とを生成する、請求項１５に記載のコンパイラ・プログラム。
19. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、前記アドレス格納部に格納された前記シンボルエントリ内の値オブジェクトのアドレスを不正なアドレスに書き換える命令を生成する、請求項１５に記載のコンパイラ・プログラム。
20. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルの値オブジェクトを読み出す命令または書き込む命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、前記アドレス格納部に格納された前記シンボルエントリのアドレスを使用して該シンボルへアクセスする命令を生成する際、アクセスして取得したシンボルに格納される値オブジェクトのアドレスを０と比較する命令も生成し、前記シンボルを削除する命令である場合、前記値オブジェクトのアドレスとして０を代入する命令を生成する、請求項１５に記載のコンパイラ・プログラム。
21. 前記シンボルへアクセスする命令に該当するか否かを判定するステップで、前記シンボルへアクセスする命令に該当する場合であって、前記命令が前記シンボルを削除する命令である場合、前記アクセスを可能にする命令を生成するステップにおいて、読み出されたときに例外を発生させるハンドラを実行する値を前記値オブジェクトのアドレスの値として代入する命令を生成する、請求項１５に記載のコンパイラ・プログラム。
22. 請求項１５〜請求項２１のいずれか１項に記載のコンパイラ・プログラムが記録された記録媒体。