1 // Copyright 2022 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/wasm/canonical-types.h"
6
7 #include "src/wasm/wasm-engine.h"
8
9 namespace v8 {
10 namespace internal {
11 namespace wasm {
12
GetTypeCanonicalizer()13 V8_EXPORT_PRIVATE TypeCanonicalizer* GetTypeCanonicalizer() {
14 return GetWasmEngine()->type_canonicalizer();
15 }
16
AddRecursiveGroup(WasmModule * module,uint32_t size)17 void TypeCanonicalizer::AddRecursiveGroup(WasmModule* module, uint32_t size) {
18 // Multiple threads could try to register recursive groups concurrently.
19 // TODO(manoskouk): Investigate if we can fine-grain the synchronization.
20 base::MutexGuard mutex_guard(&mutex_);
21 DCHECK_GE(module->types.size(), size);
22 uint32_t start_index = static_cast<uint32_t>(module->types.size()) - size;
23 CanonicalGroup group;
24 group.types.resize(size);
25 for (uint32_t i = 0; i < size; i++) {
26 group.types[i] = CanonicalizeTypeDef(module, module->types[start_index + i],
27 start_index);
28 }
29 int canonical_index = FindCanonicalGroup(group);
30 if (canonical_index >= 0) {
31 // Identical group found. Map new types to the old types's canonical
32 // representatives.
33 for (uint32_t i = 0; i < size; i++) {
34 module->isorecursive_canonical_type_ids[start_index + i] =
35 canonical_index + i;
36 }
37 } else {
38 // Identical group not found. Add new canonical representatives for the new
39 // types.
40 uint32_t first_canonical_index =
41 static_cast<uint32_t>(canonical_supertypes_.size());
42 canonical_supertypes_.resize(first_canonical_index + size);
43 for (uint32_t i = 0; i < size; i++) {
44 CanonicalType& canonical_type = group.types[i];
45 // Compute the canonical index of the supertype: If it is relative, we
46 // need to add {first_canonical_index}.
47 canonical_supertypes_[first_canonical_index + i] =
48 canonical_type.is_relative_supertype
49 ? canonical_type.type_def.supertype + first_canonical_index
50 : canonical_type.type_def.supertype;
51 module->isorecursive_canonical_type_ids[start_index + i] =
52 first_canonical_index + i;
53 }
54 canonical_groups_.emplace(group, first_canonical_index);
55 }
56 }
57
58 // An index in a type gets mapped to a relative index if it is inside the new
59 // canonical group, or the canonical representative if it is not.
CanonicalizeValueType(const WasmModule * module,ValueType type,uint32_t recursive_group_start) const60 ValueType TypeCanonicalizer::CanonicalizeValueType(
61 const WasmModule* module, ValueType type,
62 uint32_t recursive_group_start) const {
63 if (!type.has_index()) return type;
64 return type.ref_index() >= recursive_group_start
65 ? ValueType::CanonicalWithRelativeIndex(
66 type.kind(), type.ref_index() - recursive_group_start)
67 : ValueType::FromIndex(
68 type.kind(),
69 module->isorecursive_canonical_type_ids[type.ref_index()]);
70 }
71
IsCanonicalSubtype(uint32_t sub_index,uint32_t super_index,const WasmModule * sub_module,const WasmModule * super_module)72 bool TypeCanonicalizer::IsCanonicalSubtype(uint32_t sub_index,
73 uint32_t super_index,
74 const WasmModule* sub_module,
75 const WasmModule* super_module) {
76 // Multiple threads could try to register and access recursive groups
77 // concurrently.
78 // TODO(manoskouk): Investigate if we can improve this synchronization.
79 base::MutexGuard mutex_guard(&mutex_);
80 uint32_t canonical_super =
81 super_module->isorecursive_canonical_type_ids[super_index];
82 uint32_t canonical_sub =
83 sub_module->isorecursive_canonical_type_ids[sub_index];
84 while (canonical_sub != kNoSuperType) {
85 if (canonical_sub == canonical_super) return true;
86 canonical_sub = canonical_supertypes_[canonical_sub];
87 }
88 return false;
89 }
90
91 // Map all type indices (including supertype) inside {type} to indices relative
92 // to {recursive_group_start}.
CanonicalizeTypeDef(const WasmModule * module,TypeDefinition type,uint32_t recursive_group_start)93 TypeCanonicalizer::CanonicalType TypeCanonicalizer::CanonicalizeTypeDef(
94 const WasmModule* module, TypeDefinition type,
95 uint32_t recursive_group_start) {
96 uint32_t canonical_supertype = kNoSuperType;
97 bool is_relative_supertype = false;
98 if (type.supertype < recursive_group_start) {
99 canonical_supertype =
100 module->isorecursive_canonical_type_ids[type.supertype];
101 } else if (type.supertype != kNoSuperType) {
102 canonical_supertype = type.supertype - recursive_group_start;
103 is_relative_supertype = true;
104 }
105 TypeDefinition result;
106 switch (type.kind) {
107 case TypeDefinition::kFunction: {
108 const FunctionSig* original_sig = type.function_sig;
109 FunctionSig::Builder builder(&zone_, original_sig->return_count(),
110 original_sig->parameter_count());
111 for (ValueType ret : original_sig->returns()) {
112 builder.AddReturn(
113 CanonicalizeValueType(module, ret, recursive_group_start));
114 }
115 for (ValueType param : original_sig->parameters()) {
116 builder.AddParam(
117 CanonicalizeValueType(module, param, recursive_group_start));
118 }
119 result = TypeDefinition(builder.Build(), canonical_supertype);
120 break;
121 }
122 case TypeDefinition::kStruct: {
123 const StructType* original_type = type.struct_type;
124 StructType::Builder builder(&zone_, original_type->field_count());
125 for (uint32_t i = 0; i < original_type->field_count(); i++) {
126 builder.AddField(CanonicalizeValueType(module, original_type->field(i),
127 recursive_group_start),
128 original_type->mutability(i));
129 }
130 result = TypeDefinition(builder.Build(), canonical_supertype);
131 break;
132 }
133 case TypeDefinition::kArray: {
134 ValueType element_type = CanonicalizeValueType(
135 module, type.array_type->element_type(), recursive_group_start);
136 result = TypeDefinition(
137 zone_.New<ArrayType>(element_type, type.array_type->mutability()),
138 canonical_supertype);
139 break;
140 }
141 }
142
143 return {result, is_relative_supertype};
144 }
145
146 // Returns the index of the canonical representative of the first type in this
147 // group, or -1 if an identical group does not exist.
FindCanonicalGroup(CanonicalGroup & group) const148 int TypeCanonicalizer::FindCanonicalGroup(CanonicalGroup& group) const {
149 auto element = canonical_groups_.find(group);
150 return element == canonical_groups_.end() ? -1 : element->second;
151 }
152
153 } // namespace wasm
154 } // namespace internal
155 } // namespace v8
156