computed goto - MEMO:はてな支店

Gaucheのソースではgotoって使われているんだろうかと思ってのぞいてみたら、vm.cにおもしろそうな箇所発見。

/* We take advantage of GCC's `computed goto' feature
   (see gcc.info, "Labels as Values"). */
#ifdef __GNUC__
#define SWITCH(val) goto *dispatch_table[val];
#define CASE(insn)  SCM_CPP_CAT(LABEL_, insn) :
#define DEFAULT     LABEL_DEFAULT :
#define DISPATCH    /*empty*/
#define NEXT                                            \
    do {                                                \
        if (vm->queueNotEmpty) goto process_queue;      \
        FETCH_INSN(code);                               \
        goto *dispatch_table[SCM_VM_INSN_CODE(code)];   \
    } while (0)
#else /* !__GNUC__ */
#define SWITCH(val) switch (val)
#define CASE(insn)  case insn :
#define DISPATCH    dispatch:
#define NEXT        goto dispatch
#endif

computed gotoはGaucheだけじゃなくて、Ruby1.9、Perl6、Python3.1、PHP5.2でも使われているらしい。

DSAS開発者の部屋:インタプリタ型言語を高速化する computed goto
computed goto という名前を聞き慣れなかったのですが、調べてみると Ruby 1.9 の VM (YARV) や、 Perl6 の VM として開発されとうとうリリースされた Parrot にも採用されている手法でした。
Python3.1をビルドするときには、忘れずに --with-computed-gotos を付けましょう！
http://dsas.blog.klab.org/archives/51393628.html

DSAS開発者の部屋:phpを高速化する computed goto
Python 3.1 だけじゃなくて php をビルドするときも computed goto を試してみて下さい。
http://dsas.blog.klab.org/archives/51395944.html

具体的な使い方。

Using and Porting GNU CC - C 言語ファミリに対する拡張
値としてのラベル
カレントな関数（あるいは、そのラベルを含んでいる関数）の中で定義されたラベルのアドレスを、単項演算子 `&&' で獲得することができます。この値の型は void * です。この値は定数であり、 void * 型の定数が正当であるところではどこでも使うことができます。以下に例を示します。
void *ptr;
...
ptr = &&foo;
この値を使うためには、そのラベルにジャンプすることができる必要があります。これは評価 goto（computed goto）文 (10) goto *exp; で行います。以下に例を示します。
goto *ptr;
評価 goto 文では void * 型の任意の式を使うことができます。
このような定数の用途の１つに、ジャンプ・テーブルとして機能する静的配列の初期化があります。
static void *array[] = { &&foo, &&bar, &&hack };
こうすると、以下のようにインデックスを使ってラベルを選択することができます。
goto *array[i];
http://www.asahi-net.or.jp/~WG5K-ICKW/html/online/gcc-2.8.1/gcc_3.html

関数ポインタと対比するようなサンプルを書いてみた。

#include<stdio.h>

void foo(){
  puts("foo");
}

int main(){
  void (*func)(),*label;

  printf("%d\n",foo);
  func=foo;
  (*func)();

  printf("%d\n",&&bar);
  label=&&bar;
  goto *label;

  puts("dummy");
bar:
  puts("bar");
}

実行結果

$ gcc --version
i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465)
$ gcc test.c
$ ./a.out
8018
foo
8159
bar

関数のアドレスは「関数名そのまま」で取り出し、*をつけてコールする
ラベルのアドレスは「&&ラベル名」で取り出し、*をつけてジャンプする