WebAssemblyのbr命令について

はじめに

WebAssemblyにはbrという命令があります。
この命令はbr <label>という形になっており、<label>が示す制御構造に対して何らかの動作をします。
例えばブロックに対して使えばブロックを抜け、ループの中で使えばcontinueのような振る舞いをします。
wasmのループについてはκeenさんのWebAssemblyのloopはまりどころという記事を見てみて下さい。
なぜこのように制御構造によってブロックを抜ける働きをしたり、continueの働きをしたりするか仕様書を読んでいたところ理由が分かり面白いと思ったので記事にしました。

br命令

基本的にはbr 数値という形の命令です。この数値は相対的な値となっておりbr命令を囲っているすぐ外側の制御構造に対してなにかするときはbr 0と、その外側であればbr 1と...いうふうに指定します。
また、watでは制御構造に$labelをつけることでbr $labelと書けばbr命令がどの深さに関係なくその制御構造に対して命令を実行することができます。

例

関数に対して使うとその関数を抜けます。

(call $log (i32.const 1))
(br 0)
(call $log (i32.const 2))

;; output: 1

ブロックで使うとそのブロックを抜けます。

(block $label
  (call $log (i32.const 1))
  (br $label)
  (call $log (i32.const 2))
)
(call $log (i32.const 3))

;; output: 1 3

ちなみにこのwatはwasmにコンパイルすると以下のコードと等しくなります。

(block
  (call $log (i32.const 1))
  (br 0)
  (call $log (i32.const 2))
)
(call $log (i32.const 3))

以下のコードはbr 1としているのでbr命令の2つ外側の制御構造、つまり関数を抜けます。

(block
  (call $log (i32.const 1))
  (br 1)
  (call $log (i32.const 2))
)
(call $log (i32.const 3))

;; output: 1

ループに対してはcontinueとして働きます。brがなければループは一回しか実行されません。
br_ifは引数が0でなければbrを実行する命令です。

(local $n i32)
(loop $loop
  (call $log (get_local $n))
  (set_local $n (i32.add (get_local $n) (i32.const 1)))
  (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
)

;; output: 0 1 2

labelとbr命令の正体

なぜbrは対象の制御構造によってブロックを抜けたりcontinueとして働いたりするのでしょうか。
これはbr nはn番目に外側(すぐ外側は0番目)のlabel命令の継続にジャンプする命令だからです。
label命令というのは仕様を書くために出てくる拡張命令みたいなものでwasmコード自体には現れません。
label命令はlabel {継続} {命令}のような形になっています。そして通常は{命令}を評価しそれが終われば、labelの評価は終了します。brされれば{命令}の評価を中断し、{継続}を評価し、それが終わればlabelの評価は終了します。
そしてblockやloopを評価すると一旦このlabel命令に変換されます(これは仕様書上の話で実際の処理系がこうなっているという事ではない)。また関数に入ったときもlabelが作られます(これによって関数の直下でbr 0とすると関数を抜けられます。)
例えばblockであればlabel {} {...}のように変換されるのでbrでジャンプする継続は空です。つまりbrされれば何もせずにブロックを抜けます。
ifや関数に入った時も継続が空のlabelに変換されるのでbrされれば何もせずにその制御構造を抜けます。
しかしloopはlabel {loop ... end} {...}のように変換されます。もしloopに対してbrすればlabelの継続であるloop ... endにジャンプし、これが評価されてまたlabelに変換されlabel {loop ... end} {...}となり…を繰り返す事でループが実現しています。これがloopに対するbrがcontinueとして働く理由です。またbrしなければそのままlabelを抜けることになるのでこれによってloopに対してbrしなければ一回しか処理は実行されません。

例

先ほど例として出した以下のループの実行を例にします。(label命令は仕様書の中だけに出てくるものでwatには存在しないのでコンパイルはできません)

(local $n i32)
(loop $loop
  (call $log (get_local $n))
  (set_local $n (i32.add (get_local $n) (i32.const 1)))
  (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
)

;; output: 0 1 2

loopを評価するとlabelに変換します。

;; n: 0

(loop $loop ;; ←評価
  (call $log (get_local $n))
  (set_local $n (i32.add (get_local $n) (i32.const 1)))
  (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
)

(label $loop
  {loop $loop
    (call $log (get_local $n))
    (set_local $n (i32.add (get_local $n) (i32.const 1)))
    (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
  }
  {
    (call $log (get_local $n))
    (set_local $n (i32.add (get_local $n) (i32.const 1)))
    (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
  }
)

labelでは継続ではなく本体を順に評価します。
評価3を実行するとbr_ifの引数は1なのでbrを実行します。
この時継続にジャンプし、継続を評価します。ここでの継続はloopです。
これによってloopが評価されlabelになり…を繰り返します。

;; n: 0→1

(label $loop
  {loop $loop
    (call $log (get_local $n))
    (set_local $n (i32.add (get_local $n) (i32.const 1)))
    (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
  }
  {
    (call $log (get_local $n)) ;; ←評価1
    (set_local $n (i32.add (get_local $n) (i32.const 1))) ;; ←評価2
    (br_if $loop (i32.ne (get_local $n) (i32.const 3))) ;; ←評価3
  }
)

;; n: 1

(loop $loop
    (call $log (get_local $n))
    (set_local $n (i32.add (get_local $n) (i32.const 1)))
    (br_if $loop (i32.ne (get_local $n) (i32.const 3)))
)

nが3の時br_ifの引数は0なので何もしません。つまり継続には飛ばずそのままlabelの本体の処理が終わります。つまりループが終了します。

参考

WebAssembly Specification