組み込み向け言語CbCのGCC上の実装 http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html

組み込み向け言語Continuation based CのGCC上の実装

与儀健人 (並列信頼研究室) <kent@cr.ie.u-ryukyu.ac.jp>

研究の背景

なにが問題になるのか？

研究目的

状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する

条件

Continuation based Cの提案

継続を基本とする記述言語CbC

継続とはなんなのか？

継続

CbCでの軽量継続

コードセグメントと軽量継続の記述

typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i;
  i = atoi(argv[1]);
  goto factor(i, print_fact);
}
code factor(int x, NEXT next) {
  goto factor0(1, x, next);
}
code factor0(int prod,int x,NEXT next) {
  if (x >= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    goto (*next)(prod);
  }
}
code print_fact(int value) {
  printf("factorial = %d\n", value);
  exit(0);
}

実際のプログラム記述は？

これまでのCbC

2000
micro-cをベースとしたコンパイラの完成
x86, PowerPC, ARM, MIPS.
2002
CbCを用いた分散計算
2005
CbCを用いたプログラム分割手法
2006
CbCによるSPUマシンのシミュレータ
2007
時相論理をベースとしたCbCプログラムの検証
2008
GCCをベースとしたコンパイラが開発される
2010
GCCベースコンパイラを実用レベルに拡張

本研究での取り組み

取り組み

First
GCCにて実用レベルのCbCプログラムを動作可能にする
  • 軽量継続の実装、これまでの制限の除去
  • x86アーキテクチャにて高速化を行った
  • PowerPCアーキテクチャでの間接継続の追加
Second
C言語との相互利用を可能にした
Third
ソースコードメンテナンス性の向上

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

First: 軽量継続の実装

軽量継続を実装するには？

そこで、末尾呼出をGCCに強制させる必要がある

First: 軽量継続の実装

末尾呼出ってなに？

First: 軽量継続の実装

末尾呼出ってなに？

この末尾呼出(TCE)を強制して軽量継続を実装！

First: 軽量継続の実装

プログラム実行時のスタックの変化

First: x86における高速化

軽量継続は実装されたが、やはりmicro-cに比べると遅い

fastcallの導入

First: x86における高速化

fastcallの強制

これで軽量継続制御が高速化される！

First: CbCコンパイラ実装の評価

CbCGCCとmicro-cで性能の比較

実行環境

First: 性能評価（速度比較） vs.旧ver

速度測定結果(単位:秒)

新CbCGCC 旧CbCGCC
最適化無し 最適化有り 最適化無し 最適化有り
x86/OS X 5.907 2.434 4.668 3.048
x86/Linux 5.715 2.401 4.525 2.851

評価

First: 性能評価（速度比較）

速度測定結果(単位:秒)

最適化なしのGCC 最適化付きのGCC micro-c
x86/OS X 5.901 2.434 2.857
x86/Linux 5.732 2.401 2.254
ppc/OS X 14.875 2.146 4.811
ppc/Linux 19.793 3.955 6.454
ppc/PS3 39.176 5.874 11.121

結果(micro-cとの比較)

この違いはどこから？

Second: Cとの相互利用

なぜそれが必要か

環境付き継続の導入

Second: Cとの相互利用

typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i,a;
  i = atoi(argv[1]);
  a = factor(i);
  printf("%d! = %d\n", a);
}
int factor(int x) {
  NEXT ret = __return;
  goto factor0(1, x, ret);
}
code
factor0(int prod,int x,NEXT next) {
  if (x >= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    goto (*next)(prod);
  }
}

環境付き継続の使用例

Second: Cとの相互利用

内部関数を用いた実装

int factor(int x) {
   int retval;

   code __return(int val) {
      retval = val;
      goto label;
   }
   if (0) {
     label:
      return retval;
   }

   NEXT ret = __return;
   goto factor0(1, x, ret);
}

Second: Cとの相互利用・評価

この取り組みにより

まとめ

本研究での取り組み

First
CbCGCCにて実用レベルのCbCプログラムが動作可能となった
  • 軽量継続における引数順序の制限を取り除いた
  • PowerPCでの間接継続の制限を取り除いた
  • x86アーキテクチャにて高速化を行った
