changeset 3:d9b703be7359

fix
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 01 Mar 2016 18:10:30 +0900
parents 7cc0be313596
children 5ebc6e5c5c8f
files paper.tex
diffstat 1 files changed, 129 insertions(+), 180 deletions(-) [+]
line wrap: on
line diff
--- a/paper.tex	Tue Mar 01 17:16:15 2016 +0900
+++ b/paper.tex	Tue Mar 01 18:10:30 2016 +0900
@@ -361,19 +361,23 @@
 この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 
 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.
 
-\begin{lstlisting}[float=*,frame=lrbt,label=parse__Code,caption={\_\_code の parse}]
+\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,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);
+    isInvalid = DS.SetTypeSpecType(
+      DeclSpec::TST___code, Loc, PrevSpec, DiagID);
     break;
   }
 \end{lstlisting}
 
 重要なのは 5行目である. SetTypeSpecType 関数はその名の通り TypeSpecType を設定する関数であり, ここで \_\_code 型が DeclSpec に登録される. DeclSpec は 型の識別子を持つためのクラスであり, 後に QualType に変換される. 
 
-\section{LLVM の基本構造}
+ここでは型を追加しただけなので、ASTからIRへの変換をいじる必要はない. 実際のCbC言語では軽量継続部分のコード生成を行う必要がある.
+それにはLLVM IR生成以降の部分を追う必要がある.
+
+\section{LLVM IRから機械語への変換の流れ}
 \label{sec:llvm}
 LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない. 中間表現を何度か変え, その度に最適化を行い, そして最終的にターゲットのアセンブリ言語に変換するのである. 
 また LLVM では, 最適化や中間表現の変換といったコンパイラを構成する処理は全て pass が行う. 多くの pass は最適化のために存在し, この pass を組み合わせることにより, LLVM の持つ機能の中から任意のものを利用することができる.
@@ -386,7 +390,7 @@
   \item[SSA-based Machine Code Optimizations]\mbox{}\\
     SSA-based Machine Code に対する最適化を行う. 各最適化はそれぞれ独立した pass になっている.
   \item[Register Allocation]\mbox{}\\
-    仮装レジスタから物理レジスタへの割り当てを行う. ここで PHI 命令が削除され, SSA-based でなくなる.
+    仮想レジスタから物理レジスタへの割り当てを行う. ここで PHI 命令が削除され, SSA-based でなくなる.
   \item[Prolog/Epilog Code Insertion]\mbox{}\\
     Prolog/Epilog Code の挿入を行う. どちらも関数呼び出しに関わるものであり, Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理, Epilog は呼び出し元の関数に戻る際に行う処理である.
   \item[Late Machine Code Optimizations]\mbox{}\\
@@ -450,7 +454,9 @@
 }
 \end{lstlisting}
 
-SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は初め illegal SelectionDAG に変換され, legalization を含む多くの段階を踏んで次の中間表現である Machine Code になる. 以下に SelectionDAG が Machine Code に変換されるまでに行われる処理の過程を示す. 
+SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は初め illegal SelectionDAG に変換され, legalization を含む多くの段階を踏んで次の中間表現である Machine Code になる. 
+
+以下に SelectionDAG が Machine Code に変換されるまでに行われる処理の過程を示す. 
 
 \begin{description}
   \item[Build initial DAG]\mbox{}\\
@@ -476,177 +482,126 @@
 
 \begin{figure}[htpb]
  \begin{center}
-  \scalebox{0.50}{\includegraphics{fig/dag.pdf}}
+  \scalebox{0.40}{\includegraphics{fig/dag.pdf}}
  \end{center}
  \caption{add 関数に対応する legalize 直前の SelectionDAG}
  \label{fig:dag}
 \end{figure}
 
 
-Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ Single Static Assignment (SSA) 形式と物理レジスタを持つ non-SSA 形式がある. SSA 形式とは全ての変数が一度のみ代入されるように記述した形式であり. この形式を取ることで LLVM は効率よく最適化を行うことが出来る.
+Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮想レジスタを持つ Single Static Assignment (SSA) 形式と物理レジスタを持つ non-SSA 形式がある. SSA 形式とは全ての変数が一度のみ代入されるように記述した形式であり. この形式を取ることで LLVM は効率よく最適化を行うことが出来る.
 
 Machine Code は LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている.
 
-Machine Code の一例を以下のリスト \ref{MachineCodeSSA}, \ref{MachineCodeNonSSA}に示す. リスト \ref{MachineCodeSSA} が SSA 形式, リスト \ref{MachineCodeNonSSA} が non-SSA 形式であり, 元となるコードはリスト \ref{IRtestC} である. \%varg1, \%varg2 といったものが仮想レジスタであり, リスト \ref{MachineCodeSSA} に多く存在することが確認できる. しかし, リスト \ref{MachineCodeNonSSA} には1行目を除いてそれが存在しない. 1行目はこの関数の引数に対応する物理レジスタと仮想レジスタを並べて表記しているだけなので, ここに仮想レジスタが残っていることについて問題はなく, non-SSA 形式の Machine Code では仮想レジスタが取り除かれていることがわかる.
-\begin{lstlisting}[frame=lrbt, label=MachineCodeSSA, caption={Machine Code (SSA)}]
-Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
-
-BB#0: derived from LLVM BB %entry
-    Live Ins: %EDI %ESI
-%vreg5<def> = COPY %ESI
-%vreg4<def> = COPY %EDI
-%vreg6<def> = MOV32r0 %EFLAGS<imp-def,dead>
-    Successors according to CFG: BB#1
+IRを安易に変更すると、LLVM内部の最適化と干渉してしまう。IRで許される変更は、新しい型名の追加ぐらいしか許されない.
+CbC ではIR以降の変更は、その型名と関数呼び出し時に付けられる汎用のフラグを用いている.
 
-BB#1: derived from LLVM BB %while.cond
-    Predecessors according to CFG: BB#0 BB#2
-%vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#2>
-%vreg1<def> = PHI %vreg6, <BB#0>, %vreg2, <BB#2>
-%vreg7<def,tied1> = SUB32rr %vreg0<tied0>, %vreg5, %EFLAGS<imp-def>
-JG_4 <BB#3>, %EFLAGS<imp-use>
-JMP_4 <BB#2>
-    Successors according to CFG: BB#2(124) BB#3(4)
 
-BB#2: derived from LLVM BB %while.body
-    Predecessors according to CFG: BB#1
-%vreg2<def,tied1> = ADD32rr %vreg1<tied0>, %vreg0, %EFLAGS<imp-def,dead>
-%vreg3<def,tied1> = INC64_32r %vreg0<tied0>, %EFLAGS<imp-def,dead>
-JMP_4 <BB#1>
-    Successors according to CFG: BB#1
 
