JPH0756745A - 言語処理プログラムのコンパイラ処理方式 - Google Patents

Abstract

(57)【要約】 【目的】ソースプログラムを機械語プログラムに翻訳す
るコンパイラにおいて、構文解析時に最適化可能な部分
を判断し、最適化可能な部分のみを最適化処理すること
によって最適化処理にかかる時間を最小にする。 【構成】ソースプログラム７をコンパイラ１に入力する
と、構文解析部２で構文解析を行ない、最適化可否情報
生成部３で最適化可否の判断を行ない、最適化可否情報
を持つ中間コード８を生成し、最適化可否判断部４にて
最適化可能な部分のみ最適化処理部５で最適化処理を行
ない最適化処理済みの中間コード９を生成し、コード生
成部６で機械語プログラム１０を生成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は言語処理プログラムのプ
ログラム処理方式に関し、とくにプログラムの最適化処
理に関する。

【０００２】

【従来の技術】一般に、コンピュータに動作を指示する
機械語のプログラムはコンピュータが実行できるよう
に、２進数や１６進数などの数字の列で表現される。こ
の数字の列は理解するには複雑過ぎるため、プログラム
開発者は理解しやすい表現を用いた高級言語のプログラ
ム（以下ソースプログラムという）を作成し、この言語
処理プログラムがソースプログラムを機械語に翻訳し、
コンピュータに渡して実行させる。コンパイラはこの翻
訳を行なう言語処理プログラムの１つである。

【０００３】以下に従来技術の一例を、図１３の構成図
により説明する。プログラム開発者は、ソースプログラ
ム７を作成し、コンパイラ１ａに入力する。ソースプロ
グラム７を入力されたコンパイラ１ａは構文解析部２ａ
にてそのプログラムの解析をし、中間コード８ａを出力
する。中間コードとはプログラマによってソースプログ
ラム上に記述された情報が、言語処理プログラムで処理
し易い形態に変換された情報の集まりである。

【０００４】次に、一例として挙げる中間コードは三番
地文と呼ばれ、次の表１のような形を持つ文の列であ
る。

【０００５】

【表１】

【０００６】上の表１でＡ，Ｂ，Ｃは定数かプログラマ
が定義した名前かコンパイラが生成した名前である。
３），４）でｇｏｔｏＬはラベルＬが示す位置へプログ
ラムの流れが移ることを示す。ラベルとは、プログラム
の制御を移す場合にプログラムの位置を示したり、記憶
領域の場所を示すためにプログラム中に記述される名札
である。また、４）のｒｅｌｏｐは＜，＞，＜＞，＝，
などで大小関係，当否関係を表す。また、２）の特別な
形としてＡ：＝Ｂがあり、Ｂの値をＡに代入することを
意味する。

【０００７】例えば、次の表２に示されるＣ言語で書か
れたソースプログラムは、構文解析部２ａでプログラム
は三番地文１、プログラム２は三番地文２に変換され
る。

【０００８】

【表２】

【０００９】図１３において、構文解析部２ａが中間コ
ード８ａを出力した後、最適化処理部５ａで無駄な三番
地文を削除したり、実行時間が早くなるように三番地文
を置換したりする。

【００１０】図１４は従来の最適化処理の一例の動作手
順を示す流れ図である。まず、ステップ１０１で処理を
初め、ステップ１０２で三番地文を最初から読み初め、
最適化処理（ステップ１０４ａ）を行い、中間コード８
ａを最後まで処理したと判断されるまで中間コード８ａ
の読込みを行い（１０６）、最適化処理１０４ａを繰り
返す。ステップ１０７で中間コードに変更があったと判
断した場合にはステップ１０２に戻り、再び最適化処理
を行なう。再び最適化処理を行なう理由は、最適化処理
により三番地文が変わった場合、新たに最適化が行なわ
れる可能性があるためである。最適化処理を行なっても
中間コードに変更がなかったなら、それ以上最適化は起
こらないので処理を終る。

