view recital-slide/slide.html @ 15:67544736317e

add slides for recital.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 17:25:21 +0900
parents
children d9b85f041908
line wrap: on
line source

<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="ja" lang="ja">
<head>
  <title>Continuation based C</title>
  <meta name="copyright" content="Copyright &#169; 2009 KSL: Yogi KENT" />
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  <meta name="font-size-adjustment" content="1" />
  <link rel="stylesheet" href="slidy.css"
        type="text/css" media="screen, projection, print" />
  <link rel="stylesheet" href="slide.css"
        type="text/css" media="screen" />
  <!--link rel="stylesheet" href="../Slidy/w3c-blue2.css"
        type="text/css" media="screen, projection, print" /-->
  <style type="text/css">
      .right {
	  float: right;
          width: 40%;
      }
      .left {
	  float: left;
          width: 40%;
      }
      div.slide {
          vertical-align: middle;
      }
      div.top h1 {
	  width: 70%;
	  padding: 0 1em 0;
	  text-align: center;
      }
      #frame {
	position: fixed;
	left: -1px;
	top: -1px;
	width: 800px;
	height: 600px;
	border: solid 1px red;
	visibility: visible;
      }
      .speak {

        visibility: hidden;

        font-size: 80%;
        line-height: 1.0;
        position: fixed;
        right: 0.5em;
        bottom: 1.5em;
        max-width: 60%;
        background-color: green;
        opacity: 0.90;
        color: black;
        -moz-border-radius: 8px;
        -webkit-border-radius: 8px;
      }
      ul.narrow li {
	margin-right: 0;
      }
      table {
        border-collapse: collapse;
	border: solid 1px black;
      }
      table td {
	border: solid 1px black;
      }
      table th {
        text-align: center;
	border: solid 1px black;
      }
  </style>
  <script src="slidy.js"
          charset="utf-8" type="text/javascript">
  </script>
  <script type="text/javascript">
      sizes = new Array("14pt", "15pt", "16pt", "17pt", "18pt", "19pt", "20pt", "21pt", "22pt","23pt",  "24pt", "26pt", "28pt", "30pt", "32pt");
      sizeIndex = 1;
      mouseClickEnabled = false;
  </script>
</head>
<body>
<!-- this defines the slide background -->
<div id="frame"></div>

<div class="background">
  <div class="header">
    <!-- sized and colored via CSS -->
  </div>

  <!--img id="head-icon" alt="graphic with four colored squares"
      src="../Slidy/icon-blue.png" /-->

  <div class="footer">
    <object id="w3c-logo" data="kent-logo2.svg" type="image/svg+xml" title="KENT logo">
      <a href="http://www.w3.org/">
	<img alt="W3C logo" id="w3c-logo-fallback" src="kent-logo2.png" />
      </a>
    </object>

    <!-- modify the following text as appropriate -->
    組み込み向け言語CbCのGCC上の実装 <span style="font-size:70%;">http://www.cr.ie.u-ryukyu.ac.jp/~kent/slide/final.html</span><br />
    <!--Event, Location, Month Year-->
  </div>
</div>

<div class="slide top">
  <h1>組み込み向け言語Continuation based CのGCC上の実装</h1>
  <p>
    与儀健人 (並列信頼研究室)
    &lt;<a href="mailto:">kent@cr.ie.u-ryukyu.ac.jp</a>&gt;
  </p>
  <!--img src="../Slidy/keys.jpg" class="cover"
  alt="W3C as letters on 3 plastic buttons from a keyboard" /-->
  <!--h2>ゼミ, 河野研, Sep, 2009</h2-->
</div>

<div class="slide">
  <h1>研究の背景</h1>
  <ul>
    <li>ソフトウェアは今も大規模・複雑化が続いている</li>
    <li>しかし、ソフトウェアのバグを発見するのは難しい</li>
    <li style="marker:none;"/>
    <li>組込みやReal-time処理の需要も増大してる</li>
    <li>高速な応答が要求される組込み処理にはハードウェアに近い言語が適している</li>
  </ul>
  <p class="subtitle">なにが問題になるのか?</p>
  <ul>
    <li>組込みソフト、Real-time処理、通信プロトコル記述、どれも状態遷移ベース</li>
    <li>現存する記述言語は状態遷移の記述に向いていない</li>
    <li>スタックが状態を隠蔽するため、分割しにくい、検証が難しい</li>
  </ul>
