(57)【要約】      （修正有）【課題】計算機ソフトウエアの分岐アドレスを管理し、メモリ領域の有効利用を図る。【解決手段】相対アドレスが用いられる命令セットアーキテクチャを採用するルーチン１０６０が、メモリ空間上を移動した場合に、分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリ上の分岐先管理エントリ１０５３に生成し、前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する。【選択図】図１０
2014010661.tif 000002
【特許請求の範囲】
【請求項１】
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理をコンピュータに実行させるプログラムであって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリ上の分岐先管理エントリに生成し、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、
処理をコンピュータに実行させるプログラム。
【請求項２】
前記分岐命令が移動した場合、前記分岐命令の分岐先相対アドレスを、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスに修正する、
処理を更にコンピュータに実行させる請求項１記載のプログラム。
【請求項３】
前記分岐先管理エントリに、前記分岐先ルーチンを特定する情報が既に存在する場合、
前記生成する処理を実行しない、
請求項１又は２に記載のプログラム。
【請求項４】
前記分岐命令が、コール命令である場合であって、前記コール命令が実行された後に、前記コール命令に対応するリターン命令が実行される前に、前記リターン命令の戻り相対アドレスに位置する命令が、所定のオフセットだけ移動した場合、前記所定のオフセットに基づいて、前記リターン命令の戻り相対アドレスを修正する、
処理を更にコンピュータに実行させる、請求項１ないし３のうちいずれか１項に記載のプログラム。
【請求項５】
前記ルーチンの移動前のアドレスの範囲をメモリに記憶する処理を更にコンピュータに実行させ、
前記戻り相対アドレスを修正する処理は、
記憶された前記ルーチンの移動前のアドレスの範囲に、修正前の前記戻り相対アドレスが入ることを判断する、処理を含む、
請求項４記載のプログラム。
【請求項６】
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理をコンピュータが実行する方法であって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリの分岐先管理エントリに生成し、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、
処理を有する方法。
【請求項７】
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理を行う装置であって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリの分岐先管理エントリに生成する、分岐先管理エントリ生成部と、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定する、分岐命令設定部と、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、ジャンプ先修正部と、
を有する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機ソフトウエアの分岐アドレスを管理するプログラム、方法、及び装置に関する。
【背景技術】
【０００２】
計算機システムにおけるプログラムは、機械語で記述されたルーチンをプロセッサが処理することで動作する（本明細書では、機械語で記述された１つ以上のコードのことを「ルーチン」と記す）。
【０００３】
ルーチンに含まれる命令は、プロセッサによって１つずつ順に処理される。しかし、ほとんどのプログラムのルーチンは、次に処理する命令を、条件に応じて直後の命令以外に変更したり、あるいは別のルーチンの命令に変更したりする命令を含む。このような次に処理する命令のアドレスを変更する命令のことを、一般的に「分岐命令」と呼ぶ。
【０００４】
分岐命令によって処理の順序が変わる例を図１に示す。分岐命令の名称や命令のコードはプロセッサによって様々である。一般的なプロセッサの命令セットには、分岐命令としてジャンプ命令とコール・リターン命令が存在する（コール・リターン命令は、コール命令とリターン命令に分けられる）。本明細書において、分岐命令とは、ジャンプ命令、コール／リターン命令等を総称する用語として用いる。
【０００５】
図１に示すように、命令Ａ２がジャンプ命令である場合、命令Ａ２の後に処理される命令を、直後の命令Ａ３ではなく、命令Ａ４とすることができる。また、命令Ａ４が、ルーチンＢをコールするコール命令である場合には、命令Ａ４の実行後に、処理はルーチンＢの命令Ｂ１に移る。その後、ルーチンＢの命令Ｂ２ないしＢ４が順に処理される。そして、命令Ｂ５がリターン命令である場合には、ルーチンＡの命令Ａ４の直後の命令Ａ５に処理が戻る。コール命令はリターン命令と対で用いられる。リターン命令を実行した際に、戻るアドレスを保持しておくために、スタックポインタの操作などが伴う。一般的には、同じルーチン内で分岐する目的にはジャンプ命令、別のルーチン内の命令に分岐する目的にはコール・リターン命令が用いられることが多い。
【０００６】
ルーチンに含まれる個々の命令は、主に命令の種類を示す「オペコード」と命令の演算対象となる値を示す「オペランド」で構成される。ジャンプ命令とコール命令のオペランドには、分岐先の命令の存在するアドレスが格納される。多くの場合、そのアドレスは分岐元の命令からの相対アドレスで表現される。
【０００７】
なお、本明細書で用いるアドレスは、仮想アドレスであっても、実アドレスであってもよい。また、本明細書では、Ｊａｖａ（登録商標）を例として用いる場合があるが、本発明の対象がＪａｖａに限定されるものではない点に留意すべきである。
【０００８】
Ｊａｖａで書かれたプログラムは、バイトコードに変換される。バイトコードはＪａｖａＶＭ（Ｊａｖａ仮想マシン）で実行される。そのため、Ｊａｖａで書かれたプログラムは、ＪａｖａＶＭをサポートしているコンピュータならばＣＰＵを問わず動作する。したがって、Ｊａｖａは、マルチプラットフォームで動作する利点を持つ。一般的なＪａｖａ  ＶＭは、「バイトコード」をプロセッサ固有の機械語に逐次変換して、プロセッサにその機械語を処理させる。しかし、バイトコードの逐次変換は、その処理コストが高くなる場合が多い。
【０００９】
そこで、プログラム実行中にバイトコードをメソッド単位で機械語のルーチンに変換する技術が存在する。そのような技術は、一般的に「ＪＩＴ（Ｊｕｓｔ  ｉｎ  ｔｉｍｅ）コンパイラ」と呼ばれる。
【００１０】
図２は、一般的なＪＩＴコンパイラの処理を示している。ステップ２０２において、ＪＩＴコンパイラは、コンパイル対象のメソッドのバイトコードを、ホストマシンに依存しない中間コードに変換する。ステップ２０４において、ＪＩＴコンパイラは、中間コードをホストマシンの機械語ルーチンに変換する。ステップ２０６において、機械語ルーチンを、メモリ上の機械語ルーチン領域に書き込む。その結果、コンパイルされたメソッドはすべてプロセッサ固有の機械語ルーチンで表現されるため、プロセッサが直接その機械語ルーチンを処理できるようになる。以降の説明では、ＪＩＴコンパイラが生成する機械語ルーチンを格納するメモリ領域を「ルーチン領域」と記す。
【００１１】
プログラムの処理が進むと、ルーチンが不要になることがあるため、ルーチン領域の内容は時間とともに変化する。すなわち、ルーチンの数やメモリの使用量は常に変動する。不要になったルーチンは、ガーベジコレクションを実行することにより、他のルーチンのために開放される。しかしながら、単純にガーベジコレクションを実行した場合に特に問題となるのが、フラグメントの発生である。
【００１２】
図３は、メモリ上のフラグメントの発生を示している。それぞれのメソッドのルーチンは、ほとんどの場合、分岐命令を含んでいる。その分岐先を示すオペランドが相対アドレスの場合、分岐命令を含むルーチンを単純に移動すると分岐先を誤ることになる。また、分岐先が移動した場合も同様である。そのため、不要になったルーチンが増えてルーチン領域に空きができても、ルーチンを移動してメモリ領域を寄せ集めることができないこととなる。このため、フラグメントが存在したままとなる。
【００１３】
仮想メモリが利用されている場合であっても、ルーチン領域の大きさには制限がある。なぜなら、仮想メモリ領域も無限ではないからである。したがって、フラグメントは、仮想メモリ空間であっても仮想メモリ資源を圧迫し得る。
【００１４】
なお、メモリ領域のフラグメントを解消する技術としては、空きメモリ領域を寄せ集めるコンパクション型のガーベジコレクションなどが存在する。しかし、上述のように、相対アドレスを使って分岐するルーチンは移動できない。そのため、ルーチン領域に対してコンパクション型のガーベジコレクションを有効に適用できない。
【００１５】
ＪＩＴコンパイルの最小単位は、メソッドと呼ばれるサブルーチンである。フラグメントが発生すると、すべての空きメモリを足せば余裕があるような状況でも、個々の空きメモリのサイズが小さいために、例えばＪＩＴコンパイラでコンパイルされたルーチンのためのメモリを割り当てられないことがある。ルーチン領域にメモリを割り当てられないときは、アプリケーションが停止することがある。これを避けるために、このときＪＩＴコンパイラは、そのメソッドをコンパイルしないという選択肢が取られることもある。あるいはＪＩＴコンパイラの最適化レベルを低くしてよりメモリを消費しないコンパイルに切り替えるという選択肢がとられることもある。
【００１６】
従来、ユーザプログラムがＩ／Ｏ処理等によってブロッキングしている間にガーベジコレクションが起動され、そのガーベジコレクションの終了前に、Ｉ／Ｏブロッキングが終了し、ユーザプログラムが再開されるというように、メモリコンパクション中に不正なメモリアクセスを行うことを避ける技術が存在する（例えば、特許文献１参照）。
【００１７】
また、従来、ＪＩＴコンパイルされるメソッドが、フレーム（ローカル変数を格納する領域）を作らないで実行できるかどうかを判別し、そのようなメソッドに対してはフレームを作らないで実行するネイティブコードを生成し、メソッドの呼び出しを効率化する技術が存在する（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２０００−１８１７２３号公報
【特許文献２】特開２００５−２８４７２９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
１つの側面では、本発明は、計算機ソフトウエアの分岐アドレスを管理し、メモリ領域の有効利用を図ることを目的とする。
【課題を解決するための手段】
【００２０】
一態様のプログラムは、相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理をコンピュータに実行させるプログラムであって、分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリ上の分岐先管理エントリに生成し、前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、処理をコンピュータに実行させる。
【発明の効果】
【００２１】
一態様によれば、計算機ソフトウエアの分岐アドレスを管理し、メモリ領域の有効利用を図ることができる。
【図面の簡単な説明】
【００２２】
【図１】分岐命令による処理を示す図である。
【図２】一般的なＪＩＴコンパイラの処理を示す図である。
【図３】メモリ上のフラグメントの発生を示す図である。
【図４】一実施形態のＪＩＴコンパイルの処理を示す図である。
【図５】一実施形態の分岐先管理テーブル内に格納された分岐先管理エントリを用いた分岐を示す図である。
【図６】一実施形態に従った、ルーチンを移動させる処理の概要を示すフローチャートである。
【図７】一実施形態に従った、ルーチンを移動させる処理の詳細を示すフローチャートである。
【図８】一実施形態に従った、ルーチン移動管理テーブルを示す図である。
【図９】一実施形態に従った、リターン命令の戻りアドレス調整処理のフローチャートを示す図である。
【図１０】一実施形態の機能ブロック図である。
【図１１】一実施形態のハードウェアの構成例を示す図である。
【発明を実施するための形態】
【００２３】
以下に、図面を用いて本発明の実施形態を詳細に説明する。なお、以下の実施形態は、発明を理解するためのものであり、本発明の範囲を限定するためのものではない点に留意すべきである。また、以下の複数の実施形態は、相互に排他的なものではない。したがって、矛盾が生じない限り、実施形態の各要素を組み合わせることも意図されていることに留意すべきである。また、請求項に記載された方法やプログラムに係る発明は、矛盾のない限り処理の順番を入れ替えてもよく、あるいは、複数の処理を同時に実施してもよい。そして、これらの実施形態も、請求項に記載された発明の技術的範囲に包含されることは言うまでもない。
【００２４】
また、コンピュータが読み出したプログラムコードを実行することにより、後述の実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳなどの他のプログラムが実際の処理の一部または全部を行ない、その処理によって実施形態の機能が実現される場合も、本発明に含まれることは言うまでもない。
【００２５】
なお、本明細書では、ＪＩＴコンパイルがメソッド単位で行われることとして説明を行う。また、メソッドをＪＩＴコンパイルした機械語の集合をルーチンと呼ぶ。なお、本発明は、これに限定されるものではない。
【実施例】
【００２６】
図４は、一実施形態のＪＩＴコンパイルの処理を示す図である。なお、ＪＩＴコンパイル処理のうち、本発明に関連の薄い他の処理については、理解を容易にするために省略している点に留意すべきである。
【００２７】
なお、図４に示す処理は、ＪＩＴコンパイル内での処理であるとして説明するが、ＪＩＴコンパイルが終了し、機械語ルーチンが生成された後に、この処理の一部又は全部を実行してもよい。この処理が、ＪＩＴコンパイル内で行われるか否かは問わない。
【００２８】
ステップ４０２において、コンパイルする命令コードが分岐命令か否かがチェックされる。分岐命令でない場合には、処理はステップ４４０に移る。分岐命令である場合には、処理はステップ４０４に移る。
【００２９】
ステップ４４０においては、機械語のオペランド及びオペコードが指定されて、機械語の命令が出力される。
【００３０】
ステップ４０４においては、分岐命令の種類の判定が行われる。分岐命令がジャンプ命令であれば、ステップ４０６に移る。分岐命令がコール命令であれば、ステップ４０８に移る。
【００３１】
ステップ４０６においては、生成する機械語のオペコードをジャンプ命令とする。
【００３２】
ステップ４０８においては、生成する機械語のオペコードをコール命令とする。
【００３３】
ステップ４１０においては、分岐先のアドレスが、固定であるか否か、又は分岐先が自己のメソッド内か否かが判断される。分岐先のルーチンが、例えばＣ言語などでコーディングされ、静的にコンパイルされた機械語である場合（分岐先のルーチンが移動しない場合）には、後述する「分岐先管理エントリ」を生成しなくてもよい。また、分岐先が自己のメソッド内である場合には、後述する「分岐先管理エントリ」を生成しなくてもよい。この判断が「はい」である場合には、ステップ４３０に移る。この判断が「いいえ」である場合、すなわち、分岐先アドレスが、固定アドレスではなく、かつ自己のメソッド外への分岐である場合には、処理はステップ４２０に移る。
【００３４】
ステップ４３０においては、分岐命令のオペランドを分岐先の命令への相対アドレスとする。すなわち、オペランドには、分岐先の命令の位置するアドレスと、分岐命令の位置するアドレスとの差が格納されてもよい。
【００３５】
ステップ４２０においては、分岐先管理エントリが既に存在しているか否かがチェックされる。分岐先管理エントリには、分岐先を特定する情報と、新たに生成されたジャンプ命令とが含まれる。分岐先を特定する情報としては、例えば、分岐先のメソッド名などが用いられてもよい。あるいは、分岐先のアドレスが用いられてもよい。新たに生成されたジャンプ命令は、分岐先のルーチンがメモリ上を移動した場合に、分岐先のルーチンの移動に従って、ジャンプ先が置換されてもよい。これによって、生成されたジャンプ命令は、移動した分岐先にジャンプすることができる。既に分岐先管理エントリが存在している場合には、処理は、ステップ４２８に移る。分岐先管理エントリが、未だ生成されていない場合には、ステップ４２２に移る。なお、分岐先エントリが既に存在するか否かの判断は、分岐先を特定する情報と新たに生成されたジャンプ命令との双方のペアが既に存在しているか否かをチェックしてもよい。或いは、分岐先を特定する情報だけで、分岐先管理エントリが一意に特定できる場合には、分岐先を特定する情報だけをチェックしてもよい。例えば、１つのルーチンに複数のジャンプ先が存在し得る場合であって、分岐先を特定する情報が、ルーチンの名前である場合には、分岐先を特定する情報（ルーチンの名前）と、ジャンプ命令のオペランド内の分岐先相対アドレスとの双方をチェックすることが望ましい。或いは、分岐先を特定する情報として、分岐先の絶対アドレスを用いる場合には、分岐先を特定する情報（分岐先の絶対アドレス）だけをチェックしてもよい。なお、分岐先を特定する情報として、分岐先の絶対アドレスを用いた場合には、その分岐先の移動に従って、分岐先管理エントリの分岐先を特定する情報（分岐先の絶対アドレス）を書き換える。
【００３６】
ステップ４２２において、新たな分岐先管理エントリが生成される。上述のように分岐先管理エントリには、「分岐先のメソッドを示す情報」及び「ジャンプ命令」が含まれる。
【００３７】
ステップ４２４において、分岐先管理エントリの「ジャンプ命令」のオペランドに、分岐先への相対アドレスを設定する。この設定によって、生成された「ジャンプ命令」は、分岐先にジャンプすることができる。
【００３８】
ステップ４２６において、分岐先管理エントリの「分岐先のメソッドを示す情報」に分岐先メソッドの名前が設定される。なお、「分岐先のメソッドを示す情報」に格納される情報は、分岐先メソッドの名前に限られるものではない。分岐先メソッドを特定できる情報であれば、他の情報であってもよい。例えば、分岐先メソッドがコンパイルされたルーチンの分岐先の絶対アドレスであってもよい。
【００３９】
ステップ４２８において、分岐命令の機械語のオペランドを、生成された「ジャンプ命令」への相対アドレスとする。この処理によって、分岐命令は、生成された「ジャンプ命令」にジャンプすることができる。この処理を行うことによって、分岐命令は、生成された「ジャンプ命令」を経由して、目的の分岐先の命令に処理を移すことができる。
【００４０】
なお、この生成された「ジャンプ命令」にはスタックポインタの変更などの作用がないため、分岐元の命令がコール命令であっても、分岐先のメソッドがリターン命令を実行すれば分岐元のメソッドに処理を戻すことができる。
【００４１】
ステップ４４０において、オペコードとオペランドを指定して、機械語の命令を出力する。
【００４２】
図５は、一実施形態の分岐先管理テーブル内に格納された分岐先管理エントリを用いた分岐を示す図である。
【００４３】
メソッドＡ（５１０）における、ｃａｌｌメソッドＢ（５１２）の命令は、メソッドＢをコールする命令である。この命令は、直接メソッドＢをコールしなくてもよい。すなわち、分岐先管理テーブル５５０内の分岐先管理エントリＢ（５５１）に存在するジャンプ命令５５３に処理が移る。ジャンプ命令５５３を経由して、メソッドＢ（５２０）の命令１（５２２）をコールする。そして、リターン命令ＲＥＴＵＲＮ（５２４）により、メソッドＡ（５１０）の命令３（５１４）に戻る。
【００４４】
図５において、メソッドＡ（５１０）のジャンプ命令ＪＵＭＰメソッドＣ（５１６）が実行されると、分岐先管理テーブル５５０内の分岐先管理エントリＣ５５５に存在するジャンプ命令５５７を経由して、メソッドＣ（５３０）の命令１（５３２）にジャンプすることができる。
【００４５】
このように、コール命令及びジャンプ命令は、分岐先管理テーブル５５０内の分岐先管理エントリに存在するジャンプ命令を介して、分岐先に処理を移す。
【００４６】
更に図５を参照すると、分岐先管理エントリＢには、分岐先であるメソッドＢを示す情報５５２が存在する。また、分岐先管理エントリＣには、分岐先であるメソッドＣを示す情報５５６が存在する。これらの情報は、分岐先が移動した場合に利用される情報である。分岐先が移動した場合の処理の詳細については後述する。
【００４７】
図６は、一実施形態に従った、ルーチンを移動させる処理の概要を示すフローチャートである。ここでの処理は、１つ以上のルーチンを移動させ、連続した空きメモリ領域を拡大させる処理の例を示している。
【００４８】
ステップ６０２において、全てのスレッドを停止させる。スレッドが動いている場合には、メモリ領域に動的に新たなルーチンが生成される場合がある。したがって、この処理を行う場合には、全てのスレッドを停止させることが望ましい。
【００４９】
ステップ６０４において、ルーチン領域に含まれる先頭のルーチンを「対象ルーチン」とする。この処理は、１つ以上のルーチンに対して、先頭から順番に処理するために、現在注目しているルーチンを最初に特定するために行う処理である。
【００５０】
ステップ６０６において、「対象ルーチン」が存在するか否かがチェックされる。判断結果が「いいえ」であれば、処理はステップ６１６に移る。判断結果が「はい」であれば、ステップ６０８に移る。
【００５１】
ステップ６０８において、ルーチン領域に、「対象ルーチン」よりもアドレス上小さい部分に空きが存在するか否かがチェックされる。判断結果が「いいえ」であれば、処理はステップ６１２に移る。判断結果が「はい」であれば、ステップ６１０に移る。この判断が「はい」であれば、アドレス上小さい部分に空きが存在することになるため、対象ルーチンをアドレス上小さい方向に移動させれば、この空きを無くすことができる。
【００５２】
ステップ６１０において、ルーチンの移動が実行される。この処理については、ルーチンを移動させる処理の詳細フローチャート（図７）を参照しながら後述する。
【００５３】
ステップ６１２において、ルーチン領域に、「対象ルーチン」よりもアドレス上大きい部分にルーチンが存在するか否かが判断される。判断結果が「いいえ」であれば、処理はステップ６１６に移る。判断結果が「はい」であれば、処理は、ステップ６１４に移る。
【００５４】
ステップ６１４において、アドレス上の位置が「対象ルーチン」の次に大きいルーチンを「対象ルーチン」とする。この処理によって、次に移動させるルーチンを注目ルーチンとして特定する。そして、処理は、ステップ６０８に戻る。
【００５５】
ステップ６１６において、コール命令に対応するリターン命令が実行された場合であって、リターン命令が実行される前に、全スレッドが停止した場合に対する処理が行われる。すなわち、この一連の処理によって、リターン命令の戻り先が移動してしまう場合が想定される。この場合には、リターンが正しく行われるように、リターン命令の戻りアドレスを調整する処理を行う。この処理の詳細は、リターン命令の戻りアドレス調整処理のフローチャート（図９）を用いて後述する。
【００５６】
ステップ６１８において、停止していた全てのスレッドを動かす。以上の処理によって、１つ以上のルーチンが移動し、連続した空きメモリ領域が拡大し、メモリのフラグメンテーションを解消することができる。
【００５７】
図７は、一実施形態に従った、ルーチンを移動させる処理の詳細を示すフローチャートである。
【００５８】
ステップ７０２において、移動対象のルーチンの移動先アドレスを計算する。この計算は、アドレス上小さい部分に存在した空き領域の大きさだけ移動するよう、移動先のアドレスを決定してもよい。
【００５９】
ステップ７０４において、移動対象の「ルーチンの移動前アドレス」「サイズ」「移動先アドレスから移動前アドレスを引いた値」をそれぞれ「移動前のアドレス」「ルーチンのサイズ」「オフセット」とするルーチン移動管理エントリを、ルーチン移動管理テーブルに作成することが望ましい。ここで作成される情報は、コール命令が実行された場合であって、リターン命令が実行される前に、ステップ６０２において全スレッドが停止した場合であって、戻り先のルーチンの移動により、戻りアドレスが移動した場合、戻りアドレスの調整を行う際に利用する情報を保存するためのものである。この情報を用いた処理の詳細については、後述する。
【００６０】
ステップ７０６において、移動対象のルーチンに対応する分岐先管理エントリが存在するか否かが判断される。判断結果が「いいえ」であれば、処理は、ステップ７１０に移る。判断結果が「はい」であれば、処理はステップ７０８に移る。
【００６１】
ステップ７０８において、分岐先管理エントリのジャンプ命令のジャンプ先相対アドレスが移動先アドレスとなるよう修正する。分岐先管理エントリが存在しているということは、移動するルーチンは、他のルーチンからジャンプ命令又はコール命令によって分岐対象となっているルーチンである。したがって、分岐先管理エントリに存在するジャンプ命令のジャンプ先を、ルーチンの移動に従って調整する。
【００６２】
ステップ７１０において、移動対象のルーチンの先頭の命令を「確認対象命令」とする。この処理によって、ルーチン内の注目する命令として、まずルーチンの先頭の命令が特定される。
【００６３】
ステップ７１２において、「確認対象命令」が移動対象のルーチン外への分岐命令であるか否かが判断される。この判断が「いいえ」であれば、処理はステップ７１６に移る（「確認対象命令」が移動対象のルーチンの中のアドレスへの分岐命令である場合には、分岐命令のオペランド内のアドレス情報の修正は不要である）。この判断が「はい」であれば、処理はステップ７１４に移る。
【００６４】
ステップ７１４において、移動対象のルーチンの移動後のアドレスから移動前のアドレスを引き、その計算結果を「確認対象命令」のオペランドから引く処理が行われる。この処理は、「確認対象命令」のオペランドが、分岐先管理エントリのジャンプ命令になるよう、オペランドに格納されている相対アドレスを調整する処理である。
【００６５】
ステップ７１６において、「確認対象命令」の次に命令が存在するか否かが判断される。判断が「いいえ」であれば、処理は、ステップ７１８に移る。判断が「はい」であれば、処理はステップ７１２に戻る。
【００６６】
以上の処理によって、分岐先管理エントリが存在する場合には、対応するジャンプ命令のジャンプ先が、移動対象ルーチンの移動先のアドレスとなるよう、正しく調整される。加えて、移動対象ルーチン内に存在する全ての分岐命令のオペランドの内容も、分岐先管理エントリのジャンプ命令の存在するアドレスとなるよう、正しく調整される。
【００６７】
ステップ７１８において、移動対象のルーチンの内容を移動先にコピーする処理が実行される。
【００６８】
図８は、一実施形態に従った、ルーチン移動管理テーブルを示す図である。ルーチン移動管理テーブル８００には、ルーチン移動管理エントリ８１０が含まれる。ルーチン移動管理エントリ８１０内には、ルーチンの移動前のアドレス８１２、ルーチンのサイズ８１４、ルーチンのアドレス移動量であるオフセット８１６が含まれる。なお、ルーチンの移動前のアドレス８１２は、例えば、ルーチンの先頭アドレスであってもよい。ルーチンの移動前のアドレス８１２と、サイズ８１４によって、そのルーチンが移動前に占めていたアドレスの範囲を知ることができる。このアドレスの範囲に、リターン命令の戻りアドレスが入る場合には、戻りアドレスを、オフセット値に基づいて調整する。戻り先のルーチンが移動しても、この戻りアドレスの調整によって、リターン命令が適切に実行されることを担保する。
【００６９】
図９は、一実施形態に従った、リターン命令の戻りアドレス調整処理のフローチャートを示す図である。
【００７０】
ステップ９０２において、処理していないスレッドが存在しているか否かが判断される。全てのスレッドを停止した際に、処理途中のスレッドにおいては、コール命令が実行された後、リターン命令が実行されていない場合があり得る。この判断が「いいえ」であれば、処理は、ステップ９１０に移る。この判断が「はい」であれば、処理はステップ９０４に移る。
【００７１】
ステップ９０４において、処理していないフレームが存在するか否かが判断される。Ｊａｖａにおいては、コール・リターン命令は、スレッド単位にスタックで管理され、スタックの情報は、フレームを単位として扱われる。したがって、フレームが存在する場合には、リターン命令が実行されていない状態であることが分かる。この判断が「いいえ」であれば、処理は、ステップ９０２に戻り、他のスレッドについての調査が行われる。この判断が「はい」であれば、処理はステップ９０６に移る。
【００７２】
ステップ９０６において、フレームに記録されている戻りアドレスが、「ルーチン移動管理テーブル」に存在する「ルーチン移動管理エントリ」のうち、いずれかの範囲に含まれるか否かが判断される。すなわち、戻りアドレスが、移動前のルーチンが存在したアドレス範囲内にあるか否かが判断される。この判断が「いいえ」であれば、戻りアドレスを調整しなくてもよい。このため、処理はステップ９０４に戻り、他のフレームについての調査が行われる。この判断が「はい」であれば、処理はステップ９０８に移る。
【００７３】
ステップ９０８において、フレームに記録されている戻りアドレスに、該当する「ルーチン移動管理エントリ」の「オフセット」を加算する。この処理によって、戻りアドレスが移動後のルーチンのアドレスに修正されるため、戻りアドレスが適切に調整される。
【００７４】
ステップ９１０において、「ルーチン移動管理テーブル」に含まれるすべての「ルーチン移動管理エントリ」を削除する。この処理を行う理由は、全ての戻りアドレスの調整が終わったため、「ルーチン移動管理テーブル」に含まれる全ての「ルーチン移動管理エントリ」の情報が不要となるためである。そして、新たなルーチンの移動のための処理を適切に行うために、これらの情報をクリアすることが望ましい。
【００７５】
図１０は、一実施形態の機能ブロック図である。
【００７６】
図１０に示す実施形態は、ＪＩＴコンパイラ１０１０、移動制御部１０５０、及び１つ以上のルーチン１０６０を含む。ＪＩＴコンパイラ１０１０は、分岐先管理エントリ生成部１０１２と、分岐命令設定部１０１４とを含む。分岐先管理エントリ生成部１０１２は、例えば、分岐先管理エントリ５５１を生成してもよい。なお、既に分岐先管理エントリ５５１が存在する場合には、同じエントリを重複して作成しなくてもよい。なぜなら、分岐先管理エントリが一つ存在すれば、同一の分岐先を示す複数の分岐命令は、１つの分岐先管理エントリを共用することができるからである。
【００７７】
分岐命令設定部１０１４は、ＪＩＴコンパイルする分岐命令のオペランドに、ジャンプ命令５５３の存在するアドレスを格納する。これによって、ＪＩＴコンパイルされる分岐命令は、例えば、図５の分岐先管理エントリＢ（５５１）内のジャンプ命令５５３を経由して、メソッドＢ（５２０）に分岐することができる。
【００７８】
図１０において、移動制御部１０５０は、ジャンプ先修正部１０５２、分岐命令修正部１０５４、ルーチン移動管理エントリ生成部、戻り相対アドレス修正部１０５８、戻り相対アドレス判断部１０５９を有する。
【００７９】
ジャンプ先修正部１０５２は、分岐先のルーチンが移動した場合に、分岐先管理エントリ５５１にあるジャンプ命令のオペランドを修正する。
【００８０】
分岐命令修正部１０５４は、分岐命令が移動した場合に、その分岐命令のオペランドを修正する。
【００８１】
ルーチン移動管理エントリ生成部１０５６は、ルーチン移動管理エントリ８１０を生成する。
戻り相対アドレス判断部１０５９は、ルーチン移動管理エントリ８１０の内容を参照して、リターン命令の戻りアドレスが、移動前のルーチンのアドレス範囲にあるか否かを判断する。この判断が肯定的であれば、リターン命令が移動後のルーチンに戻るよう、戻り相対アドレス修正部１０５８が、戻りアドレスを修正する。
ルーチン１０６０、分岐先管理エントリ５５１、及びルーチン移動管理エントリ８１０は、メモリに存在してもよい。
【００８２】
図１１は、一実施形態のハードウェアの構成例を示す図である。ハードウェアは、プロセッサ１１０２、メモリ１１０４、表示制御部１１０６、表示装置１１０８、入出力装置１１１０、通信制御部１１１２、ドライブ装置１１１４、ハードディスク１１１８が含まれる。そして、それぞれの機器は、バス１１２０によって接続されている。また、ドライブ装置１１１４は、可搬記録媒体１１１６を読み書きすることができる。そして通信制御部１１１２には、ネットワーク（不図示）が接続されてもよい。
【００８３】
一実施形態におけるＪａｖａＶＭや、ＪａｖａＶＭ上で動作するＪＩＴコンパイラは、メモリ１１０４、ハードディスク１１１８等に格納され、プロセッサ１１０２によって、動作する。コンパイルされた機械語ルーチンは、仮想メモリアーキテクチャを介してメモリ１１０４上に配置されてもよい。
【００８４】
なお、本実施形態の全部又は一部はプログラムによってインプリメントされ得る。このプログラムは、可搬記録媒体１１１６に格納することができる。可搬記録媒体１１１６とは、構造（ｓｔｒｕｃｔｕｒｅ）を有する１つ以上の非一時的（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ）な、有形（ｔａｎｇｉｂｌｅ）な、記憶媒体を言う。例示として、可搬記録媒体１１１６としては、磁気記録媒体、光ディスク、光磁気記録媒体、不揮発性メモリなどがある。磁気記録媒体には、ＨＤＤ、フレキシブルディスク（ＦＤ）、磁気テープ（ＭＴ）などがある。光ディスクには、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）などがある。また、光磁気記録媒体には、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ  ｄｉｓｋ）などがある。可搬型記録媒体に格納されたプログラムが読み込まれ、プロセッサによって実行されることにより、本発明の実施形態の全部又は一部が実施され得る。
【００８５】
なお、本明細書では、相対アドレスを用いる分岐命令を用いた実施形態を説明したが、分岐命令に絶対アドレスが用いられる場合にも、実施形態の思想は応用できるものである。具体的には、分岐先（リターン命令の戻り先を含む）が、メモリ上を移動した場合には、分岐先（リターン命令の戻り先を含む）の絶対アドレスが変動するため、この側面に関する限り本実施形態に従った処理を行うことが望ましい。しかしながら、分岐元（リターン命令を含む）がメモリ上を移動しても、分岐先（リターン命令の戻り先を含む）の絶対アドレスは変動しないため、この側面に関する限り本実施例に従った処理は行わなくてもよいこととなる。なお、メモリ上をルーチンが移動する場合には、そのルーチンは、分岐元でありかつ分岐先である可能性があるため、上記２つの側面が同時に発生することがある点に留意すべきである。
【００８６】
以上の実施形態に関し、以下の付記を開示する。
（付記１）
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理をコンピュータに実行させるプログラムであって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリ上の分岐先管理エントリに生成し、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、
処理をコンピュータに実行させるプログラム。
（付記２）
前記分岐命令が移動した場合、前記分岐命令の分岐先相対アドレスを、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスに修正する、
処理を更にコンピュータに実行させる付記１記載のプログラム。
（付記３）
前記分岐先管理エントリに、前記分岐先ルーチンを特定する情報が既に存在する場合、
前記生成する処理を実行しない、
付記１又は２に記載のプログラム。
（付記４）
前記分岐命令が、コール命令である場合であって、前記コール命令が実行された後に、前記コール命令に対応するリターン命令が実行される前に、前記リターン命令の戻り相対アドレスに位置する命令が、所定のオフセットだけ移動した場合、前記所定のオフセットに基づいて、前記リターン命令の戻り相対アドレスを修正する、
処理を更にコンピュータに実行させる、付記１ないし３のうちいずれか１項に記載のプログラム。
（付記５）
前記ルーチンの移動前のアドレスの範囲をメモリに記憶する処理を更にコンピュータに実行させ、
前記戻り相対アドレスを修正する処理は、
記憶された前記ルーチンの移動前のアドレスの範囲に、修正前の前記戻り相対アドレスが入ることを判断する、処理を含む、
付記４記載のプログラム。
（付記６）
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理をコンピュータが実行する方法であって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリの分岐先管理エントリに生成し、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定し、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、
処理を有する方法。
（付記７）
前記分岐命令が移動した場合、前記分岐命令の分岐先相対アドレスを、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスに修正する、
処理を更に有する付記６記載の方法。
（付記８）
前記分岐先管理エントリに、前記分岐先ルーチンを特定する情報が既に存在する場合、
前記生成する処理を実行しない、
付記６又は７に記載の方法。
（付記９）
前記分岐命令が、コール命令である場合であって、前記コール命令が実行された後に、前記コール命令に対応するリターン命令が実行される前に、前記リターン命令の戻り相対アドレスに位置する命令が、所定のオフセットだけ移動した場合、前記所定のオフセットに基づいて、前記リターン命令の戻り相対アドレスを修正する、
処理を更に有する、付記６ないし８のうちいずれか１項に記載の方法。
（付記１０）
前記ルーチンの移動前のアドレスの範囲をメモリに記憶する処理を更に有し、
前記戻り相対アドレスを修正する処理は、
記憶された前記ルーチンの移動前のアドレスの範囲に、修正前の前記戻り相対アドレスが入ることを判断する、処理を含む、
付記９記載の方法。
（付記１１）
相対アドレスが用いられる命令セットアーキテクチャを採用するルーチンが、メモリ空間上を移動した場合に、アドレスの管理を行う装置であって、
分岐命令の分岐先ルーチンを特定する情報と、新たなジャンプ命令であって、前記新たなジャンプ命令のジャンプ先として前記分岐先ルーチンへの相対アドレスが設定される、新たなジャンプ命令とを、対応付けてメモリの分岐先管理エントリに生成する、分岐先管理エントリ生成部と、
前記分岐命令の分岐先相対アドレスとして、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスを設定する、分岐命令設定部と、
前記分岐先ルーチンが移動した場合、前記分岐先管理エントリを参照して、前記分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令のジャンプ先を、前記分岐先ルーチンの移動後の位置への相対アドレスに修正する、ジャンプ先修正部と、
を有する装置。
（付記１２）
前記分岐命令が移動した場合、前記分岐命令の分岐先相対アドレスを、前記分岐命令の分岐先ルーチンを特定する情報に対応する前記新たなジャンプ命令の位置への相対アドレスに修正する、分岐命令修正部、
処理を更に有する付記６記載の装置。
（付記１３）
前記分岐先管理エントリに、前記分岐先ルーチンを特定する情報が既に存在する場合、
前記分岐先管理エントリ生成部を実行しない、
付記１１又は１２に記載の装置。
（付記１４）
前記分岐命令が、コール命令である場合であって、前記コール命令が実行された後に、前記コール命令に対応するリターン命令が実行される前に、前記リターン命令の戻り相対アドレスに位置する命令が、所定のオフセットだけ移動した場合、前記所定のオフセットに基づいて、前記リターン命令の戻り相対アドレスを修正する、戻り相対アドレス修正部、
を更に有する、付記１１ないし１３のうちいずれか１項に記載の装置。
（付記１５）
前記ルーチンの移動前のアドレスの範囲を含むルーチン移動管理エントリをメモリに記憶する、ルーチン移動管理エントリ生成部、を更に有し、
前記戻り相対アドレス修正部は、
前記ルーチン移動管理エントリに基づいて、記憶された前記ルーチンの移動前のアドレスの範囲に、修正前の前記戻り相対アドレスが入ることを判断する、戻り相対アドレス判断部を含む、
付記１４記載の装置。
【符号の説明】
【００８７】
１０１０  ＪＩＴコンパイラ
１０１２  分岐先管理エントリ生成部
１０１４  分岐命令設定部
１０５０  移動制御部
１０５２  ジャンプ先修正部
１０５４  分岐命令修正部
１０５６  ルーチン移動管理エントリ生成部
１０５８  戻り相対アドレス修正部
１０５９  戻り相対アドレス判断部
１０６０  ルーチン
【図１】
2014010661.tif 000003
【図２】
2014010661.tif 000004
【図３】
2014010661.tif 000005
【図４】
2014010661.tif 000006
【図５】
2014010661.tif 000007
【図６】
2014010661.tif 000008
【図７】
2014010661.tif 000009
【図８】
2014010661.tif 000010
【図９】
2014010661.tif 000011
【図１０】
2014010661.tif 000012
【図１１】
2014010661.tif 000013