changeset 13:607acd92b8eb

fix
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Sat, 04 Jul 2015 22:52:09 +0900
parents 40be058f9df8
children b9179e9084d9
files presentation/presen.html
diffstat 1 files changed, 87 insertions(+), 166 deletions(-) [+]
line wrap: on
line diff
--- a/presentation/presen.html	Sat Jul 04 21:20:22 2015 +0900
+++ b/presentation/presen.html	Sat Jul 04 22:52:09 2015 +0900
@@ -59,9 +59,10 @@
           </tr>
           <tr>
             <td><div align="left">
-                Kaito Tokumori, Shinji Kono
+                Kaito Tokumori, Shinji Kono <br>
+		University of the Ryukyus
                 <script>
-                  document.write("<br>July 4, 2015");
+                  document.write("<br>July 5, 2015");
                 </script>
                 <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:300%;height:0.2em;">
             </div></td>
@@ -72,10 +73,10 @@
       <div class='slide'>
         <h2>Objective</h2>
         <ul>
-          <li>Reliable computation
-          <li>Concurrent execution
-          <li>Reliable improvement
-          <li>Reusablity
+          <li>Acheive Reliable computation
+          <li>Extract Concurrent Execution Automatically
+          <li>Modify and Improve software in a Reliable way
+          <li>Get more Reusablity
         </ul>
         <h3>Introducing new units of programming</h3>
       </div>
@@ -102,7 +103,7 @@
           <li>Add meta computation.
           <li>Extract concurrency from programming units.
         </ul>
-        <h3>It is not easy in the traditional units.</h3>
+        <h3>It is not easy to do this in the traditional units.</h3>
       </div>
 
       <div class='slide'>
@@ -139,14 +140,13 @@
 
       <div class='slide'>
         <h2>Meta code / data segments</h2>
+        A thread of code segments has a context as a meta data segment
         <ul>
           <li>Execution contexts: Thread
           <li>Type signatures of data segments.
           <li>Data segment linkages: Pointer
-          <li>Machine code
+          <li>Machine code of code segments
         </ul>
-        <h3>Meta code segments are executed right after the goto.</h3>
-        <h3>Meta data segments are kinds of process data.</h3>
       </div>
 
       <div class='slide'>
@@ -154,14 +154,15 @@
         <ul>
           <li>An implementation of code segments.
           <li>CbC stands for Continuation based C.
-          <li>Basic syntax is the same as the C.
-          <li>Code segments are set of C statements with goto.
+          <li>Basic syntax is the same as the C, except __code and goto.
+          <li>__code is a type of code segment 
+          <li>Code segments end with parameterized goto.
           <li>Data segments are inplemented as C structures.
         </ul>
       </div>
 
       <div class='slide'>
-        <h2>CbC sample</h2>
+        <h2>code segment syntax</h2>
         <table border='1' align='center' width='80%'>
           <tr><td width='50%'>
               <pre class='small_code'>
@@ -175,9 +176,8 @@
               </pre>
             </td><td valign='top'>
               <ul>
-                <li>Code segments like C functions.
-                <li>CbC transition is goto.
-                <li>Code segments do not return to previous.
+                <li>code segment transition is goto.
+                <li>Code segments have no return statement.
                 <li>There are no return values.
               </ul>
           </td></tr>
@@ -185,19 +185,18 @@
       </div>
 
       <div class='slide'>
-        <h2>CbC sample with data segments</h2>
+        <h2>code segment syntax with data segments</h2>
         <table border='1' align='center' width='80%'>
           <tr><td width='50%'>
               <pre class='small_code'>