</div>

<div class="slide" style="font-size:95%">
  <h1>研究目的</h1>
  <p class="subtitle">
  状態遷移記述をベースとした、より細かい単位でのプログラミングを実現する
  </p>
  <ul>
    <li>組込み、通信プロトコル、Real-time処理などの記述に向いている</li>
    <li>状態遷移を直接記述するため、タブロー法での検証に有利</li>
    <li>関数より細かく、ステートメントより大きい処理単位</li>
    <li>細かい単位でソースコードレベルの最適化を可能にする</li>
  </ul>
  <p class="subtitle">条件</p>
  <ul>
    <li>既存のソフトウェアは膨大であり、無駄にはできない</li>
    <li>互換性が必須条件</li>
    <li>Cからの変換、Cへの変換ができる事が望ましい</li>
  </ul>
</div>

<div class="slide">
  <h1>Continuation based Cの提案</h1>
  <p class="subtitle">継続を基本とする記述言語CbC</p>
  <ul>
    <li>環境を保持しない継続、<dfn>軽量継続</dfn>を導入</li>
    <li>軽量継続で<em class="weak">状態遷移が明確</em>になる</li>
    <li>関数の代わりとなる処理単位<dfn>コードセグメント</dfn></li>
    <li>関数 &gt; コードセグメント &gt; ステートメント</li>
    <li>for, whileなどのループも軽量継続で実現できる</li>
    <li>Cとの相互利用のための構文<dfn>環境付き継続</dfn>
      <ul>
	<li>このCとの相互利用可能なCbCは<em>C with Continuation</em>と呼ばれる</li>
      </ul>
    </li>
  </ul>
  <p class="subtitle"></p>
</div>

<div class="slide" style="font-size:95%;">
  <h1>コードセグメントと軽量継続の記述</h1>
  <pre style="float:right; width-max:45%">
<code>typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i;
  i = atoi(argv[1]);
  goto factor(i, print_fact);
}
<em>code factor(int x, NEXT next)</em> {
  goto factor0(1, x, next);
}
code factor0(int prod,int x,NEXT next) {
  if (x &gt;= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    <em>goto (*next)(prod);</em>
  }
}
code print_fact(int value) {
  printf("factorial = %d\n", value);
  exit(0);
} </code></pre>
  <p class="subtitle">実際のプログラム記述は?</p>
  <ul>
    <li>コードセグメント定義
    <ul>
      <li><code>codeキーワードで宣言</code></li>
      <li>書式は関数と同じ</li>
    </ul>
    </li>
    <li>軽量継続制御
    <ul>
      <li><code>goto</code>キーワードと引数</li>
      <li>コードセグメントの最初に飛ぶ</li>
      <li>コードセグメントポインタによる間接継続も可能</li>
    </ul>
    </li>
  </ul>
</div>

<div class="slide">
  <h1>これまでのCbC</h1>
  <p class="subtitle"></p>
  <dl>
    <dt>2000</dt>
    <dd>micro-cをベースとしたコンパイラの完成<br/>
      x86, PowerPC, ARM, MIPS.
    </dd>
    <dt>2002</dt>
    <dd>CbCを用いた分散計算</dd>
    <dt>2005</dt>
    <dd>CbCを用いたプログラム分割手法</dd>
    <dt>2006</dt>
    <dd>CbCによるSPUマシンのシミュレータ</dd>
    <dt>2007</dt>
    <dd>時相論理をベースとしたCbCプログラムの検証</dd>
    <dt>2008</dt>
    <dd>GCCをベースとしたコンパイラが開発される</dd>
    <dt>2010</dt>
    <dd>GCCベースコンパイラを実用レベルに拡張</dd>
  </dl>
</div>

<div class="slide">
  <h1>本研究での取り組み</h1>
  <p class="subtitle">取り組み</p>
  <dl>
    <dt>First</dt>
    <dd>GCCにて実用レベルのCbCプログラムを動作可能にする
      <ul>
        <li>軽量継続の実装、これまでの制限の除去</li>
	<li>x86アーキテクチャにて高速化を行った</li>
	<li>PowerPCアーキテクチャでの間接継続の追加</li>
      </ul>
    </dd>
    <dt>Second</dt>
    <dd>C言語との相互利用を可能にした</dd>
    <dt>Third</dt>
    <dd>ソースコードメンテナンス性の向上</dd>
  </dl>
