yutopp's blog

サンドバッグになりたい

Boost.Spirit.X3のご紹介 - C++ Advent Calendar 2014(16日目)

この記事はC++ Advent Calendar 2014 16日目の記事です.
おはようございます,@yutoppです.

去年のC++ Advent Calendar 2013ではBoost.Spirit.QiのTipsを書きました.今年は,Boost.Spirit.X3の紹介をしたいと思います!

環境は,Antergos Linux(x64) / Clang 3.5.0 / Boost 1.56.0 です.
また,Boost.Spirit.X3はexperimentalとのことなので,この記事の内容はすぐに古くなる可能性があります.

Boost.Spirit.X3とは?

Spirit X3
boostorg/sprit

C++11やC++14の機能を用いて再設計されたBoost.Spirit.Qiの次のexperimentalな実装です.
Classic Spiritのようなシンプルさを取り戻すことを目標にしているとのことです.

spirit/include/boost/spirit/home/x3がお目当てのX3の内容になります.

X3を使ったコードには以下のものがありました.

X3の利点

コンパイルが速い

試しにサンプルをビルドして計測してみました.
Qi Calc1 / Qi Calc2 / Qi Calc4
X3 Calc1 / X3 Calc2 / X3 Calc4

以下の表は,
clang++ -ftime-report -std=c++14 -I /usr/include/boost/ -c 各サンプル名
を10回繰り返し計測したClang front-end timerUser Timeの値(sec)の平均です.

calc1 calc2 calc4
Qi 4.283 4.409 4.96335
X3 1.87333 1.89767 2.34934

大体今までの2倍の速さでコンパイル出来るようになっているようです.体感でわかる程度に速いので良いですね.

エラーがわかりやすい(Qi比)

内部実装がシンプルになったことによって,エラーも分かりやすくなった気がします.

宣言と定義を同時に書けるようになる(?)

X3からruleの内容を先に定義してから,rule自体を定義するようなスタイルになったので,謎マクロを噛ますことで同時に宣言できます(後述します).

C++14を使いまくれる

ライブラリ自体が最低でもC++14を要求するので,このライブラリをincludeした時点でC++14の機能を使わないともったいないという気持ちになれます.

X3の現状の問題点

undocumented

ドキュメントが無いのでつらいです…が,X3の実装がとても読みやすいので,コードを読みながら何とか使えます.
特に変わったのはruleの定義とセマンティックアクションの記述,attrvalの扱いかな,と思います.

定義済みパーサが少ない

仕方がないので自分で書きます.

Tips

X3では,以下のようにruleを定義します.(サンプルより抜粋)

x3::rule<class expression, ast::program> const expression("expression");

auto const expression_def =
            term
            >> *(   ('+' >> term)
                |   ('-' >> term)
                )
            ;

BOOST_SPIRIT_DEFINE(
    expression = expression_def
    );

しかし,個人的にはruleとdefを同時に書きたいわけです. そこで,マクロを噛まします.
実際のコード

#define RULES_BEGIN( struct_name, entrypoint_name )         \
    struct struct_name                                      \
    {                                                       \
    using self_type = struct_name;                          \
                                                            \
    static auto instance()                                  \
        -> struct_name const&                               \
    {                                                       \
        static struct_name self;                            \
        return self;                                        \
    }                                                       \
                                                            \
    static auto entrypoint()                                \
    {                                                       \
        return instance().entrypoint_name;                  \
    }                                                       \

#define RULES_END                          \
    };

#define ANNOTATOR_COL() :

#define ANNOTAROR_BASE_SPEC( r, _unused, index, elem )      \
    BOOST_PP_IIF( BOOST_PP_EQUAL(index, 0),                 \
                  ANNOTATOR_COL,                            \
                  BOOST_PP_COMMA                            \
        )() public elem

#define RULE( name, type, ... )                    \
    RULE_WITH_ANNOTATOR( name, type, BOOST_PP_SEQ_NIL, __VA_ARGS__ )