【００１１】次に、一例として次の場合の最適化を考え
る。 １）ジャンプ文の飛び先が無条件ジャンプならば、ジャ
ンプ先を無条件ジャンプの飛び先に変えた方が実行効率
がよい。 ２）どこからも飛んでこないラベルは削除できる。 ３）無条件ジャンプの後の次のラベルまでの文は削除で
きる。

【００１２】１）〜３）の最適化は図１５の流れ図で示
される処理で実現される。この図１５でＣＨＧＦＬＧは
三番地文が変えられた時に立てられるフラグで、最適化
処理が初められる時にリセットされ、三番地文に何らか
の変更が加えられた時にセットされる。最適化処理部
は、ＣＨＧＦＬＧが立っている間は最適化を繰り返し最
大の最適化効果を得られるようにする。

【００１３】図１５の流れ図で実現される最適化を、次
の表３のソースプログラムに適応する例を考える。

【００１４】

【表３】

【００１５】このソースプログラムを構文解析部２ａに
入力し、中間コード（この従来例では三番地コード）８
ａに変換すると、次の表４のようになる。

【００１６】

【表４】

【００１７】図１５において、ステップ２０１から処理
を初め、ステップ２０２でフラグＣＨＧＦＬＧをリセッ
トし、ステップ２０３で三番地コードを最初から読込
む。

【００１８】読込まれた三番地コードがｇｏｔｏＬ４な
ので、ステップ２０６でｙｅｓへ進む。次に、ステップ
２０７でジャンプ先が無条件ジャンプかどうかを調べ
る。Ｌ４の次の三番地文は条件ジャンプなのでｎｏを選
択し、ステップ２１３へ進む。もし、処理している三番
地文が無条件ジャンプの後でラベルの前ならば、ステッ
プ２１３〜２１８の処理で削除されるが、無条件ジャン
プのあとにすぐラベルが来ているので、ステップ２１６
でｙｅｓに進む。

【００１９】三番地文は最終ではないので、ステップ２
２１でｎｏを選択し、ステップ２２２で次の三番地コー
ドを読み込んだ後、ステップ２０６に処理を戻す。

【００２０】次に、読込んだ三番地文はｇｏｔｏＬ２な
ので、ステップ２０６でｙｅｓを選択し、ステップ２０
７に進む。ジャンプ先の次の命令は無条件ジャンプなの
で、ステップ２０７ではｙｅｓを選択し２）の最適化を
行なうために、ステップ２０８でジャンプ先を無条件ジ
ャンプの飛び先にし、ステップ２０９でラベルの参照数
を補正した後、ステップ２０９で三番地文に変更があっ
たことを示すＣＨＧＦＬＧをセットする。

【００２１】

【表５】

【００２２】この段階での３番地コードとラベルの参照
数は、次の表６に示す通りである。

【００２３】

【表６】

【００２４】参照数が０になったとき、ラベルＬ２は最
適化３）で削除できるので、次の表７のようにステップ
２１２の処理で削除する。

【００２５】

【表７】

【００２６】次に、ステップ２１３に進み、さらにステ
ップ２１４に進む。ステップ２１４で読込んだ次の三番
地文はｊ：＝２であるが３）の最適化により、ステップ
２１７の処理で削除され、ステップ２１８で三番地文に
変更があったことを示すＣＨＧＦＬＧをセットする。次
のｇｏｔｏＬ５も同じ理由で、ステップ２１４〜２１８
の処理で、次の表８のように削除される。

【００２７】

【表８】

【００２８】以下同様に処理を進め最後の三番地コード
まで処理をしたものが、次の表９の三番地コードであ
る。

【００２９】

【表９】

【００３０】この時点でＣＨＧＦＬＧはセットされてい
るので、再び最初から最適化処理を行うが、もうこれ以
上の最適化は行われないのでつぎの最適化処理で三番地
文が変更されることはなく最適化は終了する。

【００３１】以上の最適化処理により、最初の三番地コ
ードから３行の削除と２つのラベルの消去と２つの連続
ジャンプの解消ができた。最適化フェーズが最適化処理
を行なったら、次に機械語プログラムの生成を行なう。

