[dart2wasm] More CFG support for type arguments

Add support for generic functions in the CFG lowering, and for
`DirectCall` lowerings whose type arguments depend on the caller's type
parameters.

Change-Id: I0b09924ae95af105ec25e10ea4c533d0a2b43433
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/573522
Reviewed-by: Martin Kustermann <kustermann@google.com>
Commit-Queue: Nicholas Shahan <nshahan@google.com>
diff --git a/pkg/cfg/lib/front_end/ast_to_ir.dart b/pkg/cfg/lib/front_end/ast_to_ir.dart
index 1039eeb..170dfca 100644
--- a/pkg/cfg/lib/front_end/ast_to_ir.dart
+++ b/pkg/cfg/lib/front_end/ast_to_ir.dart
@@ -2376,7 +2376,7 @@
         .getThisVariable(function.member);
     if (function.hasFunctionTypeParameters) {
       functionTypeParameters = builder.declareLocalVariable(
-        '#functionTypeParameters',
+        LocalVariable.functionTypeParametersVariableName,
         null,
         const TypeParametersType(),
       );
diff --git a/pkg/cfg/lib/ir/local_variable.dart b/pkg/cfg/lib/ir/local_variable.dart
index 22b27c5..0fcbff9 100644
--- a/pkg/cfg/lib/ir/local_variable.dart
+++ b/pkg/cfg/lib/ir/local_variable.dart
@@ -12,6 +12,8 @@
 class LocalVariable {
   static const String exceptionVariableName = '#exception';
   static const String stackTraceVariableName = '#stackTrace';
+  static const String functionTypeParametersVariableName =
+      '#functionTypeParameters';
 
   /// Name of the variable.
   final String name;
@@ -41,6 +43,8 @@
       declaration == null && name == exceptionVariableName;
   bool get isStackTraceVariable =>
       declaration == null && name == stackTraceVariableName;
+  bool get isFunctionTypeParametersVariable =>
+      declaration == null && name == functionTypeParametersVariableName;
 
   @override
   String toString() => name;
diff --git a/pkg/dart2wasm/lib/prod/cfg/to_wasm.dart b/pkg/dart2wasm/lib/prod/cfg/to_wasm.dart
index 0740bec..fff15d8 100644
--- a/pkg/dart2wasm/lib/prod/cfg/to_wasm.dart
+++ b/pkg/dart2wasm/lib/prod/cfg/to_wasm.dart
@@ -15,13 +15,21 @@
 import '../../param_info.dart';
 import '../../reference_extensions.dart';
 import '../../translator.dart';
+import '../../types.dart';
 
 /// Translates a [FlowGraph] (CFG IR) to WebAssembly bytecode for the
 /// production compiler.
 final class ProdCfgToWasm extends CfgToWasm {
   final Translator translator;
-  final List<w.Local> paramLocals;
   final EntryPoint kind;
+  final List<w.Local> paramLocals;
+
+  /// The locals holding the type arguments built for each [TypeArguments]
+  /// instruction.
+  ///
+  /// Each list has one element per type argument. The element is `null` for
+  /// constant type arguments, which are instantiated where they are used.
+  final Map<TypeArguments, List<w.Local?>> typeArgumentLocals = {};
 
   @override
   late final ProdWasmInstructionLowerer lowerer = ProdWasmInstructionLowerer(
@@ -74,7 +82,8 @@
 }
 
 final class ProdWasmInstructionLowerer
-    extends WasmInstructionLowerer<ProdCfgToWasm> {
+    extends WasmInstructionLowerer<ProdCfgToWasm>
+    implements TypeCodeGenerator {
   ProdWasmInstructionLowerer(super.gen);
 
   Translator get translator => gen.translator;
@@ -89,6 +98,10 @@
       Constant() =>
         !gen.isUndefined(instr) ||
             instr.inputUses.every((u) => u.getInstruction(gen.graph) is Phi),
+      // TODO(dart2wasm): Support class type parameters.
+      TypeParameters(:final kind) =>
+        kind == TypeParametersKind.functionTypeParameters,
+      TypeArguments() => true,
       Return() => true,
       Unreachable() => true,
       Branch() => true,
@@ -147,11 +160,6 @@
     }
     final member = target.member;
     if (member is! ast.Procedure || member.isInstanceMember) return false;
-    // TODO(nshahan): Support type arguments that depend on type parameters
-    // (`TypeArguments` instruction).
-    if (instr.hasTypeArguments && instr.typeArguments is! Constant) {
-      return false;
-    }
     // TODO(nshahan): Support intrinsics and external effects (see
     // `CodeGenerator.visitStaticInvocation`).
     if (member.isExternal ||
@@ -165,7 +173,17 @@
   @override
   void visitParameter(Parameter instr) {
     assert(instr.isFunctionParameter);
-    final paramLocal = gen.paramLocals[instr.variable.index];
+    // The CFG passes all function type arguments in a single parameter, but
+    // the wasm function has a separate `_Type` parameter for each of them.
+    // Uses of the type parameters load them directly from those wasm
+    // parameters in [instantiateTypeParameter].
+    if (instr.variable.isFunctionTypeParametersVariable) return;
+    final typeParameterCount =
+        gen.graph.function.numberOfFunctionTypeParameters;
+    final wasmIndex = typeParameterCount == 0
+        ? instr.variable.index
+        : instr.variable.index - 1 + typeParameterCount;
+    final paramLocal = gen.paramLocals[wasmIndex];
     final expectedType = gen.translateType(instr.type);
     if (translator.needsConversion(paramLocal.type, expectedType)) {
       final convertedLocal = b.addLocal(expectedType);
@@ -179,6 +197,46 @@
   }
 
   @override
+  void visitTypeParameters(TypeParameters instr) {
+    // Nothing to do here. Currently only function type parameters are
+    // loaded from their wasm parameter local when needed for TypeArgument
+    // instructions.
+    //
+    // Other instructions uses are not yet supported.
+  }
+
+  @override
+  void visitTypeArguments(TypeArguments instr) {
+    // Build each non-constant type argument once and store it in a local, so
+    // all users of this instruction can share it.
+    final locals = <w.Local?>[];
+    final typeType = translator.types.nonNullableTypeType;
+    for (final typeArgument in instr.types) {
+      if (translator.types.isTypeConstant(typeArgument)) {
+        locals.add(null);
+      } else {
+        final local = b.addLocal(typeType);
+        translator.types.makeType(this, typeArgument);
+        b.local_set(local);
+        locals.add(local);
+      }
+    }
+    gen.typeArgumentLocals[instr] = locals;
+  }
+
+  @override
+  w.ValueType instantiateTypeParameter(ast.TypeParameter parameter) {
+    final index = gen.member.function!.typeParameters.indexOf(parameter);
+    if (index < 0) {
+      throw UnsupportedError('Type parameter $parameter is not in scope.');
+    }
+    final local = gen.paramLocals[index];
+    b.local_get(local);
+    translator.convertType(b, local.type, translator.types.nonNullableTypeType);
+    return translator.types.nonNullableTypeType;
+  }
+
+  @override
   void instantiateConstant(Constant instr, w.ValueType expectedType) {
     translator.constants.instantiateConstant(
       b,
@@ -275,26 +333,37 @@
     int signatureOffset = 0;
 
     // Push the type arguments. They are passed as a single input but each type
-    // argument is a separate function parameter.
+    // argument is passed as a separate function parameter, typed as a
+    // non-nullable `_Type`.
     if (instr.hasTypeArguments) {
-      final typeArguments =
-          (instr.typeArguments as Constant).value.constant
-              as TypeArgumentsConstant;
-      assert(typeArguments.types.length == paramInfo.typeParamCount);
-      for (int i = 0; i < typeArguments.types.length; ++i) {
-        // TODO(nshahan): Support type arguments that depend on type parameters
-        // (`TypeArguments` instruction).
-        assert(translator.types.isTypeConstant(typeArguments.types[i]));
-        translator.constants.instantiateConstant(
-          b,
-          ast.TypeLiteralConstant(typeArguments.types[i]),
-          signature.inputs[i],
-        );
+      final typeArgumentsDef = instr.typeArguments!;
+      final List<ast.DartType> types;
+      switch (typeArgumentsDef) {
+        case Constant(value: ConstantValue(:TypeArgumentsConstant constant)):
+          // All type arguments are constant.
+          types = constant.types;
+          for (int i = 0; i < types.length; ++i) {
+            _pushConstantType(types[i]);
+          }
+        case TypeArguments():
+          // Some type arguments depend on type parameters.
+          types = typeArgumentsDef.types;
+          final locals = gen.typeArgumentLocals[typeArgumentsDef]!;
+          for (int i = 0; i < types.length; ++i) {
+            final local = locals[i];
+            // [visitTypeArguments] stored those in locals with `null` element
+            // placeholders where constant types should be pushed instead.
+            local == null ? _pushConstantType(types[i]) : b.local_get(local);
+          }
+
+        default:
+          throw StateError('Unexpected type arguments: $typeArgumentsDef');
       }
+      assert(types.length == paramInfo.typeParamCount);
       // The CFG instruction packs all type arguments together into the input
       // at offset 0. Positional parameters start after that.
       inputOffset = 1;
-      signatureOffset = typeArguments.types.length;
+      signatureOffset = types.length;
     }
 
     // Push the provided positional arguments.
@@ -346,4 +415,13 @@
       }
     }
   }
+
+  /// Pushes the constant `_Type` for [type], loaded from its constant global.
+  void _pushConstantType(ast.DartType type) {
+    translator.constants.instantiateConstant(
+      b,
+      ast.TypeLiteralConstant(type),
+      translator.types.nonNullableTypeType,
+    );
+  }
 }
diff --git a/tests/web/wasm/cfg/direct_call_test.dart b/tests/web/wasm/cfg/direct_call_test.dart
index 9091b48..cb2b67d 100644
--- a/tests/web/wasm/cfg/direct_call_test.dart
+++ b/tests/web/wasm/cfg/direct_call_test.dart
@@ -240,8 +240,8 @@
 @pragma('wasm:cfg')
 bool callIsNullNamed() => isNullNamed();
 
-// Not compiled via CFG (generic functions are unsupported). The type argument
-// determines the result.
+// Not compiled via CFG (`is T` is unsupported). The type argument determines
+// the result.
 @pragma('wasm:never-inline')
 bool isA<T>(Object? o) => o is T;
 
@@ -305,6 +305,41 @@
 String callDescribeGenericNamed(int x, String s) =>
     describeGenericNamed<int>(x, suffix: s);
 
+// The type parameter is a separate wasm parameter before the value parameter.
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+T cfgIdentity<T>(T x) => x;
+
+// Type arguments that are type parameters of the caller.
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+String forwardTypeNames<A, B>() => typeNames<B, A>();
+
+// Type arguments that are built at runtime from type parameters of the caller.
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+String forwardCompositeTypeNames<A, B>() => typeNames<List<A>, B Function(A)>();
+
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+String forwardNamedParameterTypeNames<A>() =>
+    typeNames<void Function({A a, int b}), A>();
+
+// A nullable type parameter and a constant type argument.
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+String forwardNullableTypeNames<A>() => typeNames<A?, int>();
+
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+bool forwardIsA<T>(Object? o) => isA<T>(o);
+
+// Type parameters combined with value and named arguments.
+@pragma('wasm:never-inline')
+@pragma('wasm:cfg')
+String forwardDescribeGenericNamed<T>(T value, String s) =>
+    describeGenericNamed<T>(value, suffix: s);
+
 void main() {
   final int0 = int.parse('0');
   final int1 = int.parse('1');
@@ -417,4 +452,24 @@
     'x $String y z',
     describeGenericNamed<String>('y', suffix: 'z', prefix: 'x'),
   );
+
+  // Type arguments that depend on type parameters of the caller.
+  Expect.equals(5, cfgIdentity<int>(int5));
+  Expect.equals('$String, $int', forwardTypeNames<int, String>());
+  Expect.equals(
+    typeNames<List<int>, String Function(int)>(),
+    forwardCompositeTypeNames<int, String>(),
+  );
+  Expect.equals(
+    typeNames<void Function({String a, int b}), String>(),
+    forwardNamedParameterTypeNames<String>(),
+  );
+  Expect.equals(typeNames<String?, int>(), forwardNullableTypeNames<String>());
+  Expect.equals(typeNames<int?, int>(), forwardNullableTypeNames<int?>());
+  Expect.isTrue(forwardIsA<int>(int1));
+  Expect.isFalse(forwardIsA<int>(stringValue));
+  Expect.isFalse(forwardIsA<int>(nullValue));
+  Expect.isTrue(forwardIsA<int?>(nullValue));
+  Expect.equals('p $int 1 a', forwardDescribeGenericNamed<int>(int1, 'a'));
+  Expect.equals('p $String y z', forwardDescribeGenericNamed<String>('y', 'z'));
 }