view recital-slide/slide.html @ 17:7c25b2856f27

up recital-slide
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2010 14:09:50 +0900
parents d9b85f041908
children
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">
  <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>これまでの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: 軽量継続の実装</h1>
  <p class="subtitle">プログラム実行時のスタックの変化</p>
  <img style="float:right; width:50%; margin:1em; " src="figures/interfacestack.png" />
  <ul>
    <li>スタックの拡張はしなくなる</li>
    <li>継続されるデータはインタフェイスのみ</li>
    <li>継続の際に古いデータは上書きされる</li>
  </ul>
</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>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>__return</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>Continuation based C</dfn> の全仕様を満たした</li>
    <li>ソースコードレベルで、Cと相互に利用することが可能になった</li>
  </ul>
</div>



<div class="slide">
  <h1>まとめ</h1>
  <p class="subtitle">本研究での取り組み</p>
  <dl>
    <dt>First</dt>
    <dd><em>CbCGCCにて実用レベルのCbCプログラムが動作可能となった</em>
      <ul>
	<li>軽量継続における引数順序の制限を取り除いた</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>継続とはなんなのか?</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>これまでの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>
      </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>GCC フロントエンド</h1>
  <p class="subtitle">GCCにおける構文解析部</p>
  <ul class="outline">
    <li>C,Java,Adaなど、言語毎に違う</li>
    <li>解析した構文は<dfn>Generic</dfn>という構文木に構築</li>
    <li>さらに静的単一代入と呼ばれる手法で<dfn>GIMPLE</dfn>という構文木に変換</li>
    <li>最終的にこのGIMPLE構文木をミドルエンドに渡す</li>
    <li>GIMPLEの内部表現例
  <pre><code>
 &lt;call_expr 0xb7bc7850
    type &lt;void_type 0xb7cc9270 void VOID
        align 8 symtab 0 alias set -1 canonical type 0xb7cc9270
        pointer_to_this &lt;pointer_type 0xb7cc92d8&gt;&gt;
    side-effects addressable tree_5
    fn &lt;var_decl 0xb7d65370 D.2156
        type &lt;pointer_type 0xb7da74e0 type &lt;function_type 0xb7da7478&gt;
            unsigned SI
            size &lt;integer_cst 0xb7cb36ac constant 32&gt;
            unit size &lt;integer_cst 0xb7cb3498 constant 4&gt;
            align 32 symtab 0 alias set -1 structural equality&gt;
        used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
        align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
        (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
        (const_int -12 [0xfffffff4])) [0 D.2156+0 S4 A32])
        chain &lt;var_decl 0xb7d653c8 D.2157 type &lt;pointer_type 0xb7cc92d8&gt;
            used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
            align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
            (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
        (const_int -8 [0xfffffff8])) [0 D.2157+0 S4 A32]) chain &lt;var_decl 0xb7d65420 D.2158&gt;&gt;&gt; arg 0 &lt;var_decl 0xb7d653c8 D.2157&gt;
    arg 1 &lt;var_decl 0xb7d65420 D.2158
        type &lt;pointer_type 0xb7da7270 stack type &lt;void_type 0xb7cc9270 void&gt;
            sizes-gimplified unsigned SI size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
            align 32 symtab 0 alias set -1 canonical type 0xb7cc92d8
            pointer_to_this &lt;pointer_type 0xb7bb7000&gt;&gt;
        used unsigned SI file quicksort/quicksort_cbc.cbc line 29 col 2 size &lt;integer_cst 0xb7cb36ac 32&gt; unit size &lt;integer_cst 0xb7cb3498 4&gt;
        align 32 context &lt;function_decl 0xb7da2c80 returner&gt;
        (mem/f/c/i:SI (plus:SI (reg/f:SI 54 virtual-stack-vars)
        (const_int -4 [0xfffffffc])) [0 D.2158+0 S4 A32])&gt;
    quicksort/quicksort_cbc.cbc:29:7&gt;
  </code></pre>
    <p class="subtitle">全ての構文はこのGIMPLEで表される</p>
    </li>
  </ul>
  <p class="subtitle incremental">つまり、主に修正すべきはこのフロントエンドとなる</p>
</div>

