JP2000339171A

JP2000339171A - コンパイル装置、方法及び記録媒体

Info

Publication number: JP2000339171A
Application number: JP11147742A
Authority: JP
Inventors: Eishin Tanaka; 英信田中
Original assignee: NEC IC Microcomputer Systems Co Ltd
Current assignee: NEC IC Microcomputer Systems Co Ltd
Priority date: 1999-05-27
Filing date: 1999-05-27
Publication date: 2000-12-08

Abstract

(57)【要約】【課題】メモリの利用効率がよく、実行速度の速いオ
ブジェクトプログラムを生成する。【解決手段】字句解析手段１０１、構文解析手段１０
２及び最適化手段１０３の処理結果を中間ファイルとし
て出力する。コード生成手段１０４１では、外部変数お
よびレジスタ情報出力コード生成手段１０４１２が、中
間ファイルを基にして外部変数の参照領域をメモリ領域
に確保するコードと、外部変数の参照回数と変数へのレ
ジスタ割り当てに関する情報を実行時にファイルに出力
する第１のコードを生成する。未使用レジスタ外部変数
割り当て手段１０４１３は、上記第１のコードの実行結
果に従って、外部変数へのレジスタ割り当てを行う。未
使用レジスタ外部変数割り当てコード生成手段１０４１
４は、外部変数へのレジスタ割り当て結果を参照し、上
記の中間ファイルを基にして外部変数の参照領域をメモ
リ領域に確保しないコードを生成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、コンパイル装置、
方法及びコンパイラプログラムを記録したコンピュータ
読み取り可能な記録媒体に関する。

【０００２】

【従来の技術】従来のコンパイラは、例えば、図１８に
示すように、字句解析手段１０１と、構文解析手段１０
２と、最適化手段１０３と、コード出力手段１０４０１
を有するコード生成手段１０４１とで構成されている。
このようなコンパイラでは、字句解析、構文解析、最適
化の各フェーズを経て、コード生成手段１０４１におい
てオブジェクトプログラム（アセンブラまたは機械語）
のコードが生成される。

【０００３】このようなコンパイラにおいて、コンパイ
ル対象となるソースプログラムで変数を定義すると、生
成されたオブジェクトプログラムは、定義した変数の領
域をメモリ中に確保するためのコードを含むものとな
る。そして、このオブジェクトプログラムを実行するコ
ンピュータのＣＰＵ（Central Processing Unit）は、
当該変数に対する参照があったとき、前記のコードによ
り確保されたメモリ中の領域にアクセスすることとな
る。

【０００４】ところが、メモリへのアクセスは外部バス
を経由して行わなければならないので、時間がかかって
しまう。そこで、参照頻度の高い変数にはＣＰＵ内部の
レジスタを割り当て、変数の参照時にレジスタに対する
アクセスを行うようにすることが、プログラムの実行時
間の観点から有効である。このような最適化処理は、一
般に、レジスタ割り当て最適化と呼ばれている。

【０００５】従来のコンパイラにおけるレジスタ割り当
て最適化は、一般に、ソースプログラムでの参照回数が
多い変数にレジスタを割り当てるものであった。ところ
が、ソースプログラムで変数の参照命令が出現する回数
と、コンパイルしたオブジェクトプログラムを実行する
ときに変数を参照する回数とは異なっている。例えば、
変数の参照命令の前に条件分岐命令がある場合には、プ
ログラム実行時の条件によって当該変数が参照されたり
参照されなかったりする。

【０００６】また、ループ処理には、ループの回数が静
的に判断可能なものもあるが、実行時にしか分からない
ものもある。実行時にしか回数の分からないループ処理
がある場合には、適当な重み付けをしてループの回数と
見なし、変数を参照する回数を判断するのが一般的であ
るが、これは当然誤差を含んだものとなる。ループの回
数は、プログラムによっては実行時にかなり変動するも
のもあり、これが変数の参照回数を判断するために大き
な誤差となって、最適なレジスタ割り当てが行われない
場合がかなりあった。

【０００７】そこで、特開昭６１−８２２４３号公報に
記載の「オブジェクトプログラム生成方法」では、コン
パイラに２つの出力手段を持たせることで、最適なレジ
スタ割り当てを行っている。すなわち、１つ目の手段で
は、実行時に変数毎の参照回数を記録する参照頻度記憶
領域を生成するコードを含むオブジェクトプログラムを
生成し、２つ目の手段では、１つ目の手段で出力された
オブジェクトプログラムを実行することにより得られた
参照頻度記憶領域内の情報を参照して、参照頻度の高い
変数にレジスタを割り当てるオブジェクトプログラムを
生成するものとしている。

【０００８】

【発明が解決しようとする課題】しかしながら、上記特
開昭６１−８２２４３号公報では、参照頻度に従ってレ
ジスタの割り当てを行うのみで、レジスタの割り当て対
象となる変数の属性に関する記述がなされていない。ま
た、どのような変数にどのようなレジスタを割り当てる
かに関する記述もされていない。このため、例えば、外
部変数の参照回数が多くなり、これに多くのレジスタが
割り当てられてしまうと、関数の整合性を図るために必
要なレジスタを確保することができなくなってしまう。

【０００９】ところが、上記公報では、このような場合
の対処方法が何ら開示されていなかった。そこで、この
ような事態が発生した場合には、結局のところレジスタ
の退避／復帰を行わなければならなくなってしまうの
で、コード効率が悪くなり、プログラムの実行速度が遅
くなってしまうという問題があった。また、メモリ中に
レジスタの退避領域も用意しておく必要があり、メモリ
の利用効率が悪くなってしまうという問題もあった。

【００１０】なお、レジスタ割り当て最適化に関する他
の技術が、例えば、特開平４−３２６４３２号公報や特
開平６−２１４８０２号公報において開示されている。
しかしながら、これらの公報に記載された技術でも、上
記特開昭６１−８２２４３号公報に記載の技術で指摘し
た問題点を何ら解決することができない。

【００１１】本発明は、メモリの利用効率がよく、しか
も実行速度の速いオブジェクトプログラムを生成するこ
とができるコンパイル装置、方法、及びこのようなコン
パイラプログラムを記録したコンピュータ読み取り可能
な記録媒体を提供することを目的とする。

【００１２】

【課題を解決するための手段】上記目的を達成するた
め、本発明の第１の観点にかかるコンパイル装置は、互
いに参照される外部変数を含む複数のソースプログラム
を構文解析した複数の中間ファイルに基づいて、オブジ
ェクトプログラムを生成するコンパイル装置であって、
前記複数の中間ファイルに基づいて、前記外部変数を参
照するための領域をメモリに確保する複数の第１のオブ
ジェクトプログラムを生成する第１のオブジェクトプロ
グラム生成手段と、前記オブジェクトプログラム生成手
段が生成した複数の第１のオブジェクトプログラムを結
合した実行形式のプログラムを実行した結果、参照回数
が多い外部変数から順に、他で使用されていないレジス
タを割り当てるレジスタ割り当て手段と、前記レジスタ
割り当て手段によるレジスタの割り当てを参照し、前記
複数の中間ファイルに基づいて、レジスタが割り当てら
れた外部変数の参照を当該割り当てられたレジスタを用
いて行う複数の第２のオブジェクトプログラムを生成す
る第２のオブジェクトプログラム生成手段とを備えるこ
とを特徴とする。

【００１３】上記コンパイル装置では、参照頻度の高い
外部変数は割り当てたレジスタを用いて参照することが
できるため、生成された第２のオブジェクトプログラム
を結合したプログラムを実行した場合の実行速度を早く
することができる。また、レジスタを使用して参照され
る外部変数には、メモリを割り当てなくても済む場合が
生じるため、メモリの利用効率を高いものとすることが
できる。

【００１４】上記コンパイル装置において、前記レジス
タ割り当て手段が外部変数に割り当てる他で使用されて
いないレジスタは、前記実行形式のプログラムを実行し
た結果により得られたものであってもよい。

【００１５】この場合において、前記第１のオブジェク
トプログラム生成手段は、前記複数の第１、第２のオブ
ジェクトプログラムを結合した実行形式のプログラムが
実行される装置に含まれるレジスタと、各レジスタに対
応付けてその使用状況に関する情報を管理するレジスタ
使用管理手段を前記複数の第１のオブジェクトプログラ
ムを結合した実行形式のプログラムを実行するときに生
成するためのコードを生成する手段と、前記複数の第１
のオブジェクトプログラムを結合した実行形式のプログ
ラムを実行してレジスタが使用されたときに当該使用さ
れたレジスタに対応する前記レジスタ使用管理手段内の
使用状況を使用状態とするコードを生成する手段とを含
むものとすることができ、前記レジスタ割り当て手段
は、前記複数の第１のオブジェクトプログラムを結合し
た実行形式のプログラムを実行後に得られた前記レジス
タ使用管理手段を参照して、外部変数へレジスタを割り
当てるものとすることができる。

