JavaScript はどのように実行されるか

Safari *1 の実装を例に JavaScript はどのようにして実行されているかを書く。自分用のメモ。日本語の出来は気にしない

1. ブラウザを起動して以下のようなページを開いたとする

<html>
  <head>
    <script>
var a = 1;
var b = 2;
alert(a + b);
    </script>
  </head>
  <body>
  </body>
</html>

2. インターネットからデータが到着する

そうすると WebCore::FrameLoader::write という関数に生の文字列が渡される。型は char* だ。
http://trac.webkit.org/browser/trunk/WebCore/loader/FrameLoader.cpp#L990
この関数の中では、到着した文字の文字コードを解決し WebCore::Tokenizer に文字コード解決済みの HTML を渡す。
重要なところだけ抜粋すると

void FrameLoader::write(const char* str, int len, bool flush)
{
    // 文字コード解決
    String decoded = m_decoder->decode(str, len);

    // Tokenizer に渡す
    Tokenizer* tokenizer = m_frame->document()->tokenizer();
    tokenizer->write(decoded, true);
}

3. HTML が解析される

WebCore::Tokenizer は抽象クラスで実際には、 WebCore::HTMLTokenizer の write が呼ばれる。
このクラスと HTMLParser が連携して HTML は解析され、 DOM のノードが生成される。
この途中に script 要素の開始タグが現れると。。。

4. HTML の世界から JavaScript の世界への入り口へとどんどん進んでいく

script 要素が開始されると、 WebCore::HTMLTokenizer::scriptHandler が呼び出される。

