Mercurial > hg > Papers > 2015 > kaito-lola

<!DOCTYPE html>
<html>
  <head>
    <meta charset='utf-8'>
    <title>Presen</title>
    <!-- style sheet links -->
    <link rel="stylesheet/less" href="themes/blank/projection.css.less"  media="screen,projection">
    <link rel="stylesheet/less" href="themes/blank/screen.css.less"      media="screen">
    <link rel="stylesheet/less" href="themes/blank/print.css.less"       media="print">

    <link rel="stylesheet/less" href="blank.css.less"    media="screen,projection">

    <!-- add js libs (less, jquery) -->
    <script src="js/less-1.1.4.min.js"></script>
    <script src="js/jquery-1.7.min.js"></script>

    <!-- S6 JS -->
    <script src="js/jquery.slideshow.js"></script>
    <script src="js/jquery.slideshow.counter.js"></script>
    <script src="js/jquery.slideshow.controls.js"></script>
    <script src="js/jquery.slideshow.footer.js"></script>
    <script src="js/jquery.slideshow.autoplay.js"></script>
    <script>
      $(document).ready( function() {
      Slideshow.init();

      // Example 2: Start Off in Outline Mode
      // Slideshow.init( { mode: 'outline' } );

      // Example 3: Use Custom Transition
      // Slideshow.transition = transitionScrollUp;
      // Slideshow.init();

      // Example 4: Start Off in Autoplay Mode with Custom Transition
      // Slideshow.transition = transitionScrollUp;
      // Slideshow.init( { mode: 'autoplay' } );
      } );
    </script>
  </head>
  <body>

    <div class="layout">
      <div id="header"></div>
      <div id="footer">
        <div align="right">
          <img src="images/concurrency.png" width="200">
        </div>
      </div>
    </div>

    <div class="presentation">

      <div class='slide cover'>
        <table width="90%" height="90%" border="0" align="center">
          <tr>
            <td><div align="center">
                <h1><font color="#808db5">Implementating Continuation based language in Clang and LLVM</font></h1>
            </div></td>
          </tr>
          <tr>
            <td><div align="left">
                Kaito Tokumori, Shinji Kono
                <script>
                  document.write("<br>July 4, 2015");
                </script>
                <hr style="color:#ffcc00;background-color:#ffcc00;text-align:left;border:none;width:300%;height:0.2em;">
            </div></td>
          </tr>
        </table>
      </div>

      <div class='slide'>
        <h2>Objective</h2>
        <ul>
          <li>Reliable computation
          <li>Concurrent execution
          <li>Reliable improvement
          <li>Reusablity
        </ul>
        <h3>Introducing new units of programming</h3>
      </div>


      <div class='slide'>
        <h2>Traditional units of programming</h2>
        <ul>
          <li>Machine instruction
          <li>Statements of programming language
          <li>Function call / Method
          <li>Module / Class / Interface
          <li>Thread / Process
          <li>Object
          <li>Record / Table
        </ul>
      </div>

      <div class='slide'>
        <h2>What we want to do with programming units?</h2>
        <ul>
          <li>Divide large functions into small parts.
          <li>Add hidden arguments without code modification.
          <li>Add meta computation.
          <li>Extract concurrency from programming units.
        </ul>
        <h3>It is not easy in the traditional units.</h3>
      </div>

      <div class='slide'>
        <h2>New programing units</h2>
        <ul>
          <li>Units of programming: code segments, data segments.
          <li>Code segments are units of calculation.
          <li>Data segments are sets of typed data.
        </ul>
      </div>

      <div class='slide'>
        <h2>Code segments</h2>
        <ul>
          <li>Function from input data segments to output data segments.
          <li>Code segments have no states.
          <li>Access in typed data in the data segments by name.
          <li>Specify code segmnets to be executed using goto.
        </ul>
        <h3>It is easy to divide or combine.</h3>
      </div>

      <div class='slide'>
        <h2>Data segments</h2>
        <ul>
          <li>Set of typed data.
          <li>Type signatures are in meta data segments.
          <li>Variable and extendable data structure.
          <li>Data segments are dominated by connected code segments.
          <li>Code segments atomically access connected data segments.
        </ul>
        <h3>It is easy to divide or combine.</h3>
      </div>

      <div class='slide'>
        <h2>Meta code / data segments</h2>
        <ul>
          <li>Execution contexts: Thread
          <li>Type signatures of data segments.
          <li>Data segment linkages: Pointer
          <li>Machine code
        </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'>
        <h2>Continuation based C (CbC)</h2>
        <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>Data segments are inplemented as C structures.
        </ul>
      </div>

      <div class='slide'>
        <h2>CbC sample</h2>
        <table border='1' align='center' width='80%'>
          <tr><td width='50%'>
              <pre class='small_code'>
__code f() {
    goto g();
}

__code g() {
    goto h();
}
              </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>There are no return values.
              </ul>
          </td></tr>
        </table>
      </div>

      <div class='slide'>
        <h2>CbC sample 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,
            struct Element* element) {
    allocate->after_append = Code2;
    element ->value        = 10;
    goto meta(context, Append);
}

