Mercurial > hg > Papers > 2015 > kaito-lola

comparison presentation/presen.html @ 9:41fe2e188445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Fri, 03 Jul 2015 20:06:57 +0900
parents a6907650e3e1
children 81195c2fcf4a
comparison
equal deleted inserted replaced
8:a6907650e3e1 9:41fe2e188445
163 <div class='slide'> 163 <div class='slide'>
164 <h2>CbC sample</h2> 164 <h2>CbC sample</h2>
165 <table border='1' align='center' width='80%'> 165 <table border='1' align='center' width='80%'>
166 <tr><td width='50%'> 166 <tr><td width='50%'>
167 <pre class='small_code'> 167 <pre class='small_code'>
168 <!-- 168 __code f() {
169 __code code2(struct Context* context, struct Allocate* allocate, struct Element* element) { 169 goto g();
170 allocate->after_append = Code3; 170 }
171 element ->value = 10; 171
172 goto meta(context, Append); 172 __code g() {
173 } 173 goto h();
174 --> 174 }
175 </pre>
176 </td><td valign='top'>
177 <ul>
178 <li>A part of list program.
179 <li>Code segments like C functions.
180 <li>CbC transition is goto so code segments do not return to previous.
181 <li>There are no return values.
182 </ul>
183 </td></tr>
184 </table>
185 </div>
186
187 <div class='slide'>
188 <h2>CbC sample</h2>
189 <table border='1' align='center' width='80%'>
190 <tr><td width='50%'>
191 <pre class='small_code'>
175 __code code(struct Context* context, struct Allocate* allocate, struct Element* element) { 192 __code code(struct Context* context, struct Allocate* allocate, struct Element* element) {
176 allocate->after_append = Code2; 193 allocate->after_append = Code2;
177 element ->value = 10; 194 element ->value = 10;
178 goto meta(context, Append); 195 goto meta(context, Append);
179 } 196 }
180 197
181 __code append(struct Context* context, struct Allocate* allocate, struct List* list, struct Element* element) { 198 __code append(struct Context* context, struct Allocate* allocate,
199 struct List* list, struct Element* element) {
182 if(list->head) { 200 if(list->head) {
183 list->tail->next = element; 201 list->tail->next = element;
184 } else { 202 } else {
185 list->head = element; 203 list->head = element;
186 } 204 }
215 </ul> 233 </ul>
216 </ul> 234 </ul>
217 </div> 235 </div>
218 236
219 <div class='slide'> 237 <div class='slide'>
220 <h2>What is LLVM?</h2> 238 <h2>What are LLVM and Clang?</h2>
221 <ul> 239 <ul>
222 <li>Compiler frameworks. 240 <li>Compiler frameworks.
223 <li>has a intermidiate language which is called LLVM IR, LLVM language or LLVM bitcode. 241 <li>has a intermidiate language which is called LLVM IR, LLVM language or LLVM bitcode.
224 <li>Translates LLVM IR to assembly language. 242 <li>Translates LLVM IR to assembly language.
225 <li>Many kinds of optimization. 243 <li>Many kinds of optimization.
227 <li>Clang uses LLVM for compiler backend. 245 <li>Clang uses LLVM for compiler backend.
228 </ul> 246 </ul>
229 </div> 247 </div>
230 248
231 <div class='slide'> 249 <div class='slide'>
232 <h2>What is Clang?</h2> 250 <h2>Why?</h2>
233 <ul>
234 <li>C, C++ and Obj-C compiler frontend.
235 <li>Uses LLVM for compiler backend.
236 </ul>
237 </div>
238
239 <div class='slide'>
240 <h2>Why LLVM?</h2>
241 <ul> 251 <ul>
242 <li>Apple supported. 252 <li>Apple supported.
243 <li>OS X default compiler. 253 <li>OS X default compiler.
244 <li>LLVM IR's documantation is useful and readable. 254 <li>LLVM IR has readable documents.
245 <li>LLVM and Clang has readable documantation of their source codes. 255 <li>More readable and modifiable than GCC.
246 </ul> 256 </ul>
247 </div> 257 </div>
248 258
249 <div class='slide'> 259 <div class='slide'>
250 <h2>LLVM and Clang's compilation flow</h2> 260 <h2>LLVM and Clang's compilation flow</h2>
252 <li>Clang translate C/C++/Obj-C into LLVM IR. 262 <li>Clang translate C/C++/Obj-C into LLVM IR.
253 <li>LLVM translate LLVM IR into assembly code. 263 <li>LLVM translate LLVM IR into assembly code.
254 <li>LLVM optimize all of intermidiate representation. 264 <li>LLVM optimize all of intermidiate representation.
255 </ul> 265 </ul>
256 <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div> 266 <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
267 </div>
268
269 <div class='slide'>
270 <h2>LLVM and Clang's intermidiate representations</h2>
271 <ul>
272 <li>clang AST
273 <li>LLVM IR
274 <li>SelectionDAG
275 <li>Machine Code
276 <li>MC Layer
277 </ul>
278 <h3 align='center'>Intermidiate representations are not modified.</h3>
279 </div>
280
281 <div class='slide'>
282 <h2>Clang AST</h2>
283 <ul>
284 <li>Abstract Syntax Tree.
285 <li>Representation of the source codes structure.
286 <li>Basic node type: Stmt, Decl, Expr.
287 </ul>
288 </div>
289
290 <div class='slide'>
291 <h2>LLVM IR</h2>
292 <ul>
293 <li>The main intermidiate representation.
294 <li>LLVM translate it into assembly codes.
295 <li>Three forms: in-memory compiler IR, on-disk bitcode, assembly language.
296 </ul>
297 <table width='100%'>
298 <tr>
299 <td style="border: double;">
300 <pre class='code'>
301 define fastcc void @factorial(i32 %x) #0 {
302 entry:
303 tail call fastcc void @factorial0(i32 1, i32 %x)
304 ret void
305 }
306 </pre>
307 </td>
308 </tr>
309 </table>
310 </div>
311
312 <div class='slide'>
313 <h2>Basic strategy of implementating</h2>
314 <ul>
315 <li>Code segments are implemented by C functions.
316 <li>Data segments are implemented by C structs.
317 <li>Transition is implemented by forced tail call elimination.
318 <li>Goto with environment is implemented by setjmp and longjmp.
319 </ul>
320 </div>
321
322 <div class='slide'>
323 <h2>Implementating CbC compiler in LLVM and Clang</h2>
324 <ul>
325 <li>__code type.
326 <li>Goto syntax.
327 <li>Force to do tail call elimination.
328 <li>Goto with environment.
329 <li>Automatically prototype declatation genarating.
330 </ul>
331 </div>
332
333 <div class='slide'>
334 <h2>Parser</h2>
335 <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
336 <ul>
337 <li>__code type
338 <li>Prototype declaration generating
339 <li>Goto syntax for transitions
340 </ul>
341 </div>
342
343 <div class='slide'>
344 <h2>__code type</h2>
345 <table width='100%'>
346 <tr>
347 <ul>
348 <li>Code segments as __code type functions.
349 <li>Handled like void functions.
350 </ul>
351 </tr>
352 </table>
353 </div>
354
355 <div class='slide'>
356 <h2>Prototype declaration generating</h2>
357 <ul>
358 <li>In CbC, programmer write a lot of code segments.
359 <li>When function pointer's arguments are omitted, TCE was failed sometimes.
360 <li>Automatically prototype declaration generating saves a lot of effort.
361 <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.
362 <li>If the declaration was not found, search definision and generate declaration.
363 <ul>
364 <li>Of course you can write declaration yourself too.
365 </ul>
366 </ul>
367 <table border='1' width='80%' align='center'>
368 <tr>
369 <td>original input code
370 <td>Clang genarates it
371 </tr>
372 <tr>
373 <td><pre class='small_code'>
374 __code code1(int a, int b) {
375 :
376 goto code2(a,b);
377 }
378
379 __code code2(int a, int b){
380 :
381 }
382 </pre>
383 <td><pre class='small_code'>
384 <font color='red'>__code code2(int a, int b);</font>
385 __code code1(int a, int b) {
386 :
387 goto code2(a,b);
388 }
389
390 __code code2(int a, int b){
391 :
392 }
393 </pre>
394 </tr>
395 </table>
396 </div>
397
398 <div class='slide'>
399 <h2>goto syntax for transition</h2>
400 <table width='100%'>
401 <tr><td>
402 <ul>
403 <li>New goto syntax for transition.
404 <li>Generate normal function call.
405 <li>Tail call elimination is forced later.
406 </ul>
407 </tr>
408 </table>
409 </div>
410
411 <div class='slide'>
412 <h2>goto syntax for transition</h2>
413 <ul>
414 <li>Add return statement after goto transition.
415 <li>It is one the requirement force to tail call elimination.
416 </ul>
417 <table border='1' width='80%' align='center'>
418 <tr>
419 <td>original input code
420 <td>Clang genarates it
421 </tr>
422 <tr>
423 <td><pre class='small_code'>
424 __code code1() {
425 :
426 goto code2();
427 }
428 </pre>
429 <td><pre class='small_code'>
430 void code1() {
431 :
432 code2();
433 <font color='red'>return;</font>
434 }
435 </pre>
436 </tr>
437 </table>
438 </div>
439
440 <div class='slide'>
441 <h2>Forcing Tail Call Elimination</h2>
442 <p>TCE is enabled at CodeGen.</p>
443 <p>TCE is act at SelectionDAGISel.</p>
444 <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="70%"></div>
445 </div>
446
447 <div class='slide'>
448 <h2>Jmp instruction based transition</h2>
449 <ul>
450 <li>Tail call is immediately followed by return.
451 <li>Tail call elimination replace tail call's call instructions with jmp instructions.
452 <li>Transitions are implemented by forced tail call elimination.
453 </ul>
454 <div align='center'><img src="fig/TCE.svg" width="40%"></div>
455 </div>
456
457
458 <div class='slide'>
459 <h2>Forcing Tail Call Elimination</h2>
460 <ul>
461 <li>LLVM IR has function call flags.
462 <li>tail mean it is tail call.
463 <li>Calling convention tell compiler how callee functions receive parameters from their caller.
464 </ul>
465 <table width='100%'>
466 <tr>
467 <td style="border: double;">
468 <pre class='code'>
469 define fastcc void @factorial(i32 %x) #0 {
470 entry:
471 <font color='red'>tail</font> call <font color='red'>fastcc</font> void @factorial0(i32 1, i32 %x)
472 ret void
473 }
474 </pre>
475 </td>
476 </tr>
477 </table>
478 <div align='center'><h3>Use them for force to tail call elimination.</h3></div>
479 </div>
480
481 <div class='slide'>
482 <h2>Forcing Tail Call Elimination</h2>
483 <p>Tail Call Elimination requirements</p>
484 <ul>
485 <li>Set tail flag at the code segments call.
486 <li>Tailcallopt is enabled.
487 <li>The caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
488 <li>Return value type has to be the same as the caller's.
489 </ul>
490 </div>
491
492 <div class='slide'>
493 <h2>Forcing Tail Call Elimination</h2>
494 <ul>
495 <li>Always add tail call elimination pass.
496 <li>Tailcallopt is enabled in CbC.
497 <li>Fast cc is used consistently in code segments call.
498 <li>All the code segments return value type is void.
499 </ul>
500 </div>
501
502 <div class='slide'>
503 <h2>What is a Goto with environment?</h2>
504 <ul>
505 <li>Code segments do not have environment but C functions have.
506 <li>Code segments can reutn C functions by Goto with environment.
507 <li>In the GCC, use nested functions.
508 <li>In the LLVM and Clang, use setjmp and longjmp.
509 </ul>
510 </div>
511
512 <div class='slide'>
513 <h2>Sample code of Goto with environment</h2>
514 <table width='100%'>
515 <tr><td valign='top'>
516 <ul>
517 <li>Use new keywords __return and __environment.
518 <li>__return is a code segment pointer for C functions.
519 <li>__environment is a envitonment for C functions.
520 <li>Code1 use a continuation with environments to return main function.
521 </ul>
522 <td style="border: double;">
523 <pre class='small_code'><div class='highlight'>__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
524 printf("code1 : code entry1\n");
525 goto exit_code(n,exit_env);
526 }
527
528 int caller(){
529 printf("caller : main1 entry\n");
530 __code (*__ret)(int, void *) = <font color='red'>__return</font>;
531 struct __CbC_env *__env = <font color='red'>__environment</font>;
532 goto code1(1, __ret, __env);
533 return 0;
534 }
535
536 int main(){
537 int n;
538 n = caller();
539 printf("return = %d\n",n);
540 return 0;
541 } </div></pre>
542 </tr>
543 </table>
544 </div>
545
546 <div class='slide'>
547 <h2>Implementing goto with environment</h2>
548 <ul>
549 <li>Include setjmp.h always.
550 <li>Generate C struct for saving environment.
551 <ul>
552 <li>This struct is __environment.
553 </ul>
554 <li>Insert setjmp in C function.
555 <li>Generate longjmp code segment as return.
556 <ul>
557 <li>This code segment is pointed by __return.
558 </ul>
559 </ul>
560 </div>
561
562
563 <div class='slide'>
564 <h2>Compiling result</h2>
565 <table width='100%' align='center' border='1'>
566 <tr>
567 <td valign='top'>
568 <pre class='small_code'>
569
570 __code caller(int x)
571 {
572 goto code1(1, x); // should be jmp
573 }
574 </pre>
575 <td>
576 <pre class='small_code'>
577 _caller: ## @factorial
578 .cfi_startproc
579 ## BB#0: ## %entry
580 subq $24, %rsp
581 Ltmp5:
582 .cfi_def_cfa_offset 32
583 movl $1, %eax
584 movl %edi, 20(%rsp) ## 4-byte Spill
585 movl %eax, %edi
586 movl 20(%rsp), %esi ## 4-byte Reload
587 addq $24, %rsp
588 <font color='red'>jmp</font> _code1 ## TAILCALL
589 .cfi_endproc
590 </pre>
591 </tr>
592 </table>
593 <ul>
594 <li>Code1 should called by jmp instruction.
595 <li>In assembly code, code1 called by jmp instruction.
596 <li>Tail call elimination was forced.
597 <li>If tail call elimination was failed, compiler output error messages.
598 </ul>
599 </div>
600 <!--
601 <div class='slide'>
602 <h2>Execution Result</h2>
603 <ul>
604 <li>Conv1 program.
605 <ul>
606 <li>Repeat calculation program.
607 <li>Stack is defined in the program.
608 </ul>
609 <li>Select execution code by arguments.
610 <ul>
611 <li>1: not optimized.
612 <li>2,3: optimized stack operation.
613 </ul>
614 <li>Inline optimization is omitted.
615 </ul>
616 <table width='80%' align='center' border='1'>
617 <tr>
618 <td width='30%'>
619 <td>Argument 1
620 <td>Argument 2
621 <td>Argument 3
622 </tr>
623 <tr>
624 <td>Micro-C
625 <td>6.875
626 <td>2.4562
627 <td>3.105
628 </tr>
629 <tr>
630 <td>GCC -O2
631 <td>2.9438
632 <td>0.955
633 <td>1.265
634 </tr>
635 <tr>
636 <td>LLVM and Clang -O0
637 <td>5.835
638 <td>4.1887
639 <td>5.0625
640 </tr>
641 <tr>
642 <td>LLVM and Clang -O2
643 <td>3.3875
644 <td>2.29
645 <td>2.5087
646 </tr>
647 </table>
648 <table width='80%' align='center' border='0'>
649 <tr><td align='right'>unit : seconds</tr>
650 </table>
651 <ul>
652 <li>LLVM and Clang compilers are faster than Micro-C when optimize is enabled.
653 <li>CbC gets benefits from LLVM optimizations.
654 <li>LLVM can compile CbC examples.
655 </ul>
656 </div>
657 -->
658 <div class='slide'>
659 <h2>Conclusion</h2>
660 <ul>
661 <li>CbC compiler on LLVM and Clang is implemented.
662 <li>LLVM IR is not modified.
663 <li>goto with environment is implemented by setjmp and longjmp.
664 <li>Automatic prototype generating.
665 </ul>
666 </div>
667
668 <div class='slide'>
669 <h2>Future works</h2>
670 <ul>
671 <li>Write operating system in CbC.
672 <li>Meta computation syntax.
673 <li>Automitic data segment generator.
674 </ul>
257 </div> 675 </div>
258 676
259 <div class='slide'> 677 <div class='slide'>
260 <h2>LLVM and Clang's intermidiate representations</h2> 678 <h2>LLVM and Clang's intermidiate representations</h2>
261 <table border='1' align='center' width='80%'> 679 <table border='1' align='center' width='80%'>
292 </table> 710 </table>
293 <br> 711 <br>
294 <p align='center' class='step emphasize'>Intermidiate representations are not modified.</p> 712 <p align='center' class='step emphasize'>Intermidiate representations are not modified.</p>
295 </div> 713 </div>
296 714
297 <div class='slide'>
298 <h2>Problems on implementating</h2>
299 <ul>
300 <li>How to implement code segments and data segments?
301 <li>How to implement jmp instruction based transition?
302 <li>How to implement goto with environment syntax?
303 </ul>
304 </div>
305
306 <div class='slide'>
307 <h2>Basic strategy of implementating</h2>
308 <ul>
309 <li>Code segments are implemented by C functions.
310 <li>Data segments are implemented by C structs.
311 <li>Transition is implemented by forced tail call elimination.
312 <li>Goto with environment is implemented by setjmp and longjmp.
313 </ul>
314 </div>
315
316 <div class='slide'>
317 <h2>Implementating CbC compiler in LLVM and Clang</h2>
318 <ul>
319 <li>add __code type for code segment.
320 <li>add goto syntax for transition.
321 <li>force to tail call elimination.
322 <li>goto with environment.
323 <li>automatically prototype declatation genarating.
324 </ul>
325 </div>
326
327 <div class='slide'>
328 <h2>__code type</h2>
329 <p>modify parser.</p>
330 <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
331 </div>
332
333 <div class='slide'>
334 <h2>__code type</h2>
335 <table width='100%'>
336 <tr><td>
337 <ul>
338 <li>Clang and LLVM handle code segments as __code type functions.
339 <li>Code segments do not have return value so they are handled like void functions.
340 <li>The following code is the place where Clang parse a __code type.
341 <li>DS.SetTypeSpecType() set AST nodes __code type.
342 </ul>
343 </tr>
344 <tr>
345 <td style="border: double;">
346 <pre class='code'>
347 case tok::kw___code: {
348 LangOptions* LOP;
349 LOP = const_cast<LangOptions*>(&getLangOpts());
350 LOP->HasCodeSegment = 1;
351 isInvalid = <font color='red'>DS.SetTypeSpecType(DeclSpec::TST___code, Loc, PrevSpec, DiagID);</font>
352 break;
353 }</pre>
354 </tr>
355 </table>
356 </div>
357
358 <div class='slide'>
359 <h2>goto syntax for transition</h2>
360 <p>modify parser.</p>
361 <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
362 </div>
363
364 <div class='slide'>
365 <h2>goto syntax for transition</h2>
366 <table width='100%'>
367 <tr><td>
368 <ul>
369 <li>Add new goto syntax for transition.
370 <li>Jmp instraction based transition is enabled by tail call elimination.
371 <li>In this part, clang create AST for normal function call and force to tail call elimination later.
372 <li>The following code is the place where CbC goto was parsed.
373 <li>If the goto is not for C syntax, we judge it is for CbC syntax.
374 </ul>
375 </tr>
376 <tr>
377 <td style="border: double;">
378 <pre class='code'>
379 case tok::kw_goto:
380 #ifndef noCbC
381 if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) &&
382 NextToken().isNot(tok::star)) {
383 SemiError = "goto code segment";
384 return ParseCbCGotoStatement(Attrs, Stmts);
385 }
386 #endif
387 Res = ParseGotoStatement();
388 SemiError = "goto";
389 break;</pre>
390 </tr>
391 </table>
392 </div>
393
394 <div class='slide'>
395 <h2>goto syntax for transition</h2>
396 <ul>
397 <li>Add return statement after goto transition.
398 <li>It is one the requirement force to tail call elimination.
399 </ul>
400 <table border='1' width='80%' align='center'>
401 <tr>
402 <td>original input code
403 <td>Clang genarates it
404 </tr>
405 <tr>
406 <td><pre class='small_code'>
407 __code code1() {
408 :
409 goto code2();
410 }
411 </pre>
412 <td><pre class='small_code'>
413 void code1() {
414 :
415 code2();
416 <font color='red'>return;</font>
417 }
418 </pre>
419 </tr>
420 </table>
421 </div>
422
423 <div class='slide'>
424 <h2>Jmp instruction based transition</h2>
425 <ul>
426 <li>It is implemented by Tail Call Elimination (TCE).
427 <li>TCE is one of the optimization.
428 <li>If the function call is immediately followed by return, it is tail call.
429 <li>TCE replace tail call's call instructions with jmp instructions.
430 <li>Code segments transition is implemented by forced tail call elimination.
431 </ul>
432 <div align='center'><img src="fig/TCE.svg" width="40%"></div>
433 </div>
434
435 <div class='slide'>
436 <h2>Forcing Tail Call Elimination</h2>
437 <p>TCE is enabled at CodeGen.</p>
438 <p>TCE is act at SelectionDAGISel.</p>
439 <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="70%"></div>
440 </div>
441
442 <div class='slide'>
443 <h2>Forcing Tail Call Elimination</h2>
444 <ul>
445 <li>LLVM IR has function call flags.
446 <li>tail mean it is tail call.
447 <li>Calling convention tell compiler how callee functions receive parameters from their caller.
448 </ul>
449 <table width='100%'>
450 <tr>
451 <td style="border: double;">
452 <pre class='code'>
453 define fastcc void @factorial(i32 %x) #0 {
454 entry:
455 <font color='red'>tail</font> call <font color='red'>fastcc</font> void @factorial0(i32 1, i32 %x)
456 ret void
457 }
458 </pre>
459 </td>
460 </tr>
461 </table>
462 <div align='center'><h3>Use them for force to tail call elimination.</h3></div>
463 </div>
464
465 <div class='slide'>
466 <h2>Forcing Tail Call Elimination</h2>
467 <p>We have to meet the following requirements.</p>
468 <ul>
469 <li>set tail flag at the code segments call.
470 <li>tailcallopt is enabled.
471 <li>the caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
472 <li>return value type has to be the same as the caller's.
473 </ul>
474 </div>
475
476 <div class='slide'>
477 <h2>Forcing Tail Call Elimination</h2>
478 <p>We met them by following ways.</p>
479 <ul>
480 <li>Always add tail call elimination pass and set flag at the code segments call.
481 <li>If the input code contains code segment, tailcallopt is enabled automatically.
482 <li>Fast cc is used consistently in code segments call.
483 <li>All the code segments return value type is void.
484 </ul>
485 </div>
486
487 <div class='slide'>
488 <h2>Goto with environment</h2>
489 <p>Goto with environment is enabled by modifying parser.</p>
490 <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
491 </div>
492
493 <div class='slide'>
494 <h2>What is a Goto with environment?</h2>
495 <ul>
496 <li>Code segments do not have environment cut functions have.
497 <li>Usually, code segments can't return to functions.
498 <li>Goto with environment enable to it.
499 <li>In the GCC, use nested functions to implementing.
500 <li>In the LLVM and Clang, use setjmp and longjmp to implementing.
501 </ul>
502 </div>
503
504 <div class='slide'>
505 <h2>Sample code of Goto with environment</h2>
506 <table width='100%'>
507 <tr><td valign='top'>
508 <ul>
509 <li>Use new keywords __return and __environment.
510 <li>__return is a code segment pointer for C functions.
511 <li>__environment is a envitonment for C functions.
512 <li>Code1 use a continuation with environments to return main function.
513 </ul>
514 <td style="border: double;">
515 <pre class='small_code'><div class='highlight'>__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
516 printf("code1 : code entry1\n");
517 goto exit_code(n,exit_env);
518 }
519
520 int caller(){
521 printf("caller : main1 entry\n");
522 __code (*__ret)(int, void *) = <font color='red'>__return</font>;
523 struct __CbC_env *__env = <font color='red'>__environment</font>;
524 goto code1(1, __ret, __env);
525 return 0;
526 }
527
528 int main(){
529 int n;
530 n = caller();
531 printf("return = %d\n",n);
532 return 0;
533 } </div></pre>
534 </tr>
535 </table>
536 </div>
537
538 <div class='slide'>
539 <h2>Implementing goto with environment</h2>
540 <ul>
541 <li>Include setjmp.h always.
542 <li>Generate C struct for saving environment.
543 <ul>
544 <li>This struct is __environment.
545 </ul>
546 <li>Insert setjmp in C function.
547 <li>Generate longjmp code segment as return.
548 <ul>
549 <li>This code segment is pointed by __return.
550 </ul>
551 </ul>
552 </div>
553
554 <div class='slide'>
555 <h2>Prototype declaration generating</h2>
556 <p>modify parser.</p>
557 <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
558 </div>
559
560 <div class='slide'>
561 <h2>Prototype declaration generating</h2>
562 <ul>
563 <li>In CbC, programmer write a lot of code segments.
564 <li>When function pointer's arguments are omitted, TCE was failed sometimes.
565 <li>Automatically prototype declaration generating saves a lot of effort.
566 <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.
567 <li>If the declaration was not found, search definision and generate declaration.
568 <ul>
569 <li>Of course you can write declaration yourself too.
570 </ul>
571 <!-- <li>This feature is important to code segment transition.-->
572 </ul>
573 <table border='1' width='80%' align='center'>
574 <tr>
575 <td>original input code
576 <td>Clang genarates it
577 </tr>
578 <tr>
579 <td><pre class='small_code'>
580 __code code1(int a, int b) {
581 :
582 goto code2(a,b);
583 }
584
585 __code code2(int a, int b){
586 :
587 }
588 </pre>
589 <td><pre class='small_code'>
590 <font color='red'>__code code2(int a, int b);</font>
591 __code code1(int a, int b) {
592 :
593 goto code2(a,b);
594 }
595
596 __code code2(int a, int b){
597 :
598 }
599 </pre>
600 </tr>
601 </table>
602 </div>
603
604 <div class='slide'>
605 <h2>Compiling result</h2>
606 <table width='100%' align='center' border='1'>
607 <tr>
608 <td valign='top'>
609 <pre class='small_code'>
610
611 __code caller(int x)
612 {
613 goto code1(1, x); // should be jmp
614 }
615 </pre>
616 <td>
617 <pre class='small_code'>
618 _caller: ## @factorial
619 .cfi_startproc
620 ## BB#0: ## %entry
621 subq $24, %rsp
622 Ltmp5:
623 .cfi_def_cfa_offset 32
624 movl $1, %eax
625 movl %edi, 20(%rsp) ## 4-byte Spill
626 movl %eax, %edi
627 movl 20(%rsp), %esi ## 4-byte Reload
628 addq $24, %rsp
629 <font color='red'>jmp</font> _code1 ## TAILCALL
630 .cfi_endproc
631 </pre>
632 </tr>
633 </table>
634 <ul>
635 <li>Code1 should called by jmp instruction.
636 <li>In assembly code, code1 called by jmp instruction.
637 <li>Tail call elimination was forced.
638 <li>If tail call elimination was failed, compiler output error messages.
639 </ul>
640 </div>
641
642 <div class='slide'>
643 <h2>Execution Result</h2>
644 <ul>
645 <li>Conv1 program.
646 <ul>
647 <li>Repeat calculation program.
648 <li>Stack is defined in the program.
649 </ul>
650 <li>Select execution code by arguments.
651 <ul>
652 <li>1: not optimized.
653 <li>2,3: optimized stack operation.
654 </ul>
655 <li>Inline optimization is omitted.
656 </ul>
657 <table width='80%' align='center' border='1'>
658 <tr>
659 <td width='30%'>
660 <td>Argument 1
661 <td>Argument 2
662 <td>Argument 3
663 </tr>
664 <tr>
665 <td>Micro-C
666 <td>6.875
667 <td>2.4562
668 <td>3.105
669 </tr>
670 <tr>
671 <td>GCC -O2
672 <td>2.9438
673 <td>0.955
674 <td>1.265
675 </tr>
676 <tr>
677 <td>LLVM and Clang -O0
678 <td>5.835
679 <td>4.1887
680 <td>5.0625
681 </tr>
682 <tr>
683 <td>LLVM and Clang -O2
684 <td>3.3875
685 <td>2.29
686 <td>2.5087
687 </tr>
688 </table>
689 <table width='80%' align='center' border='0'>
690 <tr><td align='right'>unit : seconds</tr>
691 </table>
692 <ul>
693 <li>LLVM and Clang compilers are faster than Micro-C when optimize is enabled.
694 <li>CbC gets benefits from LLVM optimizations.
695 <li>LLVM can compile CbC examples.
696 </ul>
697 </div>
698
699 <div class='slide'>
700 <h2>Conclusion</h2>
701 <ul>
702 <li>CbC compiler on LLVM and Clang is implemented.
703 <li>LLVM IR is not modified.
704 <li>goto with environment is implemented by setjmp and longjmp.
705 <li>Automatic prototype generating.
706 </ul>
707 </div>
708
709 <div class='slide'>
710 <h2>Future works</h2>
711 <ul>
712 <li>Write operating system in CbC.
713 <li>Meta computation syntax.
714 <li>Automitic data segment generator.
715 </ul>
716 </div>
717
718 </div> <!-- presentation --> 715 </div> <!-- presentation -->
719 </body> 716 </body>
720 </html> 717 </html>