JPH01118931A - プログラム変換方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はプログラム変換方式に関し、特に原始プログラ
ムを目的プログラムに変換する情報処理装置における、
最適化された目的プログラムを生成するに好適なプログ
ラム変換方式に関する。

〔従来の技術〕

従来、プログラム実行時の動的特性を、プログラム変換
の一例としてのコンパイル処理に反映させるものとして
は、特開昭６１−８２２４３号公報に開示された技術が
ある。この技術は、プログラム実行時の変数の参照頻度
を変数ごとに求め、参照頻度の多い変数をレジスタに割
付けることにより、プログラムの最適化を図るものであ
る。

この方法では、コンパイル部が第一コンパイル部と第二
コンパイル部の二つに分かれている。第一コンパイル部
は原始プログラムを読込んで仮の目的プログラムを、ま
ず、生成する。これを、別に設けられたプログラム実行
部で実行し、各変数ごとにその参照回数をカウントして
、参照頻度記憶領域に、変数とその参照回数の対の組と
いう形で記憶する。

第二コンパイル部は、上記参照頻度記憶領域を参照しな
がら、もう−度原始プログラムをコンパイルし、最終的
な目的プログラムを生成する。その際、参照頻度の高い
変数から順にレジスタに割付けるという処理を行うこと
により、最適化された目的プログラムを得るというもの
である。

〔発明が解決しようとする問題点〕

上記従来技術は、プログラム実行時の変数の参照頻度の
みを、プログラム変換の一例としてのコンパイル処理に
反映させるものであり、手続きの呼出し頻度２手続き間
相互の参照頻度や、条件ブランチ命令における条件の成
立頻度等については配慮がなされておらず、レジスタ割
付は以外のコンパイラ処理、または他のプログラム変換
処理には、動的特性データを利用してぃなかった。

本発明は上記事情に鑑みてなされたもので、その目的と
するところは、従来のプログラム変換方式における上述
の如き問題を解消し、精度の良いプログラム動特性を、
レジスタ割付は以外のコンパイル処理を含むプログラム
変換処理にも反映させるようにしたプログラム変換方式
を提供することにある。

〔問題点を解決するための手段〕

本発明の上述の目的は、原始プログラムを目的プログラ
ムに変換するプログラム変換方式において、前記原始プ
ログラムもしくは前記原始プログラムをコンパイルする
過程で一時的に得られる目的プログラムの動的特性を解
析する手段を設け、該解析手段による前記原始プログラ
ムもしくは目的プログラムの動的特性解析結果を利用し
て目的プログラムの生成・最適化を行うことを特徴とす
るプログラム変換方式、または、前記原始プログラムも
しくは前記原始プログラムをコンパイルする過程で一時
的に得られる目的プログラムの動的特性に関するデータ
をユーザが指定することにより、これを利用して目的プ
ログラムの生成・最適化を行うことを特徴とするプログ
ラム変換方式によって達成される。

また、本発明においては、前記解析手段が、動的特性デ
ータの精度を向上させるため、同一のプログラムに対す
る複数の異なる入力による解析結果を積算し、統計処理
を行う如く構成されている点も特徴となる点である・ 〔作用〕 本発明においては、プログラム変換手段は、原始プログ
ラムの他に、プログラム中の各手続きの呼出し頻度２手
続き間相互の参照頻度２条件ブランチ命令における条件
成立頻度等のプログラムの動的特性データを受取り、こ
れらを基に目的プログラムの生成・最適化を行う。

また、上述の目的プログラムの動的特性を解析する装置
は、解析しようとするプログラムへの入力データを一組
以上受取り、それぞれの入力データに対する動的特性デ
ータを積算する等して、統計処理を行った結果を出力す
る。これにより、入力データが個々には偏ったものであ
っても、動的特性データが偏ったものとなることがない
。

なお、上記プログラムの動的特性データは、上記解析装
置から受取る方式の他に、ユーザが指定するようにする
ことも可能であり、この場合にも同様の効果が得られる
。

〔実施例〕

以下１本発明の実施例を図面に基づいて詳細に説明する
。なお、以下の説明においては、本発明をコンパイル方
式として実施する場合を示す。

