\chapter{実装}
第 \ref{chapter:CbC}, \ref{chapter:LLVM/clang} 章をもとに LLVM, clang への CbC コンパイル機能の実装を行う. 実装の流れは以下のようになる.
\begin{enumerate}
  \item clang 側での \_\_code 型の追加.
  \item LLVM 側での \_\_code 型の追加.
  \item 継続のための goto syntax の構文解析.
  \item Tail call elimination の条件の達成.
  \item 環境付き継続の実装.
\end{enumerate}
　\_\_code 型の追加が clang 側と LLVM 側とで分かれているのはそれぞれが型を扱うために使うクラスが異なるからである. \\
　以下の節ではそれぞれの工程について詳しく説明する. \\
　また, 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.

\section{clang 側での \_\_code 型の追加とその構文解析}
\label{sec:add__code}
まず最初に関数が code segment であることを示す \_\_code 型の追加を行う. そのためには \_\_code を予約語として定義する必要がある. clang では, 予約語は全て \$(CLANG)/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 次のように変更を加えて \_\_code を追加した. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. また, 同時に定義されている \_\_return, \_\_environment は環境付き継続のための予約語である. \\
\begin{lstlisting}[frame=lrbt,label=token,caption={TokenKinds.def}]
       :
KEYWORD(__func__                    , KEYALL)
KEYWORD(__objc_yes                  , KEYALL)
KEYWORD(__objc_no                   , KEYALL)

#ifndef noCbC // CbC Keywords.
KEYWORD(__code                      , KEYALL)
KEYWORD(__return                    , KEYALL)
KEYWORD(__environment               , KEYALL)
#endif
       :
\end{lstlisting}
　予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. したがって, 次に clang に \_\_code 型を認識させる必要がある.\\
　clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを以下のように編集した.\\
\begin{lstlisting}[frame=lrbt,label=TST,caption={Specifiers.h}]
enum TypeSpecifierType {
  TST_unspecified,
  TST_void,
       :
#ifndef noCbC
    TST___code,
#endif
       :
\end{lstlisting}
　これに加えてさらに\ref{sec:QualType} 節で説明した QualType が用いる Type を作らなければならない. この定義は \$(CLANG)/include/clang/AST/BuiltinTypes.def で行われているので, これを以下のように編集した. ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. \_\_code 型は符号無し,有りといった性質を保つ必要はなく, また void 型が BUILTIN\_TYPE を利用していることから \_\_code 型も BUILTIN\_TYPE を使うべきだと判断した.\\
\begin{lstlisting}[frame=lrbt,label=clangType,caption={BuiltinTypes.def}]
       :
// 'bool' in C++, '_Bool' in C99
UNSIGNED_TYPE(Bool, BoolTy)

// 'char' for targets where it's unsigned
SHARED_SINGLETON_TYPE(UNSIGNED_TYPE(Char_U, CharTy))

// 'unsigned char', explicitly qualified
UNSIGNED_TYPE(UChar, UnsignedCharTy)

#ifndef noCbC
BUILTIN_TYPE(__Code, __CodeTy)
#endif
       :
\end{lstlisting}
　これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. よって次に \_\_code 型を解析できるよう clang に変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.\\
\begin{lstlisting}[frame=lrbt,label=parse__Code,caption={\_\_code の parse}]
  case tok::kw___code: {
    LangOptions* LOP;
    LOP = const_cast<LangOptions*>(&getLangOpts());
    LOP->HasCodeSegment = 1;
    isInvalid = DS.SetTypeSpecType(DeclSpec::TST___code, Loc, PrevSpec, DiagID);
    break;
  }
\end{lstlisting}
　重要なのは 5行目で, ここで \_\_code 型が DeclSpec に登録される. DeclSpec は 型の識別子を持つためのクラスであり, 後に \ref{sec:QualType} 節で述べた QualType に変換される. \\
　その他の処理について, 最初にある LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, tailcallopt を有効化するためである. LangOptions が管理するオプションは \$(CLANG)/include/clang/Basic/LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.
\begin{lstlisting}[frame=lrbt,label=langOpt,caption={LangOptions の追加}]
       :
LANGOPT(ApplePragmaPack, 1, 0, "Apple gcc-compatible #pragma pack handling")

BENIGN_LANGOPT(RetainCommentsFromSystemHeaders, 1, 0, "retain documentation comments from system headers in the AST")

#ifndef noCbC
LANGOPT(HasCodeSegment          , 1, 0, "CbC")
#endif
       :
\end{lstlisting}


\section{LLVM 側での \_\_code 型の追加}
LLVM でも clang と同様に \_\_code 型の追加を行う. 型の追加を行うと言っても LLVM IR の持つ type の拡張を行うわけではなく, コンパイル時に内部で code segment であることを知るためだけに型の定義を行い, LLVM IR として出力した場合には 型は void となる. LLVM では型の情報は Type というクラスで管理しており, Type の定義は \$(LLVM)/lib/IR/LLVMContextImpl.h で行う. これに加えて TypeID の登録も行う必要があり, これは \$(LLVM)/include/llvm/IR/Type.h で定義されている. それぞれ, 以下のように編集した. \\
　さらに, \_\_CodeTy は VoidTy としても扱いたいため, 型判別に用いられる isVoidTy 関数の編集も行った. この関数は Type が VoidTy の場合に真を返す関数である. この関数を Type が \_\_CodeTy の場合にも真を返すようにした. ここで変更されたは if 文の条件文のみなので, ソースコードの記載はしない.\\
\begin{lstlisting}[frame=lrbt,label=LLVMType,caption={LLVMContextImpl.h}]
       :
  // Basic type instances.
  Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy;
  Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
#ifndef noCbC
  Type __CodeTy;
#endif  
       :
\end{lstlisting}
\begin{lstlisting}[frame=lrbt,label=LLVMType,caption={Type.h}]
  enum TypeID {
       :
    StructTyID,      ///< 12: Structures
    ArrayTyID,       ///< 13: Arrays
    PointerTyID,     ///< 14: Pointers
    VectorTyID       ///< 15: SIMD 'packed' format, or other vector type
#ifndef noCbC
    ,__CodeTyID      /// for CbC
#endif
       :
\end{lstlisting}
　これらの編集により, LLVM 側でも code segment を認識できるようになった.

\section{継続のための goto syntax の構文解析}
続いて, 継続のための新しい goto syntax の構文解析を行えるようにする. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下のように変更した. \\
\begin{lstlisting}[frame=lrbt,label=ParseStmt,caption={goto 文の構文解析}]
       :
case tok::kw_goto:                // C99 6.8.6.1: goto-statement
#ifndef noCbC
  if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) && // C: 'goto' identifier ';'
    NextToken().isNot(tok::star)) {                                        // C: 'goto' '*' expression ';'
      SemiError = "goto code segment";
      return ParseCbCGotoStatement(Attrs, Stmts);                              // CbC: goto codesegment statement
    }
