JPH09101896A

JPH09101896A - コンパイル最適化方法

Info

Publication number: JPH09101896A
Application number: JP7259797A
Authority: JP
Inventors: Takahiro Hirose; 隆裕廣▲瀬▼
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1995-10-06
Filing date: 1995-10-06
Publication date: 1997-04-15

Abstract

(57)【要約】【課題】計算機の利用において、演算回数を削減し、
処理速度を向上する。【解決手段】原始プログラム501をコンパイラ502で処
理して目的プログラム507を出力する。コンパイラ502に
入力されたプログラムは、503で構文解析とデータフロ
ー解析を受ける。その結果を元に、504で共通部分式を
検出する。503は部分式の排他関係を解消し、共通部分
式を削除する処理である。最後にコード生成処理506を
行い目的プログラムを出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】計算機の利用において、メモ
リ読みだし回数及び演算回数を削減する、コンパイル方
式に関する。

【０００２】

【従来の技術】コンパイラの生成する目的プログラムの
実行速度を向上させるための方法は、これまでにも数多
く開発されている。その中の一つとして、同じ機能の重
複する命令を削除することで処理の高速化を図る方法が
ある。

【０００３】演算命令の重複とは、同一の演算を複数回
実行している場合である。このとき、２回目以後の演算
では、１回目の演算の結果を使用することができるの
で、同一の演算を繰り返す必要はない。

【０００４】このような最適化は共通式削除と呼ばれ
「A.V.エイホ R.セシィ J.D.ウルマン著 : コンパイ
ラ P772 : サイエンス社」等がある。図1(a)101の
ようなループがあったとき、式(1)と式(2)は、同一の演
算演算結果をもつことがわかる。式(1)で計算した結果
をレジスタに保存しておいて、式(2)でその結果を使う
ことができれば、式(2)の演算は実行する必要がなくな
り、演算を削減することができる。この最適化をソース
コードで表現すると図1(b)102のようになる。

【０００５】

【発明が解決しようとする課題】四則演算の部分式は、
孤立して存在している場合を除いて、排他的な性格を持
っていることが多い。ある四則演算部分式を削除する
と、別の四則演算部分式は削除不可能になってしまうこ
とがある。

【０００６】図2の201は四則演算部分式の排他的性格を
示す例である。図2左は削除を行う前のプログラム片で
ある。この段階では、文の中には3つの部分式が存在し
ている。ここで部分式A+Bを削除したとすると図2右のよ
うになる。削除が終わった段階では、この文の中には、
もはやB+C, A+Cは存在しない。3つの部分式は互いに排
他的であり、同時に削除することはできない。従って、
どの部分式を優先して削除するかで、最適化の結果が変
わってしまうことになる。

【０００７】図3の301と図4の401は、同一のプログラム
片に対して、異なった順序で削除を行ったときに異なっ
た結果が出ることを示すための例である。この例では共
通部分式として A+B, B+C, A+C の3つが存在している。
図3はA+Bを先に削除した場合で、図4はB+Cを先に削除し
た場合を示している。この例ではA+Bを先に削除するの
が正解である。B+Cを先に削除してしまうと最後の文が
最適化されずに残ってしまう。 A+Cを選択した場合も同
様である。これを演算数で比較すると判り易い。図3の
順序で最適化したときは、演算数は3になり、6演算を削
減することができた。しかし、図4の順序で最適化した
結果を見ると、演算数は4であり、5演算しか削減できな
かったことになる。

【０００８】このように共通部分式を削除する順序によ
って、最適化の効果が影響を受ける。従来は、削除の順
序を考慮していなかったので、部分式排他関係の影響を
受けて最適化の効果が低下してしまうという問題があっ
た。

【０００９】

【課題を解決するための手段】上記の課題を解決するた
め、以下のような手段を設ける。 (1) プログラムを走査して検出した部分式を登録す
る。登録した部分式をカウントして、数の多い部分式を
優先して排他関係を解消してから、共通部分式を削除す
る。

【００１０】(2) プログラムを走査して検出した部分
式を登録する。登録した部分式に対して、データフロー
解析を実施し、削除可能と判定された数の多い部分式を
優先して排他関係を解消してから、共通部分式を削除す
る。

【００１１】(3) プログラムを走査して検出した部分
式を登録する。登録した部分式に対して、データフロー
解析を実施し、削除可能と判定された数の最も多い部分
式削除する。残った部分式に対して、再びデータフロー
解析を実施し、削除可能と判定された数の最も多い部分
式削除する。以上の手順を削除できる部分式がなくなる
まで繰り返す。 (4) (1)から(3)の処理方式をユーザーの指定により切
り換え可能にする。

【００１２】(1)により、コンパイル負荷の増加を最小
限に留めながら、最適化効果の高い順序で共通部分式削
除することができる。(2)により、削除可能な部分式の
数を見積ることができるので、最適化効果の高い順序で
共通部分式削除することができる。