【００３２】コード生成部６は、三番地文を入力して、
機械語命令列に置き換える。三番地コードをどのような
機械語命令列に置き換えるかは、対象となる計算機がど
のような機械語命令を持つかに依存しているが、例えば
Ｃ：＝Ａ ＡＤＤ Ｂに対しては、次の表１０（Ａ）の
機械語命令列に置き換え、ｉｆＡ＞ＢｇｏｔｏＬに対し
ては次の表１０（Ｂ）の機械語命令列に置き換える。コ
ード生成部６がすべての三番地コードを機械語命令列
（１０）に変換して、コンパイラは処理を終る。

【００３３】

【００３４】

【表１０】

【００３５】

【発明が解決しようとする課題】上述したように従来の
最適化処理は、無駄なコードを省くため、記憶領域を小
さくしプログラムを実行したときの速度を上げるのに有
効であるが、どの中間コードを削除してよいのかとかコ
ードを置き換えていいのかを判断するためには多くの情
報を集めたり、プログラムの流れを解析しなくてはなら
ないため、処理時間が長くなる。いかにして無駄な処理
に時間を浪費しないで処理を行なうかが問題となる。

【００３６】本発明の目的は、最適化処理時間を短縮し
た言語処理プログラムのコンパイラ処理方式を提供する
ことにある。

【００３７】

【課題を解決するための手段】本発明の構成は、構文解
析部にてプログラマが作成したプログラムを解析して中
間情報を出力し、最適化処理部にてコード生成時に効率
の良いコードを出力できるよう中間情報を処理し、コー
ド生成部にてコード生成を行なう言語処理プログラうの
コンパイラ処理方式において、前記構文解析部の構文解
析時に前記中間情報へ最適化の可否の範囲の情報を付加
して出力する情報生成手段と、前記最適化処理部の最適
化処理時に最適化の可否の前記範囲情報によりその最適
化を判断する最適化判断手段とを有することを特徴とす
る。

【００３８】本発明によれば、構文解析時に最適化の不
必要な部分を判断し、中間情報に最適化可否情報を持た
せ、最適化処理時に最適化の可能性のない部分について
は最適化処理を行なわない様にし、最適化処理時間を短
くしている。

【００３９】

【実施例】図１は本発明の一実施例を説明する構成図で
ある。プログラム作成者が作成したソースプログラム７
を入力されたコンパイラ１は、構文解析部２にてそのソ
ースプログラム７を解析し、中間コード８を作成するま
では、従来例と同じであるが、本実施例では構文解析部
内２の最適化可否情報生成部３で中間コード中に最適化
可能な範囲を示す情報を生成する。例えば、ＯＰＴＢＥ
ＧとＯＰＴＥＮＤという三番地文を三番地コードに追加
して、ＯＰＴＢＥＧとＯＰＴＥＮＤで挟まれた部分のみ
最適化の可能性があるとする。

【００４０】最適化処理部５は、最適化処理判定部４で
最適化処理の可能な部分だけを判断し、その部分にのみ
最適化処理を施す。図２はこの最適化処理の概要の一例
を示す流れ図である。

【００４１】まず、ステップ１０１から処理を始め、ス
テップ１０２で三番地文を最初から読始め、ステップ１
０５で中間コードを最後まで処理したと判断されるまで
中間コードの読込み（ステップ１０６）、最適化処理
（ステップ１０４）を繰り返すが、ステップ１０３で最
適化処理を必要としているかどうかを判断し、不必要な
場合にはステップ１０４の処理をとばし、中間コードに
変更があった場合には、ステップ１０２に戻り、再び最
適化処理を行なう。

【００４２】図３は従来例で示した表１の１）〜３）の
最適化を実現する図２の最適化処理（１０４）の流れ図
である。本実施例の最適化処理も、従来例の表３と同様
に、次の表１１のプログラムをコンパイルするとする。

【００４３】

【表１１】

【００４４】このソースプログラムを構文解析部２に入
力し、中間コード８に変換すると次の表１２のようにな
る。

