JP2004062324A

JP2004062324A - 最適化コンパイル装置、プログラム最適化方法、プログラム、及び記憶媒体

Info

Publication number: JP2004062324A
Application number: JP2002216856A
Authority: JP
Inventors: Kenji Suehiro; 末廣　謙二
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2002-07-25
Filing date: 2002-07-25
Publication date: 2004-02-26

Abstract

【課題】プログラム最適化装置において、実行時情報を利用してコンパクトで高速な目的コードを生成すること。その際、実行時情報の取得にかかるコストを最小とし、最適化を高速に行えるようにすること。
【解決手段】プログラム最適化手段と、実行時情報取得プログラム生成手段と、実行時情報解析手段とを設ける。プログラム最適化手段はソースプログラムの最適化変形を行う。実行時情報取得プログラム生成手段は最適化の過程で必要な実行時情報を取得するため、プログラム最適化手段からの要求により、ソースプログラムから必要最小限の実行時情報取得プログラムを作成し、出力する。実行時情報解析手段は、実行時情報取得プログラムを対象計算機上で実行した出力として得られる実行時情報を解析し、プログラム最適化手段で利用できる形に加工する。
【選択図】　図１

Description

【０００１】
【発明の属する技術分野】
本発明は、最適化コンパイル装置、プログラム最適化方法、及び記憶媒体に関し、特に、プログラムの実行時の情報を最適化に利用することができる最適化コンパイル装置、プログラム最適化方法、プログラム、及び記憶媒体に関する。
【０００２】
【従来の技術】
入力されたプログラムに何らかの最適化変形を施して出力するプログラム変換装置（以下「コンパイラ」と呼ぶ）は、最適化の対象となるプログラムに関して、その文面から静的に解析できる情報だけをもとに最適化を行うのが通例である。しかし、対象プログラムを実行してみて初めてわかるプログラム情報（以下「実行時情報」）を用いれば、より進んだ最適化を行うことができる場合がある。
【０００３】
たとえば、ループ処理をベクトル命令に置き換える自動ベクトル化コンパイラにおいては、ループの反復数の多寡によってベクトル処理命令列に置き換えた方が、コンピュータによって実際に実行される目的コードの処理時間がより高速になる場合、別のベクトル処理命令列の方が前記目的コードの処理時間が高速になる場合、ベクトル処理命令列に置き換えない方が前記目的コードの処理時間が高速になる場合などがある。コンパイラはこれらを適切に判断して前記目的コードを生成し、該目的コードを使用してオブジェクトプログラムを生成しなければならない。しかし、そもそも対象ループの反復数がプログラムの文面だけから静的にわからない場合には、このような判断ができない。
【０００４】
従来、このような場合には、コンパイラは様々な場合を仮定したループの最適化コードを複数同時に生成し、実行時にループの反復数の多寡に応じて、いずれかのコードを条件分岐により選択して使用する、「マルチバージョン方式」と呼ばれる方法が採られていた。マルチバージョン方式については、たとえば、特開平０１−０１８８７６号公報、特開平０３−０９４３７１号公報、特開平０３−２２０６３２号公報、特開平０４−３３２０４４号公報、特開平０６−３２４８８１号公報、特開平０６−２５０９８９号公報、特開平１０−３３３９１９号公報に記載されている。
【０００５】
一方、目的コードの実行時の挙動を逐一記録し、この情報をソースプログラムとともに再度コンパイラ等に入力してプログラムの最適化に利用する、「プロファイル方式」と呼ばれる方法もある。プロファイル方式については、たとえば、特開平０１−１１８９３１号公報、特開平０６−００４２９９号公報、特開平０９−３３０２３３号公報に記載されている。
【０００６】
【発明が解決しようとする課題】
マルチバージョン方式では、コンパイラによって生成される目的コードのサイズが増大するばかりでなく、結果的には利用されないコードも目的コードに含まれることになるため、目的コードのメモリの利用効率が悪い。また、どの最適化方式を採用するかの条件判断をプログラムの翻訳時ではなく実行時に行うため、プログラムの実行性能が低下するという問題があった。
【０００７】
また、プロファイル方式では、実行時情報の取得のために本質的にソースプログラムと同一のプログラムを利用するため、実行時間のかかる巨大なプログラムに対して適用が困難であるという問題があった。
【０００８】
本発明の目的は、実行時情報を利用して、コンパクトで高速な目的コードを生成するコンパイラを提供することである。また、その際、実行時情報の取得にかかるコストを最小とし、コンパイラにおけるプログラムの最適化を高速に行えるようにすることができる。
【０００９】
【課題を解決するための手段】
請求項１記載の最適化コンパイル装置は、前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出し、最適化のために必要とする最小限の実行時情報を取得するために構成された実行時情報取得プログラムを生成する実行時情報取得プログラム生成手段と、前記実行時情報抽出プログラムを実行した結果得られる最適化のために必要とする最小限の実行時情報の構造を解析し、解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する実行時情報解析手段と、前記実行時情報取得プログラム生成手段に対し、最適化に必要な実行時情報の取得を要求するとともに、前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行うプログラム最適化手段とを有することを特徴とする。
【００１０】
請求項２記載の最適化コンパイル装置は、前記プログラム最適化手段が、最適化処理を行う際、前記実行時情報取得プログラム生成手段に対して最適化の対象となるループの反復数の値を要求し、当該ループの反復数が、最適化処理を行うのに必要最小限のあらかじめ定められた所定数よりも大きいときに、当該ループをベクトル処理命令に置き換えることを特徴とする。
【００１１】
請求項３記載の最適化コンパイル装置は、前記実行時情報取得プログラム生成手段はデータの有効範囲の解析を行うデータフロー解析部を有し、該データフロー解析部によるデータフロー解析により最適化のために必要とする最小限の実行文情報を抽出することを特徴とする。
【００１２】
請求項４記載の最適化コンパイル装置は、前記最小限の実行文情報は、前記ソースプログラムに実行される実行文情報の内、コンパイラの最適化処理において省略しても差し支えない実行文情報を除いた実行文情報であることを特徴とする。
【００１３】
請求項５記載のプログラム最適化方法は、最適化に必要な最小限の実行時情報の取得を要求する第１のステップと、前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出する第２のステップと、最適化のために必要とする最小限の実行時情報を取得するためのプログラムであって、抽出された前記最小限の実行文情報が埋め込まれている実行時情報取得プログラムを生成する第３のステップと、前記実行時情報抽出プログラムを実行した結果得られる前記最小限の実行時情報の構造を解析する第４のステップと、解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する第５のステップと、前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行う第６のステップを有することを特徴とする。
【００１４】
請求項６記載のプログラム最適化方法は、前記第６のステップには、さらに最適化の対象となるループの反復数の値を要求するステップと、当該ループの反復数が、最適化処理を行うのに必要最小限のあらかじめ定められた所定数よりも大きいときに、当該ループをベクトル処理命令に置き換えるステップを有することを特徴とする。
【００１５】
請求項７記載のプログラム最適化方法は、前記第１のステップにおいて、最適化のために必要とする最小限の実行文情報をデータフロー解析により抽出することを特徴とする。
【００１６】
請求項８記載のプログラム最適化方法は、前記最小限の実行文情報は、前記ソースプログラムに実行される実行文情報の内、コンパイラの最適化処理において省略しても差し支えない実行文情報を除いた実行文情報であることを特徴とする。
【００１７】
請求項９記載のプログラムは、プログラム最適化処理が、最適化に必要な最小限の実行時情報の取得を要求する第１のステップと、前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出する第２のステップと、最適化のために必要とする最小限の実行時情報を取得するためのプログラムであって、抽出された前記最小限の実行文情報が埋め込まれている実行時情報取得プログラムを生成する第３のステップと、前記実行時情報抽出プログラムを実行した結果得られる前記最小限の実行時情報の構造を解析する第４のステップと、解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する第５のステップと、前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行う第６のステップを有することを特徴とする。
【００１８】
請求項１３記載の記録媒体は、請求項９〜１２のいずれかに記載のプログラムが記録されているものである。
【００１９】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明による最適化コンパイル装置の一実施の形態を示すブロック図である。
【００２０】
コンパイラ２０は、その内部に実行時情報取得プログラム生成手段２２と、実行時情報解析手段２３と、プログラム最適化手段２１を備えている。
【００２１】
コンパイラ２０は高級言語で記述されたソースプログラム１０を入力として受理し、最適化変形を施した後、高級言語、アセンブリ言語、若しくは機械命令列で表現された目的コード６０を出力する。そして、その目的コード６０を使用してオブジェクトプログラムが生成される。
【００２２】
ここで、ソースプログラム１０の最適化変形はプログラム最適化手段２１によって行なわれる。以下、コンパイラ２０の各構成要素の動作について図２のフローチャートを参照して説明する。
【００２３】
プログラム最適化手段２１は、実行時情報取得プログラム生成手段２２に対し、最適化に必要な実行時情報５０の取得を要求する（ステップＳ１０１）。
【００２４】
実行時情報取得プログラム生成手段２２は、ソースプログラム１０から最適化の過程で必要とする最小限の実行文情報（モジュール）を抽出し（ステップＳ１０２）、最適化のために必要とする最小限の実行時情報を取得するために構成された実行時情報取得プログラム３０を生成する（ステップＳ１０３）。
【００２５】
対象計算機４０は実行時情報抽出プログラム３０を実行する（ステップＳ１０４）。実行時情報解析手段２３は、対象計算機４０が実行時情報抽出プログラム３０を実行した結果、出力された実行時情報５０を入力し、入力された実行時情報５０の構造を解析し（ステップＳ１０５）、解析された実行時情報５０をプログラム最適化手段２１でソースプログラム１０の最適化に利用できる形式に加工する（ステップＳ１０６）。
【００２６】
プログラム最適化手段２１は、上記したように解析された実行時情報５０に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行う（ステップＳ１０７）。
【００２７】
次に、図３のソースプログラムを例に、本実施の形態の動作を説明する。プログラム最適化手段２１は、入力されたソースプログラム１０中のループの反復数が、例えば２５６よりも大きいときに、そのループをベクトル処理命令に置き換えるものとする。
【００２８】
図３のソースプログラムがコンパイラ２０に入力されると、プログラム最適化手段２１は、５行目のループをベクトル命令に置き換えるべきかどうか判定しようとする。ループの反復数はＣであるが、Ｃの値はプログラムの文面上だけからは不明である。そこで、プログラム最適化手段２１は、実行時情報取得プログラム生成手段２２に対し、「５行目におけるＣの値」を要求する。
【００２９】
実行時情報取得プログラム生成手段２２は、データフロー解析の手法により、「５行目におけるＣの値」を決定するのに必要最小限の実行文（必要最小限の実行時情報）をソースプログラム１０から抽出し、その必要最小限の実行文だけを必要最小限の実行時情報として取得するのに利用される実行時情報取得プログラム３０を再構成する。
【００３０】
さらに、実行時情報取得プログラム３０には、ソースプログラムの５行目に相当する位置に、Ｃの値のみを出力するための出力文が埋め込まれる。図３のソースプログラムで、５行目におけるＣの値を計算しているのは３行目の代入文「Ｃ＝Ａ＊Ａ」であり、さらにその右辺のＡの値は１行目のＲＥＡＤ文によりプログラム外から入力されている。
【００３１】
したがって、実行時情報取得プログラム生成手段２２により出力される実行時情報取得プログラムは、図３のソースプログラムから１行目と３行目を抽出し、さらに５行目の位置にＣの値を出力するＷＲＩＴＥ文を挿入したもの、すなわち図４のようになる。
【００３２】
図４に示す実行時情報取得プログラムを対象計算機４０の上で実行すると、出力として図５のような実行時情報が得られる。実行時情報解析手段２３はこの出力を構文解析し、プログラム最適化手段２１に対して「５行目におけるＣの値」の回答として４００を与える。プログラム最適化手段２１は、ループの反復数（４００）が２５６よりも大きいため、５行目のループをベクトル処理命令で置き換える最適化処理を行う。
【００３３】
【発明の効果】
マルチバージョン方式では複数の最適化方式によるコードを目的コード内に併せ持ち、結果的には利用されない無駄なコードも目的コードに含まれるのに対し、本発明では、実際に利用されるコードのみが目的コードに含まれるため、従来のマルチバージョン方式と比べて目的コードのサイズが小さくなり、メモリの利用効率がよいという効果が得られる。
【００３４】
マルチバージョン方式ではどの最適化方式によるコードを利用するかの判断を実行時に行うため、オーバーヘッドが生じるのに対し、本発明では、その判断を翻訳時にすべて終えており、実行時にオーバーヘッドが生じないので、マルチバージョン方式と比べて目的コードが高速に実行されるという効果が得られる。
【００３５】
プロファイル方式が、元のソースプログラムに情報取得ルーチンを追加しただけのものを実行時情報の取得に利用しており、本質的に元のプログラムの実行時間と同じだけの時間を実行時情報の取得に必要とするのに対し、本発明では、コンパイラが最適化のために必要とする情報だけを取得する最小限の実行時情報取得プログラムを実行時情報の取得に利用するため、その実行時間がわずかで済むプロファイル方式と比べて実行時情報の取得に要する時間が短く、結果としてプログラムの最適化に要する時間が短いという効果が得られる。
【図面の簡単な説明】
【図１】本発明の一実施の形態を示したブロック図である。
【図２】本発明のプログラム最適化方法における各処理手順を示したフローチャートである。
【図３】ソースプログラムの一例を示した図である。
【図４】実行時情報取得プログラムの一例を示した図である。
【図５】実行時情報の一例を示した図である。
【符号の説明】
１０　ソースプログラム
２０　コンパイラ
２１　プログラム最適化手段
２２　実行時情報取得プログラム生成手段
２３　実行時情報解析手段
３０　実行時情報取得プログラム
４０　対象計算機
５０　実行時情報