#endif
  Res = ParseGotoStatement();
  SemiError = "goto";
  break;
       :
\end{lstlisting}
　ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す.\\
\begin{lstlisting}[frame=lrbt,label=ParseCbCGotoStmt,caption={ParseCbCGotoStatement}]
StmtResult Parser::ParseCbCGotoStatement(ParsedAttributesWithRange &Attrs,StmtVector &Stmts) {
  assert(Tok.is(tok::kw_goto) && "Not a goto stmt!");
  ParseScope CompoundScope(this, Scope::DeclScope);
  StmtVector CompoundedStmts;

  SourceLocation gotoLoc = ConsumeToken();  // eat the 'goto'.
  StmtResult gotoRes;
  Token TokAfterGoto = Tok;
  Stmtsp = &Stmts;
  
  gotoRes = ParseStatementOrDeclaration(Stmts, false);
  if (gotoRes.get() == NULL)
    return StmtError();
  else if (gotoRes.get()->getStmtClass() != Stmt::CallExprClass) { // if it is not function call
    Diag(TokAfterGoto, diag::err_expected_ident_or_cs);
    return StmtError();
  }
  
  assert((Attrs.empty() || gotoRes.isInvalid() || gotoRes.isUsable()) &&
	 "attributes on empty statement");
  if (!(Attrs.empty() || gotoRes.isInvalid()))
    gotoRes = Actions.ProcessStmtAttributes(gotoRes.get(), Attrs.getList(), Attrs.Range);
  if (gotoRes.isUsable())
    CompoundedStmts.push_back(gotoRes.release());

  // add return; after goto codesegment();
  if (Actions.getCurFunctionDecl()->getResultType().getTypePtr()->is__CodeType()) {
    ExprResult retExpr;
    StmtResult retRes;
    retRes = Actions.ActOnReturnStmt(gotoLoc, retExpr.take());
    if (retRes.isUsable())
      CompoundedStmts.push_back(retRes.release());
  }
  return Actions.ActOnCompoundStmt(gotoLoc, Tok.getLocation(), CompoundedStmts, false);
}
\end{lstlisting}
　この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する. 
\section{Tail call elimination pass の条件の達成}
\label{sec:TCEreq}
CbC の構文が解析できるようになったところで, 次に tail call elimination を強制する処理, つまり tail call elimination の条件を満たす処理の追加を行う. \ref{sec:TCE}節で述べた条件のうち, code segment を tail call にする (呼び出した直後に return 文がくる) という条件は前節で達成した. したがって残りの条件は, 呼び出し規約を fastcc, cc 10, cc 11 のいずれかにする, tailcallopt の有効化, tail call elimination pass の追加の三つである. \\
　まず初めに, tail call elimination pass の追加を行う. clang は最適化の pass の追加を \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数内で行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるが, その pass の追加はこの関数から呼び出される populateModulePassManager 関数で行われる. この関数は LLVM が用意した最適化に用いられる主要な pass を追加するものである. この関数を以下のリスト\ref{PassManager}のように変更した. 変数 MPM は PassManagerBase という pass の管理を行うクラスのインスタンスで, MPM の持つ add 関数を用いて pass の登録を行う. add 関数の引数に createTailCallEliminationPass 関数を指定することで tail call elimination pass が追加され, リスト\ref{PassManager}の 5, 11, 13 行目がその処理を行っている. この中で書き加えられたのは 5 行目と 11 行目のものである. 二箇所に記述しているのはこの関数が最適化レベルが 0 かどうかによって追加する pass を変えるためである. CbC コンパイラを実装するためにはどちらの場合でも tail call elimination pass が必要となるので二箇所に記述している. 5 行目 最適化レベルが 0 の場合, 11行目がそれ以外の場合ののための記述である. このとき, createTailCallEliminationPass 関数の引数は, tail call elimination を code segment のみに適用するかどうかを表す. 最適化レベルが 0 の場合に code segment 以外の関数に触れないようにするためにこのような引数を設けた.\\
\begin{lstlisting}[frame=lrbt,label=PassManager,caption={tail call elimnation pass の追加}]
       :
  if (OptLevel == 0) {
       :
#ifndef noCbC
    MPM.add(createTailCallEliminationPass(true));   // Eliminate tail calls
#endif
       :
  }
       :
