(57)【特許請求の範囲】
【請求項１】
コンピュータを制御して実行プログラムを変換する変換プログラムであって、
前記コンピュータに、
前記実行プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該実行プログラム中で定義されている値に関して、当該値のデータサイズを補正するための符号拡張命令を当該実行プログラムに付加してメモリに格納する処理と、
前記メモリに格納された前記符号拡張命令が付加された前記実行プログラムに対して前方データフロー解析を行って、前記符号拡張命令の各々に関して、当該符号拡張命令の入力値が入力以前に符号拡張されているか否かを調べ、当該入力値が入力以前に符号拡張されているような冗長な符号拡張命令を除去する処理と
を実行させることを特徴とする変換プログラム。
【請求項２】
前記実行プログラムの構造に基づいて前記符号拡張命令の各々の実行頻度を予め定めた規則に基づいて、実行頻度が高いと判断される当該符号拡張命令から順に除去の実行順を決定する処理を、前記コンピュータに実行させ、
前記符号拡張命令を除去する処理では、決定された前記符号拡張命令の実行順にしたがって、前記冗長な符号拡張命令を除去することを特徴とする請求項１に記載の変換プログラム。
【請求項３】
コンピュータを制御して実行プログラムを変換する変換プログラムであって、
前記実行プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該実行プログラム中で定義されている値に関して、当該値のデータサイズを補正するための符号拡張命令を当該実行プログラムに付加してメモリに格納する機能と、
前記メモリに格納された前記符号拡張命令が付加された前記実行プログラムに対して後方データフロー解析を行って、前記符号拡張命令の各々に関して、当該符号拡張命令の出力結果が使用される全ての場所において、符号拡張前のデータサイズ以下で使用されているか否かを調べ、当該出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されているような冗長な符号拡張命令を除去する機能と
を前記コンピュータに実現させることを特徴とする変換プログラム。
【請求項４】
前記実行プログラムの構造に基づいて前記符号拡張命令の各々の実行頻度を予め定めた規則に基づいて、実行頻度が高いと判断される当該符号拡張命令から順に除去の実行順を決定する機能を、前記コンピュータに実現させ、
前記符号拡張命令を除去する機能では、決定された前記符号拡張命令の実行順にしたがって、前記冗長な符号拡張命令を除去することを特徴とする請求項３に記載の変換プログラム。
【請求項５】
前記符号拡張命令を除去する機能では、前記実行プログラム中の配列アクセスの各々に関して下記のいずれかの場合に該当するか否かを調べ、該当する場合に、当該配列アクセスの配列インデックスに付加された前記符号拡張命令を除去することを特徴とする請求項３に記載の変換プログラム。
１．配列インデックスａに関して、当該配列インデックスａの上位３２ビットが０であり、かつ前記実行プログラムを記述した言語の仕様により、当該配列インデックスａの下位３２ビットについて、
０≦配列インデックスａの下位３２ビット≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
２．配列インデックス（ａ＋ｂ）に関して、配列インデックスａ、ｂは両方とも既に符号拡張されており、かつ配列インデックスａまたは配列インデックスｂのどちらかの値が０〜０ｘ７ｆｆｆｆｆｆｆの範囲内にあり、かつ前記実行プログラムを記述した言語の仕様により、当該配列インデックス（ａ＋ｂ）の下位３２ビットについて、
０≦配列インデックス（ａ＋ｂ）の下位３２ビット≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
３．配列インデックス（ａ＋ｂ）に関して、配列の大きさの上限がmaxlen（０≦maxlen≦０ｘ７ｆｆｆｆｆｆｆ）で与えられ、かつ配列インデックスａ、ｂは両方とも既に符号拡張されており、かつ配列インデックスａまたは配列インデックスｂのどちらかの値が（−１）−０ｘ７ｆｆｆｆｆｆｆ〜０ｘ７ｆｆｆｆｆｆｆの範囲内にあり、かつ前記実行プログラムを記述した言語の仕様により、当該配列インデックス（ａ＋ｂ）の下位３２ビットについて、
０≦配列インデックス（ａ＋ｂ）の下位３２ビット＜maxlen≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
【請求項６】
プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラにおいて、
前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納する補正命令生成部と、
前記メモリに格納された前記補正命令が付加された前記プログラムに対して前方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の入力値が入力以前に符号拡張されているか否かを調べ、当該入力値が入力以前に符号拡張されているような冗長な補正命令を除去する命令除去処理部と
を備えることを特徴とするコンパイラ。
【請求項７】
前記プログラムの構造に基づいて前記補正命令の各々の実行頻度を予め定めた規則に基づいて、実行頻度が高いと判断される当該補正命令から順に除去の実行順を決定する除去順決定部をさらに備え、
前記補正命令生成部は、前記除去順決定部により決定された前記補正命令の実行順にしたがって、前記冗長な補正命令を除去することを特徴とする請求項６に記載のコンパイラ。
【請求項８】
プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラにおいて、
前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納する補正命令生成部と、
前記メモリに格納された前記補正命令が付加された前記プログラムに対して後方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の出力結果が使用される全ての場所において、符号拡張前のデータサイズ以下で使用されているか否かを調べ、当該出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されているような冗長な補正命令を除去する命令除去処理部と
を備えることを特徴とするコンパイラ。
【請求項９】
前記プログラムの構造に基づいて前記補正命令の各々の実行頻度を予め定めた規則に基づいて、実行頻度が高いと判断される当該補正命令から順に除去の実行順を決定する除去順決定部をさらに備え、
前記補正命令生成部は、前記除去順決定部により決定された前記補正命令の実行順にしたがって、前記冗長な補正命令を除去することを特徴とする請求項８に記載のコンパイラ。
【請求項１０】
前記命令除去処理部は、前記プログラム中の配列アクセスの各々に関して下記のいずれかの場合に該当するか否かを調べ、該当する場合に、当該配列アクセスの配列インデックスに付加された前記補正命令を除去することを特徴とする請求項８に記載のコンパイラ。
１．配列インデックスａに関して、当該配列インデックスａの上位３２ビットが０であり、かつ前記プログラムを記述した言語の仕様により、当該配列インデックスａの下位３２ビットについて、
０≦配列インデックスａの下位３２ビット≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
２．配列インデックス（ａ＋ｂ）に関して、配列インデックスａ、ｂは両方とも既に符号拡張されており、かつ配列インデックスａまたは配列インデックスｂのどちらかの値が０〜０ｘ７ｆｆｆｆｆｆｆの範囲内にあり、かつ前記プログラムを記述した言語の仕様により、当該配列インデックス（ａ＋ｂ）の下位３２ビットについて、
０≦配列インデックス（ａ＋ｂ）の下位３２ビット≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
３．配列インデックス（ａ＋ｂ）に関して、配列の大きさの上限がmaxlen（０≦maxlen≦０ｘ７ｆｆｆｆｆｆｆ）で与えられ、かつ配列インデックスａ、ｂは両方とも既に符号拡張されており、かつ配列インデックスａまたは配列インデックスｂのどちらかの値が（−１）−０ｘ７ｆｆｆｆｆｆｆ〜０ｘ７ｆｆｆｆｆｆｆの範囲内にあり、かつ前記プログラムを記述した言語の仕様により、当該配列インデックス（ａ＋ｂ）の下位３２ビットについて、
０≦配列インデックス（ａ＋ｂ）の下位３２ビット＜maxlen≦０ｘ７ｆｆｆｆｆｆｆ
が成り立つ。
【請求項１１】
プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラと、
機械語コードに変換された前記プログラムを実行する処理装置とを備えたコンピュータ装置において、
前記コンパイラは、
前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納する補正命令生成部と、
前記メモリに格納された前記補正命令が付加された前記プログラムに対して前方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の入力値が入力以前に符号拡張されているか否かを調べ、当該入力値が入力以前に符号拡張されているような冗長な補正命令を除去する命令除去処理部と
を備えることを特徴とするコンピュータ装置。
【請求項１２】
プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラと、
機械語コードに変換された前記プログラムを実行する処理装置とを備えたコンピュータ装置において、
前記コンパイラは、
前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納する補正命令生成部と、
前記メモリに格納された前記補正命令が付加された前記プログラムに対して後方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の出力結果が使用される全ての場所において、符号拡張前のデータサイズ以下で使用されているか否かを調べ、当該出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されているような冗長な補正命令を除去する命令除去処理部と
を備えることを特徴とするコンピュータ装置。
【請求項１３】
コンピュータを制御してプログラムを変換するプログラム変換方法において、
前記コンピュータが、前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納するステップと、
前記コンピュータが、前記メモリに格納された前記補正命令が付加された前記プログラムに対して前方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の入力値が入力以前に符号拡張されているか否かを調べ、当該入力値が入力以前に符号拡張されているような冗長な補正命令を除去するステップと
を含むことを特徴とするプログラム変換方法。
【請求項１４】
コンピュータを制御してプログラムを変換するプログラム変換方法において、
前記コンピュータが、前記プログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値として当該プログラム中で定義されている値に関して、当該値のデータサイズを補正するための補正命令を当該プログラムに付加してメモリに格納するステップと、
前記コンピュータが、前記メモリに格納された前記補正命令が付加された前記実行プログラムに対して後方データフロー解析を行って、前記補正命令の各々に関して、当該補正命令の出力結果が使用される全ての場所において、符号拡張前のデータサイズ以下で使用されているか否かを調べ、当該出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されているような冗長な補正命令を除去するステップと
を含むことを特徴とするプログラム変換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム中の冗長な符号拡張命令を除去することにより、プログラムの実行効率の向上を図る方法に関する。
【０００２】
【従来の技術】
コンパイラでプログラムをコンパイルする場合に、ＣＰＵのアーキテクチャにおけるレジスタサイズよりも小さいサイズの値としてプログラム中で定義されている値に関しては、当該ＣＰＵのレジスタサイズに補正した後に計算するようにコードを生成することとなる。
【０００３】
例えば、６４ビットアーキテクチャ（演算処理やデータ転送を６４ビットで行い、６４ビットのメモリ・アドレッシングが可能な仕様）では、レジスタイメージは６４ビットである。そのため、プログラム中の３２ビット、１６ビット、８ビットの各値は、符号拡張により６４ビットの値として計算する必要がある。ここで、符号拡張とは、定義されている値の最上位ビットである符号ビットのさらに上位に当該符号ビットと同じ値を入れることである。
【０００４】
図１８に示すサンプルプログラムにおいて、「extend()」は３２ビットから６４ビットへの符号拡張を意味し、「i」はプログラム内で３２ビットの変数と仮定する。
この例で、「mem」が３２ビットのメモリ内の値で0xffffffff（符号付き３２ビットで「−１」）と仮定する場合、符号拡張命令（図中（１）行）を実行しないと、配列アクセス（図中（２）行）において誤った結果となってしまう。そこで、符号拡張により値のビット数をＣＰＵのレジスタイメージに対応させることが必要となる。
【０００５】
【発明が解決しようとする課題】
６４ビットアーキテクチャにおいて、３２ビットの値の演算を中心とする言語（例えばＪａｖａ）をコンパイルしようとすると、メモリからのロードだけではなく、ほとんどの整数型命令に対して符号拡張が必要となる。そして、図１８の（１）行に示したように符号拡張命令を挿入すれば、その分だけ当該プログラムの実行速度が低下することとなる。
【０００６】
ところで、３２ビットアーキテクチャ（すなわち、レジスタサイズが３２ビット）においても、１６ビットや８ビットの値を扱う場合には符号拡張が必要となる。これに対し、３２ビットアーキテクチャのＣＰＵであるＩＡ−３２では、メモリからのロードと符号拡張とを同時に行う命令（ＭＯＶＳＸ、ＭＯＶＺＸ）が存在する。したがって、この命令を用いる場合には、符号拡張によるＣＰＵの負荷を考慮する必要はない。
【０００７】
しかし、現時点で６４ビットアーキテクチャにおいては、メモリからのロードと符号拡張とを同時に行う命令が一般に知られておらず、かつシステムやアプリケーションの多くが３２ビットアーキテクチャを前提として設計されているという今日的状況においては、結果として、多くの整数型命令に対して符号拡張命令が必要となり、プログラムの実行速度を下げることとなる。
【０００８】
そこで、本発明は、プログラム中の冗長な符号拡張命令を除去し、プログラムの実行効率の向上を図ることを目的とする。
また、本発明は、プログラムをコンパイルする際に、冗長な符号拡張命令を除去することにより、実行効率の高いオブジェクトプログラムを生成するコンパイラを提供することを他の目的とする。
【０００９】
【課題を解決するための手段】
上記の目的を達成する手段として、本発明は、コンピュータを制御して実行プログラムを変換する変換プログラムであって、この実行プログラムに対し、この実行プログラム中で定義されている値を符号拡張するための符号拡張命令に関する解析を行う機能と、この解析結果に応じて、この実行プログラム中の符号拡張命令のうち、所定の符号拡張命令を除去する機能とをコンピュータに実現させることを特徴とする。
【００１０】
ここで、除去すべき冗長な符号拡張命令としては、所定の符号拡張命令における入力値が入力以前に符号拡張されている場合におけるこの符号拡張命令がある。また、所定の符号拡張命令における出力結果が、この出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されている場合におけるこの符号拡張命令がある。
したがって、上記の変換プログラムにて実現される符号拡張命令を除去する機能は、これらの条件に該当する符号拡張命令を除去する機能を含む。
【００１１】
また、この符号拡張命令を除去する機能は、選択的にいずれかを除去すべき複数の符号拡張命令がある場合に、実行頻度の高い符号拡張命令を除去する構成とすることができる。
【００１２】
上述した変換プログラムは、磁気ディスクや光ディスク、半導体メモリなどの記録媒体に記録して配布したり、プログラム伝送装置の記録装置に格納しネットワークを介して配信したりすることにより、提供することができる。
【００１３】
また、本発明は、プログラミング言語で記述されたプログラムのソースコードを機械語コードに変換するコンパイラにおいて、このプログラムを実行するＣＰＵのレジスタサイズよりも小さいサイズの値としてこのプログラム中で定義されている値に関して、この値のデータサイズを補正するための補正命令をこのプログラムに付加する補正命令生成部と、この補正命令生成部にて付加された補正命令のうち、所定の補正命令を除去する命令除去処理部とを備えることを特徴とする。
【００１４】
ここで、この命令除去処理部が除去すべき冗長な補正命令としては、一定の条件の下で、配列アクセスのアドレス計算のために付加された前記補正命令がある。かかる一定の条件には、言語仕様に基づいて定められる条件も含まれる。
また、この命令除去処理部は、この所定の値に関してこのプログラムにおけるループ処理の外側と内側のいずれか一方で補正命令を除去可能な場合に、このループ処理の内側に位置する補正命令を除去する構成とすることができる。
さらに、これらの条件に該当する補正命令を除去するため、この命令除去処理部は、使用−定義連鎖及び定義−使用連鎖を用いる構成とすることができる。
【００１５】
また、本発明は、プログラムのソースコードをコンパイルして機械語コードに変換するコンパイラと、機械語コードに変換されたプログラムを実行する処理装置とを備えたコンピュータ装置において、このコンパイラは、このプログラム中で定義されている値を符号拡張するためにこのプログラム中に挿入されている符号拡張命令のうち、所定の符号拡張命令を除去することを特徴とする。
【００１６】
ここで、このコンパイラは、所定の符号拡張命令における入力値が入力以前に符号拡張されている場合、所定の符号拡張命令における出力結果が、この出力結果が使用される全ての場所において符号拡張以前のデータサイズ以下で使用されている場合に、これらの符号拡張命令を除去する。
また、このコンパイラは、一定の条件の下で、配列アクセスのアドレス計算のために付加された前記補正命令を除去する。
さらに、このコンパイラは、実行頻度の高い符号拡張命令から順に、冗長な命令かどうかを判断し、除去する。
【００１７】
また、本発明は、コンピュータを制御してプログラムを変換するプログラム変換方法において、この実行プログラムに対し、このプログラム中で定義されている値を符号拡張するための符号拡張命令を付加するステップと、このプログラムに付加された符号拡張命令のうち、冗長な命令を除去するステップとを含むことを特徴とする。
【００１８】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて、この発明を詳細に説明する。
図１７は、本実施の形態におけるコンパイラが用いられるコンピュータ装置のシステム構成を示す図である。
図１７において、コンパイラ１０は、バイトコード（byte code）で記述された入力プログラムを入力して処理し、機械語で記述された出力プログラムを生成して出力する。
なお、本実施の形態において、コンパイラ１０は、ＪａｖａにおけるＪＩＴ（Just In Time）コンパイラのような、実行プログラムを実行する際に動的に実行プログラムのコンパイル処理を行うコンパイラであっても良いし、ソースプログラムを予めコンパイルして生成されたオブジェクトプログラムを実行プログラムとする使用形態におけるコンパイラであっても良い。
コンパイラ１０により生成された出力プログラムは、プログラム実行部３０により実行される。
【００１９】
図１は、本発明の一実施の形態におけるコンパイラの全体構成を説明する図である。
本実施の形態の背景として、入力プログラムは、３２ビットアーキテクチャのＣＰＵで動作することを想定して記述されているものとする。また、図１に示すコンパイラ１０にてコンパイルされた出力プログラムは、６４ビットアーキテクチャのＣＰＵで動作するものとする。したがって、コンパイラ１０は、ソースコードで記述された入力プログラムから機械語コードで記述された出力プログラムを生成する際に、プログラム中の必要な箇所に符号拡張命令を挿入する。
【００２０】
図１を参照すると、本実施の形態のコンパイラ１０は、実行プログラムに付加する符号拡張命令を生成する符号拡張命令生成部１１と、不要な符号拡張命令の除去を行う符号拡張命令除去処理部１２とを備える。
図１に示したコンパイラ１０の各構成要素は、コンピュータプログラムにより制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。ＣＰＵを制御する当該コンピュータプログラムは、ＣＤ−ＲＯＭやフロッピーディスクなどの記憶媒体に格納して配布したり、ネットワークを介して伝送したりすることにより提供される。
なお、図１に示したコンパイラ１０の構成要素は、本実施の形態における特徴的な機能に関して記述したものである。図示しないが、実際にはコンパイラ１０は、入力プログラムの字句解析や構文解析、機械語のコード生成といったコンパイル処理における一般的な機能を有することは言うまでもない。
【００２１】
コンパイラ１０の構成要素において、符号拡張命令生成部１１は、プログラム中の所定の値を３２ビットから６４ビットに補正する補正命令である符号拡張命令を生成し、コンパイル対象であるプログラムの所定の場所に挿入する。符号拡張命令を挿入する場所は、コンパイル後の出力プログラムが実行されるコンピュータ装置のアーキテクチャにおけるレジスタサイズ（６４ビット）よりも小さいデータサイズの変数の値が定義されている全ての場所である。
【００２２】
ところで、プログラムにおける符号拡張命令を挿入する場所として、変数の定義個所に挿入する方法と変数の使用個所に挿入する方法の２種類が考えられる。しかし、プログラムにおけるループ処理の部分において、変数の使用個所に挿入する方法で符号拡張命令を挿入した場合、後述する冗長な符号拡張命令の除去処理を実行する際に、単に符号拡張命令を除去するだけでは十分でなく、ループ不変の符号拡張命令をループ外に移動する処理が必須となる。これに対し、変数の定義個所に挿入する方法で符号拡張命令を挿入した場合は、変数の定義位置をループの外に移動するような最適化が行われた場合にのみ、対応する符号拡張命令をループ外に移動すれば良く、処理工数を削減することができる。
また、一般的に、変数の定義個所と使用個所では使用個所の方が数が多い。そのため、変数の使用個所に符号拡張命令を挿入する方法は、定義箇所に挿入する方法に比して、符号拡張命令の最適化処理に多くの時間を必要とする。
したがって、変数の定義箇所に符号拡張命令を挿入することが好ましい。
【００２３】
符号拡張命令除去処理部１２は、符号拡張命令生成部１１によりプログラムに挿入された符号拡張命令のうち、冗長な符号拡張命令を除去する。ここで、除去可能な符号拡張命令とは、次の二つの場合である。
１．符号拡張命令の入力（値）が必ず既に符号拡張されている場合。
２．符号拡張命令の出力結果が全ての場所で入力のデータサイズ以下で使用されている場合。
【００２４】
実際に符号拡張命令を除去する処理は、例えば、上記二つの条件を両方とも用いて除去を行う場合、次の２段階のステップで実行することができる。
まず、後方データフロー解析を用いて、各符号拡張命令の出力結果に関して、当該出力結果が使用される全ての場所において、符号拡張前のデータサイズ（３２ビットから６４ビットへの符号拡張の場合は３２ビット）以下で使用されているかどうかを調べる。そして、これに該当する符号拡張命令を除去する。
次に、前方データフロー解析を用いて、各符号拡張命令の入力に関して、必ず既に符号拡張されているかどうかを調べる。そして、これに該当する符号拡張命令を除去する。
なお、実際の除去処理において上の二つのステップは、いずれを先に実行しても良い。また、冗長な命令の除去によるプログラムの効率化の効果は劣るが、いずれか一方のみを実行しても良い。
【００２５】
図２は、上述した本実施の形態による、符号拡張命令生成部１１による符号拡張命令の挿入（ステップ２０１）から、符号拡張命令除去処理部１２による符号拡張命令の除去処理（ステップ２０２、２０３）までの処理の流れを示すフローチャートである。
【００２６】
次に、本発明の他の実施の形態について説明する。
図３は、本実施の形態におけるコンパイラの全体構成を説明する図である。図３に示すコンパイラ２０は、図１７のコンピュータ装置において、コンパイラ１０に代えて設けられる。
本実施の形態においても、入力プログラムは、３２ビットアーキテクチャのＣＰＵで動作することを想定して記述されているものとする。また、図３に示すコンパイラ２０にてコンパイルされた出力プログラムは、６４ビットアーキテクチャのＣＰＵで動作するものとする。したがって、コンパイラ２０は、ソースコードで記述された入力プログラムから機械語コードで記述された出力プログラムを生成する際に、プログラム中の必要な箇所に符号拡張命令を挿入する。
【００２７】
図１及び図２を参照して説明した実施の形態によっても、多くの冗長な符号拡張命令を除去することができる。しかし、次のような場合には、不要な符号拡張命令が除去されずに残ってしまう。
すなわち、ループの誘導変数が配列のインデックスとして使われている場合、ループ内の当該変数に対する符号拡張命令は除去できない。その理由は、配列アクセスのアドレス計算そのものはレジスタサイズで計算されることから、出力結果の解析処理（図２のステップ２０２参照）では除去条件に該当しないためである。また、ループ内で変数が更新されることから、入力の解析処理（図２のステップ２０３）でも除去条件に該当しないためである。
また、図１及び図２に示した実施の形態は、一定の条件の下では、必ずしも効率の良い符号拡張命令の除去処理ができるとは限らない。
例えば、プログラム中のループ処理の外側または内側のどちらか片方しか符号拡張命令を除去できない場合、実行頻度の高いループ処理の内側の符号拡張命令を除去する方がコンパイル後のプログラムにおける実行速度の向上を期待できる。しかしながら、後方データフロー解析を使った出力結果の解析処理では実行順で後の符号拡張命令が残る傾向にあり、前方データフロー解析を使った入力の解析処理では実行順で先の符号拡張命令が残る傾向にあり、いずれもループ処理の構造及び命令の実行頻度を考慮してはいないため、プログラムの記述順序によっては、ループ処理の内側の符号拡張命令が残る場合がある。
図３に示した本実施の形態によれば、このような場合にも効果的に不要な符号拡張命令を除去することが可能である。
【００２８】
図３を参照すると、本実施の形態のコンパイラ２０は、プログラムに付加する符号拡張命令を生成する符号拡張命令生成部２１と、不要な符号拡張命令の除去順を決定する除去順決定部２２と、実際に符号拡張命令の除去を行う符号拡張命令除去処理部２３とを備える。
図３に示したコンパイラ２０の各構成要素は、コンピュータプログラムにより制御されたＣＰＵにて実現される仮想的なソフトウェアブロックである。ＣＰＵを制御する当該コンピュータプログラムは、ＣＤ−ＲＯＭやフロッピーディスクなどの記憶媒体に格納して配布したり、ネットワークを介して伝送したりすることにより提供される。
なお、図３に示したコンパイラ２０の構成要素は、本実施の形態における特徴的な機能に関して記述したものである。図示しないが、実際にはコンパイラ２０は、入力プログラムの字句解析や構文解析、機械語のコード生成といったコンパイル処理における一般的な機能を有することは言うまでもない。
【００２９】
コンパイラ２０の構成要素において、符号拡張命令生成部２１は、図１に示したコンパイラ１０における符号拡張命令生成部１１と同様であり、コンパイル後の出力プログラムが実行されるコンピュータ装置のアーキテクチャにおけるレジスタサイズ（６４ビット）よりも小さいデータサイズの変数の値が定義されている全ての場所に符号拡張命令を挿入する。
【００３０】
除去順決定部２２は、コンパイラ２０の出力プログラム（コンパイル後のプログラム）が実行された場合に、実行される頻度が高いと予想される符号拡張命令から順に除去順を決定する。これは、選択的にいずれか一方を除去すべき複数の前記符号拡張命令がある場合に、実行頻度の高い方の符号拡張命令を除去することにより、コンパイル後のプログラムにおける実行速度の一層の向上を図るためである。
【００３１】
具体的には、例えば、プログラム中におけるループ処理の外側及び内側に存在する符号拡張命令のうち、どちらか一方しか除去できない場合がある。この場合、ループの内側ほど実行される頻度が高いため、ループの最内ネストから順に符号拡張命令を除去することが好ましい。
また、プログラム中には必ず実行されるパスと条件に応じて実行されるパスとが存在する。そこで、これら２種類のパスに記述された符号拡張命令のうち一方しか除去できない場合は、必ず実行されるパスに記述された符号拡張命令を除去することが好ましい。
【００３２】
図８は、除去順決定部２２をコンパイラ２０に実装するためのアルゴリズムの例を示す図である。図中、「EliminateOneExtend(I)」は、一つの符号拡張命令Ｉに対する除去処理（後述）に移行することを示す。
なお、どのような状況においてどの符号拡張命令の実行頻度が高いかは、状況に応じて個別的に判断し、設定しておくことができる。また、どちらの符号拡張命令の実行頻度が高いかを判断できない場合は、前方データフロー解析や後方データフロー解析などの通常の手法にしたがう順番で符号拡張命令の除去を行えば良い。
複数の符号拡張命令のうち選択的に一方しか除去できない場合としては、例えば、配列アクセスのアドレス計算に対する符号拡張命令は、配列インデックスにかかわる計算の一箇所で行えば良い場合が多い。そのため、ある場所で符号拡張命令を除去した影響で、他の符号拡張命令を除去できなくなる場合がある。
【００３３】
符号拡張命令除去処理部２３は、除去順決定部２２によって決定された除去順にしたがって、符号拡張命令の除去処理を行う。
また、本実施の形態の符号拡張命令除去処理部２３は、一定の条件の下で、配列アクセスのアドレス計算のために配列インデックスに付加された符号拡張命令を除去する。
【００３４】
図４は、符号拡張命令除去処理部２３が、プログラム中の一つの符号拡張命令を除去する際の動作を説明するフローチャートである。符号拡張命令除去処理部２３は、除去順決定部２２により決定された順番に従って、各符号拡張命令に対して図４に示す処理を行い、必要に応じて符号拡張命令の除去処理を行う。
図４に示すように、符号拡張命令除去処理部２３は、まず、処理対象の符号拡張命令を順次入力する（ステップ４０１）。そして、対象である符号拡張命令の出力について解析処理を行い（ステップ４０２）、解析結果に応じて符号拡張が必要かどうかを判断する（ステップ４０３）。解析処理及び判断の詳細については後述する。
符号拡張が不要と判断した場合は、当該符号拡張命令を除去する（ステップ４０６）。
【００３５】
一方、出力についての解析では符号拡張が不要と判断できなかった場合は、次に当該符号拡張命令の入力について解析を行い（ステップ４０４）、解析結果に応じて符号拡張が必要かどうかを判断する（ステップ４０５）。解析処理及び判断の詳細については後述する。
符号拡張が不要と判断した場合は、当該符号拡張命令を除去する（ステップ４０６）。また、入力についての解析においても符号拡張が不要と判断できなかった場合は、当該符号拡張命令を除去せずに処理を終了する。
なお、符号拡張命令の出力に関する解析処理及び判断（ステップ４０２、４０３）と、符号拡張命令の入力に関する解析処理及び判断（ステップ４０４、４０５）とは、いずれを先に実行しても良いことは言うまでもない。
【００３６】
図９は、符号拡張命令除去処理部２３をコンパイラ２０に実装するためのアルゴリズムの例を示す図である。
図９において、符号拡張命令の出力に関する解析処理にはＤＵ−ｃｈａｉｎ（definition-use chain：定義−使用連鎖）が用いられ、符号拡張命令の入力に関する解析処理にはＵＤ−ｃｈａｉｎ（use-definition chain：使用−定義連鎖）が用いられている。なお、ＤＵ−ｃｈａｉｎ及びＵＤ−ｃｈａｉｎは、符号拡張命令除去処理部２３による処理が開始される前の段階で作成されている。
なお、図中、EXT、Extend、Extend命令などとあるのは符号拡張命令である（以下、図１０乃至図１６において同様）。
【００３７】
ここで、符号拡張命令を除去できる場合は、まず、「１．符号拡張命令の入力（値）が必ず既に符号拡張されている場合」及び「２．符号拡張命令の出力結果が全ての場所で入力のデータサイズ以下で使用されている場合」である。したがって、ステップ４０２、４０３の解析処理及び判断において、第２の条件を判断し、ステップ４０４、４０５の解析処理及び判断において、第１の条件を判断する。
しかしながら、かかる条件だけでは、上述したように、配列のアドレス計算のために配列インデックスに付加された符号拡張命令は除去できずに残ってしまう場合が多い。
ところが、言語仕様により負のインデックスを使って配列をアクセスしてはいけないと定められている言語（Ｊａｖａ、Ｃ、Ｃ＋＋など）では、配列インデックスに必ず負の値が入らないと仮定することで、一定の条件下、符号拡張を不要とすることができる（下記、定理１、定理２、定理３）。そこで、符号拡張命令の出力についての解析処理（ステップ４０２）において、上述した第２の条件の他に、配列のアドレス計算のために配列インデックスに付加された符号拡張命令が定理１、定理２、定理３に該当するかどうかを判断し、該当する場合は当該符号拡張命令を除去する。以下、各定理について説明する。
【００３８】
＜定理１＞
次の２つの条件が全て満たされる場合、配列インデックスａにてアクセスされる配列のアドレス計算には、当該配列インデックスａに対して３２ビットから６４ビットへの符号拡張は必要ない。
（１）配列インデックスａの上位３２ビットが０で初期化されている。
（２）言語仕様により、配列インデックスａの下位３２ビットについて、
0 ≦ 配列インデックスａの下位３２ビット ≦ 0x7fffffff
が成り立つ。
＜証明＞
条件（１）より、配列インデックスａの取り得る範囲は、0 〜 0xffffffffである。また条件（２）により、0 ≦ 配列インデックスａ ≦ 0x7fffffffとなり、負の値にはならない。したがって、符号拡張は必要ない。
【００３９】
＜定理２＞
次の３つの条件が全て満たされるときには、配列インデックス（ａ＋ｂ）でアクセスされる配列のアドレス計算には、配列インデックス（ａ＋ｂ）に対して３２ビットから６４ビットへの符号拡張は必要ない。
（１）配列インデックスａ、ｂは両方とも既に符号拡張されている。
（２）配列インデックスａまたは配列インデックスｂのどちらかの値が0 〜 0x7fffffffの範囲内にある。
（３）言語仕様により、配列インデックス（ａ＋ｂ）の下位３２ビットについて、
0 ≦ 配列インデックス（ａ＋ｂ）の下位３２ビット ≦ 0x7fffffff
が成り立つ。
＜証明＞
配列インデックス（ａ＋ｂ）について、配列インデックスａと配列インデックスｂとは交換可能であるため、配列インデックスａが条件（２）に合うときのみを証明できれば、配列インデックスｂが条件（２）に合うときについても同様に証明することができる。したがって、配列インデックスａが条件（２）に合う場合、すなわち配列インデックスａが 0 〜 0x7fffffff の範囲内にある場合について説明する。
ｉ）配列インデックスｂが 0 〜 0x7fffffff の範囲のとき：配列インデックス（ａ＋ｂ）の取り得る範囲は 0 〜 0xffffffff となり、上位３２ビットについて０であることが保証されているので、定理１より、符号拡張は必要ない。
ｉｉ）配列インデックスｂが 0xffffffff80000000 〜 0xffffffffffffffff の範囲のとき：配列インデックス（ａ＋ｂ）の取りうる範囲は 0xffffffff80000000 〜 0xffffffffffffffff、及び 0 〜 0x7ffffffe である。条件（３）により、配列インデックス（ａ＋ｂ）は0 ≦ 配列インデックス（ａ＋ｂ） ＜ 0x7fffffffとなり、負の値にはならないため、符号拡張は必要ない。
【００４０】
また、配列の大きさの上限が、ある値に制限されている（または制限できる）場合には、定理２を拡張した次の定理３が導き出せる。定理３を利用すると、片方が負の値の足し算式であっても、符号拡張命令の除去を行うことができる。
例えば、Ｊａｖａ言語では、言語仕様上の配列の大きさの最大値は0x7fffffffとなるので、配列インデックスａまたは配列インデックスｂのどちらかの値が -1 〜 0x7fffffff の範囲内にあり、配列インデックスａ、ｂの両方が符号拡張されていれば、配列インデックス（ａ＋ｂ）でアクセスされる配列のアドレス計算には、配列インデックス（ａ＋ｂ）に対して符号拡張は必要なくなる。
また、別の例を挙げると、言語処理システムの実装上の制限等により、配列の大きさの最大値が、例えば0x1fffffffに制限できる場合は、配列インデックスａまたは配列インデックスｂのどちらかの値が 0xffffffff9fffffff(-1610612737)〜 0x7fffffff の範囲内にあり、配列インデックスａ、ｂの両方が符号拡張されていれば、配列インデックス（ａ＋ｂ）でアクセスされる配列のアドレス計算には、配列インデックス（ａ＋ｂ）に対して符号拡張は必要なくなる。
【００４１】
＜定理３＞
次の４つの条件がすべて満たされるときには、配列インデックス（ａ＋ｂ）でアクセスされる配列のアドレス計算には、配列インデックス（ａ＋ｂ）に対して３２ビットから６４ビットへの符号拡張は必要ない。
（１）配列の大きさの上限がmaxlenで与えられ、0 ≦ maxlen ≦ 0x7fffffff が成り立つ。
（２）配列インデックスａ、ｂは両方ともすでに符号拡張されている。
（３）配列インデックスａまたは配列インデックスｂのどちらかの値が (maxlen-1)-0x7fffffff 〜 0x7fffffff の範囲内にある。
（４）言語仕様により、配列インデックス（ａ＋ｂ）の下位３２ビットについて、
0 ≦ 配列インデックス（ａ＋ｂ）の下位３２ビット ＜ maxlen ≦ 0x7fffffffが成り立つ。
＜証明＞
配列インデックス（ａ＋ｂ）について、配列インデックスａと配列インデックスｂとは交換可能であるため、配列インデックスａが条件（３）に合うときのみを証明できれば、配列インデックスｂが条件（３）に合うときについても同様に証明することができる。したがって、配列インデックスａが条件（３）に合う場合について説明する。
ａ）配列インデックスａが 0 〜 0x7fffffff の範囲内にある場合
定理２より、この場合は、符号拡張は必要ない。
ｂ）配列インデックスａが (maxlen-1)-0x7fffffff 〜 0xffffffffffffffffの範囲内にある場合
ｉ）配列インデックスｂが 0 〜 0x7fffffff の範囲のとき：定理２より、この場合は、符号拡張は必要ない。
ｉｉ）配列インデックスｂが 0xffffffff80000000 〜 0xffffffffffffffffの範囲のとき：配列インデックス（ａ＋ｂ）の取り得る範囲は0xffffffff00000000+maxlen 〜 0xfffffffffffffffeであり、配列インデックス（ａ＋ｂ）の下位３２ビットの取り得る範囲はmaxlen 〜 0xfffffffeとなる。この場合、条件（４）が成り立つことは一切ないため、条件外となり、符号拡張は必要である。
【００４２】
次に、図４に示した符号拡張命令除去処理部２３による、符号拡張命令の出力についての解析処理及び判断（ステップ４０２、４０３）の詳細を説明する。
図５は、符号拡張命令の出力についての解析処理の内容を説明するフローチャートである。上述したように、この処理には、上記の定理１、定理２、定理３に基づいて、配列のアドレス計算のために付加された符号拡張命令が必要かどうかを判断する処理が含まれる。
【００４３】
図５に示すように、符号拡張命令除去処理部２３は、まず、符号拡張命令をＥ、解析対象の値をＴとする（ステップ５０１）。さらに、符号拡張命令Ｅによる解析対象Ｔの出力変数をＤとし（ステップ５０２）、出力変数Ｄを使用する命令をＩとする（ステップ５０３）。
そして、命令Ｉが出力変数Ｄの上位３２ビットの値に全く影響を受けない命令かどうかを判断する（ステップ５０４）。
【００４４】
命令Ｉが出力変数Ｄの上位３２ビットの値に影響を受る命令である場合、次に符号拡張命令除去処理部２３は、命令Ｉの出力結果に関して符号拡張の必要なしと判断できるならば、解析対象Ｔも必要なしと判断できるかどうかを調べる（ステップ５０５）。解析対象Ｔも必要なしと判断した場合、符号拡張命令除去処理部２３は、この命令Ｉの出力結果に対して本処理（図５の処理）を再帰的に呼び出して実行する（ステップ５０６）。解析対象Ｔも必要なしと判断できる命令には、例えばＣＯＰＹ命令がある。
【００４５】
一方、ステップ５０５で解析対象Ｔが必要であると判断した場合、次に符号拡張命令除去処理部２３は、この命令Ｉが配列のアドレス計算のための命令かどうかを判断する（ステップ５０７）。命令Ｉが配列のアドレス計算のための命令である場合は、かかる命令に対する解析処理を実行する（ステップ５０８）。
命令Ｉが配列のアドレス計算のための命令でない場合は、図４のステップ４０３において、当該符号拡張命令Ｅが必要であると判断する。
また、ステップ５０６、５０８の解析処理を経て符号拡張が必要と判断された場合も、図４のステップ４０３において、当該符号拡張命令Ｅが必要であると判断する（ステップ５０９）。
【００４６】
ステップ５０４において命令Ｉが出力変数Ｄの上位３２ビットの値に影響を受けない命令である場合、及びステップ５０９において符号拡張が不要と判断された場合、符号拡張命令除去処理部２３は、出力変数Ｄを使用している命令が他にも存在するかどうかを調べ、存在するならば、当該他の命令を新たに命令Ｉとして処理を繰り返す（ステップ５１０、５０３）。
一方、出力変数Ｄを使用している命令が他に存在しない場合、すなわち出力変数Ｄを使用している全ての命令について当該符号拡張命令Ｅが必要であると判断できなかった場合は、図４のステップ４０３において、当該符号拡張命令Ｅを不要であると判断する。
【００４７】
図１０は、符号拡張命令除去処理部２３が図５に示した符号拡張命令の出力に関する解析処理及び判断を実行するためのアルゴリズムの例を示す図である（図９における＜USEに対するExtend命令は必要か解析＞（EXT, I）の内容）。
図１０において、５行目の「case 明示的な整数型cast命令：」から１１行目の「case 符号無し右シフト命令：」までがステップ５０４の条件分岐に対応する。また、１３行目の「case 足し算命令：」から２０行目の「case コピー命令：」までがステップ５０５の条件分岐に対応する。また、２６行目の「case 配列のアドレス計算：」がステップ５０７の条件分岐に対応する。
【００４８】
次に、ステップ５０８の処理の内容について説明する。
図６は、配列のアドレス計算のための命令に対する解析処理を説明するフローチャートである。
図６に示すように、符号拡張命令除去処理部２３は、まず、符号拡張命令をＥ、解析対象の値をＴとする（ステップ６０１）。さらに、符号拡張命令Ｅの入力変数をＳとし（ステップ６０２）、入力変数Ｓを設定している命令をＩとする（ステップ６０３）。
そして、命令Ｉの出力結果の上位３２ビットが必ず０であるかどうかを判断する（ステップ６０４）。この判断は、上述した定理１の適用に相当する。
【００４９】
命令Ｉの出力結果の上位３２ビットが必ず０であるとは言えない場合、次に、符号拡張命令除去処理部２３は、命令Ｉが足し算か引き算命令であり、かつ命令Ｉの出力変数の仕様箇所が１カ所かどうかを判断する（ステップ６０５）。命令Ｉがこの条件を満足する場合、次に、符号拡張命令除去処理部２３は、命令Ｉのオペランドについて、上述した定理２または定理２を拡張した定理３の条件が成り立つかどうかを判断する（ステップ６０６）。
命令Ｉがステップ６０５の条件を満足しない場合、または命令Ｉのオペランドについて定理２あるいは定理３の条件が成立しない場合は、図４のステップ４０３において、当該符号拡張命令Ｅが必要であると判断する。
【００５０】
ステップ６０４において命令Ｉの出力結果の上位３２ビットは必ず０であると判断した場合、及びステップ６０６において命令Ｉのオペランドについて定理２または定理３の条件が成立する場合、符号拡張命令除去処理部２３は、入力変数Ｓを設定している命令が他にも存在するかどうかを調べ、存在するならば、当該他の命令を新たに命令Ｉとして処理を繰り返す（ステップ６０７、６０３）。
一方、入力変数Ｓを設定している命令が他に存在しない場合、すなわち入力変数Ｓを設定している全ての命令について当該符号拡張命令Ｅが必要であると判断できなかった場合は、図４のステップ４０３において、当該符号拡張命令Ｅを不要であると判断する。
【００５１】
図１１は、符号拡張命令除去処理部２３が図６に示した配列のアドレス計算のための命令に対する解析処理を実行するためのアルゴリズムの例を示す図である（図１０における＜配列のアドレス計算についてExtend命令は必要か解析＞（EXT, I（図１１ではEOP2））の内容）。
図１１の９、１０行目において、定理３を用いることが記述されているが、言語仕様によっては定理２を用いることができる。定理２を用いる場合、条件のうち、「Dのどちらか片方のオペランドは−１以上である」の部分が「Dのどちらか片方のオペランドは０以上である」に変わることとなる。
【００５２】
次に、図４に示した符号拡張命令除去処理部２３による、符号拡張命令の入力についての解析処理及び判断（ステップ４０４、４０５）の詳細を説明する。
図７は、符号拡張命令の入力についての解析処理の内容を説明するフローチャートである。
図７に示すように、符号拡張命令除去処理部２３は、まず、解析対象の符号拡張命令をＥとし（ステップ７０１）、命令Ｅの入力変数をＳとし（ステップ７０２）、入力変数Ｓを設定している命令をＩとする（ステップ７０３）。
そして、命令Ｉの出力が必ず符号拡張されているかどうかを判断する（ステップ７０４）。命令Ｉの出力が必ず符号拡張されている命令としては、例えば配列の長さを返す命令などがある。
【００５３】
命令Ｉの出力が必ず符号拡張されているとは言えない場合、次に、符号拡張命令除去処理部２３は、命令Ｉの入力変数Ｓが符号拡張されていれば、解析対象である符号拡張命令Ｅも必要なしと判断できるかどうかを調べる（ステップ７０５）。符号拡張命令Ｅも必要なしと判断した場合、符号拡張命令除去処理部２３は、この命令Ｉの入力に対して本処理（図７の処理）を再帰的に呼び出して実行する（ステップ７０６）。符号拡張命令Ｅも必要なしと判断できる命令には、例えばＣＯＰＹ命令がある。
【００５４】
ステップ７０５において、命令Ｉの入力変数Ｓが符号拡張されていても解析対象である符号拡張命令Ｅが必要であると判断された場合、図４のステップ４０３において、当該符号拡張命令Ｅが必要であると判断する（ステップ７０７）。
また、ステップ７０６の解析処理を経て符号拡張が必要と判断された場合も、図４のステップ４０３において、当該符号拡張命令Ｅが必要であると判断する（ステップ７０７）。
【００５５】
ステップ７０４において命令Ｉの出力が必ず符号拡張されている場合、及びステップ７０７において符号拡張が不要と判断された場合、符号拡張命令除去処理部２３は、入力変数Ｓを設定している命令が他にも存在するかどうかを調べ、存在するならば、当該他の命令を新たに命令Ｉとして処理を繰り返す（ステップ７０８、７０３）。
一方、入力変数Ｓを設定している命令が他に存在しない場合、すなわち入力変数Ｓを設定している全ての命令について当該符号拡張命令が必要であると判断できなかった場合は、図４のステップ４０３において、当該符号拡張命令Ｅを不要であると判断する。
【００５６】
図１２は、符号拡張命令除去処理部２３が図７に示した符号拡張命令の入力に関する解析処理及び判断を実行するためのアルゴリズムの例を示す図である（図９における＜Destinationに対してExtend命令は必要か解析＞（I）の内容）。
図１２において、５行目の「case Ｉの出力結果が符号拡張された状態になっているもの：」がステップ７０４の条件分岐に対応する。また、８行目の「case コピー命令：」がステップ７０５の条件分岐に対応する。
【００５７】
次に、サンプルプログラムに対する符号拡張命令の付加及び除去処理の実行例を示す。
図１３は、本実施の形態により符号拡張命令の挿入及び除去を行う対象のサンプルプログラムを示す図である。
ここでは、サンプルプログラムに対し、図３に示した実施の形態のコンパイラ２０により符号拡張命令の付加及び除去処理を行うこととする。また、各処理は、図８乃至図１２に示したアルゴリズムにしたがうこととする。
【００５８】
まず、図１３に示すサンプルプログラムがコンパイラ２０に入力され、符号拡張命令生成部２１がこのサンプルプログラムに符号拡張命令を挿入する。
図１４は、図１３のサンプルプログラムにおける所定の箇所に対して符号拡張命令（extend）を生成した状態の中間表現を示す図である。
図１４において、（２）、（４）、（７）、（９）、（１５）の各行が符号拡張命令である。
【００５９】
次に、除去順決定部２２が、図８に示したアルゴリズムにしたがって、図１４のプログラム中の各符号拡張命令に対して、除去処理を行う順番が決定される。ここでは、サンプルプログラムを実行する際の実行頻度の高いものから、（１５）→（２）→（４）→（７）→（９）の順で符号拡張命令の除去を行うように決定されたものとする。
【００６０】
最初に、（１５）の符号拡張命令の除去を試みる。
（１５）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所（出力結果を使用している命令）は（１１）、（１２）、（１３）、（１４）、（１５）、（１６）の各命令である。この中で（１２）以外は、図９及び図１０に示した＜ＵＳＥに対するＥｘｔｅｎｄ命令は必要か解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。また、（１２）については、図１０及び図１１に示した＜配列のアドレス計算についてＥｘｔｅｎｄ命令が必要であるか解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。その結果、（１５）の符号拡張命令は除去される。
【００６１】
次に、（２）の符号拡張命令の除去を試みる。
（２）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（５）であり、（５）はコピー命令なので、図１０に示すアルゴリズムにより、（５）の命令の出力結果を使用している命令が次に解析される。そして、（５）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（６）である。
（６）は引き算命令なので、図１０に示すアルゴリズムにより、さらに（６）の命令の出力結果を使用している命令が解析される。そして、（６）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（７）であり、符号拡張命令なので、図１０に示すアルゴリズムにより、不要と判断される。その結果、（２）の符号拡張命令は除去される。
【００６２】
次に、（４）の符号拡張命令の除去を試みる。
（４）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（１０）、（１６）の各命令であり、いずれも図９及び図１０に示す＜ＵＳＥに対するＥｘｔｅｎｄ命令は必要か解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。その結果、（４）の符号拡張命令は除去される。
【００６３】
次に、（７）の符号拡張命令の除去を試みる。
（７）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（１０）、（１１）、（１２）、（１３）、（１４）、（１６）の各命令である。そこで、図９及び図１０のアルゴリズムにより個々に解析していくこととなるが、（１２）におけるＵＳＥ（（７）の出力結果の使用）に対しては、（１５）を以前に除去している影響で必要と判断される。そのため、（７）の符号拡張命令は除去されない。
【００６４】
次に、（９）の符号拡張命令の除去を試みる。
（９）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（１１）であり、図９及び図１０に示した＜ＵＳＥに対するＥｘｔｅｎｄ命令は必要か解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。その結果、（９）の符号拡張命令は除去される。
【００６５】
以上の処理の結果、（７）以外の符号拡張命令は除去される。
図１５は、図１４のプログラムに対して上記の除去順を考慮した符号拡張命令の除去処理を行った結果を示す図である。
【００６６】
ここで、図１３のサンプルプログラムに対して、図１に示した実施の形態のコンパイラ１０により符号拡張命令の付加及び除去処理を行った場合について考える。なお、各処理は図９乃至図１２のアルゴリズムにしたがって実行されるものとする。
まず、符号拡張命令生成部１１により、図１３のサンプルプログラムに対して符号拡張命令が付加され、図１４に示した状態となる。
図１のコンパイラ１０は符号拡張命令の実行頻度に応じて除去処理を行う順番を決定する手段を持たないので、例えばプログラムの先頭から順に符号拡張命令の除去を試みるものとする。
【００６７】
この場合、上述した手順と同様の手順で（２）、（４）の符号拡張命令が除去され、次に（７）の符号拡張命令の除去が試みられる。
（７）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（１０）、（１１）、（１２）、（１３）、（１４）、（１６）の各命令である。したがって、（１２）以外は、図９及び図１０に示した＜ＵＳＥに対するＥｘｔｅｎｄ命令は必要か解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。また、（１２）は、図１０及び図１１に示した＜配列のアドレス計算についてＥｘｔｅｎｄ命令が必要であるか解析＞のアルゴリズムにより、符号拡張命令は不要と判断される。その結果、（７）の符号拡張命令は除去される。
【００６８】
次に、（９）の符号拡張命令が上述した手順と同様の手順で除去され、次に（１５）の符号拡張命令の除去が試みられる。
（１５）のｄｅｓｔｉｎａｔｉｏｎに対するＵＳＥの場所は（１１）、（１２）、（１３）、（１４）、（１５）、（１６）の各命令である。そして、（１２）におけるＵＳＥ（（１５）の出力結果の使用）に対しては、（７）を以前に除去している影響で必要と判断される。そのため、（１５）の符号拡張命令は除去されない。
【００６９】
以上の処理の結果、（１５）以外の符号拡張命令が除去されることとなる。
図１６は、図１４のプログラムに対して上記の除去順を考慮しない符号拡張命令の除去処理を行った結果を示す図である。
【００７０】
図１５、１６の処理結果を比較すると、（７）と（１５）の符号拡張命令については、いずれか一方が除去され、他方が残ることとなる。
いずれの場合であっても、（２）、（４）、（９）の符号拡張命令と（７）または（１５）の符号拡張命令の一方とを除去することにより、プログラムの実行効率を向上させることが可能である。数値計算処理プログラム（メソッドレベル）であれば最大で２倍程度、アプリケーションプログラムであれば最大１２パーセント程度のパフォーマンスの向上が期待できる。
しかしながら、ループ内が実行されることにより、（７）の符号拡張命令が残っている場合よりも（１５）の符号拡張命令が残っている場合の方が、実行速度が落ちてしまう。したがって、除去順を考慮して符号拡張命令の除去処理を行う方が、（１５）の符号拡張命令を除去できる分だけ、さらにプログラムの実行効率を向上させることができることがわかる。
【００７１】
なお、上述した実施の形態では、本発明による符号拡張命令の付加及び除去処理をコンパイラの機能として実現する場合について説明した。
しかし本発明は、コンパイラの機能として実現する他に、所定のプログラムを処理対象とし、プログラム中に符号拡張命令を生成し、かつ生成した符号拡張命令のうちで冗長なものを除去するプログラム変換手段としてコンピュータ装置に設けることもできる。
また、既にプログラム中に挿入されている符号拡張命令を検出し、冗長な命令を除去するプログラム変換手段としてコンピュータ装置に設けることもできる。
さらに、処理対象である言語についても、コンパイラ言語に限らず、応用可能な範囲でインタプリタ言語に関しても利用することが可能である（例えば、符号拡張命令の入力が符号拡張不要の状態になっている場合に符号拡張命令を除去する手法）。
【００７２】
【発明の効果】
以上説明したように、本発明によれば、プログラム中の冗長な符号拡張命令を除去し、プログラムの実行効率の向上を図ることが可能となる。
また、本発明によれば、プログラムをコンパイルする際に、冗長な符号拡張命令を除去することにより、実行効率の高いオブジェクトプログラムを生成するコンパイラを提供することができる。
【図面の簡単な説明】
【図１】  本発明の一実施の形態におけるコンパイラの全体構成を説明する図である。
【図２】  図１のコンパイラによる符号拡張命令の挿入から除去処理までの処理の流れを示すフローチャートである。
【図３】  本発明の他の実施の形態におけるコンパイラの全体構成を説明する図である。
【図４】  図３のコンパイラにおける符号拡張命令除去処理部が、プログラム中の一つの符号拡張命令を除去する動作を説明するフローチャートである。
【図５】  図４の動作における符号拡張命令の出力についての解析処理の内容を説明するフローチャートである。
【図６】  図５の動作における配列のアドレス計算のための命令に対する解析処理を説明するフローチャートである。
【図７】  図４の動作における符号拡張命令の入力についての解析処理の内容を説明するフローチャートである。
【図８】  本実施の形態における除去順決定部をコンパイラに実装するためのアルゴリズムの例を示す図である。
【図９】  本実施の形態における符号拡張命令除去処理部をコンパイラに実装するためのアルゴリズムの例を示す図である。
【図１０】  本実施の形態における符号拡張命令除去処理部が符号拡張命令の出力に関する解析処理及び判断を実行するためのアルゴリズムの例を示す図である。
【図１１】  本実施の形態における符号拡張命令除去処理部が配列のアドレス計算のための命令に対する解析処理を実行するためのアルゴリズムの例を示す図である。
【図１２】  本実施の形態における符号拡張命令除去処理部が符号拡張命令の入力に関する解析処理及び判断を実行するためのアルゴリズムの例を示す図である。
【図１３】  本実施の形態により符号拡張命令の挿入及び除去を行う対象のサンプルプログラムを示す図である。
【図１４】  図１３のサンプルプログラムにおける所定の箇所に対して符号拡張命令を生成した状態の中間表現を示す図である。
【図１５】  図１４のプログラムに対して除去順を考慮して符号拡張命令の除去処理を行った結果を示す図である。
【図１６】  図１４のプログラムに対して除去順を考慮せずに符号拡張命令の除去処理を行った結果を示す図である。
【図１７】  本実施の形態におけるコンパイラが用いられるコンピュータ装置のシステム構成を示す図である。
【図１８】  符号拡張命令の必要性を説明するサンプルプログラムである。
【符号の説明】
１０、２０…コンパイラ、１１、２１…符号拡張命令生成部、１２、２３…符号拡張命令除去処理部、２２…除去順決定部
【図１】
0003763516.tif 000002
【図２】
0003763516.tif 000003
【図３】
0003763516.tif 000004
【図４】
0003763516.tif 000005
【図５】
0003763516.tif 000006
【図６】
0003763516.tif 000007
【図７】
0003763516.tif 000008
【図８】
0003763516.tif 000009
【図９】
0003763516.tif 000010
【図１０】
0003763516.tif 000011
【図１１】
0003763516.tif 000012
【図１２】
0003763516.tif 000013
【図１３】
0003763516.tif 000014
【図１４】
0003763516.tif 000015
【図１５】
0003763516.tif 000016
【図１６】
0003763516.tif 000017
【図１７】
0003763516.tif 000018
【図１８】
0003763516.tif 000019