Mercurial > hg > Papers > 2012 > nobu-thesis

<!DOCTYPE html>
<!--
  Copyright 2010 Google Inc.

  Licensed under the Apache License, Version 2.0 (the "License");
  you may not use this file except in compliance with the License.
  You may obtain a copy of the License at

     http://www.apache.org/licenses/LICENSE-2.0

  Unless required by applicable law or agreed to in writing, software
  distributed under the License is distributed on an "AS IS" BASIS,
  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  See the License for the specific language governing permissions and
  limitations under the License.

  Original slides: Marcin Wichary (mwichary@google.com)
  Modifications: Ernest Delgado (ernestd@google.com)
                 Alex Russell (slightlyoff@chromium.org)

  landslide modifications: Adam Zapletal (adamzap@gmail.com)
                           Nicolas Perriault (nperriault@gmail.com)
-->
<html>
<head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    <meta http-equiv="X-UA-Compatible" content="chrome=1">
    <title>Continuation based C の <br> GCC 4.6による実装</title>
    <!-- Styles -->

    <link rel="stylesheet" media="print" href="file:///Library/Python/2.7/site-packages/landslide-1.0.1-py2.7.egg/landslide/themes/default/css/print.css">
    <link rel="stylesheet" media="screen, projection" href="file:///Library/Python/2.7/site-packages/landslide-1.0.1-py2.7.egg/landslide/themes/tango/css/screen.css">


      <link rel="stylesheet" href="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/presen.css">


    <!-- /Styles -->
    <!-- Javascripts -->

    <script type="text/javascript" src="file:///Library/Python/2.7/site-packages/landslide-1.0.1-py2.7.egg/landslide/themes/default/js/slides.js"></script>


    <!-- /Javascripts -->
</head>
<body>
  <div id="blank"></div>
  <div class="presentation">
    <div id="current_presenter_notes">
      <div id="presenter_note"></div>
    </div>
    <div class="slides">

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>Continuation based C の <br> GCC 4.6による実装</h1></header>


          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              1/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide has_notes">
          <div class="inner">

            <header><h2>研究目的</h2></header>


            <section><p class="notes">plop</p>
<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>

<ul>
<li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
<li>現存する記述言語は状態遷移の記述に向いていない</li>
<li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
<li>当研究室ではコードセグメント単位で記述するプログラミング言語Continuation based C (以下CbC)という言語を提案している。</li>
<li>CbC のコンパイラは Micro-C 版 と GCC ベース(以下 CbC-GCC)のコンパイラが開発されている。</li>
<li>しかし, CbC-GCC はいくつかのバグがあり機能の修正の余地があった。</li>
<li>また、GCC の最新の機能を使用するためにも CbC-GCC は GCC のアップデートに合わせていく必要がある。</li>
</ul>
<h2>本研究では CbC-GCC のアップデートを行い、より良いコードを生成する CbC の処理系を開発した。</h2></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              2/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>Continuation based C</h1></header>


            <section><h2>コードセグメント単位での記述と継続を基本としたプログラミング言語</h2>
<li>コーセグメント:CbC におけるプログラムの基本単位</li>

<ul>
<li>C の関数よりも細かな単位</li>
<li>構文は C と同じだが、C から関数コールとループ制御が取り除かれた形</li>
<li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li>
</ul>

<table width=100%  border=1>
  <tr>
    <td style="margin-left:auto; margin-right: auto; text-align: center; width:50%" >
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/codesegment.png" style="width:100%">
    </td>
    <td>
      <pre style="margin-left:5%">
__code cs_a(int num) {
   :
   :
   goto cs_b();
}
      </pre>
    </td>
  </tr>
</table></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              3/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>Continuation based C</h1></header>


            <section><h2>継続:現在の処理を実行していく為の情報</h2>