【００４５】

【表１２】

【００４６】このプログラムの流れを制御する制御文は
単体では最善のコードが作られるように作られているの
で最適化の可能性はないが、制御文が組み合わせられて
いるプログラムでは最適化の可能性が出てくる。

【００４７】ソースプログラムの１〜７行目までは、プ
ログラムの流れを制御する制御文が組合わせられている
ため、最適化出来る可能性があるが８行目以降はその可
能性はないので１〜７行目に対応する三番地コードの前
後にＯＰＴＢＥＧとＯＰＴＥＮＤを出力し最適化の可能
性があることを示す。

【００４８】最適化処理部５は、ステップ２０１から処
理を始め、ステップ２０４でＯＰＴＢＥＧを見つけたら
ステップ１０６〜１１８の最適化処理を行ない、ステッ
プ２１５でＯＰＴＥＮＤを見つけるまで最適化処理を行
なう。この最適化処理（２０６〜２１８）で行なってい
ることは従来例の処理と同様である。以上のようにＯＰ
ＴＢＥＧからＯＰＴＥＮＤまでの三番地コードを最適化
処理を行ない、１６行目以降の三番地文はステップ２０
４，２０５のループで読飛ばし最後の三番地文まで処理
を行う。三番地コードに変更があった場合にはＣＨＧＦ
ＬＧをセットし、ＣＨＧＦＬＧが立っている間最適化処
理を繰り返す点も従来例と同様である。

【００４９】この最適化処理部５の処理が終ったら、三
番地文の中間コード９を機械語プログラム１０に変換す
るが、その処理は従来例で示した処理と同様である。

【００５０】次に、ループ内不変式のループ外への移動
に本発明を適応する例を説明する。ループ内で不変な結
果を持つ式はループ内で毎回計算する必要がなく、始め
にループ外で計算しループ内部では計算結果のみを使用
する方が実行時間の点で効率がよい。

【００５１】ループ外への不変式の移動を行なうために
は、１）ループの検出、および２）不変式の検出の２つ
が必要である。

【００５２】この１）を実現する為には中間情報の基本
ブロックへの分割とフローグラフの作成と支配関係木の
作成が必要である。基本ブロックとは、先頭が唯一の入
口で最後が唯一の出口であるように分けた中間コードの
ブロックで、プログラムの流れを実現する際の基本単位
となるものである。以下に説明するフローグラフと支配
関係木も基本ブロックを基本単位として表現されてい
る。フローグラフとはプログラムの流れを基本ブロック
のつながりで表したもので、次の表１３の中間コードの
フローグラフは図４のように表わされる。

【００５３】

【表１３】

【００５４】フローグラフ内で基本ブロックＡから基本
ブロックＢへ矢印が出ている時、これを辺と記述し“Ａ
→Ｂ”と記述する。プログラムがスタートしてから基本
ブロックＡに到達する時には必ず、基本ブロックＢを通
らなければならない時、辺Ａは辺Ｂを支配するという。
この支配関係を表したのが支配関係木である。支配関係
木において辺Ａから下のすべての辺は、辺Ａに支配され
る。上のＣプログラムから支配関係木を作成すると、図
５のようになる。

【００５５】フローグラフと支配関係からループを検出
するのであるが、フローグラフ内の辺Ａ→ＢにおいてＢ
がＡを支配するとき、ループが存在する。つまり、基本
ブロックＡから基本ブロックＢへの流れがあり、また基
本ブロックＢに到達するには必ず基本ブロックＡを通る
必要がある時、ループが存在する。図４のフローグラフ
では辺Ａ→Ｂにおいて基本ブロックＢは基本ブロックＡ
を支配しており、ループを構成している。

【００５６】また、２）を実現する為には、ループ内に
変数の値の変更が無いことが必要である。従って、基本
ブロックでどの変数の値の変更があったかの情報を蓄え
ておっき、ループが検出された時にはループが通る基本
ブロックで値が変えられたかどうかの判断をする必要が
ある。