<div class="slide" style="font-size:95%">
  <h1>GCC ミドルエンド</h1>
  <p class="subtitle">GIMPLEからRTLへの変換と最適化</p>
  <ul class="outline">
    <li><dfn>pass</dfn>と呼ばれる様々な処理の集合体</li>
    <li>登録されたpassを一つ一つ実行する</li>
    <li>最初にGIMPLEの最適化がたくさんある</li>
    <li>そしてもっとも重要なGIMPLEから<dfn>RTL</dfn>への変換</li>
    <li>最後にRTLの最適化がまた大量にある
      <pre style="font-size:80%"><code>
  p = &amp;all_lowering_passes;
  NEXT_PASS (pass_remove_useless_stmts);
  NEXT_PASS (pass_mudflap_1);
  NEXT_PASS (pass_lower_omp);
  NEXT_PASS (pass_lower_cf);
  NEXT_PASS (pass_refactor_eh);
  NEXT_PASS (pass_lower_eh);
  NEXT_PASS (pass_build_cfg);
  NEXT_PASS (pass_lower_complex_O0);
  NEXT_PASS (pass_lower_vector);
#ifndef noCbC
  //NEXT_PASS (pass_warn_function_return);
#else
  NEXT_PASS (pass_warn_function_return);
#endif
  NEXT_PASS (pass_build_cgraph_edges);
  NEXT_PASS (pass_inline_parameters);
  *p = NULL;

  /* Interprocedural optimization passes.  */
  p = &amp;all_ipa_passes;
  NEXT_PASS (pass_ipa_function_and_variable_visibility);
  NEXT_PASS (pass_ipa_early_inline);
    {
      struct opt_pass **p = &amp;pass_ipa_early_inline.pass.sub;
      NEXT_PASS (pass_early_inline);
      NEXT_PASS (pass_inline_parameters);
      NEXT_PASS (pass_rebuild_cgraph_edges);
    }
  NEXT_PASS (pass_early_local_passes);
    {
      struct opt_pass **p = &amp;pass_early_local_passes.pass.sub;
      NEXT_PASS (pass_tree_profile);
      NEXT_PASS (pass_cleanup_cfg);
      NEXT_PASS (pass_init_datastructures);
      NEXT_PASS (pass_expand_omp);

      NEXT_PASS (pass_referenced_vars);
      NEXT_PASS (pass_reset_cc_flags);
      NEXT_PASS (pass_build_ssa);
      NEXT_PASS (pass_early_warn_uninitialized);
      NEXT_PASS (pass_all_early_optimizations);
	{
	  struct opt_pass **p = &amp;pass_all_early_optimizations.pass.sub;
	  NEXT_PASS (pass_rebuild_cgraph_edges);
	  NEXT_PASS (pass_early_inline);
	  NEXT_PASS (pass_rename_ssa_copies);
	  NEXT_PASS (pass_ccp);
	  NEXT_PASS (pass_forwprop);
	  NEXT_PASS (pass_update_address_taken);
	  NEXT_PASS (pass_sra_early);
	  NEXT_PASS (pass_copy_prop);
	  NEXT_PASS (pass_merge_phi);
	  NEXT_PASS (pass_cd_dce);
	  NEXT_PASS (pass_simple_dse);
	  NEXT_PASS (pass_tail_recursion);
	  NEXT_PASS (pass_convert_switch);
          NEXT_PASS (pass_profile);
	}
      NEXT_PASS (pass_release_ssa_names);
      NEXT_PASS (pass_rebuild_cgraph_edges);
      NEXT_PASS (pass_inline_parameters);
    }
  NEXT_PASS (pass_ipa_increase_alignment);
  NEXT_PASS (pass_ipa_matrix_reorg);
  NEXT_PASS (pass_ipa_cp);
  NEXT_PASS (pass_ipa_inline);
  NEXT_PASS (pass_ipa_reference);
  NEXT_PASS (pass_ipa_pure_const); 
  NEXT_PASS (pass_ipa_type_escape);
  NEXT_PASS (pass_ipa_pta);
  NEXT_PASS (pass_ipa_struct_reorg);  
  *p = NULL;

  /* These passes are run after IPA passes on every function that is being
     output to the assembler file.  */
  p = &amp;all_passes;
  NEXT_PASS (pass_all_optimizations);
    {
      struct opt_pass **p = &amp;pass_all_optimizations.pass.sub;
      /* Initial scalar cleanups before alias computation.
	 They ensure memory accesses are not indirect wherever possible.  */
      NEXT_PASS (pass_strip_predict_hints);
      NEXT_PASS (pass_update_address_taken);
      NEXT_PASS (pass_rename_ssa_copies);
      NEXT_PASS (pass_complete_unrolli);
      NEXT_PASS (pass_ccp);
      NEXT_PASS (pass_forwprop);
      /* Ideally the function call conditional
	 dead code elimination phase can be delayed
	 till later where potentially more opportunities
	 can be found.  Due to lack of good ways to
	 update VDEFs associated with the shrink-wrapped
	 calls, it is better to do the transformation
	 here where memory SSA is not built yet.  */
      NEXT_PASS (pass_call_cdce);
      /* pass_build_alias is a dummy pass that ensures that we
	 execute TODO_rebuild_alias at this point.  Re-building
	 alias information also rewrites no longer addressed
	 locals into SSA form if possible.  */
      NEXT_PASS (pass_build_alias);
      NEXT_PASS (pass_return_slot);
      NEXT_PASS (pass_phiprop);
      NEXT_PASS (pass_fre);
      NEXT_PASS (pass_copy_prop);
      NEXT_PASS (pass_merge_phi);
      NEXT_PASS (pass_vrp);
      NEXT_PASS (pass_dce);
      NEXT_PASS (pass_cselim);
      NEXT_PASS (pass_tree_ifcombine);
      NEXT_PASS (pass_phiopt);
      NEXT_PASS (pass_tail_recursion);
      NEXT_PASS (pass_ch);
      NEXT_PASS (pass_stdarg);
      NEXT_PASS (pass_lower_complex);
      NEXT_PASS (pass_sra);
      NEXT_PASS (pass_rename_ssa_copies);
      NEXT_PASS (pass_dominator);
      /* The only const/copy propagation opportunities left after
	 DOM should be due to degenerate PHI nodes.  So rather than
	 run the full propagators, run a specialized pass which
	 only examines PHIs to discover const/copy propagation
	 opportunities.  */
      NEXT_PASS (pass_phi_only_cprop);
      NEXT_PASS (pass_dse);
      NEXT_PASS (pass_reassoc);
      NEXT_PASS (pass_dce);
      NEXT_PASS (pass_forwprop);
      NEXT_PASS (pass_phiopt);
      NEXT_PASS (pass_object_sizes);
      NEXT_PASS (pass_ccp);
      NEXT_PASS (pass_copy_prop);
      NEXT_PASS (pass_fold_builtins);
      NEXT_PASS (pass_cse_sincos);
      NEXT_PASS (pass_split_crit_edges);
      NEXT_PASS (pass_pre);
      NEXT_PASS (pass_sink_code);
      NEXT_PASS (pass_tree_loop);
	{
	  struct opt_pass **p = &amp;pass_tree_loop.pass.sub;
	  NEXT_PASS (pass_tree_loop_init);
	  NEXT_PASS (pass_copy_prop);
	  NEXT_PASS (pass_dce_loop);
	  NEXT_PASS (pass_lim);
	  NEXT_PASS (pass_predcom);
	  NEXT_PASS (pass_tree_unswitch);
	  NEXT_PASS (pass_scev_cprop);
	  NEXT_PASS (pass_empty_loop);
	  NEXT_PASS (pass_record_bounds);
	  NEXT_PASS (pass_check_data_deps);
	  NEXT_PASS (pass_loop_distribution);
	  NEXT_PASS (pass_linear_transform);
	  NEXT_PASS (pass_graphite_transforms);
	  NEXT_PASS (pass_iv_canon);
	  NEXT_PASS (pass_if_conversion);
	  NEXT_PASS (pass_vectorize);
	    {
	      struct opt_pass **p = &amp;pass_vectorize.pass.sub;
	      NEXT_PASS (pass_lower_vector_ssa);
	      NEXT_PASS (pass_dce_loop);
	    }
	  NEXT_PASS (pass_complete_unroll);
	  NEXT_PASS (pass_parallelize_loops);
	  NEXT_PASS (pass_loop_prefetch);
	  NEXT_PASS (pass_iv_optimize);
	  NEXT_PASS (pass_tree_loop_done);
	}
      NEXT_PASS (pass_cse_reciprocals);
      NEXT_PASS (pass_convert_to_rsqrt);
      NEXT_PASS (pass_reassoc);
      NEXT_PASS (pass_vrp);
      NEXT_PASS (pass_dominator);
      /* The only const/copy propagation opportunities left after
	 DOM should be due to degenerate PHI nodes.  So rather than
	 run the full propagators, run a specialized pass which
	 only examines PHIs to discover const/copy propagation
	 opportunities.  */
      NEXT_PASS (pass_phi_only_cprop);
      NEXT_PASS (pass_cd_dce);
      NEXT_PASS (pass_tracer);

      /* FIXME: If DCE is not run before checking for uninitialized uses,
	 we may get false warnings (e.g., testsuite/gcc.dg/uninit-5.c).
	 However, this also causes us to misdiagnose cases that should be
	 real warnings (e.g., testsuite/gcc.dg/pr18501.c).
	 
	 To fix the false positives in uninit-5.c, we would have to
	 account for the predicates protecting the set and the use of each
	 variable.  Using a representation like Gated Single Assignment
	 may help.  */
      NEXT_PASS (pass_late_warn_uninitialized);
      NEXT_PASS (pass_dse);
      NEXT_PASS (pass_forwprop);
      NEXT_PASS (pass_phiopt);
      NEXT_PASS (pass_tail_calls);
      NEXT_PASS (pass_rename_ssa_copies);
      NEXT_PASS (pass_uncprop);
    }
  NEXT_PASS (pass_del_ssa);
  NEXT_PASS (pass_nrv);
  NEXT_PASS (pass_mark_used_blocks);
  NEXT_PASS (pass_cleanup_cfg_post_optimizing);

  NEXT_PASS (pass_warn_function_noreturn);
  NEXT_PASS (pass_free_datastructures);
  NEXT_PASS (pass_mudflap_2);

  NEXT_PASS (pass_free_cfg_annotations);
  <em>NEXT_PASS (pass_expand);</em>
  NEXT_PASS (pass_rest_of_compilation);
    {
      struct opt_pass **p = &amp;pass_rest_of_compilation.pass.sub;
      NEXT_PASS (pass_init_function);
      NEXT_PASS (pass_jump);
      NEXT_PASS (pass_rtl_eh);
      NEXT_PASS (pass_initial_value_sets);
      NEXT_PASS (pass_unshare_all_rtl);
      NEXT_PASS (pass_instantiate_virtual_regs);
      NEXT_PASS (pass_into_cfg_layout_mode);
      NEXT_PASS (pass_jump2);
      NEXT_PASS (pass_lower_subreg);
      NEXT_PASS (pass_df_initialize_opt);
      NEXT_PASS (pass_cse);
      NEXT_PASS (pass_rtl_fwprop);
      NEXT_PASS (pass_gcse);
      NEXT_PASS (pass_rtl_ifcvt);
      /* Perform loop optimizations.  It might be better to do them a bit
	 sooner, but we want the profile feedback to work more
	 efficiently.  */
      NEXT_PASS (pass_loop2);
	{
	  struct opt_pass **p = &amp;pass_loop2.pass.sub;
	  NEXT_PASS (pass_rtl_loop_init);
	  NEXT_PASS (pass_rtl_move_loop_invariants);
	  NEXT_PASS (pass_rtl_unswitch);
	  NEXT_PASS (pass_rtl_unroll_and_peel_loops);
	  NEXT_PASS (pass_rtl_doloop);
	  NEXT_PASS (pass_rtl_loop_done);
	  *p = NULL;
	}
      NEXT_PASS (pass_web);
      NEXT_PASS (pass_jump_bypass);
      NEXT_PASS (pass_cse2);
      NEXT_PASS (pass_rtl_dse1);
      NEXT_PASS (pass_rtl_fwprop_addr);
      NEXT_PASS (pass_reginfo_init);
      NEXT_PASS (pass_inc_dec);
      NEXT_PASS (pass_initialize_regs);
      NEXT_PASS (pass_outof_cfg_layout_mode);
      NEXT_PASS (pass_ud_rtl_dce);
      NEXT_PASS (pass_combine);
      NEXT_PASS (pass_if_after_combine);
      NEXT_PASS (pass_partition_blocks);
      NEXT_PASS (pass_regmove);
      NEXT_PASS (pass_split_all_insns);
      NEXT_PASS (pass_lower_subreg2);
      NEXT_PASS (pass_df_initialize_no_opt);
      NEXT_PASS (pass_stack_ptr_mod);
      NEXT_PASS (pass_mode_switching);
      NEXT_PASS (pass_see);
      NEXT_PASS (pass_match_asm_constraints);
      NEXT_PASS (pass_sms);
      NEXT_PASS (pass_sched);
      NEXT_PASS (pass_subregs_of_mode_init);
      NEXT_PASS (pass_ira);
      NEXT_PASS (pass_subregs_of_mode_finish);
      NEXT_PASS (pass_postreload);
	{
	  struct opt_pass **p = &amp;pass_postreload.pass.sub;
	  NEXT_PASS (pass_postreload_cse);
	  NEXT_PASS (pass_gcse2);
	  NEXT_PASS (pass_split_after_reload);
	  NEXT_PASS (pass_branch_target_load_optimize1);
	  NEXT_PASS (pass_thread_prologue_and_epilogue);
	  NEXT_PASS (pass_rtl_dse2);
	  NEXT_PASS (pass_rtl_seqabstr);
	  NEXT_PASS (pass_stack_adjustments);
	  NEXT_PASS (pass_peephole2);
	  NEXT_PASS (pass_if_after_reload);
	  NEXT_PASS (pass_regrename);
	  NEXT_PASS (pass_cprop_hardreg);
	  NEXT_PASS (pass_fast_rtl_dce);
	  NEXT_PASS (pass_reorder_blocks);
	  NEXT_PASS (pass_branch_target_load_optimize2);
	  NEXT_PASS (pass_leaf_regs);
	  NEXT_PASS (pass_split_before_sched2);
	  NEXT_PASS (pass_sched2);
	  NEXT_PASS (pass_stack_regs);
	    {
	      struct opt_pass **p = &amp;pass_stack_regs.pass.sub;
	      NEXT_PASS (pass_split_before_regstack);
	      NEXT_PASS (pass_stack_regs_run);
	    }
	  NEXT_PASS (pass_compute_alignments);
	  NEXT_PASS (pass_duplicate_computed_gotos);
	  NEXT_PASS (pass_variable_tracking);
	  NEXT_PASS (pass_free_cfg);
	  NEXT_PASS (pass_machine_reorg);
	  NEXT_PASS (pass_cleanup_barriers);
	  NEXT_PASS (pass_delay_slots);
	  NEXT_PASS (pass_split_for_shorten_branches);
	  NEXT_PASS (pass_convert_to_eh_region_ranges);
	  NEXT_PASS (pass_shorten_branches);
	  NEXT_PASS (pass_set_nothrow_function_flags);
	  NEXT_PASS (pass_final);
	}
      NEXT_PASS (pass_df_finish);
    }
  NEXT_PASS (pass_clean_state);
  *p = NULL;
      </code></pre>
    </li>
  </ul>
  <p class="subtitle">RTL</p>
  <ul class="outline">
    <li>一般的には中間コードとも呼ばれる</li>
    <li>アセンブラに変換する前の、アーキテクチャに依存しないマシン語表現</li>
    <li>RTLの例
