JPS63240636A - 復元可能なレジスタフアイル装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、論理型プログラミング言語を実行する計算機
システムに係る復元可能なレジスタファイル装置に関し
、特に論理型プログラミング言語を実行する際の述語呼
ｑ出し及びバックトラック処理の高速化できる復元可能
なレジスタファイル装置に関する。

〔従来の技術〕

論理型プログラミング言語の実行における述語の呼び出
しは、従来型プログラミング言語における関数・手続き
の呼び出しと同様の処理が必要となる。即ち、呼び出す
べき述語（ｒＡ数）が必要とする引数情報を渡すこと、
戻りアドレスの保有、目的の述語コードへの分岐である
。引数の引き渡しにはスタックを用いるのが一般的であ
る。引数情報は呼び出された関数の実行が完了した時点
で不要となり、消去しても良いため関数の呼び出し時に
主記憶装置にとられたスタックの先頭に引数情報を格納
（ＰＵＳＨ）Ｌ、関数の実行完了時（関数からのリター
ン時）に取出（ｐｏｐ）せば良い。

従来、この引数情報をハードウェアレジスタを介して渡
すことにより高速化する手法が採用されてきた。レジス
タを用いることにより引数情報の書き込み〃及び呼び出
された関数側での引数情報の読み出しがともに高速化で
きる。また、呼び出された関数が非常に単純でありすぐ
に実行完了となる場合には、引数情報を主記憶装置に置
いてもすぐに消去される。従って、一時的にレジスタ上
に置くことにより不要なメモリアクセスを避けることが
可能となりこの点でも処理の高速化が図れる。

このような理由から、まず関数に渡すべき引数情報をレ
ジスタ（引数レジスタと呼ぶ）に−担格納する。呼び出
された関数は引数レジスタ上の引数情報をアクセスし、
必要ならば主記憶上のスタック先頭に格納するという手
法がこれまで実現されてきた。

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

従来の引数レジスタを用いる高速化手法は、論理型プロ
グラミング言語【おける述語呼び出しの高速化にも有効
であるが、以下のような問題が生ずる。

引数レジスタを用いる方式は、主記憶装置へのアクセス
をレジスタアクセスに変えることにより高速化を図る鴫
のである。従って、引数レジスタを極力長い間使用する
ことが望ましい。例えば、呼び出された述語が別の追語
をただ１つ呼び出すような場合には、現在使用中の引数
情報は不要となる訳であるの、で、引数レジスタを破壊
して使用すれば主記憶装置への格納を避けることが可能
となる。

例えば”ｐ（Ｘ、Ｙ、Ｚ）−ｑ（Ｘ、Ｚ）”という節の
実行を考えると次のようになる。述語ｐ（Ｘ、Ｙ、Ｚ）
　　を呼び出す場合には、引数レジスタの例えばＡＯ−
ＡＩ・Ａ２に引数情報を設定したとすると、節の中の変
数ＸはＡＯに、ＹはＡ１に、２はＡ２にそれぞれ対応す
ることとなる。次に、節の右辺の述語ｑ（Ｘ、Ｚ）の呼
び出し処理では、述語ｑのためにＡＯｅＡｌに引数情報
を設定する必要があるか′ミこの時、ＡＯには既に変数
Ｘの値が格納されているので、ＡＩに変数２の値をセッ
トすれば良い。変数Ｚの値は今Ａ２に格納されているの
で、引数レジスタＡ２の内容をＡ１に移すだけで述語ｑ
の引数情報が設定できたことになる。ここでＡ１が破壊
使用されることになる。

コンパイラは引数レジスタの有効利用を図るため、この
ような破壊使用を多用することになる。

ところが論理型プログラミング言語ではバックトラック
機能があり、与えられた引数情報とのユニフィケーシ璽
ンがうまくいかなかった場合には、他の節を試みること
が必要となる。ところがバックトラックにより再実行す
る場合には、初めに渡された引数情報を復元することが
必要となり、上記のような引数レジスタの破壊使用がで
きなくなる。従来、単純なハードウェアレジスタを引数
レジスタとして用いているため、このようなバックトラ
ックの可能性がある場合には、あらかじめ引数レジスタ
の内容を主記憶装置上にとられたスタック領域に保存し
ておく必要があり、レジスタを用いる効果が減少してし
まうという欠点があった。

本発明は、引数レジスタを用いることによる高速化を活
かすと共に、バックトラック発生時に引数レジスタの内
容を復元可能とすることにより、バックトラック処理が
発生してもハードウェアレジスタによる高速化を図るこ
とを目的とする。

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

