Skip to content

Make dart compile wasm -O4 not omit explicit type checks #55516

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
mkustermann opened this issue Apr 19, 2024 · 5 comments
Closed

Make dart compile wasm -O4 not omit explicit type checks #55516

mkustermann opened this issue Apr 19, 2024 · 5 comments
Assignees
Labels
area-dart2wasm Issues for the dart2wasm compiler.

Comments

@mkustermann
Copy link
Member

Now that we have optimized is / as type checks using short & fast cid-range checks, we may consider no longer omitting explicit as checks.

This will naturally result in worse size & performance, so we should investigate the differences and see what can be done about it.

One area where this will show up is in the interator implementations as they have as checks in them, but they can be optimized to null checks.

@mkustermann mkustermann added the area-dart2wasm Issues for the dart2wasm compiler. label Apr 19, 2024
@mnordine
Copy link
Contributor

If your investigation yields a decision to keep them for -O4, will there still be a flag to omit them?

@mkustermann
Copy link
Member Author

If your investigation yields a decision to keep them for -O4, will there still be a flag to omit them?

Right now it's not explicitly exposed by flutter build web or dart compile wasm, but one could use it via dart compile wasm --extra-compiler-option=--omit-explicit-checks.

(Notice that dart2js -O4 drops implicit checks but keeps explicit checks. So this issue is tracking us to align with dart2js)

@sigmundch
Copy link
Member

Cool to see this @mkustermann!

About the iterator example you mention. Are you referring to covariant checks? Or actual explicit as expressions? I ask also for the purpose of aligning with dart2js: dart2js -O3 not only omits implicit downcasts from dynamic, but also implicit parameter checks (which can come from a dynamic invocation or an explicit covariance check)

copybara-service bot pushed a commit that referenced this issue May 1, 2024
Currently `-O4` drops explicit as-checks. Before changing this, we have
to do more optimizations on type checks. As a start, we call out to the
VM's lowering of as-checks in the modular transformer.

Issue #55516

Change-Id: I71f35a95ab41cc7a30f7dea088d9d41ac5243f59
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/365141
Commit-Queue: Martin Kustermann <[email protected]>
Reviewed-by: Slava Egorov <[email protected]>
@rakudrama
Copy link
Member

@sigmundch The optimization is for the explicit as used in many Iterator.current implementations (example)

  E? _current;
  ...
  E get current => _current as E;

The transform is to change _current as E to _current == null ? _current as E : _current, since the only value that needs checking when casting from E? to E is null.

dart2js does this in the SSA builder.

@mkustermann mkustermann self-assigned this Jun 3, 2024
copybara-service bot pushed a commit that referenced this issue Jun 3, 2024
…thods

There's no need to make an instance of _TypeUniverse and pass around a
`this` reference to method calls as there's no state.

Issue #55516

Change-Id: I522a3ef677d0301c0a5dcd1d83499a99293618a3
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369242
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 4, 2024
If we do a type check against a class that isn't generic, then we can
safely ignore all the type arguments - because irrespective of their
values - either the class we test against is in the transitive super
hierarchy of an object's class or not.

Issue #55516

Change-Id: Ibf6950492d4c33d7eaf55d6ce8389ebfac201b00
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369461
Commit-Queue: Martin Kustermann <[email protected]>
Reviewed-by: Srujan Gaddam <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 4, 2024
…f not needed

When checking against a destination type that isn't generic, we can
safely ignore the type arguments of the concrete class (as we only care
whether the object's class has the destination type in its transitive
super type hierarchy).

=> Avoid calling `Object._getTypeArguments(o)` if dst type is non-generic.

Issue #55516

Change-Id: Ie9c6a3ab2d99acc07546f9d28ca71ac740c4aad5
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369462
Reviewed-by: Srujan Gaddam <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 4, 2024
Instead of hand-written assembly to instantiate various different kinds
of type constants, we simply lower type constants to `InstanceConstant`s
for which we already have code generation.

This lowering also means that types that are considered to be different
on the kernel `DartType` level may end up being lowered to the same
`InstanceConstant`.
=> We canonicalize them now where we didn't before
=> We reduce code size.

An example where this happens the `TypeParameterType`: On the kernel
level two such types are different if they refer to a different class.
But in the RTT data structure we do not care about what class they refer
to, only the index is important (as RTT knows which class it belongs
to).

Issue #55516

Change-Id: I7ebd68b2c48c752f6d074a7981da75fbbfbcf00f
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369480
Reviewed-by: Srujan Gaddam <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 5, 2024
…hecking

Issue #55516