<p><table width=100% border=1>
  <tr>
    <td><h2>Cの継続</h2></td>
    <td><h2>CbCの継続(軽量継続)</h2></td>
  </tr>
  <tr>
    <td>
      <ul>
    <li>続く命令のアドレス</li>
    <li>命令に必要なデータ</li>
    <li>スタックに積まれている値(環境)</li>
      </ul>
    </td>
    <td>
      <ul>
    <li>Cの継続から環境を除外</li>
    <li>続く命令とその命令に必要なデータのみ</li>
      </ul>
    </td>
  </tr>
  <t>
    <td style="margin-left:auto; margin-right: auto; text-align: center;">
      <img class="scale" src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/func_call.png" style="height: 18em;">
    </td>
    <td style="margin-left:auto; margin-right: auto; text-align: center;">
      <img class="scale" src="./pix/cs_stack.png" style="height: 18em;">
    </td>
  </tr>
</table></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              4/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>Continuation based C</h1></header>


            <section><p><table width=100% border=1>
<caption>階乗を求める CbC のプログラム</caption>
<td width=50%>
<pre style="margin-left:5%">
__code print_factorial(int prod)
{
  printf("factorial = %d\n",prod);
  exit(0);
}
__code factorial0(int prod, int x)
{
  if ( x &gt;= 1) {
    goto factorial0(prod*x, x-1);
  }else{
    goto print_factorial(prod);
  }
}
__code factorial(int x)
{
  goto factorial0(1, x);
}
int main(int argc, char **argv)
{
  int i;
  i = atoi(argv[1]);
  goto factorial(i);
}
</pre>
</td>
<td>
<li>__code によるコードセグメントの宣言</li>
<li>引数付きの goto でコードセグメントを呼び出すことができる</li>
<li>内部では call ではなく jmp 命令でコードセグメントの処理が遷移している</li>
</td>
</table></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              5/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>Gnu Compiler Collection (GCC)</h1></header>


            <section><p><li>GCC: オープンソースのコンパイラ群</li>
<li>ここで扱う GCC はソースコードをアセンブラに変換する『cc1』のことを指す。</li>
<li>GCC がソースコードを読み込みアセンブラ言語を出力するまでの流れは以下の図のようになる。</li>
<table width=100%>
  <caption>GCC のアセンブラ言語出力までの流れ</caption>
  <td style="margin:auto; text-align:center;">
    <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/ir.png" style="height:15em">
  </td>
</table>
<li>ソースコードはアセンブラに変換される間に 4 つのデータ構造に変換される。</li>
<li>この中でも CbC の実装では Parser と RTL の生成部分に手が加えられている。</li></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              6/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>CbC の実装 : 軽量継続</h1></header>


            <section><p><li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Elimination(末尾除去)</font>により実装されている.</li></p>
<h2>Tail Call Elimination</h2>
<p><li>関数呼び出しを call ではなく jmp 命令で行う最適化</li>
<li>例えば、以下の場合関数 g は jmp 命令で関数 f へと処理が移る</li></p>
<table width=100% border=1>
  <tr>
    <td width=50%>
<pre>
  void f(int a, int b) {
    printf("f: a=%d b=%d\n",a,b);
    return ;
  }

  void g(int a, int b){
    printf("g: a=%d b=%d\n",a,b);
    f(a,b);
    return;
  }

  int main() {
    g(3,4);
    return 0;
  }</pre>
    </td>
    <td>
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/continuation.png" style="height:80%;">
    </td>
  </tr>
</table></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              7/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>CbC の実装: Tail Call Elimination</h1></header>


            <section><h2>Tail Call Elimination の条件</h2>
<p><ul>
  <li>関数を呼び出す側(caller)と呼び出される側(callee)の戻値の型が一致している。</li>
  <li>関数呼び出しがリターン直前に行われている。</li>
  <li>呼び出される関数(callee)の引数に用いられるスタックサイズが呼出元(caller)のそれより少ない。</li>
  <li>引数の並びのコピーに上書きがない。</li>
</ul></p>
<h2>条件回避の為の実装</h2>
<p><ul>
  <li>コードセグメントの型はvoid型で統一する。</li>
  <li>gotoの直後に自動で return を置く。</li>
  <li>スタックサイズは固定にする。</li>
  <li>引数は一旦、一時変数にコピーする。</li>
