Mercurial > hg > Papers > 2016 > kaito-cq
changeset 2:7cc0be313596
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 01 Mar 2016 17:16:15 +0900 |
| parents | 1c933f3a5cb7 |
| children | d9b703be7359 |
| files | paper.tex |
| diffstat | 1 files changed, 145 insertions(+), 74 deletions(-) [+] |
line wrap: on
line diff
--- a/paper.tex Mon Feb 29 18:23:40 2016 +0900 +++ b/paper.tex Tue Mar 01 17:16:15 2016 +0900 @@ -91,8 +91,24 @@ % creates the second title. It will be ignored for other modes. \IEEEpeerreviewmaketitle -本章では LLVM と Clang を利用した新しいプログラミング言語のコンパイラの実装を行う方法を Continuaton based C という言語の実装例とともに説明する. -また, この実装では LLVM IR に変更を加えることはしない. LLVM IR に変更を加える事は可能であるが, そうした場合最適化を含む LLVM の全てのパスがその変更の影響を受け, 対応させなければならくなる. これは大変難しく現実的でない. + + +本章では LLVM と Clang を利用した新しいプログラミング言語のコンパイラの実装を行う方法を Continuaton based C(CbC)\ref{cbc} +という言語の実装例とともに説明する. +LLVMとClangは、C++ で記述されており、GCCよりも見通し良く書かれている。 +LLVMは汎用のコンパイラフレームワークであり、プログラミング言語の構文解析、中間コード生成、機械語生成の各段階で様々なサポートがある。 +LLVMで新しい言語を作る方法には様々な方法がある。一つは自作の構文解析器からLLVMの抽象構文木生成のAPI呼び出す方法である。 +また、LLVM IRという中間コードを直接生成しても良い。 +DSL(ドメイン特化言語)のような場合は、それですむことが多い。 +しかし、LLVMの機能を越えたプログラミング言語を作成したい場合は、LLVMの内部に立ち入る必要がある。 + +CbCは組み込みシステムやOSなどのメタ計算、あるいは言語処理系そのものの実装に的にするように設計された言語である。 +コードセグメントという単位と、それを接続する軽量継続(引数付き大域goto文)を持つ。このように関数呼び出しそのものを +独自に持つような言語を実装するにはLLVM自体をLLVMの大域的局所的な最適化に干渉しないように修正する必要がある。 + +ここではLLVMの内部構造について詳細に説明し、CbCでの修正方法について説明していく。 + +% また, この実装では LLVM IR に変更を加えることはしない. LLVM IR に変更を加える事は可能であるが, そうした場合最適化を含む LLVM の全てのパスがその変更の影響を受け, 対応させなければならくなる. これは大変難しく現実的でない. % \section{Continuation based C} % 今回例として用いる Continuation based C \cite{CbC2011}(以下 CbC) は code segment という処理単位を持つ. @@ -121,14 +137,22 @@ % \section{LLVM clang} -LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる. LLVM を利用する各コンパイラフロントエンドはターゲットとなるプログラミング言語を LLVM IR に変換することで LLVM の持つ最適化機構を利用する. +LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本稿でも, 単に LLVM といった場合は LLVM Core を指す. -clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる. +LLVMは、 LLVM IR という独自の中間言語を持つ。これはアーキテクチャ依存でない型付きのアセンブラとなっている。人が読める形式のものと +LLVM BitCode というビットストリームにエンコードされたものがある。 +LLVMはLLVM IRを実行することのできる仮想機械も持ち、もちろん、. + LLVM IR を最適化しながら特定のターゲットの機械語に変換することもできる. + +clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたソースコードを解析し, +抽象構文木(AST)を生成する。そして、そのASTを LLVM IR に変換し、LLVM Coreにより ターゲットマシンの機械語に変換する. GCC と比較すると丁寧でわかりやすいエラーメッセージを出力する, コンパイル時間が短いといった特徴を持つ. -clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている. clang はこれらのライブラリを与えられた引数に応じて呼び出し, コンパイルを行う. さらに, 必要な場合はリンカを呼び出してリンクを行い, ソースコードを実行可能な状態まで変換することも可能である. +clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている. +clang はこれらのライブラリを与えられた引数に応じて呼び出し, コンパイルを行う. +さらに, 必要な場合は外部のリンカを呼び出してリンクを行い, ソースコードを実行可能な状態まで変換することも可能である. -ここで, そのライブラリの中でもコンパイルに関連するものについて説明する. +ここで, そのライブラリの中でもclangが使用するコンパイルに関連するものについて説明する. \begin{description} \item[libast]\mbox{}\\ @@ -157,35 +181,7 @@ \label{fig:clangProcess} \end{figure} - -\section{clangAST について} -LLVM と clang を用いたコンパイラの実装では基本的に clang の中間表現である clangAST を組み立てていくことになる. clangAST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 例えばリスト\ref{ASTSampleCode}コンパイル時にオプション ``-Xclang -ast-dump'' を付与した場合は出力結果としてリスト\ref{AST}が得られる. 出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. それぞれの簡単な説明を以下に記す (各クラスの詳細な実装は clang documentation\cite{clang} を参考に). - -\begin{description} - \item[Decl]\mbox{}\\ - 宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する. - \item[Stmt]\mbox{}\\ - 一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する. - \item[Expr]\mbox{}\\ - 一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する. -\end{description} - -これらを踏まえて, ソースコード\ref{ASTSampleCode}と出力された AST( リスト\ref{AST} ) に注目する. - -1行目の TranslationUnitDecl が根ノードに当たる. TranslationUnitDecl は翻訳単位を表すクラスであり, この AST が一つのファイルと対応していることがわかる. 実際にソースコードの内容が反映されているのは5行目以降のノードで, 5行目の FunctionDecl がソースコード\ref{ASTSampleCode}の1行目, add 関数の定義部分に当たる. ソースコード\ref{ASTSampleCode}の7行目の add 関数の呼び出しは, AST ではリスト\ref{AST}の21行目, CallExpr で表されている. この CallExpr の下のノードを見ていくと23行目の DeclRefExpr が関数のアドレスを持っており, これが add 関数のアドレスと一致することから, CallExpr は呼び出す関数への参照を持っていることがわかる. これらのノード以外についても return 文は ReturnStmt, 変数宣言は VarDecl というように, 各ノードがソースコードのいずれかの部分に対応していることが読み取れる. - -\begin{lstlisting}[frame=lrbt, label=ASTSampleCode, caption={sample.c}] -int add(int a, int b){ - return a + b; -} - -int main(){ - int res; - res = add(1,1); - return res; -} -\end{lstlisting} -\begin{lstlisting}[float=*,frame=lrbt, label=AST, caption={sample.c の AST}] +\begin{lstlisting}[float=*,basicstyle=\tiny,frame=tb, label=AST, caption={sample.c の AST}] TranslationUnitDecl 0x102020cd0 <<invalid sloc>> |-TypedefDecl 0x1020211b0 <<invalid sloc>> __int128_t '__int128' |-TypedefDecl 0x102021210 <<invalid sloc>> __uint128_t 'unsigned __int128' @@ -216,12 +212,75 @@ `-DeclRefExpr 0x102052360 <col:10> 'int' lvalue Var 0x1020219a0 'res' 'int' \end{lstlisting} -\section{LLVMでの型の扱い} -clang で新しい型を扱えるようにするためには, キーワードを登録する, 識別子を登録する, QualType の扱う Type の登録をするといった作業が必要である. これらを順に説明する. + +\section{clangAST について} +LLVM と clang を用いたコンパイラの実装では基本的に clang の中間表現である clangAST を組み立てていくことになる. clangAST はソースコードの解析結果を保持したツリーである. +AST は \\ +\begin{lstlisting}[basicstyle=\tiny,frame=lrbt, caption={ASTを表示するオプション}] + -Xclang -ast-dump +\end{lstlisting} +というオプションを付加することで表示することもできる. +例えば、簡単なCのソースコード(\ref{ASTSampleCode})は、 +リスト\ref{AST}のようになる。 + +\begin{lstlisting}[basicstyle=\tiny,frame=lrbt, label=ASTSampleCode, caption={sample.c}] +int add(int a, int b){ + return a + b; +} + +int main(){ + int res; + res = add(1,1); + return res; +} +\end{lstlisting} + +出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったC++のクラスを継承したものになっている. +それぞれの簡単な説明を以下に記す (各クラスの詳細な実装は clang documentation\cite{clang} を参考に). + +\begin{description} + \item[Decl]\mbox{}\\ + 宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する. + \item[Stmt]\mbox{}\\ + 一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する. + \item[Expr]\mbox{}\\ + 一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する. +\end{description} -clang では, 予約語は全て \$(CLANG)\footnote{clang のソースコードを展開したディレクトリのパス}/include/ clang/Basic/TokenKinds.def に定義されており, ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. ここに, 次のように変更を加えて \_\_code を追加した. これで \_\_code に対応する token の id が kw\_\_\_code になる. ここで使われている KEYWORD マクロは予約語の定義に用いられるもので, 第一引数が登録したい予約語, 第二引数がその予約語が利用される範囲を表す. KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. code segment は C のバージョンに関わらずサポートされるべきであるので KEYALL を選択した. + + +1行目の TranslationUnitDecl が根ノードに当たる. TranslationUnitDecl は翻訳単位を表すクラスであり, この AST が一つのファイルと対応していることがわかる. 実際にソースコードの内容が反映されているのは5行目以降のノードで, 5行目の FunctionDecl がソースコード\ref{ASTSampleCode}の1行目, add 関数の定義部分に当たる. +対応するソースコードの位置が明らかな場合は\verb+sample.c1:1+などと指定されており、そうでない場合は\verb+<<invalid sloc>>+となっている。 +型名や変数名などがASTに格納されていることもわかる。 +ソースコード\ref{ASTSampleCode}の7行目の add 関数の呼び出しは, AST ではリスト\ref{AST}の21行目, CallExpr で表されている. +この CallExpr の下のノードを見ていくと23行目の DeclRefExpr が関数のアドレス0x102021700を持っており, +これが add 関数のアドレスと一致することから, CallExpr は呼び出す関数への参照を持っていることがわかる. +これらのノード以外についても return 文は ReturnStmt, 変数宣言は VarDecl というように, +各ノードがソースコードのいずれかの部分に対応していることが読み取れる. + + +\section{LLVMでの型の扱い} -\begin{lstlisting}[float=*,frame=lrbt,label=token,caption={キーワードの登録}] +clangに新しい機能を付け加えるには新しい型が必要となることがある。 +clang で新しい型を扱えるようにするためには, まず型の表す予約後(KEYWORD)を登録する, +そして、それに対応する識別子を登録する, +それを QualType (Qaulified type)というC++のオブジェクトの扱う Type として登録をするという手順になる。 +ここで新しく作られた型はIRレベルでは基本的な型に展開されてしまうので、LLVMの最適化と衝突することはない。 + +clang では, 予約語は全て \$(CLANG)\footnote{clang のソースコードを展開したディレクトリのパス}/include/ clang/Basic/TokenKinds.def に定義されている. +ここで定義した予約語の頭に kw\_ を付けたものがその予約語の ID となる. + +ここでは CbC のコードセグメントを表す型である\_\_code を追加してみよう。 +\_\_code という型は実際には\verb+void *+だが、これを関数の戻り値の型と指定することにより、その関数がコードセグメントであることを表す. + +まず、TokenKinds.def のKEYWORDにに\_\_code を追加する. +これで \_\_code に対応する token の id が kw\_\_\_code になる. +ここで使われている KEYWORD はCのマクロであり、予約語の定義に用いられる. +KEYWORDの第一引数が登録したい予約語, 第二引数のKEYALLはその予約語が利用される範囲を表す. +KEYALL は全ての C, C++ でサポートされることを示し, この他には C++ の予約語であることを示す KEYCXX や C++11 以降で利用されることを示す KEYCXX11 等がある. +\verb+noCbC+はCbCでの変更部分を示す条件マクロになっている. + +\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=token,caption={キーワードの登録}] : KEYWORD(__func__ , KEYALL) KEYWORD(__objc_yes , KEYALL) @@ -234,11 +293,11 @@ : \end{lstlisting} -予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. +予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. 次は clang 内部で使用する識別子を作る. -clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを以下のように編集した. +clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include /clang/Basic/Specifiers.h で行われており, これを以下のように編集した. -\begin{lstlisting}[float=*,frame=lrbt,label=TST,caption={TypeSpecTypeの登録}] +\begin{lstlisting}[frame=lrbt,,basicstyle=\tiny,label=TST,caption={TypeSpecTypeの登録}] enum TypeSpecifierType { TST_unspecified, TST_void, @@ -250,7 +309,12 @@ \end{lstlisting} これに加えてさらに QualType が用いる Type を作らなければならない. -QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (ポインタ) 等の型情報を持つ Type オブジェクトへのポインタを持つ. QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる. また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ, それを通してポインタの指す型を知ることが可能である. 配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する. 修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる. +QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (ポインタ) 等の型情報を持つ Type オブジェクトへのポインタを持つ. +QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる. +また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ, +それを通してポインタの指す型を知ることが可能である. +配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する. +修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる. ここで, 以下に一つの例として ``const int *'' 型に対応する QualType を表した図を示す. @@ -267,9 +331,11 @@ このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる. -この Type の定義は \$(CLANG)/include/clang/AST/BuiltinTypes.def で行われているので, これを編集する(リスト\ref{clangType}). ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. \_\_code 型は符号無し,有りといった性質を保つ必要はないため, 今回は BUILTIN\_TYPE を使うべきである. +この Type の定義は \$(CLANG)/include/ clang/AST/BuiltinTypes.def で行われているので, これを編集する(リスト\ref{clangType}). +ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. +\_\_code 型は符号無し,有りといった性質を保つ必要はないため, 今回は BUILTIN\_TYPE を使うべきである. -\begin{lstlisting}[float=*,frame=lrbt,label=clangType,caption={Typeの登録}] +\begin{lstlisting}[frame=lrbt,basicstyle=\tiny,label=clangType,caption={Typeの登録}] : // 'bool' in C++, '_Bool' in C99 UNSIGNED_TYPE(Bool, BoolTy) @@ -286,8 +352,14 @@ : \end{lstlisting} -ここまでの変更で clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. -次は \_\_code 型を解析し clangAST に変換できるようにしなければならない. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている. +ここまでの変更で clang が \_\_code 型を扱えるようになった. +% り, \_\_code 型の関数, 即ち code segment を解析する準備が整った. + + +次は clang が \_\_code 型を解析し clangAST に変換できるようにしなければならない. +clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. +この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. +具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている. \begin{lstlisting}[float=*,frame=lrbt,label=parse__Code,caption={\_\_code の parse}] case tok::kw___code: { @@ -493,33 +565,32 @@ MC Layer で用いられる各クラスも ``-mllvm -asm-show-inst'' オプションを用いることで他の中間表現のように確認することが出来る. MCInst はアセンブリの各命令に対応しているので, アセンブリファイルにコメントとして出力される. リスト \ref{MCInst} は\ref{IRtestC} をコンパイルして得られるアセンブリコードの一部である. 各命令の隣にコメントで記されているのが MCInst, 下に記されているのが MCOperand である. -\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=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} \section{オプションの追加} リスト\ref{parse__Code} では新たに作成した HasCodeSegment というオプションを変更する処理を行っている(4行目). このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, 最適化を利用するためである. このオプションは LangOptions というクラスによって管理されている. LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, それらは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.