YARV Maniacs 【第 7 回】 YARV 命令セット (4) 分岐
書いた人：ささだ
はじめに
YARV: Yet Another RubyVM を解説するこの連載。今回は (まだまだ) 命令セットの紹介の続きで、分岐を解説します。if 文とか、お馴染みのああいうやつです。ご想像通り、今回の内容はとっても簡単です。気楽に読んでみてください。
YARV の今後について
さて、本編に入る前に恒例の与太話を。
一部では YARV が 1.9 にマージされるのは今年のバレンタインデーだ、という話もありましたが、実際には 1.9 へのマージはもうちょっと先になるかと思います。積み残している作業は、リファクタリング関連で、特に API 名やファイル名などが統一がなされていない、ということで、この辺をしっかりと見直してからということになりそうです。まさに、名前重要、と言う感じです。CVS だと、ファイル名の整理とかしづらいので面倒ですね。いっそ、Ruby 開発で利用するバージョン管理システムを Subversion に移行してくれないかな思っているんですが。
さて、移行の具体的な方策として、とりあえずまつもとさんに YARV のコミッターになってもらいました (YARV Merged Matz)。まつもとさんに実際に手をつけてもらうことで、現実味が増したんではないかと思います。Ruby 2.0 も大分見えてきましたね (そういうことにしておきたいのです)。
さて、sheepman さんからのバグ報告 (と、その fix）などにより、大分 YARV も安定してきました。今 test-all をすると
ruby 1.9.0 (2006-02-14) [i686-linux]
YARVCore 0.3.3 (rev: 674) [opts: ]
...
1754 tests, 13147 assertions, 15 failures, 0 errorsこんな感じでした。まだちょこっと通らないテストも残ってますが (大半は Ruby の不思議な不思議なブロックパラメータ)、動かない機能が大分減ったという印象です。あなたも YARV を使ってみませんか？
ちなみに、バグ報告は yarv-dev へどうぞ。積んでるバグの一覧などは YARV Bugs で確認できます。
Over two orders of magnitude faster with YARV, yay for algorithmical optimization
ところで、RedHanded でも記事になっていましたが (Mauricio Skips Recursion With YARV’s Hidden Levels!)、秘密の VM コンパイルオプションを使うと、YARV ではアッカーマン関数が 2桁以上高速に動くんだそうです。凄いですね。これを見つけた Mauricio が凄い。
どんなに難しい、計算オーダの大きな問題も定数時間で答えちゃう、という話です。でも、答えが 42 だってわかっていないとダメなんですけどね。
YARV における分岐の基礎
まず、分岐について説明していく上で必要なことをまとめておきます。簡単にいうと「どうやって分岐するのか」ということと、「どこへ分岐するのか」ということです。
ちなみに、ジャンプとか分岐とか言っている操作は VM のプログラムカウンタ (PC) を操作して命令列中の任意の地点から実行を開始する操作をいいます。
条件ジャンプと無条件ジャンプ
YARV には条件ジャンプ命令 if 1 と unless、無条件ジャンプ命令の jump があります。
条件ジャンプ命令
条件ジャンプ命令は、読んで字のごとく条件によってジャンプしたりしなかったり、という命令です。条件によってジャンプ先を変えるわけではありません2。条件分岐命令 if はスタックからひとつ値をポップして、もしそれが真ならオペランドで指定された分岐先へジャンプし、そうでなければ何もしません。unless 命令はその逆です。
Ruby における真偽の判断は、値が nil か false なら偽、それ以外なら真ということになります。C 言語レベルでは RTEST(val) というマクロが用意されています。
if と unless 命令
YARV には否定の値を得るための not 命令があります。not 命令はスタックトップの値が真なら false を、偽なら true をスタックトップに置く命令です。not 命令があるならば、if / unless 命令はどちらか一方あればよいことがわかります。つまり、if 命令は not と unless という命令の並び、unless 命令は not と if 命令の並びで実現できるからです。
ただ、性能的な観点からと、コンパイラを作るのが楽だったという理由で (どちらもたいした事じゃないんだけど) 両方の命令を設けました。
無条件ジャンプ命令
無条件ジャンプ命令 jump は、問答無用で分岐先へジャンプします。いわゆる分岐ではありませんが、ここにまとめて書いておきます。
YARV におけるローカルな分岐命令、ジャンプ命令はこの 3 つだけです。何も難しいことはないですね3。
分岐先とラベル
さて、分岐先ですが、どのように指定するかというと、現在の PC からの増分値として指定します。たとえば、10 番地にある無条件ジャンプ命令 jump が 20 番地へジャンプしたければ、
0010 jump 8という命令列 (内部表現) になります。ここで +10 したいのに 8 を指定しているのは、「jump 8」という命令表現自体が 2 番地分消費するので、8 + 2 で 10 番地分進める、という意味にするためです。ちなみに、PC が減る方向にジャンプするときはこの増分値が負の値になります。
さて、上記で「内部表現」という言葉を使いました。なんでこんなことを言うかというと、YARV の逆アセンブラはこの場合、「jump 20」という命令を表示します。逆アセンブルした結果を見るとき、いちいち PC と増分値を足すのは面倒ですよね。
しかし、分岐先を数字で示しても、わかりづらいことこの上ありません。そこで、これからの擬似コードでは分岐先をラベルで表現します。C 言語などでお馴染みで、アセンブラでもお馴染みです。たとえば、
jump LABEL
...
LABEL:という命令列は、「…」で示している命令列をすっ飛ばして LABEL の位置へジャンプする、という意味です。分岐先のラベルは「(LABEL名):」と表記し、インデントをひとつ下げて表現するようにします。
本連載でも以前からこんな表記を使っていたような気がしますが、一応ここで定義しておきました。まぁ、見てわかるよね。
さて、これで基本はおしまいです。簡単ですね。
条件分岐
では、説明した命令を利用して Ruby の if 文などをどうやって表現するか見てみましょう。
if 文
とっても簡単な if 文の例である
# Ruby プログラム
if COND
THEN_BODY
endという命令を見てみましょう。ところで、COND とか THEN_BODY とか、全部大文字で書いてありますが、全部大文字の部分は任意の Ruby 式がまとまっていると思ってください。なんでもいいです。たとえば、COND に if 文が入っていても問題ありません。
これを YARV 命令列で表現すると、次のようになります。
# YARV 命令列
<COND>
unless ELSE
<THEN_BODY>
ELSE:ここで <COND> と <THEN_BODY> は COND と THEN_BODY をコンパイルした結果ということを示すことにしておきます。
処理を見てみると、<COND> 式はスタックにひとつ値を積み、unless 命令で、もしその値が偽なら ELSE ラベルへジャンプする、ということになります。馬鹿にするな、というほど簡単ですね。
では、ELSE 節があるときにどうなるか見てみましょう。次のような Ruby プログラム
# Ruby プログラム
if COND
THEN_BODY
else
ELSE_BODY
endは、以下のような YARV 命令列にコンパイルされます。
# YARV 命令列
<COND>
unless ELSE
<THEN_BODY>
jump END
ELSE:
<ELSE_BODY>
END:今度は jump 文が増えました。これも、説明するよりも見てもらったほうが早いですね。<THEN_BODY> を実行してから、後に続く <ELSE_BODY> をスキップするために END へジャンプしています。簡単ですね。
次に、Ruby 玄人も打ち間違える elsif を含んだプログラムを見てみましょう。
# Ruby プログラム
if COND
THEN_BODY
elsif COND_ELSIF_1
ELSIF_BODY_1
elsif COND_ELSIF_2
ELSIF_BODY_2
else
ELSE_BODY
endこのプログラムは、以下のプログラムと同じです。
# Ruby プログラム改
if COND
THEN_BODY
else
if ELSIF_COND_1
ELSIF_BODY_1
else
if ELSIF_COND_2
ELSIF_BODY_2
else
ELSE_BODY
end
end
endこれを、先に説明したものと同じようにコンパイルするだけです。
# YARV 命令列
<COND>
unless ELSIF_1
<THEN_BODY>
jump END_THEN
ELSIF_1:
<ELSIF_COND_1>
unless ELSIF_2
<ELSIF_BODY_1>
jump END_ELSIF_1
ELSIF_2:
<ELSIF_COND_2>
unless ELSE
<ELSIF_BODY_2>
jump END_ELSIF_2
ELSE:
<ELSE_BODY>
END_ELSIF_2:
END_ELSIF_1:
END_THEN:最後にラベルが複数重なっていますが、結局同じ番地を指していることになります。ちょっと込み入っていますが、やっていることは単純ですね。
では、具体的な Ruby プログラムで実験してみましょう。
# Ruby プログラム
a = 0
if a > 10
a = :then
elsif a > 5
a = :elsif1
elsif a > 0
a = :elsif2
else
a = :else
endこのプログラムを実際にコンパイルすると次のようになります。わかりやすいようにコメントを入れておきました。
# YARV 命令列
# a = 0
0000 putobject 0
0002 setlocal a
# if a > 10
0004 getlocal a
0006 putobject 10
0008 send :>, 1, nil, 0, <ic>
0014 unless 22
# a = :then
0016 putobject :then
0018 setlocal a
0020 jump 62
# elsif a > 5
0022 getlocal a
0024 putobject 5
0026 send :>, 1, nil, 0, <ic>
0032 unless 40
# a = :elsif1
0034 putobject :elsif1
0036 setlocal a
0038 jump 62
# elsif a > 0
0040 getlocal a
0042 putobject 0
0044 send :>, 1, nil, 0, <ic>
0050 unless 58
# a = :elsif2
0052 putobject :elsif2
0054 setlocal a
0056 jump 62
# else
# a = :else
0058 putobject :else
0060 setlocal a
# exit
0062 putself
0063 send :exit, 0, nil, 12, <ic>
0069 endまぁ、長いですけどそのまんまだし、読めばわかりますよね。
unless 文
if 文の次は unless 文を説明します。いや、説明しようと思ったんですが、if 文で出てきた unless 命令を if 命令に変更するだけなので省略します。
if 文で unless 命令、unless 文で if 命令、というのがちょっと面白いですね。
後置の if / unless 文
Ruby は後置の if 文、unless 文が記述できます。たとえば、
if COND
THEN_BODY
endの代わりに
THEN_BODY if CONDと書けます4。
後置の式は、そのまま普通の if 文に置き換えられるため、YARV のコンパイラは普通の if 文として扱います。というか、パーサが普通の if 文と変わらないように構文木を作るため、違いがわからないということになります。
ついでにいうと、三項演算子 (a ? b c : d みたいなの) も同様に、普通の if 文と同じようにコンパイルされます。
and / or 演算子
| Ruby には and もしくは &&、同様に or もしくは | という演算子がありますが、これも条件分岐と言えるでしょう。 |
# Ruby プログラム
a and b and cは、
# Ruby プログラム
if __tmp__ = a
if __tmp__ = b
c
else
__tmp__
end
else
__tmp__
endとほぼ同じ意味 (仮に作った変数 tmp が余計) になります5。
これを YARV 命令列にしてみると次のようになります。
# YARV 命令列
# a = b = c = nil
0000 putnil
0001 dup
0002 setlocal c
0004 dup
0005 setlocal b
0007 setlocal a
# if __tmp__ = a
0009 getlocal a
0011 dup
0012 unless 23
0014 pop
# if __tmp__ = b
0015 getlocal b
0017 dup
0018 unless 23
0020 pop
# c
0021 getlocal c
0023 endtmp のような一時的な変数の代わりにスタックトップをこの目的に使っています。そのために dup 命令によって値を複製してスタックに積んでいます。
or もちょっと変わっただけです。a or b or c を if 文で表すと次のようになります。
# Ruby プログラム
if __tmp__ = a
__tmp__
elsif __tmp__ = b
__tmp__
else
c
endこれを YARV 命令列で表すと次のようになります。
# YARV 命令列
# a = b = c = nil
0000 putnil
0001 dup
0002 setlocal c
0004 dup
0005 setlocal b
0007 setlocal a
# if __tmp__ = a
0009 getlocal a
0011 dup
0012 if 23
0014 pop
# elsif __tmp__ = b
0015 getlocal b
0017 dup
0018 if 23
0020 pop
# c
0021 getlocal c
0023 endまぁ、ゆっくり考えれば簡単ですね。
繰り返し
さて、繰り返しは条件分岐と無条件分岐を組み合わせれば作れるのは誰でも知ってますよね。たとえば、C 言語では、
while(expr){
body;
}という繰り返しは
while_start:
if(!expr){
goto while_end;
}
body;
goto while_start;
while_end;と表現できます。釈迦に説法ですみません。
さて、我らが Ruby では while と until 文を使って繰り返しを表現できますが、while と until は if と unless のように条件文を逆にすればいいだけなので while 文だけ説明します。
while 文
早速ですが Ruby プログラム
# Ruby プログラム
while LOOP_COND
LOOP_BODY
endは、YARV 命令列では次のようにコンパイルします。
# YARV 命令列
jump LOOP_START
LOOP_BODY_START:
<LOOP_BODY>
LOOP_START:
<LOOP_COND>
if LOOP_BODY_START
LOOP_END:後置の while では、必ず一回は LOOP_BODY を実行するので最初の jump 命令がなくなります。
# Ruby プログラム：後置の while 文
begin
LOOP_BODY
end while LOOP_COND # YARV 命令列：後置の while 文
LOOP_BODY_START:
<LOOP_BODY>
LOOP_START:
<LOOP_COND>
if LOOP_BODY_START
LOOP_END:さて、LOOP_COND の処理を、LOOP_BODY の前に持ってきてもいいんですが (初期の YARV はそうしていました)、そうすると次のようになります。
# YARV 命令列
LOOP_START:
<LOOP_COND>
if LOOP_BODY
jump LOOP_END
LOOP_BODY:
<LOOP_BODY>
jump LOOP_START # これが余分
LOOP_END:繰り返しのたびに「jump LOOP_START」を余計に行うことになります (先の例だと最初の一回だけ)。まぁ、たった 1 命令なんですが、されど 1 命令ということで、今のようにしています。
具体的な例を示しましょう。
# Ruby プログラム
a = nil
while a
b
endこのような Ruby プログラムでは次のような YARV 命令列にコンパイルされます。
# YARV 命令列
# a = nil
0000 putnil
0001 setlocal a
# while a をする準備
0003 jump 13
# b
0005 putself
0006 send :b, 0, nil, 12, <ic>
0012 pop
# while a の条件式
0013 getlocal a
0015 if 5
0017 putnil
0018 end条件式の最適化
さて、分岐における条件式は、ちょっとの工夫で最適化が可能です。その方法を少し紹介してみます。
リテラルだけの条件式
たとえば、if 1 という式があった場合 (あまり用途が考えられませんが)、その条件式は必ず真になります。while true という表現で無限ループを作るという例なら見かけるかな？ さて、そういう場合、if 命令などを利用するのは無意味なので、無条件ジャンプ命令になります。nil、false なら分岐しないので、そもそも if 命令自体が消えます。
# Ruby プログラム
if 1
p :ok
end
if false
p :ng
end# YARV 命令列
0000 putself
0001 putobject :ok
0003 send :p, 1, nil, 4, <ic>
0009 pop
0010 jump 22
0012 putself
0013 putobject :ng
0015 send :p, 1, nil, 4, <ic>
0021 end
0022 putnil
0023 end本当は、if false; BODY; end の場合、BODY をスキップするための jump 命令も省略できるのですが (不到達ブロックの除去)、面倒なのでやっていません。
否定の条件式
たとえば if !expr という条件があった場合、これは unless expr と同じ意味になります。
具体的な例としては、
# Ruby プログラム
a = nil
if !a
p :ok
endという Ruby プログラムは
# YARV 命令列
0000 putnil
0001 setlocal a
# if !a <= not 命令を省略
0003 getlocal a
0005 unless 9
0007 putnil
0008 end
0009 putself
0010 putobject :ok
0012 send :p, 1, nil, 4, <ic>
0018 endとなります。
and / or が混ざる条件式
and 式、or 式は値を返す式ですが、条件文として使われる場合、その値は重要ではなくその結果の真偽値が問題になります。
たとえば、素直に実装すると、
# Ruby プログラム
if A and B
BODY
endは
# YARV 命令列
<A>
dup
unless END_AND
<B>
END_AND:
unless END_IF
<BODY>
END_IF:となりますが、この命令列はちょっと冗長なので、
# YARV 命令列改
<A>
unless END_IF
<B>
unless END_IF
<BODY>
END_IF:とすることが出来ます。
具体的な例を出してみましょう。
# Ruby プログラム
a = b = nil
if a and b
p :ng
end
p :okは、次のようにコンパイルされます。
# YARV 命令列
0000 putnil
0001 dup
0002 setlocal b
0004 setlocal a
# if a and b
0006 getlocal a
0008 unless 24
0010 getlocal b
0012 unless 24
# p :ng
0014 putself
0015 putobject :ng
0017 send :p, 1, nil, 4, <ic>
0023 pop
# p :ok
0024 putself
0025 putobject :ok
0027 send :p, 1, nil, 4, <ic>
0033 end実現手法
条件式に or や and はよく出てくるので、この最適化はしっかりとしたいところです。ちょっと面倒そうですが、少し問題を一般化すればこの最適化を簡単に行うことが出来ます。
A and B という式が条件式だった場合、真なら then_label、偽なら else_label へ飛ぶということにすると、条件式を
<A>
unless else_label
<B>
unless else_label
jump then_labelというプログラムを生成すればいいことになります。
or の場合は
<A>
if then_label
<B>
if then_label
jump else_labelというプログラムを生成します。
さて、これを
if A and B
BODY
endという式に適用してみると、
# YARV 命令列
<A>
unless else_label
<B>
unless else_label
jump then_label # (*)
then_label:
<BODY>
else_label:となります。(*) で示したところは次の命令に無条件ジャンプしろ、という命令なので、無駄ですね。というわけで、こいつは削ります。
# YARV 命令列
<A>
unless else_label
<B>
unless else_label
<BODY>
else_label:求める結果が得られました。
ここでは and と or を引き合いに出していますが、not もこれで一般化できます。if not A というプログラムは
<A>
unless else_label:
jump then_label:
then_label:
<BODY>
else_label:というようになります。
これを一般化したものは compile.c の compile_branch_condition() という関数にまとめられています。上述した「リテラルだけの条件式」は無条件ジャンプにする、という最適化もこの中にまとめています。
compile_branch_condition() は引数として、条件文としてコンパイルしたいノード (node) と、もし条件が成立したときに飛ぶジャンプ先 (then_label)、そうでない場合に飛ぶジャンプ先 (else_label) を取ります。たとえば、if !expr というプログラムがあった場合、条件文としてコンパイルする式 (node) には !expr が指定されます。if !expr は unless expr と同じですから、この結果はcompile_branch_condition() を then_label、else_label 逆にして、node を expr として実行したものでいいということになります。not 命令を見事に省けましたね。まぁ、詳しくはソースを読んでください。
ピープホール最適化
上述したように、「次の命令へジャンプする無条件ジャンプ命令」は、削ってもまったく問題ありません。というわけで、こういうのは削ることにします。こういう、コンパイル結果をちょこっとだけ見てちょこっとだけ命令列を変更する手法をピープホール (のぞき穴) 最適化といいます。
他にも、分岐関連では次のようなピープホール最適化をしています。
- 無条件ジャンプする命令 (a) のジャンプ先が無条件ジャンプ命令 (b) だった場合、(a) のジャンプ先を (b) のジャンプ先に変更する。
jump LABEL1 # (a)
...
LABEL:
jump LABEL2 # (b)
=> ピープホール最適化
jump LABEL2 # ジャンプ先を LABEL2 へ変更
...
LABEL
jump LABEL2- 無条件ジャンプ命令のジャンプ先が end 命令だった場合、ジャンプ命令を end 命令に置き換える[^6]。
jump LABEL
...
LABEL:
end
=> ピープホール最適化
end # jump 命令が end 命令に
...
LABEL:
end- 「if L1; jump L2; L1: …」という命令列は「unless L2」という命令列に置き換える。
if L1
jump L2
L1:
=> ピープホール最適化
unless L2 # if 命令と jump 命令を融合言葉だけだとちょっとわかりづらいですが、コードを見ると、ああ、なるほど、とわかるかと思います。
ちなみに、これらの最適化は自分で考えたものもあるし、人から教えてもらったものもあるんですが、全てよく知られているものばかりです。調べるより自分で考えたほうが早い、というのもあるんで、あまり真面目に調べていないんですが。何か、これはいいぞ、という方法があったら教えてください。
おわりに
今回は YARV における分岐について説明しました。
このあたり、分岐のあたりは考えることがなくとても簡単で、特に最適化について考えやすい部分なので、ついつい色々と考えてしまうのですが、分岐命令を一つ減らしてもあんまり速くなんないんですよね。でも、楽しいので考えてしまう。
さて次回はまだまだ命令セットの説明ですが、まだネタが思いつかないので未定です。えーと、お楽しみに。
著者について
ささだこういち。学生。
先日紙の雑誌に記事を書かせてもらったんだけど、るびまの記事執筆がいかに楽かを痛感しました。るびまでは識者のチェックが入るし、リンクが貼れるし、何より分量を気にしないでいい。紙の雑誌のほう、色々ご迷惑をおかけいたしました。まぁいいか (いや、よくないよ)。
バックナンバー
if a if b if tmp = c tmp end end end ではありません。返り値を考えてみてください。 [^6]: 先ほどのプログラムで最後に p :ok と書いていたのは、end の置き換えを回避するためでした。