</ul></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              8/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>CbC の実装: Tail Call Elimination</h1></header>


            <section><h2>Tail Call Elimination の条件をチェックする関数</h2>
<ul>
<li>今までの実装では Tail Call Elimination の条件をクリアする為に専用の関数を用意していた。</li>
<li>この専用関数は元々ある GCC コードを元に作成している為, アップデートに合わせて修正していく
必要があった。</li>
</ul>
<h2>実装の修正とその利点</h2>
<ul>
<li>しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。</li>
<li>専用関数がなくなったことで、今後より楽なアップデートを行なっていくことができるようになった。</li>
<li>また、コードセグメントへの継続が jmp ではなく call 命令で行われるバグがあったが修正できた。</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              9/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>GCC-4.5, GCC-4.6 の性能比較</h1></header>


            <section><p><li><font color=red size=5em>本研究では GCC-4.5 から GCC-4.6 へのアップデートを行った。</font></li>
<li>この 2 つのバージョンを用いて生成したプログラムの速度比較を行った。</li>
<li>conv1: 加算と継続を交互に繰り返すプログラム</li></p>
<table width=100% border=1>
  <caption>各コンパイラにより生成されたプログラムの速度比較</caption>
  <tr>
  <td style="margin:auto; text-align:center;">
    <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/conv1_for_resume.png" style="height:15em">
  </td>
  <td>
    <img src="./pix/conv1_mac_for_presen.png" style="height:15em">
  </td>
  </tr>
  <tr>
    <td style="text-align:center;">x86/Linux</td>
    <td style="text-align:center;">x86/OS X (10.7)</td>
  </tr>
</table>

<li>Mac の GCC-4.5 では動かなかった 32bit のプログラムが GCC-4.6 では問題なく動いている。</li>

<li>引数 2、3 の結果はほぼ同じ</li>

<li>引数 1 の結果では 32bit, 64bit 共に GCC-4.6 の方が 1.5倍以上早い</li></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              10/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>GCC-4.6 の最適化</h1></header>


            <section><ul>
<li>GCC-4.6 では最適化の 1つ『インライン展開』が強化されている。</li>
</ul>
<h2>インライン展開</h2>
<ul>
<li>関数の処理をそのまま関数呼び出し部に展開することで call を省略できる最適化</li>
</ul>
<table width=100% border=1>
<caption><h3>インライン展開の例</h3></caption>
<tr>
<td width=50%>
<pre style="margin-left:5%">
void func(){
  A;
  B;
}

int main() {
  func();
  func();
}
</pre>
</td>
<td>
<pre style="margin-left:5%">
int main() {
  A;
  B;
  A;
  B;
}
</pre>
</td>
</tr>
</table>
<li>func の呼び出しがなくなっている。</li></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              11/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>最適化の比較</h1></header>


            <section><table width=100% border=1>
  <caption><h3>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</h3></caption>
  <tr>
    <td width=30%>最適化なし</td>
    <td width=30%>GCC-4.5の最適化(-O2)</td>
    <td width=30%>GCC-4.6の最適化(-O2)</td>
  </tr>
  <tr>
    <td style="margin:auto; text-align:center;">
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/state_conv1_noopt.png" style="width:65%;">
    </td>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_45.png"  style="width:65%;">
    </td>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_46.png"  style="width:65%;">
    </td>
  </tr>
</table>

<ul>
<li>最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</li>
<li>GCC-4.5 でもインライン展開はされているが、GCC-4.6 はより良い最適化がかけられている。</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              12/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>最新版のアップデートに合わせる有用性</h1></header>


            <section><ul>
<li>今回の『インライン展開』のように GCC の最適化は日々改良されている。</li>
<li>また、既存の最適化の改良だけでなく新たな最適化の追加等も行われていく。</li>
<li>それらの恩恵を受ける為にも GCC のアップデートに合わせていく事は今後も重要である。</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              13/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>まとめ</h1></header>


            <section><ul>
