Error on implicit upcast

If I give Binaryen this code, containing an implicit upcast from a (structural) subtype:

(module
    (type $A (struct (field (mut i32))))
    (type $B (struct (field (mut i32)) (field (mut i64))))
    (func $f (param $0 (ref $B))
        (struct.set $A 0 (local.get $0) (i32.const 5))
    )
)

I get this error message:

[parse exception: bad heap type: expected (struct (field (mut i32))) but found (ref null (struct (field (mut i32) (mut i64)))) (at 5:8)]
Fatal: error parsing wasm

It looks like the structural subtype check is not done properly for the validation here.

Even if I pass --no-validation, I still get the error.

Interesting, I had not understood the MVP docs to allow this, but maybe I've misunderstood... it wouldn't be the first time 😄

I see this:

struct.set <typeidx> <fieldidx> writes field i of a structure
  struct.set $t i : [(ref null $t) ti] -> []
    iff $t = struct (mut1 t1)^i (var ti) (mut2 t2)*
    and t = unpacked(ti)
  traps on null

To me it looks like $t must be identical on both sides of the second line there, and not a subtype?

@kripken

@kripken, you're correct about the type being the same throughout the typing rule for struct.set, so this struct.set expects a value of type (ref null $A). But the type of the local.get is (ref $B), which is a subtype of (ref null $A), so it should be allowed.

@askeksa-google, would it be a problem if Binaryen turned that program into this? Right now Binaryen IR does not keep the original heap type around, so it is not able to round-trip the types here perfectly. I don't think that should matter, but I might be missing something.

(module
 (type $B (struct (field (mut i32)) (field (mut i64))))
 (func $f (param $0 (ref null $B))
  (struct.set $B 0
   (local.get $0)
   (i32.const 5)
  )
 )
)

@kripken

Although, no, my interpretation above doesn't seem sound. If B <: A and C <: A, but nether B <: C nor C <: B, then implicitly upcasting (struct (ref B)) to (struct (ref A)) then doing a struct.set to write a (ref C) would type check under my interpretation, but would end up writing a (ref C) over a (ref B). @kripken, I think you're right after all.

@kripken

When the static heap type of the struct reference in a struct.get or struct.set is a subtype of the heap type specified in the instruction, it should indeed not be a problem to change the heap type of the instruction to the subtype. It will still typecheck according to the static typing rules of Wasm, and the field read/written will still be the same.

Although, no, my interpretation above doesn't seem sound. If B <: A and C <: A, but nether B <: C nor C <: B, then implicitly upcasting (struct (ref B)) to (struct (ref A)) then doing a struct.set to write a (ref C) would type check under my interpretation, but would end up writing a (ref C) over a (ref B). @kripken, I think you're right after all.

This would not typecheck, as it involves a downcast from A to C.

Interestingly, I can't find the place in the GC proposal (or any of the proposals that it depends on) where it explicitly states that implicit upcasts are always allowed, i.e. that instruction inputs always accept any subtype of their specified input type, and the same for block inputs and outputs.