第１図は、本発明を、手続きのインライン展開による最
適化を行うコンパイラに適用した一実施例を示す構成図
である６手続きのインライン展開とは１手続き呼出し命
令を、呼出される手続きの本体と置換えることによって
、呼出し時に起こるレジスタ退避やスタックフレーム生
成等のオーバーヘッドをなくして、実行速度を上げよう
とするものである。なお、第１図において、１は変換前
の原始プログラム、２はコンパイラ、３は一時的な目的
プログラム、４は手続き呼出し頻度解析プログラム、５
はユーザが上記手続き呼出し頻度解析プログラム４に与
える入力データ、６は手続き呼出し頻度解析結果表、７
は最終的な目的プログラムを示している。

第２図は、第１図中の手続き呼出し頻度解析結果表６の
内容の一例を示すものである。ここで、ｓｕｂ　１　、
ｓｕｂ　２等は手続き名、サイズ欄の数字は該手続きの
目的プログラムのコード量をバイトで表わしたもの、参
照頻度欄の数字は該手続きが実行中、何回呼出されたか
を示すものである。

以下、上述の如く構成された本実施例の動作を説明する
。

まず、コンパイラ２は、原始プログラム１を読込み、イ
ンライン展開最適化を行わずに、−時的な目的プログラ
ム３を出力する６次に、手続き呼出し頻度解析プログラ
ム４が、上記−時的目的プログラム３と、ユーザが与え
る入力データ群５を読込んで、目的プログラムの実行を
シュミレートしつつ、目的プログラム中の各手続きが参
照された回数をカウントし、その結果を、手続きコード
のサイズと合わせて、第２図に示した形式で、手続き呼
出し頻度解析結果表６に出方する。この除毛続き呼出し
頻度解析プログラム４は、各入力データに対して得られ
た手続き呼出し頻度を積算した結果を出力するようにし
ておく。

最後に、コンパイラ２は１手続き呼出し頻度解析結果表
６を読込んで、各手続きが呼出される頻度と、その手続
きのサイズを判断材料として、手続きをインライン展開
するか否かを決定し、その決定に基づいて必要ならばイ
ンライン展開処理を行い、最終的な目的プログラム７を
出力する。

第３図は、コンパイラ２が手続き呼出しをインライン展
開するかどうかを決定するときの処理を示す動作フロー
チャートである。

ステップ３１では、該当手続きコードのサイズを手続き
呼出し頻度解析結果表６から読込む、ステップ３２では
、そのサイズが予め定めた基準値を越えているか調べ、
もし、越えていたら、ステップ３６に進む、越えていな
い場合は、ステップ３３で、該当手続きの呼出し頻度を
前記手続き呼出し頻度解析結果表６から読込む。

ステップ３４では、読込んだ頻度（回数）が予め定めた
基準値を越えているか調べ、越えていなかったら、ステ
ップ３６．に進む、越えていたら、ステップ３５で該当
手続きをインライン展開する。ステップ３６では１手続
きをインライン展開せず５通常の手続き呼出しの処理を
行う。

上記実施例は、手続きのインライン展開最適化を行うコ
ンパイラに本発明を適用し゛た例を示すものであったが
、本発明は、手続きコード配置の最適化を行うコンパイ
ラに適用することもできる。

手続きコード配置の最適化とは、呼出し一被呼出し関係
の密な手続き同志を、コード上で近くに配置することに
より、時間的に連続して実行される可能性の高い命令列
を、物理的に近くに配置することである。これにより１
手続き呼出し命令、すなわち、サブルーチン命令をロン
グジャンプからショートジャンプに変えることが可能に
なり、■コード量、実行時間を減少することができる■
命令キャッシュが有効となる可能性が高くなる ■仮想メモリにおけるページフォールトの可能性が少な
くなる 等のメリットが生ずる。

本発明を、手続きコード配置の最適化を行うコンパイラ
に適用した実施例の構成図は、第１図と同様であるが、
前記手続き参照頻度結果表の形式を第４図のように変更
する。第４図で縦軸は呼出す側の手続きの名前、横軸は
呼出される側の手続きの名前を表わす０図中の数字は呼
出し回数で、例えば、横軸のｍａｉｎと縦軸の５ｕｂｌ
とが交わったところに“１”とあるのは、ｍａｉｎが５
ｕｂｌを１回だけ呼出すということを意味している。こ
れにより、任意の二つの手続き間の参照関係の密接さを
計算することができ、この結果に基づいて手続きコード
の再配置による最適化をコンパイラが行うことができる
。

