(57)【要約】【課題】より効率的な最適化処理を行うことが可能なプログラム最適化処理装置を提供する。【解決手段】命令ｎの演算に基づく変数のライブ情報をビット単位で設定するライブ情報設定手段と、命令ｎの演算に基づく変数の定数伝播情報をビット単位で設定して、命令ｎの演算前後の定数伝播情報に基づいて命令ｎの演算効果を示す演算効果情報をビット単位で設定する定数伝播情報設定手段と、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の定数伝播情報が真か偽である場合、命令ｎを変数へ定数を代入する命令に置き換える第１最適化手段と、第１最適化手段で命令ｎの最適化処理が行われない場合、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の演算効果情報に演算効果がない場合、命令ｎを削除する第２最適化手段とを備える。【選択図】図２
2010160561.tif 000002
【特許請求の範囲】
【請求項１】
命令ｎの演算に基づく変数のライブ情報をビット単位で設定するライブ情報設定手段と、
前記命令ｎの演算に基づく変数の定数伝播情報をビット単位で設定して、前記命令ｎの演算前後の前記定数伝播情報に基づいて前記命令ｎの演算効果を示す演算効果情報をビット単位で設定する定数伝播情報設定手段と、
前記命令ｎの演算後の前記ライブ情報がライブである全てのビットにおいて、前記命令ｎの演算後の前記定数伝播情報が真か偽である場合、前記命令ｎを変数へ定数を代入する命令に置き換える第１最適化手段と、
前記第１最適化手段で前記命令ｎの最適化処理が行われない場合、前記命令ｎの演算後の前記ライブ情報がライブである全てのビットにおいて、前記命令ｎの演算後の前記演算効果情報に前記演算効果がない場合、前記命令ｎを削除する第２最適化手段と
を備えるプログラム最適化処理装置。
【請求項２】
請求項１に記載のプログラム最適化処理装置であって、
前記定数伝播情報設定手段は、前記命令ｎの演算前後で前記定数伝播情報の値が変化するビット、および値が不明となるビットを演算効果有りと設定し、前記命令ｎの演算前後で前記定数伝播情報の値が変化しないビットを演算効果無しに設定する
プログラム最適化処理装置。
【請求項３】
コンピュータが、命令ｎの演算に基づく変数のライブ情報をビット単位で設定するステップと、
前記コンピュータが、前記命令ｎの演算に基づく変数の定数伝播情報をビット単位で設定するステップと、
前記コンピュータが、前記命令ｎの演算前後の前記定数伝播情報に基づいて前記命令ｎの演算効果を示す演算効果情報をビット単位で設定するステップと、
前記コンピュータが、前記命令ｎの演算後の前記ライブ情報がライブである全てのビットにおいて、前記命令ｎの演算後の前記定数伝播情報が真か偽である場合、前記命令ｎを変数へ定数を代入する命令に置き換えるステップと、
前記コンピュータが、前記第１最適化手段で前記命令ｎの最適化処理が行われない場合、前記命令ｎの演算後の前記ライブ情報がライブである全てのビットにおいて、前記命令ｎの演算後の前記演算効果情報に前記演算効果がない場合、前記命令ｎを削除するステップと
を備えるプログラム最適化処理方法。
【請求項４】
請求項３に記載のプログラム最適化処理方法であって、前記演算効果情報をビット単位で設定するステップは、
前記コンピュータが、前記命令ｎの演算前後で前記定数伝播情報の値が変化するビット、および値が不明となるビットを演算効果有りと設定し、前記命令ｎの演算前後で前記定数伝播情報の値が変化しないビットを演算効果無しに設定するステップ
を含むプログラム最適化処理方法。
【請求項５】
請求項３または請求項４に記載のプログラム最適化処理方法をコンピュータへ実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラムの最適化処理を行うプログラム最適化処理装置に関する。
【背景技術】
【０００２】
ソースプログラムからオブジェクトプログラムへのコンパイルに際して、プログラムの冗長性を排除するための最適化処理が行われている。プログラムの最適化処理の手法として、定数伝播情報による最適化処理や、デッドコードによる最適化処理がある。
【０００３】
定数伝播情報を用いた最適化処理は、以下のような処理を行うことでプログラムの最適化を行う。
ａ）命令ｎの式で参照する変数を、置き換えることが可能であれば、定数へ置き換える。
ｂ）命令ｎの演算により定義される変数とその演算結果を記録する。
ｃ）命令ｎの演算結果が定数になる場合、命令ｎを、変数に定数を代入する命令へ変更する。
定数伝播情報を用いた最適化処理では、上述のａ）からｃ）を繰り返すことによって最適化を行う。たとえば、以下のような命令のリストを考える。
ａ＝１＋２  ・・・（１）
ｂ＝ａ＋３  ・・・（２）
上述のリストでは、式（１）は「ａ＝３」となり、ａを式（２）へ代入することで、「ｂ＝６」との命令に最適化することができる。定数伝播情報を用いた最適化処理をビット単位の定数伝播情報で行う場合は、ビット単位で定数を設定する。例えば、以下のような式のリストを考える。
ｃ＝ｃ｜０ｘＦ０Ｆ０  ・・・（３）
ｃ＝ｃ＆０ｘＦ０Ｆ０  ・・・（４）
なお、定数伝播情報の初期値を「０ｘＵＵＵＵ（Ｕ：Ｕｎｋｎｏｗ）」とする。上述のリストでは、式（３）により「ｃ＝０ｘＦＵＦＵ」であり、式（４）により「ｃ＝０ｘＦ０Ｆ０」となる。「ｃ＝０ｘＦ０Ｆ０」は、不明値がないため、式（３）と式（４）は、「ｃ＝０ｘＦ０Ｆ０」との命令へ最適化することができる。
【０００４】
一方、デッドコードによる最適化は、以下のような処理を行うことでプログラムの最適化を行う。デッドコードによる最適化は、プログラムの基本ブロックを実行する順番とは逆の順番にライブ情報を設定しながら行われる。ライブ情報は、ライブ（プログラム処理において、当該変数が、命令ｎより後で参照されることを意味する。）と、デッド（プログラムの実行処理において、当該変数は、命令ｎより後で参照されないことを意味する。）と、を含んでいる。各命令の変数に対して設定されたライブ情報を用いて最適化処理が行われる。
ｉ）命令ｎの演算により定義される変数が、デッドと記述されているなら、命令ｎを削除する。
ｉｉ）命令ｎの演算により定義される変数をデッドと記述し、命令ｎで参照される変数をライブと記述する。
デッドコードによる最適化は、上記ｉ）、ｉｉ）を繰り返すことによって、最適化を行う。例えば、以下のような命令のリストを考える。
ａ＝０ｘ１００  ・・・（５）
ａ＝ｂ＋３      ・・・（６）
上述のリストでは、式（５）でａを定義しているが、式（６）でもａを定義しているため、式（５）を削除することができる。特許文献１は、ビット単位に拡張したデッドコードによる最適化について開示している。
【０００５】
特許文献１は、オブジェクトプログラムの実行時間を高速にすることができ、しかもそのオブジェクトプログラムのサイズを小さくできるプログラム最適化処理装置を開示している。特許文献１のプログラム最適化処理装置は、命令ｎが定義する変数のライブ情報をビット単位で設定するライブ情報設定手段と、ライブ情報設定手段で設定されたライブ情報のうち命令ｎが定義する変数の部分がデッドに設定されている場合に命令ｎを削除する第１最適化手段と、第１最適化手段で命令ｎが削除されなかった場合に、ライブ情報設定手段で設定されたライブ情報のうち命令ｎが定義する部分をデッドに設定するデッド設定手段と、デッド設定手段でデッドに設定されたライブ情報に基づき命令ｎが参照する部分を計算する参照部計算手段と、参照部計算手段での計算により得られた参照部に基づき命令ｎを変更する第２最適化手段と、第２最適化手段で使用されたライブ情報のうち参照部をライブに設定するライブ設定手段とを備える。特許文献１のプログラム最適化処理装置によれば、ソースプログラムを構成する命令の動作に基づいてビット単位でライブ情報を得られる。そのため、ソースプログラム中の命令の削除や変更をきめ細かく制御できるので、オブジェクトプログラムの実行時間の高速化、およびオブジェクトプログラムのサイズの減少化を図ることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−２２９０３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、特許文献１の最適化処理装置は、注目する命令の演算効果が、その後の命令によってデッド設定された変数部分にのみ効果がある場合に、当該注目する命令を削除する。このような処理では、実際に注目する命令を実行した場合に演算効果の及ぶ変数までは考慮していないため、本来、削除できるはずの命令を削除することができないという課題が有った。そのため、より効率的な最適化処理が求められている。
【課題を解決するための手段】
【０００８】
以下に、（発明を実施するための最良の形態）で使用される番号を用いて、課題を解決するための手段を説明する。これらの番号は、（特許請求の範囲）の記載と（発明を実施するための最良の形態）との対応関係を明らかにするために付加されたものである。ただし、それらの番号を、（特許請求の範囲）に記載されている発明の技術的範囲の解釈に用いてはならない。
【０００９】
本発明のプログラム最適化処理装置は、命令ｎの演算に基づく変数のライブ情報をビット単位で設定するライブ情報設定手段（２０３、ステップＳ４０１）と、命令ｎの演算に基づく変数の定数伝播情報をビット単位で設定して、命令ｎの演算前後の定数伝播情報に基づいて命令ｎの演算効果を示す演算効果情報をビット単位で設定する定数伝播情報設定手段（２０３、ステップＳ４０３）と、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の定数伝播情報が真か偽である場合、命令ｎを変数へ定数を代入する命令に置き換える第１最適化手段（２０３、ステップＳ４０４）と、第１最適化手段で命令ｎの最適化処理が行われない場合、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の演算効果情報に演算効果がない場合、命令ｎを削除する第２最適化手段（２０３、ステップＳ４０６）とを備える。
【００１０】
プログラム最適化処理方法は、コンピュータが、命令ｎの演算に基づく変数のライブ情報をビット単位で設定するステップ（Ｓ４０１）と、コンピュータが、命令ｎの演算に基づく変数の定数伝播情報をビット単位で設定するステップ（Ｓ４０３）と、コンピュータが、命令ｎの演算前後の定数伝播情報に基づいて命令ｎの演算効果を示す演算効果情報をビット単位で設定するステップ（Ｓ４０３）と、コンピュータが、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の定数伝播情報が真か偽である場合、命令ｎを変数へ定数を代入する命令に置き換えるステップ（Ｓ４０４）と、コンピュータが、第１最適化手段で命令ｎの最適化処理が行われない場合、命令ｎの演算後のライブ情報がライブである全てのビットにおいて、命令ｎの演算後の演算効果情報に演算効果がない場合、命令ｎを削除するステップ（Ｓ４０６）とを備える。
【００１１】
本発明のプログラムは、上述のプログラム最適化処理方法をコンピュータへ実行させる。
【発明の効果】
【００１２】
本発明によれば、ビット単位の定数伝播情報と、ビット単位のライブ情報とを考慮して最適化処理を行うことが可能となるため、より効率的に最適化処理を行うことが可能なプログラム最適化処理装置を提供できる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態のプログラム最適化処理装置の構成を示す機能ブロック図である。
【図２】本実施形態における最適化部２０３の最適化処理動作フローである。
【図３】本実施形態における命令ｎの実行前後の定数伝播情報と、演算効果情報との対応表である。
【図４】本実施形態における最適化部２０３による最適化処理の実施例を示す図である。
【図５】本実施形態において命令１０２に対する処理に注目した図である。
【発明を実施するための形態】
【００１４】
添付図面を参照して、本発明の実施形態によるプログラム最適化処理装置を以下に説明する。
【００１５】
［構成の説明］
はじめに、本実施形態におけるプログラム最適化処理装置の構成の説明を行う。図１は、本実施形態のプログラム最適化処理装置の構成を示す機能ブロック図である。本実施形態のプログラム最適化処理装置は、ソースプログラムファイル１０と、コンパイラ２０と、オブジェクトプログラムファイル３０とを備える。
【００１６】
ソースプログラムファイル１０は、ソースプログラムを記録している。ソースプログラムは、例えば、Ｃ言語等の高級言語記述されている。オブジェクトプログラムファイル３０は、オブジェクトプログラムを記録している。オブジェクトプログラムは、機械語で記述されている。コンパイラ２０は、ソースプログラムを読み込んで、ソースプログラムからオブジェクトプログラムを生成する。
【００１７】
コンパイラ２０は、字句解析部２０１と、構文解析部２０２と、最適化部２０３と、コード生成部２０４とを備える。字句解析部２０１は、ソースプログラムファイル１０からソースプログラムを読み込み、ソースプログラムの字句解析を行ってシンボルテーブルを作成する。構文解析部２０２は、シンボルテーブルに基づいてソースプログラムの構文解析を行って中間言語を生成する。最適化部２０３は、中間言語に対して最適化処理を実行する。コード生成部２０４は、最適化処理後の中間言語に基づいてオブジェクトプログラムを作成して、オブジェクトプログラムをオブジェクトプログラムファイル３０へ格納する。本発明は、最適化部２０３に特徴を有するため、最適化部２０３の最適化処理を中心に説明を行い、字句解析部２０１、構文解析部２０２、及びコード生成部２０４の詳細な説明を省略する。
【００１８】
ここで、プログラム最適化処理装置は、図示されない記憶部、処理部、入出力部を備えるコンピュータで構成される。記憶部は、ソースプログラムファイル１０や、オブジェクトプログラムファイル３０を記憶し、また、コンパイラ２０を含むプログラム最適化処理装置の機能を実現するための処理用プログラム等を記憶する、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）や、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）や、ハードディスク等で構成される。処理部は、処理用プログラムを記憶部から読み込んで実行することで、コンパイラの機能を実現するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）で構成される。入出力部は、プログラム最適化処理装置の使用者との入出力インターフェイスであるキーボード、マウス、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等や、あるいは外部装置、外部記憶媒体との入出力インターフェイスである通信ポートや、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）ドライブ等で構成される。なお、プログラム最適化処理装置を実現する処理用プログラムは、ＣＤ等の記憶媒体に格納することが可能である。この場合、記憶媒体を用いて他のコンピュータへ処理用プログラムを導入すること、また、記憶媒体から処理用プログラムを起動することが可能である。
【００１９】
［動作方法の説明］
次に、本実施形態におけるプログラム最適化処理装置の動作方法の説明を行う。まず、図２を用いて、最適化部２０３による最適化処理の動作方法の説明を行う。図２は、本実施形態における最適化部２０３による最適化処理動作フローである。
【００２０】
（ステップＳ４０１）
最適化部２０３は、命令の基本ブロックを入力する。最適化部２０３は、基本ブロックの最後の命令から順に最初の命令まで、全ての命令に対するビット単位のライブ情報を設定する。最適化部２０３は、注目する命令ｎで定義される変数とその定義部分を、命令ｎより前では、「デッド（参照されない）」か、「ライブ（参照される）」かに設定する。最適化部２０３によるライブ情報の設定については、例を用いて後述するが、詳細については、特許文献１を参照されたい。
【００２１】
（ステップＳ４０２）
最適化部２０３は、基本ブロックの先頭の命令を、注目すべき命令ｎとして設定する。
【００２２】
（ステップＳ４０３）
最適化部２０３は、命令ｎが定義する変数の定数伝播情報を設定する。また、最適化部２０３は、命令ｎによる演算の効果を示す演算効果情報を設定する。最適化部２０３は、定数演算情報を、「不明（Ｕ：Ｕｎｋｎｏｗ）」、「真（１）」、「偽（０）」のいずれかに設定する。なお、最適化部２０３は、レジスタＲの変数が初期値を持つ場合、変数の初期値を定数伝播情報に設定する。最適化部２０３は、レジスタＲの変数が初期値を持たない場合、変数の初期値を「不明：Ｕ」に設定する。最適化部２０３は、注目している命令ｎが基本ブロックの先頭の命令である場合、当該基本ブロックの前段の基本ブロックにおいて、定数伝播情報の最終状態を元に初期値を設定する。最適化部２０３は、前段の基本ブロックの最終の定数伝播情報が、すべて「真」であれば初期値を「真」と設定し、すべて「偽」であれば初期値を「偽」と設定し、「不明」が含まれる場合や、あるいは「真」と「偽」が混在する場合は、共に初期値を「不明」と設定する。また、最適化部２０３は、演算効果情報を、命令ｎの演算前後の定数伝播情報に基づいて設定する。最適化部２０３は、命令ｎの演算前後の定数伝播情報において、レジスタＲの変数に変化がある場合に演算効果があると設定する。図３は、本実施形態における命令ｎの実行前後の定数伝播情報と、演算効果情報との対応表である。本実施形態の最適化部２０３は、図３の対応表に基づいて演算効果情報を設定する。例えば、命令ｎにより定数伝播情報に変化が無い場合、最適化部２０３は、演算効果情報を演算効果無しと設定する。つまり、命令ｎによる定数伝播情報に変化が無い場合、演算前の定数伝播情報「真」、「偽」、「不明」は、演算後の定数伝播情報も、それぞれ「真」、「偽」、「不明」であり、最適化部２０３は、演算効果情報を演算効果無しに設定する。次に、命令ｎにより定数伝播情報が、必ず「真」となる場合を考える。最適化部２０３は、演算前の定数伝播情報「偽」と「不明」について、演算後に「真」となり、定数伝播情報に変化があるため演算効果情報を演算効果有りと設定する。しかし、最適化部２０３は、演算前の定数伝播情報「真」について、演算後の定数伝播情報も「真」であり定数伝播情報に変化が無いため、演算効果情報を演算効果無しと設定する。同様に、命令ｎにより定数伝播情報が、必ず「偽」となる場合を考える。最適化部２０３は、演算前の定数伝播情報「真」と「不明」について、演算後に「偽」となり定数伝播情報に変化があるため演算効果情報を有りと設定する。しかし、最適化部２０３は、演算前の定数伝播情報「偽」について、演算後も「偽」であり定数伝播情報に変化が無いため、演算効果情報を演算効果無しに設定する。次に、命令ｎによる定数伝播情報の設定に不定な変更がある場合を考える。最適化部２０３は、演算前の定数伝播情報「真」、「偽」、「不明」のいずれについても、演算後の定数伝播情報が「不明」となるため、演算効果情報を演算効果有りと設定する。これは、演算後の定数伝播情報が不定のため、演算前後で定数伝播情報に変化があるか否かを確定できないためである。最適化部２０３は、以上のように、命令ｎによる演算前後の定数伝播情報に基づいて、演算効果情報を設定する。
【００２３】
（ステップＳ４０４）
最適化部２０３は、最適化処理Ａを行う。最適化部２０３は、命令ｎによるライブ情報と、定数伝播情報とに基づいて、最適化処理Ａを行う。最適化部２０３は、ライブ情報がライブであるビットにおいて、全ての定数伝播情報が「真」もしくは「偽」であるかを判定する。最適化部２０３は、命令ｎによるライブ情報がライブである全てのビットにおいて定数伝播情報が「真」もしくは「偽」である場合、命令ｎを、変数へ定数を代入する命令に置き換える最適化処理Ａを行う。一方、最適化部２０３は、命令ｎによるライブ情報がライブである全てのビットにおいて定数伝播情報が「真」もしくは「偽」でない場合、最適化処理Ａを行わない。
【００２４】
（ステップＳ４０５）
最適化処理Ａを行った場合、ステップＳ４０７へ進む。一方、最適化処理Ａを行っていない場合、ステップＳ４０６へ進む。
【００２５】
（ステップＳ４０６）
最適化部２０３は、最適化処理Ｂを行う。最適化部２０３は、命令ｎによるライブ情報と、演算の効果情報に基づいて最適化処理Ｂを行う。最適化部２０３は、ライブ情報がライブである全てのビットにおいて、演算効果の有無を判定する。最適化部２０３は、命令ｎによるライブ情報がライブである全てのビットにおいて、演算効果が無い場合、命令ｎを削除する最適化処理Ｂを行う。一方、最適化部２０３は、命令ｎによるライブ情報がライブである全てのビットにおいて、少なくともいずれかのビットに演算効果がある場合、最適化処理Ｂを行わない。
【００２６】
（ステップＳ４０７）
最適化部２０３は、現在、注目している命令ｎが、基本ブロックにおける最後の命令であるか否かを判定する。現在、注目している命令ｎが基本ブロックにおける最後の命令である場合、当該基本ブロックに対する最適化処理は、終了となる。一方、現在、注目している命令ｎが基本ブロックにおける最後の命令で無い場合、ステップＳ４０８へ進む。
【００２７】
（ステップＳ４０８）
最適化部２０３は、現在、注目している命令ｎの次の命令を、注目する命令ｎとして設定する。その後、ステップＳ４０３へ戻る。
【００２８】
以上が、本実施形態における最適化部２０３による最適化処理の動作方法の説明である。
【００２９】
次に、具体的な実施例を用いて、図２に示した本実施形態における最適化部２０３による最適化処理動作の説明を行う。図４は、本実施形態における最適化部２０３による最適化処理の実施例を示す図である。
【００３０】
図４に示すように、最適化部２０３は、基本ブロックを入力する。本説明における基本ブロックは、命令１０１から命令１０４により構成されている。なお、以下の説明において、レジスタＲは、１６ビットであり、一桁４ビットで表される合計４桁として示されている。また、レジスタＲの変数における初期の定数伝播情報は、定数伝播情報１１１に示すように、全て不明（Ｕ：Ｕｎｋｎｏｗ）とする。さらに、最適化部２０３は、この基本ブロック以降の処理においてレジスタＲの利用があるとして、レジスタＲの変数における初期のライブ情報を、ライブ情報１２５に示すように、全てライブとする。
【００３１】
命令１０１は、「Ｒ←Ｒ＆０ｘＦ００Ｆ」というシンボルで表される。命令１０１は、変数Ｒと即値０ｘＦ００Ｆとの論理積演算を行って新たなＲを生成する命令である。なお、第２オペランドの文字列の先頭に記載された「０ｘ」は、続く文字列が１６進数であることを示している。命令１０２は、「Ｒ←Ｒ＋０ｘＦ」というシンボルで表される。命令１０２は、変数Ｒにおける即値０ｘＦを加算して新たなＲを生成する命令である。命令１０３は、「Ｒ←Ｒ｜０ｘＦ」というシンボルで表される。命令１０３は、変数Ｒと即値０ｘＦとの論理和演算を行って新たなＲを生成する命令である。命令１０４は、「Ｒ←Ｒ＞＞８」というシンボルで表される。命令１０４は、変数Ｒの変数を８ビット右シフトして新たなＲを生成する命令である。
【００３２】
以下、図２の動作フローを、図４の例に適用しつつ説明を行っていく。
【００３３】
まず、最適化部２０３は、基本ブロックのライブ情報を設定する（ステップＳ４０１）。最適化部２０３は、基本ブロックの最後の命令から順に、ライブ情報の設定を行う。前述の通り、命令１０４以降でレジスタＲの使用があるものとし、レジスタＲの変数における初期のライブ情報は全てライブであり、ライブ情報１２５と設定されている。なお、レジスタＲの「Ｌ」の表示は、対応する各桁のライブ情報がライブであることを示し、「Ｄ」の表示は、対応する各桁のライブ情報がデッドであることを示している。まず、命令１０４は、変数Ｒを８ビット右シフトして新たなＲを生成する。命令１０４の実行により下位２桁は無効となるので、下位２桁のライブ情報はデッドとなる。そのため、最適化部２０３は、ライブ情報をライブ情報１２４へ設定する。次に、命令１０３は、変数Ｒと即値０ｘＦとの論理和演算を行って新たなＲを生成する。命令１０３は、１桁目にのみ演算効果を与える。しかし、ライブ情報１２４では下位２桁がデッドであるため、命令１０３を、削除することができる。この場合、ライブ情報１２４は、そのまま伝播され、ライブ情報１２３となる。次に、命令１０２は、変数Ｒに即値０ｘＦを加算して新たなＲを生成する。命令１０２は、即値０ｘＦの加算による繰り上がりを考慮すると、全ての桁に演算効果が及ぶ。そのため、変数Ｒは、全ての桁がライブとなり、ライブ情報１２２となる。次に、命令１０１は、変数Ｒと即値０ｘＦ００Ｆとの論理積演算を行って新たなＲを生成する。命令１０１は、０ｘＦ００Ｆとの論理積であるため、２桁目、３桁目がデッドとなる。ライブ情報１２２は、２桁目、３桁目がデッドとなり、ライブ情報１２１となる。最適化部２０３は、以上のようにライブ情報の設定を行う。最適化部２０３は、基本ブロックへのライブ情報の設定により、命令１０３を削除することができる。
【００３４】
次に、最適化部２０３は、基本ブロックの先頭の命令である命令１０１を処理対象に設定する（ステップＳ４０２）。
【００３５】
最適化部２０３は、命令１０１における変数の定数伝播情報と、演算効果情報とを設定する（ステップＳ４０３）。なお、定数伝播情報の初期値は、全ての桁で不明「Ｕ」とし、最適化部２０３は、定数伝播情報を、定数伝播情報１１１と設定している。命令１０１は、変数Ｒと即値０ｘＦ００Ｆとの論理積演算を行って新たな変数Ｒを生成する演算であり、２桁目、３桁目が「０」となる。最適化部２０３は、命令１０１により定数伝播情報を、定数伝播情報１１２と設定する。また、最適化部２０３は、演算効果情報を、値の変化がある２桁目、３桁目に演算効果有りと設定する。
【００３６】
最適化部２０３は、命令１０１に対する最適化Ａを行う（ステップＳ４０４）。最適化部２０３は、定数伝播情報１１２と、ライブ情報１２２とに基づいて、最適化Ａを行う。最適化部２０３は、ライブ情報１２２においてライブである全てのビットについて、定数伝播情報１１２が「真」または「偽」であるかを判定する。すなわち、ライブ情報１２２においてライブである１桁目から４桁目までの全てのビットが、定数伝播情報１１２において、「１」か「０」で有るかを判定する。定数伝播情報１１２は、１桁目と４桁目が「Ｕ」である。そのため、最適化部２０３は、ライブ情報１２２においてライブである全てのビットについて、定数伝播情報１１２が「真」または「偽」ではないと判定する。よって、最適化部２０３は、命令１０１の最適化Ａを行わない。
【００３７】
最適化部２０３は、命令１０１に対する最適化Ａを行わなかったため、最適化Ｂへ進む（ステップＳ４０５）。
【００３８】
最適化部２０３は、命令１０１に対する最適化Ｂを行う（ステップＳ４０６）。最適化部２０３は、演算効果情報とライブ情報１２２とに基づいて、最適化Ｂを行う。最適化部２０３は、ライブ情報１２２においてライブである全てのビットについて、演算効果が無いかを判定する。すなわち、ライブ情報１２２においてライブである１桁目から４桁目までの全てのビットが、演算効果情報において演算効果が無いかを判定する。演算効果情報は、２桁目、３桁目に演算効果がある。そのため、最適化部２０３は、ライブ情報１２２においてライブである全てのビットについて、演算効果が無いのではないと判定する。よって、最適化部２０３は、命令１０１を最適化Ｂは行わない。
【００３９】
最適化部２０３は、命令１０１が基本ブロックの最後の命令であるか否かを判定する（ステップＳ４０７）。
【００４０】
命令１０１は、基本ブロックの最後の命令ではない。そのため、最適化部２０３は、命令１０１の次の命令である命令１０２を処理対象に設定する（ステップＳ４０８）。
【００４１】
最適化部２０３は、命令１０２における変数の定数伝播情報と、演算効果情報とを設定する（ステップＳ４０３）。命令１０２は、変数Ｒへ即値０ｘＦを加算して新たな変数Ｒを生成する演算であり、加算後の桁繰り上がりを考慮すると、下位２桁が「Ｕ」となる。最適化部２０３は、命令１０２により定数伝播情報を、定数伝播情報１１３と設定する。また、最適化部２０３は、演算効果情報を、下位２桁に演算効果有りを設定する。
【００４２】
最適化部２０３は、命令１０２に対する最適化Ａを行う（ステップＳ４０４）。最適化部２０３は、定数伝播情報１１３と、ライブ情報１２３とに基づいて、最適化Ａを行う。最適化部２０３は、ライブ情報１２３においてライブである全てのビットについて、定数伝播情報１１３が「真」または「偽」であるかを判定する。すなわち、ライブ情報１２３においてライブである１桁目と２桁目の全てのビットが、定数伝播情報１１３において、「１」か「０」で有るかを判定する。定数伝播情報１１３は、１桁目が「Ｕ」である。そのため、最適化部２０３は、ライブ情報１２３においてライブである全てのビットについて、定数伝播情報１１３が「真」または「偽」ではないと判定する。よって、最適化部２０３は、命令１０１の最適化Ａを行わない。
【００４３】
最適化部２０３は、命令１０２に対する最適化Ａを行わなかったため、最適化Ｂへ進む（ステップＳ４０５）。
【００４４】
最適化部２０３は、命令１０２に対する最適化Ｂを行う（ステップＳ４０６）。最適化部２０３は、演算効果情報とライブ情報１２３とに基づいて、最適化Ｂを行う。最適化部２０３は、ライブ情報１２３においてライブである全てのビットについて、演算効果が無いかを判定する。すなわち、ライブ情報１２３においてライブである１桁目と２桁目の全てのビットが、演算効果情報において演算効果が無いかを判定する。演算効果情報は、下位２桁に演算効果があり、３桁目、４桁目には演算効果が無い。そのため、最適化部２０３は、ライブ情報１２３においてライブである全てのビットについて、演算効果が無いと判定する。よって、最適化部２０３は、命令１０２を削除することができる。
【００４５】
最適化部２０３は、命令１０２が基本ブロックの最後の命令であるか否かを判定する（ステップＳ４０７）。
【００４６】
命令１０２は、基本ブロックの最後の命令ではない。そのため、最適化部２０３は、命令１０２の次の命令である命令１０４を処理対象に設定する（ステップＳ４０８）。なお、命令１０３は、前述の通り、基本ブロックへのライブ情報の設定時に削除されている。
【００４７】
最適化部２０３は、命令１０４における変数の定数伝播情報と、演算効果情報とを設定する（ステップＳ４０３）。命令１０４は、変数Ｒを８ビット右シフトして新たなＲを生成する演算であり、上位８ビットは「Ｕ」となる。最適化部２０３は、命令１０４により定数伝播情報を、定数伝播情報１１５と設定する。また、最適化部２０３は、演算効果情報を、１桁目から４桁目までの全ての桁に演算効果有りを設定する。
【００４８】
最適化部２０３は、命令１０４に対する最適化Ａを行う（ステップＳ４０４）。最適化部２０３は、定数伝播情報１１５と、ライブ情報１２５とに基づいて、最適化Ａを行う。最適化部２０３は、ライブ情報１２５においてライブである全てのビットについて、定数伝播情報１１５が「真」または「偽」であるかを判定する。すなわち、ライブ情報１２５においてライブである１桁目から４桁目までの全ての桁における全てのビットが、定数伝播情報１１５において、「１」か「０」で有るかを判定する。定数伝播情報１１３は、上位３桁が「Ｕ」である。そのため、最適化部２０３は、ライブ情報１２５においてライブである全てのビットについて、定数伝播情報１１５が「真」または「偽」ではないと判定する。よって、最適化部２０３は、命令１０４の最適化Ａを行わない。
【００４９】
最適化部２０３は、命令１０４に対する最適化Ａを行わなかったため、最適化Ｂへ進む（ステップＳ４０５）。
【００５０】
最適化部２０３は、命令１０４に対する最適化Ｂを行う（ステップＳ４０６）。最適化部２０３は、演算効果情報とライブ情報１２５に基づいて、最適化Ｂを行う。最適化部２０３は、ライブ情報１２５においてライブである全てのビットについて、演算効果が無いかを判定する。すなわち、ライブ情報１２５においてライブである１桁目から４桁目まで全ての桁における全てのビットが、演算効果情報において演算効果が無いかを判定する。演算効果情報は、１桁目から４桁目まで全ての桁において演算効果がある。そのため、最適化部２０３は、ライブ情報１２５においてライブである全てのビットについて、演算効果が無いわけではないと判定する。よって、最適化部２０３は、最適化Ｂを行わない。
【００５１】
最適化部２０３は、命令１０５が基本ブロックの最後の命令であるか否かを判定する（ステップＳ４０７）。命令１０５は、基本ブロックの最後の命令であるので、当該基本ブロックに対する最適化処理を完了する。
【００５２】
ここで、図５は、本実施形態において命令１０２に対する処理に注目した図である。前述した通り、命令１０２によるライブ情報の設定において、最適化部２０３は、命令１０２の演算効果が全桁にあるとしてライブ情報１２２とするため、命令１０２の削除を行うことができない。しかし、命令１０２による定数伝播情報の設定において、最適化部２０３は、演算効果が下位２桁に有ると演算効果情報を設定する。そのため、最適化部２０３は、演算効果情報とライブ情報１２３を用いることで、命令１０２による演算効果のある下位２桁は、デッドであることを検知することができる。そのため、最適化部２０３は、命令１０２を削除する最適化Ｂを行うことができる。
【００５３】
このように、本実施形態のプログラム最適化処理装置は、命令ｎによる定数伝播情報と、定数伝播情報に基づく演算効果情報、及びライブ情報を用いることにより、より効率的なプログラム最適化処理を行うことができる。
【００５４】
以上、実施形態を参照して本発明を説明したが、本発明は上記の実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００５５】
１０  ソースプログラムファイル
２０  コンパイラ
３０  オブジェクトプログラムファイル
１０１  命令
１０２  命令
１０３  命令
１０４  命令
１１１  定数伝播情報
１１２  定数伝播情報
１１３  定数伝播情報
１１４  定数伝播情報
１１５  定数伝播情報
１２１  ライブ情報
１２２  ライブ情報
１２３  ライブ情報
１２４  ライブ情報
１２５  ライブ情報
２０１  字句解析部
２０２  構文解析部
２０３  最適化部
２０４  コード生成部
【図１】
2010160561.tif 000003
【図２】
2010160561.tif 000004
【図３】
2010160561.tif 000005
【図４】
2010160561.tif 000006
【図５】
2010160561.tif 000007