Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

Polymorphic Inline Cache implementation of iv / lv5

ECMAScript C++ JIT VM lv5

This is a blog post for 12/22 VM advent calendar.

See http://qiita.com/advent-calendar/2012/vm for more nice blog posts :)

この記事は更新中です... 完成しました

Introduction

ECMA262 engine, iv / lv5 には, Polymorphic Inline Cache(以下PIC)が実装されています. ということで, ここではPIC, 特にLoadPropertyICの実装について記述したいと思います. PICのsystem本体についてはかなり多くの場所で記述されていると思うので, ここでは, かなり実践的な方向で記述したいと思います. そのため, 多くの前提知識を要求していますのでご容赦ください.

LoadOwnPropertyIC & PIC overview

iv / lv5におけるICの実装を紹介します. lv5/breaker/compiler.h

      asm_->mov(rdi, r14);
      LoadPropertyIC* ic(new LoadPropertyIC(native_code(), name));
      native_code()->BindIC(ic);
      asm_->mov(rdx, core::BitCast<uint64_t>(ic));
      const std::size_t offset = PolyIC::Generate64Mov(asm_);
      ic->BindOriginal(offset);
      asm_->call(rax);

raxに設定されているのは, 通常のLOAD_PROP関数です. このため, 一番最初の場合, LOAD_PROP関数が呼ばれます. そしてそこでは, 通常通りhashtableを引いてlookupします, 問題はここからです.

lv5/breaker/stub.h

  // cache phase
  // own property / proto property / chain lookup property
  if (slot.base() == obj) {
    // own property
    ic->LoadOwnProperty(ctx, obj->map(), slot.offset());
    return Extract(res);
  }

cacheableでown propertyであることが発覚すると, offsetを使って, ICを構築し始めます. lv5/breaker/poly_ic.h

    as.inLocalLabel();
    gen(this, &as, ".EXIT");  // ここでmain codeが作成される
    // fail path
    as.L(".EXIT");  // TestMapContentsなどで失敗するとここへjmpする
    // ここでIC末尾のjmpを生成, fallback pathへjmp
    const std::size_t pos = GenerateTail(&as);
    ic->set_tail(const_cast<uint8_t*>(as.getCode()) + pos);
    as.outLocalLabel();
      // main code

      // map一致を検査
      IC::TestMapConstant(as, map_, r8, r10, fail);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r8, offset_);
    // GenerateFastLoad
    const std::ptrdiff_t data_offset =
        JSObject::SlotsOffset() +
        JSObject::Slots::DataOffset();

    // dataのpointerを取得し
    as->mov(rax, qword[reg + data_offset]);

    // offset access. 結果はraxに入れる
    // これはx64 calling convension参照
    as->mov(rax, qword[rax + kJSValSize * offset]);

    // retはICがpassした時に行われる
    as->ret();

r8にobjectが入っているので, cache対象のmapと一致するかどうかをtestします. そして一致した場合にGenerateFastLoadでoffset accessを行います. ここでretが最後に入っているところに注目です.

そして, ICの末尾をLOAD_PROP関数へのjmpにして, また, 一番初めのcallのraxをICのcallに書き換えます

  void ChainingObjectLoad(Unit* ic, uintptr_t code) {
    // このICが呼ばれるようにする
    if (empty()) {  // ICが初めて生成された時
      // rewrite original
      // LOAD_PROP呼び出しのcallを書き換え
      native_code()->assembler()->rewrite(from_original_, code, k64Size);
    } else {
      if (!object_chain()) {
        // rewrite object guard
        Rewrite(from_object_guard_, code, k64Size);
      } else {
        // 一つ前のICの最後のjmpを自分に書き換え
        object_chain()->Redirect(code);
      }
    }

    // このICの最後のjmpを設定する
    if ((size() + 1) == kMaxPolyICSize) {
      // last one
      // kMaxPolyICSizeより多くのICがぶら下がっている時
      // ICを生成しないLOAD_PROPにjmpするようにする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP_GENERIC));
    } else {
      // それ以外の場合は, LOAD_PROPへjmpする
      ic->Redirect(core::BitCast<uintptr_t>(&stub::LOAD_PROP));
    }
  }

iv / lv5のICにおいては, 次々とtestをしながら条件が合うかどうかをcheckしていきます, そして, passすると, propertyをloadしてretするのです. これによって, ICが成功次第, もとのprogramのpathに戻ることができます.

ICが徐々に構築されていくさまを図で表します. 初回. 通常のLOAD_PROP stub function callになっています.

first

ICが構築されると, 最初のcallの対象がICになり, ICのtestで失敗するとLOAD_PROPへfallbackします.

second

また, LOAD_PROPは, 新たにICを構築し, 前に構築したICの最後のjmpを書き換え, 自分をchainにつなぎます. これによって, 一つのcallsiteで幾つものmapをhandleすることができます, これこそ, Polymorphicであるということです.

third

LoadProto/ChainPropertyIC & Map transition system

LoadOwnPropertyICにおいては, objectのmapが期待値かどうかをtestします, このtestにpassすれば, 対象のobjectのshapeはcacheをとった時のobjectのshapeと同じということであり, offset lookupによってpropertyを引っ張りだすことができます. では, prototypeにある場合, あるいはもっと上にある場合はどうでしょうか?