【００１６】上記コンパイル装置において、前記レジス
タ割り当て手段が外部変数に割り当てる他で使用されて
いないレジスタは、また、前記複数の第１のオブジェク
トプログラム中で使用されているレジスタ以外のレジス
タであってもよい。

【００１７】この場合において、前記第１のオブジェク
トプログラム生成手段は、前記複数の第１、第２のオブ
ジェクトプログラムを結合した実行形式のプログラムが
実行される装置に含まれる各レジスタに対応付けてその
使用状況に関する情報を管理するレジスタ使用管理手段
を生成する手段と、前記レジスタのいずれかを使用する
コードを生成したときに当該使用されたレジスタに対応
する前記レジスタ使用管理手段内の使用状況を使用状態
とする手段とを備えるものとすることができる。

【００１８】上記コンパイル装置において、前記第１の
オブジェクトプログラム生成手段は、各外部変数と対応
付けて参照回数を記憶する参照頻度記憶手段を前記複数
の第１のオブジェクトプログラムを結合した実行形式の
プログラムを実行するときに生成するためのコードを生
成する手段と、前記複数の第１のオブジェクトプログラ
ムを結合した実行形式のプログラムを実行して外部変数
が参照さたときに当該参照された外部変数に対応する前
記参照頻度記憶手段内の参照回数を加算するコードを生
成する手段とを含むものとしてもよい。

【００１９】また、前記参照頻度記憶手段は、さらに前
記外部変数のそれぞれに対応付けてその初期値を記憶す
るものとしてもよく、この場合には、前記第１のオブジ
ェクトプログラム生成手段は、前記外部変数の初期値を
前記参照頻度記憶手段内に設定するコードを生成する手
段を含むものとすることができる。

【００２０】さらに、前記参照頻度記憶手段は、前記外
部変数のそれぞれに対応して割り当てたレジスタに関す
る情報を記憶するものとしてもよく、この場合には、前
記レジスタ割り当て手段は、前記複数の第１のオブジェ
クトプログラムを結合した実行形式のプログラムを実行
した後の前記参照頻度記憶手段内の各外部変数の参照回
数に従ってレジスタの割り当てを行って、対応する外部
変数のレジスタに関する情報の欄に記憶させ、前記第２
のオブジェクトプログラム生成手段は、前記参照頻度記
憶手段を参照して、前記複数の第２のオブジェクトプロ
グラムを生成するものとすることができる。

【００２１】また、上記コンパイル装置において、前記
第２のオブジェクトプログラム生成手段は、前記レジス
タ割り当て手段が外部変数に割り当てたレジスタを、割
り込み処理での退避及び復帰の対象となるレジスタから
除外するためのコードを生成する手段を含むものとして
もよい。

【００２２】なお、上記コンパイル装置において、前記
複数の中間ファイルは、前記第１のオブジェクトプログ
ラム生成手段が前記複数の第１のオブジェクトプログラ
ムを生成する前と、前記第２のオブジェクトプログラム
生成手段が前記複数の第２のオブジェクトプログラムを
生成する前とにおいて、それぞれ別々に生成されたもの
であってもよい。

【００２３】上記目的を達成するため、本発明の第２の
観点にかかるコンパイル方法は、互いに参照される外部
変数を含む複数のソースプログラムを構文解析した複数
の中間ファイルに基づいて、オブジェクトプログラムを
生成するコンパイル方法であって、前記複数の中間ファ
イルに基づいて、前記外部変数を参照するための領域を
メモリに確保する複数の第１のオブジェクトプログラム
を生成する第１のオブジェクトプログラム生成ステップ
と、前記オブジェクトプログラム生成ステップで生成し
た複数の第１のオブジェクトプログラムを結合した実行
形式のプログラムを実行した結果、参照回数が多い外部
変数から順に、他で使用されていないレジスタを割り当
てるレジスタ割り当てステップと、前記レジスタ割り当
てステップにおけるレジスタの割り当てを参照し、前記
複数の中間ファイルに基づいて、レジスタが割り当てら
れた外部変数の参照を当該割り当てられたレジスタを用
いて行う複数の第２のオブジェクトプログラムを生成す
る第２のオブジェクトプログラム生成ステップとを含む
ことを特徴とする。

【００２４】上記コンパイル方法において、前記レジス
タ割り当てステップで外部変数に割り当てる他で使用さ
れていないレジスタは、前記実行形式のプログラムを実
行した結果により得られたものであってもよい。

【００２５】上記コンパイル方法において、前記レジス
タ割り当てステップで外部変数に割り当てる他で使用さ
れていないレジスタは、また、前記複数の第１のオブジ
ェクトプログラム中で使用されているレジスタ以外のレ
ジスタであってもよい。

【００２６】上記目的を達成するため、本発明の第３の
観点にかかるコンピュータ読み取り可能な記録媒体は、
互いに参照される外部変数を含む複数のソースプログラ
ムを構文解析した複数の中間ファイルに基づいて、オブ
ジェクトプログラムを生成するためのコンパイラプログ
ラムを記録したコンピュータ読み取り可能な記録媒体で
あって、前記複数の中間ファイルに基づいて、前記外部
変数を参照するための領域をメモリに確保する複数の第
１のオブジェクトプログラムを生成する第１のオブジェ
クトプログラム生成ステップと、前記オブジェクトプロ
グラム生成ステップで生成した複数の第１のオブジェク
トプログラムを結合した実行形式のプログラムを実行し
た結果、参照回数が多い外部変数から順に、他で使用さ
れていないレジスタを割り当てるレジスタ割り当てステ
ップと、前記レジスタ割り当てステップにおけるレジス
タの割り当てを参照し、前記複数の中間ファイルに基づ
いて、レジスタが割り当てられた外部変数の参照を当該
割り当てられたレジスタを用いて行う複数の第２のオブ
ジェクトプログラムを生成する第２のオブジェクトプロ
グラム生成ステップとを実行させるためのプログラムを
記録することを特徴とする。

【００２７】上記記録媒体に記録されているプログラム
において、前記レジスタ割り当てステップで外部変数に
割り当てる他で使用されていないレジスタは、前記実行
形式のプログラムを実行した結果により得られたもので
あってもよい。

【００２８】上記記録媒体に記録されているプログラム
において、前記レジスタ割り当てステップで外部変数に
割り当てる他で使用されていないレジスタは、また、前
記複数の第１のオブジェクトプログラム中で使用されて
いるレジスタ以外のレジスタであってもよい。

【００２９】

【発明の実施の形態】以下、添付図面を参照して、本発
明の実施の形態について説明する。

【００３０】［第１の実施の形態］図１は、この実施の
形態にかかるコンパイラを示す機能ブロック図である。
この図では、メモリ上に記憶されたコンパイラプログラ
ムを実行するプロセッサが実現する機能として示してい
る。すなわち、コンパイラプログラムが実行されるコン
ピュータシステムが、コンパイル装置として動作する。

【００３１】図１に示すように、この実施の形態にかか
るコンパイラ１０は、字句解析手段１０１と、構文解析
手段１０２と、最適化手段１０３と、コード生成手段１
０４１とを備えている。コード生成手段１０４１は、コ
ード生成制御手段１０４１１と、外部変数およびレジス
タ情報出力コード生成手段１０４１２と、未使用レジス
タ外部変数割り当て手段１０４１３と、未使用レジスタ
外部変数割り当てコード生成手段１０４１４と、コード
出力手段１０４０１とを備えている。

【００３２】字句解析手段１０１は、コンパイルの対象
となる、高級言語で記述されたソースプログラムを字句
（トークン）に分解する。構文解析手段１０２は、分解
された字句を当該プログラム言語の仕様に従って構文解
析し、解析結果として、例えば構文木などを生成する。
最適化手段１０３は、冗長な命令等を見直すことで、コ
ンパイル後のオブジェクトプログラムの実行効率を向上
させる。これらの手段１０１〜１０３の処理結果は、中
間ファイルとしてコード生成手段１０４１に渡される。

