1 | // Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file |
2 | // for details. All rights reserved. Use of this source code is governed by a |
3 | // BSD-style license that can be found in the LICENSE file. |
4 | |
5 | #ifndef RUNTIME_VM_TYPE_TESTING_STUBS_H_ |
6 | #define RUNTIME_VM_TYPE_TESTING_STUBS_H_ |
7 | |
8 | #include "vm/object.h" |
9 | |
10 | #if !defined(DART_PRECOMPILED_RUNTIME) |
11 | #include "vm/compiler/assembler/assembler.h" |
12 | #include "vm/compiler/backend/il.h" |
13 | #include "vm/compiler/stub_code_compiler.h" |
14 | #endif // !defined(DART_PRECOMPILED_RUNTIME) |
15 | |
16 | namespace dart { |
17 | |
18 | class TypeTestingStubNamer { |
19 | public: |
20 | TypeTestingStubNamer(); |
21 | |
22 | // Simple helper for stringinfying a [type] and prefix it with the type |
23 | // testing |
24 | // |
25 | // (only during dart_boostrap). |
26 | const char* StubNameForType(const AbstractType& type) const; |
27 | |
28 | private: |
29 | const char* StringifyType(const AbstractType& type) const; |
30 | static const char* AssemblerSafeName(char* cname); |
31 | |
32 | Library& lib_; |
33 | Class& klass_; |
34 | AbstractType& type_; |
35 | TypeArguments& type_arguments_; |
36 | String& string_; |
37 | }; |
38 | |
39 | class TypeTestingStubGenerator { |
40 | public: |
41 | // During bootstrapping it will return `null` for |void| and |dynamic| types, |
42 | // otherwise it will return a default stub which tail-calls |
43 | // subtypingtest/runtime code. |
44 | static CodePtr DefaultCodeForType(const AbstractType& type, |
45 | bool lazy_specialize = true); |
46 | |
47 | #if !defined(DART_PRECOMPILED_RUNTIME) |
48 | static void SpecializeStubFor(Thread* thread, const AbstractType& type); |
49 | #endif |
50 | |
51 | TypeTestingStubGenerator(); |
52 | |
53 | // Creates new stub for [type] (and registers the tuple in object store |
54 | // array) or returns default stub. |
55 | CodePtr OptimizedCodeForType(const AbstractType& type); |
56 | |
57 | private: |
58 | #if !defined(TARGET_ARCH_IA32) |
59 | #if !defined(DART_PRECOMPILED_RUNTIME) |
60 | CodePtr BuildCodeForType(const Type& type); |
61 | static void BuildOptimizedTypeTestStub( |
62 | compiler::Assembler* assembler, |
63 | compiler::UnresolvedPcRelativeCalls* unresolved_calls, |
64 | const Code& slow_type_test_stub, |
65 | HierarchyInfo* hi, |
66 | const Type& type, |
67 | const Class& type_class); |
68 | |
69 | static void BuildOptimizedTypeTestStubFastCases( |
70 | compiler::Assembler* assembler, |
71 | HierarchyInfo* hi, |
72 | const Type& type, |
73 | const Class& type_class); |
74 | |
75 | static void BuildOptimizedSubtypeRangeCheck(compiler::Assembler* assembler, |
76 | const CidRangeVector& ranges, |
77 | bool smi_is_ok); |
78 | |
79 | static void BuildOptimizedSubclassRangeCheckWithTypeArguments( |
80 | compiler::Assembler* assembler, |
81 | HierarchyInfo* hi, |
82 | const Type& type, |
83 | const Class& type_class, |
84 | const TypeArguments& type_parameters, |
85 | const TypeArguments& type_arguments); |
86 | |
87 | static void BuildOptimizedSubclassRangeCheckWithTypeArguments( |
88 | compiler::Assembler* assembler, |
89 | HierarchyInfo* hi, |
90 | const Type& type, |
91 | const Class& type_class, |
92 | const TypeArguments& type_parameters, |
93 | const TypeArguments& type_arguments, |
94 | const Register class_id_reg, |
95 | const Register instance_type_args_reg); |
96 | |
97 | static void BuildOptimizedSubclassRangeCheck(compiler::Assembler* assembler, |
98 | const CidRangeVector& ranges, |
99 | compiler::Label* check_failed); |
100 | |
101 | static void BuildOptimizedTypeArgumentValueCheck( |
102 | compiler::Assembler* assembler, |
103 | HierarchyInfo* hi, |
104 | const AbstractType& type_arg, |
105 | intptr_t type_param_value_offset_i, |
106 | compiler::Label* check_failed); |
107 | |
108 | #endif // !defined(DART_PRECOMPILED_RUNTIME) |
109 | #endif // !defined(TARGET_ARCH_IA32) |
110 | |
111 | TypeTestingStubNamer namer_; |
112 | ObjectStore* object_store_; |
113 | }; |
114 | |
115 | template <typename T> |
116 | class ReusableHandleStack { |
117 | public: |
118 | explicit ReusableHandleStack(Zone* zone) : zone_(zone), handles_count_(0) {} |
119 | |
120 | private: |
121 | T* Obtain() { |
122 | T* handle; |
123 | if (handles_count_ < handles_.length()) { |
124 | handle = handles_[handles_count_]; |
125 | } else { |
126 | handle = &T::ZoneHandle(zone_); |
127 | handles_.Add(handle); |
128 | } |
129 | handles_count_++; |
130 | return handle; |
131 | } |
132 | |
133 | void Release(T* handle) { |
134 | handles_count_--; |
135 | ASSERT(handles_count_ >= 0); |
136 | ASSERT(handles_[handles_count_] == handle); |
137 | } |
138 | |
139 | Zone* zone_; |
140 | |
141 | intptr_t handles_count_; |
142 | MallocGrowableArray<T*> handles_; |
143 | |
144 | template <typename U> |
145 | friend class ScopedHandle; |
146 | }; |
147 | |
148 | template <typename T> |
149 | class ScopedHandle { |
150 | public: |
151 | explicit ScopedHandle(ReusableHandleStack<T>* stack) |
152 | : stack_(stack), handle_(stack_->Obtain()) {} |
153 | |
154 | ~ScopedHandle() { stack_->Release(handle_); } |
155 | |
156 | T& operator*() { return *handle_; } |
157 | T* operator->() { return handle_; } |
158 | |
159 | private: |
160 | ReusableHandleStack<T>* stack_; |
161 | T* handle_; |
162 | }; |
163 | |
164 | // Attempts to find a [Class] from un-instantiated [TypeArgument] vector to |
165 | // which it's type parameters are referring to. |
166 | // |
167 | // If the given type argument vector contains references to type parameters, |
168 | // this finder will either return a valid class if all of the type parameters |
169 | // come from the same class and returns `null` otherwise. |
170 | // |
171 | // It is safe to use this class inside loops since the implementation uses a |
172 | // [ReusableHandleStack] (which in pratice will only use a handful of handles). |
173 | class TypeArgumentClassFinder { |
174 | public: |
175 | explicit TypeArgumentClassFinder(Zone* zone) |
176 | : klass_(Class::Handle(zone)), |
177 | type_(AbstractType::Handle(zone)), |
178 | type_arguments_handles_(zone) {} |
179 | |
180 | const Class& FindClass(const TypeArguments& ta) { |
181 | klass_ = Class::null(); |
182 | |
183 | const intptr_t len = ta.Length(); |
184 | for (intptr_t i = 0; i < len; ++i) { |
185 | type_ = ta.TypeAt(i); |
186 | if (!FindClassFromType(type_)) { |
187 | klass_ = Class::null(); |
188 | break; |
189 | } |
190 | } |
191 | return klass_; |
192 | } |
193 | |
194 | private: |
195 | bool FindClassFromType(const AbstractType& type) { |
196 | if (type.IsTypeParameter()) { |
197 | const TypeParameter& parameter = TypeParameter::Cast(type); |
198 | if (!parameter.IsClassTypeParameter()) { |
199 | return false; |
200 | } |
201 | if (klass_.IsNull()) { |
202 | klass_ = parameter.parameterized_class(); |
203 | } else { |
204 | // Dart has no support for nested classes. |
205 | ASSERT(klass_.raw() == parameter.parameterized_class()); |
206 | } |
207 | return true; |
208 | } else if (type.IsFunctionType()) { |
209 | // No support for function types yet. |
210 | return false; |
211 | } else if (type.IsTypeRef()) { |
212 | // No support for recursive types. |
213 | return false; |
214 | } else if (type.IsType()) { |
215 | ScopedHandle<TypeArguments> type_arguments(&type_arguments_handles_); |
216 | *type_arguments = Type::Cast(type).arguments(); |
217 | const intptr_t len = type_arguments->Length(); |
218 | for (intptr_t i = 0; i < len; ++i) { |
219 | type_ = type_arguments->TypeAt(i); |
220 | if (!FindClassFromType(type_)) { |
221 | return false; |
222 | } |
223 | } |
224 | return true; |
225 | } |
226 | UNREACHABLE(); |
227 | return false; |
228 | } |
229 | |
230 | Class& klass_; |
231 | AbstractType& type_; |
232 | |
233 | ReusableHandleStack<TypeArguments> type_arguments_handles_; |
234 | }; |
235 | |
236 | // Used for instantiating a [TypeArguments] which contains references to type |
237 | // parameters based on an instantiator [TypeArguments] vector. |
238 | // |
239 | // It is safe to use this class inside loops since the implementation uses a |
240 | // [ReusableHandleStack] (which in pratice will only use a handful of handles). |
241 | class TypeArgumentInstantiator { |
242 | public: |
243 | explicit TypeArgumentInstantiator(Zone* zone) |
244 | : klass_(Class::Handle(zone)), |
245 | type_(AbstractType::Handle(zone)), |
246 | instantiator_type_arguments_(TypeArguments::Handle(zone)), |
247 | type_arguments_handles_(zone), |
248 | type_handles_(zone) {} |
249 | |
250 | TypeArgumentsPtr Instantiate( |
251 | const Class& klass, |
252 | const TypeArguments& type_arguments, |
253 | const TypeArguments& instantiator_type_arguments) { |
254 | instantiator_type_arguments_ = instantiator_type_arguments.raw(); |
255 | return InstantiateTypeArguments(klass, type_arguments).raw(); |
256 | } |
257 | |
258 | private: |
259 | const TypeArguments& InstantiateTypeArguments( |
260 | const Class& klass, |
261 | const TypeArguments& type_arguments); |
262 | |
263 | AbstractTypePtr InstantiateType(const AbstractType& type); |
264 | |
265 | Class& klass_; |
266 | AbstractType& type_; |
267 | TypeArguments& instantiator_type_arguments_; |
268 | |
269 | ReusableHandleStack<TypeArguments> type_arguments_handles_; |
270 | ReusableHandleStack<Type> type_handles_; |
271 | }; |
272 | |
273 | // Collects data on how [Type] objects are used in generated code. |
274 | class TypeUsageInfo : public ThreadStackResource { |
275 | public: |
276 | explicit TypeUsageInfo(Thread* thread); |
277 | ~TypeUsageInfo(); |
278 | |
279 | void UseTypeInAssertAssignable(const AbstractType& type); |
280 | void UseTypeArgumentsInInstanceCreation(const Class& klass, |
281 | const TypeArguments& ta); |
282 | |
283 | // Finalize the collected type usage information. |
284 | void BuildTypeUsageInformation(); |
285 | |
286 | // Query if [type] is very likely used in a type test (can give |
287 | // false-positives and false-negatives, but tries to make a very good guess) |
288 | bool IsUsedInTypeTest(const AbstractType& type); |
289 | |
290 | private: |
291 | template <typename T> |
292 | class ObjectSetTrait { |
293 | public: |
294 | // Typedefs needed for the DirectChainedHashMap template. |
295 | typedef const T* Key; |
296 | typedef const T* Value; |
297 | typedef const T* Pair; |
298 | |
299 | static Key KeyOf(Pair kv) { return kv; } |
300 | static Value ValueOf(Pair kv) { return kv; } |
301 | static inline intptr_t Hashcode(Key key) { return key->Hash(); } |
302 | }; |
303 | |
304 | class TypeSetTrait : public ObjectSetTrait<const AbstractType> { |
305 | public: |
306 | static inline bool IsKeyEqual(const AbstractType* pair, |
307 | const AbstractType* key) { |
308 | return pair->Equals(*key); |
309 | } |
310 | }; |
311 | |
312 | class TypeArgumentsSetTrait : public ObjectSetTrait<const TypeArguments> { |
313 | public: |
314 | static inline bool IsKeyEqual(const TypeArguments* pair, |
315 | const TypeArguments* key) { |
316 | return pair->raw() == key->raw(); |
317 | } |
318 | }; |
319 | |
320 | class TypeParameterSetTrait : public ObjectSetTrait<const TypeParameter> { |
321 | public: |
322 | static inline bool IsKeyEqual(const TypeParameter* pair, |
323 | const TypeParameter* key) { |
324 | return pair->raw() == key->raw(); |
325 | } |
326 | }; |
327 | |
328 | typedef DirectChainedHashMap<TypeSetTrait> TypeSet; |
329 | typedef DirectChainedHashMap<TypeArgumentsSetTrait> TypeArgumentsSet; |
330 | typedef DirectChainedHashMap<TypeParameterSetTrait> TypeParameterSet; |
331 | |
332 | // Runs an (early terminated) fix-point algorithm which propagates type |
333 | // arguments. For example: |
334 | // |
335 | // class Base<X> {} |
336 | // |
337 | // class Foo<A, B> extends Base<B> { |
338 | // foo() => new Map<List<B>, A>(); |
339 | // } |
340 | // |
341 | // main() { |
342 | // new Foo<String, int>(); |
343 | // new Map<double, bool>(); |
344 | // } |
345 | // |
346 | // will end up adding new type argument vectors to the per-class instantiator |
347 | // type argument vector set: |
348 | // |
349 | // Foo: |
350 | // <int, String, int> |
351 | // Map: |
352 | // <List<int>, String> |
353 | // <double, bool> |
354 | // |
355 | void PropagateTypeArguments(ClassTable* class_table, intptr_t cid_count); |
356 | |
357 | // Collects all type parameters we are doing assert assignable checks against. |
358 | void CollectTypeParametersUsedInAssertAssignable(TypeParameterSet* set); |
359 | |
360 | // All types which flow into any of the type parameters in [set] will be added |
361 | // to the set of types we test against. |
362 | void UpdateAssertAssignableTypes(ClassTable* class_table, |
363 | intptr_t cid_count, |
364 | TypeParameterSet* set); |
365 | |
366 | void AddToSetIfParameter(TypeParameterSet* set, |
367 | const AbstractType* type, |
368 | TypeParameter* param); |
369 | void AddTypeToSet(TypeSet* set, const AbstractType* type); |
370 | |
371 | Zone* zone_; |
372 | TypeArgumentClassFinder finder_; |
373 | TypeSet assert_assignable_types_; |
374 | TypeArgumentsSet* instance_creation_arguments_; |
375 | |
376 | Class& klass_; |
377 | }; |
378 | |
379 | #if !defined(DART_PRECOMPILED_RUNTIME) |
380 | void RegisterTypeArgumentsUse(const Function& function, |
381 | TypeUsageInfo* type_usage_info, |
382 | const Class& klass, |
383 | Definition* type_arguments); |
384 | #endif |
385 | |
386 | #if !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME) |
387 | |
388 | void DeoptimizeTypeTestingStubs(); |
389 | |
390 | #endif // !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME) |
391 | |
392 | } // namespace dart |
393 | |
394 | #endif // RUNTIME_VM_TYPE_TESTING_STUBS_H_ |
395 | |