JPH0778736B2 - 電子計算機 - Google Patents

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は遅延スロット長の異なる遅延分岐命令を用いて
効率的に命令を実行する電子計算機に関する。

（従来の技術） 最近、RISC（Reduced Instruction Set Computer）型の
アーキテクチャを持つマイクロプロセッサが注目されて
いる。この種のマイクロプロセッサでは、そのパイプラ
イン処理の流れを乱すことなく命令を実行することが、
その性能を十分に発揮させる上での重要な課題となる。

さて上述したパイプライン処理の乱れを招く原因の１つ
に分岐命令がある。即ち、パイプライン処理は、既に前
のフェーズでフェッチした命令のデコードと、次の命令
のフェッチとを同じフェーズで並行して行われる。この
際、デコードによって命令の種別が分岐であることが解
釈されると、上述した如くフェッチした次の命令を取消
し、前記分岐命令の分岐先の命令を改めてフェッチする
ことが必要となる。このような命令フェッチのやり直し
がクロックのロスとなり、パイプライン処理の乱れの原
因となる。

このような分岐命令によるパイプライン処理の乱れに起
因する不具合を解決する手段として、例えば 『D.J.Lilja, “Reducing the Branch Penalty in Pipelined Process
ors,"Computer,July,1988,pp.47〜55』 等の文献に紹介されるように、 静的な分岐予測（Static Branch Prediction） 動的な分岐予測（Dynamic Branch Prediction） 遅延分岐（Delayed Branch） ループバッファ（Loop Buffers） 等の手法を採用することが考えられている。

上述した遅延分岐の手法で用いられる遅延分岐命令は、
その命令（遅延分岐命令）の実行直後に一定長の遅延ス
ロットを設定するものであり、この遅延スロット期間に
ある命令は前記遅延分岐命令の実行前に実行されること
になる。尚、この遅延分岐命令の遅延スロット長はパイ
プライン処理のステージ数の各ステージでの処理の内容
に応じて決定される。例えば『Berkeley RISC II』等で
は、一般的に遅延スロット長［１］の遅延分岐命令が設
定される。

さて分岐命令のデコード時には、その直後（次）の命令
を既にフェッチしているので、一般的にはデコードによ
って命令の分岐が確定した場合、既にフェッチした次の
命令の実行を取消す必要がある。この点、遅延分岐命令
によれば、その次の命令の取消しを行なう代りに、遅延
分岐命令の後にnop（no operation）命令を置き、このn
op命令をそのまま実行することになる。この結果、前述
したように次の命令を取消す場合と実質的に等価な処理
を、より単純なハードウェアにより、しかもパイプライ
ン処理を乱すことなく実行することが可能となる。

ところでこの種の遅延分岐命令を持つ電子計算機におい
ては、遅延分岐命令によって設定される遅延スロット期
間に、例えばその分岐命令の直前の命令や分岐先の命
令、或いは分岐しない先の命令を持ってくることができ
る。このような命令実行順序の変更（シフト）により命
令列（コード）の最適化を行うことが可能となる。

このコードの最適化の手法については、例えば 『T.R.Gross and J.L.Hennessy. “Optimizing Delayed Branchs," Proc.IEEE Micro−15,Oct.1982,pp.114〜120』 等の文献に詳しく紹介される。しかしてこのようなコー
ドの最適化手法を用いることにより、例えば本来的には
何の処理も実行しなかったクロックを有効に使って、そ
の命令列を効率的に実行することが可能となる。

ここで上述した遅延分岐命令が関係するコード最適化手
法の代表的な例について説明する。ここに示す代表的な
コード最適化手法の１つは、或る分岐命令Ａの分岐先ａ
が分岐命令Ｂである場合、その分岐元の分岐命令Ａの分
岐先ａを、その分岐先ａの分岐命令Ｂの分岐先ｂにて置
換えると云う最適化手法でるある。もう１つの手法は、
本来、インタロックを起こしてしまうような２つの命令
の間に置かれたnop命令の位置に分岐命令を持ってくる
ことで、無駄なクロックを消すようにした最適化の手法
である。尚、ここで用いる［インタロック］の意味につ
いては後述する。

先ず、これらの最適化手法を実際に適用する際しての制
約について考える。

分岐命令Ａの分岐先が分岐命令Ｂである場合、分岐元の
分岐命令Ａの分岐先ａを、その分岐先ａの分岐命令Ｂの
分岐先ｂで置き換えることで、分岐の回数を減らすよう
にした最適変手法について述べる。但し、ここでは分岐
元、および分岐先の両分岐命令とも遅延分岐命令である
場合を考える。また説明の簡単化の為、ここではこれら
の遅延分岐命令の遅延スロット長を［１］として説明す
る。