__code append(struct Context* context, struct Allocate* allocate,
              struct List* list, struct Element* element) {
    if(list->head) {
        list->tail->next = element;
    } else {
        list->head = element;
    }
    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);
}
              </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.
              </ul>
          </td></tr>
        </table>
      </div>

      <div class='slide'>
        <h2>CbC compilers</h2>
        <ul>
          <li>Micro-C(one pass standalone compiler)
          <li>GCC(GNU Compiler Collection)
          <li>LLVM and Clang
            <ul>
              <li><font color='red'>The latest!</font>
            </ul>
        </ul>
      </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>Clang translate C/C++/Obj-C into LLVM IR.
          <li>LLVM translate LLVM IR into assembly code.
          <li>LLVM optimize all of intermidiate representation.
        </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>
        <ul>
          <li>clang AST
          <li>LLVM IR
          <li>SelectionDAG
          <li>Machine Code
          <li>MC Layer
        </ul>
        <h3 align='center'>Intermidiate representations are not modified.</h3>
      </div>

      <div class='slide'>
        <h2>Clang AST</h2>
        <ul>
          <li>Abstract Syntax Tree.
          <li>Representation of the source codes structure.
          <li>Basic node type: Stmt, Decl, Expr.
        </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.
        </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>Basic strategy of implementating</h2>
        <ul>
          <li>Code segments are implemented by C functions.
          <li>Data segments are implemented by C structs.
          <li>Transition is implemented by tail call elimination.
          <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 as __code type functions.
              <li>Handled like void functions.
            </ul>
          </tr>
        </table>
      </div>

      <div class='slide'>
        <h2>Prototype declaration generating</h2>
        <ul>
          <li>In CbC, programmer write a lot of code segments.
          <li>When function pointer's arguments are omitted, TCE was failed sometimes.
          <li>Automatically prototype declaration generating saves a lot of effort.
          <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.
          <li>If the declaration was not found, search definision and generate declaration.
            <ul>
              <li>Of course you can write declaration yourself too.
            </ul>
        </ul>
        <table border='1' width='80%' align='center'>
          <tr>
            <td>original input code
            <td>Clang genarates it
          </tr>
          <tr>
            <td><pre class='small_code'>
__code code1(int a, int b) {
     :
  goto code2(a,b);
}

__code code2(int a, int b){
     :
}
              </pre>
            <td><pre class='small_code'>
<font color='red'>__code code2(int a, int b);</font>
__code code1(int a, int b) {
     :
  goto code2(a,b);
}

__code code2(int a, int b){
     :
}
              </pre>
          </tr>
        </table>
      </div>

      <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.
        </ul>
        <table border='1' width='80%' align='center'>
          <tr>
            <td>original input code
            <td>Clang genarates it
          </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>Forcing Tail Call Elimination</h2>
        <p>TCE is enabled at CodeGen.</p>
        <p>TCE is act at SelectionDAGISel.</p>
        <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="60%"></div>
      </div>

      <div class='slide'>
        <!--        <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 elimination replace tail call's call instructions with jmp instructions.
          <li>Transitions are implemented by forced tail call elimination.
        </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>
        <ul>
          <li>Set tail flag at the code segments call.
          <li>Tailcallopt is enabled.
          <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>
      </div>

      <div class='slide'>
        <h2>Forcing Tail Call Elimination</h2>
        <ul>
          <li>Always add tail call elimination pass.
          <li>Tailcallopt is enabled in CbC.
          <li>Fast cc is used consistently in code segments call.
          <li>All the code segments return value type is void.
        </ul>
      </div>

      <div class='slide'>
        <h2>What is a Goto with environment?</h2>
        <ul>
          <li>Code segments can reutn C functions by Goto with environment.
            <ul>
              Code segment do not have return.
            </ul>
          <li>In the GCC, use nested functions.
          <li>In the LLVM and Clang, use setjmp and longjmp.
        </ul>
      </div>

      <div class='slide'>
        <h2>Sample code of Goto with environment</h2>
        <table width='100%'>
          <tr><td valign='top'>
              <ul>
                <li>Use new keywords __return and __environment.
                <li>__return is a code segment pointer for C functions.
                <li>__environment is a envitonment for C functions.
                <li>Code1 use a continuation with environments to return main function.
              </ul>
            <td style="border: double;">
              <pre class='small_code'><div class='highlight'>__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
  printf("code1 : code entry1\n");
  goto exit_code(n,exit_env);
}

int caller(){
  printf("caller : main1 entry\n");
  __code (*__ret)(int, void *) = <font color='red'>__return</font>;
  struct __CbC_env *__env = <font color='red'>__environment</font>;
  goto code1(1, __ret, __env);
  return 0;
}