</div>



<div class="slide">
  <h1>GNU コンパイラコレクション (GCC)</h1>
  <div style="width:50%;float:right;">
  <p class="subtitle">GCCでのコンパイルの流れ</p>
  <ul style="padding-left:3em">
    <li>フロントエンド</li>
    <li>ミドルエンド</li>
    <li>バックエンド</li>
  </ul>
  </div>
  <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow.png" />
</div>

<div class="slide">
  <h1>GNU コンパイラコレクション (GCC)</h1>
  <div style="width:50%;float:right;">
  <p class="subtitle">GCCでのコンパイルの流れ</p>
  <ul style="padding-left:3em">
    <li>フロントエンド</li>
    <li>ミドルエンド</li>
    <li>バックエンド</li>
  </ul>
  </div>
  <img style="width:80%;position:relative;top:-15%;" src="figures/gcc-flow2.png" />
</div>


<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">軽量継続を実装するには?</p>
  <ul>
    <li>河野先生の作ったmicro-cは元より軽量継続を考慮して良く設計されている</li>
    <li>micro-Cと同じ命令列を出力させるのは難しい</li>
    <li>関数コール(call命令)ではもちろんダメ</li>
    <li>必ず<em>jmp命令</em>を出力しないといけない</li>
    <li>スタックを拡張してはいけない</li>
    <li>しかしGCCでは<em>関数をベース</em>にしなければならない</li>
  </ul>
  <p class="subtitle"><dfn>末尾呼出</dfn>をGCCに<em>強制</em>させる必要がある</p>
</div>

<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">末尾呼出ってなに?</p>
  <img style="float:right; width:50%; margin:1em; " src="figures/tailcall.png" />
  <ul>
    <li>リターンの直前の関数呼び出しのこと</li>
    <li>GCCが最適化してくれる (<em>TCE</em>)</li>
    <li>元の関数に戻らないため少し高速に</li>
    <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
  </ul>
</div>

<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">末尾呼出ってなに?</p>
  <img style="float:right; width:50%; margin:1em; " src="figures/tailcallstack.png" />
  <ul>
    <li>リターンの直前の関数呼び出しのこと</li>
    <li>GCCが最適化してくれる (<em>TCE</em>)</li>
    <li>元の関数に戻らないため少し高速に</li>
    <li>スタックも積まなくてよいため、大幅なメモリ節約、アクセス軽減</li>
  </ul>
  <p class="subtitle incremental">この末尾呼出(TCE)を強制して軽量継続を実装!</p>
</div>

<div class="slide">
  <h1>First: x86における高速化</h1>
  <p class="subtitle">軽量継続は実装されたが、やはりmicro-cに比べると遅い</p>
  <ul>
    <li>特にx86アーキテクチャ</li>
    <li><em class="weak">あくまで関数がベース</em>なので</li>
    <li>関数呼出規約に従い全ての引数をスタックに格納してしまう</li>
    <li>これをレジスタにすれば高速化が可能</li>
  </ul>
  <p class="subtitle">fastcallの導入</p>
  <ul>
    <li>GCCの独自拡張機能</li>
    <li>引数の最初の<em>2つのみレジスタに</em>保持するようになる</li>
  </ul>
</div>

<div class="slide">
  <h1>First: x86における高速化</h1>
  <p class="subtitle">fastcallの強制</p>
  <ul>
    <li>通常は以下の様に定義される
<pre><code>__code current(int a, int b, int c) __attribute__((fastcall));
</code></pre></li>
    <li>しかしこれを毎回ユーザが書くのは変</li>
    <li>やはりフロントエンドにて、強制するべき</li>
    <li>型の構文木を生成した際にfastcall属性を付加</li>
  </ul>
  <p class="subtitle incremental">これで軽量継続制御が高速化される!</p>
</div>