例えば第11図（ａ）に示すように、分岐先および分岐元
の両遅延命令とも無条件分岐命令（以下、［brd］と標
記する）であるような命令列である場合、これらの各無
条件分岐命令brd A,brd Bの次の命令＜ope1＞，＜ope2
＞の少なくとも一方がnop命令であるならば、この命令
列を第11図（ｂ）に示すように分岐元の無条件分岐命令
brd Aをbrd Bに書き換えて最適化することができる。

尚、命令＜ope＞は、命令＜ope1＞，＜ope2＞のうちのn
op命令ではない方の命令を示している。また上記命令＜
ope1＞，＜ope2＞の両方がそれぞれnop命令である場合
には、上記命令＜ope＞もnop命令となる。

また上記命令＜ope1＞，＜ope2＞が共にnop命令ではな
い場合には、例えば第11図（ｃ）に示すように分岐元の
無条件分岐命令の分岐先を書き換え（brd A→brd B）、
この無条件分岐命令の前に命令＜ope1＞を移動（シフ
ト）することによりその命令列を最適化することができ
る。しかし命令＜ope1＞を無条件分岐命令brdの前に移
動すると、もともの上記無条件分岐命令brdの前に存在
する命令との間でインタロックを起こす虞れがある。従
ってこのような場合には、例えばそれらの命令の間にno
p命令を挿入する必要が生じる。これ故、上述した第11
図（ｃ）に示すような最適化は、必ずしも有効であると
は云えない。

これに対して第12図（ａ）に示すように、分岐元が条件
分岐命令（以下、［cbrd］と表記する）であり、その分
岐先が無条件分岐命令brdである場合には次のようにし
てその最適化を行うことができる。即ち、条件分岐命令
cbrdが、その条件の成立・不成立に拘らず遅延スロット
期間にある命令を実行するものとすると、例えば第12図
（ｂ）に示すように条件分岐命令cbrdの分岐先を書き換
え（cbrd cc,A→cbrd cc,B）、命令＜ope1＞を上記条件
分岐命令cbrdの実行前に移動することにより最適化する
ことができる。但し、このような最適化が行えるのは命
令＜ope1＞の実行の結果、そのコンディション・コード
が変わらない場合だけである。

ちなみに命令＜ope1＞の実行によってコンディション・
コードが変わるような場合は、上記＜ope1＞を前記条件
分岐命令cbrdの前に移動させることはできない。しかし
この場合には、例えば第12図（ｃ）に示すように条件分
岐命令cbrdの分岐先を書き換え（cbrd cc,A→cbrd cc,
C）、その分岐先を命令＜ope2＞にすることにより最適
化することができる。但し、ラベルB:で始まる基本ブロ
ックにとって、その直前の基本ブロックがプレデセッサ
であって、且つその基本ブロックの最後の命令が分岐命
令でなく、また遅延分岐命令の遅延スロット期間に存在
するものでもない場合には、上述した最適化の後、ラベ
ルC:の前にラベルB:への分岐命令br Bを挿入することが
必要となる。従ってこのような最適化を行っても、その
プログラムの実行時間が短くなるという保証はない。

しかし上記ラベルB:で始まる基本ブロックへの入り方
が、分岐だけによって発生するならば上述したような新
たな分岐命令の挿入の必要はなく、従って上述した最適
化はいちがいに悪とは云えない。

次に、例えば第13図（ａ）に示すように、分岐元の条件
分岐命令が、条件不成立時に遅延スロット期間に存在す
る命令の実行を打ち消すような条件分岐命令（以下、
［cbrd^＊］と標記する）である場合について考える。こ
の場合には前述した第12図（ｂ）に示したような最適化
はできず、前述した第12図（ｃ）に示した最適化と同様
にして、例えば第13図（ｂ）に示すように条件分岐命令
の分岐先を変更（cbrd^＊ cc,A→cbrd^＊ cc,B）すること
で、その最適化が可能である。

但し、この場合にもラベルB:で始まる基本ブロックの直
前の基本ブロックがプレデセッサであって、この基本ブ
ロックの最後の命令が分岐命令でなく、また遅延分岐命
令の遅延スロット期間に存在するものでもない場合に
は、その最適化の後にラベルC:の前にラベルB:への分岐
命令br Bを挿入することが必要となる。従ってこの場合
にも、上述した最適化によりプログラムの実行時間が短
くなるという保証はない。しかし上記ラベルB:で始まる
基本ブロックへの入り方が前述したように分岐だけによ
って発生するならば新たな分岐命令の挿入の必要がなく
なるので、この最適化は非常に有効に作用することにな
る。

最後に、本来、インタロックを起こしてしまうような２
つの命令の間に置かれたnop命令の位置に分岐命令を持
ってくることで、無駄なクロックを消すようにした最適
化の手法について述べる。

第14図（ａ）はインタロックを起こしてしまうような２
つの命令＜ope1＞，＜ope2＞の間にnop命令を持つ命令
列を示している。ここで上記２つの命令＜ope1＞，＜op
e2＞の間の挿入されているnop命令は、命令＜ope1＞，
＜ope2＞が起こすインタロックを防止する為のものであ
る。