#ifndef noCbC
  MPM.add(createTailCallEliminationPass(false));   // Eliminate tail calls
#else
  MPM.add(createTailCallEliminationPass());   // Eliminate tail calls
#endif
       :
\end{lstlisting}
　これで code segment の呼び出しに対して tail フラグが付与されるようになった. しかし実際にはこれだけでは不十分でさらに二つの pass を追加する必要がある. 追加する pass は SROA pass と codeGenPrepare pass である. 一つ目の SROA pass は メモリ参照を減らすスカラー置換を行う pass でこれにより LLVM IR の alloca 命令を可能な限り除去できる. tail call elimination の条件に直接記されてはいないが, tail call elimination pass を用いて tail フラグを付与する場合には 呼び出し元の関数に alloca がないことが求められるのである. 二つ目の codeGenPrepare pass は名前の通りコード生成の準備を行う pass で, これを通さないと if 文を用いた時に call の直後に配置した return 文が消えてしまう. これらの pass 追加されるように変更する必要がある. SROA pass は tail call elimination と同じようにして追加される pass なので同様にして追加することができる. codeGenPrepare pass はこれら二つとは異なり, addPassesToEmitFile という関数を とおして LLVM によって追加される. この時の追加されるかどうか条件が最適化レベルに依存するものであったため, code segment を持つ場合には最適化レベルに関わらず追加するように変更した.
　次に, 呼び出し規約の問題を解消する. 条件を満たす呼び出し規約は fastcc, cc 10, cc 11 の三種類があり, それぞれ簡単に説明すると以下の様な特徴がある.
\begin{description}
  \item[fastcc]\mbox{}\\
    この規約を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. この呼び出し規約は可変引数をサポートせず, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要がある.
  \item[cc 10]\mbox{}\\
    Glasgow Haskell Compiler のために実装された呼び出し規約. X86 でのみサポートされており, 引数に関するいくつかの制限をもつ. レジスタ内の値を全て渡し, 呼び出された関数はレジスタの値を保存できない. この呼び出し規約は関数型プログラミング言語を実装する際に使用される register pinning という技術の代わりとして特定の状況でしか使用してはならない.
  \item[cc 11]\mbox{}\\
    High-Performance Erlang のために実装された呼び出し規約. 通常の C の呼び出し規約以上に引数を渡すためにレジスタを利用する. X86 でのみサポートされており, cc 10 同様に register pinning を用いる. 
