Preservation of initialization state of locals

[askeksa-google]

I am currently working on making dart2wasm output code with non-nullable locals adhering to the "initialized until end of block" rule. Inspired by https://github.com/WebAssembly/function-references/issues/44#issuecomment-944306921 I initialize all non-nullable locals to a dummy value if they are not already initialized.

This works in V8 with the --experimental-wasm-nn-locals flag (which activates this validation rule). However, if I run the code through Binaryen (even with no optimizations), specifying the --enable-gc-nn-locals flag, the resulting module fails validation under this rule.

One cause of the failure (there may be several) is that Binaryen inserts extra blocks and locals in some situations, such as when the code does something statement-like while the operand stack is not empty.

For example, a function call with an object creation:

foo(new Bar());

is translated by dart2wasm into:

(global.get $global$7)
(struct.new_default_with_rtt $type$3)
(local.tee $0)
(local.get $0)
(i32.const 7)
(struct.set $type$3 0)
(call $4)
(local.get $0)
(call $3)

which Binaryen turns into:

  (call $4
   (block (result (ref $type$3))
    (local.set $1
     (local.tee $0
      (struct.new_default_with_rtt $type$3
       (global.get $global$7)
      )
     )
    )
    (struct.set $type$3 0
     (local.get $0)
     (i32.const 7)
    )
    (local.get $1)
   )
  )
  (call $3
   (local.get $0)
  )

where the (local.tee $0) is now inside a block which ends before the final (local.get $0).

Is it feasible for Binaryen to generally preserve the initialization property such that if the input code validates under the "initialized until end of block" rule, then so does the output?

For the particular case of these extra blocks, I presume they could be eliminated in the output whenever there are no branches to them?

[kripken]

I believe V8 has or will get a flag to allow "unsafe" experimentation here, that should unblock you - @manoskouk?

Otherwise, this would not be simple to do in binaryen in general: it's a constraint on the structure that extends into many passes, in theory. Probably if we need to we'd end up doing a fixup phase at the end, though that would have downsides too. See some discussion of a related topic here: https://github.com/WebAssembly/binaryen/issues/4237#issuecomment-942600098

[askeksa-google]

Yes, with the --experimental-wasm-unsafe-nn-locals V8 option, optimized output from Binaryen with --enable-gc-nn-locals works fine. I was investigating the feasibility of generating code for the --experimental-wasm-nn-locals validation mode.

So it looks like this feasibility comes down to the ability of Binaryen to transform the code into an appropriate form on output. It seems there are (at least) two approaches one could take here:

1. Create explicit joins via block outputs. In general, this will require multiple block outputs.
2. Initialize every non-nullable local to a dummy value in a place that dominates all uses (if such an initialization does not already exist).

Generating such initializers in the initial code generation (as I have done in dart2wasm) is evidently not useful as a means to make the final code validate according to the "initialized until end of block" rule when subsequent code transformations are present. Good to know.

I guess it could be beneficial to remove those redundant blocks in any case. Doing that before the final local initialization transformation will probably cut down the number of such transformations that are needed considerably.

[kripken]

Things that worry me here are stuff like this:

if (..) {
  return;
} else {
  x = 1;
}
foo(x);

That assignment dominates the use, but we don't actually need a join here - adding one would be wasteful.

Probably this pattern could just move the assignment out of the if-else, which here would be obviously better for other reasons. But I'm not sure that's the case in general.

[askeksa-google]

Dominance is not actually the right criterion for validity here. Rather, the second approach should read:

2. Initialize every non-nullable local to a dummy value in a block that encloses all uses and defs, before all uses and defs (if such an initialization does not already exist).

Optimally, this should be in the innermost such block, as late as possible (right before the first sub-block containing a use or def), but this is not required for validity.

If we generally optimize away redundant blocks (also in cases like your example), I think the number of places where we need to insert such a dummy initialization will be very small. As mentioned in the other issue, adding such initializers in the unoptimized code for barista3 increased the module size by just 0.06%.

For the actual dummy value, Binaryen could look to see if there is already a suitable value (immutable global with compatible type), and synthesize one otherwise. If the input module validates, and only sound optimizations are applied, then the value should not be able to reach any uses.

[kripken]

For the actual dummy value, Binaryen could look to see if there is already a suitable value (immutable global with compatible type), and synthesize one otherwise.

Do we have a guarantee that is possible in general? At minimum it may be very difficult with recursive data structures.

[askeksa-google]

If a type is recursive through only non-nullable references, it is indeed impossible to ever create a value of that type.

AFAIK it's currently permitted in WasmGC to define such a type and declare a local with that type. Maybe it shouldn't be. Seems pretty useless. I certainly wouldn't deride Binaryen for refusing to work with such types.

[askeksa-google]

For inspiration, the code for generating dummy values in dart2wasm can be seen here.

[kripken]

I see, thanks @askeksa-google Yes, it seems like this could work. Would be interesting to measure the code size overhead.

Is this urgent to do on the binaryen side atm? My sense is there is a lot of other discussion going on around non-nullable locals anyhow, and also that non-nullable locals are not our largest problem atm (since j2wasm is still slower than JS). For those reasons I'm not inclined to work on this myself atm, but maybe that's wrong?

[askeksa-google]

I think adding this post-transformation to Binaryen is an important step in verifying the feasibility of the "initialized until end of block" validation model. So it will be hard to close the non-nullable locals discussion without it.

On the other hand, I do agree that the non-nullable locals question is not particularly urgent.