<pre><code>(insn 27 26 0 quicksort/quicksort_cbc.cbc:29 (parallel [
            (set (reg/f:SI 7 sp)
                (plus:SI (reg/f:SI 7 sp)
                    (const_int -1024 [0xfffffc00])))
            (clobber (reg:CC 17 flags))
        ]) -1 (nil))
</code></pre>
    </li>
  </ul>
</div>

<div class="slide">
  <h1>バックエンド</h1>
  <p class="subtitle">RTLからアセンブラに変換する処理</p>
  <ul class="outline">
    <li><dfn>Machine Description(md)</dfn>と呼ばれる変換規則を用いる</li>
    <li>アーキテクチャ毎にこのmdが必要になる</li>
    <li>新しいアーキテクチャの対応はこのバックエンドを修正することになる</li>
    <li>mdの例
    <pre><code>
(define_insn "cmpdi_ccno_1_rex64"
  [(set (reg FLAGS_REG)
        (compare (match_operand:DI 0 "nonimmediate_operand" "r,?mr")
                 (match_operand:DI 1 "const0_operand" "")))]
  "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCNOmode)"
  "@
   test{q}\t%0, %0
   cmp{q}\t{%1, %0|%0, %1}"
  [(set_attr "type" "test,icmp")
   (set_attr "length_immediate" "0,1")
   (set_attr "mode" "DI")])