【００３３】コード生成制御手段１０４１１は、２回の
処理で行われる翻訳処理（上記の中間ファイルからアセ
ンブラコードを生成するための処理をいう。以下、同
じ）を制御する。すなわち、コード生成手段１０４１１
は、１回目の翻訳処理では、外部変数及びレジスタ情報
出力コード生成手段１０４１２を呼び出し、２回目の翻
訳処理では、未使用レジスタ外部変数割り当て手段１０
４１３及び未使用レジスタ外部変数割り当てコード生成
手段１０４１４を順次呼び出す。

【００３４】外部変数およびレジスタ情報出力コード生
成手段１０４１２は、最適化手段１０３の出力結果であ
る中間ファイルから従来と同様の外部変数のための領域
をメモリ内に確保するためのコードを生成すると共に、
外部変数の参照回数と変数に割り当てるレジスタに関す
る情報を出力するためのコードを生成する。

【００３５】未使用レジスタ外部変数割り当て手段１０
４１３は、外部変数およびレジスタ情報出力コード生成
手段１０４１２が生成したコードが実行形式となって実
行されたときの情報を基にして、未使用のレジスタを外
部変数のために割り当てる処理を行う。

【００３６】未使用レジスタ外部変数割り当てコード生
成手段１０４１４は、未使用レジスタ外部変数割り当て
手段１０４１３による外部変数へのレジスタ割り当てを
参照して、最適化手段１０３の出力結果である中間ファ
イルから、レジスタ割り当ての行われた外部変数のため
の領域をメモリ領域に確保しないコードを生成する。

【００３７】コード出力手段１０４０１は、外部変数お
よびレジスタ情報出力コード生成手段１０４１２により
生成されたアセンブラプログラムのコード、または未使
用レジスタ外部変数割り当てコード生成手段１０４１４
により生成されたアセンブラプログラムのコードを出力
する。

【００３８】以下、この実施の形態にかかるコンパイラ
１０を含むシステムにおいて、高級言語で記述されたソ
ースプログラムから実行可能な形式のロードモジュール
が生成されるまでの動作の概略について、説明する。図
２は、このような動作を行うための、コンパイラ１０を
含むシステム全体を示す図である。

【００３９】まず、高級言語で記述された複数のソース
プログラム（Ａ、Ｂ、Ｃ）２０１をコンパイラ１０に入
力する。コンパイラ１０は、入力されたソースプログラ
ム２０１のそれぞれに対して１回目の翻訳処理を行う。
この１回目の翻訳処理では、まず、字句解析手段１０
１、構文解析手段１０２及び最適化手段１０３が、従来
と同様の処理を行い、その結果を中間ファイル（Ａ、
Ｂ、Ｃ）２０２として出力する。

【００４０】次に、コンパイラ１０では、コード生成手
段１０４１が、中間ファイル２０２を入力として通常の
コード生成を行うと共に、外部変数およびレジスタ情報
出力コード生成手段１０４１２により外部変数の参照回
数と変数に割り当てるレジスタに関する情報を出力する
ためのコードを生成することにより、第１のアセンブラ
プログラム（Ａ、Ｂ、Ｃ）２０３を生成する。

【００４１】次に、アセンブラ２０が第１のアセンブラ
プログラム２０３をそれぞれアセンブルし、これをさら
にリンカ３０がリンクして、実行形式のプログラム２０
５を生成する。そして、プログラム実行部４０が実行形
式のプログラム２０５を実行することにより、レジスタ
使用管理領域３０１と、参照頻度記憶領域３０２とを生
成する。

【００４２】次に、コンパイラ１０では、コード生成手
段１０４１が、１回目の翻訳処理で生成された中間ファ
イル２０２、並びにレジスタ使用管理領域３０１及び参
照頻度記憶領域３０２を入力として２回目の翻訳処理を
行う。２回目の翻訳処理では、未使用レジスタ外部変数
割り当て手段１０４１３がすべてのプログラムで同一の
レジスタを参照回数の多い変数に割り当てると共に、使
用レジスタ外部変数割り当てコード生成手段１０４１４
がレジスタが割り当てられた外部変数のための領域をメ
モリ領域に確保しないコードを生成することにより、第
２のアセンブラプログラム（Ａ、Ｂ、Ｃ）２０４を生成
する。

【００４３】そして、アセンブラ２０が第２のアセンブ
ラプログラム２０４をそれぞれアセンブルし、これをさ
らにリンカ３０がリンクして、最終の出力として、実行
形式のプログラム２０６を生成する。

【００４４】以下、コード生成制御手段１０４１１、外
部変数およびレジスタ情報出力コード生成手段１０４１
２、未使用レジスタ外部変数割り当て手段１０４１３及
び未使用レジスタ外部変数割り当てコード生成手段１０
４１４の動作の詳細について、それぞれ図３〜図６に示
すフローチャートを参照して説明する。

【００４５】図３は、コード生成制御手段１０４１１の
処理を示すフローチャートである。コード生成制御手段
１０４１１は、まず、最初の翻訳処理であるかどうかを
判定する（ステップＳ１０１）。最初の翻訳処理である
場合には、コード生成制御手段１０４１１は、外部変数
およびレジスタ情報出力コード生成手段１０４１２を呼
び出し、後述する処理を実行させる（ステップＳ１０
２）。外部変数およびレジスタ情報出力コード生成手段
１０４１２から制御が戻ると、コード生成制御手段１０
４１１は、このフローチャートの処理を終了する。

【００４６】一方、最初の翻訳処理でない場合、すなわ
ち２回目の翻訳処理である場合には、コード生成制御手
段１０４１１は、未使用レジスタ外部変数割り当て手段
１０４１３を呼び出し、後述する処理を実行させる（ス
テップＳ１０３）。外部変数およびレジスタ情報出力コ
ード生成手段１０４１２から制御が戻ると、コード生成
制御手段１０４１１は、今度は未使用レジスタ外部変数
割り当てコード生成手段１０４１４を呼び出し、後述す
る処理を実行させる（ステップＳ１０４）。未使用レジ
スタ外部変数割り当てコード生成手段１０４１４から制
御が戻ると、コード生成手段１０４１１は、このフロー
チャートの処理を終了する。

【００４７】図４は、外部変数およびレジスタ情報出力
コード生成手段１０４１２の処理を示すフローチャート
である。外部変数およびレジスタ情報出力コード生成手
段１０４１２は、まず、上述した参照頻度記憶領域３０
２及びレジスタ使用管理要域３０１を確保するためのコ
ードがまだ生成されていないかどうかを判定する（ステ
ップＳ２０１）。判定結果により、このようなコードが
生成されていればステップＳ２０３に、そうでなければ
ステップＳ２０２の処理に進む。

【００４８】ステップＳ２０２では、外部変数およびレ
ジスタ情報出力コード生成手段１０４１２は、プログラ
ム実行部４０による実行時において参照頻度記憶領域３
０１とレジスタ使用管理領域３０２とをメモリ内に確保
し、レジスタ使用管理領域３０２のレジスタ名の欄に特
殊レジスタを除くすべてのレジスタの名称を登録し、且
つレジスタ使用管理領域３０２の使用フラグの欄を
“０”に初期化するための処理を行うためのコードを生
成する。このコードの生成が終了すると、ステップＳ２
０３の処理に進む。

【００４９】ステップＳ２０３では、外部変数およびレ
ジスタ情報出力コード生成手段１０４１２は、最適化手
段１０３の処理結果である中間ファイル２０２がすべて
終了したかどうかを判定する。なお、この判定における
中間ファイル２０２は、コンパイルの対象となるものす
べてのことを意味し、図２の例でいえば、中間ファイル
Ａ、Ｂ、Ｃの３つすべてをいう。

【００５０】中間ファイル２０２がまだ終了していない
と判定すれば、外部変数およびレジスタ情報出力コード
生成手段１０４１２は、最適化手段１０３の処理結果で
ある中間ファイル２０２から１行分を読み出す（ステッ
プＳ２０４）。さらに、外部変数およびレジスタ情報出
力コード生成手段１０４１２は、当該読み出した行が外
部変数定義文であるかどうかを判定する（ステップＳ２
０５）。

【００５１】外部変数定義文であると判定した場合は、
外部変数およびレジスタ情報出力コード生成手段１０４
１２は、プログラム実行部４０による実行時において参
照頻度記憶領域３０２の変数の欄に当該外部変数の名称
を登録し、対応する参照回数の欄を“０”に初期化し、
対応する初期値の欄に当該外部変数の初期値を設定する
ためのコードを生成する（ステップＳ２０６）。そし
て、ステップＳ２０３に戻る。

