JPS63254533A - レジスタ同値情報管理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はコンパイラのオブジェクトコード生成方式に関
し、特にレジスタ同値情報を管理して効率の良いオブジ
ェクトコードを生成するためのレジスタ同値情報管理方
式に関する。

〔従来の技術〕

コンパイラのオブジェクトコード生成方式においては、
効率の良いオブジェクトコードを生成する目的でレジス
タ内のデータと主起’＝＠ｇＷ内のデータとの同値関係
を管理して、主記憶装置内のデータを参照するときにそ
のデータを格納しているレジスタが存在すれば、主記憶
装置内のデータを参照するオブジェクトコードに代えて
そのレジス夕を参照するオブジェクトコードを生成する
レジスタ同値情報管理方式が採用されている。

例えば、第２図の左に示すような原始プログラムが与え
られた場合、レジスタ同値情報の管理を行わなければ第
２図の右に示すようなオブジェクトコードが生成される
が、レジスタ同値情報を管理しオブジェクトコードの第
３ステツプの段階で主記憶装置内のデータＸとレジスタ
ＧＲｉの内容とが一致することを認識しておけば、オブ
ジェクトコードの第４および第６ステツプは生成しなく
てもすむ。

従来、この種のレジスタ同値情報管理方式では、例えば
第３図の左に示すような原始プログラムが与えられた場
合、第３図の右に示すように、原始プログラムの第１ス
テツプではレジスタＧＲｉとデータＸとがレジスタ同値
情報によって管理され、第４ステツプではレジスタ同値
情報の参照によってデータＸのロード用のオブジェクト
コードは生成されずにレジスタＧＲｉをデータＹにスト
アするオブジェクトコードが生成され同時にレジスタＧ
Ｒ４とデータＹとがレジスタ同値情報によって管理され
、第５ステツプではレジスタＧＲｋとデータＰとがレジ
スタ同値情報によって管理され、第８ステツプではデー
タＹの代わりにデータＺとして第４ステツプのときと同
様に管理され、第９ステツプでは第５ステツプを実行し
た場合は第９ステツプが実行されないのでデータＰに関
するレジスタ同値情報は参照されずにデータＰをレジス
タＧＲ１にロードしてデータＱにストアするオブジェク
トコードが生成される。

このように、目的プログラムの制御が分岐または合流す
る点（以下、実行分岐点と称する）から次の実行分岐点
までの範囲（以下、ユニ７）と称する）を越えてレジス
タ同値情報を管理する従来のレジスタ同値情報管理方式
には、 （１）命令中間コード列をスタックして置きそれを随時
にサーチしてレジスタ同値情報を抽出するスタック方式
と、 （２）最適化手段が中間語コード列に対して解析する目
的プログラム内の実行分岐点に関する情報と同一なもの
を同値情報処理手段内で命令中間コード列に対して解析
し収集してレジスタ同値情報を抽出する再解析方式と、 があった。

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

上述した従来のレジスタ同値情報管理方式では、＋１１
のスタック方式の場合には、 ■　命令中間コード列をスタックする範囲が有限となる
ので、最適なオブジェクトコードを生成できる目的プロ
グラムの範囲が限定される、■　レジスタ同値情報の抽
出および更新が必要となるたびにスタックした命令中間
コード列のサーチが必要となるので、コンパイラの処理
速度を遅くする要因になる、 という欠点がある。

また、（２）の再解析方式の場合には、■　最適化手段
と同様な目的プログラム内の実行分岐点に関する情報を
抽出する処理内容が同値情報処理手段に必要となる、 ■　かつこの目的プログラムの実行分岐点に関する情報
を抽出する処理はコード生成手段が生成した命令中間コ
ード列に対する解析となるので、収集する情報が多様か
つ大量となりコンパイラの処理速度を遅くする要因にな
る（命令中間コード列は中間語コード列に比べて目的機
種のオブジェクトコードにより近（情報が細分化されて
いる）、という欠点がある。

本発明の目的は、上述の点に鑑み、最適化手段が中間語
コード列に対して解析する目的プログラム内の実行分岐
点に関する情報に基づいてレジスタ同値情報の管理範囲
を規定する命令中間コード（以下、ユニットコードと称
する）を生成して命令中間コード列に含めてレジスタ同
値情報処理手段に与えることにより、最適なオブジェク
トコードを生成できる目的プログラムの範囲を限定する
ことなしにレジスタ同値情報をより簡単な処理構成で目
的プログラムの実行分岐点を越えて管理して最適なオブ
ジェクトコードをより高速に生成できるようにしたレジ
スタ同値情報管理方式を提供することにある。

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