Change-Id: I2cddd95211f3d831965a1bba45774ad8d72847a9
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369621
Reviewed-by: Srujan Gaddam <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 8, 2024
This CL optimizes the RTT data structures by

* Having a canonical table for substitution arrays
* Stores the (canonical) substitution index to use right next
  to the super class id, thereby
* Removing an indirection when looking up substitutions

See more information in `sdk/lib/_internal/wasm/lib/type.dart`

This reduces
  * `Hello.Compile.Size.wasm.opt` by ~ 4%
  * `FluteComplex.Compile.Size.wasm.opt` by ~0.5%

Issue #55516

Change-Id: If0a50780a9a604886bd67a08a2f345103f0bcb32
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/369641
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 10, 2024
We make the compiler emit a special index (namely 0) into the
canonical type argument substitution table iff no substitution has to be
performed.

This is very common:

    ```
    class List<T> implements Iterable<T> {}
    ```

=> The translation of the type arguments from `List` to those of
   `Iterable` is a NOP and can therefore be skipped.

Issue #55516

Change-Id: I16ad8d7196656dddeba15801e80c2e23ae0af51b
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/370242
Commit-Queue: Martin Kustermann <[email protected]>
Reviewed-by: Ömer Ağacan <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 10, 2024
Currently if we have a `<obj> is/as Iterable<T>` check we will

  * allocate a `WasmArray<_Type>` array and put value for `T` in it
  * allocate a `_InterfaceType` object with the array as type arguments
  * call to RTT which is looping over the type arguments array

With this CL we recognize in the compiler if we generate tests against
interface types and specialize the most common cases (0, 1 or 2 type
arguments). This in return will make us

  * call to 0/1/2 specialized RTT isInterfaceSubtype implementation
    which will use unrolled loops to do the checking.

=> We avoid allocation of `_InterfaceType` always
=> We avoid allocation of `WasmArray<_Type>` for length=0/1/2
=> We have faster checking due to unrolled loops.

(It is very unlikely binaryen can achieve the same, as it would
need to do very aggressive inlining & loop unrolling to get to the
same result. If we'd force it to inline then every is/as check
would be very large).

Issue #55516

Change-Id: Ia99548d514683f678178ea30d07aeb742ae914ca
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/370260
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 12, 2024
If the transitive supers graph contains many classes we use a binary
search instead of a linear search.

Issue #55516

Change-Id: I1018082e8d27090293b67a2239abfaf279270b9e
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/370860
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jun 13, 2024
…s not InterfaceType

Right now the optimized is/as-checkers are only used when the operand
type is an [InterfaceType]. That means they don't get used for e.g.

   dynamic obj;
   T obj2;
   obj is String
   obj2 is List<dynamic>;

But we can use the is/as-checkers on any operand type as long as the
type we test against is an [InterfaceType] without arguments or where
the type arguments are equivalent to defaults-to-bounds (i.e. require
no checking).

Issue #55516

Change-Id: I1adff52b3d880c37c344edb0c42ffd454d7b1164
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/371124
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jul 8, 2024
…iated types

The specialized is/as checker functions are currently only used
for cases where the type to check against doesn't require checking
argument types.

This CL will extend that for cases where we do have to check
argument types, but we know that there's no need to substitute
type arguments. This saves the RTT system from searching for
the type argument substitution value.

Cases where this applies is for example
```
class Base<T> {}
class Sub<T> extends Base<T> {}
class Sub2<T> extends Base<T> {}
class Sub3<T> extends Base<T> {}

final l = <Base<Object>>[Sub<int>(), Sub2<String>(), Sub3<double>()];
foo<T>() {
  final Base<Object> b = l[1];
  if (b is Base<T>) { ... }
  if (b is Base<String>) { ... }
}
```

Here we know that all classes that directly or indirectly implement
`Base<T>` just pass their type parameter up the hierarchy.
=> There's no need to translate from type parameter array of subclass
to that of the super class.

We'll generate optimized is/as helpers for this case now, e.g.
```
func foo {
      ...
      local.get $var0
      global.get $global40
      call $<obj> is Base<T0>
      ...
}

func $<obj> is Base<T0> {
      // Check whether obj is in class-id range of Base subtypes
      i32.const 0
      local.get $var0
      struct.get $Base $field0
      i32.const 107
      i32.sub
      i32.const 3
      i32.ge_u
      br_if $label0
      drop
      // Call Object._getTypeArguments()
      i32.const 0
      local.get $var0
      local.get $var0
      struct.get $Base $field0
      i32.const 338
      i32.add
      call_indirect (param (ref $#Top)) (result (ref $Array<_Type>))
      // Check whether first type argument is subtype of T0
      i32.const 0
      array.get $Array<_Type>
      ref.null none
      local.get $var1
      ref.null none
      call $_TypeUniverse.isSubtype
      i32.const 1
      i32.ne
      br_if $label0
      drop
      i32.const 1
}
```