<div class="slide">
  <h1>First: CbCコンパイラ実装の評価</h1>
  <p class="subtitle">CbCGCCとmicro-cで性能の比較</p>
  <ul>
    <li>CbCGCCが実用的になったことで、micro-cとの比較が可能に</li>
    <li>コンパイラの出力した実行ファイルを比較</li>
    <li>CbCでのquicksort例題を用意</li>
    <li>実行速度、ファイルサイズ</li>
    <li>比較対象はまずは旧CbCGCC、それとmicro-c</li>
  </ul>
  <p class="subtitle">実行環境</p>
  <ul>
    <li>CbCGCC、micro-cでともに実行可能な環境を選択</li>
    <li>アーキテクチャは x86, PowerPC(Cell含む)</li>
    <li>OSはLinuxとOS Xを使用する</li>
  </ul>
</div>

<div class="slide">
  <h1>First: 性能評価(速度比較) vs.旧ver</h1>
  <p class="subtitle">速度測定結果(単位:秒)</p>
  <table>
    <tr>
      <th></th>
      <th colspan="2">新CbCGCC</th>
      <th colspan="2">旧CbCGCC</th>
    </tr>
    <tr>
      <td></td>
      <th>最適化無し</th>
      <th>最適化有り</th>
      <th>最適化無し</th>
      <th>最適化有り</th>
    </tr>
    <tr>
      <td>x86/OS X</td>
      <td>5.907</td>
      <td>2.434</td>
      <td>4.668</td>
      <td>3.048</td>
    </tr>
    <tr>
      <td>x86/Linux</td>
      <td>5.715</td>
      <td>2.401</td>
      <td>4.525</td>
      <td>2.851</td>
    </tr>
  </table>
  <p class="subtitle">評価</p>
  <ul>
    <li>最適化無の場合は遅くなった </li>
    <li>最適化を行うと、<em>約20%の高速化に成功</em></li>
    <li>fastcallの効果が十分に出ている</li>
  </ul>
</div>


<div class="slide">
  <h1>First: 性能評価(速度比較)</h1>
  <p class="subtitle">速度測定結果(単位:秒)</p>
  <table>
    <tr>
      <td></td>
      <td>最適化なしのGCC</td>
      <td>最適化付きのGCC</td>
      <td>micro-c</td>
    </tr>
    <tr>
      <td>x86/OS X</td>
      <td>5.901</td>
      <td>2.434</td>
      <td>2.857</td>
    </tr>
    <tr>
      <td>x86/Linux</td>
      <td>5.732</td>
      <td>2.401</td>
      <td>2.254</td>
    </tr>
    <tr>
      <td>ppc/OS X</td>
      <td>14.875</td>
      <td>2.146</td>
      <td>4.811</td>
    </tr>
    <tr>
      <td>ppc/Linux</td>
      <td>19.793</td>
      <td>3.955</td>
      <td>6.454</td>
    </tr>
    <tr>
      <td>ppc/PS3</td>
      <td>39.176</td>
      <td>5.874</td>
      <td>11.121</td>
    </tr>
  </table>
  <p class="subtitle">結果(micro-cとの比較)</p>
  <ul>
    <li>x86では速度にあまり差が出なかった</li>
    <li>x86に特化しているmicro-cと差がないのは<em>とても良い結果</em></li>
    <li>PowerPCではCbCGCCが<em>2倍ほど早い</em></li>
  </ul>
  <p class="subtitle">この違いはどこから?</p>
  <ul style="font-size:95%;">
    <li>実際にアセンブラを出力して比較、その結果</li>
    <li>x86は自由に使えるレジスタが少ないため、CbCGCCの最適化が効きにくい</li>
    <li>演算の度にメモリ読み込み、演算、書き込みが発生する</li>
    <li><em>レジスタの多いアーキテクチャではCbCGCCが断然有利になる</em></li>
    <li>またCbC言語そのものもレジスタが多いアーキテクチャで有利</li>
  </ul>
</div>


<div class="slide">
  <h1>Second: Cとの相互利用</h1>
  <p class="subtitle">なぜそれが必要か</p>
  <ul>
    <li>既存のソフトウェアを無駄にはできない</li>
    <li></li>
    <li>ソースコード上での互換性がある事が望ましい</li>
    <li>CbCからCの関数を呼び出すのは問題ない</li>
    <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
  </ul>
  <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
  <ul>
    <li>軽量継続に、スタックの情報を加える</li>
    <li>関数からのみ使用可能</li>
  </ul>
</div>

<div class="slide" style="font-size:95%;">
  <h1>Second: Cとの相互利用</h1>
  <pre style="float:right; width-max:45%">
