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="theme/css/print.css">
    <link rel="stylesheet" media="screen, projection" href="theme/css/screen.css">


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

    <script type="text/javascript" src="theme/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/23
            </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"></p>
<li><font color=red size=5em>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</font></li>

<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/23
            </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><font size=5em>コーセグメント:CbC におけるプログラムの基本単位</font></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="./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/23
            </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="./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/23
            </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%">
<font color="blue">__code</font> print_factorial(int prod)
{
  printf("factorial = %d\n",prod);
  exit(0);
}
<font color="blue">__code</font> factorial0(int prod, int x)
{
  if ( x &gt;= 1) {
    <font color="red">goto</font> factorial0(prod*x, x-1);
  }else{
    <font color="red">goto</font> print_factorial(prod);
  }
}
<font color="blue">__code</font> factorial(int x)
{
  <font color="red">goto</font> factorial0(1, x);
}
int main(int argc, char **argv)
{
  int i;
  i = atoi(argv[1]);
  <font color="red">goto</font> factorial(i);
}
</pre>
</td>
<td>
<li><font color="blue">__code</font> によるコードセグメントの宣言</li>
<li>引数付きの <font color="red">goto</font> でコードセグメントを呼び出すことができる</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/23
            </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="./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/23
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>CbC の実装: 末尾除去の強制</h1></header>


            <section><h2>末尾除去の条件をチェックする関数</h2>
<ul>
<li>関数(コードセグメント)が末尾除去にかかる為には幾つか条件があり、その条件はある関数によってチェックされる。</li>
<li>その関数を元に、『コードセグメントを末尾除去にかける』専用の関数を用意していた。</li>
<li>しかしこの方法は、元になった関数が修正に合わせて専用の関数も修正を行う必要があった。</li>
</ul>
<h2>実装の修正とその利点</h2>
<ul>
<li>しかし 今回の実装でその関数を無くし, 末尾除去のフラグを強制的に立たせる実装に変更</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">
              7/23
            </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>
<table width=100% border=1>
  <caption>各コンパイラにより生成されたプログラムの速度比較</caption>
  <tr>
  <td style="margin:auto; text-align:center;">
    <img src="./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></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/23
            </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_b(){
  X;
  Y;
}

void func_a() {
  func_b();
  func_b();
}
</pre>
</td>
<td>
<pre style="margin-left:5%">
void func_a() {
  X;
  Y;
  X;
  Y;
}
</pre>
</td>
</tr>
</table>
<li>func_b の呼び出しがなくなっている。</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/23
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>最適化の比較(conv1)</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="./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">
              10/23
            </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">
              11/23
            </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">
              12/23
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>CbC</h1></header>


            <section><h2>状態遷移記述をベースとしたより細かい単位でのプログラミングを実現する</h2>
<p><li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
<li>現存する記述言語は状態遷移の記述に向いていない</li>
<li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
<li>以上の問題を解決する言語として CbC は提案されている。</li></p>
<h2>具体的な CbC の利用予定</h2>
<ul>
<li>Cerium の実装</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">
              13/23
            </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="./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">
              14/23
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>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>条件回避の為の CbC の実装内容</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">
              15/23
            </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="./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">
              16/23
            </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="./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">
              17/23
            </aside>
          </footer>
        </div>
      </div>

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

            <header><h1>CbC-GCC のアップデート手法</h1></header>


            <section><ol>
<li>GCC のソースを入れるリポジトリを用意する。</li>
<li>GCC のリポジトリの中身を全て消し、新しい GCC を入れて新しいファイルは追加、消えたファイルは削除する。</li>
<li>コミット</li>
</ol>

<h2>CbC-GCC のリポジトリ</h2>
<p><ol>
<li>GCC のソースから pull</li>
<li>merge を行う</li>
<li>衝突のあったファイルを手動でマージする</li>
<li>コミット</li>
</ol></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/23
            </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">
              19/23
            </aside>
          </footer>
        </div>
      </div>

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

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


            <section><p><li>性能評価で用いた conv1 プログラムの C 版</li>
<pre style="width:5%;" border=1>
f0(int i) {
    int k,j;
    k = 3+i;
    j = g0(i+3);
    return k+4+j;
}
g0(int i) {
    return h0(i+4)+i;
}
h0(int i) {
    return i+4;
}</pre>
<li>性能評価はこのプログラムを CbC へと書き換えて行なっている。</li>
<li>引数 1 のプログラムは上のプログラムをただ CbC へと書き換えたもの</li>
<li>引数 2 と 3 のプログラムは手動で最適化を行なって CbC へと書き換えたもの</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">
              20/23
            </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">
              21/23
            </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>
__code c1(__code ret(int,void <em>),void </em>env) {
    goto ret(1,env);
}
int main() {
    goto c1(__return, __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">
              22/23
            </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>
-->

---

最適化の比較
========

<table width=100% border=1>
  <caption>各コンパイラにより生成されたコードの速度比較</caption>
  <tr>
  <td style="margin:auto; text-align:center;">
    <img src="./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">
              23/23
            </aside>
          </footer>
        </div>
      </div>

      <!-- slide source:  -->
      <div class="slide-wrapper">
        <div class="slide">
          <div class="inner">


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

            </section>
          </div>
          <footer>

            <aside class="page_number">
              /23
            </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 の実装 : 軽量継続</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">GCC-4.5, GCC-4.6 の性能比較</a></th>
        <td><a href="#slide8">8</a></td>
      </tr>


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


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


      <tr id="toc-row-11">
        <th><a href="#slide11">最新バージョンに合わせる有用性</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">CbC</a></th>
        <td><a href="#slide13">13</a></td>
      </tr>


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


      <tr id="toc-row-15">
        <th><a href="#slide15">Tail Call Elimination</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">jmp と call</a></th>
        <td><a href="#slide17">17</a></td>
      </tr>


      <tr id="toc-row-18">
        <th><a href="#slide18">CbC-GCC のアップデート手法</a></th>
        <td><a href="#slide18">18</a></td>
      </tr>


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


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


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


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


      <tr id="toc-row-23">
        <th><a href="#slide23">最適化の比較</a></th>
        <td><a href="#slide23">23</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	Wed, 29 Feb 2012 09:55:14 +0900
parents	8539cd84106e
children	bf8db1c89618