\end{description}
　これらのうち, cc 10, cc 11 は関数型プログラミング言語の実装に用いられる register pinning という技術の代わりに用いられ, これを積極的に利用することは好ましくないとある. 対して fastcc には, 可変引数をサポートしない, プロトタイプは正確でなければならないといった条件があるが, 前者は \ref{sec:TCE}節で説明したとおり tail call elimination の条件に含まれており, 後者は特別厳しい条件ではない上, プロトタイプの不正な関数は clang がエラーを出してくれるので問題ないだろう. よって code segment の呼び出し規約には fastcc を用いることにした. \\
　fastcc の追加は clang が関数情報の設定処理を行っている箇所で行った. 関数情報は CGFunctionInfo というクラスを用いて管理される. 関数情報の設定は \$(CLANG)/lib/CodeGen /CGCall.cpp 内の arrangeLLVMFunctionInfo という関数で行われる. この関数内に以下のリスト\ref{CC} に示されるコードを加えた. 5行目が fastcc を設定している箇所である. 関数が \_\_code型の場合で, かつ可変長引数を持たない場合に呼び出し規約を fastcc に設定する. 可変長引数に関する条件を加えているのは, 可変長引数が使用されている場合には呼び出し規約を変えず tail call elimination を行わないことで通常の関数呼び出しを生成するためである.\\
\begin{lstlisting}[frame=lrbt,label=CC,caption={fastcc の追加}]
       :
#ifndef noCbC
  if(resultType.getTypePtr()->is__CodeType()){
    if(!required.allowsOptionalArgs())
      CC = llvm::CallingConv::Fast;
  }
#endif
       :
\end{lstlisting}
　最後に, tailcallopt を有効化を行う. clang と LLVM は指定されたオプションを管理するクラスを別々に持っており, clang はユーザーに指定されたオプションを LLVM に引き継ぐ処理を持つ. その処理が行われているのが \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数である. この関数のオプションの引き継ぎを行っている箇所を以下のリスト\ref{option}のように変更する. 6 行目が tailcallopt を有効にしている箇所である. tailcallopt は内部では GuaranteedTailCallOpt となっており, code segment を持つ場合にこれを有効化する. 右辺の HasCodeSegment が code segment を持つか否かを表し, これは \ref{sec:add__code} 節で記したように, 予約語 \_\_code を解析する際に有効化される. また, 5 行目からわかるように LLVM 側でも HasCodeSegment というオプションを追加している. これは \ref{sec:TCEreq} 節で述べた codeGenPrepare pass を追加する際に利用する. \\
\begin{lstlisting}[frame=lrbt,label=option,caption={オプションの引き継ぎ}]
       :
  Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
  Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
#ifndef noCbC
  Options.HasCodeSegment = LangOpts.HasCodeSegment;
  Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
#endif
       :
\end{lstlisting}
　LLVM でのオプションの追加方法についてもここで述べておく. LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. TargetOptions クラスの中で変数を宣言するだけで追加できるので, コードは省略する.
\section{環境付き継続の実装}
環境付き継続を行うためには \ref{sec:withEnv} 節で述べたように, \_\_return, \_\_environment という特殊変数を用いる. これら二つの変数の実装方法には様々な方法が考えられる. GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文である内部関数を用いていた. しかし, clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. 

\subsection{clang により追加されるコード}
環境付き継続は, \_\_return, \_\_environment が使用された時に自動的にあるコードを生成することで実現される. 具体的には, リスト \ref{autoCodeGenB} のようなコードを, コンパイルした場合にはリスト \ref{autoCodeGenA} のように解釈することで実現される.
\begin{lstlisting}[frame=lrbt,label=autoCodeGenB,caption={環境付き継続の例}]
__code cs(int retval,__code(*ret)(int,void *),void *env){
  goto ret(n, env);
}

int func (){
  goto cs(30, __return, __environment);
  return 0;
}
\end{lstlisting}
\begin{lstlisting}[frame=lrbt,label=autoCodeGenA,caption={内部での解釈}]
#include <setjmp.h>

struct CbC_env {
  void *ret_p,*env;
};

__code cs(int retval,__code(*ret)(int,void *),void *env){
  goto ret(n, env);
}

__code return1 (int retval, void* env){
  *(int*)((struct CbC_env *)(env))->ret_p = retcal;
  longjmp((int*)(((struct CbC_env *)env)->env),1);
}

int func (){
  __code (*__return)();
  struct CbC_env __environment;
  jmp_buf env;
  int retval;
  __environment.ret_p = &retval;
  __environment.env = &env;
  __return = return1;
    if (setjmp(__environment.env)){
      return retval;
    }
  goto code1(30, __return, &__environment);
  return 0;
}
\end{lstlisting}
　追加された処理は, setjmp ヘッダのインクルード, 環境と戻り値を保持する構造体 CbC\_env の定義, 元の環境に戻るための特殊 code segment return1 の定義, そして関数 func 内の 17 行目から 26 行目までの処理であり, 27 行目の継続の第三引数も参照渡しに変更される. 追加された処理の大まかな流れを説明する. 環境付き継続を用いる関数は継続前に setjmp を用いて戻り先の環境を保存し, 継続を行う. このとき, 引数として渡される \_\_return には特殊 code segment return1 のアドレス, \_\_environment の持つメンバには戻り値として返される値を持つ変数のアドレスと, setjmp により保存された継続前の環境が保持されている. 元の環境に戻るための code segment は自動生成されるので, 継続先の code segment は返す戻り値と \_\_environemnt を引数として \_\_return の指す code segment を呼び出すだけで元の環境に戻れる. return1 は 構造体の持つ戻り値へのポインタを利用して戻り値を更新した後, longjmp を用いて元の環境に戻る. longjmp によって再度 setjmp の呼び出しに戻るが今回は if文内に入り, 戻り値を返す.
%% \begin{lstlisting}[frame=lrbt,label=autoCodeGenA,caption={内部で自動追加されるコード}]
%% #include <setjmp.h>