It has overall negligible code size impact (~ 0.1% increase)

Issue #55516

Change-Id: Ic151269ad1b4a1456782b387beb4d646786ac493
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/374681
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jul 8, 2024
…ationships

The main RTT information we need is whether a subclass is that of
another and if so how to translate type arguments from the subclass to
the super class.

This CL switches the data structure we use to represent this
relationship to a row-displacement table (simlar to how we do method
dispatch).

=> With two array lookups we can determine if a class is a superclass of
another
=> With one more array lookup we obtain the type argument substitution
array.

The packing of the row displacement table is 80-90%.

Issue #55516

Change-Id: I1a8d1205402c2c5e49c44b2f60c32e79a0e429ce
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/374720
Commit-Queue: Martin Kustermann <[email protected]>
Reviewed-by: Ömer Ağacan <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jul 9, 2024
…lass relationships"

This reverts commit 79dff00.

Reason for revert: flutter/flutter#151473
A bisect found https://dart-review.googlesource.com/c/sdk/+/374320 to be the CL that caused the failure and this CL uses maxClassId which was defined in that CL and reverting that CL causes build failures from the changes in this CL.

Original change's description:
> [dart2wasm] Use row displacement table for representing RTT class relationships
>
> The main RTT information we need is whether a subclass is that of
> another and if so how to translate type arguments from the subclass to
> the super class.
>
> This CL switches the data structure we use to represent this
> relationship to a row-displacement table (simlar to how we do method
> dispatch).
>
> => With two array lookups we can determine if a class is a superclass of
> another
> => With one more array lookup we obtain the type argument substitution
> array.
>
> The packing of the row displacement table is 80-90%.
>
> Issue #55516
>
> Change-Id: I1a8d1205402c2c5e49c44b2f60c32e79a0e429ce
> Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/374720
> Commit-Queue: Martin Kustermann <[email protected]>
> Reviewed-by: Ömer Ağacan <[email protected]>

Change-Id: I2bfb72ae68dc2e671edf79cd5161541d849b8fcf
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/375042
Bot-Commit: Rubber Stamper <[email protected]>
Reviewed-by: Nate Biggs <[email protected]>
Commit-Queue: Siva Annamalai <[email protected]>
copybara-service bot pushed a commit that referenced this issue Jul 11, 2024
…lass relationships"

No changes from original CL.

Original CL description:

  The main RTT information we need is whether a subclass is that of
  another and if so how to translate type arguments from the subclass to
  the super class.

  This CL switches the data structure we use to represent this
  relationship to a row-displacement table (simlar to how we do method
  dispatch).

  => With two array lookups we can determine if a class is a superclass of
  another
  => With one more array lookup we obtain the type argument substitution
  array.

  The packing of the row displacement table is 80-90%.

  Issue #55516

  Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/374720
Change-Id: I7ef7f74d999fd211f075a47dffaa7c9c3d5f2a30
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/375281
Commit-Queue: Martin Kustermann <[email protected]>
Reviewed-by: Slava Egorov <[email protected]>
copybara-service bot pushed a commit that referenced this issue Aug 22, 2024
…n backend.

Up to Patchset 4 reverts commit 36fb02d

Remaining Patchsets implement specialized support in is/as check
implementation to handle cases where only a null check is required. The
most common case in iterators:

  class <...>Iterator<T> {
    T? _current;

    T get current => _current as T;
  }

This ensures we're never emitting the general subtype checking code as
this only requres checking whether the object is non-`null` or whether
the destination type is declared nullable.

The asymmetry between `is` and `as` checks comes due to the fact that
the `as` checks have to (for the slow case) materialize a type object
for a nice error message.


Issue #55516

Change-Id: Ie4a845816ec4eda37a5a2e78cac0aeda0e411abd
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/381482
Reviewed-by: Ömer Ağacan <[email protected]>
Commit-Queue: Martin Kustermann <[email protected]>
@mkustermann
Copy link
Member Author

After many optimizations to the RTT data structures and is / as implementation this has been completed.

Dart2wasm should now always perform user-written as checks, even in -O4 mode.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-dart2wasm Issues for the dart2wasm compiler.
Projects
None yet
Development

No branches or pull requests

4 participants