【００５７】フローグラフと変数の値変更情報をコンパ
イラの内部で表現する為に、図６のような情報を各基本
ブロックについてつくる（以降基本ブロック情報と記述
する）。図７は図６のフローグラフ内の基本ブロック２
の基本ブロック情報を作成した例である。

【００５８】基本ブロック情報は直前の基本ブロックの
基本ブロック情報と直後の基本ブロックの基本ブロック
情報と値の変更があった変数をもつが、各要素は複数存
在する可能性があるので、図のように複数の情報をもて
るような構造としておく。また基本ブロック情報は基本
ブロックの中間コードでの開始行と終了行を情報として
持つ。

【００５９】次に、次の表１４のＣソースプログラムを
コンパイルする場合を考える。

【００６０】

【表１４】

【００６１】最適化可否情報をもつ中間コード８が出力
された場合、最適化可否判定処理を持つ最適化処理部５
で最適化処理が行われる。

【００６２】図８は本発明の第２の実施例の最適化処理
の詳細を示す流れ図である。最適化処理部８は、ステッ
プ４０１から処理を始め、ステップ４０２でＣＨＧＦＬ
Ｇをオフとしてリセットし、ステップ４０３で三番地コ
ードを最初から読み込む。

【００６３】ＯＰＴＢＥＧが現れるまでの中間コードは
最適化の可能性は無いので、ステップ４０４〜４０６の
ループで読飛ばす。中間コードの４行目を読んで、ステ
ップ４０４でｙｅｓを選択し、ステップ４０７〜４１３
のループで不変式の移動の為の情報を収集する。まず、
ステップ４０７の処理でいま処理している中間コードが
ジャンプ命令かもしくはラベルかを判断する。

【００６４】もし、ジャンプ命令かラベルならば基本ブ
ロックの切れ目なので、ステップ４０８，４０９の処理
で基本ブロック情報に必要な情報を設定する。ステップ
４０８の処理では新しい基本ブロック情報を作成し、ス
テップ４０９では直前ブロックと次ブロックのブロック
情報に情報を設定する。ジャンプ命令かラベルでなけれ
ば、ステップ４１０の処理で値変更があるかどうか調べ
値変更があったら、ステップ４１１の処理で基本ブロッ
ク情報の値変更情報を設定する。

【００６５】ステップ４０７〜４１３の処理をＯＰＴＥ
ＮＤが現れるまで処理を繰り返す。上の中間コードで４
行目から１２行目までを、ステップ４０７〜４１３のル
ープで処理した後の基本ブロック情報は、図９の通りで
ある。この基本ブロック情報で表現されるフローグラフ
は、図１０の通りである。

【００６６】ステップ４０７〜４１３のループで基本ブ
ロック情報が生成出来、ステップ４１２でループを抜け
たら、ステップ４１４の処理で基本ブロック情報を元に
支配関係木を作る。この時、生成される支配関係木は、
図１１の通りである。

【００６７】ステップ４１５の処理でフローグラフと支
配関係木からループを検出するのであるが、図１０で辺
２→１に着目すると基本ブロック１は基本ブロック２を
支配しているためループが存在することがわかる。この
場合基本ブロック１と基本ブロック２がループを構成し
ている。

【００６８】ループが検出されたら、ステップ４でルー
プ内不変式を検出するのであるが、ループを構成してい
る基本ブロック１と基本ブロック２で値が変更されてい
るのはｉ，ｊ，ｑで、それぞれ中間コードの７，８，９
行目で変更している。ｉの値はｉの値と定数から決まる
が、ｉの値は不定なのでループ内不変式ではない。ｊの
値はｋの値と定数から決まるがｋの値はループ内で変え
られないのでループ内不変式である。ｑの値はｑの値と
ｉの値から決定されるが、ｉの値がループ内で不定なの
でループ内不定式ではない。ステップ４１５でｊがルー
プ内不定式と分かったので、ステップ４１６の処理で８
行目をループ外に移動する。

【００６９】このプログラムを構文解析部で解析し、中
間コードに変換すると、次の表１５のようになる。