(define_insn "*cmpdi_minus_1_rex64"
  [(set (reg FLAGS_REG)
        (compare (minus:DI (match_operand:DI 0 "nonimmediate_operand" "rm,r")
                           (match_operand:DI 1 "x86_64_general_operand" "re,mr"))
                 (const_int 0)))]
  "TARGET_64BIT &amp;&amp; ix86_match_ccmode (insn, CCGOCmode)"
  "cmp{q}\t{%1, %0|%0, %1}"
  [(set_attr "type" "icmp")
   (set_attr "mode" "DI")])
    </code></pre></li>
  </ul>
</div>

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



<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">軽量継続を実装するには?</p>
  <ul>
    <li>micro-cは元より軽量継続を考慮して良く設計されている</li>
    <li>GCCでは<em class="weak">あくまで関数</em>がベース</li>
    <li>micro-Cと同じ命令列を出力させるのは難しい</li>
    <li>関数コール(call命令)ではもちろんダメ</li>
    <li>必ず<em>jmp命令</em>を出力しないといけない</li>
    <li>スタックを拡張するのもダメ</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: 軽量継続の実装</h1>
  <p class="subtitle">末尾呼出による軽量継続の実装</p>
  <ul>
    <li>全ての軽量継続は末尾呼出と解釈する</li>
    <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
    <li><code>goto cs(20, 30);</code></li>
    <li><code>cs(20, 30); return;</code></li>
  </ul>
  <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
  <ol>
    <li>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</li>
    <li>引数を順にスタックに格納すると、書き込み前のデータが上書きされてしまう場合</li>
  </ol>