さて上述したインタロックとは、命令＜ope1＞の或るフ
ェーズと命令＜ope2＞の或るフェーズとの間に何等かの
依存関係があり、これらの命令＜ope1＞，＜ope2＞を連
続して実行すると、上記依存関係が因果律に反し、この
結果、正しい実行動作が保証されないような現象のこと
を称する。

例えば第15図（ａ）に示すように命令＜ope1＞がフェー
ズＭを終了した後でないと命令＜ope2＞のフェーズＥを
実行できない場合、命令＜ope1＞＜ope2＞を連続して実
行するとインタロックが発生する。従ってこのような場
合には、第15図（ｂ）に示すように連続する２つの命令
＜ope1＞，＜ope2＞の間にnop命令をおくことで、イン
タロックの発生を防止する必要がある。

この場合、例えば命令＜ope2＞の次の命令が無条件分岐
命令brである場合には、例えば第15図（ｃ）に示すよう
に上記分岐命令brを遅延分岐命令brdに変え、前記命令
＜ope1＞，＜ope2＞の間に移動することにより、nop命
令が与えられていた部分での無駄なクロックを無くすこ
とが可能となる。但し、このような最適化が行なえるの
は、nop命令がbr命令の２つの前（遅延スロット長＋１
スロット前）にある場合だけである。このような条件が
満たされない場合には、例えば命令のスケジューリング
により、nop命令をその位置まで移動させる必要があ
り、このようなnop命令の移動が必ずしも可能であると
は保証されない。

（発明が解決しようとする課題） このようにRISC型のアーキテクチャを持つマイクロプロ
セッサにおいては、遅延分岐命令の分岐先が同様な遅延
分岐命令である場合、その分岐元の分岐命令の分岐先
を、その分岐先の分岐命令の分岐先にて置き換えると云
う命令コードの最適化が考えられる。しかし遅延命令の
種類によっては、種々の制約により必ずしもその最適化
を行い得るとは限らない。また最適化を行うに際して新
たな分岐命令の追加が必要になる場合もあり、実行時間
を減らすことが可能となると云う保証もない。従ってこ
れらの問題を考慮すると、その最適化は不浄に複雑なも
のとなることが否めない。

またインタロックを起こすような２つの命令間に分岐命
令を移動させることで無駄なクロックをなくすような最
適化においては、nop命令のスケジューリングにより最
適化可能な位置に置くことができるとは限らない。

本発明はこのような事情を考慮してなされたもので、そ
の目的とするところは、命令列の最適化手続きの複雑さ
を解決し、更には最適化を行う上での制約を緩和して実
際の命令列の最適化を容易に行って無駄なく効率的に命
令列を実行することのできる電子計算機を提供すること
にある。

［発明の構成］ （課題を解決するための手段） 本発明に係る電子計算機は、命令を順次取得する命令プ
リフェッチレジスタと、前記取得された命令を解釈する
デコーダと、前記解釈された命令が、遅延スロット長が
可変である遅延分岐命令または遅延スロット長が異なる
複数の遅延分岐命令の場合に、前記分岐命令の分岐先ア
ドレスを格納する分岐先アドレスレジスタと、前記解釈
された命令が、遅延スロット長が可変である遅延分岐命
令または遅延スロット長が異なる複数の遅延分岐命令の
場合に、前記分岐命令の遅延スロット長の値が格納さ
れ、命令の同期をとるためのクロック信号に応じて前記
格納された遅延スロット長の値を減少する分岐カウンタ
と、遅延スロット期間終了を判定するための設定値と前
記分岐カウンタに格納された値とを比較し、該比較によ
り一致のときには遅延スロット期間の終了を検出する比
較器と、前記デコーダによりデコードされた命令が前記
遅延分岐命令でない分岐命令の場合には、該分岐命令の
分岐先アドレスが格納され、前記デコーダによりデコー
ドされた命令が分岐命令ではない場合には、格納されて
いるアドレスの次のアドレスが格納され、前記遅延スロ
ット期間の終了が検出された場合には前記分岐先アドレ
スレジスタに格納されているアドレスが格納されるプロ
グラムカウンタと、前記遅延スロット期間の終了が検出
されたときに前記分岐先アドレスレジスタに格納されて
いる値を選択し、前記遅延スロット期間終了が検出され
ないときには、前記プログラムカウンタの値を選択する
ことにより、次に取得する命令の制御を行うセレクタと
を備え、無条件分岐命令の分岐先が無条件分岐命令であ
るときには、分岐元の無条件分岐命令の分岐先を、分岐
先の無条件分岐命令の分岐先が分岐先であり、かつ遅延
スロット長を［２］とする遅延分岐命令に変更し、更
に、分岐先の無条件分岐命令の直後の命令を分岐元の無
条件分岐命令の直後の命令の後に複写する最適化を行
い、命令列が第１の命令、インタロックを防止するため
のnop命令、第２の命令、…、第Ｍ＋１（Ｍは整数とす
る）の命令、無条件分岐命令、の順番で並んでいるとき
には、前記nop命令を、前記無条件分岐命令の分岐先が
分岐先であり、かつ遅延スロット長を［Ｍ］とする遅延
分岐命令に変更し、更に、前記無条件分岐命令を削除す
る最適化を行い、遅延スロット長［Ｍ］の遅延分岐命令
の分岐先が、遅延スロット長［Ｎ］（Ｎは整数とする）
の遅延分岐命令であるときには、分岐元の遅延分岐命令
を、分岐先の遅延分岐命令の分岐先が分岐先であり、か
つ分岐元の遅延分岐命令の遅延スロットの値と分岐先の
遅延分岐命令の遅延スロットの値との合計を遅延スロッ
ト長とする遅延分岐命令に変更し、更に、分岐先の遅延
分岐命令の後の命令Ｎ個を分岐元の遅延分岐命令の後の
Ｍ個の命令の後に複写する最適化を行うことを特徴と
し、更に、パイプライン機能を持つことを特徴とするも
のである。