<li>今回 CbC-GCC を GCC-4.6 へとアップデートを行った。</li>
<li>アップデートにより、よりよいコードを生成する CbC のコンパイラを用意することができた。</li>
<li>また、最適化の強制付与やといった実装の修正も行えた。</li>
<li>細かな実装を除けば, CbC-GCC は今後 GCC のアップデートに合わせていくだけとなる。</li>
</ul>
<h2>今後の課題</h2>
<ul>
<li>LLVM ベースの CbC コンパイラの開発</li>
<li>google Go 言語への実装の検討</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              14/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>jmp と call</h1></header>


            <section><p><table width=100%>
<caption>インライン展開無しの conv1 プログラム実行結果</caption>
<td style="text-align:center;">
<img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/fno_inline.png">
</td>
</table></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              15/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>構文の追加</h1></header>


            <section><h2>リカーシブタイプの宣言に使う"__rectype"</h2>
<ul>
<li>関数宣言時、以下のように引数に自分自身を指す型を入れたい。
<pre>
__code func(int, func*);
<pre></li>
<li>上記の宣言ではエラーがでる。その為、以下のような宣言になる。
<pre>
__code func(int, __code (*)());
</pre></li>
<li>しかし、これでは正しい情報をコンパイラに渡せていない。関数ポインタの引数に型情報が入っていないからである。
<pre>
__code func(int, __code (<em>)(int, __code(</em>)(int, __code(*)(int, ...))))
</pre></li>
<li>だが、正しい情報を渡そうとすると上記のように再帰してしまい、宣言できない。</li>
<li>そこで __rectype という構文を追加して宣言中の関数自身を指すようにした。
<pre>
__code func(int, rectype*);
</pre></li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              16/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>conv1 プログラム</h1></header>


            <section><ul>
<li>conv1 プログラムでは計算と継続を交互に繰り返し行なう。</li>
<li>
<p>しかし状態のいくつかへは関数ポインタとして保存させておき継続を行う。
<pre>
__code g(int i,stack sp) { // Caller
    struct f_g0_interface <em>c =
        (struct f_g0_interface </em>)(sp -= sizeof(struct f_g0_interface));
    c-&gt;ret = g_h1;
    c-&gt;i_ = i;
    goto h(i+3,sp);
}
__code h(int i,stack sp) {
    struct f_g0_interface <em>c = (struct f_g0_interface </em>)sp;
    goto (c-&gt;ret)(i+4,sp);
}
</pre></p>
</li>
<li>
<p>関数ポインタへの継続はインライン展開されない。</p>
</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              17/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>CbC の実装: 環境付き継続</h1></header>


            <section><ul>
<li>環境付き継続: C との互換を取るための機能。継続を行った C の関数に戻ることができる。 </li>
<li>_CbC_return、 _CbC_environment キーワードを使うことで使える。</li>
<li>
<p>以下の使い方の場合、戻値 1 を返す。
<pre>
<strong>code c1(</strong>code ret(int,void <em>),void </em>env) {
    goto ret(1,env);
}
int main() {
    goto c1(<strong>return, </strong>environment);
}
</pre></p>
</li>
<li>
<p>今回この環境付き継続をスレッドセーフの実装へと修正した。</p>
</li>
</ul></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              18/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>CbC 引数渡し</h1></header>


            <section><p><li>CbC では引数渡しにできるだけレジスタを用いるようにしている.</li>
<table border=1 width=100%>
  <caption><small>fastcall属性有・無の実行速度</small></caption>
  <tr>
    <td width=50% style="text-align:center;">fastcall無し</td>
  </tr>
  <tr>
  <td style="margin:auto; text-align:center;">
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/linux_conv_nofastcall.png" style="height:15em;">
    </td>
  </tr>
  <tr>
    <td width=50% style="text-align:center;">fastcall有り</td>
  <tr>
    <td>
      <img src="./pix/linux_conv_fastcall.png" style="height:15em;">
    </td>
  </tr>