-BB#3: derived from LLVM BB %while.end
-    Predecessors according to CFG: BB#1
-%vreg8<def,tied1> = IMUL32rr %vreg4<tied0>, %vreg5, %EFLAGS<imp-def,dead>
-%vreg9<def,tied1> = SUB32rr %vreg1<tied0>, %vreg8<kill>, %EFLAGS<imp-def,dead>
-%EAX<def> = COPY %vreg9
-RET %EAX
-\end{lstlisting}
-
-\begin{lstlisting}[frame=lrbt, label=MachineCodeNonSSA, caption={Machine Code (non-SSA)}]
-Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
-
-0B    BB#0: derived from LLVM BB %entry
-        Live Ins: %EDI %ESI
-48B        %EAX<def> = MOV32r0 %EFLAGS<imp-def,dead>
-64B        %ECX<def> = COPY %EDI
-        Successors according to CFG: BB#1
+% \section{オプションの追加}
+% 
+% リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.
+% 
+% \begin{lstlisting}[float=*,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}
+% 
+% ただしこのオプションは clang 内で有効なもので, LLVM IR の処理以降も有効にしておきたい場合 LLVM 側でもオプションを新設し, 引き継ぐ必要がある.
+% 
+% clang のオプションの値は \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数(\ref{option})で行われる. 
+% 
+% \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
+%        :
+%   Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
+%   Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
+% #ifndef noCbC
+%   Options.HasCodeSegment = LangOpts.HasCodeSegment;
+%   Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
+% #endif
+%        :
+% \end{lstlisting}
+% 
+% LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)\footnote{LLVMのソースコードをインストールしたディレクトリのパス}/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. 
+% 
+% \begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
+%   class TargetOptions {
+%        :
+%     /// Emit target-specific trap instruction for 'unreachable' IR instructions.
+%     unsigned TrapUnreachable : 1;
+% 
+%     /// EmulatedTLS - This flag enables emulated TLS model, using emutls
+%     /// function in the runtime library..
+%     unsigned EmulatedTLS : 1;
+%     #ifndef noCbC
+%     unsigned HasCodeSegment : 1;
+%     #endif
+%        :
+% \end{lstlisting}
+% 
 
-96B    BB#1: derived from LLVM BB %while.cond
-        Live Ins: %ESI %EDI %ECX %EAX
-        Predecessors according to CFG: BB#0 BB#2
-144B        CMP32rr %ECX, %ESI, %EFLAGS<imp-def>
-160B        JG_4 <BB#3>, %EFLAGS<imp-use,kill>
-176B        JMP_4 <BB#2>
-        Successors according to CFG: BB#2(124) BB#3(4)
+\section{CbCの構文}
+次は新しい構文の追加について. ここでは CbC の軽量継続のための構文を追加する.
+CbC で追加される構文は\_\_codeと、それを呼び出すgoto 文だけである.
 
-192B    BB#2: derived from LLVM BB %while.body
-        Live Ins: %ESI %EDI %ECX %EAX
-        Predecessors according to CFG: BB#1
-224B        %EAX<def,tied1> = ADD32rr %EAX<kill,tied0>, %ECX, %EFLAGS<imp-def,dead>
-256B        %ECX<def,tied1> = INC64_32r %ECX<kill,tied0>, %EFLAGS<imp-def,dead>
-304B        JMP_4 <BB#1>
-        Successors according to CFG: BB#1
+\begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCのコード}]
+__code code3(int a, int b,
+             int loop, int ans){
+  goto code4(b,b/a,loop, ans);
+}
 
-320B    BB#3: derived from LLVM BB %while.end
-        Live Ins: %ESI %EDI %EAX
-        Predecessors according to CFG: BB#1
-352B        %EDI<def,tied1> = IMUL32rr %EDI<kill,tied0>, %ESI<kill>, %EFLAGS<imp-def,dead>
-384B        %EAX<def,tied1> = SUB32rr %EAX<kill,tied0>, %EDI<kill>, %EFLAGS<imp-def,dead>
-416B        RET %EAX
+__code code2(int a, int b,
+             int loop, int ans){
+  goto code3(b,a*b,loop, ans);
+}
 \end{lstlisting}
 
-MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. MC Layer が扱うデータ構造は複数あるが, ここでは MCInst, MCStreamer, MCOperand について説明する.
-
-MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令を出力するには MCInst クラスを用いる.
+コードセグメント\_\_codeはCの関数と同じ形をしているが、return 文は許されず、goto 文で次のコードセグメント
+に移行する。この例では\_\_code2 から \_\_code3 へ処理が移行している.
 
-MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.
-
-MCOperand はオペランドに対応し, MCInst はこのクラスを用いる.
-
-MC Layer で用いられる各クラスも ``-mllvm -asm-show-inst'' オプションを用いることで他の中間表現のように確認することが出来る. MCInst はアセンブリの各命令に対応しているので, アセンブリファイルにコメントとして出力される. リスト \ref{MCInst} は\ref{IRtestC} をコンパイルして得られるアセンブリコードの一部である. 各命令の隣にコメントで記されているのが MCInst, 下に記されているのが MCOperand である. 
+これは以下のCのコードに似ている.
 
-% \begin{lstlisting}[frame=lrbt, label=MCInst, caption={アセンブリコードと MCInst}]
-%   _add:                                   ## @add
-%       .cfi_startproc
-%   ## BB#0:                                ## %entry
-%       pushq   %rbp                    ## <MCInst #2300 PUSH64r
-%   ##  <MCOperand Reg:36>>
-%   Ltmp0:
-%       .cfi_def_cfa_offset 16
-%   Ltmp1:
-%       .cfi_offset %rbp, -16
-%       movq    %rsp, %rbp              ## <MCInst #1684 MOV64rr
-%   ##  <MCOperand Reg:36>
-%   ##  <MCOperand Reg:44>>
-%   Ltmp2:
-%       .cfi_def_cfa_register %rbp
-%       addl    %esi, %edi              ## <MCInst #97 ADD32rr
-%   ##  <MCOperand Reg:23>
-%   ##  <MCOperand Reg:23>
-%   ##  <MCOperand Reg:29>>
-%       movl    %edi, %eax              ## <MCInst #1665 MOV32rr
-%   ##  <MCOperand Reg:19>
-%   ##  <MCOperand Reg:23>>
-%       popq    %rbp                    ## <MCInst #2178 POP64r
-%   ##  <MCOperand Reg:36>>
-%       retq                            ## <MCInst #2460 RETQ>
-% \end{lstlisting}
+\begin{lstlisting}[frame=lrbt,label=calc,caption={Cのコード}]
+int func3(int a, int b){
+  return func4(b,b/a);
+}
 
-\section{オプションの追加}
-リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.
-
-\begin{lstlisting}[float=*,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
-       :
+int func2(int a, int b){
+  return func3(b,a*b);
+}
 \end{lstlisting}
 
-ただしこのオプションは clang 内で有効なもので, LLVM IR の処理以降も有効にしておきたい場合 LLVM 側でもオプションを新設し, 引き継ぐ必要がある.
-
-clang のオプションの値は \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数(\ref{option})で行われる. 
-
-\begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
-       :
-  Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
-  Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
-#ifndef noCbC
-  Options.HasCodeSegment = LangOpts.HasCodeSegment;
-  Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
-#endif
-       :
-\end{lstlisting}
-
-LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)\footnote{LLVMのソースコードをインストールしたディレクトリのパス}/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. 
-
-\begin{lstlisting}[float=*,frame=lrbt,label=option,caption={clang から LLVM へのオプションの引き継ぎ}]
-  class TargetOptions {
-       :
-    /// Emit target-specific trap instruction for 'unreachable' IR instructions.
-    unsigned TrapUnreachable : 1;
-
-    /// EmulatedTLS - This flag enables emulated TLS model, using emutls
-    /// function in the runtime library..
-    unsigned EmulatedTLS : 1;
-    #ifndef noCbC
-    unsigned HasCodeSegment : 1;
-    #endif
-       :
-\end{lstlisting}
+Cの関数はcall命令で呼び出され値を返すのに対して、コードセグメントはjmp命令で移動するだけである.
+それ以外は同じと言って良い. 引数の計算, 局所変数の扱いなどなどである.
+つまり構文的には コードセグメントの定義は関数の定義の構文と同じであり,
+軽量継続つまり, goto 文の後のコードセグメントの呼び出しは関数呼び出しの構文と同じで良い.
 
 
-\section{新しい構文(軽量継続)の追加}
-次は新しい構文の追加について. ここでは CbC の軽量継続のための構文を追加する.
+実際には LLVM 内部で末尾最適化を強制することでこれを実現している.
+末尾最適化とは, 関数の一番最後に呼び出される関数は call せすに jmp するだけで良いということである.
+LLVM IRレベルでは、call命令にTAIL CALLフラグを付ければ良い.
+フラグを付ける以外に
+末尾最適化を実現するためのいくつかの条件があり CbC コンパイラでは, それを満たすように
+コードセグメントのAST生成部分、あるいは最適化部分に手を入れている.
 
-CbC で軽量継続は goto に code segment 名を添えることで行う. この新しい goto syntax を追加する. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下のように変更した.
+さて構文定義に戻ろう.
+CbC で軽量継続は, 構文的には  goto に code segment 名とその引数を添えたものである.
+この新しい goto syntax を追加する. 
+継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. 
+したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. 
+clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, こ
+の関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. 
+この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下のように変更した.
 
 
-\begin{lstlisting}[float=*,frame=lrbt,label=ParseStmt,caption={goto 文の構文解析}]
+\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,label=ParseStmt,caption={goto 文の構文解析}]
        :
 case tok::kw_goto:                // C99 6.8.6.1: goto-statement
 #ifndef noCbC
