@@ -209,7 +210,7 @@ AST - ソースコードの解析結果を保持したツリー. 今回の実装ではパーサーが AST を生成する部分に手を加えている. + ソースコードの解析結果を保持したツリー. LLVM IR @@ -219,8 +220,7 @@ SelectionDAG - SelectionDAG は非巡回有向グラフで, 各ノードが命令とその対象となるオペランドを持つ. illegal なものと leagal な物があり, 前者の段階ではターゲットがサポートしていない型や命令が残っている.
- 今回の実装ではここで行われる最適化の一つである Tail Call Elimination を code segment に対して強制するように変更を加えた. + 非巡回有向グラフで, 各ノードが命令とその対象となるオペランドを持つ. Machine Code @@ -230,7 +230,7 @@ MC Layer - 正確には中間表現ではなく, コード生成を抽象化して扱えるようにした層である. MC Layer を用いることで Machine Code からアセンブリ言語への変換やオブジェクトファイルの生成といった異なった処理を同一の API を用いて行うことが可能になる. + 正確には中間表現ではなく, コード生成を抽象化して扱えるようにした層.
@@ -252,13 +252,12 @@

 int main(){
-  int a, b;
-  a = 1;
-  b = func(a,2);
-  return b;
+  int a;
+  a = func(1,2);
+  return a;
 }

CbC の文に対してこの木が正しく生成されるようにソースコードに手を加えていく.

@@ -277,6 +276,11 @@

__code 型の追加

+ +

__code 型の追加

LLVM 側では型情報を管理するクラスである Type と ID の作成が必要.
以下は clang が __code をパースする箇所.

@@ -304,6 +307,11 @@

goto syntax の追加

+ +

goto syntax の追加

ここでは関数呼び出しを生成しておき, 後で Tail Call Elimination によって継続に直す.
以下は goto をパースする箇所. C の goto 出ない場合に継続の構文と判断する.

@@ -365,6 +372,11 @@

clang/LLVM 間の __code 型の変換

+ +

clang/LLVM 間の __code 型の変換

以下が実際に変換を行っている箇所. ABIArgInfo の種類に応じて型の変換をしている.
Ignore の時 void 型であるので, この時に __code 型かどうかのチェックを加えた.

@@ -395,38 +406,18 @@

code segment の継続の実装

Tail Call Elimination という最適化によって実現する. -
この最適化により, code segment への継続が jmp 命令で行われるようになる. -
以下の図は, 関数B の呼び出しに対して Tail Call Elimination が行われた例を示している. -

- - - -

-void B() {
-    :
-  return;
-}
-
-void caller() {
-    :
-  return;
-}
-
-int main() {
-    :
-  caller();
-    :
-}
-

code segment に対してこれが強制されるように実装する. +
この最適化は関数呼び出しに対して行われ, これにより関数への移動が call 命令でなく jmp 命令で行われるようになる. +
これを code segment に対して強制することで継続が実装される.

Tail Call Elimination

Tail Call Elimination の強制

+ +

Tail Call Elimination の強制

LLVM の入力となる中間言語, LLVM IR には大域 jmp に相当する命令がない.
しかし LLVM IR は関数呼び出しにフラグを付けることができるので, それを利用することで code segment の呼び出しだという情報を残すことが可能.

以下の条件を満たす必要がある

呼び出し元と呼び出す関数の呼び出し規約を fastcc, cc 10, cc 11 のいずれかにする.
最適化のオプションである tailcallopt が有効になっている.

- -

tail call elimination pass の追加

- - - - - - - -

tail call elimination pass 最適化のレベルに関わらず追加. -
最適化のレベルが 1 以下の時には code segment 以外に触れないようにする. -
tail call elimination pass の他に, SROA pass と codeGenPrepare pass を追加する必要がある. -
SROA pass はメモリ参照を減らすスカラー置換を行う pass. tail call elimination の条件には記されていないが, この pass により alloca を減らす必要がある. -
codeGenPrepare pass は名前の通りコード生成の準備を行う pass でこの pass を通さなければ, if 文使用時に code segment 呼び出し直後に配置した return文が消えてしまう. -

-       :
-  if (OptLevel == 0) {
-       :
-#ifndef noCbC
-    MPM.add(createTailCallEliminationPass(true));
-#endif
-       :
-  }
-       :
-#ifndef noCbC
-  MPM.add(createTailCallEliminationPass(false));
-#else
-  MPM.add(createTailCallEliminationPass());
-#endif
-       :
-

+
+

それぞれ以下のようにして条件を満たす

最適化のレベルにかかわらず taill call elimintaion pass の追加. +
呼び出し規約を fastcc に変更. +
code segment が含まれる際に tailcallopt を自動で有効化. +

呼び出し規約の変更

- - - - -

条件を満たす呼び出し規約は fastcc, cc10, cc11 の三種類があるが, cc10, cc11 は関数型プログラミング言語の実装上で特定の状況でのみ使用されることが想定されている. -
- よって fastcc を用いる. -
-
fastcc は情報のレジスタ渡しなどを行うようになる呼び出し規約. -
fastcc を使用するのにも, 関数のプロトタイプを正確に記述する, 可変引数を使用しないという条件がある. -
これらの条件を満たしていない code segment に対しては警告を行う. -
以下のコードが fastcc を付与している部分. -

-       :
-#ifndef noCbC
-  if(resultType.getTypePtr()->is__CodeType()){
-    if(!required.allowsOptionalArgs())
-      CC = llvm::CallingConv::Fast;
-  }
-#endif
-       :
-

- -

tailcallopt の有効化

- - - - -

tailcallopt は内部では GuaranteedTailCallOpt なのでこれを有効化. -
Options は LLVM のクラスで LangOpts, CodeGenOpts は clang のクラス. -
HasCodeSegment は __code 解析時に有効化される code segment の有無を示すフラグ. -

-       :
-  Options.PositionIndependentExecutable = LangOpts.PIELevel != 0;
-  Options.EnableSegmentedStacks = CodeGenOpts.EnableSegmentedStacks;
-#ifndef noCbC
-  Options.HasCodeSegment = LangOpts.HasCodeSegment;
-  Options.GuaranteedTailCallOpt = LangOpts.HasCodeSegment;
-#endif
-       :
-

環境付き継続

@@ -546,7 +450,6 @@

__return, __environment という二つのキーワードを利用して実現.

以下のコードのように使用し, この場合 0 でなく 1 が返る. -