本発明の復元可能なレジスタファイル装置は、述語の呼
び出しに必要な引数情報を格納するための第１の複数の
引数レジスタと、述語の実行中に生ずる引数レジスタへ
の書き込み情報を格納するするための第２の複数レジス
タと、引数レジスタへの書き込みが行われたことを示す
フラグ情報を格納するための記憶装置と、該第１の引数
レジスタ書き込み時に該記憶装置の対応する位置に書き
込みが行われた旨のフラグをヒツトする手段と、該記憶
装置に格納された書き込みが行われたか否かを示すフラ
グ情報に基づいて該第１の引数レジスタと該第２の引数
レジスタの出力のうちいずれかを選択する手段と、該記
憶装置の内容を初期化する手段とｆ：具備し、述語の呼
び出し時だ必要な引数情報を該第１の引数レジスタに格
納し、述語の実行中に生ずる引数レジスタへの書き込み
情報を該第２の引数レジスタに格納すると共に該記憶装
置に格納され７’（書き込みが行われたか否かを示すフ
ラグ情報に従って引数レジスタ１・２の出方を選択する
ことにより引数レジスタに格納された最新の情報を読み
出すことを可能にすると共に、該記憶装置の内容をリセ
ットすることに従って最初に設定された該第１の引数レ
ジスタの内容を有効とすることにより最初に渡された引
数情報全復元できること’＆！徴とするレジスタファイ
ル装置。

〔作用〕

該レジスタファイル装置によって、述語呼び出しが行わ
れると該第１の引数レジスタに必要な引数が格納される
。その後、述語の実行中に発生する引数レジスタへの値
の代入は、すべて該第２の引数レジスタへ格納される。

この書き込みが発生する場合、該記憶装置の対応する位
置に書き込みのあった旨のフラグがＯＮ（！−なる。引
数レジスタの読み出しは、該第１の引数レジスタと＃第
２の引数レジスタとの出力を、核記憶装置に格納された
フラグにより核２−１セレクタを制御することによＩ）
選択する。即ち、該記憶装置のフラグがＯＦＦの場合は
、該第１の引数レジスタの出力を選び、フラグがＯＮの
場合、即ち既に書き込みが発生した場合に″は核引数レ
ジスタ２の出力を選択する。これにより、常に最新の引
数情報を読み出すことが可能となる。

更に、パックド２ツクが発生した場合Ｆｉ、該記憶装置
をクリアし、全フラグをＯＦＦにすることにより、すべ
ての引数レジスタの読み出しを該第１の引数レジスタと
することができ、最初に渡された引数情報を読み出すこ
とができる。即ち、最初の引数情報を復元できたことに
なる。

〔実施例〕 次に、本発明について図面全参照して説明する。

第１図は本発明の一実施例である復元可能なし拳 ジスタフアイルハードウェアブロック図である。

第１図において、１け引数情報を格納する九めの４０ｂ
ｉｔｘ　　３２個のレジスタファイル、２は引数レジス
タが破壊使用される際して、新しく内容を保持するため
の４０ｂｉｔ　ｘ３２個のレジスタファイル、３は引数
レジスタに新たな書き込みが行われたこ七を示す１ｂｉ
ｔＸ３２個のフラグメモリ、４は２つのレジスタファイ
ル１−２の出力を選択するための２−１セレクタ、５は
レジスタファイルト２へのλカデータパス、６１ｄレジ
スタファイル１拳２及びフラグメモリ３へのアドレスバ
ス、７けレジスタファイル１からの出力データバス、８
はレジスタファイル２からの出力データバス、９はフラ
グメモリ３からの出力データバス、１０は７ラグメモリ
３のクリア信号用パスを示す。

レジスタファイル１・２には、３２個分の引数情報が格
納できる。さらに、これには入力データバス５と入力ア
ドレスバス６と全弁して、フラグ付きの４Ｑｂｉｔのデ
ータを書き込むことができ、第１〜２の書き込み手段を
形成している。

フラグメモリ３では、入力アドレスバス６と入力データ
“１”とを介して得られ、３２個の引数情報レジスタ知
対応して、それが更新されたこと示す１ｂｉｔの情報が
保持され、フラグをセットする手段が形成される。また
、フラグメモリ３では、格納されているメモリをクリヤ
して、初期化する手段として、クリヤのためのリセット
信号がクリヤ信号用パス１０を介して入力されている。

２−１セレクタ４は、出力データバス７・８を介して得
られるレジスタファイル１・２の４０ｂｉｔの出力を選
択するもので、その制御は、出力データバス９を介して
得られるＩｂ１ｔのフラグメモリ３の出力（出力データ
バス９）によって行われる。

つぎに本実施例の動作を詳しく説明する。

第２図（ａ）〜（ｅ）は本発明の詳細な説明図で、第１
図のハードウェアブロック図を簡単化して示しである。

第２図（ａ）は述語の呼び出しのために、３つの引数情
報がレジスタファイル１に書き込まれた状態を示してい
る。引数レジスタを利用するマイクロプログラムからＦ
ｉＯ〜３１のレジスタ番号でこのレジスタファイル１・
２がアクセスされるので、これをＡＯ〜Ａ３１と仮に呼
ぶこととする。第２図（ａ）の状態でｒｆｉ３つの引数
レジスタＡＯ−ＡＩ・Ａ２におのおの１・２・３という
引数情報が格納されていると見る。レジ、スタフアイル
２及びフラグメモリ３は初期化されている状態にある。

