Mercurial > hg > Papers > 2015 > kaito-lola

changeset 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
files presentation/presen.html
diffstat 1 files changed, 183 insertions(+), 186 deletions(-) [+]
line wrap: on
line diff
--- a/presentation/presen.html	Fri Jul 03 13:38:40 2015 +0900
+++ b/presentation/presen.html	Fri Jul 03 20:06:57 2015 +0900
@@ -165,20 +165,38 @@
         <table border='1' align='center' width='80%'>
           <tr><td width='50%'>
               <pre class='small_code'>
-<!--
-__code code2(struct Context* context, struct Allocate* allocate, struct Element* element) {
-    allocate->after_append = Code3;
-    element ->value        = 10;
-    goto meta(context, Append);
+__code f() {
+    goto g();
+}
+
+__code g() {
+    goto h();
 }
-  -->
+              </pre>
+            </td><td valign='top'>
+              <ul>
+                <li>A part of list program.
+                <li>Code segments like C functions.
+                <li>CbC transition is goto so code segments do not return to previous.
+                <li>There are no return values.
+              </ul>
+          </td></tr>
+        </table>
+      </div>
+
+      <div class='slide'>
+        <h2>CbC sample</h2>
+        <table border='1' align='center' width='80%'>
+          <tr><td width='50%'>
+              <pre class='small_code'>
 __code code(struct Context* context, struct Allocate* allocate, struct Element* element) {
     allocate->after_append = Code2;
     element ->value        = 10;
     goto meta(context, Append);
 }
 
-__code append(struct Context* context, struct Allocate* allocate, struct List* list, struct Element* element) {
+__code append(struct Context* context, struct Allocate* allocate,
+              struct List* list, struct Element* element) {
     if(list->head) {
         list->tail->next = element;
     } else {
@@ -217,7 +235,7 @@
       </div>
 
       <div class='slide'>
-        <h2>What is LLVM?</h2>
+        <h2>What are LLVM and Clang?</h2>
         <ul>
           <li>Compiler frameworks.
           <li>has a intermidiate language which is called LLVM IR, LLVM language or LLVM bitcode.
@@ -229,20 +247,12 @@
       </div>
 
       <div class='slide'>
-        <h2>What is Clang?</h2>
-        <ul>
-          <li>C, C++ and Obj-C compiler frontend.
-          <li>Uses LLVM for compiler backend.
-        </ul>
-      </div>
-
-      <div class='slide'>
-        <h2>Why LLVM?</h2>
+        <h2>Why?</h2>
         <ul>
           <li>Apple supported.
           <li>OS X default compiler.
-          <li>LLVM IR's documantation is useful and readable.
-          <li>LLVM and Clang has readable documantation of their source codes.
+          <li>LLVM IR has readable documents.
+          <li>More readable and modifiable than GCC.
         </ul>
       </div>
 
@@ -258,49 +268,45 @@
 
       <div class='slide'>
         <h2>LLVM and Clang's intermidiate representations</h2>
-        <table border='1' align='center' width='80%'>
-          <tr><td width='25%'>
-              Name
-            </td><td>
-              Desctiption
-          </td></tr>
-          <tr><td>
-              clang AST
-            </td><td>
-              Abstract Syntax Tree. It is a representation of the structure source codes.
-          </td></tr>
-          <tr><td>
-              LLVM IR
-            </td><td>
-              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.
-          </td></tr>
-          <tr><td>
-              SelectionDAG
-            </td><td>
-              Directed Acyclic Graph. Its nodes indicate what operation the node performs and the operands to the operation.
-          </td></tr>
-          <tr><td>
-              Machine Code
-            </td><td>
-              This representation is designed to support both an SSA representation for machine code, as well as register allocated, non-SSA form.
-          </td></tr>
-          <tr><td>
-              MC Layer
-            </td><td>
-              It is used to represent and process code at the raw machine code level. User can some kinds of file (.s, .o, .ll, a.out) by same API.
-          </td></tr>
-        </table>
-        <br>
-        <p align='center' class='step emphasize'>Intermidiate representations are not modified.</p>
+        <ul>
+          <li>clang AST
+          <li>LLVM IR
+          <li>SelectionDAG
+          <li>Machine Code
+          <li>MC Layer
+        </ul>
+        <h3 align='center'>Intermidiate representations are not modified.</h3>
+      </div>
+
+      <div class='slide'>
+        <h2>Clang AST</h2>
+        <ul>
+          <li>Abstract Syntax Tree.
+          <li>Representation of the source codes structure.
+          <li>Basic node type: Stmt, Decl, Expr.
+        </ul>
       </div>
 
       <div class='slide'>
-        <h2>Problems on implementating</h2>
+        <h2>LLVM IR</h2>
         <ul>
-          <li>How to implement code segments and data segments?
-          <li>How to implement jmp instruction based transition?
-          <li>How to implement goto with environment syntax?
+          <li>The main intermidiate representation.
+          <li>LLVM translate it into assembly codes.
+          <li>Three forms: in-memory compiler IR, on-disk bitcode, assembly language.
         </ul>
+        <table width='100%'>
+          <tr>
+            <td style="border: double;">
+              <pre class='code'>
+define fastcc void @factorial(i32 %x) #0 {
+  entry:
+  tail call fastcc void @factorial0(i32 1, i32 %x)
+  ret void
+}
+              </pre>
+            </td>
+          </tr>
+        </table>
       </div>
 
       <div class='slide'>
@@ -316,49 +322,77 @@
       <div class='slide'>
         <h2>Implementating CbC compiler in LLVM and Clang</h2>
         <ul>
-          <li>add __code type for code segment.
-          <li>add goto syntax for transition.
-          <li>force to tail call elimination.
-          <li>goto with environment.
-          <li>automatically prototype declatation genarating.
+          <li>__code type.
+          <li>Goto syntax.
+          <li>Force to do tail call elimination.
+          <li>Goto with environment.
+          <li>Automatically prototype declatation genarating.
        </ul>
       </div>
 
       <div class='slide'>
-        <h2>__code type</h2>
-        <p>modify parser.</p>
+        <h2>Parser</h2>
         <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
+        <ul>
+          <li>__code type
+          <li>Prototype declaration generating
+          <li>Goto syntax for transitions
+        </ul>
       </div>
 
       <div class='slide'>
         <h2>__code type</h2>
         <table width='100%'>
-          <tr><td>
-              <ul>
-                <li>Clang and LLVM handle code segments as __code type functions.
-                <li>Code segments do not have return value so they are handled like void functions.
-                <li>The following code is the place where Clang parse a __code type.
-                <li>DS.SetTypeSpecType() set AST nodes __code type.
-              </ul>
-          </tr>
           <tr>
-            <td style="border: double;">
-              <pre class='code'>
-  case tok::kw___code: {
-    LangOptions* LOP;
-    LOP = const_cast<LangOptions*>(&getLangOpts());
-    LOP->HasCodeSegment = 1;
-    isInvalid = <font color='red'>DS.SetTypeSpecType(DeclSpec::TST___code, Loc, PrevSpec, DiagID);</font>
-    break;
-  }</pre>
+            <ul>
+              <li>Code segments as __code type functions.
+              <li>Handled like void functions.
+            </ul>
           </tr>
         </table>
       </div>
 
       <div class='slide'>
-        <h2>goto syntax for transition</h2>
-        <p>modify parser.</p>
-        <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
+        <h2>Prototype declaration generating</h2>
+        <ul>
+          <li>In CbC, programmer write a lot of code segments.
+          <li>When function pointer's arguments are omitted, TCE was failed sometimes.
+          <li>Automatically prototype declaration generating saves a lot of effort.
+          <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.
+          <li>If the declaration was not found, search definision and generate declaration.
+            <ul>
+              <li>Of course you can write declaration yourself too.
+            </ul>
+        </ul>
+        <table border='1' width='80%' align='center'>
+          <tr>
+            <td>original input code
+            <td>Clang genarates it
+          </tr>
+          <tr>
+            <td><pre class='small_code'>
+__code code1(int a, int b) {
+     :
+  goto code2(a,b);
+}
+
+__code code2(int a, int b){
+     :
+}
+              </pre>
+            <td><pre class='small_code'>
+<font color='red'>__code code2(int a, int b);</font>
+__code code1(int a, int b) {
+     :
+  goto code2(a,b);
+}
+
+__code code2(int a, int b){
+     :
+}
+              </pre>
+          </tr>
+        </table>
       </div>
 
       <div class='slide'>
@@ -366,28 +400,11 @@
         <table width='100%'>
           <tr><td>
               <ul>
-                <li>Add new goto syntax for transition.
-                <li>Jmp instraction based transition is enabled by tail call elimination.
-                <li>In this part, clang create AST for normal function call and force to tail call elimination later.
-                <li>The following code is the place where CbC goto was parsed.
-                <li>If the goto is not for C syntax, we judge it is for CbC syntax.
+                <li>New goto syntax for transition.
+                <li>Generate normal function call.
+                <li>Tail call elimination is forced later.
               </ul>
           </tr>
-          <tr>
-            <td style="border: double;">
-              <pre class='code'>
-case tok::kw_goto:
-#ifndef noCbC
-  if (!(NextToken().is(tok::identifier) && PP.LookAhead(1).is(tok::semi)) &&
-    NextToken().isNot(tok::star)) {
-      SemiError = "goto code segment";
-      return ParseCbCGotoStatement(Attrs, Stmts);
-    }
-#endif
-  Res = ParseGotoStatement();
-  SemiError = "goto";
-  break;</pre>
-          </tr>
         </table>
       </div>
 
@@ -421,18 +438,6 @@
       </div>
 
       <div class='slide'>
-        <h2>Jmp instruction based transition</h2>
-        <ul>
-          <li>It is implemented by Tail Call Elimination (TCE).
-          <li>TCE is one of the optimization.
-          <li>If the function call is immediately followed by return, it is tail call.
-          <li>TCE replace tail call's call instructions with jmp instructions.
-          <li>Code segments transition is implemented by forced tail call elimination.
-        </ul>
-        <div align='center'><img src="fig/TCE.svg" width="40%"></div>
-      </div>
-
-      <div class='slide'>
         <h2>Forcing Tail Call Elimination</h2>
         <p>TCE is enabled at CodeGen.</p>
         <p>TCE is act at SelectionDAGISel.</p>
@@ -440,6 +445,17 @@
       </div>
 
       <div class='slide'>
+        <h2>Jmp instruction based transition</h2>
+        <ul>
+          <li>Tail call is immediately followed by return.
+          <li>Tail call elimination replace tail call's call instructions with jmp instructions.
+          <li>Transitions are implemented by forced tail call elimination.
+        </ul>
+        <div align='center'><img src="fig/TCE.svg" width="40%"></div>
+      </div>
+
+
+      <div class='slide'>
         <h2>Forcing Tail Call Elimination</h2>
         <ul>
           <li>LLVM IR has function call flags.
@@ -464,40 +480,32 @@
 
       <div class='slide'>
         <h2>Forcing Tail Call Elimination</h2>
-        <p>We have to meet the following requirements.</p>
+        <p>Tail Call Elimination requirements</p>
         <ul>
-          <li>set tail flag at the code segments call.
-          <li>tailcallopt is enabled.
-          <li>the caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
-          <li>return value type has to be the same as the caller's.
+          <li>Set tail flag at the code segments call.
+          <li>Tailcallopt is enabled.
+          <li>The caller and calle's calling conventions must be the same and their types should be cc10, cc11 or fastcc.
+          <li>Return value type has to be the same as the caller's.
         </ul>
       </div>
 
       <div class='slide'>
         <h2>Forcing Tail Call Elimination</h2>
-        <p>We met them by following ways.</p>
         <ul>
-          <li>Always add tail call elimination pass and set flag at the code segments call.
-          <li>If the input code contains code segment, tailcallopt is enabled automatically.
+          <li>Always add tail call elimination pass.
+          <li>Tailcallopt is enabled in CbC.
           <li>Fast cc is used consistently in code segments call.
           <li>All the code segments return value type is void.
         </ul>
       </div>
 
       <div class='slide'>
-        <h2>Goto with environment</h2>
-        <p>Goto with environment is enabled by modifying parser.</p>
-        <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
-      </div>
-
-      <div class='slide'>
         <h2>What is a Goto with environment?</h2>
         <ul>
-          <li>Code segments do not have environment cut functions have.
-          <li>Usually, code segments can't return to functions.
-          <li>Goto with environment enable to it.
-          <li>In the GCC, use nested functions to implementing.
-          <li>In the LLVM and Clang, use setjmp and longjmp to implementing.
+          <li>Code segments do not have environment but C functions have.
+          <li>Code segments can reutn C functions by Goto with environment.
+          <li>In the GCC, use nested functions.
+          <li>In the LLVM and Clang, use setjmp and longjmp.
         </ul>
       </div>
 
@@ -551,55 +559,6 @@
         </ul>
       </div>
 
-      <div class='slide'>
-        <h2>Prototype declaration generating</h2>
-        <p>modify parser.</p>
-        <div align='center'><img src="fig/clang_llvm_slide_parse.svg" width="70%"></div>
-      </div>
-
-      <div class='slide'>
-        <h2>Prototype declaration generating</h2>
-        <ul>
-          <li>In CbC, programmer write a lot of code segments.
-          <li>When function pointer's arguments are omitted, TCE was failed sometimes.
-          <li>Automatically prototype declaration generating saves a lot of effort.
-          <li>When parser meet a code segment call, it stop current parsing and search called code segment declaration.
-          <li>If the declaration was not found, search definision and generate declaration.
-            <ul>
-              <li>Of course you can write declaration yourself too.
-            </ul>
-<!--          <li>This feature is important to code segment transition.-->
-        </ul>
-        <table border='1' width='80%' align='center'>
-          <tr>
-            <td>original input code
-            <td>Clang genarates it
-          </tr>
-          <tr>
-            <td><pre class='small_code'>
-__code code1(int a, int b) {
-     :
-  goto code2(a,b);
-}
-
-__code code2(int a, int b){
-     :
-}
-              </pre>
-            <td><pre class='small_code'>
-<font color='red'>__code code2(int a, int b);</font>
-__code code1(int a, int b) {
-     :
-  goto code2(a,b);
-}
-
-__code code2(int a, int b){
-     :
-}
-              </pre>
-          </tr>
-        </table>
-      </div>
 
       <div class='slide'>
         <h2>Compiling result</h2>
@@ -638,7 +597,7 @@
           <li>If tail call elimination was failed, compiler output error messages.
         </ul>
       </div>
-
+<!--
       <div class='slide'>
         <h2>Execution Result</h2>
         <ul>
@@ -695,7 +654,7 @@
           <li>LLVM can compile CbC examples.
         </ul>
       </div>
-
+-->
       <div class='slide'>
         <h2>Conclusion</h2>
         <ul>
@@ -715,6 +674,44 @@
         </ul>
       </div>
 
+      <div class='slide'>
+        <h2>LLVM and Clang's intermidiate representations</h2>
+        <table border='1' align='center' width='80%'>
+          <tr><td width='25%'>
+              Name
+            </td><td>
+              Desctiption
+          </td></tr>
+          <tr><td>
+              clang AST
+            </td><td>
+              Abstract Syntax Tree. It is a representation of the structure source codes.
+          </td></tr>
+          <tr><td>
+              LLVM IR
+            </td><td>
+              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.
+          </td></tr>
+          <tr><td>
+              SelectionDAG
+            </td><td>
+              Directed Acyclic Graph. Its nodes indicate what operation the node performs and the operands to the operation.
+          </td></tr>
+          <tr><td>
+              Machine Code
+            </td><td>
+              This representation is designed to support both an SSA representation for machine code, as well as register allocated, non-SSA form.
+          </td></tr>
+          <tr><td>
+              MC Layer
+            </td><td>
+              It is used to represent and process code at the raw machine code level. User can some kinds of file (.s, .o, .ll, a.out) by same API.
+          </td></tr>
+        </table>
+        <br>
+        <p align='center' class='step emphasize'>Intermidiate representations are not modified.</p>
+      </div>
+
     </div> <!-- presentation -->
   </body>
 </html>