第５図は、再配置の一例を示すもので、当初、同図（、
）に示す如＜　５ｕｂｌ、５ｕｂ２．・・・・の順で１
手続きコードが並んでいたものを１手続き相互の参照頻
度解析結果から、５ｕｂｌとａｕｂ３の参照関係が密で
あることがわかったため、第５図（ｂ）に示す如く５ｕ
ｂ２，５ｕｂｌ、５ｕｂ３．”・・の順にコードを再配
置したものである。

これらの再配置は、必ずしも、コンパイラが目的プログ
ラム中の手続きコードの物理的な順序を変更することの
みによって実現されるものではなく、例えば、それに相
当するリンカへの制御命令を埋込むことによって、メモ
リに配置する順序を制御するという方法でも実現できる
。

また、別の実施例として、目的プログラム中の条件ブラ
ンチ命令における条件の設定を最適化するコンパイラに
本発明を適用することも可能である。ここで、ブランチ
命令における条件の設定を最適化するとは、目的プログ
ラム中の条件ブランチにおいて、条件が成立する頻度、
すなわちブランチが起こる頻度を低くするように条件を
設定することである。これにより、パイプライン計算機
において先行制御を妨げるような制御の移動が起こるこ
とを減らすことができる。

上述の、最適化を行うコンパイラに本発明を適用した実
施例の構成図は、第１図と同様である。

但し、手続き参照頻度解析プログラムではなく、条件成
立頻度解析プログラムを置き、−時的な目的プログラム
中の各条件ブランチの条件成立回数と条件不成立回数を
カウントするようにし、その解析結果を第６図に示す如
く出力する。

第６図は、条件ブランチ命令のある行番号とその命令、
命令成立頻度（回数）と、条件不成立頻度（回数）を目
的プログラム中のすべての条件ブランチ命令について記
したものである。

また、第７図は、コンパイラが行う条件設定の最適化の
例を示すものであり、当初、同図（ａ）に示す如きコー
ドになっていたものを、解析の結果ｒＢＥＱ　Ｌ４ｊの
命令の条件成立頻度が、不成立ｊｌＨＦに比べて著しく
高いことがわかったため、同図（ｂ）に示す如く、条件
をｒＥＱＪからその否定のｒＮＥＪに反転し、それに従
って、これに続くコードとブランチ先のコープを交換し
たことを示す。

また、更に別の実施例として、目的プログラム中のルー
プの最適化、すなわち命令のループ外への移動、ループ
の変換等を行うコンパイラに本発明を適用することも可
能である。ここで、ループの最適化は、対象となるルー
プを数多く回ったときに初めて効果があるものであって
、はんの数回回っただけでは、実質上効果がないばかり
か、却ってオーバーヘッドが大きくなる場合もある。更
に、ループ最適化を行うためのデータフロー解析等、コ
ンパイル時間も無駄になる可能性がある。

そこで、各ループ中の命令の実行回数を動的に求めて、
それがある基準値を越えたときに初めてループの最適化
を行うようにすれば、コンパイル時間の節約になり、し
かも、適切な目的プログラムを生成できる。

更に別の実施例として、変数領域の配置を最適化するコ
ンパイラに本発明を適用することも可能である。これは
、大域変数の如くプログラムの実行前にメモリ領域をと
っておくような変数に対するアクセスコストを、その配
置を考えることによって、より軽減しようとするもので
ある。

このような変数は、多くのマシンで、 番地＝基底番地＋変位 という形で表わされる。このとき、基底番地は、レジス
タに入れられるのが普通である。連続して参照されるよ
うな大域変数は、一つの基底番地から指定できるように
しておくのが望ましい、そうでないと、その基底番地を
一旦レジスタにロードしてからアクセスすることになる
からである。

そこで、各大域変数について、それが参照されたときの
タイムスタンプを記録しておくようにして、ある時間帯
ではどのような変数が多く参照されるかがわかるように
すれば、そのような変数同志を近くに配置することによ
って同じ基底番地から指定できるようになる。このとき
の基になるデータは、プログラムを動的に実行させて初
めて得ることができる。

以上の説明では、前述の目的プログラムの動的特性を解
析する装置は、ユーザが指定した入力入力データを一度
に取込み処理を行っていたが、本発明はこれに限定され
るものではなく、例えば、−回のコンパイルでは一種類
の入力データしか取込まないが、その解析結果を保存し
ておき、同一原始プログラムの新たなコンパイルの際に
は、その解析結果と、上で保存しておいた解析結果とを
積算して新たな解析結果を得るという方法も可能である
。

