|
8
|
1 \chapter{LLVM clang 上での CbC の実装}
|
|
17
|
2 第 \ref{chapter:CbC}, \ref{chapter:LLVM/clang} 章をもとに LLVM, clang への CbC コンパイル機能の実装を行う. コードセグメントの解釈, 軽量継続などいくつかの機能は過去の研究によって実装されたが, 本研究での実装に繋がるのでここでも説明する.
|
|
4
|
3
|
|
|
4 以降に示される LLVM, clang のファイルパスについて, \$(CLANG) を clang のソースコードを展開したディレクトリのパス, \$(LLVM) を LLVM のソースコードを展開したディレクトリのパスとする.
|
|
|
5 \section{code segment}
|
|
|
6 \label{sec:codeSegment}
|
|
|
7 code segment は \_\_code 型の関数のように扱えるよう実装する. また, code segment は 戻り値を返さないので void 型を参考に変更を加えていく. 最初に関数が code segment であることを示す \_\_code 型の追加を行う. これは clang, llvm 別々で行う必要がある. clang 側の作業は \_\_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 の定義も同時に行う.
|
|
|
8
|
|
|
9 \begin{lstlisting}[frame=lrbt,label=token,caption={TokenKinds.def}]
|
|
|
10 :
|
|
|
11 KEYWORD(__func__ , KEYALL)
|
|
|
12 KEYWORD(__objc_yes , KEYALL)
|
|
|
13 KEYWORD(__objc_no , KEYALL)
|
|
|
14
|
|
|
15 #ifndef noCbC // CbC Keywords.
|
|
|
16 KEYWORD(__code , KEYALL)
|
|
|
17 KEYWORD(__return , KEYALL)
|
|
|
18 KEYWORD(__environment , KEYALL)
|
|
|
19 #endif
|
|
|
20 :
|
|
|
21 \end{lstlisting}
|
|
|
22
|
|
|
23 予約語を定義したことで, clang の字句解析器が各予約語を認識できるようになった. しかし, まだ予約語を認識できるようになっただけで \_\_code という型自体は用意されていない. したがって, 次に clang に \_\_code 型を認識させる必要がある.
|
|
|
24
|
|
|
25 clang では型の識別子の管理に TypeSpecType という enum を用いる. この enum の定義は \$(CLANG)/include/clang/Basic/Specifiers.h で行われており, これを以下のように編集した.
|
|
|
26
|
|
|
27 \begin{lstlisting}[frame=lrbt,label=TST,caption={Specifiers.h}]
|
|
|
28 enum TypeSpecifierType {
|
|
|
29 TST_unspecified,
|
|
|
30 TST_void,
|
|
|
31 :
|
|
|
32 #ifndef noCbC
|
|
|
33 TST___code,
|
|
|
34 #endif
|
|
|
35 :
|
|
|
36 \end{lstlisting}
|
|
|
37 これに加えてさらに QualType が用いる Type を作らなければならない. この定義は \$(CLANG)/include/clang/AST/BuiltinTypes.def で行われているので, これを以下のように編集した. ここで使用されているマクロには符号付き整数であることを示す SIGNED\_TYPE や符号無し整数であることを示す UNSIGNED\_TYPE 等があり, それらは BUILTIN\_TYPE マクロを拡張するものである. \_\_code 型は符号無し,有りといった性質を保つ必要はなく, また void 型が BUILTIN\_TYPE を利用していることから \_\_code 型も BUILTIN\_TYPE を使うべきだと判断した.
|
|
|
38
|
|
|
39 \begin{lstlisting}[frame=lrbt,label=clangType,caption={BuiltinTypes.def}]
|
|
|
40 :
|
|
|
41 // 'bool' in C++, '_Bool' in C99
|
|
|
42 UNSIGNED_TYPE(Bool, BoolTy)
|
|
|
43
|
|
|
44 // 'char' for targets where it's unsigned
|
|
|
45 SHARED_SINGLETON_TYPE(UNSIGNED_TYPE(Char_U, CharTy))
|
|
|
46
|
|
|
47 // 'unsigned char', explicitly qualified
|
|
|
48 UNSIGNED_TYPE(UChar, UnsignedCharTy)
|
|
|
49
|
|
|
50 #ifndef noCbC
|
|
|
51 BUILTIN_TYPE(__Code, __CodeTy)
|
|
|
52 #endif
|
|
|
53 :
|
|
|
54 \end{lstlisting}
|
|
|
55
|
|
|
56 これで clang が \_\_code 型を扱えるようになり, \_\_code 型の関数, 即ち code segment を解析する準備が整った. よって次に \_\_code 型を解析できるよう clang に変更を加える. clang では型の構文解析は Parser クラスの ParseDeclarationSpecifiers 関数で行われる. この関数のもつ巨大な switch 文に kw\_\_\_code が来た時の処理を加えてやれば良い. 具体的には switch 文内に以下のように記述を加えた. また, この関数の定義は \$(CLANG)/lib/Parse/ParseDecl.cpp で行われている.
|
|
|
57
|
|
|
58 \begin{lstlisting}[frame=lrbt,label=parse__Code,caption={\_\_code の parse}]
|
|
|
59 case tok::kw___code: {
|
|
|
60 LangOptions* LOP;
|
|
|
61 LOP = const_cast<LangOptions*>(&getLangOpts());
|
|
|
62 LOP->HasCodeSegment = 1;
|
|
|
63 isInvalid = DS.SetTypeSpecType(DeclSpec::TST___code, Loc, PrevSpec, DiagID);
|
|
|
64 break;
|
|
|
65 }
|
|
|
66 \end{lstlisting}
|
|
|
67
|
|
|
68 重要なのは 5行目で, ここで \_\_code 型が DeclSpec に登録される. DeclSpec は 型の識別子を持つためのクラスであり, 後に QualType に変換される.
|
|
|
69
|
|
|
70 その他の処理について, 最初にある LangOptions はコンパイル時のオプションのうち, プログラミング言語に関わるオプションを管理するクラスであり, このオプションの値を変更しているのはコード内に code segment が存在することを LLVM に伝え, tailcallopt を有効化するためである. LangOptions が管理するオプションは \$(CLANG)/include/clang/Basic/ LangOptions.def で定義される. これを以下のリスト \ref{langOpt} のように変更して HasCodeSegment というオプションを追加した. LANGOPT マクロの引数は第一引数から順にオプション名, 必要ビット数, デフォルトの値, オプションの説明 となっている.
|
|
|
71 \begin{lstlisting}[frame=lrbt,label=langOpt,caption={LangOptions の追加}]
|
|
|
72 :
|
|
|
73 LANGOPT(ApplePragmaPack, 1, 0, "Apple gcc-compatible #pragma pack handling")
|
|
|
74
|
|
|
75 BENIGN_LANGOPT(RetainCommentsFromSystemHeaders, 1, 0, "retain documentation comments from system headers in the AST")
|
|
|
76
|
|
|
77 #ifndef noCbC
|
|
|
78 LANGOPT(HasCodeSegment , 1, 0, "CbC")
|
|
|
79 #endif
|
|
|
80 :
|
|
|
81 \end{lstlisting}
|
|
|
82
|
|
|
83 ここまでの変更により clang が正しく \_\_code を解釈し, code segment を AST に変換できるようになる. 次に LLVM 側の変更を行う.
|
|
|
84
|
|
|
85 LLVM でも clang と同様に \_\_code 型の追加を行うが, 追加を行うと言っても LLVM IR の持つ type の拡張を行うわけではなくコンパイル時に内部で code segment であることを知るためだけに型の定義を行う. そのため LLVM IR への変更は一切なく, LLVM IR として出力した場合には型は void となる. LLVM では型の情報は Type というクラスで管理しており, Type の定義は \$(LLVM)/lib/IR/LLVMContextImpl.h で行う. これに加えて TypeID の登録も行う必要があり, これは \$(LLVM)/include/llvm/IR/Type.h で定義されている. それぞれ, 以下のように編集した.
|
|
|
86
|
|
|
87 さらに, \_\_CodeTy は VoidTy としても扱いたいため, 型判別に用いられる isVoidTy 関数の編集も行った. この関数は Type が VoidTy の場合に真を返す関数である. この関数を Type が \_\_CodeTy の場合にも真を返すようにした. ここで変更されたは if 文の条件文のみなので, ソースコードの記載はしない.
|
|
|
88
|
|
|
89 \begin{lstlisting}[frame=lrbt,label=LLVMType,caption={LLVMContextImpl.h}]
|
|
|
90 :
|
|
|
91 // Basic type instances.
|
|
|
92 Type VoidTy, LabelTy, HalfTy, FloatTy, DoubleTy, MetadataTy;
|
|
|
93 Type X86_FP80Ty, FP128Ty, PPC_FP128Ty, X86_MMXTy;
|
|
|
94 #ifndef noCbC
|
|
|
95 Type __CodeTy;
|
|
|
96 #endif
|
|
|
97 :
|
|
|
98 \end{lstlisting}
|
|
|
99 \begin{lstlisting}[frame=lrbt,label=LLVMType,caption={Type.h}]
|
|
|
100 enum TypeID {
|
|
|
101 :
|
|
|
102 StructTyID, ///< 12: Structures
|
|
|
103 ArrayTyID, ///< 13: Arrays
|
|
|
104 PointerTyID, ///< 14: Pointers
|
|
|
105 VectorTyID ///< 15: SIMD 'packed' format, or other vector type
|
|
|
106 #ifndef noCbC
|
|
|
107 ,__CodeTyID /// for CbC
|
|
|
108 #endif
|
|
|
109 :
|
|
|
110 \end{lstlisting}
|
|
|
111
|
|
|
112 これらの編集により, LLVM 側でも code segment を認識できるようになった.
|
|
|
113
|
|
1
|
114 \section{軽量継続}
|
|
9
|
115 CbC で軽量継続は goto に code segment 名を添えることで行う. この新しい goto syntax を追加する. 継続のための goto syntax は, goto の後に関数呼び出しと同じ構文が来る形になる. したがって, goto の構文解析を行う際にこの構文も解析できるように変更を加える必要がある. clang が goto 文の構文解析を行っているのは, Parser クラスの ParseStatementOrDeclarationAfterAttributes 関数であり, この関数は \$(clang)/lib/Parse/ParseStmt.cpp で定義されている. この関数内にも switch 文があり, この中の kw\_goto が来た時の処理に手を加える. 具体的には以下のように変更した.
|
|
4
|
116
|
|
|
117
|
|
|
118 \begin{lstlisting}[frame=lrbt,label=ParseStmt,caption={goto 文の構文解析}]
|
|
|
119 :
|
|
|
120 case tok::kw_goto: // C99 6.8.6.1: goto-statement
|
|
|
121 #ifndef noCbC
|
|
|
122 if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) && // C: 'goto' identifier ';'
|
|
|
123 NextToken().isNot(tok::star)) { // C: 'goto' '*' expression ';'
|
|
|
124 SemiError = "goto code segment";
|
|
|
125 return ParseCbCGotoStatement(Attrs, Stmts); // CbC: goto codesegment statement
|
|
|
126 }
|
|
|
127 #endif
|
|
|
128 Res = ParseGotoStatement();
|
|
|
129 SemiError = "goto";
|
|
|
130 break;
|
|
|
131 :
|
|
|
132 \end{lstlisting}
|
|
|
133
|
|
|
134 ifndef, endif マクロで囲まれた部分が追加したコードである. 初めの if 文は, token の先読みを行い, この goto が C の goto 文のためのものなのか, そうでないのかを判断している. C のための goto でないと判断した場合のみ ParseCbCGotoStatement 関数に入り, 継続構文の構文解析を行う. ParseCbCGotoStatement 関数は独自に定義した関数で, その内容を以下のリスト\ref{ParseCbCGotoStmt} に示す.
|
|
|
135
|
|
|
136 \begin{lstlisting}[frame=lrbt,label=ParseCbCGotoStmt,caption={ParseCbCGotoStatement}]
|
|
|
137 StmtResult Parser::ParseCbCGotoStatement(ParsedAttributesWithRange &Attrs,StmtVector &Stmts) {
|
|
|
138 assert(Tok.is(tok::kw_goto) && "Not a goto stmt!");
|
|
|
139 ParseScope CompoundScope(this, Scope::DeclScope);
|
|
|
140 StmtVector CompoundedStmts;
|
|
|
141
|
|
|
142 SourceLocation gotoLoc = ConsumeToken(); // eat the 'goto'.
|
|
|
143 StmtResult gotoRes;
|
|
|
144 Token TokAfterGoto = Tok;
|
|
|
145 Stmtsp = &Stmts;
|
|
|
146
|
|
|
147 gotoRes = ParseStatementOrDeclaration(Stmts, false);
|
|
|
148 if (gotoRes.get() == NULL)
|
|
|
149 return StmtError();
|
|
|
150 else if (gotoRes.get()->getStmtClass() != Stmt::CallExprClass) { // if it is not function call
|
|
|
151 Diag(TokAfterGoto, diag::err_expected_ident_or_cs);
|
|
|
152 return StmtError();
|
|
|
153 }
|
|
|
154
|
|
|
155 assert((Attrs.empty() || gotoRes.isInvalid() || gotoRes.isUsable()) &&
|
|
|
156 "attributes on empty statement");
|
|
|
157 if (!(Attrs.empty() || gotoRes.isInvalid()))
|
|
|
158 gotoRes = Actions.ProcessStmtAttributes(gotoRes.get(), Attrs.getList(), Attrs.Range);
|
|
|
159 if (gotoRes.isUsable())
|
|
|
160 CompoundedStmts.push_back(gotoRes.release());
|
|
|
161
|
|
|
162 // add return; after goto codesegment();
|
|
|
163 if (Actions.getCurFunctionDecl()->getResultType().getTypePtr()->is__CodeType()) {
|
|
|
164 ExprResult retExpr;
|
|
|
165 StmtResult retRes;
|
|
|
166 retRes = Actions.ActOnReturnStmt(gotoLoc, retExpr.take());
|
|
|
167 if (retRes.isUsable())
|
|
|
168 CompoundedStmts.push_back(retRes.release());
|
|
|
169 }
|
|
|
170 return Actions.ActOnCompoundStmt(gotoLoc, Tok.getLocation(), CompoundedStmts, false);
|
|
|
171 }
|
|
|
172 \end{lstlisting}
|
|
|
173
|
|
|
174 この関数では, goto の後の構文を解析して関数呼び出しの Stmt を生成する. その後, tail call elimination の条件を満たすために直後に return statement の生成も行う. 関数呼び出しの解析部分は ParseStatementOrDeclaration 関数に任せ, goto の後に関数呼び出しの構文がきていない場合にはエラーを出力する.
|
|
|
175
|
|
|
176 \section{Tail call elimination pass の条件の達成}
|
|
|
177 \label{sec:TCEreq}
|
|
|
178 tail call elimination を強制するためにその条件を満たす処理の追加を行う. \ref{sec:TCE}節で述べた条件のうち, code segment を tail call にする (呼び出した直後に return 文がくる) という条件は前節で達成した. したがって残りの条件は, 呼び出し規約を fastcc, cc 10, cc 11 のいずれかにする, tailcallopt の有効化, tail call elimination pass の追加の三つである.
|
|
|
179
|
|
|
180 まず初めに, 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 以外の関数に触れないようにするためにこのような引数を設けた.
|
|
|
181
|
|
|
182 \begin{lstlisting}[frame=lrbt,label=PassManager,caption={tail call elimnation pass の追加}]
|
|
|
183 :
|
|
|
184 if (OptLevel == 0) {
|
|
|
185 :
|
|
|
186 #ifndef noCbC
|
|
|
187 MPM.add(createTailCallEliminationPass(true)); // Eliminate tail calls
|
|
|
188 #endif
|
|
|
189 :
|
|
|
190 }
|
|
|
191 :
|
|
|
192 #ifndef noCbC
|
|
|
193 MPM.add(createTailCallEliminationPass(false)); // Eliminate tail calls
|
|
|
194 #else
|
|
|
195 MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
|
|
|
196 #endif
|
|
|
197 :
|
|
|
198 \end{lstlisting}
|
|
|
199 これで 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 を持つ場合には最適化レベルに関わらず追加するように変更した.
|
|
|
200
|
|
|
201 次に, 呼び出し規約の問題を解消する. 条件を満たす呼び出し規約は fastcc, cc 10, cc 11 の三種類があり, それぞれ簡単に説明すると以下の様な特徴がある.
|
|
|
202
|
|
|
203 \begin{description}
|
|
|
204 \item[fastcc]\mbox{}\\
|
|
|
205 この規約を指定すると, 情報をレジスタを用いて渡す等して, 可能な限り高速な呼び出しを試みるようになる. この呼び出し規約は可変引数をサポートせず, 呼び出される関数のプロトタイプと呼び出される関数が正確に一致する必要がある.
|
|
|
206 \item[cc 10]\mbox{}\\
|
|
|
207 Glasgow Haskell Compiler のために実装された呼び出し規約. X86 でのみサポートされており, 引数に関するいくつかの制限をもつ. レジスタ内の値を全て渡し, 呼び出された関数はレジスタの値を保存できない. この呼び出し規約は関数型プログラミング言語を実装する際に使用される register pinning という技術の代わりとして特定の状況でしか使用してはならない.
|
|
|
208 \item[cc 11]\mbox{}\\
|
|
|
209 High-Performance Erlang のために実装された呼び出し規約. 通常の C の呼び出し規約以上に引数を渡すためにレジスタを利用する. X86 でのみサポートされており, cc 10 同様に register pinning を用いる.
|
|
|
210 \end{description}
|
|
|
211
|
|
|
212 これらのうち, cc 10, cc 11 は関数型プログラミング言語の実装に用いられる register pinning という技術の代わりに用いられ, これを積極的に利用することは好ましくないとある. 対して fastcc には, 可変引数をサポートしない, プロトタイプは正確でなければならないといった条件があるが, 前者は \ref{sec:TCE}節で説明したとおり tail call elimination の条件に含まれており, 後者は特別厳しい条件ではない上, プロトタイプの不正な関数は clang がエラーを出してくれるので問題ないだろう. よって code segment の呼び出し規約には fastcc を用いることにした.
|
|
|
213
|
|
|
214 fastcc の追加は clang が関数情報の設定処理を行っている箇所で行った. 関数情報は CGFunctionInfo というクラスを用いて管理される. 関数情報の設定は \$(CLANG)/lib/CodeGen /CGCall.cpp 内の arrangeLLVMFunctionInfo という関数で行われる. この関数内に以下のリスト\ref{CC} に示されるコードを加えた. 5行目が fastcc を設定している箇所である. 関数が \_\_code型の場合で, かつ可変長引数を持たない場合に呼び出し規約を fastcc に設定する. 可変長引数に関する条件を加えているのは, 可変長引数が使用されている場合には呼び出し規約を変えず tail call elimination を行わないことで通常の関数呼び出しを生成するためである.
|
|
|
215
|
|
|
216 \begin{lstlisting}[frame=lrbt,label=CC,caption={fastcc の追加}]
|
|
|
217 :
|
|
|
218 #ifndef noCbC
|
|
|
219 if(resultType.getTypePtr()->is__CodeType()){
|
|
|
220 if(!required.allowsOptionalArgs())
|
|
|
221 CC = llvm::CallingConv::Fast;
|
|
|
222 }
|
|
|
223 #endif
|
|
|
224 :
|
|
|
225 \end{lstlisting}
|
|
|
226
|
|
|
227 最後に, tailcallopt を有効化を行う. clang と LLVM は指定されたオプションを管理するクラスを別々に持っており, clang はユーザーに指定されたオプションを LLVM に引き継ぐ処理を持つ. その処理が行われているのが \$(CLANG)/lib/CodeGen/BackendUtil.cpp 内の CreateTargetMachine 関数である. この関数のオプションの引き継ぎを行っている箇所を以下のリスト\ref{option}のように変更する. 6 行目が tailcallopt を有効にしている箇所である. tailcallopt は内部では GuaranteedTailCallOpt となっており, code segment を持つ場合にこれを有効化する. 右辺の HasCodeSegment が code segment を持つか否かを表し, これは予約語 \_\_code を解析する際に有効化される. また, 5 行目からわかるように LLVM 側でも HasCodeSegment というオプションを追加している. これは \ref{sec:TCEreq} 節で述べた codeGenPrepare pass を追加する際に利用する.
|
|
|
228
|
|
|
229 \begin{lstlisting}[frame=lrbt,label=option,caption={オプションの引き継ぎ}]
|
|
|
230 :
|
|
|
231 Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
|
|
|
232 Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
|
|
|
233 #ifndef noCbC
|
|
|
234 Options.HasCodeSegment = LangOpts.HasCodeSegment;
|
|
|
235 Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
|
|
|
236 #endif
|
|
|
237 :
|
|
|
238 \end{lstlisting}
|
|
|
239
|
|
|
240 LLVM でのオプションの追加方法についてもここで述べておく. LLVM のオプションは TargetOptions というクラスが管理しており, その定義は \$(LLVM)/include/llvm/Target/ TargetOptions.h で行われている. こちらはマクロは使っておらずビットフィールドを用いて定義されている. TargetOptions クラスの中で変数を宣言するだけで追加できるので, コードは省略する.
|
|
|
241
|
|
1
|
242 \section{プロトタイプ宣言の自動化}
|
|
4
|
243 プロトタイプ宣言の自動化は本研究で追加された機能である. CbC の code segment の処理単位は小さく, そのままでは大量のプロトタイプ宣言を書く必要があり, 好ましくない. また, tail call elimination 強制のために付加した fastcc は正確にプロトタイプ宣言を書くことを要求する. つまりプロトタイプ宣言を自動的に行うようにすることで fastcc の条件を安定して満たすことができ, さらにプログラマは大量のプロトタイプ宣言を書く必要がなくなるのである.
|
|
|
244
|
|
|
245 プロトタイプ宣言の自動化は, パーサーが code segment への継続の解析を行った際にプロトタイプ宣言の有無を確認し, 存在しない場合に継続先の code segment のプロトタイプ宣言を生成するというようにして行う. リスト \ref{checkProto} はプロトタイプ宣言の有無を確認する関数である. この関数に code segment 名を渡すとプロトタイプ宣言の有無を返す. LookupParsedName で指定された識別子が解析されているかどうかを知ることが出来るのでそれを用いて有無の判別を行う.
|
|
|
246
|
|
|
247 \begin{lstlisting}[frame=lrbt,label=checkProto,caption={プロトタイプ宣言の有無を確認する関数}]
|
|
|
248 bool Parser::NeedPrototypeDeclaration(Token IITok){
|
|
|
249 LookupResult LR(Actions, IITok.getIdentifierInfo(), IITok.getLocation(), Actions.LookupOrdinaryName);
|
|
|
250 CXXScopeSpec SS;
|
|
|
251 Actions.LookupParsedName(LR, getCurScope(), &SS, !(Actions.getCurMethodDecl()));
|
|
|
252
|
|
|
253 return (LR.getResultKind() == LookupResult::NotFound);
|
|
|
254 }
|
|
|
255 \end{lstlisting}
|
|
|
256
|
|
|
257 プロトタイプ宣言の有無を確認し, 存在しない場合には以下のリスト \ref{createDecl} に示した CreatePrototypeDeclaration 関数を用いて対象となる code segment のプロトタイプ宣言を生成する. この関数では対象 code segment の定義を探しだし, そこからプロトタイプ宣言部分を抜き出す. 定義を探す処理は \ref{searchDecl} に示す SearchCodeSegmentDeclaration 関数で行う. プロトタイプ宣言の自動生成を行う際まず scope を top レベルに移さなければならない. 有無を確認した時点では scope は関数の内部であるためこのまま生成すると不具合が生じるためである. リスト \ref{createDecl} の 10 行目までがその処理である. top の scope が親を持たないことを利用して top に変更している.
|
|
|
258
|
|
|
259 その次のブロックでは Token を保存している. この関数の処理によって code segment 名等の token が解析されたという扱いになってしまうが, プロトタイプ宣言の生成が済んだあとは呼び出しの処理に戻る必要がある. そのため token を保存しておき解析を再度行う際に利用できるようにしているのである.
|
|
|
260
|
|
|
261 その後, SearchCodeSegmentDeclaration 関数を使用して対象 code segment の定義を探すが, SkipAnyUntil という関数を用いる. この関数は指定された token が来るまで token を飛ばすというものである. このままこの関数を使用すると現在のバッファが破壊されてしまい, 以後正しく解析を行えなくなってしまう. それを回避するために, 現在のファイルを新しいものとして別に読み込みを行い, この処理に入る. これにより現在のバッファを破壊せずに code segment の探索が可能になる.
|
|
|
262
|
|
|
263 対象 code segment の定義を見つけたらそれを元にプロトタイプ宣言を行う. その後前のファイルに戻り, 保存した token を元に戻すことで正しく元の解析位置に戻ることが出来るのである.
|
|
|
264
|
|
|
265 \begin{lstlisting}[frame=lrbt,label=createDecl,caption={プロトタイプ宣言の生成を行う関数}]
|
|
|
266 void Parser::CreatePrototypeDeclaration(){
|
|
|
267 // move to the top level scope
|
|
|
268 Scope *SavedScope = getCurScope();
|
|
|
269 DeclContext *SavedContext = Actions.CurContext;
|
|
|
270 sema::FunctionScopeInfo *SavedFSI = Actions.FunctionScopes.pop_back_val();
|
|
|
271 Actions.CurContext = static_cast<DeclContext *>(Actions.Context.getTranslationUnitDecl());
|
|
|
272 Scope *TopScope = getCurScope();
|
|
|
273 while(TopScope->getParent() != NULL)
|
|
|
274 TopScope = TopScope->getParent();
|
|
|
275 Actions.CurScope = TopScope;
|
|
|
276
|
|
|
277 Token Next = NextToken();
|
|
|
278 Token CachedTokens[3] = {Next, PP.LookAhead(1)};
|
|
|
279 Token SavedToken = Tok;
|
|
|
280 Token IITok = Tok.is(tok::identifier) ? Tok : Next;
|
|
|
281 PP.ClearCache();
|
|
|
282 PP.ProtoParsing = true;
|
|
|
283 ProtoParsing = true;
|
|
|
284
|
|
|
285 const DirectoryLookup *CurDir = nullptr;
|
|
|
286 FileID FID = PP.getSourceManager().createFileID(PP.getCurrentFileLexer()->getFileEntry(), IITok.getLocation(), SrcMgr::C_User);
|
|
|
287 PP.EnterSourceFile(FID,CurDir,IITok.getLocation());
|
|
|
288 ConsumeToken();
|
|
|
289
|
|
|
290 if(SearchCodeSegmentDeclaration(IITok.getIdentifierInfo()->getName().str())){
|
|
|
291 DeclGroupPtrTy ProtoDecl;
|
|
|
292 ParseTopLevelDecl(ProtoDecl);
|
|
|
293 // add declaration to AST.
|
|
|
294 if(ProtoDecl)
|
|
|
295 (&Actions.getASTConsumer())->HandleTopLevelDecl(ProtoDecl.get());
|
|
|
296 // File Closing
|
|
|
297 Token T;
|
|
|
298 PP.HandleEndOfFile(T, false);
|
|
|
299
|
|
|
300 // recover tokens.
|
|
|
301 Tok = SavedToken;
|
|
|
302 PP.RestoreTokens(CachedTokens, 2);
|
|
|
303
|
|
|
304 }
|
|
|
305 else {
|
|
|
306 // recover tokens.
|
|
|
307 CachedTokens[2] = Tok;
|
|
|
308 Tok = SavedToken;
|
|
|
309 PP.RestoreTokens(CachedTokens, 3);
|
|
|
310 }
|
|
|
311
|
|
|
312 // move to the previous scope.
|
|
|
313 Actions.CurScope = SavedScope;
|
|
|
314 Actions.CurContext = SavedContext;
|
|
|
315 Actions.FunctionScopes.push_back(SavedFSI);
|
|
|
316
|
|
|
317 ProtoParsing = false;
|
|
|
318 PP.ProtoParsing = false;
|
|
|
319 }
|
|
|
320 \end{lstlisting}
|
|
|
321
|
|
|
322 \begin{lstlisting}[frame=lrbt,label=searchDecl,caption={code segment を探す関数}]
|
|
|
323 bool Parser::SearchCodeSegmentDeclaration(std::string Name){
|
|
|
324 while(SkipAnyUntil(tok::kw___code, StopBeforeMatch)){
|
|
|
325 if(NextToken().is(tok::identifier) && NextToken().getIdentifierInfo()->getName().str() == Name)
|
|
|
326 return true;
|
|
|
327 ConsumeToken();
|
|
|
328 }
|
|
|
329 return false;
|
|
|
330 }
|
|
|
331 \end{lstlisting}
|
|
|
332
|
|
1
|
333 \section{フレームポインタ操作最適化}
|
|
17
|
334 フレームポインタ操作の最適化は omit leaf frame pointer を強制することで行う. この最適化は関数呼び出しの際に行われるフレームポインタ操作に関わる最適化である. 通常関数呼び出しを行う際にはフレームポインタの値をスタックに積み, return 直前に戻すという作業を行う. omit leaf frame pointer はこの操作を leaf function を呼び出す際に行わないようにする最適化である.
|
|
|
335 leaf function とはコールツリーの終端の位置する関数のことを指し, この関数が関数を呼び出さないことを意味する. 軽量継続を続ける code segment は何もせずとも leaf function の条件を満たしているので内部で有効化するだけで良い.
|
|
|
336
|
|
|
337 以下のリスト \ref{loptno}, \ref{lopt} はどちらもリスト \ref{leaf} をコンパイルして得られるアセンブリコードから関数 caller の部分を抜き出したものであり, 前者が omit leaf frame pointer 無し, 後者が omit leaf frame pointer ありのコードである. push, pop 命令によるフレームポインタの操作がリスト \ref{lopt} ではなくなっていることがわかる.
|
|
4
|
338
|
|
17
|
339 \begin{lstlisting}[frame=lrbt, label=leaf, caption={関数 caller}]
|
|
|
340 void caller(int a, int b, int c){
|
|
|
341 B(a, b, c, 40);
|
|
|
342 return;
|
|
|
343 }
|
|
|
344 \end{lstlisting}
|
|
|
345 \begin{lstlisting}[frame=lrbt, label=loptno, caption={関数 caller (omit leaf frame pointer 無し)}]
|
|
|
346 _caller: ## @caller
|
|
|
347 .cfi_startproc
|
|
|
348 ## BB#0:
|
|
|
349 pushq %rbp
|
|
|
350 Ltmp0:
|
|
|
351 .cfi_def_cfa_offset 16
|
|
|
352 Ltmp1:
|
|
|
353 .cfi_offset %rbp, -16
|
|
|
354 movq %rsp, %rbp
|
|
|
355 Ltmp2:
|
|
|
356 .cfi_def_cfa_register %rbp
|
|
|
357 movl %edi, -4(%rbp)
|
|
|
358 movl %esi, -8(%rbp)
|
|
|
359 movl -4(%rbp), %esi
|
|
|
360 addl -8(%rbp), %esi
|
|
|
361 movl %esi, %eax
|
|
|
362 popq %rbp
|
|
|
363 retq
|
|
|
364 .cfi_endproc
|
|
|
365 \end{lstlisting}
|
|
|
366 \begin{lstlisting}[frame=lrbt, label=lopt, caption={関数 caller (omit leaf frame pointer 有り)}]
|
|
|
367 _caller: ## @caller
|
|
|
368 .cfi_startproc
|
|
|
369 ## BB#0:
|
|
|
370 movl %edi, -4(%rbp)
|
|
|
371 movl %esi, -8(%rbp)
|
|
|
372 movl -4(%rbp), %esi
|
|
|
373 addl -8(%rbp), %esi
|
|
|
374 movl %esi, %eax
|
|
|
375 retq
|
|
|
376 .cfi_endproc
|
|
|
377 \end{lstlisting}
|
|
|
378
|
|
4
|
379 omit leaf frame pointer は clang 内部では CodeGenOpts.OmitLeafFramePointer として表現されている. clang は CodeGen で LLVM IR の function を生成する際にこのフラグが立っているかどうかを確認し, 立っている場合には関数の no-frame-pointer-elim という attribute を false にする. それにより最適化が当該関数に作用するようになる. この, LLVM IR function への attribute 設定を行っているのは \$(CLANG)/lib/CodeGen/CGCall.cpp である. ここをリスト \ref{olfp} のように変更した. 通常は OmitLeafFramePointer のみを確認する部分を HasCodeSegment によって code segment の有無も確認するように変更している. これにより, code segment を含むコードのコンパイル, 即ち CbC のコードのコンパイルの際には自動的に omit leaf frame pointer が有効化されるようになった.
|
|
|
380
|
|
|
381 \begin{lstlisting}[frame=lrbt,label=olfp,caption={omit leaf frame pointer 有効化}]
|
|
|
382 } else if (CodeGenOpts.OmitLeafFramePointer || LangOpts.HasCodeSegment) {
|
|
|
383 FuncAttrs.addAttribute("no-frame-pointer-elim", "false");
|
|
|
384 FuncAttrs.addAttribute("no-frame-pointer-elim-non-leaf");
|
|
|
385 \end{lstlisting}
|