もっと上にあった場合, ICはその道中たどったobjectのshape全てが期待値を維持していることをtestしなければいけません. それは, 途中のobjectのshapeが変わることで, lookup先が変わる場合があるからです. ECMAScriptで例を示します.

function getToString(instance) {
  return instance.toString;
}
function Test() { }
var instance = new Test;
getToString(instance);    // lookup Object.prototype.toString
Test.prototype.toString = function() { };
getToString(instance);    // lookup Test.prototype.toString

一度目のtoString lookupでは,

  1. instance object
  2. Test.prototype
  3. Object.prototype

とたどってlookupしました. その後Test.prototype.toStringへの代入によってTest.prototypeのshapeが変わった事によって, Object.prototypeに至らずにlookupが終了するようになっています. ここでTest.prototypeのmap testをしなければ, この変更を検知できません.

では, 実際にLoadChainPropertyICのcodeを紹介します.

lv5/breaker/poly_ic.h

    void operator()(LoadPropertyIC* site, Xbyak::CodeGenerator* as, const char* fail) const {
      JSObject* prototype = NULL;
      as->mov(r11, r8);  // r11に対象のobject
      for (Chain::const_iterator it = chain_->begin(),
           last = chain_->end(); it != last; ++it) {
        // mapの数だけtestを出力
        Map* map = *it;
        IC::TestMapConstant(as, map, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
        prototype = map->prototype();
        as->mov(r11, core::BitCast<uintptr_t>(prototype));
      }
      // last check
      IC::TestMapConstant(as, map_, r11, r10, fail, Xbyak::CodeGenerator::T_NEAR);
      // load
      LoadPropertyIC::GenerateFastLoad(as, r11, offset_);
    }

objectがlookupされた時, own objectからtarget objectに至るまでのmapをchainとして取得し, それに合わせてtestを出力しています. chainにはmapが詰まっており, このguardのcheckしているのは道中のobjectが全てあるときのmapと同じmapを持っているか?を確認しているのです.

注意して欲しいのは, 一番初めは, 実行時に与えられるobject, r11のmapを検査していますが, その後r11のprototypeを取るのではなく, chainからprototypeを取得しています. つまり, 実はこのguardではprototypeの探索をやっておらず, IC作成時に取得されたchainに属するobjectのmapが変わっていないかを確認しているだけなのです

chain

なぜr11のprototypeを動的にたどる必要がないのでしょうか?

それは, Mapの中にprototypeが含まれているからです. iv / lv5ではobjectのprototypeが変更されるとMap transitionが起こるようになっており, MapのIDの表す同じShapeの中には同じPrototypeであるという保証も含まれているからです. これによってmapが一致することを検査すると, 一つ上のprototype objectも変わっていないことも同時に検査できるのです.

Storing ALL information into Map ID

ICにおいてはMapのtestが重要となります. このため, Mapが何の一意性を表しているのかが非常に重要になります. 例えば, prototypeをMapに持たせてprototypeの変更によってMap transitionを起こすことにより, MapのIDのtestはprototypeが変わっていないことを保証することができるのです.

このため, 一般にECMAScript engineでは, Objectを以下のように設計します.

map

Mapがhashtableを持っており, hashtableにはkeyに対してattributesとoffsetが格納されています. そしてoffsetがObjectのslotを表しているというふうな実装です. 注目して欲しいのは, hashtableのvalueがoffsetだけではなく, attributesも含んでいるところです. slotの方には, property descriptorでいうところのvalueしか存在しません. なぜslotの方でattributesとvalueを持たないのでしょうか?

それはこのようにすることで, attributesをMapの管理下に置くことができるからです. そしてiv / lv5ではこのattributesが変わるだけでもMap transitionが起きます. writable:truewritable:falseにするとMap transitionが起こるのです. その結果, MapのIDはattributesが変わっていないことをも保証することができるのです

例えば, propertyをstoreするとします.

var obj = {};
for (var i = 0; i < 100; ++i) {
  obj.test = i;
}

この時, StorePropertyICを構築するとして, StoreOwnPropertyICが構築された時, ICは何をcheckすれば良いのでしょうか?

答えはなんと, Map checkをするだけで良いのです. もしもMapにattributesの情報が入っていなければ, lv5はstoreするたびにwritableがtrueであるかどうかを検査する必要があります. しかし, attributesの情報がMapに入っており, ICが構築されたとすれば, そのIC構築対象のMapのslotは当然writableであり, このMap checkをするだけで, writableなattributesかどうかのtestをも行なっていることになるのです.

Conclusion

iv / lv5におけるLoadPropertyPICの具体的なcodeを用いて, Map transitionの設計, PICの設計について説明しました.

ホワイトクリスマスイブになるそうですが, あずにゃんと一緒に楽しく過ごす予定です. iv / lv5はまだまだ高速化を予定しております, Context Threading JITが終了すると, 自作GC, SSA based optimizing JIT compilerへと進もうと考えております. また, ES6本格対応も検討しており, Meta Object Protocol(MOP, ECMAScripterにとって今熱い言葉の一つ)によるrewrite, cleanupも考えております. 来年度もiv / lv5にご期待ください><