更に、以上の説明では、コンパイラが一時的に出力した
目的プログラムを用いて動的特性を得ていたが１本発明
はこれに限定されるべきものではなく、他の方法でも実
現し得るものである０例えば、原始プログラムを読込ん
でインターブリットしながらその動的特性を解析する装
置を設け、その結果をコンパイラが利用するという構成
も可能である。この場合の構成例を、第８図に示す。

ここでは、原始プログラム１と入力データ群５を動的特
性解析プログラム８１が読込み、手続き参照頻度等の動
的特性を解析し、動的特性解析結果表８２に出力する。

その後、コンパイラ２が、原始プログラム１と、上記動
的特性解析結果表８２から最終的な目的プログラム７を
生成するというものである。

上記実施例によれば、プログラム中の手続き呼出し頻度
１手続き間相互の参照頻度２条件ブランチ命令における
条件成立頻度等のプログラムの動的特性を利用して、よ
り効率のよい目的プログラムを生成することが可能とな
る。更に、複数の入力データに対する動的特性解析結果
を積算することにより、特性結果の精度を高めることが
できるという効果もある。

次に、本発明を、より一般的なプログラム変換に適用し
た場合の実施例を示す。

第９図は、本発明を、Ｃ言語の如きレジスタ変数宣言の
ある言語で、参照頻度の高い変数をレジスタに割付ける
宣言をするような原始プログラム゛６゛へする実施例を
示す構成図である。記号１〜３および５は、先に第１図
、第８図に示したと同じ構成要素を示しており、４Ａは
変数参照頻度解析プログラム、６Ａは変数参照頻度解析
結果表、７Ａは最適化されたプログラム、９はプログラ
ム変換プログラムを示している。

第１０図は上記変数参照頻度解析結果表６Ａの内容の一
例を示すものである。以下、第９図、第１０図に基づい
て、本実施例の動作を説明する。

まず、コンパイラ２が原始プログラム１を読込み、目的
プログラム３を出力する。変数参照頻度解析プログラム
４Ａは、目的プログラム３と、ユーザが与える入力デー
タ５を読込み、目的プログラムの実行をシュミレートし
つつ、目的プログラム中の各変数が参照された回数をカ
ウントする。

、入力データ５を変えて、変数参照頻度解析プログラム
４Ａの実行を繰り返す、変数参照頻度解析プログラム４
Ａは、各入力データに対して得られた変数参照頻度を、
その都度積算する。実行を一定回数以上繰り返したら、
変数参照頻度解析プログラム４Ａは、積算結果を統計処
理し、第１０図の形式で前記変数参照頻度解析結果表６
Ａに出力する。この変数参照頻度解析結果表６Ａの内容
を、プログラム変換プログラム９が読込んで、参照頻度
の多い変数をレジスタに割付ける宣言を行うか否かを、
他の判断材料（変数の属性等）も参考にして決定する。

この決定に基づき、プログラム変換プログラム９は、原
始プログラム１を読込んで、必要な変換を施して最適化
されたプログラム７Ａを出力する。

上述の実施例を、呼出し頻度の多い手続きの本体を呼出
した場所に展開（インライン展開）する最適化変換に応
用する場合には、上記第９図の変数参照頻度解析プログ
ラム４Ａを前述の手続き呼出し頻度解析プログラム４に
、また、変数参照頻度解析結果表６Ａを手続き呼出し頻
度解析結果表６に、それぞれ変更すれば良い、他の構成
は第９図の通りである。

本実施例における各部の動作は、手続き呼出し頻度解析
結果表６を出力するまでは上述の通りであり（但し、「
変数」が「手続き」に、「参照」がｒ呼出し」に置き替
わる）、以後は、手続き呼出し頻度解析結果表６をプロ
グラム変換プログラム９が読込んで、番手続き呼出しの
頻度と、呼出される手続きのサイズを判断材料として、
先に第３図に示したと同様の処理に従って１手続き呼出
しをインライン展開するか否かを決定する。

プログラム変換プログラム９は、原始プログラム１を読
込み、上記決定に基づいた変換を行い、最適化されたプ
ログラム７Ａを出力する。

同様に、手続きのインライン展開を応用した手続き本体
の配置替えによる最適化も実施することが可能である。

手続き本体の配置替えによる最適化による効果等につい
ては、前述の手続きコード配置の最適化と同様である。

〔発明の効果〕

