Optimize partial instantiation of generic functions

[mkustermann]

Right now the partial instantiation of generic functions always calls to runtime for potentially checking whether bounds are qualified.

class A { 
  T foo<T>(T a) => a;
}

void main() {
  final a = A();
  while (true) {
    int Function(int) y = a.foo;
  }
}

This will perform calls to runtime on each loop iteration. Though there is no bound on T and it is therefore not needed to do those checks.

There's a TODO in the code:

Fragment StreamingFlowGraphBuilder::BuildPartialTearoffInstantiation() {
  // Create a copy of the closure.
  ...

  // Check the bounds.
  //
  // TODO(sjindel): We should be able to skip this check in many cases, e.g.
  // when the closure is coming from a tearoff of a top-level method or from a
  // local closure.
  instructions += LoadLocal(original_closure);
  instructions += LoadLocal(type_args_vec);
  const Library& dart_internal = Library::Handle(Z, Library::InternalLibrary());
  const Function& bounds_check_function = Function::ZoneHandle(
      Z, dart_internal.LookupFunctionAllowPrivate(
             Symbols::BoundsCheckForPartialInstantiation()));
  ASSERT(!bounds_check_function.IsNull());
  instructions += StaticCall(TokenPosition::kNoSource, bounds_check_function, 2,
                             ICData::kStatic);
  instructions += Drop();

  // Store instantiated type arguments
  ...
  // Copy over the instantiator type arguments.
  ...
  // Copy over the function type arguments.
  ...

  return instructions;
}

We should avoid that call if we have a static guarantee that bounds are satisfied.

The main usage where the bounds check is relevant is in case of covariant generics:

class B<X extends num> {
  T foo<T extends X>(T value) => value;
}

void main() {
  var x = B<int>();
  B<num> y = x;
  T Function<T extends num>(T value) z = y.foo;
  z<double>(42.0);
}

[eernstg]

Ah! — the example with class B is quite similar to https://github.com/dart-lang/sdk/issues/46784. Note that the initialization of z should throw, because there is no subtype relationship between T Function<T extends num>(T) and T Function<T extends int>(T) (actually, it's already the evaluation of y.foo that should throw, so we never reach the point where z is initialized).

[mkustermann]

@eernstg Is that then a VM bug in the partial instantiation / bounds checking algorithm or a CFE issue (as https://github.com/dart-lang/sdk/issues/46784 is marked)?

[eernstg]

I marked #46784 as a CFE issue because I expect the CFE to generate kernel code for the dynamic type check. The VM should then be able to proceed with an operation like z<double> or z<double>(42.0) without checking the correctness of the actual type argument, because double <: num can be seen to be true at compile-time.

Here is the kernel code for main with the example [here]():

static method main() → void {
  self::B<core::int> x = new self::B::•<core::int>();
  self::B<core::num> y = x;
  <T extends core::num>(T) → T z = y.{self::B::foo}{<T extends core::num>(T) → T};
  z<core::double>(42.0){(core::double) → core::double};
}

If we adjust the source code to use a "contravariant member" (a getter) then we get the following:

class B<X extends num> {
  T Function<T extends X>(T) get foo => <T extends X>(T value) => value;
}

void main() {
  var x = B<int>();
  B<num> y = x;
  T Function<T extends num>(T value) z = y.foo;
}

with the following kernel:

static method main() → void {
  self::B<core::int> x = new self::B::•<core::int>();
  self::B<core::num> y = x;
  <T extends core::num>(T) → T z = y.{self::B::foo}{<T extends core::num = dynamic>(T) → T} as{TypeError,CovarianceCheck,ForNonNullableByDefault} <T extends core::num = dynamic>(T) → T;
}

With #46784, we should get the type check (as{...} ...) in the former case as well as the latter.

[eernstg]

As a followup on the previous comment, I don't know enough about the information delivered by the CFE to the VM to know how it is possible to see in the VM context exactly in which cases there is a need to perform the dynamic check on the actual type argument. @johnniwinther, maybe you could help us here?

[eernstg]

Just talked to @stefantsov. I think the dynamic check on the actual type argument on a generically instantiated instance method is needed if and only if that type parameter in the statically known method declaration D has generic-covariant-impl (in which case the corresponding type parameter in any method that overrides D or that is overridden by D has generic-covariant-impl as well). If it is possible to store that property in the representation of the method then it should be possible to look it up and only do the dynamic check on the type parameter when needed.

[johnniwinther]

I think this problem is just the consequence of the missing check reported in #46784. For these checks we set the isCovarianceCheck flag (see the CovarianceCheck in the generated AST) so these AsExpressions can be recognized by backends - and for instance not be optimized away.