</table></p></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              19/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>引数の並びに上書きコピー</h1></header>


            <section><p><li>以下の呼び出しを行うと、スタックの書き換えがおこる</li>
<pre>
void funcA(int a, int b) {
  funcB(b, a);
}
</pre></p>
<table width=100%>
<tr>
<td style="margin:auto; text-align:center;">
<img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/cs_prog.png">
</td>
</tr>
</table></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              20/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>最適化の比較</h1></header>


            <section><table width=100% border=1>
  <caption>各コンパイラにより生成されたコードの速度比較</caption>
  <tr>
  <td style="margin:auto; text-align:center;">
    <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/O3_conv1_linux.png" style="height:15em">
  </td>
  <td>
    <img src="./pix/O3_conv1_mac.png" style="height:15em">
  </td>
  </tr>
  <tr>
    <td style="text-align:center;">x86/Linux</td>
    <td style="text-align:center;">x86/OS X (10.7)</td>
  </tr>
</table></section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              21/22
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source: ./cbc.md -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">

            <header><h1>最適化の比較</h1></header>


            <section><table width=100% border=1>
  <caption>それぞれの最適化により吐かれたアセンブラコード</caption>
  <tr>
    <td width=50% style="text-align:center;">CbC-GCC-4.5</td>
    <td width=50% style="text-align:center;">CbC-GCC-4.6</td>
  </tr>

  <tr>
    <td>
      <pre>
main:
    call    f
    :
    jmp     f_g0
    :
    movq    $f_g1, -24(%rdx)
    addl    $10, %edi
    movq    $g_h1, -48(%rdx)
    jmp     g_h1
    :
    movq    24(%rsi), %rdx
    movq    %rax, %rsi
    :
    jmp     *%rdx
    :
    movq    24(%rsi), %rdx
    :
    jmp     *%rdx
      </pre>
    </td>
    <td>
      <pre>
main:
    movq    $f_g1, main_stack+2000(%rip)
    :
    call    g_h1
    :
    movq    24(%rax), %rdx
    :
    jmp     *%rdx
    :
    movq    24(%rax), %rdx
    :
    jmp     *%rdx
      </pre>
    </td>
  </tr>
<!--
  <tr>
    <td></td>
    <td></td>
  </tr>
-->

</table>
<li>関数を展開してその場で計算する『インライン展開』がより強力になっているのが確認できる</li>
<!--
<li>保存していた関数ポインタへの継続はインライン展開は行われない</li>
-->