<code>typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i,a;
  i = atoi(argv[1]);
  <em>a = factor(i);</em>
  printf("%d! = %d\n", a);
}
int factor(int x) {
  NEXT ret = <em>__return</em>;
  goto factor0(1, x, ret);
}
code
factor0(int prod,int x,NEXT next) {
  if (x &gt;= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    <em>goto (*next)(prod);</em>
  }
}
</code></pre>
  <p class="subtitle">環境付き継続の使用例</p>
  <ul>
    <li><code><em>__retunr</em></code>で表される特殊なコードセグメント</li>
    <li>コードセグメントからは通常のコードセグメントポインタに見える</li>
    <li>この<code>__return</code>に継続すると、元の関数の環境にリターン</li>
  </ul>
</div>

<div class="slide" style="font-size:95%;">
  <h1>Second: Cとの相互利用</h1>
  <p class="subtitle">内部関数を用いた実装</p>
  <ul>
    <li><code>__return</code>が参照された場合にGCCが自動で内部関数を定義する</li>
    <li>内部関数の中からは外の関数にgotoして脱出</li>
  </ul>
  <pre><code>int factor(int x) {
   int retval;

   <em class="weak">code __return(int val) {
      retval = val;
      goto label;
   }
   if (0) {
     label:
      return retval;
   }</em>

   NEXT ret = <em>__return</em>;
   goto factor0(1, x, ret);
} </code></pre>
</div>


<div class="slide" style="font-size:95%;">
  <h1>Second: Cとの相互利用・評価</h1>
  <p class="subtitle">この取り組みにより</p>
  <ul>
    <li>これにより、<dfn>C with Continuation</dfn> の仕様を満たした</li>
    <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
  </ul>
</div>



<div class="slide">
  <h1>まとめ</h1>
  <p class="subtitle">本研究での取り組み</p>
  <dl>
    <dt>First</dt>
    <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
      <ul>
	<li><em>軽量継続における引数順序の制限を取り除いた</em></li>
	<li>PowerPCでの間接継続の制限を取り除いた</li>
	<li><em>x86アーキテクチャにて高速化を行った</em></li>
      </ul>
    </dd>
    <dt>Second</dt>
    <dd><em>Cとの相互利用性の向上</em></dd>
    <dt>Third</dt>
    <dd>ソースコードメンテナンス性の向上</dd>
  </dl>
</div>

<div class="slide" style="font-size:95%;">
  <h1>まとめ</h1>
  <p class="subtitle">本研究での成果</p>
  <dl>
    <dt>成果1</dt>
    <dd>CbCGCCがCとの相互利用も含むCbCのフルセットとして利用可能になった
    <dt>成果2</dt>
    <dd>CbCが多数のアーキテクチャに対応
      <ul>
        <li>20以上のアーキテクチャ</li>
	<li>特に64bitのx86, SPUがうれしい</li>
      </ul> </dd>
    <dt>成果3</dt>
    <dd>CbCの高速化
      <ul>
	<li>x86においてmicro-cと互角の速度を達成</li>
	<li>PowerPCでは2倍の速度</li>
      </ul></dd>
  </dl>
</div>

<div class="slide">
  <h1>今後の課題</h1>
  <p class="subtitle"></p>
  <ul>
    <li>Real-time、組込み向けに実用的なCbCプログラムの例題が欲しい</li>
    <li>タブロー方を用いた検証</li>
    <li>TaskManagerのCbC実装</li>
  </ul>
  <p class="subtitle">CbC言語の今後</p>
  <ul>
    <li>オブジェクティブなCbCの設計</li>
    <li>データセグメントの導入</li>
    <li>スケジューラのためのリフレクション</li>
  </ul>
</div>


<div class="slide">
  <h1>おわり</h1>
  <p class="subtitle">ありがとうございました</p>
</div>




















<div class="slide">
  <h1>Continuation based C</h1>
  <ul>
    <li>言語仕様</li>
    <li>return-callから軽量継続へ</li>
    <li>コードセグメント</li>
    <li>状態遷移に適した言語</li>
    <li>Cとの互換性</li>
  </ul>
</div>


<div class="slide">
  <h1></h1>
  <p class="subtitle"></p>
  <ul>
    <li></li>
    <li></li>
  </ul>
</div>
<div class="slide">
  <h1></h1>
  <p class="subtitle"></p>
  <ul>
    <li></li>
    <li></li>
  </ul>
