|
8
|
1 \chapter{LLVM clang}
|
|
3
|
2 \label{chapter:LLVM/clang}
|
|
|
3 LLVM とはコンパイラ, ツールチェーン技術等を開発するプロジェクトの名称である. 単に LLVM といった場合は LLVM Core を指し, これはコンパイラの基板となるライブラリの集合である. 以降は本論文でも, 単に LLVM といった場合は LLVM Core を指す. LLVM IR や LLVM BitCode と呼ばれる独自の言語を持ち, この言語で書かれたプログラムを実行することのできる仮想機械も持つ. また, LLVM IR を特定のターゲットの機械語に変換することが可能であり, その際に LLVM の持つ最適化機構を利用することができる. LLVM を利用する各コンパイラフロントエンドはターゲットとなるプログラミング言語を LLVM IR に変換することで LLVM の持つ最適化機構を利用する.
|
|
1
|
4
|
|
|
5 clang は バックエンドに LLVM を利用する C/C++/Objective-C コンパイラである. 具体的には与えられたコードを解析し, LLVM IR に変換する部分までを自身で行い, それをターゲットマシンの機械語に変換する処理と最適化に LLVM を用いる.
|
|
|
6 GCC と比較すると丁寧でわかりやすいエラーメッセージを出力する, コンパイル時間が短いといった特徴を持つ.
|
|
|
7
|
|
3
|
8
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 \section{clang の基本構造}
|
|
3
|
10 \label{sec:clang}
|
|
|
11 clang は library-based architecture というコンセプトの元に設計されており, 字句解析を行う liblex, 構文解析を行う libparse といったように処理機構ごとに複数のライブラリに分割されている. clang はこれらのライブラリを与えられた引数に応じて呼び出し, コンパイルを行う. さらに, 必要な場合はリンカを呼び出してリンクを行い, ソースコードを実行可能な状態まで変換することも可能である.
|
|
|
12
|
|
|
13 ここで, そのライブラリの中でもコンパイルに関連するものについて説明する.
|
|
|
14
|
|
|
15 \begin{description}
|
|
|
16 \item[libast]\mbox{}\\
|
|
|
17 Abstract Syntax Tree (AST) や C の型等をクラスとして利用できるようにしたライブラリ. AST の説明は後述する. % AST は ``-Xclang -ast-dump'' オプションを付加することで表示できる.
|
|
|
18 \item[liblex]\mbox{}\\
|
|
|
19 字句解析ライブラリ. マクロの展開等の前処理系も担当する.
|
|
|
20 \item[libparse]\mbox{}\\
|
|
|
21 構文解析ライブラリ. 解析結果を元に後述するlibsemaを使用して AST を生成する.
|
|
|
22 \item[libsema]\mbox{}\\
|
|
|
23 意味解析ライブラリ. parser (libparse) に AST を生成する機能を提供する.
|
|
|
24 \item[libcodegen]\mbox{}\\
|
|
|
25 コード生成ライブラリ. 生成された AST を LLVM IR に変換する.
|
|
|
26 \item[clang]\mbox{}\\
|
|
|
27 ドライバ. 各ライブラリを用いて求められた処理を行う.
|
|
|
28 \end{description}
|
|
|
29
|
|
|
30 これを踏まえて clang が C のコードを LLVM IR に変換する処理について説明する. 尚 LLVM IR が アセンブリ言語にコンパイルされる処理の過程については\ref{sec:llvm}節で LLVM の基本構造とともに説明する.
|
|
|
31
|
|
|
32 以下の図\ref{fig:clangProcess}は clang が C のコードを LLVM IR に変換する処理の過程を簡潔に図示したものである. clang は C のソースコードを受け取るとまずその解析を libparser による parser を用いて行い, libsema を用いて 解析結果から AST を構築する. そしてその AST を libcodegen を用いて LLVM IR に変換する.
|
|
|
33
|
|
|
34 \begin{figure}[htpb]
|
|
|
35 \begin{center}
|
|
|
36 \scalebox{0.35}{\includegraphics{fig/clangProcess.pdf}}
|
|
|
37 \end{center}
|
|
|
38 \caption{clang の 処理過程}
|
|
|
39 \label{fig:clangProcess}
|
|
|
40 \end{figure}
|
|
|
41
|
|
|
42 AST はソースコードの解析結果を保持したツリーである. AST は ``-Xclang -ast-dump'' というオプションを付加することで表示することもできる. 例えばリスト\ref{ASTSampleCode}コンパイル時にオプション ``-Xclang -ast-dump'' を付与した場合は出力結果としてリスト\ref{AST}が得られる. 出力された AST の各行が AST のノード なっており, 各ノードは Decl, Stmt, Expr といったクラスを継承したものになっている. それぞれの簡単な説明を以下に記す.
|
|
|
43
|
|
|
44 \begin{description}
|
|
|
45 \item[Decl]\mbox{}\\
|
|
|
46 宣言や定義を表すクラスであり, 関数の宣言を表す FunctionDecl, 変数の宣言を表す VarDecl 等のサブクラスが存在する.
|
|
|
47 \item[Stmt]\mbox{}\\
|
|
|
48 一つの文に対応するクラスであり, if 文と対応する IfStmt, 宣言文と対応する DeclStmt, return 文と対応する ReturnStmt 等のサブクラスが存在する.
|
|
|
49 \item[Expr]\mbox{}\\
|
|
|
50 一つの式に対応するクラスであり, 関数呼び出しと対応する CallExpr, キャストと対応する CastExpr 等のサブクラスが存在する.
|
|
|
51 \end{description}
|
|
|
52
|
|
|
53 これらを踏まえて, ソースコード\ref{ASTSampleCode}と出力された AST( リスト\ref{AST} ) に注目する.
|
|
|
54
|
|
|
55 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 というように, 各ノードがソースコードのいずれかの部分に対応していることが読み取れる.
|
|
|
56
|
|
|
57 \begin{lstlisting}[frame=lrbt, label=ASTSampleCode, caption={sample.c}]
|
|
|
58 int add(int a, int b){
|
|
|
59 return a + b;
|
|
|
60 }
|
|
|
61
|
|
|
62 int main(){
|
|
|
63 int res;
|
|
|
64 res = add(1,1);
|
|
|
65 return res;
|
|
|
66 }
|
|
|
67 \end{lstlisting}
|
|
|
68 \begin{lstlisting}[frame=lrbt, label=AST, caption={sample.c の AST}]
|
|
|
69 TranslationUnitDecl 0x102020cd0 <<invalid sloc>>
|
|
|
70 |-TypedefDecl 0x1020211b0 <<invalid sloc>> __int128_t '__int128'
|
|
|
71 |-TypedefDecl 0x102021210 <<invalid sloc>> __uint128_t 'unsigned __int128'
|
|
|
72 |-TypedefDecl 0x102021560 <<invalid sloc>> __builtin_va_list '__va_list_tag [1]'
|
|
|
73 |-FunctionDecl 0x102021700 <sample.c:1:1, line:3:1> add 'int (int, int)'
|
|
|
74 | |-ParmVarDecl 0x1020215c0 <line:1:9, col:13> a 'int'
|
|
|
75 | |-ParmVarDecl 0x102021630 <col:16, col:20> b 'int'
|
|
|
76 | `-CompoundStmt 0x102021878 <col:22, line:3:1>
|
|
|
77 | `-ReturnStmt 0x102021858 <line:2:3, col:14>
|
|
|
78 | `-BinaryOperator 0x102021830 <col:10, col:14> 'int' '+'
|
|
|
79 | |-ImplicitCastExpr 0x102021800 <col:10> 'int' <LValueToRValue>
|
|
|
80 | | `-DeclRefExpr 0x1020217b0 <col:10> 'int' lvalue ParmVar 0x1020215c0 'a' 'int'
|
|
|
81 | `-ImplicitCastExpr 0x102021818 <col:14> 'int' <LValueToRValue>
|
|
|
82 | `-DeclRefExpr 0x1020217d8 <col:14> 'int' lvalue ParmVar 0x102021630 'b' 'int'
|
|
|
83 `-FunctionDecl 0x1020218f0 <line:5:1, line:9:1> main 'int ()'
|
|
|
84 `-CompoundStmt 0x1020523c0 <line:5:11, line:9:1>
|
|
|
85 |-DeclStmt 0x102052210 <line:6:3, col:10>
|
|
|
86 | `-VarDecl 0x1020219a0 <col:3, col:7> res 'int'
|
|
|
87 |-BinaryOperator 0x102052338 <line:7:3, col:16> 'int' '='
|
|
|
88 | |-DeclRefExpr 0x102052228 <col:3> 'int' lvalue Var 0x1020219a0 'res' 'int'
|
|
|
89 | `-CallExpr 0x102052300 <col:9, col:16> 'int'
|
|
|
90 | |-ImplicitCastExpr 0x1020522e8 <col:9> 'int (*)(int, int)' <FunctionToPointerDecay>
|
|
|
91 | | `-DeclRefExpr 0x102052250 <col:9> 'int (int, int)' Function 0x102021700 'add' 'int (int, int)'
|
|
|
92 | |-IntegerLiteral 0x102052278 <col:13> 'int' 1
|
|
|
93 | `-IntegerLiteral 0x102052298 <col:15> 'int' 1
|
|
|
94 `-ReturnStmt 0x1020523a0 <line:8:3, col:10>
|
|
|
95 `-ImplicitCastExpr 0x102052388 <col:10> 'int' <LValueToRValue>
|
|
|
96 `-DeclRefExpr 0x102052360 <col:10> 'int' lvalue Var 0x1020219a0 'res' 'int'
|
|
|
97 \end{lstlisting}
|
|
|
98
|
|
|
99 AST の他に本研究において重要な clang のクラスに QualType がある. このクラスは後に説明する環境付き継続の実装に関わるクラスである.
|
|
|
100
|
|
|
101 QualType は変数や関数等の型情報を持つクラスで, const, volatile 等の修飾子の有無を示すフラグと, int, char, * (ポインタ) 等の型情報を持つ Type オブジェクトへのポインタを持つ. QualType の持つ Type オブジェクトは getTypePtr 関数を呼び出すことで取得でき, Type クラスは isIntegerType, isVoidType, isPointerType と言った関数を持つので, これを利用して型を調べることができる. また, ポインタ型である場合には getPointeeType という関数を呼び出すことでそのポインタが指す型の Type を持つ QualType を得ることができ, それを通してポインタの指す型を知ることが可能である. 配列や参照等に対しても同様に, それぞれ要素, 参照元の Type へのポインタを持つ QualType を得る関数が存在する. 修飾子の有無は const なら isConstQualified, volatile なら isVolatileQualified といった関数を用いて確認できる.
|
|
|
102
|
|
|
103
|
|
|
104 ここで, 以下に一つの例として ``const int *'' 型に対応する QualType を表した図を示す.
|
|
|
105
|
|
|
106 \begin{figure}[htpb]
|
|
|
107 \begin{center}
|
|
|
108 \scalebox{0.4}{\includegraphics{fig/qualType.pdf}}
|
|
|
109 \end{center}
|
|
|
110 \caption{const int * に対応する QualType}
|
|
|
111 \label{fig:qual}
|
|
|
112 \end{figure}
|
|
|
113
|
|
|
114 図\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 が返る.
|
|
|
115
|
|
|
116
|
|
|
117 このように, clang では複雑な型を持つ関数, 変数でもその型を表すために持つ QualType は一つであり, それが指す Type を辿ることで完全な型を知ることができる.
|
|
|
118
|
|
|
119
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120 \section{LLVM の基本構造}
|
|
3
|
121 \label{sec:llvm}
|
|
|
122 LLVM は LLVM IR をターゲットのアセンブリ言語に直接的に変換を行うわけではない. 中間表現を何度か変え, その度に最適化を行い, そして最終的にターゲットのアセンブリ言語に変換するのである.
|
|
|
123 また LLVM では, 最適化や中間表現の変換といったコンパイラを構成する処理は全て pass が行う. 多くの pass は最適化のために存在し, この pass を組み合わせることにより, LLVM の持つ機能の中から任意のものを利用することができる.
|
|
|
124
|
|
|
125 LLVM がターゲットのアセンブリ言語を生成するまでの過程を簡潔に記すと以下のようになる.
|
|
|
126
|
|
|
127 \begin{description}
|
|
|
128 \item[SelectionDAG Instruction Selection (SelectionDAGISel)]\mbox{}\\
|
|
|
129 LLVM IR を SelectionDAG (DAG は Directed Acycric Graph の意) に変換し, 最適化を行う. その後 Machine Code を生成する.
|
|
|
130 \item[SSA-based Machine Code Optimizations]\mbox{}\\
|
|
|
131 SSA-based Machine Code に対する最適化を行う. 各最適化はそれぞれ独立した pass になっている.
|
|
|
132 \item[Register Allocation]\mbox{}\\
|
|
|
133 仮装レジスタから物理レジスタへの割り当てを行う. ここで PHI 命令が削除され, SSA-based でなくなる.
|
|
|
134 \item[Prolog/Epilog Code Insertion]\mbox{}\\
|
|
|
135 Prolog/Epilog Code の挿入を行う. どちらも関数呼び出しに関わるものであり, Prolog は関数を呼び出す際に呼び出す関数のためのスタックフレームを準備する処理, Epilog は呼び出し元の関数に戻る際に行う処理である.
|
|
|
136 \item[Late Machine Code Optimizations]\mbox{}\\
|
|
|
137 Machine Code に対してさらに最適化を行う.
|
|
|
138 \item[Code Emission]\mbox{}\\
|
|
|
139 Machine Code を MC Layer での表現に変換する. その後さらにターゲットのアセンブリ言語へ変換し, その出力を行う.
|
|
|
140 \end{description}
|
|
|
141
|
|
|
142 これらの処理の流れを図示したものが以下の図\ref{fig:llvmProcess}である. 前述した通りこれらの処理は全て pass によって行われる. pass にはいくつかの種類があり, 関数単位で処理を行うもの, ファイル単位で処理を行うもの, ループ単位で処理を行うもの等がある.
|
|
|
143
|
|
|
144 \begin{figure}[htpb]
|
|
|
145 \begin{center}
|
|
|
146 \scalebox{0.35}{\includegraphics{fig/llvmProcess.pdf}}
|
|
|
147 \end{center}
|
|
|
148 \caption{LLVM の 処理過程}
|
|
|
149 \label{fig:llvmProcess}
|
|
|
150 \end{figure}
|
|
|
151
|
|
|
152
|
|
|
153 \section{LLVM の中間表現}
|
|
|
154 この節では LLVM の中間表現である LLVM IR, SelectionDAG, Machine Code, MC Layer\footnote{ MC Layer は正確には中間表現ではない. 詳しくは本節で後述する. } と LLVM の最適化について簡単に説明する. なお, 詳しくは LLVM Documantation\cite{LLVM}を参照していただきたい.
|
|
|
155
|
|
|
156 LLVM のメインとなる中間表現はフロントエンドの出力, バックエンドの入力に対応する LLVM IR である.
|
|
|
157
|
|
|
158 LLVM IR はLLVM BitCode とも呼ばれ, リファレンスが公開されている\cite{LLVMIR}. この言語で記述したプログラムを LLVM 上で実行することも可能である. 各変数が一度のみ代入される Static Single Assignment (SSA) ベースの言語であり, コンパイラ中のメモリ上での形式, 人が理解しやすいアセンブリ言語形式 (公開されているリファレンスはこの形式に対するものである), JIT 上で実行するための bitcode 形式の三種類の形を持ち, いずれも相互変換が可能で同等なものである. ループ構文は存在せず, 一つのファイルが一つのモジュールという単位で扱われる.
|
|
|
159
|
|
|
160 LLVM IR の一例として c 言語の関数を clang を用いて LLVM IR に変換したものをリスト \ref{IRtestC}, \ref{IRtestIR} に示す. LLVM IR に変換された後の関数 test を見ると, while文によるループ構文がなくなっていることがわかる. while文は while.cond, while.body という 2つのブロックに分けられており, while.cond が while文の条件文, while.body が while文の中身を表している. while.end は while という名が付いているが, while文と直接は関係しておらず, これは while文によるループ処理が終わった後の処理が置き換わったものである.
|
|
|
161
|
|
|
162 \begin{lstlisting}[frame=lrbt, label=IRtestC, caption={c での関数 test}]
|
|
|
163 int test(int a, int b){
|
|
|
164 int i, sum = 0;
|
|
|
165 i = a;
|
|
|
166 while ( i <= b) {
|
|
|
167 sum += i;
|
|
|
168 i++;
|
|
|
169 }
|
|
|
170 return sum - a * b;
|
|
|
171 }
|
|
|
172 \end{lstlisting}
|
|
|
173
|
|
|
174 \begin{lstlisting}[frame=lrbt, label=IRtestIR, caption={LLVM IR での関数 test}]
|
|
|
175 define i32 @test(i32 %a, i32 %b) #0 {
|
|
|
176 entry:
|
|
|
177 br label %while.cond
|
|
|
178
|
|
|
179 while.cond:
|
|
|
180 %i.0 = phi i32 [ %a, %entry ], [ %inc, %while.body ]
|
|
|
181 %sum.0 = phi i32 [ 0, %entry ], [ %add, %while.body ]
|
|
|
182 %cmp = icmp sle i32 %i.0, %b
|
|
|
183 br i1 %cmp, label %while.body, label %while.end
|
|
|
184
|
|
|
185 while.body:
|
|
|
186 %add = add nsw i32 %sum.0, %i.0
|
|
|
187 %inc = add nsw i32 %i.0, 1
|
|
|
188 br label %while.cond
|
|
|
189
|
|
|
190 while.end:
|
|
|
191 %mul = mul nsw i32 %a, %b
|
|
|
192 %sub = sub nsw i32 %sum.0, %mul
|
|
|
193 ret i32 %sub
|
|
|
194 }
|
|
|
195 \end{lstlisting}
|
|
|
196
|
|
|
197 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 に変換されるまでに行われる処理の過程を示す.
|
|
|
198
|
|
|
199 \begin{description}
|
|
|
200 \item[Build initial DAG]\mbox{}\\
|
|
|
201 LLVM IR を illegal SelectionDAG に変換する.
|
|
|
202 \item[Optimize]\mbox{}\\
|
|
|
203 illegal SelectionDAG に対して最適化を行う.
|
|
|
204 \item[Legalize SelectionDAG Types]\mbox{}\\
|
|
|
205 ターゲットのサポートしていない型を除去し, ターゲットのサポートする型だけで構成された SelectionDAG に変換する.
|
|
|
206 \item[Optimize]\mbox{}\\
|
|
|
207 最適化. 型変換が行われたことで表面化した冗長性の解消を行う.
|
|
|
208 \item[Legalize SelectionDAG Ops]\mbox{}\\
|
|
|
209 ターゲットのサポートしていない命令を除去し, ターゲットのサポートする命令だけで構成された SelectionDAG に変換する. これで SelectionDAG の legalization が完了となる.
|
|
|
210 \item[Optimize]\mbox{}\\
|
|
|
211 最適化. 命令を変更したことによって発生した非効率性を排除する.
|
|
|
212 \item[Select instructions from DAG]\mbox{}\\
|
|
|
213 SelectionDAG を元に, 現在の命令をターゲットのサポートする命令に置き換えた DAG を生成する.
|
|
|
214 \item[SelectionDAG Scheduling and Formation]\mbox{}\\
|
|
|
215 命令のスケジューリングを行い, DAG を Machine Code に変換する.
|
|
|
216 \end{description}
|
|
|
217
|
|
|
218 SelectionDAG を確認したい場合は clang に ``-mllvm -view-***-dags'' オプションを与えることで生成される dot ファイルを見れば良い. *** には legalize などの文字列が入り, どの段階の DAG を出力するか選択することが出来る. 図 \ref{fig:dag} はリスト \ref{IRtestC} の add 関数に対応する legalize 直前の DAG である. この図より, + 演算子に対応する add ノードや return 命令に対応するノードその戻り値を受けるためのレジスタが指定されているのがわかる.
|
|
|
219
|
|
|
220
|
|
|
221 \begin{figure}[htpb]
|
|
|
222 \begin{center}
|
|
|
223 \scalebox{0.50}{\includegraphics{fig/dag.pdf}}
|
|
|
224 \end{center}
|
|
|
225 \caption{add 関数に対応する legalize 直前の SelectionDAG}
|
|
|
226 \label{fig:dag}
|
|
|
227 \end{figure}
|
|
|
228
|
|
|
229
|
|
|
230 Machine Code は LLVM IR よりも機械語に近い形の中間言語であり, 無限の仮装レジスタを持つ Single Static Assignment (SSA) 形式と物理レジスタを持つ non-SSA 形式がある. SSA 形式とは全ての変数が一度のみ代入されるように記述した形式であり. この形式を取ることで LLVM は効率よく最適化を行うことが出来る.
|
|
|
231
|
|
|
232 Machine Code は LLVM IR より抽象度は低いが, この状態でもまだターゲットに依存しない抽象度を保っている. Machine Code は LLVM 上では MachineFunction, MachineBasicBlock, MachineInstr クラスを用いて管理される. MachineInstr は一つの命令と対応し, MachineBasicBlock は MachineInstr のリスト, そして MachineFunction が MachineBasicBlock のリストとなっている.
|
|
|
233
|
|
|
234 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 では仮想レジスタが取り除かれていることがわかる.
|
|
|
235 \begin{lstlisting}[frame=lrbt, label=MachineCodeSSA, caption={Machine Code (SSA)}]
|
|
|
236 Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
|
|
|
237
|
|
|
238 BB#0: derived from LLVM BB %entry
|
|
|
239 Live Ins: %EDI %ESI
|
|
|
240 %vreg5<def> = COPY %ESI
|
|
|
241 %vreg4<def> = COPY %EDI
|
|
|
242 %vreg6<def> = MOV32r0 %EFLAGS<imp-def,dead>
|
|
|
243 Successors according to CFG: BB#1
|
|
|
244
|
|
|
245 BB#1: derived from LLVM BB %while.cond
|
|
|
246 Predecessors according to CFG: BB#0 BB#2
|
|
|
247 %vreg0<def> = PHI %vreg4, <BB#0>, %vreg3, <BB#2>
|
|
|
248 %vreg1<def> = PHI %vreg6, <BB#0>, %vreg2, <BB#2>
|
|
|
249 %vreg7<def,tied1> = SUB32rr %vreg0<tied0>, %vreg5, %EFLAGS<imp-def>
|
|
|
250 JG_4 <BB#3>, %EFLAGS<imp-use>
|
|
|
251 JMP_4 <BB#2>
|
|
|
252 Successors according to CFG: BB#2(124) BB#3(4)
|
|
|
253
|
|
|
254 BB#2: derived from LLVM BB %while.body
|
|
|
255 Predecessors according to CFG: BB#1
|
|
|
256 %vreg2<def,tied1> = ADD32rr %vreg1<tied0>, %vreg0, %EFLAGS<imp-def,dead>
|
|
|
257 %vreg3<def,tied1> = INC64_32r %vreg0<tied0>, %EFLAGS<imp-def,dead>
|
|
|
258 JMP_4 <BB#1>
|
|
|
259 Successors according to CFG: BB#1
|
|
|
260
|
|
|
261 BB#3: derived from LLVM BB %while.end
|
|
|
262 Predecessors according to CFG: BB#1
|
|
|
263 %vreg8<def,tied1> = IMUL32rr %vreg4<tied0>, %vreg5, %EFLAGS<imp-def,dead>
|
|
|
264 %vreg9<def,tied1> = SUB32rr %vreg1<tied0>, %vreg8<kill>, %EFLAGS<imp-def,dead>
|
|
|
265 %EAX<def> = COPY %vreg9
|
|
|
266 RET %EAX
|
|
|
267 \end{lstlisting}
|
|
|
268
|
|
|
269 \begin{lstlisting}[frame=lrbt, label=MachineCodeNonSSA, caption={Machine Code (non-SSA)}]
|
|
|
270 Function Live Ins: %EDI in %vreg4, %ESI in %vreg5
|
|
|
271
|
|
|
272 0B BB#0: derived from LLVM BB %entry
|
|
|
273 Live Ins: %EDI %ESI
|
|
|
274 48B %EAX<def> = MOV32r0 %EFLAGS<imp-def,dead>
|
|
|
275 64B %ECX<def> = COPY %EDI
|
|
|
276 Successors according to CFG: BB#1
|
|
|
277
|
|
|
278 96B BB#1: derived from LLVM BB %while.cond
|
|
|
279 Live Ins: %ESI %EDI %ECX %EAX
|
|
|
280 Predecessors according to CFG: BB#0 BB#2
|
|
|
281 144B CMP32rr %ECX, %ESI, %EFLAGS<imp-def>
|
|
|
282 160B JG_4 <BB#3>, %EFLAGS<imp-use,kill>
|
|
|
283 176B JMP_4 <BB#2>
|
|
|
284 Successors according to CFG: BB#2(124) BB#3(4)
|
|
|
285
|
|
|
286 192B BB#2: derived from LLVM BB %while.body
|
|
|
287 Live Ins: %ESI %EDI %ECX %EAX
|
|
|
288 Predecessors according to CFG: BB#1
|
|
|
289 224B %EAX<def,tied1> = ADD32rr %EAX<kill,tied0>, %ECX, %EFLAGS<imp-def,dead>
|
|
|
290 256B %ECX<def,tied1> = INC64_32r %ECX<kill,tied0>, %EFLAGS<imp-def,dead>
|
|
|
291 304B JMP_4 <BB#1>
|
|
|
292 Successors according to CFG: BB#1
|
|
|
293
|
|
|
294 320B BB#3: derived from LLVM BB %while.end
|
|
|
295 Live Ins: %ESI %EDI %EAX
|
|
|
296 Predecessors according to CFG: BB#1
|
|
|
297 352B %EDI<def,tied1> = IMUL32rr %EDI<kill,tied0>, %ESI<kill>, %EFLAGS<imp-def,dead>
|
|
|
298 384B %EAX<def,tied1> = SUB32rr %EAX<kill,tied0>, %EDI<kill>, %EFLAGS<imp-def,dead>
|
|
|
299 416B RET %EAX
|
|
|
300 \end{lstlisting}
|
|
|
301
|
|
|
302 MC Layer は正確には中間表現を指すわけではなく, コード生成などを抽象化して扱えるようにした層である. 関数やグローバル変数といったものは失われており, MC Layer を用いることで, Machine Code からアセンブリ言語への変換, オブジェクトファイルの生成, JIT 上での実行と言った異なった処理を同一の API を用いて行うことが可能になる. MC Layer が扱うデータ構造は複数あるが, ここでは MCInst, MCStreamer, MCOperand について説明する.
|
|
|
303
|
|
|
304 MCStreamer は アセンブラ API であり, アセンブリファイルの出力や, オブジェクトファイルの出力はこの API を通して行われる. ラベルや .align 等のディレクティブの生成はこの API を利用するだけで可能になる. しかし MCStreamer は機械語に対応する命令は持っておらず, それらの命令を出力するには MCInst クラスを用いる.
|
|
|
305
|
|
|
306 MCInst はターゲットに依存しないクラスである. 一つの機械語の命令を表し, 命令とオペランドから構成される.
|
|
|
307
|
|
|
308 MCOperand はオペランドに対応し, MCInst はこのクラスを用いる.
|
|
|
309
|
|
|
310 MC Layer で用いられる各クラスも ``-mllvm -asm-show-inst'' オプションを用いることで他の中間表現のように確認することが出来る. MCInst はアセンブリの各命令に対応しているので, アセンブリファイルにコメントとして出力される. リスト \ref{MCInst} は\ref{IRtestC} をコンパイルして得られるアセンブリコードの一部である. 各命令の隣にコメントで記されているのが MCInst, 下に記されているのが MCOperand である.
|
|
|
311
|
|
|
312 \begin{lstlisting}[frame=lrbt, label=MCInst, caption={アセンブリコードと MCInst}]
|
|
|
313 _add: ## @add
|
|
|
314 .cfi_startproc
|
|
|
315 ## BB#0: ## %entry
|
|
|
316 pushq %rbp ## <MCInst #2300 PUSH64r
|
|
|
317 ## <MCOperand Reg:36>>
|
|
|
318 Ltmp0:
|
|
|
319 .cfi_def_cfa_offset 16
|
|
|
320 Ltmp1:
|
|
|
321 .cfi_offset %rbp, -16
|
|
|
322 movq %rsp, %rbp ## <MCInst #1684 MOV64rr
|
|
|
323 ## <MCOperand Reg:36>
|
|
|
324 ## <MCOperand Reg:44>>
|
|
|
325 Ltmp2:
|
|
|
326 .cfi_def_cfa_register %rbp
|
|
|
327 addl %esi, %edi ## <MCInst #97 ADD32rr
|
|
|
328 ## <MCOperand Reg:23>
|
|
|
329 ## <MCOperand Reg:23>
|
|
|
330 ## <MCOperand Reg:29>>
|
|
|
331 movl %edi, %eax ## <MCInst #1665 MOV32rr
|
|
|
332 ## <MCOperand Reg:19>
|
|
|
333 ## <MCOperand Reg:23>>
|
|
|
334 popq %rbp ## <MCInst #2178 POP64r
|
|
|
335 ## <MCOperand Reg:36>>
|
|
|
336 retq ## <MCInst #2460 RETQ>
|
|
|
337 \end{lstlisting}
|
|
|
338
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 \section{Tail call elimination}
|
|
8
|
340 \label{sec:TCE}
|
|
3
|
341 前述した通り, LLVM の処理は最適化を含め全て pass によって行われるため, pass を選択することで任意の最適化をかけることができる. 独自の pass を作ることも可能であり, pass 作成のチュートリアルは LLVM のドキュメント\cite{LLVM}にも記されている. また, pass の雛形となるクラスも用意されており, 独自の pass を作成する環境は整っていると言える.
|
|
|
342
|
|
17
|
343 最適化機構は本研究にはほとんど関係しないが, CbC では継続の実装に Tail Call Elimination という最適化を用いるため, これは別である.
|
|
3
|
344
|
|
|
345 Tail call elimination の説明の前にまず, tail call について簡単に説明する. tail call は, ある関数の持つ処理の一番最後に位置し, 呼び出し元が戻り値を返す場合は呼び出された関数の戻り値がそのまま呼び出し元の戻り値として返されるような関数呼び出しのことを指す. 具体的には以下のリスト \ref{tailCall} の 関数B, 関数C の呼び出しがそれに当たる. Tail call elimination はこの末尾にある関数呼び出しの最適化を行う. 通常, 関数呼び出しはアセンブルされると call 命令に置き換わるが, tail call elimination ではその代わりに jmp 命令を用いる. その様子を関数Bの呼び出しに注目し, 関数 caller が main 関数から呼ばれるとして図示したものが以下の図\ref{fig:TCE}である. 通常の関数呼び出しの場合, 関数 caller に呼び出された関数 B はその処理を終えると ret 命令により一度関数 caller に戻る. そして再び ret 命令を用いることで main 関数に戻る. Tail call elimination ではこの関数 B から関数 caller に戻る無駄な処理を低減する. 図\ref{fig:TCE}より, 関数 caller が関数 B を呼び出す時の命令が call から jmp にかわり, 関数 B は処理を終えると直接 main 関数に戻っていることがわかる.
|
|
|
346 \begin{lstlisting}[frame=lrbt, label=tailCall, caption={Tail call の例}]
|
|
|
347 void caller(){
|
|
17
|
348 int a = A();
|
|
|
349 if ( a != 10 ){
|
|
3
|
350 B();
|
|
|
351 return;
|
|
17
|
352 }
|
|
|
353 else {
|
|
3
|
354 C();
|
|
|
355 return;
|
|
17
|
356 }
|
|
3
|
357 }
|
|
|
358 \end{lstlisting}
|
|
|
359 \begin{figure}[htpb]
|
|
|
360 \begin{center}
|
|
|
361 \scalebox{0.4}{\includegraphics{fig/TCE.pdf}}
|
|
|
362 \end{center}
|
|
|
363 \caption{Tail call elimination}
|
|
|
364 \label{fig:TCE}
|
|
|
365 \end{figure}
|
|
|
366
|
|
|
367
|
|
|
368 では次に, Tail call elimination によって実際にアセンブリコードがどのように変化するかを確認する. この例では x64 形式のアセンブリ命令セットを使用する. リスト\ref{tailCall}のコードでは分かり辛いので, 図\ref{fig:TCE}の関数をそれぞれリスト\ref{tailCall2}のように再定義する.
|
|
|
369 \begin{lstlisting}[frame=lrbt, label=tailCall2, caption={caller, B, main 関数の定義}]
|
|
|
370 void B(int a, int b, int c, int d){
|
|
|
371 return;
|
|
|
372 }
|
|
|
373
|
|
|
374 void caller(int a, int b, int c){
|
|
|
375 B(a, b, c, 40);
|
|
|
376 return;
|
|
|
377 }
|
|
|
378
|
|
|
379 int main(){
|
|
|
380 caller(10, 20, 30);
|
|
|
381 return 0;
|
|
|
382 }
|
|
|
383 \end{lstlisting}
|
|
|
384
|
|
|
385 これを tail call elimination を行わずにコンパイルしたものが以下のリスト \ref{asmCaller}, tail call elimination を行いコンパイルしたものがリスト \ref{asmCallerTCE} である. なお, tail call elimination の影響を受けるのは関数 caller のみなのでその部分のみ記載する.
|
|
|
386
|
|
|
387 \begin{minipage}[t]{0.5\textwidth}
|
|
|
388 \begin{lstlisting}[frame=lrbt, label=asmCaller, caption={関数 caller (tail call elimination 無し)}]
|
|
|
389 _caller: ## @caller
|
|
|
390 .cfi_startproc
|
|
|
391 ## BB#0: ## %entry
|
|
|
392 pushq %rbp
|
|
|
393 Ltmp7:
|
|
|
394 .cfi_def_cfa_offset 16
|
|
|
395 Ltmp8:
|
|
|
396 .cfi_offset %rbp, -16
|
|
|
397 movq %rsp, %rbp
|
|
|
398 Ltmp9:
|
|
|
399 .cfi_def_cfa_register %rbp
|
|
|
400 movl $40, %ecx
|
|
|
401 callq _B
|
|
|
402 popq %rbp
|
|
|
403 ret
|
|
|
404 .cfi_endproc
|
|
|
405 \end{lstlisting}
|
|
|
406 \end{minipage}
|
|
|
407 \begin{minipage}[t]{0.5\textwidth}
|
|
|
408 \begin{lstlisting}[frame=lrbt, label=asmCallerTCE, caption={関数 caller (tail call elimination 有り)}]
|
|
|
409 _caller: ## @caller
|
|
|
410 .cfi_startproc
|
|
|
411 ## BB#0: ## %entry
|
|
|
412 pushq %rbp
|
|
|
413 Ltmp7:
|
|
|
414 .cfi_def_cfa_offset 16
|
|
|
415 Ltmp8:
|
|
|
416 .cfi_offset %rbp, -16
|
|
|
417 movq %rsp, %rbp
|
|
|
418 Ltmp9:
|
|
|
419 .cfi_def_cfa_register %rbp
|
|
|
420 movl $40, %ecx
|
|
|
421 popq %rbp
|
|
|
422 jmp _B ## TAILCALL
|
|
|
423 .cfi_endproc
|
|
|
424 \end{lstlisting}
|
|
|
425 \end{minipage}
|
|
|
426
|
|
|
427 二つのアセンブリを比較すると, tail call elimination を行った方では call 命令を用いずに jmp 命令で 関数 B に移動していることがわかる. 移動の前に popq を \%rbp に対して行っているのはベースポインタの値を戻しておき, 関数 B から直接 main 関数に戻れるようにするためである. 尚, GCC では tail call elimination を行っていない場合には関数呼び出し前にスタックの値を操作する処理が入っていたが, LLVM ではそれが行われていない. これについて, LLVM では tail call elimination を行っていない場合でも関数呼び出しが末尾にある場合には, その関数に戻ることがないことが自明であることから, 現在のスタックに割り当てられたスタックフレームをそのまま使用するようにしているのだろう.
|
|
|
428
|
|
8
|
429 しかし, Tail call elimination は 全ての tail call に対して行えるわけではなく, 行うためにはいくつかの条件を満たさなければならない. この条件は LLVM Document\cite{LLVM}に記されている. 現在 LLVM では x86/x86-64, PowerPC を tail call elimination のサポート対象としている. 今回の実装では x86/x86-64 を対象としたので, そちらの条件について考える. x86/x86-64 での tail call elimination の要件は以下のようになっている.
|
|
3
|
430
|
|
|
431 \begin{enumerate}
|
|
|
432 \item 呼び出し元と呼び出す関数の呼び出し規約が fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかである.
|
|
|
433 \item 対象となる関数呼び出しが tail call である.
|
|
|
434 \item 最適化のオプションである tailcallopt が有効になっている.
|
|
|
435 \item 対象関数が可変長引数を持たない.
|
|
|
436 \item GOT (Global Offset Table) / PIC (Position Independent Code) を生成する場合, visibility が hidden か protect でなければならない.
|
|
|
437 \end{enumerate}
|
|
|
438
|
|
|
439 これらの条件のうち, コンパイラ側でサポートする必要のある条件について考える. 3つめの条件にある tailcallopt は有効化することで tail call elimination を行うようになるオプションである. しかし tail call elimination を行うためには 関数呼び出しに対して tail フラグを立てる必要がある. これは Tail Call Elimination pass によって付与されるので, CbC コンパイラではこのパスをオプションに関わらず無条件で追加しなければならない. 4つめの条件にある可変長引数について, CbC では可変長引数の機能は data segment を用いてサポートすることになるだろう. data segment は現在 CbC には未実装なので今の段階では可変長引数を持つ code segment を作ることは出来ない. 5つめの条件について, LLVM を用いて PIC を生成する場合には -fPIC というオプションを付加する必要がある. 本論文の主旨から大きく離れるため詳しくは説明しないが, PIC は主に共有ライブラリなどに用いられる, 絶対アドレスにかかわらず正しく実行できるコードの形式, GOT は PIC がアクセスする全グローバル変数のアドレスを格納しているテーブルである. この条件の達成はユーザーに委ねられる.
|
|
|
440
|
|
|
441 これらのことから, code segment に対して tail call elimination を行うために達成しなければならない条件は以下のようになることがわかる.
|
|
|
442 \begin{itemize}
|
|
|
443 \item 呼び出し規約を fastcc, cc 10 (GHC calling convention), cc 11 (HiPE calling convention) のいずれかに指定.
|
|
|
444 \item code segment を tail call にする.
|
|
|
445 \item tailcallopt の有効化.
|
|
|
446 \item 最適化レベルに関わらず Tail call elimination pass を追加.
|
|
|
447 \end{itemize}
|
