Mercurial > hg > Papers > 2017 > mitsuki-thesis
view presen/index.html @ 15:1ba7fa1773d9
update
| author | mir3636 |
|---|---|
| date | Wed, 15 Feb 2017 22:07:09 +0900 |
| parents | 86f6bb9be40a |
| children |
line wrap: on
line source
<!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>