コードセグメント単位での記述と継続を基本としたプログラミング言語

• C の関数よりも細かな単位
• 構文は C と同じだが、C から関数コールとループ制御が取り除かれた形
• コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。

__code cs_a(int num) { : : goto cs_b(); }

継続:現在の処理を実行していく為の情報

Cの継続	CbCの継続(軽量継続)
続く命令のアドレス 命令に必要なデータ スタックに積まれている値(環境)	Cの継続から環境を除外 続く命令とその命令に必要なデータのみ

Tail Call Elimination

void f(int a, int b) { printf("f: a=%d b=%d\n",a,b); return ; } void g(int a, int b){ printf("g: a=%d b=%d\n",a,b); f(a,b); return; } int main() { g(3,4); return 0; }

Tail Call Elimination の条件

• 関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。
• 関数呼び出しがリターン直前に行われている。
• 呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。
• 引数の並びのコピーに上書きがない。

条件回避の為の実装

• コードセグメントの型はvoid型で統一する。
• gotoの直後に自動で return を置く。
• スタックサイズは固定にする。
• 引数は一旦、一時変数にコピーする。

Tail Call Elimination の条件をチェックする関数

• 今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。
• この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく 必要があった。

実装の修正とその利点

• しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。
• 専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。
• また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。

• GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。

インライン展開

• 関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化

void func(){
  A;
  B;
}

int main() {
  func();
  func();
}

int main() {
  A;
  B;
  A;
  B;
}

それぞれの最適化にかかった conv1プログラムの挙動(引数 1)

最適化なし	GCC-4.5の最適化(-O2)	GCC-4.6の最適化(-O2)

• 最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。
• GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。

• 今回の『インライン展開』のように GCC の最適化は日々改良されている。
• また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。
• それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。

• 今回 CbC-GCC を GCC-4.6 へとアップデートを行った。
• アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。
• また、最適化の強制付与やといった実装の修正も行えた。
• 細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。

今後の課題

• LLVM ベースの CbC コンパイラの開発
• google Go 言語への実装の検討

リカーシブタイプの宣言に使う"__rectype"

• 関数宣言時、以下のように引数に自分自身を指す型を入れたい。

  __code func(int, func*);
  

• 上記の宣言ではエラーがでる。その為、以下のような宣言になる。

  __code func(int, __code (*)());
  

• しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。

  __code func(int, __code ()(int, __code()(int, __code(*)(int, ...))))
  

• だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。
• そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。

  __code func(int, rectype*);
  

• conv1 プログラムでは計算と継続を交互に繰り返し行なう。

• しかし状態のいくつかへは関数ポインタとして保存させておき継続を行う。

  __code g(int i,stack sp) { // Caller
      struct f_g0_interface c = 
          (struct f_g0_interface )(sp -= sizeof(struct f_g0_interface));
      c->ret = g_h1;
      c->i_ = i;
      goto h(i+3,sp);
  }
  __code h(int i,stack sp) {
      struct f_g0_interface c = (struct f_g0_interface )sp;
      goto (c->ret)(i+4,sp);
  }
  

• 関数ポインタへの継続はインライン展開されない。

• 環境付き継続: C との互換を取るための機能。継続を行った C の関数に戻ることができる。
• _CbC_return、 _CbC_environment キーワードを使うことで使える。

• 以下の使い方の場合、戻値 1 を返す。

  code c1(code ret(int,void ),void env) {
      goto ret(1,env);
  }
  int main() {
      goto c1(return, environment);
  }
  

• 今回この環境付き継続をスレッドセーフの実装へと修正した。

void funcA(int a, int b) {
  funcB(b, a);
}