以上述べた如く、本発明によれば、原始プログラムを目
的プログラムに変換するプログラム変換方式において、
前記原始プログラムもしくは前記原始プログラムをコン
パイルする過程で一時的に得られる目的プログラムの動
的特性を解析する手段を設けて、該解析手段による前記
原始プログラムもしくは目的プログラムの動的特性解析
結果を利用して目的プログラムの生成・最適化を行うよ
うに、または、前記原始プログラムもしくは前記原始プ
ログラムをコンパイルする過程で一時的に得られる目的
プログラムの動的特性に関するデータをユーザが指定す
ることにより、これを利用して目的プログラムの生成・
最適化を行うようにしたので、精度の良いプログラム動
特性を、レジスタ割付は以外のコンパイル処理を含むプ
ログラム変換処理にも反映させるようにしたプログラム
変換方式を実現できるという顕著な効果を奏するもので
ある。

【図面の簡単な説明】

第１図は本発明をコンパイラに適用した一実施例を示す
構成図、第２図は手続き呼出し頻度解析結果表の内容の
一例を示す図、第３図はインライン展開するかどうかを
決定する処理を示す動作フローチャート、第４図は手続
き参９照頻度結果表の形式の一例を示す図、第５図は手
続きコードの再配置の一例を示す図、第６図は条件ブラ
ンチの条件成立頻度解析結果表の内容の一例を示す図、
第７図はコンパイラが行う条件設定の最適化の例を示す
図、第８図は本発明をコンパイラに適用した他の実施例
を示す構成図、第９図は本発明をプログラム変換に適用
した一実施例を示す構成図、第１０図は変数参照頻度解
析結果表の内容の一例を示す図である。 １：原始プログラム、２：コンパイラ、３：目的プログ
ラム、４：手続き呼出し頻度解析プログラム、４Ａ：変
数参照頻度解析プログラム、５：入力データ、６：手続
き呼出し頻度解析結果表、６Ａ：変数参照頻度解析結果
表、７：（最終的な）目的プログラム、７Ａ：最適化さ
れたプログラム、８１：動的特性解析プログラム、８２
：動的特性解析結果表。 第７目 第２旧 第４図

Claims (1)

1. 【特許請求の範囲】 １、原始プログラムを目的プログラムに変換するプログ
   ラム変換方式において、前記原始プログラムもしくは前
   記原始プログラムをコンパイルする過程で一時的に得ら
   れる目的プログラムの動的特性を解析する手段を設けて
   、該解析手段による前記原始プログラムもしくは目的プ
   ログラムの動的特性解析結果を利用して目的プログラム
   の生成・最適化を行うことを特徴とするプログラム変換
   方式。 ２、前記解析手段が解析対象とする前記原始プログラム
   もしくは目的プログラムの動的特性が、１）各手続きの
   呼出し頻度 ２）手続き相互間の参照頻度 ３）条件ブランチ命令における条件成立頻度４）ループ
   中の命令の実行回数 ５）時間的に連続して参照される頻度の高い変数の組 または、これらを組合わせたものであることを特徴とす
   る特許請求の範囲第１項記載のプログラム変換方式。 ３、前記解析手段が、同一のプログラムに対する複数の
   異なる入力による解析結果を積算し、統計処理を行う如
   く構成されていることを特徴とする特許請求の範囲第１
   項または第２項記載のプログラム変換方式。 ４、原始プログラムを目的プログラムに変換するプログ
   ラム変換方式において、前記原始プログラムもしくは前
   記原始プログラムをコンパイルする過程で一時的に得ら
   れる目的プログラムの動的特性に関するデータをユーザ
   が指定することにより、これを利用して目的プログラム
   の生成・最適化を行うことを特徴とするプログラム変換
   方式。 ５、前記ユーザが指定する前記原始プログラムもしくは
   目的プログラムの動的特性に関するデータが、 １）各手続きの呼出し頻度 ２）手続き相互間の参照頻度 ３）条件ブランチ命令における条件成立頻度４）ループ
   中の命令の実行回数 ５）時間的に連続して参照される頻度の高い変数の組 または、これらを組合わせたものに対応するデータであ
   ることを特徴とする特許請求の範囲第４項記載のプログ
   ラム変換方式。 ６、前記ユーザが指定する前記原始プログラムの動的特
   性に関するデータが、前記原始プログラム中にコメント
   の形で埋込まれる如く構成されていることを特徴とする
   特許請求の範囲第４項または第５項記載のプログラム変
   換方式。