【００５２】一方、ステップＳ２０５で外部変数定義文
でないと判定した場合は、外部変数およびレジスタ情報
出力コード生成手段１０４１２は、さらに当該読み出し
た行が外部変数参照文であるかどうかを判定する（ステ
ップＳ２０７）。ここで、外部変数参照文でもないと判
定した場合には、ステップＳ２０９の処理に進む。

【００５３】一方、ステップＳ２０７で外部変数参照文
であると判定した場合には、外部変数およびレジスタ情
報出力コード生成手段１０４１２は、参照頻度記憶領域
３０２の当該外部変数に対応する参照回数の欄を“１”
だけ加算するためのコードを生成する（ステップＳ２０
８）。そして、ステップＳ２０９の処理に進む。

【００５４】ステップＳ２０９では、外部変数およびレ
ジスタ情報出力コード生成手段１０４１２は、さらに読
み出した当該行がレジスタを使用するコード（変数の参
照以外の場合も含む）を生成するものであるかどうかを
判定する。レジスタを使用するコードを生成するもので
ないと判定したときはステップＳ２０３の処理に戻り、
レジスタを使用するコードを生成するものであると判定
したときはステップＳ２１０の処理に進む。

【００５５】ステップＳ２１０では、外部変数およびレ
ジスタ情報出力コード生成手段１０４１２は、レジスタ
使用管理領域３０２の当該使用するレジスタに対応する
使用フラグの欄を“１”とするためのコードを生成す
る。そして、ステップＳ２０３の処理に戻る。

【００５６】上記したようなステップＳ２０４からＳ２
１０の処理を繰り返し、ステップＳ２０３において最終
的に中間ファイル２０２が終了したと判定すれば、この
フローチャートの処理を終了する。

【００５７】図５は、未使用レジスタ外部変数割り当て
手段１０４１３の処理を示すフローチャートである。処
理が開始すると、未使用レジスタ外部変数割り当て手段
１０４１３は、１回目の翻訳処理に従って得られた実行
形式のプログラム２０５の実行結果から、レジスタ使用
管理領域３０１に管理されるレジスタに未使用レジスタ
があり、且つ外部変数に割り当てられてないかどうかを
判定する（ステップＳ３０１）。

【００５８】未使用レジスタがあり、且つ外部変数に割
り当てられていないと判定した場合には、未使用レジス
タ外部変数割り当て手段１０４１３は、参照頻度記憶領
域３０２において参照回数の多い変数から順にレジスタ
を割り当て、割り当てレジスタの欄に登録する。このと
き、割り当てを行ったレジスタに関するレジスタ使用管
理領域３０１の使用フラグをセットする（ステップＳ３
０２）。そして、このフローチャートの処理を終了す
る。

【００５９】一方、未使用レジスタがなく、および／ま
たは外部変数に割り当てられていないと判定した場合に
は、そのままこのフローチャートの処理を終了する。

【００６０】図６は、未使用レジスタ外部変数割り当て
コード生成手段１０４１４の処理を示すフローチャート
である。未使用レジスタ外部変数割り当てコード生成手
段１０４１４は、最適化手段１０３の処理結果である中
間ファイル２０２がすべて終了したかどうかを判定する
（ステップＳ４０１）。

【００６１】一方、中間ファイル２０２がまだ終了して
いないと判定すれば、未使用レジスタ外部変数割り当て
コード生成手段１０４１４は、最適化手段１０３の処理
結果である中間ファイル２０２から１行分を読み出す
（ステップＳ４０２）。次に、未使用レジスタ外部変数
割り当てコード生成手段１０４１４は、読み出した当該
行がｍａｉｎ関数の先頭のコードを生成するものである
かどうかを判定する（ステップＳ４０３）。

【００６２】ｍａｉｎ関数の先頭のコードを生成するも
のであると判定した場合には、未使用レジスタ外部変数
割り当てコード生成手段１０４１４は、参照頻度記憶領
域３０２を参照して、外部変数を割り当てたレジスタに
対して初期値をロードするためのコードを生成する（ス
テップＳ４０４）。そして、ステップＳ４０１の処理に
戻る。

【００６３】一方、ステップＳ４０３でｍａｉｎ関数の
先頭のコードを生成するものでないと判定した場合に
は、未使用レジスタ外部変数割り当てコード生成手段１
０４１４は、ステップＳ４０２で読み出した当該行が割
り込み関数の先頭のコードを生成するものであるかどう
かどうかをさらに判定する（ステップＳ４０５）。

【００６４】割り込み関数の先頭のコードを生成するも
のであると判定した場合には、未使用レジスタ外部変数
割り当てコード生成手段１０４１４は、外部変数に割り
当てたレジスタを割り込み処理の際の退避レジスタ群か
ら除くためのコードを生成する（ステップＳ４０６）。
そして、ステップＳ４０１の処理に戻る。

【００６５】一方、ステップＳ４０５で割り込み関数の
先頭のコードを生成するものでないと判定した場合に
は、未使用レジスタ外部変数割り当てコード生成手段１
０４１４は、ステップＳ４０２で読み出した当該行が割
り込み関数の終わりのコードを生成するものであるかど
うかをさらに判定する（ステップＳ４０７）。

【００６６】割り込み関数の終わりのコードを生成する
ものであると判定した場合には、未使用レジスタ外部変
数割り当てコード生成手段１０４１４は、外部変数に割
り当てたレジスタを割り込み処理から復帰する際の退避
レジスタ群から除くためのコードを生成する（ステップ
Ｓ４０８）。そして、ステップＳ４０１の処理に戻る。

【００６７】一方、ステップＳ４０７で割り込み関数の
終わりのコードを生成するものでないと判定した場合に
は、未使用レジスタ外部変数割り当てコード生成手段１
０４１４は、ステップＳ４０２で読み出した当該行がレ
ジスタを割り当てた外部変数に対して参照を行うもので
あるかどうかを判定する（ステップＳ４０９）。レジス
タを割り当てた外部変数に対して参照を行うものでない
と判定したときは、そのままステップＳ４０１の処理に
戻る。

【００６８】一方、レジスタを割り当てた外部変数に対
して参照を行うものであると判定したときは、未使用レ
ジスタ外部変数割り当てコード生成手段１０４１４は、
参照頻度記憶領域３０２を参照して、当該レジスタを使
用して外部変数を参照するためのコードを生成する（ス
テップＳ４１０）。そして、ステップＳ４０１の処理に
戻る。

【００６９】そして、ステップＳ４０２〜Ｓ４１０の処
理を繰り返し、ステップＳ４０１で最終的に中間ファイ
ル２０２が終了したと判定した場合には、このフローチ
ャートの処理を終了する。

【００７０】以下、この実施の形態にかかるコンパイラ
１０によって、高級言語で記述されたソースプログラム
２０１から第２アセンブラプログラム２０２が生成され
るまでの動作を、具体例に従って説明する。ここでは、
ソースプログラム２０１として、図７、図８に示すＣ言
語で記述されたプログラムを例とする。ここで、図９、
図１０は、１回目の翻訳処理で得られる第１アセンブラ
プログラム２０１（従来技術と同じ）、図１３、図１４
は、２回目の翻訳処理で得られる第２アセンブラプログ
ラム２０２を示している。また、図１１、図１２は、そ
れぞれ１回目の翻訳処理で得られた第１アセンブラプロ
グラム２０３をアセンブル、リンクして実行したときの
レジスタ使用管理領域３０１と参照頻度記憶領域３０２
の状態遷移を示している。

【００７１】図７で示されるソースプログラムａ．ｃを
コンパイラ１０に入力すると、字句解析手段１０１、構
文解析手段１０２、最適化手段１０３で従来技術と同等
の処理を行ない、その結果を中間ファイル２０１として
出力する。次に、コード生成制御手段１０４１１に制御
が移り、図３のＳ１０１の判定処理の結果によりステッ
プＳ１０２の処理が行われ、外部変数およびレジスタ情
報出力コード生成手段１０４１２に制御が移る。

【００７２】外部変数およびレジスタ情報出力コード生
成手段１０４１２の処理では、ｍざう、図４のステップ
Ｓ２０１の判定処理の結果により、ステップＳ２０２の
処理が行われ、レジスタ使用管理領域３０１、参照頻度
記憶領域３０２を確保し、初期化するコードが生成され
る。

