[ 目次, 前節, 次節, 索引 ]

gcd-1
 (test (op =) (reg b) (const 0))
 (branch (label after-gcd-1))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd-1))
after-gcd-1
  
gcd-2
 (test (op =) (reg d) (const 0))
 (branch (label after-gcd-2))
 (assign s (op rem) (reg c) (reg d))
 (assign c (reg d))
 (assign d (reg s))
 (goto (label gcd-2))
after-gcd-2

   この計算機には剰余演算の箱二つと等価をテストする箱二つがある. 重複した部品が剰余の箱のように複雑なら, これは計算機を組み立てる経済的な方法ではない. われわれは, そうすることがより大きい計算機の計算の残りの部分に影響しないなら, 両方のGCD計算に同じ部品を使うことで, データパスの部品の重複を避けることが出来る. 制御器がgcd-2に来た時にレジスタaとbの値が必要ないなら(あるいはこれらの値が保護のため, 他のレジスタへ移動出来るなら), 第二のGCD計算でレジスタcとdを使う代りに, 第一の計算と同様, レジスタaとbを使うように計算機を変更出来る. そうすると図5.8に示すような制御器の命令列が得られる.

   われわれは重複したデータパスの部品を除去した. (データパスが再び図5.1のようになった.) しかし制御器は入り口のラベルが違うだけの二つのGCD列を持つ. この二つの列を, その最後で主要な命令列の正しい場所へ分岐し戻る一つの列---gcd サブルーチン(subroutine)---への分岐で取り替えられればもっとよいに違いない. これを次のように実現する: gcdへ分岐する前に, (0か1のような)識別用の値を, 特別なレジスタ continueに置く. gcdサブルーチンの終りで, continueレジスタの値に従いafter-gcd-1かafter-gcd-2のどちらかへ戻る. 図5.9 は結果の制御器の命令列の関係ある部分を示す. これにはgcd命令の単一コピーしかない.

gcd-1
 (test (op =) (reg b) (const 0))
 (branch (label after-gcd-1))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd-1))
after-gcd-1
  
gcd-2
 (test (op =) (reg b) (const 0))
 (branch (label after-gcd-2))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd-2))
after-gcd-2

gcd
 (test (op =) (reg b) (const 0))
 (branch (label gcd-done))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd))
gcd-done
 (test (op =) (reg continue) (const 0))
 (branch (label after-gcd-1))
 (goto (label after-gcd-2))
  
 ;; それを必要とする第一の場所からgcdへ分岐する前に
 ;; continueレジスタに 0 を置く
 (assign continue (const 0))
 (goto (label gcd))
after-gcd-1
  
 ;; gcdの第二の使用の前にcontinueレジスタに 1 を置く
 (assign continue (const 1))
 (goto (label gcd))
after-gcd-2

gcd
 (test (op =) (reg b) (const 0))
 (branch (label gcd-done))
 (assign t (op rem) (reg a) (reg b))
 (assign a (reg b))
 (assign b (reg t))
 (goto (label gcd))
gcd-done
 (goto (reg continue))
  
 ;; gcdを呼び出す前に, gcdから戻るべきラベルを
 ;; continueに代入する.
 (assign continue (label after-gcd-1))
 (goto (label gcd))
after-gcd-1
  
 ;; gcdへの第二の呼出しでは継続は異る.
 (assign continue (label after-gcd-2))
 (goto (label gcd))
after-gcd-2

   これは小さい問題を扱うにはうまい解決法である. しかし制御列に多くのGCD計算があると, 大変なことになる. gcdサブルーチンの後, 実行を続ける場所を決めるため, gcdを使うすべての場所でデータパスでのテストと制御器での分岐命令が必要になる. サブルーチンを実装する更に強力な方法は, サブルーチンが終った時, そこから実行を続ける制御列の入り口のラベルをcontinueレジスタに保持させることである. この戦略の実装には, レジスタ計算機のデータパスと制御器の間に新しい関係が必要になる: その値をレジスタから取り出し, 指示された入り口から実行を続けるのに使う, 制御列のラベルをレジスタに代入する方法が必要である.

   この機能を実現するため, レジスタ計算機の言語のassign命令を拡張し, 命令列からラベルを値として(特別な定数として)レジスタに代入出来るようにする. またgoto命令も拡張し, 定数ラベルで記述した入り口だけでなく, レジスタの内容で記述した入り口からも実行が続けられるようにする. これらの新しい構成を使い, gcdサブルーチンをcontinueレジスタに格納された場所への分岐で終らせることが出来る. これにより, 図5.10に示した命令列が出来る.

   一つを超えるサブルーチンのある計算機は, 複数の継続レジスタ(例えばgcd-continueやfactorial-continue)を使うことが出来るか, またすべてのサブルーチンに単一のcontinueレジスタを共有させることが出来る. 共有は経済的だが, 別のサブルーチン(sub2)を呼び出すサブルーチン(sub1)があれば, 注意しなければならない. sub2を呼ぶためにcontinueの設定をする前に, sub1がcontinueの内容を, 他のレジスタに退避しなければ, sub1は終った時に, どこへ戻るか分らなくなる. 次の節の再帰を扱うために開発した機構も, 入れ子サブルーチンの呼出しの, この問題によりよい解決法を提供する.

[ 目次, 前節, 次節, 索引 ]