Mercurial > hg > Papers > 2014 > kaito_sigos

Binary file 2014_sigos.pdf has changed
--- a/2014_sigos.tex	Tue Apr 22 18:28:27 2014 +0900
+++ b/2014_sigos.tex	Tue Apr 22 18:57:44 2014 +0900
@@ -177,14 +177,11 @@
   \label{fig:cs}
 \end{figure}

-%\section{LLVM/clang の概要}
-%LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.\\
-%　clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
 \section{LLVM/clang}
 LLVM はコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる.
 clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.

-LLVM, clang はコンパイル対象コードを Abstract Syntax Tree (AST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブリコードに変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブリコードを出力するまでの流れを表した図である. clang はソースコードを与えられると, パーサーで構文解析を行い, AST を生成する. そしてその AST を CodeGen を用いて LLVM IR に変換する. LLVM IR をアセンブリコードに変換するまでの処理は LLVM が用いられる. LLVM IR はまず, SelectionDAGISel によって Machine Code に変換される. この時, 直接変換されるのではなく SelectionDAG という内部表現に一度変換され, 最適化された後に変換される. Machine Code は Machine code に対する最適化をかけられた後, Code Emission を通じてアセンブリコードに変換される. またこれらの内部表現の他に, clang が型を表現するのに用いる QualType というクラスについても説明する.
+LLVM, clang はコンパイル対象コードを Abstract Syntax Tree (AST), LLVM IR, Selection Directed Acycric Graph (SelectionDAG), Machine Code, MCLayer の順に変換し, その後アセンブリコードに変換する. 図\ref{fig:llvmFlow}は clang がソースコードを読み込み, アセンブリコードを出力するまでの流れを表した図である. clang はソースコードを与えられると, パーサーで構文解析を行い, AST を生成する. そしてその AST を CodeGen を用いて LLVM IR に変換する. LLVM IR をアセンブリコードに変換するまでの処理は LLVM が用いられる. LLVM IR はまず, SelectionDAGISel によって Machine Code に変換される. この時, 直接変換されるのではなく SelectionDAG という内部表現に一度変換され, 最適化された後に変換される. Machine Code は Machine code に対する最適化をかけられた後, Code Emission を通じてアセンブリコードに変換される. これらの内部表現の他に, clang が型を表現するのに用いる QualType というクラスについても説明する.

 \begin{figure}[ht]
   \begin{center}
@@ -207,47 +204,33 @@
  \label{fig:qual}
 \end{figure}

- 図\ref{fig:qual}の QualType A が const int * 型の変数, もしくは関数の持つ QualType である. これの持つ getTypePtr 関数を呼び出すことで, PointerType を得ることができる. この PointerType がどの型に対するポインタかを知るには前述したとおり getPointeeType を呼び出せば良い. そうして呼び出されたのが QualType B である. この例の QualType は const int * 型に対応するものであるので, ここで取得できた QualType B のgetTypePtr 関数を呼び出すと, 当然 IntegerType が得られる. また, この時 int には const がかかっているので, QualType B の isConstQualified 関数を呼ぶと true が返る.
+図\ref{fig:qual}の QualType A が const int * 型の変数, もしくは関数の持つ QualType である. これの持つ getTypePtr 関数を呼び出すことで, PointerType を得ることができる. この PointerType がどの型に対するポインタかを知るには前述したとおり getPointeeType を呼び出せば良い. そうして呼び出されたのが QualType B である. この例の QualType は const int * 型に対応するものであるので, ここで取得できた QualType B のgetTypePtr 関数を呼び出すと, 当然 IntegerType が得られる. また, この時 int には const がかかっているので, QualType B の isConstQualified 関数を呼ぶと true が返る.

 このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる.

 \subsection{Abstract Syntax Tree (AST)}
 AST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる.
-出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. CbC コンパイラの実装ではパーサーがこの AST を生成する部分に手を加えている.
-%% それぞれの簡単な説明を以下に記す.
-%% \begin{description}
-%%   \item[Decl]\mbox{}\\
-%%     宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
-%%   \item[Stmt]\mbox{}\\
-%%     一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する.
-%%   \item[Expr]\mbox{}\\
-%%     一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
-%% \end{description}
+出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. CbC コンパイラの実装ではパーサーが AST を生成する部分に手を加えている.

 \subsection{LLVM IR}
 LLVM IR はLLVM BitCode とも呼ばれ, リファレンスが公開されている\cite{LLVMIR}. この言語で記述したプログラムを LLVM 上で実行することも可能である. 各変数が一度のみ代入される Static Single Assignment (SSA) ベースの言語であり, LLVM 内部で扱うためのメモリ上での形式, 人が理解しやすいアセンブリ言語形式, JIT 上で実行するための bitcode 形式の三種類の形を持ち, いずれも相互変換が可能で同等なものである. ループ構文は存在せず, 一つのファイルが一つのモジュールという単位で扱われる. CbC コンパイラの実装では特に変更を行っていない.

 \subsection{SelectionDAG}
-SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種類が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は illegal SelectionDAG, legal SelectionDAG の順に変換されていき, その都度最適化が行われる. CbC コンパイラの実装では, ここで行われる最適化のうちの一つである Tail Call Elimination を code segment に対して強制するように変更を加えている.
+SelectionDAG は LLVM IR が SelectionDAG Instruction Selection Pass によって変換されたものである. SelectionDAG は非巡回有向グラフであり, そのノードは SDNode クラスによって表される. SDNode は命令と, その命令の対象となるオペランドを持つ. SelectionDAG には illegal なものと legal なものの二種が存在し, illigal SelectionDAGの段階ではターゲットがサポートしていない方や命令が残っている. LLVM IR は illegal SelectionDAG, legal SelectionDAG の順に変換されていき, その都度最適化が行われる. CbC コンパイラの実装では, ここで行われる最適化のうちの一つである Tail Call Elimination を code segment に対して強制するように変更を加えている.

 \subsection{Machine Code}
 Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ SSA 形式と物理レジスタを持つ non-SSA 形式がある. LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている. CbC コンパイラの実装では特に変更を行っていない.

 \subsection{MC Layer}
 MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. CbC コンパイラの実装では特に変更を行っていない.
-% MC Layer が扱うデータ構造は複数あるが, ここでは MCInst と MCStreamer について説明する.\\
-%　MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令は次に説明する MCInst と組み合わせて出力する.\\
-%　MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.
-

 \section{LLVM/clang 3.5 での CbC コンパイラの実装}
 以下の節では LLVM と clang に CbC コンパイラを実装する工程について詳しく説明する.

-また, 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.
+以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.
 \subsection{clang への \_\_code 型の追加}
 \label{sec:add__code}
 まず最初に関数が code segment であることを示す \_\_code 型の追加を行う. そのためには \_\_code を予約語として定義する必要がある. clang では, 予約語は全て \$(CLANG)/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 図\ref{fig:TokenKinds}のように変更を加えて \_\_code を追加した. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示す. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を設定した.
-%KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. また, 同時に定義されている \_\_return, \_\_environment は環境付き継続のための予約語である. \\

 \begin{figure}[htpb]
   \begin{center}
@@ -257,9 +240,9 @@
   \label{fig:TokenKinds}
 \end{figure}

-予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. したがって, 次に clang に \_\_code 型を認識させる必要がある.
+予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. 次に clang に \_\_code 型を認識させる.

-clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを図\ref{fig:Specifiers}のように編集した.\\
+clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを図\ref{fig:Specifiers}のように編集した.

 \begin{figure}[htpb]
   \begin{center}
@@ -278,7 +261,7 @@
   \label{fig:BuiltinTypes}
 \end{figure}

-これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. よって次に \_\_code 型を解析できるよう clang に変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われており, これが持つ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下の図\ref{fig:parse__code}ように記述を加えた. ここで重要なのは SetTypeSpecType 関数であり, これによって \_\_code 型が DeclSpec に登録される. DeclSpec は型の識別子を持つためのクラスで, 後に QualType に変換される.
+これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. 次に \_\_code 型を解析できるようパーサーに変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われており, これが持つ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下の図\ref{fig:parse__code}ように記述を加えた. ここで重要なのは SetTypeSpecType 関数であり, これによって \_\_code 型が DeclSpec に登録される. DeclSpec は型の識別子を持つためのクラスで, 後に QualType に変換される.
 \begin{figure}[htpb]
   \begin{center}
     \scalebox{0.55}{\includegraphics{figure/parse__code.pdf}}
@@ -318,7 +301,7 @@
 \end{figure}

 \subsection{継続のための goto syntax の構文解析}
-続いて, 継続のための新しい goto syntax の構文解析を行えるようにする. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下の図\ref{fig:ParseGoto}ように変更した. \\
+続いて, 継続のための新しい goto syntax の構文解析を行えるようにする. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に以下の図\ref{fig:ParseGoto}のように手を加えた.

 \begin{figure}[htpb]
   \begin{center}
@@ -328,7 +311,7 @@
   \label{fig:ParseGoto}
 \end{figure}

-ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下の図\ref{fig:ParseCbCGotoStmt} に示す.
+ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. この関数は独自に定義した関数で, その内容を以下の図\ref{fig:ParseCbCGotoStmt} に示す.
 \begin{figure}[htpb]
   \begin{center}
     \scalebox{0.55}{\includegraphics{figure/ParseGotoStmt.pdf}}
@@ -340,7 +323,8 @@
 この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する.

 \subsection{clang/LLVM 間の \_\_code 型の変換}
-前述したように, clang と LLVM は別々のクラスを用いて型を管理する. そのため clang の型クラスが LLVM のものに置き換えられる箇所で \_\_code も正しく置き換えられるようにしなければならない. \$(CLANG)/lib/CodeGen/CGCall.cpp の GetFunctionType 関数が clang での関数の型を LLVM のものに変換する関数であるのでここを編集すれば良い. 具体的には以下の図\ref{fig:type} のように編集した. 図のコード中の ABIArgInfo は clang が関数にどのように引数を渡すかの情報を保持するクラスである. void 型ではこれが必ず Ignore になり, 同じことが \_\_code 型にも言える. したがって switch 文内のこの箇所だけで型のチェックを行い, \_\_code 型の時のみ LLVM 側でも \_\_code として扱えば良い.
+%前述したように, clang と LLVM は別々のクラスを用いて型を管理する. そのため clang の型クラスが LLVM のものに置き換えられる箇所で \_\_code も正しく置き換えられるようにしなければならない.
+clang での Type が LLVM のものに置き換えられるのは \$(CLANG)/lib/CodeGen/CGCall.cpp の GetFunctionType 関数である. ここを以下の図\ref{fig:type} のように編集した. 図のコード中の ABIArgInfo は clang が関数にどのように引数を渡すかの情報を保持するクラスである. void 型ではこれが必ず Ignore になり, 同じことが \_\_code 型にも言える. したがって switch 文内のこの箇所だけで型のチェックを行い, \_\_code 型の時のみ LLVM 側でも \_\_code として扱えば良い.
 \begin{figure}[htpb]
   \begin{center}
     \scalebox{0.55}{\includegraphics{figure/type.pdf}}
@@ -349,7 +333,7 @@
   \label{fig:type}
 \end{figure}
 \subsection{Tail call eliminationの強制}
-前述したように, CbC の継続の実装には Tail call elimination を用いる. Tail call elimination は最適化の一つで, これにより code segment 間の移動を call でなく jmp 命令で行うようになる. 図\ref{fig:tce}は Tail call elimination が行われた際のプログラムの処理を表している. caller は funcB を call でなく jmp で呼び出し, funcB は caller でなく main に戻る.
+ Tail call elimination は最適化の一つで, これにより code segment 間の移動を call でなく jmp 命令で行うようになる. 図\ref{fig:tce}は Tail call elimination が行われた際のプログラムの処理を表している. caller は funcB を call でなく jmp で呼び出し, funcB は caller でなく main に戻る.

 \begin{figure}[htpb]
   \begin{center}
@@ -363,12 +347,10 @@
 \begin{enumerate}
   \item tail フラグを立てる tail call eliminatoin pass の追加.
   \item 呼び出し元と呼び出す関数の呼び出し規約が fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかである.
-%  \item 対象となる関数呼び出しが tail call である.
   \item 最適化のオプションである tailcallopt が有効になっている.
-%  \item 対象関数が可変長引数を持たない.
 \end{enumerate}

-まず tail call elimination pass 追加の処理について述べる. clang は最適化の pass の追加を \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数内で行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるが, その pass の追加はこの関数から呼び出される populateModulePassManager 関数で行われる. この関数は LLVM が用意した最適化に用いられる主要な pass を追加するものである. この関数を以下の図\ref{fig:PassManager}のように変更し, 最適化レベルに関わらず追加するようにした. MPM はpass を管理するクラスのインスタンスで, add 関数によってpass の追加が可能になる. また, createTailCallEliminationPass 関数に対して引数を受け取れるように変更を加え, これによって最適化レベルが低い時に code segment 以外の関数に対して tail call elimination しないようにしている.
+まず tail call elimination pass 追加の処理について述べる. clang は最適化の pass の追加を \$(CLANG)/lib/CodeGen/BackendUtil.cpp の CreatePasses 関数内で行っている. clang では最適化レベルを 2 以上にした場合に tail call elimination が有効化されるが, その pass の追加はこの関数から呼び出される populateModulePassManager 関数で行われる. この関数は LLVM が用意した最適化に用いられる主要な pass を追加するものである. この関数を以下の図\ref{fig:PassManager}のように変更し, 最適化レベルに関わらず追加するようにした. また, createTailCallEliminationPass 関数に対して引数を受け取れるように変更を加え, これによって最適化レベルが低い時に code segment 以外の関数に対して tail call elimination しないようにしている.

 \begin{figure}[htpb]
   \begin{center}
@@ -378,7 +360,9 @@
   \label{fig:PassManager}
 \end{figure}

-これで 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 を持つ場合には最適化レベルに関わらず追加するように変更した.
+これで 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 を持つ場合には最適化レベルに関わらず追加するように変更した.
+これら二つの pass も最適化のレベルにかかわらず追加するように変更した.

 次に, 呼び出し規約の問題を解消する. 条件を満たす呼び出し規約は fastcc, cc 10, cc 11 の三種類があるが, LLVM のドキュメントに cc 10 と cc 11 積極的に利用するのは好ましくないとあった. よって本実験では fastcc を使用する. fastcc を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. 加えて可変引数の使用が不可になり, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要があるという要件を持つ. fastcc の追加は clang が関数情報の設定処理を行っている箇所で行った. 関数情報は CGFunctionInfo というクラスを用いて管理される. 関数情報の設定は \$(CLANG)/lib/CodeGen /CGCall.cpp 内の arrangeLLVMFunctionInfo という関数で行われる. この関数に図\ref{fig:CC} に示されるコードを加えた. 変数 CC への代入文が fastcc を設定している箇所である. \\
 %関数が \_\_code型の場合で, かつ可変長引数を持たない場合に呼び出し規約を fastcc に設定する. 可変長引数に関する条件を加えているのは, 可変長引数が使用されている場合には呼び出し規約を変えず tail call elimination を行わないことで通常の関数呼び出しを生成するためである.\\
@@ -404,7 +388,7 @@
 LLVM でのオプションの追加方法についてもここで述べておく. LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. TargetOptions クラスの中で変数を宣言するだけで追加できるので, コードは省略する.

 \subsection{環境付き継続}
-CbC には通常の C の関数からコードセグメント継続する際, その関数から値を戻す処理への継続を得ることでき, これを環境付き継続と言う. こには は\_\_return, \_\_environment という特殊変数を用い. る図\ref{fig:autoCodeGenB} は環境付き継続の使用例で, この場合 caller が func を呼び出した結果得られる値 0は でなく 1 となる.
+CbC には通常の C の関数からコードセグメント継続する際, その関数から値を戻す処理への継続を得ることでき, これを環境付き継続と言う. これには \_\_return, \_\_environment という特殊変数を用いる. 図\ref{fig:autoCodeGenB} は環境付き継続の使用例で, この場合 caller が func を呼び出した結果得られる値 0 はでなく 1 となる.

 \begin{figure}[htpb]
   \begin{center}
@@ -414,28 +398,13 @@
   \label{fig:autoCodeGenB}
 \end{figure}

-GCC 上に実装した CbC コンパイラでは GCC による C の拡張構文で nested function を用いていた\cite{yogi:2008a}が, LLVM/clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. \_\_return, \_\_environment が宣言されると, 環境付き継続を用いる関数内での継続前に setjmp の構文が追加され, 環境を保持して継続を行うようになる. このとき, \_\_return には元の環境に戻るための code segment へのアドレスが, \_\_environment には元の環境が保持され, \_\_return の指す code segment に \_\_environment を渡して継続することで元の環境に戻ることができる. \_\_return へ継続することで元の環境に戻ることができるのは \_\_return の指す code segment が longjmp を呼び出すためである. また, 環境付き継続を行う際には戻り値を返すために継続元の関数の型をコピーしなければならないという問題があるが, clang では \ref{sec:QualType}節で述べた QualType をコピーするだけで解決する.
+GCC 上に実装した CbC コンパイラでは nested function を用いていた\cite{yogi:2008a}が, LLVM/clang ではこの拡張構文は対応しておらず, 別の方法をとる必要がある. そこで今回の実装には setjmp, longjmp を用いた実装を行った. \_\_return, \_\_environment が宣言されると, 環境付き継続を用いる関数内での継続前に setjmp の構文が追加され, 環境を保持して継続を行うようになる. このとき, \_\_return には元の環境に戻るための code segment へのアドレスが, \_\_environment には元の環境が保持され, \_\_return の指す code segment に \_\_environment を渡して継続することで元の環境に戻ることができる. \_\_return へ継続することで元の環境に戻ることができるのは \_\_return の指す code segment が longjmp を呼び出すためである. また, 環境付き継続を行う際には戻り値を返すために継続元の関数の型をコピーしなければならないという問題があるが, clang では \ref{sec:QualType}節で述べた QualType をコピーするだけで解決する.

 setjmp/longjmp を使って C の関数に戻ることは CbC コンパイラとは関係なくプログラムレベルでも実現できる。しかし、本来は取っておいた C のstack pointerを回復するだけでよく、
 register のsaveなどを伴う比較的重い作業である setjmp は必要ないはずである。Micro C 実装ではそのように実装されている。
 将来的により軽い処理で戻れる構文を維持することが望ましいと考えられるので、LLVM/GCC 内部で、Cへの復帰のコードを提供するようにしている。

-
-%% 図\ref{fig:autoCodeGenB} のコードの場合内部では図\ref{fig:autoCodeGenA} のように解釈される.
-
-%% \begin{figure}[htpb]
-%%   \begin{center}
-%%     \scalebox{0.50}{\includegraphics{figure/autoCodeGenA.pdf}}
-%%   \end{center}
-%%   \caption{内部での解釈}
-%%   \label{fig:autoCodeGenA}
-%% \end{figure}
-
-%% 追加された処理は, 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 を利用しており, これによって変数への代入も可能となっている.
-%追加された処理の大まかな流れを説明すると, 環境付き継続を用いる関数は継続前に setjmp を用いて戻り先の環境を保存し, 継続を行う. このとき, 引数として渡される \_\_return には特殊 code segment return1 のアドレス, \_\_environment の持つメンバには戻り値として返される値を持つ変数のアドレスと, setjmp により保存された継続前の環境が保持されている. 元の環境に戻るための code segment は自動生成されるので, 継続先の code segment は返す戻り値と \_\_environemnt を引数として \_\_return の指す code segment を呼び出すだけで元の環境に戻れる. return1 は 構造体の持つ戻り値へのポインタを利用して戻り値を更新した後, longjmp を用いて元の環境に戻る. longjmp によって再度 setjmp の呼び出しに戻るが今回は if文内に入り, 戻り値を返す.
-
 \section{評価と考察}
-% 今回の実装を行った LLVM/clang 上での CbC コンパイラの評価を試みる.
 評価は, コンパイルして出力されたアセンブリコードの確認と, CbC プログラムを Micro-C, GCC, LLVM/clang でコンパイルして得られたプログラムの実行速度を計測により行う. コンパイル, 計測は x86-64 アーキテクチャの Mac OS X 上で行った. なお, このときの GCC のバージョンは 4.9.0 である.
 末尾最適化が行われない場合は、警告が出るようになっており、CbCの仕様を満たしているかどうかは、すぐにわかるようになっている。
 \subsection{アセンブリコードの評価}
@@ -479,9 +448,9 @@

 今後は, data segment の設計及び実装がある. code segment が処理を表す単位であるのに対し, data segment は処理に必要なデータに対応する. 我々は code segment と data segment の組みがひとつの task に相当すると考えており, data segment は, 内部表現と外部表現を持つ, priority を持ち処理順序の切り替えが可能, task の待ち合わせ制御に依存される, といった要件を満たすように設計されるべきであると考えている.

-二つ目の課題として, 環境付き継続の実装をアセンブリコードを用いて行うというものがある. 今回の実装では setjmp/longjmp を用いたが, インラインアセンブリを用いてアセンブリコードを直接書き出すことで速度の向上が見込めるのではないかと考えている. GCC, LLVM はそれぞれ nested function, setjmp/longjmp と言った機能を利用して環境付き継続を実装しているが, Micro-C では直接対応するアセンブリコードを出力する. Micro-Cでは環境付き継続を用いると元の環境のアドレスをベースポインタに代入する mov 命令, ベースポインタの値をスタックポインタに代入する mov 命令, そして元の環境に帰るための jmp 命令の三つで済む. この方法だと各アーキテクチャ毎に対応しなければならないという欠点はあるが, 他の実装方法よりも楽に実装でき, 速度も勝るだろうと考えている.
-
-%以下の図\ref{MicroCAsm} の様なアセンブリコードを出力するのでこれを出力することで GCC, LLVM でも Micro-C と同等の環境付き継続が行えるようにしたい.
+二つ目の課題として, 環境付き継続の実装をアセンブリコードを用いて行うというものがある. 今回の実装では setjmp/longjmp を用いたが, インラインアセンブリを用いてアセンブリコードを直接書き出すことで速度の向上が見込めるのではないかと考えている. GCC, LLVM はそれぞれ nested function, setjmp/longjmp と言った機能を利用して環境付き継続を実装しているが, Micro-C では直接対応するアセンブリコードを出力する.
+%Micro-Cでは環境付き継続を用いると元の環境のアドレスをベースポインタに代入する mov 命令, ベースポインタの値をスタックポインタに代入する mov 命令, そして元の環境に帰るための jmp 命令の三つで済む.
+この方法だと各アーキテクチャ毎に対応しなければならないという欠点はあるが, 他の実装方法よりも楽に実装でき, 速度も勝るだろうと考えている.

 \nocite{yogi:2008a, nobu:2011a, LLVMIR, LLVM, clang, clangAPI}
 \bibliographystyle{junsrt}