(57)【特許請求の範囲】
【請求項１】
ソースプログラムから、複数種類用意された最適化方法毎に、最適化処理の対象となる命令の数を最適化因子として集計する情報解析部と、
前記最適化因子に基づいて採用すべき最適化方法とその実行順を選択する最適化選択部と、
該最適化選択部により選択された実行順で選択された最適化方法を実行する最適化処理部と
を有することを特徴とするプログラム変換装置。
【請求項２】
前記情報解析部は入力と出力との間に分岐がない処理ブロック毎に前記最適化因子の集計を行い、前記最適化選択部は前記情報解析部の最適化因子の集計結果に応じて前記処理ブロック毎に前記最適化方法とその実行順を選択し、前記最適化処理部は前記最適化選択部の選択結果に応じて前記処理ブロック毎に前記最適化方法を実行することを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
ソースプログラムから、複数種類用意された最適化方法毎に、最適化処理の対象となる命令の数を最適化因子として集計する工程と、
前記最適化因子に応じて採用すべき最適化方法とその実行順を選択する工程と、
選択した最適化方法を選択した実行順で実行する工程と
を有することを特徴とするプログラム変換方法。
【請求項４】
前記最適化因子の集計、最適化方法の選択及び実行は、入力と出力との間に分岐がない処理ブロック毎に行なうことを特徴とする請求項３に記載のプログラム変換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ソースプログラム（原始プログラム）をオブジェクトプログラム（目的プログラム）に変換するプログラム変換装置（コンパイラ）及びプログラム変換方法に関し、特に、最終的に得られるオブジェクトプログラムを高速化したり、又はメモリ使用量を減少させるなどの最適化（ｏｐｔｉｍａｉｚａｔｉｏｎ  ）を行なうプログラム変換装置及びプログラム変換方法に関する。
【０００２】
【従来の技術】
近年、種々のアーキテクチャを持つマイクロコンピュータが開発されており、それらのプログラム変換装置については、メモリ使用量の減少や、実行速度の向上などが要求されている。このため、プログラム変換装置では、単にソースプログラムをオブジェクトプログラムに変換するだけでなく、冗長な命令（関数及び演算式等を含む；以下、同じ）を削減したり、メモリ使用量が少ない命令に置き換える等の処理を施すいわゆる最適化が行われることがある。
【０００３】
図１３は従来のプログラム変換装置を示す模式図である。プログラム変換装置の入力部１１に入力されたソースプログラムは、字句解析部１２で字句（ｔｏｋｅｎ  ）解析が行われる。すなわち、この字句解析部１２では、ソースプログラムを読み込んで、意味がある名前、予約語、定数及び区切り記号などの基本単位の字句に分解し、これらを後の処理が効率よく実行できるように記号表等に展開する。また、この字句解析部１２では、ソースプログラム中の注釈行の読み飛ばし処理や、開始行と継続行との区分処理などを行なう。更に、この過程でマクロの展開処理等も行なう。
【０００４】
構文解析部１３は、プログラムの構文解析（ｓｙｎｔａｘ  ａｎａｌｙｓｉｓ  ）を行なう。すなわち、構文解析部１３は、ソースプログラムを構成する文がどのような階層構成になっているのかを調べたり、文法的に正しいか否かを判定する。
情報解析部１４はデータの依存関係の解析部１４ａを含んで構成されており、構文解析によって得られた構文情報や記号表を基にして、プログラム中で使用されているデータの依存関係の解析を行なう。例えば、変数の宣言を認識した場合には、その変数の名前、型、初期値等の情報を記号表に登録するなどの処理を行なう。また、実行文を認識した場合にはどのような実行文であるかを調べ、文中で使われている各種の変数、関数、手続きなどの使われかたのチェックなどを行う。そして、その結果として、データの依存関係が記号表などの各種の表に記入されたり、入力したソースプログラムに対する内部形式（ｉｎｔｅｒｎａｌ  ｆｏｒｍ  ）の形で内部に蓄えられる。
【０００５】
このようにして情報の解析を行った後、最適化処理部１６で最適化処理を行なう。一般的に、最適化処理部１６では、複数種類の最適化方法を予め定められた順番で実行する。
出力部１７においては、最適化された内部形式から、アセンブリ言語、絶対番地の機械語、再配置可能（ｒｅｌｏｃａｔａｂｌｅ  ）な機械語、又は他のプログラミング言語などで表現されたコードを生成して出力する。
【０００６】
最適化方法には、例えば以下に示すものがある。
（１）畳み込み（ｆｏｌｄｉｎｇ  ）による最適化
定数同士の加減乗除などのように予め演算結果が求められる場合は、演算式を演算結果に置き換える。
（２）共通式の削除による最適化
繰り返し現れるが演算結果が等しい演算式を共通式という。２回目以降に現れる共通式を最初の共通式の結果で置き換える。
【０００７】
（３）ループの最適化
ループ内に、ループを回っている間は演算結果が変わらない演算式がある場合は、その演算式をループ内からループの直前に移動する。
（４）レジスタ割付けによる最適化
外部メモリ等のアクセスタイムが長い場所に格納されている変数などのうち、アクセスが頻繁に行われる変数については、その変数をマイクロコンピュータの内部レジスタなどのようにアクセスタイムが短い場所におくことにより、データの転送時間や演算時間が短縮される。
【０００８】
（５）式の演算順序の変更による最適化
演算結果を変えない範囲で、演算の順序を変更することで効率化を図る。例えば、ａｂ＋ａｃとａ（ｂ＋ｃ）とは同じ演算結果が得られるが、前者の式では（ａ×ｂ）の演算結果と（ａ×ｃ）の演算結果とを加算し、演算回数は３回となる。後者の式では、（ｂ＋ｃ）を演算した結果とａとを乗算し、演算回数は２回となる。この場合、演算結果は同じであるが、後者のほうが演算回数が削減され、効率が良いオブジェクトプログラムが得られる。
【０００９】
（６）二重定義の削除による最適化
１つの変数が二重に定義されており、初めに定義されてから次に定義されるまでの間にその定数が使用されない場合、初めに変数を定義している式を削除する。
（７）基本ブロックをまたがって移動する命令の削除による最適化
基本ブロックとは、ソースプログラムを構成する文の集合体であり、その初めと終わりとの間には分岐がなく、連続している単位をいう。ある基本ブロックに対して複数の基本ブロックから同じ命令が渡ってくる場合には、その命令を移動先の基本ブロックのみにし、移動元の基本ブロックの命令を削除する。
【００１０】
（８）命令の置き換え
同じ処理結果が得られるが演算速度が高速な命令が存在する場合には、その高速な命令に置き換える。
この他にも、種々の最適化方法がある。
【００１１】
【発明が解決しようとする課題】
従来のプログラム変換装置においては、予め統計的に決定された最も効率がよくなるであろう順番で複数の最適化方法を実行している。しかし、このように最適化方法とその実行順とが一定である場合には、ある特定のソースプログラムでは最適なオブジェクトを生成できるが、他のソースプログラムでは最適化が十分でないことがある。
【００１２】
アーキテクチャに依存する部分での最適化では、入力されるソースプログラムによって最適化方法やその実行順を変えることにより、最適化のかかるパターンが多くなり、よいオブジェクトが生成できる可能性がある。
本発明の目的は、ソースプログラムに応じて最適化方法とその実行順とを自動的に選択し、常に効率良い最適化を行なうことができるプログラム変換装置及びプログラム変換方法を提供することである。
【００１３】
【課題を解決するための手段】
上記した課題は、ソースプログラムから、各種最適化方法毎に処理対象となる命令の数を最適化因子として集計する情報解析部と、前記最適化因子に基づいてき最適化方法とその実行順を選択する最適化選択部と、該最適化選択部により選択された実行順で選択された最適化方法を実行する最適化処理部とを有することを特徴とするプログラム変換装置により解決する。
【００１４】
また、上記の課題は、ソースプログラムから、各種最適化処理毎に処理対象となる命令の数を最適化因子として集計する工程と、前記最適化因子に応じて最適化方法とその実行順を選択する工程と、選択した最適化方法を選択した実行順で実行する工程とを有することを特徴とするプログラム変換方法により解決する。
なお、本発明において以下に説明する処理ブロックとは、基本ブロックを指す場合と、一連の処理を実行する複数の基本ブロックの集合体を指す場合とがあるが、いずれも場合でも発明の原理は同じである。
【００１５】
本発明においては、各種最適化方法毎に最適化処理対象となる命令の数を集計し、それを各最適化処理方法の最適化因子として取得する。例えば、レジスタ割付けによる最適化に関して最適化因子を集計するには、外部メモリ等のアクセスタイムが長い場所に格納されている変数のうち、アクセスが頻繁に行われる変数（アクセス回数が所定数以上の変数）に対してアクセスを行なう命令の数を集計する。その集計した値がレジスタ割付けによる最適化に関する最適化因子となる。
【００１６】
また、二重定義の削除による最適化に関して最適化因子を集計するには、二重定義の関係にある命令の数を集計する。その集計した値が二重定義の削除による最適化に関する最適化因子となる。
更に、基本ブロックをまたがって移動する命令の削除による最適化に関する最適化因子を集計するには、基本ブロック間をわたる同じ命令の数を集計する。その集計した値が基本ブロックをまたがって移動する命令の削除による最適化因子となる。
【００１７】
このように、各種の最適化方法に対して処理対象となる命令の数を最適化因子として集計することによりソースプログラムの傾向が分かり、どの最適化方法が最も有効であるかを判断することができる。基本的には、最適化因子が大きいものほど最適化の効果が大きいといえる。従って、例えば最適化因子が大きい最適化方法を優先させて最適化を実行することにより、効率よく最適化が行われる。
【００１８】
なお、ソースプログラム全体について最適化因子を集計し、その集計結果に基づいて最適化方法とその実行順を選択し、選択した最適化方法をソースプログラム全体について実行してもよい。しかし、ソースプログラムを複数の処理ブロックに分割し、処理ブロック毎に最適化の集計、最適化方法とその実行順の選択及び最適化の実行を行なうことにより、より一層効率がよい最適化が可能である。
【００１９】
【発明の実施の形態】
以下、本発明の実施の形態について、添付の図面を参照して説明する。
図１は本発明の実施の形態に係るプログラム変換装置を示す模式図である。プログラム変換装置の入力部１１に入力されたソースプログラムは、従来と同様に、字句解析部１２で字句解析が行われる。また、構文解析部１３は、字句解析後のプログラムの構文を解析して、プログラムを構成する文の階層構成を調べたり、文法的なチェックを行なう。
【００２０】
情報解析部１４は、データの依存関係の解析部１４ａ及び最適化因子の情報収集部１４ｂを有している。データの依存関係の解析部１４ａでは、従来と同様に、構文解析によって得られた構文情報や記号表を基にして、データの依存関係の解析を行い、データの依存関係を記号表等の各種の表に記入したり、入力したソースプログラムに対する内部形式の形で蓄える。このデータの依存関係の解析結果により、最適化により他の部分に影響を与えることがない命令を抽出することが可能になる。
【００２１】
最適化因子の情報収集部１４ｂでは、データの依存関係の解析結果を使用して各種最適化方法毎に処理対象となる命令の数を最適化因子として集計する。
最適化選択部１５では、最適化因子の情報収集部１４ｂで集計した最適化因子の値を基に、適用すべき最適化方法及びその実行順を選択する。そして、最適化処理部１６では、最適化選択部１５で選択された最適化方法を選択された実行順で実行する。
【００２２】
出力部１７では、最適化された内部形式から、アセンブリ言語、絶対番地の機械語、再配置可能な機械語又は他のプログラミング言語などで表現されたコードを生成して出力する。
最適化方法の選択は、以下のように行われる。例えば、図２に示すように、最適化方法及びその実行順をパターン化した５種類の最適化パターン１〜５を用意しておく。そして、ソースプログラムを入力し、最適化因子の集計（情報の収集）を行なった後、最適化因子の値を基に最適化パターン１〜５のいずれか一つを選択し、最適化処理部１５ではその最適化パターンに定められた最適化方法を定められた実行順で実行して、その結果を出力する。
【００２３】
最適化処理の実行は、以下のようにしてもよい。すなわち、図３は、情報収集の結果を基に、最適化方法１〜５のうちから適宜１つを選択して呼び出し、その方法を実行し、その後更に最適化方法１〜５のいずれか１つを選択して呼び出すというようにして、複数回の最適化を実行するものである。
図４は図２の最適化処理例に基づいた最適化の選択処理の一例を示している。この例では、最適化因子をｘ，ｙの２つとし、これらの最適化因子ｘ，ｙの値を直交座標上に示しており、点Ｐはこのプログラムの最適化因子の状態を示している。この例では、点Ｐが第１象限（ｘ＞０、ｙ＞０）にあることから、このプログラムがパターン１で決められた最適化方法と処理順で最適化処理を行なう。なお、点Ｐが第２象限（ｘ＜０、ｙ＞０）又は第３象限（ｘ＜０、ｙ＜０）に位置するときはパターン２で決められた最適化方法と処理順で最適化処理を行ない、第４象限（ｘ＞０、ｙ＜０）に位置するときはパターン３で決められた最適化方法と処理順で最適化処理を行なう。
【００２４】
なお、最適化因子の情報収集部１４ｂは、ある最適化方法の最適化因子をプラスの値とし、別の最適化方法の最適化因子をマイナスの値としてアーキテクチャ毎に決められる初期値から増減し、その集計結果に基づいて最適化方法及びその実行順を選択してもよい。
また、これらの手順はプログラムの処理単位毎に行なえばよいため、一つのソースプログラムでも処理ブロック毎に最適化方法及びその実行順を替えて行なうことができる。これにより、より一層効率が良い最適化がなされる。
【００２５】
以下、更に具体的に本発明について説明する。
図５は二重定義の削除による最適化（以下、最適化Ａという）を示す図である。図５（ａ）に示すように、ソースプログラムでは、基本ブロック内において、変数ａを、「ａ＝ｂ」と「ａ＝ｃ」とに二重定義している。なお、「ａ＝ｂ」を定義した後、「ａ＝ｃ」を定義するまでの間に変数ａは使用されていないとする。この場合、図５（ｂ）に示すように、先の命令「ａ＝ｂ」を削除することにより処理数が削減される。
【００２６】
図６は基本ブロックをまたがって移動する命令の削除による最適化（以下、最適化Ｂという）を示す図である。図６（ａ）に示すように、基本ブロックＢＫ３に制御が渡ってくる２つの基本ブロックＢＫ１，ＢＫ２に共通の命令（「ａ＝ｂ」）がある場合に、図６（ｂ）に示すように、共通の命令をブロックＢＫ３に移動することにより処理数が削減される。
【００２７】
図７，８は最適化方法の実行順を変えたときの処理結果を示す例であり、最適化Ａと最適化Ｂとの実行順によってどのように最適化が行われ、結果が異なるかを示している。
図７（ａ）は、ソースプログラムを構成する基本ブロックＢＫ１，ＢＫ２，ＢＫ３のうち、ブロックＢＫ１，ＢＫ２に命令「ａ＝ｂ」があり、ブロックＢＫ１，ＢＫ２から処理が移るブロックＢＫ３に命令「ａ＝ｃ」があるプログラムである。このプログラムに対し、最適化Ａを実行した後に最適化Ｂを実行したとする。この場合、最初に最適化Ａを実行しても、同一ブロック内に二重定義がなされているわけではないので、図７（ｂ）に示すように、プログラムは変化しない。その後、最適化Ｂを実行すると、図７（ｃ）に示すように、ブロックＢＫ１，ＢＫ２で共通の命令「ａ＝ｂ」がブロックＢＫ３に移動する。このように最適化Ａ→最適化Ｂの順番で最適化を実行すると、最適化処理後のブロックＢＫ３に変数ａに対する二重定義が存在することになり、最適化が十分であるとはいえない。
【００２８】
一方、同じソースプログラムに対し、最適化Ｂを実行した後に最適化Ａを実行したとする。そうすると、図８（ａ）に示すように、最適化Ｂを実行することにより、ブロックＢＫ１，ＢＫ２で共通する命令「ａ＝ｂ」がブロックＢＫ３に移動する。次に、最適化Ａを実行すると、ブロックＢＫ３内で二重定義されている命令「ａ＝ｂ」及び「ａ＝ｃ」とのうち先の命令が削除され、図８（ｂ）に示すように、ブロックＢＫ３には変数ａに関する命令が「ａ＝ｃ」のみとなる。
【００２９】
すなわち、図７（ａ）のソースプログラムについては、最適化Ｂ→最適化Ａの順番で最適化を実行することにより、効率よく最適化することができる。
しかしながら、この順番で最適化を実行すると、最適化が十分でないときがある。図９，１０は他のソースプログラムについて最適化方法の実行順を変えたときの処理結果を示す例である。図９（ａ）は基本ブロックＢＫ１，ＢＫ２，ＢＫ３で構成されたソースプログラムであり、ブロックＢＫ１では命令「ａ＝ｂ」の後に命令「ａ＝ｄ」があり、ブロックＢＫ２では命令「ａ＝ｃ」の後に命令「ａ＝ｄ」がある。そして、ブロックＢＫ１，ＢＫ２からブロックＢＫ３に処理が移る。
【００３０】
このソースプログラムに対し、まず、最適化Ａを行なうと、図９（ｂ）に示すように、ブロックＢＫ１，ＢＫ２では、ａについて二重定義している２つの命令のうち先の命令が削除され、ブロックＢＫ１，ＢＫ２内にはいずれもａについての命令が「ａ＝ｄ」のみとなる。その後、最適化Ｂを行なうと、図９（ｃ）に示すように、ブロックＢＫ１，ＢＫ２に共通の命令「ａ＝ｄ」がブロックＢＫ３に移動する。
【００３１】
一方、図９（ａ）のソースプログラムに対し、まず最適化Ｂを実行すると、図１０（ａ）に示すように、ブロックＢＫ１，ＢＫ２に共通の命令「ａ＝ｄ」がブロックＢＫ３に移動する。その後、最適化Ａを実行しても、図１０（ｂ）に示すように、ブロックＢＫ１，ＢＫ２にはいずれもａについて二重定義がないため、プログラムは変化しない。
【００３２】
このように、図９（ａ）に示すソースプログラムに対しては、最適化Ｂ→最適化Ａの順で最適化を行なうよりも最適化Ａ→最適化Ｂの順番で最適化を実行することにより、効率よく最適化することができる。
以下に、最適化方法の実施順を決定するための最適化因子について説明する。図１１（ａ）は図７（ａ）と同一のソースプログラムであり、図１１（ｂ）はそのソースプログラムにおける最適化因子の計算方法を示す図である。通常、最適化因子は、適用すべき多数の最適化方法毎に用意する必要があるが、ここでは、説明を簡単にするために、最適化方法としては図５に示す二重定義の削除による最適化Ａと、図６に示す基本ブロックをまたがって移動する命令の削除による最適化Ｂとの二つだけであり、最適化因子はＸ（＋Ｘ及び−Ｘ）のみであるとする。また、最適化因子Ｘの初期値は０とする。
【００３３】
最適化因子Ｘは最適化Ａ，Ｂは以下の条件で計算（集計）する。
１．同一ブロック内で同一変数の定義が続く場合、最適化Ａにより処理数が１つ減少するので、「Ｘ＝Ｘ＋１」とする。
２．基本ブロックにまたがって移動する命令がある場合、最適化Ｂにより処理数が命令の個数だけ減少するので、「Ｘ＝Ｘ−命令の個数」とする。
【００３４】
そして、Ｘの値に応じて、最適化方法の実行順を下記表１のように選択する。
【００３５】
【表１】
0003580394.tif 000002
【００３６】
この条件に沿って、図１１（ａ）に示すソースプログラムの最適化因子Ｘを計算すると、図１１（ｂ）に示すように、最適化因子Ｘの計算結果は−３となる。従って、この場合は、最適化Ｂ→最適化Ａの順で処理を行う。そうすると、図８に示すように、効率よく最適化が行われる。
一方、図１２（ａ）に示すソースプログラムの最適化因子を計算すると、図１２（ｂ）に示すように、最適化因子Ｘの計算結果は０となり、最適化Ａ→最適化Ｂの順番で処理を行なう。この場合、図９に示すように最適化されるので、効率よく最適化が行われる。
【００３７】
このように、本実施の形態では、最適化方法毎に処理対象の命令の数を最適化因子として集計し、その結果に基づいて最適化方法及びその実行順を自動的に選択して最適化を行なうため、最適化の効率がよく、プログラムサイズの縮小、処理速度のより一層の向上や、メモリ使用量のより一層の減少が達成される。
なお、上述の実施の形態においては、最適化方法として二重定義の削除による最適化及び基本ブロックをまたがって移動する命令の削除による最適化の場合について説明したが、本発明が適用可能な最適化方法はこれに限定されるものではなく、その他の最適化方法についても適用できることは勿論である。この場合、最適化方法毎にその処理対象となる命令の数を集計して、その値を最適化因子とする。
【００３８】
【発明の効果】
以上説明したように、本発明に係るプログラム変換装置によれば、最適化選択部において各種最適化方法毎に処理対象となる命令の数を最適化因子として集計し、適用すべき最適化方法及びその実行順を選択して、選択された最適化方法及び実行順で最適化処理部において最適化処理を実行するので、効率が良い最適化を行なうことができて、プログラムサイズの減少、処理速度の向上及びメモリ使用量の減少などのソースプログラムに応じた最適化がなされる。
【００３９】
また、本発明に係るプログラム変換方法によれば、ソースプログラムから各最適化方法毎に処理対象となる命令の数を最適化因子として集計し、その最適化因子の値に応じて最適化方法及びその実行順を決定するので、常にソースプログラムに応じた効率よい最適化がなされる。これにより、プログラムサイズの減少、処理速度の向上及びメモリ使用量の減少等の効果が得られる。
【図面の簡単な説明】
【図１】本発明の実施の形態に係るプログラム変換装置を示す模式図である。
【図２】最適化方法及びその実行順の選択処理の一例を示す模式図である。
【図３】最適化方法及びその実行順の選択処理の他の例を示す模式図である。
【図４】図２に示す選択処理例のより具体的な処理を示す模式図である。
【図５】二重定義の削除による最適化を示す図である。
【図６】基本ブロックをまたがって移動する命令の削除による最適化を示す図である。
【図７】最適化Ａ→最適化Ｂの順で最適化を行ったときの最適化の例を示す図である。
【図８】最適化Ｂ→最適化Ａの順で最適化を行ったときの最適化の例を示す図である。
【図９】最適化Ａ→最適化Ｂの順で最適化を行ったときの最適化の他の例を示す図である。
【図１０】最適化Ｂ→最適化Ａの順で最適化を行ったときの最適化の他の例を示す図である。
【図１１】最適化因子の集計の例を示す図である。
【図１２】最適化因子の集計の他の例を示す図である。
【図１３】従来のプログラム変換装置を示す模式図である。
【符号の説明】
１１  入力部
１２  字句解析部
１３  構文解析部
１４  情報解析部
１４ａ  データの依存関係の解析部
１４ｂ  最適化因子の情報収集部
１５  最適化選択部
１６  最適化処理部
１７  出力部
【図１】
0003580394.tif 000003
【図２】
0003580394.tif 000004
【図３】
0003580394.tif 000005
【図４】
0003580394.tif 000006
【図５】
0003580394.tif 000007
【図６】
0003580394.tif 000008
【図７】
0003580394.tif 000009
【図８】
0003580394.tif 000010
【図９】
0003580394.tif 000011
【図１０】
0003580394.tif 000012
【図１１】
0003580394.tif 000013
【図１２】
0003580394.tif 000014
【図１３】
0003580394.tif 000015