VMのスタック操作 (未完)

GaucheのVMはごく単純なスタックマシンである。だが、Schemeの場合、first class continuationを実現するために、スタックフレームがヒープにセーブされたり、逆にヒープからスタックに復元されたりという操作が入って来るので、うっかりすると自分でも混乱してバグを持ち込むことがある。後で思い出せるように、ここに整理しておこう。

基本レジスタ

スタック操作に深くかかわるのは次のレジスタ群。

ScmEnvFrame *env

現在の環境のトップ。いわゆるstatic link。直接には、最も内側の静的スコープで見えている環境を指している。 upポインタをたぐってゆけば上の環境に行ける。upポインタはNULLで終端される。

ScmContFrame *cont

現在のコンティニュエーションフレームのトップ。いわゆるactivation record。多くのC言語実装のスタックモデルとは異なり、 Gaucheでは関数の引数フレームより前にコンティニュエーションフレームが積まれる。すなわち、関数fooを呼び出す場合、(1) fooのコンティニュエーションをpush、(2) fooへ渡す引数を計算してpush (3) foo自体をコール、という順序になる。

このため、ある関数が呼ばれた直後、およびその関数からリターンする直前は contはその関数のコンティニュエーションを指しているが、多くの場合は「これから呼び出される関数のコンティニュエーション」を指していることになる。

ScmEnvFrame *argp

これから呼び出すことになる関数へ渡すことになる、構築中の引数フレームへのポインタ。引数フレームが完成していざ関数を呼ぶという段階で、この引数フレームは環境フレームへとつながれる。

Gaucheでは、引数は最初のものから順に評価されスタックに積まれる。引数評価の途中で別の関数を呼ぶ必要がある場合は、作成中の引数フレームもコンティニュエーションの一部として扱われる。

ScmObj *sp

スタックポインタ。 Gauche VMではスタックはアドレスの低い方から高いほうへ伸びる。

ScmObj pc

プログラムカウンタ。Gaucheではプログラムは有向グラフとして表現されており、具体的には単なるリストである。リスト終端に達した時点で現在の処理は終了し、コンティニュエーションフレームがポップされ、そこに記録されている処理を続行する。ポップすべきコンティニュエーションが無ければ、全てのコードの実行終了であるから、 VMのループからreturnする。

ScmObj val0

値レジスタ。式の評価結果はここに返る。push, popインストラクションはこのレジスタとスタックとの間でpush/popを行う。

また、スタックに関するポインタは常に次の条件を満たす。

スタック領域の外からスタック内部を指すポインタは sp、env、cont、argpのみ。このうち、spとargpは常にスタック領域を指しているが、 env、contはヒープ領域を指す可能性がある。

スタック内の環境フレームのチェインとコンティニュエーションフレームのチェインはそれぞれ常に直鎖である(分岐が無い)。つまり、envレジスタから辿って行けば全てのスタック上の環境フレームを辿れるし、contレジスタから辿って行けば全てのスタック上のコンティニュエーションフレームを辿れる。分岐が発生するケース、例えば複数の環境フレームがひとつの環境フレームを指しているというケースはヒープ領域でのみ発生する。

スタックフレーム

環境

環境フレームの構造は次の通り。フレームデータはソースコード上に現われる順番に割り当てられる。

       :         :
       +---------+
       |data[n-1]|    |
       |   :     |    | frame data
       | data[0] |    |
       | size=n  |    - size of the frame (excluding header part)
       |  info   |    - debug information
       |   up    |    - pointer to the upper env
       +---------+
       :         :

引数フレーム

引数フレームは環境フレームと同じで、コード中でも環境フレームの一部として扱われる。但し、準備中の引数フレームにおいてはヘッダ (up, info, size) には情報がセットされていない。関数呼び出しの直前にこれらのフィールドが埋められる。

コンティニュエーション

コンティニュエーションフレームには2種類ある。Schemeで関数を呼ぶ時に使われる通常のフレームと、Cで書いた関数で使われる特殊な C-continuation と呼ばれるフレームである。 C-continuation はargp==NULLであることでマークされる。下は通常のコンティニュエーションフレーム。

       :         :
       +---------+
       |   pc    |   - next PC to be executed
       |  size   |   - size of the partially prepared argument frame
       |  argp   |   - pointer to the partially prepared argument frame
       |   env   |   - pointer to the env to be recovered
       |  prev   |   - pointer to the previous continuation frame
       +---------+
       :         :

