2009-03-18

erlangのアセンブリを読んでみる．

Erlang

に興味が湧いたので，erlangのアセンブリコードを見てみた．beamのバイトコードにほぼ一対一対応していると考えていいと思う．
まず単純な定義の場合

fact(0) -> 1;
fact(N) -> N * fact(N-1).

以下のようになる．アセンブリコードの各行はそのままerlangのタプルとなっている．ここで，

{x, N}: はx registerという．Nはレジスタ番号．
{y, N}: はy registerという．レジスタという名前だが，スタック上に置かれる．
{f, N}: は{label, N}に対応している．{f, 0}はプログラム終了コードのラベル．

{function, fact, 1, 2}.   % 引数1個, {label,2}がエントリーポイントという意味．
  {label,1}.
    {func_info,{atom,fact},{atom,fact},1}.
  {label,2}.
    % 引数は{x, 0}に入っている．
    {test,is_eq_exact,{f,3},[{x,0},{integer,0}]}. % N!=0なら{label, 3}に飛ぶ
    {move,{integer,1},{x,0}}. % 戻り値は{x, 0}に入れる
    return.
  {label,3}.
    {allocate_zero,1,1}. % スタックフレームを1ワード分確保．
    {gc_bif,'-',{f,0},1,[{x,0},{integer,1}],{x,1}}.
    {move,{x,0},{y,0}}.  % もとのNをスタックに退避
    {move,{x,1},{x,0}}.
    {call,1,{f,2}}.       % 再帰呼び出し．1は引数の数を表す．
    {gc_bif,'*',{f,0},1,[{y,0},{x,0}],{x,0}}. 
    {'%live',1}.
    {deallocate,1}.
    return.

見ての通りerlangだからといって何も特殊な点はなく，いたって普通のコードだった．
スタックも通常どおり消費されているので，Erlangが末尾再帰最適化をしてるか調べようとした - みずぴー日記でスタックオーバーフローしないというのは単にスタックを大きく取れているからなのだと思う．

続いて末尾再帰バージョンを見てみる。

fact(N) -> fact_iter(N, 1).

fact_iter(0, R) -> R;
fact_iter(N, R) -> fact_iter(N-1, N*R).

{function, fact, 1, 2}.
  {label,1}.
    {func_info,{atom,fact},{atom,fact},1}.
  {label,2}.
    {move,{integer,1},{x,1}}.
    {'%live',2}.
    {call_only,2,{f,4}}.

{function, fact_iter, 2, 4}.
  {label,3}.
    {func_info,{atom,fact},{atom,fact_iter},2}.
  {label,4}.
    {test,is_eq_exact,{f,5},[{x,0},{integer,0}]}.
    {move,{x,1},{x,0}}.
    return.
  {label,5}.
    {gc_bif,'-',{f,0},2,[{x,0},{integer,1}],{x,2}}.
    {gc_bif,'*',{f,0},3,[{x,0},{x,1}],{x,1}}.
    {move,{x,2},{x,0}}.
    {call_only,2,{f,4}}.

末尾呼び出しの部分がcall_onlyとなっているので，確かに末尾再帰の最適化が行われている事が分かる．y registerが使われていない事からもスタックが消費されていないことが見て取れる．

ところでこれらのコードをみる限り，スケジューラとレジスタ割り当てがあまり賢くないようだ．
コンパイル時間を優先して簡略化しているのかな．[追記]コンパイラを見てみたら、そもそも命令スケジューリングを行っていないように見えた．もしかしたらアセンブリ -> バイトコードのフェーズか，beam側で何かやっているかも知れない．

2009-01-17

[C/C++][コンパイラ] オペランド評価の実際

こことか

http://code.nanigac.com/forum/view/342

こことか

http://www.st.rim.or.jp/~phinloda/cqa/cqa7.html

で話されているオペランドの評価に関してだけれども, もちろん処理系依存なので一般的な議論はできないが,実際のところコンパイラの実装がどうなっているかは興味がある所ではないかと思う。

例えばC Q&Aの例の

int i = 7;
printf("%d", i++ * i++);

が49になるのは, まぁ納得できる人は多いと思うけれども,

int i = 7;
printf("%d", ++i * ++i);

が81になると言ったら(つまり2つの++iがどちらも9になる), 驚く人は結構いるのではないかと思う。
実はこれは何も奇妙な話ではなく,コンパイラを素直に実装するとこうなってしまう。多くのコンパイラで同じになっているのではないだろうか。