Claims

ソースプログラムを入力として受理し、最適化変形を施した目的コードを含む目的プログラムを生成する最適化コンパイル装置において、
前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出し、最適化のために必要とする最小限の実行時情報を取得するために構成された実行時情報取得プログラムを生成する実行時情報取得プログラム生成手段と、前記実行時情報抽出プログラムを実行した結果得られる最適化のために必要とする最小限の実行時情報の構造を解析し、解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する実行時情報解析手段と、
前記実行時情報取得プログラム生成手段に対し、最適化に必要な実行時情報の取得を要求するとともに、前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行うプログラム最適化手段と
を有することを特徴とする最適化コンパイル装置。
前記プログラム最適化手段は、最適化処理を行う際、前記実行時情報取得プログラム生成手段に対して最適化の対象となるループの反復数の値を要求し、当該ループの反復数が、最適化処理を行うのに必要最小限のあらかじめ定められた所定数よりも大きいときに、当該ループをベクトル処理命令に置き換えることを特徴とする請求項１記載の最適化コンパイル装置。
前記実行時情報取得プログラム生成手段はデータの有効範囲の解析を行うデータフロー解析部を有し、該データフロー解析部によるデータフロー解析により最適化のために必要とする最小限の実行文情報を抽出することを特徴とする請求項１又は２記載の最適化コンパイル装置。
前記最小限の実行文情報は、前記ソースプログラムに実行される実行文情報の内、コンパイラの最適化処理において省略しても差し支えない実行文情報を除いた実行文情報であることを特徴とする請求項１〜３のいずれかに記載の最適化コンパイル装置。
ソースプログラムに最適化変形を施し、最適な実行プログラムを生成するプログラム最適化方法において、
最適化に必要な最小限の実行時情報の取得を要求する第１のステップと、
前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出する第２のステップと、
最適化のために必要とする最小限の実行時情報を取得するためのプログラムであって、抽出された前記最小限の実行文情報が埋め込まれている実行時情報取得プログラムを生成する第３のステップと、
前記実行時情報抽出プログラムを実行した結果得られる前記最小限の実行時情報の構造を解析する第４のステップと、
解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する第５のステップと、
前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行う第６のステップ
を有することを特徴とするプログラム最適化方法。
前記第６のステップには、さらに最適化の対象となるループの反復数の値を要求するステップと、
当該ループの反復数が、最適化処理を行うのに必要最小限のあらかじめ定められた所定数よりも大きいときに、当該ループをベクトル処理命令に置き換えるステップを
有することを特徴とする請求項５記載のプログラム最適化方法。
前記第１のステップにおいて、最適化のために必要とする最小限の実行文情報をデータフロー解析により抽出することを特徴とする請求項５又は６記載のプログラム最適化方法。
前記最小限の実行文情報は、前記ソースプログラムに実行される実行文情報の内、コンパイラの最適化処理において省略しても差し支えない実行文情報を除いた実行文情報であることを特徴とする請求項５〜７のいずれかに記載のプログラム最適化方法。
ソースプログラムに最適化変形を施し、最適な実行プログラムを生成するプログラム最適化処理をコンピュータに対して実行させるプログラムにおいて、前記プログラム最適化処理は、
最適化に必要な最小限の実行時情報の取得を要求する第１のステップと、
前記ソースプログラムから最適化のために必要とする最小限の実行文情報を抽出する第２のステップと、
最適化のために必要とする最小限の実行時情報を取得するためのプログラムであって、抽出された前記最小限の実行文情報が埋め込まれている実行時情報取得プログラムを生成する第３のステップと、
前記実行時情報抽出プログラムを実行した結果得られる前記最小限の実行時情報の構造を解析する第４のステップと、
解析された実行時情報を前記ソースプログラムの最適化に利用できる形式に加工する第５のステップと、
前記実行時情報に基いて最適化の対象となるループをベクトル命令に置き換える最適化処理を行う第６のステップ
を有することを特徴とするプログラム。
前記第６のステップには、さらに最適化の対象となるループの反復数の値を要求するステップと、
当該ループの反復数が、最適化処理を行うのに必要最小限のあらかじめ定められた所定数よりも大きいときに、当該ループをベクトル処理命令に置き換えるステップを
有することを特徴とする請求項９記載のプログラム。
前記第１のステップにおいて、最適化のために必要とする最小限の実行文情報をデータフロー解析により抽出することを特徴とする請求項９又は１０記載のプログラム。
前記最小限の実行文情報は、前記ソースプログラムに実行される実行文情報の内、コンパイラの最適化処理において省略しても差し支えない実行文情報を除いた実行文情報であることを特徴とする請求項９〜１１のいずれかに記載のプログラム。
請求項９〜１２のいずれかに記載のプログラム最適化方法を実行可能なプログラムが記録されている記録媒体。