C-continuationではsizeワード分だけスタックの上方向に余分なデータが積まれる。

基本的なスタック操作

まず、環境およびコンティニュエーションがヒープに移動されない、最も単純なケースを考える。

通常の関数呼び出し

その関数のコンティニュエーションをpush。この時、作りかけの引数フレームがあれば、その引数フレームへのポインタとサイズをコンティニュエーションフレーム内に保存する。 (マクロPUSH_CONT)。
引数フレームの頭を積む (マクロPUSH_ENV_HDR)
引数を頭から順に評価し、スタックに積んで行く。
リストの第一要素を評価する。結果はval0に残る。これがprocedureで無かったらエラー。 procedureがoptional argumentを取る場合はその調整など行う。
引数フレームのupリンクに、クロージゃの環境へのリンクをセット。 PCに関数本体のコードをセット (実質的にgotoと等価)。

                                                              sp>|         |      sp>|         |
                                                                 +---------+         +---------+
                                          sp>|         |         |  arg[1] |         |  arg[1] |
                                             +.........+         |  arg[0] |         |  arg[0] |
                                             |  size   |         |  size   |         |  size   |
                                             |  info   |         |  info   |         |  info   |
                 argp,sp>|         |    argp>|  up     |    argp>|  up     |argp,env>|  up     |
                         +---------+         +---------+         +---------+         +---------+
                         |  pc     |         |  pc     |         |  pc     |         |  pc     |
                         |  size   |         |  size   |         |  size   |         |  size   |
                         | argp(*3)|         | argp(*3)|         | argp(*3)|         | argp(*3)|
                         |  env(*2)|         |  env(*2)|         |  env(*2)|         |  env(*2)|
  sp>|         |    cont>| prev(*1)|    cont>| prev(*1)|    cont>| prev(*1)|    cont>| prev(*1)|
     +.........+         +---------+         +---------+         +---------+         +---------+
     |  arg[0] |         |  arg[0] |         |  arg[0] |         |  arg[0] |         |  arg[0] |
     |  size   |         |  size   |         |  size   |         |  size   |         |  size   |
     |  info   |         |  info   |         |  info   |         |  info   |         |  info   |
argp>|  up     |      *3>|  up     |      *3>|  up     |      *3>|  up     |      *3>|  up     |
     +---------+         +---------+         +---------+         +---------+         +---------+
     :         :         :         :         :         :         :         :         :         :
     +---------+         +---------+         +---------+         +---------+         +---------+
     |         |         |         |         |         |         |         |         |         |
 env>|  ENV    |   env*2>|  ENV    |   env*2>|  ENV    |   env*2>|  ENV    |      *2>|  ENV    |
     +---------+         +---------+         +---------+         +---------+         +---------+
     :         :         :         :         :         :         :         :         :         :
     +---------+         +---------+         +---------+         +---------+         +---------+
     |         |         |         |         |         |         |         |         |         |
cont>|  CONT   |      *1>|  CONT   |      *1>|  CONT   |      *1>|  CONT   |      *1>|  CONT   |
     +---------+         +---------+         +---------+         +---------+         +---------+
     :         :         :         :         :         :         :         :         :         :

      [before]          [1. push cont]    [2. push env hdr]   [3. prepare args]       [5. call]

関数からのリターン

リターン直前には、contはこの関数のコンティニュエーションを指している。したがってcontの保持するenv, argp, pcおよびその前のcontの値(prev)をレジスタに復帰して実行を続ければ良い。上の図の5から1へ戻るパスである。

注意が必要なのはspの復帰。普通のスタックモデルではポップしたコンティニュエーションの先頭アドレスをspにすれば良いが、Gaucheではコンティニュエーションフレームがヒープに移動されている場合があるので無条件にコンティニュエーションフレームの値を取るわけには行かない。この点に関しては後述する。

末尾呼び出し