Second
Cとの相互利用性の向上
Third
ソースコードメンテナンス性の向上

まとめ

本研究での成果

成果1
CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
成果2
CbCが多数のアーキテクチャに対応
  • 20以上のアーキテクチャ
  • 特に64bitのx86, SPUがうれしい
成果3
CbCの高速化
  • x86においてmicro-cと互角の速度を達成
  • PowerPCでは2倍の速度

今後の課題

CbC言語の今後

おわり

ありがとうございました

継続とはなんなのか？

継続

CbCでの軽量継続

コードセグメントと軽量継続の記述

typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i;
  i = atoi(argv[1]);
  goto factor(i, print_fact);
}
code factor(int x, NEXT next) {
  goto factor0(1, x, next);
}
code factor0(int prod,int x,NEXT next) {
  if (x >= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    goto (*next)(prod);
  }
}
code print_fact(int value) {
  printf("factorial = %d\n", value);
  exit(0);
}

実際のプログラム記述は？

これまでのCbC

2000
micro-cをベースとしたコンパイラの完成
x86, PowerPC, ARM, MIPS.
2002
CbCを用いた分散計算
2005
CbCを用いたプログラム分割手法
2006
CbCによるSPUマシンのシミュレータ
2007
時相論理をベースとしたCbCプログラムの検証
2008
GCCをベースとしたコンパイラが開発される
2010
GCCベースコンパイラを実用レベルに拡張

本研究での取り組み

取り組み

First
GCCにて実用レベルのCbCプログラムを動作可能にする
  • 軽量継続の実装、これまでの制限の除去
  • x86アーキテクチャにて高速化を行った
Second
C言語との相互利用を可能にした
Third
ソースコードメンテナンス性の向上

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

GNU コンパイラコレクション (GCC)

GCCでのコンパイルの流れ

GCC フロントエンド

GCCにおける構文解析部

つまり、主に修正すべきはこのフロントエンドとなる

GCC ミドルエンド

GIMPLEからRTLへの変換と最適化

RTL

バックエンド

RTLからアセンブラに変換する処理

本研究での取り組み

取り組み

First
GCCにて実用レベルのCbCプログラムを動作可能にする
  • 軽量継続の実装、これまでの制限の除去
  • x86アーキテクチャにて高速化を行った
Second
C言語との互換性の向上
Third
ソースコードメンテナンス性の向上

First: 軽量継続の実装

軽量継続を実装するには？

末尾呼出をGCCに強制させる必要がある

First: 軽量継続の実装

末尾呼出ってなに？

First: 軽量継続の実装

末尾呼出ってなに？

軽量継続ではこの末尾呼出(TCE)を強制する！

First: 軽量継続の実装

末尾呼出による軽量継続の実装

ある条件で末尾呼出が行われなくなる

  1. 呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合
  2. 引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合

First: 軽量継続の実装

末尾呼出による軽量継続の実装

ある条件で末尾呼出が行われなくなる

  1. 呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合 解決済み
  2. 引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合

First: 軽量継続の実装

引数順序の問題の解決

First: 軽量継続の実装

全ての引数を一時変数に退避

これで軽量継続が実装された

First: x86における高速化

軽量継続は実装されたが、やはりmicro-cに比べると遅い

fastcallの導入

First: x86における高速化

fastcallの強制

実際の出力はどうなる？

__code current(int a, int b, int c) {
    goto next(10, 20, 30);
}

First: x86における高速化

実際の出力アセンブラ

fastcallにした場合

current:
    subl    $12, %esp
    movl    $30, 16(%esp)
    movl    $20, %edx
    movl    $10, %ecx
    addl    $12, %esp
    jmp     next

normalcallの場合

current:
    pushl   %ebp
    movl    %esp, %ebp
    movl    $30, 16(%ebp)
    movl    $20, 12(%ebp)
    movl    $10, 8(%ebp)
    leave
    jmp     next

First: CbCコンパイラ実装の評価

CbCGCCとmicro-cで性能の比較

実行環境

First: 性能評価（速度比較） vs.旧ver

速度測定結果(単位:秒)

新CbCGCC 旧CbCGCC
最適化無し 最適化有り 最適化無し 最適化有り
x86/OS X 5.907 2.434 4.668 3.048
x86/Linux 5.715 2.401 4.525 2.851