int main(){
  int n;
  n = caller();
  printf("return = %d\n",n);
  return 0;
}      </div></pre>
          </tr>
        </table>
      </div>

      <div class='slide'>
        <h2>Implementing goto with environment</h2>
        <ul>
          <li>Include setjmp.h always.
          <li>Generate C struct for saving environment.
            <ul>
              <li>This struct is __environment.
            </ul>
          <li>Insert setjmp in C function.
          <li>Generate longjmp code segment as return.
            <ul>
              <li>This code segment is pointed by __return.
            </ul>
        </ul>
      </div>


      <div class='slide'>
        <h2>Compiling result</h2>
        <table width='100%' align='center' border='1'>
          <tr>
            <td valign='top'>
              <pre class='small_code'>

__code caller(int x)
{
  goto code1(1, x); // should be jmp
}
              </pre>
            <td>
              <pre class='small_code'>
_caller:                             ## @factorial
        .cfi_startproc
## BB#0:                                ## %entry
        subq    $24, %rsp
Ltmp5:
        .cfi_def_cfa_offset 32
        movl    $1, %eax
        movl    %edi, 20(%rsp)          ## 4-byte Spill
        movl    %eax, %edi
        movl    20(%rsp), %esi          ## 4-byte Reload
        addq    $24, %rsp
        <font color='red'>jmp</font>     _code1             ## TAILCALL
        .cfi_endproc
              </pre>
          </tr>
        </table>
        <ul>
          <li>Code1 should called by jmp instruction.
          <li>In assembly code, code1 called by jmp instruction.
          <li>Tail call elimination was forced.
          <li>If tail call elimination was failed, compiler output error messages.
        </ul>
      </div>
<!--
      <div class='slide'>
        <h2>Execution Result</h2>
        <ul>
          <li>Conv1 program.
            <ul>
              <li>Repeat calculation program.
              <li>Stack is defined in the program.
            </ul>
          <li>Select execution code by arguments.
            <ul>
              <li>1: not optimized.
              <li>2,3: optimized stack operation.
            </ul>
          <li>Inline optimization is omitted.
        </ul>
        <table width='80%' align='center' border='1'>
          <tr>
            <td width='30%'>
            <td>Argument 1
            <td>Argument 2
            <td>Argument 3
          </tr>
          <tr>
            <td>Micro-C
            <td>6.875
            <td>2.4562
            <td>3.105
          </tr>
          <tr>
            <td>GCC -O2
            <td>2.9438
            <td>0.955
            <td>1.265
          </tr>
          <tr>
            <td>LLVM and Clang -O0
            <td>5.835
            <td>4.1887
            <td>5.0625
          </tr>
          <tr>
            <td>LLVM and Clang -O2
            <td>3.3875
            <td>2.29
            <td>2.5087
          </tr>
        </table>
        <table width='80%' align='center' border='0'>
          <tr><td align='right'>unit : seconds</tr>
        </table>
        <ul>
          <li>LLVM and Clang compilers are faster than Micro-C when optimize is enabled.
          <li>CbC gets benefits from LLVM optimizations.
          <li>LLVM can compile CbC examples.
        </ul>
      </div>
-->
      <div class='slide'>
        <h2>Conclusion</h2>
        <ul>
          <li>CbC compiler on LLVM and Clang is implemented.
          <li>LLVM IR is not modified.
          <li>goto with environment is implemented by setjmp and longjmp.
          <li>Automatic prototype generating.
        </ul>
      </div>

      <div class='slide'>
        <h2>Future works</h2>
        <ul>
          <li>Write operating system in CbC.
            <ul>
              <li>Gears OS
            </ul>
          <li>Meta computation syntax.
          <li>More user friendly syntax.
          <li>Automitic data segment generator.
          <li>Signature for data segment.
        </ul>
      </div>

      <div class='slide'>
        <h2>LLVM and Clang's intermidiate representations</h2>
        <table border='1' align='center' width='80%'>
          <tr><td width='25%'>
              Name
            </td><td>
              Desctiption
          </td></tr>
          <tr><td>
              clang AST
            </td><td>
              Abstract Syntax Tree. It is a representation of the structure source codes.
          </td></tr>
          <tr><td>
              LLVM IR
            </td><td>
              The main intermidiate representation of LLVM. It has three diffirent forms: as an in-memory compiler IR, as an on-disk bitcode representation, and as a human readable assembly language representation.
          </td></tr>
          <tr><td>
              SelectionDAG
            </td><td>
              Directed Acyclic Graph. Its nodes indicate what operation the node performs and the operands to the operation.
          </td></tr>
          <tr><td>
              Machine Code
            </td><td>
              This representation is designed to support both an SSA representation for machine code, as well as register allocated, non-SSA form.
          </td></tr>
          <tr><td>
              MC Layer
            </td><td>
              It is used to represent and process code at the raw machine code level. User can some kinds of file (.s, .o, .ll, a.out) by same API.
          </td></tr>
        </table>
      </div>

    </div> <!-- presentation -->
  </body>
</html>
author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Sat, 04 Jul 2015 17:25:27 +0900
parents	81195c2fcf4a
children	40be058f9df8