#define RULE_WITH_ANNOTATOR( name, type, bases, ... )                   \
    class name                                                          \
        BOOST_PP_SEQ_FOR_EACH_I( ANNOTAROR_BASE_SPEC, _, bases )        \
    {};                                                                 \
    struct PP_ ## name {                                                \
        using rule_type = x3::rule<name, type>;                         \
        static auto def( self_type const& t ) {                         \
            return __VA_ARGS__;                                         \
        }                                                               \
        auto operator()() const -> rule_type                            \
        {                                                               \
            return rule_type( #name );                                  \
        }                                                               \
    };                                                                  \
    decltype(( std::declval<PP_ ## name>()) ()) name                    \
        = PP_ ## name()();                                              \
    template <typename Iterator, typename Context, typename Attribute>  \
    friend inline bool parse_rule(                                      \
        decltype(( std::declval<PP_ ## name>()) ()) rule_,              \
        Iterator& first, Iterator const& last,                          \
        Context const& context, Attribute& attr                         \
        )                                                               \
    {                                                                   \
        using boost::spirit::x3::unused;                                \
        auto const& ri = self_type::instance();                         \
        auto const& raw_def = PP_ ## name :: def( ri );                 \
        auto const& def_ = ( ri.name = raw_def );                       \
        return def_.parse(first, last, context, unused, attr);          \
    }

classの中であれば前方参照できるので,ruleは全体的にclassの中で定義するようにします.
ruleの中身はstruct PP_ ## namedefで定義します.引数のtがキモで,ruleを定義する際は,tのメンバ変数として参照するようにします.
また,parse_ruleが呼べればX3から使えるようなので,BOOST_SPIRIT_DEFINEの定義から抜き出してfriendとして定義しておきます.

実際の使い方はこのような感じになります.
実際のコード

RULES_BEGIN( rules, program )

RULE_WITH_ANNOTATOR( program, ast::module_ptr,
    ( on_error_annotator_base ),
    t.module > ( x3::eol | x3::eoi )
    )

RULES_END

RULES_BEGINでは,rulesというクラスを定義して,programから始まるrule群を定義しています.
RULE_WITH_ANNOTATORでは,on_error_annotator_baseに従ってアノテーションを行い,ast::module_ptr型の属性を持つ,programというruleを定義しています.
t.moduleというrule(ここでは定義していませんが…)を参照しています.残りはQiのときと同じですね.

あとはこのように使うだけです.

このマクロを用いると,ruleの定義を1箇所で行えるようになります.X3自体の効果でコンパイル時間も短くなりますし,良さがありますね.

実際に使ってみた

去年の記事にも書いた文鳥言語で,実際にX3を使ってみました.
(文鳥言語はC++14とBoost.Spirit.X3,LLVMを用いて,C++とDlangライクな言語を目指して開発している言語です)

yutopp/rill

Boost.Spirit.X3を使ってみて大きいのは,コンパイル時間が短くなったこと,それとコンパイル時間が短くなったこと,後はコンパイル時間が短くなったことが挙げられます.
エラーメッセージが分かりやすくなったこと,マクロで定義を1箇所に書けるようになったのも大きいかもしれません.
C++14のgeneric lambdaと組み合わせると,セマンティックアクションがとても書きやすいのも魅力でした.

Spirit.Qiでコンパイル時間がBoostするのがつらい皆様,ぜひX3を使ってみませんか.
そしてついでに文鳥言語も開発しませんか?とてもアットホームな鳥小屋です.

おわり

experimentalだけど現段階でも十分魅力的なBoost.Spirit.X3の紹介でした.
後日もう少し書き足します…

イヌヌ
@Linda_ppさんの今年気になった C++ ライブラリとかフレームワークを紹介する記事

!2!文鳥言語にプルリクください!2! - Aizu Advent Calendar 2014(3日目)

おはようございます.Aizu Advent Calendar 2014,3日目の@yutoppです.
25日分埋まりましたありがとうございます!!!!

さて今日も,Rill(a.k.a. 文鳥言語)についてポエムを書きます.
この記事の要約をすると,"pullreqください" になります.

Rill

文鳥言語にプルリクください - Aizu Advent Calendar 2014(1日目)

今日は?

Rillの構文が変わり,一昨日書いたサンプルコードが早速動かなくなりました.ユーザが自分しか居ないので,言語機能の破壊的変更もなんのそのです.
テンプレートの構文が変わり,より短く記述できるようになりました.

ちなみに,「D言語パクった?」「劣化C++」「劣化D言語」「劣化Embedded C++」などというコメントは大歓迎です.

サンプルの一部

一昨日のやつ

template(T: type)
def advent(_: u, c: T) {
    p("Advent");
    return \() => p(c);
}

今日のやつ

def advent!(T)(_: u, c: T) {
    p("Advent");
    return \() => p(c);
}

その他のサンプルはここにあります!

おわり

このように,Rillの構文や意味付けは数日単位で思いきり変わります.
Rillに関する何かがあれば,喜んで取り入れるのでissueやpullreqメッチャください.一緒に文鳥言語を作りませんか?とてもアットホームな鳥小屋です.

次は〜

(◔⊖◔)つ @i__yahoo

前は〜

@youxkei ⊂(◔⊖◔)

文鳥言語にプルリクください - Aizu Advent Calendar 2014(1日目)

おはようございます.Aizu Advent Calendar 2014一日目の@yutoppです.
現段階で9人枠が余ってるので各位頼む頼む頼む!!!!

さて今年は,Rill(a.k.a. 文鳥言語)についてポエムを書きます.
この記事の要約をすると,"pullreqください" になります.

Rill

Rillは趣味で作っているプログラミング言語です.

yutopp/rill

自分はC++をよく使うのですけど,構文に対して「こう書けたら良いのになあ」と思うことが多く,その感情を解決してみたかったということと,型理論LLVMの勉強したさで実装を始めたのがこの処理系です.ア,C++は大好きですよ.
意味が直感的で落とし穴が少なく,ライブラリが作りやすい言語が目標です.[要出典]
C++Ruby,Go,D,Scalaを主に参考にしています.
静的型付けです.また,この処理系が仕様です.

あれこれ

  • 仮引数は,デフォルトでconst参照.
  • 値と参照の扱いはC++に似ている.コピーとムーブがある.参照自体の値が欲しければポインタを使う.
  • 型に生存期間の情報を付けて,リソースを適切に扱えるようにする.
  • GCやスレッドサポートも入れたいところ.もちろんオプションで切り離し出来るようにする.
  • コンパイル時処理はD以上に充実させたい.ライブラリを作りやすくするにはメタプログラミングの手厚いサポートが必要だという考えから. 現状の処理系でも,意味解析中にLLVM IRを生成し,IRをJITコンパイルして呼び出すような実装になっているので,Rillの言語機能の全体に近いサブセットをコンパイル時にも実行できるようになっているはず.既にintなどの型情報はコンパイル時はtype型の値として扱われていて,例えば,const(int)はただの関数呼び出しであり,コンパイル時にコンパイラ内部のconstという関数intの型を表す整数値を渡して呼び出すLLVM IRを生成してJITコンパイル,実行され,const属性が付加されたint型を表す整数値を生成する.今のところ上手くいっているけれど,コードが大きくなると重たそうでア!
  • それでいてC++並の自由さが欲しい.
  • "C++の設計と進化"は最高.

つまり?

つまりRillは,文鳥が,小さいライブラリとランタイムを組み合わせて自由に楽しくコードを書けるプログラミング言語(になる|という)わけです.

ちなみに,「Rustと被ってない?」「劣化C++」「劣化D言語」「劣化Embedded C++」などというコメントは大歓迎です.

部分的に実装されている機能

サンプルコード

def main(): int {
    val i = "i";
    ref calendar = "Calendar";
    (Aizu() + i).f("u").advent(calendar)();
    return 0;
}

class Aizu {
    def ctor() {
        p( "A" );
    }

    def op +(v: ptr!int8) {
        p(v);
        return u("z");
    }
}

class u {
    def ctor(v: ptr!int8) {
        this.f(v);
    }

    def f(v: ptr!int8): ref(u) {
        p(v);
        return this;
    }
}

template(T: type)
def advent(_: u, c: T) {
    p("Advent");
    return \() => p(c);
}

これをコンパイルして実行すると

bytes => A
bytes => i
bytes => z
bytes => u
bytes => Advent
bytes => Calendar

と出力されます.(bytes =>はランタイムのデバッグログ)

pは標準ライブラリに含まれる関数です.ptrint8typeも標準ライブラリで定義されるクラスです.(標準ライブラリ)
このサンプルではテンプレートや演算子オーバーロード,UFCS,ラムダ式を使ってみました.

その他のサンプルはここにあります!

おわり

プログラミング言語を作るのは楽しすぎてつらいですよね.
Rillは全体的に構文や意味付けも未完成ですので,issueやpullreqメッチャください.一緒に文鳥言語を作りませんか?とてもアットホームな鳥小屋です.

次は〜

(◔⊖◔)つ @youxkei

鳥小屋のシンチョク#1

9月に入ってしまうので,鳥小屋のここまでのシンチョクのまとめ.

去年のBoost.勉強会 仙台で"鳥小屋を支える技術"というLTをしたものの,今や過去の技術は全て鳥小屋と共に倒壊しました.

Wandboxがつよくてつらい.

鳥小屋 is 何

いわゆるオンラインコンパイラです.

ProcGarden

ProcGarden(最新)

シンチョク

おわり

つらい

LLVMと俺俺ランタイムで例外を実装する(その1)

環境: Arch Linux(x86_64), LLVM 3.4, GCC 4.9.0

文鳥言語の言語機能に例外を追加したかったので,先にLLVM側の調査とランタイムを実装しました(進捗).自分で思い出すために後々読み返しそうなので,例外ハンドリングについてメモっておきます.

何かの参考になれば幸い.間違いなどは指摘していただけると嬉しいです.

今回実装したのはLinuxx86_64用の実装でtable-basedのものです.

コードはこちら yutopp/llvm-exception-handling-test

例外ハンドリング

LLVMの例外ハンドリングのドキュメントはこちら Exception Handling in LLVM

今回は,このドキュメントで示されている"Itanium ABI Zero-cost Exception Handling"を元に自前の例外ランタイムを実装したことになりますが,このドキュメントは,CやC++で使われている例外ハンドリングについて深く説明しているため,実際に言語のランタイムに実装するとなると少し物足りない感じがありました.でも読みやすくてスバラシイ〜

そして,次に参考にしたのが,LLVM PROJECT BLOG.New libunwind implementation in libc++abi

大体

例外のunwindには,libcxxabiに含まれるcxa*例外関数群が要求するUnwind*関数群(高レベルAPI)と,old HP libunwind projectで定義されたインターフェースであるunw*関数群(低レベル操作)の二通りがある.

多くのアーキテクチャでは”ゼロコスト”例外をC++に使っている.ゼロコストとは,例外が発生しない通常の実行では余計な命令が生じないものである.しかし,例外が投げられた場合には,ランタイムはどのようにレジスタをリストアし,現在のスタックフレームからcatch項まで"unwind"するかを,side tableを参照し把握しなければならない. スタックフレームを修正,全てのレジスタをリストアし,適切にスレッドをcatch節にresumeさせることが,libunwindの主な用途である.

みたいな事が書いてありました.

Itanium C++ ABI: Exception Handling でいうと,”libcxxabiに含まれるcxa*例外関数群” が”Level II: C++ ABI”以降,”Unwind*関数群”が,”Level I. Base ABI”になるようです.

従って,今回はLLVMと共に自前の例外ランタイムを実装したいので,このC++ ABIを使わずに,この部分を自前で実装すればいいことになります.また,Level 1 ABIの実装は共通なので,既にある実装を使うことができます. というわけで,Level 1 ABIについては,今回は既存の実装を利用しています(申し訳 of the world).

フォーマット

LLVMが生成してくれるASM テーブルフォーマット(ドキュメントてきとう訳)

例外が投げられた際に,どんな処理を取るべきか決定するために例外ハンドリングランタイムに使われるテーブルが2つあります.

Exception Handling Frame

例外ハンドリングフレームであるeh_frameは,DWARF debug infoに使われているunwind frameにとても良く似ています. このフレームは,現在のフレームをtear downし,以前のフレームの情報をリストアするために必要な全ての情報を含んでいます. コンパイル単位における,それぞれの関数の例外ハンドリングフレームに加え,全ての関数の共通する情報を定義した一般的な例外ハンドリングフレームも存在します.

Exception Tables

例外テーブルは関数のコードのある部分で例外が投げられた際に,どのアクションを起こすべきか,という情報を含んでいます. 例外テーブルを必要としないリーフ関数(注:関数テーブルエントリ(スタックフレームなど)を使用しない関数のこと)やnon-throwな関数のみを呼び出す関数を除いて,各関数には一つの例外テーブルが存在します.

これらのフォーマットの読み込みをコードに落とすのに,以下のスライドがとても参考になりました.

Compiler Internals: Exceptions and RTTI

また,例外処理で出てくる用語は以下の感じ

単語 意味
LSDA Language Specific Data Areaのこと.
landingpad 例外が投げられたあと,catch,またはclean upするための,ユーザーコードのセクションのこと.personality routineによってexception runtimeからコントロールを得た後,通常のユーザーコードに合流させるか,resumeによってランタイムに戻る,新しい例外をraiseするかといった目的に用いる.
personality routine C++(や他の言語)のランタイムライブラリにある,system unwind libraryとlanguage-specific exception handling semanticsとの間のインターフェースを提供する関数のこと.

LLVMでの流れ

  • landingpad 命令で例外の着地点をつくる
  • @llvm.eh.typeid.for を用いて例外を選択する

おわり

今回実装したもの

  • 言語固有の例外ハンドリングの関数(allocate, throw, resume, free)
  • personality routine

言語固有の例外ハンドリングの関数

C++ ABIを真似て適当に作った.

personality routine

今回の山場でした.unwindを行うライブラリと言語固有の機能のインターフェースを取り持つ関数です.

2段階のフェーズに分かれて呼ばれるようで,最初の探索フェーズで

  • LSDAの読み込み
  • landingpad の選択
  • call siteやaction_tableの読み込み
  • 適切なcatch節やclean upの選択
  • その情報の保存

を行い.

次の段階で,

  • 第一段階の情報の引き出し
  • 目的の節へのジャンプの登録

を行います.

C++D言語のランタイムの実装を参考にしました!

eh_personality.cc Source File

druntime/src/ldc/eh.d at ldc · ldc-developers/druntime

おわりに

くぅ〜疲れました!w

Binary Hacks ください.

その2に続く→

参考資料

dzeta.jp技術資料 - NPTLとC++例外処理 force_unwindの存在をこれで知りました.

g++の例外を捕まえよう!!(素手で)

exception handling | 0xdeadp0rk

Mono:Runtime:Documentation:LLVM

unwind自体の実装

gcc/libgcc/unwind-dw2.c at master · mirrors/gcc https://llvm.org/svn/llvm-project/libcxxabi/trunk/src/Unwind/UnwindLevel1.c

LLVM IRの構造の可視化をするメモ

LLVM IRの構造をグラフで見たかったので試してみました.メモ.

参考資料:

LLVM’s Analysis and Transform Passes

Visualizing code structure in LLVM

環境: Arch LinuxLLVM 3.4,graphviz 2.36.0

試す

試しに使ったC++コード(test.cpp)

ProcGarden - test.cpp (libc++がおかしいのでclangでなくGCCでビルドしています…ウッ)

そして,この test.cppclang++ test.cpp -emit-llvm -c -SLLVM IRにした結果は以下(test.ll)

ProcGarden - test.ll

このLLVM IRとoptコマンドを用いてdotファイルを生成し,それをgraphvizで可視化する.

CallGraph

opt test.ll -dot-callgraph > /dev/null

e.g. CallGraphをgraphvizを用いてPNGにする

dot -Tpng callgraph.dot > callgraph.f.png

f:id:yutopp:20140503003625p:plain

CFG

opt test.ll -dot-cfg > /dev/null

e.g. 関数fのCFGをgraphvizを用いてPNGにする

dot -Tpng cfg._Z1fv.dot > cfg.f.png

f:id:yutopp:20140503003546p:plain

Dominance Tree

opt test.ll -dot-dom > /dev/null

e.g. 関数fのDominance Treeをgraphvizを用いてPNGにする

dot -Tpng dom._Z1fv.dot > dom.f.png

f:id:yutopp:20140503003640p:plain

Post-dominance Tree

opt test.ll -dot-postdom > /dev/null

e.g. 関数fのPost-dominance Treeをgraphvizを用いてPNGにする

dot -Tpng postdom._Z1fv.dot > postdom.f.png

f:id:yutopp:20140503003658p:plain

おわり

次はLLVMで例外を使ってみる.

鳥小屋でOpenJDK9を動かしたときのメモ

オンラインコンパイラにOpenJDK9を入れた後にハマったのでメモ

オンラインコンパイラの実行環境ではメモリリソースに制限をかけている(rlimit_asで1.5GB程度)ので、そのままのJVMの起動ではリソース不足で動かなかった。だいたいJVMが2GB使うようだったので微妙に足りない…。

結局解決できたので、そのオプションを書いておく。
Java8からPermGenというものがMetaspaceというものに変わったようなのでそこもチェックする。

まずヒープ
-Xms 64m
-Xmx 128m

スタック
-Xss 512k

Metaspace
-XX:MaxMetaspaceSize=128M
-XX:MetaspaceSize=64M

ここまで指定すると
"Could not allocate metaspace: 1073741824 bytes"
と遺してJVMが死んでしまう。

そこで、以下のようにオプションを指定したところエラーは発生しなくなった。
-XX:CompressedClassSpaceSize=32M

-XX:CompressedClassSpaceSizeのデフォルト値は1024Mであり、エラーの内容とも一致しているのでこれが原因のはず。
エラーの発生箇所がjdk8/awt/hotspot: 209aa13ab8c0 src/share/vm/memory/metaspace.cppだったので、この値を変えてみたのだけど、結局これはなんなのだろう…

とりあえず、これでJVMのメモリ使用量が1GB程度になって無事動かせるようになった。


参考