【００１３】(3)により、実際に削除可能な部分式の数
を比較することができるので、最適化効果の高い順序で
共通部分式削除することができる。(4)により、順序決
定に伴うコンパイル負荷の増加を、ユーザーの許容でき
る範囲に押さえることができる。

【００１４】

【発明の実施の形態】図5は全体の構成を表している。
原始プログラム501をコンパイラ502で処理して目的プロ
グラム507を出力する。コンパイラ502に入力されたプロ
グラムは、503で構文解析とデータフロー解析を受け
る。その結果を元に、504で共通部分式を検出する。503
は部分式の排他関係を解消し、共通部分式を削除する処
理である。この処理の詳細は後述する。最後にコード生
成処理506を行い目的プログラムを出力する。

【００１５】図6は実際に削除を行う処理505の内部構成
をを表している。削除の方法は3種類用意してある。図
では、602、603、604で示してある。それぞれコンパイ
ル負荷と最適化能力が異なるので、ユーザーの指示601
によって処理を選択する。ここでは便宜的に602、603、
604をそれぞれ、処理A、処理B、処理Cと呼ぶことにす
る。以下で3つの処理の内部構成について述べる。

【００１６】図7は処理A602の内部構成を示している。
部分式計数処理701では、登録した部分式の数をカウン
トする。処理Aではこのカウント結果をそのまま利用し
て、部分式の優先順位を付ける。即ち、数の多い部分式
を優先する。実際に削除できる部分式の数は、排他関係
を解消し、データフロー解析を行わないと確定しない。
しかし、少ないコンパイル負荷で優先順位を見積る手段
としては有効である。

【００１７】部分式排他関係解消処理702では、計数結
果を元に多いものを優先して排他関係を解消する。排他
関係にある部分式を見つけたら、部分式の優先順位を比
較する。優先順位が低い方の部分式は登録を削除する。

【００１８】データフロー解析処理703では、登録され
ている部分式を対象にデータフロー解析を実施する。解
析の結果、削除可能と判定された部分式は削除処理704
で削除する。

【００１９】図8は処理B603の内部構成を示している。
最初のデータフロー解析処理801では登録されている全
ての部分式を対象にデータフロー解析を実施する。この
時点ではまだ排他関係を解消していないので、削除でき
る部分式は確定しない。削除できる可能性があることし
か判らない。

【００２０】部分式計数処理802では、データフロー解
析801の結果として削除できる可能性があると判定され
た部分式の数をカウントする。このカウントが部分式の
優先順位になる。単純に部分式の数で優先順位を決める
方式よりも、高い精度で優先順位を決定することが出来
る。

【００２１】部分式排他関係解消処理803では、計数結
果を元に多いものを優先して排他関係を解消する。排他
関係にある部分式を見つけたら、部分式の優先順位を比
較する。優先順位が低い方の部分式は登録を削除する。

【００２２】2回目のデータフロー解析処理804では、登
録されている部分式を対象にデータフロー解析を実施す
る。部分式の排他関係を解消したので、データフロー条
件はは変化してしまう。削除する部分式を決定するに
は、もう一度データフロー解析を行う必要がある。この
時点では部分式の排他関係は既に解消されているので、
削除可能と判定された部分式は実際に削除することがで
きる。実際の削除は805で行う。

【００２３】図9は処理C604の内部構成を示している。
処理Ｃの特徴は部分式を一つづつ削除していくことにあ
る。削除が終わる毎にデータフロー解析を繰り返すの
で、高い精度で優先順位を評価することができる。この
ような手順を繰り返し、判定処理902で削除できる部分
式がなくなったと判定されたら終了する。

【００２４】処理Ｃのもう一つの特徴は、部分式の排他
関係を解消する処理が必要ないことである。排他関係の
解消が必要になるのは複数の部分式のデータフロー解析
を１度で済ますためである。処理Ｃでは部分式ごとに解
析を行うので、排他関係を考慮する必要がない。部分式
を削除したことによるデータ依存関係の変化は、次の回
のデータフロー解析に反映されるので、排他関係の解消
は必要ない。

【００２５】データフロー解析処理901では、登録され
ている部分式を対象にデータフロー解析を実施する。最
初の解析では当然登録してある全ての部分式についてデ
ータフロー解析を行わなくてはならないが、2回目以後
はデータフローに変化のあった部分式についてのみ解析
を行えばよい。

【００２６】部分式計数処理903では、データフロー解
析の結果として削除できる可能性があると判定された部
分式の数をカウントする。このカウントが部分式の優先
順位になる。

【００２７】部分式選択処理904では、計数処理の結果
優先順位がトップになった部分式のみを削除する。それ
以外の部分式はすべて以後の繰り返しに持ち越す。トッ
プの部分式を削除すると、トップの部分式と排他関係に
あった部分式は存在しなくなる。次回のデータフロー解
析処理901で、再解析を行うと部分式が削除されたこと
に起因するデータフロー条件の変化は全て反映される。

【００２８】次に例題のプログラム片を用いて、処理
A、処理B、処理Cを適用したときの最適化結果の違いを
述べる。図10は処理Aと処理B違いを説明するためのプロ
グラム片である。このプログラム片1001の中にはA+B,B+
C,C+Aという3つの部分式が存在する。この3つの部分式
は互いに排他的な関係にあるので、このうちの1つしか
削除することはできない。このプログラム片1001を処
理Aで処理した場合を考える。部分式の数を数えると、
部分式A+Bが3つで最も多い。そこで、A+Bを優先して排
他関係を解消すると、B+C,C+Aは登録を抹消されること
になる。ところが、実際にデータフロー解析を行うと、
途中に変数Aの再定義があるので、A+Bは全く削除するこ
とができない。プログラム片1001は、処理Aの方式では
最適化することが出来ない。

【００２９】このプログラム片1001を処理Bで処理した
場合を考える。まずデータフロー解析が行われるので、
この時点でA+Bは共通化できないことが判明する。変数A
の再定義の影響を受けない部分式B+Cだけが登録され
て、無事削除される。

【００３０】図11と図12は処理Bと処理Cを比較するため
の図である。プログラム片1101は説明のための例題であ
る。多数の部分式を含んでいる。個数を数えると、A+B
が4個で最も多い。変数の再定義はないので、いずれの
部分式も削除可能である。しかし、互いに排他関係にあ
るので、実際に削除できるのは一部である。

【００３１】図11はプログラム片1101を処理Bにかけた
場合の処理過程と結果を示している。部分式を数える
と、A+Bが最も多く、以下B+C,C+Fの順番になっている。
この優先順位に従って、排他関係を解消すると1102のよ
うになる。s3,s4に含まれるB+Cは登録を抹消される。s5
ではB+Cの方が優先されて、C+Fは登録抹消となる。1103
はA+Bを削除した様子である。ここで問題なのはC+Fであ
る。s5とs6にC+Fが含まれているので、本来なら削除で
きるはずである。しかし、s5のC+Fは排他関係解消の結
果、登録を抹消されてしまっているので、もはや最適化
できない。1204は処理の結果であるが、C+Fが最適化さ
れずに残ってしまっていることが判る。

【００３２】図12プログラム片1101を処理Cにかけた場
合の処理過程と結果を示している。データフロー解析を
行い、削除できる部分式の数をカウントする。A+Bが最
も多いので、まずこれを削除することになる。その結果
が1301である。このプログラム片1201に対して、2回目
のデータフロー解析を実施する。C+FとT1+Cが2個づつ削
除可能とことが判明する。C+Fを削除すると1202のよう
になり、さらにT1+Cを削除すると最終結果として1203が
得られる。この例題ではC+Fを先に削除しているが、T1+
Cを先に削除しても、途中経過が違うだけで結果は同じ
である。処理Cでは排他関係の解消を行わずに、部分式
を削除する毎にデータフロー解析を実施する。登録して
おいた部分式C+Fが登録を抹消されてしまうことがない
ので、削除できる共通部分式は余すことなく削除するこ
とができる。

【００３３】

【発明の効果】同一の演算が行われている場合に、同一
の命令のうち２回目以後の命令は削除される。目的プロ
グラムの実行命令数が減り、目的プログラムの実行速度
が高速化される。

【図面の簡単な説明】

【図１】共通部分式削除の原理を説明するための図。

【図２】四則演算部分式の排他性を説明するための図。

【図３】部分式削除の順序を変えたときの効果を説明す
るための図。

【図４】部分式削除の順序を変えたときの効果を説明す
るための図。

【図５】処理の全体構成を示す図。

【図６】処理の構成を示すための図。

【図７】処理Aの内部構成を示す図。

【図８】処理Bの内部構成を示す図。

【図９】処理Cの内部構成を示す図。

【図１０】処理Aと処理Bの違いを示すための例題。

【図１１】例題を処理Bにかけたときの処理過程と結
果。

【図１２】例題を処理Cにかけたときの処理過程と結
果。

Claims

【特許請求の範囲】

【請求項１】コンパイル方法において、入力プログラム
内の、同一の値をとる部分式を検出し、その部分式の中
から、最も最適化効果の高い部分式を選択して削除する
ことを特徴とするコンパイル最適化方法。
【請求項２】請求項１のコンパイル最適化方法におい
て、部分式を選択する方式を複数用意し、ユーザーの指
示により選択方式を選ぶことで、コンパイル負荷の増加
を許容できる範囲に押さえることを特徴とするコンパイ
ル最適化方法。