JPS617946A - 最適化コンパイル方式 - Google Patents
最適化コンパイル方式Info
- Publication number
- JPS617946A JPS617946A JP59127435A JP12743584A JPS617946A JP S617946 A JPS617946 A JP S617946A JP 59127435 A JP59127435 A JP 59127435A JP 12743584 A JP12743584 A JP 12743584A JP S617946 A JPS617946 A JP S617946A
- Authority
- JP
- Japan
- Prior art keywords
- program
- information
- execution
- optimization
- data
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔発明の利用分野〕
本発明は、コンパイラ言語を用いて書かれたプログラム
の自動翻訳の最適化方式に係り、特に、大量のデータを
高速に処理する必要のある電子計算機の利用分野のプロ
グラムについて、各プログラム特有の実行環境に合った
最適化処理を行うコンパイル方式に関する。
の自動翻訳の最適化方式に係り、特に、大量のデータを
高速に処理する必要のある電子計算機の利用分野のプロ
グラムについて、各プログラム特有の実行環境に合った
最適化処理を行うコンパイル方式に関する。
〔９発明の背景〕
大量のデータを高速に処理することが要求される科学技
術計算の分野などでは、良いオブジェクト・プログラム
（実行時間の短かいオブジェクト・プログラム）を生成
するために、コンパイラには高度の最適化が要求される
。
術計算の分野などでは、良いオブジェクト・プログラム
（実行時間の短かいオブジェクト・プログラム）を生成
するために、コンパイラには高度の最適化が要求される
。
従来、この種のコンパイラは生成したオブジェクト・プ
ログラムの実行時間を短縮するために。
ログラムの実行時間を短縮するために。
入力されたソースプログラムを解析し、制御の流れ、デ
ータの流れに関する情報を収集し、共通部分式の削除、
ループ内不変式のループ外への移動、ループ内の演算強
度の削減等の、大局的最適化を行っている。しかしなが
ら、ループに開かる最適化については、ループは多数回
実行されるという前提に立って最適化操作を行うため、
実行時にループが実行されない度合が圧倒的に多い場合
には。
ータの流れに関する情報を収集し、共通部分式の削除、
ループ内不変式のループ外への移動、ループ内の演算強
度の削減等の、大局的最適化を行っている。しかしなが
ら、ループに開かる最適化については、ループは多数回
実行されるという前提に立って最適化操作を行うため、
実行時にループが実行されない度合が圧倒的に多い場合
には。
最適化操作を行ったために、かえって実行時間が長くな
ってしまう場合があるという欠点があった。
ってしまう場合があるという欠点があった。
また、一般に電子計算機は、通常のメモリに比ベてアク
セス速度が極めて高速なレジスタ類を備えており、この
レジスタ類を有効に活用することが、プログラム実行時
間の短縮のために極めて重要であるが、ハードウェア・
アーキテクチャ上の制約から、レジスタの個数は限られ
ているため、コンパイラが実行回数が多いと推定して、
重点的にレジスタ類を割り当てた箇所と、そうでない場
所ではプログラムの実行時間に大きな差が出来てしまう
。従来、実行回数の推定は、ループのネストの深さなど
を基にし１て行っているが、コンパイラの推定と、実際
の実行回数とが一致せず、結果的にレジスタ類を効果的
に使用できていないという欠点もあった。
セス速度が極めて高速なレジスタ類を備えており、この
レジスタ類を有効に活用することが、プログラム実行時
間の短縮のために極めて重要であるが、ハードウェア・
アーキテクチャ上の制約から、レジスタの個数は限られ
ているため、コンパイラが実行回数が多いと推定して、
重点的にレジスタ類を割り当てた箇所と、そうでない場
所ではプログラムの実行時間に大きな差が出来てしまう
。従来、実行回数の推定は、ループのネストの深さなど
を基にし１て行っているが、コンパイラの推定と、実際
の実行回数とが一致せず、結果的にレジスタ類を効果的
に使用できていないという欠点もあった。
本発明の目的は、上述のように従来ソース・プログラム
という静的な情報のみを用いて行っていた最適化処理に
おいて、その最適化の効果をさらに向上させるコンパイ
ラ方式を提供することにある。
という静的な情報のみを用いて行っていた最適化処理に
おいて、その最適化の効果をさらに向上させるコンパイ
ラ方式を提供することにある。
本発明は、ソース・プログラムを一度コンパイルして生
成し、たオブジェクト・プログラムを１回もしくは複数
回実行し７、その実行状態を解析して得られる情報を入
力して再度コンパイルすることを特徴とするものである
。
成し、たオブジェクト・プログラムを１回もしくは複数
回実行し７、その実行状態を解析して得られる情報を入
力して再度コンパイルすることを特徴とするものである
。
Ｃ発明の実施例〕
以下１本発明の一実施例を図面により詳細に説明する。
第１図は本発明のコンパイル方式の一実施例を示したも
のである。１０１の記憶媒体等からソース・プログラム
、及び、ＩＯ２のカード等がら実行時情報（プログラム
実行時の動的状態を示す情報）を採取する指令を入力し
て、１回目のコンパイル１０３を行ない、生成されたオ
ブジェクト・プログラムを１０４の記憶媒体等に格納す
る。次にこの生成されたオブジェクト・プログラムを、
１０５の記憶媒体等に予め格納されている実行データを
用いて１回もしくは複数回実行する（１０６）。この時
、先にカード等から入力しておいた実行時情報を採取す
る指令に従って実行時情報を採取し１．１０７の記憶媒
体等に蓄積する。次に。
のである。１０１の記憶媒体等からソース・プログラム
、及び、ＩＯ２のカード等がら実行時情報（プログラム
実行時の動的状態を示す情報）を採取する指令を入力し
て、１回目のコンパイル１０３を行ない、生成されたオ
ブジェクト・プログラムを１０４の記憶媒体等に格納す
る。次にこの生成されたオブジェクト・プログラムを、
１０５の記憶媒体等に予め格納されている実行データを
用いて１回もしくは複数回実行する（１０６）。この時
、先にカード等から入力しておいた実行時情報を採取す
る指令に従って実行時情報を採取し１．１０７の記憶媒
体等に蓄積する。次に。
１０１の記憶媒体等からソース・プログラムを再び入力
し、同時番こ、１０８のカード等から実行時情報の取込
みを指示して、記憶媒体１０７の実行時情報を入力し、
２回目のコンパイル１０９を行い、生成されたオブジェ
クト・プログラムを最終オブジェクト・プログラムとし
て１１０の記憶媒体等に格納する。第１図中、１０１，
１０４，１０５．１０７，１．１０の記憶媒体等は同一
のものであっても別のものでもよい。
し、同時番こ、１０８のカード等から実行時情報の取込
みを指示して、記憶媒体１０７の実行時情報を入力し、
２回目のコンパイル１０９を行い、生成されたオブジェ
クト・プログラムを最終オブジェクト・プログラムとし
て１１０の記憶媒体等に格納する。第１図中、１０１，
１０４，１０５．１０７，１．１０の記憶媒体等は同一
のものであっても別のものでもよい。
第２図に実行時情報の一例を示す。即ち、実行時情報と
し、では、ソース・プログラムの各文毎に、その実行回
数を採取する。第２図において１例えば文番号１０の文
は３０００回実行実行たことを意味し、ている。他の文
番号についても同様である。
し、では、ソース・プログラムの各文毎に、その実行回
数を採取する。第２図において１例えば文番号１０の文
は３０００回実行実行たことを意味し、ている。他の文
番号についても同様である。
なお、これらの文番号には、コンパイラが作成する内部
文番号も入る。第２図は実行回数を単純に累積し、て実
行時情報とする例であるが、各文の実行毎に予め定める
か、あるいは実行回数それ自身により決定される重みを
加味した値詮実行時情報としでもよい。
文番号も入る。第２図は実行回数を単純に累積し、て実
行時情報とする例であるが、各文の実行毎に予め定める
か、あるいは実行回数それ自身により決定される重みを
加味した値詮実行時情報としでもよい。
第３図は本発明を適用したコンパイラの処理フロー図で
ある。以下、第３図の各ステップについて説明する。
ある。以下、第３図の各ステップについて説明する。
ステップ２０１：
ソース・プログラムを入力し、構文の解析等を行って、
最適化処理に適した形式の中間形式テキストに変換する
。
最適化処理に適した形式の中間形式テキストに変換する
。
ステップ２０２：
制御の流れの解析を行う。ここでは、２回めのコンパイ
ル（第１図の１０９）では、実行時情報を参照して、基
本ブロックと呼ばれる制御の流れの解析の基本晰位とな
るプログラムの区域毎に作成される基本ブロック情報テ
ーブル中に、実行回数情報を設定する。
ル（第１図の１０９）では、実行時情報を参照して、基
本ブロックと呼ばれる制御の流れの解析の基本晰位とな
るプログラムの区域毎に作成される基本ブロック情報テ
ーブル中に、実行回数情報を設定する。
ステップ２０３：
最適化処理に必要な対象データの選択を行う。
即ち、大規模なプログラムに対して、出現する全データ
に対して最適化処理に必要な種々の解析を行うことは、
メモリ、処理速度の制約により不可能、も１． ＜は、
各種資源の有効作用という観点がらみて望ましくないた
め、最適化の効果が最大となるよう、データの属性、参
照回数を考慮して。
に対して最適化処理に必要な種々の解析を行うことは、
メモリ、処理速度の制約により不可能、も１． ＜は、
各種資源の有効作用という観点がらみて望ましくないた
め、最適化の効果が最大となるよう、データの属性、参
照回数を考慮して。
最適化対象データを選択する。この場合、２回目のコン
パイルでは、基本ブロック情報テーブル中に設定した実
行回数情報を利用して、参照回数の推定を行う二とによ
り、最適化の効果が最大に発揮されるような最適化対象
変数の選択を行う。
パイルでは、基本ブロック情報テーブル中に設定した実
行回数情報を利用して、参照回数の推定を行う二とによ
り、最適化の効果が最大に発揮されるような最適化対象
変数の選択を行う。
ステップ２０４：
データの流れの解析を行い、次の最適化操作を行うのに
必要なデータの定義参照の関係の情報を収集する。
必要なデータの定義参照の関係の情報を収集する。
ステップ２０５ニ
スフ−ツブ２０４で収集した情報を基にして、共通部分
式の削除、ループ内不変式のループ外への移動、ループ
内の演算強度の削減、冗長な式の削除、冗長な弔純代入
文の削除等の大局的最適化処理を行う。ここで、２回め
のコンパイルにおいては、ステップ２０２で基本ブロッ
ク情報テーブル中に設定し７た実行回数情報を利用して
、ある一定の回数以下Ｌ７か実行されていないループに
対して。
式の削除、ループ内不変式のループ外への移動、ループ
内の演算強度の削減、冗長な式の削除、冗長な弔純代入
文の削除等の大局的最適化処理を行う。ここで、２回め
のコンパイルにおいては、ステップ２０２で基本ブロッ
ク情報テーブル中に設定し７た実行回数情報を利用して
、ある一定の回数以下Ｌ７か実行されていないループに
対して。
ループ内不変式のループ外への移動、ループ内の演算強
度の削減等の処理を行わないようにする。
度の削減等の処理を行わないようにする。
あるいは、ある一定回数以下しか実行されていないパス
に対し、では、共通部分式の削除の処理を行わないよう
にするなどして、積極的に実行されない部分に対して最
適化処理を施、ニジ、全体として実行時間が増加するの
を防止する。
に対し、では、共通部分式の削除の処理を行わないよう
にするなどして、積極的に実行されない部分に対して最
適化処理を施、ニジ、全体として実行時間が増加するの
を防止する。
ステップ２０６：
データの記憶域への割り付けを行う。記憶域中の割り当
てられた場所により、ハードウェア的あるいはソフトウ
ェア的にアクセス速度が異なるので、参照頻度の高いデ
ータをアクセス速度の速い場所に割り付けることにより
、プログラムの実行時間の短縮を図ることができる。２
回めのコンパイルでは、実行回数情報を利用し、て参照
頻度を正確に推定し・、最適なデータの記憶域への割り
付けを行う。
てられた場所により、ハードウェア的あるいはソフトウ
ェア的にアクセス速度が異なるので、参照頻度の高いデ
ータをアクセス速度の速い場所に割り付けることにより
、プログラムの実行時間の短縮を図ることができる。２
回めのコンパイルでは、実行回数情報を利用し、て参照
頻度を正確に推定し・、最適なデータの記憶域への割り
付けを行う。
ステップ２０７：
レジスタの割り付けを行う。コンパイラは、実行回数が
多いと判断した区域内で、なるべく必要なデータがレジ
スタ上に保持されるようにレジスタを割り付けるが、実
行回数の推定が誤まっていると、実行時に、メモリへの
アクセスの回数が多くなり、実行時間の増加をもたらす
。２回めのコンパイルでは実行回数の推定にステップ２
０２で設定し、た基本ブロック情報テーブル中の実行回
数情報を用い、実行時にメモリへのアクセス回数が最小
となるようなレジスタ割り付けを行う。
多いと判断した区域内で、なるべく必要なデータがレジ
スタ上に保持されるようにレジスタを割り付けるが、実
行回数の推定が誤まっていると、実行時に、メモリへの
アクセスの回数が多くなり、実行時間の増加をもたらす
。２回めのコンパイルでは実行回数の推定にステップ２
０２で設定し、た基本ブロック情報テーブル中の実行回
数情報を用い、実行時にメモリへのアクセス回数が最小
となるようなレジスタ割り付けを行う。
ステップ２０８：
コード生成を行う分岐先アドレスがペースレジスタと称
されるレジスタの内容と、例えば４０９５ （１ページ
）以下の変位の和によって表現されるような分岐命令を
もつハードウェアにおいて、１つのペースレジスタの値
によって分岐先アドレスを表現できるプログラムの範囲
をリージョンと呼ぶが、リージョン境界を越える分岐命
令については、ペースレジスタの更新を行う命令が必要
となり、リージコン内の分岐に比べ命令が余計に必要と
なる。分岐命令の実行回数を推定して、回数の多い４０
９５バイト以内はなるべくリージョン内分岐となるよう
に、リージョンを設定することにより実行時間の短縮を
図ることができる。最もネストの深いループの途中では
リージョンをなるべく切らないというような処理は静的
情報のみがらも行えるが１分岐の回数の情報も、実行時
情報とし、て採取すれば、２回めのコンパイル時には、
リージョン外分岐の実行回数が最小となるようなリージ
ョン設定を行う二とができる。また、分岐以外でも、リ
ージョンの境界を制御が渡る際には、ペースレジスタの
更新が必要となるため、第２図に示す実行時情報から、
実行回数の多い箇所ではなるべくリージョンを切らない
ようなリージョン設定をすることもできる。
されるレジスタの内容と、例えば４０９５ （１ページ
）以下の変位の和によって表現されるような分岐命令を
もつハードウェアにおいて、１つのペースレジスタの値
によって分岐先アドレスを表現できるプログラムの範囲
をリージョンと呼ぶが、リージョン境界を越える分岐命
令については、ペースレジスタの更新を行う命令が必要
となり、リージコン内の分岐に比べ命令が余計に必要と
なる。分岐命令の実行回数を推定して、回数の多い４０
９５バイト以内はなるべくリージョン内分岐となるよう
に、リージョンを設定することにより実行時間の短縮を
図ることができる。最もネストの深いループの途中では
リージョンをなるべく切らないというような処理は静的
情報のみがらも行えるが１分岐の回数の情報も、実行時
情報とし、て採取すれば、２回めのコンパイル時には、
リージョン外分岐の実行回数が最小となるようなリージ
ョン設定を行う二とができる。また、分岐以外でも、リ
ージョンの境界を制御が渡る際には、ペースレジスタの
更新が必要となるため、第２図に示す実行時情報から、
実行回数の多い箇所ではなるべくリージョンを切らない
ようなリージョン設定をすることもできる。
本発明によれば、個々のプログラムが実際に実行される
環境に即した最適化処理が行えるため、最適化処理の効
果が向上し、コンパイルされたプログラムの実行時間の
短縮を図ることができる。
環境に即した最適化処理が行えるため、最適化処理の効
果が向上し、コンパイルされたプログラムの実行時間の
短縮を図ることができる。
なお、本発明方式を用いることにより従来のコンパイル
手順に比べ、オブジェクト・ブロクラムの実行、２回め
コンパイルが手順として増えるが、プログラムの実行回
数が非常に多い場合には１本発明力式により強化された
最適化により短縮される実行時間により、十分補償され
る。
手順に比べ、オブジェクト・ブロクラムの実行、２回め
コンパイルが手順として増えるが、プログラムの実行回
数が非常に多い場合には１本発明力式により強化された
最適化により短縮される実行時間により、十分補償され
る。
第１図は本発明の一実施例を示す図、第２図は実行時情
報の一例を示す図、第３図は本発明を適用したコンパイ
ラの処理フローを示す図である。 １０１・・・ソース・プログラム格納媒体、１０４．１
１０・・・オブジェクト・プログラム格納媒体、 １
０５・・・実行用データ格納媒体、１０７・・・実行時
情報格納媒体。 第１図 第２図 第３図
報の一例を示す図、第３図は本発明を適用したコンパイ
ラの処理フローを示す図である。 １０１・・・ソース・プログラム格納媒体、１０４．１
１０・・・オブジェクト・プログラム格納媒体、 １
０５・・・実行用データ格納媒体、１０７・・・実行時
情報格納媒体。 第１図 第２図 第３図
Claims (1)
- （１）コンパイラ言語を用いて書かれたソース・プログ
ラムをオブジェクト・プログラムに変換するコンパイル
方式において、生成されたオブジェクト・プログラムを
実行して、該プログラムの実行状態を示す情報（以下、
実行時情報）を採取し、該実行時情報を参照しつつ前記
ソース・プログラムを再度コンパイルして最終的オブジ
ェクト・プログラムを生成することを特徴とする最適化
コンパイル方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59127435A JPS617946A (ja) | 1984-06-22 | 1984-06-22 | 最適化コンパイル方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59127435A JPS617946A (ja) | 1984-06-22 | 1984-06-22 | 最適化コンパイル方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS617946A true JPS617946A (ja) | 1986-01-14 |
Family
ID=14959879
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59127435A Pending JPS617946A (ja) | 1984-06-22 | 1984-06-22 | 最適化コンパイル方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS617946A (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6353646A (ja) * | 1986-08-22 | 1988-03-07 | Nec Corp | 最適目的プログラム生成方式 |
| JP2005301415A (ja) * | 2004-04-07 | 2005-10-27 | Ricoh Co Ltd | コンパイル方式、シミュレータ、エミュレータおよびプログラム開発支援システム |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5960642A (ja) * | 1982-09-30 | 1984-04-06 | Fujitsu Ltd | 原始プログラムの最適化方式 |
-
1984
- 1984-06-22 JP JP59127435A patent/JPS617946A/ja active Pending
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5960642A (ja) * | 1982-09-30 | 1984-04-06 | Fujitsu Ltd | 原始プログラムの最適化方式 |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6353646A (ja) * | 1986-08-22 | 1988-03-07 | Nec Corp | 最適目的プログラム生成方式 |
| JP2005301415A (ja) * | 2004-04-07 | 2005-10-27 | Ricoh Co Ltd | コンパイル方式、シミュレータ、エミュレータおよびプログラム開発支援システム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5428793A (en) | Method and apparatus for compiling computer programs with interproceduural register allocation | |
| US6202204B1 (en) | Comprehensive redundant load elimination for architectures supporting control and data speculation | |
| US6072951A (en) | Profile driven optimization of frequently executed paths with inlining of code fragment (one or more lines of code from a child procedure to a parent procedure) | |
| US5966539A (en) | Link time optimization with translation to intermediate program and following optimization techniques including program analysis code motion live variable set generation order analysis, dead code elimination and load invariant analysis | |
| US7103881B2 (en) | Virtual machine to provide compiled code to processing elements embodied on a processor device | |
| US5457799A (en) | Optimizer for program loops | |
| US6725448B1 (en) | System to optimally create parallel processes and recording medium | |
| US6973644B2 (en) | Program interpreter | |
| US6249910B1 (en) | Apparatus and method for incrementally update static single assignment form for cloned variable name definitions | |
| Leopoldseder et al. | Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizations | |
| US20120198427A1 (en) | Ensuring Register Availability for Dynamic Binary Optimization | |
| US5937191A (en) | Determining and reporting data accessing activity of a program | |
| US20040255279A1 (en) | Block translation optimizations for program code conversation | |
| JP2500079B2 (ja) | プログラムの最適化方法及びコンパイラ・システム | |
| US20120198428A1 (en) | Using Aliasing Information for Dynamic Binary Optimization | |
| JPH07129412A (ja) | コンパイル方法及び装置 | |
| JP2000347874A (ja) | レジスタ割当器を用いた呼出規則プロローグ・エピローグコード構築方法及び装置 | |
| US6895580B2 (en) | Expression reduction during compilation through routine cloning | |
| US20040194071A1 (en) | Compiling device, computer-readable recording medium on which a compiling program is recorded and a compiling method | |
| JP2003196106A (ja) | プログラム変換方法、コンピュータ装置及びプログラム | |
| US6665864B1 (en) | Method and apparatus for generating code for array range check and method and apparatus for versioning | |
| JPH07319710A (ja) | コンパイル処理方法 | |
| US6421824B1 (en) | Method and apparatus for producing a sparse interference graph | |
| US7240341B2 (en) | Global constant pool to allow deletion of constant pool entries | |
| KR20060035077A (ko) | 데이터 처리 장치 및 이를 이용한 레지스터 할당 방법 |