[wasm] The types in a recgroup may not be mutually recursive

[Air111]

I try compiling Dart to Wasm according to the tutorial on the website WebAssembly (Wasm) compilation.

After disassembling the generated main.wasm file using wasm-dis, I found that the types in several recgroups are not mutually recursive. They all seem to be able to be split into two separate types, which provides the possibility for deduplicating the types.

 (rec
  (type $173 (struct))
  (type $174 (func (param i64 i64 (ref null $3)) (result (ref $37))))
 )
 (rec
  (type $175 (struct))
  (type $176 (func (param (ref $1) (ref $11))))
 )
 (rec
  (type $177 (struct))
  (type $178 (func (param (ref $2)) (result i32)))
 )
 (rec
  (type $179 (struct))
  (type $180 (func (result (ref $2))))
 )

$ dart --version
Dart SDK version: 3.7.2 (stable) (Tue Mar 11 04:27:50 2025 -0700) on "linux_x64"

To my understanding, only when two types are mutually recursive is it necessary to place them in the same recgroup.

(rec
  (type $t1 (struct (field i32 (ref $t2))))
  (type $t2 (struct (field i64 (ref $t1))))
)

Otherwise, they can be split into two separate recursive groups containing just one type.

(type $173 (struct))
(type $174 (func (param i64 i64 (ref null $3)) (result (ref $37))))
(type $176 (func (param (ref $1) (ref $11))))
(type $178 (func (param (ref $2)) (result i32)))
(type $180 (func (result (ref $2))))

Previously I obtained dozens of files named "main.dart.wasm" from the web, and after decompiling several of them, I found that this issue existed in all of those decompiled files.

I'm wondering if this was done intentionally. If so, what was the reason behind it? Or is it something that hasn't been fully optimized yet?

[kevmoo]

@Air111 – who are you? What a great bug!

[sigmundch]

Indeed, this is an intentional choice. The main reason is that Dart has a nominal type system, while wasm has a structural type system. The dart2wasm compiler tries to leverage wasm types to enforce some of the Dart semantics, but to do so, it needs to make Dart types distinguishable once lowered to wasm types. We leverage rec groups to achieve that.

For example, consider when classes A and B have the same superclass and the exact same field types. Internally, both A and B have the same structural shape and are lowered to exactly the same wasm structural type, putting them in singleton rec groups would cause them to get consolidated and make them indistinguishable at the wasm level.

The compiler leverages rec groups in different ways to make types distinguishable. A while back, it used to emit all types in a single rec group. If two identical structural types are in the same rec group, we can distinguish them by their index in the group. As we started adding support for deferred-loading to the compiler, we changed the layout to emit small rec groups instead. We had a secondary goal that types emitted for the main module and types emitted for a deferred module needed to match. At first, we used to combine equivalent types under a single a rec group, but later we explored other techniques, like adding a sentinel type to a rec group that makes it different from other rec groups. The latter made it easier to match types between modules, so I believe it's what we now use by default.

@mkustermann and @biggs0125 - I wonder if our current sentinel could be omitted from the first rec-group that introduces a structurally equivalent type? That would potentially save the overhead when we haven't encountered a second type that needs to be distinguished.

[biggs0125]

dart2wasm itself already does omit the extra "brand" type for the first rec-group is encounters in each equivalence class. If you compile the same program with -O0 you should see that some types named brand{N} (for some integer N) are added to only some of the rec groups but most don't have a brand type. Here's an example rec group in a program I compiled locally with -O0.

(rec
  (type $type844 (func (param $this (ref $_HashFieldBase))))
)

The empty struct seen in the provided snippet is actually getting added by binaryen, the wasm optimizer we use. It uses the same technique of adding brand types to distinguish otherwise identical types. It seems like that tool may be including brand types in some unnecessary cases.

[Air111]

Thank you very much for your replies. To be honest, I don't know much about the Dart compiler itself. I understand that for the sake of convenience and to preserve some information (such as debug info), it is necessary to distinguish these types.

For the release version, I think the consolidating of these types seems to have no impact during runtime. For the main module and the deferred module, it may be possible to combine equivalent types each of them (as well as the glue code).

In addition, in a wasm file obtained from the web, which is likely compiled from Dart, the following situation was also found.

(rec
  (type $11944 (array (mut i8)))
  (type $11945 (struct (field (ref $399))))
)
(rec
  (type $13194 (struct (field (ref $399))))
  (type $13195 (array (mut i8)))
)

Finally, even if this is a possible optimization, the complexity seems not to match the benefits. Thank you again for your help.