本発明のレジスタ同値情報管理方式は、レジスタ内のデ
ータと主記憶装置内のデータとの同値関係を示すレジス
タ同値情報を管理して効率の良いオブジェクトコードを
生成するコンパイラのオブジェクトコード生成方式にお
いて、最適化手段によって起動され起動時に通知される
目的プログラム内の実行分岐点に関する情報に基づいて
レジスタ同値情報の管理範囲を規定する命令中間コード
であるユニットコードを生成するユニットコード生成手
段と、レジスタ割当て手段から起動される同値情報処理
手段によって起動され起動時に通知される前記ユニット
コードに基づいてレジスタ同値情報の管理範囲を表示す
るユニット情報テーブルを作成するユニットコード解析
手段と、前記同値情報処理手段から起動され前記ユニ７
）情報テーブルに基づいて前記同値情報処理手段が作成
したレジスタ同値情報テーブルのうちの現在処理中の命
令中間コードが含まれるユニットにおいて有効なレジス
タ同値情報を決定して前記同値情報処理手段に通知する
同値情報参照手段とを有する。

〔作用〕

本発明のレジスタ同値情報管理方式では、ユニットコー
ド生成手段が最適化手段によって起動され起動時に通知
される目的プログラム内の実行分岐点に関する情報に基
づいてレジスタ同値情報の管理範囲を規定する命令中間
コードであるユニットコードを生成し、ユニットコード
解析手段がレジスタ割当て手段から起動される同値情報
処理手段によって起動され起動時に通知されるユニット
コードに基づし、）でレジスタ同値情報の管理範囲を表
示するユニット情報テーブルを作成し、同値情報参照手
段が同値情報処理手段から起動されユニット情報テーブ
ルに基づいて同値情報処理手段が作成したレジスタ同値
情報テーブルのうちの現在処理中の命令中間コードが含
まれるユニットにおいて有効なレジスタ同値情報を決定
して同値情報処理手段に通知する。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明のレジスタ同値情報管理方式の一実施
例の構成を示すブロック図である。本実施例のレジスタ
同値情報管理方式は、原始プログラム（図示せず）が読
み込まれ字句解析され構文解析されて生成された中間語
コード列１と、最適なオブジェクトコードを生成する目
的で中間語コード列１の段階での最適化と呼ばれる種々
の処理を行う最適化手段２と、目的プログラムの実行分
岐点と各実行分岐点での実行分岐後の流れの関係とを示
す目的プログラム内の実行分岐点に関する情報を管理す
るユニットテーブル３と、ユニットテーブル３のエント
リである目的プログラム内の実行分岐点に関する情報に
基づいてレジスタ同値情報の管理範囲を規定する命令中
間コードであるユニットコードを生成するユニットコー
ド生成手段４と、最適化手段２から出力されるユニット
コードを含む第１命令中間コード列５と、第１命令中間
コード列５を入力して第２命令中間コード列７を生成す
るコード生成手段６と、コード生成手段６から出力され
る目的プログラムのオブジェクトコードのイメージであ
る第２命令中間コード列７と、レジスタ同値情報に基づ
いて最適なオブジェクトコードが生成されるようにレジ
スタ割当てを行うレジスタ割当て手段８と、レジスタ同
値情報の検索、追加および削除の処理を行う同値情報処
理手段９と、レジスタ同値情報を格納するレジスタ同値
情報テーブル１０と、第２命令中間コード列７に含まれ
るユニットコードを解析するユニットコード解析手段１
１と、ユニットコードより復元された目的プログラムの
実行分岐点に関する情報とレジスタ同値情報テーブル１
０内の各エントリのうちの目的プログラム内のユニット
ごとに有効となるエントリに関する情報とを含むユニッ
ト情報テーブル１２と、ユニット情報テーブル１２に基
づいてレジスタ同値情報テーブル１０のエントリのうち
の現在処理中のユニットで有効となるエントリを決定す
る同値情報参照手段１３と、レジスタ割当て手段８から
出力される第３命令中間コード列１４と、第３命令中間
コード列１４を入力してオブジェクトコードユニット１
６を編集するオブジェクトコード編集手段１５と、オブ
ジェクトコード編集手段１５から出力されるオブジェク
トコードユニット１６とから、その主要部が構成されて
いる。

