comparison presentation/presen.html @ 14:b9179e9084d9

spell check
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Sat, 04 Jul 2015 23:00:54 +0900
parents 607acd92b8eb
children bbbeecda034d
comparison
equal deleted inserted replaced
13:607acd92b8eb 14:b9179e9084d9
1 <!DOCTYPE html> 1 <!DOCTYPE html>
2 <html> 2 <html>
3 <head> 3 <head>
4 <meta charset='utf-8'> 4 <meta charset='utf-8'>
5 <title>Presen</title> 5 <title>Presentation</title>
6 <!-- style sheet links --> 6 <!-- style sheet links -->
7 <link rel="stylesheet/less" href="themes/blank/projection.css.less" media="screen,projection"> 7 <link rel="stylesheet/less" href="themes/blank/projection.css.less" media="screen,projection">
8 <link rel="stylesheet/less" href="themes/blank/screen.css.less" media="screen"> 8 <link rel="stylesheet/less" href="themes/blank/screen.css.less" media="screen">
9 <link rel="stylesheet/less" href="themes/blank/print.css.less" media="print"> 9 <link rel="stylesheet/less" href="themes/blank/print.css.less" media="print">
10 10
71 </div> 71 </div>
72 72
73 <div class='slide'> 73 <div class='slide'>
74 <h2>Objective</h2> 74 <h2>Objective</h2>
75 <ul> 75 <ul>
76 <li>Acheive Reliable computation 76 <li>Achieve Reliable computation
77 <li>Extract Concurrent Execution Automatically 77 <li>Extract Concurrent Execution Automatically
78 <li>Modify and Improve software in a Reliable way 78 <li>Modify and Improve software in a Reliable way
79 <li>Get more Reusablity 79 <li>Get more Reusablity
80 </ul> 80 </ul>
81 <h3>Introducing new units of programming</h3> 81 <h3>Introducing new units of programming</h3>
105 </ul> 105 </ul>
106 <h3>It is not easy to do this in the traditional units.</h3> 106 <h3>It is not easy to do this in the traditional units.</h3>
107 </div> 107 </div>
108 108
109 <div class='slide'> 109 <div class='slide'>
110 <h2>New programing units</h2> 110 <h2>New programming units</h2>
111 <ul> 111 <ul>
112 <li>Units of programming: code segments, data segments. 112 <li>Units of programming: code segments, data segments.
113 <li>Code segments are units of calculation. 113 <li>Code segments are units of calculation.
114 <li>Data segments are sets of typed data. 114 <li>Data segments are sets of typed data.
115 </ul> 115 </ul>
119 <h2>Code segments</h2> 119 <h2>Code segments</h2>
120 <ul> 120 <ul>
121 <li>Function from input data segments to output data segments. 121 <li>Function from input data segments to output data segments.
122 <li>Code segments have no states. 122 <li>Code segments have no states.
123 <li>Access in typed data in the data segments by name. 123 <li>Access in typed data in the data segments by name.
124 <li>Specify code segmnets to be executed using goto. 124 <li>Specify code segments to be executed using goto.
125 </ul> 125 </ul>
126 <h3>It is easy to divide or combine.</h3> 126 <h3>It is easy to divide or combine.</h3>
127 </div> 127 </div>
128 128
129 <div class='slide'> 129 <div class='slide'>
155 <li>An implementation of code segments. 155 <li>An implementation of code segments.
156 <li>CbC stands for Continuation based C. 156 <li>CbC stands for Continuation based C.
157 <li>Basic syntax is the same as the C, except __code and goto. 157 <li>Basic syntax is the same as the C, except __code and goto.
158 <li>__code is a type of code segment 158 <li>__code is a type of code segment
159 <li>Code segments end with parameterized goto. 159 <li>Code segments end with parameterized goto.
160 <li>Data segments are inplemented as C structures. 160 <li>Data segments are implemented as C structures.
161 </ul> 161 </ul>
162 </div> 162 </div>
163 163
164 <div class='slide'> 164 <div class='slide'>
165 <h2>code segment syntax</h2> 165 <h2>code segment syntax</h2>
231 <h2>LLVM and Clang's compilation flow</h2> 231 <h2>LLVM and Clang's compilation flow</h2>
232 <ul> 232 <ul>
233 <li>AST : Abstract Syntax Tree (C++ object) 233 <li>AST : Abstract Syntax Tree (C++ object)
234 <li>LLVM IR is Intermediate Representation (bit code). 234 <li>LLVM IR is Intermediate Representation (bit code).
235 <li>Clang translate C/C++/Obj-C into LLVM IR. 235 <li>Clang translate C/C++/Obj-C into LLVM IR.
236 <li>SelectionDAG : Codegenerator internal 236 <li>SelectionDAG : Code generator internal
237 <li>Machine Code : LLVM Machine code 237 <li>Machine Code : LLVM Machine code
238 </ul> 238 </ul>
239 <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div> 239 <div align="center"><img src="fig/clang_llvm_structure.svg" width="45%"></div>
240 </div> 240 </div>
241 241
250 </div> 250 </div>
251 251
252 <div class='slide'> 252 <div class='slide'>
253 <h2>CbC implementation strategy</h2> 253 <h2>CbC implementation strategy</h2>
254 <ul> 254 <ul>
255 <li>define special type __coee for code segments 255 <li>define special type __code for code segments
256 <li>no code segment prototyping (othewise it beomes quite messy ) 256 <li>no code segment prototyping (otherwise it becomes quite messy )
257 <li>code segments are implemented as tail call force functions 257 <li>code segments are implemented as tail call force functions
258 <li>Do not modify IR (Intermidiate representations ) 258 <li>Do not modify IR (Intermediate representations )
259 <li>goto statement is actualy a function call with following return statement <br> 259 <li>goto statement is actually a function call with following return statement <br>
260 goto f() --> { f() ; return; } 260 goto f() --> { f() ; return; }
261 <li>allow mixing code segments and normal function calls ( goto with environment ) 261 <li>allow mixing code segments and normal function calls ( goto with environment )
262 </ul> 262 </ul>
263 </div> 263 </div>
264 264
266 <h2>LLVM IR</h2> 266 <h2>LLVM IR</h2>
267 <ul> 267 <ul>
268 <li>Intermediate Representation (bit code). 268 <li>Intermediate Representation (bit code).
269 <li>Three forms: in-memory IR, bitcode stream, human readable language. 269 <li>Three forms: in-memory IR, bitcode stream, human readable language.
270 <li>it has precise type, data size, alignment 270 <li>it has precise type, data size, alignment
271 <li>funcion call flags : tail, fastcc, cc10, cc11, erlang, ghc 271 <li>function call flags : tail, fastcc, cc10, cc11, Erlang, ghc
272 </ul> 272 </ul>
273 <table width='100%'> 273 <table width='100%'>
274 <tr> 274 <tr>
275 <td style="border: double;"> 275 <td style="border: double;">
276 <pre class='code'> 276 <pre class='code'>
288 <div class='slide'> 288 <div class='slide'>
289 <h2>CbC implementation strategy</h2> 289 <h2>CbC implementation strategy</h2>
290 <ul> 290 <ul>
291 <li>Code segments are implemented by C functions with return-type __code. 291 <li>Code segments are implemented by C functions with return-type __code.
292 <li>Data segments are implemented by C structs. 292 <li>Data segments are implemented by C structs.
293 <li>Goto statement is implemented by seting tail call flag. 293 <li>Goto statement is implemented by setting tail call flag.
294 <li>Goto with environment is implemented by setjmp and longjmp. 294 <li>Goto with environment is implemented by setjmp and longjmp.
295 </ul> 295 </ul>
296 </div> 296 </div>
297 297
298 298
300 <h2>Prototype declaration generating</h2> 300 <h2>Prototype declaration generating</h2>
301 <ul> 301 <ul>
302 <li>In CbC, programmer write a lot of code segments. 302 <li>In CbC, programmer write a lot of code segments.
303 <li>Automatically prototype declarator support it. 303 <li>Automatically prototype declarator support it.
304 <!-- <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.--> 304 <!-- <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.-->
305 <li>If the declaration was not found, search definision and generate declaration. 305 <li>If the declaration was not found, search definition and generate declaration.
306 <ul> 306 <ul>
307 <li>Of course you can write declaration yourself too. 307 <li>Of course you can write declaration yourself too.
308 </ul> 308 </ul>
309 </ul> 309 </ul>
310 <table border='1' width='80%' align='center'> 310 <table border='1' width='80%' align='center'>
311 <tr> 311 <tr>
312 <td>original input code 312 <td>original input code
313 <td>Clang genarates it internaly 313 <td>Clang generates it internally
314 </tr> 314 </tr>
315 <tr> 315 <tr>
316 <td><pre class='small_code'> 316 <td><pre class='small_code'>
317 __code code1(int a, int b) { 317 __code code1(int a, int b) {
318 : 318 :
345 <li>It is one the requirement force to tail call elimination. 345 <li>It is one the requirement force to tail call elimination.
346 </ul> 346 </ul>
347 <table border='1' width='80%' align='center'> 347 <table border='1' width='80%' align='center'>
348 <tr> 348 <tr>
349 <td>original input code 349 <td>original input code
350 <td>Clang genarates it 350 <td>Clang generates it
351 </tr> 351 </tr>
352 <tr> 352 <tr>
353 <td><pre class='small_code'> 353 <td><pre class='small_code'>
354 __code code1() { 354 __code code1() {
355 : 355 :
367 </table> 367 </table>
368 </div> 368 </div>
369 369
370 <div class='slide'> 370 <div class='slide'>
371 <h2>Forcing Tail Call Elimination</h2> 371 <h2>Forcing Tail Call Elimination</h2>
372 <p>Tail call flang is set in CodeGen.</p> 372 <p>Tail call flag is set in CodeGen.</p>
373 <p>Ensure TCE in SelectionDAGISel.</p> 373 <p>Ensure TCE in SelectionDAGISel.</p>
374 <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="60%"></div> 374 <div align='center'><img src="fig/clang_llvm_slide_cg_DAG.svg" width="60%"></div>
375 </div> 375 </div>
376 376
377 <div class='slide'> 377 <div class='slide'>
390 <div class='slide'> 390 <div class='slide'>
391 <h2>Tail Call Elimination requirements</h2> 391 <h2>Tail Call Elimination requirements</h2>
392 <ul> 392 <ul>
393 <li>Set tail flag at the code segments call. 393 <li>Set tail flag at the code segments call.
394 <li>Tailcallopt path is enabled in the compiler. 394 <li>Tailcallopt path is enabled in the compiler.
395 <li>The caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc. 395 <li>The caller and callee's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
396 <li>Return value type has to be the same as the caller's. 396 <li>Return value type has to be the same as the caller's.
397 </ul> 397 </ul>
398 </div> 398 </div>
399 399
400 <div class='slide'> 400 <div class='slide'>
409 </div> 409 </div>
410 410
411 <div class='slide'> 411 <div class='slide'>
412 <h2>goto a code segment from a normal C function</h2> 412 <h2>goto a code segment from a normal C function</h2>
413 <ul> 413 <ul>
414 <li>Assume we have code segment g and normal funciton f 414 <li>Assume we have code segment g and normal function f
415 <li>simply goto g() in C function f() 415 <li>simply goto g() in C function f()
416 <li>goto g() never returns to function f 416 <li>goto g() never returns to function f
417 </ul> 417 </ul>
418 How to return to C from a code segment? 418 How to return to C from a code segment?
419 </div> 419 </div>
433 <table width='100%'> 433 <table width='100%'>
434 <tr><td valign='top'> 434 <tr><td valign='top'>
435 <ul> 435 <ul>
436 <li>Use new keywords __return and __environment. 436 <li>Use new keywords __return and __environment.
437 <li>__return is a code segment pointer for C functions. 437 <li>__return is a code segment pointer for C functions.
438 <li>__environment is a envitonment for C functions. 438 <li>__environment is a environment for C functions.
439 <li>Code1 use a continuation with environments to return main function. 439 <li>Code1 use a continuation with environments to return main function.
440 </ul> 440 </ul>
441 <td style="border: double;"> 441 <td style="border: double;">
442 <pre class='small_code'><div class='highlight'>__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){ 442 <pre class='small_code'><div class='highlight'>__code code1(int n,__code(*exit_code)(int,void *),void *exit_env){
443 printf("code1 : code entry1\n"); 443 printf("code1 : code entry1\n");
464 464
465 <div class='slide'> 465 <div class='slide'>
466 <h2>Implementation of goto with environment</h2> 466 <h2>Implementation of goto with environment</h2>
467 Several ways to implementation 467 Several ways to implementation
468 <ul> 468 <ul>
469 <li>setmp/longjmp (LLVM) 469 <li>setjmp/longjmp (LLVM)
470 <li>nested function closure with thread safe variable (GCC) 470 <li>nested function closure with thread safe variable (GCC)
471 <li>direct manipulation of frame pointer and return value (Micro-C) 471 <li>direct manipulation of frame pointer and return value (Micro-C)
472 </ul> 472 </ul>
473 </div> 473 </div>
474 474
601 <ul> 601 <ul>
602 <li>Gears OS 602 <li>Gears OS
603 </ul> 603 </ul>
604 <li>Meta computation syntax. 604 <li>Meta computation syntax.
605 <li>More user friendly syntax. 605 <li>More user friendly syntax.
606 <li>Automitic data segment generator. 606 <li>Automatic data segment generator.
607 <li>Signature for data segment. 607 <li>Signature for data segment.
608 </ul> 608 </ul>
609 </div> 609 </div>
610 610
611 <div class='slide'> 611 <div class='slide'>
612 <h2>LLVM and Clang's intermidiate representations</h2> 612 <h2>LLVM and Clang's intermediate representations</h2>
613 <table border='1' align='center' width='80%'> 613 <table border='1' align='center' width='80%'>
614 <tr><td width='25%'> 614 <tr><td width='25%'>
615 Name 615 Name
616 </td><td> 616 </td><td>
617 Desctiption 617 Description
618 </td></tr> 618 </td></tr>
619 <tr><td> 619 <tr><td>
620 clang AST 620 clang AST
621 </td><td> 621 </td><td>
622 Abstract Syntax Tree. It is a representation of the structure source codes. 622 Abstract Syntax Tree. It is a representation of the structure source codes.
623 </td></tr> 623 </td></tr>
624 <tr><td> 624 <tr><td>
625 LLVM IR 625 LLVM IR
626 </td><td> 626 </td><td>
627 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. 627 The main intermediate representation of LLVM. It has three different forms: as an in-memory compiler IR, as an on-disk bitcode representation, and as a human readable assembly language representation.
628 </td></tr> 628 </td></tr>
629 <tr><td> 629 <tr><td>
630 SelectionDAG 630 SelectionDAG
631 </td><td> 631 </td><td>
632 Directed Acyclic Graph. Its nodes indicate what operation the node performs and the operands to the operation. 632 Directed Acyclic Graph. Its nodes indicate what operation the node performs and the operands to the operation.