（作 用） 本発明によれば、遅延分岐命令の遅延スロット長が可変
され、その遅延スロット長に応じて分岐の実行が制御さ
れるので、例えば遅延スロット期間を長くしてその間に
他の命令を効率的に実行することが可能となり、命令列
の最適化に対する制約条件を大幅に緩和することが可能
となる。この結果、命令列の最適化を簡単に、且つ効率
的に行い、クロックの無駄を招くことなくその命令実行
時間の短縮化を図ることが可能となる。

（実施例） 本発明に係る電子計算機は、第１図に示すように構成さ
れた命令フェッチ部を備える。この命令フェッチ部は命
令を順次取得する命令プリフェッチレジスタと、前記取
得された命令を解釈するデコーダと、前記解釈された命
令が、遅延スロット長が可変である遅延分岐命令または
遅延スロット長が異なる複数の遅延分岐命令の場合に、
前記分岐命令の分岐先アドレスを格納する分岐先アドレ
スレジスタと、前記解釈された命令が、遅延スロット長
が可変である遅延分岐命令または遅延スロット長が異な
る複数の遅延分岐命令の場合に、前記分岐命令の遅延ス
ロット長の値が格納され、命令の同期をとるためのクロ
ック信号に応じて前記格納された遅延スロット長の値を
減少する分岐カウンタと、遅延スロット期間終了を判定
するための設定値と前記分岐カウンタに格納された値と
を比較し、該比較により一致のときには遅延スロット期
間の終了を検出する比較器と、前記デコーダによりデコ
ードされた命令が前記遅延分岐命令でない分岐命令の場
合には、該分岐命令の分岐先アドレスが格納され、前記
デコーダによりデコードされた命令が分岐命令ではない
場合には、格納されているアドレスの次のアドレスが格
納され、前記遅延スロット期間の終了が検出された場合
には前記分岐先アドレスレジスタに格納されているアド
レスが格納されるプログラムカウンタと、前記遅延スロ
ット期間の終了が検出されたときに前記分岐先アドレス
レジスタに格納されている値を選択し、前記遅延スロッ
ト期間終了が検出されないときには、前記プログラムカ
ウンタの値を選択することにより、次に取得する命令の
制御を行うセレクタとを備えており、更に、パイプライ
ン機能を有する電子計算機を用いる。

上記可変の遅延スロット長を持つ遅延分岐命令は、その
遅延スロット長を［Ｎ］としたとき、無条件分岐命令の
場合にはbrd（Ｎ）として標記され、また条件分岐命令
の場合にはcbrd^＊（Ｎ）として標記される。そして、例
えば第２図に示すような命令列に対しては、遅延スロッ
ト長が［Ｎ］である遅延分岐命令brd（Ｎ）の後に続く
命令列＜ope1＞，＜ope2＞，…，＜opeN＞を、上記遅延
分岐命令brd（Ｎ）により設定される遅延スロット期間
内に順に実行し、その後、上記遅延スロット［Ｎ］を経
た時点で前期遅延分岐命令brd（Ｎ）の分岐先の命令で
ある＜ope＞を実行するものとなっている。

つまり本発明では可変の遅延スロット長を持つ遅延分岐
命令が取り扱われるので、第３図（ａ）に示すよう遅延
分岐命令の分岐先を数スロット先に意図的に延ばし、そ
の遅延スロット期間に他の複数の命令を実行し得るもの
となっている。ちなみに従来にあっては、遅延分岐命令
の遅延スロット長が［１］として固定的に定められてい
るだけなので、第３図（ｂ）に対比して示すように、そ
の遅延スロット期間に高々１の命令しか実行することが
できない。これ故、前述したように命令コード列の最適
化の上での種々の制約が発生し、その最適化が困難化す
ると云う不具合が生じていた。

以下、このような可変の遅延スロット長を持つ遅延分岐
命令による、上述した問題の解決について説明する。

