Mercurial > hg > Papers > 2015 > kaito-lola
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. |