@@ -662,9 +617,15 @@
        :
 \end{lstlisting}
 
-ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す. このように, 長い処理を追加する場合には別のファイルを作成し, そこに関数として処理を定義するほうが LLVM, clang のアップデートの際に変更が楽になるため良い.
+ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, PP.LookAhead(1)でtoken の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. 
+C では goto の後はラベルまたは*のついた間接ラベルになる. 
+そこで, 識別子とセミコロン、あるいは*がある場合はCのgoto文として扱い, そうでなければ CbC の軽量継続として取り扱う.
+ここで軽量継続が呼び出しているのがコードセグメントであることを確認することが望ましいが, この段階では, まだ, 呼び出し側の
+型が何かを知ることはできない.
+C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. 
+ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す. このように, 長い処理を追加する場合には別のファイルを作成し, そこに関数として処理を定義するほうが LLVM, clang のアップデートの際に変更が楽になるため良い.
 
-\begin{lstlisting}[float=*,frame=lrbt,label=ParseCbCGotoStmt,caption={ParseCbCGotoStatement}]
+\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,,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);
@@ -715,7 +676,7 @@
 
 clang では \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数から populateModulePassManager 関数を呼び出してパスの追加を行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるがこれをレベルにかかわらず追加するように変更した (リスト\ref{PassManager}). 変数 MPM が PassManager で, add 関数を用いて pass の登録を行う. add 関数の引数に createTailCallEliminationPass 関数を指定することで tail call elimination pass が追加される.
 
-\begin{lstlisting}[float=*,frame=lrbt,label=PassManager,caption={tail call elimnation pass の追加}]
+\begin{lstlisting}[float=*,frame=lrbt,basicstyle=\tiny,label=PassManager,caption={tail call elimnation pass の追加}]
        :
   if (OptLevel == 0) {
        :
@@ -778,7 +739,7 @@
 
 アセンブリコードの方では code segment f\_g0 への遷移が call 命令でなく jmp 命令で行われており, きちんと tail call elimination が強制されていることがわかる. これはオプションの引き継ぎが正しく行われたことを示す.
 
-\begin{lstlisting}[float=*,frame=lrbt,label=evalCbC,caption={CbCのコード}]
+\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalCbC,caption={CbCのコード}]
 __code f(int i,stack sp) {
   int k,j;
   k = 3+i;
@@ -786,7 +747,7 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[float=*,frame=lrbt,label=evalIR,caption={出力された LLVM IR}]
+\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalIR,caption={出力された LLVM IR}]
 define fastcc void @f(i32 %i, i8* %sp) #0 {
 entry:
 %add = add nsw i32 3, %i