【００７３】図７のソースプログラムの１行目では、ス
テップＳ２０３、Ｓ２０４、Ｓ２０５、Ｓ２０６の処理
により、参照頻度記憶領域３０２に変数の初期値を登録
するためのコードが生成される。図７のソースプログラ
ムの３、５、６、７、８、１０、１１行目では、それぞ
れステップＳ２０３、Ｓ２０４、Ｓ２０５、Ｓ２０７、
Ｓ２０９の処理が行われる。

【００７４】図７のソースプログラムの１２、１３、１
４行目では、それぞれステップＳ２０３、Ｓ２０４、Ｓ
２０５、Ｓ２０７、Ｓ２０８、Ｓ２０９、Ｓ２１０の処
理が行われ、参照頻度記憶領域３０２の参照回数を加算
するためのコード、及びレジスタ使用管理領域３０１の
使用フラグを“１”とするためのコードが生成される。
図７のソースプログラムの１５、１６行目では、それぞ
れステップＳ２０３、Ｓ２０４、Ｓ２０５、Ｓ２０７、
Ｓ２０９の処理が行われる。そして、最後にステップＳ
２０３の処理で中間ファイル２０２の終了を認識して終
了し、コード出力手段１０４０１から図９に示す第１ア
センブラプログラム２０３を出力する。

【００７５】次に、図８で示されるソースプログラム
ｂ．ｃをコンパイラ１０に入力すると、字句解析手段１
０１、構文解析手段１０２、最適化手段１０３で従来技
術と同等の処理を行ない、その結果を中間ファイル２０
２として出力する。次に、コード生成制御手段１０４１
１に制御が移り、図３のＳ１０１の判定処理の結果によ
りステップＳ１０２の処理が行われ、外部変数およびレ
ジスタ情報出力コード生成手段１０４１２に制御が移
る。

【００７６】外部変数およびレジスタ情報出力コード生
成手段１０４１２では、図４のステップＳ２０１の判定
処理においてすでにレジスタ使用管理領域３０１および
参照頻度記憶領域３０２を確保するコードを生成してい
ると判定されるため、そのままステップＳ２０３以降の
処理に進む。

【００７７】図８のソースプログラムの１、３、６、７
行目では、それぞれステップＳ２０３、Ｓ２０４、Ｓ２
０５、Ｓ２０７、Ｓ２０９の処理が行われる。図８のソ
ースプログラムの８、９行目では、それぞれステップＳ
２０３、Ｓ２０４、Ｓ２０５、Ｓ２０７、Ｓ２０８、Ｓ
２０９、Ｓ２１０の処理が行われ、参照頻度記憶領域３
０２の参照回数を加算するためのコード、及びレジスタ
使用管理領域３０１の使用フラグを“１”とするための
コードが生成される。

【００７８】図８のソースプログラムの１０、１２、１
３、１４、１５行目では、それぞれステップＳ２０３、
Ｓ２０４、Ｓ２０５、Ｓ２０７、Ｓ２０９の処理が行わ
れる。そして、最後にステップＳ２０３の処理で中間フ
ァイル２０２の終了を認識して終了し、コード出力手段
１０４０１から図１０に示す第１アセンブラプログラム
２０３を出力する。

【００７９】以上述べた処理で得られた図９に示す第１
アセンブラプログラムａ．ｓと図１０に示す第１アセン
ブラプログラムｂ．ｓとを、アセンブル、リンクして得
られた実行形式のプログラム２０５を実行することによ
り、図３におけるレジスタ使用管理領域３０１、及び参
照頻度記憶領域３０２が生成される。次に、実行形式の
プログラム２０５の実行時における各生成領域の状態遷
移について述べる。なお、実行時に割り込みは起こら
ず、割り込み関数ｗａｒｉは実行しないこととする。

【００８０】プログラムはｍａｉｎ関数から始まり、図
９のオブジェクトプログラムの２２行目において、外部
変数およびレジスタ情報出力コード生成手段１０４１２
によって生成されたコードから、レジスタ使用管理領域
３０１及び参照頻度記憶領域３０２が確保、初期化され
る。ここで、レジスタ使用管理領域３０１の状態遷移は
図１１（ａ）に、参照頻度記憶領域３０２の状態遷移は
図１２（ａ）となる。

【００８１】次に、図９のオブジェクトプログラムの２
４行目の関数コールで関数ｆｕｎｃ１に処理が移る。ｆ
ｕｎｃ１では、図９における３６行目から３９行目の処
理であり、レジスタ＄２と＄８とを使用し、変数ａを２
回、変数ｂを１回参照している。このため、外部変数お
よびレジスタ情報出力コード生成手段１０４１２により
生成されたコードにより、レジスタ使用管理領域３０１
の状態遷移は図１１（ｂ）に、参照頻度記憶領域３０２
の状態遷移は図１２（ｂ）となる。

【００８２】次に、図９のオブジェクトプログラムの４
１行目から４４行目の処理では、レジスタ＄９と＄１０
を使用し、変数ｃを１回、変数ｄを１回、変数ｅを１回
参照している。このため、外部変数およびレジスタ情報
出力コード生成手段１０４１２により生成されたコード
により、レジスタ使用管理領域３０１の状態遷移は図１
１（ｃ）、参照頻度記憶領域３０２の状態遷移は図１２
（ｃ）となる。

【００８３】次に、図９のオブジェクトプログラムの４
６行目から４９行目の処理では、レジスタ＄１１と＄１
２を使用し、変数ｆを１回、変数ｇを１回、変数ｈを１
回参照している。このため、外部変数およびレジスタ情
報出力コード生成手段１０４１２により生成されたコー
ドにより、レジスタ使用管理領域３０１の状態遷移は図
１１（ｄ）、参照頻度記憶領域３０２の状態遷移は図１
２（ｄ）となる。

【００８４】次に、図９のオブジェクトプログラムの５
１行目の関数コールで関数ｆｕｎｃ２に処理が移る。ｆ
ｕｎｃ２の処理において、図１０のオブジェクトプログ
ラムの１１行目から１４行目の処理でレジスタ＄２と＄
８を使用し、変数ａを２回、変数ｆを１回参照してい
る。このため、外部変数およびレジスタ情報出力コード
生成手段１０４１２により生成されたコードにより、レ
ジスタ使用管理領域３０１の状態遷移は図１１（ｄ）か
ら変わらず、参照頻度記憶領域３０２の状態遷移は図１
２（ｅ）となる。

【００８５】次に、図１０のオブジェクトプログラムの
１６行目から２１行目の処理でレジスタ＄９と＄１０と
＄１１を使用し、変数ｅを２回、変数ｂを１回、変数ｇ
を１回参照している。このため、外部変数およびレジス
タ情報出力コード生成手段１０４１２により生成された
コードによりレジスタ使用管理領域３０１の状態遷移は
図１１（ｄ）から変わらず、参照頻度記憶領域３０２の
状態遷移は図１２（ｆ）となる。

【００８６】次に、図１０のオブジェクトプログラムの
２３行目の処理で、関数ｆｕｎｃ２の呼出し側に戻る。
そして、図９のオブジェクトプログラムの５５行目の処
理で関数ｆｕｎｃ１から呼出し側に戻る。さらに、図９
のオブジェクトプログラムの２８行目の処理で関数ｍａ
ｉｎの呼出し側であるスタートアップルーチンに戻り、
処理を終了する。

【００８７】２回目の翻訳処理では、１回目の翻訳処理
で得られた図９、図１０のオブジェクトプログラムをア
センブル、リンクすることにより得られた実行形式のプ
ログラムを実行することで得られたレジスタ使用管理領
域３０１および参照頻度記憶領域３０２をコンパイラに
入力する。その後、まず、１回目の翻訳処理で得られた
図７に示すソースプログラムａ．ｃに対する中間ファイ
ル２０２に対し処理を行なう。

【００８８】コード生成制御手段１０４１１は、図３の
ステップＳ１０１の判定処理の結果によりステップＳ１
０３を行ない、未使用レジスタ外部変数割り当て手段１
０４１３に制御を移す。未使用レジスタ外部変数割り当
て手段１０４１３は、図５のステップＳ３０１の判定処
理にの結果により、ステップＳ３０２の処理を実行す
る。