HTMLTokenizer::State HTMLTokenizer::scriptHandler(State state)
{
    // We are inside a <script>

そこで script を実行すべきか判定し WebCore::HTMLTokenizer::scriptExecution が呼び出される

HTMLTokenizer::State HTMLTokenizer::scriptExecution(const String& str, State state, const String& scriptURL, int baseLine)
{

str には JavaScript のソースが入っている
次に WebCore::FrameLoader::executeScript → WebCore::ScriptController::evaluate と呼び出されていく。引数はそのまま。
WebCore::ScriptController::evaluate では以下の事を行う。

VM の起動
JavaScript の実行

5. VM の起動

WebCore::ScriptController::evaluate からは初回起動時だけ WebCore::FrameLoader::initScript という関数が呼ばれる。
その関数の中から、 JSC::Machine が new される。

6. JavaScript の実行

WebCore::ScriptController::evaluate から JSC::Interpreter::evaluate が呼び出され、 JavaScript は実行されます
JavaScript の実行は以下のフェーズで行われる。

JavaScript を解析して構文木（構文をデータにしたもの）を生成する
構文木をバイトコードにする
バイトコードをマシン語に変換できる場合は変換する
バイトコード、または、マシン語を実行する

順番に見て行きましょう

7. JavaScript を解析して構文木を生成する

JSC::Interpreter::evaluate の以下の行

RefPtr<ProgramNode> programNode = exec->globalData().parser->parse<ProgramNode>(exec, exec->dynamicGlobalObject()->debugger(), source, &errLine, &errMsg);

この programNode が構文木というものです。
parse 関数の中では bison というツールによって生成された kjsyyparse を実行している。
bison は kjs/grammer.y ファイルを読んで、そのパーサを自動で生成する。
この構文木の構造は

var a = 1;
var b = 2;

alert(a + b);

の場合、以下のようになる

- ProgramNode
  - VarStatementNode => "var"
    - AssignResolveNode => "a ="
      - NumberNode => "1"
  - VarStatementNode => "var"
    - AssignResolveNode => "b ="
      - NumberNode => "2"
  - ExprStatementNode
    - FunctionCallResolveNode => "alert"
      - ArgumentsNode => "(" ")"
        - ArgumentListNode
          - AddNode => "+"
            - ResolveNode => "a"
            - ResolveNode => "b"

この構造の節々にあるそれぞれのオブジェクトをノードという。ノードには親子関係があり、親ノード、子ノードという言葉も使う。
構文木の概要は以下のファイルにまとめて書いてある。
http://trac.webkit.org/browser/trunk/JavaScriptCore/kjs/nodes.h
http://trac.webkit.org/browser/trunk/JavaScriptCore/kjs/nodes.cpp

8. 構文木をバイトコードにする

ここでは、構文木をバイトコードに変換する
構文木のクラスは emitCode という関数を持っている。
この関数は

再帰的に自分の子ノードの emitCode を呼び出し、子ノードをバイトコード化し、それぞれの子ノードの評価結果が入るレジスタ番号を知る
自分自身をバイトコード化し、自分自身の評価結果を保存するレジスタを知り、その値を返す

ということをする。
このとき、レジスタ番号が被らないように調整や、ノードがどんなバイトコードを生成すればいいかを管理しているのが JSC::CodeGenerator である。
以下の構文木に対して emitCode を呼び出すと

- ProgramNode
  - VarStatementNode => "var"
    - AssignResolveNode => "a ="
      - NumberNode => "1"
  - VarStatementNode => "var"
    - AssignResolveNode => "b ="
      - NumberNode => "2"
  - ExprStatementNode
    - FunctionCallResolveNode => "alert"
      - ArgumentsNode => "(" ")"
        - ArgumentListNode
          - AddNode => "+"
            - ResolveNode => "a"
            - ResolveNode => "b"

以下のようなバイトコードが生成される

enter

// ここから ProgramNode

// $0 には undefined が入っている
// $1 には 1 が入っている
// $2 には 2 が入っている

mov $-16 $0
mov $-17 $0
mov $3 $0

// $3 は this
// $-16 は a
// $-17 は b

// ここから VarStatementNode
// ここから AssignResolveNode
// ここから NumberNode

mov $-16 $1
// a = 1

// ここまで NumberNode
// ここまで AssignResolveNode
// ここまで VarStatementNode
// ここから VarStatementNode
// ここから AssignResolveNode
// ここから NumberNode

mov $-17 $2
// b = 2

// ここまで NumberNode
// ここまで AssignResolveNode
// ここまで VarStatementNode
// ここから ExprStatementNode
// ここから FunctionCallResolveNode

resolve_func $3 $4 #alert
// $4 に alert 関数が入る
// $3 に呼び出したときの this の値が入る

// ここから AargumentListNode
// ここから AddNode

add $6 $-16 $-17 [toInt]

// ここまで AddNode
// ここまで AargumentListNode

profile_will_call $4
call $3 $4 $3 $5 2 15
profile_did_call $4

// 2 というのは引数が二個あるという意味で
// 2 個目の引数が $6 （足し算の結果）になっている
// $3 に関数呼び出しの結果が入る

// ここまで FunctionCallResolveNode
// ここまで ExprStatementNode
// ここまで ProgramNode

end $3
// JavaScript 実行の結果は $3 に格納されている

バイトコードは、実際には配列のような形で持たれている。

9. バイトコードをマシン語に変換できる場合は変換する

バイトコード化された JavaScript のコードは、 JSC::Machine::execute の以下の箇所で実行される。

#if ENABLE(CTI)
    if (!codeBlock->ctiCode)
        CTI::compile(this, newCallFrame, codeBlock);
    JSValue* result = CTI::execute(codeBlock->ctiCode, &m_registerFile, newCallFrame, scopeChain->globalData, exception);
#else
    JSValue* result = privateExecute(Normal, &m_registerFile, newCallFrame, exception);
#endif

ここで分かるのは、コンパイル時に CTI というフラグを立てておけば、マシン語に変換されてから実行されるということだ。
というわけで、この先は２つに道が別れる

バイトコードとして実行される
マシン語に変換されて実行される

10. バイトコードとして実行される場合

JSC::Machine::privateExecute の中では以下のようなことが行われる

バイトコードを一つ取り出して、 goto 文（goto 文で任意の場所に飛べないコンパイラでは switch を使う）でそのバイトコードの処理が書かれているところに飛ぶ
その処理を実行する
淡々と上の２つを繰り返す。

JSC::Machine::privateExecute のコードは非常に分かり易い

11. マシン語に変換される場合

初回に CTI::compile が呼び出され、マシン語に変換される。（そのコードが一度マシン語されている場合は、呼び出されない）
CTI::compile は CTI::privateCompile を呼び出す。この関数では以下のようなっことを行う。

バイトコードを一つ取り出す
そのバイトコードを X86::X86Assembler オブジェクトを使ってマシン語に変換
X86::X86Assembler オブジェクトが持っているバッファにためる
淡々と上の3つを繰り返す。

そして、最終的にバッファにたまったマシン語を callFrame->ctiCode に入れておく
最後にそのマシン語を呼び出す場合は以下のようになっている
まず、 CTI::execute はこんな感じ

        inline static JSValue* execute(void* code, RegisterFile* registerFile, CallFrame* callFrame, JSGlobalData* globalData, JSValue** exception)
        {   
            return ctiTrampoline(code, registerFile, callFrame, exception, Profiler::enabledProfilerReference(), globalData);
        }

ctiTrampoline は C 言語の名前でリンケージされていて

    extern "C" {
        JSValue* ctiTrampoline(void* code, RegisterFile*, CallFrame*, JSValue** exception, Profiler**, JSGlobalData*);
        void ctiVMThrowTrampoline();
    };

以下のように code を呼び出している（gcc の場合）

asm(
".globl " SYMBOL_STRING(ctiTrampoline) "\n" 
SYMBOL_STRING(ctiTrampoline) ":" "\n" 
    "pushl %esi" "\n" 
    "pushl %edi" "\n" 
    "pushl %ebx" "\n" 
    "subl $0x20, %esp" "\n" 
    "movl $512, %esi" "\n" 
    "movl 0x38(%esp), %edi" "\n" // Ox38 = 0x0E * 4, 0x0E = CTI_ARGS_callFrame (see assertion above)
    "call *0x30(%esp)" "\n" // Ox30 = 0x0C * 4, 0x0C = CTI_ARGS_code (see assertion above)
    "addl $0x20, %esp" "\n" 
    "popl %ebx" "\n" 
    "popl %edi" "\n" 
    "popl %esi" "\n" 
    "ret" "\n" 
);

スタック %esp から code を取り出して call しているのだ

最後に

なんだか凄い時代に生きている気がしてきた

*1:WebKit

IT戦記

プログラミング、起業などについて書いているプログラマーのブログです😚

JavaScript はどのように実行されるか

JavaScript はどのように実行されるか

1. ブラウザを起動して以下のようなページを開いたとする

2. インターネットからデータが到着する

3. HTML が解析される

4. HTML の世界から JavaScript の世界への入り口へとどんどん進んでいく

5. VM の起動

6. JavaScript の実行

7. JavaScript を解析して構文木を生成する

8. 構文木をバイトコードにする

9. バイトコードをマシン語に変換できる場合は変換する

10. バイトコードとして実行される場合

11. マシン語に変換される場合

最後に