| // Copyright (c) 2022, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import 'dart:math' show min; |
| |
| import 'package:kernel/ast.dart'; |
| import 'package:vm/metadata/procedure_attributes.dart'; |
| import 'package:vm/metadata/table_selector.dart'; |
| import 'package:wasm_builder/wasm_builder.dart' as w; |
| |
| import 'class_info.dart'; |
| import 'dynamic_module_kernel_metadata.dart'; |
| import 'dynamic_modules.dart'; |
| import 'param_info.dart'; |
| import 'reference_extensions.dart'; |
| import 'serialization.dart'; |
| import 'translator.dart'; |
| |
| /// Information for a dispatch table selector. |
| /// |
| /// A selector encapsulates information to generate code that selects the right |
| /// member (method, getter, setter) implementation in an instance invocation, |
| /// from the dispatch table. Dispatch table is generated by [DispatchTable]. |
| /// |
| /// Target of a selector is a method, getter, or setter [Reference]. A target |
| /// does not have to correspond to a user-written Dart member, it can be for a |
| /// generated one. For example, for torn-off methods, we generate a [Reference] |
| /// for the tear-off getter a selector for it. |
| class SelectorInfo { |
| final DispatchTable dispatchTable; |
| |
| Translator get translator => dispatchTable.translator; |
| |
| /// Unique ID of the selector. |
| final int id; |
| |
| /// Number of use sites of the selector. |
| final int callCount; |
| |
| /// Least upper bound of [ParameterInfo]s of all targets. |
| late final ParameterInfo paramInfo; |
| |
| /// Is this an implicit or explicit setter? |
| final bool isSetter; |
| |
| /// Whether we create multiple entry points for the selector. |
| /// |
| /// We create multiple entry points when any implementation of this selector |
| /// performs type checks on the passed arguments. |
| late bool useMultipleEntryPoints; |
| |
| late bool isDynamicSubmoduleOverridable; |
| late bool isDynamicSubmoduleCallable; |
| late bool isDynamicSubmoduleInheritable; |
| |
| /// Whether the computation of [paramInfo] should enforce usage of sentinels |
| /// for optional parameters. |
| late bool _useSentinelForOptionalParameters; |
| |
| /// Wasm function type for the selector. |
| /// |
| /// This should be read after all targets have been added to the selector. |
| late final w.FunctionType signature = _computeSignature(); |
| |
| /// The selector's member's name. |
| final String name; |
| |
| SelectorTargets? _checked; |
| SelectorTargets? _unchecked; |
| SelectorTargets? _normal; |
| |
| /// The set of references we use to calculate the [paramInfo]. |
| final List<Reference> _references = []; |
| |
| SelectorTargets targets({required bool unchecked}) { |
| if (useMultipleEntryPoints) { |
| assert(_checked!.targetRanges.length == _unchecked!.targetRanges.length); |
| return unchecked ? _unchecked! : _checked!; |
| } |
| assert(_checked == null && _unchecked == null); |
| return _normal!; |
| } |
| |
| SelectorInfo._( |
| this.dispatchTable, |
| this.id, |
| this.name, |
| this.callCount, { |
| required this.isSetter, |
| }); |
| |
| void serialize(DataSerializer sink) { |
| sink.writeInt(id); |
| sink.writeString(name); |
| sink.writeInt(callCount); |
| sink.writeBoolList([ |
| isSetter, |
| useMultipleEntryPoints, |
| isDynamicSubmoduleOverridable, |
| isDynamicSubmoduleCallable, |
| isDynamicSubmoduleInheritable, |
| _useSentinelForOptionalParameters, |
| ]); |
| sink.writeNullable(_checked, (targets) => targets.serialize(sink)); |
| sink.writeNullable(_unchecked, (targets) => targets.serialize(sink)); |
| sink.writeNullable(_normal, (targets) => targets.serialize(sink)); |
| sink.writeList(_references, sink.writeReference); |
| } |
| |
| factory SelectorInfo.deserialize( |
| DataDeserializer source, DispatchTable dispatchTable) { |
| final id = source.readInt(); |
| final name = source.readString(); |
| final callCount = source.readInt(); |
| final [ |
| isSetter, |
| useMultipleEntryPoints, |
| isDynamicSubmoduleOverridable, |
| isDynamicSubmoduleCallable, |
| isDynamicSubmoduleInheritable, |
| useSentinelForOptionalParameters, |
| ] = source.readBoolList(); |
| final checked = |
| source.readNullable(() => SelectorTargets.deserialize(source)); |
| final unchecked = |
| source.readNullable(() => SelectorTargets.deserialize(source)); |
| final normal = |
| source.readNullable(() => SelectorTargets.deserialize(source)); |
| final references = source.readList(source.readReference); |
| |
| final paramInfo = _parameterInfoFromReferences( |
| references, useSentinelForOptionalParameters); |
| return SelectorInfo._(dispatchTable, id, name, callCount, |
| isSetter: isSetter) |
| ..useMultipleEntryPoints = useMultipleEntryPoints |
| ..isDynamicSubmoduleCallable = isDynamicSubmoduleCallable |
| ..isDynamicSubmoduleOverridable = isDynamicSubmoduleOverridable |
| ..isDynamicSubmoduleInheritable = isDynamicSubmoduleInheritable |
| .._useSentinelForOptionalParameters = useSentinelForOptionalParameters |
| .._checked = checked |
| .._unchecked = unchecked |
| .._normal = normal |
| .._references.addAll(references) |
| ..paramInfo = paramInfo; |
| } |
| |
| String entryPointName(bool unchecked) { |
| if (!useMultipleEntryPoints) return name; |
| return '$name (${unchecked ? 'unchecked' : 'checked'})'; |
| } |
| |
| /// Compute the signature for the functions implementing members targeted by |
| /// this selector. |
| /// |
| /// When the selector has multiple targets, the type of each parameter/return |
| /// is the upper bound across all targets, such that all targets have the |
| /// same signature, and the actual representation types of the parameters and |
| /// returns are subtypes (resp. supertypes) of the types in the signature. |
| w.FunctionType _computeSignature() { |
| var nameIndex = paramInfo.nameIndex; |
| final int returnCount = isSetter ? 0 : 1; |
| List<Set<w.ValueType>> inputSets = |
| List.generate(1 + paramInfo.paramCount, (_) => {}); |
| List<Set<w.ValueType>> outputSets = List.generate(returnCount, (_) => {}); |
| List<bool> ensureBoxed = List.filled(1 + paramInfo.paramCount, false); |
| Iterable<({Reference target, Range range})> targetRanges = |
| targets(unchecked: false).targetRanges; |
| for (final (range: _, :target) in targetRanges) { |
| Member member = target.asMember; |
| DartType receiver = |
| InterfaceType(member.enclosingClass!, Nullability.nonNullable); |
| List<DartType> positional; |
| Map<String, DartType> named; |
| List<DartType> returns; |
| if (member is Field) { |
| if (target.isImplicitGetter) { |
| positional = const []; |
| named = const {}; |
| returns = [translator.typeOfReturnValue(member)]; |
| } else { |
| positional = [member.setterType]; |
| named = const {}; |
| returns = const []; |
| } |
| } else { |
| FunctionNode function = member.function!; |
| if (target.isTearOffReference) { |
| positional = const []; |
| named = const {}; |
| returns = [function.computeFunctionType(Nullability.nonNullable)]; |
| } else { |
| final typeForParam = translator.typeOfParameterVariable; |
| positional = [ |
| for (int i = 0; i < function.positionalParameters.length; i++) |
| typeForParam(function.positionalParameters[i], |
| i < function.requiredParameterCount) |
| ]; |
| named = { |
| for (VariableDeclaration param in function.namedParameters) |
| param.name!: typeForParam(param, param.isRequired) |
| }; |
| returns = target.isSetter |
| ? const [] |
| : [translator.typeOfReturnValue(member)]; |
| } |
| } |
| assert(returns.length <= outputSets.length); |
| inputSets[0].add(isDynamicSubmoduleOverridable |
| ? translator.topTypeNonNullable |
| : translator.translateType(receiver)); |
| for (int i = 0; i < positional.length; i++) { |
| DartType type = positional[i]; |
| inputSets[1 + i].add(translator.translateType(type)); |
| ensureBoxed[1 + i] |= |
| paramInfo.positional[i] == ParameterInfo.defaultValueSentinel; |
| } |
| for (String name in named.keys) { |
| int i = nameIndex[name]!; |
| DartType type = named[name]!; |
| inputSets[1 + i].add(translator.translateType(type)); |
| ensureBoxed[1 + i] |= |
| paramInfo.named[name] == ParameterInfo.defaultValueSentinel; |
| } |
| for (int i = 0; i < returnCount; i++) { |
| if (i < returns.length) { |
| DartType type = returns[i]; |
| outputSets[i].add(translator.translateReturnType(type)); |
| } else { |
| outputSets[i].add(translator.topType); |
| } |
| } |
| } |
| |
| List<w.ValueType> typeParameters = List.filled(paramInfo.typeParamCount, |
| translator.classInfo[translator.typeClass]!.nonNullableType); |
| List<w.ValueType> inputs = List.generate( |
| inputSets.length, |
| (i) => _upperBound(inputSets[i], |
| ensureBoxed: ensureBoxed[i], isReceiver: i == 0)); |
| if (name == '==') { |
| // == can't be called with null |
| inputs[1] = inputs[1].withNullability(false); |
| } |
| List<w.ValueType> outputs = List.generate(outputSets.length, |
| (i) => _upperBound(outputSets[i], ensureBoxed: false)); |
| return translator.typesBuilder.defineFunction( |
| [inputs[0], ...typeParameters, ...inputs.sublist(1)], outputs); |
| } |
| |
| w.ValueType _upperBound(Set<w.ValueType> types, |
| {required bool ensureBoxed, bool isReceiver = false}) { |
| if (types.isEmpty) { |
| // This happens if the selector doesn't have any targets. Any call site of |
| // such a selector is unreachable. Though such call sites still have to |
| // evaluate receiver and arguments. Doing so requires the signature. So we |
| // create a dummy signature with top types. Receivers specifically should |
| // be non-nullable since we must be invoking a selector on some object. |
| assert(!isReceiver || isDynamicSubmoduleOverridable); |
| return isReceiver ? translator.topTypeNonNullable : translator.topType; |
| } |
| if (!ensureBoxed && types.length == 1 && types.single.isPrimitive) { |
| // Unboxed primitive. |
| return types.single; |
| } |
| final bool nullable = types.any((type) => type.nullable); |
| int minDepth = 999999999; |
| Set<w.DefType> heapTypes = types |
| .where((type) => type is! w.RefType || type.heapType is w.DefType) |
| .map((type) { |
| w.DefType def = type is w.RefType |
| ? type.heapType as w.DefType |
| : translator.classInfo[translator.boxedClasses[type]!]!.struct; |
| minDepth = min(minDepth, def.depth); |
| return def; |
| }).toSet(); |
| if (heapTypes.isEmpty) { |
| // Only abstract heap types. |
| Set<w.HeapType> heapTypes = |
| types.map((type) => (type as w.RefType).heapType).toSet(); |
| return w.RefType(heapTypes.single, nullable: nullable); |
| } |
| int targetDepth = minDepth; |
| while (heapTypes.length > 1) { |
| heapTypes = heapTypes.map((s) { |
| while (s.depth > targetDepth) { |
| s = s.superType!; |
| } |
| return s; |
| }).toSet(); |
| targetDepth -= 1; |
| } |
| return w.RefType.def(heapTypes.single, nullable: nullable); |
| } |
| |
| late final Set<Reference> _targetSet = useMultipleEntryPoints |
| ? { |
| ..._checked!._targetSet, |
| ..._unchecked!._targetSet, |
| } |
| : _normal!._targetSet; |
| |
| bool containsTarget(Reference target) => _targetSet.contains(target); |
| } |
| |
| class SelectorTargets { |
| /// Targets for all concrete classes implementing this selector. |
| /// |
| /// As a subclass hierarchy often inherits the same target, we associate the |
| /// target with a range of class ids. The ranges are non-empty, |
| /// non-overlapping and sorted in ascending order. |
| final List<({Range range, Reference target})> targetRanges; |
| |
| /// Targets that a interface call will check & directly call before falling |
| /// back to dispatch table calls. |
| /// |
| /// The targets in here are mainly the ones annotated with |
| /// `@pragma('wasm:static-dispatch')`. The compiler will generate then code |
| /// that first checks the receiver for those targets directly and issue direct |
| /// calls before falling back to dispatch table calls. |
| final List<({Range range, Reference target})> staticDispatchRanges; |
| |
| /// Offset of the selector in the dispatch table. |
| /// |
| /// For a class in [targetRanges], `class ID + offset` gives the offset of the |
| /// class member for this selector. |
| int? offset; |
| |
| SelectorTargets(this.targetRanges, this.staticDispatchRanges); |
| |
| late final Set<Reference> _targetSet = |
| targetRanges.map((e) => e.target).toSet(); |
| |
| void serialize(DataSerializer sink) { |
| sink.writeInt(offset == null ? 0 : offset! + 1); |
| sink.writeInt(targetRanges.length); |
| for (final (:range, :target) in targetRanges) { |
| range.serialize(sink); |
| sink.writeReference(target); |
| } |
| sink.writeInt(staticDispatchRanges.length); |
| for (final (:range, :target) in staticDispatchRanges) { |
| range.serialize(sink); |
| sink.writeReference(target); |
| } |
| } |
| |
| factory SelectorTargets.deserialize(DataDeserializer source) { |
| final offset = source.readInt(); |
| final targetRangesLength = source.readInt(); |
| final targetRanges = <({Range range, Reference target})>[]; |
| for (int i = 0; i < targetRangesLength; i++) { |
| final range = Range.deserialize(source); |
| final target = source.readReference(); |
| targetRanges.add((range: range, target: target)); |
| } |
| final staticDispatchRangesLength = source.readInt(); |
| final staticDispatchRanges = <({Range range, Reference target})>[]; |
| for (int i = 0; i < staticDispatchRangesLength; i++) { |
| final range = Range.deserialize(source); |
| final target = source.readReference(); |
| staticDispatchRanges.add((range: range, target: target)); |
| } |
| return SelectorTargets(targetRanges, staticDispatchRanges) |
| ..offset = offset == 0 ? null : offset - 1; |
| } |
| } |
| |
| /// Builds the dispatch table for member calls. |
| class DispatchTable { |
| static const _functionType = w.RefType.func(nullable: true); |
| final bool isDynamicSubmoduleTable; |
| |
| late final Map<TreeNode, ProcedureAttributesMetadata> |
| procedureAttributeMetadata = |
| translator.isDynamicSubmodule && !isDynamicSubmoduleTable |
| ? (translator.component |
| .metadata[dynamicMainModuleProcedureAttributeMetadataTag] |
| as ProcedureAttributesMetadataRepository) |
| .mapping |
| : translator.procedureAttributeMetadata; |
| |
| late final Translator translator; |
| |
| late final List<TableSelectorInfo> _selectorMetadata = |
| translator.isDynamicSubmodule && !isDynamicSubmoduleTable |
| ? (translator.component.metadata[dynamicMainModuleSelectorMetadataTag] |
| as TableSelectorMetadataRepository) |
| .mapping[translator.component]! |
| .selectors |
| : (translator.component |
| .metadata[TableSelectorMetadataRepository.repositoryTag] |
| as TableSelectorMetadataRepository) |
| .mapping[translator.component]! |
| .selectors; |
| late final int minClassId = isDynamicSubmoduleTable |
| ? translator.classIdNumbering.firstDynamicSubmoduleClassId |
| : 0; |
| late final int maxClassId = isDynamicSubmoduleTable |
| ? translator.classIdNumbering.maxDynamicSubmoduleConcreteClassId! |
| : translator.classIdNumbering.maxConcreteClassId; |
| |
| /// Maps selector IDs to selectors. |
| final Map<int, SelectorInfo> _selectorInfo = {}; |
| |
| /// Maps member names to getter selectors with the same member name. |
| final Map<Name, Set<SelectorInfo>> _dynamicGetters = {}; |
| |
| /// Maps member names to setter selectors with the same member name. |
| final Map<Name, Set<SelectorInfo>> _dynamicSetters = {}; |
| |
| /// Maps member names to method selectors with the same member name. |
| final Map<Name, Set<SelectorInfo>> _dynamicMethods = {}; |
| |
| /// Contents of [_definedWasmTable]. For a selector with ID S and a target |
| /// class of the selector with ID C, `table[S + C]` gives the reference to the |
| /// class member for the selector. |
| late final List<Reference?> _table; |
| |
| late final w.TableBuilder _definedWasmTable; |
| late final WasmTableImporter _importedWasmTables = |
| WasmTableImporter(translator, 'dispatch'); |
| |
| /// The Wasm table for the dispatch table. |
| w.Table getWasmTable(w.ModuleBuilder module) => |
| _importedWasmTables.get(_definedWasmTable, module); |
| |
| DispatchTable({this.isDynamicSubmoduleTable = false}); |
| |
| void serialize(DataSerializer sink) { |
| sink.writeList(_selectorInfo.values, (s) => s.serialize(sink)); |
| sink.writeList(_table, (r) => sink.writeNullable(r, sink.writeReference)); |
| // Preserve call selectors for closure calls which are handled dynamically. |
| final callSelectors = _dynamicGetters[Name('call')]!; |
| sink.writeList(callSelectors, (s) => sink.writeInt(s.id)); |
| } |
| |
| factory DispatchTable.deserialize(DataDeserializer source) { |
| final dispatchTable = DispatchTable(); |
| |
| final selectors = |
| source.readList(() => SelectorInfo.deserialize(source, dispatchTable)); |
| final table = source |
| .readList(() => source.readNullable(() => source.readReference())); |
| final callSelectorIds = source.readList(source.readInt); |
| |
| for (final selector in selectors) { |
| dispatchTable._selectorInfo[selector.id] = selector; |
| } |
| dispatchTable._table = table; |
| |
| // Preserve call selectors for closure calls which are handled dynamically. |
| final callSelectors = <SelectorInfo>{}; |
| for (final selectorId in callSelectorIds) { |
| callSelectors.add(dispatchTable._selectorInfo[selectorId]!); |
| } |
| dispatchTable._dynamicGetters[Name('call')] = callSelectors; |
| |
| return dispatchTable; |
| } |
| |
| SelectorInfo selectorForTarget(Reference target) { |
| Member member = target.asMember; |
| bool isGetter = target.isGetter || target.isTearOffReference; |
| ProcedureAttributesMetadata metadata = procedureAttributeMetadata[member]!; |
| int selectorId = isGetter |
| ? metadata.getterSelectorId |
| : metadata.methodOrSetterSelectorId; |
| return _selectorInfo[selectorId]!; |
| } |
| |
| SelectorInfo _createSelectorForTarget(Reference target) { |
| Member member = target.asMember; |
| bool isGetter = target.isGetter || target.isTearOffReference; |
| bool isSetter = target.isSetter; |
| ProcedureAttributesMetadata metadata = procedureAttributeMetadata[member]!; |
| int selectorId = isGetter |
| ? metadata.getterSelectorId |
| : metadata.methodOrSetterSelectorId; |
| |
| // _WasmBase and its subclass methods cannot be called dynamically |
| final cls = member.enclosingClass; |
| final isWasmType = cls != null && translator.isWasmType(cls); |
| |
| final calledDynamically = !isWasmType && |
| (metadata.getterCalledDynamically || |
| metadata.methodOrSetterCalledDynamically || |
| member.name.text == "call"); |
| |
| // The compiler will generate calls to `noSuchMethod` in the dynamic |
| // invocation forwarders. So we ensure that the call count is positive. |
| final isNoSuchMethod = member == translator.objectNoSuchMethod; |
| final callCount = |
| _selectorMetadata[selectorId].callCount + (isNoSuchMethod ? 1 : 0); |
| final selector = _selectorInfo.putIfAbsent( |
| selectorId, |
| () => SelectorInfo._(this, selectorId, member.name.text, callCount, |
| isSetter: isSetter)); |
| assert(selector.isSetter == isSetter); |
| selector._references.add(target); |
| |
| if (calledDynamically) { |
| if (isGetter) { |
| (_dynamicGetters[member.name] ??= {}).add(selector); |
| } else if (isSetter) { |
| (_dynamicSetters[member.name] ??= {}).add(selector); |
| } else { |
| (_dynamicMethods[member.name] ??= {}).add(selector); |
| } |
| } |
| |
| return selector; |
| } |
| |
| /// Get selectors for getters and tear-offs with the given name. |
| Iterable<SelectorInfo> dynamicGetterSelectors(Name memberName) => |
| _dynamicGetters[memberName] ?? Iterable.empty(); |
| |
| /// Get selectors for setters with the given name. |
| Iterable<SelectorInfo> dynamicSetterSelectors(Name memberName) => |
| _dynamicSetters[memberName] ?? Iterable.empty(); |
| |
| /// Get selectors for methods with the given name. |
| Iterable<SelectorInfo> dynamicMethodSelectors(Name memberName) => |
| _dynamicMethods[memberName] ?? Iterable.empty(); |
| |
| void _initializeWasmTable() { |
| final module = isDynamicSubmoduleTable |
| ? translator.dynamicSubmodule |
| : translator.mainModule; |
| _definedWasmTable = module.tables.define(_functionType, _table.length); |
| if (!isDynamicSubmoduleTable) { |
| for (final module in translator.modules) { |
| // Ensure the dispatch table is imported into every module as the first |
| // table. |
| getWasmTable(module); |
| } |
| } |
| } |
| |
| void build() { |
| if (!isDynamicSubmoduleTable && translator.isDynamicSubmodule) { |
| _initializeWasmTable(); |
| return; |
| } |
| // Collect class/selector combinations |
| |
| // Maps class to selector IDs of the class |
| final selectorsInClass = <Class, Map<SelectorInfo, Reference>>{}; |
| final staticDispatchPragmas = <Reference>{}; |
| |
| // Add classes to selector targets for their members |
| for (ClassInfo info in translator.classesSupersFirst) { |
| final Class cls = info.cls ?? translator.coreTypes.objectClass; |
| final Map<SelectorInfo, Reference> selectors; |
| |
| // Add the class to its inherited members' selectors. Skip `_WasmBase`: |
| // it's defined as a Dart class (in `dart._wasm` library) but it's special |
| // and does not inherit from `Object`. |
| final ClassInfo? superInfo = info.superInfo; |
| if (superInfo == null || cls == translator.wasmTypesBaseClass) { |
| selectors = {}; |
| } else { |
| final Class superCls = |
| superInfo.cls ?? translator.coreTypes.objectClass; |
| selectors = Map.of(selectorsInClass[superCls]!); |
| } |
| |
| final classIsDynamicSubmoduleExtendable = |
| cls.isDynamicSubmoduleExtendable(translator.coreTypes); |
| |
| /// Add a method (or getter, setter) of the current class ([info]) to |
| /// [reference]'s selector's targets. |
| /// |
| /// Because we visit a superclass before its subclasses, if the class |
| /// inherits [reference], then the selector will already have a target |
| /// for the class. Override that target if [reference] is a not abstract. |
| /// If it's abstract, then the superclass's method will be called, so do |
| /// not update the target. |
| void addMember(Reference reference, bool staticDispatch) { |
| SelectorInfo selector = _createSelectorForTarget(reference); |
| if (reference.asMember.isAbstract) { |
| // Reference is abstract, do not override inherited concrete member |
| selectors[selector] ??= reference; |
| } else { |
| // Reference is concrete, override inherited member |
| selectors[selector] = reference; |
| |
| if (staticDispatch) staticDispatchPragmas.add(reference); |
| } |
| } |
| |
| // Add the class to its non-static members' selectors. If `info.cls` is |
| // `null`, that means [info] represents the `#Top` type, which is not a |
| // Dart class but has the members of `Object`. |
| for (Member member in cls.members) { |
| // Skip static members |
| if (!member.isInstanceMember) { |
| continue; |
| } |
| final bool staticDispatch = |
| translator.getPragma<bool>(member, 'wasm:static-dispatch', true) ?? |
| false; |
| if (member is Field) { |
| addMember(member.getterReference, staticDispatch); |
| if (member.hasSetter) { |
| final target = member.setterReference!; |
| addMember(target, staticDispatch); |
| } |
| } else if (member is Procedure) { |
| final target = member.reference; |
| addMember(target, staticDispatch); |
| final procedureMetadata = procedureAttributeMetadata[member]!; |
| // `hasTearOffUses` can be true for operators as well, even though |
| // it's not possible to tear-off an operator. (no syntax for it) |
| if (member.kind == ProcedureKind.Method && |
| (procedureMetadata.hasTearOffUses || |
| // If the member can be invoked from a dynamic submodule then |
| // we need to include the tearoff too. |
| member.isDynamicSubmoduleCallable(translator.coreTypes) || |
| classIsDynamicSubmoduleExtendable)) { |
| addMember(member.tearOffReference, staticDispatch); |
| } |
| } |
| } |
| selectorsInClass[cls] = selectors; |
| } |
| |
| final selectorTargets = <SelectorInfo, Map<int, Reference>>{}; |
| for (int classId = minClassId; classId <= maxClassId; ++classId) { |
| final cls = translator.classes[classId].cls; |
| if (cls != null) { |
| selectorsInClass[cls]!.forEach((selectorInfo, target) { |
| if (!target.asMember.isAbstract) { |
| selectorTargets.putIfAbsent(selectorInfo, () => {})[classId] = |
| target; |
| } |
| }); |
| } |
| } |
| |
| _selectorInfo.forEach((_, selector) { |
| bool isDynamicSubmoduleCallable = false; |
| bool isDynamicSubmoduleOverridable = false; |
| bool isDynamicSubmoduleInheritable = false; |
| for (final target in selector._references) { |
| final member = target.asMember; |
| isDynamicSubmoduleOverridable |= |
| member.isDynamicSubmoduleOverridable(translator.coreTypes); |
| isDynamicSubmoduleCallable |= |
| member.isDynamicSubmoduleCallable(translator.coreTypes); |
| isDynamicSubmoduleInheritable |= |
| member.isDynamicSubmoduleInheritable(translator.coreTypes); |
| } |
| selector.isDynamicSubmoduleOverridable = isDynamicSubmoduleOverridable; |
| selector.isDynamicSubmoduleCallable = isDynamicSubmoduleCallable; |
| selector.isDynamicSubmoduleInheritable = isDynamicSubmoduleInheritable; |
| |
| if (!selectorTargets.containsKey(selector)) { |
| // There are no concrete implementations for the given [selector]. |
| selector._normal = SelectorTargets([], []); |
| selector.useMultipleEntryPoints = false; |
| selector._useSentinelForOptionalParameters = true; |
| selector.paramInfo = _parameterInfoFromReferences( |
| selector._references, selector._useSentinelForOptionalParameters); |
| } else { |
| // Will be initialized in the `selectorTargets.forEach()` below. |
| } |
| }); |
| selectorTargets |
| .forEach((SelectorInfo selector, Map<int, Reference> targets) { |
| final List<({Range range, Reference target})> ranges = targets.entries |
| .map((entry) => |
| (range: Range(entry.key, entry.key), target: entry.value)) |
| .toList() |
| ..sort((a, b) => a.range.start.compareTo(b.range.start)); |
| assert(ranges.isNotEmpty); |
| int writeIndex = 0; |
| for (int readIndex = 1; readIndex < ranges.length; ++readIndex) { |
| final current = ranges[writeIndex]; |
| final next = ranges[readIndex]; |
| assert(next.range.length == 1); |
| if ((current.range.end + 1) == next.range.start && |
| identical(current.target, next.target)) { |
| ranges[writeIndex] = ( |
| range: Range(current.range.start, next.range.end), |
| target: current.target |
| ); |
| } else { |
| ranges[++writeIndex] = next; |
| } |
| } |
| ranges.length = writeIndex + 1; |
| |
| bool useMultipleEntryPoints = false; |
| final implementationReferences = <Reference>[]; |
| for (final targetRange in ranges) { |
| final target = targetRange.target; |
| final member = target.asMember; |
| assert(!member.isAbstract); |
| |
| // Compute [useMultipleEntryPoints] |
| if (!member.isExternal && |
| !target.isGetter && |
| !target.isTearOffReference && |
| translator.needToCheckTypesFor(member)) { |
| useMultipleEntryPoints = true; |
| } |
| implementationReferences.add(target); |
| } |
| selector.useMultipleEntryPoints = useMultipleEntryPoints; |
| |
| if (!selector.isDynamicSubmoduleOverridable && |
| implementationReferences.isNotEmpty) { |
| // We have global knowledge of all targets of the selector. We can use |
| // this global knowledge to compute the [ParameterInfo]. |
| selector._references.clear(); |
| selector._references.addAll(implementationReferences); |
| selector._useSentinelForOptionalParameters = false; |
| } else { |
| // Case 1) We may have no targets for the selector, but there may |
| // still be calls to it (see e.g. https://dartbug.com/60733). |
| // |
| // Case 2) We may have 3rd party implementations of the selector |
| // in a dynamic module with unknown default values for optionals. |
| // |
| // => We make caller pass sentinel if the optional parameter is not |
| // provided. |
| selector._useSentinelForOptionalParameters = true; |
| } |
| selector.paramInfo = _parameterInfoFromReferences( |
| selector._references, selector._useSentinelForOptionalParameters); |
| |
| // Split up [ranges] into those that are statically dispatched to and |
| // those are used via dispatch table. |
| final staticDispatchRanges = selector.isDynamicSubmoduleOverridable |
| ? const <({Range range, Reference target})>[] |
| : (translator.options.polymorphicSpecialization || ranges.length == 1) |
| ? ranges |
| : ranges |
| .where( |
| (range) => staticDispatchPragmas.contains(range.target)) |
| .toList(); |
| if (selector.useMultipleEntryPoints) { |
| ({Range range, Reference target}) getChecked( |
| ({Range range, Reference target}) targetRange, |
| bool unchecked, |
| ) => |
| ( |
| range: targetRange.range, |
| target: translator.getFunctionEntry(targetRange.target, |
| uncheckedEntry: unchecked) |
| ); |
| final checkedTargets = SelectorTargets( |
| ranges.map((r) => getChecked(r, false)).toList(), |
| staticDispatchRanges.map((r) => getChecked(r, false)).toList(), |
| ); |
| final uncheckedTargets = SelectorTargets( |
| ranges.map((r) => getChecked(r, true)).toList(), |
| staticDispatchRanges.map((r) => getChecked(r, true)).toList(), |
| ); |
| selector._checked = checkedTargets; |
| selector._unchecked = uncheckedTargets; |
| } else { |
| final normalTargets = SelectorTargets(ranges, staticDispatchRanges); |
| selector._normal = normalTargets; |
| } |
| }); |
| |
| // Assign selector offsets |
| |
| final List<SelectorInfo> selectors = |
| selectorTargets.keys.where(_isUsedViaDispatchTableCall).toList(); |
| |
| // Sort the selectors based on number of targets and number of use sites. |
| // This is a heuristic to keep the table small. |
| // |
| // Place selectors with more targets first as they are less likely to fit |
| // into the gaps left by selectors placed earlier. |
| // |
| // Among the selectors with approximately same number of targets, place |
| // more used ones first, as the smaller selector offset will have a smaller |
| // instruction encoding. |
| int selectorSortWeight(SelectorInfo selector) => |
| selectorTargets[selector]!.length * 10 + selector.callCount; |
| |
| selectors.sort((a, b) => selectorSortWeight(b) - selectorSortWeight(a)); |
| |
| final rows = <Row<Reference>>[]; |
| for (final selector in selectors) { |
| Row<Reference> buildRow( |
| List<({Range range, Reference target})> targetRanges) { |
| final rowValues = <({int index, Reference value})>[]; |
| for (final (:range, :target) in targetRanges) { |
| for (int classId = range.start; classId <= range.end; ++classId) { |
| final adjustedClassId = classId - minClassId; |
| rowValues.add((index: adjustedClassId, value: target)); |
| } |
| } |
| rowValues.sort((a, b) => a.index.compareTo(b.index)); |
| return Row(rowValues); |
| } |
| |
| if (selector.useMultipleEntryPoints) { |
| rows.add(buildRow((selector._checked!.targetRanges))); |
| rows.add(buildRow((selector._unchecked!.targetRanges))); |
| } else { |
| rows.add(buildRow((selector._normal!.targetRanges))); |
| } |
| } |
| |
| _table = buildRowDisplacementTable<Reference>(rows); |
| |
| int rowIndex = 0; |
| for (final selector in selectors) { |
| if (selector.useMultipleEntryPoints) { |
| selector._checked!.offset = rows[rowIndex++].offset; |
| selector._unchecked!.offset = rows[rowIndex++].offset; |
| } else { |
| selector._normal!.offset = rows[rowIndex++].offset; |
| } |
| } |
| |
| _initializeWasmTable(); |
| } |
| |
| void output() { |
| final Map<w.BaseFunction, w.BaseFunction> wrappedDynamicSubmoduleImports = |
| {}; |
| for (int i = 0; i < _table.length; i++) { |
| Reference? target = _table[i]; |
| if (target != null) { |
| w.BaseFunction? fun = translator.functions.getExistingFunction(target); |
| // Any call to the dispatch table is guaranteed to hit a target. |
| // |
| // If a target is in a deferred module and that deferred module hasn't |
| // been loaded yet, then the entry is `null`. |
| // |
| // Though we can only hit a target if that target's class has been |
| // allocated. In order for the class to be allocated, the deferred |
| // module must've been loaded to call the constructor. |
| if (fun != null) { |
| final targetModule = fun.enclosingModule; |
| final targetModuleBuilder = |
| translator.moduleToBuilder[fun.enclosingModule]!; |
| if (targetModule == _definedWasmTable.enclosingModule) { |
| if (isDynamicSubmoduleTable && |
| targetModuleBuilder == translator.dynamicSubmodule && |
| fun is w.ImportedFunction) { |
| // Functions imported into submodules may need to be wrapped to |
| // match the updated dispatch table signature. |
| fun = wrappedDynamicSubmoduleImports[fun] ??= |
| _wrapDynamicSubmoduleFunction(target, fun); |
| } |
| _definedWasmTable.setElement(i, fun); |
| } else { |
| // This will generate the imported table if it doesn't already |
| // exist. |
| (getWasmTable(targetModuleBuilder) as w.ImportedTable) |
| .setElements[i] = fun; |
| } |
| } |
| } |
| } |
| } |
| |
| w.BaseFunction _wrapDynamicSubmoduleFunction( |
| Reference target, w.BaseFunction importedFunction) { |
| final mainSelector = |
| translator.dynamicMainModuleDispatchTable!.selectorForTarget(target); |
| final mainSignature = translator.signatureForMainModule(target); |
| final localSelector = translator.dispatchTable.selectorForTarget(target); |
| final localSignature = localSelector.signature; |
| |
| // If the type is the same in both the main module and the submodule, use |
| // the imported function itself. |
| if (mainSignature.isStructurallyEqualTo(localSignature)) { |
| return importedFunction; |
| } |
| |
| // Otherwise we need to create a wrapper to handle the differing types. |
| // The local signature should include all the parameters necessary to call |
| // the target in main since the local signature must include the target |
| // member itself and any other members in the main module's selector range. |
| final wrapper = translator.dynamicSubmodule.functions |
| .define(localSignature, '${target.asMember} wrapper'); |
| |
| final ib = wrapper.body; |
| |
| assert(mainSignature.inputs.length <= localSignature.inputs.length); |
| |
| final mainModulePreParamCount = |
| (mainSelector.paramInfo.takesContextOrReceiver ? 1 : 0) + |
| mainSelector.paramInfo.typeParamCount; |
| final mainModuleBeforeNamedCount = |
| mainModulePreParamCount + mainSelector.paramInfo.positional.length; |
| int mainIndex = 0; |
| for (; mainIndex < mainModuleBeforeNamedCount; mainIndex++) { |
| final local = ib.locals[mainIndex]; |
| ib.local_get(local); |
| translator.convertType(ib, local.type, mainSignature.inputs[mainIndex]); |
| } |
| |
| final localPreParamCount = |
| (localSelector.paramInfo.takesContextOrReceiver ? 1 : 0) + |
| localSelector.paramInfo.typeParamCount; |
| |
| for (final name in mainSelector.paramInfo.names) { |
| final namedIndex = localSelector.paramInfo.nameIndex[name]!; |
| final local = ib.locals[localPreParamCount + namedIndex]; |
| ib.local_get(local); |
| translator.convertType(ib, local.type, mainSignature.inputs[mainIndex++]); |
| } |
| ib.call(importedFunction); |
| translator.convertType( |
| ib, mainSignature.outputs.single, localSignature.outputs.single); |
| ib.end(); |
| |
| return wrapper; |
| } |
| } |
| |
| bool _isUsedViaDispatchTableCall(SelectorInfo selector) { |
| // If there's no callers in this module and no callers in dynamic modules then |
| // there's no need for us to create a dispatch table entry. |
| if (selector.callCount == 0 && !selector.isDynamicSubmoduleCallable) { |
| return false; |
| } |
| |
| final targets = selector.targets(unchecked: false); |
| |
| // If there's 0 or 1 target than the call sites will either emit an |
| // unreachable or a direct call, so no call site goes via dispatch table, so |
| // we don't need a row in the table. |
| if (targets.targetRanges.length <= 1) return false; |
| |
| // If all targets are dispatched to via static polymorphic dispatchers, |
| // then no callsite will emit a dispatch table call, so we don't need a row in |
| // the table. |
| if (targets.staticDispatchRanges.length == targets.targetRanges.length) { |
| return false; |
| } |
| |
| return true; |
| } |
| |
| ParameterInfo _parameterInfoFromReferences( |
| List<Reference> references, bool useDefaultValueSentinel) { |
| // We know all target implementations (closed world) if all of them use |
| // the same default value for optionals, we can make the caller pass it. |
| final first = references.first; |
| final paramInfo = ParameterInfo.fromMember( |
| first, useDefaultValueSentinel || first.asMember.isAbstract); |
| for (final target in references.skip(1)) { |
| paramInfo.merge(ParameterInfo.fromMember( |
| target, useDefaultValueSentinel || target.asMember.isAbstract)); |
| } |
| return paramInfo; |
| } |
| |
| /// Build a row-displacement table based on fitting the [rows]. |
| /// |
| /// The returned list is the resulting row displacement table with `null` |
| /// entries representing unused space. |
| /// |
| /// The offset of all [Row]s will be initialized. |
| List<V?> buildRowDisplacementTable<V extends Object>(List<Row<V>> rows, |
| {int firstAvailable = 0}) { |
| final table = <V?>[]; |
| for (final row in rows) { |
| final values = row.values; |
| int offset = firstAvailable - values.first.index; |
| bool fits; |
| do { |
| fits = true; |
| for (final value in values) { |
| final int entry = offset + value.index; |
| if (entry >= table.length) { |
| // Fits |
| break; |
| } |
| if (table[entry] != null) { |
| fits = false; |
| break; |
| } |
| } |
| if (!fits) offset++; |
| } while (!fits); |
| row.offset = offset; |
| for (final (:index, :value) in values) { |
| final int tableIndex = offset + index; |
| while (table.length <= tableIndex) { |
| table.add(null); |
| } |
| assert(table[tableIndex] == null); |
| table[tableIndex] = value; |
| } |
| while (firstAvailable < table.length && table[firstAvailable] != null) { |
| firstAvailable++; |
| } |
| } |
| return table; |
| } |
| |
| class Row<V extends Object> { |
| /// The values of the table row, represented sparsely as (index, value) tuples. |
| final List<({int index, V value})> values; |
| |
| /// The given [values] must not be empty and should be sorted by index. |
| Row(this.values) { |
| assert(values.isNotEmpty); |
| assert(() { |
| int previous = values.first.index; |
| for (final value in values.skip(1)) { |
| if (value.index <= previous) return false; |
| previous = value.index; |
| } |
| return true; |
| }()); |
| } |
| |
| /// The selected offset of this row. |
| late final int offset; |
| |
| int get width => values.last.index - values.first.index + 1; |
| int get holes => width - values.length; |
| int get density => (100 * values.length) ~/ width; |
| int get sparsity => 100 - density; |
| } |