次に、このように構成された本実施例のレジスタ同値情
報管理方式の動作について第４図〜第７図に示す具体例
を参照しながら説明する。

コンパイラにおいて、原始プログラムが読み込まれ字句
解析され構文解析されて中間語コード列１が生成される
と、最適化手段２は目的プログラムの実行分岐点を表す
中間語コードをＬ’ｌ　３６し、認識した中間語コード
に基づいて目的プログラムの実行順序の流れを解析して
、目的プログラムの実行分岐点と各実行分岐点からの実
行分岐後の実行順序の流れの関係を示す実行分岐点に関
する情報を管理するユニットテーブル３を作成する０例
えば、第４図の左に示すような原始プログラムから生成
された中間語コード列１が与えられた場合、最適化手段
２は、第４図の右に示すようなユニットＵ１がユニット
ＵよとユニットＵ、とに分岐し、ユニ、ト［Ｊ２がユニ
ットＵＩから分岐されユニットし、に分岐し、ユニット
Ｕ、がユニソ１−ＩＪ、から分岐されユニットＵ４に分
岐し、ユニットＵ４がユニ、トＵ２とユニットＵ、とか
ら分岐されることを示す実行分岐点に関する情報を管理
するユニットテーブル３を作成する。

また、最適化手段２は、ユニットテーブル３を作成また
は更新するたびごとにユニットコード生成手段４を起動
する。

起動されたユニットコード生成手段４は、起動時に最適
化手段２から通知されろユニットテーブル３のエントリ
である目的プログラム内の実行分岐点に関する悄叩に基
づいてレジスタ同値情報の管理範囲を規定する命令中間
コードであるユニットコードを生成して最適化手段２に
返却する。

ユニットコード生成手段４からユニットコードを返却さ
れた最適化手段２は、ユニットコードを含めて中間語コ
ード列１を最適化処理して第１命令中間コード列５を生
成する。例えば、第５図の左に示すような原始プログラ
ムから生成された中間語コード列１が与えられた場合に
は、第５図の右に示すように、実行分岐点によって目的
プログラムの実行が分岐される関係を表すユニットコー
ドＵＣ，〜ＵＣ１が目的プログラム内の実行分岐点の位
置に生成される。

第１命令中間コード列５が出力されると、コード生成手
段６は、第１命令中間コード列５から目的プログラムの
オブジェクトコードのイメージである第２命令中間コー
ド列７を生成する。

このコード生成手段６での処理と連動してまたは処理の
終了後に、レジスタ割当て手段８は第３命令中間コード
列１４の生成を開始する。

レジスタ割当て手段８は、まず同値情報処理手段９を起
動する。

起動された同値情報処理手段９は、第２命令中間コード
列７に基づいてレジスタ同値情報を管理するレジスタ同
値情報テーブル１０を作成する０例えば、第６図の左に
示すような原始プログラムが与えられた場合、第６図の
右に示すように、レジスタＧＲｉとデータＸとが同値で
あることを示す情報、レジスタＧＲｊとデータ■とが同
値であることを示す情轄、レジスタＧＲｉとデータＹと
が同値であることを示す情報、レジスタＧＲｋとデータ
Ｐとが同値であることを示す情報、レジスタＧＲｉとデ
ータＺとが同値であることを示す情報。

レジスタＧＲ１とデータＰとおよびレジスタＧＲ１とデ
ータＱとが同値であることを示す情報等のレジスタ同値
情報を管理するレジスタ同値情報テーブル１０を作成す
る。

また、レジスタ割当て手段８は、第２命令中間コード列
７中に含まれるユニットコードを認識するたびごとに同
値情報処理手段９を介してユニットコード解析手段１１
を起動する。

起動されたユニットコード解析手段１１は、起動時にレ
ジスタ割当て手段８から同値情報処理手段９を介して通
知されるユニットコードとレジスタ同値情報テーブル１
０とに基づいてユニットごとに有効なレジスタ同値情報
テーブル１０のエントリに関する情報を管理するユニッ
ト情報テーブル１２を作成する。ユニット情報テーブル
１２は、例えば第７図に示すように、リスト構造を有す
るテーブルで形成されていて、ユニットコードから復元
される目的プログラム内の実行分岐点に関する情報（第
４図に示したユニットテーブル３の内容と一致する情報
）と、ポインタと、レジスタ同値情報テーブル１０の有
効エントリを示すポインタチェインとから構成されてい
る。