先ず前述した第11図（ａ）に示したような命令列に対し
ては、例えば遅延スロット長が［２］である無条件分岐
命令brd（２）を用いることにより、その不具合を解消
することができる。即ち、この場合には、例えば第４図
（ａ）に示すように、分岐元の無条件分岐命令brdの分
岐先を、その分岐先の無条件分岐命令brdの分岐先に変
更し（brd A→brd B）、かつ、その遅延スロット長を
［２］とし、更に、分岐先の無条件分岐命令の直後の命
令を分岐元の無条件分岐命令の直後の命令の後に複写す
るような（brd B→brd（Ｎ） B）最適化を行えば良い。

この場合、前述した第11図（ｂ）に示した最適化のよう
に、命令＜ope1＞，＜ope2＞のいずれかがnop命令であ
る必要はない。また第11図（ｃ）に示した最適化のよう
に、命令＜ope1＞を分岐命令brd（Ｎ） Bの前に移動す
る必要が無いので、その命令＜ope1＞とその直前の命令
との間のインタロックを考慮する必要はない。但し、命
令＜ope1＞＜ope2＞の間のインタロックの可能性につい
ては十分に考慮する必要がある。このような新しい最適
化は非常に単純であり、且つその最適化に成功する可能
性が非常に高いものである。

一方、第12図（ａ）に示したような命令列に対しては、
例えば同様にして遅延スロット長［２］の条件分岐命令
cbrd（２）を準備する。このような条件分岐命令cbrd
（２）を用いれば、先の無条件分岐の場合と同様にし
て、その分岐元の分岐命令cbrd cc,Aをcbod（２） cc,B
に変更することで、第４図（ｂ）に示すように最適化す
ることが可能となる。

この場合にも、前述した第12図（ｂ）に示した最適化の
ように、命令＜ope1＞を分岐命令cbrdの前に移動する必
要がないので、命令＜ope1＞がコンディション・コード
を変えるか否かを考慮する必要がなくなる。また第12図
（ｃ）に示した最適化のように、新たな分岐命令を挿入
する必要もないので、確実にプログラムの実行時間を短
くすることが可能となる。

また前述した第13図（ａ）に示したような命令列に対し
ても、例えば遅延スロット長が［２］の条件分岐命令cb
rd^＊ （２）を準備する。そしてこの条件分岐命令cbrd
^＊ （２）を用い、条件分岐命令cbrd^＊ cc,Aをcbrd^＊
（２） cc,Bに変更することで、例えば第４図（ｃ）
に示すように最適化することが可能となる。尚、条件分
岐命令cbrd^＊は、その条件不成立時には遅延スロットに
存在する命令の実行を取消すものである。この場合に
も、前述した第13図（ｂ）に示した最適化のように新た
な分岐命令を挿入する必要がないので、そのプログラム
の実行時間を確実に短くすることが可能となる。

尚、第図５（ａ）に示すように命令列が第１の命令、イ
ンタロックを防止するためのnop命令、第２の命令、
…、第Ｍ＋１（Ｍは整数とする）の命令、無条件分岐命
令、の順番で並んでいる場合について考える。従来、こ
のような命令列は、前記命令＜opeM＋１＞のＭが［１］
でなければ最適化の対象にならなかったものである。

このような命令列については、一般的には命令のスケジ
ューリングにより、例えば第６図（ａ）に示すように並
べ変えることができる。このようにスケジューリングさ
れた命令列の場合には、上記nop命令が分岐命令brの２
スロット前（遅延スロット長＋１スロット前）に置かれ
るときにだけ、つまり［Ｍ＝１］の形になるときにだ
け、例えば第６図（ｂ）に示すような最適化が可能であ
る。但し、上記分岐命令brは遅延スロット長［０］の無
条件分岐命令を表している。尚、遅延スロット期間の全
てがnop命令で埋められている遅延分岐命令brdの場合に
も同様に最適化することが可能である。

しかし前述した遅延スロット長［Ｍ］の遅延分岐命令を
用いれば、例えば第５図（ａ）に示した命令列を、第６
図（ａ）に示したようにスケジューリングすることがで
きないような場合であっても、その命令列を第５（ｂ）
に示すように前記インターロックを防止するためのnop
命令を、前記分岐命令の分岐先が分岐先であり、かつそ
の遅延スロット長を［Ｍ］とする遅延分岐命令に変更
し、更に前記分岐命令を削除することで、直接的に最適
化することが可能となる。従って第５図（ａ）に示すよ
うな命令列をわざわざスケジューリングして第６図
（ａ）に示すような命令列に変換する必要がなくなり、
その最適化を非常に簡単に行うことが可能となる。

このように可変の遅延スロット長を持つ分岐命令を導入
することにより、本発明に係る電子計算機では、従来よ
り問題となっていた最適化の複雑さを解決し、しかも従
来では最適化の対象とならなかった命令列に対しても、
これを効果的に最適化することが可能となる。