-__code code(struct Context* context, struct Allocate* allocate,
+__code code1(struct Allocate* allocate,
             struct Element* element) {
-    allocate->after_append = Code2;
     element ->value        = 10;
-    goto meta(context, Append);
+    struct List* list = (struct List *)malloc(sizeof( struct List));
+    goto append(allocate,list, element);
 }
 
-__code append(struct Context* context, struct Allocate* allocate,
-              struct List* list, struct Element* element) {
+__code append(struct Allocate* allocate, struct List* list, struct Element* element) {
     if(list->head) {
         list->tail->next = element;
     } else {
@@ -205,19 +204,12 @@
     }
     list->tail       = element;
     list->tail->next = 0;
-    goto meta(context, allocate->after_append);
-}
-
-__code meta(struct Context* context, enum Code next) {
-    goto (context->code[next])(context);
+    goto code2(allocate,list, element);
 }
               </pre>
             </td><td valign='top'>
               <ul>
-                <li>A part of list program.
-                <li>Code segment transition into next one via meta code segment.
-                <li>Context has code segments name.
-                <li>Context give meta code segments next code segment pointer.
+                <li>data segments are arguments of a code segment and a goto statement.
               </ul>
           </td></tr>
         </table>
@@ -226,9 +218,9 @@
       <div class='slide'>
         <h2>CbC compilers</h2>
         <ul>
-          <li>Micro-C(one pass standalone compiler)
-          <li>GCC(GNU Compiler Collection)
-          <li>LLVM and Clang
+          <li>Micro-C(one pass standalone compiler) 2001
+          <li>on GCC(GNU Compiler Collection) 2008
+          <li>on LLVM and Clang (Compiler framework) 2014
             <ul>
               <li><font color='red'>The latest!</font>
             </ul>
@@ -236,64 +228,47 @@
       </div>
 
       <div class='slide'>
-        <h2>What are LLVM and Clang?</h2>
-        <ul>
-          <li>Compiler frameworks.
-          <li>has a intermidiate language which is called LLVM IR, LLVM language or LLVM bitcode.
-          <li>Translates LLVM IR to assembly language.
-          <li>Many kinds of optimization.
-          <li>Clang is C, C++ and Obj-C compiler frontend.
-          <li>Clang uses LLVM for compiler backend.
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>Why?</h2>
-        <ul>
-          <li>Apple supported.
-          <li>OS X default compiler.
-          <li>LLVM IR has readable documents.
-          <li>More readable and modifiable than GCC.
-        </ul>
-      </div>
-
-      <div class='slide'>
         <h2>LLVM and Clang's compilation flow</h2>
         <ul>
+          <li>AST : Abstract Syntax Tree (C++ object)
+          <li>LLVM IR is Intermediate Representation (bit code).
           <li>Clang translate C/C++/Obj-C into LLVM IR.
-          <li>LLVM translate LLVM IR into assembly code.
-          <li>LLVM optimize all of intermidiate representation.
+          <li>SelectionDAG : Codegenerator internal 
+          <li>Machine Code : LLVM Machine code
         </ul>
         <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
       </div>
 
       <div class='slide'>
-        <h2>LLVM and Clang's intermidiate representations</h2>
+        <h2>Advantage of LLVM implementation</h2>
         <ul>
-          <li>clang AST
-          <li>LLVM IR
-          <li>SelectionDAG
-          <li>Machine Code
-          <li>MC Layer
+          <li>Apple supported (working on OS X).
+          <li>OS X default compiler.
+          <li>LLVM IR is well documented.
+          <li>better than GCC
         </ul>
-        <h3 align='center'>Intermidiate representations are not modified.</h3>
       </div>
 
       <div class='slide'>
-        <h2>Clang AST</h2>
+        <h2>CbC implementation strategy</h2>
         <ul>
-          <li>The first intermidiate representation.
-          <li>Representation of the source codes structure.
-          <li>Basic node type: Stmt, Decl, Expr.
+          <li>define special type __coee for code segments 
+          <li>no code segment prototyping  (othewise it beomes quite messy )
+          <li>code segments are implemented as tail call force functions
+          <li>Do not modify IR (Intermidiate representations )
+          <li>goto statement is actualy a function call with following return statement <br>
+                 goto f() --> { f() ; return; }
+          <li>allow mixing code segments and normal function calls ( goto with environment )
         </ul>
       </div>
 
       <div class='slide'>
         <h2>LLVM IR</h2>
         <ul>
-          <li>The main intermidiate representation.
-          <li>LLVM translate it into assembly codes.
-          <li>Three forms: in-memory compiler IR, on-disk bitcode, assembly language.
+          <li>Intermediate Representation (bit code).
+          <li>Three forms: in-memory IR, bitcode stream, human readable language.
+          <li>it has precise type, data size, alignment
+          <li>funcion call flags : tail, fastcc, cc10, cc11, erlang, ghc
         </ul>
         <table width='100%'>
           <tr>
@@ -311,54 +286,15 @@
       </div>
 
       <div class='slide'>
-        <h2>Basic strategy of implementating</h2>
+        <h2>CbC implementation strategy</h2>
         <ul>
-          <li>Code segments are implemented by C functions.
+          <li>Code segments are implemented by C functions with return-type __code.
           <li>Data segments are implemented by C structs.
-          <li>Transition is implemented by tail call elimination.
-<!--
+          <li>Goto statement is implemented by seting tail call flag.
           <li>Goto with environment is implemented by setjmp and longjmp.
-            <ul>
-              <li>Goto with environment enable code segments to return C functions.
-            </ul>
--->
         </ul>
       </div>
 
-<!--
-      <div class='slide'>
-        <h2>Implementating CbC compiler in LLVM and Clang</h2>
-        <ul>
-          <li>__code type.
-          <li>Goto syntax.
-          <li>Force to do tail call elimination.
-          <li>Goto with environment.
-          <li>Automatically prototype declatation genarating.
-       </ul>
-      </div>
--->
-
-      <div class='slide'>
-        <h2>Parser</h2>
-        <ul>
-          <li>__code type
-          <li>Prototype declaration generating
-          <li>Goto syntax for transitions
-        </ul>
-        <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="60%"></div>
-      </div>
-
-      <div class='slide'>
-        <h2>__code type</h2>
-        <table width='100%'>
-          <tr>
-            <ul>
-              <li>Code segments are implemented __code type functions.
-              <li>Handled like void functions.
-            </ul>
-          </tr>
-        </table>
-      </div>
 
       <div class='slide'>
         <h2>Prototype declaration generating</h2>
@@ -374,7 +310,7 @@
         <table border='1' width='80%' align='center'>
           <tr>
             <td>original input code
-            <td>Clang genarates it
+            <td>Clang genarates it internaly
           </tr>
           <tr>
             <td><pre class='small_code'>
@@ -404,19 +340,6 @@
 
       <div class='slide'>
         <h2>goto syntax for transition</h2>
-        <table width='100%'>
-          <tr><td>
-              <ul>
-                <li>New goto syntax for transition.
-                <li>Generate normal function call.
-                <li>Tail call elimination is forced later.
-              </ul>
-          </tr>
-        </table>
-      </div>
-
-      <div class='slide'>
-        <h2>goto syntax for transition</h2>
         <ul>
           <li>Add return statement after goto transition.
           <li>It is one the requirement force to tail call elimination.
@@ -446,8 +369,8 @@
 
       <div class='slide'>
         <h2>Forcing Tail Call Elimination</h2>
-        <p>TCE is enabled at CodeGen.</p>
-        <p>TCE is act at SelectionDAGISel.</p>
+        <p>Tail call flang is set in CodeGen.</p>
+        <p>Ensure TCE in SelectionDAGISel.</p>
         <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="60%"></div>
       </div>
 
@@ -455,43 +378,20 @@
         <!--        <h2>Jmp instruction based transition</h2> -->
         <h2>What is tail call elimination?</h2>
         <ul>
-          <li>Tail call is immediately followed by return.
+          <li>Tail call is a function call immediately followed by return.
+          <li>If stack frame have to be unchanged,
           <li>Tail call elimination replace tail call's call instructions with jmp instructions.
-          <li>Transitions are implemented by forced tail call elimination.
+          <li>that is tail call function should have the same arguments and the same return type
         </ul>
         <div align='center'><img src="fig/TCE.svg" width="40%"></div>
       </div>
 
 
       <div class='slide'>
-        <h2>Forcing Tail Call Elimination</h2>
-        <ul>
-          <li>LLVM IR has function call flags.
-          <li>tail mean it is tail call.
-          <li>Calling convention tell compiler how callee functions receive parameters from their caller.
-        </ul>
-        <table width='100%'>
-          <tr>
-            <td style="border: double;">
-              <pre class='code'>
-define fastcc void @factorial(i32 %x) #0 {
-  entry:
-  <font color='red'>tail</font> call <font color='red'>fastcc</font> void @factorial0(i32 1, i32 %x)
-  ret void
-}
-              </pre>
-            </td>
-          </tr>
-        </table>
-        <div align='center'><h3>Use them for force to tail call elimination.</h3></div>
-      </div>
-
-      <div class='slide'>
-        <h2>Forcing Tail Call Elimination</h2>
-        <p>Tail Call Elimination requirements</p>
+        <h2>Tail Call Elimination requirements</h2>
         <ul>
           <li>Set tail flag at the code segments call.
-          <li>Tailcallopt is enabled.
+          <li>Tailcallopt path is enabled in the compiler.
           <li>The caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
           <li>Return value type has to be the same as the caller's.
         </ul>
@@ -505,20 +405,31 @@
           <li>Fast cc is used consistently in code segments call.
           <li>All the code segments return value type is void.
         </ul>
+        This is the reason why we need __code type for code segments.
+      </div>
+
+      <div class='slide'>
+        <h2>goto a code segment from a normal C function</h2>
+        <ul>
+          <li>Assume we have code segment g and normal funciton f
+          <li>simply goto g() in C function f()
+          <li>goto g() never returns to function f
+        </ul>
+        How to return to C from a code segment?
       </div>
 
       <div class='slide'>
         <h2>Goto with environment</h2>
-        <ul>
-          <li>Code segments do not have return.
-          <li>Code segments can return C functions by Goto with environment.
-          <li>In the GCC, use nested functions.
-          <li>In the LLVM and Clang, use setjmp and longjmp.
+        <p>
+          We want provide continuation of function f.
+          The continuation is not a simple code segment,
+          because code segment has not state.
+          We represent the continuation with a code segment (__return) and a meta data segment (__environment).
         </ul>
       </div>
 
       <div class='slide'>
-        <h2>Sample code of Goto with environment</h2>
+        <h2>Syntax of Goto with environment</h2>
         <table width='100%'>
           <tr><td valign='top'>
               <ul>
@@ -552,9 +463,19 @@
       </div>
 
       <div class='slide'>
-        <h2>Implementing goto with environment</h2>
+        <h2>Implementation of  goto with environment</h2>
+        Several ways to implementation
         <ul>
-          <li>Include setjmp.h always.
+        <li>setmp/longjmp (LLVM)
+        <li>nested function closure with thread safe variable (GCC)
+        <li>direct manipulation of frame pointer and return value (Micro-C)
+        </ul>
+      </div>
+
+      <div class='slide'>
+        <h2>LLVM Implementation of  goto with environment</h2>
+        <ul>
+          <li>Include setjmp.h internally.
           <li>Generate C struct for saving environment.
             <ul>
               <li>This struct is __environment.