%% struct CbC_env {
%%   void *ret_p,*env;
%% };

%% __code cs(int retval,__code(*ret)(int,void *),void *env){
%%   goto ret(n, env);
%% }

%% __code return1 (int retval, void* env){
%%   *(int*)((struct CbC_env *)(env))->ret_p = retval;
%%   longjmp((int*)(((struct CbC_env *)env)->env),1);
%% }

%% int func (){
%%   goto code1(30,
%%       ({
%%         __code (*__CbC_return)();
%% 	__CbC_return = return1;
%% 	__CbC_return;
%%       }),
%%       ({
%%         struct CbC_env __CbC_environment;
%%         jmp_buf env;
%%         int retval;
%%         __CbC_environment.ret_p = &retval;
%%         __CbC_environment.env = &env;
%%         if (setjmp(__CbC_environment.env)){
%% 	  return retval;
%%         }
%%         &__CbC_environment;
%%       })
%%     );
%%   return 0;
%% }
%% \end{lstlisting}
%% 　自動生成された処理は, setjmp ヘッダのインクルード, 構造体 CbC\_env の定義, 元の環境に戻るための特殊 code segment return1 の定義であり, これに加えて \_\_return, \_\_environment が環境付き継続の前準備を行う処理に変更される. \_\_return は内部では元の環境に戻るための code segment へのポインタの宣言文と, アドレスの代入を行う文に変換され, \_\_environment は内部では環境を保持する構造体, setjmp, longjmp が用いる jmp\_buf, 関数の戻り値となる retval の宣言文, 構造体のメンバの値の設定を行う代入文, そして特殊 code segment return1 の戻り先となる setjmp を用いた構文に変換される. また, \_\_return, \_\_environment 変数を置換した処理は Statement Exprs を利用しており, これにより, 変数への代入も可能となっている. \\

\section{実装方法}
　前節より, それぞれの予約語を解析する際に自動生成しなければならない文は次のようになることがわかる. 
\begin{itemize}
  \item \_\_return
    \begin{itemize}
    \item 元の環境に戻るための特殊な code segment
    \item 各変数の宣言及び代入文
    \end{itemize}
  \item \_\_environment
    \begin{itemize}
    \item 環境を保持する構造体 CbC\_env の定義
    \item 各変数の宣言及び代入文
    \item setjmp を条件文にとり, 真の場合に関数の戻り値を返す if文
    \end{itemize}
  \item どちらにも依存しない
    \begin{itemize}
    \item setjmp.h のインクルード文
    \end{itemize}