ところで一般的に、遅延スロット長が長くなるとその最
適化は難しくなると云われている。その理由は遅延スロ
ット期間内に移動可能な命令の種別に制約があることに
起因する。しかしこのような議論が成立するのは、遅延
スロット長が固定されているとの前提に基づくものであ
る。然し乍ら、前述したように遅延スロット長（期間）
が可変される場合には、逆に長い遅延スロット長を持つ
遅延分岐命令が存在することにより、その長い遅延スロ
ット期間内に移動可能な命令に対する制約が少なくな
り、最適化の観点から見ると幾つかの利点が生じる。

その１つは前述したように、最適化を単純に行うことが
できることと、従来では最適化の対象とならなかった命
令列に対しても最適化を行なうことが可能となると云う
点である。今１つは、新たに導入した遅延スロット長が
可変な遅延分岐命令を含む命令列に対しても、前述した
新たな最適化の手法を一般化して適用できるという点で
ある。

この新たな最適化の手法の一般化した適用について説明
する。例えば前述した第４図（ａ）に示す最適化の一般
化について考えると、この場合には第７図（ａ）に示す
ように分岐元の遅延スロット長［Ｍ］の遅延分岐命令br
d（Ｍ）の分岐先が、遅延スロット長［Ｎ］の遅延分岐
命令brd（Ｎ）であるとして一般化することができる。

しかしてこの場合には、分岐元の遅延分岐命令brd
（Ｍ）の分岐先を、分岐先の遅延分岐命令の分岐先が分
岐先であり、かつ分岐元の遅延分岐命令の遅延スロット
の値と分岐先の遅延分岐命令の遅延スロットの値との合
計を遅延スロット長とする遅延分岐命令に変更し（brd
（Ｍ） A→brd（Ｍ＋Ｎ） B）、更に、分岐先の遅延分
岐命令の後の命令Ｎ個を分岐元の遅延分岐命令の後のＭ
個の命令の後に複写することにより、第７図（ｂ）に示
すように最適化することが可能となる。この最適化に際
しては、その遅延スロット期間内に移動されるどの命令
もnop命令である必要はない。但し、命令＜opeM＞と命
令＜opeM＋１＞との間のインタロックについては注意す
る必要がある。

同様に第８図（ａ）に示すような遅延スロット長が可変
な条件遅延分岐命令cbrd（Ｍ） cc,Aを含む命令列につ
いても第８図（ｂ）に示すように最適化することがで
き、第９図（ａ）に示すような遅延スロット長が可変な
条件遅延分岐命令cbrd^＊ （Ｍ） cc,Aを含む命令列に
ついても第９図（ｂ）に示すように最適化することがで
きる。

いずれの場合であっても、連続する命令＜opeM＞，＜op
eM＋１＞との間のインタロックについては十分に注意す
る必要があるが、条件分岐命令の前の位置に命令が移動
することが無いので、コンディション・コードが変わる
か否かについては注意する必要はない。

但し、このようにして最適化を進めると、分岐命令の遅
延スロット長が長くなる傾向がある。

然し乍ら、遅延スロット期間内におかれた命令列＜ope1
＞，＜ope2＞，…，＜opeM＋Ｎ＞をスケジューリング
し、その遅延スロット期間内から外部に出せるものにつ
いては、例えば遅延分岐命令の前の位置に移動すること
により、必要な遅延スロット長を或る程度短くすること
ができる。また遅延スロット期間内の長い命令列をその
まま新たな最適化の対象としたり、或いはスケジューリ
ングにより新たに最適化の対象となる命令列に変換する
ことも可能である。従って可変の遅延スロット長を持つ
分岐命令を導入しても、従来の最適化の手法をそのまま
一般化し、最適化の複雑さを解消して種々の命令列を効
果的に最適化して、その命令列を効率的に実行すること
が可能となる。

また第10図（ａ）は、命令＜ope1＞，＜ope2＞の間に、
インタロックを防止する為のnop命令を置き、その後に
条件分岐命令が出現する命令列の例を示している。この
場合には、例えば第10図（ｂ）に示すように条件分岐命
令をnop命令の位置に移動させ、命令＜ope1＞，＜ope2
＞の間にインタロックを防止する為にわざわざ設けられ
たnop命令を消し、スロットの無駄な使用をなくすこと
ができる。但し、このような無駄スロットの消去は、常
に可能であると云うものではなく、命令＜ope2＞，…，
＜opeM＋１＞がコンディション・コードを変えない場合
にだけ可能なものである。またこのようにして条件分岐
命令をnop命令の位置に移動させる場合、これによって
連続する命令＜opeM＋１＞，＜opeM＋２＞との間で新た
なインタロックが生じないように配慮する必要があるこ
とは勿論のことである。

次に上述した可変遅延スロット長を持つ遅延分岐命令を
含む命令列を実行する電子計算機（マイクロプロセッ
サ）の命令フェッチ部について説明する。この命令フェ
ッチ部は、前述したように第１図に示す如く構成され
る。

