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/21
            </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>
<ul>
<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/21
            </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 から関数コールとループ制御が取り除かれた形</li>
<li>コードセグメントの末尾処理で別のコードセグメントへ継続(goto)することで CbC のプログラムは続いていく。</li>
</ul>

<table width=100% >
    <td style="margin-left:auto; margin-right: auto; text-align: center;">
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/codesegment.png" style="height:14em;">
    </td>
</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/21
            </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/21
            </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>
<pre>
    __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<em>x, x-1);
      }else{
        goto print_factorial(prod);
      }
    }
    __code factorial(int x)
    {
      goto factorial0(1, x);
    }
    int main(int argc, char </em>*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/21
            </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><p><li>CbC-GCC の軽量継続は最適化の1つ, <font color=red>Tail Call Celimination(末尾除去)</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">
              6/21
            </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>呼出先関数の引数に用いられるスタックサイズが呼出元のそれより少ない。</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">
              7/21
            </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>
<li>しかし, 今回の実装でその関数を無くし, Tail Call Elimination のフラグを強制的に立たせる実装に変更。</li>
<li>専用関数がなくなったことで今後より楽なアップデートを行なっていくことができるようになった。</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">
              8/21
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>性能評価</h1></header>


            <section><li>conv1: 演算と継続を交互に繰り返すプログラム</li>

<table width=100%>
  <caption>各コンパイラにより生成されたコードの速度比較</caption>
  <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>
</table>

<li>GCC-4.5 では動かなかったプログラムが 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">
              9/21
            </aside>
          </footer>
        </div>
      </div>

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

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


            <section><p><table width=100% border=1>
  <caption>それぞれの最適化にかかった conv1プログラムの挙動(引数 1)</caption>
  <tr>
    <td>最適化</td>
    <td style="text-align:center;">状態遷移</td>
  </tr>
  <tr>
    <td>最適化無し</td>
    <td style="margin:auto; text-align:center;">
      <img src="file:///Users/aotokage/hg/Papers/2012/nobu-thesis/presen/./pix/state_conv1_noopt.png">
  </td>
  <tr>
    <td>GCC-4.5<br>の最適化<br>(-O2)</td>
    <td style="margin:auto; text-align:center;">
    <img src="./pix/state_conv1_45.png">
  </td>
  </tr>
  <tr>
    <td>GCC-4.6<br>の最適化<br>(-O2)</td>
    <td style="margin:auto; text-align:center;">
      <img src="./pix/state_conv1_46.png">
    </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">
              10/21
            </aside>
          </footer>
        </div>
      </div>

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

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


            <section><ul>
<li>最適化無しに比べると GCC-4.5、 GGC-4.6 共にコードセグメントの数が減っている。</l></li>
<li>これは、最適化の 1 つ『インライン展開』により各コードセグメントの計算がまとめて行われ、
継続する数を減らされている為。</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">
              11/21
            </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">
              12/21
            </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>アップデートに伴い最適化の強制付与や環境付き継続の部分の実装の修正を行った。</li>
<li>アップデートにかけたことで, より良い最適化がかかることを確認できた。</li>
<li>GCC ベースの CbC コンパイラは今後 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">
              13/21
            </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>
<li>引数 0 は C の関数で書かれたプログラム</li>

<li>引数 3 は引数 0 のプログラムをただ CbC に書き直したもの</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">
              14/21
            </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">
              15/21
            </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">
              16/21
            </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">
              17/21
            </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">
              18/21
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>GCC でのコンパイルの仕組み</h1></header>


            <section><table width=100%>
  <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>CbC の実装では Parser と RTL の生成部分に手が加えられている。</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">
              19/21
            </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/21
            </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">
              21/21
            </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">CbC の実装 : Tail Call Elimination</a></th>
        <td><a href="#slide6">6</a></td>
      </tr>


      <tr id="toc-row-7">
        <th><a href="#slide7">CbC の実装: Tail Call Elimination</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">性能評価</a></th>
        <td><a href="#slide9">9</a></td>
      </tr>


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


      <tr id="toc-row-11">
        <th><a href="#slide11">GCC の最適化</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">jmp と call</a></th>
        <td><a href="#slide14">14</a></td>
      </tr>


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


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


      <tr id="toc-row-17">
        <th><a href="#slide17">CbC の実装: 環境付き継続</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">GCC でのコンパイルの仕組み</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>


    </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	Mon, 27 Feb 2012 18:34:32 +0900
parents	3dbaff8febef
children	01238ec569ea