説明

プログラムは何でも機械語まで落ちるわけなので, コンパイルの途中で直列化を行う必要がある。例えば

op(e1, e2, ..., en)

というオペランドがn個ある命令を直列化する場合には

e1を直列化したもの
e2を直列化したもの
...
enを直列化したもの
op(e1の評価値, e2の評価値, ..., enの評価値)

という風になる。(並べ方は自由だけれども, 第1オペランドから並べるのがまぁ自然でしょう)

具体例をあげると

x = y++;

は

t = y;
y = y + 1;
x = t;  /* tがy++の評価値 */

とか

x = y;
y = y + 1;

とかになる。(実装は前者が楽だが,後者の方が効率が良く,例えばgccは主に後者を使う.)
++yの場合は「yそのものを評価値として使用」して

x = ++y;

を

y = y + 1;
x = y;

としてしまう事が多い。

以上を踏まえて冒頭の例を考えて見ると,

i = 7;
x = ++i * ++i;

は

i = 7;
i = i + 1; /* 左の++i (iが評価値) */
i = i + 1; /* 右の++i (iが評価値) */
x = i * i;

となるので++i*++iが81になるわけである。

次に

http://code.nanigac.com/forum/view/342

の

#include <stdio.h>
void f(int x;int y;int z){
        printf(“%d %d %d\n”,x,y,z);
}
int main(){
        int n=10;
        f(n++, --n, ++n);
        return 0;
}

の出力がなぜ

10 11 11

となるかだけれども,

n = 10;
f(n++, --n, ++n);

を直列化すると

n = 10;
t = n;      /* tがn++の評価値 */
n = n + 1;
n = n - 1; /* このnが--nの評価値 */
n = n + 1; /* このnが++nの評価値 */
f(t, n, n);

となるので,f(10, 11, 11)という呼び出しになると説明できる。

以上の話は, もちろん規格で何も定められていない話なのでさまざまな実装がありえるし, 同一の実装でも最適化などの具合によっていくらでも変わりうる話であるという事に注意。
ただ, 未定義だからとそれですませるのではなく，実際の所どうなっているのかに興味を持ってみるのも面白いのでは無いかと思う。

2009-01-10

形骸化している代入演算子の優先順位

コンパイラ

true ? 1 : x = 2
のようなソースがパースエラーにならないかどうか。
ちょっと調べた限りでは、

書ける：

Ruby

C#

書けない：

C

Java

のように分かれております。
Javaと文法が似てると思ってたC#ですが、こんなところに違いがあったんですねぇ。
http://mono.kmc.gr.jp/~yhara/d/?date=20090108

を読んで思ったこと。

> こんなところに違いがあったんですねぇ
演算子の優先順位という観点でみると, 4言語とも(代入) < (条件)と同じなので, もしこの式が

true ? 1 : (x = 2)

とパースされるならそれはある意味でバグです.

ただ, Rubyに関して言えば代入式が括弧無しで右辺に来れるので,代入演算子の優先順位が崩れてしまうのは仕方がないことなんですよね。
例えば

x = 1 + x = 2

が

x = (1 + (x = 2))

になるなど、代入演算子の優先順位はもはや形だけになってしまっています。(この例だと左の=と右の=で使われている文法規則が違うのでこういうことになる)
私はこういった点をちゃんとドキュメントに明示しなければならない(代入演算子とひとくくりにしないで, 「〜にある代入演算子」と種別分けするとか)と思いますが,多分暗黙の了解があるんでしょうね。

ところで,C#はどうなんだろうか。

2009-01-08

[コンパイラ][Haskell][OCaml] Haskellのinfixの仕組み

OCamlでは＜や | で始まる中置演算子は左結合になるため、|> はO.K.ですが、<| 演算子をつなげたときにカッコが必要になってしまいます。
http://d.hatena.ne.jp/mzp/20090105#c1231290114

なんだそれと思ったが,ほんとだった。

  | ['=' '<' '>' '|' '&' '$'] symbolchar *
            { INFIXOP0(Lexing.lexeme lexbuf) }
(* 略 *)
  | ['*' '/' '%'] symbolchar *
            { INFIXOP3(Lexing.lexeme lexbuf) }