末尾呼び出しの場合、作成途中の引数フレームというのは存在しない。

コンティニュエーションを積まずに、直接引数フレームを積む。これから呼ぶ関数のコンティニュエーションは、今の関数のコンティニュエーテョンと同じだから。
引数を頭から順に評価し、スタックに積んで行く。
リストの第一要素を評価する。結果はval0に残る。これがprocedureで無かったらエラー。 procedureがoptional argumentを取る場合はその調整など行う。
スタック上にある現在の関数の環境を破棄し、引数フレームをコンティニュエーションのすぐ上にシフトして、新たな環境とする。
引数フレームのupリンクに、クロージゃの環境へのリンクをセット。 PCに関数本体のコードをセット (実質的にgotoと等価)。

                                          sp>|         | 
                                             +---------+ 
                      sp>|         |         |  arg[1] | 
                         +.........+         |  arg[0] | 
                         |  size   |         |  size   | 
                         |  info   |         |  info   |      sp>|         |      sp>|         | 
  sp>|         |    argp>|  up     |    argp>|  up     |         +---------+         +---------+ 
     +---------+         +---------+         +---------+         |  arg[1] |         |  arg[0] |
     |         |         |         |         |         |         |  arg[0] |         |  arg[0] |
 env>|  ENV    |     env>|  ENV    |     env>|  ENV    |         |  size   |         |  size   |
     +---------+         +---------+         +---------+         |  info   |         |  info   |
     :         :         :         :         :         :argp,env>|  up     |argp,env>|  up     |
     +---------+         +---------+         +---------+         +---------+         +---------+
     |         |         |         |         |         |         |         |         |         |
cont>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |
     +---------+         +---------+         +---------+         +---------+         +---------+
     :         :         :         :         :         :         :         :         :         :

      [before]        [1. push env hdr]   [2. prepare args]    [4. shift args]        [5. call]

ステップ4で引数をシフトすることにより、正しい末尾再帰が実現される。なお、[Kelsey93]によれば、わざわざ引数フレームのシフトを行わずにスタックが伸びるにまかせて、スタックが溢れた時にスタックエリアのガベージコレクションを行うという戦略の方が若干性能が良いらしい。将来の課題として考えておく。

コンティニュエーションが捕捉されていた場合、ステップ4での動作が若干異なる。

ローカルな環境

let等によって新たにローカルな束縛が導入されたら、必要なだけ環境フレームをスタックから取得する (下図の1)。このフォームが末尾式でない場合は、フォームを抜ける時に環境フレームをポップする (下図の2)。このフォームが末尾式の時は、最後の末尾呼び出しでローカルフレームも自動的に捨てられる。

                      sp>|         |
                         +---------+
                         | local[2]|
                         | local[1]|
                         | local[0]|
                         |  size   |
                         |  info   |
  sp>|         |     env>|  up (*1)|         sp>|         |
     +---------+         +---------+            +---------+
     |         |         |         |            |         |
 env>|  ENV    |      *1>|  ENV    |        env>|  ENV    |
     +---------+         +---------+            +---------+
     :         :         :         :            :         :
     +---------+         +---------+            +---------+
     |         |         |         |            |         |
cont>|  CONT   |    cont>|  CONT   |       cont>|  CONT   |
     +---------+         +---------+            +---------+
     :         :         :         :            :         : 

      [before]        [1. enter let]     [2. exit let (non-tail)]

環境のセーブ

lambdaフォームによりクロージャが作成されると、その時点での環境フレームのリストを、envポインタから順に手繰ってヒープにコピーする。 (もしこのlambdaフォームがその場でapplyされるだけならば、ここで環境フレームをコピーすることは無駄になる。真っ当にフロー解析を行えばこのようなケースで最適化可能だが、まだ手をつけてはいない。)

環境フレームのセーブに伴って、気をつけなければならないことが2点ある。

コピーされたフレームを指しているポインタの変更

スタックフレーム内には、コピーされた環境フレームを指していたポインタがあるので、それらのポインタをコピー後のフレームを指すように変更しなければならない。

この操作は一見大変そうだが、スタック内のポインタの関係を考えると、調べるべきは現在のコンティニュエーションチェインのみである。

