(57)【要約】  プログラムを最適化する場合に、最適化前にプログラムの実行を必要とせずに、プログラムが処理するデータの特徴に依存した最適化を行うプログラム最適化装置は、最適化対象となる入力プログラム（１１１）を中間コード（１３１）に変換する中間コード変換部（１２１）と、入力プログラム（１１１）中の変数の取り得る値を、外部から与えられた情報に基づいて設定する変数値設定部（１２２）と、変数値設定部（１２２）で設定された値に基づき、中間コード（１３１）に含まれるノードの取り得る値を算出するノード値算出部（１２３）と、ノード値算出部（１２３）で算出された値に基づき、中間コードの最適化を行う中間コード最適化部（１２４）と、中間コード最適化部（１２４）で最適化された中間コード（１３１）を出力プログラム（１１２）に変換する出力プログラム変換部（１２５）とを備える。
2009098739.tif 000002
【特許請求の範囲】
【請求項１】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、
前記入力プログラムを中間コードに変換する中間コード変換部と、
前記入力プログラムで使用される変数の取り得る値を、外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードに設定する変数値設定部と、
設定された前記変数の取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部と
を備えるプログラム最適化装置。
【請求項２】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項３】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項４】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項５】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換する
請求項１に記載のプログラム最適化装置。
【請求項６】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除する
請求項１に記載のプログラム最適化装置。
【請求項７】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換する
請求項１に記載のプログラム最適化装置。
【請求項８】
前記中間コード最適化部は、前記変数の取り得る値から、前記中間コードを木構造で表した際のノードの取り得る値を算出し、前記ノードの取り得る値に基づいて、前記中間コードを最適化する
請求項１に記載のプログラム最適化装置。
【請求項９】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、
前記入力プログラムを中間コードに変換する中間コード変換部と、
前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定する変数値設定部と、
前記ノードの取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部と
を備えるプログラム最適化装置。
【請求項１０】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換する
請求項９に記載のプログラム最適化装置。
【請求項１１】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除する
請求項９に記載のプログラム最適化装置。
【請求項１２】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換する
請求項９に記載のプログラム最適化装置。
【請求項１３】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１４】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１５】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１６】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化方法であって、
前記入力プログラムを中間コードに変換し、
前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定し、
前記ノードの取り得る値に基づいて、前記中間コードを最適化し、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する
プログラム最適化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムを最適化する最適化装置および最適化方法に関し、特に、実行時のデータの性質に基づき、コンピュータプログラムを最適化する最適化装置および最適化方法に関する。
【背景技術】
【０００２】
通常、プログラミング言語で記述されたソースプログラムをコンパイルする際に、ソースプログラムの動作を解析し、ソースプログラムの最適化処理を行う。【０００３】
例えば、一般的に知られている最適化方法として、定数の畳み込み、または不要コード削除等がある。これらの最適化方法では、コンパイル時に計算可能な演算を演算結果に置換したり、プログラム実行時に到達し得ないコード等をコンパイル後のプログラムから削除したりする。このような方法により、従来、プログラムの最適化を行っている。【０００４】
さらに、非特許文献１で開示されているように、ソースプログラムに対する解析範囲を拡大し、手続き間解析（interprocedural analysis）の解析結果に基づいて手続き間の定数伝播（interprocedural constant propagation）を行い、可能な限りコンパイル時に計算処理を行うことで、実行時の処理時間の改善を行う方法がある。【０００５】
また、特許文献１で開示されているように、プログラムを実行することにより変数の取り得る値の出現頻度を求め、変数が特定の値の場合に特殊化されたプログラムを生成し、変数が出現頻度の多い特定の値のときに実行時の処理時間の改善を行う方法がある。
【特許文献１】特開２００２−２５９１３５号公報
【非特許文献１】Paul R. Carini, M. Hind, "Flow-Sensitive Interprocedural Constant Propagation", The ACM SIGPLAN Conference on Programming Language Design and Implementation, 1995
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述のような最適化手法は、ソースプログラムの解析結果に基づく最適化である。このため、プログラムの実行により処理されるデータの特徴に依存した最適化が行えない。また、データの特徴に依存した最適化を行う場合でも、最適化の前にプログラムを実行する必要がある。【０００７】
本発明は上述の課題を解決するためになされたもので、最適化の前にプログラムの実行を必要とせず、プログラムの実行により処理されるデータの特徴に依存した最適化を可能とするプログラム最適化装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明にかかるプログラム最適化装置は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、前記入力プログラムを中間コードに変換する中間コード変換部と、前記入力プログラムで使用される変数の取り得る値を、外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードに設定する変数値設定部と、設定された前記変数の取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部とを備える。【０００９】
この構成によると、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行うことができる。このように、プログラムの実行により処理されるデータの特徴を、変数の取り得る値として設定することにより、プログラムの実行により処理されるデータの特徴に依存した最適化を行うことができる。【００１０】
具体的には、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードに設定する。【００１１】
また、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードに設定してもよい。【００１２】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードに設定してもよい。【００１３】
また、前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換してもよい。【００１４】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除してもよい。【００１５】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。【００１６】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換してもよい。【００１７】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。【００１８】
また、前記中間コード最適化部は、前記変数の取り得る値から、前記中間コードを木構造で表した際のノードの取り得る値を算出し、前記ノードの取り得る値に基づいて、前記中間コードを最適化してもよい。【００１９】
本発明にかかるプログラム最適化装置は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、前記入力プログラムを中間コードに変換する中間コード変換部と、前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定する変数値設定部と、前記ノードの取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部とを備えるものであってもよい。【００２０】
この構成によると、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行うことができる。このように、プログラムの実行により処理されるデータの特徴を、変数の取り得る値として設定することにより、プログラムの実行により処理されるデータの特徴に依存した最適化を行うことができる。【００２１】
また、前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換するものであってもよい。【００２２】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除するものであってもよい。【００２３】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。【００２４】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換するものであってもよい。【００２５】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。【００２６】
また、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。【００２７】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。【００２８】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。【００２９】
本発明にかかるプログラム最適化方法は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化方法であって、前記入力プログラムを中間コードに変換し、前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定し、前記ノードの取り得る値に基づいて、前記中間コードを最適化し、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する。【００３０】
なお、本発明は、このような特徴的な処理部を備えるプログラム最適化装置、または特徴的なステップを含むプログラム最適化方法として実現できるだけでなく、プログラム最適化方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００３１】
本発明によると、プログラムの実行により処理されるデータの特徴に依存した最適化を行い、かつ、最適化の前のプログラムの実行を必要としないプログラム最適化装置を提供することができる。【００３２】
また、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。【００３３】
さらに、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明の実施の形態に係るプログラム最適化装置を示す図である。
【図２】図２は、本発明のプログラム最適化装置が実行する処理のフローチャートである。
【図３】図３は、入力プログラムの一例を示す図である。
【図４】図４は、中間コードの一例を示す図である。
【図５】図５は、図４に示す中間コードと、当該中間コードに含まれる各ノードが取り得る値とを示す図である。
【図６】図６は、データの連鎖情報の一例を示す図である。
【図７】図７は、ノード値算出部の算出結果である定数の集合を示す図である。
【図８】図８は、中間コード最適化部の第１の変換の一例を説明するための図である。
【図９】図９は、中間コード最適化部の第３の変換の一例を説明するための図である。
【図１０】図１０は、本発明により図３に示した入力プログラムから変換した出力プログラムを示す図である。
【図１１】図１１は、従来技術により図３に示した入力プログラムから変換した出力プログラムを示す図である。
【図１２】図１２は、プログラム最適化装置の変形例を示す図である。
【図１３】図１３は、入力プログラムの一例を示す図である。
【図１４】図１４は、指定ファイルの一例を示す図である。
【図１５】図１５は、プログラム最適化装置の変形例を示す図である。
【図１６】図１６は、ＧＵＩの一例を示す図である。
【図１７】図１７は、ＧＵＩの一例を示す図である。
【符号の説明】
【００３５】
１０１、１０１ａ、１０１ｂ  プログラム最適化装置
１１１  入力プログラム
１１２  出力プログラム
１１３  指定ファイル
１１４  表示端末
１２１  中間コード変換部
１２２、１２２ａ、１２２ｂ  変数値設定部
１２３  ノード値算出部
１２４  中間コード最適化部
１２５  出力プログラム変換部
１３１  中間コード
【発明を実施するための最良の形態】
【００３６】
以下、本発明の実施の形態に係るプログラム最適化装置について図面を参照しながら説明する。【００３７】
まず、プログラム最適化装置の構成について図１を参照して説明する。【００３８】
プログラム最適化装置１０１は、最適化対象のプログラムを記述した入力プログラム１１１を、最適化を施したプログラムである出力プログラム１１２に変換する装置であり、中間コード変換部１２１と、変数値設定部１２２と、ノード値算出部１２３と、中間コード最適化部１２４と、出力プログラム変換部１２５とを含む。プログラム最適化装置１０１は、プロセッサとメモリとを備える通常のコンピュータ上で、各処理部を実現するためのプログラムを実行することにより実現される。なお、プログラム最適化装置１０１の処理で用いられる、プログラム、コード、データ等は、コンピュータのメモリ等に一時的に記憶される。【００３９】
中間コード変換部１２１は、入力プログラム１１１を中間コード１３１に変換する。【００４０】
入力プログラム１１１は、例えば、Ｃ言語といった既存のプログラミング言語で記述されている。中間コード１３１は、例えば、抽象構文木といった、既存のプログラムの表現形式で、入力プログラム１１１の内容を表現している。【００４１】
変数値設定部１２２は、入力プログラム１１１に記述されている変数に対して、変数の取り得る値を定数の集合として、中間コード１３１に設定する。変数の取り得る値は、入力プログラム１１１に、例えばｐｒａｇｍａのような指示子を記述することにより指定することができる。また、入力プログラムとは別のファイルに変数の取り得る値を示す情報を記述することにより指定することもできる。さらに、ＧＵＩ（Graphical User Interface）を用いたユーザ入力により入力プログラムに対して指定することもできる。なお、ユーザ入力は必ずしもＧＵＩを用いる必要はなく、他のインタフェースを用いてユーザ入力を受け付けるようにしても良い。【００４２】
ノード値算出部１２３は、変数値設定部１２２によって設定された変数に対する定数の集合に基づいて、中間コード１３１を木構造で表した際の各ノードが取り得る値を算出する。【００４３】
中間コード最適化部１２４は、ノード値算出部１２３によって算出された中間コード１３１の各ノードが取り得る値に基づいて、以下の３つの変換方法のいずれかの方法に従い、中間コードの変換を行う。【００４４】
第１の変換方法は、ノードが取り得る値が１つである場合に、当該ノードをノードが取り得る値を表現する定数ノードに置換する方法である。【００４５】
第２の変換方法は、ノードが条件分岐を表現するノードである場合に、ノードが取り得る値に含まれない値による条件分岐を、中間コードより削除する方法である。【００４６】
第３の変換方法は、定数の集合の要素数分の分岐を生成し、各分岐において第１の変換と同様に、ノードを定数ノードに置換する方法である。【００４７】
出力プログラム変換部１２５は、最適化された中間コード１３１を所定の書式で記述された出力プログラム１１２に変換する。【００４８】
出力プログラム１１２の書式は、例えば、プログラム最適化装置１０１を、Ｃコンパイラとして利用する場合は、Ｃ言語、アセンブリ言語、機械語等であり、高位合成ツールとして利用する場合は、Ｖｅｒｉｌｏｇ言語等である。【００４９】
次に、プログラム最適化装置１０１が実行する処理について説明する。【００５０】
図２は、プログラム最適化装置が実行する処理のフローチャートである。【００５１】
中間コード変換部１２１は、入力プログラム１１１を中間コード１３１に変換する（Ｓ２１１）。図３は、入力プログラムの一例を示す図である。図４は、中間コード１３１の一例を示す図である。同図は、図３に示す入力プログラム３０１の１３行目の文Ｓ５を変換した結果得られる中間コードを示す。この中間コードは、変数の参照を示すノードＳ５＿ａおよびＳ５＿ｒと、定数を示すノードＳ５＿１と、演算を示すノードＳ５＿ａｄｄとを含む木構造で表現されている。【００５２】
次に、変数値設定部１２２は、変数の参照を示すノード（変数の参照ノード）に対し、変数の取り得る値を示す定数の集合を設定する（Ｓ２１２）。図３に示す入力プログラム３０１の３行目および４行目のｐｒａｇｍａ記述は、それぞれ、変数ａの取り得る値が｛０，１｝、変数ｃの取り得る値が｛０，２，４｝であることを指定する記述である。この場合、変数値設定部１２２は、入力プログラム１１１のｐｒａｇｍａ記述から変数の取り得る値を取得し、変数ａを参照するノードに対し、定数の集合｛０，１｝を設定する。変数ｃを参照するノードに対しても同様に、定数の集合｛０，２，４｝を設定する。【００５３】
次に、ノード値算出部１２３は、中間コード１３１に含まれる各ノードに対し、ノードが取り得る値を示す定数の集合を算出する（Ｓ２１３）。例えば、図４に示す中間コードについて検討する。図５は、図４に示す中間コードと、当該中間コードに含まれる各ノードが取り得る値とを示す図である。同図に示すように、変数ａの参照を示すノードＳ５＿ａには、図３に示す入力プログラム３０１の３行目のｐｒａｇｍａ記述の通り、定数の集合｛０，１｝が設定済みである。また、定数ノードＳ５＿１は、取り得る値が“１”のみである。このため、ノード値算出部１２３は、定数ノードＳ５＿１が取り得る値として、定数の集合｛１｝を算出する。加算ノードＳ５＿ａｄｄでは、オペランドであるノードＳ５＿ａの値とノードＳ５＿１の値との加算が行われる。このため、ノード値算出部１２３は、ノードＳ５＿ａの取り得る値を示す定数の集合｛０，１｝と、ノードＳ５＿１の取り得る値を示す定数の集合｛１｝とから、加算ノードＳ５＿ａｄｄの取り得る値を示す定数の集合として｛１，２｝を算出する。さらに、ノード値算出部１２３は、変数ｒの参照を示すノードＳ５＿ｒについても、加算ノードＳ５＿ａｄｄの取り得る値を示す定数の集合と同じ定数の集合｛１，２｝を算出する。【００５４】
また、ノード値算出部１２３は、一般的な最適化方法である定数伝播と同様に、データの連鎖情報を元に定数の集合を伝播させる。例えば、図３に示す入力プログラム３０１の１０〜１４行目で定義された変数ｒが、１７行目の文で使用されている。この場合、１０〜１４行目に対応する文ノードＳ２〜Ｓ６と１７行目に対応する文ノードＳ７とのデータの連鎖情報は、図６に示すように連鎖元から連鎖先を示すグラフとして表現できる。つまり、変数ｒの定義を行う文ノードＳ２〜Ｓ６が連鎖元を示し、変数ｒを参照する文ノードＳ７が連鎖先として表現される。ノード値算出部１２３は、データの連鎖情報を元に、文ノードＳ２〜Ｓ６の定数の集合に基づいて文ノードＳ７の定数の集合の算出を行う。つまり、ノード値算出部１２３は、データの連鎖情報を元に、連鎖先の定数の集合を、連鎖元の定数の集合の和集合として算出する。結果として、文ノードＳ７における変数ｒの参照ノードＳ７＿ｒの定数の集合が算出される。【００５５】
同様に、全てのノードに対して、ノードの取り得る値を示す定数の集合が算出されることにより、図７に示すようにノード毎に定数の集合が算出される。図７は、中間コード１３１に含まれるノードに設定されている定数の集合の一部を示す図である。ノードに設定された定数の集合は、中間コード１３１に含まれる各ノードが取り得る値を示す集合である。定数の集合が算出できなかったノードには、空集合φが設定され、この場合は任意の値を取り得ることを示している。【００５６】
次に、中間コード最適化部１２４は、算出されたノードの定数の集合を使用した中間コード１３１の変換を行う（Ｓ２１４）。中間コード１３１の変換方法には以下の３つの変換方法がある。【００５７】
第１の変換は、ノードの定数の集合の要素数が１つの場合に、当該ノードを、当該集合の要素を表現する定数ノードに置換する変換である。図８（ａ）は、入力プログラム３０１の文ノードＳ９における変換前の中間コードを示す図である。図８（ｂ）は、文ノードＳ９における変換後の中間コードを示す図である。ノード値算出部１２３によって算出された変数ｎの参照ノードＳ９＿ｎにおける定数の集合は、図７に示す通り｛１｝であり、要素数が１つである。このため、中間コード最適化部１２４は、変数ｎの参照ノードＳ９＿ｎを、その要素である数値“１”を表現する定数ノードＳ９＿１に置換する。この置換の結果、文ノードＳ８は不要コードとなる。このため、中間コード最適化部１２４は、一般的な最適化方法である不要コード削除の最適化により、文ノードＳ８を削除する。これにより、プログラムサイズを小さくすることが可能となる。【００５８】
第２の変換は、ノードが有する定数の集合に含まれない値に依存する分岐を、中間コードより削除する変換である。入力プログラム３０１の分岐文ノードＳ１における分岐条件を示すノードＳ１＿ｓが有する定数の集合は、図７が示す通り｛１，３，５｝である。文ノードＳ２が示す分岐“ｃａｓｅ０”は、ノードＳ１＿ｓの値が“０”の場合の条件分岐である。図７で示されるノード値算出結果において、ノードＳ１＿ｓは要素“０”を含まない。このため、プログラム実行時に文Ｓ２は実行されない。よって、中間コード最適化部１２４は、文ノードＳ２が示す分岐“ｃａｓｅ０”を削除する。同様に、中間コード最適化部１２４は、文ノードＳ４が示す分岐“ｃａｓｅ２”も削除する。これにより、分岐は、出力プログラム４０１に示されるように文ノードＳ３，Ｓ５，Ｓ６のみの分岐に削減される。この置換の結果、プログラムサイズが小さくなることは自明である。【００５９】
第３の変換は、定数の集合の要素数分の分岐を生成し、各分岐において第１の変換と同様に、ノードを定数ノードに置換する変換である。図９（ａ）は、図３に示す入力プログラム３０１の文ノードＳ７における変換前の中間コードを示す図である。図９（ｂ）は、文ノードＳ７における変換後の中間コードを示す図である。文ノードＳ７において、変数ｒの参照ノードＳ７＿ｒの定数の集合は｛０，１，２｝である。このため、中間コード最適化部１２４は、図９（ｂ）に示すように０，１，２にそれぞれに対応する分岐を生成する。中間コード最適化部１２４は、各分岐において、変数ｒの参照ノードＳ７＿ｒを定数ノードに置換することにより、中間コードを変換する。分岐は、文ノードＳ７２，Ｓ７４，Ｓ７６で示される。文ノードＳ７２，Ｓ７４，Ｓ７６は、文ノードＳ７を複製し、変数ｒの参照ノードＳ７＿ｒに該当するノードを、定数０，１，２をそれぞれ示す定数ノードＳ７２＿０，Ｓ７４＿１，Ｓ７６＿２に置換することで生成される。この変換の結果、従来技術の最適化方法である定数の畳み込み（constant folding）、あるいは、演算強度の削減といった最適化が可能になる。最終的に、文ノードＳ７に含まれる乗算が別の演算に変換され、図１０に示す出力プログラム４０１における文ノードＳ７２’，Ｓ７４’，Ｓ７６’に最適化される。プログラムの実行時にシフト演算が乗算より高速に実行できる場合には、この第３の変換により、プログラムの実行時間を改善することができる。また、出力プログラムを用いてハードウェアを生成するような場合においては、乗算器自体が不要となる。このため、ハードウェアの規模を小さくすることが可能になる。【００６０】
第３の変換においては、要素数分の分岐が新たに生成される。このため、第３の変換の実施を制限してもよい。例えば、変換により定数の畳み込みが可能になる要素についてのみ第３の変換を実施するようにしてもよい。また、変換により演算強度の削減が可能になる乗算や除算等の演算を含む場合に限定して第３の変換を実施するようにしてもよい。【００６１】
次に、プログラム最適化装置１０１は、中間コードの変換を実施したか否かを判定し（Ｓ２１５）、中間コードの変換を実施した場合は（Ｓ２１５でＹＥＳ）、再度、ノード値算出処理（Ｓ２１３）以降の処理を実行することにより、さらなる最適化を試みる。【００６２】
中間コードの変換が実施されなかった場合には（Ｓ２１５でＮＯ）、出力プログラム変換部１２５は、中間コード最適化部１２４によって最適化された中間コード１３１から、所定の書式で記述された出力プログラム１１２を生成する（Ｓ２１６）。【００６３】
図１０は、入力プログラム３０１に対してプログラム最適化装置１０１により最適化された出力プログラムを示している。図１１は、入力プログラム３０１に対して従来技術により最適化された出力プログラムの一例を示している。図１１では、変数が特定の値を取る場合に特化した最適化を行っている。図１０および図１１より、プログラム最適化装置１０１により生成された出力プログラムは、従来技術により生成された出力プログラムと比べて、プログラムサイズが小さいことは明らかである。【００６４】
以上説明したように、本発明の実施の形態によれば、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行っている。このため、最適化の前にプログラムを実行することなく、プログラムの実行により処理されるデータの特徴に依存した最適化を可能としている。さらに、変数の取り得ない値の情報を利用した最適化を行うことで、不要なコードの削減が可能となる。このため、従来技術による最適化よりもプログラムサイズの小さいコードを生成することが可能となる。【００６５】
また、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。【００６６】
さらに、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。【００６７】
以上、本発明の実施の形態に係るプログラム最適化装置１０１について説明したが、本発明は、この実施の形態に限定されるものではない。【００６８】
例えば、上述の実施の形態では、入力プログラム１１１がＣ言語で記述され、変数の取り得る値をｐｒａｇｍａにより指定する方法について説明した。しかし、ｐｒａｇｍａで指定する情報と同じ情報を入力プログラムとは別のファイルに記述することにより、変数の取り得る値を指定してもよい。【００６９】
図１２〜図１４を用いて、入力プログラムとは別の指定ファイルを用いて変数の取り得る値を指定する方法について説明する。【００７０】
図１２は、この方法に係るプログラム最適化装置の構成を示す図である。プログラム最適化装置１０１ａは、図１に示したプログラム最適化装置１０１の構成において、変数値設定部１２２を変数値設定部１２２ａに変更したものである。それ以外の構成は、プログラム最適化装置１０１と同様である。変数値設定部１２２ａは、変数の取り得る値を指定ファイル１１３から取得し、変数の取り得る値を定数の集合として、中間コード１３１に設定する。【００７１】
図１３は、入力プログラムの一例を示す図である。図１４は、指定ファイルの一例を示す図である。例えば、入力プログラム１１０１に記述されている変数ａおよびｃに対して、変数の取り得る値を指定する場合、指定ファイル１１０２に変数ａおよびｃを特定する情報と、変数ａおよびｃが取り得る値とを記述することにより、ｐｒａｇｍａ記述と同様に、変数ａおよびｃの取り得る値を指定することができる。【００７２】
なお、ｐｒａｇｍａまたは指定ファイルを用いて変数の取り得る値を指定する以外にも、ＧＵＩを用いて、入力プログラムを画面に表示し、ユーザがポインタで指定した変数に対して、当該変数の取り得る値を入力するようにしてもよい。【００７３】
図１５〜図１７を用いて、ＧＵＩを用いて変数の取り得る値を指定する方法について説明する。【００７４】
図１５は、この方法に係るプログラム最適化装置の構成を示す図である。プログラム最適化装置１０１ｂは、図１に示したプログラム最適化装置１０１の構成において、変数値設定部１２２を変数値設定部１２２ｂに変更したものである。それ以外の構成は、プログラム最適化装置１０１と同様である。変数値設定部１２２ｂは、入力プログラム１１１を表示端末１１４に表示させ、ユーザによる入力により変数の取り得る値を取得し、変数の取り得る値を変数の集合として、中間コード１３１に設定する。【００７５】
図１６は、表示端末１１４に表示される、入力プログラムを含む入力プログラム表示ウィンドウの一例を示す図である。図１７は、変数属性ダイアログの一例を示す図である。例えば、入力プログラム表示ウィンドウ１２０１に表示されている入力プログラムに記述されている変数ａに対して、変数の取り得る値を指定する場合を考える。ユーザは、入力プログラム表示ウィンドウ１２０１上で、変数ａをポインタにより選択する。次に、ユーザは、プルダウンメニューから変数属性ダイアログ１２０２を開くためのメニューを選択することにより、変数属性ダイアログ１２０２を表示端末１１４上に表示させる。ユーザは、変数属性ダイアログ１２０２において、変数ａの取り得る値として“０，１”を入力する。同様に変数ｃに対しても取り得る値を入力することで、ｐｒａｇｍａ記述と同様に、変数ａおよびｃの取り得る値を指定することができる。【００７６】
なお、ＧＵＩを用いずとも、例えば、ＣＵＩ（Character User Interface）を用いて、ユーザが変数の取り得る値を入力するような構成であってもよい。【００７７】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される
【産業上の利用可能性】
【００７８】
本発明にかかるプログラム最適化装置は、プログラムのソースコードからオブジェクトコードを生成するコンパイラや、逐次処理プログラムからハードウェアのＲＴＬ（Register Transfer Level）記述を生成する高位合成ツールに適用でき、特に、プログラムの処理するデータに依存した最適化を施したオブジェクトコードやＲＴＬ記述を生成する場合に有用である。
【図１】
2009098739.tif 000003
【図２】
2009098739.tif 000004
【図３】
2009098739.tif 000005
【図４】
2009098739.tif 000006
【図５】
2009098739.tif 000007
【図６】
2009098739.tif 000008
【図７】
2009098739.tif 000009
【図８】
2009098739.tif 000010
【図９】
2009098739.tif 000011
【図１０】
2009098739.tif 000012
【図１１】
2009098739.tif 000013
【図１２】
2009098739.tif 000014
【図１３】
2009098739.tif 000015
【図１４】
2009098739.tif 000016
【図１５】
2009098739.tif 000017
【図１６】
2009098739.tif 000018
【図１７】
2009098739.tif 000019
【手続補正書】
【提出日】平成21年8月19日(2009.8.19)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムを最適化する最適化装置および最適化方法に関し、特に、実行時のデータの性質に基づき、コンピュータプログラムを最適化する最適化装置および最適化方法に関する。
【背景技術】
【０００２】
通常、プログラミング言語で記述されたソースプログラムをコンパイルする際に、ソースプログラムの動作を解析し、ソースプログラムの最適化処理を行う。
【０００３】
例えば、一般的に知られている最適化方法として、定数の畳み込み、または不要コード削除等がある。これらの最適化方法では、コンパイル時に計算可能な演算を演算結果に置換したり、プログラム実行時に到達し得ないコード等をコンパイル後のプログラムから削除したりする。このような方法により、従来、プログラムの最適化を行っている。
【０００４】
さらに、非特許文献１で開示されているように、ソースプログラムに対する解析範囲を拡大し、手続き間解析（interprocedural analysis）の解析結果に基づいて手続き間の定数伝播（interprocedural constant propagation）を行い、可能な限りコンパイル時に計算処理を行うことで、実行時の処理時間の改善を行う方法がある。
【０００５】
また、特許文献１で開示されているように、プログラムを実行することにより変数の取り得る値の出現頻度を求め、変数が特定の値の場合に特殊化されたプログラムを生成し、変数が出現頻度の多い特定の値のときに実行時の処理時間の改善を行う方法がある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００２−２５９１３５号公報
【非特許文献】
【０００７】
【非特許文献１】Paul R. Carini, M. Hind, “Flow-Sensitive Interprocedural Constant Propagation”, The ACM SIGPLAN Conference on Programming Language Design and Implementation, 1995
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述のような最適化手法は、ソースプログラムの解析結果に基づく最適化である。このため、プログラムの実行により処理されるデータの特徴に依存した最適化が行えない。また、データの特徴に依存した最適化を行う場合でも、最適化の前にプログラムを実行する必要がある。
【０００９】
本発明は上述の課題を解決するためになされたもので、最適化の前にプログラムの実行を必要とせず、プログラムの実行により処理されるデータの特徴に依存した最適化を可能とするプログラム最適化装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明にかかるプログラム最適化装置は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、前記入力プログラムを中間コードに変換する中間コード変換部と、前記入力プログラムで使用される変数の取り得る値を、外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードに設定する変数値設定部と、設定された前記変数の取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部とを備える。
【００１１】
この構成によると、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行うことができる。このように、プログラムの実行により処理されるデータの特徴を、変数の取り得る値として設定することにより、プログラムの実行により処理されるデータの特徴に依存した最適化を行うことができる。
【００１２】
具体的には、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードに設定する。
【００１３】
また、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードに設定してもよい。
【００１４】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードに設定してもよい。
【００１５】
また、前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換してもよい。
【００１６】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除してもよい。
【００１７】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。
【００１８】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換してもよい。
【００１９】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。
【００２０】
また、前記中間コード最適化部は、前記変数の取り得る値から、前記中間コードを木構造で表した際のノードの取り得る値を算出し、前記ノードの取り得る値に基づいて、前記中間コードを最適化してもよい。
【００２１】
本発明にかかるプログラム最適化装置は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、前記入力プログラムを中間コードに変換する中間コード変換部と、前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定する変数値設定部と、前記ノードの取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部とを備えるものであってもよい。
【００２２】
この構成によると、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行うことができる。このように、プログラムの実行により処理されるデータの特徴を、変数の取り得る値として設定することにより、プログラムの実行により処理されるデータの特徴に依存した最適化を行うことができる。
【００２３】
また、前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換するものであってもよい。
【００２４】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除するものであってもよい。
【００２５】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。
【００２６】
さらに、前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換するものであってもよい。
【００２７】
入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。
【００２８】
また、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。
【００２９】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。
【００３０】
さらに、前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定するものであってもよい。
【００３１】
本発明にかかるプログラム最適化方法は、プログラミング言語で記述された入力プログラムを最適化するプログラム最適化方法であって、前記入力プログラムを中間コードに変換し、前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定し、前記ノードの取り得る値に基づいて、前記中間コードを最適化し、前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する。
【００３２】
なお、本発明は、このような特徴的な処理部を備えるプログラム最適化装置、または特徴的なステップを含むプログラム最適化方法として実現できるだけでなく、プログラム最適化方法に含まれる特徴的なステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００３３】
本発明によると、プログラムの実行により処理されるデータの特徴に依存した最適化を行い、かつ、最適化の前のプログラムの実行を必要としないプログラム最適化装置を提供することができる。
【００３４】
また、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。
【００３５】
さらに、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。
【図面の簡単な説明】
【００３６】
【図１】図１は、本発明の実施の形態に係るプログラム最適化装置を示す図である。
【図２】図２は、本発明のプログラム最適化装置が実行する処理のフローチャートである。
【図３】図３は、入力プログラムの一例を示す図である。
【図４】図４は、中間コードの一例を示す図である。
【図５】図５は、図４に示す中間コードと、当該中間コードに含まれる各ノードが取り得る値とを示す図である。
【図６】図６は、データの連鎖情報の一例を示す図である。
【図７】図７は、ノード値算出部の算出結果である定数の集合を示す図である。
【図８】図８は、中間コード最適化部の第１の変換の一例を説明するための図である。
【図９】図９は、中間コード最適化部の第３の変換の一例を説明するための図である。
【図１０】図１０は、本発明により図３に示した入力プログラムから変換した出力プログラムを示す図である。
【図１１】図１１は、従来技術により図３に示した入力プログラムから変換した出力プログラムを示す図である。
【図１２】図１２は、プログラム最適化装置の変形例を示す図である。
【図１３】図１３は、入力プログラムの一例を示す図である。
【図１４】図１４は、指定ファイルの一例を示す図である。
【図１５】図１５は、プログラム最適化装置の変形例を示す図である。
【図１６】図１６は、ＧＵＩの一例を示す図である。
【図１７】図１７は、ＧＵＩの一例を示す図である。
【発明を実施するための形態】
【００３７】
以下、本発明の実施の形態に係るプログラム最適化装置について図面を参照しながら説明する。
【００３８】
まず、プログラム最適化装置の構成について図１を参照して説明する。
【００３９】
プログラム最適化装置１０１は、最適化対象のプログラムを記述した入力プログラム１１１を、最適化を施したプログラムである出力プログラム１１２に変換する装置であり、中間コード変換部１２１と、変数値設定部１２２と、ノード値算出部１２３と、中間コード最適化部１２４と、出力プログラム変換部１２５とを含む。プログラム最適化装置１０１は、プロセッサとメモリとを備える通常のコンピュータ上で、各処理部を実現するためのプログラムを実行することにより実現される。なお、プログラム最適化装置１０１の処理で用いられる、プログラム、コード、データ等は、コンピュータのメモリ等に一時的に記憶される。
【００４０】
中間コード変換部１２１は、入力プログラム１１１を中間コード１３１に変換する。
【００４１】
入力プログラム１１１は、例えば、Ｃ言語といった既存のプログラミング言語で記述されている。中間コード１３１は、例えば、抽象構文木といった、既存のプログラムの表現形式で、入力プログラム１１１の内容を表現している。
【００４２】
変数値設定部１２２は、入力プログラム１１１に記述されている変数に対して、変数の取り得る値を定数の集合として、中間コード１３１に設定する。変数の取り得る値は、入力プログラム１１１に、例えばｐｒａｇｍａのような指示子を記述することにより指定することができる。また、入力プログラムとは別のファイルに変数の取り得る値を示す情報を記述することにより指定することもできる。さらに、ＧＵＩ（Graphical User Interface）を用いたユーザ入力により入力プログラムに対して指定することもできる。なお、ユーザ入力は必ずしもＧＵＩを用いる必要はなく、他のインタフェースを用いてユーザ入力を受け付けるようにしても良い。
【００４３】
ノード値算出部１２３は、変数値設定部１２２によって設定された変数に対する定数の集合に基づいて、中間コード１３１を木構造で表した際の各ノードが取り得る値を算出する。
【００４４】
中間コード最適化部１２４は、ノード値算出部１２３によって算出された中間コード１３１の各ノードが取り得る値に基づいて、以下の３つの変換方法のいずれかの方法に従い、中間コードの変換を行う。
【００４５】
第１の変換方法は、ノードが取り得る値が１つである場合に、当該ノードをノードが取り得る値を表現する定数ノードに置換する方法である。
【００４６】
第２の変換方法は、ノードが条件分岐を表現するノードである場合に、ノードが取り得る値に含まれない値による条件分岐を、中間コードより削除する方法である。
【００４７】
第３の変換方法は、定数の集合の要素数分の分岐を生成し、各分岐において第１の変換と同様に、ノードを定数ノードに置換する方法である。
【００４８】
出力プログラム変換部１２５は、最適化された中間コード１３１を所定の書式で記述された出力プログラム１１２に変換する。
【００４９】
出力プログラム１１２の書式は、例えば、プログラム最適化装置１０１を、Ｃコンパイラとして利用する場合は、Ｃ言語、アセンブリ言語、機械語等であり、高位合成ツールとして利用する場合は、Ｖｅｒｉｌｏｇ言語等である。
【００５０】
次に、プログラム最適化装置１０１が実行する処理について説明する。
【００５１】
図２は、プログラム最適化装置が実行する処理のフローチャートである。
【００５２】
中間コード変換部１２１は、入力プログラム１１１を中間コード１３１に変換する（Ｓ２１１）。図３は、入力プログラムの一例を示す図である。図４は、中間コード１３１の一例を示す図である。同図は、図３に示す入力プログラム３０１の１３行目の文Ｓ５を変換した結果得られる中間コードを示す。この中間コードは、変数の参照を示すノードＳ５＿ａおよびＳ５＿ｒと、定数を示す定数ノードＳ５＿１と、演算を示す加算ノードＳ５＿ａｄｄとを含む木構造で表現されている。
【００５３】
次に、変数値設定部１２２は、変数の参照を示すノード（変数の参照ノード）に対し、変数の取り得る値を示す定数の集合を設定する（Ｓ２１２）。図３に示す入力プログラム３０１の３行目および４行目のｐｒａｇｍａ記述は、それぞれ、変数ａの取り得る値が｛０，１｝、変数ｃの取り得る値が｛０，２，４｝であることを指定する記述である。この場合、変数値設定部１２２は、入力プログラム１１１のｐｒａｇｍａ記述から変数の取り得る値を取得し、変数ａを参照するノードに対し、定数の集合｛０，１｝を設定する。変数ｃを参照するノードに対しても同様に、定数の集合｛０，２，４｝を設定する。
【００５４】
次に、ノード値算出部１２３は、中間コード１３１に含まれる各ノードに対し、ノードが取り得る値を示す定数の集合を算出する（Ｓ２１３）。例えば、図４に示す中間コードについて検討する。図５は、図４に示す中間コードと、当該中間コードに含まれる各ノードが取り得る値とを示す図である。同図に示すように、変数ａの参照を示すノードＳ５＿ａには、図３に示す入力プログラム３０１の３行目のｐｒａｇｍａ記述の通り、定数の集合｛０，１｝が設定済みである。また、定数ノードＳ５＿１は、取り得る値が“１”のみである。このため、ノード値算出部１２３は、定数ノードＳ５＿１が取り得る値として、定数の集合｛１｝を算出する。加算ノードＳ５＿ａｄｄでは、オペランドであるノードＳ５＿ａの値と定数ノードＳ５＿１の値との加算が行われる。このため、ノード値算出部１２３は、ノードＳ５＿ａの取り得る値を示す定数の集合｛０，１｝と、定数ノードＳ５＿１の取り得る値を示す定数の集合｛１｝とから、加算ノードＳ５＿ａｄｄの取り得る値を示す定数の集合として｛１，２｝を算出する。さらに、ノード値算出部１２３は、変数ｒの参照を示すノードＳ５＿ｒについても、加算ノードＳ５＿ａｄｄの取り得る値を示す定数の集合と同じ定数の集合｛１，２｝を算出する。
【００５５】
また、ノード値算出部１２３は、一般的な最適化方法である定数伝播と同様に、データの連鎖情報を元に定数の集合を伝播させる。例えば、図３に示す入力プログラム３０１の１０〜１４行目で定義された変数ｒが、１７行目の文で使用されている。この場合、１０〜１４行目に対応する文ノードＳ２〜Ｓ６と１７行目に対応する文ノードＳ７とのデータの連鎖情報は、図６に示すように連鎖元から連鎖先を示すグラフとして表現できる。つまり、変数ｒの定義を行う文ノードＳ２〜Ｓ６が連鎖元を示し、変数ｒを参照する文ノードＳ７が連鎖先として表現される。ノード値算出部１２３は、データの連鎖情報を元に、文ノードＳ２〜Ｓ６の定数の集合に基づいて文ノードＳ７の定数の集合の算出を行う。つまり、ノード値算出部１２３は、データの連鎖情報を元に、連鎖先の定数の集合を、連鎖元の定数の集合の和集合として算出する。結果として、文ノードＳ７における変数ｒの参照ノードＳ７＿ｒの定数の集合が算出される。
【００５６】
同様に、全てのノードに対して、ノードの取り得る値を示す定数の集合が算出されることにより、図７に示すようにノード毎に定数の集合が算出される。図７は、中間コード１３１に含まれるノードに設定されている定数の集合の一部を示す図である。ノードに設定された定数の集合は、中間コード１３１に含まれる各ノードが取り得る値を示す集合である。定数の集合が算出できなかったノードには、空集合φが設定され、この場合は任意の値を取り得ることを示している。
【００５７】
次に、中間コード最適化部１２４は、算出されたノードの定数の集合を使用した中間コード１３１の変換を行う（Ｓ２１４）。中間コード１３１の変換方法には以下の３つの変換方法がある。
【００５８】
第１の変換は、ノードの定数の集合の要素数が１つの場合に、当該ノードを、当該集合の要素を表現する定数ノードに置換する変換である。図８（ａ）は、入力プログラム３０１の文ノードＳ９における変換前の中間コードを示す図である。図８（ｂ）は、文ノードＳ９における変換後の中間コードを示す図である。ノード値算出部１２３によって算出された変数ｎの参照ノードＳ９＿ｎにおける定数の集合は、図７に示す通り｛１｝であり、要素数が１つである。このため、中間コード最適化部１２４は、変数ｎの参照ノードＳ９＿ｎを、その要素である数値“１”を表現する定数ノードＳ９＿１に置換する。この置換の結果、文ノードＳ８は不要コードとなる。このため、中間コード最適化部１２４は、一般的な最適化方法である不要コード削除の最適化により、文ノードＳ８を削除する。これにより、プログラムサイズを小さくすることが可能となる。
【００５９】
第２の変換は、ノードが有する定数の集合に含まれない値に依存する分岐を、中間コードより削除する変換である。入力プログラム３０１の分岐文ノードＳ１における分岐条件を示すノードＳ１＿ｓが有する定数の集合は、図７が示す通り｛１，３，５｝である。文ノードＳ２が示す分岐“ｃａｓｅ０”は、ノードＳ１＿ｓの値が“０”の場合の条件分岐である。図７で示されるノード値算出結果において、ノードＳ１＿ｓは要素“０”を含まない。このため、プログラム実行時に文Ｓ２は実行されない。よって、中間コード最適化部１２４は、文ノードＳ２が示す分岐“ｃａｓｅ０”を削除する。同様に、中間コード最適化部１２４は、文ノードＳ４が示す分岐“ｃａｓｅ２”も削除する。これにより、分岐は、出力プログラム４０１に示されるように文ノードＳ３，Ｓ５，Ｓ６のみの分岐に削減される。この置換の結果、プログラムサイズが小さくなることは自明である。
【００６０】
第３の変換は、定数の集合の要素数分の分岐を生成し、各分岐において第１の変換と同様に、ノードを定数ノードに置換する変換である。図９（ａ）は、図３に示す入力プログラム３０１の文ノードＳ７における変換前の中間コードを示す図である。図９（ｂ）は、文ノードＳ７における変換後の中間コードを示す図である。文ノードＳ７において、変数ｒの参照ノードＳ７＿ｒの定数の集合は｛０，１，２｝である。このため、中間コード最適化部１２４は、図９（ｂ）に示すように０，１，２にそれぞれに対応する分岐を生成する。中間コード最適化部１２４は、各分岐において、変数ｒの参照ノードＳ７＿ｒを定数ノードに置換することにより、中間コードを変換する。分岐は、文ノードＳ７２，Ｓ７４，Ｓ７６で示される。文ノードＳ７２，Ｓ７４，Ｓ７６は、文ノードＳ７を複製し、変数ｒの参照ノードＳ７＿ｒに該当するノードを、定数０，１，２をそれぞれ示す定数ノードＳ７２＿０，Ｓ７４＿１，Ｓ７６＿２に置換することで生成される。この変換の結果、従来技術の最適化方法である定数の畳み込み（constant folding）、あるいは、演算強度の削減といった最適化が可能になる。最終的に、文ノードＳ７に含まれる乗算が別の演算に変換され、図１０に示す出力プログラム４０１における文ノードＳ７２’，Ｓ７４’，Ｓ７６’に最適化される。プログラムの実行時にシフト演算が乗算より高速に実行できる場合には、この第３の変換により、プログラムの実行時間を改善することができる。また、出力プログラムを用いてハードウェアを生成するような場合においては、乗算器自体が不要となる。このため、ハードウェアの規模を小さくすることが可能になる。
【００６１】
第３の変換においては、要素数分の分岐が新たに生成される。このため、第３の変換の実施を制限してもよい。例えば、変換により定数の畳み込みが可能になる要素についてのみ第３の変換を実施するようにしてもよい。また、変換により演算強度の削減が可能になる乗算や除算等の演算を含む場合に限定して第３の変換を実施するようにしてもよい。
【００６２】
次に、プログラム最適化装置１０１は、中間コードの変換を実施したか否かを判定し（Ｓ２１５）、中間コードの変換を実施した場合は（Ｓ２１５でＹＥＳ）、再度、ノード値算出処理（Ｓ２１３）以降の処理を実行することにより、さらなる最適化を試みる。
【００６３】
中間コードの変換が実施されなかった場合には（Ｓ２１５でＮＯ）、出力プログラム変換部１２５は、中間コード最適化部１２４によって最適化された中間コード１３１から、所定の書式で記述された出力プログラム１１２を生成する（Ｓ２１６）。
【００６４】
図１０は、入力プログラム３０１に対してプログラム最適化装置１０１により最適化された出力プログラムを示している。図１１は、入力プログラム３０１に対して従来技術により最適化された出力プログラムの一例を示している。図１１では、変数が特定の値を取る場合に特化した最適化を行っている。図１０および図１１より、プログラム最適化装置１０１により生成された出力プログラムは、従来技術により生成された出力プログラムと比べて、プログラムサイズが小さいことは明らかである。
【００６５】
以上説明したように、本発明の実施の形態によれば、入力プログラムで使用される変数の取り得る値を、予め取得し、その値に基づいて、中間コードの最適化を行っている。このため、最適化の前にプログラムを実行することなく、プログラムの実行により処理されるデータの特徴に依存した最適化を可能としている。さらに、変数の取り得ない値の情報を利用した最適化を行うことで、不要なコードの削減が可能となる。このため、従来技術による最適化よりもプログラムサイズの小さいコードを生成することが可能となる。
【００６６】
また、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、算出結果が常に固定された値の場合は定数に置換したり、冗長な分岐を削除したりすることで、プログラムサイズの小さい出力プログラムを生成することもできる。
【００６７】
さらに、入力プログラム中の変数の取り得る値を指定しているため、変数の取り得る値から算出された値を利用して、少ない分岐数でありながら、定数への置換数を増やせるため、実行速度の改善の可能性を高めることもできる。
【００６８】
以上、本発明の実施の形態に係るプログラム最適化装置１０１について説明したが、本発明は、この実施の形態に限定されるものではない。
【００６９】
例えば、上述の実施の形態では、入力プログラム１１１がＣ言語で記述され、変数の取り得る値をｐｒａｇｍａにより指定する方法について説明した。しかし、ｐｒａｇｍａで指定する情報と同じ情報を入力プログラムとは別のファイルに記述することにより、変数の取り得る値を指定してもよい。
【００７０】
図１２〜図１４を用いて、入力プログラムとは別の指定ファイルを用いて変数の取り得る値を指定する方法について説明する。
【００７１】
図１２は、この方法に係るプログラム最適化装置の構成を示す図である。プログラム最適化装置１０１ａは、図１に示したプログラム最適化装置１０１の構成において、変数値設定部１２２を変数値設定部１２２ａに変更したものである。それ以外の構成は、プログラム最適化装置１０１と同様である。変数値設定部１２２ａは、変数の取り得る値を指定ファイル１１３から取得し、変数の取り得る値を定数の集合として、中間コード１３１に設定する。
【００７２】
図１３は、入力プログラムの一例を示す図である。図１４は、指定ファイルの一例を示す図である。例えば、入力プログラム１１０１に記述されている変数ａおよびｃに対して、変数の取り得る値を指定する場合、指定ファイル１１０２に変数ａおよびｃを特定する情報と、変数ａおよびｃが取り得る値とを記述することにより、ｐｒａｇｍａ記述と同様に、変数ａおよびｃの取り得る値を指定することができる。
【００７３】
なお、ｐｒａｇｍａまたは指定ファイルを用いて変数の取り得る値を指定する以外にも、ＧＵＩを用いて、入力プログラムを画面に表示し、ユーザがポインタで指定した変数に対して、当該変数の取り得る値を入力するようにしてもよい。
【００７４】
図１５〜図１７を用いて、ＧＵＩを用いて変数の取り得る値を指定する方法について説明する。
【００７５】
図１５は、この方法に係るプログラム最適化装置の構成を示す図である。プログラム最適化装置１０１ｂは、図１に示したプログラム最適化装置１０１の構成において、変数値設定部１２２を変数値設定部１２２ｂに変更したものである。それ以外の構成は、プログラム最適化装置１０１と同様である。変数値設定部１２２ｂは、入力プログラム１１１を表示端末１１４に表示させ、ユーザによる入力により変数の取り得る値を取得し、変数の取り得る値を変数の集合として、中間コード１３１に設定する。
【００７６】
図１６は、表示端末１１４に表示される、入力プログラムを含む入力プログラム表示ウィンドウの一例を示す図である。図１７は、変数属性ダイアログの一例を示す図である。例えば、入力プログラム表示ウィンドウ１２０１に表示されている入力プログラムに記述されている変数ａに対して、変数の取り得る値を指定する場合を考える。ユーザは、入力プログラム表示ウィンドウ１２０１上で、変数ａをポインタにより選択する。次に、ユーザは、プルダウンメニューから変数属性ダイアログ１２０２を開くためのメニューを選択することにより、変数属性ダイアログ１２０２を表示端末１１４上に表示させる。ユーザは、変数属性ダイアログ１２０２において、変数ａの取り得る値として“０，１”を入力する。同様に変数ｃに対しても取り得る値を入力することで、ｐｒａｇｍａ記述と同様に、変数ａおよびｃの取り得る値を指定することができる。
【００７７】
なお、ＧＵＩを用いずとも、例えば、ＣＵＩ（Character User Interface）を用いて、ユーザが変数の取り得る値を入力するような構成であってもよい。
【００７８】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味及び範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【００７９】
本発明にかかるプログラム最適化装置は、プログラムのソースコードからオブジェクトコードを生成するコンパイラや、逐次処理プログラムからハードウェアのＲＴＬ（Register Transfer Level）記述を生成する高位合成ツールに適用でき、特に、プログラムの処理するデータに依存した最適化を施したオブジェクトコードやＲＴＬ記述を生成する場合に有用である。
【符号の説明】
【００８０】
１０１、１０１ａ、１０１ｂ  プログラム最適化装置
１１１  入力プログラム
１１２  出力プログラム
１１３  指定ファイル
１１４  表示端末
１２１  中間コード変換部
１２２、１２２ａ、１２２ｂ  変数値設定部
１２３  ノード値算出部
１２４  中間コード最適化部
１２５  出力プログラム変換部
１３１  中間コード
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、
前記入力プログラムを中間コードに変換する中間コード変換部と、
前記入力プログラムで使用される変数の取り得る値を、外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードに設定する変数値設定部と、
設定された前記変数の取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部と
を備えるプログラム最適化装置。
【請求項２】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項３】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項４】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードに設定する
請求項１に記載のプログラム最適化装置。
【請求項５】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換する
請求項１に記載のプログラム最適化装置。
【請求項６】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除する
請求項１に記載のプログラム最適化装置。
【請求項７】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換する
請求項１に記載のプログラム最適化装置。
【請求項８】
前記中間コード最適化部は、前記変数の取り得る値から、前記中間コードを木構造で表した際のノードの取り得る値を算出し、前記ノードの取り得る値に基づいて、前記中間コードを最適化する
請求項１に記載のプログラム最適化装置。
【請求項９】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化装置であって、
前記入力プログラムを中間コードに変換する中間コード変換部と、
前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定する変数値設定部と、
前記ノードの取り得る値に基づいて、前記中間コードを最適化する中間コード最適化部と、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する出力プログラム変換部と
を備えるプログラム最適化装置。
【請求項１０】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、当該中間コードに含まれる複数のノードのうち、取り得る値が１つのみのノードを、定数を示すノードに置換する
請求項９に記載のプログラム最適化装置。
【請求項１１】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、条件分岐を表現するノードについて、当該ノードが取り得る値に含まれない値に依存する分岐を、前記中間コードより削除する
請求項９に記載のプログラム最適化装置。
【請求項１２】
前記中間コード最適化部は、前記中間コードを木構造で表した際の、複数の値を取り得る変数を示す変数ノードを含むノードを、取り得る値に従い分岐する前記変数ノードを含む複数のノードに変換し、変換後の前記複数のノードの各々に含まれる前記変数ノードを、分岐条件とされた取り得る値を示す定数ノードに置換する
請求項９に記載のプログラム最適化装置。
【請求項１３】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、ユーザからの入力により取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１４】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、前記入力プログラム中に記載された指示子から取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１５】
前記変数値設定部は、前記入力プログラムで使用される変数の取り得る値を、所定のファイルから取得し、取得した前記変数の取り得る値を前記中間コードのノードに設定する
請求項９に記載のプログラム最適化装置。
【請求項１６】
プログラミング言語で記述された入力プログラムを最適化するプログラム最適化方法であって、
前記入力プログラムを中間コードに変換し、
前記入力プログラムで使用される変数の取り得る値を外部から与えられる情報より取得し、取得した前記変数の取り得る値を前記中間コードを木構造で表した際のノードに設定し、
前記ノードの取り得る値に基づいて、前記中間コードを最適化し、
前記中間コード最適化部により最適化された中間コードを、所定の書式で記述された出力プログラムに変換する
プログラム最適化方法。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2009098739.tif 000020
【図２】
2009098739.tif 000021
【図３】
2009098739.tif 000022
【図４】
2009098739.tif 000023
【図５】
2009098739.tif 000024
【図６】
2009098739.tif 000025
【図７】
2009098739.tif 000026
【図８】
2009098739.tif 000027
【図９】
2009098739.tif 000028
【図１０】
2009098739.tif 000029
【図１１】
2009098739.tif 000030
【図１２】
2009098739.tif 000031
【図１３】
2009098739.tif 000032
【図１４】
2009098739.tif 000033
【図１５】
2009098739.tif 000034
【図１６】
2009098739.tif 000035
【図１７】
2009098739.tif 000036
【国際調査報告】
2009098739.tif 000037
2009098739.tif 000038
2009098739.tif 000039
2009098739.tif 000040