【００８９】この時点でのレジスタ使用管理領域３０１
は図１１（ｄ）の状態であるため、未使用レジスタ外部
変数割り当て手段１０４１３は、レジスタ＄１３と＄１
４と＄１５を未使用レジスタと認識する。また、この時
点での参照頻度記憶領域３０２は図１２（ｇ）の状態で
あるため、未使用レジスタ外部変数割り当て手段１０４
１３は、参照回数の多い変数をａ、ｅ、ｂに対してレジ
スタ＄１３と＄１４と＄１５をそれぞれ割り当て、参照
頻度記憶領域３０２を図１２（ｈ）の状態とする。変数
ｂは、変数ｆ、ｇと参照回数が同じであるが、この場合
には、どの変数にレジスタを割り当てても同じ効果が得
られるので、本例では一例として変数ｂに割り当てるも
のとする。

【００９０】次に、コード生成制御手段１０４１１に処
理が戻り、図３のステップＳ１０４の処理を行って、未
使用レジスタ外部変数割り当てコード生成手段１０４１
４に制御を移す。

【００９１】未使用レジスタ外部変数割り当てコード生
成手段１０４１４では、図７のステップＳ４０１の判定
処理の結果により、ステップＳ４０２が実行される。次
に、図９のオブジェクトプログラムの２０行目でステッ
プＳ４０３、Ｓ４０４の処理が行われ、図１３のオブジ
ェクトプログラムの１８、１９、２０行目のコードが生
成される。以後、判定処理に適合しない行に関して、未
使用レジスタ外部変数割り当てコード生成手段１０４１
４は、ステップＳ４０３、Ｓ４０５、Ｓ４０７、Ｓ４０
９、Ｓ４０１、Ｓ４０２の処理が繰り返される。

【００９２】次に、図９のオブジェクトプログラムの３
６行目から４９行目でステップＳ４０９、Ｓ４１０の処
理が行われ、図１３のオブジェクトプログラムの３３行
目から４２行目のコードが生成される。未使用レジスタ
外部変数割り当てコード生成手段１０４１４は、最後に
ステップＳ４０１の処理で中間ファイルの終了を認識し
て終了し、コード出力手段１０４０１から図１３に示す
アセンブラコードを出力する。

【００９３】次に、１回目の翻訳処理で得られた図８に
示すソースプログラムｂ．ｃに対する中間ファイル２０
２に対し処理を行なう。まず、コード生成制御手段１０
４１１は、図３のステップＳ１０１の判定処理の結果に
よりステップＳ１０３を行ない、未使用レジスタ外部変
数割り当て手段１０４１３に制御を移す。ここでは、既
に未使用レジスタを外部変数に割り当て済みのため、本
手段を終了し、コード生成制御手段１０４１１に処理が
戻り、図３のステップＳ１０４の処理を行った結果、未
使用レジスタ外部変数割り当てコード生成手段１０４１
４に制御が移る。

【００９４】未使用レジスタ外部変数割り当てコード生
成手段１０４１４では、図６のステップＳ４０１の判定
処理の結果によりステップＳ４０２の処理が実行され
る。次に、図９のアセンブラプログラムの２０行目でス
テップＳ４０３、Ｓ４０４の処理が行われ、図１３のア
センブラプログラムの１８、１９、２０行目のコードが
生成される。以後、判定処理に適合しない行に関して
は、ステップＳ４０３、Ｓ４０５、Ｓ４０７、Ｓ４０
９、Ｓ４０１、Ｓ４０２の処理が繰り返される。

【００９５】次に、図１０のアセンブラプログラムの１
１行目から２１行目でステップＳ４０９、Ｓ４１０の処
理が行われ、図１４の８行目から１３行目のコードが生
成される。次に、図１０のアセンブラプログラムの２９
行目から３８行目でステップＳ４０５、Ｓ４０６の処理
が行われ、レジスタ＄１３と＄１４と＄１５を退避レジ
スタ群から除いて、図１４のアセンブラプログラムの２
１行目から２７行目のコードが生成される。

【００９６】次に、図１０のアセンブラプログラムの４
４行目から５３行目でステップＳ４０７、Ｓ４０８の処
理が行われ、レジスタ＄１３と＄１４と＄１５を復帰レ
ジスタ群から除いて、図１４の３３行目から３９行目の
コードが生成される。次に、図１０のアセンブラプログ
ラムの４４行目から５３行目でステップＳ４０７、Ｓ４
０８の処理が行われ、図１４の２８行目から３２行目の
コードが生成される。次に、図１０のアセンブラプログ
ラムの２９行目から３８行目でステップＳ４０５、Ｓ４
０６の処理が行われ、レジスタ＄１３と＄１４と＄１５
を退避レジスタ群から除いて、図１４の２１行目から２
７行目のコードが生成される。

【００９７】そして、未使用レジスタ外部変数割り当て
コード生成手段１０４１４は、最後にステップＳ４０１
で中間ファイル２０１の終了を認識して終了し、コード
出力手段１０４０１から図１４に示すアセンブラプログ
ラムを出力する。

【００９８】以上のように図７、図８のソースプログラ
ムから生成した第１アセンブラプログラム２０３（図
９、図１０：従来技術）に対する第２アセンブラプログ
ラム（図１３、図１４：本実施形態）でのデータ領域及
びコード領域の削減率を、図１５に示す。この図から、
本実施形態では、メモリ領域の大幅な削減ができること
が分かる。また、この例とは異なる大規模のソースプロ
グラムに対しても、定量的に同等な削減効果が得られる
ことは、経験上予測することができる。

【００９９】以上説明したように、この実施の形態にか
かるコンパイラ１０では、外部変数およびレジスタ情報
出力コード生成手段１０４１２が１回目の翻訳処理で生
成した第１アセンブラプログラム２０３をアセンブル、
リンクした実行形式のプログラム２０５を実行して、外
部変数にに割り当てることのできるレジスタを調べてレ
ジスタ使用管理領域３０１に登録している。

【０１００】そして、未使用レジスタ外部変数割り当て
手段１０４１３は、実行形式のプログラム２０５を実際
に実行した状態におけるレジスタ使用管理領域３０１で
使用フラグが“０”のレジスタを、参照頻度の多い外部
変数に割り当てている。こうして、未使用レジスタ外部
変数割り当てコード生成手段１０４１４が参照頻度の高
い外部変数にレジスタを割り当ててコードを生成するこ
とができるため、第２のアセンブラプログラム２０４を
アセンブル、リンクした実行形式のプログラム２０６
は、コード効率がよく、その実行速度が速いものとな
る。

【０１０１】また、この実施の形態にかかるコンパイラ
１０では、外部変数およびレジスタ情報出力コード生成
手段１０４１２による１回目の翻訳処理では外部変数以
外の変数にレジスタの割り当てを行い、外部変数に対す
るレジスタの割り当ては、２回目の翻訳処理で行うこと
にしている。このため、複数のソースプログラム２０１
のうちで互いに異なるもの同士での外部変数の参照につ
いても、同一のレジスタを割り当てることができるた
め、、第２のアセンブラプログラム２０４をアセンブ
ル、リンクした実行形式のプログラム２０６は、コード
効率がよく、その実行速度が速いものとなる。

【０１０２】また、この実施の形態にかかるコンパイラ
１０では、レジスタを割り当てる外部変数に初期値があ
る場合に、未使用レジスタ外部変数割り当てコード生成
手段１０４１４が当該レジスタに初期値を設定するため
のコードを生成している。このため、外部変数を最初か
ら最後まで同一のレジスタに割り当てることが可能とな
り、この分だけメモリ領域に確保しなければならない外
部変数の参照のための領域を小さくすることができる。

【０１０３】さらに、この実施の形態にかかるコンパイ
ラ１０では、未使用レジスタ外部変数割り当てコード生
成手段１０４１４は、割り込み関数で退避／復帰するレ
ジスタから外部変数に割り当てたレジスタを除いてい
る。これにより、第２のアセンブラプログラム２０４を
アセンブル、リンクした実行形式のプログラム２０６
は、割り込み処理時に退避／復帰しなければならないレ
ジスタの数が従来よりも少なくすることができるので、
コード効率がよく、その実行速度が速いものとなる。ま
た、レジスタの退避／復帰のためのメモリの領域も小さ
くすることができる。

【０１０４】［第２の実施の形態］この実施の形態にか
かるコンパイラ１０は、第１の実施の形態にかかるもの
とほぼ同じである。但し、この実施の形態では、図１６
に示すように、レジスタ使用管理領域３０１が未使用の
レジスタに関する情報を１回目の翻訳処理において得て
レジスタ使用管理領域３０１を生成する。すなわち、こ
の実施の形態では、外部変数およびレジスタ情報出力コ
ード生成手段１０４１２がレジスタ使用管理領域３０１
を生成する点において、第１の実施の形態のものと異な
る。