【００７０】

【表１５】

【００７１】ＯＰＴＢＥＧとＯＰＴＥＮＤで挟まれた部
分の最適化処理が終ったら、またステップ４０４に処理
を戻し、ステップ４０４〜４０６のループでＯＰＴＢＥ
Ｇを探すが１３行目以降にはＯＰＴＢＥＧは存在しない
為、最後まで三番地コードを読み飛ばし、次の表１６の
ように最適化処理を終了する。

【００７２】

【表１６】

【００７３】最適化処理が終ったら、コード生成部６で
中間コード９を機械語プログラム１０に変換するのであ
るが、その処理は従来例で示した処理と同様である。

【００７４】本実施例の効果を図１２のタイムチャート
を用いて示す。図１２において、ＴＡは最適化可能なソ
ースプログラムの範囲、ＴＢは最適化不可能な範囲を線
表で示す。ＴＣ，ＴＤ′，ＴＥは従来の方式のコンパイ
ラがそれぞれ構文解析・最適化処理・コード生成にかか
る時間を示し、ＴＣ，ＴＤ，ＴＥは本実施例のコンパイ
ラがそれぞれ構文解析，最適化処理，コード生成にかか
る時間を表す。従来の方式ではソースプログラム全体に
対して最適化処理時間ＴＤ分がかかっていたのに対し、
本発明ではソースプログラムの処理時間ＴＢに対応する
処理時間を削除することによって処理時間を差分ΔＴだ
け短縮することができる。

【００７５】

【発明の効果】以上説明したように本発明は、処理時間
に大きな時間を要する複雑な最適化処理であればあるほ
どその最適化処理時間短縮の効果が大きい。

【図面の簡単な説明】

【図１】本発明の一実施例を説明するブロック図。

【図２】図１の最適化処理部５の動作を説明する流れ
図。

【図３】図２の最適化処理を説明する流れ図。

【図４】図２の中間コードから作られるフローグラフの
図。

【図５】図４のフローグラフから作られる支配関係木の
図。

【図６】図５の支配関係を説明するフローグラフの図。

【図７】図６の基本ブロック情報を説明する図。

【図８】本発明の第２の実施例の最適化処理部を説明す
る流れ図。

【図９】図８で作成した基本ブロック情報の図。

【図１０】図９の基本情報が表すフローグラフの図。

【図１１】図１０から作られる支配関係木の図。

【図１２】本発明の効果を説明するタイムチャート。

【図１３】従来例の言語処理システムのブロック図。

【図１４】図１３の最適化処理部の動作を説明する流れ
図。

【図１５】図１４の最適化処理を説明する流れ図。

【符号の説明】

１，１ａ コンパイラ ２，２ａ 構文解析部 ３ 最適化可否情報生成部 ４ 最適化可否判定部 ５ 最適化処理部 ６ コード生成部 ７ ソースプログラム ８，８ａ 最適化可否情報を持つ中間コード ９ 最適化処理済み中間コード １０ オブジェクトプログラム １０１〜１０７，２０１〜２２４，４０１〜４１７
処理ステップ

Claims (2)

【特許請求の範囲】
1. 【請求項１】 構文解析部にてプログラマが作成したプ
   ログラムを解析して中間情報を出力し、最適化処理部に
   てコード生成時に効率の良いコードを出力できるよう中
   間情報を処理し、コード生成部にてコード生成を行なう
   言語処理プログラうのコンパイラ処理方式において、前
   記構文解析部の構文解析時に前記中間情報へ最適化の可
   否の範囲の情報を付加して出力する情報生成手段と、前
   記最適化処理部の最適化処理時に最適化の可否の前記範
   囲情報によりその最適化を判断する最適化判断手段とを
   有することを特徴とする言語処理プログラムのコンパイ
   ラ処理方式。
2. 【請求項２】 所定開始・終了の文をコードに追加し、
   これら開始文・終了文で挟まれた部分のみを最適化する
   請求項１記載の言語処理プログラムのコンパイラ処理方
   式。