Make br_if with a value's type match the spec

[kripken]

Previously br_if with a value had the same type as the value, but the spec says it should be the type of the block it targets, which might be less refined. Context:

https://github.com/WebAssembly/gc/issues/516#issuecomment-1969753085

This is unfortunate for Binaryen as the value is right there in our IR, while looking up the block's type is more effort. I measure a 1.5% slowdown in building a J2Wasm testcase with this. There do not seem to be downsides to the output, but that is just because the value output of br_if is practically never used outside of fuzz testcases and exploits.

Summary of the necessary changes for this:

• Adjust validator to allow the spec form only.
• Add optional Type param to the C API to create a Break.
• ReFinalize may do another pass if it ends up updating br_ifs - we can no longer just do a simple forward pass here, as block changes go "backwards" to br_ifs. In practice I think that should be rare (on J2Wasm I see only a 3 times where an extra iteration is needed when running -O3).
• Update br_if types in the few passes that modify br_if values or add values or conditions to brs, including Heap2Local, RemoveUnusedBrs, SimplifyLocals.
• RemoveUnusedBrs also must be careful not to un-refine block types. It used to do that, and they generally ended up refined later anyhow, but now this would be a danger (they would unrefine the br_if, which might break).
• The parsers must provide br_if types during construction.
• Add Type.containsRef() helper.

[tlively]

I also just realized that this refinalization algorithm does not find the smallest fixed point of the types (i.e. the most refined possible block and br_if types).

Consider this program:

(type $A (sub (struct)))
(type $B (sub $A (struct)))

(func (result (ref $A))
 (block $a (result (ref $A))
  (br_if $a
   (struct.new $B)
   (i32.const 0)
  )
 ) 
)

If I'm not mistaken, ReFinalize will not be able to improve the type of the block because it calculates the type of the block as the LUB of the sent values of the br_if and the fallthrough value, which is (ref $A). It will also never improve the type of the br_if.

The fix would be to do the first ReFinalization walk with the old behavior of setting the br_if type equal to its value's type, then doing subsequent iterations with the new behavior to relax the types up to the smallest fixed point.

[kripken]

The fix would be to do the first ReFinalization walk with the old behavior of setting the br_if type equal to its value's type, then doing subsequent iterations with the new behavior to relax the types up to the smallest fixed point.

Good point about this not necessarily reaching the optimal point. And, interesting idea to solve it.

Thinking about that, perhaps another option is to first walk with the old behavior, and then to add casts as necessary afterwards, without any further iterations? That is, any br_if that we must force to be a less-precise type than it "wants" to be would be cast so that it does flow out the type it "wants." Adding casts is not ideal, but that situation is quite rare.

[tlively]

Oh yeah, adding casts seems fine, too. It gets back all of the type precision at the cost of having to execute the casts at runtime. How much do you think that would simplify this PR beyond ReFinalize itself?

Since following the spec rules has more downsides than I had anticipated, I also started pushing more to get them changed: https://github.com/WebAssembly/gc/issues/516#issuecomment-1986700340.

[kripken]

How much do you think that would simplify this PR beyond ReFinalize itself?

Hmm, good question. I think adding the casts would remove a little bit of complexity (while not adding much extra tracking logic). But that would still leave 99% of the complexity in this PR. Good idea to discuss spec options.

[tlively]

If we are able to change the spec, then we'll have to fix our handling of local.tee instead. local.tee would no longer be exactly equivalent to a local.set + local.get. IIRC, you did some experiments with that a while ago and decided that wouldn't be a big problem, right?

[kripken]

Yes, updating local.tee would require some work but we thought it was not a big burden: https://github.com/WebAssembly/binaryen/issues/3704 (it's possible changes since then make things worse but I doubt it).

Reading that and https://github.com/WebAssembly/gc/issues/201 again, it's hard not to see how we seem to keep returning to this topic again and again... :smile: :repeat:

[kripken]

Closing in favor of #6510