@@ -795,7 +756,7 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[float=*,frame=lrbt,label=evalAsm,caption={出力されたアセンブリコード}]
+\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=evalAsm,caption={出力されたアセンブリコード}]
    .cfi_startproc
 ## BB#0:                                ## %entry
    subq  $24, %rsp
@@ -811,32 +772,18 @@
    .cfi_endproc
 \end{lstlisting}
 
-\section{軽量継続の評価}
-今回実装した CbC の軽量継続を評価する. 比較対象は C の関数呼び出しとし, それぞれを大量に行った時の時間の差を確認する. 計測に使用したコードはリスト \ref{calc},\ref{calcCbC} で, 結果は表\ref{comp} である.
-
-結果より, 軽量継続が関数呼び出しよりも高速であることがわかる. 軽量継続では tail call elimination 等によってスタック操作の処理が省かれるのでその影響だろう.
-
-\begin{lstlisting}[frame=lrbt,label=calc,caption={Cの計測用コード}]
-int func3(int a, int b){
-  return func4(b,b/a);
-}
+Cの関数呼び出しは, スタックの書込を伴うので, かなり重い操作である. 階層化されたライブラリを経由するたびに
+関数呼び出しがはさまり, 大きなアプリでは30段になる場合もある.
+LLVMを含む最近のコンパイラでは関数は積極的に展開されてしまい, 生成されたコードが大きくなる原因となっている.
 
-int func2(int a, int b){
-  return func3(b,a*b);
-}
-\end{lstlisting}
+CbC は関数呼び出しを排除するので, jmp 命令で高速にコードセグメントを切り替えることができる. 
+C の関数呼び出しとし, それぞれを5万回に行った時の時間の差を見ると結果は表\ref{comp}になる.
 
-\begin{lstlisting}[frame=lrbt,label=calcCbC,caption={CbCの計測用コード}]
-__code code3(int a, int b,
-             int loop, int ans){
-  goto code4(b,b/a,loop, ans);
-}
-
-__code code2(int a, int b,
-             int loop, int ans){
-  goto code3(b,a*b,loop, ans);
-}
-\end{lstlisting}
+関数呼び出しを完全に排除したCbCのコードはアセンブラ的であり, 人が書きやすいものとは言えない.
+CbC はアーキテクチャに依存しないアセンブラとして使用することができる.
+性能が要求されるOSやデータベースなどのシステムソフトウェアなどに向いている.
+あるいは,状態遷移を基本としたアプリ, 例えばネットワークアプリケーション, あるいは grep などをにも
+向いている. 
 
 \begin{table}[htpb]
   \centering
@@ -850,7 +797,9 @@
 \end{table} 
 
 \section{まとめ}
-本章では LLVM と Clang を利用したオリジナルの言語のコンパイラの実装を行った. 新しい型や構文の実装方法, オプションの作り方, 最適化の追加と強制の方法について説明を行い, 正しくコンパイルできることを確認した. 重要なのは LLVM IR の改変を行わないことで, これによりバックエンドの処理をそのまま利用することが出来る. 今回実装した言語は C ベースな言語であるため clang を利用したが, 必要に応じて他のフロントエンドを利用すること, 一からフロントエンドを書くことを検討するのも良い.
+本章では LLVM と Clang を利用したオリジナルの言語のコンパイラの実装を行った. 新しい型や構文の実装方法, 
+% オプションの作り方, 
+最適化の追加と強制の方法について説明を行い, 正しくコンパイルできることを確認した. 重要なのは LLVM IR の改変を行わないことで, これによりバックエンドの処理をそのまま利用することが出来る. 今回実装した言語は C ベースな言語であるため clang を利用したが, 必要に応じて他のフロントエンドを利用すること, 一からフロントエンドを書くことを検討するのも良い.
 
 \nocite{CbC2011, LLVMIR, LLVM, clang, repo}
 \bibliographystyle{IEEEtran}