とレキサの中で先頭文字だけ('**'のみ2文字)を見て演算子の種別分けをしている。
なんでこんな設計になっているんだろうか。(手抜き? 高速化の為?)

ところで,演算子の結合性を指定できる言語にSMLやHaskellがある。例えばHaskellでは

infixr 5 <+>   -- 右結合性で優先順位は5

などと指定できる。しかし, yaccなどのコンパイラコンパイラには動的に定義される演算子を扱う方法がないので一体どうやっているのかが気になった。
そこでghcを読んでみたところ,以下のようになっていた。

パース時には全て同一の結合性(全部左結合)としてパースする
型検査時のα変換(異なる値の変数には違う名前を割り振る)のフェーズで, 結合性をチェックして組み換える

組み替えは,(e1 op1 e2) op2 e3 となっている部分で op1とop2の結合性を比較して,必要ならe1 op1 (e2 op2 e3)に直すというようにする.

以下が組み替え処理の一部。

-- (e11 `op1` e12) `op2` e2
mkOpAppRn e1@(L _ (OpApp e11 op1 fix1 e12)) op2 fix2 e2
  | nofix_error = do
    addErr (precParseErr (ppr_op op1,fix1) (ppr_op op2,fix2))
    return (OpApp e1 op2 fix2 e2)

    -- op2の方が結合性が高い
  | associate_right = do
    -- 新しく組み直した e12 `op2` e2 の再組み替え
    new_e <- mkOpAppRn e12 op2 fix2 e2
    return (OpApp e11 op1 fix1 (L loc' new_e))
  where
    loc'= combineLocs e12 e2
                                           -- 結合性のチェック
    (nofix_error, associate_right) = compareFixity fix1 fix2

-- nofix_error = False, associate_right = Falseの時は何もしない

何か面白いことをやっているかと思ったら想像通りでおもしろくなかった。もっと工夫したやり方はないだろうか。

ところで,Haskellでは型検査が終わるまで構文木は正しくない状態という事になるけれども,これは一年以上放置していたなぜ型検査は脱糖の前か?という疑問の解答の一つになった。

2009-01-04

[日記] あけましておめでとうございます

しばらく卒論関係のコーディングに追われているので, 2008-12-11 - mad日記の続きがなかなかできないでいます。そのうち時間を見つけて何とか。

ところで,2008年もいろいろあったのにブログを読み返したらなんかコンパイラの話ばかりで悲しかったので,もうちょっと日記を書こうかと思った。

最近の主だった出来事。

12/24

塾の高3クラス最終授業日なので授業後に壮行会をした。今年は教え子に企画をさせてみたが,生徒持参のガチャピンの着ぐるみを着ながら若干後悔。
でも,ケーキを作って持ってきてくれる子がいたり,ロシアンルーレット饅頭(見事私が当たりを引いた)とかジェンガを用意してたりとなかなか盛り上がったので良かったかもしれない。
皆様受験がんばって下さい。

12/31〜1/3

久しぶりに故郷の岩手で年越し。寒かった。
年を越しながら, ひたすら自作コンパイラのバグと戦っていた。

1/2

高校の吹奏楽部の同級会に参加したが,想定外の男1女8というハーレム状態で一人おどおどしてきた。
久しぶりの飲み会+カラオケ+ボーリングでだいぶストレス発散をする事ができた。
飲み会では会社の友達が派遣切りにあったとか,転職するだとかいった話題がやはり多かったように思う。

1/3

小学校以来の友達に第一子(女の子)ができたという連絡をもらったのを思い出し会いに行った。やはり赤ん坊は可愛い。さらにその後, 町をぶらついていたら中高時代の同級生の夫婦に遭遇。そいつは既に2児の親になっていた。
もうそんな歳かとしみじみ。田舎だから早いだけかもしれないけれども。

2008-12-11

参照とポインタの違い

C/C++

参照とポインタの機能面の違いというのは良く知られているかと思いますが,コード生成の違いに関しては結構知らない方が多いのかもと思い解説します。
記事が大変長くなってしまいましたが, 個人的には参照は非常に面白い物だと思っていましてそれが伝わればと思います。もし何か間違いがあれば誰か教えて下さい。

まず, 参照とはつまりエイリアス(別名)だというのは良いかと思いますが,それをどう実現するかに関して規格は一切言及していないんですね。どうやるかはコンパイラの自由です。

具体的にどういう実現方法があるかというと, unionやハードウェア固有の機能の利用(特殊なメモリとか)もありえますが,現実的には

ポインタ
名前置換 (分かり易く言うと #define x y みたいなただの置換)

がほとんどだと思います。
C++の参照は再代入不可, アドレス取得不可等の制約があるため簡単な解析で後者にも使えるというのがポイントで, Javaなどの参照とは異なっています。

そして, コンパイラはポインタなんて極力使いたくないので, 可能な場合は置換で参照を処理します。

では, どういう場合にポインタを使用するかというと他の関数の引数として渡す場合等, そうせざるを得ない場合です。例えば

void
pair_swap(std::pair<int, int> &p)
{
    int t = p.first;
    p.first = p.second;
    p.second = t;
}

と

void
pair_swap(std::pair<int, int> *p)
{
    int t = p->first;
    p->first = p->second;
    p->second = t;
}

は通常はほぼ同じアセンブリになると思います。

次にこれらがインライン化された場合を考えてみます。

参照の場合

std::pair<int,int> x = std::make_pair(0, 1);
pair_swap(x);
std::cout << x.first << x.second << std::endl;

が

std::pair<int,int> x = std::make_pair(0, 1);
std::pair<int,int> &p = x;
int t = p.first;
p.first = p.second;
p.second = t;
std::cout << x.first << x.second << std::endl;

になります。すると,もはやpがポインタである必要がないので,ただの置換で処理します。

std::pair<int,int> x = std::make_pair(0, 1);
int t = x.first;
x.first = x.second;
x.second = t;
std::cout << x.first << x.second << std::endl;

次に, 全てのアクセスがx.firstかx.secondの形なので, xに連続領域を割り当てる必要がない事が解析され,pairはバラバラに分解されます。

int x_first = 0;
int x_second = 1;
int t = x_first;
x_first = x_second;
x_second = t;
std::cout << x_first << x_second << std::endl;

最終的に定数畳み込みで

std::cout <<  1 << 0 << std::endl;

になります。こんな感じで参照を利用すると, 他のコード変換の効果が向上する場合が結構あります。

ポインタの場合

インライン化すると

std::pair<int,int> x = std::make_pair(0, 1);
std::pair<int,int> *p = &x;
int t = p->first;
p->first = p->second;
p->second = t;
std::cout << x.first << x.second << std::endl;

となります。さて, これの最適化は困難です。pは再代入などが可能なので, ただの置換では処理できません。より最適化をかける為にはエイリアス解析という高度な解析が必要になります。

g++の場合は, この程度の単純なコードであれば-O2で両者とも全く同じコードになりますが, コンパイラの苦労度合は全然違うんですね。
エイリアス解析は完全に行う事が困難なので,分岐が入った複雑なコードになると-O2でも差が現れてくると思います。

まとめですが, 参照は可能な場合は単なる置換で処理されるので生成されるコードも変わってきます。もっと面白い事をしているコンパイラもあるかもしれません。

ここに書いたのは参照の実現の一形態であって, 処理系によって異なるということに注意しておきます。~~少なくともg++では以上のような感じになっているようです。~~[追記]これは調べなおします。

2008-12-11

寺田寅彦

科学者とあたまを書いたひとだけれども、この名前どっかで聞いた事があるなと思ったら, 昨日劇団青年座の人の講演で聞いたのだった。

「フユヒコ」という劇団青年座の公演が明日NHKで放送されるらしいです。冬彦ってのは寺田寅彦のペンネームらしい。
http://cgi4.nhk.or.jp/hensei/program/p.cgi?area=001&date=2008-12-12&ch=31&eid=9950
おもしろそうだから観てみようかな。

ところで小柴先生が同じような事を言っていたのを思い出した。このインタビューは面白い。

一流の理論家は、「自分の理論では、ここまでは使えるけれど、これから先は分からない」という適用限界をいつも意識している。ところが二流の理論家というのは、自分が名前を覚えた、あるいは、使った理論で何でもやれると思ってしまう。二流の理論家に困らされるのは、新しい実験計画が出てきたら、自分の理論じゃあそれは料理できないから、こんなものはつまらんと言ってはじいちゃうところだね。
(中略)
二流の理論家というのは、物事を全部知っていると思っているから、かえって害を及ぼすことが多いんだ。
東京大学理学部2006-2007 - 東京大学大学院理学系研究科・理学部