ローカル環境をポップした時のspの値

環境がセーブされていなければ、ローカル環境のポップは上の図にあったように

   sp  = env
   env = env->up

で済む。しかし、環境がセーブされた場合はenvはヒープ領域を指しているので、 spの値として使うわけには行かない。

そこで、原則としてこの場合のspの復帰は現在のspの値からの相対距離で行う。すなわち、

   sp  = sp - env->up->size
   env = env->up

とするのだ。

実は、捕捉されていたコンティニュエーションが再起動されていた場合にはこの関係は成り立たないのだが、その場合は上の計算でspがスタックの底を下回るから検出できる。 spは単にスタックボトムにしておけば良い。

下図は、ローカル環境下でクロージャが作られて、ローカル環境がポップされた場合の例。

                       sp>|         |      sp>|         |
                          +---------+         +---------+
                          |   :     |         |/////////|
                          |  size   |         |/////////|
                          |  info   |         |/////////|
   sp>|         |     env>|  up(*3) |         |/////////|      sp>|         |
      +---------+         +---------+         |/////////|         +---------+
      |   :     |         |   :     |         |/////////|         |/////////|
      |  size   |         |  size   |         |/////////|         |/////////|
      |  info   |         |  info   |         |/////////|         |/////////|
  env>|  up(*1) |      *3>|  up(*1) |         |/////////|         |/////////|
      +---------+         +---------+         +---------+         +---------+
      |         |         |         |         |         |         |         |
 cont>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |
      +---------+         +---------+         +---------+         +---------+
      :         :         :         :         :         :         :         : 


      *1->heap            *1->heap            env->heap

      [before]         [push local env]    [closure is created.  [pop local env]
                                            env chain is saved]

ローカル環境の上でtail callの準備がなされ、さらに別の関数へのcallが準備されている段階で環境がコピーされるケース。


                       sp>|         |
   sp>|         |         +.........+
      +.........+         | closure |
      |   :     |         |  :      |
 argp>|   :     |    argp>|  :      |
      +---------+         +---------+
      | pc      |         | pc      |
      | size    |         | size    |
      | argp(*5)|         | argp(*5)|
      | env(*4) |         | env(*4) |      sp>|         |
 cont>| prev(*2)|    cont>| prev(*2)|         +---------+
      +---------+         +---------+         | arg[n]  |
      |   :     |         |  :      |         |  :      |
   *5>|   :     |      *5>|  :      |    argp>|  :      |
      +---------+         +---------+         +---------+
      |   :     |         |/////////|         |/////////|
      |  size   |         |/////////|         |/////////|
      |  info   |         |/////////|         |/////////|
env*4>|  up(*3) |         |/////////|         |/////////|
      +---------+         |/////////|         |/////////|      sp>|         |
      |   :     |         |/////////|         |/////////|         +---------+
      |  size   |         |/////////|         |/////////|         | arg[n]  |
      |  info   |         |/////////|         |/////////|         |  :      |
   *3>|  up(*1) |         |/////////|         |/////////|env,argp>|  :      |
      +---------+         +---------+         +---------+         +---------+
      |         |         |         |         |         |         |         |
   *2>|  CONT   |      *2>|  CONT   |    cont>|  CONT   |    cont>|  CONT   |
      +---------+         +---------+         +---------+         +---------+
      :         :         :         :         :         :         :         : 


       *1->heap          env=*4->heap         env=*3->heap

      [before]     [env chain is saved,    [procedure returned.  [shift args,
                    closure keeps pointer   the result is         and tail call]
                    to the saved env.    ]  pushed.  env keeps
                                            pointing heap.]

コンティニュエーションのセーブ

コンティニュエーションをfirst classにするためには、コンティニュエーションが call/ccによって捕捉された時点でコンティニュエーションフレームをヒープにセーブする必要がある。 (これも、クロージャの場合と同様に、作られたコンティニュエーションのエクステントがローカルに決定できる場合はコピーを避けることができる筈だが、それを決定するのは容易ではない)。

コンティニュエーションフレームのコピーの際には、それが保持している「作りかけの引数フレーム」もコピーする必要がある。