</div>

<div class="slide">
  <h1></h1>
  <p class="subtitle"></p>
  <ul>
    <li></li>
    <li></li>
  </ul>
</div>


<div class="slide">
  <h1>First: PowerPCでの間接継続</h1>
  <p class="subtitle"></p>
  <ul>
    <li></li>
  </ul>
  <p class="subtitle"></p>
  <div style="width:70%;margin:1em auto 0;">
<pre><code>
</code></pre>
  </div>
</div>

<div class="slide">
  <h1>継続制御での並列代入</h1>
  <p class="subtitle" style="margin:0 1em 0.1em;">
    本当に最適化で余分なコードが消えるのか?
  </p>
  <div style="width:45%;float:left;margin-left:1em;">
  最適化しない場合
<pre style="margin-top:0"><code> _test:
    stwu r1,-64(r1)
    mr r30,r1
    stw r3,88(r30)
    stw r4,92(r30)
    stw r5,96(r30)
    lwz r0,92(r30)
    stw r0,32(r30)
    lwz r0,96(r30)
    addic r0,r0,1
    stw r0,28(r30)
    lwz r0,88(r30)
    stw r0,24(r30)
    lwz r3,32(r30)
    lwz r4,28(r30)
    lwz r5,24(r30)
    addi r1,r30,64
    lwz r30,-8(r1)
    lwz r31,-4(r1)
    b L_next$stub
</code></pre>
  </div>
  <div style="width:45%;float:right;margin-right:1em;">
  最適化した場合
<pre><code>
_test:
    mr r0,r3
    mr r3,r4
    mr r4,r5
    mr r5,r0
    b L_next$stub
</code></pre>
  </div>
  <div style="width:50%;float:right">
  <ul>
    <li>r3:=a, r4:=b, r5:=c</li>
    <li>最適化しないとload, storeが満載</li>
    <li>最適化すると無駄なload, store命令が消えている</li>
    <li>実際はr0を使って4命令で入れ替えられる!</li>
  </ul>
  </div>
</div>


<div class="slide">
  <h1>継続とはなんなのか?</h1>
  <p class="subtitle">継続</p>
  <ul>
    <li>現在の処理を続行するための情報
      <ul>
        <li>Cならば続く命令のアドレスや</li>
        <li>命令に必要な値、</li>
        <li>スタックなど、その環境全てを含む</li>
      </ul>
    </li>
  </ul>
  <p class="subtitle">CbCでの軽量継続</p>
  <ul>
    <li>継続からスタックに関する情報を落とす</li>
    <li>続く命令とデータのみのシンプルな継続</li>
    <li>命令は<em>コードセグメント</em>、引数は<em>インタフェイス</em>と呼ばれる</li>
  </ul>
</div>

<div class="slide" style="font-size:95%;">
  <h1>コードセグメントと軽量継続の記述</h1>
  <pre style="float:right; width-max:45%">
<code>typedef code (*NEXT)(int);
int main(int argc, char **argv) {
  int i;
  i = atoi(argv[1]);
  goto factor(i, print_fact);
}
<em>code factor(int x, NEXT next)</em> {
  goto factor0(1, x, next);
}
code factor0(int prod,int x,NEXT next) {
  if (x &gt;= 1) {
    goto factor0(prod*x, x-1, next);
  } else {
    <em>goto (*next)(prod);</em>
  }
}
code print_fact(int value) {
  printf("factorial = %d\n", value);
  exit(0);
} </code></pre>
  <p class="subtitle">実際のプログラム記述は?</p>
  <ul>
    <li>コードセグメント定義
    <ul>
      <li><code>codeキーワードで宣言</code></li>
      <li>書式は関数と同じ</li>
    </ul>
    </li>
    <li>軽量継続制御
    <ul>
      <li><code>goto</code>キーワードと引数</li>
      <li>コードセグメントの最初に飛ぶ</li>
      <li>コードセグメントポインタによる間接継続も可能</li>
    </ul>
    </li>
  </ul>
</div>

<div class="slide">
  <h1>Cとの比較について</h1>
  <p class="subtitle">quicksort例題をCと比較すると</p>
  <ul>
    <li>現在のところ、遅くなる</li>
    <li>問題はquicksortという例題では必ずスタックが必要だということ</li>
    <li>例題ではスタックを自前の構造体で用意している</li>
    <li>そのため、ハードウェアで考慮されたスタックよりは遅い</li>
    <li>状態遷移ベースの例題を作りたい</li>
  </ul>
