Akihiro Memo

開発関連のメモ、雑記

Emscriptenの論文読んだ。Webの賢い選択。

大学院に入学するとともに、無職になりました。新しい仕事場を探しています!といってもインターン先ですが!という挨拶も程々に、Emscriptenの論文を読みましたので、その内容について少し。


JIT関連の論文を読んでいて、これは難しいと思い悩んできたところ、友達が卒研の参考文献であげていたプロジェクトがOOPSLAで発表した(正確にはSPLASH '11)よー、ということなので、じゃあこれしかないということで読み始めました。


サイトや論文は以下(正確には自分が読んだのはSPLASH '11版)
https://github.com/kripken/emscripten/wiki


Emscripten とは、LLVM-IR(LLVMにおけるプログラムの内部表現)をJavaScriptに変換するものです。前回の記事で投稿したものとは変換方向が逆になります。Emscriptenは、主に他の言語で書かれたコード資源をWebに移植使用という目的の元、制作が行われました。LLVM用のフロントエンドがある言語ならもちろん、それらの言語で書かれた処理系がある言語なら、Webで動作することがわかります。サンプルを見れば分かる通り、キャンバスを用いることで、ゲームを行ったり、PDFのレンダリング、レイトレースを行なっていたりもします。


論文には例があるので追ってみましょう。以下のC++のコードを変換していきます。

#include <stdio.h>
int main(){
    int sum = 0;
    for (int i = 1; i < 100; i++)
      sum += i;
    printf("1+...+100=%d\n", sum);
    return 0;
}


なんか、プログラムがちぐはぐだけど、あくまで変換する対象なので、どうでもいいとして、これをClangをもちいて、LLVM-IRに変換すると、以下のようなコードになります。たしか、$clang file.c -S -emit-llvm -o - とか打てばできます。clangが無いって? いやいや、何言ってるんですが、むしろ素のGCCなんてオワコンじゃないですか、せめてllvm-gcc使いましょうよ。ってことで、改めてLLVM-IRは以下のようになります。

@.str = private constant [4 x i8] c"%d\0A\00"

define i32 @main() {
  %1 = alloca i32, align 4
  %sum = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1
  store i32 0, i32* %sum, align 4
  store i32 1, i32* %i, align 4
  br label %2

; <label>:2
  %3 = load i32* %i, align 4
  %4 = icmp slt i32 %3, 100
  br i1 %4, label %5, label %12

; <label>:5
  %6 = load i32* %i, align 4
  %7 = load i32* %sum, align 4
  %8 = add nsw i32 %7, %6
  store i32 %8, i32* %sum, align 4
  br label %9

; <label>:9
  %10 = load i32* %i, align 4
  %11 = add nsw i32 %10, 1
  store i32 %11, i32* %i, align 4
  br label %2

; <label>:12
  %13 = load i32* %sum, align 4
  %14 = call i32 (i8*, ...)*
        @printf(i8* getelementptr inbounds
        ([14 x i8]* @.str, i32 0, i32 0), i32 %13)
  ret i32 0
}


なんて分かりやすい! というか、言語としての抽象度はCに毛が生えた程度で、非常に理解しやすいと思うのですがどうでしょう? LLVM論文ではMIPSライク! とか言ってましたが、アセンブラーから見ればなにいってんだ糞が! と言われても可笑しくありません。簡単に解説すると、Label2より前がfor文の初期化まで。Label2がfor文の分岐、Label5がsum+=i;、Label9がi++;をしている部分であり、Label12が最後の印字を行う部分です。そこまで分かると読みやすいとおもいます。必要な値をload命令でレジスタにロードして、それらを計算し、store命令でメモリに書き戻す。基本的に計算はこのパターンです。そして、さらにそれをEmscriptenでJavaScript(最適化無し)変換すると、以下のようになります。

function _main() {
  var __stackBase__  = STACKTOP;
  STACKTOP += 12;
  var __label__ = -1;
  while(1) switch(__label__) {
    case -1:
      var $1 = __stackBase__;
      var $sum = __stackBase__+4;
      var $i = __stackBase__+8;
      HEAP[$1] = 0;
      HEAP[$sum] = 0;
      HEAP[$i] = 0;
      __label__ = 0; break;

    case 0:
      var $3 = HEAP[$i];
      var $4 = $3 < 100;
      if ($4) { __label__ = 1; break; }
      else    { __label__ = 2; break; }

    case 1:
      var $6 = HEAP[$i];
    var $7 = HEAP[$sum];
      var $8 = $7 + $6;
      HEAP[$sum] = $8;
      __label__ = 3; break;

    case 3:
      var $10 = HEAP[$i];
      var $11 = $10 + 1;
      HEAP[$i] = $11;
      __label__ = 0; break;

    case 2:
      var $13 = HEAP[$sum];
      var $14 = _printf(__str, $13);
      STACKTOP = __stackBase__;
      return 0;
} }


このように、単純にメモリをHEAPという配列に仮想的に作成し、その配列内にデータを格納しています。また、制御においては、__label__変数と、while,switch構文により、LLVM-IRで見られたような構造が垣間見えます。このように、馬鹿丁寧に変換をまず行います。この後、HEAPを用いないように変数を書き換えたり、 Emscripten独自のRelooperアルゴリズムで以下のようなJavaScriptプログラムまで最適化します。

function _main() {
  var __label__;
  var $1;
  var $sum;
  var $i;
  $1 = 0;
  $sum = 0;
  $i = 0;
  $2$2: while(1) {
    var $3 = $i;
    var $4 = $3 < 100;
    if (!($4)) { __label__ = 2; break $2$2; }
    var $6 = $i;
    var $7 = $sum;
    var $8 = $7 + $6;
    $sum = $8;
    var $10 = $i;
    var $11 = $10 + 1;
    $i = $11;
    __label__ = 0; continue $2$2;
  }
  var $13 = $sum;
  var $14 = _printf(__str, $13);
  return 0;
}


色々冗長ですが、らしいプログラムまで変化しました。更にこのコードに既存のJavaScript最適化ツールである、Closure Compiler をかけてやると、不要な変数やコードの削除や、関数インライニング等、様々な基本的な最適化を施してくれます。結果、以下のようなJavaScriptにも変わります。

function K() {
  var a, b;
  b = a = 0;
  a:for(;;) {
    if(!(b < 100)) {
      break a
    }
  a += b; b += 1;
  }
  _printf(J, a);
  return 0;
}


ここまで変化すれば、元のプログラムと遜色ないといっても過言ではないでしょう。すごいEmscripten、これはいい!!


以上で変換の過程は終わりですが、余談として、1つ気になった点として、この関数は必ず同じ結果を返す関数であり、LLVMの最適化機構を用いて最適化すると、以下のようなコードになります。

@.str = private unnamed_addr constant 
[14 x i8] c"1+...+100=%d\0A\00", align 1

define i32 @main() nounwind uwtable {
  %1 = tail call i32 (i8*, ...)* @printf(i8* getelementptr 
    inbounds ([14 x i8]* @.str, i64 0, i64 0), i32 4950)
  ret i32 0
}


要するに何が言いたいかというと、アンローリングと定数伝搬を行えば、結果の定数値が求まり、そもそも計算する必要が無いということです。まあ、当たり前の結果なのですが、while,forの無限ループはアンローリングできませんし、Emscriptenのループの復元方法が若干あれな気がしてならないです。以上です! 公式サイトには WebGL等を用いた様々なデモがあります。Web系の人はぜひこのEmscriptenを使った、未来のWebを作ってみてください!!


以下使用例

物理エンジンを移植した例(With OpenGL
http://www.syntensity.com/static/box2d.html

様々な言語処理系を移植しWebで実行
(Ruby, Python, Lua...)
http://repl.it/#:languages