</div>
<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">末尾呼出による軽量継続の実装</p>
  <ul>
    <li>全ての軽量継続は末尾呼出と解釈する</li>
    <li>変更箇所はGCCの<a href="#(10)">フロントエンド</a>での構文解析</li>
    <li><code>goto cs(20, 30);</code></li>
    <li><code>cs(20, 30); return;</code></li>
  </ul>
  <p class="subtitle">ある条件で末尾呼出が行われなくなる</p>
  <ol>
    <li><del>呼出先関数の全引数が占めるスタックサイズが、呼出元関数のそれより大きい場合</del> <em class="weak">解決済み</em></li>
    <li><em>引数を順にスタックに格納すると、書き込み前のデータが上が着されてしまう場合</em></li>
  </ol>
</div>


<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">引数順序の問題の解決</p>
  <ul>
    <li>問題となる例
<pre><code>code somesegment(int a, int b, int c) {
  /∗ do something ∗/
  goto nextsegment(b, c, a);
}
</code></pre>
    </li>
    <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>

</div>

<div class="slide">
  <h1>First: 軽量継続の実装</h1>
  <p class="subtitle">全ての引数を一時変数に退避</p>
  <ul>
    <li>次の様に構文木を変更する
<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>
    </li>
    <li>これにより、引数順序を考える必要はなくなる</li>
    <li>代わりに、メモリアクセスが大量に発生</li>
    <li>しかし、これはGCCの最適化で除去される</li>
  </ul>

  <p class="subtitle">これで軽量継続が実装された</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">実際の出力はどうなる?</p>
  <div style="width:70%;margin:1em auto 0;">