また、同値情報処理手段９は、レジスタの有効利用を図
りより良いオブジェクトコードを生成するために、レジ
スタ同値情報の検索、追加または削除の処理が必要とな
るたびごとに同値情報参照手段１３を起動する。

起動された同値情４参照手段１３は、ユニー／　トコー
ド解析手段１１によって作成されたユニット情報テーブ
ル１２に基づいて同値情報処理手段９が作成したレジス
タ同値情報テーブル１０のエントリのうちの現在処理中
の命令中間コードが含まれるユニットに対応するエント
リを決定してその結果を同値清報処理手段９に通知する
。

レジスタ同値情報テーブル１０のエントリの通知を受け
た同値情報処理手段９は、このレジスタ同値情報テーブ
ルＩＯのエントリに基づいて現在処理中の命令中間コー
ドが含まれるユニットで有効なレジスタ同値情報を決定
してレジスタ割当て手段８に通知する。

現在処理中の命令中間コードが含まれるユニットで有効
なレジスタ同値情報を通知されたレジスタ割当て手段８
は、通知されたレジスタ同値情報に基づいて最適なオブ
ジェクトコードを生成するレジスタ割当てを行って第３
命令中間コード列１４を生成する。

最後に、オブジェクトコード編集手段１５は、第３命令
中間コード列１４を目的機種のオブジェクトコードユニ
ット１６に編集して出力する。

〔発明の効果〕

以上説明したように本発明は、ユニットコード生成手段
、ユニットコード解析手段および同値情報参照手段を設
置すたことにより、最適なオブジェクトコードを生成で
きる目的プログラムの範囲を限定することなしにレジス
タ同値情報をより簡単な処理構成で目的プログラムの実
行分岐点を越えて管理して目的プログラムの全体にわた
って有効なレジスタの使用を反映した効率の良いオブジ
ェクトコードを高速に生成できる効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示すブロック図、 第２図は原始プログラムからのオブジェクトコードの生
成例を示す図、 第３図はレジスタ同値情報の管理イメージを例示する図
、 第４図は第１図中のユニットテーブルの情報イメージの
一例を示す図、 第５図は本実施例のレジスタ同値情報管理方式における
ユニットコードの生成位置と情報イメージとの一例を示
す図、 第６図は第１図中のレジスタ同値情報テーブルの一例を
示す図、 第７図は第１図中のユニット情報テーブルの一例とレジ
スタ同値情報テーブルとの関連を示す図である。 図において、 ｌ・・・中間語コード列、 ２・・・最適化手段、 ３・・・ユニットテーブル、 ４・・・ユニットコード生成手段、 ５・・・第１命令中間コード列、 ６・・・コード生成手段、 ７・・・第２命令中間コード列、 ８・・・レジスタ割当て手段、 ９・・・同値情報処理手段、 １０・・・レジスタ同値情報テーブル、１１・・・ユニ
ットコード解析手段、 １２・・・ユニット情報テーブル、 １３・・・同値情報参照手段、 １４・・・第３命令中間コード列、 １５・・・オブジェクトコード［１手段、１６・・・オ
ブジェクトコードユニットである。

Claims (1)

1. 【特許請求の範囲】 レジスタ内のデータと主記憶装置内のデータとの同値関
   係を示すレジスタ同値情報を管理して効率の良いオブジ
   ェクトコードを生成するコンパイラのオブジェクトコー
   ド生成方式において、最適化手段によって起動され起動
   時に通知される目的プログラム内の実行分岐点に関する
   情報に基づいてレジスタ同値情報の管理範囲を規定する
   命令中間コードであるユニットコードを生成するユニッ
   トコード生成手段と、 レジスタ割当て手段から起動される同値情報処理手段に
   よって起動され起動時に通知される前記ユニットコード
   に基づいてレジスタ同値情報の管理範囲を表示するユニ
   ット情報テーブルを作成するユニットコード解析手段と
   、 前記同値情報処理手段から起動され前記ユニット情報テ
   ーブルに基づいて前記同値情報処理手段が作成したレジ
   スタ同値情報テーブルのうちの現在処理中の命令中間コ
   ードが含まれるユニットにおいて有効なレジスタ同値情
   報を決定して前記同値情報処理手段に通知する同値情報
   参照手段と、を有することを特徴とするレジスタ同値情
   報管理方式。