第１図において命令プリフェッチ・レジスタ１は、キャ
ッシュバス２を介してプログラムメモリ（図示せず）か
ら、後述するプログラム・カウンタ３の制御の下で命令
を順次プリフェッチする。この命令プリフェッチ・レジ
スタ１にフェッチされた命令はデコーダ４によりデコー
ドされ、その命令が解釈される。しかしてその命令が可
変遅延スロット長を持つ遅延分岐命令の場合には、その
遅延スロット長の値が分岐カウンタ５に格納され、また
その分岐先アドレスが分岐先アドレス・レジスタ６に格
納される。また前記デコーダ４によりデコードされた命
令が通常の分岐命令の場合には、その分岐命令の分岐先
アドレスはそのままプログラム・カウンタ３に格納され
る。

尚、デコーダ４によりデコードされた命令が上述したよ
うな分岐命令以外の一般的な命令である場合には、前記
プログラム・カウンタ３は命令の実行に伴ってインクリ
メントされるだけである。

さて前記分岐カウンタ５は、そこに格納された遅延スロ
ット長を示す位置が［１］以上ならば、命令の実行に伴
うクロックを受けて［０］になるまでデクリメントす
る。つまり遅延分岐命令のデコードによりその遅延スロ
ット長を示す値が分岐カウンタ５が格納されると、命令
の実行に伴うスロットの進行に伴って分岐カウンタ５に
格納された値がデクリメントされ、遅延分岐命令によっ
て設定された遅延スロットの残りスロット期間が示され
るようになっている。しかしてこの分岐カウンタ５の値
は比較器７にて設定値［１］と比較され、その一致が検
出されたとき遅延スロット期間の終了として判定されて
いる。この時点で前記分岐先アドレス・レジスタ６に格
納されている値（分岐先アドレス）が前記プログラム・
カウンタ３に移される。

セレクタ８は、常時は前記プログラム・カウンタ３の値
を選択して前記プログラム・メモリからの命令の読み出
しを制御し、上述した如く遅延スロット期間の終了が検
出されたときに前記分岐先アドレス・レジスタ６に格納
されている値（分岐先アドレス）を選択することで、命
令の分岐を実現している。

つまりこの命令フェッチ部では、遅延分岐命令が与えら
れたとき、その遅延分岐命令の遅延スロット長を分岐カ
ウンタ５により計測することで、遅延分岐命令の実行を
上記遅延スロット長分だけ意図的に送らせるように構成
されている。

かくしてこのように構成された命令フェッチ部によれ
ば、例えば第３図（ａ）に示すように遅延分岐命令をデ
コードしたのち、その分岐先の命令を実行するまでに複
数スロットに亘る遅延期間が設定されるので、この遅延
スロット期間を利用して他の複数の命令を円滑に実行す
ることができる。

ちなみに従来では、遅延分岐命令の遅延スロット長が
［１］に固定されているので、第３図（ｂ）に示すよう
にその遅延スロット期間（１スロット）内に高々１つの
命令しか実行することができない。この結果、前述した
ように命令コードの最適化を行う場合、その制約から種
々の不具合が生じ、例えば或る命令を遅延分岐命令の実
行前に実行するようにその命令を移動させる等の不具合
があった。この点、可変長の遅延分岐命令を用いる実施
例計算機によれば、遅延分岐命令の分岐先の命令を実行
するフェーズを意図的に遅らせることができるので、そ
の遅延スロット期間を利用して、必要な複数の命令を効
率的に実行することが可能となる。この結果、命令列の
最適化を行う場合でも、これを容易になすことが可能と
なる。

尚、上述した命令コードの最適化を行うに際しては、コ
ンディション・コードを変える算術演算命令や論理演算
命令とは別に、コンディション・コードを変えない算術
演算命令や論理演算命令を用意しておくことも有用であ
る。このようにすれば、例えば条件判定の必要がない演
算の場合、上記コンディション・コードを変えない命令
を用いることにより、その最適化の可能性を更に大きく
することが可能となる。

またコンディション・コードを変えない算術演算命令や
論理演算命令を別に用意することは、条件分岐命令の遅
延スロット内の命令を上記条件分岐命令の前に移動し得
る可能性を高くするので、最適化の自由度を更に大きく
すると云える。

尚、本発明は上述した実施例に限定されるものではな
い。例えば遅延スロット長に関する情報を遅延分岐命令
に持たせる手法としては、遅延分岐命令の命令コード内
に遅延スロット長を直接指定するためのフィールドを用
意したり、或いは遅延スロット長の異なる複数の遅延分
岐命令をそれぞれ独立した命令として用意しておくよう
にしても良い。この場合には、遅延スロット長に関する
情報を格納する為の分岐カウンタ５を省略することが可
能である。分岐カウンタ５を省略する場合には、例えば
遅延スロット長に関する情報をプロセッサの制御部の論
理として組み込んでおくようにすれば良い。また遅延ス
ロット長に関する情報をレジスタやメモリに格納してお
き、レジスタ番号やメモリ・アドレスを指定するするこ
とで、その制御を行うようにしても良い。その他、本発
明はその要旨を逸脱しない範囲で種々変形して実施する
ことができる。

