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
16namespace dart {
17
18class 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
39class 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
115template <typename T>
116class 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
148template <typename T>
149class 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).
173class 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).
241class 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.
274class 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)
380void 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
388void DeoptimizeTypeTestingStubs();
389
390#endif // !defined(PRODUCT) && !defined(DART_PRECOMPILED_RUNTIME)
391
392} // namespace dart
393
394#endif // RUNTIME_VM_TYPE_TESTING_STUBS_H_
395