第２図（ｂ）は、述語の処理が進み、引数レジスタＡ２
・Ａ３に書き込みが生じた状態を示している。

引数レジスタへの書き込みは、レジスタファイル２に対
して行われ、フックメモリ３には対応する位置に′″１
”がセットされている。この状態で、引数レジスタの読
み出しが行われると、フラグメモリ３の内容が”Ｏｏの
引数レジスタはレジスタファイル１から、フラグメモリ
３の内容が１の引数レジスタはレジスタファイル２から
データがそれぞれ読み出されるので、常に引数レジスタ
ＡＯ〜Ａ３１の最新の内容を読み出すことが可能である
。従って、引数レジスタＡ２は３から４へ書き直された
ことになる。レジスタファイル１又は２への書き込みの
区別は、本実施例ではマイクロ命令により区別しており
、書き込み命令ならレジスタファイル１へ、リセット可
能な書き込み命令ならレジスタファイル２への書き込み
と７ラグメモＩ７３への書き込みを行う。

第２図（Ｃ）は引数レージ゛ネタのリセットを行った状
態を示している。レジスタファイルト２の内容は変わら
ず、フラグメモリ３のクリアのみが、クリア信号用パス
１００入力により行われている。

フラグメモリ３全リセツトすることにより、引数レジス
タＡＯ−ＡＩ・Ａ２の読み出しけすべてレジスタファイ
ル１から行われることになり、述語が呼び出された時に
渡された引数情報１・２・３を読み出すことができる。

これで、引数レジスタは復元された。

本実施例によって引数レジスタへの書き込み、読み出し
が通常のレジスタアクセスとして実現でき、かつフラグ
メモリ３のクリアにより、最初に渡された引数情報が復
元可能であることが明らかである。

なお、本発明は上記実施例に限らず多くの変形が可能で
あり、例えばレジスタファイルト２及びフラグメモリ３
のエントリａ（即ち引数レジスタの個数）は任意で良い
。またフラグメモリ３は、レジスタを用いて実現しても
よい。フラグメモリ３は賽き込みの行われ次（すなわち
使用中の）引数レジスタ位置を示しているので、この情
報によって、使用中の引数レジスタを保有する処理を制
御することが可能である。その場合にはフラグメモリ３
は、レジスタもしくはシフトレジスタとして構成すると
よい。

〔発明の効果〕

以上のごとく本発明によれば、述語の呼び出しに必要な
引数情報を主記憶装置に設けられたスタックにではなく
、高速なハードウェアレジスタに置き、引数情報へのア
クセスの高速化を図ると共に、述語の実行に失敗し他の
候補節を実行するというバックトラック時に、最初に渡
された引数情報を復元することが可能になった。従来は
バックトラックに備えて引数情報を主記憶上に保有する
しかなかったが、この主記憶装置への保存を不要とした
ことが本発明の大きな特色であり、論理型プログラミン
グ言語を実行する計ｎ機システム（例えばｐｒｏｌｏ３
　Ｊ／マシン〕の高速化ができるという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例である復元可能なレジスタフ
ァイルのハードウェアブロック図、８２図は本発明の詳
細な説明図。 １・・・・・・レジスタファイル、２・・・・・・レジ
スタファイル、３・・・・・・フラグメモリ、４・・・
・・・２−１セレク第　１　　図

Claims (1)

1. 【特許請求の範囲】 述語の呼び出しに必要な引数情報を格納するための第１
   の複数の引数レジスタと、 述語の実行中に生ずる引数レジスタへの書き込み情報を
   格納するための第２の複数の引数レジスタと、引数レジ
   スタへの書き込みが行われたことを示すフラグ情報を格
   納するための記憶装置と、該第１の引数レジスタへの書
   き込み手段と、該第２の引数レジスタへの書き込み手段
   と、該第２の引数レジスタへのデータ書き込み時に該記
   憶装置の対応する位置に書き込みが行われた旨のフラグ
   をセットする手段と、 該記憶装置に格納された書き込みが行われたか否かを示
   すフラグ情報に基づいて該第１の引数レジスタと該第２
   の引数レジスタとの出力のうちいずれかを選択する手段
   と、 該記憶装置の内容を初期化する手段とを具備し、述語の
   呼び出し時に必要な引数情報を該第１の引数レジスタに
   格納し、述語の実行中に生ずる引数レジスタへの書き込
   み情報を該第２の引数レジスタに格納すると共に該記憶
   装置に格納された書き込みが行われたか否かを示すフラ
   グ情報に従って引数レジスタ１、２の出力を選択するこ
   とにより引数レジスタに格納された最新の情報を読み出
   すことを可能にすると共に、該記憶装置の内容をリセッ
   トすることに従って最初に設定された該第１の引数レジ
   スタの内容を有効とすることにより、最初に渡された引
   数情報を復元できることを特徴とするレジスタファイル
   装置。