\end{itemize}
　setjmp.h のインクルード文がどちらにも属さないのは, 無条件でこのヘッダをインクルードするようにしてもよいからである. 必要のないコードは最適化によって除去されるので, 使用されない場合でもインクルードして構わない. また, これらの文を生成する際, 元の関数の型の戻り値を返せるようにしなければならないが, \ref{QualType} 節で説明したように, clang では型情報を QualType が管理しているので, 生成する関数や変数に対して元の関数の返り値に対応する QualType を与えるだけでこの問題は解決する. 尚, 二つの予約語を登録する処理は既に \ref{sec:add__code} 節で説明したので省く.\\
　まずはじめに setjmp.h のインクルード文の生成について説明する. clang では include マクロによって他のファイルのインクルードを行う場合, 字句解析対象となるのファイルの変更を行う. 本研究では, これらの処理に必要なものを IncludeHeader という一つの関数にまとめ, それを呼び出すことで任意のファイルをインクルードできるようにした. その関数のうち, 重要な部分を抜き出したものを以下のリスト \ref{IncludeHeader} に示す. この関数は引数に現在の token とインクルードするファイルの名前を求める. まずこの関数は, 現在の token の保存処理を行う. これは, この関数が呼ばれた時点で取得された token はすでに字句解析対象のバッファから取り除かれており, これを保存しておかないとインクルード処理終了後の構文解析に影響が出るために行っている. 次に, 指定されたファイルの検索を行う. その処理を行っているのは 11行目であり, このときファイルが見つからなかった場合には NULL が返るので, これを利用してエラーの生成も行っている. 解析対象の変更を行っているのが 16行目以降の処理で, 実際にファイルを移っているのは 18行目の EnterSourceFile 関数である. この関数によって字句解析対象が現在のファイルから指定したファイルへと変更される. また, この関数の戻り値はファイルのインクルード処理を行ったかどうかを判断するために用いる. \\
\begin{lstlisting}[frame=lrbt,label=IncludeHeader,caption={IncludeHeader 関数}]
bool Preprocessor::IncludeHeader(Token Tok, const char* Name) {
  if (SavedTokenFlag) // If the lexer has already entered a header file, we have to leave this function.
    return false;
  SourceLocation Loc = Tok.getLocation();
  SavedToken = Tok;
  SavedDepth = IncludeMacroStack.size();
  SavedTokenFlag = true;

       :

  const FileEntry *File = LookupFile(Loc, Filename, isAngled, LookupFrom, CurDir, NULL, NULL,
				     HeaderInfo.getHeaderSearchOpts().ModuleMaps ? &SuggestedModule : 0);

       :

  FileID FID = SourceMgr.createFileID(File, Loc, FileCharacter);      
  EnterSourceFile(FID, CurDir, FilenameTok.getLocation(), static_cast<bool>(BuildingModule));
  return true;
}
\end{lstlisting}
　次に, 元の環境に戻るための特殊な code segment の定義生成処理の説明をする. これを行うためには clang の持つ AST に関数の定義を加えてやれば良い. 今回の実装でその処理を担うのが以下のリスト \ref{return1} に示される CreateRetCS 関数である. ただしここでは重要でない箇所を省いている. この関数は引数として生成する関数の名前を受け取る. 2, 3 行目が元の関数の QualType を取得する処理である. 5 行目から 14 行目までの処理は関数宣言のためにスコープをグローバルスコープに変更するための処理で, すべての処理を終えた後, 59 行目から 62 行目の処理によって元のスコープに戻す. 16 行目から 42 行目までが関数のプロトタイプ宣言に関する設定処理を行っており, 29 行目で 取得しておいた QualType を利用していることがわかる. 44 行目からが関数の持つ処理の定義を指定する部分にあたり, 52 行目にある StmtVector クラスのインスタンスに対して任意の文に対応する StmtResult を追加し, 54 行目の関数を呼び出すと戻り値としてこの関数の中身を表す StmtResult を得ることができる. その後これを定義や宣言を管理するクラスである Decl へと変換し, 58 行目の関数を呼び出すことで生成した関数の定義が AST に追加される. 
\begin{lstlisting}[frame=lrbt,label=return1,caption={CreateRetCS 関数}]
bool Parser::CreateRetCS(IdentifierInfo *csName){
  FunctionDecl *CurFunctionDecl = Actions.getCurFunctionDecl();
  QualType CurFuncResQT = CurFunctionDecl->getResultType();

  Scope *SavedScope = getCurScope();
  DeclContext *SavedContext = Actions.CurContext;
  TypeSourceInfo *CurFuncTI = Actions.Context.CreateTypeSourceInfo(CurFuncResQT);
  sema::FunctionScopeInfo *SavedFSI = Actions.FunctionScopes.pop_back_val();

  Actions.CurContext = static_cast<DeclContext *>(Actions.Context.getTranslationUnitDecl());
  Scope *TopScope = getCurScope();
  while(TopScope->getParent() != NULL)
    TopScope = TopScope->getParent();
  Actions.CurScope = TopScope;

  DeclGroupPtrTy returnDecl = DeclGroupPtrTy();
  ParsingDeclSpec PDS(*this);
  setTST(&PDS, DeclSpec::TST___code);
  ParsingDeclarator D(*this, PDS, static_cast<Declarator::TheContext>(Declarator::FileContext));
  D.SetIdentifier(csName, Loc);
  ParseScope PrototypeScope(this,Scope::FunctionPrototypeScope|Scope::DeclScope|Scope::FunctionDeclarationScope);
  SmallVector<DeclaratorChunk::ParamInfo, 16> ParamInfo;
  DeclSpec FDS(AttrFactory);
  ParmVarDecl *Param;
		
  IdentifierInfo *retvalII = CreateIdentifierInfo(__CBC_RETVAL_NAME, Loc);
  Param = CreateParam(retvalII);
  Param->setTypeSourceInfo(CurFuncTI);
  Param->setType(CurFuncResQT);

  ParamInfo.push_back(DeclaratorChunk::ParamInfo(retvalII, Loc, Param, 0));
  IdentifierInfo *envII = CreateIdentifierInfo(__CBC_STRUCT_ENV_NAME, Loc);
  Param = CreateParam(envII, 1, DeclSpec::TST_void);
  ParamInfo.push_back(DeclaratorChunk::ParamInfo(envII, Loc, Param, 0));

  D.AddTypeInfo(DeclaratorChunk::getFunction(HasProto, IsAmbiguous, Loc, ParamInfo.data(), ParamInfo.size(), EllipsisLoc, Loc,
					     FDS.getTypeQualifiers(), RefQualifierIsLValueRef, RefQualifierLoc, ConstQualifierLoc,
					     VolatileQualifierLoc, SourceLocation(), ESpecType, ESpecRange.getBegin(),
					     DynamicExceptions.data(), DynamicExceptionRanges.data(), DynamicExceptions.size(),
					     NoexceptExpr.isUsable() ? NoexceptExpr.get() : 0,
					     Loc, Loc, D, TrailingReturnType), FnAttrs, Loc);
  PrototypeScope.Exit();
	
  Decl *TheDecl;
  ParseScope BodyScope(this, Scope::FnScope|Scope::DeclScope);
  Decl *BodyRes = Actions.ActOnStartOfFunctionDef(getCurScope(), D);

  D.complete(BodyRes);
  D.getMutableDeclSpec().abort();
  Actions.ActOnDefaultCtorInitializers(BodyRes);
  StmtResult FnBody;
  StmtVector FnStmts;
  /* add function body statements */
  FnBody = Actions.ActOnCompoundStmt(Loc, Loc, FnStmts, false);
  BodyScope.Exit();
  TheDecl = Actions.ActOnFinishFunctionBody(BodyRes, FnBody.take());
  returnDecl =  Actions.ConvertDeclToDeclGroup(TheDecl);
  (&Actions.getASTConsumer())->HandleTopLevelDecl(returnDecl.get());
  Actions.CurScope = SavedScope;
  Actions.CurContext = SavedContext;
  Actions.FunctionScopes.push_back(SavedFSI);
  return false;
}
\end{lstlisting}
　つづいて構造体 CbC\_env の定義を行う. この構造体は setjmp, longjmp が環境の保持に使う jmp\_buf へのポインタと元の関数の戻り値となる変数へのポインタを持つ. 構造体の宣言は通常, 構文解析器によって Decl というクラスのインスタンスが生成され, それを利用して行う. 今回の実装では Decl の生成を手書きのコードで行うことで, 自動で構造体の定義を行う処理を実現した. 今回の実装ではそのコード群を Create\_\_CbC\_envStruct という一つの関数にまとめた. その関数のうち,重要な部分を抜き出したものを以下のリスト \ref{CbC_env} に示す. この関数はソースコードの位置と C++ で用いられるアクセス修飾子を引数に取る. この関数もスコープを変更する処理を持つが, それについては先ほど説明したので省いている. 12 行目から 22 行目までが, この構造体の Decl を生成する処理である. メンバの設定を行っているのが 27 行目から 30 行目で, ここで使用している Create\_\_CbC\_envBody 関数はメンバの宣言を行うために独自に作成した関数である. 構造体のメンバとして宣言するために ActOnField という Sema クラスの関数を呼び出す以外は後述する CreateDeclStmt 関数と処理内容にあまり差が無いため, この関数については本論文では説明を省く. 32 行目で呼び出している ActOnTagFinishDefinision が, 生成した Decl を元に構造体の宣言の意味解析を行ってくれる関数である. これにより, 生成した構造体に対応する Type も生成される. 
\begin{lstlisting}[frame=lrbt,label=CbC_env,caption={Create\_\_CbC\_envStruct 関数}]
void Parser::Create__CbC_envStruct(SourceLocation Loc, AccessSpecifier AS) {

          :

  ParsingDeclSpec SDS(*this);
  DeclSpec::TST TagType = DeclSpec::TST_struct;
  DeclResult TagOrTempResult = true;
  bool Owned = false;
  bool IsDependent = false;
  TagOrTempResult = Actions.ActOnTag(getCurScope(), TagType, Sema::TUK_Definition, Loc,
				     SDS.getTypeSpecScope(), Name, Loc, attrs.getList(), AS,
				     SDS.getModulePrivateSpecLoc(), TParams, Owned, IsDependent,
				     SourceLocation(), false, clang::TypeResult());

  Decl *TagDecl = TagOrTempResult.get();
  ParseScope StructScope(this, Scope::ClassScope|Scope::DeclScope);
  Actions.ActOnTagStartDefinition(getCurScope(), TagDecl);
  SmallVector<Decl *, 32> FieldDecls;

  FieldDecls.push_back(Create__CbC_envBody(TagDecl, DeclSpec::TST_void, Loc, __CBC_STRUCT_POINTER_NAME));
  FieldDecls.push_back(Create__CbC_envBody(TagDecl, DeclSpec::TST_int, Loc, __CBC_STRUCT_ENV_NAME));

  Actions.ActOnFields(getCurScope(),Loc, TagDecl, FieldDecls,Loc, Loc,attrs.getList());
  StructScope.Exit();
  Actions.ActOnTagFinishDefinition(getCurScope(), TagDecl, Loc);

          :
}
\end{lstlisting}
　つづいて両予約語解析時に共通する処理の一つである変数の定義文に関して説明する. これも定義に関する文であるので Decl の生成がメインとなる. 今回の実装では以下のリスト\ref{DeclStmt} に示す CreateDeclStmt という関数を作り, その関数によってその処理を行う. ここでも重要でない処理は省いている. この関数は引数として変数名, code segment へのポインタかどうか, 呼び出し元の関数の型をコピーするかどうか, 変数の型, 構造体だった場合の構造体名を持つ. 4 行目の setTST 関数が指定された型修飾子を設定している箇所である. 変数名は 6 行目の SetIdentifier 関数によって設定され, その後は関数へのポインタだった場合や構造体だった場合のときにのみ行われる処理が来るがここでは省いた. その後型コピーを行うかどうかで処理が異なる. 型コピーの方法については既に述べたのでここでは省く. すべての処理を終えると, Decl の意味解析が行われ, その結果が StmtResult として返る. 
\begin{lstlisting}[frame=lrbt,label=DeclStmt,caption={CreateDeclStmt 関数}]
StmtResult Parser::CreateDeclStmt(IdentifierInfo *II, bool isRetCS, bool copyType, DeclSpec::TST valueType, IdentifierInfo* Name){
  DeclGroupPtrTy DeclGPT;
  ParsingDeclSpec DS(*this);
  setTST(&DS, valueType, Name);
  ParsingDeclarator D(*this, DS, static_cast<Declarator::TheContext>(Declarator::BlockContext));
  D.SetIdentifier(II, Loc);

        :

  SmallVector<Decl *, 8> DeclsInGroup;
  Decl *FirstDecl;
  
  if (copyType)
    FirstDecl = HandleDeclAndChangeDeclType(D);
  else
    FirstDecl = ParseDeclarationAfterDeclaratorAndAttributes(D);
  
  D.complete(FirstDecl);
  DeclsInGroup.push_back(FirstDecl);
  DeclGPT =  Actions.FinalizeDeclaratorGroup(getCurScope(), *DSp, DeclsInGroup);
  return Actions.ActOnDeclStmt(DeclGPT, Loc, Loc);
}
\end{lstlisting}
　つづいて両予約語解析時に共通するもう一つの処理, 代入文の生成について説明する. 今回の実装ではこの処理を以下のリスト \ref{assignment} に示す CreateAssginmentStmt 関数にまとめた. ここでも重要でない処理は省いている. この関数は引数として左辺,右辺の変数名と, 左辺が構造体のメンバかどうか, 右辺が演算子 \& を持つかどうか, 左辺が構造体だった場合の構造体名を求める. 8 行目から 14 行目までは左辺に対応する ExprResult を取得する処理で, ExprResult は一つの式に対応するクラスである. 同様に, 18 行目が右辺に対応する ExprResult を取得する処理で, 代入式の生成は 20　行目に当たる. ここで生成した ExprResult を ActOnExprStmt に渡すことで, 式として StmtResult に変換される.
\begin{lstlisting}[frame=lrbt,label=assignment,caption={CreateAssignmentStmt 関数}]
StmtResult Parser::CreateAssignmentStmt(IdentifierInfo* LHSII, IdentifierInfo* RHSII, bool LHSisMemberAccess, bool RHShasAmp,
					IdentifierInfo* extraLHSII){
  ExprResult Expr,LHS,RHS;
  Token Next,LHSToken;

        :

  ExternalSpace::StatementFilterCCC Validator(Next);
  Sema::NameClassification Classification = Actions.ClassifyName(getCurScope(), SS, LHSII, Loc, Next, false, SS.isEmpty() ? &Validator : 0);
  setExprAnnotation(LHSToken, Classification.getExpression());
  LHSToken.setAnnotationEndLoc(Loc);
  PP.AnnotateCachedTokens(LHSToken);
  
  LHS = getExprAnnotation(LHSToken);

        :
  
  RHS = LookupNameAndBuildExpr(RHSII);

  Expr = Actions.ActOnBinOp(getCurScope(), Loc,tok::equal,LHS.take(),RHS.take());
  
  return Actions.ActOnExprStmt(Expr);
}
\end{lstlisting}
　さて, 残る if 文の自動生成についてであるが, これは if 文のためのスコープを生成した後条件文を作り, その後 if 文内のスコープを作りそこに文を生成していくことで行える. この処理は前述した code segment の生成に含まれる処理に酷似する. したがってここではその説明を省略する. \\