Mercurial > hg > Papers > 2017 > mitsuki-thesis
diff presen/index.html @ 10:86f6bb9be40a
add
| author | mir3636 |
|---|---|
| date | Wed, 15 Feb 2017 18:20:07 +0900 |
| parents | |
| children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presen/index.html Wed Feb 15 18:20:07 2017 +0900 @@ -0,0 +1,248 @@ +<!DOCTYPE html> + +<html> + <head> + <title>Presentation</title> + + <meta charset='utf-8'> + <script + src='./slides.js'></script> + </head> + + <style> + /* Your individual styles here, or just use inline styles if that’s + what you want. */ + + </style> + + <body style='display: none'> + <section class='slides layout-regular template-default'> + + <!-- + Your slides (<article>s) go here. Delete or comment out the + slides below. + --> + <article> + <h1>Implementation of CbC compiler on LLVM/clang 3.5</h1> + <h3 class="title">Kaito Tokumori 27 Feb 2014</h3> + <div align="right">Teacher : Shinji Kono</div> + </article> + + <article> + <h3>Introduction of CbC</h3> + <ul> + <li>CbC is programming language. + <li>CbC stands for Continuation based C. + <li>For pararell tasks. + <li>For state machine. + <li>For meta computation. + </ul> + </article> + + <article> + <h3>CbC compilers</h3> + <ul> + <li>Micro-C + <li>GCC + <li>LLVM/clang <font color="ff3300"><= New!!</font> + </ul> + </article> + + <article> + <h3>LLVM/clang??</h3> + <br> + <h3 class='yellow'>What??</h3> + <ul> + <li>LLVM is compiler framework. + <li>clang is C/C++/Obj-C compiler frontend. + </ul> + <h3 class='yellow'>Why??</h3> + <ul> + <li>Apple supported. + <li>OS X default compiler. + <li>LLVM IR (Intermidiate Representation). + </ul> + </article> + + <article> + <h3>Basic strategy of implementation</h3> + <ul> + <li>A code segment is implemented by normal function. + <li>Transition is implemented by forced tail call. + <li>Goto with environment is implemented by setjmp/longjmp. + <li><span class='red'>Do not modify intermidiate code.</span> + </ul> + </article> + + <article> + <h3>Problems</h3> + <ul> + <li>Code segment go-to moves between function.</li> + <li>LLVM IR jmp instruction is limited in a function.</li> + <li>LLVM IR can't express code segment jump...</li> + <br> + </ul> + <ul class="build"> + <li>But LLVM has tail call elimination,<br> + so there is a way to generate unlimited jmp instruction in LLVM.</li> + </ul> + </article> + + <article> + <h3>Solution</h3> + <pre>define fastcc void @factorial(i32 %x) #0 { +entry: + <span class="red">tail</span> call <span class="red">fastcc</span> void @factorial0(i32 1, i32 %x) + ret void +}</pre> + <ul> + <li>LLVM IR has call flag. + <li>Tail and fastcc flag are enable to tail call elimination! + <li><h3 class='yellow'>We can implement CbC compiler on LLVM!!</h3> + </ul> + </article> + + <article> + <h3>Structure of LLVM/clang</h3> + <div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div> + </article> + + <article> + <h3>Implementation on parser</h3> + <div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div> + <ul> + <li>Code segment type</li> + <li>Goto syntax</li> + </ul> + </article> + + <article> + <h3>Implementation on parser</h3> + <div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div> + <ul> + <!-- <li>Goto with environment</li> --> + <li>Include setjmp.h always. + <li>Generate C struct for saving environment. + <li>Insert setjmp statement. + <li>Generate longjmp code segment as return. + </ul> + </article> + + <article> + <h3>Implementation on code generator</h3> + <div align="center"><img src="fig/clang_llvm_structure.svg" width="600"></div> + <ul> + <!-- <li>Keep tail call elimination</li> --> + <li>Enable to tailcallopt LangOption. + <li>Add a return statement after code sgment call. + <li>Add fastcc calling convention. + <li>Enable to TailCallElim pass. + </ul> + </article> + + + <article class='smaller'> + <h3>Compiling result</h3> + <table border="0"> + <tbody> + <tr> + <td> + <pre>__code factorial(int x) +{ + goto factorial0(1, x); +} +</pre> + </td> + <td> + <pre>_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 + <span class="red">jmp _factorial0 ## TAILCALL</span> + .cfi_endproc</pre> + </td> + </tr> + </tbody> + </table> + <ul> + <li>Jmp instructions are in assembler source.</li> + </ul> + </article> + + <article> + <h3>Benchmark result</h3> + <table border="2" style="font-size:18pt;"> + <tbody> + <tr> + <td bgcolor="#8091B5"></td> + <td style="text-align: center;">no optimized code</td> + <td style="text-align: center;">optimized code A</td> + <td style="text-align: center;">optimized code B</td> + </tr> + <tr> + <td style="text-align: center;">Micro-C</td> + <td style="text-align: right;">6.06 s</td> + <td style="text-align: right;">2.21 s</td> + <td style="text-align: right;">2.40 s</td> + </tr> + <!-- <tr> --> + <!-- <td style="text-align: center;">GCC -O0</td> --> + <!-- <td style="text-align: right;">1.59 s</td> --> + <!-- <td style="text-align: right;">1.02 s</td> --> + <!-- <td style="text-align: right;">0.99 s</td> --> + <!-- </tr> --> + <tr> + <td style="text-align: center;">GCC -O2</td> + <td style="text-align: right;">1.59 s</td> + <td style="text-align: right;">1.02 s</td> + <td style="text-align: right;">0.99 s</td> + </tr> + <!-- <tr> --> + <!-- <td style="text-align: center;">LLVM -O0</td> --> + <!-- <td style="text-align: right;">5.52 s</td> --> + <!-- <td style="text-align: right;">3.95 s</td> --> + <!-- <td style="text-align: right;">4.64 s</td> --> + <!-- </tr> --> + <tr> + <td style="text-align: center;">LLVM -O2</td> + <td style="text-align: right;">5.52 s</td> + <td style="text-align: right;">3.95 s</td> + <td style="text-align: right;">4.64 s</td> + </tr> + </tbody> + </table> + <ul> + <li>LLVM can compile CbC examples like other CbC compilers.</li> + <li>LLVM is slower than other compilers but it is not important for us.</li> + </ul> + </article> + + <article> + <h3>Conclusion</h3> + <ul> + <li>We can use LLVM/clang to compile CbC code.</li> + <li>We did not modify LLVM IR to implement CbC compiler.</li> + </ul> + <h3 class='yellow'>Future</h3> + <ul> + <li>Data segment interface</li> + <li>Meta computation</li> + <li>Dynamic rewriting of a jmp</li> + <li>Generating specialized code</li> + </ul> + </article> + + </body> +</html>