Mercurial > hg > Papers > 2015 > kaito-lola
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.