(57)【要約】      （修正有）【課題】最適化処理を中断することなく、コンパイル所要時間の大幅増加を防止する。【解決手段】最適化コンパイラは、ソースプログラムを構文解析し、中間言語コード列を生成する構文解析部１１と、中間言語コード列のコントロールフローを解析し、中間言語コード列を基本ブロックに展開するコントロールフロー解析部１２と、既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えている場合は、既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する最適化範囲判断部１３と、最適化範囲の中間言語コード列のデータフローを解析するデータフロー解析部１４と、データフローの解析結果に基づいて、最適化範囲の中間言語コード列を変形する最適化処理を行う最適化処理部１５と、最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、目的プログラムを出力するコード生成部１７と、を有する。【選択図】図１
2010049315.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムを、最適化処理を伴ってコンパイルする最適化コンパイラであって、
前記ソースプログラムを構文解析し、該解析結果に基づいて中間言語コード列を生成する構文解析部と、
前記中間言語コード列のコントロールフローを解析し、該解析結果に基づいて中間言語コード列を基本ブロックに展開するコントロールフロー解析部と、
既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判断し、上限値を超えていない場合は、最適化範囲を既定のままとし、上限値を超えている場合は、前記既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する最適化範囲判断部と、
前記各々の最適化範囲の中間言語コード列のデータフローを解析するデータフロー解析部と、
前記データフローの解析結果に基づいて、前記各々の最適化範囲の中間言語コード列を変形する最適化処理を行う最適化処理部と、
前記最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力するコード生成部と、を有する最適化コンパイラ。
【請求項２】
前記最適化範囲判断部は、前記コントロールフロー解析部により解析されたＩＦ…ＴＨＥＮ…ＥＬＳＥ構造およびループ構造が、異なる最適化範囲に分断されないように、前記既定の最適化範囲を分割する、請求項１に記載の最適化コンパイラ。
【請求項３】
前記各々の最適化範囲における、中間言語コード列の行数、基本ブロックの個数、および最適化処理の所要時間を含む最適化プロファイル情報を、画面またはファイルに出力する最適化プロファイル情報出力部をさらに有する、請求項１または２に記載の最適化コンパイラ。
【請求項４】
利用者が基本ブロック数の上限値を指定すると、指定された値に基本ブロック数の上限値の設定を変更する上限値変更部をさらに有する、請求項１から３のいずれか１項に記載の最適化コンパイラ。
【請求項５】
ソースプログラムを、最適化処理を伴ってコンパイルする最適化コンパイル方法であって、
前記ソースプログラムを構文解析し、該解析結果に基づいて中間言語コード列を生成する構文解析ステップと、
前記中間言語コード列のコントロールフローを解析し、該解析結果に基づいて中間言語コード列を基本ブロックに展開するコントロールフロー解析ステップと、
既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判断し、上限値を超えていない場合は、最適化範囲を既定のままとし、上限値を超えている場合は、前記既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する最適化範囲判断ステップと、
前記各々の最適化範囲の中間言語コード列のデータフローを解析するデータフロー解析ステップと、
前記データフローの解析結果に基づいて、前記各々の最適化範囲の中間言語コード列を変形する最適化処理を行う最適化処理ステップと、
前記最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力するコード生成ステップと、を有する最適化コンパイル方法。
【請求項６】
前記最適化範囲判断ステップは、前記コントロールフロー解析ステップで解析されたＩＦ…ＴＨＥＮ…ＥＬＳＥ構造およびループ構造が、異なる最適化範囲に分断されないように、前記既定の最適化範囲を分割する、請求項５に記載の最適化コンパイル方法。
【請求項７】
前記各々の最適化範囲における、中間言語コード列の行数、基本ブロックの個数、および最適化処理の所要時間を含む最適化プロファイル情報を、画面またはファイルに出力する最適化プロファイル情報出力ステップをさらに有する、請求項５または６に記載の最適化コンパイル方法。
【請求項８】
利用者が基本ブロック数の上限値を指定すると、指定された値に基本ブロック数の上限値の設定を変更する上限値変更ステップをさらに有する、請求項５から７のいずれか１項に記載の最適化コンパイル方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソースプログラムを、最適化処理を伴ってコンパイルする最適化コンパイラおよび最適化コンパイル方法に関する。
【背景技術】
【０００２】
従来の最適化コンパイラは、ソースプログラムから生成した中間言語コード列を、コントロールフロー解析により基本ブロックに展開し、データフロー解析を実施した後、最適化処理を実施する方式となっている。
【０００３】
このとき、一度の最適化処理で対象となる最適化範囲は、通常、副プログラムの入口から出口までの間に含まれる基本ブロックとなる。ここで、副プログラムは、ソースプログラムの手続や関数等に相当する。また、基本ブロックは、制御の流れの入口と出口が１つずつしかなく、途中分岐もしない中間言語コード列の塊である。これらの基本ブロックを束ねた範囲が最適化範囲となり、この最適化範囲を対象として最適化処理が実施される。
【０００４】
すなわち、従来の最適化コンパイラにおいては、ソースプログラムの副プログラムがほぼそのまま最適化範囲に該当し、副プログラムに対応する中間言語コード列が、複数の最適化範囲に分割されて各々別々に最適化されることはなかった。
【０００５】
一般に、プログラムを、最適化処理を伴ってコンパイルするときの所要時間と中間言語コード列の行数との間には、次の関係式（１）が成り立つ。
【０００６】
Ｔ＝ｋ・Ｌ＾ｎ（＾はべき乗を表す）−−−−−（１）
Ｔ：コンパイル所要時間
ｋ：比例係数
Ｌ：中間言語コード列の行数
ｎ：中間言語コード列を走査する回数
ｋは、比例係数であり、プログラムの構造、記述言語等の特性、処理系等に依存すると考えられる。また、ｎは、最適化のレベルにより変動する。
【０００７】
単純なレベルの最適化処理の場合、構文解析のためのプログラム走査に加え、中間言語コード列を基本ブロックに分割するための走査が発生する。そのため、走査回数ｎ＝２となり、コンパイル所要時間は、中間言語コード列の行数の２乗に比例する。
【０００８】
また、最適化処理の内容がより複雑で高度なレベルになると、中間言語コード列を繰り返し走査することが必要になるため、走査回数ｎは増加し、コンパイル所要時間Ｔが中間言語コード列行数Ｌのｎ乗に比例することになる。このことは、従来の最適化コンパイラに次のような問題があることを意味する。
（Ａ）プログラムが大規模になれば中間言語コード列も巨大になり、最適化処理の所要時間が指数関数的に増加し、コンパイル全体の所要時間が大幅に増加する。
（Ｂ）プログラム規模が一定の場合、高度なレベルの最適化になるほど、最適化処理の所要時間が次数的に増加し、コンパイル全体の所要時間が大幅に増加する。
【０００９】
こうした問題に対処するため、従来より、最適化コンパイラにおいて、以下の（ａ）〜（ｃ）のような最適化コンパイル方法を実施することが提案されている。
（ａ）手動で大規模プログラムをより小さなプログラムに分割しコンパイルする。
（ｂ）大きな副プログラムをより小さな副プログラムに分けて記述しコンパイルする。
（ｃ）最適化のレベルを落としてコンパイルする。
【００１０】
しかしながら、（ａ）〜（ｃ）の最適化コンパイル方法には、それぞれ次の欠点がある。
（ａ）プログラムを誤りなく修正するための手作業に細心の注意を払う必要があり、効率的でない。
（ｂ）副プログラムの名称や呼び出し方法等の変更を伴うため、プログラムの構造が変わるとともに仕様書などの修正が必要となる。
（ｃ）最適化によるオブジェクトの実行時性能向上を享受できない。
【００１１】
このため、最近は、他の最適化コンパイル方法により、コンパイル所要時間の大幅増加を防止することの重要性が一層増してきている。
【００１２】
そこで、例えば、一部の言語処理系の中には、コンパイル所要時間の大幅増加防止を目的として、利用者が、最適化対象の基本ブロック数の上限値を指定し、副プログラムの基本ブロック数が上限値を超えた場合に、最適化処理を中断して最適化前の目的コードを生成する最適化コンパイル方法を採用しているものがある（例：日本電気株式会社製ワークステーションＥＷＳ用のＥＷＳ−ＵＸ／Ｖ搭載のＣコンパイラ）。
【００１３】
しかしながら、この最適化コンパイル方法では、最適化処理が中断されるため、大規模プログラムの場合、ソースプログラムの一部が最適化されず、実行時の性能向上を実現できないという欠点がある。
【００１４】
また、コンパイル所要時間の大幅増加防止を目的とする他の最適化コンパイル方法として、特許文献１に開示された方法がある。この方法は、プログラムに一度最適化を適用して最適化情報を記録しておき、次に同じプログラムあるいは同じプログラムを修正等した類似のプログラムをコンパイルする場合に、前回のコンパイル時に記録しておいた最適化情報を再利用しコンパイル所要時間を短縮しようとするものである。
【００１５】
しかしながら、この最適化コンパイル方法では、最適化情報として、最適化前コード、最適化コード、最適化適用条件等を記録する。このため、最適化情報を再利用できるプログラムが、命令の定数や変数名等が異なるだけの極めて類似したプログラムに限られてしまうという欠点がある。
【特許文献１】特開２００３−３３７７０９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１６】
このように、上述した、コンパイル所要時間の大幅増加を防止する最適化コンパイル方法には、最適化処理を中断しなければならないという課題や、前回コンパイルしたプログラムと類似性のないプログラムは適用できないという課題がある。
【００１７】
そこで、本発明の目的は、上述した課題のいずれかを解決する最適化コンパイラおよび最適化コンパイル方法を提供することにある。
【課題を解決するための手段】
【００１８】
本発明の最適化コンパイラは、
ソースプログラムを、最適化処理を伴ってコンパイルする最適化コンパイラであって、
前記ソースプログラムを構文解析し、該解析結果に基づいて中間言語コード列を生成する構文解析部と、
前記中間言語コード列のコントロールフローを解析し、該解析結果に基づいて中間言語コード列を基本ブロックに展開するコントロールフロー解析部と、
既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判断し、上限値を超えていない場合は、最適化範囲を既定のままとし、上限値を超えている場合は、前記既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する最適化範囲判断部と、
前記各々の最適化範囲の中間言語コード列のデータフローを解析するデータフロー解析部と、
前記データフローの解析結果に基づいて、前記各々の最適化範囲の中間言語コード列を変形する最適化処理を行う最適化処理部と、
前記最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力するコード生成部と、を有する。
【００１９】
本発明の最適化コンパイル方法は、
ソースプログラムを、最適化処理を伴ってコンパイルする最適化コンパイル方法であって、
前記ソースプログラムを構文解析し、該解析結果に基づいて中間言語コード列を生成する構文解析ステップと、
前記中間言語コード列のコントロールフローを解析し、該解析結果に基づいて中間言語コード列を基本ブロックに展開するコントロールフロー解析ステップと、
既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判断し、上限値を超えていない場合は、最適化範囲を既定のままとし、上限値を超えている場合は、前記既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する最適化範囲判断ステップと、
前記各々の最適化範囲の中間言語コード列のデータフローを解析するデータフロー解析ステップと、
前記データフローの解析結果に基づいて、前記各々の最適化範囲の中間言語コード列を変形する最適化処理を行う最適化処理ステップと、
前記最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力するコード生成ステップと、を有する。
【発明の効果】
【００２０】
本発明の最適化コンパイラは、既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えている場合、既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する。
【００２１】
したがって、各々の最適化範囲では、基本ブロック数が上限値を超えず、中間言語コード列の行数が減少するため、最適化処理を中断することなく、最適化処理の所要時間を抑えコンパイル所要時間の大幅増加を防止することが可能となるという効果が得られる。
【発明を実施するための最良の形態】
【００２２】
以下に、本発明を実施するための最良の形態について図面を参照して説明する。
【００２３】
図１を参照すると、本実施形態の最適化コンパイラは、構文解析部１１と、コントロールフロー解析部１２と、最適化範囲判断部１３と、データフロー解析部１４と、最適化処理部１５と、最適化プロファイル情報出力部１６と、コード生成部１７と、上限値変更部１８と、を有する。
【００２４】
構文解析部１１は、高級プログラミング言語で記述されたソースプログラムを構文解析し、その解析結果に基づいて中間言語コード列を生成する。
【００２５】
コントロールフロー解析部１２は、構文解析部１１により生成された中間言語コード列のコントロールフローを解析し、その解析結果に基づいて中間言語コード列を基本ブロックに展開する。
【００２６】
最適化範囲判断部１３は、既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判断し、上限値を超えていない場合は、最適化範囲を既定のままとし、上限値を超えている場合は、既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する。
【００２７】
このとき、最適化範囲判断部１３は、コントロールフロー解析部１２により解析されたＩＦ…ＴＨＥＮ…ＥＬＳＥ構造やループ構造等の制御構造が、異なる最適化範囲に分断されることのないように、既定の最適化範囲を分割する。
【００２８】
データフロー解析部１４は、最適化範囲判断部１３により得られた各々の最適化範囲の中間言語コード列のデータフローを解析する。
【００２９】
最適化処理部１５は、目的コードの実行速度をより高速化するために、データフロー解析部１４による解析結果に基づいて、最適化範囲判断部１３により得られた各々の最適化範囲の中間言語コード列を変形する最適化処理を行う。
【００３０】
最適化プロファイル情報出力部１６は、各々の最適化範囲における、中間言語コード列の行数、基本ブロックの個数、最適化処理の所要時間等を、最適化プロファイル情報として画面またはファイルに出力する。
【００３１】
コード生成部１７は、最適化処理部１５により最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力する。
【００３２】
上限値変更部１８は、利用者が基本ブロック数の上限値を指定すると、指定された値に基本ブロック数の上限値の設定を変更する。なお、この上限値の設定値は、不図示のメモリに格納されるものとする。
【００３３】
以下、本実施形態の最適化コンパイラによる最適化コンパイル方法について、具体例を用いて説明する。
【００３４】
まず、構文解析部１１は、高級プログラミング言語で記述されたソースプログラムを構文解析し、その解析結果に基づいて中間言語コード列を生成する。
【００３５】
次に、コントロールフロー解析部１２は、構文解析部１１により生成された中間言語コード列のコントロールフローを解析し、その解析結果に基づいて中間言語コード列を基本ブロックに展開する。
【００３６】
すると、最適化範囲判断部１３は、まず、コントロールフロー解析部１２により展開された基本ブロックのうち、副プログラムの入口から出口までの範囲に含まれる基本ブロックの全体を既定の最適化範囲とする。
【００３７】
次に、最適化範囲判断部１３は、既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えているか否かを判定し、上限値を超えていない場合は、最適化範囲を既定のままとする。一方、上限値を超えている場合は、最適化範囲判断部１３は、既定の最適化範囲を、各々のブロック数が上限値を超えない複数の最適化範囲に分割する。
【００３８】
なお、最適化範囲判断部１３は、既定の最適化範囲を分割するときは、コントロールフロー解析の結果により各基本ブロックのＩＦ…ＴＨＥＮ…ＥＬＳＥ構造やループ構造等の制御構造が判明しているので、これらの制御構造が異なる最適化範囲に分断されることのないようにする。
【００３９】
具体例として、図２を参照する。
【００４０】
図２の例においては、コントロールフロー解析部１２によるコントロールフロー解析の結果、副プログラムの中間言語コード列が、計１４個の基本ブロックに展開されている。この１４個の基本ブロック全体が、既定の最適化範囲となる。
【００４１】
このとき、基本ブロック数の上限値が５に設定されていたとする。そうすると、既定の最適化範囲に含まれる基本ブロックの個数は１４であるため、上限値を超えている。
【００４２】
そこで、最適化範囲判断部１３は、各々の最適化範囲に含まれる基本ブロックの数が上限値を超えないよう、既定の最適化範囲を更に分割する。
【００４３】
このとき、基本ブロックＡ〜Ｄ、基本ブロックＥ〜Ｈ、基本ブロックＪ〜Ｍは、それぞれＩＦ…ＴＨＥＮ…ＥＬＳＥ構造、ＩＦ…ＴＨＥＮ…ＥＬＳＥ構造、ループ構造を構成していることが、コントロールフロー解析で判明していたとする。
【００４４】
そのため、最適化範囲判断部１３は、これらのＩＦ…ＴＨＥＮ…ＥＬＳＥ構造やループ構造が異なる最適化範囲に分断されてしまうことのないよう、基本ブロックがどの制御構造に属しているかを判断しながら、既定の最適化範囲を分割する。
【００４５】
その結果、図３に示すように、３個の最適化範囲が得られる。
【００４６】
次に、データフロー解析部１４は、最適化範囲判断部１３により得られた各々の最適化範囲において、中間言語コード列のデータフローを解析する。
【００４７】
次に、最適化処理部１５は、目的コードの実行速度をより高速化するために、データフロー解析部１４による解析結果に基づいて、最適化範囲判断部１３により得られた各々の最適化範囲の中間言語コード列を変形する最適化処理を行う。
【００４８】
次に、最適化プロファイル情報出力部１６は、各々の最適化範囲における、中間言語コード列の行数、基本ブロックの個数、最適化処理の所要時間等を、最適化プロファイル情報として画面またはファイルに出力する。
【００４９】
その後、コード生成部１７は、最適化処理部１５により最適化処理が行われた中間言語コード列に基づいて目的コードを生成し、生成した目的コードを含む目的プログラムを出力する。
【００５０】
上述したように本実施形態においては、最適化範囲判断部１３は、既定の最適化範囲に含まれる基本ブロック数が予め設定された上限値を超えている場合、既定の最適化範囲を、各々の基本ブロック数が上限値を超えない複数の最適化範囲に分割する。
【００５１】
したがって、各々の最適化範囲では、基本ブロック数が上限値を超えず、中間言語コード列の行数Ｌが減少するため、最適化処理を中断することなく、最適化処理の所要時間を抑えコンパイル所要時間の大幅増加を防止することが可能になるという効果が得られる。
【００５２】
例えば、図３の場合、既定の最適化範囲が３個の最適化範囲に分割されている。各々の最適化範囲に含まれる中間言語コード列は、約１／３になったとみなし、分割前の中間言語コード列の行数をＬとすると、各々の最適化範囲の最適化処理の所要時間ｔ１，ｔ２，ｔ３は、上述した関係式（１）より、それぞれ以下のようになる。
【００５３】
ｔ１＝ｋ・（Ｌ／３）＾ｎ
ｔ２＝ｋ・（Ｌ／３）＾ｎ
ｔ３＝ｋ・（Ｌ／３）＾ｎ
そのため、最適化処理全体の所要時間Ｔ’は以下のようになる。
【００５４】
Ｔ’＝ｔ１＋ｔ２＋ｔ３
＝３ｋ・（Ｌ／３）＾ｎ
＝ｋ・Ｌ＾ｎ／３＾（ｎ−１）
したがって、最適化処理の所要時間は、分割前の所要時間のほぼ３＾（ｎ−１）分の１になる。
【００５５】
なお、本実施形態においては、基本ブロックが１４個の副プログラムを例に挙げて説明したが、このような小さな副プログラムの場合、実際のコンパイル所要時間は数秒単位であることが多く、本発明による効果は目立たない程小さい可能性がある。
【００５６】
しかし、実際の大規模プログラミングにおいては、１つの副プログラムの行数が数万行〜１０万行以上になることも珍しくない。例えば、８万行を対象に最適化コンパイルを実施すると、所要時間が約４０分〜１時間になることもある。この８万行をそのまま最適化範囲とするよりも、約１／３の２．７万行を対象に最適化処理を実施すれば最適化処理の所要時間を短縮できる。このように、最適化範囲の分割によるコンパイル所要時間の短縮効果は、巨大な副プログラムを多数生産する大規模なプログラミングにおいてより顕著になる。
【００５７】
また、最適化範囲に含まれる中間言語コード列の行数Ｌが減少するので、最適化処理時間の短縮だけでなく、最適化処理に必要なメモリ量を削減できるという効果が得られる。
【００５８】
また、本実施形態においては、最適化プロファイル情報出力部１６は、各々の最適化範囲における、中間言語コード列の行数、基本ブロックの個数、最適化処理の所要時間等を、最適化プロファイル情報として画面またはファイルに出力する。
【００５９】
この最適化プロファイル情報は、次にコンパイラで再利用するのが目的ではなく、利用者が基本ブロック数の上限値を指定する際の参考情報として利用者に提供することを目的として出力されるものである。したがって、次にコンパイルするソースプログラムが前回のソースプログラムと類似である必要は一切ないため、本発明は、全く類似性のないプログラムにも有効に適用できるという効果が得られる。
【００６０】
また、本実施形態においては、上限値変更部１８は、利用者が基本ブロック数の上限値を指定すると、指定された値に基本ブロック数の上限値の設定を変更する。
【００６１】
したがって、利用者は、最適化プロファイル情報を参考にして、現在設定されている基本ブロック数の上限値では満足な所要時間が得られないとき、上限値変更部１８を利用して上限値を増減することにより、受容可能な所要時間を得ることが可能になるという効果が得られる。
【産業上の利用可能性】
【００６２】
本発明は、高級プログラミング言語で記述されたソースプログラムを対象とする最適化コンパイラに適用可能である。
【図面の簡単な説明】
【００６３】
【図１】本発明の一実施形態の最適化コンパイラの構成を示すブロック図である。
【図２】図１に示した最適化コンパイラの既定の最適化範囲を説明する図である。
【図３】図１に示した最適化コンパイラの既定の最適化範囲を分割した３つの最適化範囲を説明する図である。
【符号の説明】
【００６４】
１１    構文解析部
１２    コントロールフロー解析部
１３    最適化範囲判断部
１４    データフロー解析部
１５    最適化処理部
１６    最適化プロファイル情報出力部
１７    コード生成部
１８    上限値変更部
【図１】
2010049315.tif 000003
【図２】
2010049315.tif 000004
【図３】
2010049315.tif 000005