評価

First: 性能評価（速度比較）

速度測定結果(単位:秒)

最適化なしのGCC 最適化付きのGCC micro-c
x86/OS X 5.901 2.434 2.857
x86/Linux 5.732 2.401 2.254
ppc/OS X 14.875 2.146 4.811
ppc/Linux 19.793 3.955 6.454
ppc/PS3 39.176 5.874 11.121

結果(micro-cとの比較)

First: 性能評価（速度比較）

結果(micro-cとの比較)

この違いはどこから？

First: 性能評価（サイズ比較）

ファイルサイズの比較

結果

CbCGCC
速度最適化		 CbCGCC
サイズ最適化		 micro-c
x86/OS X 9176 9176 9172
x86/Linux 5752 5752 5796
ppc/OS X 8576 8576 12664
ppc/Linux 10068 10068 9876
ppc/PS3 6960 6728 8636

結果考察

Second: Cとの相互利用

なぜそれが必要か

環境付き継続の導入

Second: Cとの相互利用

typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i,a;
  i = atoi(argv[1]);
  a = factor(i);
  printf("%d! = %d\n", a);
}
int factor(int x) {
  NEXT ret = __return;
  goto factor0(1, x, ret);
}
code
factor0(int prod,int x,NEXT next) {
  if (x >= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    goto (*next)(prod);
  }
}

環境付き継続の使用例

Second: Cとの相互利用

どのように実装する？

  1. setjmp()/longjmp()を使って実装可能
    • Cの標準ライブラリの関数
    • しかし余計な環境も保持するためオーバヘッドが大きい
    • 継続の際に渡す引数が一つ増えてしまう
  2. 内部関数
    • GCCの独自拡張
    • 関数内に関数を定義可能
    • 内部関数から外の関数のラベルにgotoできる

内部関数が使いやすい

Second: Cとの相互利用

具体的には

int factor(int x) {
   int retval;

   code __return(int val) {
      retval = val;
      goto label;
   }
   if (0) {
     label:
      return retval;
   }

   NEXT ret = __return;
   goto factor0(1, x, ret);
}

Second: Cとの相互利用・評価

この取り組みにより

Third: メンテナンス性の向上

GCCのアップデートリリースは早い

このリリースに追従して差分をアップデートしたい

Third: メンテナンス性の向上

二つのリポジトリ管理

Third: メンテナンス性の向上

アップデート手順

Third: メンテナンス性の向上・比較

これまでのアップデートは

新しい管理方法により

まとめ

本研究での取り組み

First
CbCGCCにて実用レベルのCbCプログラムが動作可能となった
  • 軽量継続における引数順序の制限を取り除いた
  • PowerPCでの間接継続の制限を取り除いた
  • x86アーキテクチャにて高速化を行った
Second
Cとの相互利用性の向上
Third
ソースコードメンテナンス性の向上

まとめ

本研究での成果

成果1
CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
成果2
CbCが多数のアーキテクチャに対応
  • 20以上のアーキテクチャ
  • 特に64bitのx86, SPUがうれしい
成果3
CbCの高速化
  • x86においてもmicro-cと互角の速度を達成
  • PowerPCでは2倍の速度
成果4
メンテナンス性が向上

今後の課題

CbC言語の今後

おわり

ありがとうございました

Continuation based C

First: PowerPCでの間接継続

継続制御での並列代入

本当に最適化で余分なコードが消えるのか？

最適化しない場合 
 _test:
    stwu r1,-64(r1)
    mr r30,r1
    stw r3,88(r30)
    stw r4,92(r30)
    stw r5,96(r30)
    lwz r0,92(r30)
    stw r0,32(r30)
    lwz r0,96(r30)
    addic r0,r0,1
    stw r0,28(r30)
    lwz r0,88(r30)
    stw r0,24(r30)
    lwz r3,32(r30)
    lwz r4,28(r30)
    lwz r5,24(r30)
    addi r1,r30,64
    lwz r30,-8(r1)
    lwz r31,-4(r1)
    b L_next$stub
最適化した場合 

_test:
    mr r0,r3
    mr r3,r4
    mr r4,r5
    mr r5,r0
    b L_next$stub

Cとの比較について

CbCとCの比較に関して