It is sort of implied from the way other things are formulated (it's the whole point of the static subtyping relation, after all), and there are several references to the fact, for instance:

Note: The br_on_* instructions allow an operand of unrelated reference type, even though this cannot possibly succeed. That's because subtyping allows to forget that information, so by the subtype substitutibility property, it would be accepted in any case. The given typing rules merely allow this type to also propagate to the result, which avoids the need to compute a least upper bound between the operand type and the target type in the typing algorithm.

As a write target, It's sound for the struct operand to struct.set to be a supertype of of the expected type and as a written value, it's sound for the value operand to be a subtype of the expected type. I guess the contravariance of the struct argument disproves the idea that all stack operands are allowed to be subtypes at all times. I'm not sure how to understand when they are allowed, then.

Yes, when doing (struct.set $x (..target..) (..value..)) then I believe it is ok if the value is a subtype of the expected value, following the usual rules for finding a subtype on the stack, but on the other hand it is not ok if the target is a subtype of $x. It has to be $x or a supertype, that is, adding more fields or adding more possible values to existing ones. I assumed that is why the spec wrote struct.set $t i : [(ref null $t) ti] -> [] (with the same $t on both sides), to disallow target subtyping.

But it also disallows supertyping which could have been written as

struct.set $t i : [(ref null $t') ti] -> []
  $t <: $t'

I am not sure why that is not allowed.

It also, I notice, has the exact same type for the value as well, which would mean that a "strict" reading like mine would rule out value subtyping, which seems odd... so maybe I am misreading it.

I forgot that mutable struct fields are invariant, so depth subtyping isn't relevant for struct.set. Width subtyping works fine, so both target and value can safely accept subtypes of their expected values.

[Wasm GC] Allow subtyping in arguments to struct.get etc. Fixes #3636

[Wasm GC] Allow subtyping in arguments to struct.get etc. Fixes #3636 (…

Works now, thanks!

I ran into two semi-related follow-up issues:

Binaryen and V8 do not agree on the output type of local.tee. I have opened a design issue for that: Output type of local.tee? gc#201
Binaryen inlining produced a redundant ref.cast (explicit upcast) which V8 complained about. It's a V8 issue, but it also points to an optimization opportunity for Binaryen (eliminating redundant casts).

@askeksa-google

@askeksa-google Interesting, thanks for the info!

Do you have an example of the second issue? I'm not quite sure what optimization you mean, and can't think of where we add new ref.casts.

It's not a newly added ref.cast; it's an existing one which becomes redundant due to the removal of the implicit upcast to the parameter type.

(module
    (type $A (struct (field (mut i32))))
    (type $B (struct (field (mut i32)) (field (mut i64))))
    (type $C (struct (field (mut i32)) (field (mut i64)) (field (mut i64))))
    (global $Artt (rtt 0 $A) (rtt.canon $A))
    (global $Brtt (rtt 1 $B) (rtt.sub $B (global.get $Artt)))
    (global $Crtt (rtt 2 $C) (rtt.sub $C (global.get $Brtt)))
    (export "f" (func $f))
    (func $f (param $0 (ref $C)) (result (ref $B))
        (call $g (local.get $0))
    )
    (func $g (param $0 (ref $A)) (result (ref $B))
        (ref.cast (local.get $0) (global.get $Brtt))
    )
)

is optimized by Binaryen to

(module
 (type $B (struct (field (mut i32)) (field (mut i64))))
 (type $ref?|$C|_=>_ref?|$B| (func (param (ref null $C)) (result (ref null $B))))
 (type $A (struct (field (mut i32))))
 (type $C (struct (field (mut i32)) (field (mut i64)) (field (mut i64))))
 (global $Artt (rtt 0 $A) (rtt.canon $A))
 (global $Brtt (rtt 1 $B) (rtt.sub $B
  (global.get $Artt)
 ))
 (export "f" (func $f))
 (func $f (; has Stack IR ;) (param $0 (ref null $C)) (result (ref null $B))
  (ref.cast
   (local.get $0)
   (global.get $Brtt)
  )
 )
)

where the cast is statically redundant.

The cast could still fail if the passed-in object happens to have a runtime type which is not a sub-rtt of $Brtt. So removing it is only valid under the assumption that the cast succeeds (the --ignore-implicit-traps option, I guess, assuming that also covers casts).

@askeksa-google

I see, thanks @askeksa-google !

Yes, this would require --ignore-implicit-traps to work because of the possible trap. But then it should be possible.

When things are stable I expect I'll start to work on optimizations for things like this. I'm marking down a note for myself to return to this then.

@askeksa-google

@askeksa-google Ok, I've been getting to general optimization work in binaryen now, and am reading this again. I'm not sure what can be optimized here, though, so maybe I'm missing something.

The input to the ref.cast is of type $C, but we don't know what RTT it has. $B is a supertype of $C, but without the RTT values, perhaps the RTT of $0 is (rtt.canon $C) which is not a sub-RTT of $Brtt?

As I understand the description of the --ignore-implicit-traps flag, it enables optimizations that are only valid under the assumption that the program does not trap (where I assume that by "implicit" you mean everything except unreachable instructions). Thus, with this flag, it is permissible to remove operations which might trap, but which have no other observable effect and are not necessary for static correctness. The ref.cast in this case is such an operation.

I consider such aggressive optimizations quite useful, since in many cases, a compiler will generate code that indeed never traps (unless there is a bug in the compiler).

@askeksa-google

Thanks @askeksa-google ! Sorry, I missed how --ignore-implict-casts was the key thing here. Yes, that makes sense. I will do this after #3725 I think. (Btw, if you have time let me know if you have thoughts on that PR.)

[Wasm GC] Optimize RefCast + ignore-implicit-traps (#3748)

[Wasm GC] Optimize RefCast + ignore-implicit-traps (WebAssembly#3748)

Navigation Menu

Repository navigation

Error on implicit upcast #3636

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Error on implicit upcast #3636

Description

Activity

kripken commented on Mar 2, 2021

tlively commented on Mar 2, 2021

tlively commented on Mar 2, 2021

askeksa-google commented on Mar 2, 2021

askeksa-google commented on Mar 2, 2021

tlively commented on Mar 2, 2021

kripken commented on Mar 2, 2021

tlively commented on Mar 2, 2021

askeksa-google commented on Mar 3, 2021

kripken commented on Mar 3, 2021

askeksa-google commented on Mar 4, 2021

kripken commented on Mar 4, 2021

kripken commented on Mar 24, 2021

askeksa-google commented on Mar 29, 2021

kripken commented on Mar 29, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions