Continuation based Cの GCC 4.6 上の実装について

  • 大城 信康
  • 琉球大学 並列信頼研究室

    目的と背景(1)

  • 当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を開発している。
  • コードセグメントは並列実行の単位として使うことができ、プログラムの正しさを示す単位としても使用することができる。
  • Many Core での並列実行を高い性能と高い信頼性で実現することができると考えている。
  • 目的と背景(2)

  • CbC のコンパイラは2001年に Micro-C 版、2008年には GCC 4.2 をベースとしたコンパイラが開発された。
  • GCC をベースとした CbC コンパイラは、修正・追加されていく最適化の機能を使用する為に、 GCC のアップデートに合わせ変更する必要がある。
  • 本研究ではCbC コンパイラを GCC-4.6 へとアップデートを行った。
  • 発表内容

    1. CbC の紹介
    2. GCC でのコンパイルの流れ
    3. CbC の実装
    4. Micro-C との性能比較
    5. まとめ

    Continuation based C

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


    コードセグメント

    Continuation Based C

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

  • Cにおいての継続
  • Continuation Based C (軽量継続)

    CbCの継続(軽量継続)

  • 関数コールが無い -> 呼び出し元への復帰がない
  • Cの関数呼び出し CbCの継続

    Continuation based C

    階乗を求めるCbCのプログラム
    __code print_factorial(int prod) {
      printf("factorial = %d\n",prod);
      exit(0); 
    }
    
    __code factorial0(int prod, int x) {
      if ( x >= 1) {
        goto factorial0(prod*x, x-1);
      }else{
        goto print_factorial(prod);
      } 
    }
    	  
    __code factorial(int x) {
      goto factorial0(1, x); 
    }
    
    int main(int argc, char **argv) {
      int i;
      i = atoi(argv[1]);
      goto factorial(i); 
      return 0;
    }
    
  • __code キーワードによるコードセグメントの宣言
  • goto によるコードセグメントへの継続(Cの関数呼び出しと同等)
  • GCC

  • 本来はGnu Compiler Collectionのことを指すが、
    ここで扱うのはGnu C Compilerになる。
  • GCCでは次の4つの内部表現が扱われる。
    1. Generic Tree
    2. GIMPLE
    3. Tree SSA
    4. RTL

    GCC

  • Generic Tree:ソースコードを構文木の形に直したもの
  • GIMPLE: Generic Treeの命令を簡単にした構文木
  • Tree SSA: GIMPLEの中で変数代入を一度しか行わせない形にした構文木
  • RTL: レジスタの割り当てといった低レベルの表現でアセンブラとほぼ同じ命令の表現ができる。
  • GCC

  • CbCの実装においてはGeneric Tree生成部分とRTLへの変換部分に修正が加えられる。
  • Generic Tree生成部分について触れてみる。
  • GCC:Generic Tree

  • Generic Treeではソースコードの内容が FUNCTION_TYPE, CALL_EXPR, MODIFY_EXPR 等と言った形で表される。
  • 値の代入:MODIFY_EXPR 関数呼び出し:CALL_EXPR

    Generic Treeでの表現

    GCC:Generic Tree

  • それぞれの命令はSTATEMENT_LISTでまとめて保持される。
  • ソースコード Generic Treeでの表現
    int main() {
      int a, b;
      a = 3;
      b = func(a, 10);
      return b;
    }
    	

  • CbCの実装においてこのGeneric Treeの生成を意識していくことになる。
  • CbCの実装

    CbCの実装:シンタックスの追加

  • 追加したgotoシンタックスの実際のソースは次のようになる。
  • CbCの実装:シンタックスの追加

    gotoシンタックスの追加

    expr = c_parser_expr_no_commas (parser, NULL);
    if (TREE_CODE(expr.value) == CALL_EXPR )
      {
        location_t loc = c_parser_peek_token (parser)->location;
        cbc_replace_arguments (loc, expr.value);
        TREE_TYPE(expr.value) = void_type_node;
        CbC_IS_CbC_GOTO (expr.value) = 1;
        CALL_EXPR_TAILCALL (expr.value) = 1;
        add_stmt(expr.value);
        stmt = c_finish_return(loc, NULL_TREE, NULL_TREE);
      }
    	
  • cbc_replace_arguments関数は引数のデータを一時的な変数へ避難させる。
  • CALL_EXPR_TAILCALLマクロでtail callフラグを立てる。
  • 最後にc_finish_return関数によりreturn文を生成している。
  • CbCの実装:シンタックスの追加

    gotoシンタックスの追加

  • 最後にリターン文を生成することにより、次へと制御を移させず。また末尾最適化がかかるようになる。
  • 実際のコード GCC 内で処理されるコード
    goto factorial0(1, x); 
    	    
    factorial0(1, x); 
    return;
    	    
  • 末尾最適化(末尾除去)については後ほど詳しく説明する。
  • CbCの実装:引数渡し

  • GCC版コンパイラー開発当初、コンパイルしたCbCのプログラムはMicro-C版に速度面で勝てなかった。
  • そこで、GCC版CbCコンパイラの引数渡しもできるだけレジスタで行うことに。
  • CbCの実装:引数渡し(fastcall)

    fastcall

  • __code で宣言された関数は自動でfastcall属性が付与されるように。
  • if(!TARGET_64BIT) {
      attrs = build_tree_list (get_identifier("fastcall"), NULL_TREE); 
      declspecs_add_attrs(specs, attrs);
     }	  
    	

    Intel64 ではレジスタが増えている為、fastcallは標準でつくようになっている。

    CbCの実装:引数渡し

    引数渡しに使われるレジスタの数(gcc)
    arch int(整数型) float(浮動小数点型) double(浮動小数点型)
    i386 2 0
    (stackを使用)
    0
    (stackを使用)
    x86_64 6 8 8

    CbCの実装:TCE

    Tail Call Elimination(TCE):末尾除去

  • 関数呼び出しをcallではなくjmp命令で行ことでreturnを1度で済ませる最適化。
  • CbCにおけるコードセグメントへの継続はこのTCEを用いて実装されている。
  • CbCの実装:TCE

  • TCEにより関数へjmp命令で処理を移すことを利用。
  • TCEにかかることで、コードセグメントへの継続はjmp命令で行われている。

  • 具体的な実装内容

  • TCEにかかるにはtry_tail_callフラグ次第
  • CbCの実装:TCE

  • try_tail_callフラグはexpand_call関数で落とされる。
  • 次の条件を満たしていないとtry_tail_callフラグを落とす。
    1. caller側とcallee側の戻値の型の一致している。
    2. 関数呼び出しがリターン直前に行われている。
    3. 呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。
    4. 引数の並びのコピーに上書きがない。

    CbCの実装:TCE

  • フラグを落とされない為にコードセグメントは次の条件で作成する。
    1. 型はvoid型で統一。
    2. gotoの直後にreturnを置く。
    3. スタックサイズは固定。
    4. 引数は一旦、一時変数にコピーする。
  • これでコードセグメントへの処理はjmp命令で移ることになる。
  • CbCの実装:環境付き継続

  • CbCにおけるCとの互換性を保つための機能。コードセグメントを呼び出したCの関数に戻ることができる。
  • __returnキーワードを引数に渡すことで使うことができる。
  • 以下の使い方の場合は1を返す。
  • __code c1(__code ret(int,void *),void *env) {
     goto ret(1,env);
    }
    int main() {
     goto c1(__return, __environment);
    }
    	

    __environmentキーワードは関数の環境を保存している。

    CbCの実装:環境付き継続

    実際には以下のコードを生成している。

    goto c1(__return, __environment);
    
    goto c1(({
    	  __label__ _cbc_exit0;
    	  static int retval;
    	  void _cbc_internal_return(int retval_, void *_envp) {
    	    retval = retval_;
    	    goto _cbc_exit0; 
              }
    	  if (0) { 
                _cbc_exit0:
    	    return retval; 
              }
    	  _cbc_internal_return;
    	}), __environment);
    	  

    retval変数はint型になっているが、実際には継続を行った関数と同じ戻値の型となる。

  • 上記のコードをGCC内で生成するのが次のソースとなる。
  • CbCの実装:環境付き継続

    環境付き継続の生成部分:

    {
      tree value, stmt, label, tlab, decl;
      c_parser_consume_token (parser);
    
      stmt = c_begin_stmt_expr ();
      cbc_return_f = c_parser_peek_token (parser)->value;
      location_t location = c_parser_peek_token (parser)->location;
    
      /* create label. (__label__ _cbc_exit0;) */
      label = get_identifier ("_cbc_exit0");
      tlab = declare_label (label);
      C_DECLARED_LABEL_FLAG (tlab) = 1;
      add_stmt (build_stmt (location, DECL_EXPR, tlab));
    
      /* declare retval.  (int retval;) */
      tree decl_cond =
        build_decl (location, VAR_DECL, get_identifier ("retval"),
    		TREE_TYPE (TREE_TYPE (current_function_decl)));
      TREE_STATIC (decl_cond) = 1;
      TREE_USED (decl_cond) = 1;
    
      /* Use thread-local */
      DECL_TLS_MODEL (decl_cond) = decl_default_tls_model (decl_cond);
      DECL_NONLOCAL (decl_cond) = 1;
      add_stmt (build_stmt(location, DECL_EXPR,  pushdecl (decl_cond)));
    
      /* define nested function.  */
      decl =
        cbc_finish_nested_function (location, label, decl_cond);
      TREE_USED(decl) = 1;
    
      /* define if-ed goto label and return statement. */
      cbc_finish_labeled_goto (location, label, decl_cond);
    
      /* get pointer to nested function.  */
      value = build_addr (decl , current_function_decl);
      TREE_USED (current_function_decl) = 1;
      SET_EXPR_LOCATION (value, location);
      add_stmt (value);
    
      TREE_SIDE_EFFECTS (stmt) = 1;
      expr.value = c_finish_stmt_expr (location, stmt);
      expr.original_code = ERROR_MARK;
    }
    	  

    CbCの実装:環境付き継続

    作成されるTree

    環境付き継続:実装の問題

  • 次の方法が考えられる。
  • 環境付き継続:実装の問題

  • クロージャでの実装
  • 問題点
  • 環境付き継続:実装の問題

  • staticでの実装
  • 問題点
  • 環境付き継続:実装の問題

  • static tlsでの実装
  • 現在はこの方法で実装を行なっている。
  • しかし、最適化にかけると正しい値が返ってこない。
    (恐らくTreeの生成の部分が間違っている。)
  • 環境付き継続:その他の実装方法

    CbCの機能の拡張:__rectype の実装

  • 通常、関数の引数に関数ポインタを渡した際は以下の様に使われる。
  • void factorial(int n, int result, void(*print)()){
       :
       (*print)(n,result,print,exit1, envp);
    }
    	
  • 以下の様に扱えるようにしたい。
  • void factorial(int n, int result, void *print){
       :
       (*print)(n,result,print,exit1, envp);
    }
    	

    CbCの機能の拡張:__rectype の実装

  • そこで、__rectype という予約後を作り、以下の宣言を行えるようにした。
  • __code factorial(int n, int result, __rectype *print) {
       :
       (*print)(n,result,print,exit1, envp);
    }
    	

    CbCの機能の拡張:selftype

    selftypeの実装

  • 以下の宣言が行えるようにしたい。
  • typedef sturct node {
     selftype *left;
     selftype *right;
     int num;
    }*NODE
    	

    selftype は struct node を指す。

    Micro-Cとの比較

  • Micro-C,GCC-4.4とGCC-4.6のCbCコンパイラでコンパイルしたプログラムの実行の速度
  • GCC版の最適化無しの場合、引数を全て一時変数に代入するという処理が入る。 その為に明らかに遅くなっていることが分かる。
  • だがGCCの最適化有りの場合はMicro-C版よりも早い。
  • まとめ

    今後の予定