---</section>

          </div>
          <div class="presenter_notes">
            <header><h1>Presenter Notes</h1></header>
            <section>

            </section>
          </div>
          <footer>

            <aside class="source">
              Source: <a href="./cbc.md">./cbc.md</a>
            </aside>

            <aside class="page_number">
              22/22
            </aside>
          </footer>
        </div>
      </div>

    </div>
  </div>

  <div id="toc" class="sidebar hidden">
    <h2>Table of Contents</h2>
    <table>
      <caption>Table of Contents</caption>

      <tr id="toc-row-1">
        <th><a href="#slide1">Continuation based C の <br> GCC 4.6による実装</a></th>
        <td><a href="#slide1">1</a></td>
      </tr>


        <tr id="toc-row-2" class="sub">
          <th><a href="#slide2">研究目的</a></th>
          <td><a href="#slide2">2</a></td>
        </tr>


      <tr id="toc-row-3">
        <th><a href="#slide3">Continuation based C</a></th>
        <td><a href="#slide3">3</a></td>
      </tr>


      <tr id="toc-row-4">
        <th><a href="#slide4">Continuation based C</a></th>
        <td><a href="#slide4">4</a></td>
      </tr>


      <tr id="toc-row-5">
        <th><a href="#slide5">Continuation based C</a></th>
        <td><a href="#slide5">5</a></td>
      </tr>


      <tr id="toc-row-6">
        <th><a href="#slide6">Gnu Compiler Collection (GCC)</a></th>
        <td><a href="#slide6">6</a></td>
      </tr>


      <tr id="toc-row-7">
        <th><a href="#slide7">CbC の実装 : 軽量継続</a></th>
        <td><a href="#slide7">7</a></td>
      </tr>


      <tr id="toc-row-8">
        <th><a href="#slide8">CbC の実装: Tail Call Elimination</a></th>
        <td><a href="#slide8">8</a></td>
      </tr>


      <tr id="toc-row-9">
        <th><a href="#slide9">CbC の実装: Tail Call Elimination</a></th>
        <td><a href="#slide9">9</a></td>
      </tr>


      <tr id="toc-row-10">
        <th><a href="#slide10">GCC-4.5, GCC-4.6 の性能比較</a></th>
        <td><a href="#slide10">10</a></td>
      </tr>


      <tr id="toc-row-11">
        <th><a href="#slide11">GCC-4.6 の最適化</a></th>
        <td><a href="#slide11">11</a></td>
      </tr>


      <tr id="toc-row-12">
        <th><a href="#slide12">最適化の比較</a></th>
        <td><a href="#slide12">12</a></td>
      </tr>


      <tr id="toc-row-13">
        <th><a href="#slide13">最新版のアップデートに合わせる有用性</a></th>
        <td><a href="#slide13">13</a></td>
      </tr>


      <tr id="toc-row-14">
        <th><a href="#slide14">まとめ</a></th>
        <td><a href="#slide14">14</a></td>
      </tr>


      <tr id="toc-row-15">
        <th><a href="#slide15">jmp と call</a></th>
        <td><a href="#slide15">15</a></td>
      </tr>


      <tr id="toc-row-16">
        <th><a href="#slide16">構文の追加</a></th>
        <td><a href="#slide16">16</a></td>
      </tr>


      <tr id="toc-row-17">
        <th><a href="#slide17">conv1 プログラム</a></th>
        <td><a href="#slide17">17</a></td>
      </tr>


      <tr id="toc-row-18">
        <th><a href="#slide18">CbC の実装: 環境付き継続</a></th>
        <td><a href="#slide18">18</a></td>
      </tr>


      <tr id="toc-row-19">
        <th><a href="#slide19">CbC 引数渡し</a></th>
        <td><a href="#slide19">19</a></td>
      </tr>


      <tr id="toc-row-20">
        <th><a href="#slide20">引数の並びに上書きコピー</a></th>
        <td><a href="#slide20">20</a></td>
      </tr>


      <tr id="toc-row-21">
        <th><a href="#slide21">最適化の比較</a></th>
        <td><a href="#slide21">21</a></td>
      </tr>


      <tr id="toc-row-22">
        <th><a href="#slide22">最適化の比較</a></th>
        <td><a href="#slide22">22</a></td>
      </tr>


    </table>
  </div>

  <div id="help" class="sidebar hidden">
    <h2>Help</h2>
    <table>
      <caption>Help</caption>
      <tr>
        <th>Table of Contents</th>
        <td>t</td>
      </tr>
      <tr>
        <th>Exposé</th>
        <td>ESC</td>
      </tr>
      <tr>
        <th>Full screen slides</th>
        <td>e</td>
      </tr>
      <tr>
        <th>Presenter View</th>
        <td>p</td>
      </tr>
      <tr>
        <th>Source Files</th>
        <td>s</td>
      </tr>
      <tr>
        <th>Slide Numbers</th>
        <td>n</td>
      </tr>
      <tr>
        <th>Toggle screen blanking</th>
        <td>b</td>
      </tr>
      <tr>
        <th>Show/hide slide context</th>
        <td>c</td>
      </tr>
      <tr>
        <th>Notes</th>
        <td>2</td>
      </tr>
      <tr>
        <th>Help</th>
        <td>h</td>
      </tr>
    </table>
  </div>
  <script>main()</script>
</body>
</html>
author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Tue, 28 Feb 2012 05:23:38 +0900
parents	01238ec569ea
children	bbebd829c423