なお、Gaucheではコンティニュエーションは捕捉時にヒープにコピーされ、以降はそのままヒープから参照される。作りかけの引数フレームのみが必要に応じてスタックエリアにコピーバックされる。

捕捉されたコンティニュエーションが必ずしも起動されるとは限らないこと、及び複数回起動されるケースが現実にはそれほど多くないことを考えると、 [Hieb90]のような、コンティニュエーションの作成時にコピーを行わない戦略の方が有利であると考えられる。[Burson94]の方法も興味深い (でも引数フレームはやっぱりコピーが必要だと思うのだが)。いずれも、スタックエリアのガベージコレクションが前提となる。

コンティニュエーションフレームがセーブされるのは、 call/ccが呼ばれた時のみである。その動作を以下に示す。コンティニュエーションフレームがヒープにコピーされると、それらが指している環境も同様にヒープにコピーされる。その時点でスタックには何も情報は残っていない。したがって、call/ccから復帰する時、もしくは捕捉されたコンティニュエーションが起動される時は、spは一気にスタックボトムまで戻り、その上でcall/ccを呼んだ時にセーブされていた引数フレームがコピーされる。

      sp>|         |        sp>|         |
         +---------+           +---------+
         |  arg[0] |           |  arg[0] |
         |  size   |           |  size   |
         |  info   |           |  info   |
     env>|  up     |       env>|  up     |
         +---------+           +---------+
         |  pc     |           :         :
         |  size   |           : (none)  :
         | argp(*3)|           :         :
         |  env(*2)|           :         :
    cont>| prev(*1)|           :         :
         +---------+           :         :
         |         |           :         :
      *3>|  ARG    |           :         :
         +---------+           :         :
         :         :           :         :
         +---------+           :         :
         |         |           :         :
      *2>|  ENV    |           :         :
         +---------+           :         :
         :         :           :         :
         +---------+           :         :
         |         |           :         :                        sp>|         |
      *1>|  CONT   |           :         :                           +---------+
         +---------+           :         :                           |         |
         :         :           :         :                  argp,env>| ARG     |
 (bottom)+=========+           +=========+                           +=========+
                                    
                                          Heap                                  Heap 
                               +---------+     +---------+           +---------+     +---------+
                               |  pc     |     |         |           |  pc     |     |         |
                               |  size   |     |  ARG    |           |  size   |     |  ARG    |
                               |  argp  ------>+---------+           |  argp  ------>+---------+
                               |  env   ----\                        |  env   ----\
                          cont>|  prev  --\ |  +---------+      cont>|  prev  --\ |  +---------+
                               +---------+| |  |         |           +---------+| |  |         |
                                          | |  |  ENV    |                      | |  |  ENV    | 
                            /-------------/ \->+---------+        /-------------/ \->+---------+
                            |                                     |
                            |  +---------+                        |  +---------+
                            |  |         |                        |  |         |
                            |  |  CONT   |                        |  |  CONT   |
                            \->+---------+                        \->+---------+
                             
                                            
     [just after call/cc       [continuations are copied             [saved continuation is
      is invoked     ]          to the heap.  Nothing but             invoked.  all the stack is
                                the argument frame of call/cc         discarded, and the saved
                                remains in the stack.       ]         argument frame is copied
                                                                      to the stack.             ]

SchemeからC関数の呼び出し

Cで実装された関数(subr)が呼ばれる場合も、そのシーケンスは上で述べたものと全く同様である。 subrには、引数フレームのデータの先頭アドレスとそのサイズが渡される。C側からは、引数がScmObjのアレイで渡されたように見える。

C関数から復帰すると、その戻り値がval0に保存され、コンティニュエーションフレームがpopされる。

C関数からSchemeの呼び出し

スタックのオーバーフロー

スタックサイズは有限であるから、深い再帰呼び出しなどがあると当然溢れる可能性がある。どこかでオーバーフローを検出してやらねばならない。

オーバーフローの検出

どこで検出するのが一番効率が良いだろうか。方法はいくつか考えられる。