【０１０５】図１７は、この実施の形態における外部変
数およびレジスタ情報出力コード生成手段１０４２の処
理を示すフローチャートである。この実施の形態では、
外部変数およびレジスタ情報出力コード生成手段１０４
１２は、まず、レジスタ使用管理領域３０１がメモリ中
に確保されていないかどうかを判定する（ステップＳ５
０１）。レジスタ使用管理領域３０１がメモリ中に確保
されていると判定したときは、ステップＳ５０３の処理
に進む。

【０１０６】一方、レジスタ使用管理領域３０１がメモ
リ中に確保されていないと判定したときは、外部変数お
よびレジスタ情報出力コード生成手段１０４１２は、レ
ジスタ使用管理領域３０１をメモリ中に確保し、さらに
レジスタ使用管理領域３０２のレジスタ名の欄に特殊レ
ジスタを除くすべてのレジスタの名称を登録する（ステ
ップＳ５０２）。そして、ステップＳ５０３の処理に進
む。

【０１０７】ステップＳ５０３からステップＳ５０９ま
での処理は、図４のステップＳ２０３からＳ２０９まで
の処理と同じである。

【０１０８】ステップＳ５０９においてレジスタを使用
するコードを生成するものであると判定したときは、外
部変数およびレジスタ情報出力コード生成手段１０４１
２は、レジスタ使用管理領域３０２の当該使用するレジ
スタに対応する使用フラグの欄を“１”とする（ステッ
プＳ５１０）。そして、ステップＳ５０３の処理に戻
る。

【０１０９】以上説明したように、この実施の形態にか
かるコンパイラ１０では、外部変数およびレジスタ情報
出力コード生成手段１０４１２がレジスタ使用管理領域
３０１を確保し、特殊レジスタを除くすべてのレジスタ
の名称を登録すると共に、レジスタを使用するコードを
生成する場合には、当該使用するレジスタに対応する使
用フラグの欄を“１”に設定している。これにより、こ
の実施の形態にかかるコンパイラ１０では、第１の実施
の形態での効果に加えて次のような効果を得ることがで
きる。

【０１１０】すなわち、ソースプログラム２０１によっ
ては、外部からの情報の入力や割り込みによって、実行
する度に動作が異なるものとなることがある。このよう
な場合、ある実行結果では未使用であったレジスタを別
の実行結果では使用する場合がある。しかし、この実施
の形態では、実行時に使用される可能性のあるレジスタ
に対応する使用フラグを、１回目の翻訳時にすべて
“１”にセットするため、外部変数に割り当てられたレ
ジスタが、プログラムの実行時に使用されて、不正な動
作が行われることがなくなる。

【０１１１】［実施の形態の変形］本発明は、上記の第
１、第２の実施の形態に限られず、種々の変形、応用が
可能である。以下、本発明に適用可能な上記の実施の形
態の変形態様について、説明する。

【０１１２】上記の第１、第２の実施の形態では、未使
用レジスタ外部変数割り当てコード生成手段１０４１４
によって２回目の翻訳処理を行うときに、最初に入力し
たソースプログラム２０１から生成した中間ファイル２
０２を利用していた。すなわち、１回目の翻訳処理と２
回目の翻訳処理とで同じ中間ファイル２０２を利用して
いた。しかしながら、２回目の翻訳処理を行う前に、コ
ンパイラ１０にソースプログラム２０１を新たに入力し
て、１回目の翻訳処理を行う前と同様に中間ファイルを
生成するものとしてもよい。

【０１１３】上記の第１、第２の実施の形態では、ソー
スプログラム２０１をコンパイラ１０でコンパイルした
オブジェクトプログラムとしてアセンブラプログラムを
生成するものとし、生成されたアセンブラプログラムを
アセンブラ２０を用いて機械語のコードに変換するもの
としていた。しかしながら、ソースプログラムからアセ
ンブラプログラムをコンパイルしたオブジェクトプログ
ラムとして、直接機械語のコードを生成するものとして
もよい。

【０１１４】上記の第１、第２の実施の形態では、コン
パイラ１０は、字句解析手段１０１、構文解析手段１０
２、最適化手段１０３、及びコード生成手段１０４１で
構成されるものとしていた。しかしながら、最適化手段
１０３を有さず、ソースプログラムを字句解析、構文解
析しただけの中間ファイルに基づいてアセンブラコード
を生成する場合でも、コード生成手段１０４１に含まれ
る各手段が正しく動作することができる。

【０１１５】上記の第１、第２の実施の形態では、コン
パイラ１０は、メモリ上に記憶されたコンパイラプログ
ラムを実行するプロセッサが実現する機能として説明し
ていた。しかし、このようなコンパイラプログラムは、
磁気ディスク或いは光ディスクなどのコンピュータ読み
取り可能な記録媒体に格納して配布してもよい。さらに
は、ネットワーク上のサーバから当該ネットワークを介
して配信するものとしてもよい。

【０１１６】上記の第１、第２の実施の形態では、コン
パイラ１０は、字句解析手段１０１、構文解析手段１０
２、最適化手段１０３及びコード生成手段１０４１が一
体のものとして構成されるものとしていた。しかしなが
ら、字句解析手段１０１、構文解析手段１０２及び最適
化手段１０３は、従来のものと同じであるので、コード
生成手段１０４１のみのモジュールとして提供するよう
にしてもよい。

【０１１７】

【発明の効果】以上説明したように、本発明によれば、
コード効率のよい、すなわち実行速度が速いオブジェク
トプログラムを生成することができる。また、外部変数
を参照するための領域をメモリ内に確保しなくても済む
ようになるので、メモリの利用効率のよいオブジェクト
プログラムを生成することができる。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態にかかるコンパイラ
を示す機能ブロック図である。

【図２】本発明の第１の実施の形態において、ソースプ
ログラムから実行形式のプログラムを生成するまでの処
理を行うシステム全体を示す図である。

【図３】図１のコード生成制御手段の処理を示すフロー
チャートである。

【図４】図１の外部変数およびレジスタ情報出力コード
生成手段の処理を示すフローチャートである。

【図５】未使用レジスタ外部変数割り当て手段の処理を
示すフローチャートである。

【図６】未使用レジスタ外部変数割り当てコード生成手
段の処理を示すフローチャートである。

【図７】Ｃ言語で記述されたソースプログラムの例を示
す図である。

【図８】Ｃ言語で記述されたソースプログラムの例を示
す図である。

【図９】図７のソースプログラムから１回目の翻訳処理
で生成されたアセンブラコードを示す図である。

【図１０】図８のソースプログラムから１回目の翻訳処
理で生成されたアセンブラコードを示す図である。

【図１１】レジスタ使用管理領域の状態遷移を示す図で
ある。

【図１２】参照頻度記憶領域の状態遷移を示す図であ
る。

【図１３】図７のソースプログラムから２回目の翻訳処
理で生成されたアセンブラコードを示す図である。

【図１４】図８のソースプログラムから２回目の翻訳処
理で生成されたアセンブラコードを示す図である。

【図１５】本発明の第１の実施の形態にかかるコンパイ
ラによる効果を説明する図である。

【図１６】本発明の第１の実施の形態において、ソース
プログラムから実行形式のプログラムを生成するまでの
処理を行うシステム全体を示す図である。

【図１７】本発明の第２の実施の形態における外部変数
およびレジスタ情報出力コード生成手段の処理を示すフ
ローチャートである。

【図１８】従来例にかかるコンパイラを示す機能ブロッ
ク図である。

【符号の説明】

１０コンパイラ１０１字句解析手段１０２構文解析手段１０３最適化手段１０４１コード生成手段１０４０１コード出力手段１０４１１コード生成制御手段１０４１２外部変数およびレジスタ情報出力コード生
成手段１０４１３未使用レジスタ外部変数割り当て手段１０４１４未使用レジスタ外部変数割り当てコード生
成手段２０アセンブラ３０リンカ４０プログラム実行部２０１ソースプログラム２０２中間ファイル２０３第１アセンブラプログラム２０４第２アセンブラプログラム２０５実行形式のプログラム２０６実行形式のプログラム３０１レジスタ使用管理領域３０２参照頻度記憶領域

Claims

【特許請求の範囲】

