Implementation of CbC compiler on LLVM/clang 3.5
-Kaito Tokumori 27 Feb 2014
-Teacher : Shinji Kono
- Introduction of CbC
--
-
- CbC is programming language. -
- CbC stands for Continuation based C. -
- For pararell tasks. -
- For state machine. -
- For meta computation. -
CbC compilers
--
-
- Micro-C -
- GCC -
- LLVM/clang <= New!! -
LLVM/clang??
--
What??
--
-
- LLVM is compiler framework. -
- clang is C/C++/Obj-C compiler frontend. -
Why??
--
-
- Apple supported. -
- OS X default compiler. -
- LLVM IR (Intermidiate Representation). -
Basic strategy of implementation
--
-
- A code segment is implemented by normal function. -
- Transition is implemented by forced tail call. -
- Goto with environment is implemented by setjmp/longjmp. -
- Do not modify intermidiate code. -
Problems
--
-
- Code segment go-to moves between function. -
- LLVM IR jmp instruction is limited in a function. -
- LLVM IR can't express code segment jump... -
-
-
-
- But LLVM has tail call elimination,
- so there is a way to generate unlimited jmp instruction in LLVM.
-
Solution
-define fastcc void @factorial(i32 %x) #0 {
-entry:
- tail call fastcc void @factorial0(i32 1, i32 %x)
- ret void
-}
- -
-
- LLVM IR has call flag. -
- Tail and fastcc flag are enable to tail call elimination! -
We can implement CbC compiler on LLVM!!
-
Structure of LLVM/clang
-
Implementation on parser
--
-
- Code segment type -
- Goto syntax -
Implementation on parser
--
-
-
- Include setjmp.h always. -
- Generate C struct for saving environment. -
- Insert setjmp statement. -
- Generate longjmp code segment as return. -
Implementation on code generator
--
-
-
- Enable to tailcallopt LangOption. -
- Add a return statement after code sgment call. -
- Add fastcc calling convention. -
- Enable to TailCallElim pass. -
Compiling result
-
- __code factorial(int x)
-{
- goto factorial0(1, x);
-}
-
- |
-
- _factorial: ## @factorial
- .cfi_startproc
-## BB#0: ## %entry
- pushq %rbp
-Ltmp12:
- .cfi_def_cfa_offset 16
-Ltmp13:
- .cfi_offset %rbp, -16
- movq %rsp, %rbp
-Ltmp14:
- .cfi_def_cfa_register %rbp
- movl $1, %eax
- movl %edi, -4(%rbp) ## 4-byte Spill
- movl %eax, %edi
- movl -4(%rbp), %esi ## 4-byte Reload
- popq %rbp
- jmp _factorial0 ## TAILCALL
- .cfi_endproc
- |
-
-
-
- Jmp instructions are in assembler source. -
Benchmark result
-| - | no optimized code | -optimized code A | -optimized code B | -
| Micro-C | -6.06 s | -2.21 s | -2.40 s | -
| GCC -O2 | -1.59 s | -1.02 s | -0.99 s | -
| LLVM -O2 | -5.52 s | -3.95 s | -4.64 s | -
-
-
- LLVM can compile CbC examples like other CbC compilers. -
- LLVM is slower than other compilers but it is not important for us. -
Conclusion
--
-
- We can use LLVM/clang to compile CbC code. -
- We did not modify LLVM IR to implement CbC compiler. -
Future
--
-
- Data segment interface -
- Meta computation -
- Dynamic rewriting of a jmp -
- Generating specialized code -
Code Gear と Data Gear
-
+
- Code Gear とはプログラムの処理の単位である。
- Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
- Data Gear はデータの単位であり、Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
Context
-
-
- Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。 +
- Gears OS には Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
- Gears OSは必要なCode/DataGearに参照したい場合、このContext を通す必要がある。
- interface を記述することで Context を通して Code Gear が参照できるようになった。
- create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。 -
- return で interface を返し、その先で指定した Code Gear へ継続できるようになる。 +
- return で interface を返し、その先で inter face の持つ Code Gear へと継続できるようになる。
Stack* createSingleLinkedStack(struct Context* context) {
struct Stack* stack = new Stack();
@@ -235,7 +236,7 @@
+
+
+Context の生成
+
+ - Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
+ - generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。
+ - 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
+ - generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。
+ - これらを自動生成することで Gears OS の記述量を約半分にすることができます。
diff -r 327435666caa -r 8644cade9765 presen/slide.md
--- a/presen/slide.md Thu Feb 16 08:14:21 2017 +0900
+++ b/presen/slide.md Thu Feb 16 09:19:18 2017 +0900
@@ -11,6 +11,7 @@
- そこで当研究室では Meta Computation を柔軟に記述するためのプログラミング言語の単位として Code Gear、Data Gear という単位を提案している。
# Code Gear と Data Gear
+- Code Gear とはプログラムの処理の単位である。
- Code Gear は関数に比べて細かく分割されているので Meta Computation をより柔軟に記述できる。
- Data Gear はデータの単位であり、Code Gear は 任意の数の Input Data Gear を参照して処理を行い、Output Data Gear を出力し処理を終える。
@@ -38,7 +39,7 @@
- Meta Code Gear で OS の 機能であるメモリ管理やスレッド管理を行う。
# Context
-- Gears OS では Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
+- Gears OS には Context と呼ばれる接続可能な Code/Data Gear のリスト、Temporal Data Gear のためのメモリ空間等を持っている Meta Data Gear がある。
- Gears OSは必要なCode/DataGearに参照したい場合、このContext を通す必要がある。
# Gearef、GearImpl
@@ -84,7 +85,7 @@
# interface の記述
- interface を記述することで Context を通して Code Gear が参照できるようになった。
- create は関数呼び出しで呼び出され、interface と impliment の初期化と Code Gear のポインタの設定を行う。
-- return で interface を返し、その先で指定した Code Gear へ継続できるようになる。
+- return で interface を返し、その先で inter face の持つ Code Gear へと継続できるようになる。
```impl
Stack* createSingleLinkedStack(struct Context* context) {
struct Stack* stack = new Stack();
@@ -102,14 +103,24 @@
}
```
-# Context、stub Code Segment の自動生成
+# Context、stub Code Gear の自動生成
- Gears OS では通常の計算の他に Context や stub などの meta computation を記述する必要がある。
- 現在の CbC で Gears OS を記述すると、この meta computation の記述も行わなくてはならず、これには多くの労力を要する。
- この記述を助けるために Context を生成する generate_context と stub Code Gear を生成する generate_stub を perl スクリプトで作成した。
-# generate context
-- generate\_stub は指定された cbc ファイルの \_\_code型である Code Gear を取得
-- generate\_context は context.h から Data Gear、c ファイルから Code Gear の取得
+# stub Code Gear の生成
+- stub Code Gear は Code Gear 間の継続に挟まれ、Code Gear が必要な Data Gear を Context から取り出す処理を行うものである。
+- stub Code Gear は Code Gear 毎に記述する必要があり、そのCode Gear の引数を見て取り出す Data Gear を選択する。
+- generate_stub は指定された cbc ファイルの __code型である Code Gear を取得。
+- 引数と interface を照らし合わせ、Gearef または GearImpl を決定する。
+- cbc ファイルのから、生成した stub Code Gear を加えて、c ファイルを生成する。
+
+# Context の生成
+- Context は Meta Data Gear に相当し、Code Gear や Data Gear を管理している。
+- generate_context は context.h から Data Gear、c ファイルから Code Gear を取得。
+- 取得した Code/Data Gear の enum の定義は enumCode.h、enumData.h に生成される。
+- generate_context は取得した Code/Data Gear から Context の生成を行うコードを生成する。
+- これらを自動生成することで Gears OS の記述量を約半分にすることができます。
# 今後の課題