Mercurial > hg > Papers > 2016 > kaito-master

changeset 19:1d151a4d03f6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix slide
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Mon, 15 Feb 2016 22:49:13 +0900
parents e47c56bfcd2f
children fc397777a7e2
files paper/master_paper.tex slide/blank.html
diffstat 2 files changed, 320 insertions(+), 255 deletions(-) [+]
line wrap: on
line diff
--- a/paper/master_paper.tex	Mon Feb 15 07:49:26 2016 +0900
+++ b/paper/master_paper.tex	Mon Feb 15 22:49:13 2016 +0900
@@ -7,7 +7,7 @@
 \usepackage{comment}
 %\input{dummy.tex} %% font
 
-\jtitle{LLVM, Clang 上の Continuation based C コンパイラの改良}
+\jtitle{LLVM Clang 上の Continuation based C コンパイラの改良}
 \etitle{Improvement of Continuation based C compiler on LLVM and Clang}
 \year{2016年 3月}
 \eyear{March 2016}
@@ -26,7 +26,7 @@
 \end{minipage}}
 \markleftfoot{% 左下に挿入
   \begin{minipage}{.8\textwidth}
-    LLVM, Clang 上の Continuation based C コンパイラの改良
+    LLVM Clang 上の Continuation based C コンパイラの改良
 \end{minipage}}
 
 \newcommand\figref[1]{図 \ref{fig:#1}}
--- a/slide/blank.html	Mon Feb 15 07:49:26 2016 +0900
+++ b/slide/blank.html	Mon Feb 15 22:49:13 2016 +0900
@@ -2,7 +2,7 @@
 <html>
   <head>
     <meta charset='utf-8'>
-    <title>LLVM, Clang 上の Continuation based C コンパイラの改良</title>
+LLVM Clang 上の Continuation based C コンパイラの改良
 
     <!-- 
          Notes on CSS media types used:
@@ -88,7 +88,7 @@
         <table width="90%" height="90%" border="0" align="center">
           <tr>
             <td><div align="center">
-                <h1><font color="#808db5">LLVM, Clang 上の Continuation based C コンパイラの改良</font></h1>
+                <h1><font color="#808db5">LLVM Clang 上の Continuation based C コンパイラの改良</font></h1>
             </div></td>
           </tr>
           <tr>
@@ -114,44 +114,38 @@
       
       <div class='slide'>
         <h2>code segment を用いるプログラミング言語 CbC</h2>
-        <p>関数やクラス、オブジェクト等は分割、結合を行うことは困難である。</p>
-        <p>アセンブリは分割、結合が可能だが易しくない。</p>
-        <p>当研究室ではプログラムを code segment、data segmentという単位を用いて書くという手法を提案しており、Cerium, Continuation based C(CbC)等がそれらを利用する。</p>
-        <p>それぞれの単位は分割と結合を行うことが可能で、プログラムの分割、結合を容易にする。</p>
-        <p>それぞれの単位はメタレベルのものが存在し, メタ計算の記述も可能である。</p>
+        <p>プログラムを記述する際, 本来行いたい処理の他にも記述しなけらばならない処理が存在する. malloc 等によるメモリの管理, スレッドの待ち合わせやネットワークの管理, エラーハンドリング等がこれにあたる.</p>
+        <p>これらの計算は meta computation と呼ばれる.</p>
+        <p>meta computation を柔軟に記述するために計算を細かく分割したい.</p>
+        <p>code segment, data segment という単位を提案する. code segment が処理, data segment がデータの単位であり, meta code segment, meta data segment という meta computation の単位も存在する.</p>
+        <p>Continuation based C (CbC) は code segment を用いるプログラミング言語である. </p>
+        <p>本研究では, LLVM Clang をベースとしたコンパイラの改良を行い, 他の CbC コンパイラが出力するコードとの実行速度の比較, C と Scheme との実行速度の比較を行った</p>
       </div>
 
 
       <div class='slide'>
         <h2>Continuation based C(CbC)</h2>
-        <ul>
-          <li>基本的な構文は C と同じ
-          <li>CbC は code segment を処理の基本単位とする
-          <li>goto による軽量継続を用いて処理を行う
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>コード例</h2>
         <table border='1' align='center' width='80%'>
           <tr><td width='50%'>
               <pre class='small_code'>
-__code f() {
-    goto g();
+__code cs0(int a, int b){
+  goto cs1(a+b);
 }
 
-__code g() {
-    goto h();
+__code cs1(int c){
+  goto cs2(c);
 }
               </pre>
             </td><td valign='top'>
               <ul>
-                <li>__code は code segment であることを示す
-                <li>code segment は返り値を持たない
-                <li>軽量継続は goto のとなりに code segment 名と引数を書く
+                <li>__code は code segment であることを示す.
+                <li>code segment から次の code segment への移動を軽量継続と呼ぶ.
+                <li>軽量継続は goto のとなりに code segment 名と引数(出力)を書く.
+                <li>軽量継続はフレームポインタ操作によるスタックの状態の保存を行わない.
               </ul>
           </td></tr>
         </table>
+        <div align="center"><img src="fig/codesegment.svg" width="45%"></div>
       </div>
 
       <div class='slide'>
@@ -197,44 +191,14 @@
           clang はソースコードを読み込むと Parser を用いて clangAST を生成する。CodeGenがASTを元にLLVM IRを生成し, それが LLVM の入力に対応する。
         </p>
         <p>
+          AST の各ノードが式や文, 値等に対応している.
+        </p>
+        <p>
           LLVM は中間表現の形を何度も変化させる。最適化をかけながら徐々にターゲットへの依存度が高くし、最終的にアセンブリコードや実行可能ファイルを出力する。最適化を含む全ての処理がパスによって行われる。
         </p>
         <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
       </div>
 
-      <div class='slide'>
-        <h2>LLVM と Clang のもつ 中間表現</h2>
-        <ul>
-          <li>clangAST : 抽象構文木。各ノードが式や文、値等に対応する。
-          <li>LLVM IR : LLVM の入力。LLVM 言語とも呼ばれる。メインの中間表現。
-          <li>SelectionDAG : 各ノードが命令や演算子に対応する有向非巡回グラフ。
-          <li>Machine Code : アセンブリコードとは異なる。レジスタの割当などはここで行う。
-          <li>MC Layer : 正確には中間表現を扱う層。一つの命令や演算子に対応するクラスを持ち、様々な出力を同様のAPIを用いて行える。
-        </ul>
-        <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
-      </div>
-
-      <div class='slide'>
-        <h2>LLVM IR</h2>
-        <ul>
-          <li>LLVM bitcode とも呼ばれる
-          <li>人が読みやすいアセンブリ言語形式、ビットコード、実行時のメモリ上の形式の3つの形式を持つ
-          <li>関数呼び出しに、呼び出し規約等のフラグをもつ
-        </ul>
-        <table width='100%'>
-          <tr>
-            <td style="border: double;">
-              <pre class='code'>
-define fastcc void @factorial(i32 %x) #0 {
-  entry:
-  tail call fastcc void @factorial0(i32 1, i32 %x)
-  ret void
-}
-              </pre>
-            </td>
-          </tr>
-        </table>
-      </div>
 
       <div class='slide'>
         <h2>CbC 実装概要</h2>
@@ -242,48 +206,8 @@
           <li>code segment は __code 型の関数とする
           <li>軽量継続は tail call elimination の強制によって実現
           <li>code segment はプロトタイプ宣言を必要としない
-          <li>LLVM IR に変更を加えない
-        </ul>
-      </div>
-
-
-      <div class='slide'>
-        <h2>__code 型</h2>
-        <ul>
-          <li>__code 型の値を返す関数というわけではなく code segment を示すフラグとする
-          <li>code segment は戻り値を持たないので void 型と同様に実装する
-          <li>LLVM IR として出力した際にも void になる
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>goto code_segment();</h2>
-        <ul>
-          <li>code segment のための goto syntax の追加
-          <li>通常の関数呼び出しと同じように実装し、 tail call elimination を強制することで軽量継続にする
-          <li>AST生成の時点では関数呼び出しの直後に return 文を付加するだけ
+          <li>LLVM IR に変更を加えると後の最適化全てに手を加えなければならなくなる. そのため LLVM IR は一切変更しない.
         </ul>
-        <table border='1' width='80%' align='center'>
-          <tr>
-            <td>元のコード
-            <td>生成される AST に対応するコード
-          </tr>
-          <tr>
-            <td><pre class='small_code'>
-__code code1() {
-     :
-  goto code2();
-}
-              </pre>
-            <td><pre class='small_code'>
-void code1() {
-     :
-  code2();
-  <font color='red'>return;</font>
-}
-              </pre>
-          </tr>
-        </table>
       </div>
 
       <div class='slide'>
@@ -325,22 +249,55 @@
       </div>
 
       <div class='slide'>
-        <h2>tail call elimination の強制</h2>
+        <h2>軽量継続のための構文</h2>
         <ul>
-          <li>__code 型の関数 (= code segment) に tail call elimination を強制
-          <li>TailCallElim というパスを利用する
-          <li>いくつかの条件を満たさなければならない
+          <li>code segment の軽量継続ための goto syntax の追加
+          <li>通常の関数呼び出しと同じように実装し、 tail call elimination を強制することで軽量継続にする
+          <li>AST生成の時点では関数呼び出しの直後に return 文を付加するだけ
         </ul>
+        <table border='1' width='80%' align='center'>
+          <tr>
+            <td>元のコード
+            <td>生成される AST に対応するコード
+          </tr>
+          <tr>
+            <td><pre class='small_code'>
+__code code1() {
+     :
+  goto code2();
+}
+              </pre>
+            <td><pre class='small_code'>
+void code1() {
+     :
+  code2();
+  <font color='red'>return;</font>
+}
+              </pre>
+          </tr>
+        </table>
       </div>
 
       <div class='slide'>
         <h2>tail call elimination</h2>
+        <table border='1' align='center' width='80%'>
+          <tr><td width='50%'>
+              <pre class='small_code'>
+int funcA(int a, int b){
+      :
+  funcC(a-b); // NOT TAIL CALL
+      :
+  return funcB(a+b); // TAIL CALL
+}
+              </pre>
+            </td><td valign='top'>
         <ul>
           <li>tail call に対する最適化
           <li>tail call は関数の最後に位置する関数呼び出し
           <li>通常関数は call 命令で呼び出されるが tail call elimination によって jmp 命令を用いるようになる
         </ul>
-        <div align='center'><img src="fig/TCE.svg" width="40%"></div>
+          </td></tr>
+        </table>
       </div>
 
       <div class='slide'>
@@ -355,7 +312,7 @@
       </div>
 
       <div class='slide'>
-        <h2>CbC から生成される LLVM IR</h2>
+        <h2>CbC から生成される LLVM IR とアセンブリ</h2>
         <ul>
           <li>軽量継続は tail, fastcc 付きの void 型の関数呼び出しに
           <li>LLVM IR への変更は一切ない
@@ -364,39 +321,129 @@
           <tr>
             <td>元のコード
             <td>LLVM IR
+            <td>アセンブリ
           </tr>
           <tr>
             <td><pre class='small_code'>
-__code code1() {
-     :
-  goto code2();
+__code code1(int a, int b) {
+  goto code2(a+b);
 }
 
-__code code2(){
+__code code2(int c){
      :
 }
               </pre>
             <td><pre class='small_code'>
-define fastcc void @code1() #0 {
+define fastcc void @code1(i32 %a, i32 %b) #0 {
 entry:
-     :
+  %add = add nsw i32 %a, %b
 <font color='red'>tail call fastcc void</font> @code2()
-ret void
+  ret void
 }
 
 define fastcc void @code2() #0 {
      :
 }
               </pre>
+            <td><pre class='small_code'>
+_code1:                                 ## @code1
+	.cfi_startproc
+## BB#0:                                ## %entry
+	pushq	%rbp
+Ltmp0:
+	.cfi_def_cfa_offset 16
+Ltmp1:
+	.cfi_offset %rbp, -16
+	movq	%rsp, %rbp
+Ltmp2:
+	.cfi_def_cfa_register %rbp
+	addl	%esi, %edi
+	popq	%rbp
+	jmp	_code2                  ## TAILCALL
+	.cfi_endproc
+              </pre>
           </tr>
         </table>
+        <ul>
+          <li>code segment code2 への軽量継続が jmp 命令で行われている
+          <li>tail call elimination が正しく働いている
+          <li>万が一 tail call elimination に失敗した場合にはエラーメッセージを出す
+          <li>push, pop 命令によるフレームポインタの操作が残ってしまっている
+        </ul>
+      </div>
+
+      <div class='slide'>
+        <h2>フレームポインタとスタックポインタ操作の除去</h2>
+        <ul>
+          <li>omit leaf frame pointer という最適化を使用する.
+          <li>omit leaf frame pointer は leaf function 呼び出し時のスタック操作に関わる最適化.
+          <li>フレームポインタ, スタックポインタの操作を除去する.
+          <li>leaf function とは 関数を呼び出さない関数, コールツリーの先端に位置する関数を指す.
+          <li>全ての code segment は leaf function の条件を満たす.
+        </ul>
       </div>
 
       <div class='slide'>
+        <h2>フレームポインタとスタックポインタ操作の除去</h2>
+        <table border='1' width='80%' align='center'>
+          <tr>
+            <td>元のコード
+            <td>omit leaf frame pointer 無し
+            <td>omit leaf frame pointer 有り
+          </tr>
+          <tr>
+            <td><pre class='small_code'>
+__code code1(int a, int b) {
+  goto code2(a+b);
+}
+
+__code code2(int c){
+     :
+}
+              </pre>
+            <td><pre class='small_code'>
+_code1:                                 ## @code1
+	.cfi_startproc
+## BB#0:                                ## %entry
+<span style='background-color:#ffff77'>	pushq	%rbp
+Ltmp0:
+	.cfi_def_cfa_offset 16
+Ltmp1:
+	.cfi_offset %rbp, -16
+	movq	%rsp, %rbp</span>
+Ltmp2:
+	.cfi_def_cfa_register %rbp
+	addl	%esi, %edi
+	popq	%rbp
+	jmp	_code2                  ## TAILCALL
+	.cfi_endproc
+              </pre>
+            <td><pre class='small_code'>
+_code1:                                 ## @code1
+	.cfi_startproc
+## BB#0:                                ## %entry
+	pushq	%rax
+Ltmp0:
+	.cfi_def_cfa_offset 16
+	addl	%esi, %edi
+	popq	%rax
+	jmp	_code2                  ## TAILCALL
+	.cfi_endproc
+              </pre>
+          </tr>
+        </table>
+        <ul>
+          <li>スタックポインタとフレームポインタの操作が取り除くことができた
+          <li>rax の値を push/pop しているがコレも取り除くことが出来る.
+        </ul>
+      </div>
+      <div class='slide'>
         <h2>環境付き継続</h2>
         <ul>
           <li>code segment から 関数に戻るための継続
-          <li>通常 code segment は環境を保持しないので前の関数に戻ることが出来ない
+          <li>環境とはスタックの状態を指す
+          <li>関数呼び出しが行われる際, スタックポインタとフレームポインタの値を変更し, 呼び出す関数用にスタックを割く. その際元のフレームポインタとスタックポインタの値を保持しておき, return の際にもとに戻すことで前の関数に戻る.
+          <li>軽量継続ではスタックポインタとフレームポインタの値は変更されず, 環境を保持しないので前の関数に戻ることが出来ない
           <li>継続前の環境を __environment, 継続前の環境に戻るための code segment を __return に保存し, これらを利用して関数に戻る
         </ul>
       </div>
@@ -417,7 +464,7 @@
 }
 
 int funcB(){
-  goto cs(__return, __environment);
+  goto cs(<font color='red'>__return</font>, <font color='red'>__environment</font>);
   /* never reached */
   return -1;
 }
@@ -443,32 +490,6 @@
       </div>
 
       <div class='slide'>
-        <h2>LLVM Clang 上での環境付き継続実装の問題</h2>
-        <ul>
-          <li>__return として利用する code segment の名前が一意にならなければならない.
-          <li>継続前の C の関数の型に応じて返す値の型を変化させなければならない.
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>code segment 名の問題の解決法</h2>
-        <ul>
-          <li>C の仕様では関数名に '.' (ドット) を使用することは出来ないが、LLVM IR , clang 内部では使用することが出来る
-          <li>戻り先関数名 + '..' + ID という名前にすることで解決
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>戻り値の型の問題の解決法</h2>
-        <ul>
-          <li>clang では型情報を QualType という一つのオブジェクトに保存できる.
-          <li>下図は const int * 型に対応する QualType
-          <li>戻り先関数の型に使われている QualType を戻り値を保存する変数の型に利用することで解決
-        </ul>
-        <div align='center'><img src="fig/qualType.svg" width="80%"></div>
-      </div>
-
-      <div class='slide'>
         <h2>LLVM での環境付き継続の実装</h2>
         <table width='100%'>
           <tr><td valign='top'>
@@ -515,44 +536,47 @@
       </div>
 
       <div class='slide'>
-        <h2>Gears OS サポート</h2>
+        <h2>Gears OS</h2>
         <ul>
           <li>Gears OS は CbC で記述された並列フレームワーク
-          <li>通常の CbC には存在しない meta code segment, data segment が存在する
+          <li>meta code segment, data segment が存在する
           <li>現在の CbC だけで記述するのは容易いとは言えない
-          <li>記述を助ける機能が必要
+          <li>記述を助ける機能, 新しい構文が必要
         </ul>
       </div>
 
       <div class='slide'>
-        <h2>Gears OS コード例</h2>
+        <h2>CbC での meta computation</h2>
         <table width='100%'>
           <tr><td valign='top'>
               <ul>
                 <li>code segment 間の遷移に meta code segment の処理が入る
+                <li>右のコードは synchronizedQueue のコードの一部. queue の lock が meta computation.
                 <li>data segment へは context からアクセスできる
-                <li>必要な data segment の取得は stub で行われる
-        <div align="center"><img src="fig/meta.svg" width="90%"></div>
+                <li>context は data segment, code segmentを管理する meta data segment である.
+                <li>code segment が必要とする data segment の取得は stub で行われる
+        <div align="center"><img src="fig/metaCS.svg" width="90%"></div>
               </ul>
             <td style="border: double;">
               <pre class='small_code'><div class='highlight'>
-__code meta(struct Context* context, enum Code next) {
-  goto (context->code[next])(context);
-}
-
-__code code1_stub(struct Context* context) {
-  goto code1(context, &context->data[Allocate]->allocate);
+__code meta_sender(struct Context* context, struct Queue* queue, enum Code next) {
+    // lock
+    pthread_mutex_lock(&queue->mutex);
+    goto (context->code[next])(context);
 }
 
-__code code1(struct Context* context, struct Allocate* allocate) {
-  allocate->size = sizeof(long);
-  allocator(context);
-  goto meta(context, Code2);
+__code sender(struct Context* context, struct Queue* queue) {
+    goto meta_sender(context, queue, Put);
 }
 
-__code code2(struct Context* context, long* count) {
-  *count = 0;
-  goto meta(context, Code3);
+__code sender_stub(struct Context* context) {
+    goto sender(context, &context->data[Queue]->queue);
+}
+
+__code code4(struct Context* context, long* count, struct Allocate* allocate, struct Element* element) {
+    allocate->after_put = Code3;
+    element->value = (*count)++;
+    goto meta(context, Sender);
 }
               </div></pre>
           </tr>
@@ -560,77 +584,67 @@
       </div>
 
       <div class='slide'>
-        <h2>Gears OS サポート</h2>
+        <h2>CbC で Gears OS を記述するには</h2>
         <ul>
-          <li>Gears OS は CbC で記述された並列フレームワーク
-          <li>通常の CbC には存在しない meta code segment, data segment が存在する
-          <li>現在の CbC だけで記述するのは容易いとは言えない
-          <li>記述を助ける機能が必要
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>サポートする機能</h2>
-        <ul>
-          <li>context の隠蔽
-          <li>meta code segment への自動接続
+          <li>context は meta data segment なので code segment からは見えない
+          <li>code segment は 見かけ上 code segment に接続するが, 実際には meta code segment を経由する.
           <li>stub の自動生成
-          <li>提案した構文に柔軟に対応できるよう python スクリプトでの実装
         </ul>
       </div>
 
       <div class='slide'>
         <h2>Gears OS サポート</h2>
         <ul>
-          <li>右のコードをスクリプトに通すと左側のコードが生成される
-          <li>meta code segment への継続や引数 context, stub など機械的な処理が取り除かれる
-          <li>特に stub は1つ1つのコードセグメントに対応するので記述するコードセグメントの量が大幅に減る
+          <li>右のコードから左のコードが生成される
+          <li>code segment が meta level のものに触れなくなる.
+          <li>stub による data segment の取り出しが自動的に行われる.
         </ul>
         <table border='1' width='80%' align='center'>
           <tr>
-            <td>従来のコード
-            <td>記述を簡易化したコード
+            <td>生成されるコード
+            <td>元のコード
           </tr>
           <tr>
             <td><pre class='small_code'>
-__code meta(struct Context* context, enum Code next) {
-  goto (context->code[next])(context);
+__code meta_sender(struct Context* context, struct Queue* queue, enum Code next) {
+    // lock
+    pthread_mutex_lock(&queue->mutex);
+    goto (context->code[next])(context);
+}
+
+__code sender(struct Context* context, struct Queue* queue) {
+    goto <font color='red'>meta_sender(context, queue, Put)</font>;
+}
+
+__code sender_stub(struct Context* context) {
+    goto sender(context, &context->data[Queue]->queue);
 }
 
-__code code1_stub(struct Context* context) {
-  goto code1(context, &context->data[Allocate]->allocate);
+__code code4(struct Context* context, long* count, struct Allocate* allocate, struct Element* element) {
+    allocate->after_put = Code3;
+    element->value = (*count)++;
+    goto <font color='red'>meta(context, Sender)</font>;
+}
+              </pre>
+            <td><pre class='small_code'>
+__code meta_sender(struct Context* context, struct Queue* queue, enum Code next) {
+    // lock
+    pthread_mutex_lock(&queue->mutex);
+    goto (context->code[next])(context);
 }
 
-__code code1(struct Context* context, struct Allocate* allocate) {
-  allocate->size = sizeof(long);
-  allocator(context);
-  goto meta(context, Code2);
+__code sender(struct Queue* queue) {
+    goto <font color='red'>put(queue)</font>;
 }
 
 
-__code code2(struct Context* context, long* count) {
-  *count = 0;
-  goto meta(context, Code3);
-}
+
+
 
-__code code2_stub(struct Context* context) {
-  goto code2(context, &context->data[Count]->count);
-}
-              </pre>
-            <td><pre class='small_code'>
-__code meta(struct Context* context, enum Code next) {
-  goto (context->code[next])(context);
-}
-
-__code code1(struct Allocate* allocate) {
-  allocate->size = sizeof(long);
-  allocator();
-  goto code2();
-}
-
-__code code2(long* count) {
-  *count = 0;
-  goto code3();
+__code code4(long* count, struct Allocate* allocate, struct Element* element) {
+    allocate->after_put = Code3;
+    element->value = (*count)++;
+    goto <font color='red'>sender()</font>;
 }
               </pre>
           </tr>
@@ -640,54 +654,12 @@
       <div class='slide'>
         <h2>評価</h2>
         <ul>
-          <li>出力されるアセンブリコードの確認
           <li>環境付き継続の速度比較
           <li>C と CbC との比較
         </ul>
       </div>
 
       <div class='slide'>
-        <h2>アセンブリコード</h2>
-        <table border='1' width='80%' align='center'>
-          <tr>
-            <td>CbCのコード
-            <td>出力されたアセンブリ
-          </tr>
-          <tr>
-            <td><pre class='small_code'>
-__code f(int i,stack sp) {
-  int k,j;
-  k = 3+i;
-  goto f_g0(i,k,sp);
-}
-              </pre>
-            <td><pre class='small_code'>
-_f:                                     ## @f
-	.cfi_startproc
-## BB#0:                                ## %entry
-	subq	$24, %rsp
-Ltmp9:
-	.cfi_def_cfa_offset 32
-	movl	%edi, %eax
-	addl	$3, %eax
-	movq	%rsi, 16(%rsp)          ## 8-byte Spill
-	movl	%eax, %esi
-	movq	16(%rsp), %rdx          ## 8-byte Reload
-	addq	$24, %rsp
-	<font color='red'>jmp</font>	_f_g0                   ## TAILCALL
-	.cfi_endproc
-              </pre>
-          </tr>
-        </table>
-        <ul>
-          <li>code segment f_g0 への継続が jmp 命令で行われている
-          <li>push, pop 命令によるフレームポインタの操作が除去されている
-          <li>tail call elimination, omit leaf frame pointer が正しく働いている
-          <li>万が一 tail call elimination に失敗した場合にはエラーメッセージを出す
-        </ul>
-      </div>
-
-      <div class='slide'>
         <h2>環境付き継続の速度比較</h2>
         <ul>
           <li>環境付き継続を大量に繰り返すプログラムで測定
@@ -696,19 +668,69 @@
           <li>nested function より高速
           <li>最適化を用いることで Micro-C と同等の速度を実現
         </ul>
-        <div align="center"><img src="fig/env.svg" width="40%"></div>
+          <table  border="1" align='center' width='40%'>
+            <tbody>
+              <tr>
+                <td style="text-align: center;">コンパイラ名</td>
+                <td style="text-align: center;">実行速度 (秒)</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">LLVM Clang</td>
+                <td style="text-align: right;">3.35</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">LLVM Clang -O2</td>
+                <td style="text-align: right;">1.30</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">LLVM Clang (old)</td>
+                <td style="text-align: right;">23.30</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">Micro-C</td>
+                <td style="text-align: right;">1.29</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">GCC</td>
+                <td style="text-align: right;">14.73</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">GCC -O2</td>
+                <td style="text-align: right;">12.96</td>
+              </tr>
+            </tbody>
+          </table>
       </div>
 
       <div class='slide'>
         <h2>C, Scheme との速度比較</h2>
         <ul>
-          <li>四則演算を繰り返し行うプログラム
+          <li>関数呼び出しまたは軽量継続, 継続を繰り返し行うプログラム.
           <li>x86-64 Mac OS X
           <li>Scheme は chicken コンパイラを使用
           <li>関数呼び出しよりも軽量継続の方が高速である
           <li>スタック操作の処理が重たいことがわかる
         </ul>
-        <div align="center"><img src="fig/comp.svg" width="40%"></div>
+          <table  border="1" align='center' width='40%'>
+            <tbody>
+              <tr>
+                <td style="text-align: center;">言語名</td>
+                <td style="text-align: center;">実行速度 (秒)</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">CbC</td>
+                <td style="text-align: right;">3.10</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">C</td>
+                <td style="text-align: right;">4.85</td>
+              </tr>
+              <tr>
+                <td style="text-align: center;">Scheme</td>
+                <td style="text-align: right;">39.24</td>
+              </tr>
+            </tbody>
+          </table>
       </div>
 
       <div class='slide'>
@@ -716,6 +738,7 @@
         <ul>
           <li>LLVM clang 上に実装した CbC コンパイラの改良を行った
           <li>omit leaf frame pointer の強制を行い、軽量継続時のフレームポインタ操作を除去した
+          <li>code segment のプロトタイプ宣言を自動で行うようにした.
           <li>環境付き継続に builtin の関数を用いることで速度が元の 7 倍になった
           <li>Gears OS の記述をサポートするスクリプトの作成を行い, data segment, meta code segment を用いる CbC の記述量を減らした
           <li>C 言語との速度比較では軽量継続が関数呼び出しより高速であるという結果が得られた
@@ -726,13 +749,55 @@
         <h2>今後の課題</h2>
         <ul>
           <li>環境付き継続においてアセンブリコードを直接生成するbuiltin 関数の実装
-          <li>python スクリプトで実装した Gears OS サポート機能を LLVM 上に実装
+          <li>meta code segment, meta data segment, data segment を用いる構文を LLVM Clang 上に実装
           <li>data segment の signature を利用できる構文の設計・実装
-          <li>強い最適化がかかった場合でも正しく tail call elimination を行えるよう改善
           <li>C に依存しない、code segment, data segment を用いる新しいプログラミング言語の開発
         </ul>
       </div>
 
+      <div class='slide'>
+        <h2>LLVM と Clang のもつ 中間表現</h2>
+        <ul>
+          <li>clangAST : 抽象構文木。各ノードが式や文、値等に対応する。
+          <li>LLVM IR : LLVM の入力。LLVM 言語とも呼ばれる。メインの中間表現。
+          <li>SelectionDAG : 各ノードが命令や演算子に対応する有向非巡回グラフ。
+          <li>Machine Code : アセンブリコードとは異なる。レジスタの割当などはここで行う。
+          <li>MC Layer : 正確には中間表現を扱う層。一つの命令や演算子に対応するクラスを持ち、様々な出力を同様のAPIを用いて行える。
+        </ul>
+        <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
+      </div>
+
+      <div class='slide'>
+        <h2>LLVM IR</h2>
+        <ul>
+          <li>LLVM bitcode とも呼ばれる
+          <li>人が読みやすいアセンブリ言語形式、ビットコード、実行時のメモリ上の形式の3つの形式を持つ
+          <li>関数呼び出しに、呼び出し規約等のフラグをもつ
+        </ul>
+        <table width='100%'>
+          <tr>
+            <td style="border: double;">
+              <pre class='code'>
+define fastcc void @factorial(i32 %x) #0 {
+  entry:
+  tail call fastcc void @factorial0(i32 1, i32 %x)
+  ret void
+}
+              </pre>
+            </td>
+          </tr>
+        </table>
+      </div>
+
+      <div class='slide'>
+        <h2>__code 型</h2>
+        <ul>
+          <li>__code 型の値を返す関数というわけではなく code segment を示すフラグとする
+          <li>code segment は戻り値を持たないので void 型と同様に実装する
+          <li>LLVM IR として出力した際にも void になる
+        </ul>
+      </div>
+
     </div> <!-- presentation -->
   </bodypp>
 </html>