JPH11242597A - Ｊａｖａバイトコードデータのフローグラフの生成方法 - Google Patents
Ｊａｖａバイトコードデータのフローグラフの生成方法Info
- Publication number
- JPH11242597A JPH11242597A JP10313910A JP31391098A JPH11242597A JP H11242597 A JPH11242597 A JP H11242597A JP 10313910 A JP10313910 A JP 10313910A JP 31391098 A JP31391098 A JP 31391098A JP H11242597 A JPH11242597 A JP H11242597A
- Authority
- JP
- Japan
- Prior art keywords
- bytecode
- blocks
- uninterrupted
- block
- bytecodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/43—Checking; Contextual analysis
- G06F8/433—Dependency analysis; Data or control flow analysis
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Devices For Executing Special Programs (AREA)
- Executing Machine-Instructions (AREA)
Abstract
(57)【要約】 （修正有）
【課題】ジャバ最適化器とJITコンパイラの速度と効率
を最適化するIRを形成する為ソースバイトコードからDF
Gを生成する方法を提供する。 【解決手段】バイトソースファイルからの中断されない
バイトコードブロックの前方向スキャンを中断されない
ブロック内各バイトコード開始を同定する為に実行し、
次に後方向スキャンを実行する。ブロック内各バイトコ
ードについてDFGノードを生成し、ブロック内バイトコ
ードによって使用される全ての値に対するリンクを達成
し、ファイル内の先行する又は後続するノードに対する
リンクを生成する。
を最適化するIRを形成する為ソースバイトコードからDF
Gを生成する方法を提供する。 【解決手段】バイトソースファイルからの中断されない
バイトコードブロックの前方向スキャンを中断されない
ブロック内各バイトコード開始を同定する為に実行し、
次に後方向スキャンを実行する。ブロック内各バイトコ
ードについてDFGノードを生成し、ブロック内バイトコ
ードによって使用される全ての値に対するリンクを達成
し、ファイル内の先行する又は後続するノードに対する
リンクを生成する。
Description
【０００１】
【発明の属する技術分野】本発明はジャバ（Ｊａｖａ）
クラスファイルの最適化に関する。より詳細には、本発
明はバイトコードのブロック内およびバイトコードのブ
ロック間におけるデータ値の伝搬を同定するジャバクラ
スファイル最適化器からのデータフローグラフのアスペ
クト（ａｓｐｅｃｔ）の生成に関する。
クラスファイルの最適化に関する。より詳細には、本発
明はバイトコードのブロック内およびバイトコードのブ
ロック間におけるデータ値の伝搬を同定するジャバクラ
スファイル最適化器からのデータフローグラフのアスペ
クト（ａｓｐｅｃｔ）の生成に関する。
【０００２】
【従来の技術】ソフトウエア開発者およびコンピュータ
のユーザにとって知られている１つの問題は、オペレー
ションシステムのプラットフォーム間におけるソフトウ
エアの可搬性の欠如である。この問題に向けた試みは、
ワールドワイドウェブの如き膨張するネットワークにお
いてコンピュータが相互にリンクされるにしたがって安
全性を保証する手段を含む必要がある。これらの両方に
対して対応に関して、複数層の安全性保護を含むべくデ
ザインされたプラットフォームに独立なオブジェクト指
向のコンピュータ言語として、ＪＡＶＡプログラム言語
がサンマイクロシステムズによって開発された。
のユーザにとって知られている１つの問題は、オペレー
ションシステムのプラットフォーム間におけるソフトウ
エアの可搬性の欠如である。この問題に向けた試みは、
ワールドワイドウェブの如き膨張するネットワークにお
いてコンピュータが相互にリンクされるにしたがって安
全性を保証する手段を含む必要がある。これらの両方に
対して対応に関して、複数層の安全性保護を含むべくデ
ザインされたプラットフォームに独立なオブジェクト指
向のコンピュータ言語として、ＪＡＶＡプログラム言語
がサンマイクロシステムズによって開発された。
【０００３】ジャバは、コンパイル言語と翻訳言語の両
方であることによってオペレーションシステムに対する
独立性を達成している。最初に、ジャバクラスファイル
からなるジャバソースコードがジャババイトコードと呼
ばれる汎用中間フォーマットにコンパイルされる。ジャ
ババイトコード単一バイトオプコード（ｏｐｃｏｄｅ）
のシーケンスによって構成され、各オプコードは実行さ
れるべき特定のオペレーションを同定する。更には、オ
プコードの幾つかはパラメータを有する。オプコード番
号２１ ｉｌｏａｄ＜ｖａｒｎｕｍ＞は局所変数ｖａｒ
ｎｕｍ内に格納された単一ワードの整数値を取り出して
スタック上にプッシュする。
方であることによってオペレーションシステムに対する
独立性を達成している。最初に、ジャバクラスファイル
からなるジャバソースコードがジャババイトコードと呼
ばれる汎用中間フォーマットにコンパイルされる。ジャ
ババイトコード単一バイトオプコード（ｏｐｃｏｄｅ）
のシーケンスによって構成され、各オプコードは実行さ
れるべき特定のオペレーションを同定する。更には、オ
プコードの幾つかはパラメータを有する。オプコード番
号２１ ｉｌｏａｄ＜ｖａｒｎｕｍ＞は局所変数ｖａｒ
ｎｕｍ内に格納された単一ワードの整数値を取り出して
スタック上にプッシュする。
【０００４】次に、バイトコードは、ジャババーチャル
マシーン（Ｊａｖａ Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ
ＪＶＭ）によって解釈され、バイトコードが固有の
（ｎａｔｉｖｅ）マシーンコードに翻訳される。ＪＶＭ
は物理的なマイクロプロセッサと多くの特徴を共有する
“仮想”のプロセッサのスタック化ベースの具体化であ
る。ＪＶＭによって実行されるバイトコードは本質的に
はマシーンインストラクションの集合であり、当業者に
よって認識されるであろうが、計算機のアッセンブリイ
言語に類似している。したがって、各ハードウエアプラ
ットフォームもしくはオペレーションシステムは、ジャ
バランタイムシステム（Ｊａｖａ Ｒｕｎｔｉｍｅ Ｓ
ｙｓｔｅｍ）と呼ばれる、ＪＶＭの固有の具体化手段を
有することができ、ユニバーサルなバイトコード呼出し
を下層の固有システムにルート付けする。
マシーン（Ｊａｖａ Ｖｉｒｔｕａｌ Ｍａｃｈｉｎｅ
ＪＶＭ）によって解釈され、バイトコードが固有の
（ｎａｔｉｖｅ）マシーンコードに翻訳される。ＪＶＭ
は物理的なマイクロプロセッサと多くの特徴を共有する
“仮想”のプロセッサのスタック化ベースの具体化であ
る。ＪＶＭによって実行されるバイトコードは本質的に
はマシーンインストラクションの集合であり、当業者に
よって認識されるであろうが、計算機のアッセンブリイ
言語に類似している。したがって、各ハードウエアプラ
ットフォームもしくはオペレーションシステムは、ジャ
バランタイムシステム（Ｊａｖａ Ｒｕｎｔｉｍｅ Ｓ
ｙｓｔｅｍ）と呼ばれる、ＪＶＭの固有の具体化手段を
有することができ、ユニバーサルなバイトコード呼出し
を下層の固有システムにルート付けする。
【０００５】
【発明が解決しようとする課題】ＪＡＶＡバイトコード
のインストラクションセットを開発するに当たって、設
計者は、ハードウエアの最適化にとって十分に簡単であ
ることとともに、安全性保護を与え、不適切にフォーマ
ットされたバイトコードに帰因する実行エラーやシステ
ム破壊を防ぐ検証手段が含まれているということを保証
することを要求された。ジャババイトコードは有意型
（ｓｉｇｎｉｆｉｃａｎｔ ｔｙｐｅ）の情報を含むの
で、検証手段は、バイトコードがインターネットや局所
のディスクから最初に取り出されたときに、広範囲型
（ｅｘｔｅｎｓｉｖｅ ｔｙｐｅ）のチェックを実行す
ることができる。その結果、ネイティブマシーンのイン
タープリータは、実行時に最小限の（ｍｉｎｉｍａｌ
ｔｙｐｅ）チェックを実行するのみでよい。広範囲な演
算時チェックを実行することによって保護を与えるＳｍ
ａｌｌ Ｔａｌｋの如き言語とは異なり、ジャバは演算
時チェックをより高速に実行することができる。
のインストラクションセットを開発するに当たって、設
計者は、ハードウエアの最適化にとって十分に簡単であ
ることとともに、安全性保護を与え、不適切にフォーマ
ットされたバイトコードに帰因する実行エラーやシステ
ム破壊を防ぐ検証手段が含まれているということを保証
することを要求された。ジャババイトコードは有意型
（ｓｉｇｎｉｆｉｃａｎｔ ｔｙｐｅ）の情報を含むの
で、検証手段は、バイトコードがインターネットや局所
のディスクから最初に取り出されたときに、広範囲型
（ｅｘｔｅｎｓｉｖｅ ｔｙｐｅ）のチェックを実行す
ることができる。その結果、ネイティブマシーンのイン
タープリータは、実行時に最小限の（ｍｉｎｉｍａｌ
ｔｙｐｅ）チェックを実行するのみでよい。広範囲な演
算時チェックを実行することによって保護を与えるＳｍ
ａｌｌ Ｔａｌｋの如き言語とは異なり、ジャバは演算
時チェックをより高速に実行することができる。
【０００６】ジャバは検証手段によって安全性を保証
し、バイトコードによって可搬性（ｐｏｒｔａｂｉｌｉ
ｔｙ）を与えるが、ジャバプログラムはＣ／Ｃ＋＋の如
き言語で書かれたネイティブにコンパイルされたプログ
ラムをその実行時に遅延させる。ユーザがウエブページ
（Ｗｅｂ Ｐａｇｅ）上でジャバプログラムを立上げた
場合、ユーザはプログラムがダウンロードされるのを待
つのみでなく、翻訳されるまで待たなければならない。
ジャバの実行時間を改善するためには、ジャババイトコ
ードの処理に最適化を導入することができる。この最適
化は、スタンドアローン最適化器（Ｓｔａｎｄ‐Ａｌｏ
ｎｅ Ｏｐｔｉｍｉｚｅｒ ＳＡＯ）として、或いはジ
ャストインタイム（Ｊｕｓｔ−ｉｎ−Ｔｉｍｅ ＪＩ
Ｔ）コンパイラの一部として含む様々の態様で具体化す
ることができる。
し、バイトコードによって可搬性（ｐｏｒｔａｂｉｌｉ
ｔｙ）を与えるが、ジャバプログラムはＣ／Ｃ＋＋の如
き言語で書かれたネイティブにコンパイルされたプログ
ラムをその実行時に遅延させる。ユーザがウエブページ
（Ｗｅｂ Ｐａｇｅ）上でジャバプログラムを立上げた
場合、ユーザはプログラムがダウンロードされるのを待
つのみでなく、翻訳されるまで待たなければならない。
ジャバの実行時間を改善するためには、ジャババイトコ
ードの処理に最適化を導入することができる。この最適
化は、スタンドアローン最適化器（Ｓｔａｎｄ‐Ａｌｏ
ｎｅ Ｏｐｔｉｍｉｚｅｒ ＳＡＯ）として、或いはジ
ャストインタイム（Ｊｕｓｔ−ｉｎ−Ｔｉｍｅ ＪＩ
Ｔ）コンパイラの一部として含む様々の態様で具体化す
ることができる。
【０００７】ＳＡＯはバイトコードを含む入力クラスフ
ァイルを、同じ演算をより効率的に実行するバイトコー
ドを含む出力クラスファイルに変換する。ＪＩＴはバイ
トコードを含む入力クラスファイルを実行可能なプログ
ラムに変換する。ＪＩＴの開発以前では、ＪＶＭがプロ
グラム内の全てのバイトコードインストラクションをス
テップ処理して機械的にネイティブコードコールを実行
していた。しかし、ＪＩＴコンパイラを用いる場合、Ｊ
ＶＭはまずＪＩＴに対し呼び出しをかけ、ＪＩＴはイン
ストラクションをネイティブなオペレーションシステム
上で直接に実行されるネイティブコードにコンパイルす
る。ＪＩＴコンパイラはネイティブにコンパイルされた
コードがより高速に実行されることを可能にし、コード
が一度だけコンパイルされればそれで済むことを可能に
する。更に、ＪＩＴコンパイラは、実行可能なコードが
最適化されうるステージを提供する。
ァイルを、同じ演算をより効率的に実行するバイトコー
ドを含む出力クラスファイルに変換する。ＪＩＴはバイ
トコードを含む入力クラスファイルを実行可能なプログ
ラムに変換する。ＪＩＴの開発以前では、ＪＶＭがプロ
グラム内の全てのバイトコードインストラクションをス
テップ処理して機械的にネイティブコードコールを実行
していた。しかし、ＪＩＴコンパイラを用いる場合、Ｊ
ＶＭはまずＪＩＴに対し呼び出しをかけ、ＪＩＴはイン
ストラクションをネイティブなオペレーションシステム
上で直接に実行されるネイティブコードにコンパイルす
る。ＪＩＴコンパイラはネイティブにコンパイルされた
コードがより高速に実行されることを可能にし、コード
が一度だけコンパイルされればそれで済むことを可能に
する。更に、ＪＩＴコンパイラは、実行可能なコードが
最適化されうるステージを提供する。
【０００８】バイトコードの最適化、或いはコンパイル
は、当業者には中間表現（ｉｎｔｅｒｍｅｄｉａｔｅ
ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ＩＲ）として知られて
いるソースバイトコードへの翻訳を必要とする。ＩＲ
は、プログラムの２つの基本要素、即ち、制御フローグ
ラフ（ＣＦＧ）およびデータフローグラフ（ＤＦＧ）に
関する情報を与える。次いで、ＩＲはコンパイラに関し
てはオブジェクトコードに、最適化器の場合にはソース
コードフォーマットの改善バージョンに変換される。
は、当業者には中間表現（ｉｎｔｅｒｍｅｄｉａｔｅ
ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ＩＲ）として知られて
いるソースバイトコードへの翻訳を必要とする。ＩＲ
は、プログラムの２つの基本要素、即ち、制御フローグ
ラフ（ＣＦＧ）およびデータフローグラフ（ＤＦＧ）に
関する情報を与える。次いで、ＩＲはコンパイラに関し
てはオブジェクトコードに、最適化器の場合にはソース
コードフォーマットの改善バージョンに変換される。
【０００９】ＣＦＧはコードを中断されることのないグ
ループとして常に実行されるバイトコードブロックに分
断し、ブロックを相互にリンクする関係を作り上げる。
ＤＦＧは、値が生成される所とそれらが使用される所の
間の関係をマップする。これはバイトコードブロック内
の関係とバイトコードブロック間の関係とを含む。ジャ
バプログラムは、暗黙の変数としてスタック位置を多用
するので、値の伝播のトラッキングは困難なプロセスで
ある。ＩＲのためにＤＦＧを生成するため、データフロ
ーの情報を抽出する場合、従来のアプローチは全ての可
能なフローパスを通じて、スタックと反復の両方の完全
なシミュレーションを実行することであった。
ループとして常に実行されるバイトコードブロックに分
断し、ブロックを相互にリンクする関係を作り上げる。
ＤＦＧは、値が生成される所とそれらが使用される所の
間の関係をマップする。これはバイトコードブロック内
の関係とバイトコードブロック間の関係とを含む。ジャ
バプログラムは、暗黙の変数としてスタック位置を多用
するので、値の伝播のトラッキングは困難なプロセスで
ある。ＩＲのためにＤＦＧを生成するため、データフロ
ーの情報を抽出する場合、従来のアプローチは全ての可
能なフローパスを通じて、スタックと反復の両方の完全
なシミュレーションを実行することであった。
【００１０】エンドユーザがコンパイルされたプログラ
ムと協働するのみである伝統的なコンパイラとは対照的
に、ジャバのランタイム特性は、ジャバの最適化器とＪ
ＩＴコンパイラの速度と効率を最適化するための重要な
インセンティブを創り出す。したがって、本発明の目的
は、ジャバの最適化器とＪＩＴコンパイラの速度と効率
を最適化するＩＲを形成するためソースバイトコードか
らＤＦＧを生成する方法を提供することである。本発明
のこれらおよび他の多くの目的および利点は、発明の図
面の考察および以下の記述から当業者にとって明かにな
るであろう。
ムと協働するのみである伝統的なコンパイラとは対照的
に、ジャバのランタイム特性は、ジャバの最適化器とＪ
ＩＴコンパイラの速度と効率を最適化するための重要な
インセンティブを創り出す。したがって、本発明の目的
は、ジャバの最適化器とＪＩＴコンパイラの速度と効率
を最適化するＩＲを形成するためソースバイトコードか
らＤＦＧを生成する方法を提供することである。本発明
のこれらおよび他の多くの目的および利点は、発明の図
面の考察および以下の記述から当業者にとって明かにな
るであろう。
【００１１】
【課題を解決するための手段】本発明は、ＩＲのための
ＤＦＧの生成の効率を改善することによってジャバクラ
スファイルの最適化に向けられている。本発明の第１の
態様によれば、バイトソースファイルからの中断されな
いバイトコードブロックの前方向スキャンは、中断され
ないブロック内の各バイトコードの開始を同定するため
に実行される。次に、後方向スキャンが実行される。ブ
ロック内の各バイトコードについて、ＤＦＧノードが生
成され、ブロック内のバイトコードによって使用される
全ての値に対するリンクが達成され、ファイル内の先行
する或いは後続するノードに対するリンクが生成され
る。
ＤＦＧの生成の効率を改善することによってジャバクラ
スファイルの最適化に向けられている。本発明の第１の
態様によれば、バイトソースファイルからの中断されな
いバイトコードブロックの前方向スキャンは、中断され
ないブロック内の各バイトコードの開始を同定するため
に実行される。次に、後方向スキャンが実行される。ブ
ロック内の各バイトコードについて、ＤＦＧノードが生
成され、ブロック内のバイトコードによって使用される
全ての値に対するリンクが達成され、ファイル内の先行
する或いは後続するノードに対するリンクが生成され
る。
【００１２】本発明の第２の態様によれば、バイトコー
ドブロックはファイルの実行順にリンクされるととも
に、スタック状態が各コードブロックについて生成され
る。ＣＦＧによって生成される各加入ステートメントに
ついて、ＣＦＧの１つのパスが歩進される。次に、ＤＦ
Ｇ内において、値が使用される個所と値が生成される個
所との間にリンクが達成される。最後に、値を生成する
ブロックに平行な全てのブロックについて、同じスタッ
ク状態個所を専有するバイトコードのためのリンクが複
写される。
ドブロックはファイルの実行順にリンクされるととも
に、スタック状態が各コードブロックについて生成され
る。ＣＦＧによって生成される各加入ステートメントに
ついて、ＣＦＧの１つのパスが歩進される。次に、ＤＦ
Ｇ内において、値が使用される個所と値が生成される個
所との間にリンクが達成される。最後に、値を生成する
ブロックに平行な全てのブロックについて、同じスタッ
ク状態個所を専有するバイトコードのためのリンクが複
写される。
【００１３】
【発明の実施の形態】当業者であれば、本発明の以下の
記述は図示のためだけであり、いかなる意味においても
制限的なものでないことを認識するであろう。本発明の
他の実施例は、開示の範囲内における考察から当業者に
とって容易に示唆されるであろう。
記述は図示のためだけであり、いかなる意味においても
制限的なものでないことを認識するであろう。本発明の
他の実施例は、開示の範囲内における考察から当業者に
とって容易に示唆されるであろう。
【００１４】まず、図１の（Ａ）及び（Ｂ）を参照する
と、ジャババイトコードソースファイルの最適化の簡略
化フローダイアグラム１０および２０が図示されてい
る。両方のフローダイアグラム１０と２０においても、
ジャバソースコードファイル１２はジャバコンパイラ１
４によってジャババイトコードクラスファイル１６にコ
ンパイルされる。フローダイアグラム１０では、クラス
ファイルはＳＡＯ１８において演算され、フローダイア
グラム２０では、クラスファイルはジャバランタイムシ
ステム２２を通してＪＩＴコンパイラ２４に渡される。
ジャバＳＡＯ１８は、入力クラスファイルと同じ演算を
実行するバイトコードを含むジャバクラスファイル２６
を最適化された方法においてのみ出力する。ＪＩＴ２４
はネイティブのオペレーションシステム３０上で直接に
実行される実行可能なコード２８を出力する。当業者な
らば、図１に記述された手順は単に例示的であり、クラ
スファイルが最適化されうる他の構造が存在することを
認識できるであろう。
と、ジャババイトコードソースファイルの最適化の簡略
化フローダイアグラム１０および２０が図示されてい
る。両方のフローダイアグラム１０と２０においても、
ジャバソースコードファイル１２はジャバコンパイラ１
４によってジャババイトコードクラスファイル１６にコ
ンパイルされる。フローダイアグラム１０では、クラス
ファイルはＳＡＯ１８において演算され、フローダイア
グラム２０では、クラスファイルはジャバランタイムシ
ステム２２を通してＪＩＴコンパイラ２４に渡される。
ジャバＳＡＯ１８は、入力クラスファイルと同じ演算を
実行するバイトコードを含むジャバクラスファイル２６
を最適化された方法においてのみ出力する。ＪＩＴ２４
はネイティブのオペレーションシステム３０上で直接に
実行される実行可能なコード２８を出力する。当業者な
らば、図１に記述された手順は単に例示的であり、クラ
スファイルが最適化されうる他の構造が存在することを
認識できるであろう。
【００１５】入力バイトコードソースクラスファイルの
処理において、ＳＡＯとＪＩＴの両方がＩＲを形成す
る。上記した如く、ＩＲはＣＦＧとＤＦＧへのプログラ
ムの制御およびデータフロー情報の簡単で直接的な構造
化である。ＣＦＧはプログラムの実行のためにリンクさ
れたコードブロックとしてバイトコードインストラクシ
ョンの実行のシーケンスと順序に関する情報を表す。コ
ードブロックは、中断されないグループとして常に実行
されるバイトコードの区切りであり、コードブロック間
のリンクはバイトコードブランチ、条件又はジャンプイ
ンストラクションである。
処理において、ＳＡＯとＪＩＴの両方がＩＲを形成す
る。上記した如く、ＩＲはＣＦＧとＤＦＧへのプログラ
ムの制御およびデータフロー情報の簡単で直接的な構造
化である。ＣＦＧはプログラムの実行のためにリンクさ
れたコードブロックとしてバイトコードインストラクシ
ョンの実行のシーケンスと順序に関する情報を表す。コ
ードブロックは、中断されないグループとして常に実行
されるバイトコードの区切りであり、コードブロック間
のリンクはバイトコードブランチ、条件又はジャンプイ
ンストラクションである。
【００１６】図２はバイトコードのクラスファイル４０
からのＣＦＧの生成を示すフローダイアグラムである。
ＣＦＧの生成方法は複数知られていることが認識される
べきである。開示の重複的な複雑化およびそれにより本
発明の不明確化を避けるため、これら方法のいずれかの
詳細を開示することはしない。プロシージャは１からＮ
まで順番が付けられた順序付けバイトコードインストラ
クションシーケンスを含むクラスファイル４０を用いて
開始される。１からＮの順番は、当業界において知られ
ているように、コンピュータプログラムの行の番号付け
との類推である。次に、最適化器４２はバイトコードか
ら制御フロー情報を抽出するためバイトコードクラスフ
ァイル４０を処理する。
からのＣＦＧの生成を示すフローダイアグラムである。
ＣＦＧの生成方法は複数知られていることが認識される
べきである。開示の重複的な複雑化およびそれにより本
発明の不明確化を避けるため、これら方法のいずれかの
詳細を開示することはしない。プロシージャは１からＮ
まで順番が付けられた順序付けバイトコードインストラ
クションシーケンスを含むクラスファイル４０を用いて
開始される。１からＮの順番は、当業界において知られ
ているように、コンピュータプログラムの行の番号付け
との類推である。次に、最適化器４２はバイトコードか
ら制御フロー情報を抽出するためバイトコードクラスフ
ァイル４０を処理する。
【００１７】制御フロー情報は、ＣＦＧ４４によって図
示されている。例えば、ＣＦＧ４４は、クラスファイル
４０について、バイトコードインストラクション１から
３を最初に実行し、インストラクション１００から１０
３を次に実行し、インストラクション１０から１４又は
１５から１９のいずれかを実行し、最後にインストラク
ション４から８が残りのバイトコードインストラクショ
ンの実行の前に実行されるべきことを指示する。ＣＦＧ
４４は単なる例であり、最適化器４２によってクラスフ
ァイル４０からいかなる数のＣＦＧを作ってもよいこと
が理解されるであろう。
示されている。例えば、ＣＦＧ４４は、クラスファイル
４０について、バイトコードインストラクション１から
３を最初に実行し、インストラクション１００から１０
３を次に実行し、インストラクション１０から１４又は
１５から１９のいずれかを実行し、最後にインストラク
ション４から８が残りのバイトコードインストラクショ
ンの実行の前に実行されるべきことを指示する。ＣＦＧ
４４は単なる例であり、最適化器４２によってクラスフ
ァイル４０からいかなる数のＣＦＧを作ってもよいこと
が理解されるであろう。
【００１８】上記の如く、ＣＦＧが一旦生成されると、
ＤＦＧが生成される。本発明によれば、ＤＦＧの２つの
態様がＣＦＧから生成される。１つの態様ではなく、バ
イトコードのブロック内における値の伝播が決定され
る。典型的なＪＡＶＡプログラムにおいて知られている
ように、データ値は１個所において生成され、他の個所
で使用される。本発明の第１の態様は、中断されること
のないコードブロック内において発生する生成点と消費
点の間の関係を樹立することに関係する。本発明は暗黙
の変数が容易に認識され、それらの値がＤＦＧ内におい
てそれらを用いるバイトコードに直ちにリンクされるこ
とを可能にする。
ＤＦＧが生成される。本発明によれば、ＤＦＧの２つの
態様がＣＦＧから生成される。１つの態様ではなく、バ
イトコードのブロック内における値の伝播が決定され
る。典型的なＪＡＶＡプログラムにおいて知られている
ように、データ値は１個所において生成され、他の個所
で使用される。本発明の第１の態様は、中断されること
のないコードブロック内において発生する生成点と消費
点の間の関係を樹立することに関係する。本発明は暗黙
の変数が容易に認識され、それらの値がＤＦＧ内におい
てそれらを用いるバイトコードに直ちにリンクされるこ
とを可能にする。
【００１９】先行技術とは異なり、本発明はバイトコー
ドによって使用される値を決定するためスタックを構成
する先行技術において採用されたアプローチを避ける。
例えば、図３にはＣＦＧのコードブロック内においてリ
ンクを生成するための公知の方法のブロックダイアグラ
ムが示されている。このダイアグラムはＤＦＧを生成す
るに際して、暗黙のスタック位置変数の値を決定するた
め採用された主要なステージを例示している。ステージ
６０の間、バイトコード６２の入力シーケンスの演算が
シーケンスが表すスタック６４のあるバージョンを生成
するためにシミュレートされる。６４で示されるスタッ
クはバイトコード６２の入力シーケンスの一部分６６の
みを示す。ステージ６８の間、スタック６４が実行さ
れ、ＰＯＰインストラクション７０が先行するＢＩＰＵ
ＳＨ“２”インストラクション７２によって値“２”と
関係付けられることが決定される。この情報は参照番号
７４と７６によって表されるＤＦＧノード内に格納され
る。
ドによって使用される値を決定するためスタックを構成
する先行技術において採用されたアプローチを避ける。
例えば、図３にはＣＦＧのコードブロック内においてリ
ンクを生成するための公知の方法のブロックダイアグラ
ムが示されている。このダイアグラムはＤＦＧを生成す
るに際して、暗黙のスタック位置変数の値を決定するた
め採用された主要なステージを例示している。ステージ
６０の間、バイトコード６２の入力シーケンスの演算が
シーケンスが表すスタック６４のあるバージョンを生成
するためにシミュレートされる。６４で示されるスタッ
クはバイトコード６２の入力シーケンスの一部分６６の
みを示す。ステージ６８の間、スタック６４が実行さ
れ、ＰＯＰインストラクション７０が先行するＢＩＰＵ
ＳＨ“２”インストラクション７２によって値“２”と
関係付けられることが決定される。この情報は参照番号
７４と７６によって表されるＤＦＧノード内に格納され
る。
【００２０】本発明の好ましい実施例によれば、ノード
ツリーが採用される。バイトコードクラスファイルによ
って値が生成されると、新しいノードがツリー内に生成
される。このノードは公知になるように、これを値の生
成および消費点にリンクさせることによってツリーの他
の部分に関係付けられる。この方式において、プログラ
ムを通してのデータ値の伝播は容易に追跡することがで
きる。当業者ならば、種々のデータ構造を使用しうるこ
とを認識するであろう。
ツリーが採用される。バイトコードクラスファイルによ
って値が生成されると、新しいノードがツリー内に生成
される。このノードは公知になるように、これを値の生
成および消費点にリンクさせることによってツリーの他
の部分に関係付けられる。この方式において、プログラ
ムを通してのデータ値の伝播は容易に追跡することがで
きる。当業者ならば、種々のデータ構造を使用しうるこ
とを認識するであろう。
【００２１】図４に戻って、本発明による、バイトコー
ドブロック内におけるリンクの生成方法のフローダイア
グラムが図示されている。第１ステップ１００では、バ
イトコードソースファイル１０２の前進方向スキャン
は、公知の如くバイトコードは異なる長さでありうるの
で、バイトコード１１２、１１４および１１６の開始
（スタート）１０６，１０８および１１０を夫々決定す
るために実行される。
ドブロック内におけるリンクの生成方法のフローダイア
グラムが図示されている。第１ステップ１００では、バ
イトコードソースファイル１０２の前進方向スキャン
は、公知の如くバイトコードは異なる長さでありうるの
で、バイトコード１１２、１１４および１１６の開始
（スタート）１０６，１０８および１１０を夫々決定す
るために実行される。
【００２２】次に、ステップ１１８において、バイトコ
ードソースファイル１０２の後進方向スキャンが実行さ
れる。後方向スキャンステップ１１８では、ＤＦＧのノ
ードがそれらが発生するにしたがって生成される。例え
ば、バイトコード１１６がインストラクションＰＯＰで
あれば、ＰＯＰが読取られるとノード１２０がＰＯＰイ
ンストラクション１２２を含むＤＦＧ内に生成される。
次に、インストラクションＢＩＰＵＳＨ“２”がバイト
コード１０８で読取られると、１２４において、値
“２”がそれを使用するＰＯＰインストラクション１２
２にリンクされる。
ードソースファイル１０２の後進方向スキャンが実行さ
れる。後方向スキャンステップ１１８では、ＤＦＧのノ
ードがそれらが発生するにしたがって生成される。例え
ば、バイトコード１１６がインストラクションＰＯＰで
あれば、ＰＯＰが読取られるとノード１２０がＰＯＰイ
ンストラクション１２２を含むＤＦＧ内に生成される。
次に、インストラクションＢＩＰＵＳＨ“２”がバイト
コード１０８で読取られると、１２４において、値
“２”がそれを使用するＰＯＰインストラクション１２
２にリンクされる。
【００２３】本発明は、スタックのコピーの構築全体の
プロセスがなくなるので、ＤＦＧの生成における効率の
大幅な増加を与える。本発明は、バイトコードのストリ
ームはスタックマシーンに対するインストラクションで
あるので、バイトコードインストラクションによって消
費されるオペランドあるいは値がインストラクションに
先行することを認識している。バイトコードファイルが
逆順に読まれるときに、ＤＦＧ内のノードを生成するス
テップはバイトコードが読まれた後、直ちに実行され
る。
プロセスがなくなるので、ＤＦＧの生成における効率の
大幅な増加を与える。本発明は、バイトコードのストリ
ームはスタックマシーンに対するインストラクションで
あるので、バイトコードインストラクションによって消
費されるオペランドあるいは値がインストラクションに
先行することを認識している。バイトコードファイルが
逆順に読まれるときに、ＤＦＧ内のノードを生成するス
テップはバイトコードが読まれた後、直ちに実行され
る。
【００２４】全体をカバーする意図ではないが、更なる
例が本発明によるバイトコードインストラクションから
生成されるＤＦＧ内のノードについて、図５（Ａ）と
（Ｂ）に図示されている。図５（Ａ）と（Ｂ）は、夫々
２つのリンクを持った単一インストラクションおよび多
数のリンクを持ったインストラクションのシリーズの例
である。
例が本発明によるバイトコードインストラクションから
生成されるＤＦＧ内のノードについて、図５（Ａ）と
（Ｂ）に図示されている。図５（Ａ）と（Ｂ）は、夫々
２つのリンクを持った単一インストラクションおよび多
数のリンクを持ったインストラクションのシリーズの例
である。
【００２５】図５（Ａ）において、バイトコードソース
ブロック１５０は、まず、前進方向スキャンによってバ
イトコード１５２、１５４および１５８に分けられる。
後進方向のスキャンステップが実行される時に、整数加
算（ＩＡＤＤ）インストラクションがバイトコード１５
８から読取られるとともに、ノード１６０がＤＦＧ内に
生成される。インストラクションＩＡＤＤの定義からノ
ード１６０は２つの値を消費することが知られている。
後進方向スキャンが継続すると、これら２つの値がバイ
トコード１５４と１５２から読取られ、ＤＦＧのノード
ツリー内のノード１６２と１６４として生成され、ノー
ド１６０にリンクされる。
ブロック１５０は、まず、前進方向スキャンによってバ
イトコード１５２、１５４および１５８に分けられる。
後進方向のスキャンステップが実行される時に、整数加
算（ＩＡＤＤ）インストラクションがバイトコード１５
８から読取られるとともに、ノード１６０がＤＦＧ内に
生成される。インストラクションＩＡＤＤの定義からノ
ード１６０は２つの値を消費することが知られている。
後進方向スキャンが継続すると、これら２つの値がバイ
トコード１５４と１５２から読取られ、ＤＦＧのノード
ツリー内のノード１６２と１６４として生成され、ノー
ド１６０にリンクされる。
【００２６】図５（Ｂ）において、バイトコードソース
ブロック１６６は前進方向スキャンによってバイトコー
ド１６８、１７０および１７２にまず区分される。バイ
トコード１６６のシーケンスはステートメント（Ｘ＋
Ｘ）を実施する。後進方向スキャンステップでは、最初
に出会ったバイトコード１７２はＩＡＤＤインストラク
ションである。図５（Ａ）の例に関して説明したよう
に、ＩＡＤＤインストラクションはＤＦＧ内において２
つの値とのリンクを持ったノード１７４を生成する。次
のバイトコード１７０は複写（ＤＵＰ）インストラクシ
ョンであるので、ノード１７４からの両方のリンクはＤ
ＵＰインストラクションのためノード１７６に対して作
られる。次に、整数ロードＸ（ＩＬＯＡＤＸ）インスト
ラクションを有するバイトコード１６８が読まれ、ノー
ド１７６に対するリンクを持ったノード１７８が生成さ
れる。ノードツリーにおけるこのシーケンスにおいて、
ノード１７８の値はノード１７６に複写され、両方の値
はノード１７４において消費される。上に掲げた例から
当業者には明かなように、後進方向スキャンステップを
実行する際、生成された特定のＤＦＧはＣＦＧによって
生成されたブロック内のバイトコードのシーケンスに依
存する。
ブロック１６６は前進方向スキャンによってバイトコー
ド１６８、１７０および１７２にまず区分される。バイ
トコード１６６のシーケンスはステートメント（Ｘ＋
Ｘ）を実施する。後進方向スキャンステップでは、最初
に出会ったバイトコード１７２はＩＡＤＤインストラク
ションである。図５（Ａ）の例に関して説明したよう
に、ＩＡＤＤインストラクションはＤＦＧ内において２
つの値とのリンクを持ったノード１７４を生成する。次
のバイトコード１７０は複写（ＤＵＰ）インストラクシ
ョンであるので、ノード１７４からの両方のリンクはＤ
ＵＰインストラクションのためノード１７６に対して作
られる。次に、整数ロードＸ（ＩＬＯＡＤＸ）インスト
ラクションを有するバイトコード１６８が読まれ、ノー
ド１７６に対するリンクを持ったノード１７８が生成さ
れる。ノードツリーにおけるこのシーケンスにおいて、
ノード１７８の値はノード１７６に複写され、両方の値
はノード１７４において消費される。上に掲げた例から
当業者には明かなように、後進方向スキャンステップを
実行する際、生成された特定のＤＦＧはＣＦＧによって
生成されたブロック内のバイトコードのシーケンスに依
存する。
【００２７】本発明の第２の態様によれば、ＣＦＧ内の
バイトコードブロック間の値の伝播が決定される。図６
はリンクされたコード２００、２０２、２０４および２
０６の複数のブロックを持ったＣＦＧ１８０を示してい
る。ＣＦＧ１８０ではジョイン（ｊｏｉｎ）２０８に先
行するブロック２０２と２０６は平行であると考えられ
る。ジョインは複数の平行なブロックを接続することで
あると考えられるべきである。ＣＦＧが生成されると、
スタック状態２１０、２１２、２１４および２１６がバ
イトコード２００、２０２、２０４および２０６の各ブ
ロックについて夫々生成される。スタック状態は当該ス
タックに関係するブロック内のバイトコードが実行され
た後に、スタック上に依然存在する全ての値を含む。ス
タック上の値はバイトコードブロック内のインストラク
ションによって生成されるということを認識すべきであ
る。このことは、インストラクション２１８と２２０の
スタック状態２２２と２２４への夫々のマッピングによ
って図示されている。以下の記述の図示の目的で、イン
ストラクション２１８はＰＵＳＨ“１”であり、インス
トラクション２２０はＰＵＳＨ“０”であり、インスト
ラクション２２６はＰＯＰである。
バイトコードブロック間の値の伝播が決定される。図６
はリンクされたコード２００、２０２、２０４および２
０６の複数のブロックを持ったＣＦＧ１８０を示してい
る。ＣＦＧ１８０ではジョイン（ｊｏｉｎ）２０８に先
行するブロック２０２と２０６は平行であると考えられ
る。ジョインは複数の平行なブロックを接続することで
あると考えられるべきである。ＣＦＧが生成されると、
スタック状態２１０、２１２、２１４および２１６がバ
イトコード２００、２０２、２０４および２０６の各ブ
ロックについて夫々生成される。スタック状態は当該ス
タックに関係するブロック内のバイトコードが実行され
た後に、スタック上に依然存在する全ての値を含む。ス
タック上の値はバイトコードブロック内のインストラク
ションによって生成されるということを認識すべきであ
る。このことは、インストラクション２１８と２２０の
スタック状態２２２と２２４への夫々のマッピングによ
って図示されている。以下の記述の図示の目的で、イン
ストラクション２１８はＰＵＳＨ“１”であり、インス
トラクション２２０はＰＵＳＨ“０”であり、インスト
ラクション２２６はＰＯＰである。
【００２８】バイトコードの始めのブロック内に生成さ
れた値がバイトコードのブロック間においてＤＦＧ内の
リンクを生成するためにバイトコードの相続くブロック
によって使用される又は消費される時点を決定するた
め、先のスタック状態値の消費を注目するとともに、そ
のソースを同定しながら、ブロックの実行がなされる。
この情報はバイトコードの消費と生成のノード間のリン
クとしてＤＦＧ内に表示される。全ての平行なブロック
のためのリンクを樹立するため、従来の方法はＣＦＧ内
における全ての可能な制御フロー経路を通しての繰返し
（ｉｔｅｒａｔｉｎｇ）に依存していた。例えば、ＣＦ
Ｇ１８０内のブロック間のリンクについてＤＦＧを生成
するため、第１経路はブロック２００、２０２および２
０４を含む経路を通して作られ、次いで、第２経路がブ
ロック２００、２０６および２０４を含む経路を通して
作られる。
れた値がバイトコードのブロック間においてＤＦＧ内の
リンクを生成するためにバイトコードの相続くブロック
によって使用される又は消費される時点を決定するた
め、先のスタック状態値の消費を注目するとともに、そ
のソースを同定しながら、ブロックの実行がなされる。
この情報はバイトコードの消費と生成のノード間のリン
クとしてＤＦＧ内に表示される。全ての平行なブロック
のためのリンクを樹立するため、従来の方法はＣＦＧ内
における全ての可能な制御フロー経路を通しての繰返し
（ｉｔｅｒａｔｉｎｇ）に依存していた。例えば、ＣＦ
Ｇ１８０内のブロック間のリンクについてＤＦＧを生成
するため、第１経路はブロック２００、２０２および２
０４を含む経路を通して作られ、次いで、第２経路がブ
ロック２００、２０６および２０４を含む経路を通して
作られる。
【００２９】本発明によれば、バイトコードの平行ブロ
ック間のリンクについてＤＦＧを形成するために全ての
制御フロー経路を検証する必要はない。ブロック２０
０、２０２、２０４および２０６間のＤＦＧ内のリンク
は、ブロック２００、２０２、２０４を通して歩進し、
その後、ブロック２０６に対するリンクを樹立するため
に、ブロック２００，２０２、２０４を通した経路から
の情報を適用することによって生成される。本発明は、
ジャバの標準要求および上記した検証は適切にフォーマ
ットされたコードではジョインに先行するブロックのい
ずれのスタック状態も同一であることを保障するという
事実を活用している。
ック間のリンクについてＤＦＧを形成するために全ての
制御フロー経路を検証する必要はない。ブロック２０
０、２０２、２０４および２０６間のＤＦＧ内のリンク
は、ブロック２００、２０２、２０４を通して歩進し、
その後、ブロック２０６に対するリンクを樹立するため
に、ブロック２００，２０２、２０４を通した経路から
の情報を適用することによって生成される。本発明は、
ジャバの標準要求および上記した検証は適切にフォーマ
ットされたコードではジョインに先行するブロックのい
ずれのスタック状態も同一であることを保障するという
事実を活用している。
【００３０】例えば、ＣＦＧ１８０において、ジョイン
２０８に先行するスタック状態２１２と２１６の両方は
サイズおよび相対形式の両方において同一でなければな
らない。実行時、ブロック２０２内のある値の消費はブ
ロック２０６内のある値の消費と平行に行なわれる。そ
の結果、例えば、スタック状態位置２２２に対応する値
がコードブロック２０４の２２６におけるバイトコード
インストラクションによって使用されるならば、バイト
コードインストラクション２２６はスタック状態位置２
２４に対応する値をも使用する。
２０８に先行するスタック状態２１２と２１６の両方は
サイズおよび相対形式の両方において同一でなければな
らない。実行時、ブロック２０２内のある値の消費はブ
ロック２０６内のある値の消費と平行に行なわれる。そ
の結果、例えば、スタック状態位置２２２に対応する値
がコードブロック２０４の２２６におけるバイトコード
インストラクションによって使用されるならば、バイト
コードインストラクション２２６はスタック状態位置２
２４に対応する値をも使用する。
【００３１】シュードコード（ｐｓｅｕｄｏｃｏｄｅ）
の以下の行は点を示している。もし（ＩＦ）（何らかの
条件が発生したら） Ｘ＝１； その他（ＥＬＳＥ） Ｘ＝０； ： ： Ａ＝Ｘ＋２
の以下の行は点を示している。もし（ＩＦ）（何らかの
条件が発生したら） Ｘ＝１； その他（ＥＬＳＥ） Ｘ＝０； ： ： Ａ＝Ｘ＋２
【００３２】式“Ａ＝Ｘ＋２”における“Ａ”に対する
値の付与には、“ＩＦ（何らかの条件が発生すれば）”
ステートメントによって決められるような暗黙のスタッ
ク変数“Ｘ”として割当てられた値を“Ｘ＝１”又は
“Ｘ＝０”のいずれかによって用いる。
値の付与には、“ＩＦ（何らかの条件が発生すれば）”
ステートメントによって決められるような暗黙のスタッ
ク変数“Ｘ”として割当てられた値を“Ｘ＝１”又は
“Ｘ＝０”のいずれかによって用いる。
【００３３】図７（Ａ）において、本発明の第２の態様
にしたがってＤＦＧを生成するために採用されたステッ
プを概観するブロックダイアグラムが図示されている。
ステップ２５０において、ＣＦＧグラフの第１のブラン
チがスキャンされる。図６のＣＦＧ１８０に適用する
と、ブロック２００、２０２および２０４を通る第１経
路が実行される。
にしたがってＤＦＧを生成するために採用されたステッ
プを概観するブロックダイアグラムが図示されている。
ステップ２５０において、ＣＦＧグラフの第１のブラン
チがスキャンされる。図６のＣＦＧ１８０に適用する
と、ブロック２００、２０２および２０４を通る第１経
路が実行される。
【００３４】次に、ステップ２５２において、値が生成
される個所と値が消費される個所との間のリンクが形成
される。図７（Ｂ）に図示されているように、リンク２
５４がＣＦＧ１８０内の位置２１８におけるＰＵＳＨ
“１”インストラクションとＣＦＧ１８０内の位置２２
６においてこれを消費するＰＯＰインストラクションと
の間に形成される。
される個所と値が消費される個所との間のリンクが形成
される。図７（Ｂ）に図示されているように、リンク２
５４がＣＦＧ１８０内の位置２１８におけるＰＵＳＨ
“１”インストラクションとＣＦＧ１８０内の位置２２
６においてこれを消費するＰＯＰインストラクションと
の間に形成される。
【００３５】次に、ステップ２５６において、ＰＵＳＨ
０インストラクションのためのデータはＣＦＧ１８０内
の位置２１８のＰＵＳＨ１インストラクションと同じス
タック状態位置を占有することが知られているので、リ
ンク２５８が位置２２０におけるＰＵＳＨ０インストラ
クションとこれを消費する位置２２６におけるＰＯＰイ
ンストラクションとの間に形成される。このようにし
て、本発明の第２の態様によれば、従来では行なわれて
いたＣＦＧ内の全ての経路を検証することを要すること
なく、バイトコードブロック間のＤＦＧにおけるリンク
はより効率的に形成される。ジョインはバイトコードソ
ースコード全体を通じて極めて共通であるので、本発明
は効率における大幅な増加を実現する。多重ジョインが
存在する場合には、効率の増加はより大きい。
０インストラクションのためのデータはＣＦＧ１８０内
の位置２１８のＰＵＳＨ１インストラクションと同じス
タック状態位置を占有することが知られているので、リ
ンク２５８が位置２２０におけるＰＵＳＨ０インストラ
クションとこれを消費する位置２２６におけるＰＯＰイ
ンストラクションとの間に形成される。このようにし
て、本発明の第２の態様によれば、従来では行なわれて
いたＣＦＧ内の全ての経路を検証することを要すること
なく、バイトコードブロック間のＤＦＧにおけるリンク
はより効率的に形成される。ジョインはバイトコードソ
ースコード全体を通じて極めて共通であるので、本発明
は効率における大幅な増加を実現する。多重ジョインが
存在する場合には、効率の増加はより大きい。
【００３６】この発明の例示的な実施例と応用が図示さ
れ、記述されたが、上に述べたものよりもより多くの修
正がここに設定した発明思想から逸脱することなしに可
能であることが当業者にとって明らかであろう。本発明
は、それ故、添付の特許請求の範囲の技術的思想の範囲
内における外、制限されるべきではない。
れ、記述されたが、上に述べたものよりもより多くの修
正がここに設定した発明思想から逸脱することなしに可
能であることが当業者にとって明らかであろう。本発明
は、それ故、添付の特許請求の範囲の技術的思想の範囲
内における外、制限されるべきではない。
【図１】 （Ａ）は、本発明によるスタンドアローン最
適化器を用いたＪＡＶＡバイトコードソースファイルの
最適化のフローダイアグラムであり、（Ｂ）は本発明に
よるジャストインコンパイラを用いたＪＡＶＡバイトコ
ードソースファイルの最適化のフローダイアグラムであ
る。
適化器を用いたＪＡＶＡバイトコードソースファイルの
最適化のフローダイアグラムであり、（Ｂ）は本発明に
よるジャストインコンパイラを用いたＪＡＶＡバイトコ
ードソースファイルの最適化のフローダイアグラムであ
る。
【図２】 本発明において使用するのに好適なバイトコ
ードソースファイルからの制御フローグラフの生成を図
示するフローダイアグラムである。
ードソースファイルからの制御フローグラフの生成を図
示するフローダイアグラムである。
【図３】 先行技術によるデータフローグラフの生成の
フローダイアグラムである。
フローダイアグラムである。
【図４】 本発明によるバイトコードブロック内のリン
クのためのデータフローグラフの生成の第１の態様のフ
ローダイアグラムである。
クのためのデータフローグラフの生成の第１の態様のフ
ローダイアグラムである。
【図５】 （Ａ）は本発明の第１の態様によるインスト
ラクションＩＡＤＤのためのデータフローグラフ内のノ
ードの生成についてのブロックダイアグラムであり、
（Ｂ）は本発明の第１の態様による複数のインストラク
ションについてデータフローグラフ内の複数のノードの
生成についてのブロックダイアグラムである。
ラクションＩＡＤＤのためのデータフローグラフ内のノ
ードの生成についてのブロックダイアグラムであり、
（Ｂ）は本発明の第１の態様による複数のインストラク
ションについてデータフローグラフ内の複数のノードの
生成についてのブロックダイアグラムである。
【図６】 本発明によるバイトコードブロック間のリン
クのためのデータフローグラフの生成の第２の態様を図
示するのに好適な制御フローグラフのフローダイアグラ
ムである。
クのためのデータフローグラフの生成の第２の態様を図
示するのに好適な制御フローグラフのフローダイアグラ
ムである。
【図７】 （Ａ）は本発明の第２の態様にしたがった方
法におけるステップのブロックダイアグラムであり、
（Ｂ）は本発明の第２の態様によるデータフローグラフ
におけるノードの生成のためのブロックダイアグラムで
ある。
法におけるステップのブロックダイアグラムであり、
（Ｂ）は本発明の第２の態様によるデータフローグラフ
におけるノードの生成のためのブロックダイアグラムで
ある。
Claims (2)
- 【請求項１】 データフローグラフの形成において、中
断されることのないバイトコードブロックのバイトコー
ドをリンクさせる方法は以下のステップからなる：上記
バイトコードの各々の開始を同定するため、中断される
ことのないバイトコードブロックを前進方向にスキャン
する；上記中断されることのないバイトコードブロック
内において、上記バイトコードの各々をバイトコード単
位で後進方向にスキャンする；および上記バイトコード
の各々によって使用される上記バイトコードの他の全て
に対して、上記バイトコードの各々をリンクさせる、上
記データフローグラフ内のリンクを生成する。 - 【請求項２】 データフローグラフの形成において、中
断されることのないバイトコードブロック間でバイトコ
ードをリンクさせる方法であって、上記中断されること
のないバイトコードブロックは、上記中断されることの
ないブロックの実行順にしたがったリンクを有し、スタ
ック状態は上記中断されることのないバイトコードブロ
ックの各々について生成される方法は、以下のステップ
からなる：上記中断されることのないブロックの一つに
おいて、ある値を生成する各バイトコードと上記中断さ
れることのないブロックの第１経路上のいま一つにおい
て上記値を消費する各バイトコード間に上記データフロ
ーグラフにおけるリンクを生成するため、上記実行順の
複数の経路のうち、ジョインで終端する第１の経路を通
して歩進する；およびある値を生成する各バイトコード
のための上記第１の経路以外の他の全ての経路におい
て、上記第１の経路内における上記中断されることのな
いブロックの１つにある値を生成する各バイトコードと
同様のスタック位置を有する各バイトコードのためのリ
ンクを用いて、上記第１の経路内の各リンクを複写す
る。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/940212 | 1997-09-30 | ||
| US08/940,212 US6233733B1 (en) | 1997-09-30 | 1997-09-30 | Method for generating a Java bytecode data flow graph |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11242597A true JPH11242597A (ja) | 1999-09-07 |
Family
ID=25474426
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10313910A Pending JPH11242597A (ja) | 1997-09-30 | 1998-09-29 | Ｊａｖａバイトコードデータのフローグラフの生成方法 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US6233733B1 (ja) |
| EP (1) | EP0905617B1 (ja) |
| JP (1) | JPH11242597A (ja) |
| CA (1) | CA2249042A1 (ja) |
| DE (1) | DE69833617D1 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9250880B2 (en) | 2013-11-25 | 2016-02-02 | International Business Machines Corporation | Method for obtaining execution frequency information on execution paths in control flow graph, and computer and computer program for obtaining the information |
Families Citing this family (32)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| BR9713267A (pt) | 1996-10-25 | 2004-06-15 | Schlumberger Systems & Service | Cartão de circuito integrado para uso com um terminal, processo para uso com o mesmo, microcontrolador e processo para sua programação |
| US6792600B1 (en) * | 1998-05-14 | 2004-09-14 | International Business Machines Corporation | Method and apparatus for just in time compilation of instructions |
| US6324688B1 (en) * | 1998-07-30 | 2001-11-27 | International Business Machines Corporation | Method and apparatus for optimizing execution of Java programs |
| US6412109B1 (en) * | 1999-01-29 | 2002-06-25 | Sun Microsystems, Inc. | Method for optimizing java bytecodes in the presence of try-catch blocks |
| US6421821B1 (en) * | 1999-03-10 | 2002-07-16 | Ronald J. Lavallee | Flow chart-based programming method and system for object-oriented languages |
| US6412108B1 (en) * | 1999-05-06 | 2002-06-25 | International Business Machines Corporation | Method and apparatus for speeding up java methods prior to a first execution |
| US6560774B1 (en) * | 1999-09-01 | 2003-05-06 | Microsoft Corporation | Verifier to check intermediate language |
| GB9920676D0 (en) * | 1999-09-01 | 1999-11-03 | Tao Group Ltd | Translating and executing object-oriented computer programs |
| US8121955B2 (en) * | 2003-01-16 | 2012-02-21 | Oracle America, Inc. | Signing program data payload sequence in program loading |
| US20040143739A1 (en) * | 2003-01-16 | 2004-07-22 | Sun Mircosystems, Inc., A Delaware Corporation | Run time code integrity checks |
| US7222331B2 (en) * | 2003-01-16 | 2007-05-22 | Sun Microsystems, Inc. | Linking of virtual methods |
| US7484095B2 (en) * | 2003-01-16 | 2009-01-27 | Sun Microsystems, Inc. | System for communicating program data between a first device and a second device |
| US7165246B2 (en) * | 2003-01-16 | 2007-01-16 | Sun Microsystems, Inc. | Optimized representation of data type information in program verification |
| US7272830B2 (en) * | 2003-01-16 | 2007-09-18 | Sun Microsystems, Inc. | Ordering program data for loading on a device |
| US7281244B2 (en) * | 2003-01-16 | 2007-10-09 | Sun Microsystems, Inc. | Using a digital fingerprint to commit loaded data in a device |
| KR100643268B1 (ko) * | 2004-01-17 | 2006-11-10 | 삼성전자주식회사 | 자바 가상 머신의 성능을 향상시키는 방법 및 상기 방법에의해 동작되는 시스템 |
| US7721275B2 (en) * | 2004-05-14 | 2010-05-18 | Sap Ag | Data-flow based post pass optimization in dynamic compilers |
| US20050272001A1 (en) * | 2004-06-03 | 2005-12-08 | Blain Christopher C | Oral care device |
| EP1622009A1 (en) * | 2004-07-27 | 2006-02-01 | Texas Instruments Incorporated | JSM architecture and systems |
| US7788655B2 (en) * | 2004-08-30 | 2010-08-31 | Oracle America, Inc. | Mechanism for ordering lists of local variables associated with a plurality of code blocks |
| US8108826B2 (en) * | 2004-09-29 | 2012-01-31 | Avaya Inc. | Code-coverage guided prioritized test generation |
| MY135555A (en) * | 2004-12-14 | 2008-05-30 | Axiomatic Solutions Sdn Bhd | Compile time linking via hashing technique |
| KR100763177B1 (ko) * | 2005-04-21 | 2007-10-04 | 삼성전자주식회사 | 자바 가상 머신의 명령어 수행 방법 및 그 장치 |
| US8444416B2 (en) * | 2005-04-26 | 2013-05-21 | Braun Gmbh | Valves for personal care devices |
| US20070017582A1 (en) * | 2005-07-20 | 2007-01-25 | Chenvainu Alexander T | Fluid couplings |
| US8046202B1 (en) * | 2006-07-17 | 2011-10-25 | The Mathworks, Inc. | Generation of intermediate representations based on user specified elements in a graphical model that enable simulation, propagation and code generation |
| US8191052B2 (en) * | 2006-12-01 | 2012-05-29 | Murex S.A.S. | Producer graph oriented programming and execution |
| US8307337B2 (en) | 2006-12-01 | 2012-11-06 | Murex S.A.S. | Parallelization and instrumentation in a producer graph oriented programming framework |
| US8332827B2 (en) | 2006-12-01 | 2012-12-11 | Murex S.A.S. | Produce graph oriented programming framework with scenario support |
| DE102007028184A1 (de) | 2007-06-20 | 2008-12-24 | Braun Gmbh | Bürstenkopf für eine Zahnbürste |
| US9152437B2 (en) * | 2010-10-28 | 2015-10-06 | Hewlett-Packard Development Company, L.P. | Dynamically installing image processing |
| US11321218B1 (en) * | 2021-03-08 | 2022-05-03 | Correct Computation, Inc. | Automated generation of source code models from machine code for code analysis |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1990001738A1 (en) * | 1988-07-29 | 1990-02-22 | Hunter Systems Software, Inc. | Machine process for translating programs in binary machine language into another binary machine language |
| US5428786A (en) * | 1991-03-07 | 1995-06-27 | Digital Equipment Corporation | Branch resolution via backward symbolic execution |
| US5666296A (en) * | 1991-12-31 | 1997-09-09 | Texas Instruments Incorporated | Method and means for translating a data-dependent program to a data flow graph with conditional expression |
-
1997
- 1997-09-30 US US08/940,212 patent/US6233733B1/en not_active Expired - Lifetime
-
1998
- 1998-09-29 CA CA002249042A patent/CA2249042A1/en not_active Abandoned
- 1998-09-29 DE DE69833617T patent/DE69833617D1/de not_active Expired - Lifetime
- 1998-09-29 JP JP10313910A patent/JPH11242597A/ja active Pending
- 1998-09-29 EP EP98307926A patent/EP0905617B1/en not_active Expired - Lifetime
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9250880B2 (en) | 2013-11-25 | 2016-02-02 | International Business Machines Corporation | Method for obtaining execution frequency information on execution paths in control flow graph, and computer and computer program for obtaining the information |
Also Published As
| Publication number | Publication date |
|---|---|
| US6233733B1 (en) | 2001-05-15 |
| EP0905617A2 (en) | 1999-03-31 |
| DE69833617D1 (de) | 2006-04-27 |
| CA2249042A1 (en) | 1999-03-30 |
| EP0905617A3 (en) | 2002-08-14 |
| EP0905617B1 (en) | 2006-03-01 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH11242597A (ja) | Ｊａｖａバイトコードデータのフローグラフの生成方法 | |
| US6412109B1 (en) | Method for optimizing java bytecodes in the presence of try-catch blocks | |
| CN100385399C (zh) | 用于多个异常处理模型的中间表示的方法和系统 | |
| EP1258805B1 (en) | Placing exception throwing instruction in compiled code | |
| US6247172B1 (en) | Method for a translation system that aggressively optimizes and preserves full synchronous exception state | |
| US6973644B2 (en) | Program interpreter | |
| US7062755B2 (en) | Recovering from compilation errors in a dynamic compilation environment | |
| EP2315118B1 (en) | Method and apparatus for enabling parallel processing during execution of a cobol source program using two-stage compilation | |
| US9495720B2 (en) | Method and apparatus for compiling and executing an application using virtualization in a heterogeneous system | |
| US20020100028A1 (en) | System for modifying the functionality of compiled computer code at run-time | |
| JP2011530768A (ja) | ソフトウェア・アプリケーションの性能向上 | |
| JP2013533533A (ja) | コンピューティング・プラットフォーム内のワークロードの分配及び並列化 | |
| US20060101432A1 (en) | Assembly language code compilation for an instruction-set architecture containing new instructions using the prior assembler | |
| CN100481007C (zh) | 无需额外的代码分析来进行链接时代码优化的方法和系统 | |
| US20160246622A1 (en) | Method and system for implementing invocation stubs for the application programming interfaces embedding with function overload resolution for dynamic computer programming languages | |
| US20070277166A1 (en) | Method and apparatus for performing versioning for loop, method and apparatus for collecting array range check information in basic blocks, method for modifying array range check information, method for optimizing array range checks, method for generating codes for array range checks, method and apparatus for eliminating redundant array range checks, method for selecting array range checks, method for modifying array range checks, method for collecting array range checks, and method for determining handling of array range checks | |
| JP2003513353A (ja) | Ｊａｖａ（登録商標）プログラムのプラットフォームに特定的な効率性を高めるための方法及びソフトウエア製品 | |
| Cifuentes et al. | Experience in the design, implementation and use of a retargetable static binary translation framework | |
| CN112882701A (zh) | 一种支持多架构的可执行文件静态插桩技术框架 | |
| EP4196874B1 (en) | Representing asynchronous state machine in intermediate code | |
| JP3551352B2 (ja) | ループ分割方法 | |
| US20080127072A1 (en) | Method and system for extending evaluation for intermediate representation interpretation | |
| Leroy | Compiling functional languages | |
| JP3018783B2 (ja) | コンパイル方式 | |
| JPS58169637A (ja) | コンパイル処理方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20050906 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20080924 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090310 |