<pre><code>__code current(int a, int b, int c) {
    goto next(10, 20, 30);
}
</code></pre>
  </div>
</div>

<div class="slide" style="font-size:95%;">
  <h1>First: x86における高速化</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: 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>一時変数への確保があるのでこれは予想通り</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>
</div>

<div class="slide">
  <h1>First: 性能評価(速度比較)</h1>
  <p class="subtitle">結果(micro-cとの比較)</p>
  <ul>
    <li>x86では速度にあまり差が出なかった</li>
    <li>PowerPCではCbCGCCが2倍ほど早い</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>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>Second: Cとの相互利用</h1>
  <p class="subtitle">なぜそれが必要か</p>
  <ul>
    <li>C &lt;=&gt; CbC の変換が可能なので互換性はある</li>
    <li>しかし、ソースコード上での互換性もある事が望ましい</li>
    <li>CbCからCの関数を呼び出すのは問題ない</li>
    <li>CからCbCのコードセグメントに継続するとスタックが保持されない</li>
  </ul>
  <p class="subtitle"><dfn>環境付き継続</dfn>の導入</p>
  <ul>
    <li>軽量継続に、スタックの情報を加える</li>
    <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">
  <h1>Second: Cとの相互利用</h1>
  <p class="subtitle">どのように実装する?</p>
  <ol>
    <li>setjmp()/longjmp()を使って実装可能
      <ul>
	<li>Cの標準ライブラリの関数</li>
	<li>しかし余計な環境も保持するためオーバヘッドが大きい</li>
	<li>継続の際に渡す引数が一つ増えてしまう</li>
      </ul></li>
    <li>内部関数
      <ul>
	<li>GCCの独自拡張</li>
	<li>関数内に関数を定義可能</li>
	<li><em>内部関数から外の関数のラベルにgotoできる</em></li>
      </ul></li>
  </ol>
  <p class="subtitle">内部関数が使いやすい</p>