【請求項１】互いに参照される外部変数を含む複数のソ
ースプログラムを構文解析した複数の中間ファイルに基
づいて、オブジェクトプログラムを生成するコンパイル
装置であって、前記複数の中間ファイルに基づいて、前記外部変数を参
照するための領域をメモリに確保する複数の第１のオブ
ジェクトプログラムを生成する第１のオブジェクトプロ
グラム生成手段と、前記オブジェクトプログラム生成手段が生成した複数の
第１のオブジェクトプログラムを結合した実行形式のプ
ログラムを実行した結果、参照回数が多い外部変数から
順に、他で使用されていないレジスタを割り当てるレジ
スタ割り当て手段と、前記レジスタ割り当て手段によるレジスタの割り当てを
参照し、前記複数の中間ファイルに基づいて、レジスタ
が割り当てられた外部変数の参照を当該割り当てられた
レジスタを用いて行う複数の第２のオブジェクトプログ
ラムを生成する第２のオブジェクトプログラム生成手段
とを備えることを特徴とするコンパイル装置。
【請求項２】前記レジスタ割り当て手段が外部変数に割
り当てる他で使用されていないレジスタは、前記実行形
式のプログラムを実行した結果により得られたものであ
ることを特徴とする請求項１に記載のコンパイル装置。
【請求項３】前記第１のオブジェクトプログラム生成手
段は、前記複数の第１、第２のオブジェクトプログラム
を結合した実行形式のプログラムが実行される装置に含
まれるレジスタと、各レジスタに対応付けてその使用状
況に関する情報を管理するレジスタ使用管理手段を前記
複数の第１のオブジェクトプログラムを結合した実行形
式のプログラムを実行するときに生成するためのコード
を生成する手段と、前記複数の第１のオブジェクトプロ
グラムを結合した実行形式のプログラムを実行してレジ
スタが使用されたときに当該使用されたレジスタに対応
する前記レジスタ使用管理手段内の使用状況を使用状態
とするコードを生成する手段とを含み、前記レジスタ割り当て手段は、前記複数の第１のオブジ
ェクトプログラムを結合した実行形式のプログラムを実
行後に得られた前記レジスタ使用管理手段を参照して、
外部変数へレジスタを割り当てることを特徴とする請求
項２に記載のコンパイル装置。
【請求項４】前記レジスタ割り当て手段が外部変数に割
り当てる他で使用されていないレジスタは、前記複数の
第１のオブジェクトプログラム中で使用されているレジ
スタ以外のレジスタであることを特徴とする請求項１に
記載のコンパイル装置。
【請求項５】前記第１のオブジェクトプログラム生成手
段は、前記複数の第１、第２のオブジェクトプログラム
を結合した実行形式のプログラムが実行される装置に含
まれる各レジスタに対応付けてその使用状況に関する情
報を管理するレジスタ使用管理手段を生成する手段と、
前記レジスタのいずれかを使用するコードを生成したと
きに当該使用されたレジスタに対応する前記レジスタ使
用管理手段内の使用状況を使用状態とする手段とを備え
ることを特徴とする請求項４に記載のコンパイル装置。
【請求項６】前記第１のオブジェクトプログラム生成手
段は、各外部変数と対応付けて参照回数を記憶する参照
頻度記憶手段を前記複数の第１のオブジェクトプログラ
ムを結合した実行形式のプログラムを実行するときに生
成するためのコードを生成する手段と、前記複数の第１
のオブジェクトプログラムを結合した実行形式のプログ
ラムを実行して外部変数が参照さたときに当該参照され
た外部変数に対応する前記参照頻度記憶手段内の参照回
数を加算するコードを生成する手段とを含むことを特徴
とする請求項１乃至５のいずれか１項に記載のコンパイ
ル装置。
【請求項７】前記参照頻度記憶手段は、さらに前記外部
変数のそれぞれに対応付けてその初期値を記憶し、前記第１のオブジェクトプログラム生成手段は、前記外
部変数の初期値を前記参照頻度記憶手段内に設定するコ
ードを生成する手段を含むことを特徴とする請求項６に
記載のコンパイル装置。
【請求項８】前記参照頻度記憶手段は、さらに前記外部
変数のそれぞれに対応して割り当てたレジスタに関する
情報を記憶し、前記レジスタ割り当て手段は、前記複数の第１のオブジ
ェクトプログラムを結合した実行形式のプログラムを実
行した後の前記参照頻度記憶手段内の各外部変数の参照
回数に従ってレジスタの割り当てを行って、対応する外
部変数のレジスタに関する情報の欄に記憶させ、前記第２のオブジェクトプログラム生成手段は、前記参
照頻度記憶手段を参照して、前記複数の第２のオブジェ
クトプログラムを生成することを特徴とする請求項６ま
たは７に記載のコンパイル装置。
【請求項９】前記第２のオブジェクトプログラム生成手
段は、前記レジスタ割り当て手段が外部変数に割り当て
たレジスタを、割り込み処理での退避及び復帰の対象と
なるレジスタから除外するためのコードを生成する手段
を含むことを特徴とする請求項１乃至８に記載のコンパ
イル装置。
【請求項１０】前記複数の中間ファイルは、前記第１の
オブジェクトプログラム生成手段が前記複数の第１のオ
ブジェクトプログラムを生成する前と、前記第２のオブ
ジェクトプログラム生成手段が前記複数の第２のオブジ
ェクトプログラムを生成する前とにおいて、それぞれ別
々に生成されたものであることを特徴とする請求項１乃
至９のいずれか１項に記載のコンパイル装置。
【請求項１１】互いに参照される外部変数を含む複数の
ソースプログラムを構文解析した複数の中間ファイルに
基づいて、オブジェクトプログラムを生成するコンパイ
ル方法であって、前記複数の中間ファイルに基づいて、前記外部変数を参
照するための領域をメモリに確保する複数の第１のオブ
ジェクトプログラムを生成する第１のオブジェクトプロ
グラム生成ステップと、前記オブジェクトプログラム生成ステップで生成した複
数の第１のオブジェクトプログラムを結合した実行形式
のプログラムを実行した結果、参照回数が多い外部変数
から順に、他で使用されていないレジスタを割り当てる
レジスタ割り当てステップと、前記レジスタ割り当てステップにおけるレジスタの割り
当てを参照し、前記複数の中間ファイルに基づいて、レ
ジスタが割り当てられた外部変数の参照を当該割り当て
られたレジスタを用いて行う複数の第２のオブジェクト
プログラムを生成する第２のオブジェクトプログラム生
成ステップとを含むことを特徴とするコンパイル方法。
【請求項１２】前記レジスタ割り当てステップで外部変
数に割り当てる他で使用されていないレジスタは、前記
実行形式のプログラムを実行した結果により得られたも
のであることを特徴とする請求項１１に記載のコンパイ
ル方法。
【請求項１３】前記レジスタ割り当てステップで外部変
数に割り当てる他で使用されていないレジスタは、前記
複数の第１のオブジェクトプログラム中で使用されてい
るレジスタ以外のレジスタであることを特徴とする請求
項１１に記載のコンパイル方法。
【請求項１４】互いに参照される外部変数を含む複数の
ソースプログラムを構文解析した複数の中間ファイルに
基づいて、オブジェクトプログラムを生成するためのコ
ンパイラプログラムを記録したコンピュータ読み取り可
能な記録媒体であって、前記複数の中間ファイルに基づいて、前記外部変数を参
照するための領域をメモリに確保する複数の第１のオブ
ジェクトプログラムを生成する第１のオブジェクトプロ
グラム生成ステップと、前記オブジェクトプログラム生成ステップで生成した複
数の第１のオブジェクトプログラムを結合した実行形式
のプログラムを実行した結果、参照回数が多い外部変数
から順に、他で使用されていないレジスタを割り当てる
レジスタ割り当てステップと、前記レジスタ割り当てステップにおけるレジスタの割り
当てを参照し、前記複数の中間ファイルに基づいて、レ
ジスタが割り当てられた外部変数の参照を当該割り当て
られたレジスタを用いて行う複数の第２のオブジェクト
プログラムを生成する第２のオブジェクトプログラム生
成ステップとを実行させるためのプログラムを記録する
ことを特徴とするコンピュータ読み取り可能な記録媒
体。
【請求項１５】前記レジスタ割り当てステップで外部変
数に割り当てる他で使用されていないレジスタは、前記
実行形式のプログラムを実行した結果により得られたも
のであることを特徴とする請求項１４に記載のコンピュ
ータ読み取り可能な記録媒体。
【請求項１６】前記レジスタ割り当てステップで外部変
数に割り当てる他で使用されていないレジスタは、前記
複数の第１のオブジェクトプログラム中で使用されてい
るレジスタ以外のレジスタであることを特徴とする請求
項１４に記載のコンピュータ読み取り可能な記録媒体。