［発明の効果］ 以上詳述したように本発明によれば、遅延分岐命令の分
岐先が遅延分岐命令である場合や、遅延分岐命令より数
ステップ前にnop命令がある場合のように、従来では最
適化が複雑であった命令列に対しても、これを簡易に最
適化して効率的に命令を実行することが可能となる。し
かも最適化の際の制約条件を大幅に緩和することがで
き、従来では最適化の対象とならなかった幾つかの命令
列に対しても、その最適化を行なうことを可能とする等
の実用上多大なる効果が奏せられる。

【図面の簡単な説明】

第１図は本発明の一実施例に係る遅延分岐命令を実行す
る命令フェッチ部の構成例を示す図、第２図は本発明に
おける遅延分岐命令を含む命令列の実行順序を示す図、
第３図は遅延分岐命令のパイプライン処理を表す図、第
４図乃至第10図はそれぞれ本発明に係る遅延分岐命令を
含む命令列の最適化の手法を示す図である。また第11図
乃至第14図はそれぞれ従来の最適化の手法を示す図、第
15図はインタロックの発生とその回避の状況を示す図で
ある。 １……命令プリフェッチ・レジスタ、２……キャッシュ
・バス、３……プログラム・カウンタ、４……デコー
ダ、５……分岐カウンタ、６……分岐先アドレス・レジ
スタ、７……比較器、８……セレクタ。

Claims (1)

【特許請求の範囲】
1. 【請求項１】命令を順次取得する命令プリフェッチレジ
   スタと、 前記取得された命令を解釈するデコーダと、 前記解釈された命令が、遅延スロット長が可変である遅
   延分岐命令または遅延スロット長が異なる複数の遅延分
   岐命令の場合に、前記分岐命令の分岐先アドレスを格納
   する分岐先アドレスレジスタと、 前記解釈された命令が、遅延スロット長が可変である遅
   延分岐命令または遅延スロット長が異なる複数の遅延分
   岐命令の場合に、前記分岐命令の遅延スロット長の値が
   格納され、命令の同期をとるためのクロック信号に応じ
   て前記格納された遅延スロット長の値を減少する分岐カ
   ウンタと、 遅延スロット期間終了を判定するための設定値と前記分
   岐カウンタに格納された値とを比較し、該比較により一
   致のときには遅延スロット期間の終了を検出する比較器
   と、 前記デコーダによりデコードされた命令が前記遅延分岐
   命令でない分岐命令の場合には、該分岐命令の分岐先ア
   ドレスが格納され、前記デコーダによりデコードされた
   命令が分岐命令ではない場合には、格納されているアド
   レスの次のアドレスが格納され、前記遅延スロット期間
   の終了が検出された場合には、前記分岐先アドレスレジ
   スタに格納されているアドレスが格納されるプログラム
   カウンタと、 前記遅延スロット期間の終了が検出されたときに前記分
   岐先アドレスレジスタに格納されている値を選択し、前
   記遅延スロット期間終了が検出されないときには、前記
   プログラムカウンタの値を選択することにより、次に取
   得する命令の制御を行うセレクタとを備え、 無条件分岐命令の分岐先が無条件分岐命令であるときに
   は、分岐元の無条件分岐命令の分岐先を、分岐先の無条
   件分岐命令の分岐先が分岐先であり、かつ遅延スロット
   長を［２］とする遅延分岐命令に変更し、更に、分岐先
   の無条件分岐命令の直後の命令を分岐元の無条件分岐命
   令の直後の命令の後に複写する最適化を行い、 命令列が第１の命令、インタロックを防止するためのno
   p命令、第２の命令、…、第Ｍ＋１（Ｍは整数とする）
   の命令、無条件分岐命令、の順番でが並んでいるときに
   は、前記nop命令を、前記無条件分岐命令の分岐先が分
   岐先であり、かつ遅延スロット長を［Ｍ］とする遅延分
   岐命令に変更し、更に、前記無条件分岐命令を削除する
   最適化を行い、 遅延スロット長［Ｍ］の遅延分岐命令の分岐先が、遅延
   スロット長［Ｎ］（Ｎは整数とする）の遅延分岐命令で
   あるときには、分岐元の遅延分岐命令を、分岐先の遅延
   分岐命令の分岐先が分岐先であり、かつ分岐元の遅延分
   岐命令の遅延スロットの値と分岐先の遅延分岐命令の遅
   延スロットの値との合計を遅延スロット長とする遅延分
   岐命令に変更し、更に、分岐先の遅延分岐命令の後の命
   令Ｎ個を分岐元の遅延分岐命令の後のＭ個の命令の後に
   複写する最適化を行うことを特徴とするパイプライン機
   構を持つ電子計算機。