スタックを増大させるインストラクション (PUSH, PRE_CALL, PRE_TAIL, DUP, LET, VALUES_BIND) の中。これが一番簡単だが、 PUSHなど出現頻度の高いインストラクションを重くするのは性能に響きそうだ。(implicit check)
PUSHやDUPを使う時は、だいたいいくつ使うかがコンパイル時に分かる (関数呼び出しであれば、引数の数だけPUSHする、など)。したがって、PUSHとDUPの中でスタックをチェックするかわりに、コンパイラが明示的にCHECK_STACKというインストラクションを適宜挿入して、その中でチェックする。 CHECK_STACKを挿入する場所は通常の関数呼び出しの前、インライン関数呼び出しの前、暗黙のインライン関数呼び出し (quasiquoteや、 case文) の前。(explicit check)
関数ごとに、最大のスタックの深さをコンパイル時に計算して、関数に入る時に一度だけチェック。具体的には、lambda式のボディの先頭にCHECK_STACK インストラクションを挿入。applyのスタック使用量は実行時までわからないので、それは実行時にチェック。 (function check)

とりあえず簡易ベンチマークしてみる。上の3つの方法と、オーバーフロー検出を行わない(no check)場合との対比。テストに用いたのはPentiumIII/450MHz, 128MBメモリ、Linux 2.2、 gcc 2.91.66 で -O2でコンパイル。goshは-fno-source-info (デバッグ情報無し)で実行。出力はすべて/dev/null行き。

プログラム	user time (秒)				プログラムの説明
プログラム	no check	implicit check	explicit check	function check	プログラムの説明
nqueen	2.27	2.39	2.45	2.34	8-queenを総当たりで解く。リスト処理中心。
morph	2.34	2.38	2.41	2.53	形態素解析。木探索&バックトラック。
compplot	115.6	117.4	117.2	117.3	複素関数の値域のプロット。数値計算中心。
sum-rec	-	3.68	3.57	3.78	sum(0..N) を再帰で計算。深い再帰のテスト。

ちょいと注釈。function checkでは実際にコンパイラに最大スタック深さを計算させるかわりに、一律な大きさのチェックで済ませた。sum-recはスタックオーバフローが起こるのでno checkでは実行不可。

やっぱりそれなりに性能へのインパクトはあるようだ。explicit checkやfunction check の方がimplicit checkよりもチェックの回数は少ないのに性能がそれほど出ていないのは、 explicit checkやfunction checkの方がCHECK_STACKインストラクションを挿入した分だけ総インストラクション数が多くなるためだろう。どうやら、多少ひとつのインストラクションにかかる時間が増えたとしても、総インストラクション数を増やさない方が性能には貢献するようだ。 function checkは一番チェックが少なく、総インストラクション数もexplicit checkより少ないはずだが、applyの実行時にペナルティがある (トランポリンのために実行時に挿入されるインストラクションにCHECK_STACKが追加されるため)。悪化している場合があるのはそのせいか。

結局どれでもあんまり変わらなさそうなので、とりあえずは一番実装が楽な implicit checkで行くことにする。ただし、理屈の上では、function checkを用いて、かつCHECK_STACKインストラクションを使わない (VMループ内で直接、必要な箇所でチェックを行う)、というのがさらに速そうだ。将来の課題。

オーバーフローの対応

今のところは手を抜いて、call/ccのコードを流用している。すなわち、スタックオーバフローが起こりそうになった時点で、あたかもcall/ccが呼ばれたかのように、スタックの内容が全てヒープに移されるのだ。以降、復帰してゆく時はコンティニュエーションフレームはヒープから直接参照される。

参考文献

[Kelsey93] Richard A. Kelsey, "Tail-Recursive Stack Disciplines for an Interpreter", [enhanced version of Technical Report NU-CCS-93-03, Colledge of Computer Science, Northeastern University], ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/stack-gc.ps.gz, 1993.
[Burson94] Scott L. Burson: "Continuations Without Copying", SIGPLAN Notices, 29(5), pp.27-30, 1994.
[Hieb90] Robert Hieb, Kent Dybvig, and Carl Bruggeman, "Representing Control in the Presence of First-Class Continuations", Proceedings of the ACM Conference on Programming Language Design and Implementation, pp.66-77, 1990.