</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>Third: メンテナンス性の向上</h1>
  <p class="subtitle">GCCのアップデートリリースは早い</p>
  <ul>
    <li>リリースだけで年に5回のペース</li>
    <li>その度にバグの修正やコードの改善が入る</li>
    <li>問題は、高い確率で、GIMPLEやRTLの処理がドラスティックに変更されること</li>
  </ul>
  <p class="subtitle">このリリースに追従して差分をアップデートしたい</p>
  <ul>
    <li>GCC本家にマージしてもらうのが一番良いが難しい</li>
    <li></li>
  </ul>
</div>

<div class="slide">
  <h1>Third: メンテナンス性の向上</h1>
  <img style="width:60%;float:right;" src="figures/gcc-repository.png" />
  <p class="subtitle">二つのリポジトリ管理</p>
  <ul>
    <li>本家のリリースをそのままコミットするリポジトリ GCC_copy</li>
    <li>CbCの修正が加えられたリポジトリ CbCGCC</li>
    <li>Mercurialによる分散リポジトリ管理</li>
    <li>CbCGCC は GCC_copyをクローン(ブランチ)して作成する</li>
  </ul>
  <p class="subtitle"></p>
</div>


<div class="slide">
  <h1>Third: メンテナンス性の向上</h1>
  <p class="subtitle">アップデート手順</p>
  <ul>
    <li>GCC-copyリポジトリにて
      <ol>
        <li>GCC-copyリポジトリのファイルをすべて消す</li>
        <li>GCCの最新バージョンをリポジトリ内に展開</li>
        <li>追加ファイル、削除ファイルを確認</li>
        <li>コミット、タグ付け</li>
      </ol> </li>
    <li>CbCGCCリポジトリにて
      <ol>
        <li>GCC-copyからpull.</li>
        <li>hg mergeでマージ実行</li>
        <li>衝突があればソースコードをを修正</li>
        <li>ビルドテスト</li>
        <li>コミット、タグ付け</li>
      </ol></li>
  </ul>
</div>

<div class="slide">
  <h1>Third: メンテナンス性の向上・比較</h1>
  <p class="subtitle">これまでのアップデートは</p>
  <ul>
    <li>GCCの新旧の差分、CbCの差分</li>
    <li>複雑なdiffをとる必要がある</li>
  </ul>
  <p class="subtitle">新しい管理方法により</p>
  <ul>
    <li>「3.衝突があればソースコードを修正」以外は機械的に実行可能</li>
    <li>内部の設計が変わったなど、<em>重要な変更点にだけ集中</em>できる</li>
    <li>分散管理にしたことで、移行用バージョンを分けることが可能になる</li>
  </ul>
</div>

<div class="slide">
  <h1>まとめ</h1>
  <p class="subtitle">本研究での取り組み</p>
  <dl>
    <dt>First</dt>
    <dd>CbCGCCにて実用レベルのCbCプログラムが動作可能となった
      <ul>
        <li>軽量継続における引数順序の制限を取り除いた</li>
	<li>PowerPCでの間接継続の制限を取り除いた</li>
	<li>x86アーキテクチャにて高速化を行った</li>
      </ul>
    </dd>
    <dt>Second</dt>
    <dd>Cとの相互利用性の向上</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>
    <dt>成果4</dt>
    <dd>メンテナンス性が向上</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>Cとの比較について</h1>
  <p class="subtitle">CbCとCの比較に関して</p>
  <ul>
    <li>まだ例題を用意していない</li>
    <li>quicksortはスタックが必要となるため、Cに有利</li>
    <li>この例題ではプログラム上自前でスタックを用意している</li>
    <li>このメモリへのアクセスはスタックより重い</li>
    <li>Cとの比較には状態遷移ベースの例題があった方が良い</li>
  </ul>
</div>













</body>
</html>