</div>


<div class="slide" style="font-size:95%;">
  <h1>fastcall</h1>
  <p class="subtitle">実際の出力アセンブラ</p>
  <div style="width:50%;float:left;margin-left:auto;">
    <p style="margin:0;text-align:center">fastcallにした場合</p>
<pre><code>current:
    subl    $12, %esp
    movl    $30, 16(%esp)
    movl    $20, %edx
    movl    $10, %ecx
    addl    $12, %esp
    jmp     next
</code></pre>
  </div>
  <div style="width:50%;float:right;margin-right:auto;">
    <p style="margin:0;text-align:center">normalcallの場合</p>
<pre><code>current:
    pushl   %ebp
    movl    %esp, %ebp
    movl    $30, 16(%ebp)
    movl    $20, 12(%ebp)
    movl    $10, 8(%ebp)
    leave
    jmp     next
</code></pre>
  </div>
  <br clear="all" />
  <ul>
    <li>命令数ではほとんど変化はない</li>
    <li>引数2つがレジスタecxとedxに格納されるようになった</li>
    <li>そのためメモリアクセスが減る</li>
    <li>これで高速化されるはず</li>
  </ul>
</div>

<div class="slide">
  <h1>First: 性能評価(サイズ比較)</h1>
  <p class="subtitle">ファイルサイズの比較</p>
  <ul>
    <li>組み込み系ではメモリ使用量が肝心</li>
    <li>CbCGCCのサイズ最適化、速度最適化も対象とする</li>
    <li>デバグ情報を付加しない、strip後のファイルサイズを比較</li>
  </ul>
  <p class="subtitle">結果</p>
  <table>
    <tr>
      <td></td>
      <th>CbCGCC<br/>速度最適化</th>
      <th>CbCGCC<br/>サイズ最適化</th>
      <th>micro-c</th>
    </tr>
    <tr>
      <td>x86/OS X</td>
      <td>9176</td>
      <td>9176</td>
      <td>9172</td>
    </tr>
    <tr>
      <td>x86/Linux</td>
      <td>5752</td>
      <td>5752</td>
      <td>5796</td>
    </tr>
    <tr>
      <td>ppc/OS X</td>
      <td>8576</td>
      <td>8576</td>
      <td>12664</td>
    </tr>
    <tr>
      <td>ppc/Linux</td>
      <td>10068</td>
      <td>10068</td>
      <td>9876</td>
    </tr>
    <tr>
      <td>ppc/PS3</td>
      <td>6960</td>
      <td>6728</td>
      <td>8636</td>
    </tr>
  </table>
  <p class="subtitle">結果考察</p>
  <ul>
    <li>x86ではファイルサイズの差がない</li>
    <li>ppcではOSによって違うが、OS Xでは3分の2に抑えることができている</li>
    <li>サイズ最適化は必要ない、<em>速度最適化で充分</em></li>
  </ul>
</div>

<div class="slide">
  <h1>並列代入</h1>
  <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
  <ol>
    <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
    <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
  </ol>
  <p class="subtitle">問題となる例</p>
<pre><code>code somesegment(int a, int b, int c) {
  /∗ do something ∗/
  goto nextsegment(b, c, a);
}
</code></pre>
  <ul>
    <li><code>(a,b,c) = (b,c,a)</code>と本質的に同じ。これが<dfn>並列代入</dfn></li>
    <li><code>a=b,b=c,c=a</code>ではだめ。aの値が失われる</li>
    <li>必ず一つ(1ワード)以上の一時変数が必要になる</li>
  </ul>
  <p class="subtitle">次の様に構文木を変更する</p>
<pre><code>code somesegment(int a, int b, int c) {
  int a1, b1, c1;
  /∗ do something ∗/
  a1=a; b1=b; c1=c;
  goto nextsegment(b1, c1, a1);
}
</code></pre>
  <ul>
    <li>これにより、引数順序を考える必要はなくなる</li>
    <li>代わりに、メモリアクセスが大量に発生</li>
    <li>しかし、これはGCCの最適化で除去される</li>
  </ul>
</div>



</body>
</html>